Start / Kolumne / Schlüsselvereinbarung und Schlüsselaustausch

Startseite	Up-/Download	Tutorials	Club	Das Team
Rubriken	Foren	Bücher	Tips 'n Tricks	Suche

Schlüsselvereinbarung und Schlüsselaustausch

Inhalt

Ich gehe in dieser Kolumne vom folgenden Problem aus:
Es soll eine sichere Verbindung zwischen zwei Rechnern hergestellt werden, aus Geschwindigkeitsgründen soll hierbei jedoch eine symmetrische Verschlüsselung zum Einsatz kommen. Unser Problem besteht nun darin, dass bei diesen Verfahren beide Parteien den gleichen Schlüssel haben müssen. Irgendwie muss also ein Schlüssel übertragen werden, ohne dass ein möglicher Angreifer beim Abhören der Kommunikation den Schlüssel herausfinden kann. Die anfängliche Kommunikation erfolgt selbstverständlich unverschlüsselt, da ja noch kein gemeinsamer Schlüssel existiert.

Die möglichen Verfahren kann man in zwei Hauptkategorien einteilen:

Verfahren zur Schlüsselvereinbarung
Verfahren zum Schlüsselaustausch

Diffie-Hellman-Schlüsselvereinbarung

Ziel dieses Verfahren ist es, über einen offenen Kanal einen gemeinsamen Schlüssel zu definieren, der für die weitere Kommunikation genutzt werden kann. Dem Verfahren liegt folgende diskrete Exponentialfunktion zugrunde:

Abbildung 1

Die besonderen Eigenschaften diskreter Exponentialfunktionen seien hier nicht weiter erklärt auf Grund von Platzmangel, ich verweise jedoch auf das Thema "Modulare Arithmetik".

Das Protokoll läuft folgender Maßen ab:

Ein Teilnehmer wählt eine Primzahl p und eine natürliche Zahl g. Diese beiden Zahlen teilt er dem anderen Teilnehmer öffentlich mit. Diese Informationen können getrost öffentlich gehalten werden.
Jeder Teilnehmer wählt für sich selber eine geheime Zahl, wir nehmen die Zahlen a und b an (für die Parteien A und B)
Jede Partei bildet einen Wert durch Einsatz der Exponentialfunktion mit der geheimen Zahl und den beiden öffentlichen Zahlen. Diese Zahlen seien nun und .
Die kürzlich erzeugten Zahlen werden öffentlich ausgetauscht.
Nun potenziert jede Partei die vom anderen erhaltene Zahl mit der eigenen geheimen Zahl (i.e. für Partei A und für Partei B )

Nun haben wir einen gemeinsamen Wert k gefunden, der als Schlüssel für die weitere Kommunikation benutzt werden kann.

Beweis:

Zudem kennen nur die beiden Parteien A und B den Wert k, da ein Angreifer aus den Werten und nicht auf die geheimen Zahlen a und b schließen kann. Denn bis heute kennt man keine effiziente Methode zur Berechnung des diskreten Logarithmus.

Shamirs No-Key-Protokoll

Dieses Verfahren, das auf eine unveröffentlichte Arbeit von A. Shamir zurückgeht, ist zum Austausch einer geheimen Information gedacht, ohne dass die beiden involvierten Parteien (erneut A und B) den Schlüssel des anderen kennen. Die geheime Information sei in unserem Fall der Schlüssel k, welcher von der Partei A erzeugt wurde.

Auch dieses Protokoll stützt sich auf die diskrete Exponentialfunktion.

Jedoch existieren nun zwei geheime Zahlen pro Partei und es wird nur noch die Primzahl p öffentlich ausgetauscht. In unserem Falle legt die Partei A die Primzahl p fest und gibt sie B preis. Nun erzeugt A einen Verschlüsselungs- und einen Entschlüsselungsexponenten (a und a'), ebenso B (b und b'). Hierbei gilt folgendes:

und

Man sagt, dass Produkt beider Exponenten ist kongruent zu 1 modulo (p-1) reduziert. Konkret bedeutet dies, dass wir das multiplikative Inverse des Verschlüsselungsexponenten, welchen wir vorher willkürlich unter Beachtung einiger Regeln festgelegt haben, bilden müssen. Dies erledigt der erweiterte euklidische Algorithmus für uns (Stichwort Vielfachsummendarstellung), für weitere Erklärungen sei auch hier wieder auf das Thema "Modulare Arithmetik" verwiesen.

Folglich gilt:
und
für alle (Zahlenkörper p, alle Zahlen für die gilt ).

Das Protokoll läuft nun so ab:

Partei A bildet den Wert c mit der Formel und schickt diesen an B
Partei B bildet den Wert c nach der Formel und schickt die Zahl zurück an A
Momentan gilt:
A entfernt nun seine eigene Verschlüsselung:
Daraus folgt: , wobei c immer noch verschlüsselt ist! A übermittelt nun c an B.
B entfernt nun auch seinen Schlüssel und erhält die geheime Information

Das Verfahren ist korrekt, hier der Beweis:

Zudem ist das Verfahren sicher, da zu keinem Zeitpunkt der Übertragung über einen offenen Kanal die geheime Information k unverschlüsselt war. Auch hier beruht die Sicherheit des Verfahrens wieder auf der Schwierigkeit, den diskreten Logarithmus einer Zahl zu finden.

Beispielprojekt

Dieses Beispielprojekt zeigt die praktische Anwendung des Diffie-Hellman-Verfahrens.

Beispielprojekt

Von Robert Marquardt am 01.05.2008 um 07:30

Vielen Dank :)

Von HomerS am 17.06.2007 um 10:56

Dieses Verfahren, welches so weit ich weiß auch von Diffie-Hellman stammt, war garnicht erwähnt:
Es muss auch kein Schlüssel ausgetauscht werden, dafür leider oft der Text zwischen einander hin und hergeschickt werden:

#include <iostream>
#include <Windows.h>

using namespace std;

#pragma auto_inline (off)

#define ShowSteps (True)

class Subject
{
Private:
    char Key[1024];
    char Name[1024];

    void Encode  (char*, Const char*);
    void Decode  (char*, Const char*);
    void Transmit(Subject*, Const char*, Const int);

    
Public:
    Subject  (Const char*, Const char*);
    void Send(Subject*, Const char*);

};


// Main
int main()
{
    Subject Alice("Alice", "AlicesKey");
    Subject Bob("Bob", "BobsKey");


    Alice.Send(&Bob, "Hello, Bob");
    Bob.Send(&Alice, "Hello, Alice");


    cin.ignore();
    return 0;
}
// End of Main


void Subject::Transmit(Subject* sTo, Const char* Message, Const int Phase)
{
    char tmp[1024];
    strcpy(tmp, Message);
    
    If (ShowSteps && (Phase == 0)) cout << "Transmission from " << Name << " to " << sTo->Name << ":\n";
    switch (Phase)
    {
        Case (0):
        Case (1):
        {
            Encode(tmp, Key);
            If ShowSteps cout << tmp << endl;
            sTo->Transmit(this, tmp, Phase + 1);
        } break;
        
        Case (2):
        {
            Decode(tmp, Key);
            If ShowSteps cout << tmp << endl;
            sTo->Transmit(this, tmp, Phase + 1);
        } break;

        Case (3):
        {
            Decode(tmp, Key);
            If ShowSteps cout << endl;
            cout << Name << " gets a message from " << sTo->Name << " : " << tmp << endl << endl << endl;
        } break;
    }
}

void Subject::Encode(char* Text, Const char* Key)
{
    For (Long i = 0; i < strlen(Text); i++)
        Text[i] += Key[i % strlen(Key)];
}
void Subject::Decode(char* Text, Const char* Key)
{
    For (Long i = 0; i < strlen(Text); i++)
        Text[i] -= Key[i % strlen(Key)];
}
Subject::Subject(Const char* cName, Const char* cKey)
{
    strcpy(Name, cName);
    strcpy(Key, cKey);
}
void Subject::Send(Subject* Destination, Const char* Message)
{
    Transmit(Destination, Message, 0);
}

MFG, HomerS

Von Konrad Rudolph am 26.04.2003 um 12:52

Klasse Erklärung, Dominik! Diffie-Hellman wird wahrscheinlich in meiner Kommunikations-Dll zum Einsatz kommen. Die Erklärung spart mir einiges Rumgekrame im Mathebuch!

Erstellt: 03.02.2003 Aktualisierung: 03.02.2003		Autor: Dominik Auras E-Mail: neo@tipsntricks.de

Schlüsselvereinbarung und Schlüsselaustausch

Inhalt

Diffie-Hellman-Schlüsselvereinbarung

Shamirs No-Key-Protokoll

Beispielprojekt

Ihre Meinung