Ravest-Shamir-Adleman-Algorithmus history menue Letztmalig dran rumgefummelt: 16.11.15 16:31:50

Public-Key-Systemen, die seit 1976 entwickelt werden. Das bekannteste unter ihnen, das RSA-Verfahren (nach R. RIVEST, A. SHAMIR und L. ADLEMAN), verwendet die Primfaktorenzerlegung natürlicher Zahlen sowie Modula-Operationen. Es ist nur so lange sicher, wie es keine wesentlich schnelleren Algorithmen zur Primfaktorenzerlegung gibt als die heute bekannten. Daneben setzt es die Kenntnis genügend vieler hinreichend großer (also eher sehr großer!!!) Primzahlen voraus.
1. Funktionsprinzip des RSA-Verfahrens
2. Vorläufer des RSA-Algorithmus Diffie, Hellman und Merkle
3. Einfache und komplexe mathematische Einwegfunktionen
4. Der Data Encryption Standard - kurz: DES
5. HASH-Funktionen
6. Trapdoors
7. MD4- bzw. MD5-Algorithmus
8. Verwandte Themen

die Informatikseiten

RSA-Verfahren & Einwegfunktionen-Logo

inhaltlich auf korrektem Stand - evtl. partiell unvollständig ;-)

Wissen für Fortgeschrittene der Informatik

Informatik-Profi-Wissen


1. Funktionsprinzip des RSA-Verfahrens für Kleine Kryptographen history menue scroll up

Grundlage des RSA-Verfahrens sind mathematische Einwegfunktionen. In der einen Richtung müssen sie ganz einfach lösbar, in der anderen theoretisch nicht mehr in sinnvoller Zeit realisierbar.
Den Namen hat das Verfahren von Ronald Rivest, Adi Shamir und Leonard Adleman, den drei Männern, die es 1977 erfunden haben. RSA ist ein asymmetrisches Verfahren, es gibt also einen public key und einen private key. Beide werden über Primzahlen gebildet. Außerdem geht in das Verfahren die Modulo-Rechnung ein.
Die grundsätzliche Idee lautet: verschlüsseln kann jeder - entschlüsseln lediglich authorisierte Personen (das sind diejenigen, welche den geheimen Schlüssel besitzen)
Vor- und Nachteile des Verfahrens
  • es muss kein Schlüssel ausgetauscht werden
  • der Schlüssel ist sehr sicher
  • es handelt sich in der Grundversion jedoch um eine monoalphabetische Substitutions-Chiffre
  • dieser ist in sich so anfällig, wie ein CÄSAR-Chiffre
  • zum Knacken des Chiffre benötige ich gar keinen Chiffre - das erledigt eine relativ einfache Häufigkeitsanalyse
Wie funktioniert der RSA-Verschlüsselungsalgorithmus?

Die Caesarverschiebung ist das klassische Beispiel eines konventionellen, so genannten symmetrischen Verschlüsselungsalgorithmus: Sowohl dem Sender als auch dem Empfänger der geheimen Nachricht ist der Schlüssel e bekannt (und damit auch der zweite Schlüssel d, der sich leicht aus e berechnen lässt). Das bedeutet aber, dass der geheime Schlüssel e zwischen Sender und Empfänger zunächst ausgetauscht werden muss, bevor verschlüsselt werden kann. Steht nun für diesen Austausch kein sicherer Weg zur Verfügung, sondern nur ein öffentliches Medium wie z. B. das Internet, dann wird eine sichere Schlüsselvereinbarung zwischen Sender und Empfänger ein Problem.
Eine Alternative bieten so genannte asymmetrische oder Public Key Verschlüsselungsverfahren. Hier besitzt jeder Teilnehmer zwei Schlüssel: einen privaten Schlüssel (private key), den er geheim hält, und einen öffentlichen Schlüssel (public key), der aller Welt bekannt gegeben wird (wie eine Telefonnummer in einem Telefonbuch).
Wenn Sie mir nun eine geheime Nachricht senden möchten, schlagen Sie einfach im entsprechenden öffentlichen Verzeichnis meinen öffentlichen Schlüssel e (encrypt engl. verschlüsseln) nach, verschlüsseln damit die Nachricht und senden sie dann als Email an mich. Da nur ich den zugehörigen geheimen Schlüssel d (decrypt i engl. entschlüsseln) kenne, bin nur ich in der Lage, dieses Email wieder zu entschlüsseln.
Nun liegt es aber in der Natur der Sache, dass der Zusammenhang zwischen der originalen und der verschlüsselten Nachricht eindeutig sein muss, und daraus kann man ableiten, dass auch der geheime Schlüssel d prinzipiell aus (lern öffentlichen Schlüssel e berechenbar sein muss. Es scheint also, dass es ein solches Verschlüsselungsverfahren nicht geben kann. Theoretisch ist das auch so. Praktisch aber reicht es schon aus, wenn die Berechnung von d aus e einfach so langwierig ist, dass man se auch mit den schnellsten Computern nicht innerhalb praktischer Zeitgrenzen durchführen kann. Das lässt sich mit einer so genannten Einwegfunktion realisieren: Sie kann in eine Richtung (x F--> y = f (x), also Ermittlung des Funktionswertes bei gegebenem x) leicht berechnet werden, in die andere Richtung (y = f (x) H x) praktisch nicht.
Beispiel für eine Einwegfunktion ist die Zuordnung Name x - Telefonnummer f (x) in einem Telefonfonbuch. Die eine Richtung ist kein Problem, nämlich zu einem gegebenen Namen die zugehörige Telefonnummer zu finden. Die umgekehrte Richtung, also zu einer gegebenen Telefonnummer den hörigen Namen zu finden, dauert dagegen um ein Vielfaches länger!
Wo soll man aber eine solche Funktion hernehmen? Dazu hatten die Mathematiker Ronald Rivest und Adi Shamir und der Computerwissenschaftler Leonard Adleman Jahr 1978 die zündende Idee: Die Einwegeigenschaft des nach ihnen benannten A-Verschlüsselungsalgorithmus beruht darauf, dass die Multiplikation von Primzahlen fast keine Rechenzeit in Anspruch nimmt, während aber die Zerlegung einer gegebenen Zahl in ihre Primfaktoren im Vergleich dazu um ein Vielfaches länger benötigt!

Hier nun der RSA-Algorithmus, der die eingangs geforderten Eigenschaften besitzt:
  • Schlüsselerzeugung: Möchten Sie verschlüsselte Nachrichten empfangen, so erzeugen Sie folgendermaßen einen öffentlichen und einen privaten Schlüssel:
  • wählen Sie zwei verschiedene Primzahlen p, q
  • ermitteln Sie daraus die Zahlen n = p q und m = (p - 1) (q - 1)
  • wählen Sie eine Zahl e, die teilerfremd zu m ist
  • berechnen Sie die Zahl d, die e d = 1 (mod m) erfüllt (also das multiplikative Inverse von e modulo m)
  • geben Sie die Zahlen (n, e) als öffentlichen Schlüssel bekannt
  • die Zahlen (n, d) behalten Sie als geheimen Schlüssel
  • p, q und m werden nicht mehr benötigt (bleiben aber geheim!).
Verschlüsselung:

Wenn Ihnen nun jemand eine verschlüsselte Nachricht schicken möchte, so schlägt er Ihren öffentlichen Schlüssel (n, e) nach, verschlüsselt den Klartext x gemäß y = xe (mod n), und schickt den Geheimtext y an Sie.
Die Verschlüsselungsvorschrift ist dabei eine Abbildung von 9d„ nach 9G„ und die Entschlüsselungsvorschrift ist die zugehörige Umkehrabbildung. Insbesondere muss also die Nachricht zuvor in eine Zahl kleiner als n umgewandelt werden (bzw. in eine Anzahl von Blöcken, die kleiner als n sind).

Entschlüsselung:

Zum Entschlüsseln verwenden Sie Ihren geheimen Schlüssel (n, d) und berechnen damit den Klartext gemäß x = yd (mod n).
Dass wirklich yd = (XP)d = x`d(mod n) x gilt, ist an dieser Stelle noch nicht unmittelbar einsichtig, kann aber mithilfe eines Satzes des französischen Mathematikers Fernrat (Kleiner Fermat) bewiesen werden.
Natürlich ist es prinzipiell möglich, den geheimen Schlüssel (n, d) aus Kenntnis des öffentlichen Schlüssels (n, e) zu berechnen, indem man die Gleichung
e d = 1 (mod rri) löst. Da aber m = (p - 1) (q - 1) geheim ist, muss man zur Ermittlung von m zuerst die Primfaktoren p und q von n bestimmen. Sind die beiden Primfaktoren geeignet gewählt (insbesondere genügend groß), so wird aber auch der heutzutage schnellste Computer das Zeitliche segnen, bevor er mit der Primfaktorzerlegung fertig ist. Die Sicherheit des RSA-Algorithmus hängt also von der verwendeten Schlüssellänge ab (die der Größe der Primzahlen entspricht). Das bedeutet natürlich, dass eine Schlüssellänge, die heute als sicher gilt, aufgrund der steigenden Rechnerleistung in einigen Jahren schon nicht mehr sicher ist!
Außerdem wäre es möglich, dass jemand einen schnelleren Algorithmus (der polynomial von der Größe der Zahl n abhängt) zur Primfaktorzerlegung findet, und in diesem Fall wäre die Sicherheit des RSA-Algorithmus endgültig dahin. Mathematiker versuchen deshalb zu beweisen, dass es einen solchen Algorithmus nicht geben kann.
Nun gleich zu einem Beispiel:

Verschlüsselung mit dem RSA-Algorithmus
Die Nachricht „KLEOPATRA" soll mit dem RSA-Algorithmus verschlüsselt an einen Empfänger geschickt werden, dessen öffentlicher Schlüssel (n, e) (1147, 29 ist. Wandeln Sie zuvor die Nachricht so wie in Beispiel oben in Ziffern um.

  • wie lautet der Geheimtext?
  • entschlüsseln Sie den Geheimtext (d = 149).
  • versuchen Sie, den geheimen Schlüssel (n, d) aus der Kenntnis des öffentlicher. Schlüssels (n, e) zu berechnen.

Lösung zu oben:

In Zahlen lautet KLEOPATRA: 11, 12, 5,15,16, 1,20,18, 1. Verschlüsseln wir jede dieser Zahlen x gemäß y = x29 (mod 1147):
 

RSA-Algorithmus - das Prinzip Teil I

RSA-Algorithmus - das Prinzip Teil II

RSA-Algorithmus - das Prinzip Teil III

RSA-Algorithmus - das Prinzip Teil IV

RSA-Algorithmus - das Prinzip Teil V

RSA-Algorithmus - das Prinzip Teil VI

   
Abfolge für den RSA-Algorithmus ...
Eingangsgrößen Chiffrierverfahren Dechiffrierverfahren
Als Algorithmen werden benötigt:
  • Modulo-Operationen
  • Finden wirklich sehr große Primzahlen
  • Teilbarkeitsregeln

Als Größen müssen vereinbart werden:

  • P (möglichst große Primzahl)
  • Q (möglichst große Primzahl)

woraus resultieren:

  • M  (Produkt aus (P-1) und (Q-1))
  • N (Produkt aus P und Q)
Als Algorithmen gehen ein:
  • Wert für E
  • Wert für M
  • Beherrschen der Modulo-Operationen

Als Größen werden benötigt:

  • Wert für E
  • Wert für M
  • Beherrschen der Modulo-Operationen
Als Algorithmen gehen ein:
  • Modulo-Operationen
  • Primzahlen
  • Teilbarkeitsregeln

eine gute Möglichkeit, den RSA-Algorithmus zu verstehen

Vorbereitungen zum chiffrieren bzw. Dechiffrieren ...
  • in der Praxis sind die festzulegenden Primzahlen P und Q groß, ja sehr groß - wir sprechen von 100 und mehr Stellen
  • sie stellen praktisch die Einwegfunktion dar - diese Zahlen zu finden und miteinander zu multiplizieren, ist relativ einfach - umgekehrt die Faktoren zu finden, praktisch nicht mehr möglich
  • für unsere Demonstrationen verwenden wir nur relativ kleine Primzahlen, da die Zwischenwerte auch damit schon enorm groß werden
  • aus den ermittelten Primzahlen werden die Produkte N sowie mit P-1 und Q-1 M
  • N wird Bestandteil des "Public Keys"
  • M wird in seine Primfaktoren zerlegt
  • die Zahlen P und Q sind nach Abschluss aller Schritte für das Chiffrierverfahren selbst nicht mehr von Bedeutung - sie bleiben aber geheim!
  • wir bestimmen in der Folge den Privat-Key- er muss geheim gehalten werden
  • dabei steht die Bezeichnung "E" für "encrypt" - entschlüsseln
  • er ist in jedem Falle eine Primzahl im Bereich 2 ≤ E < M und ist kein Primfaktor von M
  • für das Beispiel P=11 sowie Q=17 und M=160 sowie N=187 mögliche Werte: 3,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,102, 107,109,127,131,137,139,149,151,157 - dabei sind die Primfaktoren für 160 schon ausgelassen
  • wir bestimmen in der Folge den Public-Key - er muss veröffentlicht werden
  • dabei steht die Bezeichnung "D" für "decrypt" - also verschlüsseln
  • er wird durch ein Produkt mit eines Zahl X  mit M+1 dividiert durch E bestimmt

Bestimmung zweier Primzahlen P sowie Q

Generierung und Festlegung des "Encrypt"-Wertes E - das ist der Private-Key

Generierung und Festlegung des "Decrypt"-Wertes D - das ist der Public-Key

Primzahlsuche ...

verwende einen effizienten Algorithmus zur Primzahlsuche

Primfaktorirung ...

Bestimmung der Primfaktoren

Ermittlung des öffentlichen Schlüssels ...

Ermitteln eines möglichen "Public-Keys"

Alphabet und Zeichenpositionen - werden sowohl zum Chiffrieren als auch Dechiffrieren benötigt Chiffrieren - also Verschlüsseln Dechiffrieren - also Entschlüsseln

Zeichenpositionen im Alphabet

Chiffrieren mit RSA

Dechiffrieren mit RSA

... und das Beispiel:
Werte Alphabetische Zuordnung Encrypt - Chiffriren - also Verschlüsseln Decrypt - Dechiffriren - also Entschlüsseln
  • P = 11
  • Q = 17
  • N = 187 (Bestandteil des "Public- sowie des Privat-Keys")
  • M = 160
  • E = 7 (Bestandteil des "Public-Keys")
  • D = 23 (Bestandteil des "Privat-Keys")

Zeichenpositionen im Alphabet

Chiffrieren mit RSA

Dechiffrieren mit RSA

Plaintext zu Ciphertext
Character A L L E S K L A R A U F D E R A N D R E A D O R I  A
Plain 01 12 12 05 19 11 12 01 18 01 21 06 04 05 18 01 14 04 18 05 01 04 15 18 09 01
RSA 01 177 177 146 145 88 177 01 171 01 98 57 115 146 171 01 108 115 171 146 01 115 93 171 70 01

... mit den obigen Zahlen einmal den RSA zum Chiffrieren nachvollzogen - bewusst mit kleinen Zahlen :-)

 Ciphertext zu Plaintext
RSA 01 177 177 146 145 88 177 01 171 01 98 57 115 146 171 01 108 115 171 146 01 115 93 171 70 01
Plain 01 12 12 05 19 11 12 01 18 01 21 06 04 05 18 01 14 04 18 05 01 04 15 18 09 01
Character A L L E S K L A R A U F D E R A N D R E A D O R I  A

... mit den obigen Zahlen einmal den RSA zum Dechiffrieren nachvollzogen - bewusst mit kleinen Zahlen :-)

Berechnung aller Daten Anwendung mit bekannten Daten und unbekanntem Privat-Key des Zieles

... das benötigt der Verfasser eines Public-Keys

... das benötigt der Verfasser eines Public-Keys

... das benötigt der Versender

... das benötigt der Verfasser eines Public-Keys

Hier hat uns Herr Rainer Gürth auf der Informatiklehrerkonferenz am 12.11.05 in Dresden einige unschlagbar wertvolle Tipps zu Arbeit gegeben und diese Materialien großzügigerweise verfügbar für unsere Unterrichtsarbeit gemacht.

Übungsblatt zum RSA-Algorithmus

Übungsblatt zum RSA-Algorithmus als PDF-Datei

Rechenblatt zum RSA-Algorithmus

Download des EXCEL-Rechenblatt zum RSA-Algorithmus

Der Windows-Taschenrechner im wissenschaftlichen Modus ist neben Mathematica die einzige Software-lösung, welche ohne Rundungsfehler auch mit wirklich großen Zahlen umgehen kann ;-)

 
Basis der gesamten Verfahren sind die Primzahlen - in der Praxis natürlich sehr große ...
Primzahlsuche ... Zahlenteiler ... Primzahlfaktorisierung ...

die Primzahlsuche - zumindest die ersten Beschreibungen sind trivial ;-)

die Zahlenteiler

Primzahlfaktorisierung

Brute-Force-Methode beim Herausfinden der ersten 37434 Primzahlen

das Feststellen, ob eine Zahl eine Primzahl ist, ist trivial auch für große Zahlen

Finden aller ganzzahligen Teiler einer Zahl

startbares Programm zum Ermitteln der Primzahlfaktoren auch für ziemlich große Zahlen

Ermitteln eines möglichen "Public-Keys"

der Windows-Taschenrechner

 


2. Vorläufer des RSA-Algorithmus - Withfield Diffie, Hellman und Merkle  - Gott belohnt die Ausdauernden und Verrückten history menue scroll up

Ziel ist es, eine Zustandsveränderung von Systemen zu erreichen, welche nicht wieder oder nicht so einfach wieder in ihren Ausgangszustand versetzt werden können.


3. Einfache und komplexe mathematische Einwegfunktionen history menue scroll up
 
Suchen wir in unserer Umgebung doch einmal nach Einwegfunktionen
  • Zerschlagen eines Eis - das Ei ist faktisch nicht wieder zu reparieren
  • Beton mischen - versuch' mal, Wasser, Sand sowie Zement wieder daraus zurück zu bekommen - geht nicht
  • einen Bleistift anspitzen - versuchen wir, aus den vielen Spänen einmal den kompletten Bleistift wieder zurück zu gewinnen
In der Natur finden wir zahllose Vorgänge, welche nicht  (oder zumindest für uns und derzeit nicht!) umkehrbar sind. Mathematisch ist das bereits nicht mehr ganz so einfach, dies gilt zumindest seit der Zeit, in welcher Computer mit hinreichend Rechenleistung verfügbar waren. Zwei wesentliche Stützen bleiben uns heute:


4. Der Data Encryption Standard - kurz: DES history menue scroll up

DES, der Data Encryption Standard, ist ohne Frage das am besten untersuchte kryptografische Verfahren. Moderne Entwurfsprinzipien und moderne Kryptanalyse haben wir wesentlich diesem Algorithmus zu verdanken.
Obwohl der Verdacht, die NSA könnte in DES eine Hintertür eingebaut haben, nie ganz ausgeräumt werden konnte, ist nach aktuellem Wissen bis heute kein praktisch verwertbarer Angriffspunkt gefunden worden. Die Unsicherheit von DES rührt daher, dass der Brute-Force-Angriff heutzutage technisch möglich geworden ist.
DES spielte in der Geschichte und auch heute noch eine überragende Rolle.
 
   
Der Vorgänger von DES

LUCIFER

Data Encryption Standard


5. HASH-Funktionen history menue scroll up

 

Hash-Werte-Logo

http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo34.php
In der Kryptologie werden Hashfunktionen zum Signieren von Dokumenten oder zum Erzeugen von Einweg-Verschlüsselungen verwendet. Sie dienen in der Kryptologie auch dazu,
um z. b. zu erkennen ob eine Nachricht Manipuliert wurde oder gefälscht wurde , also um die Echtheit der Nachricht zu beweisen. Hashwerte sind auch Bestandteil von verschiedenen Verschlüsselungsverfahren.
Prüfsummen dienen dem (fast eindeutigem ) erkennen, ob eine Datei z. b. ein Text, ein Archiv oder irgend eine andere Datei von Irgendjemanden Manipuliert wurde, sie durch z. b.: das Downloaden der Datei beschädigt wurde, oder um einfach die Echtheit der Datei zu beweisen (bestätigen).
Dazu wird vorher von der Originaldatei der Hashwert ermittelt und gespeichert. Danach wird mit dem selben Verfahren der Hashwert der z. b.: herunter geladenen Datei bestimmt und mit dem der Originaldatei verglichen.
Sind beide werte identisch, dann ist eine Beschädigung oder eine Manipulation fast eindeutig auszuschließen.
Hashfunktionen werden in Datenbanksystemen verwendet, um Daten mittels Hashtabellen zu suchen. Dies wird vor allem bei großen Datenmengen für die Datensuche bevorzugt. Dies bezeichnet man als Datenbankindex.

Hash-Wert Ermittlung oder -vergleich


6. Trapdoor-Einwegfunktionen history menue scroll up

Der Nachteil von Einwegfunktionen ist der, dass ihr Einsatzbereich sich auf Berechnungen beschränkt, bei denen alle Beteiligte die Berechnungen durchführen dürfen. Eine Trapdoor-Einwegfunktion ist eine Einwegfunktion, die nur mit Hilfe einer Geheiminformation invertierbar ist.

 

Trapdoor-Spider als Logo für die Trapdoorfunktion


7. MD4- bzw. MD5-Algorithmus history menue scroll up

Der Nachteil von Einwegfunktionen ist der, dass ihr Einsatzbereich sich auf Berechnungen beschränkt, bei denen alle Beteiligte die Berechnungen durchführen dürfen. Eine Trapdoor-Einwegfunktion ist eine Einwegfunktion, die nur mit Hilfe einer Geheiminformation invertierbar ist.

 

Trapdoor-Spider als Logo für die Trapdoorfunktion


8. Verwandte Themen history menue scroll up

Technisch gesehen hat die Kryptologie von der Theorie bis zur binären Praxis eine ganze Palette von Bezügen und existiert mitnichten allein. Streng genommen hat die Geschichte und das Militär. aber auch die Politik damit zu tun.

Grundlagen der Kryptologie

Kryptologie

Codes

Steganografie

Transpositionscodes und Lipogramme

CÄSAR-Chiffre

Vigenère-Chiffre

Rotor-Chiffriermaschinen

Public Key-Verfahren

die Kryptoanalyse

One-Time-Pads

Spezielle Chiffrierverfahren



zur Hauptseite
© Samuel-von-Pufendorf-Gymnasium Flöha © Frank Rost November 2002

... dieser Text wurde nach den Regeln irgendeiner Rechtschreibreform verfasst - ich hab' irgendwann einmal beschlossen, an diesem Zirkus nicht mehr teilzunehmen ;-)

„Dieses Land braucht eine Steuerreform, dieses Land braucht eine Rentenreform - wir schreiben Schiffahrt mit drei „f“!“

Diddi Hallervorden, dt. Komiker und Kabarettist

Diese Seite wurde ohne Zusatz irgendwelcher Konversationsstoffe erstellt ;-)