Informatik - Kryptologie - Diffie-Hellman-Schlüsselaustausch

Kryptologie

Pfad: Startseite / Fächer / Informatik / Kryptologie / Schlüsseltausch

Autor: mk
27.09.2010 20:36
4830

Schlüsseltausch

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