dxdt.blog: занимательный интернет-журнал

Кстати, в продолжение теоретико-числовых аспектов “Начал” Евклида. Смотрю тут книгу Бориса Трушина для школьников по теории чисел – “Теория чисел: с нуля до теоремы Эйлера”. На странице 66 там, под названием “Теорема Евклида”, приводится утверждение о том, что “простых чисел бесконечно много”, и доказательство – от противного: примем, что простых – конечное количество, перемножим их все, прибавим единицу, заметим, что результат не делится ни на одно из простых, – противоречие. Это типовое доказательство, которое встречается во многих учебниках. Почему приводят именно его – не очень понятно, но такова традиция. Однако, заметьте, в книге Трушина доказательство не названо “доказательством Евклида”. И это правильно. Почему? Потому, что Евклид-то доказывал данное утверждение не так. Евклид доказывал несколько более конструктивно.

Собственно, даже исходное предложение Евклида (9.20) сформулировано иначе: “простых чисел больше, чем в любом заданном (конечном) наборе простых чисел”. Может показаться, что это такая же формулировка, как и про “бесконечно много”, но, логически, это не так – Евклид не постулирует тут никакой бесконечности “от противного”, не рассматривает “все простые”, а использует конструктивный подход: даёте конкретный список простых чисел, и вот метод, по которому можно построить такое простое, которого не будет в этом списке. И доказательство у Евклида не от противного. Оно, что называется, более “конструктивное” (в той же мере, что и формулировка).

Логика исходного доказательства Евклида: выберем любые три простых числа A, B, C; возьмём наименьшее D, которое делится на A, B и C; прибавим к D единицу, получив число N = D + 1. (Обратите внимание, что единица здесь – это единица в евклидовом смысле, то есть, неделимый элемент.) Полученное число N либо является простым, которое не вошло в исходный список (утверждение, в этом случае, доказано), либо N – составное, и тогда N делится на какое-то простое (обратите внимание на этот момент – к нему ещё вернёмся ниже). Обозначим простое число, на которое делится N, буквой M. Если M – число из исходного списка [A, B, C], то M делит и D (по построению D). Следовательно, раз M делит и N, и D, то оно делит и разность N – D, но эта разность есть единица, и M не может её делить. Следовательно, M не входит в исходный список [A, B, C] – мы нашли новое простое число. То есть, тут показан достаточно конкретный способ конструирования нужных чисел, и это совсем другая история, чем постулирование “актуальной” бесконечности. Тем не менее, в учебниках регулярно приводят именно “доказательство от противного”, хоть оно и не является доказательством Евклида.

В доказательстве “от противного” фигурирует произведение всех простых. Если забыть, что это произведение всех простых, то нетрудно сделать ошибочный вывод, что можно всегда получить простое число, перемножив несколько последовательных простых и прибавив единицу. Это неприятный момент неверного обобщения результата, который полностью отсутствует в исходном доказательстве Евклида (см. выше). То есть, например, 2*3*5*7*11 + 1 = 2311 (простое), но это не означает, что просты и все такие числа (которые называют числами Евклида). Надо сказать, что в книге Трушина, как раз, сразу же, после доказательства теоремы Евклида этот, – наверное, самый важный, – момент подробно рассмотрен и показано, что уже 2*3*5*7*11*13 + 1 = 30031 = 59 * 509.

Книгу Трушина, кстати, порекомендую (и далеко не только школьникам). Там, конечно, есть несколько наивный небольшой раздел про применение теории чисел в криптографии, написанный, почему-то, на примере RSA, для которой проводится странное “сращивание” с шифрами простой замены. Это при том, что, конечно, RSA возникла из совсем другой задачи – из задачи распределения ключей, – а не из задачи зашифрования информации: для зашифрования были известны и абсолютно стойкий симметричный шифр, и симметричные же “комбинаторные” шифры, обладающие высокой стойкостью; более того, и наивный “побуквенный” шифр замены можно сделать очень стойким, пусть и простым в применении (возьмите колоду карт, скажем, и книгу). Но это всё специальные детали, которые я не смог пропустить в силу тематики dxdt.blog. И, конечно, к данному разделу в книге поставлена сноска, в которой прямо указано, что реальное применение RSA – сложнее, и совсем не такое, как описано. Так что, на содержательную часть – не влияет.

Небольшое воскресное чтение манускриптов. Точнее – рассматривание чертежа из “Начал” Евклида, в версии манускрипта Vat.gr 190 девятого века. Это чертёж к Предложению 20 девятой книги, то есть, к доказательству того, что количество простых чисел больше, чем их есть в любом наперёд заданном (конечном) списке.

На чертеже почти все величины, используемые в доказательстве Предложения, обозначены отрезками одинаковой длины. Это довольно странно, а отчасти – загадочно, но именно так на старых манускриптах даны почти все чертежи для теоретико-числовых Предложений из “Начал”.

Другими словами, в доказательстве здесь используется три различных простых числа – ΑΒΓ, – это натуральные числа, но на рисунке их величины обозначены отрезками одинаковой длины. Причём, в более или менее современных переводах – отрезки на чертеже уже будут разными: очевидно, что трём разным натуральным числам не могут соответствовать отрезки одинаковой длины; ну, если только не считать эти отрезки совсем абстрактным представлением – тогда, конечно, длина на чертеже не важна: не рисуют же прямые углы, скажем, как строго прямые (вообще невозможно нарисовать прямой угол).

ΕΔ здесь – это отрезок, измеримый Α, Β и Γ, то есть, если на современный лад, произведение ΑΒΓ, а ΔΖ – единица (в евклидовом смысле), которая добавляется к ΕΔ, что даёт ΕΖ. Ну а Η – это отрезок, обозначающий простое число, которое измеряет ΕΖ (делит). И опять – одинаковой длины с ΕΔ.

Часто попадаются фразы, что, например, алгоритм ML-KEM – это алгоритм, “стойкий к подбору на квантовом компьютере”. Вопрос, конечно, терминологический, но попробуем разобраться, почему такая формулировка (“стойкий к подбору”) – не верная, и почему так писать нежелательно.

Более или менее строгое определение: “ML-KEM, теоретически, обладает стойкостью к взлому при помощи алгоритма Шора”.

Дело в том, что, во-первых, никто не доказал и не доказывал, что ML-KEM – стоек к “подбору на квантовом компьютере”, потому что непонятно, что такое “подбор на квантовом компьютере”: ведь нет даже “устойчивого” определения квантового компьютера, что уж там говорить о возможностях теоретического подбора. Из всех криптоаналитических приложений гипотетических квантовых компьютеров – более или менее описаны только гипотетические реализации алгоритма Шора. И вот, при некоторых допущениях (количество “кубитов”, что бы это ни значило, количество “ячеек пямяти” и т.д., и т.п.), определение секрета, передаваемого при помощи ML-KEM, на основе открытых параметров и данных, и даже при помощи компьютера, эффективно реализующего алгоритм Шора, оказывается вычислительно сложным – то есть, в теории, потребует слишком много ресурсов.

Однако здесь “эффективно реализующего алгоритм Шора” – это просто характеристика компьютера, который, вообще говоря, полагается универсальным (в текущей, так сказать, степени понимания “универсальности”). Впрочем, заметьте, что основной исходный посыл тут – это именно “неприменимость” алгоритма Шора. Так что определение про “стойкость к алгоритму Шора” – тоже верное. Потому что те криптосистемы, на замену которым предложен алгоритм ML-KEM, – разновидности ECDH, RSA и др., – уязвимы именно к алгоритму Шора.

(Кстати, почему тут можно смело говорить, что “к алгоритму Шора”, не упоминая “квантовый компьютер”? Потому, что это эффективное выполнение алгоритма Шора возможно только при наличии подходящего квантового компьютера, но сам алгоритм – можно “запускать” и чисто на классическом компьютере: да, времени потребуется экспоненциально больше, смысл теряется даже для коротких ключей, но это ж не мешает запуску и исполнению, верно? Будет “не квантово”, но, да, верно. Отсюда и стойкость.)

Во-вторых, никто не доказал, что невозможны другие “квантовые алгоритмы”, которые, – на подходящем, но гипотетически реализуемом, квантовом компьютере, – будут успешно и быстро взламывать ML-KEM. А если учитывать, что модели квантовых вычислений легко оперируют континуумом (синусы/косинусы и действительные числа), то, вообще говоря, не стоит делать ставку на то, что теоретический “квантовый алгоритм подбора ML-KEM” не придумают в обозримом будущем. Более того, сейчас распространено мнение, что в том самом обозримом будущем гораздо более вероятно появление практической классической атаки на ML-KEM, чем появление квантовых компьютеров, способных сломать ту же X25519 (разновидность ECDH) алгоритмом Шора. То есть, криптосистема ML-KEM может оказаться уязвима для обычных компьютеров, а X25519 и другие современные варианты ECDH – сохранят классическую стойкость.

Как же вообще нужно именовать эти криптосистемы, типа ML-KEM? Например, я и сам регулярно использую термин “криптосистемы с постквантовой стойкостью”, но это тоже не слишком-то хороший вариант, поскольку, откровенно говоря, он не так далеко ушёл от стойкости “к подбору на квантовом компьютере”, как хотелось бы. Конечно, “постквантовая стойкость” здесь – это стойкость к алгоритму Шора. Но это лишь подразумевается, а сам термин – чрезмерно широкий. Видимо, наилучший вариант, который уже сложился исторически, это просто “постквантовые криптосистемы”. То есть, такие криптосистемы, которые предлагается использовать после появления доступных универсальных квантовых компьютеров, и акцент тут – на слове “универсальных”.

Заменил адрес технического описания TLS, которое я поддерживаю, на tls.dxdt.blog (старый адрес, – tls.dxdt.ru, – пока работает, показывает на тот же узел, но там я сделал HTTP-редирект на новый адрес).

Хроники разваливающихся интернетов. Я, в силу ряда причин, использую DNS-резолвер, который установлен за пределами Рунета. С некоторых пор я заметил, что ряд вспомогательных сервисов для аккаунта Google – недоступны из браузера, из моей локальной сети. А я всё ещё использую для ряда задач почту Google – так исторически сложилось, тем более, что, в отличие от того же “Яндекса”, Google мне пока что эту историческую почту и кучу прочих сервисов под моим доменом (из Рунета, заметьте) предоставляет бесплатно, как ни странно; не знаю, долго ли ещё так будет, но пока что – так; недостатки там тоже есть, кто бы сомневался, но это другая история: а сервис, как минимум, никто за эти десятилетия у меня не отобрал – очень существенный плюс Google, по нынешним временам-то.

Вернёмся, впрочем, к доступности.

Итак, я заметил, что какие-то сервисы через HTTPS недоступны, а они необходимы для нормальной работы веб-интерфейса (там всё управление – через веб). Логичное предположение: так как мой резолвер приходит на авторитативные серверы Google из “иностранной сети”, ему DNS Google отдаёт другие IP-адреса, а именно – адреса, предназначенные для соответствующего региона; и узлы под этими IP-адресами – недоступны из российских сетей. Почему это влияет? Потому что браузером-то я подключаюсь из российской IP-сети. Где именно соответствующий трафик забанен – я уже не стал разбираться: сейчас подобное разбирательство – легко превращается в длительное исследование, так как понять, “что-как-где-почему”, довольно сложно: сети окончательно стали мутными на прикладном уровне. Да, я делал бы ставку на то, что забанено на российском транзите; но, к сожалению, тут нельзя полностью исключать и сторону CDN Google – вообще говоря, агрессивная геобалансировка на стороне крупнейших провайдеров была известна и раньше, иногда, скажем, такая блокировка может быть побочным эффектом маршрутизации для anycast-адресов (отдельная история).

В общем, я просто добавил на сторне своего DNS-резолвера функцию отправки подсети-источника DNS-запроса в ECS, но только для доменов внутри зоны google.com, чтобы авторитативные DNS-серверы на той стороне видели целевой IP-префикс запроса. В Unbound (весьма рекомендую, кстати) избирательная поддержка ECS легко включается. После того, как в запросы добавились ECS – IP-адреса в ответных A-записях стали приходить другие, а сервис Google – тут же заработал из локальной сети. Да, откровенно говоря, не могу исключить, что это совпадение, но посмотрим: в других, – более прозрачных, но аналогичных, – случаях, с которыми я сталкивался, подход с перенастройкой резолвера срабатывал эффективно.

В 2020 году я писал о том, что Starlink может послужить основой для замены GPS, потому что подобная спутниковая система имеет большие преимущества перед типовой GNSS: например, тут есть двунаправленная связь с широкой полосой и поэтому низколетящие спутники могут синхронно “наблюдать” наземный передатчик, да ещё и с разных углов, потому что спутников много. С 2020 года, кстати, спутников-то стало сильно больше – система обрела некоторую неуязвимость от целевых атак на отдельные аппараты.

Прошло почти шесть лет, и вот Arstechnica сообщает, что в гражданском Starlink собираются отключить доступный API для получения геолокации со стороны терминала. Понятно, что это не та точная система, которая планировалась, и что внутренняя система позиционирования и геопривязки останется: без определения координат, да в обе стороны, – схема не сможет эффективно работать, поэтому речь только про отключение простого, произвольного доступа к внешнему API (скорее всего, потом предоставят на замену что-нибудь платное, но с ограничениями). Заметьте, что за прошедшие годы наверняка сильно продвинули в плане решения навигационных задач закрытый вариант Starlink – это выделенная низкоорбитальная система военного назначения, часть которой на официальном сайте именуется Starshield.

У меня в GitHub тоже есть аккаунт, которым, впрочем, я почти не пользуюсь. Но это не отменяет важности GitHub, конечно. Я под своим там аккаунтом довольно давно опубликовал реализацию шифра “Кузнечик” с оптимизацией на ассемблере Go (гораздо более новая версия, с поддержкой ARM64, есть у меня на сайте, если это вообще кому-то нужно). Кроме того, на GitHub я как-то выложил Runic32 – реализация Base32 на алфавите из англосаксонских рун (“футарк/футорк”, условно говоря). Этот проект является шуточным – потому что как-то зашёл разговор о том, что “TLS-сертификаты отображаются какими-то крючками”: ну, вот, при помощи утилты runic32 можно сертификаты записывать прямо рунами (если есть Unicode).

При этом, как ни странно, но аккаунт в данной “социальной сети” GitHub (известная филологическая английская шутка) я завёл для того, чтобы написать в один из проектов IETF, которая IETF, следуя странной моде, перенесла основную часть своей деятельности по подготовке стандартов в GitHub (спорное решение, мягко говоря). К сожалению, реальность такова, что, фактически, сейчас без GitHub мало что из “рабочих вопросов”, для меня, обходится: начать с того, что с GitHub среди разработчиков принято тянуть очень много из критически важных библиотек, а какие-то библиотеки – просто негде взять удобным способом: скажем, вот полезнейшая CIRCL от Cloudflare.

Я сам сторонник того, чтобы написать всё своё. Да, именно так, и большой плюс – если на ассемблере. Однако, такое нынче – это из области фантастики. В нынешней ситуации – подобный подход не находит понимания в широких массах современных разработчиков на ЯВУ, а приводит только к смешкам и попыткам кидаться штампами вроде “зачем нам изобретать велосипед”, при том, что разработка с нуля – это не изобретение велосипеда, а попытка велосипед сделать самостоятельно, научившись делать велосипеды, а не педалировать чужие. Ну да ладно, тема для другой записки. (Кстати, например, сейчас даже весьма квалифицированный, – реально, – разработчик (не кодер) – ассемблера не знает, да и требовать такого знания – это считается лишним.) В общем, поскольку с таким положением приходится мириться, то и важность “социальной сети” GitHub становится совершенно бесспорной и – растёт дальше. Проблема, конечно, что это централизованный сервис, который, в рамках “битвы за банхаммер”, все хотят отломить. Но, к сожалению, это не уменьшает практической важности. Более того, во многих крупных проектах нынче только через GitHub принимают сообщения об ошибках и прочие технические запросы, что ещё усиливает центральное положение GitHub.

Кстати, насчёт “быстрых” TLS-сертификатов для IP-адресов, которые подходят для веб-сайтов без доменных имён. Я уже некоторое время тестирую схему с таким сертификатом на сайте под IP-адресом https://185.39.19.199/.

Напишу, как там что настроено (это виртуальная машина, понятно). ОС Debian 13, веб-сервер – nginx 1.26.3, из пакетов Debian; я установил актуальную версию 5.6.0 утилиты certbot из snap (предварительно поставив snap, конечно) и настроил профиль аккаунта с использованием директории web-root, которую обслуживает nginx для хоста по умолчанию. Поскольку нужно принимать и обрабатывать HTTP по IP-адресу, в nginx я настроил единственный блок server для произвольных имён (default_server на 80 и 443, кроме того, на всякий случай, заведомо недоступный “_” в server_name). Пути к сертификату и ключу – указывают туда, где ссылки на них выкладывает certbot: /etc/letsencrypt/live/185.39.19.199/fullchain.pem.

Сама утлита certbot запускается по таймеру Systemd, а чтобы nginx подхватывал новый сертификат после его выпуска, я добавил в /etc/letsencrypt/renewal/185.39.19.199.conf строку “renew_hook = systemctl restart nginx”, блок “[renewalparams]”.

Собственно, это всё: такая конфигурация работает, а новые сертификаты выпускаются автоматом до истечения действующего. (Один из старых сертификатов я даже отозвал, в порядке эксперимента, указав причину отзыва superseded – это сработало, но выяснилось, что, судя по CRL, практически никто при отзыве не указывает код причины.)

Да, кроме IP-адреса я ещё завёл на тот же сервер доменное имя вида 185.39.19.199.zone, чтобы протестировать заказ сертификатов для “смешанных” имён: и IP-адрес, и DNS-имя. Это тоже работает – можете проверить по составу TLS-сертификата:

DNS Name: 185.39.19.199.zone
IP Address: 185.39.19.199 

Схема та же, как и с IP-адресом, но первоначально нужно указать при вызове certbot доменное имя при помощи опции -d (дополнительно к IP-адресу). Проверка DCV будет выполнена и для IP-адреса, и для доменного имени, а сертификат выпустится с двумя именами в блоке SAN.

Даниэль Стенберг (утилита curl) сообщает, что “страшная-ужасная” система поиска уязвимостей в ПО Mythos нашла в коде утилиты curl “пять” “подтверждённых уязвимостей” (“подтверждённых” – по мнению данного ИИ-LLM), которые, после проверки разработчиками, превратились в одну действительно подтверждённую уязвимость с низким уровнем опасности. Четыре остальных представленных описания – это ложные срабатывания и обнаруженная ошибка, – не уязвимость, – в коде. Результат никак не превосходит уже имеющиеся на стороне разработки curl инструменты.

Занятно, что Mythos сейчас, в рамках “маркетингового трюкачества”, продвигают на правах настолько “опасной системы”, что её нельзя выпускать в открытый доступ – поэтому, мол, доступ предоставляется только “ограниченному кругу лиц” (куда, в том числе, входят корпорации, непосредственно участвующие в разгоне хайпа). Стенберг при этом пишет, что ему доступ к новой системе предоставить обещали, он подписал контракт, но доступ так и не предоставили, а, выждав время, предложили, что кто-то ещё, со стороны Mythos, проведёт сканирование за Стенберга и перешлёт уже готовые результаты – и это очень забавно само по себе, особенно, на фоне всех этих заявлений про “невиданный уровень в разработке программных систем”, который, якобы, демонстрируют ИИ-LLM.

Занятно, что сейчас на странице “Избранное” перечисленно 333 записки. Первая – это записка про роллероны, 2006 года.

Я стараюсь в “Избранное” добавлять только особенно удачные, на мой взгляд, записки. Если верить панели управления WordPress, то всего сейчас опубликовано 3539 записок, с учётом этой. Написано и лежит в базе на сервере – чуть больше: пара записок так и не вышли в статус опубликованных, а одну – я скрыл сразу же после публикации (возможно, ещё пару записок, за все эти десятки лет, я удалил – но тоже почти сразу после публикации), но это всё редкость и было давно – обычно, если я уж написал текст на dxdt-сайт, то я этот текст здесь публикую; иногда – публикую тексты, которые вышли где-то ещё, но это именно что “очень иногда”, да и сейчас я уже практически никуда не пишу, кроме этого сайта. Так что, пока в “Избранных” примерно одна десятая от всех записок. Довольно большая доля.

На текущий момент, если взять среди всех публикаций dxdt, то лучшей я продолжаю считать записку “О визире и слоне”, которая вышла осенью 2022 года, и ни к технике, ни к интернетам – отношения не имеет вообще никакого, но имеет некоторое отношение к теоретической математике. На второе место поставил бы записку о путях самурая, пожалуй. Насчёт третьего места – вариантов уже слишком много.

Очередное обновление страницы “Избранное” – добавил десять записок:

• Техническое: ML-KEM, постквантовая стойкость и гибридные криптосистемы
• Чётность портретов монархов на британских монетах
• Эмбеддинг с навесом: перегрузка лексических парсеров вложением неявных ссылок
• Понимание переменных float как записей алгоритмов
• Квадратное уравнение на глиняной табличке

• Компьютеры, тип float и дистрибутивность умножения
• Обратное синтезирование апертуры антенны РЛС
• Моделирование физических экспериментов и превосходство квантовых вычислений
• Техническое: строгая, но избыточная фильтрация email
• Факторизация языков и утрата словоизменения