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

На “Хабре” я вчера опубликовал небольшой разбор математической части (потенциального) бэкдора, который присутствует в Dual EC DRBG (это алгоритм генератора псевдослучайных чисел; он, собственно, широко известен именно по причине обнаружения бэкдора, которое ничуть не помешало стандартизации NIST). Возможно, как-нибудь сделаю отдельную заметку по этой же теме на dxdt.ru (если будет ресурс).

P.S. Кстати, регулярно неверно переводят “Dual Elliptic Curve” из названия на русский – как “Двойные эллиптические кривые”. Но это не “двойные кривые” – кривая там одна, да и чисто грамматически, на английском, это никак не может быть “двойными кривыми”, – а “двойные” или “сдвоенные” – точки: алгоритм использует две точки кривой для получения псевдослучайных значений, отсюда и dual в названии.

Воскресное чтение манускриптов. Сегодня у нас фрагмент “Илиады”. Не только на манускрипте, но и на папирусе. Не всё из записей на папирусах, что считается фрагментами “Илиады”, точно укладывается в современный канонический текст, представленный на манускрипте Venetus A (ну, насколько он может быть каноническим: “Илиада”, между прочим, опубликована, – ну, в строгом смысле, то есть, напечатана, – впервые только в 15 веке). При этом именно кусочки папирусов дают одну из важнейших хронологических опор, позволяющих определить, что текст “Илиады” древнее, чем Venetus A, который датируется десятым веком нашей эры.

На папирусе (точнее, на кусочке папируса) P.Mich.Inv.6972 (датируется вторым веком до н.э.), который представлен на скриншоте ниже, как раз пример отличающегося в некоторых деталях текста.

Здесь две колонки – левая и правая. Они соответствуют строкам 421-434 и 445-460 десятой книги (песни) “Илиады”. При этом, например, слово из первой строки папируса – ἐπιτρωπῶσι (“доверяют”) – хоть и укладывается в Venetus A (см. ниже), но это другое слово: на Venetus A используется ἐπιτραπέουσι (“вверяют”/”вверямши”). И там, и там – строка заканчивается одинаково: φυλάσσειν (“сторожить/охранять”). Соответствующий фрагмент Venetus A (я отметил строку 421 и упомянутое слово):

Увеличенный фрагмент папируса с повышением контраста:

И это не только не единственное расхождение, но и не самое существенное: так, на этом же папирусе присутствует совсем другая версия строки 433 (тема для отдельной заметки). То есть, как минимум, более древние записи сильно расходились с “современным” древнегреческим текстом.

Интересно, что из других, максимально древних, источников по “Илиаде” есть, например, различные художественные сюжеты, запечатлённые, скажем, на барельефах, на керамических сосудах. Их много. Эти сюжеты укладываются в какие-то знаковые текстовые описания сцен из “Илиады”. Однако, несмотря не все археологические изыскания, остаётся вопрос: рисовались ли те сюжеты по текстам, или тексты, – возможно, много позднее, – были написаны под нарисованные сюжеты?

Некоторое время назад я написал на “Хабр” о попытке использовать ChatGPT для генерирования кода OpenSCAD: задача была – сгенерировать код, описывающий простейший Y-образный разветвитель шлангов; для этого я составил подробнейший “промпт” на естественном языке (есть в статье).

Конечно, выдача ChatGPT оказалась абсолютно бесполезной – в статье есть скриншоты рендеринга того, что сгенерировала LLM. В комментариях спросили, почему я выбрал “чат-бот”, вместо “специализированной модели”. Скопирую сюда свой подробный ответ, чтобы он не потерялся:

Есть целый ряд причин.

Во-первых, эта штука не написала в ответ, что, мол, “вижу, тут требуется 3D-объект, но я всего лишь чат-бот – обратитесь к специализированной системе”. Напротив – оно прямо и уверенно пишет, что точно умеет в OpenSCAD, знает все детали, приводит примеры (я спрашивал), а также предлагает проверить, что всё в коде корректно и верно при помощи рендеринга в OpenSCAD (да, такой вот “напор” демонстрирует). Опять же – что такое “чат-бот”? Если это средство занять назойливых клиентов в чате технической поддержки пустопорожним переливанием запроса в ответ – ну, да, тогда с OpenSCAD лучше не подходить. Но позиционируется-то этот инструмент явно иначе.

Во-вторых, не то чтобы была у меня какая-то уверенность, но я предположил, что в эту систему, – возможно! – уже успели-таки встроить “специализированное решение для 3D”. Это разумное предположение: такая возможность, без сомнения, полезна, системы постоянно обновляют, ждут в этом году “универсальный ИИ”, то и дело утверждается, что оно успешно решает задачи по геометрии на уровне “продвинутого старшеклассника”. Вот и проверили. Если бы оно справилось, это бы не сделало его интеллектом, но результат бы порадовал.

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

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

Наконец, в-пятых: в качестве специализированной системы – я бы всё же предпочёл использовать тот или иной готовый инструмент для параметрического задания типовых объектов в OpenSCAD (Y-образный адаптер к ним тоже относится). Такие инструменты есть. Они детерминированы. Они проще. Натыкать в интерфейсе размеры – быстро. Но они – не LLM, на которых обещают “универсальный интеллект”. Собственно, есть ведь и немало инструментов “визуального программирования”. Даже для специальных систем, типа GNU Radio, но почему-то сейчас про них вообще забыли, а рассказывают именно про генерирование кода LLM, на которые всех заменят.

Часто попадается популярная иллюстрация к протоколу Диффи-Хеллмана, использующая аналогию “смешивания красок”: то есть, стороны, пытающиеся получить общий секрет, смешивают исходную краску, которая известна всем, каждая со своей секретной краской, а потом обмениваются результатами по открытому каналу и смешивают со своим секретом уже результат второй стороны (см. ниже), получая, таким образом, одинаковый “цвет”. Например, в английской “Википедии” сейчас дана именно такая иллюстрация.

(Source: Wikimedia)

Оказывается, такая картинка – не самый плохой способ объяснить что-то содержательное про протокол DH “на пальцах”, пусть некоторые требования и остаются за кадром. Например, эта схема не позволяет показать, почему атакующая сторона не может “перебрать все краски” (естественно, в практическом случае с числами).

Посмотрим на основные моменты, которые подразумевает имеющаяся картинка. Во-первых, результат смешивания красок должно быть трудно обратить – важнейшее свойство для DH, который строится на “однонаправленных” функциях (об этом написано на исходной картинке). То есть, сторона, наблюдающая обмен, не может простым способом разделить краски. Вспомните, что исходная краска, – которая соответствует генератору в “настоящем” DH, – известна всем, в том числе, стороне, пытающейся взломать обмен. По условию – выделить эту краску из смешанных “цветов” оказывается вычислительно невозможно. Во-вторых, операция смешивания красок должна быть “коммутативной” (условно!) – то есть, результат не отличается от порядка подмешивания ингредиентов сторонами. Это не менее важный математический момент “настоящего” протокола, который позволяет обобщить его и перенести с классических вычетов на совсем другие структуры.

Вообще, “коммутативность” тут именно в кавычках, поскольку математическая структура несколько сложнее. Запишем операцию в виде формулы, где “*” соответствует смешиванию красок и действует слева: α * G – означает, что секретная краска α смешана с краской G (чтобы как-то обосновать “левое и правое” действие – считаем, что колер α добавлен в банку к краске G). Тогда: β * (α * G) == α * (β * G) – это то, что происходит в протоколе с красками. То есть, сторона A получает результат смешивания (β * G) и замешивает свою краску α: α * (β * G). Сторона B – наоборот. Казалось бы, должно выполняться (α * β) == (β * α), тогда работает схема. Именно так устроено в классическом DH, но с показателями степенй: (G^β)^α == (G^α)^β. Однако для протокола на красках, вообще говоря, (α * β) == (β * α) хоть и очевидно работает в “локальном” случае, но не применимо в иллюстрируемой схеме – ведь ни у стороны A, ни у стороны B нет готового состава (α * β) – они не могут его приготовить по условию “неразделимости” красок. Вариант (α * β) * G провернуть не получится, по условиям задачи: краски – это не натуральные числа. Поэтому-то “коммутативность” тут – это не настоящая коммутативность (без кавычек). Требуется именно “одинаковость” действия и краски α, и краски β на уже смешанные и подходящие краски. Это можно переписать в других обозначениях: A := α * G (подмешали α в G); B := β * G (подмешали β в G); α * B == β * A – потребовали выполнения базового свойства, необходимого для работы протокола DH на красках: β переводит A в тот же цвет, в который α переводит B.

И это вовсе не беспричинно въедливое разбирательство. Любой химик вам подтвердит, что в химии – далеко не всегда порядок подмешивания ингредиентов не влияет на результат. Формулы веществ это хорошо, но иногда нарушение порядка смешивания может так повлиять, что лабораторию придётся ремонтировать или даже строить новую.

Дело не только в химии: именно обобщение структурной особенности, которая переводит две разных “краски” строго в одну при действии разными элементами (другими “красками”) как раз и позволяет максимально обобщить и сам протокол DH, переписав его в терминах того, что в математике называется “действием группы”. Это, впрочем, отдельная история.

С “красочной” иллюстрацией к DH связан и ещё один занимательный момент. Хорошо, разобрать смешанный “цвет” на составляющие краски трудно – это по условию задачи. Но что мешает атакующему перебрать все доступные краски, подмешивая их к исходной? Результаты смешивания сравниваются с переданными в открытом виде “цветами” (они соответствуют открытым ключам DH) – если цвет совпал, то угадана секретная краска. Естественный вариант защиты: красок слишком много – перебор окажется неприемлемо долгим, а вот сторонам протокола легко выбрать одну секретную краску. Это, опять же, важный математический момент протокола: краски выбрать может быть легко, – вот тысячи, допустим, банок стоят на складских полках, – но реальный DH работает не на красках и там тоже требуется, чтобы был вычислительно простой метод равновероятного случайного выбора нужного числа (секретной “краски”). Да, в классическом варианте с целыми числами – выбрать число случайно и равновероятно не трудно. Вот только тут возникает другая проблема.

Классический вариант DH требует возведения в степень. Показатель степени является секретным ключом. Чтобы атакующая сторона не могла перебрать все показатели за обозримое время, значение должно быть большим. Но как быть стороне протокола, вычисляющей открытый параметр при помощи того же возведения в степень? Последовательно умножать генератор столько же раз, сколько и атакующий – выглядит несколько абсурдно. Хорошо, что знание показателя степени позволяет использовать быстрые методы, построенные на возведении генератора в квадрат и домножении на генератор в “нечётных” случаях: например, чтобы возвести 2 в пятую степень нужно дважды возвести 2 в квадрат и домножить на 2 – (2^2)^2 * 2, это три умножения, а не четыре, как для 2*2*2*2*2. В красках этого нет, но для любого практического воплощения протокола DH данное свойство “удвоения со сложением” необходимо – иначе легитимные стороны протокола оказываются в том же положении, что и атакующая сторона.

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

Похоже, сроки по “суперинтеллекту” несколько сдвигаются: в свежей колонке лидера OpenAI Альтмана предполагается лишь, что “в 2027 году возможно появление роботов, способных выполнять задачи из реального мира” (2027 may see the arrival of robots that can do tasks in the real world) – что бы это ни значило, так сказать. Какие-то роботы, конечно, уже есть, но подождём 2027 года – будет ли там вообще до обсуждений результатов?

Занятно, что подобные утверждения были популярны, например, в конце 60-х годов прошлого века – считалось, что вот-вот и – “роботы смогут выполнять привычные задачи”. Типа глажки и складывания полотенца, да. Суперинтеллект к 2030 уже не обещают. Но если вы посмотрите профильные футуристические статьи из конца 60-х, то прямо всё узнаётся, один в один; только там, обычно, писали про 2000-й год, а в колонке по ссылке – речь про 2035:

“Сегодня сложно даже представить, что мы откроем к 2035; возможно, мы пройдём от решения [проблем] физики высоких энергий в одном году до начала колонизации космоса в следующем; или от значительного прорыва в материаловедении в одном году до подлинно высокоскоростного интерфейса “мозг-компьютер” в следующем” (It’s hard to even imagine today what we will have discovered by 2035; maybe we will go from solving high-energy physics one year to beginning space colonization the next year; or from a major materials science breakthrough one year to true high-bandwidth brain-computer interfaces the next year.)

Начало колонизации космоса. Да. Но через десять лет. Возможно.

И написано, что сингулярность будет наступать медленно, но ничего нет про то, когда же включат “суперинтеллект”.

Недавно публиковал заметку о том, как перейти с ECDH на ML-KEM в проекте на Go: там на схемах показано, что DH можно уложить в схему KEM, что делает переход почти прозрачным. С этим связан интересный момент, касающийся свойств криптографической схемы, который в англоязычной традиции называется interactive и non-interactive (“интерактивная” и “не интерактивная”).

В ECDH (и в DH вообще) каждая из сторон может в любой момент вычислить общий секрет, если только знает открытый ключ другой стороны. То есть, это “не интерактивная” схема. Буквально: в DH, если сторона A знает открытый ключ стороны B, то A домножает этот открытый ключ на собственный секрет, который тут же выбирает независимо (но в соответствии со свои открытым ключом), и получает на своей стороне общий секрет. Никакого взаимодействия с B для этого не потребовалось. Поэтому, например, статичный открытый ключ DH может быть встроен в сертификат или ещё где-то опубликован, вне зависимости от того, в каком порядке вычисляется общий секрет сторонами. То же самое – для стороны B: этой стороне не требуется участие A для получения общего секрета (но нужен открытый ключ).

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

Но главное отличие – DH можно переписать в KEM (не конкретно ML-KEM, а именно в схему), а вот произвольную схему KEM в DH – не выйдет.

Сколько лет Интернету – вопрос многогранный. Дмитрий Бурков пишет, что отсчитывать годы нужно с момента разработки BGP (и это довольно логично, так как BGP в современной Сети используется для обмена информацией о маршрутах доставки пакетов).

На фото ниже, из коллекции Библиотеки Конгресса, – установка краеугольного камня первого здания библиотеки Конгресса, а конкретно – здания Томаса Джефферсона.

Фото постановочное. Капитолий присутствует в качестве фона. Все работники в шляпах. Оно и понятно: это 1890 год, всё строго, а за нахождение на улице, – тем более – на стройплощадке, – без шляпы – могли если и не оштрафовать, то подвергнуть словесному порицанию. Ну, наверное. Не то что сейчас – если без каски.

Увеличенный фрагмент, на котором присутствует и метла, и мастерок:

Попалась статья в The Guardian. Называется “Researchers create AI-based tool that restores age-damaged artworks in hours” (“Исследователи разработали базирующийся на ИИ инструмент, который восстанавливает повреждённые временем художественные полотна за [считанные] часы”). ИИ-хайп продолжает вредить: если прочитать заголовок, то сразу возникает предположение, что это опять дорисовывание при помощи “картиночной LLM”. Однако, не совсем так. Дорисовывание, конечно, есть и в этом случае, но это не генерирование ИИ-картинок.

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

Полученные в автоматизированном режиме и сведённые в Photoshop визуальные дополнения и правки “пикселов” – печатаются на специальной прозрачной плёнке, послойно (см. ниже схему). Подготовленные плёнки особым, обратимым образом наклеиваются на оригинал, дополняя его до состояния отреставрированного произведения. (Да, возникает традиционный вопрос, что же тут нужно считать реставрацией, если дорисованы фрагменты, информация о которых на исходнике полностью утрачена; собственно, в исходной работе этот момент постоянно упоминается.)

В итоге, всё же не “дорисовывание силами ИИ”, а автоматизированная обработка человеком изображения в цифровой форме (фильтры в Python + Photoshop, да) и перенос корректирующего “трафарета” при помощи плёнок – это и есть то, что ускоряет работу, снижая затраты именно в части очень сложного ручного труда реставратора-специалиста. Но в газетном заголовке всё равно “AI-based tool”.

Исходные данные – доступны на Code Ocean.

Если судить по фото и видео, то у потерпевшего катастрофу в Индии Boeing 787-8 Dreamliner (AI171) непосредственно перед столкновением с землей выпущено шасси, но практически полностью убраны закрылки – и это ещё в процессе набора высоты, сразу после отрыва. То есть, похоже, что это продолжение странных историй с автоматическими системами управления суперсовременными “Боингами”.