Подделка цифровой подписи в схеме Эль-Гамаля

Схема цифровой подписи Эль-Гамаля уязвима к экзистенциальной подделке, но селективную подделку на этой схеме сделать очень трудно.

Подделка только ключа. В этом типе подделки Ева имеет доступ только к открытому ключу. Возможны два варианта:

1. Ева имеет заранее заданное сообщение М. Она должна подделать подпись Алисы на этом сообщении. Ева должна найти две правильных подписи S₁ и S₂ для этого сообщения. Это - селективная подделка.
• Ева может выбрать S₂ и вычислить S₁. Она должна иметь . Другими словами, или . Это означает вычисление дискретного логарифма, что является очень трудным.
• Ева может выбрать S₂ и вычислить S₁. Это намного труднее, чем выполнить часть a
2. Ева может методом случайного подбора найти три значения, М, S₁ и S₂, такие, что подпись первого используется для второго. Если Ева может найти два новых параметра x и y, такие, что М = xS₂ mod (p - 1) и S₁ = -y S₂ mod (p - 1), то она может подделать сообщение, но серьезной выгоды не получит, поскольку это - экзистенциальная подделка.

Подделка при известном сообщении. Если Ева перехватила сообщение М и его две подписи S₁ и S₂, она может найти другое сообщение М', с той же самой парой подписей S₁ и S₂. Однако обратите внимание, что это - экзистенциальная подделка, которая не помогает Еве.

Проблема схемы цифровой подписи Эль-Гамаля - в том, что p должно быть очень большим, чтобы сделать трудной проблему дискретного логарифма Zp*. Рекомендуется длина p по крайней мере 1024 битов. Можно сделать подпись размером 2048 бит. Чтобы уменьшить размер подписи, Шнорр предложил новую схему, основанную на схеме Эль-Гамаля, но с уменьшенным размером подписи.

***************************************************************************

Шифр Эль-Гамаля
Общая идея метода
	Основная идея ElGamal состоит в том, что не существует эффективных методов решения сравнения ax == b (mod p) Обозначения. Через Z(n) обозначим вычеты по модулю n, через Z*(n) - мультипликативную группу обратимых элементов в Z(n). Через ab (mod n) будем обозначать возведение a в степень b в кольце Z(n). Hапомню, что если p - простое число, то группа Z*(p) изоморфна Z(p-1). Пусть числа p и 2p+1 - простые, p>2,v и w - образующие мультипликативных групп Z*(p) и Z*(2p+1) соответственно. Лемма. Если v - образующая Z*(p), то v0 = (p + (p+1)v) (mod 2p) - образующая мультипликативной группы Z*(2p). (Эта группа, очевидно, изоморфна Z*(p)). Числа p, 2p+1, v, v0, w фиксируются при выборе алгоритма.
Пароли
	СЕКРЕТHЫЙ пароль - число x из Z*(p). ОТКРЫТЫЙ пароль (y) вычисляем в два шага. Сначала находим z=v0x (mod 2p), z принадлежит группе Z*(2p). Hаконец вычисляем сам открытый пароль y = wz (mod 2p+1), y принадлежит группе Z*(2p+1). Теорема. При любом выборе секретного пароля (x) открытый пароль (y) будет являться образующей мультипликативной группы Z*(2p+1). Другими словами, сравнение ya = b (mod 2p+1) разрешимо относительно a при любом b. Доказательство. Число w^z будет образующей группы Z*(2p+1) iff числа z и 2p взаимно просты. Hо z = v0x (mod 2p), где v0 - образующая группы Z*(2p).
Электронная подпись
	Пусть s - число (информация), к которому надо найти электронную подпись, s принадлежит группе Z(2p). Для этого выбираем случайное число r из группы Z*(2p), изоморфной Z*(p), и в качестве подписи выдаем пару чисел (a,b), где a = a(r,s) = z-1*r*s = v0(-x)*r*s (mod 2p); b = b(r,s) = wr (mod 2p+1). Так как Z*(2p) = Z*(p)+Z*(2) = Z*(p) = Z(p-1), то 1/z = z-1 = v0-x = v0(p-1-x). Таким образом, для составления подписи требуется знать секретный пароль (x), точнее говоря z=v0x. Для проверки подлинности подписи можно воспользоваться равенством ya = bs (mod 2p+1). В самом деле, ya = (wz)^(z-1*r*s) = w^(z*z-1*r*s) = wrs = (wr)^s = bs (mod 2p+1) Следовательно, для проверки подлинности подписи достаточно знать только открытый пароль (y). При вычислении подписи число s(файл) находится с помощью однонаправленной хэш-функции (аналог MD4, но другое).
Итак:
	Обозначения. p, 2p+1 - простые числа,   v, w - образующие групп Z*(p) и Z*(2p+1) соответсвенно,   v0 = p + (p+1)v - образующая Z*(2p),   x - секретный пароль, число из Z(p-1),   z - промежуточное выражение из Z(2p),   y - открытий пароль, число из Z*(2p+1),   s - информационное число,   r - случайное число из Z(2p),   (a,b) - электронная подпись,   a из Z(2p),   b из Z*(2p+1), (c,d) - зашифрованное сообщение, c из Z*(2p+1),   d из Z*(2p+1), e - промежуточное выражение из Z*(2p+1). Hахождение открытого ключа по секретному. x =>y v0 = p + (p+1)*v (mod 2p) z = v0x (mod 2p) y = wz (mod 2p+1) Электронная подпись x, s, r =>a, b (r - случайное) v0 = p + (p+1)*v (mod 2p) a = v0(p-1-x)*r*s (mod 2p) b = ws (mod 2p+1) Проверка подписи y, s, a, b =>y/n ya == bs (mod 2p+1) Шифрование y, s, r =>c, d e = yr (mod 2p+1) c = wr (mod 2p+1) d = s*e (mod 2p+1) Расшифровка x, c, d =>s v0 = p + (p+1)*v (mod 2p) z = v0x (mod 2p) 1/e = c2p-z (mod 2p+1) s = d/e (mod 2p+1)

ШИФРЫС ОТКРЫТЫМ КЛЮЧОМ

Развитие криптографии в XX веке было стремительным, но неравномерным. Анализ истории ее развития как специфической области человеческой деятельности выделяет три основных периода.

1. Начальный, имевший дело лишь с ручными шифрами, начавшийся в седой древности, закончился лишь в конце тридцатых годов XX века. Криптография за это время прошла длинный путь от магического искусства древних жрецов до будничной прикладной профессии чиновников секретных ведомств.
2. Следующий период отмечен созданием и широким внедрением в практику сначала механических, потом электромеханических и, наконец, электронных устройств шифрования, созданием сетей засекреченной связи. Его началом можно считать применение телеграфных шифровальных машин, использующих длинный одноразовый ключ. Длится он по наши дни. Однако к середине семидесятых годов было достигнуто положение, когда повышение стойкости шифров отошло на второй план. С развитием разветвленных коммерческих сетей связи, электронной почты и глобальных информационных систем самой главными стали проблемы распределения секретных ключей и подтверждения авторства. К ним теперь привлечено внимание широкого круга криптологов.
3. Началом третьего периода развития криптологии обычно считают 1976 год, когда американские математики Диффи и Хеллман предложили принципиально новый вид организации засекреченной связи без предварительного снабжения абонентов секретными ключами, так называемое шифрование с открытым ключом. В результате стали появляться криптографические системы, основанные на подходе, сформулированном еще в сороковых годах Шенноном. Он предложил строить шифр таким способом, что-бы его раскрытие было эквивалентно решению математической задачи, требующей выполнения объемов вычислений, превосходящих возможности современных ЭВМ. Новый период развития криптографии характеризуется появлением полностью автоматизированных систем шифрованной связи, в которых каждый пользователь имеет свой индивидуальный пароль для подтверждения подлинности, хранит его, к примеру на магнитной карте, и предъявляет при входе в систему, а весь остальной процесс проведения секретной связи происходит автоматически.

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

При шифровании с открытым ключом для шифрования и расшифровывания используются разные ключи, и знание одного из них не дает практической возможности определить второй. Поэтому ключ для шифрования может быть сделан общедоступным без потери стойкости шифра, если ключ для расшифровывания сохраняется в секрете, например, генерируется и хранится только получателем информации. Несмотря на подозрительность (кому верят криптоаналитики?) и консерватизм (лучшее - для криптографов - враг хорошего!) новые идеи стали быстро реализовываться на практике. Шифруют и сейчас традиционными методами, но рассылка ключей и цифровая подпись стали выполняться уже по-новому. Сейчас два метода шифрования с открытым ключом получили признание и закреплены в стандартах. Национальный институт стандартов и технологий США NIST (бывший ANSI) принял стандарт MD 20899, основанный на алгоритме ЭльГамаля, а на основе алгоритма RSA приняты стандарты ISO/IEC/DIS 9594-8 международной организацией по стандартизации и Х.509 международным комитетом по связи.

"Шифр ЭльГамаля

Криптографы постоянно вели поиски более эффективных систем открытого шифрования, и в 1985 году ЭльГамаль предложил следующую схему на основе возведения в степень по модулю большого простого числа. Для этого задается большое простое число Р. Сообщения представляются целыми числами S из интервала (1, Р). Оригинальный протокол передачи сообщения S выглядит в варианте Шамира, одного из авторов RSA, так:

1. Отправитель А и получатель b знают лишь Р. A генерирует случайное число Х из интервала (1,Р) и B тоже генерирует случайное число Y из того же интервала.
2. A шифрует сообщение S1=S**X MOD Р и посылает B.
3. B шифрует его своим ключом S2=S1**Y MOD Р и посылает S2 к A.
4. A "снимает" свой ключ S3=S2**(-X) MOD Р и возвращает S3 к B.
5. Получатель В расшифровывает сообщение: S=S3**(-Y) MOD Р.

Этот протокол можно применить, например, для таких неожиданных целей, как игра в очко или блэкджек по телефону. Крупье шифрует карты своим ключом и передает их игроку. Игрок выбирает наугад одну из карт, шифрует карты своим ключом и возвращает их крупье. Крупье "снимает" с выбранной карты свой ключ и отсылает ее игроку. "Сняв" с этой карты свой ключ игрок узнает ее номинал и принимает решение: спасовать, тянуть еще или раскрываться. Теперь, хотя колода находится у крупье, но он не может ее раскрыть, так как карты зашифрованы ключом игрока. Крупье выбирает свою карту аналогично игроку. (Аналогичный алгоритм для игры в карты можно реализовать и на основе шифрования заменой операцией XOR. Однако им нельзя распространять ключи из-за легкого перехвата и взлома.)

В системе ЭльГамаля большая степень защиты, чем у алгоритма RSA достигается с тем же по размеру N, что позволяет почти на порядок увеличить скорость шифрования и расшифрования. Криптостойкость системы ЭльГамаля основана на том, что можно легко вычислить степень целого числа, то есть произвести умножение его самого на себя любое число раз так же, как и при операциях с обычными числами. Однако трудно найти показатель степени, в которую нужно возвести заданное число, чтобы получить другое, тоже заданное. В общем случае эта задача дискретного логарифмирования кажется более трудной, чем разложение больших чисел на простые сомножители, на основании чего можно предположить, что сложности вскрытия систем RSA и ЭльГамаля будут сходными. С точки зрения практической реализации, как программным, так и аппаратным способом ощутимой разницы между этими двумя стандартами нет. Однако в криптостойкости они заметно различаются. Если рассматривать задачу разложения произвольного целого числа длиной в 512 бит на простые множители и задачу логарифмирования целых чисел по 512 бит, вторая задача, по оценкам математиков, несравненно сложнее первой. Однако есть одна особенность. Если в системе, построенной с помощью алгоритма RSA, криптоаналитику удалось разложить открытый ключ N одного из абонентов на два простых числа, то возможность злоупотреблений ограничивается только этим конкретным пользователем. В случае же системы, построенной с помощью алгоритма ЭльГамаля, угрозе раскрытия подвергнутся все абоненты криптографической сети. Кроме того, упомянутые выше Ленстра и Манасси не только поколебали стойкость RSA, разложив девятое число Ферма на простые множители за неприлично короткое время, но и, как было замечено некоторыми экспертами, указали "брешь" в способе ЭльГамаля. Дело в том, что подход, применявшийся при разложении на множители девятого числа Ферма, позволяет существенно усовершенствовать методы дискретного логарифмирования для отдельных специальных простых чисел. То есть тот, кто предлагает простое Р для алгоритма ЭльГамаля, имеет возможность выбрать специальное простое, для которого задача дискретного логарифмирования будет вполне по силам обычным ЭВМ. Следует заметить, что этот недостаток алгоритма ЭльГамаля не фатален. Достаточно предусмотреть процедуру, гарантирующую случайность выбора простого Р в этой системе, и тогда только что высказанное возражение теряет силу. Стоит отметить, что чисел специального вида, ослабляющих метод ЭльГамаля, очень мало и случайным их выбором можно пренебречь.

******************************************************************

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

При программной реализации схемы Эль Гамаля скорость ее работы (на SPARC-II) в режимах шифрования и рас-шифрования при 160-битовом показателе степени для различных длин модуля Р определяется значениями, приведенными в табл.2.

Таблица 2 Скорости работы схемы Эль Гамаля

************************************************************************

8.5. Алгоритм шифрования Эль-Гамаля

Схема была предложена Тахером Эль-Гамалем в 1984 году. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и обеспечения аутентификации. Стойкость данного алгоритма базируется на сложности решения задачи дискретного логарифмирования.

Суть задачи заключается в следующем. Имеется уравнение

g^x mod p = y. (8.6)

Требуется по известным g, y и p найти целое неотрицательное число x (дискретный логарифм). Порядок создания ключей приводится в следующей таблице.

Таблица 8.7. Процедура создания ключей

Для шифрования каждого отдельного блока исходного сообщения должно выбираться случайное число k (1 < k < p – 1). После чего шифрограмма генерируется по следующим формулам

a = g^k mod p, (8.7)

b = (y^k Т) mod p, (8.8)

где Т – исходное сообщение; (a, b) – зашифрованное сообщение.

Дешифрование сообщения выполняется по следующей формуле

T = (b (a^x)^-1) mod p (8.9) или

T = (b a^p-1-x) mod p, (8.10)

где (a^x)^-1 – обратное значение числа a^x по модулю p.

Пример шифрования и дешифрования по алгоритму Эль-Гамаля при k = 7 приведен в таблице, хотя для шифрования каждого блока (в нашем случае буквы) исходного сообщения надо использовать свое случайное число k.

Первая часть шифрованного сообщения – a = 5⁷ mod 23 = 17.

a^x = 17³ = 4917, (a^x)^-1 = 5 (4913 * 5 mod 23 = 1) или a^p-1-x = 17^23-1-3 = 239072435685151324847153.

Таблица 8.8. Пример шифрования по алгоритму Эль-Гамаля (при k = const)

Ввиду того, что число k является произвольным, то такую схему еще называют схемой вероятностного шифрования. Вероятностный характер шифрования является преимуществом для схемы Эль-Гамаля, т.к. у схем вероятностного шифрования наблюдается большая стойкость по сравнению со схемами с определенным процессом шифрования. Недостатком схемы шифрования Эль-Гамаля является удвоение длины зашифрованного текста по сравнению с начальным текстом. Для схемы вероятностного шифрования само сообщение Т и ключ не определяют шифртекст однозначно. В схеме Эль-Гамаля необходимо использовать различные значения случайной величины k для шифровки различных сообщений Т и Т’. Если использовать одинаковые k, то для соответствующих шифртекстов (a, b) и (a’, b’) выполняется соотношение b (b’)^-1 = Т (Т’)^-1 (mod p). Из этого выражения можно легко вычислить Т, если известно Т’.

Пример. Предположим злоумышленник перехватил зашифрованное сообщение С = ((a₁, b₁), (a₂, b₂), …, (a_n, b_n)), для которого использовалось одно и тоже случайное число k. Он знает один из блоков T_i = f(C_i) или при известном открытом ключе (y, g, p) ему удалось подобрать k’, которое совпало с используемым при шифровании k. Например по второму варианту, для шифрования символа Х (Т' = 22) злоумышленник использовал k’ = 7 (равное k). Тогда, b(X) = b’ = (10⁷ * 22) mod 23 = 9, (b’)^-1 = 18. Расшифрование перехваченного сообщения приведено в следующей таблице.

Таблица 8.9. Пример расшифрования перехваченного сообщения