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

В радикалах корни алгебраических уравнений с рациональными коэффициентами возможно записать только в редких случаях – про это рассказывает отдельная записка. Интересно, что этот, – казалось бы, технический, – момент можно трактовать ещё строже, воспользовавшись теоретическими трудностями арифметики в действительных числах. То есть, коэффициенты уравнения – рациональные числа, которые можно точно записать любым привычным способом. Некоторые корни некоторых из этих уравнений тоже можно записать не менее привычным способом, поскольку данные корни – рациональные числа, как и коэффициенты. Но другие корни оказываются совершенно иной числовой природы (если вообще числовой – тут тоже возможны разные трактовки, связанные, как ни странно, с понятием вычислимости). Так, √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, хоть и использует весьма нетривиальные превращения в качестве основной операции.

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

Вообще, уравнение пятой степени x⁵ – 15x⁴ + 85x³ – 225x² + 274x – 120 == 0, например, имеет рациональные корни: 1, 2, 3, 4, 5 (проверьте), а корень уравнения x⁵ – 5 == 0 нетрудно записать “в радикалах” (5^1/5). Когда здесь говорят о “неразрешимости в радикалах”, то речь идёт о том, что существуют уравнения (степени n >= 5), для которых нельзя записать формулу, выражающую все корни через коэффициенты “в радикалах” (и, вообще говоря, таких уравнений очень много – примеры, которые приведены выше, это как раз редкие исключения). Интересно, что центральным моментом тут является как раз возможность записать – именно от неё можно начинать разбор ситуации. С одной стороны, можно представить себе некоторый калькулятор, который выполняет с комплексными числами четыре привычных действия (+, -, *, ÷) и позволяет извлекать корни (√ – это и есть “радикалы”). Комплексные числа тут необходимы потому, что без них достичь универсальности не выйдет даже для кубических уравнений с рациональными корнями – ведь комплексные числа и были обнаружены в ходе построения универсальных формул решения кубических уравнений (формула Кардано). С другой стороны, конечно, никакой реальный калькулятор не может считать даже в действительных числах, что уж там говорить про комплексные, где с радикалами возникают дополнительные проблемы.

Поэтому про формулу “в радикалах” лучше всего думать в том ключе, что она позволяет корни записать точно. Например, написать √2 или ∛5. Потому что точно выписать значение √2 в десятичной, например, системе нельзя, а вот обозначить число, квадрат которого равен двум, символом √2 – можно, и это будет точное обозначение. Например, если число ∛5 возвести в третью степень, то получится рациональное число 5, то есть, значение как бы запрыгивает в рациональные числа. Это важное для теории наблюдение: коэффициенты уравнения тоже рациональные, а выражение их в радикалах подразумевает, что существует способ запрыгнуть в рациональные через возведение в степень. Этому соответствует обратная операция – извлечение корня n-й степени. Собственно, вся классическая теория строится вокруг этого факта, но соответствующие симметрии оказываются весьма сложными для понимания: заметьте, что корни должны переставляться, сохраняя истинность некоторых соотношений между ними. Так, если уравнение квадратное, а корни a и b, то такие соотношения это (a + b) и a*b (формулы Виета). Неразрешимость в радикалах означает, что “радикальных формул”, позволяющих точно записать корни, не существует совсем. Для уравнений степени меньше пяти – такие формулы есть, и они даже универсальные, то есть, подходят для произвольного уравнения. А вот для степени пять и выше – нельзя выписать не только универсальную формулу, но даже и “специальную” для каждого (произвольного) уравнения.

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

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

Существование неразрешимых в радикалах уравнений пятой степени доказали Руффини и Абель, а в максимальной общности эту задачу решил Галуа (1832, но опубликованы его работы были позже). Галуа смог понять почему такие уравнения неразрешимы, впервые увидев структуры, на которых позже построили существенную часть современной алгебры. Сейчас тот аппарат, который касается именно уравнений, называют классической теорией Галуа. А в современной математике теория Галуа превратилась в большой самостоятельный инструмент, для которого, как и для всей современной алгебры, поиск решений уравнений уже не является фундаментальным аспектом.

Утверждение, что “параллельные прямые пересекаются” сейчас нередко встречается даже в более или менее серьёзных источниках. Например:

“Представим себе двумерное пространство — это легко. Например, бесконечную плоскость, где также справедливы аксиомы Евклида. […] Но можно легко представить и иной вариант — сферу. Это замкнутое конечное пространство, где параллельные прямые пересекаются, а сумма углов треугольника больше 180°”

Это цитата из статьи под названием “Космологический ликбез. Что такое Вселенная“, опубликованной на сайте издания “Троицкий вариант. Наука”.

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

Как ни странно, тут можно вспомнить европейскую живопись 16-17 вв., которая развивалась вместе с проективной геометрией. Способы построения художественной перспективы, определяющие то, как именно трёхмерная сцена сужается в двумерное полотно картины, требуют для изображений различных параллельных линий общей точки, принадлежащей недостижимому горизонту. Это лучше всего видно на тех картинах, где сюжет содержит какую-нибудь подходящую плоскость, замощённую прямоугольниками (или даже квадратами). Я в качестве примера взял работу Бартоломеуса ван Бассена (1651), где описанный только что принцип иллюстрируют сразу и пол, и флаги, и стены.

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

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

Сложно сказать, насколько сильно история изобразительного искусства повлияла на популярное суждение про “пересекающиеся параллельные прямые”, но знакомство с полотнами голландских живописцев свою роль тут наверняка сыграло.

Немного занимательных математических основ криптографии.

Российская криптосистема электронной подписи (ГОСТ 34.10-2012) работает в группе точек эллиптической кривой над конечным полем, как и криптосистема ECDSA, широко используемая в TLS и в других протоколах защиты информации. Можно ли устроить так, чтобы открытый и секретный ключи для ГОСТ-подписи и ECDSA – совпадали? Дело в том, что если ключи одинаковые, то это добавляет удобства: например, можно использовать некие унифицированные сертификаты. Естественно, это чисто теоретической вопрос, но он довольно занятный. Если вынести за скобки криптографические параметры и способ интерпретации битовых строк, то главное отличие между ГОСТ-подписью и ECDSA состоит в уравнениях, используемых этими криптосистемами. Упростим ситуацию и рассмотрим лишь уравнения вычисления значения подписи:

ECDSA: s = k^(-1)(h + rd)

ГОСТ: s = (rd + kh)

Здесь использованы общие буквенные обозначения: h – это подписываемое значение (можно считать, что это значение хеш-функции от сообщения – натуральное число); k – случайный параметр (натуральное число); r – значение х-координаты вычисляемой на основе k “случайной” точки кривой (это элемент конечного поля, но и его в нашем случае можно понимать как натуральное число), d – секретный ключ (натуральное число). Здесь везде опущены упоминания того, что значения вычисляются по модулю порядка группы точек, связанной с точкой-генератором G, но, опять же, это нисколько не помешает изложению.

Итак, сразу видно, что секретные ключи d для обоих вариантов математически эквивалентны, так как секретный ключ – это натуральное число. Это так и есть на практике, с оговоркой, что значение секретного ключа должно лежать в некотором интервале, но это технические детали. На практике, вряд ли имеет смысл использовать небольшое значение d, которое может оказаться угадываемым. То есть и для ГОСТ-подписи, и для ECDSA в качестве секретного ключа можно использовать одно и то же значение. Если оно находится в подходящем интервале, то в работе алгоритмов, реализующих криптосистемы, равным счётом ничего не поменяется.

Как быть с соответствующими открытыми ключами? С открытыми – уже не так просто. Открытый ключ в обоих криптосистемах – это точка кривой, полученная в результате “умножения” точки-генератора G на число d (значение секретного ключа): открытый ключ Q == dG. “Умножение” здесь взято в кавычки по той причине, что для точек кривой никакого умножения не определяется, но есть “повторное сложение” точек: так, 3*A == A + A + A, где A – точка кривой. Повторное сложение и позволяет ввести умножение на скаляры (на целые числа). Итак, открытый ключ – точка кривой Q – это пара координат (x, y). Значения координат, x и y, – элементы поля, над которым рассматривается кривая. Именно здесь и кроется отличие: штатно, обсуждаемые криптосистемы используют разные кривые и разные поля, поэтому полученные значения открытого ключа будут различными, если, конечно, мы хотим сохранить корректность прочих операций (а корректность сохранить необходимо).

Таким образом, из-за использования разных криптографических параметров (уравнения кривой, базового поля, точки-генератора), для одного и того же значения секретного ключа значения открытых ключей, вообще говоря, в ECDSA и ГОСТ-подписи не совпадут. Однако, если использовать одно и то же поле, одну и ту же кривую и генератор, то и значения открытых ключей будут равны, поскольку и в одной, и в другой криптосистеме – открытый ключ Q == dG. Обе криптосистемы могут работать на общей кривой – математические операции не отличаются. Понятно, что так как уравнения подписи разные, то подписи для одного и того же значения не будут совпадать, даже если ключи удалось привести к “единому формату”. (Естественно, подписи для сообщений могут отличаться и из-за использования разных хеш-функций.) Однако все операции (вычисление подписи, проверка) останутся корректными и для ECDSA, и для ГОСТ-подписи. Поэтому использовать, буквально, одну и ту же пару ключей (секретный – для вычисления подписи, а открытый – для проверки) уже окажется возможным.

Конечно, так как практические криптосистемы включают в свой состав не только математические операции, но и конкретные значения параметров, подобное объединение ключей вряд ли реализуемо за пределами занимательного упражнения.

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

Например, вот заметка от 28.09.2018, про алгоритм Шора.

Иногда приходится слышать, что существование квантового алгоритма Шора гарантирует, что существует и классический метод быстрого разложения на множители (актуальный, например, для RSA), использующий некоторую не найденную пока что “арифметическую структуру”. (Сейчас вот опять про простые числа и криптографию вспомнили, правда, в связи с некоторой шумихой вокруг гипотезы Римана.)

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