Поиск значений p и q шифра RSA(для малых размеров ключа)

Для алгоритма RSA введем следующие обозначения:

(e, n) - открытый ключ (public key);

(d, n) - закрытый ключ (private key).

Если размеры открытого ключа невелики, то закрытый ключ можно получить, если разложить на простые множители значение n=p*q. Прямым перебором сделать это невозможно, однако используя предлагаемую ниже рекурсивную формулу, можно получить значения p и q сравнительно просто при следующих начальных условиях: p =1, q = n -1, f(p,q)=q.

Количество шагов для вычисления при этом равно n-p+q.

Значения для проверки:

863*2963=2557069, 8072791*2371=19140587461.

Задача №20. Предположим n=143. Какие значения принимает q на последних шагах рекурсии?

При затруднении используйте приведенную ниже таблицу.

Вскрытие шифра перестановки

[28, с. 107]

Осуществляется на основе таблицы логарифмов вероятностей появления биграмм в тексте (см. приложение).

Пример: рассмотрим шифртекст: «АЗЮЖЕ СШГТООИПЕР» и расположим его в прямоугольной таблице:

Рассматривая маловероятные сочетания двух букв, легко найти истинную последовательность столбцов:

P₁₂=p(АЗ) *p(Е)*p(ГТ)*p(ИП)=7+9+0+5=21;

P₁₃=p(АЮ)*p(ЕС)*p(ГО)*p(ИЕ)=6+8+8+8=30;

P₁₄=p(АЖ)*p(ЕШ)*p(ГО)*p(ИР)=7+5+8+7=27.

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

Далее по смыслу фрагментов таблицы легко угадывается текст. Расставив строки в порядке (4123) получаем открытый текст и ключи шифрования соответственно: К1, К2=(3142, 3214).

Задача №21. Шифртекст: «О^БКО^^ТООКЛШЛУЕИЫЛС» (^означает пробел, ^^ два пробела). Контрольная фраза «КОЛОБОК». Метод: перестановка. Определить ключ шифрования, используя таблицу вероятностей биграмм в тексте.

МОДЕЛИ ЗАЩИТЫ ДОСТУПА К ИНФОРМАЦИОННЫМ СИСТЕМАМ