У меня есть идея, что это связано с некоторыми сложными вычислениями, но я хочу знать, что именно происходит, что занимает много времени, чем соответствующий процесс шифрования. Любая ссылка на веб-страницу или бумагу будет очень полезной.
Спасибо
Спасибо за ответы, еще одно сомнение, а как насчет подписи и проверки? Будет ли разница во времени для Подписи и проверки? Ex. Для подписи требуется больше времени, чем проверка?
В теории это не обязательно. Алгоритмы шифрования и дешифрования по существу идентичны. Дано:
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 of 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), которое требует относительно небольшого числа операций умножения. Следовательно, значение дешифрования будет намного большим числом и, следовательно, потребуется больше работы для вычисления.
В этом есть два фактора:
С одной стороны, общественный экспонент может быть выбран как небольшое число с двумя только 1 бит (обычно 3, 17 или 65537). Это означает, что операция шифрования RSA может быть выполнена с помощью нескольких модульных квадратов и добавления. Это не может быть отменено: если вы вынуждаете частный показатель быть небольшим числом, безопасность системы, очевидно, нарушена.
С другой стороны, держатель закрытого ключа может хранить некоторые предварительно рассчитанные значения, полученные из исходных простых чисел. С ними он может использовать алгоритм CRT, чтобы заменить единое возведение в степень по n-битовому числу с двумя экспонентами по модулю 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
Короче говоря, "multiply = easy, factor = hard".
Взгляните на (http://en.wikipedia.org/wiki/RSA#Encryption), который ссылается на оптимизацию при экспонировании (http://en.wikipedia.org/wiki/Exponentiation_by_squaring#Further_applications)
Лучший ресурс, который я нашел, - следующая лекция о криптографии из Принстона (http://www.cs.princeton.edu/courses/archive/spr05/cos126/lectures/22.pdf)
d и e являются мультипликативно обратными числами по модулю phi(n). Это означает, что это не имеет значения, ведьма из двух вы выберете для шифрования, а также для дешифрования. Вы просто выбираете один раз перед шифрованием. Если вы хотите быстро расшифровать, чем выбрать большее число для шифрования. Это просто.