Записки программиста

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

1. Представление больших чисел

Большими числами в контексте этой заметки будут называться числа, разрядность которых превышает разрядность процессора, которому эти самые числа предстоит обрабатывать. Например, 32-х разрядный процессор может с легкостью обрабатывать целые числа от 0 до 2³²-1. Однако в современных программах, особенно криптографических, приходится иметь дело с числами порядка 2⁴⁰⁹⁶. И поскольку появление 4096-и разрядных процессоров в обозримом будущем не предвидится, для работы с такими числами приходится использовать специальные алгоритмы.

В школе всех нас учили оперировать цифрами в десятичной системе счисления. Припоминаете что-то про сложение и умножение в столбик? Так вот, в основу алгоритмов работы с большими числами положены те же идеи, только «цифр» будет не 10, а 2¹⁶ для 32-х разрядных машин и 2³² для 64-х разрядных. Почему мы используем только половину доступных разрядов, будет рассказано в следующем пункте.

Вот так выглядит объявление большого целого числа:

Используется порядок байт от младшего к старшему (little-endian). Массив, заполненный нулями, соответствует числу 0, заполненный единицами — 2^{BIGNUM_MAX_SIZE × 8}-1. Другими словами, имеет место то же самое представление беззнакового целого числа, что и в большинстве современных процессоров, только памяти выделяется побольше, а единица хранения — не байт, а слово или двойное слово, в зависимости от разрядности процессора.

2. Операции над большими числами

Давайте рассмотрим операцию сложения двух больших чисел:

Здесь к числу a прибавляется число b, результат сложения записывается в a. Это аналогично оператору языка си += и тому, как работает ассемблерная команда add. Преимущества такого подхода перед «add(a, b, result)» заключается в использовании меньшего числа аргументов функции и более простой ее реализации.

Функция должна вызываться следующим образом:

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

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

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

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

• Генри Уоррен «Алгоритмические трюки для программистов» (стр 142);
• Михаел Велшенбах «Криптография на Си и C++ в действии» (стр 64);
• Дональд Кнут «Искусство программирования, том 2 — получисленные алгоритмы, 3-е издание» (стр 310).

Чем выше книга в списке, тем доступнее, по моему субъективному мнению, в ней расписан алгоритм.

3. Модульная арифметика

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

Часы показывают 20:00. На какое время нужно поставить будильник, чтобы он зазвонил ровно через 8 часов?

Ответ, как несложно догадаться, — 4:00. Производя операции над часами, мы работаем с числами в поле вычетов по модулю 24. Аналогично для минут используется поле вычетов по модулю 60, для месяцев — по модулю 12, для дня недели — 7 и так далее. Если вы еще не до конца поняли, о чем идет речь, загляните на соответствующую страницу Википедии.

За выполнение операций сложения, вычитания, умножения и деления в поле вычетов отвечают функции моей библиотеки bignum_madd, bignum_msub, bignum_mmul и bignum_mdiv соответственно. Первые три не заслуживают особого внимания, потому что логика их работы проста. Сначала вычисляем обычную сумму/разность/произведение, и возвращаем остаток от деления на модуль. А вот функция bignum_mdiv заслуживает особого внимания.

Существует такое понятие, как число, мультипликативно обратное данному. Пусть p — число в поле вычетов по модулю m. Тогда число q называется мультипликативно обратным к p, если для любого x, принадлежащего полю вычетов, выполняется условие:

y = x × p (mod m) ⇔ x = y × q (mod m)

или, что то же самое:

p × q = 1 (mod m)

Такое q находится с помощью расширенного алгоритма Евклида, которому в моей библиотеке соответствует функция bignum_inv.

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

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

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

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

y² = x³ + a x + b (mod m)

причем:

4 a³ + 27 b² ≠ 0 (mod m)

Коэффициенты a и b — это параметры кривой. Помимо точек, принадлежащих кривой (координаты которых удовлетворяют уравнению y² = …), вводится так называемая «несобственная» точка, то есть не лежащая на кривой. Если со школьного курса вы припоминаете что-то про «точку на бесконечности», то вот это она и есть. Будем обозначать ее буквой «O».

С учетом вышесказанного, операция сложения двух точек P = (x_P; y_P) и Q = (x_Q; y_Q) на эллиптической кривой определяется следующим образом:

P + O = O + P = P
P − P = P + (−P) = O, где -P = (x_P; −y_P)

R = P + Q = (x_R; y_R)
x_R = λ² − x_P − x_Q
y_R = λ ( x_P − x_R) − y_P

λ = (3 x_P² + a) / (2 y_P), если P = Q
λ = (y_P − y_Q) / (x_P − x_Q), если P ≠ Q

Все это — в поле вычетов по простому модулю. А если ввести обозначения

P + P = 2 P
P + P + P = 3 P
…

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

Здесь все должно быть понятно, за исключением предпоследней строки. Что это еще за «генерирующая точка» такая? Это такая точка G на эллиптической кривой, что минимальное значение n, такое, что n × G = O, является очень большим простым числом. Другими словами, генерируя случайные числа и умножая их на G, мы может гарантировано получить много-много точек, принадлежащих кривой.

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

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

Сложение двух точек эллиптической кривой реализовано в функции eccrypt_point_add. Там все полностью соответствует теоретической части, так что разбирать ее не интересно. А вот умножение — более интересная операция. Дело в том, что вычислять произведение точки на большое число k в цикле из k итераций, полностью в соответствии с определением, — довольно долго. Спрашивается — что делать?

Здесь мы использовали двоичное представление числа k. Например, чтобы найти 8 × P, мы вычисляем 2 × ( 2 × ( 2 × P ) ), что требует лишь трех операций сложения вместо семи. Аналогично можно написать алгоритм возведения большого числа в степень:

k¹¹ = ((k²)² × k)² × k

Другими словами, алгоритм умножения точки эллиптической кривой на число состоит в следующем. Сначала полагаем результат равным несобственной точке. Затем просматриваем биты числа n от старших к младшему. Если встретили 0, умножаем текущее значение результата на 2. Если встретили 1 — умножаем результат на 2, после чего прибавляем P. Таким образом, для нахождения результата потребуется порядка log₂(k) шагов вместо k.

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

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

Национальный институт стандартов и технологий США (NIST) рекомендует использовать в криптографических приложениях следующую эллиптическую кривую:

a = -3
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
m = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
x_G = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296
y_G = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5

Кривая называется P-256. Здесь m — это модуль поля вычетов, а n — количество точек, которое может генерировать G, оба числа простые. Числа a и m специально подобраны с целью ускорения вычислений. Не знаю, как вы, а я не математик и тем более не криптограф, так что придется положиться на мнение экспертов.

Теперь рассмотрим схему обмена ключами на базе ЭК. Пусть пользователи A и B хотят обменяться ключами, но их трафик прослушивает злоумышленник E. Решение следующее:

1. Пользователь А генерирует случайно число d_A в диапазоне [1; n-1]. Это число будет его закрытым ключом.
2. Затем A вычисляет Q_A = d_AG и посылает координаты точки пользователю B. Q_A — открытый ключ пользователя A.
3. Пользователь B выполняет те же шаги.
4. Пользователь A получает Q_B, вычисляет R = d_AQ_B и считает, что x_R — это общий ключ.
5. Пользователь B повторяет предыдущий шаг.

Оба пользователя получили один и тот же ключ x_R, потому что d_AQ_B = d_Ad_BG = d_Bd_AG = d_BQ_A.

Злоумышленник E видит только Q_A и Q_B. Поскольку эффективный алгоритм, позволяющий определить d_A или d_B по Q_A или Q_B, пока что не найден и в обозримом будущем вряд ли найдется, для нахождения R злоумышленнику понадобится перебрать все (n-1) его возможных значений. Если предположить, что за секунду перебирается 2¹²⁸ значений (нереально большое число!), то на полный перебор уйдет более 10³⁰ лет. Для сравнения — считается, что возраст Вселенной составляет около 10¹⁰ лет.

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

Пусть некий пользователь хочет подписать сообщение. Как и в предыдущем примере, d и Q — его закрытый и открытый ключи соответственно. Открытый ключ должен быть доступен всем, закрытый — хранится в строжайшем секрете.

Алгоритм вычисления цифровой подписи:

1. Вычислить h — значение хэш-функции (например, SHA256) для подписываемого сообщения.
2. Выбрать случайное число k из диапазона [1; n-1], вычислить k × G = (x; y) и r = x (mod n).
3. Если r = 0, перейти к шагу 2.
4. Вычислить s = (h + d × r) / k (mod n). Если s = 0, перейти к шагу 2.
5. Вернуть цифровую подпись r || s.

Алгоритм проверки цифровой подписи:

1. Проверить, что Q принадлежит ЭК и что n × Q = O (последнее должно выполнятся, потому что n × Q = n × d × G = d × n × G = d × O = O). Если это не так, открытый ключ неверен.
2. Проверить, что r и s принадлежат интервалу [1; n-1]. Если это не так, подпись неверна.
3. Вычислить h — значение хэш-функции для подписанного сообщения.
4. Вычислить (x; y) = (h / s) G + (r / s) Q, а затем v = x (mod n).
5. Если v = r, подпись верна, иначе — не верна.

Значения v и r должны быть равны, потому что

(h / s) G + (r / s) Q = ( h / s) G + (r / s) × d × G = ( (h + d × r) / s) G = k × G

Если не понятно, посмотрите еще раз, как считались r, v и s.

Чтобы подделать подпись, нужно определить закрытый ключ d по открытому ключу Q, что, как мы уже знаем, нереально. С помощью s определить d невозможно, потому что последнее надежно скрыто неизвестным случайным числом k. Определить k с помощью r невозможно по тем же соображениям, по которым d невозможно определить по Q.

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

6. Безопасность, оптимизация и тестирование

Безопасность алгоритма Диффи-Хеллмана и цифровых подписей на основе эллиптических кривых (ECDH и ECDSA соответственно), описанных выше, гарантируется в силу причин, описанных в пункте 5. Действующий в России стандарт цифровых подписей, ГОСТ Р 34.10-2001, использует эллиптические кривые над полем вычетов по модулю порядка 2²⁵⁶. И кстати, ГОСТ Р 34.10-2001 практически полностью идентичен ECDSA. Разве доверие российских криптографов к эллиптическим кривым можно игнорировать? Наконец, эллиптическая криптография существует более 25 лет (против 35 лет «классических» алгоритмов Диффи-Хеллмана и RSA). За это время ее стойкость, похоже, ничуть не пошатнулась. Зато рекомендуемая длина ключа RSA успела увеличиться в 4 раза.

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

Теперь — что касается оптимизации. Есть множество способов ускорить работу библиотеки. Например, используя метод Карацубы или Шёнхаге-Штрассена в функции умножения. Однако в уже упомянутой мной книге Велшенбаха показано, что данные методы бессмысленно использовать, пока речь идет о числах менее 2²⁰⁴⁸. Таким образом, само использование эллиптических кривых (вместо медленного RSA) является главной оптимизацией! Нет смысла переписывать простой и понятный код с целью выиграть сотые доли секунды, особенно если выясняется, что обращение к сети приводит к еще большим задержкам. Здесь нужно сначала получить готовое приложение, и только потом, вооружившись профилировщиком, искать узкие места.

По поводу тестирования библиотеки. Первый тип ошибок, которые нам следует искать, это явные косяки, например, что x − x ≠ 0, y × 1 ≠ y, a × (b + c) ≠ a × b + a × c, сумма двух точек ЭК отлична от O и при этом не принадлежит самой ЭК и тд. Кого интересует полный список таких тестов, загляните в Perl-скрипты из каталога test в прилагающемся к заметке архиве.

Также следует проверить, что наши тесты покрывают если не 100% тестируемого кода, то хотя бы большую его часть. Например, если мы видим в функции условный оператор, то следует убедиться, что мы проверили как ветку if, так и ветку else. Особенно это касается функции, отвечающую за деление больших чисел. Условие ‘if(temp < 0)' (см пункт 2) выполняется чрезвычайно редко, так что вероятность допустить ошибку в окрестностях этого условия очень высока. К счастью, на CD, идущем вместе к Вельшенбахом, можно найти специальные числа для тестирования этого участка кода (файл testdiv.c, если у кого-нибудь из читателей есть эта книга).

Будет совсем не лишним сравнить результаты вычислений нашей библиотеки и какой-нибудь другой, давно отлаженной, программы. Например, интерпретатора Python. Он, к нашей великой радости, может производить математические операции над числами с произвольной точностью. Заодно убедимся, что преобразование строк в числа и обратно в нашей библиотеке реализовано без ошибок.

И наконец, для полной очистки совести, следует проверить библиотеку на практике. Например, подписав какие-нибудь данные с помощью ECDSA, как описано выше. А затем написать скрипт, который рекурсивно обходит файловую систему и подписывает каждый найденный файл, после чего сам же проверяет подпись. Запускаем его перед новогодними праздниками на двух машинах (с 32-х и 64-х разрядным процессором) и проверяем результат 10-го января.

7. Заключение

Здесь вы можете скачать обещанный архив с исходниками. Несмотря на тщательное тестирование библиотеки, мне будет спокойнее, если вы еще раз протестируете ее на своей машине и отпишите в комментариях о результатах. Не забудьте указать ОС и модель процессора.

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

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

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

Дополнение: Исходники к посту теперь доступны и на GitHub. Также вас может заинтересовать статья Основные криптографические алгоритмы на языке Си.

Метки: C/C++, Алгоритмы, Безопасность, Криптография.