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)