#!/usr/bin/python
# -*- coding: Latin-1 -*-
# Wir implementieren den (erweiterten) Euklidschen Algorithmus
# und das Potenzieren durch sukzessive Quadrieren.

def gcd(m,n):
  """Der ggT der ganzen Zahlen m und n."""
  if n==0:
    return abs(m)  # damit ist der ggT immer positiv
  else:
    return gcd(n, m % n) # Euklidscher Algorithmus

def sgn(m):
   """Vorzeichen der ganzen Zahl m."""
   if m == 0: return 0
   elif m < 0: return -1
   elif m > 0: return 1

def xgcd(m,n):
  """Ganze Zahlen d,x,y, sodaß d = ggT(x,y) = m*x + n*y."""
  if n==0:
    return abs(m),sgn(m),0 # funktioniert so auch für m < 0
  else:
    q = m / n # Quotient (Ganzzahlige Division)
    r = m % n # passender Rest
    # Es gilt: m = q * n + r
    d,x,y = xgcd(n,r)
    # Es gilt: d=ggT(n,r)=ggT(m,n)
    # Und: d = n*x + r*y
    # Und daher: d = n*x + (m - q*n)*y
    #              = m*y + (x - y*q)*n
    return d, y, x - y*q

def invmod(e,m):
  """Das multiplikative Inverse von e modulo m."""
  d,x,y = xgcd(e,m)
  # es gilt d = e*x + m*y
  if d==1: return x % m

def powermod(x,e,m):
  """ x^e mod m """
  if e == 0:
    return 1
  elif e < 0:  # für neg Exponenten, x^(-e) = 1 / x^e
    return invmod(powermod(x,-e,m),m) 
  else:  # Sukzessives Quadrieren
    b = 2 # Die Formel funktioniert auch für andere b
    q = e / b
    r = e % b
    # Es gilt also e = q*b + r
    # Wir verwenden x^e = x^(q*b + r) = (x^q)^b * x^r
    return ( powermod(x,q,m)**b * x**r ) % m 

### Anmerkung: 
### Für das Potenzieren schreiben wir in Kommentaren x^e,
### in Python muss man aber x**e schreiben.

# Die Beispiele:

p = 341
print "Ist",p,"eine Primzahl?"
for b in [2,3]:
  print "Basis %d sagt:"% b, powermod(b,p-1,p)==1

print "\n\nRSA-Beispiel\n"
p = 11
q = 23
m = p*q
phi = (p-1)*(q-1)
print "m = %d = %d * %d, phi = %d" % (m,p,q,phi)

print "\nSuche passendes e:"
for e in [25,17]:
  print "e = %d, ggt(e,phi) = %d, geeignet:" %(e, gcd(e,phi)), gcd(e,phi)==1

e=17
d=invmod(e,phi)
print "e = %d; d = %d" % (e,d)
print "e * d = %d * %d = %d = %d (mod %d)" % (e,d,e*d, e*d % phi,phi)

print "\nGeheime Nachricht an Alice"
for x in [47,118]:
  print "x =", x
  y = powermod(x,e,m)
  print "Verschluesselung: y = x^e = %d^%d = %d (mod %d)" % (x,e,y,m)
  print "Entschluesselung: y^d = %d^%d = %d (mod %d)" % (y,d,powermod(y,d,m),m)

print "\nGeheime Nachricht an Bob"
m_ = 323
e_ = 5
print "Bobs oeffentlicher Schluessel: m' = %d, e' = %d" % (m_,e_)

x = 16
print "x =", x
y = powermod(x,e_,m_)
print "Verschluesselung: y = x^e' = %d^%d = %d (mod %d)" % (x,e_,powermod(x,e_,m_),m_)

print "\nAlice signiert"
x_ = powermod(x,d,m)
print "Signatur: x' = x^d = %d^%d = %d (mod %d)" % (x,d,x_,m)
y_ = powermod(x_,e_,m_)
print "Verschlüsselung: y' = x'^e' = %d^%d = %d (mod %d)" % (x_,e_,powermod(x_,e_,m_),m_)

print "\nBob's Schluessel knacken:"
print "Wir suchen die Faktoren von m' =",m_
p_ = 17   # für große Zahlen
q_ = 19   # schwer zu erraten
print "m' = %d = %d * %d = p'*q'" % (p_*q_,p_,q_)

phi_ = (p_-1)*(q_-1)
d_ = invmod(e_,phi_)

print "phi' = %d, d' = %d" % (phi_,d_)

print "\nNachricht fälschen:"
z = 66
print "z =",z
z_ = powermod (z,d_,m_)
print "Signieren: z' = z^d' = %d^%d = %d (mod %d)"  % (z,d_,z_,m_)
print "Carol erhält die Nachricht %d." % z_
print "und liest: z'^e' = %d^%d = %d (mod %d)" % (z_,e_,powermod(z_,e_,m_),m_)
print "Sie glaubt daher sicher sein zu koennen, dass sie von Bob stammt"
print "...und ist ganz traurig."



print "\n\nGroße Zahlen:\n"
# Ab mindestens Python 2.3 kann auch mit großen ganzen
# Zahlen gerechnet werden.

# einfacher Primzahltest

import random  # Modul für Zufallszahlengenerator
random.seed(5345345)  # überall dasselbe Ergebnis sicherstellen

def isprime (p,iter=1):
  """Test, ob p eine Primzahl ist (einfacher Fermat-Test)"""
  # iter muß nicht angegeben werden; 
  # wenn es fehlt wird der Vorgabewert 1 verwendet.
  if p==2: return True
  if p < 2: return False
  for i in [2,3,5,7,11,13,17,19]: #ein paar kleine Primzahlen testen
    if i<p and p % i == 0: return False
  # Fermat-Test: (iter-mal wiederholen
  for i in range(iter):
    b = random.randint(2,p-1)  # zufällige Zahl als Basis wählen
    if not (powermod(b,p-1,p) == 1): # Eigenschaft verletzt
       return False
    # ansonsten weitertesten

  # wenn nach iter Wiederholungen kein Wiederspruch gefunden wurde,
  # handelt es sich wahrscheinlich um eine Primzahl:
  return True

# Testen
for p in [17,18,341,42347889747234892347492346746474788484834939394834893]:
  print "Ist %d eine Primzahl?" % p, isprime(p)

def getprime(n,b=10):
  """Suche eine n-stellige (Basis b) Primzahl"""
  p = random.randint(b**(n-1),b**n - 1)
  if isprime(p):
    return p
  else:
    return getprime(n,b) # neuer Versuch


def nextprime(p):
  """Bestimme kleinste Primzahl groesser gleich p"""
  if isprime(p):
    return p
  else:
    return nextprime(p+1)

for p in [11,24,341,464634893939474589409]:
  print "%d ist groesser gleich %d und prim." % (nextprime(p),p)

for n in [1,2,3,10,50]:
  print "%d ist eine %d-stellige Primzahl" % (getprime(n),n)

def getpublic (phi):
  """Waehle ein e relativ prim zu phi"""
  e = random.randint(5,phi-1)
  # 2,3 sind sicher zu klein
  # 4 ist nicht relativ prim zu phi, weil dieses gerade ist
  # Daher muß auch phi > 6 sein, sonst Fehler
  if gcd(e,phi)==1:
    return e
  else:
    return getpublic (phi) # neuer Versuch

def getkey(p,q):
  """Liefere ein Schluesselpaar fuer m = p*q.  Resultat als (m,e,d)."""
  m = p*q
  phi = (p-1)*(q-1)
  e = getpublic(phi)
  d = invmod(e,phi)
  return m,e,d

def generateRSA(n,b=10):
  """Erzeue einen RSA-Schluessel mit n-stelligen Primzahlen"""
  p = getprime(n)
  q = getprime(n)
  if p==q:
    return generateRSA(n,b) # neuer Versuch
  # Für optimale Sicherheit wären noch weitere Bedingungen zu überprüfen.
  return getkey(p,q)

print "\n\nRSA Verfahren:"
for n in [2,10,50]: # für Sicherheit bei heutiger Technik: n=150 (1024 bit)
  print "\nmit %d-stelligen Primzahlen" % n
  m,e,d = generateRSA(n)
  print "Modul: m =",m
  print "Oeffentlicher Schluesel: e =", e
  print "Geheimer Schluessel: d =", d
  for i in range(2):
    x = random.randint(2,m-1)
    print "\nNachricht: x =",x
    y = powermod(x,e,m)
    print "Verschluesselt: y = x^d = %d ^ %d = %d (mod %d)" % (x,e,y,m)
    print "Test: y^d =",powermod(y,d,m)
    z = powermod(x,d,m)
    print "Signiert: z = x^d =", z
    print "Test: z^e =",powermod(z,e,m)
print generateRSA(2)