Posted on

RSA-Algorithmus für den Unterricht

Vollständiger Python-Quellcode

import math
import random

# primzahlen erzeugen
obergrenze = 100
primliste = [2] #Initialisierung Primzahlarray
for i in range(3,obergrenze,2):
    teilbar = False
    for j in range(2, math.ceil(math.sqrt(i))+1):
        if(i/j == i//j):
            teilbar = True
            break
    if(not teilbar):
        primliste.append(i)
print("Primzahlen zwischen 0 und",obergrenze,": ",primliste)

# Öffentlichen Modulus und Eulersche Phi-Funktion davon
p = primliste[random.randint(0, len(primliste)-1)] #zufällige Auswahl
primliste.remove(p) #Sicherstellen, dass p und q unterschiedlich
q = primliste[random.randint(0, len(primliste)-1)] #zufällige Auswahl
print("zufällig ausgewähltes p: ", p, "und q: ", q)
phiVonN = (p-1)*(q-1)
print("Phi(N): (",p,"- 1 ) * (",q,"- 1 ) = ", phiVonN, "\n")
N = p*q #öffentlicher Modulus
print ("** öffentlicher Modulus:" ,N)

# mit größtem gemeinsamen Teiler den öffentlichen Schlüssel bestimmen
def ggt(a,b): #Euklidischer Algorithmus
    if b==0:
        return a
    return ggt(b,a%b)

e = 2 #Initialisierung mit Startwert
while ggt(e,phiVonN)!=1: #BrutForce Gleichung lösen
    e = e + 1
print("** öffentlicher schlüssel: ", e)

# privaten Schlüssel bestimmen
d = 2 #Initialisierung mit Startwert
while (d*e)%phiVonN!=1: #Nochmal BruteForce
    d = d + 1
print("** privater schlüssel: ", d)

klarzahl = 42 #irgendeine Zahl...
if klarzahl<(N-1):
    geheimzahl = pow(klarzahl,e,N)
    neueklarzahl = pow(geheimzahl,d,N)
    print("\nklarzahl:", klarzahl,
          "\ngeheimzahl:", geheimzahl,
          "\nentschlüsselt: ", neueklarzahl)
else:
    print("öffentlicher Modulus ", N, "ist kleiner als ", klarzahl, "+1")