Почему процесс Дешифрования RSA занимает время, чем Процесс шифрования?
У меня есть некоторая идея, что это происходит из-за некоторого сложного вычисления, но я хочу знать о том, что точно происходит, который занимает много времени, чем соответствующий процесс шифрования. Любая ссылка на веб-страницу или статья очень помогли бы.
Спасибо
Спасибо за ответы, Еще одно Сомнение, Что относительно Подписания и проверки? Эта разница во времени будет там для Подписания и проверки также?напр. Подписание требует большего количества времени, чем Проверка?
7 ответов
Теоретически этого не должно быть. Алгоритмы шифрования и дешифрования практически идентичны. Дано:
d = decryption key
e = encryption key
n = modulus (product of primes)
c = encrypted code group
m = plaintext code group
Тогда:
- Шифрование c i = m i e (mod n)
- Расшифровка m i = c i d (mod n)
Обычный алгоритм возведения в степень является итеративным, поэтому затрачиваемое время зависит от размера показателя степени. В большинстве случаев пара работает с ключом дешифрования (обычно значительно) большим, чем ключ шифрования.
Однако это можно изменить. В качестве игрушечного примера рассмотрим:
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-значными числами нам нужно набраться терпения, чтобы найти пару, для которой дешифрование будет (даже близко) так же быстро, как шифрование.
Короче говоря, "умножить = легко, множитель = сложно".
Взгляните на ( http://en.wikipedia.org/wiki/RSA#Encryption ), который ссылается на оптимизацию в возведении в степень ( http://en.wikipedia.org/wiki / Exponentiation_by_squaring # Additional_applications )
Лучшим ресурсом, который я нашел, была следующая лекция по криптографии из Принстона ( http://www.cs.princeton.edu/courses/archive/spr05/cos126/lectures/ 22.pdf )
Назовем 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), что требует относительно небольшого количества операций умножения. Как следствие, значение расшифровки будет гораздо большим числом и, следовательно, потребует больше усилий для вычисления.
RSA Laboratories довольно хорошо описывает, почему
В практических приложениях обычно выбирают небольшой открытый показатель степени для открытого ключа .
...
При использовании типичных алгоритмов модульного возведения в степень, используемых для реализации алгоритма RSA, операции с открытым ключом занимают O (k ^ 2) шагов, операции с частным ключом - O (k ^ 3) шагов
Сколько еще? У вас есть какие-нибудь точные детали?
В любом случае, имеет смысл, что дешифрование сложнее, чем шифрование, поскольку шифрование не является симметричным, как 123 => abc и abc> 123.
Подробнее Я предлагаю начать здесь .
Чтобы прочитать о том, как работают вычисления, эта статья кажется очень хорошей http://www.di-mgt.com.au/rsa_alg.html
В этом есть два фактора:
Один С другой стороны, публичная экспонента может быть выбрана как небольшое число только с двумя единицами разряда (обычно 3, 17 или 65537). Это означает, что операция шифрования RSA может быть выполнена с помощью нескольких модульных секций и дополнения. Это не может быть отменено: если вы заставите частный показатель быть небольшим числом, безопасность системы, очевидно, будет нарушена.
С другой стороны, владелец закрытого ключа может хранить некоторые предварительно вычисленные значения, полученные из исходных простых чисел. С ними он может использовать алгоритм CRT для замены единственного возведения в степень по модулю n-битного числа на два возведения в степень по модулю n / 2-битного числа. Это примерно в четыре раза быстрее, чем наивный способ.
Таким образом, для пар ключей RSA со случайными общедоступными показателями операции с закрытыми ключами могут быть быстрее. Но эффект от выбора небольшой публичной экспоненты намного больше, чем эффект от более быстрого алгоритма, поэтому на практике шифрование происходит быстрее.