Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

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

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

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

Содержание

Пути вскрытия RSAФактори-зациямодуля пВычисление функции φ(п)Расчет закрытой экспонентыd=е-1modφ(n)Полиномиально эквиваленты
Криптоанализ RSA Пути вскрытия RSAФактори-зациямодуля пВычисление  функции   φ(п)Расчет закрытой экспонентыd=е-1modφ(n)Полиномиально эквиваленты Пути вскрытия RSA : факторизация п ~ вычисление φ(п)п = pq φ(п) =( p -1)(q-1) L-нотация для обозначения сложности алгоритмов факторизации чисел ε =1ЭКСПОНЕНЦИАЛЬНЫЙПОЛИНОМИАЛЬНЫЙε =0Эффективны Не эффективны 0 Наиболее эффективные алгоритмы факторизацииКвадратичное    решетоФакторизация Последние результаты факторизации больших чиселрешето числового поля Атака на RSA на основе общей экспонентыЕсли модули – взаимно простые, то t1=e1 -1mod e2 t1e1= t2e2+1,  t2Є Z  M = C1t1 Атака на RSA : «встреча посередине»Мультипликативность:С1≡M1 еmod пС2≡M2 еmod пС≡(M1M2)е=M1еM2еmod п=С1С2можно построить атакуС·M 1-e=M2еmod п Атака на RSA : «встреча посередине»С·(1-е)mod пС·(2-е)mod пС·(3-е)mod п. . .. . Циклическая атака на RSA (бесключевое чтение)Се≡С1mod пС1е≡С2mod пС2е≡С3mod п…Сk-2е≡Сk-1mod пСk-1е≡Сkmod п ≡ Атака Винера: математическое Как найти элементы цепной дроби для числа х ?. . . -целая Пример. Найти разложение в цепную дробь Атака Винера: математическое Атака Винера: математическое Атака Винера: математическое Атака Винера: математическое Атака Винера: математическое Атака ВинераМ. Винер показал, что когда секретная экспонента Атака Винера: сценарийНайти все подходящие дроби для дроби Среди подходящих дробей p/q Атака Винера: противодействиеДля противодействия атаке надо, чтобы секретная экспонента была не меньше, Использование китайской теоремы об остатках для ускорения расшифрования Если длина модуля |n|=1024 Зависимость времени вычисления значения у = хe(mod n) от длины модуля Каждое Использование китайской теоремы об остатках для ускорения расшифрованияЕсли длина модуля |n|=1024 бит, Использование китайской теоремы об остатках для ускорения расшифрованияДва возведения в степень по Симметричные против асимметричных криптосистемСтойкие, работают очень быстро. Им не нужны большие вычислительные Гибридные криптосистемы Гибридные криптосистемыСовмещают преимущества криптосистем с открытым ключом и производительность симметричных шифров: данные Гибридные криптосистемыРасшифрованиесообщенияШифрованиеключаРасшифрованиеключа
Слайды презентации

Слайд 2 Пути вскрытия RSA
Фактори-зация
модуля
п
Вычисление
функции

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

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


Слайд 3 Пути вскрытия RSA : факторизация п ~ вычисление

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

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


Слайд 4 L-нотация для обозначения сложности алгоритмов факторизации чисел
ε

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

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

тем алгоритм более эффективен

Слайд 5 Наиболее эффективные алгоритмы факторизации
Квадратичное
решето
Факторизация

Наиболее эффективные алгоритмы факторизацииКвадратичное  решетоФакторизация   на эллиптических

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

кривых

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

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


Слайд 6 Последние результаты факторизации больших чисел
решето числового поля

Последние результаты факторизации больших чиселрешето числового поля

Слайд 7 Атака на RSA на основе общей экспоненты
Если модули

Атака на RSA на основе общей экспонентыЕсли модули – взаимно простые,

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

можно комбинировать

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

M 3 < п1п2п3

Т.к.


Слайд 8 t1=e1 -1mod e2
t1e1= t2e2+1, t2Є Z

t1=e1 -1mod e2 t1e1= t2e2+1, t2Є Z M = C1t1 C2


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

RSA на основе общего модуля

Почему?

t2= (t1e1 -1)/e2


Слайд 9 Атака на RSA : «встреча посередине»
Мультипликативность:
С1≡M1 еmod п
С2≡M2

Атака на RSA : «встреча посередине»Мультипликативность:С1≡M1 еmod пС2≡M2 еmod пС≡(M1M2)е=M1еM2еmod п=С1С2можно построить атакуС·M 1-e=M2еmod п

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


Слайд 10 Атака на RSA : «встреча посередине»
С·(1-е)mod п
С·(2-е)mod п
С·(3-е)mod

Атака на RSA : «встреча посередине»С·(1-е)mod пС·(2-е)mod пС·(3-е)mod п. . ..

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

. .

. . .

(2L/2 )еmod п

С·i -еmod п


j emod n

M= i · j


Слайд 11 Циклическая атака на RSA (бесключевое чтение)
Се≡С1mod п
С1е≡С2mod п
С2е≡С3mod

Циклическая атака на RSA (бесключевое чтение)Се≡С1mod пС1е≡С2mod пС2е≡С3mod п…Сk-2е≡Сk-1mod пСk-1е≡Сkmod п

п

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

k открытой експоненты e мал (k – наименьшее число, для которого еk≡1(modφ(n)); НОД(e, φ(n))=1)

М = Сk-1


Слайд 12 Атака Винера: математическое

Атака Винера: математическое

вступление

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

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

x = [a0; a1, a2,…]


Слайд 13 Как найти элементы цепной дроби для числа х

Как найти элементы цепной дроби для числа х ?. . .

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

вступление

x0 = x – a0 ;

xi – 1


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

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

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

математическое
вступление

Слайд 15 Атака Винера: математическое

Атака Винера: математическое         вступление

вступление

Слайд 16 Атака Винера: математическое

Атака Винера: математическое

вступление

x = [a0; a1, a2,…]

p–1 = 1;

p0 = a0 ;

q0 = 1

q–1 = 0;

; i = 1,2,…


Слайд 17 Атака Винера: математическое

Атака Винера: математическое

вступление

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

Решение.

[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;


Слайд 18 Атака Винера: математическое

Атака Винера: математическое

вступление

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

p3 = 11;

q3 = 32;

p4 = 34;

q4 = 99


Слайд 19 Атака Винера: математическое

Атака Винера: математическое

вступление

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

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


Слайд 20 Атака Винера
М. Винер показал, что когда секретная экспонента

Атака ВинераМ. Винер показал, что когда секретная экспонента



то

дробь удовдетворяет неравенству

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

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

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

d < n


Слайд 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)

Зависимость времени вычисления значения у = хe(mod n) от длины модуля

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

время расшифрования в 6 – 7 раз

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

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

Pentium, 2 ГГц

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

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


Слайд 25 Использование китайской теоремы об остатках для ускорения расшифрования
Если

Использование китайской теоремы об остатках для ускорения расшифрованияЕсли длина модуля |n|=1024

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

= 512 бит

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

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

M ≡ Mp mod p

M ≡ Mq mod q

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


Слайд 26 Использование китайской теоремы об остатках для ускорения расшифрования
Два

Использование китайской теоремы об остатках для ускорения расшифрованияДва возведения в степень

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

показателем 512 бит

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

t

t


Слайд 27 Симметричные против асимметричных криптосистем
Стойкие, работают очень быстро. Им

Симметричные против асимметричных криптосистемСтойкие, работают очень быстро. Им не нужны большие

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

открытых ключей – бесполезен.

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

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


Слайд 28 Гибридные криптосистемы

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

Слайд 29 Гибридные криптосистемы
Совмещают преимущества криптосистем с открытым ключом и

Гибридные криптосистемыСовмещают преимущества криптосистем с открытым ключом и производительность симметричных шифров:

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

асимметричный алгоритм шифрует только ключ симметричного шифра

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

Сm – AES, Ek(m)

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


  • Имя файла: kriptoanaliz-rsa.pptx
  • Количество просмотров: 170
  • Количество скачиваний: 0