ЮАР — широко известный алгоритм шифрования с открытым ключом.
На его основе, помимо асимметричного шифрования, можно реализовать и электронную подпись ( ЭПРОЦЕССОР ).
Эти возможности привлекательны для встраиваемых систем и микроконтроллеров.
Сам метод шифрования кажется чрезвычайно простым:
| С = (М е ) мод н | (1) |
Расширение выглядит так же просто:
| М = (С д ) мод н | (2) |
В этом случае n=p*q, где p и q — простые числа (секретные), e обычно равно 65537, d рассчитывается на основе e, p и q. Криптографическая стойкость основана на том, что при достаточно больших p и q задача факторизации n или обращения формулы шифрования без знания p и q не может быть решена за приемлемое время.
Но эта кажущаяся простота обманчива.
За этим кроется огромное количество деталей и сложностей реализации.
Особенно, если цель — получить эффективную по скорости и памяти реализацию, подходящую для использования в микроконтроллерах.
В интернете подходящих библиотек не нашел, но попытки изучить исходный код libgcrypt Они ведут тебя в такие джунгли, из которых ты не можешь выбраться.
Поэтому я написал свою собственную компактную библиотеку, которой делюсь с дорогими читателями.
1. Длинная арифметика (целочисленная арифметика различной точности)
Первые трудности начинаются при попытке проверить работоспособность 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 эти числа порядка 2. 1024 каждый, а порядок n равен 2 2048 при использовании ключа длиной 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 мегабайт. Время умножения таких чисел совершенно превосходит все мыслимые пределы.
К счастью, сам результат M нам не нужен.
е , а только остаток от деления на 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(k 2 ), где k — разрядность операндов в выбранной системе счисления.
Есть более эффективные алгоритмы: Умножение Карацубы , умножение с помощью преобразования Фурье [2, 7] и т. д. Однако эти продвинутые методы более сложны в реализации.
Из-за нехватки времени я ограничился умножением по столбикам.
Это дало приемлемую производительность выбранного микроконтроллера.
Итак, столбчатое умножение сводит длинное умножение к серии коротких умножений и сложений.
Имеет смысл использовать всю мощность существующего аппаратного умножителя.
Например, в микроконтроллерах PIC24 и dsPIC есть множитель 16*16 => 32, то есть он перемножает 16-битные числа и дает 32-битный результат. Таким образом, максимально возможное основание для этих микроконтроллеров равно 2. 16 =65536. При этом важно, чтобы результат был 32-битным, потому что все эти 32 бита понадобятся при дальнейших вычислениях.
Скажем, в процессорах x86 ширина результата равна ширине операндов, т.е.
32 бита.
Чтобы предотвратить переполнение, операнды должны быть ограничены 16 битами.
То же самое справедливо и для некоторых других 32-битных процессоров.
Они также должны использовать систему счисления по основанию 65536, как в 16-битном микроконтроллере.
При умножении «столбиком» можно вычислять промежуточные результаты в разном порядке.
Скажем, как мы привыкли в школе, можно весь первый множитель сначала умножить на одну цифру второго, затем на вторую и т. д., записав результаты в строки.
В результате получается матрица, которую затем нужно складывать построчно.
Но для микроконтроллеров dsPIC более эффективен другой подход [6].
А именно, расчет матрицы не по строкам, а по столбцам.
Сначала первый столбец, затем второй и т. д. При расчете столбца его значения можно сразу сложить для формирования окончательного результата и перенести.
Конечно, нет смысла хранить все числа из столбца; вместо этого вы можете сразу добавить их к сумме.
При таком подходе операции умножения чередуются с операциями сложения результата в аккумулятор.
Следовательно, появляется возможность использовать мощные ЦСП - средства этого микроконтроллера, инструкции REPEAT и MAC, которые за один такт процессора извлекают из памяти два операнда, умножают их, складывают результат в аккумулятор и увеличивают значения указателя.
Хотя алгоритм все равно остается неэффективным - O(k 2 ), такая оптимизированная реализация может конкурировать с более эффективными алгоритмами, которые тратят больше процессорных циклов на каждый проход внутреннего цикла.
Длинное беззнаковое умножение 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, и не жалею об этом.
Результатом этого выбора стал красивый и оптимальный код. Конечно, для процессоров с прямым порядком байтов следует выбирать формат с прямым порядком байтов.
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-битными частными и остатком.
Этого вполне достаточно для реализации длинного деления в системе счисления по основанию 2. 16 =65536. Для x86 максимальная ширина делимого составляет 32 бита, что также дает основание системы счисления 65536. После «угадывания» частного числа нужно это число умножить на делитель и вычесть произведение из частичного остатка.
Если результат меньше 0, прибавьте делитель обратно и уменьшите оценку частного на 1. Если остаток по-прежнему меньше 0, снова добавьте делитель и снова уменьшите оценку частного.
В результате мы получим правильное значение частного и правильное значение частичного остатка для продолжения процесса деления.
RSA не требует знания частного, а только остатка от деления.
В связи с этим я написал функцию mpi_moduu , который вычисляет только остаток.
Для 2048-битного RSA необходимо разделить 4096-битные числа на 2048-битные числа, оставив 2048-битный остаток.
Моя процедура выполняет деление на месте: делимое заменяется остатком после завершения процедуры.
Это повышает его эффективность, поскольку «удаление» очередной цифры из делимого превращается в простое приращение указателя.
Кроме того, для хранения частичного баланса и частного не требуется дополнительная память (поскольку она не сохраняется).
Для работы описанного выше алгоритма деления необходимы следующие компоненты длинной арифметики:
- умножение длинного числа на короткое (на одну цифру);
- вычитание длинных чисел;
- сложение длинных чисел;
- сравнение длинных чисел,
Сложность процедуры деления в столбик составляет O(k 2 ) для коротких умножений и O(k) для коротких делений, где k — количество цифр делителя в системе счисления по основанию 65536.
1,5. Длинное сложение и вычитание
Написание процедур сложения mpi_add и вычитание mpi_sub никакой особой изобретательности или каких-то сложных методов не требуется.Каждый процессор имеет команду АЦП, которая складывает два числа и бит переноса из предыдущего сложения.
Если вы каскадируете инструкции АЦП, вы можете добавлять операнды любой емкости.
То же самое верно для инструкций вычитания и 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 отдельно не указывается, но я заметил, что в ГнуПГ p и q генерируются так, что каждое из них представляет собой 1024-битное число со старшим битом, равным 1. О генерации больших простых чисел можно было бы писать книги, не говоря уже о статьях.
Но во многих ситуациях, в том числе и в моей, генерировать ключи на микроконтроллере не обязательно.
Итак, я попытался и успешно сгенерировать ключи с помощью GnuPG. Во-первых, вам нужно сгенерировать пару ключей (открытый+частный) в GnuPG обычным способом.
При этом убедитесь, что вы получили ключ RSA необходимой длины (теперь по умолчанию — 2048 бит).
Несмотря на настойчивые требования GnuPG, вам не следует защищать этот ключ паролем и хранить его на диске в виде открытого текста.
Какая разница, мы все равно собираемся «распотрошить» этот ключ на составляющие его числа p, q, n, d и сохранить их на диск в открытом виде, хотя бы временно.
Экоманда, недокументированная в новых версиях gpg, может экспортировать ключ из базы данных ключей GnuPG.
Где key_id — идентификатор ключа, который можно получить, вызвав gpg --list-secret-keys. Вы получите текстовый файл с таким содержимым:gpg --export-secret-keys --armor [key_id] >filename.asc
-----BEGIN PGP PRIVATE KEY BLOCK-----
Version: GnuPG v2.0.17 (MingW32)
lQOXBE9IdyABCADGT3+Dj0dsVPSkzW+zPlfXc4AsuKpkE9GJNAYD3mrcF70nwk1L
.
Как мы можем извлечь отсюда нужные нам цифры, составляющие ключ? Оказалось, что в самой программе gpg и прилагаемых утилитах таких инструментов НЕТ.
Есть только сторонняя утилита" pgpdump ", который интерпретирует содержимое блока секретного ключа PGP и выводит его в удобочитаемой форме.
Назовите его так: pgpdump -i filename.asc >filename.txt
Получаем нужные нам параметры: Old: Secret Key Packet(tag 5)(919 bytes)
Теги: #RSA #электронная подпись #шифрование в микроконтроллерах #открытый код #криптография #C++
-
Реализация Макета Grid В Swiftui
19 Oct, 24 -
Phatch — Пакетная Обработка Изображений
19 Oct, 24 -
Знакомство С Новым Координаторомlayout
19 Oct, 24
