Delphi World - это проект, являющийся сборником статей и малодокументированных возможностей  по программированию в среде Delphi. Здесь вы найдёте работы по следующим категориям: delphi, delfi, borland, bds, дельфи, делфи, дэльфи, дэлфи, programming, example, программирование, исходные коды, code, исходники, source, sources, сорцы, сорсы, soft, programs, программы, and, how, delphiworld, базы данных, графика, игры, интернет, сети, компоненты, классы, мультимедиа, ос, железо, программа, интерфейс, рабочий стол, синтаксис, технологии, файловая система...
Шифр Эль-Гамаля

Общая идея метода

Основная идея 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).

Электронная подпись

Пусть 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)
Проект Delphi World © Выпуск 2002 - 2024
Автор проекта: USU Software
Вы можете выкупить этот проект.