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

Dual EC DRBG (“Сдвоенный детерминированный генератор случайных битов на эллиптической кривой”) – нашумевшая схема генератора псевдослучайных чисел, в которой встроен (потенциальный) математический бэкдор. Несмотря на сразу же возникшие подозрения о бэкдоре, эта схема была без проблем стандартизована NIST в 2006-2007 годах и достаточно широко использовалась. Соответствующий стандарт позже официально отозван NIST.

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

Важнейшей особенностью криптографических генераторов (псевдо)случайных чисел является то, что выдача генератора детерминирована внутри – то есть, выдаваемые значения определяются внутренним состоянием (пояснение от 28/01/26: это только для внешнего наблюдателя генерируемая последовательность выглядит как случайная). Именно этот аспект служит фундаментом для построения бекдора в Dual EC DRBG. Криптографические генераторы псевдослучайных чисел имеют важнейшее значение не только для теоретической, но и для прикладной криптографии – это краеугольный камень всех практических систем криптографической защиты.

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

По сути, бэкдор в Dual_EC_DRBG – это реализация протокола Диффи-Хеллмана (DH) на эллиптической кривой: секретный ключ находится у стороны, контролирующей бэкдор через параметры протокола, что позволяет этой стороне получать внутреннее состояние генератора псевдослучайных чисел, наблюдая его выдачу. Знание внутреннего состояния приводит к раскрытию всей последующей выдачи генератора. При этом, математически, пользователь Dual EC DRBG неявно выполняет обмен DH с контролирующей параметры генератора стороной. Это важное свойство штатных схем построения “надёжных бэкдоров”: доступ к бэкдору должен быть только у той сторны, которая знает секретный параметр – секретный ключ. Есть и другое важное свойство: если секретный параметр не был раскрыт, то строго доказать, что бэкдор действительно встроен в конкретную реализацию – нельзя. Это не отменяет возможности тсрогого описания для механизма такого бэкдора.

Итак, в Dual EC DRBG, без знания секретного параметра раскрыть внутреннее состояние генератора вычислительно трудно, потому что базовые функции протокола – односторонние. Поэтому, если оставить за скобками секретный параметр, то протокол полностью соответствует общепринятой схеме.

Посмотрим на типовую схему построения программного генератора псевдослучайных чисел. Такие генераторы можно строить на базе двух односторонних функций и цепочки внутренних состояний. Одна из функций переводит текущее внутреннее состояние в следующее, а вторая – извлекает значение из текущего состояния и выводит его в сторону пользователя.

На схеме: S_n – внутренние состояния генератора; φ() – функция, преобразующая состояние S_n в S_n+1; ξ() – функция, преобразующая состояние S_n в выдачу генератора B_n на данном шаге. Биты пошаговой выдачи B_n могут конкатенироваться для получения псевдослучайной последовательности нужной длины (на схеме: RND[…]) – это типовой способ прикладного использования генератора.

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

Почему односторонней должна быть и функция φ, которая переводит текущее внутреннее состояние в следующее? Это нужно для того, чтобы по утекшей информации о внутреннем состоянии на каком-то шаге было вычислительно сложно восстановить предыдущую выдачу генератора. Одно из базовых требований к криптографически стойким генераторам псевдослучайных чисел состоит в минимизации возможностей по раскрытию данных. Например, если есть бэкдор, позволяющий обратить ξ, то, при условии обратимости φ, взяв любую точку можно раскрыть сколько угодно данных – и предыдущие, и следующие. При этом обратимость ξ может являться следствием не бэкдора, а обычной уязвимости, в том числе, уязвимости реализации алгоритма. Предположим, эта уязвимость ξ срабатывает лишь на каких-от редких данных: соответственно, если подобрать такие данные удалось, но φ осталась необратимой, атакующий сможет вычислить только следующие состояния генератора и все предыдущие секреты останутся защищены.

Математической особенностью описываемого бэкдора является то, что он вовсе и не позволяет обратить функции ξ и φ – они остаются односторонними, но бэкдор открывает возможность простого вычисления следующего внутреннего состояния генератора по известной выдаче ξ. Это возможно потому, что алгоритм содержит дополнительную структуру, связывающую функции ξ и φ.

Псевдослучайная выдача в криптографических протоколах постоянно используется в открытом виде. Например, в открытом виде передаются векторы инициализации для схем зашифрования (GCM и пр.), псевдослучайные векторы в сообщениях TLS (поля ClientRandom и ServerRandom) и др. Поэтому нетрудно извлечь значения из трафика, сопоставить их с выдачей генератора псевдослучайных чисел, раскрыть внутреннее состояние генератора и получить последующие биты выдачи, которые, например, были использованы тем же приложением для получения секретных ключей шифров, защищающих трафик – это позволит восстановить секретные ключи и расшифровать трафик в пассивном режиме.

Dual EC DRBG работает на эллиптической кривой (над конечным полем), а в качестве односторонних функций использует умножение точки эллиптической кривой на скаляр: x∘P. Далее умножение на скаляр обозначается “блобом” (∘). Стойкость к обращению здесь основана на задаче дискретного логарифмирования: то есть, по значению Q = x∘P – вычислительно трудно найти x.

Вспомним, что умножение на скаляр – обычное для эллиптической криптографии последовательное сложение точки кривой с самой собой. Сложение – операция, которая введена на точках кривой. А именно: точкой кривой называется пара (X, Y) значений “координат”, соответствующих уравнению кривой. Здесь X и Y – это элементы подлежащего конечного поля, которое входит в параметры криптосистемы. В данном конкретном случае (например, для кривой P-256) используемое конечное поле – это вычеты, то есть “остатки” по модулю простого числа. Сложение точек P + Q = R позволяет по паре координат точки Q (X_Q, Y_Q) и паре координат точки P (X_P, Y_P) Получить координату точки R (X_R, Y_R). Скаляр – это целое число. Умножение на скаляр 3 означает, что точка складывается сама с сбой в трёх экземплярах: 3∘P = P + P + P (плюс – это сложение точек). По такому сложению точки всякой эллиптической кривой всегда образуют группу (по определению эллиптической кривой).

В алгоритме Dual EC DRBG используется две точки кривой: P и Q. Точка P – задаёт последовательность внутренних состояний. Внутреннее состояние S_n в Dual EC DRBG – целое число, которое соответствует координате X точки кривой, полученной умножением P на значение предыдущего состояния, как на скаляр. Вторая точка, Q – задаёт “ответвления”, то есть, выдачу генератора по каждому из состояний, и используется в качестве основания на каждом шаге. Ниже представлена упрощённая схема Dual EC DRBG.

На этой схеме: S_n – внутреннее состояние; для получения следующего состояния из текущего – точка P умножается на значение состояния (скаляр: S_n∘P), а координата X получившейся точки – выводится в качестве нового состояния генератора; для вывода случайных значений – вторая точка, то есть – точка Q, умножается на состояние (S_n∘Q) и выводится координата X получившейся точки. То есть, используется две одинаковых функции с разным основанием: P и Q. Раз стойкость этих функций основана на дискретном логарифмировании, то они односторонние, как и требуется.

Математический смысл бэкдора не нарушает стойкость конкретных операций с точками P и Q, он несколько хитрее и строится на в соотношении между точками P и Q. Допустим, атакующей стороне известно такое значение δ, что P = δ∘Q. Выдача генератора – это X-координата точки S_n∘Q. Атакующий находит подходящую Y-координату, подставив значение в уравнение кривой (точек с подходящими координатами будет две, алгоритм знак координаты Y не различает, но выбор точки, очевидно, не представляет труда). Таким образом атакующий легко восстанавливает точку кривой, подходящую для выдачи генератора. Далее – умножаем на δ.

δ∘(S_n∘Q) = S_n∘(δ∘Q) = S_n∘P   (1)

Рассмотрим формулу (1) подробнее. Почему она работает? Потому что скаляры – это целые числа. Из-за коммутативности группы точек кривой к скалярам применимы арифметические свойства целых чисел. В алгебре такая конструкция называется ℤ-модулем. Всякая коммутативная группа является ℤ-модулем. (Некоторые алгебраисты из-за этого даже не считают коммутативные группы “настоящими” группами.) Применительно к эллиптической кривой: 3∘P = P + P + P, а 5∘P = P + P + P + P + P. Но тогда (3+2)∘P = 5∘P = P + P + P + P + P, что следует из свойств групповой операции – просто поставим скобки: (P + P) + (P + P + P), получив, таким образом, две точки (P + P) = 2∘P и (P + P + P) = 3∘P. 3∘P + 2∘P = 5∘P. Обратите внимание, что здесь знак “плюс” используется в двух значениях: и для обозначения сложения точек кривой, и для обозначения привычного сложения в целых числах (3+2). А раз схема работает для сложения целых чисел, то она обязательно работает и для умножения целых чисел, потому что умножение в целых числах можно построить через сложение (собственно, при корректном преобразовании 0 и 1, сложение и умножение в целых числах просто могут быть переведены одно в другое, как операции). Но тогда и (3*2)∘P = (P + P) + (P + P) + (P + P) = 3∘(2∘P) = 6∘P. Что и используется в формуле (1), вместе с коммутативностью умножения в целых числах: 2 * 3 = 3 * 2.

Таким образом, атакующая сторона, которая знает секретный скаляр δ, получила значение следующего состояния генератора, вычислив Χ-координату точки S_n∘P (см. схему). Формула (1) вообще очень похожа на реализацию протокола Диффи-Хеллмана (DH) на эллиптической кривой. То есть, пользователь генератора псведослучайных чисел, можно сказать, обменялся с атакующей стороной открытыми параметрами Диффи-Хеллмана. А именно: открытый параметр атакующей стороны, статический ключ, зашит в константы протокола – P = δ∘Q, где секретный ключ – δ; открытый параметр DH пользователя – это динамическая выдача основного алгоритма – S_n∘Q, где секретный ключ S_n. “Открытые параметры DH” пользователя атакующая сторона наблюдает в трафике. Важное отличие от практического DH состоит в том, что “общий секрет” тут не должен становиться “общим” с атакующей стороной.

Итак, для внедрения бэкдора нужно выбрать такие P и Q, что P = δ∘Q. Полученные точки – это параметры конкретной реализации алгоритма, но они могут быть закреплены в стандарте (что и было сделано). Но в спецификации Dual EC DRBG для кривой P-256 в качестве точки P строго указана базовая точка группы кривой, которая используется в спецификации P-256. То есть, произвольно выбрать P нельзя. Оказывается, в том случае, если одна из точек P или Q заранее строго задана, то определить нужное значение δ можно при помощи вычисления мультипликативного обратного по модулю порядка группы точек. Важно, чтобы порядок был простым числом. Но это стандартная практика для прикладной криптографии. Например, для кривой P-256 – соответствующий порядок простой.

Чтобы получить бэкдор, нужно определить δ из P = δ∘Q. Может показаться, что если точка P зафиксирована, – соответственно, выбрать эту точку умножением какой-то точки Q на произвольный скаляр нельзя, – то требуется решить сложную задачу отыскания дискретного логарифма. Но это не так, поскольку мы всё равно можем выбрать произвольную точку Q. Чтобы согласовать точки, возьмём произвольное значение ε в интервале от 2 до порядка группы, генерируемой P, а потом возьмём δ = ε^(-1) по модулю порядка. Пусть порядок P – то есть, количество точек в используемой группе, – это простое число n. Тогда нужно найти ε * δ = 1 (mod n). (Например, 2 – обратный по умножению элемент к 4 по модулю 7, так как 2 * 4 = 1 (mod 7).) Задача нахождения мультипликативного обратного по модулю простого числа здесь вычислительно несложная. Определив δ = ε^(-1), в качестве точки Q выберем ε∘P. Тогда: δ∘Q = δ∘(ε∘P) = (ε^(-1)*ε)∘P = P. Следовательно, мы нашли такое δ, что P = δ∘Q.

То есть, если можно выбрать оба параметра – точки P и Q, – то выбираем так, что P = δ∘Q, а если одна из точек зафиксирована – выбираем δ = ε^(-1) по модулю (простого) порядка группы точек, это всегда можно сделать из-за особенностей спецификации: подлежащие группы имеют простой порядок. (Не забывайте, что в формулах выше используется два умножения – умножение точки на скаляр и умножение целых чисел (δ = ε^(-1); 1 = ε^(-1)*ε). Это работает потому, что скаляры – целые числа, но по модулю порядка группы.)

В Dual EC DRBG битовый вывод генератора, – то есть, X-координата S_n∘Q, – урезается: из него удаляются 16 старших битов. Это означает, что прямо использовать результат для вычисления координат исходной точки нельзя. Но 16 бит можно быстро перебрать, проверяя, для всех значений подряд, лежит ли на кривой точка с соответствующей X-координатой. Вычисление значений по уравнению кривой тоже не составляет проблемы – уравнение известно, а используемые там операции обязательно быстрые.

Естественно, полученная перебором точка может оказаться неверной. То есть, точка не будет являться S_n∘Q. На этом шаге “через бэкдор” у атакующего нет никакого способа проверить, что точки совпали. Но это не сильно затрудняет атаку. Значения секретного состояния нужно вычислить для всех возможных точек, которые соответствуют сокращённому битовому значению, а результат по каждой точке – сопоставить с дальнейшим анализом трафика. Например, если выдача генератора используется для получения секретного ключа, то выбрать его верное значение можно при помощи пробного расшифрования. В любом случае, анализ 2^16 числовых значений при помощи перебора не представляет здесь вычислительной проблемы.

В ранней версии стандарта NIST на Dual EC DRBG реализация использовала подмешивание дополнительной маски на каждом шаге вычисления псевдослучайных чисел. Это делало описанный бэкдор нерабочим. Однако стандарт был быстро обновлён, точка подмешивания дополнительной маски перенесена, и использование бэкдора стало снова возможным. Поэтому данная особенность здесь не рассматривается.

Проблема алгоритма Dual EC DRBG, как криптографического генератора псевдослучайных чисел, помимо низкой производительности, в том, что внутри его конструкции есть жесткая структура, зависящая от внешних параметров. Из-за алгебраических свойств эллиптических кривых, в практической реализации – точки P и Q всегда связаны. Да, иногда, если специально постараться, они могут быть получены способом, дающим некоторую гарантию того, что связующий скаляр никому не известен. Либо, P и Q может генерировать конкретный пользователь, в качестве параметра для своей локальной версии генератора. Стандарт NIST разрешал такой вариант, но не рекомендовал его, а для соответствия строгим требованиям FIPS допускались только параметры из спецификации.

(Это расширенная версия статьи, которую я недавно опубликовал на “Хабре”.)

Немного древних чисел. На скриншоте ниже – глиняная табличка из Месопотамии Plimpton 322, которую датируют 1900-1600 годом до нашей эры.

Image: CDLI / Rare Book and Manuscript Library, Columbia University, New York, New York, USA

Табличка содержит древнюю тригонометрическую таблицу (судя по всему, да, так и есть – тригонометрическую), числа в которой записаны в шумерской системе. Шумерская система счисления – это занятная позиционная система по основанию 60, со своими тонкостями.

Попробуем прочитать числа в середине таблички (примерно – в середине: найти исходное положение фрагмента нетрудно, если воспользоваться характерным пятном).

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

Итак, если записать в принятом формате, обозначая шумерские цифры числами [01..59] в десятичной записи и разделяя позиции точкой, получатся числа, которые представлены ниже (два числа, слева направо, строка с зелёными подсказками).

38.11     59.01

Чтобы понять, как такие значения получаются – посчитайте “галки” и “палки” на картинке: например, три “галки” слева – это 30. Остальное должно сложиться само. Но это шестидесятеричная запись. Её, впрочем, нетрудно перевести в десятичную (учитывайте, что это позиционная система, поэтому цифровые значения умножаются на 60 в степени номера позиции, начиная с нуля; в этом примере – позиций только две).

38*60 + 11 = 2291
59*60 + 1 = 3541

Шумерские цифры из Месопотамии, вместе со способом записи, образуют древнейшую из известных позиционных систем. Не очень понятно, что произошло с нулём: на самых древних табличках нуль не обнаруживается, но на более поздних появился некоторый вариант, записываемый двумя диагональными палочками, который, конечно, не совсем решил проблему неоднозначной интерпретации. Впрочем, может, у древних шумеро-вавилонских инженеров тут никакой неоднозначной интерпретации и не возникало.

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

(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 данное свойство “удвоения со сложением” необходимо – иначе легитимные стороны протокола оказываются в том же положении, что и атакующая сторона.

Тавтологические формулировки в условии задачи по математике – это, обычно, очень плохо. Однако их можно использовать в роли некоторой капчи, позволяющей отличить выдачу LLM от попытки осознанного решения. Это особенно актуально, когда то и дело заявляют об “успешном решении ЕГЭ по математике” ИИ/LLM.

Речь тут вот о чём. Любое минимально содержательное утверждение можно переписать в виде набора усложнений, описывающих всё то же утверждение. Тавтологическое переписывание является традиционным источником околоматематических шуток: “возьмём формулу 1 == 1, перепишем единицу справа как определённый интеграл exp(-x) от нуля до бесконечности, а левую – как π/π” и т.д. – в итоге можно получить сколь угодно сложное, многоэтажное сочетание загадочных символов, которое, тем не менее, будет верным. При этом, что удобно именно в учебных задачах уровня ЕГЭ, так это то, что исходное утверждение можно вообще не приводить – оно считается известным.

Сумма углов треугольника равна 180°. Запишем это так: дан треугольник ABC, в котором сумма углов при стороне AC равна сумме двух прямых углов минус третий угол треугольника. Это, очевидно, верно для всякого треугольника в “школьной” геометрии на плоскости, прежде всего потому, что это всего лишь перфразированная аксиома (да, которая делает геометрию евклидовой, но эти детали сейчас не рассматриваем). Однако, во-первых, для записи используется достаточно много слов, что имеет ключевое значение для LLM; во-вторых, выглядит как формулировка свойства, применимого только к данному треугольнику данной задачи; в-третьих, в основе лежит верный геометрический факт, широко используемый в задачах.

Может присутствовать возможность тривиального решения. А может быть – тривиальное решение только подразумевается, то есть, приводится лишь запись как бы задачи, решить которую невозможно, поскольку не хватает данных. Получается своего рода капча – LLM в любом случае будет генерировать “ответ” или вывод “противоречий”, учитывая слова формулировки.

Пример первый – это просто набор утверждений, который подразумевает тривиальные соотношения, постоянно используемые в задачах по планиметрии:

В равностороннем треугольнике ABC углы обозначены α, β, γ, а из вершины B проведена медиана BP. Сумма углов α и β при стороне AC равна сумме двух прямых углов минус угол γ. Найдите высоту треугольника ABC.

Когда я задал эту “задачу” ChatGPT-4o, LLM верно перечислила все фундаментальные свойства равностороннего треугольника (углы – 60° и т.д.), верно распознала углы при стороне AC (в тексте, не на чертеже – см. ниже), но дальше – принялась “рассуждать” о том, что сумма двух прямых углов это (внимание!) 360°, а поэтому сумма углов α и β даст 300°, но должно быть 120°.

“120° ≠ 300°. Противоречие. […] Очевидно, что если треугольник равносторонний, то углы не могут давать такую сумму” – написала данная языковая модель свой вывод, перепутав прямые и прямые углы.

То есть, капча сработала. Если бы капча не сработала, если бы ответ был “интеллектуальным”, то LLM должна была бы написать что-то типа такого: “в задаче не хватает данных – найти высоту треугольника невозможно, но можно, например, утверждать, что высота равна медиане”.

Второй пример – в ту же формулировку дописываем длину медианы:

В равностороннем треугольнике ABC углы обозначены α, β, γ, а из вершины B проведена медиана BP длиной 5. Сумма углов α и β при стороне AC равна сумме двух прямых углов минус угол γ. Найти высоту треугольника ABC.

Казалось бы, тут рассказы про углы можно отбросить: из того, что треугольник равносторонний – сразу же следует, что высота равна медиане, то есть ответ – 5. Но если эту же, “уточнённую”, задачу задать ChatGPT в том же потоке, где была задана предыдущая, то выясняется, что данная LLM не только не может отбросить тавтологическую часть условия, но ещё и продолжает считать, что сумма углов – 360° == 180° + 180°. Я не привожу весьма объёмные и подробные “рассуждения” ChatGPT, чтобы не перегружать текст. Если кратко, то LLM предположила, что имеются в виду углы, “образованные при построении медианы BP”, сложила углы уже в двух получившихся треугольниках, и объявила, что “Всё сходится!” (ну конечно, “сходится” – ведь сумма углов двух треугольников это 360°, как и сумма “двух прямых”, в представлении LLM; заметьте, что это, без сомнения, одна из лучших систем в мире, но почему-то предполагается, что данная LLM, якобы, может успешно решать не только ЕГЭ, но и задачи “олимпиадного уровня”).

Далее ChatGPT продолжает “решать” задачу и, используя формулу для длины медианы в равностороннем треугольнике, вычисляет, – в лучших традициях, по формуле! – высоту, подставив найденное значение стороны в формулу высоты. Ответ верный – 5.

Сработала ли и тут “тавтологическая капча”? Да, сработала. Смысла в вычислении по формулам не было: то, что высота равна медиане – этой свойство треугольника ABC. Можно ли трактовать этот момент как желание LLM действовать в парадигме “подставляем числа в формулы так, чтобы получилась хорошая оценка”? Нет. Этому противоречат подробные и точные рассуждения о свойствах треугольника и данная рядом глубоко неверная трактовка суммы двух прямых углов. Естественно, если ChatGPT подсказать, что с прямыми углами тут что-то не то получилось, и что практический смысл интерпретации дополнительных слов условия – тёмен, система тут же исправляется – и сумма углов становится равной 180°, и признаётся, что можно сразу определить, чему равна высота.

Приём с “тавтологической капчей” очень похож на упоминавшийся раньше метод приписывания в условие арифметической задачи посторонних фактов, которые не влияют на ответ. Отличие в том, что здесь добавляемая часть текста относится к фактам, непосредственно связанным с постановкой задачи, но тавтологическое изложение гарантирует, что на ответ эта часть текста тоже не влияет.

И посмотрите на чертёж, нарисованный к данной задаче ChatGPT. Казалось бы, система “умеет выводить” формулы и “решать задачи ЕГЭ”, но почему-то не может верно обозначить углы и провести медиану в соответствии с условием.

Воскресное чтение манускриптов. Манускрипт Vat.gr.1605 из Ватиканской Апостольской библиотеки уже несколько раз упоминался на dxdt.ru. Например, в связи с “кубосом”, иллюстрирующим способ вычисления объёмов. На соседней с “кубосом” странице этого манускрипта, а также на странице предыдушей, описаны и нарисованы круги, тоже с вычислениями. Их и рассмотрим.

Специалиста, подготовившего исходные тексты манускрипта, называют иногда Героном Византийским (не Александрийским, на которого он ссылается), иногда Героном Младшим, а также – византийским Анонимом. Манускрипт Vat.gr.1605 датируют одинадцатым веком, первая часть труда посвящена осадным машинам, методам взятия крепостей и прочим хитростям военного дела, а вторая часть называется “Геодезия” и посвящена сугубо практическим методам измерений “на местности”, которые необходимы, кроме прочего, “для правильного определения высоты крепостных стен, без приближения к ним”. Методы дистанционного измерения здесь, конечно, оптические и основаны на применении диоптры (διόπτρα) – угломерного прибора, предшественника теодолита. (Способы применения диоптры подробно разобраны у более известного Герона – Александрийского.) Именно при помощи диоптры предлагается измерять первый круг. Соответствующая схема круга – на скриншоте из манускрипта.

Буквой α обозначен центр круга, по периметру которого сидят кустики и лежат камни (и они тут не просто так нарисованы – см. ниже). Радиус круга – ρε под чертой (черта обозначает запись числа); это число 105, в греческих буквенных обозначениях: ρ == 100; ε == 5; Единица измерения длины: оргия (ὄργυια); то есть, буквально, сажень, однако это не важно для геометрической интерпретации. Слева, в вертикальной записи, обозначена длина окружности: χξ, что соответствует 600 + 60 == 660. Ближе к центру, снизу от α, – площадь круга: λδ καὶ χν, что означает 34 (λδ) [тысячи] и (лигатура ϗ) 600 + 50 == 650, всё вместе: 34650 (квадратных саженей). Тысячи на иллюстрации обозначены диагональной чертой перед λ, а в тексте – прямо записаны словом как “тысячи” (χιλιάδων), что хорошо видно на скриншоте (нижняя строка, я отметил зелёными линями и буквами).

Зачем кустики и камни? Герон Византийский в тексте подробно описывает, как нужно строить окружность на местности. Это ведь практическое руководство. Описание такое: установить диоптру в будущий центр, в точку α, после чего взять прямую линию визирования по некоторой другой точке, обозначив её β, – тогда αβ будет радиусом, – и дальше, поворачивая визир диоптры, отмечать в плоскости круга на земле опорные точки по визуальным ориентирам – кустам, камням или другим хорошо заметным предметам; на иллюстрации соответствующие интервалы обозначены буквами по алфавиту. Потому что диоптра – это такой инструмент с транспортиром (диском), винтами и визиром, установленный на моноподе. Так что, пусть манускрипт и подготовлен почти тысячу лет назад, но логика текста отражена на иллюстрации почти во всех необходимых для практического руководства деталях: не хватает только изображения, собственно, диоптры.

В тексте манускрипта приводится и подробный расчёт параметров размеченного на земле круга, исходя из радиуса, который определяется при помощи измерения диоптрой. А именно: радиус нужно удвоить, получив диаметр: 105 * 2 == 210; так как длина окружности составляет “3⅐ диаметра”, то она равна 660, “поскольку это число содержит три раза по 210 и одну седьмую от 210”. Здесь отношение длины окружности к диаметру принято 3⅐, – приблизительно 3.14 в десятичной записи, – неплохое рациональное приближение современного π. Площадь круга находится из тех соображений, что произведение диаметра на длину окружности – это четыре площади круга, соответственно, нужно взять одну четверть от 210*660, что и даст 34650.

Заметьте, между прочим, что хоть это и 11 век, но одна четверть, как ни странно, тут уже сокращённо записывается с горизонтальной чертой, и очень похоже на 1/4 (см. в центр скриншота, отмечено зелёными цифрами и стрелкой).

Со вторым кругом всё несколько проще. Так пишет и сам Герон Византийский: здесь окружность рисуется при помощи натянутой от центра верёвки, человеком, у которого не оказалось экзотического прибора – диоптры.

Этот круг поменьше. Радиус: λε == 30 + 5 == 35 саженей; периметр: ςκ == 200 + 20 == 220 саженей; площадь круга: γων == 3 (тыс) + 800 + 50 == 3850 саженей – ровно в девять раз меньше предыдущего круга, что очередной раз подчёркивает полезные свойства рациональных чисел.

CAA-запись в DNS позволяет управлять тем, какие УЦ могут выпускать сертификаты для имён в соответствующей доменной зоне. Проще говоря, в DNS публикуется имя УЦ, которому разрешено выпускать сертификаты. Чьё имя не указано – тем выпускать нельзя. (Есть тонкости с Wildcard-именами и уведомлениями о попытках заказа сертификата.) Интересно, что отсутствие CAA-записи в зоне разрешает выпуск всем. А если в CAA для имён УЦ указать пустой список (“;”), то выпускать нельзя никому.

То есть, тут мы неожиданно, на практике, сталкиваемся с весьма важной особенностью из области теоретической математики вообще и математической логики в частности. Речь про логики и формальные системы разного уровня. Пустой ящик – имеет совсем другой смысл, чем отсутствие ящика. Отсутствие ящика – это отсутствие CAA-записи, которое отсутствие вовсе и не эквивалентно пустому значению CAA-записи. Ящик есть, но он пуст – это наличие CAA-записи, значение которой – пустое множество. В первом случае, пустое множество – это “количество” CAA-записей в зоне. Во втором случае – количество УЦ, имена которых указаны в CAA-записи. Пустое множество при этом одно и то же, но оно укладывается в разные, рекурсивные ящики. Так можно построить натуральные числа.

Конечно, в спецификации этот подход использован не с целью построения натуральных чисел, а всего лишь с целью сделать использование CAA мягким. Иначе без доступа к DNS вообще не получилось бы сертификаты заказывать у УЦ, которые следуют CAA-записям.

В продолжение недавней записки про числа в ML-KEM. Один из ключевых параметров ML-KEM, одинаковый для всех наборов, это число (модуль) 3329. Почему выбрано именно 3329? Был ли выбор “случайным” (а иногда используют проверяемые методы для выбора параметров) или это число подобрано специально?

Число 3329, обозначаемое q, в ML-KEM выбрано строго специально. И вот из каких соображений. Весь практический вычислительный смысл ML-KEM (Kyber) в преобразовании (NTT), позволяющем быстро производить арифметические операции с полиномами. Чтобы быстрые операции NTT стали возможны в ML-KEM, число q должно быть простым, а (q-1) должно делиться на 256. (Более “общо” – делиться должно на степень двойки.) 256 – это другой параметр ML-KEM, его значение продиктовано разрядностью операций (256 бит).

То есть, 3329 – простое, (3329 – 1)/256 == 13. Если эти требования не выполняются, быстрый NTT работать должным образом не будет, поскольку это не настолько универсальный алгоритм, умножать полиномы “в лоб” – очень медленно, и другие быстрые алгоритмы – тоже оказываются медленными по сравнению с NTT. Неподалёку от 3329 не так много чисел, обладающих описанными свойствами: 257, 769, 3329, 7681, 7937. При этом, нужно выбрать число поменьше (важна экономия каждого бита), но чтобы не слишком выросла вероятность получения неверного результата при работе криптосистемы. Для 257 и 769 вероятность ошибки заметно больше. Поэтому авторы алгоритма выбрали 3329.

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

То есть, это самое реальное применение для знаменитых “LLM с нейросетками” на ближайшее время, при котором они могли бы оказаться очень эффективными для математических исследований. Попытки такие, вроде как, предпринимались, потому что подход достаточно очевидный, однако массового результата пока что не видно.

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

Другими словами, если у вас есть добротный анализатор для языка Fortran (для языка, не для алгоритмов), то он вовсе не обязательно эффективен для программ на Haskell, которые транслированы (ну, предположим) в код на Fortran: проверяться всё равно будет Fortran-программа. Это сильно сужает возможности по созданию полезных универсальных “анализаторов кода на ЯВУ”.

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

Предположим, что на процессоре “Имярек-7” команда MOV (“копирующая/перемещающая какие-то данные”) не просто сама по себе Тьюринг-полная (как в x86), но ещё и содержит “особенность” реализации, приводящую к тому, что число 0xFFFFFFFF превращается в 0x0, если сделать два MOV подряд из ОЗУ в регистр REG1. Поэтому, чтобы какие-то детали гарантировать относительно программы и реализации алгоритма, нужно в рассмотрение включить и аппаратные особенности. Сделать это автоматическим способом непросто. Отчасти поэтому-то и появляются всякие разные трансляции в “байт-код”, пригодный для исполнения “песочницей” (например, “Java-машиной”, если хотите): в такой конфигурации можно построить какие-то формальные описания и для языка, и для “машины”, которая его интерпретирует. Можно показать, что тут, при следовании некоторым принципам, всё разрабатывается безопасно (и это, действительно, так, но далеко не в общем случае).

Если же что-то всё же пошло не так, то оно пошло из-за дефекта реализации “машины”, а эта реализация находится за пределами модели. Это удобное сужение темы: если у вас код вылезает из песочницы, то проблема существует над песочницей, а не в ней; песочница хороша по определению: существовала бы проблема в ней – вылезать и не требовалось бы, да.

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

Как понять, что факторизация числа 15 не может ничего говорить о реализации квантового алгоритма Шора? Понять это несложно: один из делителей числа 15 должен быть меньше 4 (потому что 4^2 == 16), единица не рассматривается по условиям задачи, и это не 2 (потому что только нечётные подходят). Так что любой процесс поиска, каким бы аналоговым он ни был, если вообще сходится, то неизбежно попадёт в 3, что и будет верным ответом.

Заметьте, что ещё и 5 = 3 + 2, а простых чисел, меньших 15, только шесть: поэтому, учитывая, что умножение здесь коммутативно (это очень важно для квантовых алгоритмов), число 2 отбрасывается, а схема поиска расщепляется на пары, то, в самом худшем случае, вероятность, что аналоговый аппарат, состояния которого переключаются по возможным узлам дерева, промахнётся – меньше трети. (На практике, ещё раз, для промахов там просто нет места.)

Недавняя записка про оптимизацию циклов и микроконтроллеры иллюстрирует весьма важный момент, связанный с пониманием алгоритмов, записи алгоритмов и реализаций этих алгоритмов. Не менее рельефный пример в этом же направлении касается базовых логических операций и понимания записи формул. Речь про вопрос из области логики, логических выражений: является ли P и ¬¬P – одним и тем же? Даже разработчики-программисты нередко говорят, что “да, является”.

Знак “¬” – это логическое отрицание, проще говоря – “не”, или “!”, как будет во многих привычных языках. То есть, казалось бы, тут, во второй части, написано, что “не-не-P”, а тогда, если P имеет значение TRUE, то “не-не-P” тоже TRUE; то же верно и для P == FALSE. Понятное двойное отрицание, поэтому, что P, что ¬¬P – разницы нет: одно и то же. Это, впрочем, не совсем так.

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

Понятно, что тут очень многие соглашения вынесены за скобки, но, тем не менее, это хороший пример базовых свойств процесса оптимизации. Да, компилятор мог бы заменить ¬¬P на P. Почти что то же самое компилятор и проделывает, когда заменяет запись цикла, тело которого не вносит изменений в результаты работы фрагмента кода, на простое присваивание:

b = 14; 
for(a = 0; a < 8; a++){ 
 b = b + a;
} 

заменяется на эквивалентное

b = 42;

(или это не эквивалентная замена?)

Вообще, запись алгоритма, содержащая определение цикла, описывает повтор неких операторов/команд, но не определяет, как этот повтор должен реализовываться на оборудовании. В принципе, тело цикла можно прямо выписать в качестве повторений команд, это известный приём оптимизации, он так и называется - "развернуть циклы". Очень часто, будучи применённым к программе на языке высокого уровня (ЯВУ), приём даёт заметный прирост производительности. Почему? Потому что исчезли накладные вычислительные расходы. При обычной обработке представления цикла на ЯВУ - появляются необходимые машинные команды, соответствующие "записи" цикла, а процессор вынужден их исполнять. Команд может оказаться неожиданно много: например, потребуется сложная обвязка для реализации обработки переменной цикла.

Занятно, что автоматическая "обратная оптимизация", по размеру кода, когда повторяющиеся логические блоки сворачиваются в циклы, - представляет трудность. Тут, впрочем, уже недалеко и до алгоритмической неразрешимости.