Разделы презентаций


Лекция5.ppt презентация, доклад

Содержание

Покажем, что функция f--1z ( y) является обратной к функции fz (x) так как согласно ( 10) de= Ф(n)Q+1 для некоторого Q. Уязвимость протокола РША (RSA) имеет три аспекта:1.Имеются ограничения на

Слайды и текст этой презентации

Слайд 1
Последний необходимый нам факт из теории чисел: для числа е,

удовлетворяющего условиям 0

число d такое, что 0de=1 (modФ(n)) (10) Однонаправленная функция РША с потайным ходом определяется как дискретное возведение значения х в степень ключа е
fz (x): y=xe(mod n) (11)
где x есть положительное целое число, не превосходящее n (0<еf-1z ( y): x=yd(mod n) (12)
где значение d есть единственное положительное целое, меньшее Ф(п) и удовлетворяющее условию
de=1(mod Ф(n))



Последний необходимый нам факт из теории чисел: для числа е, удовлетворяющего условиям 0

Слайд 2Покажем, что функция f--1z ( y) является обратной к функции

fz (x)




так как согласно ( 10) de= Ф(n)Q+1 для

некоторого Q.
Уязвимость протокола РША (RSA) имеет три аспекта:
1.Имеются ограничения на выбор р и q. Как и в протоколе Диффи-Хеллмана слабым местом разложения целых чисел на простые множители являются гладкие простые числа n. Один из наиболее эффективных алгоритмов факторизации – (р-1) алгоритм факторизации Полларда. Пусть р-неизвестный простой множитель числа n и наибольший простой множитель числа (р –1) ограничен величиной В=Poly(k), где k=|n|=log n, а Poly(k) – некоторый полином небольшой степени, зависящий от k. Число В называется границей гладкости числа (р-1). Сконструируем число
А=Пr [log n/log r] , где [log n/log r] –целая часть дроби log n/log r
простые числа r
Покажем, что функция f--1z ( y) является обратной к функции fz (x) так как согласно ( 10)

Слайд 3Очевидно, что такое число А делится нацело на р-1. Поэтому

из малой теоремы Ферма следует, что аА ≡1(mod p) для

любого целого числа а, удовлетворяющего условию НОД(а, р)=1.Если существует простой множитель q числа n, не равный множителю р и такой, что аА≠ 1(mod q), то существует целое число l, не кратное числу q, такое, что аА-1(mod n)=lp. Следовательно, число НОД(аА-1(mod n), n) должно быть собственным простым множителем числа n. Если n=pq, это число должно равняться числу р. Размер в битах числа А полиномиально зависит от числа k. Оценка длины числа А делается, исходя из теоремы о простом числе, по которой существует не более, чем В/log B простых чисел, которые меньше, чем число В.
Отсюда Ат.е. |А|=log A
Очевидно, что такое число А делится нацело на р-1. Поэтому из малой теоремы Ферма следует, что аА

Слайд 4неполиномиально зависела от |n|=log n. Например, большие простые числа р’и

q’, такие, что p=2p’+1 и q=2q’+1 тоже простые. Такие простые

числа называются безопасными простыми числами, а модули n алгоритма РША, имеющие два безопасных простых множителя, называются безопасными.
2. Атака «встреча посередине» при пересылке коротких сообщений. Небольшие исходные сообщения m(m1 * m2)e ≡m1e * m2e ≡c1 * c2(mod n) ). Текст, зашифрованный алгоритмом РША, трудно разложить на простые множители из-за перемешивающего свойства функции шифрования, означающего, что размер зашифрованного текста равен размеру модуля n.
неполиномиально зависела от |n|=log n. Например, большие простые числа р’и q’, такие, что p=2p’+1 и q=2q’+1 тоже

Слайд 53.Уязвимость для атаки на основе подобранного открытого текста.
1.Во многих криптографических

протоколах стандартный режим работы – инструкция «отклик-отзыв», по которой получатель

расшифровывает полученное сообщение и отсылает результат расшифровки отправителю, т.е. допускается частичный контроль блока расшифровки со стороны пользователей.
2. Криптоалгоритм должен быть таким, чтобы расшифрованный текст имеющий вид случайного набора цифр, не позволил атакующему извлечь полезную информацию.
В реальных версиях РША эти недостатки исправлены.
3.Уязвимость для атаки на основе подобранного открытого текста.1.Во многих криптографических протоколах стандартный режим работы – инструкция «отклик-отзыв»,

Слайд 6Шифрование сообщений.
Рассмотрим использование однонаправленной функции РША с потайным ходом

для шифрования сообщений, причем отправителю сообщений для этого не надо

знать секретной ключевой информации.
Выберем в качестве информации потайного хода z = {p,q,d}, а значения е и n открыто сообщим корреспондентам сети. Отправитель секретного сообщения x шифрует его с использованием несекретного ключа шифрования е согласно выражению (11). Получатель криптограммы у дешифрует сообщение x с использованием секретного ключа дешифрования d согласно выражению (12). Нарушитель, которому известен несекретный ключ шифрования, но неизвестна информация потайного хода z, не способен читать передаваемые сообщения..
Данный способ шифрования очень удобен тем, что не требует доставки секретной ключевой информации отправителям секретных сообщений.
Шифрование сообщений. Рассмотрим использование однонаправленной функции РША с потайным ходом для шифрования сообщений, причем отправителю сообщений для

Слайд 7Цифровая подпись сообщений
Рассмотрим использование однонаправленной функции РША с потайным

ходом для обеспечения подлинности сообщений, причем получателям сообщений для этого

не надо знать секретной ключевой информации.
Выберем качестве информации потайного хода z={p,q,e} }, а значения d и n открыто сообщим всем корреспондентам-получателям сообщений сети.
Отправитель заверяемого сообщения х формирует цифровую подпись у данного сообщения с использованием секретного ключа е формирования цифровой подписи общения согласно выражению (11).
Отправитель по каналу связи передает получателю само сообщение и его цифровую подпись. Получатель возводит полученное значение у цифровой подписи сообщения х в степень .несекретного ключа d проверки цифровой подписи отправителя согласно выражению (12).
Цифровая подпись сообщений Рассмотрим использование однонаправленной функции РША с потайным ходом для обеспечения подлинности сообщений, причем получателям

Слайд 8Если восстановленное из цифровой подписи сообщение совпало с принятым значением

сообщения, то принятое сообщение признается подлинным
Нарушитель, которому известен несекретный

ключ проверки цифровой подписи отправителя, но неизвестна информация потайного хода z, не способен сформировать цифровую подпись произвольного сообщения, фальшивость которого не будет обнаружена получателем. Данный способ обеспечения подлинности информации; удобен тем, что проверка подлинности сообщений не требует доставки секретной ключевой информации.
Законные пользователи, знающие информацию потайного хода z, способны вычислительно просто определить значения прямой fz(x) и обратной f-1z(y) функций.
Для нарушителя, которому неизвестна информация потайного хода z, определение обратной функции f-1z(y) для случая шифрования или значения прямой функции fz(x) для случая обеспечения подлинности сообщений должны быть вычислительно нереализуемыми.
Если восстановленное из цифровой подписи сообщение совпало с принятым значением сообщения, то принятое  сообщение признается подлиннымНарушитель,

Слайд 9Рассмотрим условия, при которых обеспечивается безопасность использовать однонаправленной функции РША

с потайным ходом. В общем случае нарушителю известно лишь n

и е (или d). Если он способен разложить число n на множители p и q, то по известному несекретному ключу он легко вычислит секретный ключ и будет иметь полную информацию о потайном ходе z. Исследования однонаправленной функции РША с потайным ходом показали, что практически все попытки противостоящей стороны получить информацию о потайном ходе эквивалентны разложению n= p q на множители. Поэтому в последние десятилетия интенсивно исследовались методы разложения составного числа на множители. В математике такая задача называется задачей факторизации составного числа. Неизвестны доказательства на принадлежность данной задачи ни к классу Р, ни к классу NР сложных задач, однако общепризнанно, что она весьма сложна. Наилучший известный алгоритм факторизации составного числа имеет субэкспоненци-альную вычислительную сложность порядка


Рассмотрим условия, при которых обеспечивается безопасность использовать однонаправленной функции РША с потайным ходом. В общем случае нарушителю

Слайд 10где A - некоторая положительная константа, большая 1, n =

p q
За последние годы в области разработки эффективных методов факторизации

достигнуты существенные успехи, поэтому- для обеспечения требуемой безопасности применения однонаправленной функции РША с потайным ходом должны использоваться числа р и q размерностью многие сотни и даже тысячи бит. Известны примеры, как, объединив через глобальную сеть связи вычислительный ресурс сотен и тысяч ЭВМ, удается разложить на множители числа, состоящие из 130 десятичных знаков ( бит). Отметим, что сложность обращения рассматриваемой однонаправленной функции существенно уменьшается при использовании чисел p и q, не являющихся простыми. Также нежелательно использовать простые числа специального вида, например числа Мерсенна вида 2k-1, где k - натуральное число, для которых известны быстрые (полиномиальной сложности) алгоритмы факторизации.

(14)

где A - некоторая положительная константа, большая 1, n = p qЗа последние годы в области разработки

Слайд 11Однонаправленная функция Эль-Гамаля с потайным ходим
На основе трудности вычисления дискретных

логарифмов в алгебраическом поле можно построить однонаправленную функцию с потайным

ходом.
Поле является более сложной алгебраической структурой по сравнению с группой, над его элементами можно выполнять операции сложения и умножения, а в группе - только сложение или только умножение. Например, рассмотренная ранее однонаправ-ленная функция Диффи и Хеллмана, послужившая основой криптосистемы открытого распространения ключей, использует операции умножения над элементами группы.
В 1985 году Т. Эль-Гамаль предложил криптографическую систему циф­ровой подписи сообщений, которая в настоящее время считается одной из наиболее стойких криптосистем обеспечения подлинности передаваемой и хранимой информации. Рассмотрим принципы построения данной криптосистемы, послужившей основой для отечественного и американского государст­венных стандартов цифровой подписи сообщений
Однонаправленная функция Эль-Гамаля с потайным ходимНа основе трудности вычисления дискретных логарифмов в алгебраическом поле можно построить однонаправленную

Слайд 12На этапе формирования ключевой информации криптосистемы равновероятно выбираются большое простое

число р и число
g (0

что его последовательные степени g0, g1,…,gp-1
в произвольном порядке пробегают все значения от 0 до р - 1. Такое число называется примитивным элементом. Далее формирователь ключа случайным образом выбирает целое число х, удовлетворя-ющее условию 0Число х является ключом формирования цифровой подписи сообщений отправителя и должно храниться корреспондентом-отправителем сообщений в секрете, а значение у сообщается всем как открытый ключ проверки цифровой подписи сообщений отправителя. Так же открыто всем корреспондентам сети с выполнением мер обеспечения их подлинности сообщаются значения параметров криптосистемы p,g и q.
Чтобы заверить цифровой подписью передаваемое сообщение М, двоичное представление которого должно быть меньше значения
р: 0<М<р, (16)
На этапе формирования ключевой информации криптосистемы равновероятно выбираются большое простое число р и число g (0

Слайд 13Отправитель равновероятным недетерминированным образом выбирает случайное число k ( 0

– 1)) так, чтобы числа k и р- 1 не

имели общих делителей, кроме 1, то есть их наибольший общий делитель НОД (k, p-1)=1. (17)
Далее отправитель вычисляет значение первого параметра цифровой подписи сообщения:


(18)

составляет уравнение вида
M=xr + ks mod(p-l), (19)
и решает его относительно второго параметра цифровой подписи сообщения


(20)

где k-1 есть число, обратное к числу k по mod (р - 1).

Отправитель равновероятным недетерминированным образом выбирает случайное число k ( 0

Слайд 14Цифровой подписью сообщения М является пара чисел г и s.

Отправитель сообщения по каналу связи передает получателю само сообщение М

и его цифровую подпись { г, s}. Отметим, что значения х и k сохраняются отправителем сообщения в тайне от всех (после формирования цифровой подписи сообщения использованное значение k целесообразно гарантированно стереть для обеспечения безопасности использования криптосистемы).
На приеме корреспондент-получатель сначала проверяет допустимость принятого значения r^.
Если оно не находится в пределах 0 < r^<р -1, принятое сообщение отвергается как ложное. Если принятое значение s^ не находится в пределах 0 < s^ <р - 1, сообщение также отвергается как ложное. Получатель удостоверяется в подлинности принятого сообщения m^ заверенного принятой подписью {r^ , s^}, и отсутствии в нем искажений тогда и только тогда, когда выполняется равенство:




(21)

Цифровой подписью сообщения М является пара чисел г и s. Отправитель сообщения по каналу связи передает получателю

Слайд 15Рассмотрим пример формирования и проверки цифровой подписи сообще­ния в системе

Эль-Гамаля. Для наглядности размерность параметров крипто­системы выбрана малой, что недопустимо

при использовании практических средств криптографической защиты информации.
Пример: пусть на этапе генерирования ключей выбран модуль криптосистемы р = 1 1 и примитивный элемент g = 2 поля Галуа GF(11). Проверим правильность выбора р и g, вычислив последовательные значения выражения gi (mod p) для 1.21(mod11)=2 26(mod 11)=9
22(mod11)=4 27(mod 11)=7
23(mod11)=8 28(mod 11)=3
24(mod11)=5 29(mod 11)=6
25(mod11)=10 210(mod 11)=1


Рассмотрим пример формирования и проверки цифровой подписи сообще­ния в системе Эль-Гамаля. Для наглядности размерность параметров крипто­системы выбрана

Слайд 16Выберем секретный ключ формирования цифровой подписи сообщений отправителя x =

8 (1< х

подписи:


Пусть необходимо подписать сообщение М = 5. Выберем случайное число k= 9 (0 < k


Составим уравнение вида (19): M=xr + ks mod(p-l) и решим его:s=k-1(M-xr)mod(p-1)=3
Итак, для сообщения М = 5 его цифровой подписью является пара чисел г = 6, s=3. При отсутствии воздействия нарушителя и ошибок канала связи



Выберем секретный ключ формирования цифровой подписи сообщений отправителя x = 8 (1< х

Слайд 17Получатель сообщения вычисляет g m^ (mod p)=25mod11=10
y r^ (r^)s (mod

p)=36 * 63 mod11=10
Таким образом, принятое сообщение не искажено и

получено от законного корреспондента-отправителя.
Условия обеспечения безопасности криптографической системы цифровой подписи сообщений Эль-Гамаля при активных атаках нарушителя Если противоборствующая сторона, зная открытый ключ проверки цифровой подписи сообщений, способна вычислить секретный ключ х из уравнения (15), то это означает полный взлом криптосистемы. Вычислительная сложность нахождения ключа формирования цифровой подписи сообщений для рассматриваемой криптосистемы соответствует вычислительной сложности нахождения ключа дешифрования системы шифрования Эль-Гамаля. Обеспечение требуемой стойкости криптосистемы цифровой подписи сообщений Эль-Гамаля требует выбора параметра n двоичной длины не менее 768 бит (1024 бита для перспективных систем аутентификации информации).



Получатель сообщения вычисляет g m^ (mod p)=25mod11=10y r^ (r^)s (mod p)=36 * 63 mod11=10Таким образом, принятое сообщение

Слайд 18Для данной криптосистемы существует еще один способ вычисления нарушителем секретного

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

открытых сообщений Mt и их подписи {ri, si} для
i = 1, ..., n. Для вычисления секретного ключа х формирования цифровой подписи, что означает при успехе полный взлом крипто-системы, нарушитель может построить систему из n линейных уравнений с n+1 неизвестными k1, k2, …,kn, x
Такая система неразрешима и нарушитель не способен однозначно определить ключ х. Однако если хотя бы один раз случайные числа k повторяются, число неизвестных не будет превышать числа уравнений и система имеет решение. Система уравнений также будет иметь решение, если случайные числа k зависимы друг от друга и любое из них можно выразить через остальные. Поэтому для сохранения в тайне ключа х необходимо строго выполнять условие неповторимости и независимости случайных чисел k.



Для данной криптосистемы существует еще один способ вычисления нарушителем секретного ключа формирования цифровой подписи сообщений. Пусть противостоящая

Слайд 19Существует также опасность подделки нарушителем сообщений и их подписей без

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

сообщение М и его подпись {r,s}. На практике это условие обычно выполняется всегда. Нарушитель подыскивает такую пару чисел (u, w). что выполняется условие
НОД (w, p-l=)1l.
Далее он вычисляет ложную цифровую подпись {r*, s*}, действуя следующим образом:




Противостоящая сторона затем формирует из истинного сообщения ложнoe сообщение М* = s • n mod (p - 1).

Существует также опасность подделки нарушителем сообщений и их подписей без знания ключа формирования подписи. Пусть нарушитель знает

Слайд 20Получатель такого ложного сообщения не в состоянии выявить факт подделки,

так как выполняется условие проверки:


где s1 есть обратный элемент к s.
Для защиты от этой атаки в сообщение М необходимо включать формируемую специальным образом избыточность, которую легко можно было бы проверить получателю сообщений. Для этого в криптосистеме Эль-Гамаля можно, например, использовать формирование избыточности из самого заверяемого сообщения, как предлагается в стандарте ISO / IЕС 9796
Другим, более эффективным средством для исключения возможности подделки сообщений и их цифровых подписей является хэширование самого сообщения с использованием устойчивых к коллизиям криптографических хэш-функций. В этом случае параметр s цифровой подписи вычисляется от хэшированного сообщения h (n) и выражение (20) можно переписать в виде:

Получатель такого ложного сообщения не в состоянии выявить факт подделки, так как выполняется условие проверки:

Слайд 21s=k-1 (h(M)-xr)mod(p-1). (26)
И тогда нарушитель или недобросовестный получатель сообщения не

в состоянии фальсифицировать сообщение n и его цифровую подпись {r,

s} так, чтобы попытка обмана не была обнаружена. Поэтому получатель сообщения сначала должен вычислить его хэшированное значение h (M^) и вместо выражения (21) проверять тождество выражения g h (M^) =y -r^ r s^ (mod p) (27), где {r^, s^} - принятые значения цифровой подписи сообщения M^.
Уязвимость системы цифровой подписи Эль-Гамаля
1. Атака Блайхенбахера.
Получатель должен выбрать случайный элемент gЄF*p. Если системные пользователи обладают одними и теми же открытыми параметрами g и p, то необходимо проверить, насколько случайным является параметр g. Злоумышленник генерирует g=βt(mod p), где β=cq и cАтаку можно предотвратить, если во время верификации проверять условие, что r не делится на q
s=k-1 (h(M)-xr)mod(p-1).	(26) И тогда нарушитель или недобросовестный получатель сообщения не в состоянии фальсифицировать сообщение n и его

Слайд 222. Предостережение относительно выбора случайного параметра k
Генерация цифровой подписи Эль-Гамаля

– вероятностный алгоритм, т.к. k –случайное. k используется один раз,

т.е. шифрование закрытого ключа x идет 1 раз. Важно, чтобы число k никогда не использовалось для других сообщений. (при повторном использовании k нарушитель может построить систему из n линейных уравнений с n+1 неизвестными k1, k2, …, kn, x, и система решается).
3. Предотвращение экзистенциальной подделки подписи.
Алгоритмы составления подписи и ее проверки образуют пару ОНФ с секретом. Т.к. функция проверки ЦП вычисляется в направлении зашифрованный текст s –исходное сообщение m, то схемы ЦП, основанные на ОНФ с секретом, позволяют подделывать правильные пары «сообщение-подпись», применяя алгоритм проверки в направлении от s к m. Но, благодаря свойству перемешивания, которым он обладает, сообщение выглядит бессмысленным.
2. Предостережение относительно выбора случайного параметра kГенерация цифровой подписи Эль-Гамаля – вероятностный алгоритм, т.к. k –случайное. k

Слайд 23
Такой способ подделки называется экзистенциальным. Для предотвращения подделки достаточно включать

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

атака становится невозможной.
Система шифрования информации эль-Гамаля относится к классу несимметричных криптосистем и предназначена для шифрования сообщений открытым ключом и дешифрирования секретным ключом, известным только получателю.
1.На этапе генерирования ключей шифрования центр формирования ключей (ЦФК) выбирает большое простое число р и первообразный элемент g поля Fp, удовлетворяющего условию 12.ЦФК выбирает случайное х (13.На этапе шифрования сообщение М представляется в виде двоичного числа длиной не более |р| бит(0
Такой способ подделки называется экзистенциальным. Для предотвращения подделки достаточно включать в исходное сообщение избыточность, позволяющую выявить подлог.

Слайд 24
Если двоичное представление сообщения превышает р, то оно разделяется на

несколько Мi длиной по | р| бит, которые шифруются последовательно.
4.

Отправитель А случайным и равновероятным для каждого сообщения образом выбираем целое k 1< k ≤ p-2
5. Для шифрования очередного блока М отправитель вычисляет криптограмму, состоящую из двух чисел
С1=gk(mod p) и C2=M yk(mod p) и передает их получателю по открытому каналу
6. Получатель вычисляет С1-х (mod p), используя х, а затем
М=С2(С1-х)(mod p)
M=С2(С1-х)(mod p)=C2(gk) -x (mod p)=Mykg-kx(mod p)=
=M(gx)kg-kx(mod p)=M p≥1024
Если двоичное представление сообщения превышает р, то оно разделяется на несколько Мi длиной по | р| бит,

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

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

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

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


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

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