Grundlagen der Kryptographie

Der Wunsch von Regierungen, Generälen und sogar privaten Einzelpersonen, auf eine Weise zu kommunizieren, die verhindert, dass private Kommunikation von anderen gelesen wird, reicht Jahrtausende zurück. Die Fähigkeit Dritter, Nachrichten zu lesen, die nicht für sie bestimmt sind, oder dass Nachrichten für Dritte unlesbar sind, hat häufig den Lauf der Geschichte verändert. Der Einsatz von Technologie in den letzten 200 Jahren hat den Prozess der Nachrichtenübermittlung verändert, zunächst mit dem Telegraphen, dann mit drahtloser Kommunikation und jetzt mit dem Internet. Bei auf Drähten basierenden Telegraphensystemen benötigte ein Dritter physischen Zugang zum Kommunikationsmedium. Mit drahtlosem Radio wurde die Übertragung öffentlich und der Bedarf an sicheren Kommunikationen stieg. Bei Nachrichten, die in Paketen über das Internet gesendet werden, kann buchstäblich jeder von überall auf der Welt mithören. In diesem Kapitel werden wir kurz einige der Geschichte behandeln und wir werden grundlegende Begriffe und Anwendungen definieren, die im gesamten Buch fortgesetzt werden.

Bis zum Computerzeitalter war das Erstellen und Brechen von Chiffren eine Aufgabe, die extreme Konzentration und Sorgfalt erforderte. Suchbäume basierend auf Vermutungen können auf Computern programmiert und mit hoher Geschwindigkeit ausgeführt werden, wobei wir die Geschwindigkeit des Computers und die Leichtigkeit der Datenverfolgung in Datenstrukturen nutzen können, um uns nicht allzu sehr um die Verfolgung von Pfaden mit geringer Wahrscheinlichkeit zu kümmern. Die Kosten in Zeit und Aufwand für die Suche mit Bleistift und Papier hätten viel bessere Vermutungen über den richtigen Pfad durch den Baum erfordert. Die Kryptoanalyse in der ersten Hälfte des zwanzigsten Jahrhunderts erforderte Kenntnisse von Sprachmustern und Frequenzstatistiken, und sowohl die Verschlüsselung als auch die Entschlüsselung mussten Prozesse sein, die leicht erinnert und befolgt werden konnten. In diesem Kapitel werden wir einige klassische Chiffren beschreiben (die leicht mit einem Programm auf einem Desktop-Computer angegriffen werden könnten) sowie einige statistische Eigenschaften von Sprachen, die verwendet werden könnten, um diese nun veralteten Chiffren anzugreifen. Es gibt zwei grundlegende Formen einfacher Chiffren. Bei einer Substitutionschiffre ersetzt man für jeden Buchstaben im zugrunde liegenden Alphabet ein anderes Symbol (vielleicht einen anderen Buchstaben im selben Alphabet, oder manchmal ein ganz anderes Symbol). Bei einer Transpositionschiffre bleiben die Buchstaben des zugrunde liegenden Alphabets gleich, aber ihre Reihenfolge wird in eine andere Reihenfolge transponiert. Dabei kann man den Begriff „Buchstabe“ als einzelnen Buchstaben oder vielleicht als Paar von Buchstaben verstehen. Wir unterscheiden von Anfang an ein Codebuch von einer Chiffre, obwohl die beiden eng miteinander verbunden sein können. Traditionelle Codebücher waren eine Form der Geheimhaltung von Kommunikation, indem für jedes der einzelnen Wörter in der Nachricht eine feste Länge (oft fünf) Sequenz von Zahlen ersetzt wurde. Man kann sich ein solches Codebuch als Substitutionschiffre vorstellen, bei der die Symbole Wörter (natürlich von variabler Länge) sind, für die man numerische Symbole ersetzt. Wir werden auch nur kurz (genau hier) den Begriff der Steganographie erwähnen, bei der eine Nachricht in einer scheinbar harmlosen Kommunikation versteckt ist. Eine Version davon wäre ein Brief, in dem die versteckte Nachricht die Sequenz der ersten Buchstaben der Wörter des Textes ist. Eine modernere umgekehrte Version der Steganographie ist das digitale Wasserzeichen, bei dem ein digitales Muster in ein Dokument, normalerweise ein Bilddokument, eingefügt wird, so dass die Herkunft des Bildes authentifiziert werden kann, wenn es illegal ohne Zuschreibung oder Lizenzgebühr entnommen wird. Dies ist nicht unähnlich der scheinbaren Einbeziehung von absichtlichen Fehlern in Karten, sagen wir, so dass der Inhaber des Urheberrechts der Karte argumentieren könnte, dass die Karte illegal kopiert wurde. Der Autor wünscht sich sehr, dass er die Straßenkarte von Louisiana (wo er aufgewachsen ist) behalten hätte, die eine Straße südlich von Venice, Louisiana, und eine Brücke über den Mississippi nach Pilottown zeigt. Eine solche Straße oder Brücke hat es nie gegeben; Pilottown ist der Ort, an dem die Mississippi River Piloten die ankommenden Schiffe treffen und das Ruder auf dem Weg flussaufwärts zum Hafen von New Orleans übernehmen, und wo sie auf der Ausreise das Ruder an die seefahrenden Piloten übergeben. Die „Stadt“ kann nur per Wasser erreicht werden; es gibt keine Straße südlich von Venice und keine Brücke über den Mississippi.

Die moderne Kryptographie basiert weitgehend auf den Mathematiken der modularen Arithmetik, Kongruenzen und der Arithmetik in den ganzen Zahlen modulo Primzahlen oder Produkte von (meistens) zwei großen Primzahlen. In diesem Kapitel behandeln wir die grundlegende Zahlentheorie, die in symmetrischen und asymmetrischen kryptographischen Systemen vorkommt: Teilbarkeit und Kongruenzen, größter gemeinsamer Teiler, Exponentiation und die Euler’sche Totient. Unser Schwerpunkt liegt auf mathematischen Theoremen, die verstanden und angewendet werden müssen, anstatt auf ihren Beweisen, es sei denn, die Methode oder Konstruktionen in den Beweisen sind relevant für die Kryptographie selbst. Obwohl wir dies als Hintergrundmathematik behandeln, weisen wir darauf hin, dass der Leser leicht Beispiele für alle abgedeckten Prinzipien generieren kann sowie Beispiele finden kann, die demonstrieren, warum die gemachten Annahmen notwendig sind und die Schlussfolgerungen eng gezogen sind.

Die moderne Kryptographie stützt sich für ihre Fähigkeit, Klartext in Chiffretext zu verwandeln, der wie zufällige Symbolsequenzen erscheint, auf die grundlegenden Konzepte der abstrakten Algebra. In diesem Kapitel führen wir die Grundlagen von Gruppen, Ringen und Körpern ein, einschließlich Untergruppen, zyklischen Gruppen, der Ordnung von Elementen und dem Lagrangeschen Theorem. Eine Gruppe ist eine Menge, die unter einer Operation geschlossen ist, die normalerweise (und oft) entweder als Addition oder als Multiplikation bezeichnet wird, mit zusätzlichen Eigenschaften. Ein Ring hat sowohl eine Addition als auch eine Multiplikation, aber möglicherweise keine Operation, die einer Division ähnelt. Ein Körper hat alle Eigenschaften, die wir normalerweise mit der Durchführung von Arithmetik verbinden. Alle drei sind in gewisser Weise lediglich abstrakte Beschreibungen der gewöhnlichen Arithmetik. Beweise werden weitgehend auf später verschoben oder gar nicht durchgeführt. Und da wir mehr daran interessiert sind, Gruppen, Ringe und Körper zu verwenden, als Theoreme über sie als algebraische Objekte zu beweisen, kann dieses Kapitel weitgehend als einfache Bereitstellung von Definitionen und formalen Aussagen der Wahrheit dessen angesehen werden, was wir beobachten, wenn wir die Operationen zum Verschlüsseln und Entschlüsseln durchführen.

Wir werden Quadratwurzeln modulo Primzahlen mit Hilfe von primitiven Wurzeln und Exponenten berechnen. Dies unterscheidet sich etwas von der Methode, die in vielen Referenzen verwendet wird, aber wir möchten betonen, dass die Welt der additiven Exponentenarithmetik wichtig ist. Modulo einer Primzahl p arbeiten die Exponenten additiv modulo \(p-1\). Wenn wir zur RSA-Verschlüsselung kommen, bei der wir einen Modulus \(N = pq\) für zwei große und unbekannte Primzahlen p und q haben, können wir nicht die gleichen Exponentenspiele wie bei Primzahlen spielen, weil \(\phi (N) = (p-1)(q-1)\) nicht \(N-1\) ist, und es ist das \(\phi (N)\), das die Arithmetik auf den Exponenten bestimmt. In den späteren Kapiteln über Faktorisierung und elliptische Kurven wird es rechnerisch vorteilhaft sein, bestimmen zu können, ob eine Zahl kongruent zu einem Quadrat modulo eines Modulus N ist oder nicht. Glücklicherweise kann festgestellt werden, ob eine Zahl ein Quadrat modulo einer Primzahl ist, oder festgestellt werden, dass eine Zahl kein Quadrat modulo einer zusammengesetzten Zahl ist, durch einen Prozess, der dem ggT ähnelt und die gleiche logarithmische Komplexität hat.

In diesem Kapitel erweitern wir uns über Ganzzahlen modulo Primzahlen hinaus, um endliche Körper der Charakteristik 2 zu betrachten. Für eine umfangreichere Darstellung endlicher Körper sollte der Leser Lidl und Niederreiter [1] konsultieren. Für eine andere Darstellung endlicher Körper der Charakteristik 2 könnte der Leser Golomb [2] konsultieren. Die Arithmetik endlicher Körper in Charakteristik 2 wird im Advanced Encryption Standard (AES) verwendet. Sie kann in anderen Kryptosystemen bevorzugt sein, da Computerhardware in Binär arbeitet und somit die zugrunde liegenden arithmetischen Operationen, die zum Verschlüsseln und Entschlüsseln benötigt werden, sehr schnell sein können.

Elliptische Kurven sind eines der eleganteren Objekte in der Algebra. Ein Hintergrundwissen über die zugrunde liegende Arithmetik von Kurven ist für die Kryptographie notwendig, da sie für (mindestens) drei Zwecke verwendet werden: zum Faktorisieren von Ganzzahlen, für die Kryptographie selbst und für den Schlüsselaustausch. Die Arithmetik der elliptischen Kurven ähnelt in vielerlei Hinsicht der Arithmetik der Ganzzahlen modulo Primzahlen oder zusammengesetzten Zahlen, zumindest. In diesem Kapitel präsentieren wir eine Einführung in elliptische Kurven als Hintergrund für spätere Kapitel, die sie für kryptographische Zwecke verwenden.

Wir haben früher bemerkt, dass die tatsächliche Durchführung von Kryptographie das Kombinieren von Mathematik und Informatik erfordert. In diesem Kapitel beschreiben wir mehrere Algorithmen und Rechentricks, die es ermöglichen, die diskrete Mathematik, die Kryptographie ist, auf Computern durchzuführen, die nicht unbedingt darauf ausgelegt sind, robuste Unterstützung für diskrete Mathematik zu bieten. Dieses Kapitel behandelt einige dieser Tricks und Algorithmen, die notwendig sind, um zu verstehen, wie man tatsächlich Kryptographie in der realen Welt durchführen könnte. Die erste Reihe von Tricks wurde ausgiebig beim Testen von Ganzzahlen auf Primzahleigenschaft verwendet, wobei die Bitmuster der Ganzzahlen verwendet wurden, um die Notwendigkeit einer Modulreduktion zu eliminieren. Multipräzise Arithmetik ist für einen Großteil der modernen Kryptographie erforderlich, wobei die Modulreduktion und Multiplikation die Kosten der Arithmetik dominieren. Die Multiplikation selbst wird mit schnellen Methoden wie der FFT durchgeführt, die wir hier behandeln, und die Reduktion kann mit der Montgomery-Multiplikation behandelt werden, die im Wesentlichen den Mersenne-Primzahltrick auf alle Ganzzahlmoduli erweitert.

In einem symmetrischen Kryptosystem ist der Schlüssel, der zum Verschlüsseln einer Nachricht verwendet wird, derselbe wie der Schlüssel, der zum Entschlüsseln einer Nachricht verwendet wird. Obwohl dies eine Belastung für die ordnungsgemäße Schlüsselverwaltung und -sicherheit für die Benutzer eines solchen Kryptosystems darstellt, wurden zwei wichtige Kryptosysteme, der Digital Encryption Standard (DES) und der Advanced Encryption Standard (AES), vom National Institute of Standards and Technology veröffentlicht. DES war aufgrund der Art und Weise, wie es veröffentlicht wurde, umstritten und wurde weitgehend vom AES abgelöst, über den fast keine Kontroversen bestehen. AES wird derzeit weit verbreitet eingesetzt, zum Teil weil es der NIST-Standard ist und zum Teil weil sein Design es schnell und auf einer Vielzahl von Plattformen mit unterschiedlichen Rechenkapazitäten nutzbar macht. Dieses Kapitel behandelt die technischen Aspekte von AES. Code für AES und Testergebnisse erscheinen im Anhang B, so dass Code-Tests durchgeführt und der Verschlüsselungsprozess beobachtet werden können.

Der Begriff eines asymmetrischen Verschlüsselungssystems stammt aus den 1970er Jahren, wobei die erste und immer noch primäre Version der asymmetrischen Verschlüsselung der RSA-Algorithmus von Rivest, Shamir und Adleman ist. Bei der asymmetrischen Verschlüsselung wird ein öffentlicher Schlüssel verwendet, um eine Nachricht zu verschlüsseln, die an den Besitzer des öffentlichen Schlüssels gesendet wird. Dieser Besitzer verwendet dann einen privat gehaltenen Schlüssel zum Entschlüsseln. Der RSA-Algorithmus basiert auf der Wahl von zwei großen Primzahlen p und q, die multipliziert werden, um einen Modulus N = pq zu erzeugen. Der öffentliche Verschlüsselungsschlüssel e und der private Entschlüsselungsschlüssel d werden so gewählt, dass ed ≡ 1 (mod Ф(N)) gilt. Nach aktuellem Wissen der Mathematik ist es so, dass wenn N und e öffentlich sind, aber p, q und d privat gehalten werden, dann erfordert das Entschlüsseln einer Nachricht das Zerlegen von N in p mal q, und das ist rechnerisch schwierig. In diesem Kapitel legen wir die Grundlagen des RSA-Prozesses dar, mit einem Beispiel, und wir kommentieren die aktuellen Rekorde im Faktorisieren als Schätzung der Sicherheit von RSA.

Die Sicherheit des RSA-Kryptosystems basiert auf der Schwierigkeit, ganze Zahlen N zu faktorisieren, die das Produkt von zwei großen Primzahlen p und q sind. Wenn p und q gut gewählt sind, dann ist das Faktorisieren von N tatsächlich schwierig, aber es gibt auch Faktorisierungsmethoden, die bei bestimmten Arten von Zahlen sehr schnell arbeiten. Um die Sicherheit eines RSA-Systems zu gewährleisten, muss man sorgfältig ein N wählen, das nicht einer der schnelleren Methoden zum Opfer fällt. Wir werden zuerst die Pollard-Rho- und Pollard- p − 1 Methoden diskutieren. Diese werden nicht nur allgemein zur Faktorisierung verwendet, sondern wurden auch verallgemeinert, um in anderen Angriffen gegen kryptographische Systeme anwendbar zu sein. Danach gehen wir zu CFRAC über, einem Vorläufer der modernsten Faktorisierungsmethode, die das Hauptthema von Kap. 12 ist.

In Kap. 11 haben wir mehrere Faktorisierungsmethoden beschrieben. Jede davon wird bei einigen Ganzzahlen erfolgreich sein, aber keine davon ist eine hochmoderne Methode, von der wir erwarten würden, dass sie bei einer gut gewählten RSA N = pq erfolgreich ist. Selbst die beste davon, CFRAC, leidet unter der Notwendigkeit, eine Probedivision durchzuführen, die die meiste Zeit keinen Fortschritt in Richtung Faktorisierung von N erbringt. In diesem Kapitel diskutieren wir Siebmethoden zur Faktorisierung. Der primäre rechnerische Vorteil einer Siebmethode besteht darin, dass alle ausgeführten Rechenschritte tatsächlich zur Findung von Faktoren beitragen und dass ein Sieb, das mit konstantem Schritt durch ein Array im Speicher geht, auf den niedrigsten Ebenen eines Rechenprozesses äußerst effizient ist. Wir diskutieren das Quadratische Sieb und das Mehrpolige Quadratische Sieb und schließen dann mit einem Hinweis auf die derzeit beste Methode zur Faktorisierung großer „schwerer“ Ganzzahlen, das Zahlkörpersieb.

Bei symmetrischer Kryptographie ist es notwendig, dass die beiden Parteien, die kommunizieren möchten, Zugang zu einem gemeinsamen Schlüssel haben, damit eine Partei eine Nachricht verschlüsseln und die andere Partei die Nachricht entschlüsseln kann. Dies würde die Fähigkeit von zwei Parteien, die in der Vergangenheit nicht kommuniziert haben, einschränken, die Art von sicherer Kommunikation zu führen, die beispielsweise für den elektronischen Handel notwendig ist. In diesem Kapitel beschreiben wir, wie zahlentheoretische Konstrukte, die scheinbar zufällige Zahlenfolgen erzeugen, verwendet werden können, um zwei Parteien den Austausch von Informationen zu ermöglichen, die es ihnen erlauben würden, sich auf einen gemeinsamen kryptographischen Schlüssel zu einigen, selbst wenn zwischen ihnen keine andere Kommunikation stattgefunden hat. Dieser Austausch von Schlüsselinformationen kann durch Exponentiation modulo einer großen Primzahl erfolgen, auf eine Weise ähnlich der RSA-Verschlüsselung, oder unter Verwendung von elliptischen Kurvengruppen in gleicher Weise. Wir werden auch die Grundlagen der Indexkalkulationsmethode behandeln, die, wenn auch mit Schwierigkeiten, zur Angriff auf diese Art des Schlüsselaustauschs verwendet werden kann.

Das erste vorgeschlagene asymmetrische Verschlüsselungsschema war das von Rivest, Shamir und Adleman, das die Exponentiation in der Gruppe der Ganzzahlen modulo das Produkt von zwei großen Primzahlen verwendet. Koblitz und Miller schlugen unabhängig voneinander die Verwendung der Gruppen von Punkten auf elliptischen Kurven vor. In diesem Kapitel behandeln wir den Algorithmus zur Verwendung von Kurven für die Kryptographie sowohl für die Verschlüsselung als auch für den Schlüsselaustausch. Da die Arithmetik zur Punktaddition aufwendig ist, enthalten wir die Formeln zur effizienten Addition von Punkten. Schließlich beinhalten wir den Pohlig-Hellman-Angriff, der bei richtig gewählten Kurven nicht erfolgreich sein sollte, und den Pollard-Rho-Angriff, der derzeit der beste Angriff auf das diskrete Logarithmusproblem der elliptischen Kurve ist.

Mit der Veröffentlichung von Peter Shors bahnbrechendem Artikel, dass das Faktorisieren und diskrete Logarithmenberechnungen auf einem Quantencomputer völlig machbar wären, und mit Fortschritten im Bau von Quantencomputern, hat sich der Fokus auf das sogenannte „Post-Quanten-Kryptographie“ gerichtet. Zu den vielversprechendsten Kandidaten für die Post-Quanten-Kryptographie gehören Kryptosysteme, die auf dem Problem der Suche nach kurzen Vektoren in Gittern basieren. In diesem Kapitel skizzieren wir kurz, warum Quantencomputer RSA-artige Kryptosysteme obsolet machen können und wie Gitter in der Kryptographie verwendet werden können. Wir konzentrieren uns auf das vielleicht bekannteste Gittersystem, NTRU, und erklären, wie es verwendet wird und warum Angriffe darauf immer noch rechnerisch unpraktikabel erscheinen.

Kurz nach dem ursprünglichen RSA-Papier [1] stellten Rivest, Adleman und Dertouzos eine Frage [2]: Wäre es möglich, eine Datenbank mit verschlüsselten Informationen (wie Finanz- oder Gesundheitsdaten) zu haben, die an einem externen Ort gespeichert sind, die dennoch Berechnungen an den verschlüsselten Daten ohne deren Entschlüsselung ermöglichen würde? Dies würde beispielsweise eine externe Speicherung und Berechnung an den verschlüsselten Daten an der externen Stelle ermöglichen, ohne dass der Eigentümer oder Betreiber der externen Stelle vertraut werden muss.\(\mathbb {R}^{3}\)