Поиск по сайту.

Другие алгоритмы.

Защита и сокрытие информации. Атаки и взлом.

Шифр Эль-Гамаля.

ОБЩАЯ ИДЕЯ МЕТОДА.

Основная идея 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) вычисляем в два шага.

  1. Сначала находим z=v0x (mod 2p), z принадлежит группе Z*(2p).

  2. 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).

ЭЛЕКТРОHHАЯ ПОДПИСЬ.

Пусть 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

  1. v0 = p + (p+1)*v (mod 2p)
  2. z = v0x (mod 2p)
  3. y = wz (mod 2p+1)

Электронная подпись x, s, r =>a, b (r - случайное)

  1. v0 = p + (p+1)*v (mod 2p)
  2. a = v0(p-1-x)*r*s (mod 2p)
  3. b = ws (mod 2p+1)

Проверка подписи y, s, a, b =>y/n

  1. ya == bs (mod 2p+1)

Шифрование y, s, r =>c, d

  1. e = yr (mod 2p+1)
  2. c = wr (mod 2p+1)
  3. d = s*e (mod 2p+1)

Расшифровка x, c, d =>s

  1. v0 = p + (p+1)*v (mod 2p)
  2. z = v0x (mod 2p)
  3. 1/e = c2p-z (mod 2p+1)
  4. s = d/e (mod 2p+1)



Вверх по странице, к оглавлению и навигации.