Comments 29
rsaref рассматривали в качестве варианта или базы для вашей реализации?
UFO just landed and posted this here
Ну там подписать, проверить подпись?
Я использую этот код для проверки подписи. Но для этого, кроме RSA, нужно еще реализовать криптографический хэш. Это тема для отдельной статьи.
Шифрование/расшифрование как то мягко говоря не звучит в контексте ЭЦП.
Генерация ЭЦП использует в качестве основы «расшифрование» RSA, проверка ЭЦП — «зашифрование» RSA. Таким образом, обладатель открытого ключа может проверить подпись, а сгенерировать ее — только обладатель секретного ключа. Так что связь самая прямая. Но, как я уже заметил, одного RSA здесь мало.
UFO just landed and posted this here
1. Даже если хеш приходит готовый, генерация ЭЦП не ограничивается вызовом базового примитива RSA. Скажем, для схем подписи типа PSS, нужно еще сгенерировать некоторое количество криптографически случайных чисел, вычислить функцию MGF, перексорить данные друг с другом, и только потом вызвать примитив rsa_decrypt (который в некоторых реализациях называется rsa_secret). Аналогично и для проверки подписи: сначала вызывается rsa_encrypt (или rsa_public), потом вычисляются MGF, ксорки, хеш над сообщением, и результаты сравниваются. Я ни в коем случае не утверждаю, что все это делать не нужно. Но эти дополнительные действия выходят за рамки примитивов rsa_encrypt и rsa_decrypt (или, если угодно, rsa_secret и rsa_public соответственно). Я же выложил и описал в статье реализацию только базового примитива rsa_encrypt (rsa_public). И так статья получилась объемной.
2. У меня термины не путаются. Независимо от того, для каких целей применяется RSA (шифрование или ЭЦП), работа самого алгоритма от этого не меняется. Это уже ваше дело, какие данные преобразовывать алгоритмом RSA — то ли это сами шифруемые/подписываемые данные, то ли это ключ симметричного шифра, то ли это хеш от данных. В зависимости от того, что вы будете преобразовывать с помощью RSA, у вас получится или асимметричное шифрование, или ЭЦП, или абракадабра.
Просто традиционно преобразование (1) называется зашифрованием, а преобразование (2) — расшифрованием RSA. Но если мыслить более широко — то оба эти преобразования изменяют данные до неузнаваемости. Разница лишь в том, что для применения (2) надо знать секретный ключ, а для (1) достаточно знать только открытый.
2. У меня термины не путаются. Независимо от того, для каких целей применяется RSA (шифрование или ЭЦП), работа самого алгоритма от этого не меняется. Это уже ваше дело, какие данные преобразовывать алгоритмом RSA — то ли это сами шифруемые/подписываемые данные, то ли это ключ симметричного шифра, то ли это хеш от данных. В зависимости от того, что вы будете преобразовывать с помощью RSA, у вас получится или асимметричное шифрование, или ЭЦП, или абракадабра.
Просто традиционно преобразование (1) называется зашифрованием, а преобразование (2) — расшифрованием RSA. Но если мыслить более широко — то оба эти преобразования изменяют данные до неузнаваемости. Разница лишь в том, что для применения (2) надо знать секретный ключ, а для (1) достаточно знать только открытый.
У меня где то валяляются исходники на C для быстрого возведения в степень по Монтгомери. Запускал на АТ91SAM7, подпись с ключом 1024-бита (на то время был рекомендуемым) происходила за приемлемое время (около секунды). К сожалению, проект не выгорел, по этому смысла в них нет никакого.
Примененный вами «трюк с использованием Китайской теоремы об остатках» требует хранения ключа в расширенном формате, но имеет сравнимую скорость. Хотя, какой способ более быстрый — вопрос открытый. Видимо зависит и от реализации…
Примененный вами «трюк с использованием Китайской теоремы об остатках» требует хранения ключа в расширенном формате, но имеет сравнимую скорость. Хотя, какой способ более быстрый — вопрос открытый. Видимо зависит и от реализации…
Спасибо! Крайне интересная тема!
Как здесь уже заметили — интересно было-бы посмотреть пример кода, использующего эту библиотеку.
Как здесь уже заметили — интересно было-бы посмотреть пример кода, использующего эту библиотеку.
В криптосистеме с электронной подписью, кроме RSA, нужно еще реализовать криптографический хеш. Для шифрования напрямую RSA обычно не используется, а только совместно с блочным шифром. В общем, RSA — это лишь кирпич в здании криптосистемы. Если рассматривать систему целиком — то потребовалось бы рассмотреть и остальные кирпичи, составляющие ее. Но мне кажется, что тема RSA сама по себе достаточно сложна, и нет смысла отвлекаться на другие, мало связанные с ней, вещи, в рамках этой статьи.
Я думаю народ намекает на более простые вещи, например, что неплохо бы на github положить файлик с main(), который бы чего-то считал, а после делал бы хотя бы assert на memcmp с ожидаемым результатом.
Намек понял.
Но вам с какой целью? Реально будете запускать и убеждаться, что работает? Или просто «для галочки»? А то я что-то смотрю, что интерес аудитории к этой теме низок. В этой связи берут сомнения, нужна ли реально кому-нибудь эта дополнительная работа на создание файлика с main().
Но вам с какой целью? Реально будете запускать и убеждаться, что работает? Или просто «для галочки»? А то я что-то смотрю, что интерес аудитории к этой теме низок. В этой связи берут сомнения, нужна ли реально кому-нибудь эта дополнительная работа на создание файлика с main().
> А то я что-то смотрю, что интерес аудитории к этой теме низок.
Я обычно иду по хостинг-линкам в статьях на код, глянуть. Если линки ведут на гитхаб, я обычно вижу 0-3 звезды. Вы набрали 13 звезд за три дня. По-моему, это *очень* хороший результат (за год столько можно не набрать). Ну а по поводу «низкого интереса» — криптография это все таки не JavaScript, толп собираться не будет, тем более, вокруг embedded криптографии.
> Реально будете запускать и убеждаться, что работает?
Реально скомпилил с "-c -Os", запустил size, увидел 1K, подумал, что хорошо, но сразу дальше подумал: «а с обвязкой сколько реально будет?».
> В этой связи берут сомнения, нужна ли реально кому-нибудь эта дополнительная работа на создание файлика с main().
Вы выпустили код под BSD лицензией — вы сами-то хотите, чтобы им пользовались? И вы уже кучу времени потратили на написание кода, портирование с asm на C, написание статьи. Я понимаю проблему последней мили, но почему бы ее все же не пройти и не быть довольным, что работа проделана до конца, а другим ничего не остается сказать, кроме «парень, ты крут»?
Я обычно иду по хостинг-линкам в статьях на код, глянуть. Если линки ведут на гитхаб, я обычно вижу 0-3 звезды. Вы набрали 13 звезд за три дня. По-моему, это *очень* хороший результат (за год столько можно не набрать). Ну а по поводу «низкого интереса» — криптография это все таки не JavaScript, толп собираться не будет, тем более, вокруг embedded криптографии.
> Реально будете запускать и убеждаться, что работает?
Реально скомпилил с "-c -Os", запустил size, увидел 1K, подумал, что хорошо, но сразу дальше подумал: «а с обвязкой сколько реально будет?».
> В этой связи берут сомнения, нужна ли реально кому-нибудь эта дополнительная работа на создание файлика с main().
Вы выпустили код под BSD лицензией — вы сами-то хотите, чтобы им пользовались? И вы уже кучу времени потратили на написание кода, портирование с asm на C, написание статьи. Я понимаю проблему последней мили, но почему бы ее все же не пройти и не быть довольным, что работа проделана до конца, а другим ничего не остается сказать, кроме «парень, ты крут»?
Вы набрали 13 звезд за три дня. По-моему, это *очень* хороший результат (за год столько можно не набрать)
Хм. Не обращал внимания, не знал про эти звезды. Ну что ж, убедили, значит интерес есть! На досуге займусь дополнительными материалами.
а с обвязкой сколько реально будет?
Для «голого» RSA обвязки больше не нужно. Ну разве что ключи где-то хранить (а они по 256 байт каждый). Для ЭЦП и шифрования нужен еще симметричный шифр (такой, как AES) и/или криптографический хеш (такой, как SHA-256). AES у меня есть, а вот SHA не делал пока. Тут еще все зависит от того, что именно предполагается шифровать или подписывать. В зависимости от этого оптимальная встраиваемая реализация может сильно отличаться. Что посоветуете в этой ситуации? Написать еще один пост и выложить вместе с ним этот дополнительный код?
Для ЭЦП и шифрования нужен еще симметричный шифр (такой, как AES) и/или криптографический хеш (такой, как SHA-256)
Там кстати еще нужно схемы дополнений реализовывать, типа OAEP. Или вы как раз о них?
Если есть время и желание писать статьи — пишите ;-). Если уж спрашиваете рекомендаций, то если есть желание и азарт, можете написать не только о том, что хотели, но и про то «как я написал самые маленькие по размеру реализации AES и SHA256». Конечно, для этого надо сначала сделать небольшой обзор существующих реализаций. Попробуйте например написать sha256 меньше, чем здесь (это лучшее, что я нашел за несколько небольших сессий поиска). Или aes128 меньше, чем здесь.
Нужно только четко определиться с правилами, конечно. Никаких асмов под конкретную архитектуру, только C, и компилить под одну архитектуру, одним компиляторо с одним набором опций. Иначе в соседней статье aes в одну сторону в килобайт вмещали, а в каментах ваш коллега по z80 и в обе стороны делал ;-).
Нужно только четко определиться с правилами, конечно. Никаких асмов под конкретную архитектуру, только C, и компилить под одну архитектуру, одним компиляторо с одним набором опций. Иначе в соседней статье aes в одну сторону в килобайт вмещали, а в каментах ваш коллега по z80 и в обе стороны делал ;-).
Раз уж вы взялись реализовывать всё самостоятельно, рекомендую прочитать: cryptocoding.net/index.php/Coding_rules
А библиотека типа PolarSSL разве не влезает?
В связи с этим C-код получился намного эффективнее первоначального кода на C++ и лишь немного уступает ассемблеру.
Вот интересно было бы увидеть параграф про сравнение этих реализаций…
Это тяжело. Производительность надо сравнивать на одной и той же системе. Сам C-код я под dsPIC не компилировал, т.к. нет компилятора. Компиляторы платные или с заблокированной оптимизацией, поэтому я вынужден писать под dsPIC только на ассемблере. В свою очередь, в тех системах, где есть бесплатные и хорошие C-компиляторы (x86) нет возможности исполнить ассемблерный код dsPIC.
Добавлю. Мое утверждение «лишь немного уступает ассемблеру» основано на том, как я оцениваю свои возможности перевести этот код на другой ассемблер (например, x86), и что в результате этого удалось бы оптимизировать. Не так уж много. За исключением разве что случая использования команд SIMD. Но это очень трудоемко, а выгода мала по сравнению с возможностью привлечь более эффективные алгоритмы умножения и деления.
e обычно равно 65537
Злоумышленник зная число e легко найдет M — открытый текст.
e нужно выбирать вот так
Вычислить m = (p — 1) * (q — 1)
Выбрать число d взаимно простое с m
Выбрать число e так, чтобы e * d = 1 (mod m)
Можно подробнее, как знание открытой экспоненты e поможет найти открытый текст?
Проблема в том, что злоумышленник не знает p и q, а знает только их произведение n. Разложить его на множители он не может за приемлемое время.
Обладатель же секретного ключа знает p и q и вычисляет d способом, похожим на описанный вами.
То, что e всегда равно константе (65537) — это, разумеется, не требование, но практически всегда поступают именно так. Число 65537 простое, так что вероятность, что phi = (p-1)*(q-1) не является с ним взаимно простым, достаточно мала. Можно при генерации ключа отвергать такие ключи, для которых не подходит e=65537.
Обладатель же секретного ключа знает p и q и вычисляет d способом, похожим на описанный вами.
То, что e всегда равно константе (65537) — это, разумеется, не требование, но практически всегда поступают именно так. Число 65537 простое, так что вероятность, что phi = (p-1)*(q-1) не является с ним взаимно простым, достаточно мала. Можно при генерации ключа отвергать такие ключи, для которых не подходит e=65537.
А не подскажете оптимальный алгоритм шифрования для Arduino? Понятно что чудес не бывает, но может быть есть какие-то упрощенные ассиметричные алгоритмы, которые можно на этом контроллере запустить?
Я думаю, там можно запустить AES, а вот насчет асимметричных — сложнее. Я знаю только RSA и Elliptic curve cryptography, но для последнего тоже нужна длинная арифметика. Теоретически ее можно реализовать и на 8-битных контроллерах, только вот скорость работы будет оставлять желать лучшего. Попробуйте на ассемблере. Ну и памяти может не хватить.
В примере с n=77 Вам не удастся зашифровать исходные тексты М =1,22,56,34,43,76 и возможно еще другие. А утверждение о невозможности прочесть сообщение без знания личного ключа (он не обязан иметь гриф секретности) просто неверно. Существует бесключевая атака на RSA.
Sign up to leave a comment.
Компактная реализация RSA для встраиваемых применений