from random import randrange
import time

# Überprüft, ob die Zahl p prim ist
def isPrime(p):
    if p%2==0:
        return False
    f=3
    while (f*f<=p):
        if p%f==0:
            return False
        f+=2
    return True

# Sucht die nächste Primzahl p>=x so, dass (p-1)/2 auch prim ist 
# (sonst vereinfacht sich die Berechnung des diskreten Logarithmus)
def nextSophieGermainPrime(x):
    while not isPrime(x) or not isPrime((x-1)//2):
        x+=1
    return x

# Sucht die nächste Primzahl p>=x
def nextPrime(x):
    while not isPrime(x):
        x+=1
    return x

# Berechnet a^e % n
def modpow(a,e,n):
    prod = 1
    while e>0:
        if e%2==1:
            prod = (prod*a) % n
        a = (a*a) % n
        e = e//2  # Ganzzahlige Division
    return prod


# Exponent durch Probieren herausfinden
def discreteLog(a,r,p):
    print("Löse (%d ^ x) %% %d = %d durch Probieren..." % (a,p,r))
    tic = time.time()
    for e in xrange(p):
        if modpow(a,e,p)==r:
            toc = time.time()
            print("x=%d, Zeit zum Knacken: %.3fs" % (e, toc-tic))
            return e
    return -1

def schluesselTausch(basis=-1, modulus=-1, x=-1, ay=-1):
    if modulus==-1:
        modulus = nextPrime(1000000+randrange(100000))
    if basis==-1:
        basis = nextSophieGermainPrime(randrange(modulus-1000)+100)
        
    # Zufällige Zahl
    if x==-1:
        x = randrange(modulus-101)+100
    
    # Öffentliches a^x mod p
    ax = modpow(basis,x, modulus)    
    
    # Öffentliche Daten ausgeben
    print("basis=%d, modulus=%d, u=a^x=%d" % (basis, modulus, ax))
    
    if ay==-1:
        ay = inputInt("Geben Sie v=a^y vom Kommunikationspartner ein")
    # Geheimnis berechnen
    s = modpow(ay, x, modulus)

    # Ausgabe    
    print("\nMeine Zufallszahl war %d" % x)
    print("Geheimnis ist %d" % s)
    # Ausgabe verstecken
    print("\n"*20)
    # Öffentliche Daten ausgeben
    print("basis=%d, modulus=%d, u=a^x=%d, v=a^y=%d" % (basis, modulus, ax, ay))
    
def hacker(basis, modulus, ax, ay):
    # Exponenten vom ersten Kommunikationsparter durch Probieren finden
    x = discreteLog(basis, ax, modulus)
    # Geheimnis s = (a^y)^x  berechnen
    s = modpow(ay, x, modulus)
    print("Der geheime Schlüssel ist %d^%d = %d" % (ay,x, s))

    
#####################
### Programmstart ###
#####################        
    
schluesselTausch()    # Basis und Modulus (p) vom Kommunikationspartner eintragen

# hacker(276779 ,1007381, 942681, 5623)  # Basis, Modulus (p), a^x und a^y eintragen zum Knacken (s=644690)