Kompakte RSA-Implementierung für eingebettete Anwendungen

  • Tutorial
RSA ist ein bekannter Verschlüsselungsalgorithmus für öffentliche Schlüssel. Auf dieser Basis kann neben der asymmetrischen Verschlüsselung auch eine elektronische Signatur ( EDS ) implementiert werden . Diese Funktionen sind attraktiv für eingebettete Systeme und Mikrocontroller. Die Verschlüsselungsmethode selbst ist sehr einfach:
= C (M e ) mod n(1)
wobei C, M, e, n ganze Zahlen sind, M Klartext ist, Zahlen e und n der öffentliche Schlüssel sind, C Chiffretext ist. mod - Rest der Teilung.

Nähen sieht genauso einfach aus:
M = (C d ) mod n(2)
Wo C, M, n die gleiche Rolle wie bei der Verschlüsselung spielen, ist d der private Schlüssel.

Außerdem ist n = p * q, wobei p und q Primzahlen sind (geheim), e ist gewöhnlich gleich 65537, d wird auf der Basis von e, p und q berechnet. Die kryptografische Stärke basiert auf der Tatsache, dass für ausreichend großes p und q das Problem der Faktorisierung von n oder der Umkehrung der Verschlüsselungsformel ohne Kenntnis von p und q nicht in einer akzeptablen Zeit gelöst werden kann.

Aber diese scheinbare Einfachheit täuscht. Dahinter stecken viele Details und Umsetzungsschwierigkeiten. Insbesondere wenn das Ziel darin besteht, eine effiziente Leistung und Speicherimplementierung zu erzielen, die für den Einsatz in Mikrocontrollern geeignet ist. Ich habe im Internet keine geeigneten Bibliotheken gefunden, sondern versucht, die Quellen von libgcrypt zu studierenFühre in solch wilde Gegenden, aus denen du nicht herauskommen kannst. Deshalb habe ich meine kompakte Bibliothek geschrieben, die ich mit angesehenen Lesern teile.

1. Lange Arithmetik (Multi-Precision Integer Arithmetics)


Die ersten Schwierigkeiten treten auf, wenn Sie versuchen, den RSA auf kleine Zahlen zu testen. Nehmen wir zum Beispiel p = 7, q = 11, dann erhalten wir n = 77. Das gewählte e sollte mit (p-1) * (q-1) einfach sein, damit 2, 3, 4 und 5 nicht passen, die Mindestanpassung 7. Abgesehen von der Methode zur Berechnung von d gebe ich einfach das Ergebnis: d = 43. Und jetzt, obwohl das Verschlüsseln einer kleinen Nachricht kein Problem darstellt, muss für die Entschlüsselung C auf die Potenz von 43 angehoben werden, und dies führt zu einem Überlauf selbst von 64-Bit-Ganzzahlen, die bereits bei C = 3 sind.

Es war jedoch auch ohne dieses Beispiel klar, dass man nicht ohne lange Arithmetik auskommen konnte. In der Tat müssen p und q groß sein, um die kryptografische Stärke sicherzustellen. In der modernen Praxis der Verwendung von RSA liegen diese Zahlen in der Größenordnung von jeweils 2 1024 und die Größenordnung von n bei 2 2048bei Verwendung einer Schlüssellänge von 2048 Bit. Es ist akzeptabel, die Reihenfolge der Zahlen um das Zweifache zu verringern (512 Bit für p und q, 1024 für n). In den letzten Jahren ist jedoch häufig die Ansicht vertreten worden, dass 1024-Bit-RSA-Schlüssel nicht mehr die richtige Verschlüsselungsstärke bieten.

Lange Arithmetik ist ein loser Begriff. Es besteht der Wunsch, die C ++ - Klasse zu verwenden, um lange Zahlen darzustellen und die Operatoren Addition, Subtraktion, Multiplikation usw. zu implementieren. Meine Praxis zeigt, dass dieser Ansatz nur für eine erste Einführung in RSA geeignet ist. Für die Implementierung in Mikrocontrollern müssen wir nicht den gesamten Satz von Operationen implementieren, sondern nur die notwendigsten. Und effizient umsetzen. Nicht in C ++, sondern in C oder gar Assembler.

In der Vergangenheit habe ich die erforderlichen langen arithmetischen Algorithmen zunächst direkt in C ++ implementiert, sie dann in den Assembler dsPIC33F übersetzt, optimiert und anschließend wieder in C übersetzt. Daher erwies sich der C-Code als wesentlich effizienter als der ursprüngliche C ++ - und nur wenig schlechter als Assembler.

1.1. Potenzierung

Offensichtlich benötigen wir zunächst einen Exponentiationsalgorithmus. Hierfür eignet sich der in der Schule untersuchte Algorithmus [1] , der die Operation auf eine Reihe von Multiplikationen reduziert und die Komplexität O (log e) hat, wobei e ein Exponent ist.

Selbst wenn lange arithmetische Algorithmen verwendet werden, führt das Erhöhen einer 2048-Bit-Zahl M auf die Potenz e = 65537 zu einer Bit-Zahl von 2048 * 65537 Bits, was mehr als 16 Megabyte erfordert, um sie im Speicher zu speichern. Die Ausführungszeit der Multiplikation für solche Zahlen überschreitet alle denkbaren Grenzen vollständig. Zum Glück brauchen wir das Ergebnis M e nicht, aber nur der Rest davon geteilt durch n. Da die Exponentiation auf eine Reihe von Multiplikationen reduziert wird, muss nach jeder Multiplikation die Bittiefe des Zwischenergebnisses reduziert werden, wobei der Rest der Division durch n ermittelt wird. Es gibt Theoreme, die garantieren, dass wir das richtige Ergebnis erhalten. Der Algorithmus der Potenzerhöhung und die anschließende Berechnung des verbleibenden Teils des Ergebnisses durch n wird somit zu einem einzigen Modul der Potenzerhöhung , das die Ergebnisse beider Operationen gleichzeitig berechnet und dadurch die RSA-Verschlüsselung gemäß Formel (1) vollständig implementiert.

Um diesen Algorithmus zu implementieren, benötigen wir die Operationen der langen Multiplikation und der Suche nach dem Rest der Division. Privat interessiert uns nicht. In diesem Fall beträgt die Kapazität der Operanden für die Multiplikation jeweils 2048 Bit, 4096-Bit-Zahlen müssen durch 2048 Bit geteilt werden, der Rest der Division ist 2048 Bit lang.

Trotz der guten Leistung ist der obige Algorithmus nur für die Verschlüsselung geeignet, bei der ein "guter" Exponent e = 65537 verwendet wird. Sein Wert ist groß genug für die kryptografische Stärke. Gleichzeitig ist es im Vergleich zur Bittiefe des Schlüssels recht klein. es ist eine Primzahl und es hat auch eine vorteilhafte binäre Darstellung, die die Effizienz der Potenzierung erhöht. Gleichzeitig kann die Zahl d nicht beliebig gewählt werden, sie hängt von p, q und e ab und ist in der Größenordnung vergleichbar mit n, 2048 Bit. Wenn 65537 in 17 langen Multiplikationen und Divisionen zu einer Potenz erhoben werden kann, sind für das Erhöhen der Potenz von d durchschnittlich etwa 3072 solcher Operationen erforderlich, wodurch die Entschlüsselungsleistung im Vergleich zur Verschlüsselung um mehr als das 180-fache verringert wird. Im Falle einer Entschlüsselung können Sie jedoch die Leistung erheblich verbessern. mit Kenntnis von p und q (für die Verschlüsselungsseite sind diese Zahlen normalerweise unbekannt). Infolgedessen unterscheidet sich der Entschlüsselungsalgorithmus bei allen mathematischen Ähnlichkeiten dieser Operationen erheblich von der Verschlüsselung.

Meine einbettbare Implementierung verwendet nur Verschlüsselung (oder den Vorgang der Überprüfung elektronischer Signaturen), sodass das Erhöhen auf eine Modulo n-Potenz als spezialisiertes Verfahren formalisiert werden kann, das eng an den Wert e = 65537 gebunden ist. Im Quellcode heißt diese Prozedur mpi_powm65537 und nimmt die Zahlen M und n als Eingabe. In ihrer Arbeit verwendet sie die Prozeduren der langen Multiplikation und der Suche nach dem Rest der langen Teilung.

1.2. Lange Multiplikation

Es gibt eine Reihe langer Multiplikationsalgorithmen. Am bekanntesten ist die Spaltenmultiplikation. Diese Methode reduziert die Multiplikation langer Zahlen auf eine Reihe von Multiplikationen und Additionen einzelner Ziffern. Befindet sich im Prozessor ein Hardware-Multiplikator, kann in Abhängigkeit von der Bittiefe des Multiplikators eine lange Multiplikation im Basisnummernsystem 256, 65536 oder mehr implementiert werden. Er multipliziert die einzelnen "Zahlen" mit langen Zahlen.

Die Spaltenmultiplikation ist nicht die effizienteste Methode. Seine Komplexität ist O (k 2 ), wobei k die Länge der Operanden im ausgewählten Zahlensystem ist. Effizientere Algorithmen existieren: Karatsuba-Multiplikation, Multiplikation mit der Fourier-Transformation [2, 7] usw. Diese fortgeschrittenen Methoden sind jedoch schwieriger zu implementieren. Aus Zeitgründen beschränkte ich mich darauf, mit einer Spalte zu multiplizieren. Dies ergab eine akzeptable Leistung auf dem ausgewählten Mikrocontroller.

Die Multiplikation „in einer Spalte“ reduziert also eine lange Multiplikation auf eine Reihe kurzer Multiplikationen und Additionen. Es ist sinnvoll, die Bittiefe des vorhandenen Hardware-Multiplikators vollständig zu nutzen. Zum Beispiel gibt es in PIC24- und dsPIC-Mikrocontrollern einen Multiplikator 16 * 16 => 32, dh einen Multiplikator von 16-Bit-Zahlen, der ein 32-Bit-Ergebnis liefert. Somit beträgt die maximal mögliche Basis des Zahlensystems für diese Mikrocontroller 2 16 = 65536.

Darüber hinaus ist es wichtig, dass das Ergebnis 32-Bit ist, da alle diese 32 Bits im Verlauf weiterer Berechnungen benötigt werden. Angenommen, in x86-Prozessoren ist die Bittiefe des Ergebnisses gleich der Bitbreite der Operanden, d.h. 32 Bits. Um einen Überlauf zu vermeiden, muss die Bitlänge der Operanden auf 16 Bit begrenzt werden. Gleiches gilt für einige andere 32-Bit-Prozessoren. Sie müssen auch das Basisnummernsystem 65536 verwenden, wie in einem 16-Bit-Mikrocontroller.

Bei der Multiplikation „in einer Spalte“ können Zwischenergebnisse in einer anderen Reihenfolge berechnet werden. Sagen wir, wie wir es in der Schule gewohnt sind, können Sie zuerst den gesamten ersten Faktor mit einer Ziffer in der Sekunde, dann mit der Sekunde usw. multiplizieren und die Ergebnisse in Zeilen schreiben. Das Ergebnis ist eine Matrix, die dann zeilenweise hinzugefügt werden muss. Bei dsPIC-Mikrocontrollern ist ein anderer Ansatz jedoch effizienter [6]. Die Berechnung der Matrix erfolgt nämlich nicht in Zeilen, sondern in Spalten. Zuerst die erste Spalte, dann die zweite usw. Wenn die Spalte berechnet wird - ihre Werte können sofort addiert werden, Sie erhalten eine Abbildung des Endergebnisses und der Übertragung. Natürlich macht es keinen Sinn, alle Zahlen aus der Spalte zu speichern - Sie können sie stattdessen sofort zur Summe hinzufügen. Bei diesem Ansatz wechseln sich die Multiplikationsoperationen mit den Operationen des Addierens des Ergebnisses zur Batterie ab. Und daher wird es möglich, leistungsstarke zu verwendenDSP- Tools dieses Mikrocontrollers, REPEAT- und MAC-Befehle, die in einem Taktzyklus des Prozessors zwei Operanden aus dem Speicher extrahieren, diese multiplizieren, das Ergebnis zur Batterie addieren und die Werte der Zeiger erhöhen. Obwohl der Algorithmus immer noch ineffizient bleibt - O (k 2 ), kann eine solche optimierte Implementierung mit effizienteren Algorithmen konkurrieren, die mehr Prozessorzyklen für jeden Durchgang des internen Zyklus benötigen.

Die vorzeichenlose lange Multiplikation 2048 * 2048 => 4096 wird von der Subroutine mpi_muluu in meiner Bibliothek verarbeitet .

1.3. Darstellung von Zahlen - Little Endian oder Big Endian?

Jeder Entwickler einer langen arithmetischen Bibliothek muss entscheiden, in welcher Form er Zahlen im Speicher darstellt. Gibt an, ob sich die ersten und wichtigsten Ziffern der Zahl (Little Endian) oder umgekehrt (Big Endian) im Speicher befinden. Das Big Endian-Format ist für eine Person natürlicher, da alle Zahlen, mit denen wir arbeiten, in diesem Format dargestellt werden. Für die interne Darstellung von Zahlen in einem Computer kann es jedoch anders ausfallen.

In unserem Fall werden die Bedingungen durch den langen Multiplikationsalgorithmus bestimmt. Während des Betriebs werden Zahlen im Speicher in Form von 16-Bit- "Ziffern" dargestellt. Es wäre ratsam, diese "Zahlen" als Ganzes aus dem Speicher zu lesen und nicht ein Byte nach dem anderen. In diesem Fall müssen Anweisungen zum Lesen von 16-Bit-Prozessoren verwendet werden. Dies gilt für dsPIC und x86 - Little Endian. Es gibt andere Überlegungen, für die Little Endian vorzuziehen ist, aber das ist das Wichtigste. Um die Leistung zu verbessern, möchten wir die verarbeiteten Informationen in möglichst großen Blöcken aus dem Speicher lesen und dabei unnötige Konvertierungen vermeiden. Deshalb habe ich mich für Little Endian entschieden, obwohl viele Lehrbücher das Big Endian-Format verwenden, und ich bereue es nicht. Diese Wahl führte zu einem schönen und optimalen Code. Natürlich sollten Sie für Big-Endian-Prozessoren das Big-Endian-Format wählen.

1.4. Lange Teilung

Effektive Methoden der Langdivision reduzieren sie auf die Multiplikation mit dem inversen Divisor der Zahl [7]. Diese inverse Zahl wird wiederum auch durch Multiplikation berechnet, beispielsweise mit einer iterativen Methode, die auf der Newton-Methode zum Lösen von Gleichungen basiert [3,7]. Theoretisch könnte dies für RSA sehr vorteilhaft sein, da Sie es viele Male durch dieselbe Zahl teilen müssen, sodass der Kehrwert der Zahl nur einmal berechnet werden muss. Ich habe mich jedoch nicht darum gekümmert, sondern mich auf die Implementierung der in [4] beschriebenen „Spalten“ -Teilung in Bezug auf Computer beschränkt.

Wenn Sie sich an die in der Schule erlernte Methode der Unterteilung „in eine Spalte“ erinnern und versuchen, diese „Stirn“ auf einem Computer zu implementieren, werden Sie feststellen, dass diese Methode mit Ausnahme der Arbeit in einem Binärzahlensystem die lange Unterteilung nicht auf kurze oder andere einfache Operationen reduziert. Tatsächlich ist es nach einer bestimmten Anzahl von Stellen der Dividende erforderlich, diese in den gesamten langen Divisor zu unterteilen, um die nächste Stelle des Quotienten zu erhalten. Wie kann man hier sein? In [4] wird ein Theorem vorgestellt, das es ermöglicht, die Nummer eines Quotienten mit einem kleinen Fehler zu „erraten“. Dies gilt für Fälle, in denen:
  1. die Ziffernkapazität des Teilers ist eine Ziffer kleiner als die Auflösung des Teilrestes;
  2. Die erste Ziffer des Teilers ist größer oder gleich der Hälfte der Basis des Zahlensystems.
Die erste Bedingung ist erfüllt, weil wir die Zahlen der Dividende in der richtigen Weise (ähnlich dem Schulverfahren) in einen Teilrest setzen. Um die zweite Bedingung zu erfüllen, können Sie Dividende und Divisor mit derselben Zahl multiplizieren. Für RSA-Schlüssel ist jedoch garantiert, dass das höchste Bit von n (Teiler) 1 ist. Daher ist die aus den hohen 16 Bits des Schlüssels gebildete 16-Bit- "Ziffer" größer oder gleich 32768. Daher ist für RSA das Umwandeln der Divisionsoperanden nicht erforderlich .

Um die Nummer des Quotienten zu „erraten“, müssen Sie die ersten beiden Ziffern des Teilrestes durch die erste Ziffer des Divisors dividieren. Der erhaltene Wert ist entweder gleich der wahren Ziffer des Quotienten oder übersteigt ihn um nicht mehr als 2. Wenn wir 499 durch 50 teilen und 49 durch 5 teilen, erhalten wir 9, was mit der wahren ersten Ziffer des Quotienten übereinstimmt. Wenn wir 890 durch 99 teilen und dann 89 durch 9 teilen, erhalten wir 9, was 1 mehr als notwendig ist. In anderen Fällen wird die Schätzung um 2 überschätzt, dies wird jedoch durch den Satz nie wieder garantiert.

Die Division von zwei Ziffern des Teilrestes durch eine Ziffer des Teilers ist eine "kurze" Division, deren Hardware-Unterstützung sehr wünschenswert ist. DsPIC33 unterstützt Hardware zum Teilen von 32-Bit-Zahlen in 16-Bit-Zahlen mit 16-Bit-Quotienten und dem Rest. Dies ist völlig ausreichend, um eine lange Division im Zahlensystem auf der Basis 2 16 = 65536 zu implementieren . Für x86 beträgt die maximale Bittiefe der Dividende 32 Bit, was auch die Grundlage des Zahlensystems 65536 darstellt.

Nach dem Erraten der Zahlen des Quotienten ist es notwendig, diese Ziffer mit dem Divisor zu multiplizieren und das Produkt vom Teilrest abzuziehen. Wenn das Ergebnis kleiner als 0 ist, addieren Sie den Divisor zurück und reduzieren Sie die Schätzung des Quotienten des Quotienten um 1. Wenn der Saldo immer noch kleiner als 0 ist, addieren Sie den Divisor erneut und reduzieren Sie den Quotienten des Quotienten erneut. Als Ergebnis erhalten wir den korrekten Wert des Quotienten des Quotienten und den korrekten Wert des Teilrestes, um den Divisionsprozess fortzusetzen.

RSA muss den Quotienten nicht kennen, sondern nur den Rest der Division. In diesem Zusammenhang habe ich die Funktion mpi_moduu geschriebenBerechnung nur den Rest. Für einen 2048-Bit-RSA ist es erforderlich, 4096-Bit-Zahlen in 2048-Bit-Zahlen mit einem 2048-Bit-Rest zu unterteilen. Mein Verfahren führt die Aufteilung "an Ort und Stelle" durch: Die Dividende wird am Ende des Verfahrens durch den Rest ersetzt. Dies erhöht die Effizienz, da der "Abriss" der nächsten Ziffer von der Dividende in ein einfaches Inkrement des Zeigers übergeht. Außerdem wird kein zusätzlicher Speicher benötigt, um den Teilrest und den privaten zu speichern (da er nicht gespeichert wird).

Damit der obige Unterteilungsalgorithmus funktioniert, sind die folgenden Komponenten der Langarithmetik erforderlich:
  1. Multiplikation einer langen Zahl mit einer kurzen (mit einer Ziffer);
  2. Subtraktion langer Zahlen;
  3. Hinzufügung von langen Zahlen;
  4. lange Zahlen vergleichen
welche unten beschrieben werden.

Die Komplexität des langen Divisionsverfahrens ist O (k 2 ) für kurze Multiplikationen und O (k) für kurze Divisionen, wobei k die Anzahl der Bits des Divisors in der Basisnotation 65536 ist.

1.5. Lange Addition und Subtraktion

Das Schreiben von Prozeduren zum Hinzufügen von mpi_add und zum Subtrahieren von mpi_sub erfordert keinen besonderen Einfallsreichtum und keine komplexen Methoden. Jeder Prozessor hat einen Befehl wie ADC, der zwei Zahlen und ein Übertragsbit aus der vorherigen Addition hinzufügt. Wenn Sie ADC-Befehle kaskadieren, können Sie Operanden beliebiger Kapazität hinzufügen. Das Obige gilt für die Subtraktion und den SBC-Befehl. Schwierigkeit - O (k). Meine Prozeduren geben beim Addieren oder Subtrahieren das Übertragsflag zurück, das in der Divisionsprozedur verwendet wird.

In C gibt es keinen Zugriff auf Prozessor-Flags, daher müssen Sie Nummern mit größerer Kapazität als erforderlich verwenden. Wenn Sie beispielsweise zwei 16-Bit-Zahlen hinzufügen, müssen Sie mindestens 32-Bit-Zahlen zum Speichern des Ergebnisses und zum Übertragen verwenden, um einen Überlauf zu vermeiden. Dies führt wiederum zu der Notwendigkeit, im auf 65536 auf 32-Bit-Prozessoren basierenden Zahlensystem zu arbeiten. Nun, in Assembler entspricht die Ziffernkapazität der Ziffern langer Zahlen dem Prozessorbit, 16 Bits im Fall von dsPIC.

1.6. Langer Vergleich

Ein Vergleich kann effektiver als eine Subtraktion implementiert werden, wenn Sie mit der Verarbeitung mit hohen Ziffern beginnen. Wenn die führende Ziffer einer Zahl größer ist als die führende Ziffer einer anderen, dann ist die ganze Zahl größer, die verbleibenden Ziffern können nicht verglichen werden. Somit ist die Komplexität des Vergleichsverfahrens die gleiche wie beim Subtrahieren von O (k), jedoch ist der statistische Vergleich schneller. Die Prozedur in der Quelle heißt mpi_cmp .

1.7. Multipliziere eine lange Zahl mit einer kurzen

Die Multiplikation einer langen Zahl mit einer kurzen Zahl (d. H. Mit einer Ziffer), die beim Teilen langer Zahlen verwendet wird, unterscheidet sich im Prinzip nicht von der langen Multiplikation. Es fehlt jedoch eine Ebene von Verschachtelungszyklen. Das Multiplizieren der Bitnummer k mit einer Ziffer in dem System, basierend auf 65536, führt zu der Bitnummer k + 1. Da im Divisionsverfahren eine solche Multiplikation unmittelbar auf die Subtraktion des Produkts vom Teilrest folgt, habe ich beide Operationen gleichzeitig im mpi_mulsubuuk- Verfahren implementiert , das die 2048-Bit-Zahl mit 16-Bit multipliziert und das Produkt von der 2064-Bit-Zahl subtrahiert, was zu einer gewissen Speicher- und Zeitersparnis führt Ausführung.

Das ist die ganze Zeit, die für die RSA-Verschlüsselung erforderlich ist.

2. Schlüsselgenerierung


Die Schlüsselerzeugung in RSA beginnt mit der Auswahl von zwei großen Primzahlen p und q. Wenn sie sagen: "RSA-Schlüssel mit einer Länge von 2048 Bits", bedeuten sie, dass das Produkt p * q eine 2048-Bit-Zahl ist, deren höchstes Bit 1 ist (andernfalls wäre es in einigen Interpretationen eine 2047-Bit-Zahl). Die Bits der Zahlen p und q sind nicht einzeln festgelegt, aber ich habe festgestellt, dass p und q in GnuPG so generiert werden, dass jedes von ihnen eine 1024-Bit-Zahl mit dem höchsten Bit gleich 1

ist. Artikel nicht mögen. In vielen Situationen, einschließlich meiner, ist es jedoch nicht erforderlich, Schlüssel auf dem Mikrocontroller zu generieren. Aus diesem Grund habe ich versucht, mit GnuPG erfolgreich Schlüssel zu generieren.

Zunächst müssen Sie in GnuPG wie gewohnt ein Schlüsselpaar (öffentlich + privat) generieren. Stellen Sie gleichzeitig sicher, dass der RSA-Schlüssel mit der erforderlichen Länge abgerufen wird (dort sind jetzt standardmäßig 2048 Bit installiert). Trotz andauernder Aufrufe von GnuPG sollten Sie sich weigern, diesen Schlüssel mit einem Passwort zu schützen und im Klartext auf der Festplatte zu speichern. Welchen Unterschied macht es, wir werden diesen Schlüssel immer noch in seine konstituierenden Zahlen p, q, n, d „ausnehmen“ und sie zumindest vorübergehend in offener Form auf der Festplatte speichern.
Der Befehl, der in neuen Versionen von gpg nicht dokumentiert ist, kann einen Schlüssel aus der GnuPG-Schlüsseldatenbank exportieren
gpg --export-secret-keys --armor [key_id] >filename.asc

Dabei ist key_id die Schlüsselkennung, die durch Aufrufen von gpg --list-secret-keys abgerufen werden kann.

Sie erhalten eine Textdatei mit Inhalten wie:
-----BEGIN PGP PRIVATE KEY BLOCK-----
Version: GnuPG v2.0.17 (MingW32)
lQOXBE9IdyABCADGT3+Dj0dsVPSkzW+zPlfXc4AsuKpkE9GJNAYD3mrcF70nwk1L
...

Wie erhält man von hier die Zahlen, aus denen der Schlüssel besteht? Es stellte sich heraus, dass es im gpg-Programm selbst und den enthaltenen Hilfsprogrammen KEINE derartigen Tools gibt. Es gibt nur ein Drittanbieter-Dienstprogramm " pgpdump ", das den Inhalt von PGP Private Key Block interpretiert und in lesbarer Form anzeigt. Wenn Sie es wie folgt aufrufen:
pgpdump -i filename.asc >filename.txt

Wir werden die Parameter bekommen, die wir brauchen:
Old: Secret Key Packet(tag 5)(919 bytes)
	Ver 4 - new
	Public key creation time - Sat Feb 25 07:52:32 FLE Standard Time 2012
	Pub alg - RSA Encrypt or Sign(pub 1)
	RSA n(2048 bits) - c6 4f 7f ...
	RSA e(17 bits) - 01 00 01 
	RSA d(2040 bits) - a5 c5 ce ...
	RSA p(1024 bits) - d0 28 ad ...
	RSA q(1024 bits) - f3 e3 61 ...
	RSA u(1024 bits) - 90 8b 22 ...
	Checksum - 3e 22
...
Hier gebe ich überhaupt keine reellen Zahlen an, aber Sie können sie leicht für Ihren Schlüssel bekommen. Sie müssen nur bei Bedarf kopiert werden, ohne zu vergessen, dass sie in dieser Datei im Big Endian- Format vorliegen . Um sie in Verbindung mit meinen Prozeduren zu verwenden, müssen Sie sie in Little Endian konvertieren, dh alle Bytes in umgekehrter Reihenfolge neu anordnen.

Vergessen Sie auch nicht, dass der öffentliche Schlüssel nur die Zahlen e und n sind. Die verbleibenden Nummern sind ein geheimer (privater) Schlüssel. Wenn Sie einen dieser Schlüssel (d, p, q, u) kennen, können Sie den Rest leicht berechnen und Ihre Nachricht entschlüsseln oder eine elektronische Signatur erstellen.

3. Entschlüsselung


Da sich die meisten RSA-Implementierungen irgendwo in den Zahlen verstecken, aus denen die Schlüssel bestehen, und verschlüsselte Nachrichten in alle Arten von Paketen einschließen, ist es erforderlich, zusätzlich zur Verschlüsselung eine Entschlüsselung zu implementieren, um die in Abschnitt 1 beschriebenen Routinen zu überprüfen.

Wie oben erwähnt, kann die Entschlüsselungsformel (2) "frontal" implementiert werden. Und obwohl es hunderte Male langsamer als die Verschlüsselung arbeitet, wird dies aufgrund des großen Wertes des Exponenten d für viele Anwendungen ausreichen. Wenn die Operation beschleunigt werden soll, wird der Trick unter Verwendung des in [5] beschriebenen chinesischen Restsatzes angewendet . Ich habe keine schönen Quellcodes, die all dies implementieren, daher gebe ich nur eine verbale Beschreibung des Algorithmus:

Zuerst wird die Anzahl d «Splits“ in zwei Teile, d p = d mod (p-1) und d q = d mod (q-1) . In diesem Fall ist die Bittiefe jedes Teils zweimal kleiner als die "Schlüssellänge" (Bitbreite n). Als nächstes wird q inv so berechnet , dass (q * q inv ) mod p = 1. Das heißt, q inv ist die Inverse von q im Ringmodulo p. In der englischen Terminologie wird dies als " modulare multiplikative Inverse " bezeichnet. Zur Berechnung des inversen Elements wird üblicherweise der erweiterte euklidische Algorithmus verwendet .

Wenn die Zahlen d p , d q und q inv gefunden, wird die Nachrichtenentschlüsselung mit der RSA-Methode wie folgt durchgeführt:
  1. m 1 : = (C d p ) mod p
  2. m 2 : = (C d q ) mod q
  3. h: = ((m 1 -m 2 ) * q inv ) mod p
  4. M: = m 2 + h * q

Bitte beachten Sie, dass die Berechnungen in den Schritten 1-3 mit einer reduzierten Bitkapazität durchgeführt werden: 1024 Bits anstelle von 2048 für Formel (2). Da Modulo-Exponentiationsalgorithmen eine kubische Komplexität aufweisen (quadratisch aus Multiplikation und Division und sogar linear aus „schneller“ Exponentiation), erhalten wir einen Geschwindigkeitsgewinn, wenn wir mit der halben Ziffernkapazität von Zahlen das 8-fache arbeiten. Da nun zwei teure exponentielle Modulo-Operationen aufgerufen werden, wird die Gesamtverstärkung im Vergleich zur direkten Anwendung der Formel (2) viermal erhalten. Obwohl dies eine Menge ist, ist es immer noch nicht so bedeutend, dass es in allen Fällen notwendig ist, die direkte Anwendung der Formel (2) aufzugeben, insbesondere angesichts der Schwierigkeiten bei der Berechnung von q inv .

Erwähnt werden sollte eine interessante Sicherheitslücke in Bezug auf die „schnelle“ Potenzierung. Dies wird in der libgcrypt-Quelldatei mpi-pow.c erwähnt. Der Angriff heißt "Yarom / Falkner Flush + Reload-Cache-Side-Channel-Angriff" und ermöglicht die Verwendung der Manipulationen mit dem Second-Level-Cache des Prozessors (der für alle Kerne gilt) für nicht autorisierte Anwendungen, um den Wert von d oder seinen Teilen d p und d q vollständig zu bestimmen. Beides bedeutet die vollständige Offenlegung des geheimen Schlüssels, sodass der Angreifer alle mit diesem Schlüssel verschlüsselten Nachrichten vollständig lesen oder eine elektronische Signatur erstellen kann. Nehmen wir an, Ihr Programm entschlüsselt etwas mit einem geheimen Schlüssel, und das Schadprogramm funktioniert derzeit auf demselben System, jedoch im Auftrag eines anderen Benutzers. Sie wissen also nichts darüber. Und in diesem Moment tritt ein Schlüsselleck auf.

Fazit


Ich habe ein C-Sprachmodul eingeführt, das für die Implementierung von RSA-Verschlüsselung oder die Überprüfung elektronischer Signaturen auf 32-Bit-Embedded-Prozessoren mit Taktfrequenzen in der Größenordnung von 40 MHz und einem Hardware-Multiplikator geeignet ist. Wenn Sie die C-Quelle in Assembler umwandeln und Materialien verwenden [6], erhalten Sie eine Implementierung für dsPIC33F, die einen RSA-2048-Datenblock für eine Zeit von ca. 10 ms bei einer Prozessortaktrate von 80 MHz verschlüsselt.

Quellen können von GitHub heruntergeladen werden .

Die RSA-Entschlüsselung (oder die Erzeugung elektronischer Signaturen) kann auch auf Mikrocontrollern dieser Klasse implementiert werden, dieser Vorgang ist jedoch ungefähr 45-180-mal langsamer.

Es ist möglich, die Bibliothek zu beschleunigen, indem effektive Multiplikations- und Divisionsalgorithmen verwendet werden, die im Artikel durch Links erwähnt werden.

Ich empfehle, meine Routinen nur für eingebettete Anwendungen zu verwenden, und für "große" Computer ist es in den meisten Fällen besser, Standardtools wie Windows CryptoAPI oder libgcrypt zu verwenden.

Referenzliste


1. A. G. Kushnirenko, G.V. Lebedev, R.A. Svoren. Grundlagen der Informatik und Informatik. M .: 1990, S. 133.
2. Wikipedia. Schoenhage-Strassen- Multiplikationsmethode
3. Wikipedia. " Lange Arithmetik "
4. Donald Knuth. "Die Kunst des Programmierens", Band 2. Erhaltene Algorithmen
5. Wikipedia, Artikel " RSA (Kryptosystem) ", Abschnitt "Ein gelungenes Beispiel"
6. Erich Wegener, Mario Werner. "Evaluierung von 16-Bit-Prozessoren für die Kryptographie mit elliptischen Kurven." Institut für Angewandte Informationsverarbeitung und Kommunikation (IAIK), TU Graz
7. William H. Press et al. Numerische Rezepte in C ++, Zweite Ausgabe, Cambridge University Press 2002, Seite 922

Jetzt auch beliebt: