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

На скриншоте ниже – результат работы нехитрой программы на языке Python, которая вычисляет в точке x == i (мнимая единица) значение функции, известной как j-инвариант – j(x).

j(x) – это модулярная функция, которая важна, например, в теории эллиптических кривых, но в настоящей заметке теоретические детали не играют существенной роли. Значение j(x) для мнимой единицы – это целое число 1728 (в каком-то смысле, по определению). А 1728 == 12^3, что тоже не является простым совпадением, так как 12 == 2^2 * 3. Можно j(x) записать в виде бесконечной суммы (разложение Фурье или q-expansion, если хотите, где q == exp(2*π*i*x)), что и используется в программе: j(x) == q^(-1) + 744*q^(0) + 196884*q^1 + 21493760*q^2 + 864299970*q^3 +… Коэффициенты – целые числа.

Поскольку модулярные формы имеют большое значение в арифметике, коэффициенты из разложения j-инварианта проявляются в математике довольно неожиданным образом, порождая даже отдельные направления (как в случае “Чудовищной бурды” – Monstrous Moonshine, самогон, который в русскоязычной “Википедии” едва не превратился в “Монструозный отблеск”). Но это тема для другой записки, более подробной. Здесь же отметим, что так как коэффициенты – целые числа, можно взять их побольше (например, 42) и посчитать значение j(x) “численными методами”, проверив, сойдётся ли, и насколько быстро, результат. Понятно, что если в выражение для q (см. выше) подставить x == i, вместо i*i получится -1, что и делает каждый очередной элемент суммы всё меньше и меньше, несмотря на увеличивающиеся коэффициенты.

Однако здесь есть хитрости. Если использовать обычные настройки Python, то точности для вычислений не хватает, результат не сходится. Если взять math.exp() и math.pi, точность по умолчанию, получаем 1728.000000000000014825929946, причём ещё на 13 шаге суммирования – не очень-то хороший результат: больше чем 1728. Увеличение точности само по себе тут не помогает, нужно использовать модуль decimal и ввести достаточно длинные значения для π и e, заменив math.exp() и math.pi на Decimal(E**(Decimal(-2)*Pi))**n, где E и Pi – значения со многими знаками после запятой. Точность в decimal устанавливается при помощи getcontext().prec. Результат со скриншота получен для prec = 81 в Python 3.5. Всё это хорошо иллюстрирует, что компьютеры не считают в действительных числах.

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

from decimal import Decimal, getcontext
getcontext().prec = 81
Pi =	Decimal('3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982')
E =	Decimal('2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427')
M = [
1, 744, 196884, 21493760, 864299970, 20245856256, 333202640600,
4252023300096, 44656994071935, 401490886656000, 3176440229784420,
22567393309593600, 146211911499519294, 874313719685775360,
4872010111798142520, 25497827389410525184, 126142916465781843075,
593121772421445058560, 2662842413150775245160, 11459912788444786513920,
47438786801234168813250, 189449976248893390028800, 731811377318137519245696,
2740630712513624654929920, 9971041659937182693533820, 35307453186561427099877376,
121883284330422510433351500, 410789960190307909157638144, 1353563541518646878675077500,
4365689224858876634610401280, 13798375834642999925542288376, 42780782244213262567058227200,
130233693825770295128044873221, 389608006170995911894300098560, 1146329398900810637779611090240,
3319627709139267167263679606784, 9468166135702260431646263438600, 26614365825753796268872151875584,
73773169969725069760801792854360, 201768789947228738648580043776000, 544763881751616630123165410477688,
1452689254439362169794355429376000
]
j = Decimal(0)
n = -1
for c in M:
	j = j + Decimal(c) * Decimal(E**(Decimal(-2)*Pi))**n
	print("j = ", j)
	n = n + 1
print("j^(1./3) =", float(j)**(1./3))

Попытаться построить квантовый компьютер на тысячи кубитов имеет смысл хотя бы для того, чтобы проверить, что имеющиеся модели работают для больших пространств состояний. Попытка факторизации 1024-битного числа на гипотетическом квантовом компьютере при помощи алгоритма Шора сталкивается с необходимостью как-то действовать в пространстве из 2^1024 состояний (ну, предположим). Влезет ли такое количество состояний во Вселенную? Насколько 2^1024 вообще большое?

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

Существенно ли (2^80)! превосходит 2^1024? Может показаться, что 2^1024 очень большое число. Однако провести сравнение нетрудно. Заметьте, что при вычислении факториала каждое чётное число повышает степень двойки (иногда – больше чем на единицу), поэтому 2^1024 вкладывается уже в 1026! (ну или примерно так; 1026 = 1024+2, проверьте; естественно, 171! больше 2^1024). Что уж говорить про (2^80)!! (Здесь второй восклицательный знак обозначает восклицание.) Теперь может показаться, что 2^1024 не такое уж и большое число, чтобы не вкладываться в качественно нарезанную Вселенную.

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

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

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

Генераторы текстов на заданную тему сейчас вновь популярны. Пример, естественно, ChatGPT. Можно ли автоматическим способом и с высокой точностью определить, что некоторый обозримый текст на естественном языке написан таким качественным компьютерным генератором, а не человеком?

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

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

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

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

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

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

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

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

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

Telegram использует “классический” (или “мультипликативный”) вариант DH, работающий в мультипликативной группе конечного поля (сейчас такой вариант принято обозначать FFDH – от Finite Field). Если обойтись без строгих научных терминов, то этот вариант DH не “эллиптический” (например), а “обычный”, работающий в арифметике остатков. Про “эллиптический” вариант многие слышали применительно к TLS – там он называется ECDH(E). То, что в Telegram не используется современный вариант на эллиптической кривой – всегда выглядело несколько странно. Скорее всего, этому есть очень простое объяснение, связанное с историей появления протокола MTProto, но, так или иначе, эти детали остаются за рамками данной заметки, которая посвящена свойствам модулей DH и небольшому фрагменту исходного кода приложения, связанному с проверкой этих свойств.

Чтобы определить конкретные параметры протокола DH (FFDH, но не только) – требуется задать достаточно большое простое число. В случае “классического” варианта битовая разрядность этого числа, по современным представлениям, должна быть хотя бы 2048 бит. Telegram требует строго 2048 бит (см. ниже). Данное простое число задаёт базовую структуру для арифметики протокола и называется модулем. От свойств модуля зависит надёжность реализации. Так, слишком маленькая разрядность, – например, 256 бит, – позволяет очень быстро решать обратную задачу (находить дискретный логарифм) и вычислять по открытой информации секретное значение, которым обмениваются стороны. (Дежурное замечание: пример про 256 бит – не относится к разрядности ECDH, там другие алгоритмы и структуры.)

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

Перейдём к особенностям кода. Telegram – среди тех немногих приложений, разработчики которых заявляют так называемую “воспроизводимую сборку“: действительно, публикация исходного кода, сама по себе, не гарантирует, что исполняемое приложение, распространяемое в собранном виде, соответствует опубликованным исходникам. Telegram предлагает описание того, как можно самостоятельно проверить соответствие сборки исходникам. Это хорошо (если работает – я не проверял). Я рассматриваю некоторый исходный код, доступный на GitHub-е по опубликованной ссылке.

Простое число P, представляющее собой модуль DH, поступает с сервера в ответе на запрос getDhConfig, в виде массива байтов. Свойства проверяются в telegram/messenger/SecretChatHelper.java вызовом функции Utilities.isGoodPrime(P, G); (G – это генератор, второй параметр протокола.)

if (!Utilities.isGoodPrime(res.p, res.g)) {
 acceptingChats.remove(encryptedChat.id);
 declineSecretChat(encryptedChat.id, false);
 return;
}

Вся содержательная проверка – внутри isGoodPrime() (telegram/messenger/Utilities.java). Эта функция начинается следующим фрагментом:

if (!(g >= 2 && g <= 7)) {
 return false;
}

if (prime.length != 256 || prime[0] >= 0) {
 return false;
}

BigInteger dhBI = new BigInteger(1, prime);

Первый if проверяет интервал значений генератора.
Следующий if – контролирует разрядность переданного модуля. 256 байтов – это 2048 бит. prime[0] >= 0 – тут проверяется, что старший бит установлен в единицу. Этот оборот может показаться не самым очевидным: тип byte в Java определён со знаком, соответственно, если значение больше либо равно нулю, это означает, что старший бит – нулевой (знак записи числа “плюс”); представление целых чисел большой разрядности (BigInteger – см. следующие строки) здесь использует запись, в которой старший байт – байт с нулевым индексом. Таким образом, prime[0] >= 0 проверяет, что получающееся число будет не меньше, чем 2^2047. new BigInteger(1, prime) – создаёт объект BigInteger и загружает в него значение модуля из массива prime. Единица в левом параметре конструктора – обозначает, что число положительное. Зачем нужен выше фрагмент с if, проверяющий длину и значение старшего бита? Например, сервер мог бы передать 256 байтов, в которых старшие значения были бы нулевыми, тогда длина массива соответствовала бы заданному требованию, но реальная разрядность получившегося в BigInteger числа оказалось бы меньше, так как нулевые байты слева не учитывались бы.

Дальше следует блок (здесь пропущен) из нескольких if..else if, которые, в соответствии со значением генератора, проверяют остатки по простым 3, 5, 7 и некоторым степеням 2. Этот фрагмент, наверное, можно рассмотреть в отдельной заметке из области занимательной математики. Цель проверки – контроль свойств полученного модуля (этим фрагментом вся проверка “доверия серверу” исчерпывается).

А следующая пара строк в telegram/messenger/Utilities.java довольно занимательная (приведено с сокращениями, см. детали ниже):

String hex = bytesToHex(prime);
if(hex.equals("C71CA...")) {
 return true;
}

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

Непосредственно в коде зашит вот такой модуль (переносы строк добавлены для удобства – это одно число):

C71CAEB9C6B1C9048E6C522F70F13F73980D40238E3E21C14934D037563D930F
48198A0AA7C14058229493D22530F4DBFA336F6E0AC925139543AED44CCE7C37
20FD51F69458705AC68CD4FE6B6B13ABDC9746512969328454F18FAF8C595F64
2477FE96BB2A941D5BCD1D4AC8CC49880708FA9B378E3C4F3A9060BEE67CF9A4
A4A695811051907E162753B56B0F6B410DBA74D8A84B2A14B3144E0EF1284754
FD17ED950D5965B4B9DD46582DB1178D169C6BC465B0D6FF9CA3928FEF5B9AE4
E418FC15E83EBEA0F87FA9FF5EED70050DED2849F47BF959D956850CE929851F
0D8115F635B105EE2E4E15D04B2454BF6F4FADF034B10403119CD8E3B92FCC5B

Это простое число (ну, с точностью до детерминированной проверки в SAGE и вероятностной проверки в Mathematica, конечно; но это означает, что простое). То есть, в этом фрагменте – код строго верит в один конкретный модуль. Для других модулей предусмотрена проверка простоты (и статуса safe prime):

BigInteger dhBI2 = dhBI.subtract(BigInteger.valueOf(1)).divide(BigInteger.valueOf(2));
return !(!dhBI.isProbablePrime(30) || !dhBI2.isProbablePrime(30));

Здесь, с помощью вероятностного теста (это единственный способ – известные детерминированные алгоритмы слишком ресурсоёмкие), проверяется, что модуль P простое число и что (P-1)/2 – тоже простое. Обычная практика. На этом проверки заканчиваются (естественно, здесь не может быть никакой аутентификации и тому подобных дополнительных шагов).

Нужно отметить, что сравнение получившихся ключей в Telegram должны проводить сами пользователи, по отпечаткам, которые им выводит приложение. Это тоже важный момент.

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

Всё это, кстати, связано и с подсчётом количества корней уравнений. Можно принять, что “бесконечные процессы” в качестве корней уравнений данного типа не допускаются. Геометрически, – пусть и несколько неожиданным образом, – это означает, что не всякие кривые, которые “пересекают” рациональную числовую координатную ось, имеют с этой осью общие точки. Потому что иррациональное число √2, например, не принадлежит множеству точек оси. А на другом конце геометрической интерпретации оказывается бесконечный процесс, возникающий в ходе геометрического доказательства иррациональности √2.

Разгадка к задаче про 2^255+19. В диалоге из “эпиграфа” к задаче говорится, что “очевидно, 2^255 + 19 делится на три”. Практически вся современная криптография так или иначе использует арифметику остатков. Поэтому понять, что 2^255 + 19 делится на три можно моментально: 2^255 при делении на 3 (mod 3) даёт остаток -1 (см. ниже); а 19 – это +1 (mod 3), потому что на 3 делится 18, соответственно, 19 == 6*3 + 1. Сумма остатков -1 + 1 == 0. Следовательно, число делится на три.

Почему 2^255 даёт остаток -1? Потому что 255 – нечётное число. Действительно, 2 в чётной степени будет давать остаток 1 (mod 3), а в нечётной остаток -1 (или 2, что здесь то же самое), так как 2 == 1*3 + (-1). Из этого можно вывести признак делимости на 3 для числа в двоичной записи, то есть, когда основание системы равно двум. А именно: биты со значением 1 (единица) на чётных позициях будут давать +1, на нечётных -1; если сумма (по единичным битам) делится на 3, то и само число делится. Пример (позиции считаем справа налево): 42 == 0b00101010; 1 + 1 + 1 == 3, следовательно, делится; 42 == 14*3; 43 == 0b00101011; 1 + 1 + 1 + (-1) == 2, следовательно, 43 не делится на 3.

Решение для 2^2023 + 2023. Доказываем, что делится на 3:
2^2023 (mod 3) == -1 (см. выше)
2023 = 2022 + 1; воспользуемся привычным признаком делимости для десятичной системы: 2 + 2 + 2 == 6, то есть, 0 (mod 3) => 2023 == 1 (mod 3)
-1 + 1 == 0

Естественно, возможны и другие, чем-то более привычные, способы. Например, в шестнадцатеричной системе, где 2^2023 это будет восьмёрка со множеством нулей, а 2023 == 0x07E7, поэтому в записи нашего числа, кроме нулей, встречаются только шестнадцатеричные цифры 8, 7, E и 7. В шестнадцатеричной системе действует тот же признак делимости на 3, что и в десятичной (“если сумма значений цифр делится на 3”), потому что основание системы 16 == 15 + 1, то есть, остаток 1. Шестнадцатеричное E это 14: 8 + 7 + 14 + 7 == 36; 36 == 12*3.

– Почему криптосистема называется X25519, откуда это 25519?
– Потому что там присутствует 2^255 и 19. Вот только “плюс” или “минус”? А, понятно, конечно, “минус”, поскольку 2^255+19 делится на 3, что очевидно.

Число, являющееся “модулем” в данной криптосистеме, должно быть простым. Соответственно, 2^255 – 19. Но выбор в большей степени обусловлен тем, что такое число имеет удобное двоичное представление: там много единичных битов подряд. Тем не менее, из наблюдения про 2^255 + 19 можно сделать задачу к Новому году: докажите, что 2^2023 + 2023 делится на три.

(Решение: записка и комментарии ниже.)

Иногда открытый ключ нужно буквально вводить руками, например, через “воздушный зазор”. Открытый ключ в ECDSA (и, кстати, в ГОСТ-подписи, но не только там) – это точка на кривой, заданной в параметрах. Речь тут про кривые, используемые в криптосистемах на практике, например, P-256. Координаты точки – это два числа X, Y (сторого говоря, два элемента соответствующего конечного поля, но это технические детали). Если разрядность 256 бит, то может показаться, что для передачи ключа придётся руками вводить 2*32 == 64 байта, что в hextext составит аж 128 знаков. Однако обычно можно ограничиться одной координатой X, а Y – вычислить из уравнения кривой. Такой способ кодирования называется сжатым представлением ключа. Единственная хитрость в том, что, так как в уравнение кривой Y входит в квадрате, координат, соответствующих данному X, пара. Это обратные по сложению элементы (всем привычные +/-). Поэтому нужно передать знак элемента, но для передачи знака достаточно одного дополнительного бита. Поэтому сжатое представление в два раза короче, но “разрядность ключа” при этом никак не страдает (страдают вычислительные затраты на принимающей ключ стороне, но этим часто можно пренебречь; иногда, впрочем, приключаются проблемы с обработкой заведомо неверных значений). Кстати, по этим же причинам ключи криптосистем с ed25519 короче в записи – они изначально “в сжатой форме”.

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

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

Запись чисел при помощи цифр различных систем счисления нередко приводит к недопониманию у тех, кто не очень хорошо представляет себе разницу между числами и их записью. Например, могут предположить, что 11 и 0x11 (в шестнадцатеричной записи, далее такая запись обозначается привычным префиксом) это одно и то же число, ну, как 7 и 0x7. Нетрудно наткнуться и на смешение свойств числа и его записи: то есть, на неверное представление о том, что какие-то свойства чисел соответствуют именно записи (запутывающее сочетание 0x100 == 2^8). Впрочем, всё это не мешает занимательным свойствам позиционных систем счисления интересным образом преобразовываться при переходе от одной системы к другой, сохраняя именно запись (то есть, цифры).

Так, если 1001001 умножить на 321, то получим 321321321. Почему? Очевидно: мы умножаем (10^6 + 10^3 + 10^0) на (10^2*3 + 10^1*2 + 10^0*1), то есть (10^6 + 10^3 + 10^0)*321. Известный, пусть и не очень широко, факт: всякое число, содержащие ровно три одинаковых тройки цифр в своей записи, делится на 333667. Примеры:
321321321/333667 == 963 == 3^2 * 107
111111111/333667 == 333 == 3 * 111
701701701/333667 == 2103 == 3 * 701

(Конструкция, конечно, переносится и на кратные записи, то есть, когда количество триплетов кратно трём.)

Выглядит занимательно. Причина в том, что на 333667 делится 1001001 == 3*333667. А 333667 – простое число. В записи 333667 нетрудно увидеть поразрядные “переносы единицы” при умножении на три. Можно ли найти число с такими же свойствами в шестнадцатеричной записи? Можно. Если в десятичной записи 3*3 == 9 == 10 – 1, где 10 – основание системы, то в шестнадцатеричной аналогом будет 3*5 == 15 == 0x10 – 1. Обратите внимание, что здесь 0x10 шестнадцатеричная запись числа 16, основания системы. Число другое, но нам здесь важны как раз некие свойства записи (а именно – позиция единицы). Искомое число – 0x555aab. Заметьте, что шестнадцатеричное 0xa равно 10 в десятичной системе, то есть, 5*2 (так же как и 3*2 == 6). Проверяем: 0x555aab * 0x3 == 0x1001001 (но это 16781313 в десятичной записи). Поэтому 0x321321321 делится на 0x555aab, а результат равен 0x963 (см. примеры в десятичной системе выше). Однако найденное нами “опорное” число хоть и полностью подходит по “свойствам” записи, но является составным: 0x13*0x25*0x49*0x6d == 0x555aab.

А вот в восмеричной системе ситуация иная. Число 0o1001001 (префикс 0o – обозначает восмеричную запись) – простое, а именно – 262657 == 8^6 + 8^3 + 8^0. Поэтому не получится найти делитель, который подходил бы для построения конструкции, аналогичной десятичной и шестнадцатеричной системам. Интересно, что число 46656216001 == 60^6 + 60^3 + 60^0 тоже простое. Это означает, что и в древней шестидесятеричной системе конструкция не сработает. Что ж, зато в десятичной системе 296296296296296296296296296/333667 == 888000000888000000888. Проверьте на калькуляторе.

Обычно, протокол Диффи-Хеллмана (DH) описывают на примере вычетов, то есть, арифметики остатков. Это так называемый классический вариант реализации протокола, который тоже используется на практике. При этом, протокол успешно обобщается на другие математические структуры, лишь бы они обладали некоторыми специальными свойствами. Эти свойства весьма важны для применимости протокола на практике.

Посмотрим на классический вариант DH: s = G^ab == G^ba (mod P), а именно – мы выбрали некоторое большое простое число P, выбрали натуральное G < P (это значение называют генератором), а в рамках операций протокола возводим G в секретную степень a или b по модулю P. Другими словами – вычисляем остаток от деления на P. Из привычного свойства степеней выводится нужное равенство, означающее, что стороны придут к одинаковому значению секрета s. Уже при разборе классического варианта можно обнаружить первое важнейшее общее свойство, о котором нередко забывают.

Действительно, стороны обмениваются значениями G^a и G^b по открытому каналу, соответственно, атакующему нужно вычислить a или b, по известному значению G^a или G^b. Почему же атакующий не может просто последовательно возводить G в натуральные степени, чтобы на каком-то шаге получить G^a (или G^b, но для примера возьмём только a), определив, таким образом, секретное значение? Ответ на этот вопрос такой: будем выбирать значение a достаточно большим, чтобы полный прямой перебор оказался вычислительно недоступным. Например, последовательно перебрать уже 2¹²⁸ значений, для нашей задачи, весьма и весьма затруднительно. (Техническая оговорка: классический протокол DH на практике использует значения гораздо большей разрядности – 4096 бит и больше; это связано с особенностями криптоанализа именно классического DH, и не должно нас смущать: 4096 бит, после применения некоторых оптимизаций, как раз превращаются, примерно, в 196 “честных” битов.) Итак, атакующий не может перебрать все показатели степени последовательно, потому что это очень долго. Но как же тогда быть сторонам, использующим DH, они же тоже возводят G в степень большой разрядности? Это и есть первое арифметическое свойство, необходимое для успешного обобщения DH.

Так как каждая сторона протокола знает своё секретное значение, она может воспользоваться тем, что, например, 16 == (2²)². То есть, вместо трёх умножений – ограничиться всего двумя: (2*2)*(2*2). Очевидно, что один раз вычислив 4 == 2*2, можно использовать 4 дальше. Зная нужное значение показателя, процесс вычисления нетрудно разбить на повторное “удвоение” (здесь – в смысле степени, но это весьма важный и более общий термин) и умножение на основание: 3⁵ == 3²*3²*3 == 243. Существенная экономия вычислительных ресурсов, которая выводится из того, что умножение в целых числах не зависит от расстановки скобок: a×a×a×a×a == (a×a)×(a×a×a) == a×(a×a×a×a). Вместо того, чтобы 128 раз умножать 3 на 3, вычисляя 3¹²⁹, можно поступить проще: 3¹²⁹ == 3¹²⁸*3 == (3⁶⁴)²*3 и т.д., рекурсивно. Всё это может показаться очевидным для целых чисел, особенно, если учесть тот факт, что описанный метод естественным образом отображается на двоичное представление, привычное для компьютерных вычислений. Однако при обобщении протокола DH данное свойство трансформируется: необходимо, чтобы арифметические операции в новой структуре позволяли выполнять “быстрое удвоение”. “Быстрое” – в смысле количества вычислительных операций.

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

Итак, следующая особенность DH – это протокол достаточно высокого уровня, чтобы его можно было переносить на другие структуры, с подходящей арифметикой. Обычно – на группы. Естественным препятствием здесь является наличие сложности решения обратной задачи. Если у нас есть функция DH с параметром, отображающая элемент новой структуры в другой элемент, задаваемый параметром, то эту функцию должно быть сложно обратить. В случае классического варианта протокола, скажем, что параметр – это показатель степени, а функция может быть представлена как S = G^x. Тогда обратная задача – это задача дискретного логарифмирования: нужно отыскать x, по известным G и S. Для эллиптической кривой обратная задача, обеспечивающая возможность переноса обобщённого DH, это задача вычисления показателя кратности (скаляра) x по двум известным точкам: S = xG. Например, в случае суперсингулярных (не будем вдаваться в технические подробности) эллиптических кривых протокол ECDH может оказаться уязвимым, поскольку существуют практические методы быстрого решения задачи дискретного логарифмирования для некоторых из этих кривых (методы эти позволяют свести задачу к вычетам, то есть, к области классического DH, но это детали). Как ни странно, это совсем не означает, что суперсингулярные эллиптические кривые не годятся для реализации DH.

Примером использования DH в совсем другом математическом окружении является постквантовый протокол CSIDH. С одной стороны, этот протокол работает на весьма экзотических объектах из области теоретической математики, а именно, на кольцах эндоморфизмов (и изогениях) эллиптических кривых (опять же, не обязательно понимать, что это такое), с другой стороны, применяемый алгоритм на уровне логики полностью аналогичен классическому DH, хоть и использует весьма нетривиальные превращения в качестве основной операции.