Содержание
- 2. Покажем, что функция f--1z ( y) является обратной к функции fz (x) так как согласно (
- 3. Очевидно, что такое число А делится нацело на р-1. Поэтому из малой теоремы Ферма следует, что
- 4. неполиномиально зависела от |n|=log n. Например, большие простые числа р’и q’, такие, что p=2p’+1 и q=2q’+1
- 5. 3.Уязвимость для атаки на основе подобранного открытого текста. 1.Во многих криптографических протоколах стандартный режим работы –
- 6. Шифрование сообщений. Рассмотрим использование однонаправленной функции РША с потайным ходом для шифрования сообщений, причем отправителю сообщений
- 7. Цифровая подпись сообщений Рассмотрим использование однонаправленной функции РША с потайным ходом для обеспечения подлинности сообщений, причем
- 8. Если восстановленное из цифровой подписи сообщение совпало с принятым значением сообщения, то принятое сообщение признается подлинным
- 9. Рассмотрим условия, при которых обеспечивается безопасность использовать однонаправленной функции РША с потайным ходом. В общем случае
- 10. где A - некоторая положительная константа, большая 1, n = p q За последние годы в
- 11. Однонаправленная функция Эль-Гамаля с потайным ходим На основе трудности вычисления дискретных логарифмов в алгебраическом поле можно
- 12. На этапе формирования ключевой информации криптосистемы равновероятно выбираются большое простое число р и число g (0
- 13. Отправитель равновероятным недетерминированным образом выбирает случайное число k ( 0 Далее отправитель вычисляет значение первого параметра
- 14. Цифровой подписью сообщения М является пара чисел г и s. Отправитель сообщения по каналу связи передает
- 15. Рассмотрим пример формирования и проверки цифровой подписи сообщения в системе Эль-Гамаля. Для наглядности размерность параметров криптосистемы
- 16. Выберем секретный ключ формирования цифровой подписи сообщений отправителя x = 8 (1 Пусть необходимо подписать сообщение
- 17. Получатель сообщения вычисляет g m^ (mod p)=25mod11=10 y r^ (r^)s (mod p)=36 * 63 mod11=10 Таким
- 18. Для данной криптосистемы существует еще один способ вычисления нарушителем секретного ключа формирования цифровой подписи сообщений. Пусть
- 19. Существует также опасность подделки нарушителем сообщений и их подписей без знания ключа формирования подписи. Пусть нарушитель
- 20. Получатель такого ложного сообщения не в состоянии выявить факт подделки, так как выполняется условие проверки: где
- 21. s=k-1 (h(M)-xr)mod(p-1). (26) И тогда нарушитель или недобросовестный получатель сообщения не в состоянии фальсифицировать сообщение n
- 22. 2. Предостережение относительно выбора случайного параметра k Генерация цифровой подписи Эль-Гамаля – вероятностный алгоритм, т.к. k
- 23. Такой способ подделки называется экзистенциальным. Для предотвращения подделки достаточно включать в исходное сообщение избыточность, позволяющую выявить
- 25. Скачать презентацию
Покажем, что функция f--1z ( y) является обратной к функции fz
Покажем, что функция f--1z ( y) является обратной к функции fz
так как согласно ( 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
Очевидно, что такое число А делится нацело на р-1. Поэтому из
Очевидно, что такое число А делится нацело на р-1. Поэтому из
Отсюда Ат.е. |А|=log A
неполиномиально зависела от |n|=log n. Например, большие простые числа р’и q’,
неполиномиально зависела от |n|=log n. Например, большие простые числа р’и q’,
2. Атака «встреча посередине» при пересылке коротких сообщений. Небольшие исходные сообщения m
3.Уязвимость для атаки на основе подобранного открытого текста.
1.Во многих криптографических протоколах
3.Уязвимость для атаки на основе подобранного открытого текста.
1.Во многих криптографических протоколах
2. Криптоалгоритм должен быть таким, чтобы расшифрованный текст имеющий вид случайного набора цифр, не позволил атакующему извлечь полезную информацию.
В реальных версиях РША эти недостатки исправлены.
Шифрование сообщений.
Рассмотрим использование однонаправленной функции РША с потайным ходом для
Шифрование сообщений.
Рассмотрим использование однонаправленной функции РША с потайным ходом для
Выберем в качестве информации потайного хода z = {p,q,d}, а значения е и n открыто сообщим корреспондентам сети. Отправитель секретного сообщения x шифрует его с использованием несекретного ключа шифрования е согласно выражению (11). Получатель криптограммы у дешифрует сообщение x с использованием секретного ключа дешифрования d согласно выражению (12). Нарушитель, которому известен несекретный ключ шифрования, но неизвестна информация потайного хода z, не способен читать передаваемые сообщения..
Данный способ шифрования очень удобен тем, что не требует доставки секретной ключевой информации отправителям секретных сообщений.
Цифровая подпись сообщений
Рассмотрим использование однонаправленной функции РША с потайным ходом
Цифровая подпись сообщений
Рассмотрим использование однонаправленной функции РША с потайным ходом
Выберем качестве информации потайного хода z={p,q,e} }, а значения d и n открыто сообщим всем корреспондентам-получателям сообщений сети.
Отправитель заверяемого сообщения х формирует цифровую подпись у данного сообщения с использованием секретного ключа е формирования цифровой подписи общения согласно выражению (11).
Отправитель по каналу связи передает получателю само сообщение и его цифровую подпись. Получатель возводит полученное значение у цифровой подписи сообщения х в степень .несекретного ключа d проверки цифровой подписи отправителя согласно выражению (12).
Если восстановленное из цифровой подписи сообщение совпало с принятым значением сообщения,
Если восстановленное из цифровой подписи сообщение совпало с принятым значением сообщения,
Нарушитель, которому известен несекретный ключ проверки цифровой подписи отправителя, но неизвестна информация потайного хода z, не способен сформировать цифровую подпись произвольного сообщения, фальшивость которого не будет обнаружена получателем. Данный способ обеспечения подлинности информации; удобен тем, что проверка подлинности сообщений не требует доставки секретной ключевой информации.
Законные пользователи, знающие информацию потайного хода z, способны вычислительно просто определить значения прямой fz(x) и обратной f-1z(y) функций.
Для нарушителя, которому неизвестна информация потайного хода z, определение обратной функции f-1z(y) для случая шифрования или значения прямой функции fz(x) для случая обеспечения подлинности сообщений должны быть вычислительно нереализуемыми.
Рассмотрим условия, при которых обеспечивается безопасность использовать однонаправленной функции РША с
Рассмотрим условия, при которых обеспечивается безопасность использовать однонаправленной функции РША с
где A - некоторая положительная константа, большая 1, n = p
где A - некоторая положительная константа, большая 1, n = p
За последние годы в области разработки эффективных методов факторизации достигнуты существенные успехи, поэтому- для обеспечения требуемой безопасности применения однонаправленной функции РША с потайным ходом должны использоваться числа р и q размерностью многие сотни и даже тысячи бит. Известны примеры, как, объединив через глобальную сеть связи вычислительный ресурс сотен и тысяч ЭВМ, удается разложить на множители числа, состоящие из 130 десятичных знаков ( бит). Отметим, что сложность обращения рассматриваемой однонаправленной функции существенно уменьшается при использовании чисел p и q, не являющихся простыми. Также нежелательно использовать простые числа специального вида, например числа Мерсенна вида 2k-1, где k - натуральное число, для которых известны быстрые (полиномиальной сложности) алгоритмы факторизации.
(14)
Однонаправленная функция Эль-Гамаля с потайным ходим
На основе трудности вычисления дискретных логарифмов
Однонаправленная функция Эль-Гамаля с потайным ходим
На основе трудности вычисления дискретных логарифмов
Поле является более сложной алгебраической структурой по сравнению с группой, над его элементами можно выполнять операции сложения и умножения, а в группе - только сложение или только умножение. Например, рассмотренная ранее однонаправ-ленная функция Диффи и Хеллмана, послужившая основой криптосистемы открытого распространения ключей, использует операции умножения над элементами группы.
В 1985 году Т. Эль-Гамаль предложил криптографическую систему цифровой подписи сообщений, которая в настоящее время считается одной из наиболее стойких криптосистем обеспечения подлинности передаваемой и хранимой информации. Рассмотрим принципы построения данной криптосистемы, послужившей основой для отечественного и американского государственных стандартов цифровой подписи сообщений
На этапе формирования ключевой информации криптосистемы равновероятно выбираются большое простое число
На этапе формирования ключевой информации криптосистемы равновероятно выбираются большое простое число
g (0
Чтобы заверить цифровой подписью передаваемое сообщение М, двоичное представление которого должно быть меньше значения
р: 0<М<р, (16)
Отправитель равновероятным недетерминированным образом выбирает случайное число k ( 01)) так, чтобы числа k и р- 1 не имели общих делителей, кроме 1, то есть их наибольший общий делитель НОД (k, p-1)=1. (17)
Далее отправитель вычисляет значение первого параметра цифровой подписи сообщения:
(18)
составляет уравнение вида
M=xr + ks mod(p-l), (19)
и решает его относительно второго параметра цифровой подписи сообщения
(20)
где k-1 есть число, обратное к числу k по mod (р - 1).
Отправитель равновероятным недетерминированным образом выбирает случайное число k ( 0 (18) составляет уравнение вида (20) где k-1 есть число, обратное к числу k по mod (р - 1).
Далее отправитель вычисляет значение первого параметра цифровой подписи сообщения:
M=xr + ks mod(p-l), (19)
и решает его относительно второго параметра цифровой подписи сообщения
Цифровой подписью сообщения М является пара чисел г и s. Отправитель
Цифровой подписью сообщения М является пара чисел г и s. Отправитель
На приеме корреспондент-получатель сначала проверяет допустимость принятого значения r^.
Если оно не находится в пределах 0 < r^<р -1, принятое сообщение отвергается как ложное. Если принятое значение s^ не находится в пределах 0 < s^ <р - 1, сообщение также отвергается как ложное. Получатель удостоверяется в подлинности принятого сообщения m^ заверенного принятой подписью {r^ , s^}, и отсутствии в нем искажений тогда и только тогда, когда выполняется равенство:
(21)
Рассмотрим пример формирования и проверки цифровой подписи сообщения в системе Эль-Гамаля.
Рассмотрим пример формирования и проверки цифровой подписи сообщения в системе Эль-Гамаля.
Пример: пусть на этапе генерирования ключей выбран модуль криптосистемы р = 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
Выберем секретный ключ формирования цифровой подписи сообщений отправителя x = 8
Выберем секретный ключ формирования цифровой подписи сообщений отправителя x = 8
Пусть необходимо подписать сообщение М = 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. При отсутствии воздействия нарушителя и ошибок канала связи
Получатель сообщения вычисляет g m^ (mod p)=25mod11=10
y r^ (r^)s (mod p)=36
Получатель сообщения вычисляет g m^ (mod p)=25mod11=10
y r^ (r^)s (mod p)=36
Таким образом, принятое сообщение не искажено и получено от законного корреспондента-отправителя.
Условия обеспечения безопасности криптографической системы цифровой подписи сообщений Эль-Гамаля при активных атаках нарушителя Если противоборствующая сторона, зная открытый ключ проверки цифровой подписи сообщений, способна вычислить секретный ключ х из уравнения (15), то это означает полный взлом криптосистемы. Вычислительная сложность нахождения ключа формирования цифровой подписи сообщений для рассматриваемой криптосистемы соответствует вычислительной сложности нахождения ключа дешифрования системы шифрования Эль-Гамаля. Обеспечение требуемой стойкости криптосистемы цифровой подписи сообщений Эль-Гамаля требует выбора параметра n двоичной длины не менее 768 бит (1024 бита для перспективных систем аутентификации информации).
Для данной криптосистемы существует еще один способ вычисления нарушителем секретного ключа
Для данной криптосистемы существует еще один способ вычисления нарушителем секретного ключа
i = 1, ..., n. Для вычисления секретного ключа х формирования цифровой подписи, что означает при успехе полный взлом крипто-системы, нарушитель может построить систему из n линейных уравнений с n+1 неизвестными k1, k2, …,kn, x
Такая система неразрешима и нарушитель не способен однозначно определить ключ х. Однако если хотя бы один раз случайные числа k повторяются, число неизвестных не будет превышать числа уравнений и система имеет решение. Система уравнений также будет иметь решение, если случайные числа k зависимы друг от друга и любое из них можно выразить через остальные. Поэтому для сохранения в тайне ключа х необходимо строго выполнять условие неповторимости и независимости случайных чисел k.
Существует также опасность подделки нарушителем сообщений и их подписей без знания
Существует также опасность подделки нарушителем сообщений и их подписей без знания
НОД (w, p-l=)1l.
Далее он вычисляет ложную цифровую подпись {r*, s*}, действуя следующим образом:
Противостоящая сторона затем формирует из истинного сообщения ложнoe сообщение М* = s • n mod (p - 1).
Получатель такого ложного сообщения не в состоянии выявить факт подделки, так
Получатель такого ложного сообщения не в состоянии выявить факт подделки, так
где s1 есть обратный элемент к s.
Для защиты от этой атаки в сообщение М необходимо включать формируемую специальным образом избыточность, которую легко можно было бы проверить получателю сообщений. Для этого в криптосистеме Эль-Гамаля можно, например, использовать формирование избыточности из самого заверяемого сообщения, как предлагается в стандарте ISO / IЕС 9796
Другим, более эффективным средством для исключения возможности подделки сообщений и их цифровых подписей является хэширование самого сообщения с использованием устойчивых к коллизиям криптографических хэш-функций. В этом случае параметр s цифровой подписи вычисляется от хэшированного сообщения h (n) и выражение (20) можно переписать в виде:
s=k-1 (h(M)-xr)mod(p-1). (26)
И тогда нарушитель или недобросовестный получатель сообщения не в
s=k-1 (h(M)-xr)mod(p-1). (26)
И тогда нарушитель или недобросовестный получатель сообщения не в
Уязвимость системы цифровой подписи Эль-Гамаля
1. Атака Блайхенбахера.
Получатель должен выбрать случайный элемент gЄF*p. Если системные пользователи обладают одними и теми же открытыми параметрами g и p, то необходимо проверить, насколько случайным является параметр g. Злоумышленник генерирует g=βt(mod p), где β=cq и c
2. Предостережение относительно выбора случайного параметра k
Генерация цифровой подписи Эль-Гамаля –
2. Предостережение относительно выбора случайного параметра k
Генерация цифровой подписи Эль-Гамаля –
3. Предотвращение экзистенциальной подделки подписи.
Алгоритмы составления подписи и ее проверки образуют пару ОНФ с секретом. Т.к. функция проверки ЦП вычисляется в направлении зашифрованный текст s –исходное сообщение m, то схемы ЦП, основанные на ОНФ с секретом, позволяют подделывать правильные пары «сообщение-подпись», применяя алгоритм проверки в направлении от s к m. Но, благодаря свойству перемешивания, которым он обладает, сообщение выглядит бессмысленным.
Такой способ подделки называется экзистенциальным. Для предотвращения подделки достаточно включать в
Такой способ подделки называется экзистенциальным. Для предотвращения подделки достаточно включать в
Система шифрования информации эль-Гамаля относится к классу несимметричных криптосистем и предназначена для шифрования сообщений открытым ключом и дешифрирования секретным ключом, известным только получателю.
1.На этапе генерирования ключей шифрования центр формирования ключей (ЦФК) выбирает большое простое число р и первообразный элемент g поля Fp, удовлетворяющего условию 1