| 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.
- Erstens finden wir z=v0x (mod 2p), z gehört der Gruppe Z * (2p).
- 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
- v0 = p + (p+1) *v (mod 2p)
- z = v0x (mod 2p)
- y = wz (mod 2p+1)
Die elektronische Unterschrift x, s, r => a, b (r - zufällig)
- v0 = p + (p+1) *v (mod 2p)
- a = v0 (p-1-x) *r*s (mod 2p)
- b = ws (mod 2p+1)
Die Prüfung der Unterschrift y, s, a, b => y/n
- ya == bs (mod 2p+1)
Die Chiffrierung y, s, r => c, d
- e = yr (mod 2p+1)
- c = wr (mod 2p+1)
- d = s*e (mod 2p+1)
Das Entziffern x, c, d => s
- v0 = p + (p+1) *v (mod 2p)
- z = v0x (mod 2p)
- 1/e = c2p-z (mod 2p+1)
- s = d/e (mod 2p+1)
|
|
|