Возможности криптоаналитика

Предположим, что злоумышленник, скажем, Ева, перехватила секретное сообщение для Боба. Если Ева знает секретный показатель Боба, то она может вскрыть из шифртекста в точности тем же путем, что и Боб, а именно вычислив (см. (9.5)).

Определить по публичному показателю и сравнению
(см. (9.4)) Еве будет легко если она знает: она просто использует расширенный алгоритм Эвклида, как это делал Боб при формировании системы.

Чтобы найти (см. (9.3)), Еве нужно факторизовать (т.е. разложить на простые множители) число.

Во время введения RSA Шроппель (Schroeppel) предложил модификацию алгоритма факторизации Моррисона и Бриллхарта [5]. Она включала

операций.

При построении следующей таблицы, дающей представление о росте этого выражения в от длины, используются функции TableForm, Table, Exp, Sqrt, Log и N из пакета "Mathematica"

TableForm[ Table [

{k, N[Exp[Sqrt[Log[10^k]*Log[Log[10^k]]]], 3]},

{k, 25, 250, 25}], TableHeadings ->

{{}, {"length in digits", "complexity"}},

TableAlignments -> {Center}]

length in digits	complexity
	4.30´10^6
	1.42´10^10
	8.99´10^12
	2.34´10^15
	3.41´10^17
	3.26´10^19
	2.25´10^21
	1.20´10^23
	5.17´10^24
	1.86´10^26

Как можно видеть, если имеет длину около 200 цифр, указанный выше способ криптоанализа недоступен. С другой стороны, были разложены числа, много большие, чем считалось возможным в то время, когда была предложена схема RSA.

Последний известный рекорд факторизации ‑ это разложение на простые множители 232-значного числа. В опубликованном исследователями отчете говорится, что 12 декабря 2009 года они завершили факторизацию 768-битного модуля RSA, взятого из конкурса RSA Challenge. Предыдущий рекорд был установлен 09 мая 2005 года, когда было объявлено о факторизации 663-битного числа.

На практике RSA с длиной ключа 768 бит почти не используется; большинство систем используют ключи длиной 1024 или 2048 бит, так что непосредственной угрозы для безопасности полученные результаты не представляют. К тому же, по оценкам исследователей, факторизация 1024-битного модуля будет примерно в тысячу раз сложнее факторизации 768-битного модуля. Тем не менее, полученный результат имеет огромное академическое значение.

По этой причине очевидны предложения использовать для RSA существенно большие модули.

Пример быстрого алгоритма факторизации можно найти в [4]. Существуют специальные алгоритмы факторизации, которые работают быстрее, если имеет особую форму.

До сих пор пока не известен способ взлома системы RSA, кроме разложения модуля, но формальное доказательство эквивалентности этих двух проблем отсутствует.

Недостатком при выборе больших модулей является то, что выполнение одного возведения в степень требует достаточно большого времени, особенно когда нужно шифровать длинный файл. В такой ситуации часто применяют гибридную систему: для шифрования данных используется симметричная система с секретным ключом, а схема RSA используется, чтобы безопасно послать этот ключ получателю (применив публичные параметры получателя).

При генерации и не безопасно сначала генерировать, а затем испытывать на простоту числа,,.... В действительности нужно, чтобы число (считая) было большим. В самом деле, если криптоаналитик может угадать, например, проверяя все вероятные значения, то он может определить из равенства

Из двух линейных уравнений находятся и, что влечет за собой взлом системы.

Дата добавления: 2013-12-12