14:11 RSA (криптосистема) | |
| RSA ( Rivest-Shamir-Adleman ) является одной из первых криптосистем с открытым ключом и широко используется для безопасной передачи данных. В такой криптосистеме , то ключ шифрования является открытым и отличаются от ключа дешифрования , который держится в секрете (частный). В RSA эта асимметрия основана на практической сложности факторизации произведения двух больших простых чисел
Пользователь RSA создает, а затем публикует открытый ключ на основе двух больших простых чисел вместе со вспомогательным значением. Простые числа должны храниться в секрете. Любой может использовать открытый ключ для шифрования сообщения, но только тот, кто знает простые числа, может декодировать сообщение. Нарушение шифрования RSA известно как проблема RSA . Является ли это так же сложно, как проблема факторинга, остается открытым вопросом. В настоящее время нет опубликованных методов, позволяющих победить систему, если используется достаточно большой ключ. RSA является относительно медленным алгоритмом, и из-за этого он реже используется для прямого шифрования пользовательских данных. Чаще всего RSA передает зашифрованные общие ключи для криптографии с симметричным ключом, которая, в свою очередь, может выполнять массовые операции шифрования-дешифрования с гораздо более высокой скоростью. Алгоритм RSA состоит из четырех этапов: ключ поколения, распределение ключей, шифрования и дешифрования. Основным принципом, лежащим в основе RSA, является наблюдение, что на практике целесообразно найти три очень больших положительных целых числа e , d и n , которые бы имели модульное возведение в степень для всех целых чисел m (с 0 ≤ m < n ): {\ displaystyle (m ^ {e}) ^ {d} \ эквивалент m {\ pmod {n}}} и что даже зная e и n или даже m, может быть чрезвычайно трудно найти d . Тройника (≡) здесь означает модульное конгруэнтность . Кроме того, для некоторых операций удобно, что порядок двух возведения в степень может быть изменен и что это отношение также подразумевает: {\ displaystyle (m ^ {d}) ^ {e} \ эквивалент m {\ pmod {n}}} RSA включает в себя открытый ключ и закрытый ключ . Открытый ключ может быть известен каждому, и он используется для шифрования сообщений. Предполагается, что сообщения, зашифрованные с помощью открытого ключа, могут быть расшифрованы только в течение разумного периода времени с использованием личного ключа. Открытый ключ представлен целыми числами n и e ; и закрытый ключ - целым числом d (хотя n также используется во время процесса расшифровки Ключи для алгоритма RSA генерируются следующим образом: Выберите два различных простых числа p и q . В целях безопасности целые числа p и q должны выбираться случайным образом и должны быть одинаковыми по величине, но различаться по длине на несколько цифр, чтобы усложнить факторинг. Простые целые числа могут быть эффективно найдены с помощью теста на простоту . p и q держатся в секрете. Вычислить n = pq . n используется как модуль для открытых и закрытых ключей. Его длина, обычно выражаемая в битах, является длиной ключа . N выпускается как часть открытого ключа. Вычислить λ ( n ), где λ - суммарная функция Кармайкла . Поскольку n = pq , λ ( n ) = lcm ( λ ( p ), λ ( q )) и поскольку p и q простые, λ ( p ) = φ ( p ) = p - 1 и аналогично λ ( q ) = q - 1. Следовательно, λ ( n ) = lcm (p - 1, q - 1). λ ( n ) держится в секрете. Выберите целое число e такое, что 1 < e < λ ( n ) и gcd ( e , λ ( n )) = 1 ; то есть e и λ ( n ) взаимно просты . е , имеющий короткую битовую длину и небольшие веса Хэмминга результаты более эффективного шифрования - наиболее часто выбирается значение е является 2 16 + 1 = 65537 . Наименьшее (и самое быстрое) возможное значение для e равно 3, но было показано , что такое небольшое значение для e является менее безопасным в некоторых настройках. е выпущена как часть открытого ключа. Определить d как d ≡ e − 1 (mod λ ( n )) ; то есть, d представляет собой модульную мультипликативный обратное по электронной модулю λ ( п ). Это означает: решить для d уравнение d ⋅ e ≡ 1 (mod λ ( n )) . d может быть эффективно вычислено с использованием расширенного евклидова алгоритма . d хранится в секрете в качестве показателя частного ключа . Открытый ключ состоит из модуля п и общественности (или шифрование) показатель степени е . Закрытый ключ состоит из частного (или дешифрование) показатель D , которые должны храниться в секрете. p , q и λ ( n ) также должны храниться в секрете, поскольку они могут использоваться для вычисления d . Фактически, все они могут быть отброшены после того, как d было вычислено Существует ряд атак против простого RSA, как описано ниже. При шифровании с низкими показателями шифрования (например, e = 3 ) и малыми значениями m (т. Е. M < n 1 / e ) результат m e строго меньше, чем модуль n . В этом случае, шифртексты могут быть легко расшифрованы, принимая E - й корень шифротекста над целыми числами. Если одно и то же текстовое сообщение отправлено e или нескольким получателям в зашифрованном виде, и получатели имеют один и тот же показатель степени e , но разные p , q и, следовательно, n , то легко дешифровать исходное текстовое сообщение с помощью Китайская теорема об остатках . Йохан Хостад заметил, что эта атака возможна, даже если явные тексты не равны, но атакующий знает линейную связь между ними. Эта атака была позже улучшена Доном Копперсмитом . Смотрите также: Атака Медника Поскольку шифрование RSA является детерминированным алгоритмом шифрования (т. Е. Не имеет случайного компонента), злоумышленник может успешно запустить выбранную атаку с открытым текстом на криптосистему, зашифровав вероятные открытые тексты под открытым ключом и проверив, равны ли они зашифрованному тексту. Криптосистема называется семантически безопасной, если злоумышленник не может отличить два шифрования друг от друга, даже если злоумышленник знает (или выбрал) соответствующие открытые тексты. Как описано выше, RSA без отступов не является семантически безопасным. SA обладает тем свойством, что произведение двух зашифрованных текстов равно шифрованию произведения соответствующих открытых текстов. То есть m 1 e m 2 e ≡ ( m 1 m 2 ) e (mod n ) . Из-за этого мультипликативного свойства возможна атака с выбранным шифротекстом . Например, злоумышленник, желающий узнать, как расшифровать зашифрованный текст c ≡ m e (mod n ), может попросить владельца закрытого ключа d расшифровать зашифрованный на вид зашифрованный текст c ′ ≡ cre (mod n )для некоторого значенияr,выбранного атакующим. Из-за мультипликативного свойстваc′ является шифрование mr (mod n ). Следовательно, если злоумышленник успешен в атаке, он узнает mr (mod n ),из которого он может извлечь сообщениеm, умноживmrна модульную обратную величинуrпо модулюn. Учитывая частный показатель d, можно эффективно разложить модуль n = pq . И учитывая факторизацию модуля n = pq , можно получить любой закрытый ключ (d ', n), сгенерированный против открытого ключа (e', n) Чтобы избежать этих проблем, практические реализации RSA обычно встраивают некоторую форму структурированного рандомизированного заполнения в значение m перед его шифрованием. Это заполнение гарантирует, что m не попадет в диапазон незащищенных открытых текстов, и что данное сообщение, после дополнения, будет зашифровано в один из большого числа различных возможных шифротекстов. Стандарты, такие как PKCS # 1 , были тщательно разработаны для надежной защиты сообщений перед шифрованием RSA. Поскольку эти схемы дополняют открытый текст m некоторым количеством дополнительных битов, размер неразбитого сообщения M должен быть несколько меньше. Схемы заполнения RSA должны быть тщательно разработаны, чтобы предотвратить сложные атаки, которые могут быть облегчены предсказуемой структурой сообщений. Ранние версии стандарта PKCS # 1 (до версии 1.5) использовали конструкцию, которая, по-видимому, делает RSA семантически безопасным Использование китайского алгоритма остатка Для эффективности многие популярные криптографические библиотеки (такие как OpenSSL , Java и .NET ) используют следующую оптимизацию для расшифровки и подписывания на основе китайской теоремы об остатках . Следующие значения предварительно вычисляются и сохраняются как часть закрытого ключа: {\ displaystyle p} и {\ displaystyle q}: простые числа от генерации ключей, {\ displaystyle d_ {P} = d {\ pmod {p-1}}}, {\ displaystyle d_ {Q} = d {\ pmod {q-1}}} и {\ displaystyle q _ {\ text {inv}} = q ^ {- 1} {\ pmod {p}}}. Эти значения позволяют получателю более эффективно вычислять возведение в степень m = c d (mod pq ) следующим образом: {\ displaystyle m_ {1} = c ^ {d_ {P}} {\ pmod {p}}} {\ displaystyle m_ {2} = c ^ {d_ {Q}} {\ pmod {q}}} {\ displaystyle h = q _ {\ text {inv}} (m_ {1} -m_ {2}) {\ pmod {p}}} (если {\ displaystyle m_ {1} <m_ {2}}тогда некоторые библиотеки вычисляют h как{\ displaystyle q _ {\ text {inv}} \ left [\ left (m_ {1} + \ left \ lceil {\ frac {q} {p}} \ right \ rceil p \ right) -m_ {2} \ право] {\ pmod {p}}}) {\ displaystyle m = m_ {2} + hq \, {\ pmod {p * q}}} Это более эффективно, чем вычисление возведения в степень путем возведения в квадрат, даже если необходимо вычислить два возведения в модуляр. Причина в том, что эти два модульных возведения в степень используют меньший показатель степени и меньший модуль. Безопасность криптосистемы RSA основана на двух математических задачах: проблема факторизации больших чисел и проблема RSA . Полное дешифрование зашифрованного текста RSA считается невозможным, если предположить, что обе эти проблемы сложны, т. Е. Не существует эффективного алгоритма для их решения. Обеспечение защиты от частичного дешифрования может потребовать добавления схемы защищенного заполнения . Проблема RSA определяется как задача взятия е й корни по модулю составного п : извлечение значения т таким образом, что с ≡ м е ( по модулю п ) , где ( п , е ) является открытым ключом RSA , и с представляет собой RSA шифротекста , В настоящее время наиболее перспективным подходом к решению проблемы RSA является фактор модуля n . Имея возможность восстанавливать простые факторы, злоумышленник может вычислить секретный показатель степени d из открытого ключа ( n , e )., затем расшифруйте c, используя стандартную процедуру. Для этого атакующий делит n на p и q и вычисляет lcm ( p - 1, q - 1), что позволяет определить d из e . Ни один метод полиномиального времени для вычисления больших целых чисел на классическом компьютере еще не найден, но не было доказано, что ни один не существует. Смотрите целочисленную факторизацию для обсуждения этой проблемы . Множественное полиномиальное квадратичное сито (MPQS) может быть использовано для факторизации общего модуля n . Время, затраченное на 128-битное и 256-битное n на настольном компьютере (процессор: Intel Dual-Core i7-4500U 1,80 ГГц), составляет соответственно 2 секунды и 35 минут. | |
|
| |
| Всього коментарів: 0 | |