Презентация на тему Криптоанализ RSA

φ(п)
Расчет
закрытой экспоненты
d=е-1modφ(n)
Полиномиально
эквиваленты

φ(п)
п = pq
φ(п) =( p -1)(q-1)

=1
ЭКСПОНЕНЦИАЛЬНЫЙ
ПОЛИНОМИАЛЬНЫЙ
ε =0
Эффективны
Не эффективны
0

на эллиптических

Общий метод
решета числового поля

р – наименьший множитель числа N

– взаимно простые, то по китайской тереме от остатках

и отсюда найти
С=M 3mod п1п2п3

M 3 < п1п2п3

Т.к.

M = C1t1 C2 -t2 mod n
Атака на

Почему?

t2= (t1e1 -1)/e2

еmod п
С≡(M1M2)е=M1еM2еmod п=С1С2
можно построить атаку
С·M 1-e=M2еmod п

п
. . .
. . .
С ·(2L/2)-e
1еmod п
2еmod п
3еmod п
.

. . .

(2L/2 )еmod п

С·i -еmod п

≡

j emod n

M= i · j

п
…
Сk-2е≡Сk-1mod п
Сk-1е≡Сkmod п ≡ C
Атака успешна, если порядок

М = Сk-1

ЦЕПНЫЕ (НЕПРЕРЫВНЫЕ) ДРОБИ

Любое действительное число х можно представить цепной дробью

x = [a0; a1, a2,…]

?
. . .
-целая часть числа х
Атака Винера: математическое

x0 = x – a0 ;

xi – 1

числа
Решение.
Атака Винера:

x = [a0; a1, a2,…]

p–1 = 1;

p0 = a0 ;

q0 = 1

q–1 = 0;

; i = 1,2,…

Пример. Найти подходящие дроби для цепной дроби

Решение.

[0; 2, 1, 10, 3]

a0 a1 a2 a3 a4

p–1 = 1;

p0 = 0 ;

q0 = 1

q–1 = 0;

p1 = 1;

q1 = 2;

p2 = 1;

q2 = 3;

Подходящие дроби:

p3 = 11;

q3 = 32;

p4 = 34;

q4 = 99

Если несократимая дробь удовлетворяет неравенству:

то дробь – одна из подходящих дробей в разложении числа х в цепную дробь.

то

это классическая аппроксимация с помощью цепных дробей;

число дробей , где , не больше log n

для некоторого k выполнится . Тогда так как НОД (k, d) =1, то p = k, q = d

d < n

Среди подходящих дробей p/q найти ту, для которой eq-1

экспонента была не меньше, чем
Например, если  модуль  имеет размер

п 0,292

Если длина модуля |n|=1024 бит, то длина секретной экспоненты

M=С dmod п

Секретный ключ – экспонента d

от длины модуля
Каждое удвоение длины ключа RSA увеличивает

Длина модуля RSA в битах

Время расшифрования (миллисекунды)

Pentium, 2 ГГц

http://security.stackexchange.com/questions/1833/encryption-decryption-time

Нужен алгоритм расшифрования
с минимальным числом операций

длина модуля |n|=1024 бит, то длины множителей |р|= |q|

Mp≡С dmod p≡С d mod p-1mod p

Mq≡С dmod q≡С d mod q-1mod q

M ≡ Mp mod p

M ≡ Mq mod q

По китайской теореме об остатках

возведения в степень по mod дл. 512 бит c

Одно возведение в степень по mod дл. 1024 бит c показателем 1024 бит

t

t

не нужны большие вычислительные ресурсы.
Распространяют открытые ключи открыто.
Перехват

 Асимметричные алгоритмы очень медленные

При передаче ключа он может быть перехвачен мошенником

производительность симметричных шифров:
данные шифруются с помощью симметричного шифра;

Сk – RSA, Eоткр.(k)

Сm – AES, Ek(m)

Числовая упаковка сообщения