Die Chiffre das Ale-gamalja




 Die allgemeine Idee der Methode



Die Hauptidee ElGamal besteht darin, dass die wirksamen Methoden der Lösung des Vergleiches ax == b (mod p nicht existieren)

Die Bezeichnungen. Durch Z (n) werden wir die Abzüge nach dem Modul n, durch Z * (n) - die Multiplikationsgruppe der umkehrbaren Elemente in Z (n) bezeichnen. Durch ab (werden wir mod n) die Errichtung a in die Stufe b im Ring Z (n) bezeichnen. Hапомню, dass wenn p - die einfache Zahl, so die Gruppe Z * (p) изоморфна Z (p-1).

Wenn auch die Zahlen p und 2p+1 - einfach, p> 2, v und w - bildend der Multiplikationsgruppen Z * (p) und Z * (2p+1) entsprechend.

Das Lemma. Wenn v - bildend Z * (p), so v0 = (p + (p+1) v) (mod 2p) - bildend Multiplikations- die Gruppen Z * (2p). (Diese Gruppe, es ist offenbar, изоморфна Z * (p)).

Die Zahlen p, 2p+1, v, v0, w werden bei der Auswahl des Algorithmus fixiert.


 Die Parolen



СЕКРЕТHЫЙ die Parole - die Zahl x aus Z * (p).

Die OFFENE Parole (y) ist in zwei Schritte ausgerechnet.

  1. Erstens finden wir z=v0x (mod 2p), z gehört der Gruppe Z * (2p).

  2. Hаконец ist die offene Parole y = wz ausgerechnet (mod 2p+1), y gehört der Gruppe Z * (2p+1).

Das Theorem. Bei einer beliebigen Auswahl der geheimen Parole wird (x) die offene Parole (y) der bildenden Multiplikationsgruppe Z * (2p+1) sein. Mit anderen Worten, der Vergleich ya = b (mod 2p+1) ist verhältnismäßig a bei jedem b lösbar.

Der Beweis. Die Zahl w^z wird der bildenden Gruppe Z * (2p+1) iff die Zahlen z und 2p sind gegenseitig einfach. Hо z = v0x (mod 2p), wo v0 - bildend die Gruppen Z * (2p).


 Die elektronische Unterschrift



Wenn auch s - die Zahl (die Informationen), zu der man die elektronische Unterschrift finden muss, s der Gruppe Z (2p) gehört. Dazu wählen wir die Zufallszahl r aus der Gruppe Z * (2p), изоморфной Z * (p), und als Unterschrift geben wir ein Paar Zahlen (a, b), wo aus

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

Da

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

Jenes

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

So ist es für die Zusammenstellung der Unterschrift erforderlich, die geheime Parole (x) zu wissen, z=v0x genauer sagend.

Für die Prüfung der Authentizität der Unterschrift kann man die Gleichheit ausnutzen

ya = bs (mod 2p+1).

In der Tat,

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

Also ist es für die Prüfung der Authentizität der Unterschrift die Noblesse nur die offene Parole (y) genügend.

Bei der Berechnung der Unterschrift befindet sich die Zahl s (die Datei) mit Hilfe der einseitigen chesch-Funktion (das Analogon MD4, aber anderes).


 Also:



Die Bezeichnungen.

        p, 2p+1 - die einfachen Zahlen, 

        v, w - bildend der Gruppen Z * (p) und Z * (2p+1) соответсвенно, 

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

        x - die geheime Parole, die Zahl aus Z (p-1), 

        z - der Zwischenausdruck aus Z (2p), 

        y - der Eröffnungen die Parole, die Zahl aus Z * (2p+1), 

        s - die informative Zahl, 

        r - die Zufallszahl aus Z (2p), 

        (a, b) - die elektronische Unterschrift, 

                a aus Z (2p), 

                b aus Z * (2p+1), 
(c, d) - die chiffrierte Mitteilung,
                c aus Z * (2p+1), 

                d aus Z * (2p+1), 
e - der Zwischenausdruck aus Z * (2p+1).

Hахождение des offenen Schlüssels nach dem Geheimen. x => y

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

Die elektronische Unterschrift x, s, r => a, b (r - zufällig)

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

Die Prüfung der Unterschrift y, s, a, b => y/n

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

Die Chiffrierung y, s, r => c, d

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

Das Entziffern 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)


Werbung auf der Website
ßíäåêñ öèòèðîâàíèÿ

Subscribe Subscribe.Ru
The Family Tree of Family
нпф будущее отзывы