Alice und Bob tauschen Schlüssel

Die beiden Informatiker Whitfield Diffie und Martin Hellman beschrieben das später nach ihnen benannte Verfahren bereits 1976. Es lässt sich in Kurzform und vorerst ohne den Einsatz elliptischer Kurven folgendermaßen beschreiben: Zwei Kommunikationspartner, in kryptographischer Tradition nennen wir sie Alice und Bob, wollen einen Schlüssel austauschen, um anschließend ihre Kommunikation zu verschlüsseln. Zunächst einmal haben sie dafür keinen sicheren Kanal. Ein neugieriger Angreifer könnte demnach alles mitlesen, was Alice und Bob hin- und herschicken.

Stellenmarkt
  1. Anwendungsentwickler JavaScript (m/w/d)
    ivv GmbH, Hannover
  2. Application SW Engineer Electric Vehicle Motion Control (m/w / divers)
    Continental AG, Nürnberg
Detailsuche

Daher einigen sich die beiden auf eine Primzahl p und eine Zahl g. Während g eine kleine Zahl sein kann, muss p möglichst groß sein. Das Bundesamt für Sicherheit in der Informationstechnik empfiehlt für eine Verwendung über das Jahr 2022 hinaus mindestens 3.000 Bit. Für ein kleines und nachvollziehbares Rechenbeispiel soll aber p hier 11 und g gleich 2 sein. Die beiden Werte können öffentlich bekannt sein, und in der Realität wählen Alice und Bob diese Zahlen auch nicht selbst aus, sondern nutzen standardisierte Werte.

Nachdem sie sich auf die öffentlichen Parameter verständigt haben, wählen beide im Geheimen jeweils eine zufällige Zahl, nennen wir sie a und b, die kleiner als p, also 11 ist. Alice wählt nun die 3, Bob die 5. Sie verraten sich die Zahlen gegenseitig nicht, stattdessen schickt Alice ihrem Kommunikationspartner das Ergebnis der Berechnung g^a modulo p. Modulo bedeutet vereinfacht gesagt: Der Wert wird durch p geteilt, hier 11, und der ganzzahlige Rest ist das Ergebnis.

Das Diskreter-Logarithmus-Problem

Alices Ergebnis lautet: 2^3 mod 11, also 8. Bob kommt auf den Wert 10, denn 2^5 ist 32, geteilt durch 11 bleibt ein Rest von 10. Die beiden Kommunikationspartner verraten sich ihre Rechenergebnisse gegenseitig. Wenn Alice nun die von Bob gesendete Zahl 10 hoch ihrer geheimen Zahl 3 rechnet - wieder modulo 11 - erhält sie den Wert 10. Rechnet Bob die Zahl von Alice hoch 5 kommt er zum gleichen Ergebnis: Die 10 ist ihr gemeinsames Geheimnis, und das kann niemand leicht berechnen - vorausgesetzt, p ist groß genug. Denn dafür müsste der Angreifer einen diskreten Logarithmus bilden können, also die Umkehrfunktion der Potenz.

Golem Akademie
  1. IT-Sicherheit für Webentwickler: virtueller Zwei-Tage-Workshop
    19./20.05.2022, Virtuell
  2. First Response auf Security Incidents: Ein-Tages-Workshop
    14.11.2022, Virtuell
Weitere IT-Trainings

Bei positiven, reellen Zahlen wäre es erst einmal kein großes Problem, den Logarithmus zu bilden. Vielleicht erinnern sich einige noch an Beispiele aus der Schulmathematik und Näherungsrechnungen. Anders sieht das aus, wenn wir eben nicht reelle Zahlen als Grundlage nehmen, sondern - nicht gleich wegklicken - prime Restklassengruppen wie oben im Beispiel.

Was heißt nun prime Restklassengruppe? Eine Gruppe im Allgemeinen ist nicht viel mehr als eine Menge an Elementen, sagen wir verkürzt der Einfachheit halber Zahlen, die bestimmte Bedingungen erfüllen. Unter anderem muss es eine Verknüpfung zwischen jeweils zwei Zahlen geben, die als Ergebnis wieder eine Zahl der Gruppe ergeben. Nehmen wir an, wir nutzen ganze Zahlen als Menge und nennen die Verknüpfung Addition. 50 addiert mit 13 ist 63, 63 ist ein Element der ganzen Zahlen: Das passt.

Wie auf dem Ziffferblatt einer Uhr

In einer Restklassengruppe modulo 60 ist 50 addiert mit 13 aber 3, denn die Menge an Elementen, die uns zur Verfügung steht, besteht nur aus der 0, 1, 2 bis 59. Eine Analogie dazu wäre der Sekundenzeiger einer Uhr, der nach dem 59. Segment einfach wieder bei der 0 anfängt. Die 3 ist dann der Rest des Teilens durch 60.

Für die Kryptographie sind besonders prime Restklassengruppen modulo einer Primzahl - wie die 11 - interessant, die als Operation die Multiplikation benutzen und einen Generator haben, der auch eine Primzahl ist. Ein Generator ist ein Element, mit dem sich alle anderen Elemente der Gruppe erzeugen lassen. In unserem Alice-und-Bob-Beispiel war der Wert g dieser Generator, also die 2. Potenzieren wir die 2 mit allen anderen Elementen der Gruppe, kommt jedes Element einmal als Ergebnis vor. Die Gruppe lässt sich also mit der 2 generieren.

Diese Restklassen machen es so schwer, den diskreten Logarithmus herauszufinden. Denn wenn ein Zahlenraum, salopp gesagt, immer wieder von vorne anfängt, springen die Ergebnisse. Bei 2^3 mod 11 ist es 8, 2^4 mod 11 = 5 und 2^5 mod 11 ergibt 10.

Man kann erahnen, warum es da so schwer ist, die Ergebnisse abzuschätzen.

Bitte aktivieren Sie Javascript.
Oder nutzen Sie das Golem-pur-Angebot
und lesen Golem.de
  • ohne Werbung
  • mit ausgeschaltetem Javascript
  • mit RSS-Volltext-Feed
 Elliptische Kurven: Alice und Bob legen sich in die KurveElliptische Kurven sehen nicht aus wie Ellipsen 
  1.  
  2. 1
  3. 2
  4. 3
  5. 4
  6. 5
  7.  


jo-1 28. Aug 2018

sehr nett! Den Spruch merke ich mir ;-) Finde den Artikel aus 2015 hierzu übrigens sehr...

corruption 24. Aug 2018

Stimmt. Man kann z.B. bei DH zeigen, dass es mind. so schwer ist wie das Problem des...

corruption 24. Aug 2018

Im Endeffekt sind beides doch sogenannte "Hidden Subgroup Problems" über eine abelsche...

neokawasaki 19. Aug 2018

Dem kann ich mich anschließen. Unter anderem durch die Faszination an asymmetrischer...



Aktuell auf der Startseite von Golem.de
Forschung
Blaualge versorgt Computer sechs Monate mit Strom

Ein Forschungsteam hat einen Mikroprozessor sechs Monate ununterbrochen mit Strom versorgt. Die Algen lieferten sogar bei Dunkelheit.

Forschung: Blaualge versorgt Computer sechs Monate mit Strom
Artikel
  1. EC-Karte: Trotz Kartensperre können Diebe stundenlang Geld abheben
    EC-Karte
    Trotz Kartensperre können Diebe stundenlang Geld abheben

    Eine Sperre der Girocard wird nicht immer sofort aktiv. Verbraucher können sich bereits im Vorfeld schützen.

  2. Milliarden-Übernahme: Musk spricht von günstigerem Übernahmeangebot für Twitter
    Milliarden-Übernahme
    Musk spricht von günstigerem Übernahmeangebot für Twitter

    Mit Blick auf die Zählung von Spam-Konten bei Twitter hat Elon Musk gefragt, ob die mehr als 200 Millionen Twitter-Nutzer angerufen worden seien.

  3. Raspberry Pi: Besser gießen mit Raspi und Xiaomi-Pflanzensensor
    Raspberry Pi
    Besser gießen mit Raspi und Xiaomi-Pflanzensensor

    Wer keinen grünen Daumen hat, kann sich von Sensoren helfen lassen. Komfortabel sind sie aber erst, wenn die Daten automatisch ausgelesen werden.
    Eine Anleitung von Thomas Hahn

Du willst dich mit Golem.de beruflich verändern oder weiterbilden?
Zum Stellenmarkt
Zur Akademie
Zum Coaching
  • Schnäppchen, Rabatte und Top-Angebote
    Die besten Deals des Tages
    Daily Deals • LG OLED TV (2021) 77" günstig wie nie: 1.771,60€ statt 4.699€ • Grakas günstig wie nie (u. a. RTX 3080Ti 1.285€) • Samsung SSD 1TB (PS5-komp.) + Heatsink günstig wie nie: 143,99€ • Microsoft Surface günstig wie nie • Jubiläumsdeals MediaMarkt • Bosch Prof. bis 53% günstiger[Werbung]
    •  /