У меня есть предположение, что это связано с некоторыми сложными вычислениями, но я хочу знать, что именно происходит, что занимает больше времени, чем соответствующий процесс шифрования. Любая ссылка на веб-страницу или документ будет большим подспорьем.
Спасибо
Спасибо за ответы, еще одно сомнение, как насчет подписи и проверки? Будет ли разница во времени для подписи и проверки? Бывший. Для подписи требуется больше времени, чем для проверки?
Теоретически этого не должно быть. Алгоритмы шифрования и дешифрования практически идентичны. Данный:
d = decryption key
e = encryption key
n = modulus (product of primes)
c = encrypted code group
m = plaintext code group
Потом:
Обычный алгоритм возведения в степень является итеративным, поэтому затрачиваемое время зависит от размера показателя степени. В большинстве случаев пара работает с ключом дешифрования (обычно значительно) большим, чем ключ шифрования.
Однако это можно изменить. В качестве игрушечного примера рассмотрим:
p=17
q=23
n=391
Вот список некоторых допустимых пар ключей шифрования / дешифрования для этой конкретной пары простых чисел:
e = 17, d = 145
e = 19, d = 315
e = 21, d = 285
e = 23, d = 199
e = 25, d = 169
e = 27, d = 339
e = 29, d = 85
e = 31, d = 159
e = 35, d = 171
e = 37, d = 333
e = 39, d = 343
e = 41, d = 249
e = 43, d = 131
e = 45, d = 133
e = 47, d = 15
e = 49, d = 273
e = 51, d = 283
e = 53, d = 93
e = 57, d = 105
e = 59, d = 179
Из этих 20 пар ключей только одна имеет ключ дешифрования, меньший, чем ключ шифрования. В других случаях размер ключа дешифрования варьируется от чуть менее чем вдвое до почти в 17 раз большего размера. Конечно, когда модуль такой крошечный, как этот, быстро и легко сгенерировать множество пар ключей, поэтому найти небольшой ключ дешифрования будет довольно просто - с настоящим ключом RSA, однако, это не так тривиально, и обычно мы просто принимаем первую найденную пару. Как видно из приведенного выше списка, в этом случае вы, скорее всего, получите ключ дешифрования, который значительно больше, чем ваш ключ шифрования, и, следовательно, дешифрование будет медленнее, чем шифрование. При работе с ~ 100-значными числами нам нужно набраться терпения, чтобы найти пару, для которой дешифрование будет (даже близко) так же быстро, как шифрование.
Назовем n, d и e модулем RSA, частным показателем и публичным показателем соответственно. Скорость дешифрования RSA пропорциональна (log d) (log n) 2 (т.е. квадратична по длине модуля и линейна по длине частной экспоненты) . Точно так же скорость шифрования RSA пропорциональна (log e) (log n) 2. Владелец закрытого ключа также знает факторизацию n, которая может использоваться для ускорения работы закрытого ключа примерно в 4 раза (с помощью Китайская теорема об остатках). Подробнее о задействованных алгоритмах см. Справочник по прикладной криптографии, особенно главу 14 ( «Эффективное внедрение»).
Для надлежащей безопасности частный показатель степени (d) должен быть большим; было показано, что если он меньше 29% длины модуля (n), то закрытый ключ может быть восстановлен. Мы не знаем, какова минимальная длина, чтобы избежать таких недостатков, поэтому на практике d будет иметь примерно такую же длину, как n. Это означает, что расшифровка будет примерно кубической при длине n.
Те же положения не применяются к публичному показателю (e), который может быть сколь угодно маленьким, если он соответствует правилам RSA (e должен быть относительно простое с r-1 для всех простых множителей r от n). Поэтому обычно выбирается очень маленький e. Это настолько обычное дело, что существуют широко распространенные реализации, которые не могут обрабатывать большие общедоступные экспоненты. Например, реализация RSA в Windows CryptoAPI (тот, который используется, например, Internet Explorer при подключении к сайту HTTPS с сертификатом сервера RSA) не может обрабатывать открытый ключ RSA, если e не подходит для 32 биты. e = 3 - наилучшее возможное, но e = 65537 - традиционное (это историческая ошибка, потому что очень маленький показатель степени может вызвать кажущуюся слабость, если RSA используется без надлежащего стандартного заполнения, чего в любом случае делать не следует). 65537 - это 17-битное целое число, тогда как типичная длина для n и d будет 1024 бит или более. Это делает операции с открытым ключом (шифрование сообщения, проверка подписи) намного быстрее, чем операции с закрытым ключом (расшифровка сообщения, генерация подписи).
Мощность шифрования обычно выбирается как простое число в форме 2 ^ n + 1 (17, 63357), что требует относительно небольшого числа операций умножения. Как следствие, значение дешифрования будет намного больше, и, следовательно, потребуется больше работы для вычисления.
2^n+1 приводит к ускорению, но основное ускорение происходит из-за небольшой мощности шифрования. Ваше второе предложение о расшифровке намекает на это, но я бы рекомендовал добавить это явно к первому предложению о шифровании.
- person CodesInChaos; 19.06.2014
В этом участвуют два фактора:
С одной стороны, публичная экспонента может быть выбрана как небольшое число только с двумя единицами разряда (обычно 3, 17 или 65537). Это означает, что операция шифрования RSA может быть выполнена с помощью нескольких модульных секций и дополнения. Это не может быть отменено: если вы зададите частному показателю небольшое число, безопасность системы, очевидно, будет нарушена.
С другой стороны, владелец закрытого ключа может хранить некоторые предварительно вычисленные значения, полученные из исходных простых чисел. С ними он может использовать алгоритм CRT для замены одинарного возведения в степень по модулю n-битное число с двумя экспонентами по модулю / 2-битного числа. Это примерно в четыре раза быстрее, чем наивный способ.
Таким образом, для пар ключей RSA со случайными общедоступными показателями операции с закрытыми ключами могут быть быстрее. Но эффект от выбора небольшой публичной экспоненты намного больше, чем эффект от более быстрого алгоритма, поэтому на практике шифрование происходит быстрее.
RSA Laboratories очень хорошо объясняет, почему
В практических приложениях обычно выбирают небольшую открытую экспоненту для открытого ключа.
...
При использовании типичных алгоритмов модульного возведения в степень, используемых для реализации алгоритма RSA, операции с открытым ключом занимают O (k ^ 2) шагов, а операции с частным ключом - O (k ^ 3) шагов.
Как долго? У вас есть точные данные?
В любом случае имеет смысл, что дешифрование сложнее, чем шифрование, поскольку шифрование не является симметричным, как 123 => abc и abc> 123.
Для получения дополнительных сведений я предлагаю начать здесь.
Чтобы узнать, как работает расчет, эта статья кажется очень хорошей http://www.di-mgt.com.au/rsa_alg.html
Короче говоря, «умножить = легко, множитель = сложно».
Взгляните на (http://en.wikipedia.org/wiki/RSA#Encryption), который ссылается на оптимизацию в возведении в степень (http://en.wikipedia.org/wiki/Exponentiation_by_squaring#FFurther_applications)
Лучшим ресурсом, который я нашел, была следующая лекция по криптографии из Принстона (http://www.cs.princeton.edu/courses/archive/spr05/cos126/lectures/22.pdf)
d и e - числа, обратные по модулю phi(n). Это означает, что не имеет значения, какой из двух вариантов вы выберете для шифрования, а какой - для дешифрования. Вы просто выбираете один раз перед шифрованием. Если вам нужно быстрое дешифрование, вы выбираете большее число для шифрования. Это так просто.
e (в результате получается большое d. Вы также можете использовать большое число как e вместе с большим d. Что вам не следует делать, так это использовать маленькое d. Это ослабляет безопасность.
- person CodesInChaos; 19.06.2014
