RSA является широкоизвестным алгоритмом шифрования с открытым ключом. На его основе, кроме асимметричного шифрования, можно также реализовать электронную подпись (ЭЦП). Эти возможности привлекательны для встраиваемых систем, микроконтроллеров. Сам метод шифрования с виду чрезвычайно прост:
| C = (Me) mod n | (1) |
где C,M,e,n — целые числа, M — открытый текст, числа e и n представляют собой открытый ключ, C — шифротекст. mod — остаток от деления.
Расширование выглядит столь же просто:
| M = (Cd) mod n | (2) |
где C,M,n играют ту же роль, что и при шифровании, d — закрытый ключ.
При этом n=p*q, где p и q — простые числа (секретные), e обычно равно 65537, d вычисляется на основе e, p и q. Криптостойкость основана на том, что для достаточно больших p и q задача разложения n на множители или обращения формулы шифрования без знания p и q не решается за приемлемое время.
Но эта кажущаяся простота обманчива. За ней скрывается огромное количество деталей и сложностей реализации. Особенно если стоит цель получить эффективную по быстродействию и памяти реализацию, пригодную для применения в микроконтроллерах. Я не нашел в интернете подходящих библиотек, а попытки изучения исходников libgcrypt заводят в такие дебри, из которых не выберешься. Поэтому я написал свою компактную библиотеку, которой и делюсь с уважаемыми читателями.
1. Длинная арифметика (Multi-precision integer arithmetics)
Первые сложности начинаются уже при попытке проверить работоспособность RSA для малых чисел. Например, если взять p=7, q=11, тогда получится n=77. Выбранное e должно быть взаимно простым с (p-1)*(q-1), поэтому 2, 3, 4 и 5 не подходят, минимально подходит 7. Оставив в стороне метод вычисления d, приведу просто результат: d=43. И теперь, хотя зашифрование небольшого сообщения не представляет проблем, для расшифровки необходимо возводить C в степень 43, и это приводит к переполнению даже 64-битных целых уже при C=3.
Впрочем, и без этого примера было ясно, что без использования длинной арифметики не обойтись. Ведь для обеспечения криптостойкости p и q должны быть большими. В современной практике использования RSA эти числа имеют порядок 21024 каждое, а порядок n — 22048 при использовании длины ключа в 2048 бит. Допустимо понизить порядок чисел в 2 раза (512 бит для p и q, 1024 для n), но в публикациях последних лет можно нередко встретить мнение, что 1024-битные RSA-ключи уже не обеспечивают должный уровень криптостойкости.
Длинная арифметика — понятие растяжимое. Возникает желание использовать класс C++ для представления длинных чисел и реализовать ему операторы сложения, вычитания, умножения и т.д. Моя практика показывает, что этот подход годится разве только для начального ознакомления с RSA. Для реализации в микроконтроллерах нам нужно реализовать не весь набор операций, а только самые необходимые. И реализовать эффективно. Не на C++, а на C или даже ассемблере.
Исторически сложилось, что сначала я реализовал необходимые алгоритмы длинной арифметики «в лоб», на C++, потом перевел их на ассемблер dsPIC33F и оптимизировал, а потом перевел обратно на C. В связи с этим C-код получился намного эффективнее первоначального кода на C++ и лишь немного уступает ассемблеру.
1.1. Возведение в степень
Очевидно, что в первую очередь нам понадобится алгоритм возведения в степень. Для этого подходит изучаемый в школе [1] алгоритм, сводящий операцию к серии умножений и имеющий сложность O(log e), где e — показатель степени.
Даже при использовании алгоритмов длинной арифметики возведение 2048-битного числа M в степень e=65537 приводит к числу разрядности 2048*65537 бит, что потребует для его хранения в памяти более 16 мегабайт. Время выполнения умножения для таких чисел и вовсе превосходит все мыслимые пределы. К счастью, нам нужен не сам результат Me, а только остаток его от деления на n. Так как возведение в степень сводится к серии умножений, следует после каждого умножения уменьшать разрядность промежуточного результата, находя остаток от деления его на n. Существуют теоремы, гарантирующие получение при этом верного результата. Таким образом, алгоритм возведения в степень и последующего вычисления остатка от деления результата на n у нас превращается в единый алгоритм возведения в степень по модулю, который вычисляет результаты обеих операций одновременно и тем самым полностью реализует зашифрование RSA по формуле (1).
Для реализации этого алгоритма нам потребуются операции длинного умножения и нахождения остатка от деления. Частное нас не интересует. При этом разрядность операндов для умножения у нас будет по 2048 бит каждый, делить необходимо 4096-битные числа на 2048-битные, остаток от деления будет иметь длину 2048 бит.
Несмотря на неплохую производительность, вышеописанный алгоритм пригоден только для зашифрования, где используется «хороший» показатель степени e=65537. Его значение достаточно велико для криптостойкости; в то же время оно достаточно мало по сравнению с разрядностью ключа; это простое число, а также оно имеет выгодное двоичное представление, повышающее эффективность возведения в степень. В то же время, число d не может быть выбрано произвольно, оно зависит от p, q и e, и по порядку величины оно сравнимо с n, 2048 бит. Если возвести в степень 65537 можно за 17 длинных умножений и делений, то для возведения в степень d потребуется в среднем около 3072 таких операций, что снизит быстродействие расшифрования по сравнению с зашифрованием более чем в 180 раз. Однако в случае расшифрования можно значительно повысить быстродействие, воспользовавшись знанием p и q (для шифрующей стороны эти числа, как правило, неизвестны). В результате алгоритм расшифрования существенно отличается от зашифрования при всем математическом сходстве этих операций.
Моя встраиваемая реализация использует только зашифрование (или операцию проверки электронной подписи), поэтому возведение в степень e по модулю n можно оформить в виде специализированной процедуры, жестко привязанной к значению e=65537. В тексте исходника эта процедура называется mpi_powm65537, она принимает на вход числа M и n. При своей работе она использует процедуры длинного умножения и нахождения остатка от длинного деления.
1.2. Длинное умножение
Существует целый ряд алгоритмов длинного умножения. Самым широкоизвестным является умножение «в столбик». Этот метод сводит умножение длинных чисел к серии умножений и сложений отдельных цифр. При наличии аппаратного умножителя в процессоре, длинное умножение можно реализовать в системе счисления по основанию 256, 65536 и более, в зависимости от разрядности умножителя. Он у нас будет умножать отдельные «цифры» длинных чисел.
Умножение в столбик не является самым эффективным методом. Его сложность составляет O(k2), где k — разрядность операндов в выбранной системе счисления. Существуют более эффективные алгоритмы: умножение Карацубы, умножение посредством преобразования Фурье [2, 7] и др. Однако эти продвинутые методы более сложны в реализации. В условиях недостатка времени я ограничился умножением в столбик. Это дало приемлемое быстродействие на выбранном микроконтроллере.
Итак, умножение «в столбик» сводит длинное умножение к серии коротких умножений и сложений. Разумно использовать разрядность имеющегося аппаратного умножителя полностью. Например, в микроконтроллерах PIC24 и dsPIC имеется умножитель 16*16 => 32, то есть умножающий 16-битные числа и дающий 32-битный результат. Таким образом, максимально возможное основание системы счисления для этих микроконтроллеров — 216=65536.
Причем важно то, что результат 32-битный, потому что все эти 32 бита понадобятся в ходе дальнейших вычислений. Скажем, в процессорах x86 разрядность результата равна разрядности операндов, т.е. 32 бита. Чтобы не допустить переполнения, приходится ограничивать разрядность операндов 16 битами. То же справедливо для некоторых других 32-битных процессоров. На них тоже приходится использовать систему счисления по основанию 65536, как в 16-битном микроконтроллере.
При умножении «в столбик» можно в разном порядке вычислять промежуточные результаты. Скажем, как мы в школе привыкли, можно сначала умножить весь первый множитель на одну цифру второго, потом на вторую и т.д., записав результаты в строки. Получится матрица, которую далее необходимо построчно сложить. Но для микроконтроллеров dsPIC более эффективен другой подход [6]. А именно, вычисление матрицы не по строкам, а по столбцам. Сначала первый столбец, потом второй и т.д. Когда столбец вычислен — его значения можно сразу сложить между собой, получится цифра итогового результата и перенос. Разумеется, нет смысла хранить все числа из столбца — можно вместо этого сразу добавлять их к сумме. При таком подходе операции умножения чередуются с операциями добавления результата к аккумулятору. А следовательно, становится возможным использование мощных DSP-средств этого микроконтроллера, инструкций REPEAT и MAC, которые за один такт процессора извлекают два операнда из памяти, перемножают их, добавляют результат к аккумулятору и увеличивают значения указателей. Хоть алгоритм по-прежнему остается неэффективным — O(k2), такая оптимизированная реализация может составить конкуренцию более эффективным алгоритмам, которые тратят больше тактов процессора на каждый проход внутреннего цикла.
Длинным беззнаковым умножением 2048*2048 => 4096 занимается в моей библиотеке подпрограмма mpi_muluu.
1.3. Представление чисел — Little Endian или Big Endian?
Любой разработчик библиотеки длинной арифметики должен решить, в каком виде он представляет числа в памяти. Расположены ли в памяти сначала младшие, а потом старшие разряды числа (Little Endian) или наоборот (Big Endian). Для человека более естественен формат Big Endian, ведь все числа, с которыми мы работаем, представлены в этом формате. Однако для внутреннего представления чисел в компьютере может оказаться иначе.
В нашем случае условия диктует алгоритм длинного умножения. При его работе числа представлены в памяти в виде 16-разрядных «цифр». Было бы желательно читать эти «цифры» из памяти целиком, а не по одному байту. При этом приходится использовать инструкции 16-битного чтения процессора, а они в случае dsPIC, да и x86 — Little Endian. Есть и другие соображения, по которым Little Endian предпочтительнее, но это — самое главное. Для повышения быстродействия мы хотим считывать обрабатываемую информацию из памяти как можно большими кусками, и при этом избегать ненужных преобразований. Поэтому я выбрал Little Endian, несмотря на то, что во многих учебниках используется формат Big Endian, и не жалею. Этот выбор привел к красивому и оптимальному коду. Разумеется, для Big-endian процессоров следует выбрать формат Big-endian.
1.4. Длинное деление
Эффективные методы длинного деления сводят его к умножению на обратное делителю число [7]. В свою очередь, это обратное число вычисляется тоже с помощью умножения, например, итеративным методом, основанным на методе Ньютона решения уравнений [3,7]. Теоретически это могло бы быть очень выгодно для RSA, ведь делить приходится много раз на одно и то же число, так что обратное ему число нужно вычислить только один раз. Однако я не стал связываться с этим, ограничившись реализацией деления «в столбик» применительно к компьютерам, которое описано в [4].
Если вспомнить изучаемый в школе метод деления «в столбик» и попытаться реализовать его «в лоб» на компьютере — то сталкиваешься с тем, что этот метод, за исключением работы в двоичной системе счисления, не сводит длинное деление к короткому или другим простым операциям. В самом деле, снеся некоторое количество цифр делимого, необходимо разделить их на весь длинный делитель, чтобы получить очередную цифру частного. Как же здесь быть? В [4] приводится теорема, которая дает возможность «угадать» цифру частного с малой погрешностью. Она действует для случаев, когда:
- разрядность делителя на одну цифру меньше разрядности частичного остатка;
- первая цифра делителя больше или равна половине основания системы счисления.
Первое условие соблюдается благодаря тому, что мы сносим цифры делимого в частичный остаток правильным образом (аналогично школьной процедуре). Чтобы выполнялось второе условие, можно умножить делимое и делитель на одно и то же число. Однако для ключей RSA и так гарантируется, что старший бит n (делителя) равен 1. А значит, и 16-битная «цифра», сформированная из старших 16 бит ключа, будет больше или равна 32768. Поэтому для RSA приведение операндов деления не требуется.
Чтобы «угадать» цифру частного, нужно разделить две первые цифры частичного остатка на первую цифру делителя. Полученное значение либо равно истинной цифре частного, либо превышает ее не более, чем на 2. В самом деле, если мы делим 499 на 50 — то разделив 49 на 5, получаем 9, что совпадает с истинной первой цифрой частного. Если делим 890 на 99 — то разделив 89 на 9, получаем 9, что на 1 больше, чем нужно. В других случаях оценка получается завышенной на 2, но никогда больше, это гарантируется теоремой.
Деление двух цифр частичного остатка на одну цифру делителя — это «короткое» деление, аппаратная поддержка которого очень желательна. В dsPIC33 есть аппаратная поддержка деления 32-битных чисел на 16-битные, с 16-битными частными и остатком. Этого вполне достаточно для реализации длинного деления в системе счисления по основанию 216=65536. Для x86 максимальная разрядность делимого составляет 32 бита, что также дает основание системы счисления 65536.
После «угадывания» цифры частного, необходимо умножить эту цифру на делитель и вычесть произведение из частичного остатка. Если результат меньше 0 — добавить делитель обратно и уменьшить оценку цифры частного на 1. Если все равно остаток меньше 0 — добавить делитель еще раз и еще раз уменьшить оценку частного. В результате у нас получится правильное значение цифры частного и правильное значение частичного остатка для продолжения процесса деления.
Для RSA не требуется знать частное, а нужен только остаток от деления. В связи с этим я написал функцию mpi_moduu, вычисляющую только остаток. Для 2048-битного RSA необходимо делить 4096-битные числа на 2048-битные, с 2048-битным остатком. Моя процедура выполняет деление «на месте»: делимое замещается остатком по окончании работы процедуры. Это повышает ее эффективность, так как «снос» очередной цифры из делимого превращается в простой инкремент указателя. Также не требуется дополнительная память для хранения частичного остатка и частного (так как оно не сохраняется).
Для работы вышеописанного алгоритма деления необходимы следующие компоненты длинной арифметики:
- умножение длинного числа на короткое (на одну цифру);
- вычитание длинных чисел;
- сложение длинных чисел;
- сравнение длинных чисел,
которые описываются ниже.
Сложность процедуры длинного деления — O(k2) по коротким умножениям и O(k) — по коротким делениям, где k — количество разрядов делителя в системе счисления по основанию 65536.
1.5. Длинное сложение и вычитание
Для написания процедур сложения mpi_add и вычитания mpi_sub не требуется особая изобретательность и какие-то сложные методы. У каждого процессора есть инструкция типа ADC, которая складывает два числа и бит переноса от предыдущего сложения. Если каскадировать команды ADC — то можно складывать операнды любой разрядности. Сказанное справедливо для вычитания и инструкции SBC. Сложность — O(k). Мои процедуры возвращают флаг переноса при сложении или вычитании, который используется в процедуре деления.
В языке C нет доступа к флагам процессора, поэтому приходится привлекать числа большей разрядности, чем необходимо. Скажем, при сложении двух 16-битных чисел необходимо использовать как минимум 32-битное для хранения результата и переноса, чтобы гарантированно избежать переполнения.Это снова приводит нас к необходимости работы в системе счисления по основанию 65536 на 32-битных процессорах. Ну а на ассемблере разрядность цифр длинных чисел у нас совпадает с разрядностью процессора, 16 бит в случае dsPIC.
1.6. Длинное сравнение
Сравнение можно реализовать эффективнее, чем вычитание, если начать обработку со старших цифр. Если старшая цифра одного числа больше старшей цифры другого — то больше и все число, остальные цифры можно не сравнивать. Тем самым сложность процедуры сравнения такая же, как для вычитания O(k), однако статистически сравнение работает быстрее. Процедура в исходнике называется mpi_cmp.
1.7. Умножение длинного числа на короткое
Умножение длинного числа на короткое (т.е. на одну цифру), которое используется при делении длинных чисел, ничем принципиально не отличается от длинного умножения. Однако в нем отсутствует один уровень вложенности циклов. Умножение числа разрядности k на цифру в системе по снованию 65536 приводит к числу разрядности k+1. Поскольку в процедуре деления за таким умножением сразу следует вычитание произведения из частичного остатка, я реализовал обе операции одновременно в процедуре mpi_mulsubuuk, умножающей 2048-битное число на 16-битное и вычитающее произведение из 2064-битного числа, что приводит к некоторой экономии памяти и времени исполнения.
Вот и вся длинная арифметика, необходимая для зашифрования методом RSA.
2. Генерация ключей
Генерация ключей в RSA начинается с выбора двух больших простых чисел p и q. Когда говорят: «RSA-ключ длиной 2048 бит» — то имеют в виду то, что произведение p*q является 2048-битным числом, старший бит которого равен 1 (иначе, в некоторых толкованиях, это было бы 2047-битное число). Разрядность чисел p и q по отдельности при этом не задается, но я заметил, что в GnuPG генерируются такие p и q, что каждое из них является 1024-битным числом со старшим битом, равным 1.
О генерации больших простых чисел можно писать книги, не то что статьи. Но во многих ситуациях, в том числе моей, генерировать ключи на микроконтроллере не требуется. Поэтому я попробовал, и успешно, генерировать ключи при помощи GnuPG.
Сначала необходимо обычным образом сгенерировать в GnuPG пару ключей (открытый+закрытый). При этом проследить, чтобы получился RSA-ключ нужной длины (2048 бит там сейчас стоит по умолчанию). Несмотря на настойчивые призывы GnuPG, следует отказаться от защиты этого ключа паролем и хранить его на диске в открытом виде. Какая разница, мы ведь все равно собираемся «распотрошить» этот ключ на составляющие его числа p, q, n, d и сохранить их на диск в открытом виде, хотя бы временно.
Экспортировать ключ из базы ключей GnuPG может недокументированная в новых версиях gpg команда
gpg --export-secret-keys --armor [key_id] >filename.ascГде key_id — идентификатор ключа, который можно получить с помощью вызова gpg --list-secret-keys.
Получится текстовый файл с содержимым вроде:
-----BEGIN PGP PRIVATE KEY BLOCK-----
Version: GnuPG v2.0.17 (MingW32)
lQOXBE9IdyABCADGT3+Dj0dsVPSkzW+zPlfXc4AsuKpkE9GJNAYD3mrcF70nwk1L
...
Как извлечь отсюда нужные нам числа, составляющие ключ? Выяснилось, что в самой программе gpg и прилагаемых утилитах НЕТ таких средств. Есть только сторонняя утилита "pgpdump", которая интерпретирует содержимое PGP Private Key Block и выводит в человекочитаемом виде. Вызвав ее следующим образом:
pgpdump -i filename.asc >filename.txtПолучим нужные нам параметры:
Old: Secret Key Packet(tag 5)(919 bytes)
Ver 4 - new
Public key creation time - Sat Feb 25 07:52:32 FLE Standard Time 2012
Pub alg - RSA Encrypt or Sign(pub 1)
RSA n(2048 bits) - c6 4f 7f ...
RSA e(17 bits) - 01 00 01
RSA d(2040 bits) - a5 c5 ce ...
RSA p(1024 bits) - d0 28 ad ...
RSA q(1024 bits) - f3 e3 61 ...
RSA u(1024 bits) - 90 8b 22 ...
Checksum - 3e 22
...Здесь я полностью не привожу реальные числа, но вы их легко получите для вашего ключа. Остается только скопипастить их куда надо, не забывая о том, что в этом файле они представлены в формате Big Endian. Так что для их использования совместно с моими процедурами необходимо их преобразовать к Little Endian, то есть переставить все байты в обратном порядке.
Также не забывайте, что открытый ключ — это только числа e и n. Остальные числа — это секретный (закрытый) ключ, и знание любого из них (d,p,q,u) позволит легко вычислить остальные и дешифровать ваше сообщение, либо подделать электронную подпись.
3. Расшифрование
Поскольку большинство реализаций RSA прячут куда-то внутрь числа, из которых состоят ключи, и оборачивают зашифрованные сообщения во всевозможные пакеты, то хотя бы для проверки приведенных в разделе 1 подпрограмм необходимо, кроме операции зашифрования, реализовать еще и расшифрование.
Как уже говорилось выше, формулу (2) расшифрования можно реализовать «в лоб». И хоть работать это будет в сотни раз медленнее, чем зашифрование, из-за большой величины показателя степени d, но этого будет достаточно для многих применений. Если же есть желание ускорить операцию, то применяется трюк с использованием Китайской теоремы об остатках, описанный в [5]. У меня нет красивых исходников, реализующих все это, поэтому привожу лишь словесное описание алгоритма:
Сначала число d «разлагается» на две части, dp = d mod (p-1) и dq = d mod (q-1). При этом разрядность каждой из частей получается в 2 раза меньше «длины ключа» (разрядности n). Далее вычисляется qinv такое, что (q*qinv) mod p = 1. То есть qinv является обратным элементом по отношению к q в кольце по модулю p. В английской терминологии это назвается "Modular multiplicative inverse". Для вычисления обратного элемента обычно применяется расширенный алгоритм Евклида.
Когда числа dp, dq и qinv найдены, расшифрование сообщения по методу RSA выполняется следующим образом:
- m1 := (Cdp) mod p
- m2 := (Cdq) mod q
- h: = ((m1-m2) * qinv) mod p
- M: = m2 + h*q
Обратите внимание, что вычисления на этапах 1-3 производятся в пониженной разрядности: 1024 бит вместо 2048 для формулы (2). Так как алгоритмы возведения в степень по модулю имеют кубическую сложность (квадратичная от умножения и деления, и еще линейная от «быстрого» возведения в степень) — то получается выигрыш в скорости при работе с половинной разрядностью чисел в 8 раз. Но так как у нас теперь вызываются две дорогие операции возведения в степень по модулю — то общий выигрыш получается в 4 раза по сравнению с прямым применением формулы (2). Хоть это и немало, но все же не настолько существенно, чтобы во всех случаях откзаться от прямого применения формулы (2), особенно учитывая сложности с вычислением qinv.
Следует упомянуть об интересной уязвимости, связанной с «быстрым» возведением в степень. Об этом упоминается в исходниках libgcrypt, файл mpi-pow.c. Атака называется «Yarom/Falkner flush+reload cache side-channel attack» и позволяет с помощью манипуляций с кэшем второго уровня процессора (который общий для всех ядер) для неавторизованных приложений полностью выяснить значение d или его частей dp и dq. То и другое означает полное раскрытие секретного ключа, позволяющее злоумышленнику полностью прочитать все зашифрованные этим ключом сообщения или сгенерировать электронную подпись. То есть, допустим, ваша программа расшифровывает секретным ключом что-нибудь, а злоумышленная программа в этот момент работает в той же системе, но от имени другого пользователя, так что вы об этом не знаете. И в этот момент происходит утечка ключа.
Заключение
Мною был представлен модуль на языке C, пригодный для реализации зашифрования по методу RSA или проверки электронной подписи на 32-битных встраиваемых процессорах с тактовыми частотами порядка 40МГц и аппаратным умножителем. При переводе C-исходника на ассемблер и с использованием материалов [6], можно получить реализацию для dsPIC33F, шифрующую один блок данных RSA-2048 за время порядка 10мс при тактовой частоте процессора 80МГц.
Исходники можно скачать с GitHub.
Расшифрование RSA (или генерацию электронной подписи) также можно реализовать на микроконтроллерах подобного класса, но эта операция будет примерно в 45-180 раз медленнее.
Возможно ускорение библиотеки за счет привлечения эффективных алгоритмов умножения и деления, упомянутых в статье по ссылкам.
Рекомендую использовать мои подпрограммы только для встраиваемых применений, а для «больших» компьютеров в большинстве случаев лучше применять стандартные средства вроде Windows CryptoAPI или libgcrypt.
Список литературы
1. А. Г. Кушниренко, Г.В. Лебедев, Р. А. Сворень. Основы информатики и вычислительной техники. М.:1990, стр. 133.
2. Википедия. Метод умножения Шёнхаге-Штрассена
3. Википедия. "Длинная арифметика"
4. Дональд Кнут. «Искусство программирования», том 2. Получисленные алгоритмы
5. Википедия, статья "RSA (cryptosystem)", раздел «A worked example»
6. Erich Wegener, Mario Werner. «Evaluating 16-bit Processors for Elliptic Curve Cryptography». Institute for Applied Information Processing And Communications (IAIK), Graz University of Technology
7. William H. Press et al. «Numerical Recipes in C++», Second edition, Cambridge University Press 2002, page 922
Автор: MichaelBorisov
