на тему : Расшифровка RSA и его стойкость

Выполнил:

Студент группы 3-СКС-11

Катушков П.С.

Принял:

Рогоза Б. Е.

Днепропетровск 2015

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

Задание 1. Проверка электронно-цифровой подписи (ЭЦП). Фирма получила по компьютерной сети важный договор от VIP - клиента с его ЭЦП, созданной по алгоритму RSA. Попытки расшифровать подпись открытым ключом не увенчались успехом. Было установлено, что на сайте, на котором вывешены открытые ключи, ошибочно помещена их противоположная закрытая шифрующая пара.

Требуется: на основании знания свойств RSA расшифровать электронно-цифровую подпись клиента, создав программу " Дешифр RSA", объединяющую три новые программные функции с именами:

1. " Factors" - факторизация параметра ключа N;

2. " invMod" - вычисление по шифрующему ключу E его пары D;

3. " deShifr" - расшифровка текста согласно уравнению X = Y D mod N.

и четыре функции, ранее созданные в ЛР-9:

4. " BVS" - быстрое возведение в степень с минимальным числом операций умножения;

5. " Mult" - перемножение длинных целых чисел без переполнения регистра;

6. " CodeAlf" - кодировка символов текста согласно алфавита;

7. " deCodeAlf" - декодирование длинного числа в символы текста;

Примечание. Для шифрования подписи использован 100-символьный алфавит '_123456789'+RU(32)+ru(32)+en(26)', ранее применявшийся в ЛР-9.

Вариант №5:

Задание 2. Циклическая атака на RSA. Требуется создать программу циклического шифрования, или циклической атаки на шифр RSA и прочитать без знания ключа имя владельца цифровой подписи из вашего варианта предыдущего задания. В отчете по заданию следует обязательно указать время взлома и длину цикла атаки.

Для правильной работы программы следует добавить в окно " Редактора JS" после приведенного основного кода функции с именами: 1) " CodeAlf"; 2) " DecodeAlf" 3) " BVS"; 4) " Mult".

Вариант №5

//функция кодирования текста

function CodeAlf(X){

…

} //конец функции CodeAlf(X)

//функция умножения длинных чисел " a" и " b" по модулю " N"

function Mult(a, b, N)

{

…

} //конец функции Mult

//функция BVS(A, k)- быстрое возведение в степень числа А**k mod N

function BVS(A, k){

…

} //конец функции BVS(A, k)

//функция DecodeAlf(x1)-разбивает кодовое слово на блоки по две цифры и проводит раскодировку

function DecodeAlf(x1){

…

} //конец DecodeAlf()

//тело основной программы

//бесключевое раскрытие шифра RSA

X=" ОСТАП"; Ek=191; N=4465239209;

Xc=CodeAlf(X); //кодируем

Yc=BVS(Xc, Ek); //шифруем

//циклическая атака на шифр

s0=-1; s=0; Z0=Yc; Z=Z0;

//формула атаки: Z=Z**E mod N

while(s0< s){Z1=Z; Z=BVS(Z, Ek);

s=s+1;

if(Z==Z0){

writeln(" Шифр RSA взломан! ")

writeln(" Длина цикла атаки =" +s);

s=s0} //конец if

} //коенц цикла атаки

X1=DecodeAlf(Z1); //декодирование Z1

writeln(" Секретный текст = " + X1)

Результат:

Время счета: 193.385 сек.

Шифр RSA взломан!

Длина цикла атаки =578376

Секретный текст = ОСТАП

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