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

Содержание

• 
  Слайд 1
  

  КриптоанализRSA

• 
  Слайд 2
  

  Пути вскрытия RSA Фактори-зация модуля п Вычисление функции φ(п) Расчет закрытой экспоненты d=е-1modφ(n) Дано:п,е, Мemodп Найти:М Задача RSA Полиномиально эквиваленты

• 
  Слайд 3
  

  Пути вскрытия RSA : факторизация п~ вычисление φ(п) п = pq φ(п) =(p -1)(q-1) Как зная pиq, найти φ(n)

• 
  Слайд 4
  

  L-нотация для обозначения сложности алгоритмов факторизации чисел e (c+О(1))(log2N)ε(log2log2N)1-ε LN (ε,c) = ε=1 ЭКСПОНЕНЦИАЛЬНЫЙ ПОЛИНОМИАЛЬНЫЙ ε=0 Эффективны Не эффективны 0

• 
  Слайд 5
  

  Наиболее эффективные алгоритмы факторизации Квадратичное решето Факторизация на эллиптических кривых Общий метод решета числового поля e (1+О(1))(log2N·log2log2N)1/2 LN (,1) = e (1+О(1))(2log2р·log2log2p)1/2 LN ()= р– наименьшиймножитель числаN =e (1,92+О(1))(log2N 1/3·log2log2N)2/3 LN ( )=

• 
  Слайд 6
  

  Последние результаты факторизации больших чисел Для RSA квадратичное решето лучше, чем эллиптические кривые Квадратичное решето работает для чисел не больше 10110с простым делителем, меньшим Числовое поле быстрее для очень больших чисел решето числового поля

• 
  Слайд 7
  

  Атака на RSA на основе общей экспоненты С1=M3modп1 С2=M3modп2 С3=M3modп3 K1 K2 K3 Если модули– взаимно простые, то по китайской тереме от остатках можно комбинировать и отсюда найти С=M3modп1п2п3 M3

• 
  Слайд 8
  

  С2=Mе2modп K1 K2 С1=Mе1modп t1=e1-1mode2 t1e1=t2e2+1, t2ЄZ M = C1t1C2-t2mod n Атака на RSA на основе общего модуля Почему? t2= (t1e1-1)/e2

• 
  Слайд 9
  

  Атака на RSA : «встреча посередине» Мультипликативность: С1≡M1еmodп С2≡M2еmodп С≡(M1M2)е=M1еM2еmodп=С1С2 Каким будет шифротекст открытого текста M=M1M2 ? можно построить атаку Пусть известно, что M=M1M2

• 
  Слайд 10
  

  Атака на RSA : «встреча посередине» С·(1-е)modп С·(2-е)modп С·(3-е)modп . . . . . . С ·(2L/2)-e 1еmodп 2еmodп 3еmodп . . . . . . (2L/2)еmodп С·i-еmodп ≡ j emodn M= i· j

• 
  Слайд 11
  

  Циклическая атака на RSA (бесключевое чтение) Се≡С1modп С1е≡С2modп С2е≡С3modп … Сk-2е≡Сk-1modп Сk-1е≡Сkmodп≡ C Атака успешна, если порядок kоткрытой експонентыe мал (k – наименьшее число, для которого еk≡1(modφ(n)); НОД(e, φ(n))=1) М = Сk-1

• 
  Слайд 12
  

  Атака Винера: математическое вступление ЦЕПНЫЕ (НЕПРЕРЫВНЫЕ) ДРОБИ Любое действительное число х можно представить цепной дробью а0Z; ∩ а1, а2,…N ∩ =a0+ 1 … a1 + 1 a2 + 1 a3 + x=[a0; a1, a2,…]

• 
  Слайд 13
  

  Как найти элементы цепной дроби для числа х ? . . . -целая часть числа х Атака Винера: математическое вступление а2= ; 1 x1 x x0 = x – a0; а1= ; 1 x0 x1= – a1; 1 x0 x2= – a2; 1 x1 аi= ; 1 xi – 1 xi = – ai; 1 xi – 1

• 
  Слайд 14
  

  Пример. Найти разложение в цепную дробь числа Решение. Атака Винера: математическое вступление а0= = = 0; x0 34 99 x0 = x – a0= 34 99 x= 34 99 а1= = = 2 ; 1 x0 99 34 x1= – a1=– 2 = 1 x0 99 34 31 34 а2= = = 1 ; 1 x1 34 31 x2= – a2=– 1 = 1 x1 34 31 3 31 а3= = = 10 ; 1 x2 31 3 x3= – a3=– 10 = 1 x2 31 3 1 3 а4= = = 3 1 x3 3 1

• 
  Слайд 15
  

  Атака Винера: математическое вступление =0+ 1 2 + 1 1 + 1 10 + 1 3 =[0; 2, 1, 10, 3] x= 34 99

• 
  Слайд 16
  

  Атака Винера: математическое вступление і-ой подходящей дробью для цепной дроби называют конечную цепную дробь pi qi =[a0; a1, a2,…,ai] pi qi x=[a0; a1, a2,…] Рекуррентные формулы для вычисления подходящих дробей для цепной дроби pi qi =[a0; a1, a2,…,ai] : p–1= 1; p0= a0; q0= 1 q–1= 0; aipi –1+ pi –2 = pi qi aiqi –1+ qi –2 ; i= 1,2,…

• 
  Слайд 17
  

  Атака Винера: математическое вступление Пример. Найти подходящие дроби для цепной дроби Решение. [0; 2, 1, 10, 3] =[0; 2, 1, 10, 3] 34 99 a0a1a2a3 a4 p–1= 1; p0= 0; q0= 1 q–1= 0; a1p0+ p–1 = p1 q1 a1q0+ q–1 = =; 2·0+1 2·1+0 1 2 p1= 1; q1= 2; a2p1+ p0 = p2 q2 a2q1+ q0 = =; 1·1+0 1·2+1 1 3 p2= 1; q2= 3;

• 
  Слайд 18
  

  Атака Винера: математическое вступление Подходящие дроби: a3p2+ p1 = p3 q3 a3q2+ q1 = =; 10·1+1 10·3+2 11 32 p3= 11; q3= 32; a4p3+ p2 = p4 q4 a4q3+ q2 = =; 3·11+1 3·32+2 34 99 p4= 34; q4= 99 =; p1 q1 1 2 =; p2 q2 1 3 =; p3 q3 11 32 =; p4 q4 34 99

• 
  Слайд 19
  

  Атака Винера: математическое вступление Если несократимая дробь удовлетворяет неравенству: то дробь – одна из подходящих дробей в разложении числа х в цепную дробь. p q p q x – ≤ 1 2q2 p q

• 
  Слайд 20
  

  Атака Винера М. Винерпоказал, чтокогдасекретнаяэкспонента то дробьудовдетворяетнеравенству это классическаяаппроксимация с помощьюцепныхдробей; число дробей , где, не большеlog n для некоторогоkвыполнится . Тогда так какНОД(k, d)=1, то p = k, q = d e n k d – ≤ 1 2d 2 e n k d d

• 
  Слайд 21
  

  Атака Винера: сценарий Разложить дробь в цепную дробь Найти все подходящие дроби для дроби Среди подходящих дробей p/q найти ту, для которой eq-1делится нацело на р. Тогда p=k, q=d.

• 
  Слайд 22
  

  Атака Винера: противодействие Для противодействия атаке надо, чтобы секретная экспонента была не меньше, чем Например, если  модуль  имеет размер 1024 бит, необходимо чтобы длина секретной экспоненты была не менее 256 бит. п0,292

• 
  Слайд 23
  

  Использование китайской теоремы об остатках для ускорения расшифрования Если длина модуля |n|=1024бит, то длина секретной экспоненты |d|~1024 бит M=С dmodп Секретный ключ – экспонента d

• 
  Слайд 24
  

  Зависимость времени вычисления значения у = хe(mod n)от длины модуля Каждое удвоение длины ключа RSA увеличивает время расшифрования в 6 – 7 раз 512 768 1536 2048 2816 3328 4096 1000 800 600 400 200 0 Длина модуля RSA в битах Время расшифрования (миллисекунды) Pentium, 2 ГГц http://security.stackexchange.com/questions/1833/encryption-decryption-time Нужен алгоритм расшифрования с минимальным числом операций

• 
  Слайд 25
  

  Использование китайской теоремы об остатках для ускорения расшифрования Если длина модуля |n|=1024 бит, то длины множителей |р|=|q| = 512 бит Mp≡С dmodp≡С dmod p-1modp Mq≡С dmodq≡С dmod q-1modq M ≡ Mpmodp M ≡ Mqmodq По китайской теореме об остатках Владелец секретного ключа знает pиq

• 
  Слайд 26
  

  Использование китайской теоремы об остатках для ускорения расшифрования Два возведения в степень по mod дл. 512 бит c показателем 512 бит Одно возведение в степень по mod дл. 1024 бит c показателем 1024 бит t t

• 
  Слайд 27
  

  Симметричные против асимметричных криптосистем Стойкие, работают очень быстро. Им не нужны большие вычислительные ресурсы. Распространяют открытые ключи открыто. Перехват открытых ключей – бесполезен.  Асимметричные алгоритмы очень медленные При передаче ключа он может быть перехвачен мошенником

• 
  Слайд 28
  

  Гибридные криптосистемы

• 
  Слайд 29
  

  Гибридные криптосистемы Совмещают преимущества криптосистем с открытым ключом и производительность симметричных шифров: данные шифруются с помощью симметричного шифра; асимметричный алгоритм шифрует только ключ симметричного шифра Сk Сm Инкапсуляция сообщения Инкапсуляция ключа Сk – RSA, Eоткр.(k) Сm – AES, Ek(m) Числовая упаковка сообщения

• 
  Слайд 30
  

  Гибридные криптосистемы Шифрование сообщения Расшифрование сообщения Сеансовый ключ Зашифро-ванный ключ Сеансовый ключ Шифрование ключа Расшифрование ключа Секретный ключ Боба Открытый ключ Боба