Interaktive Python-Programme zur Demonstration der RSA-Verschlüsselung auf grafischen Taschenrechnern (TI-Nspire und NumWorks): https://github.com/alexander-henkes/rsa-calculator-python

# RSA-Verschlüsselung: Mathematische Durchführung eines vollständigen Verschlüsselungsvorgangs

from math import gcd

# Primzahltest
def ist_prim(n):
  """Prüft, ob eine Zahl eine Primzahl ist"""
  if n<2:return False  # Zahlen kleiner 2 sind keine Primzahlen
  if n==2:return True  # 2 ist die einzige gerade Primzahl
  if n%2==0:return False  # Alle anderen geraden Zahlen sind keine Primzahlen
  # Teste nur ungerade Teiler bis zur Wurzel von n
  for i in range(3,int(n**.5)+1,2):
    if n%i==0:return False
  return True

# Primzahl-Eingabe mit Validierung
def eingabe_primzahl(name):
  """Fordert Benutzer zur Eingabe einer Primzahl auf und validiert die Eingabe"""
  while True:
    try:
      zahl=int(input('Primzahl '+name+': '))
      if zahl<2:print(str(zahl)+' ist zu klein!');continue
      if ist_prim(zahl):print('Gültige Eingabe: '+str(zahl)+' ist eine Primzahl!');return zahl
      else:print(str(zahl)+' ist keine Primzahl!')
    except:print('Ungültige Eingabe!')

# Erweiterter Euklidischer Algorithmus
def erweiterter_euklid(a,b):
  """Berechnet ggT und die Koeffizienten x, y für a*x + b*y = ggT(a,b)"""
  if b==0:return a,1,0
  else:g,x1,y1=erweiterter_euklid(b,a%b);x=y1;y=x1-a//b*y1;return g,x,y

# Modulares Inverses berechnen
def mod_inverse(e,phi):
  """Berechnet das modulare Inverse von e modulo phi"""
  g,x,y=erweiterter_euklid(e,phi)
  if g!=1:return  # Kein Inverses existiert, wenn ggT != 1
  return x%phi

# Modulare Exponentiation (effizient)
def potenz_mod(basis,exponent,modul):
  """Berechnet (basis^exponent) mod modul effizient"""
  ergebnis=1;basis=basis%modul
  while exponent>0:
    if exponent%2==1:ergebnis=ergebnis*basis%modul
    exponent=exponent>>1;basis=basis*basis%modul
  return ergebnis

# Geeignetes e finden
def finde_e(phi):
  """Findet ein geeignetes e, das teilerfremd zu phi ist"""
  kandidaten=[3,5,7,11,13,17,19,23,29,31]
  # Versuche zuerst kleine Primzahlen
  for e in kandidaten:
    if e<phi and gcd(e,phi)==1:return e
  # Falls keine passt, suche systematisch
  for e in range(2,phi):
    if gcd(e,phi)==1:return e

# Buchstabe in Zahl umwandeln
def buchstabe_zu_zahl(buchstabe):
  """Wandelt einen Buchstaben in eine Zahl um (A=0, B=1, ..., Z=25)"""
  buchstabe=buchstabe.upper()
  if'A'<=buchstabe<='Z':return ord(buchstabe)-ord('A')

# Zahl in Buchstabe umwandeln
def zahl_zu_buchstabe(zahl):
  """Wandelt eine Zahl in einen Buchstaben um (0=A, 1=B, ..., 25=Z)"""
  if 0<=zahl<=25:return chr(zahl+ord('A'))

# Hauptfunktion: RSA-Durchlauf
def rsa():
  # Ausgabe: Überschrift
  print('='*30);print('RSA-Verschlüsselung');print('='*30);print()

  # SCHRITT 1: Primzahlen wählen
  print('SCHRITT 1: Primzahlen wählen');print('-'*30)
  p=eingabe_primzahl('p')
  # Stelle sicher, dass q unterschiedlich von p ist
  while True:
    q=eingabe_primzahl('q')
    if q!=p:break
    print('Fehler: p und q müssen')
    print('verschieden sein!')
  print('Gewählt: p='+str(p)+', q='+str(q))
  input('Weiter mit Enter ...');print()

  # SCHRITT 2: n und phi(n) berechnen
  print('SCHRITT 2: n und phi(n)');print('-'*30)
  n=p*q  # Modul n = p * q
  phi=(p-1)*(q-1)  # Euler-Funktion phi(n) = (p-1)*(q-1)
  print('n = p*q = '+str(p)+'*'+str(q)+' = '+str(n))
  print('phi(n) = (p-1)*(q-1)')
  print('phi(n) = '+str(p-1)+'*'+str(q-1)+' = '+str(phi))
  input('Weiter mit Enter ...');print()

  # SCHRITT 3: Öffentlichen Schlüssel e bestimmen
  print('SCHRITT 3: Öffentlicher');print('Schlüssel e');print('-'*30)
  print('Hinweis: e muss teilerfremd zu')
  print('phi(n) = '+str(phi)+' sein, d. h. (ggT(e, phi(n)) = 1)')
  vorschlag=finde_e(phi)
  print('Vorschlag: e = '+str(vorschlag))
  antwort=input('Verwenden? (J/N): ')
  # Benutzer kann Vorschlag annehmen oder eigenes e eingeben
  if antwort.lower()=='j':e=vorschlag
  else:
    while True:
      e=int(input('Eigenes e verwenden: '))
      if e>=phi:print('e muss < '+str(phi)+' sein!');continue
      if gcd(e,phi)==1:print('Gültige Eingabe:');print('ggT('+str(e)+','+str(phi)+')=1');break
      else:print('ggT('+str(e)+','+str(phi)+')!=1')
  print('Öffentlicher Schlüssel: ('+str(e)+', '+str(n)+')')
  input('Weiter mit Enter ...');print()

  # SCHRITT 4: Privaten Schlüssel d berechnen
  print('SCHRITT 4: Privater');print('Schlüssel d');print('-'*30)
  print('d ist modulares Inverse')
  print('von e mod phi(n)')
  print('d*e = 1 (mod '+str(phi)+')')
  print('Berechne mit erweitertem euklidischen')
  print('Algorithmus:')
  d=mod_inverse(e,phi)
  print('d = '+str(d))
  # Überprüfung: d * e mod phi muss 1 ergeben
  print('Prüfung: '+str(d)+'*'+str(e))
  print('mod '+str(phi)+' = '+str(d*e%phi))
  print('Privater Schlüssel: ('+str(d)+', '+str(n)+')')
  input('Weiter mit Enter ...');print()

  # SCHRITT 5: Nachricht verschlüsseln
  print('SCHRITT 5: Verschlüsseln');print('-'*30)
  print('Verschlüsselung: c=m^e mod n')
  print('c = m^'+str(e)+' mod '+str(n))
  print()
  print('Buchstaben-Codierung:')
  print('A=0, B=1, C=2, ..., Z=25')
  print()
  # Buchstaben-Eingabe mit Validierung
  while True:
    buchstabe=input('Buchstabe (A-Z): ').strip()
    if len(buchstabe)==1:
      m=buchstabe_zu_zahl(buchstabe)
      if m is not None:
        if m<n:print("'"+buchstabe.upper()+"' = "+str(m));break
        else:print('Fehler: '+str(m)+' >= '+str(n));print('Wähle kleinere Primzahlen!')
      else:print('Ungültig! Bitte nur A-Z!')
    else:print('Nur einen Buchstaben!')
  # Verschlüsselung durchführen: c = m^e mod n
  c=potenz_mod(m,e,n)
  print()
  print('c = '+str(m)+'^'+str(e)+' mod '+str(n))
  print('c = '+str(c))
  print('Verschlüsselter Buchstabe: '+str(c))
  input('Weiter mit Enter ...');print()

  # SCHRITT 6: Nachricht entschlüsseln
  print('SCHRITT 6: Entschlüsseln');print('-'*30)
  print('Entschlüsselung:')
  print('m = c^d mod n')
  print('m = '+str(c)+'^'+str(d)+' mod '+str(n))
  # Entschlüsselung durchführen: m = c^d mod n
  m_neu=potenz_mod(c,d,n)
  buchstabe_neu=zahl_zu_buchstabe(m_neu)
  print('m = '+str(c)+'^'+str(d)+' mod '+str(n))
  print('m = '+str(m_neu))
  print('Entschlüsselter Buchstabe: '+str(buchstabe_neu))
  # Überprüfung: Stimmt der entschlüsselte Wert mit dem Original überein?
  if m==m_neu:print('Erfolgreich!')
  else:print('Fehler!')
  input('Weiter mit Enter ...');print()

# ZUSAMMENFASSUNG: Alle wichtigen Werte ausgeben
  print('='*30);print('ZUSAMMENFASSUNG');print('='*30)
  print('Primzahlen: p='+str(p)+', q='+str(q))
  print('Modul (p*q): n='+str(n))
  print('Eulersche Phi-Funktion: phi='+str(phi))
  print('Öffentlicher Schlüssel: ('+str(e)+','+str(n)+')')
  print('Privater Schlüssel: ('+str(d)+','+str(n)+')')
  print('Klartext (Buchstabe): '+buchstabe.upper())
  print('Klartext (Zahl): m='+str(m))
  print('Verschlüsselte Zahl: c='+str(c))
  print('Entschlüsselte Zahl: m='+str(m_neu))
  print('Entschlüsselter Buchstabe: '+str(buchstabe_neu))
  print('='*30)

# Potentielle Wiederholungsschleife
while True:
  rsa()  # Führe einen RSA-Durchlauf aus
  print()
  nochmal=input('Berechnung erneut durchführen? (J/N): ')
  if nochmal.lower()!='j':print('Programm beendet!');break
  print('\n'*2)