Как доказать что группа абелева

7

Абелевы группы

ТЕОРЕМА 1. Подгруппа циклической группы циклична.

Доказательство. Пусть — циклическая группа порядка ( и — ее подгруппа. Рассмотрим отображение переводящее целое число в степень . Проверим, что прообраз, , есть подгруппа в аддитивной группе целых чисел. Если , то — циклическая (единичная) подгруппа. Иначе, рассмотрим наименьшее натуральное число принадлежащее . Ясно, что . Докажем обратное включение. Пусть . Поделим на с остатком: . Тогда . В силу минимальности должно выполняться равенство , тем самым . Следовательно, равенство доказано. Тогда — циклическая группа.

СЛЕДСТВИЕ. Все подгруппы аддитивной группы целых чисел имеют вид , где

ОПРЕДЕЛЕНИЕ 1. Группа называется конечно порожденной, если существует конечный набор элементов , называемый порождающими элементами, который порождает группу . Это значит, что всякий элемент представим в виде , где каждый из либо порождающий элемент, либо обратен к порождающему элементу. Для абелевой группы набор будет порождающим, если и только если выполняется равенство

Далее мы будем иметь дело с группой целочисленных строк фиксированной длины :

Заметим, что она порождается элементами

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

ТЕОРЕМА 2. Строки образуют базис в группе тогда и только тогда, когда и

Доказательство. Если строки образуют базис в , то они же образуют базис линейного пространства . Потому . Далее, выразим каждую строку стандартного базиса через -ые:

На матричном языке это значит, что — единичная матрица. Вычисляя определитель левой и правой части, получим Так как слева в этом равенстве стоят целые числа, то каждое из них есть либо 1 либо -1.

Наоборот, если и , то матрица обратима над кольцом целых чисел (см. формулу обратной матрицы). Значит существует целочисленная -матрица такая, что . Следовательно, для любой строки выполняется равенство

Разложимость доказана. Единственность разложения следует из того, что — базис линейного пространства . □

Рассмотрим отображение такое, что

(здесь группа А задана соотношением (1)). Определим ядро отображения (4) как совокупность строк таких, что .

Прямая проверка убеждает нас в справедливости следующего утверждения.

ЛЕММА 1. Ядро — подгруппа в группе строк .

ТЕОРЕМА 3. Любая подгруппа группы строк конечно порождена и более того, имеет базис не более чем из элементов.

Доказательство – индукция по . Случай (база индукции) есть утверждение теоремы 1. Предположим для размерностей меньших утверждение теоремы 3 справедливо, и — подгруппа группы . Обозначим через проекцию на первую координату, т.е. . Образ есть подгруппа в и поэтому она имеет вид для некоторого . Выберем строку такую, что и обозначим . Лемма показывает (при и ), что — подгруппа. При этом . Индукционное предположение дает нам базис группы , состоящий из элемента и . Тогда — базис группы . Действительно, если , то найдется целое такое, что . Отсюда и поэтому . Тогда найдутся целые такие, что , откуда

Разложение доказано. Единственность разложения (5) достаточно доказать для нулевого и в предположении ненулевого . Итак, пусть . Применяя проекцию к левой и правой части этого равенства, получим , откуда Равенство возможно только при нулевых , что показывает предположение индукции. □

ТЕОРЕМА 4. Пусть – подгруппа в . Тогда в найдется базис такой, что

для некоторых целых неотрицательных таких, что при .

Доказательство сведем к элементарным преобразованиям целочисленных матриц. Согласно теореме 3 найдется базис подгруппы , состоящий не более чем из элементов. Запишем и составим -матрицу . Элементарные преобразования строк этой матрицы соответствуют замене базиса подгруппы , а элементарные преобразования столбцов этой матрицы соответствуют замене базиса группы .

Таким образом, на матричном языке утверждение теоремы звучит так: любую целочисленную матрицу элементарными преобразованиями строк и столбцов можно привести к диагональному виду , где при . Доказательство этого утверждения ведем индукцией по размеру матрицы . База индукции: — очевидный случай. Пусть равен НОД всех элементов матрицы . Пользуясь алгоритмом Евклида, элементарными преобразованиями строк и столбцов поместим на место (1;1). Все элементы получившейся матрицы (как, впрочем, и исходной матрицы ) делятся на . Тогда элементарными преобразованиями строк мы можем занулить все элементы первого столбца, стоящие под . Далее, элементарными преобразованиями столбцов зануляем все элементы первой строки, стоящие правее . Матрица приобретает блочный вид

Остается применить индукционное предположение к подматрице, отмеченной звездочками. □

СЛЕДСТВИЕ. Любая конечнопорожденная абелева группа есть прямая сумма циклических групп с порядками , где при

Доказательство. Пусть и – ядро эпиморфизма (4). Тогда группа изоморфна фактор-группе . Найдем в и согласованные базисы, т.е. базис пространства строк и натуральные числа такие, что при , кроме того и есть базис группы . Тогда

Научный форум dxdy

Последний раз редактировалось wowka19 10.03.2019, 22:21, всего редактировалось 1 раз.

Доказать, что группа абелева если
,
где a — произвольный элемент группы, а e — ее нейтральный элемент.
Задача кажется очень простой, но как я ни пытался — решить не выходит(
И не выйдет. Это неправда — возьмите в качестве и две разные транспозиции на трёх элементах.

Думаю, задача такая: квадрат любого элемента группы равен единице, доказать, что группа абелева. Это правда. Советую думать про . Чтобы прийти к нужному равенству можно домножить слева на , а справа на и посмотреть, что получится.

Последний раз редактировалось wowka19 10.03.2019, 22:26, всего редактировалось 1 раз.

Вместо одиночных элементов можно рассмотреть произведение . Чтобы прийти к нужному равенству можно домножить слева на , а справа на и посмотреть, что получится.

Черт возьми, как все просто. Уважаемый @Misuzu, как вы пришли к такому ходу? Поделитесь интуицией, а то я себя безнадежным чувствую.
И еще интересно утверждение для любой группы (не обязательно абелевой):
. Чтобы прийти к нужному равенству можно домножить слева на , а справа на и посмотреть, что получится.





Черт возьми, как все просто. Уважаемый @Misuzu, как вы пришли к такому ходу? Поделитесь интуицией, а то я себя безнадежным чувствую.
И еще интересно утверждение для любой группы (не обязательно абелевой):

Тем, кто знаком с криптографией с открытым ключом, наверно известны аббревиатуры ECC, ECDH и ECDSA. Первая — это сокращение от Elliptic Curve Cryptography (криптография на эллиптических кривых), остальные — это названия основанных на ней алгоритмов.

Сегодня криптосистемы на эллиптических кривых используются в TLS, PGP и SSH, важнейших технологиях, на которых базируются современный веб и мир ИТ. Я уже не говорю о Bitcoin и других криптовалютах.

До того, как ECC стала популярной, почти все алгоритмы с открытым ключом основывались на RSA, DSA и DH, альтернативных криптосистемах на основе модулярной арифметики. RSA и компания по-прежнему популярны, и часто используются вместе с ECC. Однако несмотря на то, что магия, лежащая в фундаменте RSA и подобных ей алгоритмов легко объяснима и понятна многим, а грубые реализации пишутся довольно просто, основы ECC всё ещё являются для большинства людей загадкой.

В этой серии статей я познакомлю вас с основами мира криптографии на эллиптических кривых. Моя цель — не создание полного и подробного руководства по ECC (в Интернете полно информации по этой теме), а простой обзор ECC и объяснение того, почему её считают безопасной. Я не буду тратить время на долгие математические доказательства или скучные подробности реализации. Также я представлю полезные примеры с визуальными интерактивными инструментами и скриптами.

В частности, я рассмотрю следующие темы:

1. Эллиптические кривые над вещественными числами и групповой закон
2. Эллиптические кривые над конечными полями и задача дискретного логарифмирования
3. Генерирование пар ключей и два алгоритма ECC: ECDH и ECDSA
4. Алгоритмы для взлома защиты ECC и сравнение с RSA

Часть 1: эллиптические кривые над вещественными числами и групповой закон

Эллиптические кривые

Во-первых: что такое эллиптическая кривая? В Wolfram MathWorld есть отличное и исчерпывающее определение. Но для нас достаточно того, что эллиптическая кривая — это просто множество точек, описываемое уравнением:

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

Различные формы эллиптических кривых (, изменяется от 2 до -3).

Виды особенностей: слева — кривая с точкой возврата (каспом) (). Справа — кривая с самопересечением (). Оба этих примера не являются полноценными эллиптическими кривыми.

В зависимости от значений и эллиптические кривые могут принимать на плоскости разные формы. Как можно легко увидеть и проверить, эллиптические кривые симметричны относительно оси .

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

Если нам требуется явным образом учитывать точку в бесконечности, то определение эллиптической кривой можно уточнить следующим образом:

Группы

В математике группа — это множество, для которого мы определили двоичную операцию, называемую «сложением» и обозначаемую символом +. Чтобы множество было группой, сложение нужно определить таким образом, чтобы оно соответствовало четырём следующим свойствам:

1. замыкание: если и входят в , то входит в ;
2. ассоциативность: ;
3. существует единичный элемент 0, такой, что ;
4. у каждого элемента есть обратная величина, то есть: для каждого существует такое , что .

1. коммутативность: ,

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

Группы удобны тем, что если мы докажем соблюдение всех четырёх свойств, то получим автоматически некоторые другие свойства «в нагрузку». Например: единичный элемент уникален; кроме того, обратные величины уникальны, то есть: для каждого существует единственное , такое, что (и мы можем записать как ). Непосредственно или косвенно эти и другие свойства групп очень пригодятся нам в будущем.

Групповой закон для эллиптических кривых

Мы можем определить группу для эллиптических кривых. А именно:

• элементы группы являются точками эллиптической кривой;
• единичный элемент — это бесконечно удалённая точка 0;
• обратная величина точки — это точка, симметричная относительно оси ;
• сложение задаётся следующим правилом: сумма трёх ненулевых точек , и , лежащих на одной прямой, будет равна .

Сумма трёх точек, находящихся на одной прямой, равна 0.

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

Пока всё идёт отлично. Но как нам вычислить сумму двух произвольных точек?

Геометрическое сложение

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

Проводим прямую через и . Прямая пересекает третью точку . Симметричная ей точка является результатом .

Геометрический способ работает, но требует усовершенствования. В частности, нам нужно ответить на несколько вопросов:

• Что если или ? Разумеется, мы не сможем провести прямую (0 не находится на плоскости ). Но поскольку мы определили 0 как единичный элемент, и для любой и любой .
• Что если ? В этом случае прямая, проходящая через две точки, вертикальна, и не пересекает третью точку. Но если является обратной величиной , то из определения обратной величины.
• Что если ? В этом случае через точку проходит бесконечное количество прямых. Здесь всё становится немного сложнее. Но представим, что точка . Что произойдёт, если мы заставим стремиться к , всё больше приближаясь к ней?

При сближении двух точек проходящая через них прямая становится касательной к кривой.

Если наша прямая пересекает только две точки, то это значит, что она является касательной к кривой. Легко увидеть, как результат сложения становится симметричным одной из двух точек.

Алгебраическое сложение

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

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

Если и не совпадают (), то проходящая через них прямая имеет наклон:

Пересечение этой прямой с эллиптической кривой — это третья точка :

Поэтому (обратите внимание на знаки и помните, что ).

Если бы нам нужно было проверить правильность результата, то пришлось бы проверить, принадлежит ли кривой и находятся ли , и на одной прямой. Проверка нахождения на одной прямой тривиальна, а проверка принадлежности кривой — нет, потому что нам придётся решать кубическое уравнение, что совсем невесело.

Вместо этого давайте поэкспериментируем с примером: согласно визуальному инструменту, при и , принадлежащих кривой , их сумма равна . Давайте проверим, соответствует ли это уравнениям:

Заметьте, что эти уравнения работают даже в случае, когда точка или является точкой касания. Давайте проверим на и .

Мы получили результат , который совпадает с результатом, полученным в визуальном инструменте.

К случаю нужно относиться немного иначе: уравнения для и остаются теми же, но с учётом того, что нам придётся использовать для наклона другое уравнение:

Заметьте, что, как можно ожидать, это выражение для является первой производной:

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

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

Скалярное умножение

Кроме сложения, мы можем определить и другую операцию: скалярное умножение, то есть:

где — натуральное число. Я написал визуальный инструмент и для скалярного умножения, так что можете поэкспериментировать с ним.

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

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

(Мы взяли каждый двоичный разряд и умножили на степень двойки.)

С учётом этого можно записать:

Алгоритм удвоения-сложения задаёт следующий порядок действий:

• Взять .
• Удвоить его, чтобы получить .
• Сложить и (чтобы получить результат ).
• Удвоить , чтобы получить .
• Сложить с результатом (чтобы получить ).
• Удвоить , получить .
• Не выполнять сложение с .
• Удвоить , чтобы получить .
• Сложить с результатом (чтобы получить ).
• .

Если вам это понятно не до конца, то вот скрипт на Python, реализующий этот алгоритм:

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

Логарифм

Для заданных и у нас есть по крайней мере один полиномиальный алгоритм вычисления . Но как насчёт обратной задачи? Что если мы знаем и , а нам нужно определить ? Эта задача известна как задача логарифмирования. Мы употребляем слово «логарифм» вместо термина «деление» для согласованности с другими криптосистемами (в которых вместо умножения используется возведение в степень).

Я не знаю ни одного «простого» алгоритма для решения задачи логарифмирования, однако экспериментируя с умножением, легко обнаружить некоторые закономерности. Например, возьмём кривую и точку . Мы можем сразу убедиться, что если нечётное, то находится на кривой в левой полуплоскости; если чётное, то — в правой полуплоскости. Если поэкспериментировать ещё, мы, возможно, найдём и другие закономерности, которые приведут нас к написанию алгоритма для эффективного вычисления логарифма этой кривой.

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

В следующей части мы исследуем конечные поля и задачу дискретной логарифмизации, а также примеры и инструменты для экспериментов.

Часть 2: эллиптические кривые над конечными полями и задача дискретного логарифмирования

В предыдущей части мы обсудили, как эллиптические кривые над вещественными числами можно использовать для определения групп. А именно, мы определили правило сложения точек: сумма трёх точек, лежащих на одной прямой, равна нулю (). Мы вывели геометрический и алгебраический способы вычисления сложения точек.

Затем мы ввели понятие скалярного умножения () и нашли «простой» алгоритм для вычисления скалярного умножения: удвоение-сложение.

Теперь мы ограничим эллиптические кривые конечными полями, а не вещественными числами, и посмотрим, что это изменит.

Поле целых чисел по модулю p

Конечное поле — это, в первую очередь, множество конечного числа элементов. Примером конечного поля является множество целых чисел по модулю , где — простое число. В общем виде это записывается как , или . Мы будем использовать последнюю запись.

Для полей существует две двухместные операции: сложение (+) и умножение (·). Обе они замкнуты, ассоциативны и коммутативны. Для обеих операций существует уникальный единичный элемент и для каждого элемента есть уникальный элемент обратной величины. И, наконец, умножение дистрибутивно относительно сложения: .

Множество целых чисел по модулю состоит из всех целых чисел от 0 до . Сложение и умножение работают как в модулярной арифметике. Вот несколько примеров операций над :

• Сложение:
• Вычитание:
• Умножение:
• Аддитивная инверсия: . Действительно:
• Мультипликативная инверсия:

Как мы уже сказали целые числа по модулю — это поле, поэтому все перечисленные выше свойства сохраняются. Учтите, что требование того, чтобы было простым числом, очень важно! Множество целых чисел по модулю 4 не является полем: 2 не имеет мультипликативной инверсии (т.е. уравнение не имеет решений).

Деление по модулю p

Скоро мы определим эллиптические кривые для , но прежде нам нужно чётко понимать, что означает над . Попросту говоря: , или, прямым текстом, в числителе и в знаменателе равно раз обратная величина . Это нас не удивляет, но даёт нам простой способ выполнения деления: найти обратную величину числа, а затем выполнить простое умножение.

Вычисление обратного числа можно «просто» выполнить с помощью расширенного алгоритма Евклида, который в худшем случае имеет сложность (или , если мы учитываем битовую длину).

Мы не будем вдаваться в подробности расширенного алгоритма Евклида, это не входит в рамки статьи, но я представлю работающую реализацию на Python:

Эллиптические кривые над

Теперь у нас есть все необходимые элементы для ограничения эллиптических кривых полем . Множество точек, которые в предыдущей части имели следующий вид:

теперь превращаются в:

где 0 — по-прежнему точка в бесконечности, а и — два целых числа в .

Кривая с . Заметьте, что для каждого существует максимум две точки. Также заметьте симметрию относительно .

Кривая — особая и имеет тройную точку в . Она не является истинной эллиптической кривой.

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

Сложение точек

Очевидно, что нам нужно немного изменить определение сложения, чтобы оно работало для . Для вещественных чисел мы сказали, что сумма трёх точек на одной прямой равна нулю (). Мы можем сохранить это определение, но что значит расположение трёх точек на одной прямой над ?

Можно сказать, что три точки находятся на одной прямой, если существует прямая, соединяющая их. Разумеется, прямые над отличаются от прямых над . Можно сказать, что прямая над — это множество точек , удовлетворяющих уравнению (это стандартное уравнение прямой с добавленной частью «»).

Сложение точек для кривой , при и . Заметьте, как соединяющая точки прямая «повторяет» себя на плоскости.

Учитывая то, что мы по-прежнему находимся в группе, сложение точек сохраняет уже известные нам свойства:

• (из определения единичного элемента).
• Для обратная величина — это точка, имеющая ту же абсциссу, но обратную ординату. Или, если угодно, . Например, если кривая над имеет точку , то обратной величиной будет .
• Кроме того, (из определения обратной величины).

Алгебраическая сумма

Уравнения для выполнения сложений точек в точности такие же, как в предыдущей части, за исключением того, что нам нужно добавлять в конце каждого выражения «». Поэтому, если , и , то можно вычислить следующим способом:

Если , то наклон принимает форму:

Иначе, если , мы получаем:

Уравнения не изменились, и это не совпадение: на самом деле, эти уравнения работают над любым полем, и над конечным, и над бесконечным (за исключением и , которые являются особыми случаями). Я чувствую, что это нужно объяснить. Но есть проблема: для доказательств группового закона обычно требуются сложные математические понятия. Однако я нашёл доказательство Стефана Фридла в котором используются только простейшие концепции. Прочитайте его, если вам интересно, почему эти уравнения работают (почти) над любым полем.

Вернёмся к кривым — мы не будем определять геометрический способ: на самом деле, с ним возникнут проблемы. Например, в предыдущей части мы сказали, что для вычисления нам придётся взять касательную к кривой в . Но при отсутствии непрерывности слово «касательная» теряет всякий смысл. Мы можем найти способ обойти эту и другие проблемы, однако чисто геометрический способ будет слишком сложным и совершенно непрактичным.

Вместо этого можно поэкспериментировать с интерактивным инструментом, написанным мной для выполнения сложений точек.

Порядок группы эллиптической кривой

Мы сказали, что эллиптическая кривая, определённая над конечным полем, имеет конечное количество точек. Нам нужно ответить на важный вопрос: сколько же в ней точек?

Во-первых, давайте определим, что количество точек в группе называется порядком группы.

Проверка всех возможных значений для в интервале от 0 до будет невыполнимым способом подсчёта точек, потому что потребует шагов, а эта задача «сложна», если — большое простое число.

К счастью, для вычисления порядка существует более быстрый алгоритм: алгоритм Шуфа. Я не буду вдаваться в его подробности — главное, что он выполняется за полиномиальное время, а именно этого нам и нужно.

Скалярное умножение и циклические подгруппы

Для вещественных чисел умножение можно определить как:

И, повторюсь, мы можем использовать алгоритм удвоения-сложения для выполнения умножения за , где — это количество бит ). Я написал интерактивный инструмент для скалярного умножения.

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

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

для любого целого . Заметьте, что благодаря оператору деления с остатком эти пять уравнений можно «ужать» в одно: .

Более того, мы можем сразу же показать, что эти пять точек замкнуты относительно операции сложения. Что это значит: как бы я ни суммировал , , , или , результатом всегда будет одна из этих пяти точек. И снова все остальные точки эллиптической кривой никогда не становятся результатом.

То же относится и ко всем остальным точкам, не только к . На самом деле, если мы возьмём в общем виде:

Что означает: если мы складываем два значения, кратных , то получаем значение, кратное (т.е. значения, кратные , замкнуты относительно операции сложения). Этого достаточно для того, чтобы доказать, что множество кратных значений — это циклическая подгруппа группы, образованной эллиптической кривой.

«Подгруппа» — это группа, являющаяся подмножеством другой группы. «Циклическая подгруппа» — это подгруппа, элементы которой циклически повторяются, как мы показали в предыдущем примере. Точка называется генератором или базовой точкой циклической подгруппы.

Циклические подгруппы — фундамент для ECC и других криптосистем. Позже я объясню, почему это так.

Порядок подгруппы

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

Пока мы определяли порядок как количество точек группы. Это определение по-прежнему действительно, но в циклических подгруппах мы можем дать новое аналогичное определение: порядок — это минимальное положительное целое , такое, что .

1. Вычисляем порядок эллиптической кривой с помощью алгоритма Шуфа.
2. Находим все делители .
3. Для каждого делителя порядка вычисляем .
4. Наименьшее , такое, что , является порядком подгруппы.

Учтите, что важно брать наименьший, а не случайный делитель. Если мы будем выбирать случайно, то можем получить , что не является порядком подгруппы, но является одним из кратных.

Ещё один пример: эллиптическая кривая, определяемая уравнением над полем , имеет порядок , которое является простым числом. Её подгруппы могут иметь порядок только или . Как вы можете догадаться, когда , подгруппа содержит только бесконечно удалённую точку; когда , подгруппа содержит все точки эллиптической кривой.

Поиск базовой точки

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

Во-первых, нужно ввести ещё одно понятие. Теорема Лагранжа подразумевает, что число всегда целое (потому что — делитель ). Число имеет собственное название: это кофактор подгруппы.

Теперь рассмотрим, что для каждой точки эллиптической кривой есть . Это справедливо, потому что — это кратное любому возможному . Исходя из определения кофактора, мы можем записать:

Теперь допустим, что — простое число (мы предпочитаем простые порядки по причинам, изложенным в первой части статьи). Это уравнение, записанное в такой форме, говорит нам, что точка создаёт подгруппу порядка (за исключением случая , в котором подгруппа имеет порядок 1).

В свете этого мы можем определить следующий алгоритм:

1. Вычисляем порядок эллиптической кривой.
2. Выбираем порядок подгруппы. Чтобы алгоритм сработал, число должно быть простым и быть делителем .
3. Вычисляем кофактор .
4. Выбираем на кривой случайную точку .
5. Вычисляем .
6. Если равно 0, то возвращаемся к шагу 4. В противном случае мы нашли генератор подгруппы с порядком и кофактором .

Дискретный логарифм

Как и в случае с непрерывными эллиптическими кривыми, теперь мы должны обсудить следующий вопрос: если мы знаем и , то каким будет , такое, что ?

Эта задача, известная как задача дискретного логарифмирования для эллиптических кривых, считается «сложной», для которой не обнаружено алгоритма полиномиального времени, выполняемого на классическом компьютере. Однако у этой точки зрения нет математических доказательств.

Эта задача аналогична задаче дискретного логарифмирования, используемой в других криптосистемах, таких как Digital Signature Algorithm (DSA), протокол Диффи-Хеллмана (D-H) и схема Эль-Гамаля. Названия задач совпадают неслучайно. Их разница в том, что в этих алгоритмах используется не скалярное умножение, а возведение в степень по модулю. Их задачу дискретного логарифмирования можно сформулировать так: если известны и , то каким будет , такое, что ?

Обе эти задачи «дискретны», потому что в них используются конечные множества (а конкретнее — циклические подгруппы). И они являются «логарифмами», потому что аналогичны обычным логарифмам.

ECC интересна тем, что на сегодняшний момент задача дискретного логарифмирования для эллиптических кривых кажется «сложнее» по сравнению с другими схожими задачами, используемыми в криптографии. Это подразумевает, что нам потребуется меньше бит для целого , чтобы получить тот же уровень защиты, что и в других криптосистемах, и мы это подробно рассмотрим в четвёртой, последней, части статьи.

Часть 3: ECDH и ECDSA

Параметры области определения

Алгоритмы эллиптических кривых будут работать в циклической подгруппе эллиптической кривой над конечным полем. Поэтому алгоритмам потребуются следующие параметры:

• Простое , задающее размер конечного поля.
• Коэффициенты и уравнения эллиптической кривой.
• Базовая точка , генерирующая подгруппу.
• Порядок подгруппы.
• Кофактор подгруппы.

Случайные кривые

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

Предположим теперь, что я дал вам параметры области определения кривой. Существует вероятность, что я обнаружил неизвестный никому новый класс слабых кривых, и, возможно, я создал «быстрый» алгоритм вычисления дискретных логарифмов для своей кривой. Как я могу убедить вас в обратном, т.е. в том, что мне неизвестно об уязвимостях? Как я могу гарантировать, что кривая «защищена» (в том смысле, что я не смогу её использовать для собственных атак)?

Чтобы решить эту проблему, иногда приходится использовать дополнительный параметр области определения: порождающее значение (seed) . Это случайное число, используемое для генерирования коэффициентов и или базовой точки , или того и другого. Эти параметры генерируются вычислением хеша . Хеши, как мы знаем, «просто» вычислить, но «сложно» реверсировать.

Простая схема генерирования случайной кривой из порождающего значения: хеш случайного числа используется для вычисления различных параметров кривой.

Если бы мы хотели сжульничать и воссоздать хеш из параметров области определения, то нам пришлось бы решать «сложную» задачу: инверсирование хеша.

Сгенерированная с помощью порождающего значения кривая называется проверяемо случайной. Принцип использования хешей для генерирования параметров известен как «nothing up my sleeve» («в рукавах ничего нет»), и широко распространён в криптографии.

Эта хитрость даёт определённую гарантию, что кривая не была специально создана таким образом, чтобы иметь известные её автору уязвимости. На самом деле, если я даю вам кривую вместе с порождающим значением, то это значит, что я не мог произвольно выбирать параметры и , и можно быть относительно спокойным, что я не смогу использовать специальные атаки. Причина использования слова «относительно» будет объяснена в четвёртой части.

Стандартизированный алгоритм генерирования и проверки случайных кривых описан в ANSI X9.62 и основан на SHA-1. Если интересно, можете прочитать об алгоритмах генерирования проверяемо случайных кривых в спецификации SECG (см. «Verifiably Random Curves and Base Point Generators»).

Я написал небольшой скрипт на Python, проверяющий все случайные кривые, поставляемые сейчас с OpenSSL. Крайне рекомендую посмотреть его!

Криптография на эллиптических кривых

Мы потратили много времени, но наконец добрались! Всё просто:

1. Закрытый ключ — это случайное целое , выбранное из (где — порядок подгруппы).
2. Открытый ключ — это точка (где — базовая точка подгруппы).

Теперь мы опишем два основанных на этом принципе алгоритма с открытым ключом: ECDH (Elliptic curve Diffie-Hellman, протокол Диффи-Хеллмана на эллиптических кривых), используемый для шифрования, и ECDSA (Elliptic Curve Digital Signature Algorithm), используемый для цифровых подписей.

Шифрование с помощью ECDH

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

Он решает следующую проблему: две стороны (обычно Алиса и Боб) хотят безопасно обмениваться информацией, чтобы третья сторона (посредник, Man In the Middle) мог перехватывать её, но не мог расшифровать. Например, это один из принципов TLS.

Вот как это работает:

1. Сначала Алиса и Боб генерируют собственные закрытые и открытые ключи. У Алисы есть закрытый ключ и открытый ключ , у Боба есть ключи и . Заметьте, что и Алиса, и Боб используют одинаковые параметры области определения: одну базовую точку на одной эллиптической кривой в одинаковом конечном поле.
2. Алиса и Боб обмениваются открытыми ключами и по незащищённому каналу. Посредник (Man In the Middle) перехватывает и , но не может определить ни , ни , не решив задачу дискретного логарифмирования.
3. Алиса вычисляет (с помощью собственного закрытого ключа и открытого ключа Боба), а Боб вычисляет (с помощью собственного закрытого ключа и открытого ключа Алисы). Учтите, что одинаков и для Алисы, и для Боба. На самом деле:

(Последняя формулировка используется в исходном алгоритме Диффи-Хеллмана, основанном на модулярной арифметике.)

Протокол Диффи-Хеллмана: Алиса и Боб могут «просто» вычислить общий секретный ключ, посреднику же придётся решать «сложную» задачу.

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

Задача Диффи-Хеллмана для эллиптических кривых считается «сложной». Считается, что она так же «сложна», как задача дискретного логарифмирования, но математических доказательств этому нет. Мы можем только с уверенностью сказать, что она не может быть «сложнее», потому что решение задачи логарифмирования — это способ решения задачи Диффи-Хеллмана.

Получив общий секретный ключ, Алиса и Боб могут обмениваться данными с симметричным шифрованием.

Например, они могут использовать координату ключа как ключ для шифрования сообщений такими безопасными шифрами, как AES или 3DES. Примерно это и делает TLS, разница в том, что TLS соединяет координату с другими числами, относящимися к подключению, а затем вычисляет хеш получившейся строки байтов.

Эксперименты с ECDH

Я написал ещё один скрипт на Python для вычисления закрытых/открытых ключей и общих секретных ключей над эллиптической кривой.

В отличие от показанных ранее примеров, в этом скрипте используется стандартизированная кривая, а не простая кривая на небольшом поле. Я выбрал кривую secp256k1 группы SECG («Standards for Efficient Cryptography Group», основанной Certicom). Та же самая кривая используется в Bitcoin для цифровых подписей. Вот параметры области определения:

• = 0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f
• = 0
• = 7
• = 0x79be667e f9dcbbac 55a06295 ce870b07 029bfcdb 2dce28d9 59f2815b 16f81798
• = 0x483ada77 26a3c465 5da4fbfc 0e1108a8 fd17b448 a6855419 9c47d08f fb10d4b8
• = 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141
• = 1

Разумеется, вы можете изменить скрипт и использовать другие кривые и параметры области определения, только обязательно используйте простые поля и обычную формулировку Вейерштрасса, иначе скрипт не будет работать.

Скрипт очень прост и содержит некоторые из описанных выше алгоритмов: сложение точек, удвоение-сложение, ECDH. Рекомендую изучить и запустить его. Он создаёт примерно такие выходные данные:

Эфемерное ECDH

Некоторые из вас, возможно, слышали об ECDHE, а не об ECDH. «E» в ECHDE обозначает «Ephemeral» (эфемерное) и связано с тем, что передаваемые ключи временны, а не статичны.

ECDHE используется, например, в TLS, где клиент и сервер генерируют свою пару закрытого-открытого ключа на лету, при установке соединения. Затем ключи подписываются сертификатом TLS (для авторизации) и передаются между сторонами.

Подписывание с помощью ECDSA

Сценарий следующий: Алиса хочет подписать сообщение своим закрытым ключом (), а Боб хочет проверить подпись с помощью открытого ключа Алисы (). Никто, кроме Алисы не должен иметь возможности создать действительные подписи. Каждый должен иметь возможность проверить подписи.

Алиса и Боб снова используют одинаковые параметры области определения. Мы рассмотрим алгоритм ECDSA, разновидность Digital Signature Algorithm, применённого к эллиптическим кривым.

ECDSA работает с хешем сообщения, а не с самим сообщением. Выбор хеш-функции остаётся за нами, но, очевидно, нужно выбирать криптографическую хеш-функцию. Хеш сообщения необходимо урезать, чтобы битовая длина хеша была такой же, что и битовая длина (порядок подгруппы). Урезанный хеш — это целое число и оно будет обозначаться как .

Алгоритм, выполняемый Алисой для подписывания сообщения, работает следующим образом:

1. Берём случайное целое , выбранное из (где — это по-прежнему порядок группы).
2. Вычисляем точку (где — базовая точка подгруппы).
3. Вычисляем число (где — это координата ).
4. Если , то выбираем другое и пробуем снова.
5. Вычисляем (где — закрытый ключ Алисы, а — мультипликативная инверсия по модулю ).
6. Если , то выбираем другое и пробуем снова.

Алиса подписывает хеш с помощью закрытого ключа и случайного . Боб проверяет правильность подписи сообщения с помощью открытого ключа Алисы .

Проще говоря, этот алгоритм сначала генерирует секретный ключ (). Благодаря умножению точек (которое, как мы знаем, является «простым» в одну сторону и «сложным» в обратную) секретный ключ прячется в . Затем привязывается к хешу сообщения уравнением .

Учтите, что для вычисления мы вычислили обратную величину по модулю . Как было сказано в предыдущей части, это гарантировано сработает только если — простое число. Если подгруппа имеет порядок непростого числа, ECDSA использовать не удастся. Неслучайно все стандартизированные кривые имеют простой порядок, а имеющие непростой порядок неприменимы для ECDSA.

Проверка подписей

Для проверки подписи необходим открытый ключ Алисы , (урезанный) хеш и, очевидно, подпись .

1. Вычисляем целое .
2. Вычисляем целое .
3. Вычисляем точку .

Корректность алгоритма

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

Начнём с . Из определения открытого ключа мы знаем, что (где — закрытый ключ). Можно записать:

С учётом определений и можно записать:

Здесь мы опустили «», как для краткости, так и потому, что циклическая подгруппа, сгенерированная точкой , имеет порядок , то есть часть «» избыточна.

Ранее мы определили . Умножив обе части уравнения уравнения на и поделив на , мы получаем: . Подставляя этот результат в наше уравнение для , получаем:

Это то же самое уравнение , которое было у нас на шаге 2 алгоритма генерирования подписи! При генерировании подписей и при их проверке мы вычисляем одну и ту же точку , просто разными наборами уравнений. Именно поэтому алгоритм работает.

Экспериментируем с ECDSA

Разумеется, я написал скрипт на Python для генерирования и проверки подписей. Код копирует некоторые части из скрипта ECDH, в частности, параметры области определения и алгоритм генерирования пары закрытого/открытого ключей.

Вот какие выходные данные создаются этим скриптом:

Как видите, скрипт сначала подписывает сообщение (байтовую строку «Hello!»), а затем проверяет подпись. После чего он пробует проверить ту же подпись для другого сообщения («Hi there!») и проверка не удаётся. Наконец, он пробуем проверить проверить подпись для правильного сообщения, но с другим случайным открытым ключом, после чего проверка тоже не удаётся.

Важность k

При генерировании подписей ECDSA важно хранить секретный по-настоящему в тайне. Если бы мы использовали одну для всех подписей или генератор случайных чисел оказался бы в какой-нибудь степени предсказуемым, то атакующий смог бы определить закрытый ключ!

Подобную ошибку сделала Sony несколько лет назад. На игровой консоли PlayStation 3 можно было запускать игры, только подписанные Sony алгоритмом ECDSA. То есть, если бы я хотел создать новую игру для PlayStation 3, я не смог бы распространять её среди пользователей без подписи Sony. Проблема заключалась в том, что все созданные Sony подписи были сгенерированы с помощью статичного .

(Похоже, создатели генератора случайных чисел Sony вдохновлялись или XKCD, или Дилбертом.)

В такой ситуации можно запросто восстановить закрытый ключ Sony, купив всего две подписанные игры, после чего извлечь их хеши ( и ) и подписи ( и ) вместе с параметрами области определения. Это делается так:

• Сначала нужно учесть, что (потому что и одинаковы для обеих подписей).
• Принять, что (этот результат следует непосредственно из уравнения для ).
• Умножить обе части уравнения на : .
• Разделить на , чтобы получить .

Похожие техники можно применить, если не статично, но каким-то образом предсказуемо.

Часть 4: алгоритмы для взлома защиты ECC и сравнение с RSA

В предыдущей части мы рассмотрели два алгоритма (ECDH and ECDSA) и разобрались, почему задача дискретного логарифмирования для эллиптических кривых играет важную роль для их безопасности. Но, если вы помните, мы сказали, что математических доказательств сложности задачи дискретного логарифмирования нет: мы полагаем, что она «сложна», но не уверены в этом. В первой части статьи мы попробовали оценить, насколько «сложна» она на практике в условиях современных технологий.

Во второй части мы попытались ответить на вопрос: зачем нам нужна криптография на эллиптических кривых, если RSA (и другие криптосистемы, основанные на модулярной арифметике) хорошо работают?

Взлом задачи дискретного логарифмирования

Теперь мы рассмотрим два наиболее эффективных алгоритма вычисления дискретных алгоритмов на эллиптической кривой: алгоритм «baby-step, giant-step» и ρ-алгоритм Полларда.

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

Baby-step, giant-step

Для начала приведу простое рассуждение: мы всегда можем записать любое целое как , где , и — три произвольных целых. Например, можно записать .

С учётом этого можно переписать уравнение задачи дискретного логарифмирования следующим образом:

Baby-step giant-step — это алгоритм «встречи посередине». В отличие от атаки перебором (при которой придётся вычислять все точки для каждого , пока мы не найдём ), можно вычислять «несколько» значений для и «несколько» значений для , пока мы не найдём соответствие. Алгоритм работает следующим образом:

1. Вычисляем
2. Для каждого из вычисляем и сохраняем результаты в хеш-таблицу.
3. Для каждого из :
   1. вычисляем ;
   2. вычисляем ;
   3. проверяем хеш-таблицу и ищем точку , такую, что ;
   4. если такая точка существует, то мы нашли .

   Алгоритм baby-step, giant-step: сначала мы вычисляем несколько точек с небольшим шагом и сохраняем их в хеш-таблице. Затем делаем великанские шаги и сравниваем новые точки с точками в хеш-таблице. Найдя соответствие, мы можем вычислить дискретный алгоритм простой перестановкой членов.

   Чтобы понять, как работает алгоритм, забудем на минуту о том, что кешируются, и возьмём уравнение . Рассмотрим, что из этого следует:

   • При мы проверяем, равно ли числу , где — одно из целых от 0 до . Таким образом, мы сравниваем со всеми точками от до .
   • При мы проверяем равно ли числу . Мы сравниваем со всеми точками от до .
   • При мы сравниваем со всеми точками от до .
   • .
   • При мы сравниваем со всеми точками от до .

   Если считать, что поиск в хеш-таблице занимает время то легко увидеть, что этот алгоритм имеет временную и пространственную сложность (или , если учесть битовую длину). Это всё ещё экспоненциальное время, но оно намного лучше, чем при атаке перебором.

   Baby-step giant-step на практике

   Имеет смысл разобраться, что же значит сложность на практике. Возьмём стандартизированную кривую: prime192v1 (она же secp192r1 , ansiX9p192r1 ). Эта кривая имеет порядок = 0xffffffff ffffffff ffffffff 99def836 146bc9b1 b4d22831. Квадратный корень из — это примерно 7,922816251426434 · 10 28 (почти восемьдесят октиллионов [прим. пер.: по короткой шкале]).

   Представим, что мы храним точек в хеш-таблице. Предположим, что каждая точка занимает ровно 32 байта: для хеш-таблицы потребуется примерно 2,5 · 10 30 байт памяти. Поискав в Интернете, можно узнать, что современная общая ёмкость накопителей всего мира имеет порядок зеттабайта (10 21 байт). Это почти на десять порядков меньше, чем объём памяти, необходимый нашей хеш-таблице! Даже если бы точки занимали по 1 байт каждая, мы всё равно не смогли бы хранить их все.

   Это впечатляет, и впечатляет ещё сильнее, если вспомнить, что prime192v1 — это одна из кривых с наименьшим порядком. Порядок secp521r1 (ещё одной стандартной кривой NIST) равен примерно 6,9 · 10 156 !

   Эксперименты с baby-step giant-step

   Я написал скрипт на Python, вычисляющий дискретные логарифмы с помощью алгоритма baby-step giant-step. Очевидно, что он работает только с кривыми малого порядка: не пытайтесь использовать secp521r1 , если только не хотите получить MemoryError .

   Скрипт выдаёт примерно такие выходные данные:

   ρ Полларда

   ρ Полларда — это ещё один алгоритм вычисления дискретных логарифмов. Он имеет ту же асимптотическую временную сложность , что и baby-step giant-step, но его пространственная сложность равна всего . Если baby-step giant-step не мог решить дискретные логарифмы из-за огромных требований к памяти, может быть, ρ Полларда справится? Давайте проверим…

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

   Найдя четыре целых числа, мы сможем использовать уравнение для вычисления :

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

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

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

   Задача заключается в следующем: как обнаружить цикл эффективным способом?

   Черепаха и заяц

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

   Но существует и более быстрый способ: алгоритм черепахи и зайца (также известный как алгоритм нахождения цикла Флойда). На рисунке ниже показан принцип работы метода черепахи и зайца, на котором основан ρ-алгоритм Полларда.

   У нас есть кривая и точки и . Точки принадлежат циклической подгруппе с порядком 5. Мы обходим последовательность пар с разными скоростями, пока не находим две разные пары и , дающих одну точку. В этом случае мы нашли пары и , что позволяет нам вычислить логарифм как . И на самом деле, у нас получилось .

   В сущности, мы берём псевдослучайную последовательность пар вместе с соответствующей последовательностью точек . Последовательность пар может быть или не быть циклической, но последовательность точек точно циклическая, потому что и сгенерированы из одной базовой точки, а из свойство подгрупп мы знаем, что не можем «сбежать» из подгруппы только скалярным умножением и сложением.

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

   Через какое-то время черепаха и заяц найдут одну точку, но с разными парами коэффициентов. Или, если выразить это уравнениями, черепаха найдёт пару , а заяц — пару , такие, что .

   Если случайная последовательность определяется через алгоритм (а не хранится статически), легко увидеть, что принцип работы требует всего пространства. Вычисление сложности асимптотического времени не так просто, но мы можем построить вероятностное доказательство, показывающее, что временная сложность равна ), как мы уже говорили.

   Экспериментируем с ρ Полларда

   Я создал скрипт на Python, вычисляющий дискретные логарифмы с помощью ρ-алгоритма Полларда. Это не реализация исходного ρ Полларда, а небольшая его вариация (я использовал более эффективный способ генерирования псевдослучайной последовательности пар). В скрипте есть полезные комментарии, так что прочитайте его, если вам интересны подробности алгоритма.

   Этот скрипт, как и baby-step giant-step, работает для маленьких кривых и создаёт те же выходные данные.

   Ро Полларда на практике

   Мы говорили, что baby-step giant-step невозможно использовать на практике из-за огромных требований к памяти. С другой стороны, ро-алгоритм Полларда требует очень мало памяти. Насколько же он практичен?

   В 1998 году Certicom начала соревнование по вычислению дискретных логарифмов на эллиптических кривых с битовой длиной от 109 до 369. На сегодняшний день успешно взломаны только кривые длиной 109 бит. Последняя успешная попытка была совершена в 2004 году. Процитируем Википедию:

   Как мы уже сказали, prime192v1 — это одна из «наименьших» эллиптических кривых. Мы также сказали, что ρ Полларда имеет временную сложность . Если бы мы использовали ту же технику, что и Крис Монико (тот же алгоритм, то же оборудование и количество машин), сколько бы заняло вычисление логарифма для prime192v1 ?

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

   Сравниние ρ Полларда и Baby-step giant-step

   Этот четвёртый скрипт вычисляет все логарифмы для всех точек на «маленькой» кривой с помощью разных алгоритмов и сообщает, сколько времени это заняло:

   Как и можно ожидать, метод перебора чудовищно медленный по сравнению с двумя другими. Baby-step giant-step быстрее, а ро-алгоритм Полларда больше чем в три раза медленнее baby-step giant-step (хоть он и использует гораздо меньше памяти и меньшее количество шагов в среднем).

   Посмотрите ещё и на количество шагов: для вычисления каждого логарифма способом перебора в среднем потребовалось 5193 шагов. 5193 очень близко к 10331 / 2 (половина порядка кривой). Baby-step giant-steps и ро Полларда использовали 152 шага и 138 шагов соответственно. Эти два числа очень близки к квадратному корню 10331 (101,64).

   Дальнейшие рассуждения

   В обсуждении этих алгоритмов я использовал много чисел. При их чтении важно быть внимательным: алгоритмы во многих аспектах можно сильно оптимизировать. Оборудование может улучшаться. Можно создать специализированное оборудование.

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

   Алгоритм Шора

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

   Эффективность квантовых алгоритмов заключается в суперпозиции состояния. У классических компьютеров ячейки памяти (т.е. биты) могут иметь значение 1 или 0. Между ними нет промежуточных состояний. С другой стороны, ячейки памяти квантовых компьютеров (кубиты) подвержены принципу неопределённости: пока их не измерят, у них нет полностью определённого состояния. Суперпозиция состояния не значит, что каждый кубит может одновременно иметь значение 0 и 1 (как часто пишут в Интернете). Она значит, что при измерении кубита у нас есть определённая вероятность наблюдать 0 и другая вероятность наблюдать 1. Работа квантовых алгоритмов заключается в изменении вероятности каждого кубита.

   Эта странность означает, что с ограниченным количеством кубитов мы можем одновременно иметь дело со множеством возможных входных данных одновременно. Например, мы можем сказать квантовому компьютеру, что существует число , равномерно распределённое между 0 и . При этом требуется всего кубитов вместо бит. Затем мы можем приказать квантовому компьютеру выполнить скалярное умножение . В результате мы получим суперпозицию состояний, заданную всеми точками от до , то есть если мы теперь измерим все кубиты, то получим одну из точек от до с вероятностью .

   Я рассказал об этом, чтобы вы поняли всю мощь суперпозиции состояний. Алгоритм Шора работает не совсем так, на самом деле он более сложен. Его усложняет то, что хотя мы и можем «симулировать» состояний одновременно, на каком-то этапе нам придётся снизить это количество состояний до нескольких, потому что на выходе нам нужно одно число, а не несколько (т.е., нам нужно знать один логарифм, а не множество вероятно ошибочных логарифмов).

   ECC и RSA

   Теперь давайте забудем о квантовых вычислениях, которые пока ещё не стали серьёзной проблемой. Я хочу ответить на следующий вопрос: зачем возиться с эллиптическими кривыми, если RSA и так работает хорошо?

   Простой ответ дал NIST, представив таблицу сравнения размеров ключей RSA и ECC, необходимых для получения одинакового уровня защиты.

   Размер ключа RSA (биты)	Размер ключа ECC (биты)
   1024	160
   2048	224
   3072	256
   7680	384
   15360	521

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

   Но почему это так? Ответ заключается в том, что самые быстрые алгоритмы для вычисления дискретных алгоритмов над эллиптическими кривыми — это ρ-алгоритм Полларда и baby-step giant-step, а в случае RSA есть более быстрые алгоритмы. В частности, один из них — это общий метод решета числового поля: алгоритм для факторизации целых чисел, который можно использовать для вычисления дискретных логарифмов. Общий метод решета числового поля — это на сегодняшний день самый быстрый алгоритм для факторизации целых чисел.

   Всё это относится и к другим криптосистемам, основанным на модулярной арифметике, в том числе к DSA, Диффи-Хеллману и Эль-Гамалю.

   Скрытые угрозы АНБ

   А теперь перейдём к сложной части. До этого момента мы обсуждали алгоритмы и математику. Настало время обсудить людей, и всё становится сложнее.

   Если вы помните, в третьей части мы говорили, что некоторые классы эллиптических кривых являются слабыми, поэтому для решения проблемы получения надёжных кривых от сомнительных источников мы добавляем случайное порождающее значение (seed) к параметрам области определения. И если посмотреть на стандартные кривые NIST, можно увидеть, что они проверяемо случайны.

   Если прочитать страницу Википедии о принципе «в рукавах ничего нет», можно заметить, что:

   • Случайные числа для MD5 получаются из синуса целых чисел.
   • Случайные числа для Blowfish получаются из первых чисел .
   • Случайные числа для RC5 получаются из и золотого сечения.

   Теперь возникает следующий вопрос: откуда берутся случайные порождающие значения для кривых NIST? Ответ: к сожалению, мы не знаем. Эти значения не имеют никакого обоснования.

   Возможно ли, что NIST обнаружил «значительно большой» класс слабых эллиптических кривых, попробовал различные возможные варианты порождающих значений и нашёл уязвимую кривую? Я не могу ответить на этот вопрос, но это закономерный и важный вопрос. Мы знаем, что NIST как минимум успешно стандартизировал уязвимый генератор случайных чисел (генератор, который, как ни странно, основан на эллиптических кривых). Возможно, он успешно стандартизировал и множество слабых эллиптических кривых? Как это проверить? Да никак.

   Важно понимать, что «проверяемо случайный» и «защищённый» не являются синонимами. И неважно, насколько сложна задача логарифмирования или насколько длинны ключи — если алгоритмы взломаны, то мы ничего не можем поделать.

   В этом отношении RSA побеждает, потому что ей не требуются специальные параметры области определения, которые можно эксплуатировать. RSA (как и другие системы модулярной арифметики) может быть хорошей альтернативой, если мы не можем доверять властям и если мы не можем создать собственные параметры области определения. И если вам любопытно: да, TLS может использовать кривые NIST. Если вы проверите в google, то увидите, что при подключении используются ECDHE и ECDSA с сертификатом, основанным на prime256v1 (она же secp256p1 ).

   Вот и всё!

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

   Стоит однако заметить, что прочитав только эту статью, вы не сможете реализовать защищённые криптосистемы на основе ECC: обеспечение безопасности требует знания многих тонких, но важных подробностей. Вспомните требования к атаке Смарта и ошибку Sony — это два примера того, как можно создать небезопасные алгоритмы и как легко их можно эксплуатировать.

   Итак, если вам интересно глубже погрузиться в мир ECC, то с чего же начать?

   Во-первых, пока мы видели кривые Вейерштрасса над простыми полями, но вы должны знать, что существуют и другие виды кривых и полей, а именно:

   Кривые Коблица над двоичными полями. Это эллиптические кривые в форме (где — 0 или 1) над конечными полями, содержащими элементов (где — простое число). Они обеспечивают особо эффективное сложение точек и скалярное умножение.

   И наконец, если вам интересны математические подробности, а не безопасность и эффективность алгоритмов, то нужно знать следующее:

   • Эллиптические кривые — это алгебраические многообразия рода 1.
   • Бесконечно удалённые точки изучаются в проективной геометрии. Они могут быть представлены с помощью однородных координат (хотя большинство из свойств проективной геометрии не нужны для криптографии на эллиптических кривых).

   Если вас интересует эта тема, то стоит искать по таким ключевым словам.

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

   Абелевы группы

   В этом разделе мы полностью опишем структуру конечно порожденных абелевых групп. Группа А называется конечно порожденной, если она порождается конечным множеством своих элементов: А = (В), В и . Мы уже встречали прямые суммы абелевых групп в примерах: группа из примера 1.5 есть не что иное, как а. группа из примера 1.21 и была обозначена как Ш 2 .

   Основные примеры абелевых групп — циклическая группа С_п порядка п и циклическая группа Z бесконечного порядка, которая есть просто аддитивная группа целых чисел.

   Теорема 1.69. Любая конечно порожденная аб&нева группа изомо]фна прямой сумме циклических групп.

   Замечание 1.70. Не все абелевы группы конечно порождены. Например, группа рациональных чисел Q относительно сложения не является конечно порожденной. Рассмотрим подгруппу < -1 не принадлежит группе (ах, а₂. а_п).

   Для построения изоморфизма из теоремы 1.69 удобно выделить структуру прямой суммы «внутри» группы А. Для этого введем новые понятия суммы подгрупп и прямой суммы подгрупп.

   Абелева группа А = Ах + А₂ -!-••• + А_п, порожденная подгруппами А], А₂, . А_п называется суммой подгрупп (или разлоэюепием группы на подгруппы). Если при этом для любого элемента a € А существует единственный набор таких

   ai ? Ai, что а = а + а₂ Н——Ь а_п, то группа А + А₂ Ч——1— А_п

   называется прямым разложением группы на подгруппы (или прямой суммой).

   Утверждение 1.71. Если А = А]_ + А₂ + • • • 4- А_п — прямое разложение абелевой группы, то А = А ф А₂ ф . Ф А_п.

   Доказательство. Искомый изоморфизм имеет вид

   

   В силу определения прямого разложения отображение ip корректно определено и взаимно однозначно. Проверим, что ip сохраняет операцию: если а = а + а₂ + • • • 4- о*,, где a i € Ai, а 6 = 61 + 6₂ + • • • + Ь_п, где hi G то а + Ь = («х + 6х) + +<а>2 + Ь₂) + • • • + (вп + 6_П) (здесь использована коммутативность), т. е. n . Поскольку каждый элемент группы А можно записать в виде целочисленной комбинации порождающих, то неудивительно следующее утверждение.

   Утверждение 1.73. Во введенных выше обозначениях А = Z n /R.

   Пример 1.74. Пусть А = С_П1 0 С_Л2 0 . 0 С_Пг. Обозначим через а_г порождающий элемент группы С_щ. Множество <а,->порождает А. По определению прямой суммы

   

   тогда и только тогда, когда с* = УхЩ, у_г Е Z. Значит, соотношения образуют подгруппу D в Z n , содержащую те наборы из п целых чисел, в которых г-й элемент набора делится на п_г. Смежный класс по подгруппе D состоит из множества наборов, имеющих заданный набор остатков от деления на щ, поэтому факторгруппа Z п /D изоморфна C_ni 0C_Tl2 0.. .0С_Пг.

   Доказательство утверждения 1.73. Пусть элемент а е А двумя способами выражен через порождающие:

   

   

   т. е. с—с’ € R. Разумеется, верно и обратное. Поэтому каждому а € А можно сопоставить класс смежности р(а) группы Z n по подгруппе Я, который состоит из тех с = (cj. ,с_п), для которых

   

   Отображение р является искомым изоморфизмом. Складывая соотношения (1.13), убеждаемся, что р сохраняет операции. Единственным прообразом класса с + R является ci ах Н—-+ с_па_п. ?

   Следующий шаг описание подгрупп группы Z ri .

   Лемма 1.75. Пусть R n . Тогда R = Z m , 0 ^ т ^ п.

   Подгруппой Z 0 будем по определению считать подгруппу, состоящую из одного нуля.

   Доказательство. Индукция по п. Основание индукции п = 1 было уже разобрано выше (см. вывод формулы (1.5) на с. 32).

   Теперь предположим, что утверждение леммы доказано при всех п’ п выделим подгруппу

   

   Поскольку Д₀ изоморфна подгруппе Z n_1 (равные нулю последние компоненты можно опустить), то по предположению индукции Д = Ъ к , 0 ^ к ^ п — 1.

   Если До = Д, утверждение леммы доказано.

   В противном случае рассмотрим подмножество R_n целых чисел, состоящее из последних компонент элементов г € Д. Это множество является подгруппой Z, поэтому имеет вид (d) (формула (1.5)). Выберем г = (п,Г2. ,r_n-i, f — tr G До- Поскольку последние компоненты всех элементов Д кратны d, такое число t обязательно найдется. Тогда г’ — tr G До, поэтому г’ представляется в виде суммы элемента До и элемента из подгруппы (г), и это представление однозначно определено.

   Итак, по утверждению 1.71,

   

   где 0 ^ т ^ п. ?

   Отметим очевидное следствие из доказанной леммы.

   Следствие 1.76. Для любой конечно порожденной абелевой группы существует такой конечный набор соотношений Ci. с*, что всякое соотношение с между порождающими является следствием С]. с*.

   Итак, из утверждения 1.73 и леммы 1.75 вытекает, что любую конечно порожденную абелеву группу с п порождающими элементами можно задать целочисленной матрицей размера т х га, т ^ га,

   

   Любой матрице М указанного вида соответствует группа

   

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

   Элементарное преобразование целочисленной матрицы это одно из следующих преобразований:

   • • прибавление к элементам одной строки соответствующих элементов другой строки, умноженных на одно и то же целое число;
   • • прибавление к элементам одного столбца соответствующих элементов другого столбца, умноженных на одно и го же целое число;
   • • перестановка строк;
   • • перестановка столбцов;
   • • умножение элементов некоторой строки или столбца на -1.

   Лемма 1.77. Пусть М’ получена из М последовательностью элементарных преобразований. Тогда А(М) = А(М’).

   Доказательство. Так как отношение изоморфизма траязи- тивно, лемму достаточно проверить для матриц, связанных одним элементарным преобразованием. Очевидно, что перестановка строк не влияет на Л(М), равно как и умножение на —1.

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

   Рассмотрим прибавление кратного строки. Пусть

   

   Тогда Cl = с — tc-2, поэтому А(М’), что

   

   Поскольку должен сохранять операции, образ любого элемента А(М) определен условиями (1.14):

   Проверим, что формула (1.15) корректно задает отображение из А(М) в А(М’). Пусть

   

   т. е. х = xiai + х₂а₂ + • • • + х_па_п = y_xai + у₂а₂ + • • • + у_па_п = У в группе А. Тогда

   

   

   так что тпц (вычитая подходящие кратные первой строки или первого столбца). После этого матрица приобретает вид

   

   где все ненулевые элементы матрицы М’ делятся на гац, а размер М’ меньше, чем у исходной матрицы.

   К матрице М’ можно применить такие же преобразования, какие были применены к М и т.д. В конце концов получим требуемую форму матрицы. ?

   Доказательство теоремы 1.69. Пусть А — конечно порожденная абелева группа. Представим ее в виде А = А(М). В силу леммы 1.77 и теоремы 1.78 можно считать, что матрица М диагональная. Если М = 0, то А = Z”. В противном случае обозначим ненулевые диагональные элементы матрицы М через n_t, 1 ^ г ^ к, соответствующие столбцам М порождающие элементы обозначим через а*. Соотношение вида =

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

   Из следствия 2.43 вытекает, что если р, q — взаимно простые числа, то C_pq = Cp®C_q. Поэтому можно построить такое разложение конечно порожденной абелевой группы в прямую сумму циклических, в котором все слагаемые — группы порядка р к где р — простое число (примарные компоненты).

   Оказывается, что набор порядков примерных компонент определен однозначно.

   Теорема 1.79. Любая конечная абелева группа изоморфна прямой сумме циклических групп порядков р к , р — простое, причем количество примерных компонент порядка р к одинаково для любого разложения в прямую сумму.

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

   Итак, пусть имеется конечная абелева группа Л. Ее можно разложить в прямую сумму примарных компонент:

   

   Выберем одно из чисел р, и докажем, что числа k_tJ не зависят от выбора разложения (1.16). Повторяя это рассуждение для всех простых делителей порядка группы, получим отсюда утверждение теоремы. Для простоты обозначений полагаем

   Pi = р, kij = kj, Si = S.

   Возведение в степень п ) образ А при гомоморфизме возведения в n-ю степень. Порядок группы |Л| = p a °q, где р q. Из основной теоремы арифметики следует, что число а₀ определено однозначно. Обозначим a_t = А^ Р fl ‘|, 1 ^ t (пяьпзд) задает искомый изоморфизм. Прежде всего нужно проверить корректность. Если пх = пу, где х = х + Х2, у = у г + У2> х,у € А, Х2,у2 ? Л-2, то по определению прямой суммы

   nxi = nx2, ra/i = nj/2- Таким образом, отображение cx корректно определено (не зависит от выбора представителя класса смежности). Проверим, что а сохраняет операцию:

   

   Из определения ясно, что а является взаимно однозначным отображением.

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

   Чтобы выразить at через kj. найдем образы циклических групп при гомоморфизмах возведения в степень.

   Если п делится на т, то для любого х Е С_т выполнено пх = 0 (порядок элемента делит порядок группы). Значит, в этом случае Ст^ — единичная группа. С другой стороны, если п взаимно просто с га, то для любого х Е С_т выполнено пх Ф 0. Это означает, что ядро гомоморфизма возведения в степень в этом случае нулевое и С= С_т.

   Пусть п = р г ,т = р к . Если t г имеют вид р г иа, 0 ^ и к

   г — 1, а — порождающий С_т). Если t ^ к, го Ст’* — единичная, так как п делит порядок группы.

   Из разложения (1.16) и изоморфизма (1.17) получаем

   

   Порядок группы равен произведению порядков прямых слагаемых. Поэтому получаем систему уравнений

   Читать:

   Ew result что это