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

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


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

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

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

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

Презентация на тему Криптосистемы с открытым ключем

Содержание

Хронология развития систем ЭЦП1976 г. – открытие М. Хэлменом и У. Диффи асимметричных криптографических систем;1978 г. – Р. Райвест, А. Шамир, Л. Адельман – предложили первую систему ЭЦП, основанную на задаче
Лекция Криптосистемы с открытым ключемЛектор: профессор Яковлев В.А. Хронология развития систем ЭЦП1976 г. – открытие М. Хэлменом и У. Диффи Односторонняя функцияПусть X и Y дискретные множества. Функция y=f(x), гдеx X , Пример односторонней функции функцииПусть p=7, a=3. Проверим, что  a примитивный элемент Оценки сложности вычислений прямой и обратной функцийПусть Односторонняя функция с потайным ходомЭто не просто ОФ, обращение которой невозможно, она Общий принцип построения криптосиcтемы с открытым ключемА - генерирует паруключей:SK(A) - секретный Требования к системам с открытым ключем1. Вычисление пары ключей PK, SK должно Система шифрования Эль-ГамаляПусть p -простое число; a - примитивный элемент.Генерирование пары открытых Система шифрования Эль-ГамаляРасшифрование сообщения.Корр.А вычисляет c1x (modp) = akx (modp) ,Затем находитc2akx Стойкость системы Эль-Гамаля1. Раскрытие секретного ключа эквивалентно решению задачи дискретного логарифмирования.2. Нахождение Пример системы Эль-Гамаляp=11, a=4, a- примитивный элемент GF(2p)Пусть x=3 – закрытый ключy=43(mod11)=64(mod11)=9 Система РША (1978г.)Генерирование ключей.Случайно выбираются два простых числа p и q. Находится Доказательство обратимости операции дешифрования операции шифрованияПокажем, что Ed(modN) =(me)d(modN) =mПо т. Эйлера Пример системы РШАp=3, q=11 N=33 Генерирование ключейe=7, НОД(7,20)=1d=7-1(mod20) = 3Шифрование m=6 Оценки стойкости системы РША  1. Нахождение чисел p и q по Алгоритм формирования ключей на основе однонаправленных функций  (алгоритм Диффи-Хеллмана) Гибридные системы шифрования
Слайды презентации

Слайд 2 Хронология развития систем ЭЦП
1976 г. – открытие М.

Хронология развития систем ЭЦП1976 г. – открытие М. Хэлменом и У.

Хэлменом и У. Диффи асимметричных

криптографических систем;
1978 г. – Р. Райвест, А. Шамир, Л. Адельман – предложили первую систему ЭЦП, основанную на задаче факторизации большого числа;
1985 г. – Эль Гамаль предложил систему ЭЦП, основанную на задаче логарифмирования в поле чисел из р элементов;
1991 г.- Международный стандарт ЭЦП ISO/IEC 9796 (вариант РША);
1994 г. – Стандарт США FIPS 186 (вариант подписи Эль Гамаля);
1994 г. – ГОСТ Р 34.10-95 (вариант подписи Эль Гамаля);
2000 г. – Стандарт США FIPS 186 – 2;
2001 г. – ГОСТ Р 34.10-01 (ЭЦП на основе математического аппарата эллиптических кривых).

Слайд 3 Односторонняя функция
Пусть X и Y дискретные множества. Функция

Односторонняя функцияПусть X и Y дискретные множества. Функция y=f(x), гдеx X

y=f(x), где
x X , y  Y называется односторонней

(однонаправленной),
если y легко вычисляется по любому x, а обратная функция x=f-1(y) является трудно вычислимой.

Пример ОФ.
y=ax(modp), где p- простое число, x - целое число,
a -примитивный элемент поля Галуа GF(p). То есть a такое число, что все его степени ai(modp), i= 1,2…p-1,
принимают все значения в множестве чисел от 1 до p-1.


Слайд 4 Пример односторонней функции функции
Пусть p=7, a=3.
Проверим, что

Пример односторонней функции функцииПусть p=7, a=3. Проверим, что a примитивный элемент

a примитивный элемент -
a1 =3(mod7), a2 =2(mod7),

a3 =6(mod7), a4 =4(mod7), a5 =5(mod7), a6 =1(mod7).
Если x=4, то y=34(mod7)=4.

Сложность нахождения функции возведения в степень Nв=O(2logp).
Обратная функция x=logay (функция дискретного логарифмирования) трудно вычислима.
Если p - сильно простое число, то Nлог=O((p)1/2).

Слайд 5 Оценки сложности вычислений прямой и обратной функций
Пусть

Оценки сложности вычислений прямой и обратной функцийПусть

1000

разрядное двоичное число, тогда для решения задачи возведения в степень числа х по modp потребуется примерно 2000 = 2*103 операций , а для нахождения логарифма такого числа потребуется примерно
p1/2=2500~10170 операций, что вычислительно невозможно осуществить ни за какое реально обозримое время.


Слайд 6 Односторонняя функция с потайным ходом
Это не просто ОФ,

Односторонняя функция с потайным ходомЭто не просто ОФ, обращение которой невозможно,

обращение которой невозможно, она содержит потайной ход (trapdoor), который

позволяет вычислять обратную функцию, если известен секретный параметр - ключ.

y=f(x,s) – легковычислима;
x=f-1(y) – трудновычислима;
x= f-1(y,s)- легковычислима.


Слайд 7 Общий принцип построения криптосиcтемы с открытым ключем
А -

Общий принцип построения криптосиcтемы с открытым ключемА - генерирует паруключей:SK(A) -

генерирует пару
ключей:
SK(A) - секретный ключ,
PK(A) - открытый ключ.
B -

генерирует пару
ключей:
SK(B) - секретный ключ,
PK(B) - открытый ключ.

Открытые ключи помещаются
в общедоступную базу
PK(A) , PK(B)

Шифрование.
А выбирает открытый ключ PK(B)
Осуществляет шифрование
EA=f(MA,PK(B))

Расшифрование.
MA=g(EA,SK(B))

EA

PK(A)

PK(B)

PK(B)


Слайд 8 Требования к системам с открытым ключем
1. Вычисление пары

Требования к системам с открытым ключем1. Вычисление пары ключей PK, SK

ключей PK, SK должно быть просто
решаемой задачей;
2. При

известном ключе шифрования PK вычисление криптограммы
E=f(M,PK) должно быть простым;
3. При известном ключе расшифрования SK восстанавливает сообщение
M=g(E,SK) должно быть простым;
4. При известном ключе шифрования PK вычисление ключа
расшифрования SK должно быть сложным;
5. При известном ключе шифрования PK, но неизвестном ключе
расшифрования SK вычисление М по известной криптограмме E
должно быть весьма сложным.


Слайд 9 Система шифрования Эль-Гамаля
Пусть p -простое число; a -

Система шифрования Эль-ГамаляПусть p -простое число; a - примитивный элемент.Генерирование пары

примитивный элемент.
Генерирование пары открытых ключей
A - генерирует число xA,

вычисляет открытый ключ
yA=ax (modp). (SK= xA , PK= yA).

yA передается корр. B.

Шифрование сообщения
Пусть корр. B хочет послать корр.А сообщение mГенерирует случайное число kФормирует криптограмму E=(c1c2)
c1=ak(modp), c2=m(yA-1)k .
Отправляет E корр. А.

Корреспондент А

Корреспондент В


Слайд 10 Система шифрования Эль-Гамаля
Расшифрование сообщения.
Корр.А вычисляет c1x (modp) =

Система шифрования Эль-ГамаляРасшифрование сообщения.Корр.А вычисляет c1x (modp) = akx (modp) ,Затем

akx (modp) ,
Затем находит
c2akx (modp)= m(yA-1)k akx (modp)= ma-xk

akx (modp)=m

Замечание.
Как найти yA-1 ?

yAp-2 (modp)= yAp-1 (modp)  yA-1 (modp) = yA-1 (modp)


Слайд 11 Стойкость системы Эль-Гамаля
1. Раскрытие секретного ключа эквивалентно решению

Стойкость системы Эль-Гамаля1. Раскрытие секретного ключа эквивалентно решению задачи дискретного логарифмирования.2.

задачи
дискретного логарифмирования.
2. Нахождение m без знания ключа возможно,

если случайное число
k используется дважды и в одном случае нарушитель знает
открытый текст
c2= m(yA-1)k (modp), c’2= m’(yA-1)k (modp)
Зная c2, c’2 и m несложно найти m’ m’= c’2mc-12 (modp)

k должно меняться случайным образом при шифровании
нового сообщения.

Слайд 12 Пример системы Эль-Гамаля
p=11, a=4, a- примитивный элемент GF(2p)
Пусть

Пример системы Эль-Гамаляp=11, a=4, a- примитивный элемент GF(2p)Пусть x=3 – закрытый

x=3 – закрытый ключ
y=43(mod11)=64(mod11)=9 открытый ключ
Шифрование сообщения m=6
Генерирование СЧ

k=4
Вычисление:
С1=ak(modp)=44(mod11)=256(mod11)=3
y-1=yp-2(modp)= 99(mod11)=929292929(mod11)=
4*4*4*4*9(mod11)=5*5*9(mod11)=5
C2=my-1k(modp)=6*54(mod11)=6*3*3(mod11)=10

C1,C2

C1,C2

Расшифрование

C1x (modp)=33(mod11)=5
C2*C1x (modp)=10*5 (mod11)=50(mod11)=6


Слайд 13 Система РША (1978г.)
Генерирование ключей.
Случайно выбираются два простых числа

Система РША (1978г.)Генерирование ключей.Случайно выбираются два простых числа p и q.

p и q. Находится
модуль N=pq. Находится функция Эйлера

(N)= (p-1)(q-1).
Выбираем число e такое, что НОД(e, (N))=1.
Находим d, как обратный элемент к e, de=1(mod (N)).
Объявляем d=SK, (e,N)=PK. PK сообщается всем
корреспондентам.

Шифрование.
Корр. А передает зашифрованное сообщение корр.В
(использует открытый ключ корр. В)
E=me(modN)

Расшифрование.
Корр. В расшифровывает принятую криптограмму от
корр.А,используя свой секретный ключ.
m=Ed(modN)


Слайд 14 Доказательство обратимости операции дешифрования операции шифрования
Покажем, что Ed(modN)

Доказательство обратимости операции дешифрования операции шифрованияПокажем, что Ed(modN) =(me)d(modN) =mПо т.

=(me)d(modN) =m
По т. Эйлера m(N)1(modN) для любого m

взаимно простого с N.
Умножая обе части сравнения на m, получаем сравнение
m(N)+1 m(modN) справедливое уже для любого целого m.
Перепишем соотношение ed1(mod(N)) в виде ed=1+k(N)
для некоторого целого k.
Тогда Ed=(me)d=m1+k(N)= m1+(N) m(k-1)(N)=
=m m(k-1)(N)= m1+(k-1)(N) =m1+(N) m(k-2)(N)=
…. = m1+(N) =m
Что и требовалось доказать.



Слайд 15 Пример системы РША
p=3, q=11 N=33
Генерирование ключей
e=7, НОД(7,20)=1
d=7-1(mod20)

Пример системы РШАp=3, q=11 N=33 Генерирование ключейe=7, НОД(7,20)=1d=7-1(mod20) = 3Шифрование m=6 E=me(modN)= 67(mod33)=62 62 62 61(mod33)==3*3*3*3*2=30РасшифрованиеEd(modN)=303(mod33)=900*30(mod33)=9*30(mod33)=6

= 3
Шифрование
m=6 E=me(modN)= 67(mod33)=62 62 62 61(mod33)=
=3*3*3*3*2=30
Расшифрование
Ed(modN)=303(mod33)=900*30(mod33)=9*30(mod33)=6


Слайд 16 Оценки стойкости системы РША
1. Нахождение чисел

Оценки стойкости системы РША 1. Нахождение чисел p и q по

p и q по известному модулю N. Задача
факторизации

имеет сложность O((N)1/2).
2. Будем последовательно возводить полученную криптограмму в
степень равную значению открытого ключа т.е. (((((Ee)e)…..)e .
Если при некотором шаге окажется, что Ei=E , то это означает,
что Ei-1=m. Доказывается, что данная атака требует непереборно
большого числа шагов.
3. Поиск слабых ключей, для которых me’ = m , т.е. возведение
в степень не меняет сообщения. Эта атака имеет малую вероятность
успеха, если p и q выбираются среди сильно простых чисел. Сильно
простое число, это число, для которого p-1 не содержит в разложении
маленьких сомножителей, и имеет в разложении хотя бы один
большой сомножитель.
4.


Слайд 17 Алгоритм формирования ключей на основе однонаправленных функций (алгоритм

Алгоритм формирования ключей на основе однонаправленных функций (алгоритм Диффи-Хеллмана)

Диффи-Хеллмана)


  • Имя файла: kriptosistemy-s-otkrytym-klyuchem.pptx
  • Количество просмотров: 86
  • Количество скачиваний: 0