1. Erzeugung von öffentlichem und privatem Schlüssel:
- (1) Wähle zufällig zwei große Primzahlen p und q und konstruiere n = p*q;
- (2) Berechne die Eulersche Phi-Funktion φ(n) = (p-1) * (q-1);
- (3) Wähle e zufällig so, dass gcd(e, φ(n)) = 1, d. h. e und φ(n) teilerfremd sind; gcd steht für die Ermittlung des größten gemeinsamen Teilers;
- (4) Berechne d so, dass e*d ≡ 1 (mod φ(n)), d. h. d ist das multiplikative Inverse von e.
2. Verschlüsselungsprozess:
(1) Die zu verschlüsselnde Information (Klartext) ist m, m < n; (da Modulo-Arithmetik durchgeführt werden soll, gelten die nachfolgenden Operationen nicht, wenn m größer als n ist; daher sollte die Information, wenn sie größer als n ist, blockweise verschlüsselt werden);
(2)) Die Erzeugung des Geheimtextes c ist $$ c = m^e mod (n) $$
3. Entschlüsselung
$$ c^d mod (n) = (m^e)^d mod (n) = m^(d*e) mod (n) ; $$
3. Entschlüsselung
$$ c^d mod (n) = (m^e)^d mod (n) = m^(d*e) mod (n) ; $$
Warum ist die Entschlüsselung möglich?
Der Satz von Euler wird benötigt (eigentlich eine Verallgemeinerung des kleinen fermatschen Satzes)
a^φ(n) ≡ 1 (mod n)，
Weitere Verallgemeinerung: a^(φ(n)k) ≡ 1 (mod n)，
Wir erhalten a^(φ(n)k+1) ≡ a (mod n)
Beachten Sie, dass ed ≡ 1 mod φ(N), d. h., ed = 1 + k*φ(N).
Daher gilt: $$ M^(de) mod N = M^1 + kφ(N) mod N = M
$$
4. Der Code lautet wie folgt
Beispiel
#coding=utf-8
#__author__ = 'ralph'
import random
def extendedGCD(a, b):
a*xi + b*yi = ri
if b == 0:
return (1, 0, a)
#a*x1 + b*y1 = a
x1 = 1
y1 = 0
#a*x2 + b*y2 = b
x2 = 0
y2 = 1
while b != 0:
q = a / b
#ri = r(i-2) % r(i-1)
r = a % b
a = b
b = r
#xi = x(i-2) - q*x(i-1)
x = x1 - q*x2
x1 = x2
x2 = x
#yi = y(i) - q*y(i-1)
y = y1 - q*y2
y1 = y2
y2 = y
return(x1, y1, a)
def computeD(fn, e):
(x, y, r) = extendedGCD(fn, e)
#y ist möglicherweise < 0, konvertiere es
if y < 0:
return fn + y
return y
def keyGeneration(p,q,e):
#öffentlichen Schlüssel und privaten Schlüssel generieren
n = p * q
fn = (p-1) * (q-1)
d = computeD(fn, e)
return (d,n)
p_v = int(raw_input('Bitte geben Sie den Wert von p (dezimal) ein\n'))
q_v = int(raw_input('Bitte geben Sie den Wert von q (dezimal) ein\n'))
e_v = int(raw_input('Bitte geben Sie den Wert von e (dezimal) ein\n'))
c_v = int(raw_input('Bitte geben Sie den Wert des Chiffretexts c (dezimal) ein\n'))
(d,n) = keyGeneration(p_v,q_v,e_v) # Erzeuge d und n
m = pow(c_v,d,n)
print ("Der erhaltene Klartext m ist:"+str(m))
Wenn p-Wert: 18443, q-Wert: 49891, e-Wert: 19,
Wert des Chiffretexts c:
70479679275221115227470416418414022368270835483295235263072905459788476483295235459788476663551792475206804459788476428313374475206804459788476425392137704796792458265677341524652483295235534149509425392137428313374425392137341524652458265677263072905483295235828509797341524652425392137475206804428313374483295235475206804459788476306220148
Das erhaltene Ergebnis wird angezeigt
Der erhaltene Klartext m ist: 88455713
Beispiel
#coding=utf-8
#__author__ = 'ralph'
import random
def extendedGCD(a, b):
a*xi + b*yi = ri
if b == 0:
return (1, 0, a)
#a*x1 + b*y1 = a
x1 = 1
y1 = 0
#a*x2 + b*y2 = b
x2 = 0
y2 = 1
while b != 0:
q = a / b
#ri = r(i-2) % r(i-1)
r = a % b
a = b
b = r
#xi = x(i-2) - q*x(i-1)
x = x1 - q*x2
x1 = x2
x2 = x
#yi = y(i) - q*y(i-1)
y = y1 - q*y2
y1 = y2
y2 = y
return(x1, y1, a)
def computeD(fn, e):
(x, y, r) = extendedGCD(fn, e)
#y ist möglicherweise < 0, konvertiere es
if y < 0:
return fn + y
return y
def keyGeneration(p,q,e):
#öffentlichen Schlüssel und privaten Schlüssel generieren
n = p * q
fn = (p-1) * (q-1)
d = computeD(fn, e)
return (d,n)
p_v = int(raw_input('Bitte geben Sie den Wert von p (dezimal) ein\n'))
q_v = int(raw_input('Bitte geben Sie den Wert von q (dezimal) ein\n'))
e_v = int(raw_input('Bitte geben Sie den Wert von e (dezimal) ein\n'))
c_v = int(raw_input('Bitte geben Sie den Wert des Chiffretexts c (dezimal) ein\n'))
(d,n) = keyGeneration(p_v,q_v,e_v) # Erzeuge d und n
m = pow(c_v,d,n)
print ("Der erhaltene Klartext m ist:"+str(m))
Der erhaltene Klartext m ist: 88455713