DE69612335T2

DE69612335T2 - System und Verfahren zur Kommunikation von verschlüsselten Nachrichten unter Verwendung von RSA mit modularer Reduktion für schnelle Entschlüsselung

Info

Publication number: DE69612335T2
Application number: DE69612335T
Authority: DE
Inventors: Robert Naciri
Original assignee: Oberthur Card Systems SA France
Current assignee: Idemia France SAS
Priority date: 1995-07-26
Filing date: 1996-07-17
Publication date: 2001-08-30
Anticipated expiration: 2016-07-18
Also published as: FR2737369A1; US5761310A; EP0756398B1; EP0756398A1; JPH0946332A; DE69612335D1

Description

Die vorliegende Erfindung betrifft ein System zur Kommunikation von verschlüsselten Nachrichten unter Verwendung von RSA, das Schlüsselzahlen "d" und "e" und eine Modulzahl N voraussetzt, wie "N", die das Produkt von zwei Faktoren "p" und "q" ist, die Primzahlen sind, N = p.q, und daß e.d = 1modφ(N) wo (p(N) die Euler'sche Anzeigefunktion ist, welches System einerseits wenigstens eine Verschlüsselungsvorrichtung, gebildet aus:
- Aufteilungsmitteln, um die zu verschlüsselnde Nachricht in wenigstens einen Teil der zu verschlüsselnden Nachricht aufzuteilen,
- Potenziermittel, um auf jeden Teil der zu verschlüsselnden Nachricht eine modulare Potenzieroperation des Moduls "N" und mit einem Exponenten gleich einer ersten der Schlüsselzahlen durchzuführen, um einen Teil der verschlüsselten Nachricht zur Verfügung zu stellen, und andererseits wenigstens eine Entschlüsselungsvorrichtung umfaßt.
Die Erfindung betrifft auch ein Verfahren zur Anwendung in dem System einer Benutzervorrichtung, wie einer Chipkarte, umfassend auf demselben Support eine Verschlüsselungsvorrichtung und eine Entschlüsselungsvorrichtung und ein sogenanntes Vertraulichkeits- bzw. Überprüfungs-Serverzentrum, um Informationen zwischen den verschiedenen Benutzervorrichtungen zu bearbeiten.
Ein derartiges Verfahren ist in dem Artikel mit dem Titel "Fast decipherement algorithm for a public-Key Cryptosystem" beschrieben, dessen Autoren mm. J. J. Quisquater und C. Couvreur sind, der in der Zeitschrift ELECTRONICS LETTERS vom 14. Oktober 1982 erschienen ist. Dieses Verfahren impliziert die Verwendung des chinesischen Rest-Theorems, um eine schnelle Entschlüsselung zu erhalten, ohne die Qualitäten des RSA-Verfahrens zu verschlechtern.
Die vorliegende Erfindung, die ebenfalls auf dem chinesischen Rest-Theorem basiert, schlägt ein System vor, für welches das Entschlüsselungsverfahren auch in einem sehr großen Maßstab betreffend die Geschwindigkeit des Entschlüsselungsvorgangs verbessert ist.
Deshalb ist ein derartiges System dadurch bemerkenswert, daß es wenigstens eine Entschlüsselungsvorrichtung umfaßt, gebildet aus:
- Mitteln zur Bestimmung des Moduls, um ein aus diesen Faktoren gewähltes Entschlüsselungsmodul zu bestimmen,
- ersten modularen Reduktionsmitteln, um eine erste modulare Reduktion auf der Zahl "d" mit einem Modul gleich dem um eine Einheit verringerten Entschlüsselungsmodul durchzuführen, um eine reduzierte Zahl zur Verfügung zu stellen,
- zweiten Reduktionsmitteln, um eine zweite modulare Reduktion auf jedem Teil der verschlüsselten Nachricht mit einem Modul gleich dem Entschlüsselungsmodul durchzuführen, um einen reduzierten Teil der verschlüsselten Nachricht zur Verfügung zu stellen,
- zweiten Potenziermitteln, um eine modulare Potenzierung auf jedem reduzierten Teil der verschlüsselten Nachricht mit einem Modul gleich dem Entschlüsselungsmodul und mit einem Exponenten gleich der reduzierten Zahl durchzuführen, um die Nachricht wiederherzustellen.
So ist es dank der durch die Erfindung vorgeschlagenen Maßnahmen nicht mehr notwendig, die Operation einer Kombination der Reste der in dem obengenannten Artikel gezeigten Formel (1) durchzuführen.
Die nachfolgende Beschreibung, die in bezug auf die beiliegenden Zeichnungen gemacht ist, wobei sie insgesamt als nicht einschränkendes Beispiel gegeben wird, wird besser verständlich machen, wie die Erfindung realisiert werden kann.
Fig. 1 zeigt ein Kommunikationssystem in Übereinstimmung mit der Erfindung.
Fig. 2 zeigt ein Verschlüsselungsflußdiagramm in Übereinstimmung mit der Erfindung.
Fig. 3 zeigt ein Entschlüsselungsflußdiagramm in Übereinstimmung mit der Erfindung.
Fig. 4 zeigt das Schema einer Benutzervorrichtung.
Fig. 5 zeigt ein System in Übereinstimmung mit der Erfindung, umfassend einen sogenannten Vertraulichkeitsserver und eine Mehrzahl von Vorrichtungen zwischen Benutzern.
In der Fig. 1 bezeichnet das Bezugszeichen 1 die Verschlüsselungsvorrichtung. Diese erhält eine Nachricht M, beispielsweise "BONJOUR" (Guten Tag). Diese Nachricht ist in Teile der zu verschlüsselnden Nachricht durch Trennungs- bzw. Aufteilungsmittel 3 zerlegt. Diese Teile bestehen jeweils aus Buchstaben, die sie zusammensetzen, und man erhält eine Folge von numerischen Codes, beispielsweise die Dezimalnummerncodes M1 = 66, M2 = 79, M3 = 78, M4 = 74, M5 = 79, M6 = 85, M7 = 82, welche die ASCI-Codes von "BONJOUR" darstellen.
Potenziermittel 5 führen Potenzieroperationen an diesen Nummerncodes aus, indem sie die Parameter "e" und "N" entsprechend Maßnahmen nehmen, deren erste sich direkt aus der Erfindung ergibt:
- Es werden die Zahlen p und q größer als 255 genommen:
p = 263 und q = 311, so daß N = p.q = 81793.
- Man wählt "e" so, daß es mit p - 1 und q - 1 eine Primzahl ist, nämlich:
e = 17.
- Man bestimmt nun d: e.d = 1modφ(N)
In dem Fall, wo p und q Primzahlen sind, ist
φ(N) = (p - 1).(q - 1):
e.d = 1mod(40610).
Unter den "d", die der obigen Beziehung genügen, kann man 54943 nehmen. Im Prinzip ist "d" nicht bei der Verschlüsselungsvorrichtung 1 bekannt. Die Mittel 5 können nun die Nachricht codieren, indem sie an jedem der zuvor genannten Codes die modulare Potenzieroperation durchführen:
C1 = Mi¹&sup7;mod(N) i = 1... 7
worin die codierte Nachricht die verschlüsselten Teile umfaßt:
C1 = 62302, C2 = 47322, C3 = 74978, C4 = 00285, C5 = 47322, C6 = 09270, C7 = 54110.
In Übereinstimmung mit der Erfindung ist für eine Entschlüsselung dieser Nachricht eine Entschlüsselungsvorrichtung 10 vorgesehen. Diese Vorrichtung verwendet ein erstes Bestimmungsmittel des Entschlüsselungsmoduls unter ·den Zahlen "p" und "q", man wählt vorzugsweise die kleinsten, um die Rechnungen ökonomischer zu gestalten, d. h.:
p ( = 263)
zweite Mittel führen eine modulare Reduktionsoperation auf der Zahl "d" durch dr = 54943 mod&sub2;&sub6;&sub2;
= 185
Man reduziert anschließend entsprechend dem Modul "p" die Teile der verschlüsselten Nachricht.
Cr1 = 62302 mod&sub2;&sub6;&sub3;
= 234
oder entsprechend Cr2 = 245, Cr3 023, Cr4 = 022, Cr5 = 245, Cr6 = 065, Cr7 = 195, worin die entschlüsselten Teile der Nachricht sind:
m&sub1; = Cr1¹&sup8;&sup5;mod263 = 66
m&sub2; = Cr2¹&sup8;&sup5;mod263 = 79
m&sub3; = Cr3¹&sup8;&sup5;mod263 = 78
m&sub4; = Cr4¹&sup8;&sup5;mod263 = 74
m&sub5; = Cr5¹&sup8;&sup5;mod263 = 79
m&sub6; = Cr6¹&sup8;&sup5;mod263 = 85
m&sub7; = Cr7¹&sup8;&sup5;mod263 = 82
Die Nachricht "m" ist nun durch Verkettung und durch Transkription in übliche Buchstaben durch die Endwiederherstellungsmittel 4 wiederhergestellt. Wenn alles gut verlaufen ist, ist m = M.
Die Verschlüsselungsvorrichtung 1 und die Entschlüsselungsvorrichtung 10 sind tatsächlich ausgehend bzw. auf Basis von programmierten Prozessoren realisiert, um die in den nachfolgenden Fig. 2 und 3 gezeigten Flußdiagramme auszuführen.
Das Flußdiagramm der Fig. 2 erklärt die Funktionsweise der Vorrichtung 1. Das Feld K1 zeigt einen Test an, der auf jeden Teil der verschlüsselten Nachricht angewandt wird. Wenn dieser Wert jenen des gewählten Entschlüsselungsmoduls übersteigt (daher der kleinste unter "p" und "q"), wird im Feld K2 erklärt, daß es einen Fehler gegeben hat. Wenn nicht, wird zum Feld K5 weitergegangen, wo die eigentliche Verschlüsselungsoperation, d. h. eine modulare Potenzierung, durchgeführt wird. Man erhält so verschlüsselte Teile der Nachrichten C1.
Das Flußdiagramm der Fig. 3 zeigt die Entschlüsselungsoperationen, die durch die Entschlüsselungsvorrichtung 10 durchgeführt werden. Dieses Flußdiagramm zeigt in dem Feld K10 eine vorangehende bzw. vorbereitende Operation einer Reduktion auf der Zahl d, um eine reduzierte Schlüsselzahl "dr" zur Verfügung zu stellen. Das Feld K12 ist eine modulare Reduktionsoperation gemäß "p", die auf den Teilen der verschlüsselten Nachrichten durchgeführt wird, und das Feld K14 ist eine modulare Potenzierung des Moduls "p", deren Exponent "dr" ist, auf den verschlüsselten Teilen der Nachricht.
Die Verschlüsselungs- und Entschlüsselungsvorrichtungen können auf einem gleichen Support eingefügt sein, um so eine Benutzervorrichtung auszubilden. Die Vorrichtungen können nun untereinander unter Verwendung des Verschlüsselungsverfahrens gemäß der Erfindung kommunizieren.
Fig. 4 zeigt die Struktur einer Benutzervorrichtung. Diese Vorrichtung ist auf Basis eines aus einem physikalischen Gesichtspunkt gesicherten Mikrocontrollers bzw. Mikrosteuerbausteins realisiert, wie beispielsweise dem 83C852, der durch Philips hergestellt ist. Ein derartiger Mikrocontroller 31 ist in Fig. 4 dargestellt und ausgehend von einem Mikroprozessor 32, einem Direktzugriffs- bzw. Lebendspeicher 33 und einem Festspeicher 34 zusammengesetzt, welcher insbesondere die Instruktionen der Funktionsweise für die Durchführung der Erfindung, insbesondere die Verschlüsselungsoperationen und die Entschlüsselungsoperationen, die bereits beschrieben wurden, enthält. Er umfaßt auch einen EEPROM-Speicher 35, um verschiedene, vorgegebene Daten zu enthalten, wie den geheimen Schlüssel der Karte, den öffentlichen Schlüssel eines Dritten, mit welchem er Informationen austauscht... Er ist auch aus einer Rechnereinheit 36 zusammengesetzt, um die notwendigen Operationen für die Realisierung der Verschlüsselungs- bzw. Kryptografiefunktionen zu übernehmen, einer Steuereinheit 37 von Eingängen/Ausgängen, die unter anderem mit einem Eingang I/O des Mikrocontrollers 31 verbunden ist. Die zuvor genannten Elemente des Mikrocontrollers 31 sind untereinander durch einen Bus 38 verbunden.
Jedes ergänzende Detail kann in der Beschreibung des zuvor genannten Mikrocontrollers 83C852 gefunden werden.
Ein wichtiges Beispiel einer Anwendung der Erfindung ist die Übertragung eines Schlüssels DES mit Hilfe von RSA, wie dies in dem Artikel "Threats of Privacy and Public Keys for protection" von Jim Bidzos, erschienen in "PROCEEDINGS OF COMPCON91, 36th IEEE COMPUTER SOCIETY INTERNATIONAL CONFERENCE - vom 25. Februar bis 1. März 1991, San Francisco - NEW YORK (US), erschienen ist. Das Protokoll für die Änderung des Schlüssels DES der Verbindung bzw. Sitzung zwischen zwei Benutzern A und B unter Zwischenschaltung eines öffentlichen Kanals kann folgendes sein.
Es seien {nA, dA} und {nB, dB} die entsprechenden geheimen Schlüssel der Benutzer A und B.
Beispielsweise möchte A den Verbindungsschlüssel KS an B übertragen.
- Benutzer A
m = Ks
Es wird die Chiffrierung unter Benutzung des öffentlichen Schlüssels eB durchgeführt.
CAg = meB
und man überträgt das Kryptogramm CAB über den öffentlichen Kanal.
- Benutzer B
Empfang des Kryptogramms CAB
Dechiftrierung des Kryptogramms m = CABdB
Benutzung des Schlüssels Ks
Allgemein ist Ks deutlich kleiner als ein RSA-Schlüssel. Ks kann ein Verbindungsschlüssel DES in der Größenordnung von 56 binären Elementen sein und p und q sind in der Größenordnung von 256 Bits.
Viele offizielle Institutionen untersagen eine Chiffrierung von Nachrichten in den öffentlichen Kommunikationen. Die Erfindung bezieht sich insbesondere darauf, daß man, um dieses Verbot zu vermeiden, einen Vertraulichkeitsserver SC benutzt. Es wurde dieser Fall in Fig. 5 dargestellt. Diese Figur erläutert den Fall, wo eine Mehrzahl von Benutzervorrichtungen A, B, ... X miteinander unter Zwischenschaltung eines Vertraulichkeitsservers SC kommunizieren können. Dieser Server SC besitzt alle Kenntnisse, um unverschlüsselt alle Nachrichten, welche die verschiedenen Benutzer austauschen, zu kennen.
Als Beispiel wird der Fall erklärt, wo der Benutzer A einen Schlüssel DES KAB an den Benutzer B kommunizieren bzw. übertragen möchte. Daher chiffriert bzw. verschlüsselt A den Schlüssel KAB mit Hilfe des öffentlichen Schlüssels eB des Servers SC, welcher selbst diesen bei seinem Erhalt entschlüsselt, worauf er diesen mit dem öffentlichen Schlüssel eB von B verschlüsselt. Schließlich entschlüsselt B das Kryptogramm, um den durch A anfänglich versendeten Schlüssel wiederzufinden.
Man sieht daher, daß sich in diesem Fall das Verfahren auch auf das Niveau der Entschlüsselung des Benutzers B ebenso wie diejenige des Servers SC bezieht. Also wird die Erfindung genutzt, um eine gute Verfügbarkeit des Servers für eine Mehrzahl von Benutzern zu erhalten. Der durch die Erfindung gebrachte Gewinn bei den Berechnungen ist insbesondere geschätzt.

Claims

1. System zur Kommunikation von verschlüsselten Nachrichten unter Verwendung von RSA, das Schlüsselzahlen "d" und "e" und eine Modulzahl N voraussetzt, wie "N", die das Produkt von zwei Faktoren "p" und "q" ist, die Primzahlen sind, N = p.q, und daß e.d = 1modφ(N), wo 9(N) die Euler'sche Anzeigefunktion ist, welches System einerseits wenigstens eine Verschlüsselungsvorrichtung, gebildet aus:

- Aufteilungsmitteln (3), um die zu verschlüsselnde Nachricht in wenigstens einen Teil der zu verschlüsselnden Nachricht aufzuteilen, der zumindest so klein ist wie die Faktoren p und q,

- Potenziermittel (5), um auf jeden Teil der zu verschlüsselnden Nachricht eine modulare Potenzieroperation des Moduls "N" und mit einem Exponenten gleich einer ersten der Schlüsselzahlen durchzuführen, um einen Teil der verschlüsselten Nachricht zur Verfügung zu stellen, und andererseits wenigstens eine Entschlüsselungsvorrichtung umfaßt,

dadurch gekennzeichnet, daß die Entschlüsselungsvorrichtung gebildet ist aus:

- Mitteln zur Bestimmung des Moduls (10, 14), um ein aus diesen Faktoren gewähltes Entschlüsselungsmodul zu bestimmen,

- ersten modularen Reduktionsmitteln (10, 12), um eine erste modulare Reduktion auf der Zahl "d" mit einem Modul gleich dem um eine Einheit verringerten Entschlüsselungsmodul durchzuführen, um eine reduzierte Zahl zur Verfügung zu stellen,

- zweiten Reduktionsmitteln (K12), um eine zweite modulare Reduktion auf jedem Teil der verschlüsselten Nachricht mit einem Modul gleich dem Entschlüsselungsmodul durchzuführen, um einen reduzierten Teil der verschlüsselten Nachricht zur Verfügung zu stellen,

- zweiten Potenziermitteln (K14), um eine modulare Potenzierung auf jedem reduzierten Teil der verschlüsselten Nachricht mit einem Modul gleich dem Entschlüsselungsmodul und mit einem Exponenten gleich der reduzierten Zahl durchzuführen, um die Nachricht wiederherzustellen.

2. Verschlüsselungs-Entschlüsselungsverfahren des RSA-Typs, gemäß welchem für eine Verschlüsselung einer Nachricht:

- Anzahlen von Schlüsseln "d" und "e" und eine Modulzahl N, wie "N", die das Produkt von zwei Faktoren "p" und "q" ist, die Primzahlen sind, N = p.q, und daß e.d = 1mod φ(N), wo φ(N) die Euler'sche Anzeigefunktion ist, definiert werden,

- die Nachricht in Teile der zu verschlüsselnden Nachricht zerlegt (3) wird,

- jeder Teil einer modularen Potenzierfunktion (5) des Moduls "N" und mit einem Exponenten gleich einer der ersten Schlüsselzahlen unterworfen wird, um Teile der verschlüsselten Nachricht zur Verfügung zu stellen und um sie zu entschlüsseln:

- die Teile der verschlüsselten Nachrichten einer Potenzieroperation einer Entschlüsselung unterworfen werden, um die Teile der entschlüsselten Nachricht zur Verfügung zu stellen,

dadurch gekennzeichnet, daß:

- die Teile der zu verschlüsselnden Nachricht in Form von Zahlen, welche zumindest kleiner als die Faktoren p und q sind, dargestellt werden,

- die Potenzieroperation der Entschlüsselung umfaßt:

- einen Bestimmungsschritt eines Entschlüsselungsmoduls (10, 14) gewählt unter den Faktoren,

- einen Vorabschritt, um eine erste modulare Reduktion (10, 12) auf der Zahl "d" mit einem Modul gleich dem um eine Einheit verringerten Verschlüsselungsmodul durchzuführen, um eine reduzierte Zahl zur Verfügung zu stellen, einen Schritt, um eine zweite modulare Reduktion (K12) auf die Teile der verschlüsselten Nachrichten mit einem Modul gleich dem Entschlüsselungsmodul durchzuführen, um reduzierte Teile der verschlüsselten Nachricht zur Verfügung zu stellen,

- einen modularen Potenzierschritt (K14), der auf die reduzierten Teile der verschlüsselten Nachricht mit einem Modul gleich dem Entschlüsselungsmodul und mit einem Exponenten gleich der reduzierten Zahl durchgeführt wird.

3. Verwendung des Systems zur Kommunikation von verschlüsselten Nachrichten gemäß Anspruch 1 in einer Benutzervorrichtung, wie einer Chipkarte, umfassend eine Verschlüsselungsvorrichtung, gebildet aus:

- Aufteilungsmitteln (3), um die zu verschlüsselnde Nachricht in wenigstens einen Teil der zu verschlüsselnden Nachricht aufzuteilen,

- Potenziermitteln (5), um auf jeden Teil der zu verschlüsselnden Nachricht eine modulare Potenzierfunktion des Moduls "N" und mit einem Exponenten gleich einer ersten der Schlüsselzahlen durchzuführen, um einen Teil der verschlüsselten Nachricht zur Verfügung zu stellen, und wenigstens eine Verschlüsselungsvorrichtung, dadurch gekennzeichnet, daß die Entschlüsselungsvorrichtung gebildet ist aus:

- Modulbestimmungsmitteln (10, 14), um ein aus den Faktoren gewähltes Entschlüsselungsmodul zu bestimmen,

zweiten Potenziermitteln (K14), um eine modulare Potenzierung auf jedem Teil der reduzierten, verschlüsselten Nachricht mit einem Modul gleich dem Entschlüsselungsmodul und mit einem Exponenten gleich der reduzierten Zahl durchzuführen, um die Nachricht wiederherzustellen.

4. Verwendung des Systems zur Kommunikation von verschlüsselten Nachrichten gemäß Anspruch 1 in einem Server, umfassend eine Verschlüsselungsvorrichtung und eine Entschlüsselungsvorrichtung, um als Zwischenglied zwischen bzw. mit Benutzervorrichtungen zu dienen, dadurch gekennzeichnet, daß die Entschlüsselungsvorrichtung gebildet ist aus:

- zweiten Potenziermitteln (K14), um eine modulare Potenzierung auf jedem Teil der reduzierten, verschlüsselten Nachricht mit einem Modul gleich dem Entschlüsselungsmodul und mit einem Exponenten gleich der reduzierten Zahl durchzuführen, um die Nachricht wiederherzustellen.