 |
|||
| HSG |
|
Das Problem
Das ganze Problem der Schlüsselverteilung ist eine klassische Paradoxie. Wenn ein Mensch einem anderen eine geheime Nachricht am Telefon übermitteln will, muss er sie verschlüsseln. Dazu baucht er einen Schlüssel, der selbst wiederum ein Geheimnis ist, und so ergibt sich das Problem, diesen geheimen Schlüssel dem Empfänger zu übermitteln, damit die geheime Botschaft gesendet werden kann. Kurz, wenn zwei Menschen sich ein Geheimnis (eine verschlüsselte Botschaft) mitteilen wollen, müssen sie sich zuvor bereits ein Geheimnis (den Schlüssel) mitgeteilt haben.
aus: Simon Singh, Geheime Botschaften, S.311
Wer glaubt, dass das Problem unlösbar ist, soll sich diese Fotostory ansehen.
Der Diffie-Hellman-Schlüsseltausch
Ausschnitt aus krypto.py
def count(e,L):
return len([x for x in L if x == e])
def primpotenzen(n):
PF = primfaktoren(n)
MPF = set(PF)
return [(x,count(x,PF)) for x in MPF]
def phi(n):
"""
berechnet iterativ die Eulerfunktion
"""
PP = primpotenzen(n)
produkt = 1
for pp in PP:
produkt = produkt*(pp[0]**(pp[1]-1))*(pp[0]-1)
return produkt
def primitivwurzel(g,n):
"""
gibt genau dann True zurück, wenn g bezüglich n eine Primitivwurzel ist
"""
return len(set([(g**x)%p for x in range(1,n)])) == phi(n)
Python-Sitzung
>>> p=257 >>> primfaktoren(p) [257] >>> g=2 >>> primitivwurzel(g,p) False >>> g=3 >>> primitivwurzel(g,p) True >>> import random >>> a = random.randint(1,p-2) >>> a 235 >>> b = random.randint(1,p-2) >>> b 195 >>> A = (g**a)%p >>> A 218 >>> B = (g**b)%p >>> B 175 >>> (A**b)%p 3 >>> (B**a)%p 3 >>> (g**(a*b))%p 3
Aufgabe
Benutze krypto.py, baue und teste ein eigenes Diffie-Hellman-System.
Erläuterungen
Diffie-Hellman aus mathematischer Sicht von Carola Rauch, Christian Seise und Patrice Schwedler