RSA funktioniert nicht

[LucaMtG]

Hi,
ich muss in Info nen Vortrag über asymetrische Kryptographie halten und hatte mich mal selbst versucht das zu programmieren, sodass die andren aus meiner Klasse das auch verstehen können. Und irgendwie fühl ich mich echt dumm, weil das hier funktioniert nicht, dabei ist es fast dasselbe was ich schonmal verwendet habe, und da hats funktioniert, war aber nicht so simpel geschrieben:
(ich hoffe, das zählt nicht unter 'Hausaufgaben, ich hätte ja auch nen xbeliebiges Programm ausm Internet nehmen können oder mein altes aber ich wollte es ja verständlicher schreiben nochmal')
import random as rd

def mod(a,m):
return a % m

def convdectobin(x,n=2):
l = []
while x != 0:
x,r = x//n,x%n
l.append(r)
print('converted')
return list(reversed(l))

def power(a,b,n): # with S&M
bb = convdectobin(b)
st = 1
for fig in bb:
st *= st
if fig == 1:
st *= a
st = mod(st,n)
print('solved! power')
return st

def isprime(n): # because the primes here are about 3 figs
if n < 2:
return False
prime = [True for i in range(n+1)]
p = 2
while p**2 <= n:
if prime[p] == True:
for i in range(p**2, n+1, p):
prime = False
p += 1
return prime[n]

def prime_generator():
# first prime is 2
yield 2
# starting from 3, check odd numbers for primality
n = 3
while True:
if isprime(n):
yield n
n += 2

primegen = prime_generator()
primegen1 = prime_generator()

def getRSAprimes():
a,b = 1,1
while a == b:
a,b = rd.randint(10,100),rd.randint(10,100)
if a > b:
a,b = b,a
b -= a
c = 1
while c < a:
c += 1
r = next(primegen1)
cb = 0
while cb < b:
cb += 1

def getRSAprimes():
a,b = 1,1
while a == b:
a,b = rd.randint(10,100),rd.randint(10,100)
if a > b:
a,b = b,a
b -= a
c = 1
while c < a:
c += 1
r = next(primegen)
cb = 0
while cb < b:
cb += 1
rb = next(primegen)
return [r,rb]

def EEA(a,b,ex=False):
x, y, u, v = 0, 1, 1, 0
while a != 0:
q, r = b // a, b % a
m, n = x - u*q, y - v*q
b, a, x, y, u, v = a, r, u, v, m, n
gcd = b
return [gcd, x, y] if ex else gcd

def getRSAkeys(p,q):
n = p*q
ph = (p-1)*(q-1)
te = [3,17,(2**16 + 1)]
rle = False
for e in te:
if EEA(e,ph) == 1:
rle = e
while not rle:
to = next(primegen)
if EEA(to,ph) == 1:
rle = to
if not rle:
print('ERROR')
return False
dcan = EEA(p,rle,True)[1]
d = mod(dcan,ph)
return [n,d,rle]

def writecrypt():
M = int(input('Message'))
e = int(input('coms key '))
n = int(input('coms n '))
Mr = mod(M,n)
if Mr != M:
print('changed your Message to:',Mr)
return power(Mr,e,n)

def getcrypt():
ps = getRSAprimes()
ks = getRSAkeys(ps[0],ps[1])
print('key',ks[2])
print('n',ks[0])
ct = int(input('crypt:'))
return power(ct,ks[1],ks[0])

die funktionen sollten selbsterklärend sein, sonst weiß ich hoffentlich später noch, was die machen.
Was jetzt falsch ist: ich hab mir selber eine Message geschickt und mit den öffentlichen Keys aus getcrypt() die Nachricht verschlüsseln lassen und das Chiffrat wieder in getcrypt() eingegeben, aber es kam nicht dasselbe heraus. Ich hab auch schon alle Funktionen getestet, die sollten alle funktionieren, wie ich sie haben will. Ich hab auch schon die Ausgabe vom EEA vertauscht, also mir den 'falschen' Linearfakto ausgeben lassen (Zeile 106, das indice von dcan von 2 zu 1 geändert) aber es kam immer noch das falsche heraus.
Kann mir hier vlt jemand helfen, den Fehler zu finden? Danke schonmal <3

[Sirius3]

Die Funktion `mod` ist überflüssig, da sie ja schon den %-Operator gibt. Es gibt auch schon die pow-Funktion. Wenn Du sie also nicht explizit erklären willst, dann benutze das, was es schon gibt.
Für eine einzelne Zahl ein Primzahlensieb aufzubauen ist fast etwas überflüssig, zumal das Sieb nur bis Wurzel n gehen muß. Ineffizient ist es, für jede Primzahl wieder ein neues Sieb aufzubauen, anstatt das schon vorhandene wieder zu verwenden.
`getRSAprimes` existiert zweimal.
Wenn man eine while-Schleife nur dann starten kann, wenn man vorher Zahlen irgendwelche Dummy-Werte gegeben hat, dann hat man eigentlich eine while-True Schleife.
Es ist Unsinn, wenn man zwei verschiedene Zufallszahlen haben möchte, immer beide Zahlen neu zu würfeln. Die restlichen while-Schleifen sind eigentlich for-Schleifen.
Man benutzt keine globalen Variablen.
Die Funktion könnte also so aussehen:

Code: Alles auswählen

def get_rsa_primes():
    a = rd.randint(10, 99)
    b = rd.randint(a + 1, 100)
    primegen = prime_generator()
    for _ in range(a):
        first_random_number = next(primegen)
    for _ in range(b):
        second_random_number = next(primegen)
    return first_random_number, second_random_number

Noch klarer wird es, wenn Du einfach ein paar Primzahlen ermittelst und daraus dann zwei ziehst:

Code: Alles auswählen

def generate_primes(n):
    primes = [False, False] + [True] * (n - 1)
    p = 2
    while p**2 <= n:
        if primes[p]:
            for i in range(p**2, n+1, p):
                primes[i] = False
        p += 1
    return [i for i, p in enumerate(primes) if p]

def get_rsa_primes():
    return rd.sample(generate_primes(100)[10:], 2)

Dass EEA für erweiterter_euklidscher_algorithmus steht, muß man wissen, besser wäre es, keine Abkürzungen zu benutzen. Das Flag ex ist überflüssig, denn ohne ex wäre es ja nur der normale euklidsche Algorithmus.
Die Methode, wie Du e bestimmst, ist etwas seltsam. Und Du beachtest nicht dabei, dass 1 < e < ph-1 gelten muß.
Eine Funktion sollte immer den selben Typ von Rückgabewert haben, für Fehler gibt es Exceptions. Das selbe gilt für `rle`, das mal ein Bool und mal eine Zahl ist.

Code: Alles auswählen

def erweiterter_euklidscher_algorithmus(a, b):
    x, y = 0, 1
    u, v = 1, 0
    while a != 0:
        q, r = divmod(b, a)
        b, a = a, r
        m, n = x - u*q, y - v*q
        x, y = u, v 
        u, v = m, n
    return b, x, y

def get_rsa_key(p, q):
    n = p * q
    phi = (p - 1) * (q - 1)
    for exponent in [17, 23, 47, 89]:
        if exponent  >= phi - 1:
            break
        ggt, d, k = erweiterter_euklidscher_algorithmus(exponent, phi)
        if ggt == 1:
            return n, d % phi, exponent 
    raise ValueError("keinen gültigen Exponenten gefunden")

Und hier der Test:

Code: Alles auswählen

In [6]: n, secret_key, public_key = get_rsa_key(59, 47)

In [7]: secret_key
Out[7]: 157

In [8]: public_key
Out[8]: 17

In [9]: pow(1918, public_key, n)
Out[9]: 2158

In [10]: pow(2158, secret_key, n)
Out[10]: 1918

[LucaMtG]

Danke dir für deine svhnelle Antwort. Ich hab mir das mal angeschaut, sollte jetzt funktionieren. Zu deinen Kritikpunkten: danke erstmal, dass du konstruktiv bleibst. Ich hatte in vielen Büchern, und ich dachte auch das in der Dokumentation gelesen zu haben, dass EEA eine gebräuchliche Abkürzung ist. In Zukunft werd ichs unmissverständlicher schreiben. Und die ganzen 'überflüssigen' Funktionen waren da, um das Thema in dem Virtrag besser zu erklären.
PS: Wollte mir das erstmal in Ruhe anschauen und daher kommt meine Antwort erst so spät.