Использование эллиптических кривых в стандарте цифровой подписи – тема научной статьи по компьютерным и информационным наукам читайте бесплатно текст научно-исследовательской работы в электронной библиотеке КиберЛенинка

Baby-step, giant-step

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

$x$

как

, где

$a$

— три произвольных целых. Например, можно записать

$10 = 2 cdot 3   4$

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

Baby-step giant-step — это алгоритм «встречи посередине». В отличие от атаки перебором (при которой придётся вычислять все точки

$xP$

для каждого

$x$

, пока мы не найдём

$Q$

), можно вычислять «несколько» значений для

$bP$

и «несколько» значений для

$Q - amP$

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

  1. Вычисляем $m = leftlceil{sqrt{n}}rightrceil$
  2. Для каждого $b$ из ${0, dots, m}$ вычисляем $bP$ и сохраняем результаты в хеш-таблицу.
  3. Для каждого $a$ из ${0, dots, m}$:
    1. вычисляем $amP$;
    2. вычисляем $Q - amP$;
    3. проверяем хеш-таблицу и ищем точку $bP$, такую, что $Q - amP = bP$;
    4. если такая точка существует, то мы нашли $x = am   b$.


Как видите, изначально мы вычисляем точки

$bP$

с небольшим инкрементом («детскими шагами»

«baby step»

) для коэффициента

$b$

, …). Во второй части алгоритма мы вычисляем точки

$amP$

с большим инкрементом («великанскими шагами»

«giant step»

) для

$am$

, …, где

$m$

— большое число).

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


В итоге

мы проверили все точки от $0P$ до $nP$

(то есть все возможные точки),

выполнив не более $2m$ сложений и умножений

(ровно

$m$

для «детских шагов», не более

$m$

для «великанских шагов»).

Если считать, что поиск в хеш-таблице занимает время $O(1)$временную и пространственную сложность $O(sqrt{n})$ (или $O(2^{k / 2})$, если учесть битовую длину). Это всё ещё экспоненциальное время, но оно намного лучше, чем при атаке перебором.

Ρ полларда

ρ Полларда — это ещё один алгоритм вычисления дискретных логарифмов. Он имеет ту же асимптотическую временную сложность

$O(sqrt{n})$

, что и baby-step giant-step, но его пространственная сложность равна всего

$O(1)$

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

Для начала ещё раз напомню задачу дискретного логарифмирования: найти для заданных $P$$Q$$x$$Q = xP$$P$$Q$целые $a$, $b$, $A$ и $B$, такие, что $aP   bQ = AP   BQ$.Найдя четыре целых числа, мы сможем использовать уравнение $Q = xP$$x$


Теперь мы можем избавиться от

$P$

. Но прежде чем сделать это, вспомним, что наша подгруппа циклическая и имеет порядок

$n$

, то есть коэффициенты, используемые при умножении точек, берутся по модулю

$n$

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

псевдослучайную последовательность пар $(a, b)$

. Эту последовательность пар можно использовать для генерирования последовательности точек

$aP   bQ$

. Поскольку

$P$

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

последовательность точек $aP   bQ$ тоже циклическаяЭто значит, что если мы обойдём нашу псевдослучайную последовательность пар $(a, b)$мы найдём пару $(a, b)$ и другую отдельную пару $(A, B)$, такие, что $aP   bQ = AP   BQ$. Те же точки, отдельные пары: мы сможем применить приведённое выше уравнение для нахождения логарифма.

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

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

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

Для начала давайте избавимся от самых раздражающих тупиковых ситуаций. Мы уже знаем, что $P   (-P) = 0$$P   0 = 0   P = P$две ненулевые несимметричные точки $P = (x_P, y_P)$ и $Q = (x_Q, y_Q)$.Если $P$ и $Q$ не совпадают ($x_P ne x_Q$наклон:Пересечение

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

$R = (x_R, y_R)$

или, аналогично:


Поэтому

$(x_P, y_P)   (x_Q, y_Q) = (x_R, -y_R)$

(обратите внимание на знаки и помните, что

$P   Q = -R$$R$$P$$Q$$R$$R$визуальному инструменту, при $P = (1, 2)$$Q = (3, 4)$$y^2 = x^3 - 7x   10$$P   Q = -R = (-3, 2)$

Да, всё верно!

Заметьте, что эти уравнения работают даже в случае, когда точка $P$ или $Q$ является точкой касания. Давайте проверим на $P = (-1, 4)$$Q = (1, 2)$

Мы получили результат

$P   Q = (1, -2)$

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

К случаю $P = Q$ нужно относиться немного иначе: уравнения для $x_R$$y_R$$x_P = x_Q$наклона другое уравнение:


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

$m$

является первой производной:

Чтобы доказать правильность этого результата, достаточно убедиться, что

$R$

принадлежит к кривой и что прямая, проходящая через

$P$

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

$P = Q = (1, 2)$


Что даёт нам

$P   P = -R = (-1, -4)$

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

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

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

квантовый алгоритм, способный вычислять дискретные логарифмы за полиномиальное время: алгоритм Шора

со временной сложностью

$O((log n)^3)$

и пространственной сложностью

$O(log n)$

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

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

Эта странность означает, что с ограниченным количеством кубитов мы можем одновременно иметь дело со множеством возможных входных данных одновременно. Например, мы можем сказать квантовому компьютеру, что существует число $x$$n - 1$$log n$$n log n$$xP$$0P$$(n - 1)P$$0P$$(n - 1)P$$1 / n$$n$

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

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

$P   Q   R = 0$

как

$P   Q = -R$

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

$P$если мы проведём линию, проходящую через $P$ и $Q$, эта прямая пересечёт третью точку кривой $R$

(это подразумевается, потому что

$P$

находятся на одной прямой)

. Если мы возьмём обратную величину этой точки $-R$, мы найдём сумму $P   Q$Проводим прямую через $P$ и $Q$. Прямая пересекает третью точку $R$. Симметричная ей точка $-R$ является результатом $P   Q$.

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

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

    Поскольку $Q'$ стремится к $P$, прямая, проходящая через $P$ и $Q'$ становится касательной к кривой. В свете этого мы можем сказать, что $P   P = -R$, где $R$ — это точка пересечения между кривой и касательной к кривой в точке $P$.

  • Что если $P ne Q$, но третьей точки $R$ нет? В этом случае ситуация похожа на предыдущую. На самом деле, в этой ситуации прямая, проходящая через $P$ и $Q$, является касательной к кривой.
    Если наша прямая пересекает только две точки, то это значит, что она является касательной к кривой. Легко увидеть, как результат сложения становится симметричным одной из двух точек.

    Предположим, что $P$ является точкой касания. В предыдущем случае мы записали $P   P = -Q$. Это уравнение теперь превращается в $P   Q = -P$. С другой стороны, если бы точкой касания была $Q$, то правильным было бы уравнение $P   Q = -Q$.

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

взгляните на визуальный инструмент на HTML5/JavaScript, созданный мной для вычисления сумм эллиптических кривых

Группы

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

$mathbb{G}$

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

  1. замыкание: если $a$ и $b$ входят в $mathbb{G}$, то $a   b$ входит в $mathbb{G}$;
  2. ассоциативность:$(a   b)   c = a   (b   c)$;
  3. существует единичный элемент 0, такой, что $a   0 = 0   a = a$;
  4. у каждого элемента есть обратная величина, то есть: для каждого $a$ существует такое $b$, что $a   b = 0$.


Если мы добавим пятое требование:

  1. коммутативность:$a   b = b   a$,

то группа называется

абелевой группойПри обычной записи сложения множество целых чисел $mathbb{Z}$$mathbb{N}$единичный элемент уникален; кроме того, обратные величины уникальны, то есть: для каждого $a$$b$$a   b = 0$$b$$-a$

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

Скоро мы определим эллиптические кривые для

$mathbb{F}_p$

, но прежде нам нужно чётко понимать, что

$x / y$

означает над

$mathbb{F}_p$

. Попросту говоря:

$x / y = x cdot y^{-1}$

, или, прямым текстом,

$x$

в числителе и

$y$

в знаменателе равно

$x$

раз обратная величина

$y$

. Это нас не удивляет, но даёт нам простой способ выполнения деления:

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

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

def extended_euclidean_algorithm(a, b):
    """
    Возвращает кортеж из трёх элементов (gcd, x, y), такой, что
    a * x   b * y == gcd, где gcd - наибольший
    общий делитель a и b.

    В этой функции реализуется расширенный алгоритм
    Евклида и в худшем случае она выполняется O(log b).
    """
    s, old_s = 0, 1
    t, old_t = 1, 0
    r, old_r = b, a

    while r != 0:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
        old_t, t = t, old_t - quotient * t

    return old_r, old_s, old_t


def inverse_of(n, p):
    """
    Возвращает обратную величину
    n по модулю p.

    Эта функция возвращает такое целое число m, при котором
    (n * m) % p == 1.
    """
    gcd, x, y = extended_euclidean_algorithm(n, p)
    assert (n * x   p * y) % p == gcd

    if gcd != 1:
        # Или n равно 0, или p не является простым.
        raise ValueError(
            '{} has no multiplicative inverse '
            'modulo {}'.format(n, p))
    else:
        return x % p

Использование эллиптических кривых в стандарте цифровой подписи

©

Читайте также:  Как получить электронную подпись для юридических лиц

Анисимова Э.С.

Ассистент, кафедра информатики и дискретной математики,

Елабужский институт (филиал) ФГ АОУ ВПО КФУ

ИСПОЛЬЗОВАНИЕ ЭЛЛИПТИЧЕСКИХ КРИВЫХ В СТАНДАРТЕ ЦИФРОВОЙ

ПОДПИСИ

Аннотация

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

Ключевые слова: эллиптическая кривая, электронно-цифровая подпись.

Keywords: elliptic curve, digital signature.

Пусть GF(q), q p представляет собой конечное поле с характеристикой р. Эллиптическая кривая определяется уравнением

E(GF(q)) : у2 a1 xy a3 y = x3 a0 x2 a2 x a4 (mod p)

Если характеристика p>3, то это уравнение эквивалентно следующему:

у = x ах b (mod p). Будем рассматривать в данном курсе только эллиптические кривые над полями характеристики р>3.

Рис. 1. Эллиптическая кривая

Кратные точки эллиптической кривой являются аналогом степеней чисел в простом поле схемы Эль-Гамаля. Задача вычисления кратности точки эквивалентна задаче вычисления дискретного логарифма. Хотя задачи дискретного логарифмирования и задачи вычисления кратности точки эллиптической кривой полиноминально эквивалентны, вторая имеет большую сложность. Именно поэтому при построении алгоритмов подписи в группе точек эллиптической кривой оказалось возможным обойтись более короткими ключами по сравнению с простым полем при обеспечении большей стойкости.

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

Выбор точки Q зависит от используемых алгоритмов и весьма непрост. Так, стандарт ГОСТ 34.10-2001 определяет, что точка Q должна иметь порядок q, где q — простое число с «хорошими алгебраическими свойствами». Число q довольно велико (2254 < q < 2256). При построении конкретного алгоритма, реализующего вычисление цифровой подписи, американский стандарт предполагает использование алгоритма DSA. Новый российский стандарт использует модифицированную версию старого ГОСТ Р 34.10-94. Оказалось, оба они

© Анисимова Э.С., 2021 г.

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

Из-за очевидной трудности взлома алгоритм ECDLP можно применять для высоко защищенных систем; обеспечивая сопоставимый уровень безопасности, алгоритм имеет значительно меньшие размеры ключа, чем, например, алгоритмы RSA или DSA. В приведенной ниже таблице сравниваются приблизительные размеры параметров эллиптических систем и RSA, обеспечивающих одинаковую стойкость шифра, которая рассчитывается на основе современных методов решения ECDLP и факторинга (поиска делителей) для больших целых чисел.

Система на основе ЭК

106 бит

132бит

160бит

224бит

RSA (длина модуля n)

512бит

768бит

1024бит

2048бит

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

Разумеется, существуют и проблемы, которые ограничивают повсеместное

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

Заключение

Криптосистемы на основе эллиптической кривой получают все большее распространение скорее как альтернатива, а не замена системам на основе RSA, поскольку системы на основе ECDLP имеют некоторые преимущества, особенно при использовании в устройствах с маломощными процессорами и/или маленькой памятью. Типичные области применения:

– m-commerce (мобильная торговля) ( например, WAP сотовые телефоны, карманные компьютеры);

– смарт-карты (например, EMV);

– e-commerce (электронная торговля) и банковские операции (например, SET);

– интернет-приложения (например, SSL).

Литература

1. E.S. Anisimova, R.R. Ibatullin – About One Method of On-Line Signature Verification Using Radial Basis Function // Modern Applied Science. – 2021. Vol. 9, No. 1. doi:10.5539/mas.v9n1p137

2. Э.С. Анисимова – Идентификация подписи с использованием радиального базиса // Фундаментальные исследования. – 2021. – № 9-6. – С. 1185-1189.

3. Э.С. Анисимова – Самоорганизующиеся карты Кохонена в задачах кластеризации // Актуальные проблемы гуманитарных и естественных наук. – 2021. – № 9. – С. 13-16.

4. Э.С. Анисимова – Издательская деятельность в школе // Актуальные проблемы гуманитарных и естественных наук. – 2021. – № 10. – С. 36-38.

5. Э.С. Анисимова – Визуализация замечательных кривых на плоскости // Актуальные проблемы гуманитарных и естественных наук. – 2021. – № 10. – С. 38-41.

6. Э.С. Анисимова – Идентификация онлайн-подписи с помощью оконного преобразования Фурье и радиального базиса // Компьютерные исследования и моделирование. – 2021. – Т. 6. № 3. – С. 357364.

7. А.Ф. Филипов, Э.С. Анисимова – Калькулятор для работы с комплексными числами // Сборник научных трудов Sworld. – 2021. – Т. 29. № 2. – С. 47-50.

8. E.S. Anisimova – Fractals and digital steganography // Сборник научных трудов Sworld. – 2021. – Т. 6. № 1. – С. 69-71.

9. Э.С. Анисимова – Определение кредитоспособности физического лица в аналитическом пакете DEDUCTOR (BASEGROUP) // Сборник научных трудов Sworld. – 2021. – Т. 23. № 2. – С. 78-81.

10. Д.С. Тимофеев, Э.С. Анисимова – Разработка электронного образовательного ресурса на площадке «Тулпар» системы дистанционного обучения КФУ // Сборник научных трудов Sworld. – 2021. – Т. 7. № 2. – С. 80-83.

11. Э.С. Анисимова – Сжатие изображений с помощью квадратичных кривых Безье // Естественные и математические науки в современном мире. – 2021. – № 14. – С. 42-46.

12. Э.С. Анисимова – Анализ кредитоспособности в пакете Deductor // Экономика и социум. – 2021. – № 2-1.- С. 261-263.

13. Э.С. Анисимова, Д.С. Тимофеев. – Разработка электронного курса по информатике в системе LMS MOODLE // Экономика и социум. – 2021. – № 2-1. – С. 264-266.

14. Э.С. Анисимова – Компетентностный подход в обучении математике студентов психологопедагогического направления // Сборник научных статей международной молодежной школы-семинара “Ломоносовские чтения на Алтае”. – Барнаул: Изд-во Алт. ун-та, 2021. -Ч.Ш. C.294-297.

15. Э.С. Анисимова – Формирование математической компетентности студентов психологопедагогического направления // Сборник научных трудов Sworld. – 2021. – Т. 19. № 4. – С. 56-58.

16. Э.С. Анисимова – Фрактальное кодирование изображений // Сборник научных трудов Sworld. -2021. – Т. 4. № 3. – С. 79-81.

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

Сценарий следующий:

Алиса хочет подписать сообщение своим закрытым ключом$d_A$

), а

Боб хочет проверить подпись с помощью открытого ключа Алисы$H_A$

). Никто, кроме Алисы не должен иметь возможности создать действительные подписи. Каждый должен иметь возможность проверить подписи.

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

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

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

  1. Берём случайное целое $k$, выбранное из ${1, dots, n - 1}$ (где $n$ — это по-прежнему порядок группы).
  2. Вычисляем точку $P = kG$ (где $G$ — базовая точка подгруппы).
  3. Вычисляем число $r = x_P bmod{n}$ (где $x_P$ — это координата $x$$P$).
  4. Если $r = 0$, то выбираем другое $k$ и пробуем снова.
  5. Вычисляем $s = k^{-1} (z   rd_A) bmod{n}$ (где $d_A$ — закрытый ключ Алисы, а $k^{-1}$ — мультипликативная инверсия $k$ по модулю $n$).
  6. Если $s = 0$, то выбираем другое $k$ и пробуем снова.

Пара

$(r, s)$ является подписьюАлиса подписывает хеш $z$ с помощью закрытого ключа $d_A$ и случайного $k$. Боб проверяет правильность подписи сообщения с помощью открытого ключа Алисы $H_A$.Проще говоря, этот алгоритм сначала генерирует секретный ключ ($k$$r$$r$$s = k^{-1} (z   rd_A) bmod{n}$$s$$k$$n$$n$Если подгруппа имеет порядок непростого числа, ECDSA использовать не удастся. Неслучайно все стандартизированные кривые имеют простой порядок, а имеющие непростой порядок неприменимы для ECDSA.

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

Для алгоритмов ECC требуются подгруппы с высоким порядком. Поэтому обычно выбирается эллиптическая кривая, вычисляется её порядок (

$N$

), в качестве порядка группы (

Читайте также:  Работа в ГИС ЖКХ — Удостоверяющий центр СКБ Контур

$n$

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

Во-первых, нужно ввести ещё одно понятие. Теорема Лагранжа подразумевает, что число $h = N / n$ всегда целое (потому что $n$$N$$h$кофактор подгруппы.Теперь рассмотрим, что для каждой точки эллиптической кривой есть $NP = 0$$N$$n$


Теперь допустим, что

$n$

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

$G = hP$

создаёт подгруппу порядка

$n$

(за исключением случая

$G = hP = 0$

, в котором подгруппа имеет порядок 1).

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

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

Заметьте, что алгоритм работает только если

$n$

простое. Если бы

$n$

не было простым, то порядок

$G$

мог быть одним из делителей

$n$

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


Можно задаться вопросом,

каков порядок подгруппы, порождённой точкой $P$

(или, иными словами, каков порядок

$P$

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

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

    На самом деле, если посмотреть на предыдущий пример, то наша подгруппа состояла из пяти точек, и $5P = 0$.

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

    Иными словами, если эллиптическая кривая содержит $N$ точек, а одна из подгрупп содержит $n$, то $n$ является делителем $N$.

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

$P$

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


Например, кривая

$y^2 = x^3 - x   3$

над полем

$mathbb{F}_{37}$

имеет порядок

$N = 42$

. Её подгруппы могут иметь порядок

$n = 1$

или

$42$

. Если

, то увидим, что

$P ne 0$

, …,

$7P = 0$

, то есть порядок

$P$

равен

$n = 7$важно брать наименьший, а не случайный делитель. Если мы будем выбирать случайно, то можем получить $n = 14$$y^2 = x^3 - x   1$$mathbb{F}_{29}$$N = 37$$n = 1$$37$$n = 1$$n = N$

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


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

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

, то есть:

где

$n$

— натуральное число. Я написал

визуальный инструмент

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

При записи в такой форме очевидно, что вычисление $nP$$n$$n$$k$$O(2^k)$удвоения-сложения. Принцип его работы проще объяснить на примере. Возьмём $n = 151$$10010111_2$

(Мы взяли каждый двоичный разряд

$n$

и умножили на степень двойки.)

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

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

В результате мы вычислим

$151 cdot P$

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

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

def bits(n):
    """
    Генерирует двоичные разряды n, начиная
    с наименее значимого бита.

    bits(151) -> 1, 1, 1, 0, 1, 0, 0, 1
    """
    while n:
        yield n & 1
        n >>= 1

def double_and_add(n, x):
    """
    Возвращает результат n * x, вычисленный
    алгоритмом удвоения-сложения.
    """
    result = 0
    addend = x

    for bit in bits(n):
        if bit == 1:
            result  = addend
        addend *= 2

    return result

Если удвоение и сложение являются операциями

$O(1)$

, то

этот алгоритм имеет сложность $O(log n)$

(или

$O(k)$

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

$O(n)$

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


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

И, повторюсь, мы можем использовать алгоритм удвоения-сложения для выполнения умножения за

$O(k)$

, где

$k$

— это количество бит

$n$

). Я написал

интерактивный инструмент для скалярного умноженияУмножение точек для эллиптических кривых над $mathbb{F}_p$$y^2 equiv x^3   2x   3 pmod{97}$$P = (3, 6)$вычислим все величины, кратные $P$Все значения, кратные $P = (3, 6)$, представляют собой пять различных точек ($0$, $P$, $2P$, $3P$, $4P$), которые циклически повторяются. Легко заметить сходство между скалярным умножением для эллиптических кривых и сложением в модулярной арифметике.


Можно сразу же заметить две особенности: во-первых, значений, кратных

$P$

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

повторяются циклически

. Можно записать:

для любого целого

$k$

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

$kP = (k bmod{5})P$эти пять точек замкнуты относительно операции сложения. Что это значит: как бы я ни суммировал $0$$P$$2P$$3P$$4P$$P = (3, 6)$$P$


Что означает:

если мы складываем два значения, кратных $P$, то получаем значение, кратное $P$

(т.е. значения, кратные

$P$

, замкнуты относительно операции сложения). Этого достаточно для того, чтобы

, что

множество кратных $P$ значений — это циклическая подгруппа

группы, образованной эллиптической кривой.

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

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

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

Когда я говорил, что задача дискретного логарифмирования «сложна», я был не совсем точен. Существуют

определённые классы эллиптических кривых, которые довольно слабы

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

$p = hn$

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

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

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

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

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

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

Стандартизированный алгоритм генерирования и проверки случайных кривых описан в ANSI X9.62 и основан на SHA-1. Если интересно, можете прочитать об алгоритмах генерирования проверяемо случайных кривых в спецификации SECG (см.

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

Упражнения

  1. Учитывая сверхвозрастающий кортежb = [7, 11,23,43,87, 173, 357], r =41 и модуль n = 1001, зашифруйте и расшифруйте букву a, используя ранцевую криптосистему. Используйте [7 6 5 1 2 3 4] как таблицу перестановки.
  2. В RSA:
  3. Для того чтобы понять безопасность алгоритма RSА, найдите d, если вы знаете, что e =17, а n =187.
  4. В RSA дано n и varphi (n), вычислите p и q.
  5. В RSA дано e = 13 и n = 100.
    Зашифруйте сообщение “HOW ARE YOU”, применяя 00 к 25 для букв от A до Z и 26 — для пробела. Используйте различные блоки, чтобы сделать P <n.
  6. В RSA дано n = 12091 и e = 13. Зашифруйте сообщение “THIS IS THOGH”, используя схему кодирования 00 к 26. Расшифровать зашифрованный текст, чтобы найти первоначальное сообщение.
  7. В RSA:
  8. Алиса использует открытый ключ RSА Боба (e = 17, n = 19519), чтобы передать сообщение из четырех символов Бобу, применяющему схему A leftrightarrow 0, B leftrightarrow 1...Z leftrightarrow 25 кодирования и декодирования по каждому символу отдельно. Ева перехватывает зашифрованный текст (6625 0 2968 17863) и расшифровывает сообщение, не разлагая на множители модуль. Найдите исходный текст; объясните, почему Ева смогла легко взломать зашифрованный текст.
  9. Алиса использует открытый ключ RSА Боба (e = 7, n = 143), чтобы передать исходный текст P = 8, зашифрованный в виде текста C = 57. Покажите, как Ева может использовать атаку выборки текста, если она имеет доступ к компьютеру Боба, чтобы найти исходный текст.
  10. Алиса использует общедоступный ключ RSA Боба (e = 3, n = 35) и передает зашифрованный текст 22 Бобу. Покажите, как Ева может найти исходный текст, используя атаку циклического повторения.
  11. Предложите, как Алиса может предотвратить атаку связанного сообщения на RSA.
  12. Используя криптосистему Рабина с p = 47 и q =11:
  13. В криптосистеме Эль-Гамаля дано простое число p = 31:
  14. Что случится в криптосистеме Эль-Гамаля —, если C1 и C2 будут изменены в течение передачи?
  15. Предположим, что Алиса применяет в криптосистеме Эль-Гамаля общедоступный ключ Боба ( e1 = 2 и e 2 = 8 ), чтобы передать два сообщения — P = 17 и P’ = 37. Они оба используют то же самое случайное целое число r = 9. Ева перехватывает зашифрованный текст и так или иначе находит значение P = 17. Покажите, как Ева может использовать атаку знания исходного текста, чтобы найти значение P’.
  16. В эллиптической кривойE (1, 2) в поле GF (11):
  17. В эллиптической кривойE (g4, 1) в поле GF(24):
  18. Используйте ранцевую криптосистему:
  19. В RSA:
  20. Напишите алгоритм для атаки циклического повторения на RSA.
  21. Напишите алгоритм для сложения двух точек на эллиптической кривой в GF(p).
  22. Напишите алгоритм для сложения двух точек на эллиптической кривой в GF(2n).
Читайте также:  Как подписать документ электронной подписью: инструкция для PDF, Word, Exel и других

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

Для обнаружения цикла мы можем проверить все возможные значения

$a$

с помощью

, но при условии, что существует

$n^2$

таких пар, алгоритм будет иметь сложность

$O(n^2)$

, что намного хуже атаки простым перебором.

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

У нас есть кривая $y^2 equiv x^3   2x   3 pmod{97}$ и точки $P = (3, 6)$ и $Q = (80, 87)$. Точки принадлежат циклической подгруппе с порядком 5. Мы обходим последовательность пар с разными скоростями, пока не находим две разные пары $(a, b)$ и $(A, B)$, дающих одну точку. В этом случае мы нашли пары $(3, 3)$ и $(2, 0)$, что позволяет нам вычислить логарифм как $x = (3 - 2)(0 - 3)^{-1} bmod{5} = 3$. И на самом деле, у нас получилось $Q = 3P$.В сущности, мы берём псевдослучайную последовательность пар $(a, b)$$aP   bQ$$(a, b)$$P$$Q$

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

Через какое-то время черепаха и заяц найдут одну точку, но с разными парами коэффициентов. Или, если выразить это уравнениями, черепаха найдёт пару $(a, b)$$(A, B)$$aP   bQ = AP   BQ$$O(log n)$ пространства. Вычисление сложности асимптотического времени не так просто, но мы можем построить вероятностное доказательство, показывающее, что временная сложность равна $O(sqrt{n}$), как мы уже говорили.

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

ECDH — это разновидность

для эллиптических кривых. На самом деле это скорее

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

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

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

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

    $S = d_A H_B = d_A (d_B G) = d_B (d_A G) = d_B H_A$

Однако посреднику известны только

$H_A$

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

общий секретный ключ $S$

. Это известно как задача Диффи-Хеллмана, которую можно сформулировать следующим образом:

Каким будет результат $abP$ для трёх точек $P$, $aP$ и $bP$?


Или, аналогично:

Каким будет результат $k^{xy}$ для трёх целых $k$, $k^x$ и $k^y$?

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

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

.5. Итоги

  • Есть два способа достигнуть информационной безопасности: криптография с симметричными ключами и криптография с асимметричными ключами. Эти два способа существуют параллельно и дополняют друг друга; преимущества одного могут дать компенсацию недостаткам другого.
  • Концептуальные различия между этими двумя способами базируются на том, как они сохраняют секретность. В криптографии с симметричными ключами секретность должна быть разделена между двумя объектами; в криптографии с асимметричными ключами секретность персональная (неразделенная).
  • Криптография с симметричными ключами базируется на подстановке и перестановке символов; криптография с асимметричными ключами базируется на применении математических функций к числам.
  • Криптография с асимметричными ключами использует два отдельных ключа: один секретный и один открытый. Шифрование и дешифрование можно представлять себе как запирание и отпирание замков ключами. Замок, который заперт открытым ключом, можно отпереть только соответствующим секретным ключом.
  • В криптографии с асимметричным ключом ответственность обеспечения безопасности находится, главным образом, на плечах приемника (Боб), который должен создать два ключа: один секретный и один открытый. Боб несет ответственность за секретный ключ. Открытый ключ может быть распространен сообществу через канал распределения открытого ключа.
  • В отличие от криптографии с симметричными ключами, в криптографии с асимметричным ключом исходный текст и зашифрованный текст обрабатываются как целые числа. Сообщение должно кодироваться как целое число (или множество целых чисел) перед шифрованием; целое число (или множество целых чисел) должно быть расшифровано в сообщение после дешифрования. Криптография с асимметричным ключом обычно используется, чтобы зашифровать или расшифровывать маленькие сообщения, такие как ключ шифра для криптографии с симметричными ключами.
  • Главная идея криптографии с асимметричным ключом — понятие “лазейка” в односторонней функции (TOWF), которая является такой функцией, что f вычисляется просто, а f -1 вычислить невозможно (в смысле сложности вычислений), если не используется лазейка.
  • Блестящая идея относительно криптографии общедоступного ключа принадлежит Меркелю и и Хеллману – это ранцевая криптосистема . Когда нам говорят, какие элементы из заранее заданного множества чисел находятся в рюкзаке, мы можем легко вычислить сумму чисел; когда нам сообщают сумму, трудно сказать, какие элементы находятся в рюкзаке, если он не заполнен элементами сверхвозрастающего множества.
  • Самый общий алгоритм общедоступного ключа — криптографическая система RSА. RSA использует два числа e и d, где e — общедоступный ключ, а d является частным (секретным). Алиса использует C = Pe mod n для того, чтобы создать зашифрованный текст C из исходного текста P ; Боб использует P = Сd mod n, чтобы извлечь исходный текст, переданный Алисой.
  • RSA применяет две алгебраических структуры: кольцо и группа. Шифрование и дешифрование выполняются с использованием коммутативного кольца R =  < {Z_n}^*,   , times  > с двумя арифметическими операциями — сложением и умножением. RSA применяет мультипликативную группу G =  < {Z_n}^*, times  > для генерации ключей.
  • Никаких разрушительных атак на RSA не было обнаружено. Теоретически предсказано несколько атак, основанных на разложении на множители, выборке шифрованного текста, образце дешифрования, образце шифрования, исходном тексте, модуле и реализации.
  • Криптосистема Рабина — вариант криптографической системы RSА. RSA базируется на экспоненциальном сравнении; криптосистема Рабина базируется на квадратичном сравнении. Мы можем представлять себе, что криптосистема Рабина — это RSA, в которой значение e = 2 и d = 1/2. Криптографическая система Рабина безопасна, пока p и q — большие числа. Сложность криптосистемы Рабина — на том же самом уровне, как и процесс разложения большого числа n на два простых сомножителя p и q.
  • Криптосистема Эль-Гамаля базируется на проблеме дискретного логарифма. Криптосистема Эль-Гамаля использует идею первообразных корней в Zn*. Шифрование и дешифрование в криптосистеме Эль-Гамаля использует группу G =  < {Z_p}^*, times  > Общедоступный ключ — это два числа, e1 и e2, а секретный ключ — это целое число d. Безопасность криптосистемы Эль-Гамаля основана на том, что решение проблемы дискретного логарифма не существует. Однако в литературе была упомянута атака, основанная на малом значении модуля, и атака знания исходного текста.
  • Другая криптографическая система, рассмотренная в этой лекции, базируется на эллиптических кривых. Эллиптические кривые являются кубическими уравнениями в двух переменных. Эллиптические кривые на поле вещественных чисел используют специальный класс эллиптических кривыхy2 = x3 ax b, где 4{a^3}   27{b^2} ne 0. Абелева группа была определена с помощью эллиптической кривой с операцией сложения, которая показывает, как две точки на кривой можно сложить, чтобы получить другую точку на этой кривой.
  • Криптография эллиптической кривой применяет две алгебраических структуры, абелеву группу и поле. Поле может быть полем вещественных чисел, GF (p) и GF (2n). Мы показали, как криптосистема Эль-Гамаля может моделироваться, используя эллиптические кривые в конечном поле. Безопасность криптографии эллиптической кривой зависит от проблемы логарифма эллиптической кривой, решение которой неосуществимо при большом значении модуля.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Adblock
detector