����� �� �����.

������ ���������.

������ � �������� ����������. ����� � �����.

���� ���-������.

����� ���� ������.

�������� ���� 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)



����� �� ��������, � ���������� � ���������.
SpyLOG