Le chiffre El-Gamalja




 L'idée totale de la méthode



L'idée principale ElGamal est qu'il n'y a pas méthodes efficaces de la décision de la comparaison ax == b (mod p)

Les désignations. Par Z (n) nous désignerons les déductions selon le module n, par Z * (n) - le groupe de multiplicateur des éléments convertibles à Z (n). Par ab (mod n) nous désignerons la construction a au degré b dans l'anneau Z (n). Hапомню que si p - le nombre premier, le groupe Z * (p) est isomorphe Z (p-1).

Que les nombres p et 2p+1 - simple, p> 2, v et w - les génératrices des groupes de multiplicateur Z * (p) et Z * (2p+1) en conséquence.

La lemme. Si v - la génératrice Z * (p), v0 = (p + (p+1) v) (mod 2p) - la génératrice du groupe de multiplicateur Z * (2p). (Ce groupe, évidemment, est isomorphe Z * (p)).

Les nombres p, 2p+1, v, v0, w sont fixés au choix de l'algorithme.


 Les mots d'ordre



СЕКРЕТHЫЙ le mot d'ordre - le nombre x de Z * (p).

Le mot d'ordre OUVERT (y) est calculé à deux pas.

  1. D'abord nous trouvons z=v0x (mod 2p), z appartient au groupe Z * (2p).

  2. Hаконец on calcule le mot d'ordre lui-même ouvert y = wz (mod 2p+1), y appartient au groupe Z * (2p+1).

Le théorème. À n'importe quel choix du mot d'ordre confidentiel (x) le mot d'ordre ouvert (y) sera du groupe formant de multiplicateur Z * (2p+1). En d'autres termes, la comparaison ya = b (mod 2p+1) разрешимо relativement a à chacun b.

La preuve. Le nombre w^z sera du groupe formant Z * (2p+1) iff les nombres z et 2p sont mutuellement simples. Hо z = v0x (mod 2p), où v0 - la génératrice du groupe Z * (2p).


 La signature électronique



Que s - le nombre (information), vers qui il faut trouver la signature électronique, s appartienne au groupe Z (2p). Est choisi Pour cela le nombre accidentel r du groupe Z * (2p), isomorphe Z * (p), et à titre de la signature nous donnons une paire des nombres (a, b), où

a = a (r, s) = z-1*r*s = v0 (-x) *r*s (mod 2p); b = b (r, s) = wr (mod 2p+1).

Puisque

Z * (2p) = Z * (p) +Z * (2) = Z * (p) = Z (p-1),

Cela

1/z = z-1 = v0-x = v0 (p-1-x).

Ainsi, pour la rédaction de la signature il faut connaître le mot d'ordre confidentiel (x), en disant plus exactement z=v0x.

Pour le contrôle de l'authenticité de la signature on peut se servir de l'égalité

ya = bs (mod 2p+1).

En effet,

ya = (wz) ^ (z-1*r*s) = w ^ (z*z-1*r*s) = wrs = (wr) ^s = bs (mod 2p+1)

Donc, pour le contrôle de l'authenticité de la signature il suffit la noblesse seulement mot d'ordre ouvert (y).

Au calcul de la signature le nombre s (le fichier) se trouve avec l'aide de l'hesh-fonction unidirectionelle (l'analogue MD4, mais l'autre).


 Donc :



Les désignations.

        p, 2p+1 - les nombres premiers, 

        v, w - les génératrices des groupes Z * (p) et Z * (2p+1) соответсвенно, 

        v0 = p + (p+1) v - formant Z * (2p), 

        x - le mot d'ordre confidentiel, le nombre de Z (p-1), 

        z - l'expression intermédiaire de Z (2p), 

        y - les ouvertures le mot d'ordre, le nombre de Z * (2p+1), 

        s - le nombre d'information, 

        r - le nombre accidentel de Z (2p), 

        (a, b) - la signature électronique, 

                a de Z (2p), 

                b de Z * (2p+1), 
(c, d) - le message chiffré,
                c de Z * (2p+1), 

                d de Z * (2p+1), 
e - l'expression intermédiaire de Z * (2p+1).

Hахождение de la clé ouverte selon le confidentiel. x => y

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

La signature électronique x, s, r => a, b (r - accidentel)

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

Le contrôle de la signature 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)

Le déchiffrement 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)
Яндекс цитирования

Subscribe Subscribe.Ru
The Family Tree of Family