Kryptographie IV

Kategorie: Technik

Heutige Public Key-Verschlüsselungssysteme arbeiten mit abelschen Gruppen.

In Teil 1 hatten wir skizziert, um was es in der Kryptographie geht, nämlich darum Verschlüsselungsverfahren zu finden, die sich nur schwer entschlüsseln lassen.

In Teil 2 hatten wir dann berichtet, daß man heute meist Kombinationen aus Secret Key- und Public Key-Verfahren verwendet: man verwendet das Public Key-Verfahren zur Übermittlung des Schlüssels, und benutzt anschließend mit dem so übermittelten Schlüssel eines der gebräuchlichen Secret Key-Verfahren.

Die Frage ist nun also, wie man den Schlüssel so übermittelt, daß Sender A und Empfänger B sich auf einen Schlüssel einigen, ohne daß ein Lauscher den Schlüssel erfährt.

Eine Lösung zu diesem Problem ist der Diffie-Hellman-Schlüsselaustausch, den wir morgen in Teil 5 vorstellen werden.

Der Diffie-Hellman-Schlüsselaustausch, wie wohl alle heute üblichen Public Key-Verschlüsselungsverfahren, arbeitet mit der Voraussetzung, daß man die Buchstaben des Textes (bzw. die einzelnen Bites) bereits als Elemente einer abelschen Gruppe kodiert hat. (So wie wir in Teil 1 die Buchstaben mit ganzen Zahlen identifiziert hatten.) Heute wollen wir deshalb zur Vorbereitung den Begriff der abelschen Gruppe einführen.

(N.H.Abel war ein norwegischer Mathematiker des 19. Jahrhunderts. Orthographiebewußte werden sich fragen, warum es 'abelsche Gruppen' und nicht 'Abel'sche Gruppen' heißt. Der Grund ist, daß in der heutigen Mathematik 'abelsch' als Synonim für 'kommutativ' verwendet wird, auch in Zusammenhängen, von denen Abel noch nichts geahnt haben dürfte. Das Wort 'abelsch' gilt deshalb inzwischen als Adjektiv, nicht mehr als Eigenname.)

Wem das mit den Gruppen zu abstrakt wird, und wer lieber nur mit ganzen Zahlen rechnet, der kann den heutigen Teil auch überspringen. Ein Beispiel einer abelschen Gruppe sind die ganzen Zahlen, und man wird die kommenden Teile dieser Serie auch verstehen können, wenn man stets nur ganze Zahlen benutzt.

Allerdings sollte man wissen, daß Verschlüsselungssysteme, die mit ganzen Zahlen arbeiten, heute als unsicher gelten und deshalb kommerziell genutzte
Verschlüsselungssysteme kompliziertere abelsche Gruppen, z.B elliptische Kurven, benutzen.

Die ganzen Zahlen kann man, wie aus der Schule bekannt, addieren.
Formeller ausgedrückt: auf der Menge der ganzen Zahlen gibt es eine Addition, die je zwei Elementen a und b ein Element a+b zuordnet.
Diese Zuordnung erfüllt das Assoziativgesetz (a+b)+c=a+(b+c) und das Kommutativgesetz a+b=b+a. Außerdem gibt es die 0, für die a+0=a gilt, und zu jedem Element a gibt es ein Element -a, so daß a+(-a)=0 ist.

Eine Verallgemeinerung ist nun die allgemeine Definition von abelschen Gruppen. Per Definition ist eine Gruppe eine Menge G mit einer Verknüpfung +, die je zwei Elementen a und b ein Element a+b zuordnet, so daß gilt:

1. Assoziativgesetz: (a+b)+c=a+(b+c) für alle a,b,c aus G

2. Nullelement: es gibt ein 0 aus G, so daß a+0=a=0+a für alle a aus G gilt

3. Inverses Element: zu jedem a aus G gibt es ein -a, so daß a+(-a)=0=(-a)+a

Eine Gruppe G ist eine abelsche Gruppe, wenn zusätzlich gilt:

4. Kommutativgesetz: a+b=b+a für alle a,b aus G

Bekannte Beispiele abelscher Gruppen, neben den schon erwähnten ganzen Zahlen mit der üblichen Addition, sind natürlich die reellen Zahlen mit der üblichen Addition, oder zum Beispiel alle geraden Zahlen ebenfalls mit der üblichen Addition.

Dagegen sind die natürlichen Zahlen, selbst wenn man 0 zu den natürlichen Zahlen dazunimmt, keine Gruppe, weil Bedingung 3 nicht erfüllt ist.

Eine weitere abelsche Gruppe sind aber zum Beispiel die positiven reellen Zahlen mit der Multiplikation. Wenn man als Verknüpfung die Multiplikation wählt, muß man natürlich beachten, daß das neutrale Element jetzt 1 und das Inverse Element 1/a ist.

(Es hat in der Gruppentheorie eingebürgert, für allgemeine Gruppen die Verknüpfung meist mit dem Symbol o zu bezeichnen oder das Symbol ganz wegzulassen. Wenn es um abelsche Gruppen geht, wie in der Kryptographie immer der Fall, verwendet man aber das Symbol +.)

Autor: Thilo· 0 Kommentare· Permalink· Trackback-URL

Tags: Abelsche Gruppe· Public Key