9.9. DES, AES, IDEA, RSA-Verfahren, Passkeys & HASH-Werte - Einwegfunktionen - Trapdoors

Letztmalig dran rumgefummelt: 13.05.25 02:40:37

	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.
	0. Kryptologische Institutionen 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 & der Advanced Encryption Standard 5. HASH-Funktionen - Salt & Pepper 6. Trapdoors 7. MD4- bzw. MD5-Algorithmus 8. Übungsbereich 9. 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

0. Kryptologische Institutionen

	Diese in die Betrachtungen von vorn herein mit einzubeziehen ist deshalb geboten, da sie unter der Hand und/oder ganz bzw. teilweise vom Staat gedeckt arbeiten und keiner wirklich genau weiß, wie hoch der "Wissensstand" dort wirklich ist (es steht zu vermuten an, dass man sich immer ein "Hintertürchen" offen halten möchte, um grundsätzlich überall "mitlesen" zu können).
	NSA MI5 MI6 KGB BND MOSSAD STASI National Security Agency   MI5 - Military Intelligence, Section Five MI6 - Secret Service KGB BND     MOSSAD Staatssicherheit der DDR
	wissenschaftliche Institutionen

1. Funktionsprinzip des RSA-Verfahrens

	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)
	zum RSA-Verfahren zum RSA-Rechner
	Notiz von Michael Krasselt Hier finde ich es recht gut und kurz erklärt. Interesannt ist vorallem der letzte abschnitt: RSA Die Sicherheit von RSA liegt in der Schwierigkeit begründet, (sehr) große Zahlen zu faktorisieren. Diese großen Zahlen n sind Produkte zweier Primzahlen p und q, d. h. n = pq. Man geht davon aus, dass es schwer ist, aus gegebenem n die Ursprungswerte p und q zu berechnen. Schlüsselerzeugung Zunächst muss ein öffentlicher und privater Schlüssel (Schlüsselpaar) erzeugt werden. Dies kann z. B. durch eine Schlüsselvergabestelle erfolgen. Diese wählt zufällig zwei große Primzahlen p und q: n = pq Dann wird Phi(n) (Symbol: Φ) berechnet. Dies dient der Berechnung der Anzahl der teilerfremden Zahlen zu n; z. B. ist Φ(15) = 8, da 1, 2, 4, 7, 8, 11, 13 und 14 keine gemeinsamen Teiler mit 15 haben (die 1 zählt man auch dazu). Da eine Primzahl nur durch 1 und sich selbst teilbar ist, sind alle Zahlen, die unterhalb von ihr liegen, zu ihr teilerfremd. D. h.: Φ(p) = p − 1 bzw. Φ(q) = q − 1. Folglich gilt für Φ(n): Φ(n) = (p − 1)(q − 1) Schließlich bestimmen wir zwei Zahlen e und d so, dass ed mod Φ(n) = 1 gilt. Das bedeutet, e und d heben sich auf, genauso wie 4 und 1/4 bezüglich Multiplikation (4 · 1/4 = 1). Man sagt auch, d ist der Kehrwert von e modulo Φ(n). e und n bilden nun den öffentlichen Schlüssel und d und n den privaten Schlüssel. Am besten sollten p und q nach der Berechnung von e, d und n vernichtet werden, da sie nicht mehr benötigt werden und nur einen unnötigen Risikofaktor darstellen (denn wer p und q kennt, kennt auch n, und die Sicherheit des Systems wäre dahin). Wie wählt man d und e? Zunächst sucht man sich eine beliebige Zahl e, die teilerfremd zu Φ(n) ist; das kann z. B. eine Primzahl sein, die kleiner als Φ(n) ist. Die Bestimmung von d (d. h. dem Kehrwert oder modularen Inversen) ist schwieriger; sie erfordert mehr oder weniger komplizierte Verfahren. Ein weniger aufwändiges Verfahren finden Sie im Artikel RSA Verschlüsselung - ggt Berechnung. Ver- und Entschlüsselung Um eine beliebige Nachricht m zu verschlüsseln, die kleiner oder gleich n ist, führen wir folgende Berechnung durch: c = m^e mod n Das heißt, m (die Nachricht) wird mit e potenziert, und der Rest, der sich bei der Division durch n ergibt, bildet den Chiffretext oder Geheimtext c. Wenn n beispielsweise 512 Bit lang ist, muss m kleiner oder gleich 512 Bit lang sein. Um den Geheimtext wieder umzuwandeln, berechnet der Empfänger: m = c^d mod n Damit das Verfahren reibungslos über die Bühne gehen kann, muss gewährleistet sein, dass sich e und d "aufheben": e · d mod (p−1)(q−1) = 1   On 13. November 2015 17:03:19 MEZ, "rostfrank@t-online.de" <rostfrank@t-online.de> wrote: ... wann, wo und vor allem wie kommt die Modulo-Division zum Einsatz? Bereite gerade einen Cache damit vor und stehe unter Zeitdruck - der ist nämlich der Schlüsselcache für ein Schüler-Projekt ;-) Also möglichst detaillierte Infos und nur die notwendigste Mathe - das habe ich schon alles ;-)   Danke - Frank ------------
	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

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

Ziel ist es, eine einen Schlüsselaustausch unter ausschließlichem Zugriff genau definierter Teilnehmerkreise zu gewähleisten - und dies auf Basis eines mathematischen Modells, welches in sich eine Einwegfunktion repräsentiert. Sind die gewählten Eingangsparameter hinreichend groß, besteht kaum eine reale Chance bei Einhaltung aller Randbedingungen in den Besitz des vollständigen Schlüssels zu gelangen.

Ablaufprotokoll Ablaufprotokoll eines realen Schlüsselaustausches mit kleinen Eingangswerten ... mal ein paar Primzahlen für unsere Zwecke hinreichend groß ... hier nochmals als Ablaufspiel Diffie & Hellmann Public-Key Tausch Ablaufprotokoll mit Echtzahlen - Beispiel 1 ... und hier als TXT-File kleine Primzahlliste Diffie-Hellmann-Verfahren Diffie - Hellman - Hintergrund-Infos

3. Einfache und komplexe mathematische Einwegfunktionen

	In der Informatik ist eine Einwegfunktion eine mathematische Funktion, die komplexitätstheoretisch „leicht“ berechenbar, aber „schwer“ umzukehren ist. In einem erweiterten Sinn werden auch Funktionen so bezeichnet, zu denen bisher keine in angemessener Zeit praktisch ausführbare Umkehrung bekannt ist. Zu einem bekannten Namen in einem sehr umfangreichen Telefonbuch die entsprechende Rufnummer zu finden, ist ganz einfach, umgekehrt, bei nur bekannter Rufnummer den zugehörigen Namen zu finden, gestaltet sich das Unterfangen schon als wesentlich komplexer
	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:
	... der Passkey ... die 2-Faktor-Athentifizierung ... die digitale Signatur Passkey   2-Faktor Authentifizierung ELGAMAL & die digitale Signatur

4. Blockchiffren

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.

Project "Lucifer" Data Encryption Standard Advanced Enryption Standard IDEA Blowfish Der Vorgänger von DES LUCIFER Data Encryption Standard Advanced Encryption Standard International Data Encryption Algorithm Blowfish

5. HASH-Funktionen - Salt & Pepper

	Schon mal irgendwo eingeloggt und sich gefragt, wie man dies sicherheitstechnisch überhaupt bewerkstelligt? ... und wie geht die Sache mit den digitalen Unterschriften? Wie bewest man die digitale Unversehrtheit einer E-Mail (niemand hat sie zuvor bereits gelesen oder anschließend gar manipuliert?
	MD4 & MD5-Algorithmen Salt & Pepper ... die potentiellen Gegner des Verfahrens - und diese sind auch heute noch ernst zu nehmen Hash-Werte Salt & Pepper Rainbow-Tables
	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

	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

	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.

8. Übbungsbereich

	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.
	RSA-Algorithmus Beispiel 1 Beispiel 2     Plaintext:

9. Verwandte Themen

	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