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

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

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

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

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

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



Комментарии (5) »

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

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

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

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

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

Источник: Wikimedia

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

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

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



Комментарии (1) »

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

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



Комментарии (2) »

“В магазин привезли два ящика с апельсинами. В каждом ящике – пять апельсинов. Сколько всего апельсинов привезли в магазин?”. Эта задача для начальной школы, а точнее – обсуждение её требуемого способа решения, как выясняется, несёт с собой много занимательных трактовок. Задача существует в различных вариантах (“диваны/подушки”, “полки/книги” и пр.), а её решение с постоянством обсуждается “в интернетах” уже несколько лет. Обсуждение вращается вокруг следующего момента: вариант решения “5*2 == 10” – учитель признаёт неверным; требуется решать так: “2*5 == 10 (апельсинов)”, поскольку в первом варианте “получаются ящики, а не апельсины“. Возможна и иная трактовка, в которой левое умножение заменяется правым, но для нас это не важно, поскольку причина бурных обсуждений состоит в том, что результат вообще зависит от порядка множителей. Почему-то считается, что это невозможно, поскольку умножение в натуральных числах коммутативно. Вообще, если отвлечься от неясных вопросов преподавания в начальной школе, то задача, взятая вместе с методикой решения, оказывается связанной с интересными аспектами математики и их проекцией в привычный опыт.

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

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

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

Распространённое конструктивное возражение такое: у нас же даны не апельсины, а “апельсины на ящик”. Да, это весьма разумный довод, опирающийся на введение некоторого понятия “размерности”. Действительно, умножаем число с размерностью “апельсины/ящик” на число с размерностью “ящик”, “ящики” сокращаются – получаем искомые апельсины, вне зависимости от порядка множителей (операндов). Это очень привычно (м/сек., кг/м2 и др.), поэтому мало кто замечает, что введение такой “размерности” подразумевает построение некоторой дополнительной теории. Почему при умножении “апельсины/ящик”*”ящик” – сокращаются именно “ящики”? Что такое “сокращаются”? А можно ли записать наоборот “ящик/апельсины”? Заметьте, что привычное деление, которое приходит тут на ум, мало того, что легко выводит за пределы натуральных чисел, так ещё и является некоммутативной операцией! (В алгебре деление вообще не рассматривают в “повседневном” смысле, а только умножение на обратный элемент. В частности, поэтому в натуральных числах универсального деления, в строгом смысле, просто нет. Что, конечно, никак не запрещает утверждать, что оно там всё же имеется, поскольку 12/3 == 4.) Другими словами, для того, чтобы реализовать коммутирующее преобразование типов при помощи только что описанного понятия “размерности”, потребуется принять некоторые вспомогательные соглашения, например, что a/b*b == a, и ситуация не отличается от соглашения про выбор типа правого (или левого) операнда.

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

Представьте гипотетический язык программирования, в котором предложения { 2 + “3” } и { “2” + 3 }, после преобразования компилятором, дают разные результаты: первый вариант – строку “23”, а второй – число 5. Исходя из рассмотренной выше задачи, нетрудно догадаться, почему такое происходит. Дело в том, что компилятор не только выполняет неявное преобразование типов, но ещё и “подгоняет” операции. В качестве главного типа компилятор выбирает тип правого операнда, приводя левый операнд к нему. Поэтому, в предложении { 2 + “3” } числовой тип двойки преобразуется в строку из символа “2”, а операция сложения превращается в конкатенацию (некоммутативная операция, кстати). Да. Не очень-то удобно, не то что апельсины по ящикам.



Комментарии (3) »

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

Эллиптическая кривая над конечным полем.

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

Что именно отображено на картинке (см. рисунок выше)? Каждой точке соответствует пара значений — элементов конечного поля. Сами эти элементы, обозначенные натуральными числами, формируют горизонтальную и вертикальную оси. А поскольку значения отображаются парами, то вся картинка соответствует F×F. Пары элементов — это пары, удовлетворяющие уравнению кривой: y2 = x3 + 2020x2 + x. Обратите внимание, что слева здесь квадрат, и уже из этого вытекает необходимость симметрии на картинке.

Возьмём более наглядный пример. На картинке ниже – нарисованы точки эллиптической кривой y2 = x3 + 17x2 + 1 над полем из 101 элемента; горизонтальная черта – разделяет “график” на верхнюю и нижнюю части (симметричные). Для двух точек – написаны их координаты: (26, 53) и (26, 48).

Кривая над полем из 101 элемента.

Почему точки симметричны? Потому что они обратные, их сумма в группе точек эллиптической кривой равна нулю (нейтральному элементу группы). Координаты X у этих точек совпадают, а координаты Y – обратные по сложению в базовом поле: 53 + 48 == 101, а это 0 (mod 101). Как уже упоминалось выше, левая часть уравнения – квадрат. Это означает, что у нас обязательно есть два элемента поля, соответствующих подстановке элемента 26 в правую часть. Полностью аналогично привычному 22 == (-2)2 == 4. Проверяем: 532 (mod 101) == 482 (mod 101) == 82, а 82 == (263 + 17*262 + 1) (mod 101). Понятно, что в группе, по определению, у каждого элемента есть обратный, поэтому картинка “ветвится” таким образом.

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



Комментировать »

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

В качестве базового поля выберем GF(8191) – конечное поле порядка 8191 (8191 – простое число). Это поле изоморфно вычетам по модулю 8191, то есть, мы рассматриваем остатки от деления на 8191: 0, 1, 2… – поэтому далее элементы поля обозначаются целыми числами.

Выберем уравнение, задающее эллиптическую кривую E:
y2 = x3 + 2020x2 + x.
Это уравнение в форме Монтгомери, общий вид таких уравнений:
y2 = x3 + Ax2 + x, где A – элемент базового поля; в нашем примере A == 2020.

Не всякую эллиптическую кривую над конечным полем можно представить в форме Монтгомери. (Нетрудно заметить, что все кривые в форме Монтгомери вполне определяются значением коэффициента А, это удобно.)

Точки кривой соответствуют парам (X, Y) элементов базового поля, удовлетворяющим уравнению, включая особую точку “бесконечность”, которая в группе точек является нейтральным элементом. Пример точки: (839, 7305). Можно проверить (например, в WoframAlpha), что 73052 (mod 8191) == (8393 + 2020*8392 + 839) (mod 8191). Заметьте, что пара (0,0) лежит на кривой, но не является нейтральным элементом! Нейтральный элемент мы будем обозначать пустой парой () или буквой O, а точка (0,0), если её сложить с точкой (839, 7305), даст точку (1523,5367). Групповую операцию на E обозначим символом “+”.

Группа точек нашей кривой E имеет порядок 8176, то есть, состоит из 8176 элементов. Сразу заметим, что эта кривая не подходит для практического использования, и не только потому, что здесь “мало точек”, но и из-за разложения числа 8176 == 24 * 7 * 73. Однако для нашего примера – именно это и нужно. Кроме базового поля и эллиптической кривой, параметры протокола ECDH включают точку кривой, которая называется генератором. Поскольку генератор – это точка на кривой, он является элементом её группы. Выбираем точку (1029, 895) на роль генератора. Обозначим генератор буквой G. Если генератор G складывать с самой собой, то на каком-то шаге получим нейтральный элемент группы. Количество экземпляров G, которые нужно сложить, чтобы получить нейтральный элемент, называется порядком элемента. Для выбранного значения G порядок равен 1022. Обратите внимание, что порядок точки-генератора меньше порядка группы. G – генерирует подгруппу в E, порядок подгруппы всегда делит порядок группы (теорема Лагранжа): 8176 == 8*1022.

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

Итак, мы выбрали поле GF(8191), уравнение кривой E y2 = x3 + 2020x2 + x, и генератор G = (1029, 895).

Кривая E

Введём умножение на скаляр: G + G + G = [3]G == 3*G. То есть, мы определили, что сложение трёх экземпляров точки с самой собой – записывается как 3*G. Важно заметить, что такое умножение – это не операция в группе точек кривой, а некоторая дополнительная конструкция.

Перейдём к протоколу ECDH между двумя сторонами. Стороны выбирают секретные скаляры – m и n, это целые положительные числа, меньшие порядка генератора G (понятно, что брать в качестве секретного скаляра единицу – особого смысла тоже нет). Стороны обмениваются по открытому каналу значениями m*G и n*G. Эти значения – точки на кривой, соответствующие n- и m-кратному сложению генератора G. Общий секрет стороны вычисляют так: m*(n*G) == n*(m*G) == (n*m)*G. Ограничение по порядку генератора вызвано тем, что нет смысла использовать числа, превышающие порядок: соответствующая точка всё равно будет находиться в подгруппе генератора.

Пример в числах:

m = 731
n = 395

m*G == (5720, 2990)
n*G == (6695, 8044)

m*(n*G) = [731](6695, 8044) == (4647, 2580) == n*(m*G) = [395](5720, 2990)

Таким образом, стороны получили общий секрет – точку на кривой с координатами (4647, 2580). Эта точка равна точке [731*395]G. Обратите внимание, что произведение 731 * 395 == 288745, можно привести по модулю 1022, то есть, по модулю порядка генератора G. (Но можно и не приводить – результат не изменится.) Значение общего секрета используется в качестве входных данных для вычисления ключей симметричного шифра. Именно так ECDH применяется в TLS. Точке соответствует пара (X, Y) элементов поля, но в качестве источника данных для ключа может использоваться только один элемент, обычно, это X-координата.

Сторона, прослушивающая канал, получила значения n*G и m*G, знает параметры поля, кривую, значение G, но не знает n и/или m. Вычисление n (или m) по известному n*G (или m*G) – называется задачей дискретного логарифмирования в конечной группе и, для произвольных групп точек эллиптической кривой достаточно большого порядка, вычислительно трудна. На практике используются параметры с порядками, близкими к 2256 (и более). Методов, позволяющих даже на специализированном суперкомпьютере за разумное время решить задачу дискретного логарифмирования для произвольных параметров и групп таких порядков – пока не найдено. Однако для некоторых специальных случаев – методы известны. Некоторые из этих методов элементарны, как будет видно из примера ниже.

Попробуем теперь взломать нашу “криптосистему” ECDH на эллиптической кривой. Конечно, в случае использованных параметров, не составляет труда простым перебором найти нужное значение секретного скаляра (оно лежит в интервале [2..1021]). Однако простой перебор здесь работает только потому, что порядок далёк от практических значений. Но есть гораздо более эффективный метод, который, с некоторыми упрощениям, и описан ниже.

Заметим, что число 1022 == 2 * 7 * 73. Это означает, что внутри нашей подгруппы генератора G могут быть меньшие подгруппы, порядок которых делит порядок генератора. Всякий элемент подгруппы представим в виде l*G – то есть: G + G+…+ G (l раз). Так что, возможно, найдутся такие элементы, которые конструируются из G, но при этом их порядок гораздо меньше 1022. Пусть такой элемент – P = (6736, 4842) == 14*G, где 14 == 1022/73 == 2 * 7. Используя P, мы можем “разбить” все элементы подгруппы генератора на подмножества с меньшим количеством элементов, каждый из которых соответствует той или иной “кратности” P. P имеет порядок 73, то есть 73*P == O, где O – нейтральный элемент группы (или, в других обозначениях: P + P + … + P = O). Это всего 73 различных значения (включая нейтральный элемент). Атака работает следующим способом. Сгенерируем и запишем в опорную таблицу все пары (k, k*P), где k пробегает [1..72]. Получив значение m*G (открытый ключ ECDH Q == m*G), мы будем вычитать из него G до тех пор, пока не обнаружим элемент, кратный P, который находится в опорной таблице. (Вычитание в группе эквивалентно сложению с обратным элементом, то есть -G, обратный к данному элемент группы кривой нетрудно вычислить.) Пусть мы на шаге q последовательного вычитания нашли подходящее k*P в таблице, тогда, зная k, мы можем вычислить секретный скаляр m == k * 1022/73 + q.

Проверим для m == 731, как в примере выше.

731*G == (5720, 2990). Вычитаем генератор G равный (1029, 895). Обратная к G точка – (1029, 7296), т.к. 7296 + 895 = 0 (mod 8191).

(5720, 2990) + (1029, 7296) == (5623, 8124)
(5623, 8124) + (1029, 7296) == (6316, 6614)
(6316, 6614) + (1029, 7296) == (7183, 6772)

Точка (7183, 6772) является кратной точкой для элемента P, который выбран нами выше в качестве опорного: [52]P == (7183, 6772). Таким образом, мы провели три операции сложения точек кривой (q == 3) и нашли заранее вычисленную опорную точку. Теперь мы можем определить секретный скаляр: 52 * 1022/73 + 3 == 731. Заметьте, что в одно значение P как бы “входит” 14 экземпляров G, то есть, чтобы гарантированно попасть в одну из точек опорной таблицы, потребуется не более 13 операций сложения точек. Для определения значения m == 731 прямым полным перебором – пришлось бы выполнить 730 сложений (если, конечно, не оптимизировать процесс поиска другим способом). Очевидно, что можно использовать и другие подгруппы для этой атаки – в каких-то случаях потребуется больше памяти для хранения опорной таблицы, но меньше операций с точками для поиска элемента таблицы; в других случаях – меньше памяти, но больше операций с точками.

Посмотрим, почему это работает, с другой стороны. В группе точек генератора все элементы представимы в виде l*G, для некоторого целочисленного l. Мы выбрали точку P == l*G. На следующем шаге мы вычисляем все значения k*P (их конечное количество) и записываем их в таблицу вместе с соответствующим k. То есть, мы построили таблицу дискретных логарифмов для P. Каждое из значений в таблице равно k*(l*G), что можно переписать как (k*l)*G (важно понимать, что здесь использованы два различных умножения: в целых числах, для k*l, и умножение скаляра на точку кривой для G). Соответственно, открытый ключ ECDH Q == m*G можно переписать как (k*l + r)*G, где k*l + r == m – представление целого m, где r – остаток от деления на l (0 <= r < l). Перепишем выражение: Q = (k*l)*G + r*G. (Здесь знак “+” уже превратился в обозначение операции сложения точек, но общий смысл не поменялся.) Мы вычитаем из значения Q генератор G до тех пор, пока полученный результат не совпадёт с каким-то из элементов нашей таблицы логарифмов для P, таким образом – подсчитывается значение остатка r. Как только мы нашли подходящий элемент в таблице, мы знаем все значения, нужные для вычисления секретного ключа m: значение k – из таблицы, l – известно из построения P, r – остаток, равный количеству операций вычитания, потребовавшихся для того, чтобы Q указало на тот или иной элемент таблицы. Таблица логарифмов содержит всего 72 элемента, что значительно меньше, чем 1022.

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



Комментировать »

Немного занимательной теории чисел, применительно к одной весьма экзотической особенности TLS (как известно, это основной защищённый протокол современного Интернета). Изучая настройки и параметры данного протокола, можно столкнуться с интересной формулой:

p = 2ⁿ – 2ⁿ⁻⁶⁴ + 2⁶⁴(⌊2ⁿ⁻¹³⁰e⌋ + x) – 1

Для чего она нужна и что обозначает?

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

Это формула, по которой генерируются простые числа, задающие группу для DH в TLS. n – требуемая разрядность, e – основание натурального логарифма, x – переменная, принимающая целые положительные значения. То есть, можно сказать, эта формула извлекает из числа e подходящее целое простое число нужной разрядности (подходящее – потому что подходит не всякое, но это детали). Для получения именно простого числа – нужно подбирать значение x (используется минимальное подходящее). Механизм описан в RFC 7919 (но попробуйте “нагуглить” эту формулу).

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

Впрочем, с фиксированными параметрами DH связаны и более простые рассуждения: стойкость DH базируется на сложности дискретного логарифмирования, но для классического варианта и заранее заданной группы (параметра, то есть) известно, что можно предвычислить некоторые алгебраические структуры, которые потом позволят вычислять логарифм быстро. Правда, такие вычисления требуют огромных мощностей и/или затрат времени. Но если вы теоретико-числовая служба специального агентства и заранее знаете, что набор из нескольких групп позволит раскрывать почти весь TLS-трафик, то можно и потратиться. Ключевой момент тут – нужно заранее знать группу, а универсальные методы неизвестны.



Comments Off on Формула для групп из TLS

Многие слышали про криптографию на эллиптических кривых. Но эллиптические кривые, которые давно являются мощным инструментом теории чисел, можно успешно применить к решению элементарной (по формулировке) арифметической задачки про бананы, яблоки и ананасы. Текст ниже – несколько сокращённая версия моего перевода ответа Quora.com, который дал Alon Amit (англ.).
Читать полностью



Comments Off on Фрукты и эллиптические кривые
Навигация по запискам: Раньше »