Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Атаки на алгоритм RSA




Взлом RSA при неудачном выборе параметров криптосистемы (Метод Ферма)

Само по себе использование RSA не обеспечивает безопасности. Дело еще в деталях реализации. Приведем ряд примеров. Для простоты вычислений будем работать с небольшими числами. Цель – показать особенности, не зависящие от размера.

Пример. Пусть пользователь выбрал = 2047, = 179, = 411. Так как 2047 = 23×89, а имеют наименьшее общее кратное 88, то любой обратный к 179 по модулю 88, например 59, будет действовать как .

Пример. Число = 536813567 является произведением простого числа Мерсенна 8191 и простого числа Ферма 65537. Это очень плохой выбор.

Пример. Число 23360947609 является очень плохим выбором для из-за того, что два его простых делителя слишком близки к друг другу. Пусть , тогда имеем . Обозначим: . Так как мало, то – целое число, лишь немного большее причем является полным квадратом. Проверяем подряд целые числа . В нашем примере = 152843, = 152844, = 152845 и , тогда , . Таким образом, мы с третьей попытки нашли и . Количество попыток, необходимых для факторизации , можно при известных и вычислить по следующей формуле: , где – операция округления до ближайшего целого числа.

Релизация атаки на алгоритм шифрования RSA посредством метода Ферма c помощью программы BCalc

Исходные данные: N = 65815671868057; e = 7423489; C = 38932868535359. Найти

1. Вычисляем n = [sqrt(N)] + 1. В поле A помещаем N, в поле B – 2; нажимаем кнопку «D = A ^(1/ B)». В поле D заносится число 8112686, в первую строку таблицы – сообщение «[error]». Это свидетельствует, о том, что N не является квадратом целого числа.

2. t 1 = n + 1. Возводим число t 1 в квадрат: A: = 8112687, B: = 2, C: = 0 (возведение в квадрат будет производиться не по правилам модульной арифметики), нажимаем «D = A ^ B mod C» => D = t 1^2 = 65815690359969.

Вычисляем w 1 = t 1^2 – N. Для этого A:= t 1^2, B:= – N, затем нажимаем «D = A + B» => D= w 1 = 18491912. Проверяем, является ли w 1 квадратом целого числа: A:= w 1,
B:= 2, нажимаем «D = A ^(1/ B)» => в первой строке таблицы появляется сообщение «[error]», следовательно проделываем п. 2 заново с t 2 = n + 2 и так далее, пока не найдем, что некое w i является квадратом целого числа.

3. При вычислении квадратного корня w 5 первая строка таблицы остается пустой, а D = sqrt(w 5) = 9132, что свидетельствует об успехе факторизации. t 5 = 8112691.

4. Вычисляем p = t 5 + sqrt(w 5); A:= t 5, B:= sqrt(w 5), нажимаем «D = A + B» => D = p = 8121823; q = t 5 – sqrt(w 5) = 8103559.

Вычисляем Phi(N) = (p – 1)(q – 1), A:= 8121822, B:= 8103558, нажимаем «D = AB» => D= Phi(N) = 65815655642676.

Вычисляем d, как обратный к e: A:= e, B:= –1, C:= Phi(N), нажимаем «D = A ^ B mod C» => D = d = 12490789985101.

5. Производим дешифрацию шифрблока С: A:= C; B:= d; C:= N. Нажимаем «D = A ^ B mod C». В поле D находится исходное сообщение M = 3402418120. Переводим M в текстовый вид. Для этого A:= M, нажимаем «D = text(A)» => D = = «КМЗИ».

Снимок экрана с окном программы «BCalc» приведен ниже.

 

 






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных