Verschlüsselung mit öffentlichem Schlüssel

Kryptographie mit öffentlichen Schlüsseln

Im Gegensatz zur Kryptographie mit symmetrischen Schlüsseln findet die Kryptographie mit öffentlichen Schlüsseln keine historische Verwendung. Es ist ein relativ neues Konzept.

Die symmetrische Kryptographie war gut geeignet für Organisationen wie Regierungen, Militärs und große Finanzunternehmen, die an der geheimen Kommunikation beteiligt waren.

Mit der Verbreitung unsicherer Computernetzwerke in den letzten Jahrzehnten wurde ein echtes Bedürfnis verspürt, Kryptographie in größerem Maßstab einzusetzen. Der symmetrische Schlüssel erwies sich aufgrund der Herausforderungen für die Schlüsselverwaltung als unpraktisch. Dies führte zu Kryptosystemen mit öffentlichem Schlüssel.

Der Prozess der Ver- und Entschlüsselung ist in der folgenden Abbildung dargestellt:

Die wichtigsten Eigenschaften des Verschlüsselungsschemas mit öffentlichem Schlüssel sind:

• Für die Ver- und Entschlüsselung werden unterschiedliche Schlüssel verwendet. Dies ist eine Eigenschaft, die dieses Schema von dem symmetrischen Verschlüsselungsschema unterscheidet.

• Jeder Empfänger besitzt einen eindeutigen Entschlüsselungsschlüssel, der allgemein als sein privater Schlüssel bezeichnet wird.

• Der Empfänger muss einen Verschlüsselungsschlüssel veröffentlichen, der als sein öffentlicher Schlüssel bezeichnet wird.

• In diesem Schema ist eine gewisse Sicherheit der Authentizität eines öffentlichen Schlüssels erforderlich, um Spoofing durch den Gegner als Empfänger zu vermeiden. Im Allgemeinen handelt es sich bei dieser Art von Kryptosystem um vertrauenswürdige Dritte, die bestätigen, dass ein bestimmter öffentlicher Schlüssel nur einer bestimmten Person oder Entität gehört.

• Der Verschlüsselungsalgorithmus ist komplex genug, um zu verhindern, dass Angreifer den Klartext aus dem Chiffretext und dem Verschlüsselungsschlüssel (öffentlich) ableiten.

• Obwohl private und öffentliche Schlüssel mathematisch zusammenhängen, ist es nicht möglich, den privaten Schlüssel aus dem öffentlichen Schlüssel zu berechnen. Tatsächlich besteht ein intelligenter Teil eines Kryptosystems mit öffentlichem Schlüssel darin, eine Beziehung zwischen zwei Schlüsseln zu entwerfen.

Es gibt drei Arten von Verschlüsselungsschemata für öffentliche Schlüssel. Wir diskutieren sie in den folgenden Abschnitten -

RSA-Kryptosystem

Dieses Kryptosystem ist eines der ursprünglichen Systeme. Es ist bis heute das am häufigsten verwendete Kryptosystem. Das System wurde von drei Gelehrten erfundenRon Rivest, Adi Shamir, und Len Adleman und daher wird es als RSA-Kryptosystem bezeichnet.

Wir werden zwei Aspekte des RSA-Kryptosystems sehen, erstens die Erzeugung von Schlüsselpaaren und zweitens Verschlüsselungs- und Entschlüsselungsalgorithmen.

Generierung eines RSA-Schlüsselpaars

Jede Person oder Partei, die mit Verschlüsselung an der Kommunikation teilnehmen möchte, muss ein Schlüsselpaar generieren, nämlich einen öffentlichen und einen privaten Schlüssel. Der Prozess bei der Schlüsselgenerierung wird nachfolgend beschrieben -

• Generate the RSA modulus (n)

  • Wählen Sie zwei große Primzahlen, p und q.

  • Berechnen Sie n = p * q. Für eine starke unzerbrechliche Verschlüsselung sei n eine große Zahl, typischerweise ein Minimum von 512 Bit.

• Find Derived Number (e)

  • Nummer e muss größer als 1 und kleiner als (p - 1) (q - 1) sein.

  • Es darf keinen gemeinsamen Faktor für e und (p - 1) (q - 1) außer 1 geben. Mit anderen Worten, zwei Zahlen e und (p - 1) (q - 1) sind Koprime.

• Form the public key

  • Das Zahlenpaar (n, e) bildet den öffentlichen RSA-Schlüssel und wird veröffentlicht.

  • Obwohl n Teil des öffentlichen Schlüssels ist, stellt die Schwierigkeit, eine große Primzahl zu faktorisieren, interessanterweise sicher, dass der Angreifer die beiden Primzahlen (p & q), mit denen n erhalten wird, nicht in endlicher Zeit finden kann. Dies ist die Stärke von RSA.

• Generate the private key

  • Der private Schlüssel d wird aus p, q und e berechnet. Für gegebenes n und e gibt es eine eindeutige Zahl d.

  • Die Zahl d ist die Umkehrung von e modulo (p - 1) (q - 1). Dies bedeutet, dass d die Zahl kleiner als (p - 1) (q - 1) ist, so dass sie bei Multiplikation mit e gleich 1 Modulo (p - 1) (q - 1) ist.

  • Diese Beziehung wird mathematisch wie folgt geschrieben:

ed = 1 mod (p − 1)(q − 1)

Der erweiterte euklidische Algorithmus nimmt p, q und e als Eingabe und gibt d als Ausgabe.

Beispiel

Ein Beispiel zum Generieren eines RSA-Schlüsselpaars ist unten angegeben. (Zum besseren Verständnis sind die hier verwendeten Primzahlen p & q kleine Werte. Praktisch sind diese Werte sehr hoch.)

• Sei zwei Primzahlen p = 7 und q = 13. Somit ist der Modul n = pq = 7 x 13 = 91.

• Wählen Sie e = 5, was eine gültige Wahl ist, da es keine Zahl gibt, die der gemeinsame Faktor 5 ist, und (p - 1) (q - 1) = 6 × 12 = 72, außer 1.

• Das Zahlenpaar (n, e) = (91, 5) bildet den öffentlichen Schlüssel und kann jedem zur Verfügung gestellt werden, dem wir verschlüsselte Nachrichten senden möchten.

• Geben Sie p = 7, q = 13 und e = 5 in den erweiterten euklidischen Algorithmus ein. Die Ausgabe ist d = 29.

• Überprüfen Sie, ob das berechnete d korrekt ist, indem Sie -

de = 29 × 5 = 145 = 1 mod 72

• Daher ist der öffentliche Schlüssel (91, 5) und der private Schlüssel (91, 29).

Verschlüsselung und Entschlüsselung

Sobald das Schlüsselpaar generiert wurde, ist der Prozess der Ver- und Entschlüsselung relativ einfach und rechnerisch einfach.

Interessanterweise arbeitet RSA nicht direkt mit Bitfolgen wie bei der symmetrischen Schlüsselverschlüsselung. Es arbeitet mit Zahlen modulo n. Daher ist es notwendig, den Klartext als eine Reihe von Zahlen kleiner als n darzustellen.

RSA-Verschlüsselung

• Angenommen, der Absender möchte eine Textnachricht an jemanden senden, dessen öffentlicher Schlüssel (n, e) ist.

• Der Absender repräsentiert dann den Klartext als eine Reihe von Zahlen kleiner als n.

• Um den ersten Klartext P zu verschlüsseln, der ein Zahlenmodul ist. Der Verschlüsselungsprozess ist ein einfacher mathematischer Schritt als -

C = Pe mod n

• Mit anderen Worten, der Chiffretext C ist gleich dem Klartext P, der e-mal mit sich selbst multipliziert und dann modulo n reduziert wird. Dies bedeutet, dass C auch eine Zahl kleiner als n ist.

• Zurück zu unserem Beispiel für die Schlüsselgenerierung mit Klartext P = 10 erhalten wir den Chiffretext C -

C = 105 mod 91

RSA-Entschlüsselung

• Der Entschlüsselungsprozess für RSA ist ebenfalls sehr einfach. Angenommen, der Empfänger des Public-Key-Paares (n, e) hat einen Chiffretext C erhalten.

• Der Empfänger erhöht C auf die Potenz seines privaten Schlüssels. D. Das Ergebnismodulo n ist der Klartext P.

Plaintext = Cd mod n

• Zurück zu unserem numerischen Beispiel: Der Chiffretext C = 82 würde mit dem privaten Schlüssel 29 auf Nummer 10 entschlüsselt.

Plaintext = 8229 mod 91 = 10

RSA-Analyse

Die Sicherheit von RSA hängt von den Stärken zweier separater Funktionen ab. Das RSA-Kryptosystem ist die beliebteste Stärke des Kryptosystems mit öffentlichem Schlüssel, dessen praktische Schwierigkeit darin besteht, die sehr großen Zahlen zu berücksichtigen.

• Encryption Function - Es wird als Einwegfunktion zur Umwandlung von Klartext in Chiffretext betrachtet und kann nur mit Kenntnis des privaten Schlüssels d rückgängig gemacht werden.

• Key Generation- Die Schwierigkeit, einen privaten Schlüssel aus einem öffentlichen RSA-Schlüssel zu bestimmen, entspricht dem Faktorisieren des Moduls n. Ein Angreifer kann daher die Kenntnis eines öffentlichen RSA-Schlüssels nicht zur Bestimmung eines privaten RSA-Schlüssels verwenden, es sei denn, er kann n faktorisieren. Es ist auch eine Einwegfunktion, von p & q-Werten zu Modul n zu wechseln ist einfach, aber eine Umkehrung ist nicht möglich.

Wenn eine dieser beiden Funktionen als nicht einseitig erwiesen ist, wird RSA unterbrochen. Wenn eine Technik zum effizienten Factoring entwickelt wird, ist RSA nicht mehr sicher.

Die Stärke der RSA-Verschlüsselung nimmt gegenüber Angriffen drastisch ab, wenn die Zahlen p und q keine großen Primzahlen sind und / oder der gewählte öffentliche Schlüssel e eine kleine Zahl ist.

ElGamal Cryptosystem

Neben RSA werden weitere Kryptosysteme mit öffentlichem Schlüssel vorgeschlagen. Viele von ihnen basieren auf verschiedenen Versionen des diskreten Logarithmusproblems.

Das ElGamal-Kryptosystem, Elliptic Curve Variant genannt, basiert auf dem Discrete Logarithm Problem. Sie leitet die Stärke aus der Annahme ab, dass die diskreten Logarithmen für eine gegebene Anzahl nicht im praktischen Zeitrahmen gefunden werden können, während der inverse Betrieb der Leistung effizient berechnet werden kann.

Lassen Sie uns eine einfache Version von ElGamal durchgehen, die mit Zahlen modulo p arbeitet. Bei elliptischen Kurvenvarianten basiert es auf ganz unterschiedlichen Zahlensystemen.

Generierung eines ElGamal-Schlüsselpaars

Jeder Benutzer des ElGamal-Kryptosystems generiert das Schlüsselpaar wie folgt:

• Choosing a large prime p. Im Allgemeinen wird eine Primzahl mit einer Länge von 1024 bis 2048 Bit gewählt.

• Choosing a generator element g.

  • Diese Zahl muss zwischen 1 und p - 1 liegen, darf aber keine Zahl sein.

  • Es ist ein Generator der multiplikativen Gruppe von ganzen Zahlen modulo p. Dies bedeutet, dass es für jede ganze Zahl m, die zu p co-primiert, eine ganze Zahl k gibt, so dass g ^k = a mod n ist.

    Zum Beispiel ist 3 Generator der Gruppe 5 (Z ₅ = {1, 2, 3, 4}).

N.	3 n	3 n mod 5
1	3	3
2	9	4
3	27	2
4	81	1

• Choosing the private key. Der private Schlüssel x ist eine beliebige Zahl größer als 1 und kleiner als p - 1.

• Computing part of the public key. Der Wert y wird aus den Parametern p, g und dem privaten Schlüssel x wie folgt berechnet:

y = gx mod p

• Obtaining Public key. Der öffentliche ElGamal-Schlüssel besteht aus den drei Parametern (p, g, y).

  Angenommen, p = 17 und g = 6 (Es kann bestätigt werden, dass 6 ein Generator der Gruppe Z _{17 ist} ). Der private Schlüssel x kann eine beliebige Zahl sein, die größer als 1 und kleiner als 71 ist. Wir wählen also x = 5. Der Wert y wird dann wie folgt berechnet:

y = 65 mod 17 = 7

• Somit ist der private Schlüssel 62 und der öffentliche Schlüssel ist (17, 6, 7).

Verschlüsselung und Entschlüsselung

Die Generierung eines ElGamal-Schlüsselpaars ist vergleichsweise einfacher als der entsprechende Prozess für RSA. Die Ver- und Entschlüsselung ist jedoch etwas komplexer als bei RSA.

ElGamal-Verschlüsselung

Angenommen, der Absender möchte einen Klartext an jemanden senden, dessen öffentlicher ElGamal-Schlüssel (p, g, y) lautet. Dann -

• Der Absender repräsentiert den Klartext als eine Reihe von Zahlen modulo p.

• Um den ersten Klartext P zu verschlüsseln, der als Zahl modulo p dargestellt wird. Der Verschlüsselungsprozess zum Erhalten des Chiffretextes C ist wie folgt:

  • Erzeugen Sie zufällig eine Zahl k;
  • Berechnen Sie zwei Werte C1 und C2, wobei -

C1 = gk mod p
C2 = (P*yk) mod p

• Senden Sie den Chiffretext C, der aus den beiden getrennten Werten (C1, C2) besteht, die zusammen gesendet wurden.

• In Bezug auf unser oben angegebenes Beispiel für die ElGamal-Schlüsselgenerierung wird der Klartext P = 13 wie folgt verschlüsselt:

  • Generieren Sie zufällig eine Zahl, sagen wir k = 10
  • Berechnen Sie die beiden Werte C1 und C2, wobei -

C1 = 610 mod 17
C2 = (13*710) mod 17 = 9

• Senden Sie den Chiffretext C = (C1, C2) = (15, 9).

ElGamal-Entschlüsselung

• Um den Chiffretext (C1, C2) mit dem privaten Schlüssel x zu entschlüsseln, werden die folgenden zwei Schritte ausgeführt:

  • Berechnen Sie die modulare Inverse von (C1) ^x modulo p, die (C1) ^{-x ist} und allgemein als Entschlüsselungsfaktor bezeichnet wird.

  • Erhalten Sie den Klartext mit der folgenden Formel:

C2 × (C1)-x  mod p = Plaintext

• In unserem Beispiel ist der Entschlüsselungsfaktor, um den Chiffretext C = (C1, C2) = (15, 9) unter Verwendung des privaten Schlüssels x = 5 zu entschlüsseln

15-5  mod 17 = 9

• Extrahieren Sie Klartext P = (9 × 9) mod 17 = 13.

ElGamal-Analyse

Im ElGamal-System verfügt jeder Benutzer über einen privaten Schlüssel x. und hatthree components des öffentlichen Schlüssels - prime modulus p, generator g, and public Y = g^x mod p. Die Stärke des ElGamal basiert auf der Schwierigkeit des diskreten Logarithmusproblems.

Die sichere Schlüsselgröße beträgt im Allgemeinen> 1024 Bit. Heute werden sogar 2048 Bit lange Schlüssel verwendet. In Bezug auf die Verarbeitungsgeschwindigkeit ist Elgamal ziemlich langsam und wird hauptsächlich für Schlüsselauthentifizierungsprotokolle verwendet. Aufgrund der höheren Verarbeitungseffizienz werden Elliptic Curve-Varianten von ElGamal immer beliebter.

Elliptische Kurvenkryptographie (ECC)

Elliptic Curve Cryptography (ECC) ist ein Begriff, der eine Reihe von kryptografischen Werkzeugen und Protokollen beschreibt, deren Sicherheit auf speziellen Versionen des Problems des diskreten Logarithmus basiert. Es werden keine Zahlen modulo p verwendet.

ECC basiert auf Mengen von Zahlen, die mathematischen Objekten zugeordnet sind, die als elliptische Kurven bezeichnet werden. Es gibt Regeln zum Hinzufügen und Berechnen von Vielfachen dieser Zahlen, genau wie es für Zahlen modulo p gibt.

ECC enthält eine Variante vieler kryptografischer Schemata, die ursprünglich für modulare Nummern wie ElGamal-Verschlüsselung und Algorithmus für digitale Signaturen entwickelt wurden.

Es wird angenommen, dass das Problem des diskreten Logarithmus viel schwieriger ist, wenn es auf Punkte auf einer elliptischen Kurve angewendet wird. Dies veranlasst das Umschalten von Zahlen modulo p zu Punkten auf einer elliptischen Kurve. Eine äquivalente Sicherheitsstufe kann auch mit kürzeren Schlüsseln erreicht werden, wenn wir elliptische kurvenbasierte Varianten verwenden.

Die kürzeren Schlüssel ergeben zwei Vorteile -

• Einfache Schlüsselverwaltung
• Effiziente Berechnung

Diese Vorteile machen elliptisch-kurvenbasierte Varianten des Verschlüsselungsschemas für Anwendungen mit eingeschränkten Rechenressourcen sehr attraktiv.

RSA- und ElGamal-Schemata - Ein Vergleich

Vergleichen wir kurz die RSA- und ElGamal-Schemata zu den verschiedenen Aspekten.

RSA	ElGamal
Es ist effizienter für die Verschlüsselung.	Es ist effizienter für die Entschlüsselung.
Es ist weniger effizient für die Entschlüsselung.	Es ist effizienter für die Entschlüsselung.
Für eine bestimmte Sicherheitsstufe sind in RSA lange Schlüssel erforderlich.	Für die gleiche Sicherheitsstufe sind sehr kurze Tasten erforderlich.
Es ist weit verbreitet und wird verwendet.	Es ist neu und auf dem Markt nicht sehr beliebt.