moderne Verfahren

Aus ProgrammingWiki

Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

Exkurs zu Primzahlen

  1. [1]
  2. [2]


Das RSA-Verfahren

Der Algorithmus

  1. Lege zwei (große) Primzahlen und fest mit .
    Bilde das Produkt .
    Suche eine weitere Zahl , für die gilt:
    • ist Primzahl und größer als und oder
    • ist teilerfremd zu .
    Die Zahlen und bilden den öffentlichen Schlüssel.
  2. Ermittle den privaten Schlüssel mit:
    • und
  3. Ein Klartext-Zeichen mit dem Code wird mit

    zu verschlüsselt.

  4. Der verschlüsselte Code wird mit

    zum Code des Klartext-Zeichens entschlüsselt.

Ron Rivest, Adi Shamir, Leonard Adleman, 2003

Das RSA-Verfahren wurde 1977 von Ronald L. Rivest, Adi Shamir und Leonard Adleman am MIT in Boston entwickelt und galt damals als das erste asymmetrische Verschlüsselungsverfahren.
Es nutzt die Tatsache, dass es praktisch unmöglich ist, eine Primfaktorenzerlegung sehr großer Zahlen (ca. 200 Stellen und mehr) in einem vertretbaren (Zeit-)Aufwand vorzunehmen.


Bei diesem Verfahren gibt es öffentliche und geheime Schlüssel.

Die Sicherheit dieses Verfahrens beruht darauf, dass die Mathematik bisher noch keine Formel gefunden hat, mit der Primzahlen einfach und schnell berechnet werden können. Nach wie vor stehen hier nur Probiermethoden zur Verfügung. Aufgrund der großen Anzahl der Zahlenwerte führt dieses Probieren bei langen Schlüsselwerten nicht mehr in vernünftiger Zeit zum Ergebnis.

In diesem Zusammenhang wird von sogenannten Einwegfunktionen gesprochen, die in einer Richtung einfach anzuwenden, in anderer Richtung (Umkehrung) gar nicht oder extrem schwierig funktionieren.

    Primzahlen 41 und 211: Produkt einfach zu bestimmen: 8651
    Aus dem Produkt 8651 sind die Primzahlen durch Faktorisieren schwer zu ermitteln! Dies wird umso schwieriger, je größer die zu faktorisierende Zahl ist!

    Das Grundprinzip

  • man wähle zwei möglichst große Primzahlen und
  • Verschlüsseln mit öffentlichem Schlüssel , wobei und eine beliebige Zahl ist aber teilerfremd zu
  • Entschlüsseln mit privatem Schlüssel , den man aus erhält


    • Es gelten also die Formeln:

      für das Verschlüsseln der Nachricht M zum chiffrierten Text C:
      sowie für das Dechiffrieren von C in die Ausgangsnachricht M:



    Ein Beispiel:

    Bob will an Alice eine Nachricht schicken. Alice hat einen öffentlichen Schlüssel wie folgt gewählt: Die Primzahlen seien =17 und =11. Damit ist =187, für wird 7 gewählt. Dieser Schlüssel wird veröffentlicht.
    Es soll die Nachricht XMAS gesendet werden. Dazu müssen die Buchstaben in ASCII-Code umgewandelt werden.

    Betrachten wir zunächst das X, so wird diese in ASCII durch dargestellt. Dies entspricht der Dezimalzahl 88, damit sei die (Teil-)Nachricht .
    Ascii-Listen finden sich z.B. unter [3] oder [4]

    Für die Verschlüsselung ergibt sich nun Dies ist 11 (nachprüfen!), damit schickt Bob die geheime Nachricht an Alice.

    Nur wer die passenden Primzahlen kennt, mit denen der öffentliche Schlüssel erzeugt wurde, kann die Botschaft entschlüsseln. Das ist allein Alice.
    Ihr privater Schlüssel folgt aus



    , weil (!?)

    Nun braucht nur noch die Nachricht entschlüsselt werden:

    X.


    Aufgabe:

    Verschlüsseln Sie den Rest der Nachricht XMAS und geben Sie Ihre Lösung in der Box in " " ein.
    Betätigen Sie den speichern & ausführen Schaltfläche!

    Zusammenfassung

    • Mit der Idee der asymmetrischen Verschlüsselung entfällt beim RSA-Verfahren der unsichere Schlüsselaustausch.
    • Die Verschlüsselung einzelner Zeichen entspricht einer monoalphabetischen Verschlüsselung und wäre durch Häufigkeitsanalysen sehr schnell zu "knacken". In der Praxis wird man deshalb die Codes mehrere Zeichen vor der RSA-Verschlüsselung zusammenfassen.
      Beispiel: 
      "Informatik" --> unverschlüsselte Codeliste: (9 40 32 41 44 39 27 46 35 37)
             --> modifizierte Codeliste    : (940 3241 4439 2746 3537)
    • Der RSA-Algorithmus gilt als sehr sicher, wenn große Primzahlen verwendet werden. Es gibt aber nach wie vor intensive Bemühungen, Produkte großer Primzahlen effizient zu faktorisieren.
    • Das RSA-Verfahren wird heute in der Regel mit symmetrischen Verschlüsselungsverfahren kombiniert. Dabei wird ein Schlüssel für eine symmetrische Verschlüsselung generiert, der dann per RSA-Algorithmus verschlüsselt und zusammen mit der Nachricht übertragen wird.

    vergleiche auch [5] oder [6]


    DES-Verfahren

    Ist die Abkürzung für Data Encryption Standard. Es ist ein symmetrischer Verschlüsselungsalgorithmus und wird seit 1976 international vielfach eingesetzt. Symmetrisch bedeutet, dass zum Ver- und Entschlüsseln der selbe Schlüssel genutzt wird. Zuerst verwendet wurde es von der US-amerikanischen Regierung und wird heute zum Beispiel beim Electronic Cash benutzt.

    Schichten

    Teil der ersten Schicht ist die Einteilung der zu verschlüsselnden Nachricht in mehrere gleich lange Blöcke, die alle nach dem gleichen Prinzip verschlüsselt werden. 1 Block entspricht einer Länge von 64 Bits und wenn man die Nachricht nicht gleichmäßig aufteilen kann wird mit sogenannten Dummy-Bits aufgefüllt.

    Um jeden einzelnen Block zu verschlüsseln gibt es unterschiedliche Standard-Operationen. Ein Beispiel dafür ist die XOR-Operation.

    Um die Bit-Folgen schwerer decodierbar zu machen benutzt man Permutationen. So besagt die Permutation (2 3 1 8 5 4 6 7), dass aus der ursprünglichen Reihenfolge (1 0 0 1 1 0 1 0) die neu abgebildete Reihenfolge (0 1 0 0 1 1 0 1)

    Die Verschlüsselung erfolgt in unterschiedlichen Phasen. Dabei kann man folgendes beobachten: -DES besteht aus einer Anfangsphase, einer mittleren Phase mit 16 Runden (Nummer 0 bis 15) und einer Endphase.

    -Die Anfangsphase besteht aus einer Permutation der gesamten Folge.

    -In den Runden werden linke und rechte Hälfte der Bit-Folge getrennt behandelt.

    -Jede Runde besteht aus einer Vertauschung von linker und rechter Hälfte, einer Manipulation der rechten Hälfte im F-Modul und einer XOR-Operation der manipulierten rechten mit der linken Hälfte.

    -Jede Runde verwendet ihren eigenen Schlüssel.

    -Die mittlere Phase wird mit einer Vertauschung von linker und rechter Hälfte abgeschlossen.

    -Die Endphase besteht aus einer abschließenden Permutation der gesamten Folge.

    Des weiteren gibt es noch Paritäten. Denn das DES-Verfahren lässt nur Schlüssel mit bestimmter Parität zu. Ist die Zahl der Einsen in einer Bit-Folge ungerade, so ist die Parität 1, andernfalls ist die Parität 0. Als übereinstimmende Abmachung zwischen Sender und Empfänger sind nur Schlüssel mit der Parität 1 zugelassen.

    [7]


    Sicherheit von Informationen: Auf Grund der großen Blöcklänge macht es einen statistischen Angriff praktisch unmöglich. Dabei wird versucht, aus der Häufigkeit von Mustern auf die zu entschlüsselnde Nachricht geschlossen. Der bisher gelungene Angriff wird als Brute-Force-Angriff bezeichnet. Dabei wird jeder Schlüssel durchprobiert.

    IDEA-Verfahren

    IDEA steht für International Data Encryption Algorithm und wurde 1990 von der ETH Zürich in Zusammenarbeit mit der Firma Ascom Systec AG von James L. Massey und Xueija Lai,als Alternative zum unsicher gewordenen DES-Verfahren, entwickelt. Wegen anfänglicher Probleme war er anfällig für die Kryptoanalyse nach Biham und Shamir und wurde deshalb 1992 verbessert. Es ist bis heute keine einzige geglückte Attacke bekannt und er gilt als sehr sicherer Algorithmus. Es bietet im Vergleich zu DES bei weniger Rechenleistung ( nur 8 statt 16 Runden) eine größere Sicherheit, u.a. durch einen größeren Schlüsselraum. Beim IDEA-Verfahren wird der 64-bit lange klartext ( nachdem jedem Buchstabe seine entsprechende Zahl nach dem Tafelwerk zugewiesen wurde) zuerst in vier 16-bit lange blöcke unterteilt. In 8 Runden werden diese dann verschlüsselt. Der 128-Bit lange Schlüssel wird folgendermaßen in 52 Schlüssel zerlegt: zuerst wird der Schlüssel in acht 16-Bit-Schlüssel zerlegt, dann werden die Zahlen des 128-Bit-Schlüssels um 25 Bit nach links veschoben und erneut zerlegt, solange bis die besagten 52 Schlüssel beisammen sind.


    [8]


    Digitale Signaturen

    Definition

    Eine digitale Signatur ist ein kryptografisches Verfahren, bei dem zu beliebigen Daten eine Zahl (die digitale Signatur) berechnet wird, deren Urheberschaft und Zugehörigkeit zur Nachricht durch jeden geprüft werden können.

    Digitale Signaturen basieren auf asymmetrischen Kryptosystemen und verwenden folglich ein Schlüsselpaar, das aus einem privaten (geheimen) und einem öffentlichen (nicht geheimen) Schlüssel besteht. Oftmals findet man dafür die englischen Bezeichnungen Private Key und Public Key. Beispiel dafür ist die bekannte Verwendung von Serials bei Spieln, wo einem öffentlichen Key eigene Daten angefügt werden. Die dann zentral mit einem nicht-öffentlichen Key des Publishers verglichen werden.

    Grundprinzip

    Aus den zu signierenden Daten und dem privaten Signaturschlüssel wird durch eine eindeutige Rechenvorschrift die Signatur berechnet. Verschiedene Daten müssen mit an Sicherheit grenzender Wahrscheinlichkeit zu einer anderen Signatur führen, und die Signatur muss für jeden Schlüssel einen anderen Wert ergeben.


    Soweit der öffentliche Schlüssel mittels eines elektronischen Zertifikats einer Person zugeordnet wurde, kann er, da es nur einen zum öffentlichen Schlüssel korrespondierenden privaten Schlüssel gibt, über das öffentliche Verzeichnis des Zertifizierungsdiensteanbieters (ZDA) die Identität des Signaturerstellers ermittelt bzw. überprüft werden. Die Gesamtheit der technischen Infrastruktur, mit der die Zertifikate und Informationen zu ihrer Gültigkeit erzeugt und öffentlich bereitgestellt werden, wird als PKI (Public Key Infrastructure) bezeichnet. So kann die "Nachricht" nur mit den zur Signatur gehörenden Daten und dem Public Key entschlüsselt und verstanden werden.

    Das am häufigsten angewendete Verfahren ist das RSA-Verfahren.


    Sicherheit

    Signatur und Verschlüsselungsschlüsselpaar Die übliche Trennung von Verschlüsselungs- und Signierschlüsselpaar, obwohl ein Schlüsselpaar für beide Sicherheitsziele bzw. Einsatzzwecke benutzt werden kann, hat gute Gründe.

    1. das kryptographische Material, das für eine Kryptanalyse zur Verfügung steht wird reduziert, da ein Schlüsselpaar nicht so oft verwendet wird

    2. die Folgen einer Manipulierung und/oder Widerrufs eines Schlüsselpaares fallen weniger gravierend aus.

    3. Eine Angriffsmöglichkeit über das Unterjubeln eines Hash-Wertes fällt weg: Da eine Anwendung des privaten Schlüssels entweder eine Signierung oder eine Entschlüsselung sein kann, könnte eine angeblich verschlüsselte Nachricht eigentlich ein Hash-Wert sein. Nachdem man als Empfänger die Nachricht entschlüsseln will und den privaten Schlüssel darauf anwendet erhält man als Ergebnis ... ein entschlüsseltes Zifferngewirr oder einen signierten Hash-Wert - je nach dem wer dies betrachtet.


    Sichere digitale Signatur Eine sichere elektronische Signatur ist laut Signaturgesetz eine elektronische Signatur

    1. die ausschließlich dem Signator zugeordnet ist,

    2. die Identifizierung des Signators ermöglicht,

    3. mit Mitteln erstellt wird, die der Signator unter seiner alleinigen Kontrolle halten kann, mit den Daten, auf die sie sich bezieht, so verknüpft ist, dass jede nachträgliche Veränderung der Daten festgestellt werden kann, sowie,

    4. auf einem qualifizierten Zertifikat beruht und unter Verwendung von technischen Komponenten und Verfahren, die den Sicherheitsanforderungen dieses Bundesgesetzes und der auf seiner Grundlage ergangenen Verordnungen entsprechen, erstellt wird.

    Visualisierung Signatur: [9]


    Visualisierung SSL: [10]



Von „https://programmingwiki.de/PMG1719/moderne_Verfahren“
Persönliche Werkzeuge