DE3685987T2

DE3685987T2 - Verfahren zum vermindern der fuer eine rsa-verschluesselung benoetigten veraenderlichen speicherkapazitaet.

Info

Publication number: DE3685987T2
Application number: DE8686302861T
Authority: DE
Inventors: Stephen Michael Matyas
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1985-04-30
Filing date: 1986-04-16
Publication date: 1993-02-04
Anticipated expiration: 2006-04-17
Also published as: DE3685987D1; US4736423A; EP0202768A3; EP0202768B1; EP0202768A2

Description

Fachgebiet

Die vorliegende Erfindung betrifft ein Verfahren zur persönlichen Identifizierung eines Benutzer eines Systems mit mehreren Datenstationen unter Verwendung eines Verschlüsselungssystems für bekannte Schlüssel.

Stand der Technik

Verschlüsselungsalgorithmen mit öffentlichen Schlüsseln nehmen rasch an Popularität und Verbreitung zu. Das Konzept eines Algorithmus mit öffentlichem Schlüssel wurde zum ersten Mal von Diffie und Hellman in ihrer Abhandlung "New Directions in Cryptography" IEEE Transactions on Information Theory, IT-22, No. 6, Seiten 644 bis 654 (1976) eingeführt. Diffie und Hellman schlugen ein Verteilungssystem für öffentliche Schlüssel auf der Grundlage mathematischer Transformationen, der sogenannten Potenzierung, vor, die nur unter Schwierigkeiten umkehrbar sind, d.h. eine Zahl läßt sich leicht in eine Potenz erheben, aber der umgekehrte Vorgang, das Berechnen des zugehörigen Logarithmus, ist schwierig. Das System ermöglicht es den Benutzern, eine leichte Potenzierung vorzunehmen, das Ergebnis zu verbreiten, und eine weitere Potenzierung vorzunehmen, um identische Schlüssel zu erzeugen. Diese Transformation ist eine Einweg-Funktion und kann daher nicht zum Verschlüsseln und Entschlüsseln von Daten benutzt werden.
In US-Patent Nr. 4,218582 nehmen Hellman und Merkle auf eine andere Abhandlung von Diffie und Hellman mit dem Titel "Multiuser Cryptographic Techniques", Proceedings 1976 National Computer Conference, New York, Seiten 109 bis 112, 7-10. Juni 1976 Bezug, in dem das Konzept eines Verschlüsselungssystems mit öffentlichem Schlüssel vorgeschlagen wird, das die Notwendigkeit für einen sicheren Übertragungskanal dadurch ausschließt, daß die Verschlüsselungsinformation des Absenders öffentlich gemacht wird. Das Patent von Hellman und Merkle baut auf diesem Konzept auf und offenbart ein Verschlüsselungssystem, das ein rechnerisch sicheres Kryptogramm übermittelt, das aus einer in der Öffentlichkeit bekannten Transformation der von Sender zu übermittelnden Botschaft beruht. Diese in der Öffentlichkeit bekannte Transformation benutzt Operationen, die leicht ausgeführt werden können, aber äußerst schwer umkehrbar sind.
Rivest, Shamir und Adleman stellen in ihrer Abhandlung "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems," Communications of the ACM, 21, No. 2, Seiten 120 bis 126 (1978) eine Verschlüsselungsmethode vor mit der Eigenschaft, daß die Veröffentlichung eines Verschlüsselungs- Schlüssels nicht gleichzeitig die Bekanntmachung des Entschlüsselungs-Schlüssels bedeutet. Das hat zwei bedeutsame Konsequenzen:
(1) Kuriere und sonstige sichere Mittel sind zur Übermittlung öffentlicher Schlüssel nicht erforderlich, und
(2) Eine Botschaft kann mit einem privaten Entschlüsselungsschlüssel "signiert" werden und jeder kann die Signatur mit dem entsprechenden öffentlich bekanntgegebenen Verschlüsselungsschlüssel überprüfen.
US-Patent Nr. 4,405,829 von Rivest, Shamir und Adelman offenbart ein kryptographisches Übertragungssystem, in dem eine zu übermittelnde Botschaft im Verschlüsselungsterminal zu einem Chiffretext verschlüsselt wird, zuerst durch Verschlüsseln der Botschaft als Zahl M in einer vorgegebenen Menge, Erheben dieser Zahl in eine erste, vorbestimmte Potenz (die mit dem beabsichtigten Empfänger vereinbart ist) und schließlich Berechnen des Rests, d.h. der Zahl C, die übrigbleibt, wenn die potenzierte Zahl durch das Produkt zweier vorgegebener Primzahlen (die mit dem beabsichtigten Empfänger abgesprochen sind) geteilt wird. Dieser Rest C ist der chiffrierte Text, der dann im Entschlüsselungsterminal auf ähnliche Weise wieder entschlüsselt wird durch Erheben des Chiffretexts in eine andere, vorgegebene Potenz (wie mit dem beabsichtigten Empfänger abgesprochen) und dann Berechnen des Rests M' nach Dividieren des potenzierten Chiffretexts durch das Produkt zweier vorgegebener, mit dem beabsichtigten Empfänger abgesprochener Primzahlen. Der Rest M' entspricht der ursprünglichen verschlüsselten Botschaft M. Die einzige bekannte Methode für einen Außenseiter zum Brechen dieses Code ist das Auffaktorieren des im öffentlichen Schlüssel enthaltenen Produkts, um die ursprünglichen zwei Primzahlen wiederzugewinnen, die die Quelle des Verschlüsselungsschlüssels sind, was derzeit rechnerisch nicht machbar ist.
US Patent Nr. 4,351,982 von Miller u.a. gibt eine Übersicht über die Entwicklung des Algorithmus mit Öffentlichem Schlüssel, anerkennt jedoch, daß sich seine Anwendung auf Großcomputer beschränkt wegen der Größe der zu generierenden Primzahlen, die erforderlich ist, die Systemsicherheit zu garantieren. Zur Lösung dieses Problems offenbaren Miller u.a. ein Verschlüsselungssystem mit öffentlichem Schlüssel, das den RSA Algorithmus anwendet, mit dem ein Abonnent, der nur mit einem Mikroprozessor ausgerüstet ist, on-line in verhältnismäßig kurzer Zeit die erforderlichen Primzahlen in ein paar Stunden generieren kann. Das wird ermöglicht durch die Anwendung der GGT-(Größter Gemeinsamer Teiler)-Routine, die zusammengesetzte Zahlen ohne Potenzierung ausscheidet und ein einzigartiges Verfahren zur Bildung einer Primzahlensequenz darstellt.
Die Anwendung des Algorithmus der öffentlichen Schlüssel auf Berechtigungssysteme auf Kartenbasis ist beschränkt. Mueller- Schloer offenbart in US-Patent Nr. 4,438,824 ein Verschlüsselungsidentitäts-Verifizierungssystem, das eine Datenkarte benutzt. In diesem System sind eine Mehrzahl von Datenstationen und eine Sicherheitsdienststation durch ein Datenübermittlungssystem miteinander verbunden. Jede Datenstation hat eine Zentraleinheit (ZE - CPU) einschließlich eines Speichers und eines Kartenlesers sowie ein Verschlüsselungsmodul. Das Verschlüsselungsmodul verschlüsselt bzw. entschlüsselt Daten, die es aus dem Speicher enthält, gesteuert von der CPU. Die Sicherheitsdienststation enthält ebenfalls eine CPU und ein Verschlüsselungsmodul sowie einen Komparator zum Vergleichen der persönlichen Identifizierungsinformationen mit einer Bezugs-Personenidentifizierungsinformation. Das System benutzt persönliche Merkmale (oder persönliche Identifizierungsnummer-Eingaben) und Überprüfung z.B. Fingerabdrücke oder Stimme) zusammen mit Verschlüsselungsprinzipien. Sowohl symmetrische Standard-Datenverschlüsselungssysteme (DES) als auch unsymmetrische Verschlüsselungssysteme mit öffentlichem Schlüssel, wie z.B. der RSA Algorithmus, können auf das Mueller-Schloer-Identitätsüberprüfungssystem angewandt werden.
Das Mueller-Schloer-System ist jedoch handelsmäßig bei elektronischen Geldüberweisungs-(EFT)- oder Verkaufsort-(POS)- Systemen nicht zulässig. Solche Systeme benutzen typischerweise Magnetstreifenkarten, die eine begrenzte Menge verschlüsselter Daten tragen, die zusammen mit einer Geheimnummer für Personenidentifizierung (PIN) den Nachweis für die Berechtigung des Benutzers liefern. Kürzlich wurden Versuche gemacht, mehr Sicherheit für EFT/POS-Systeme zu schaffen. Ein solcher Versuch ist in US-Patent Nr. 4,408,203 von Campbell enthalten. In Campbells RFT-System wird die Verschlüsselung eines geheimen Code gemäß einem Algorithmus vorgenommen, der einen Verschlüsselungsschlüssel benutzt, Insbesondere benutzt Campbell den Algorithmus des National Bureau of Standards (NBS), der dazu ausgelegt ist, 64 Bit große Datenblöcke unter der Steuerung eines 64-Bit-Schlüssels zu verschlüsseln und entschlüsseln. Im Campbell-System wird ein Sicherheitsmodul benutzt, um den von einem Benutzer eingegebenen Code zu entschlüsseln und ihn mit dem entsprechenden verschlüsselten Code zu vergleichen, der in der Datenverarbeitungseinheit abgespeichert ist.
Ein weiteres Beispiel für ein auf einer Karte beruhendes EFT- System ist in US-Patent Nr. 4,423,287 von Zeidler geoffenbart. In diesem System ist ein Schlüssel für eine einmalige Sitzung mit einem Masterschlüssel verschlüsselt und wird in bestimmten Segmenten der Anforderungs- und Beantwortungsmeldung gesendet. Weder Campbell noch Zeidler benutzen einen öffentlichen Schlüsselalgorithmus. Das Hauptproblem beim Benutzen eines öffentlichen Schlüsselalgorithmus, wie z.B. des RSA-Algorithmus, in einem EFT/POS-System ist die beschränkte Datenmenge, die in einem Magnetstreifen gespeichert werden kann.
Zur sicheren Anwendung des RSA-Algorithmus müssen seine Parametergrößen (Schlüssellänge und Modullänge) groß genug eingestellt werden, so daß es rechnerisch unausführbar wird, das Modul in seine Primfaktoren zu zerlegen. Der heute bekannte wirksamste Faktorierungsalgorithmus erfordert, daß Schlüssel und Modul 400 Bits aufweisen müssen, um die Äquivalenz mit dem Datenverschlüsselungsstandard (Data Encryption Standard - DES) zu wahren. Die heute bei Banken allgemein üblichen Magnetstreifen können jedoch diese sehr großen Kryptovariablen nicht mehr abspeichern, die für den RSA-Algorithmus erforderlich wären. Zum Beispiel enthalten die drei Spuren auf dem Magnetstreifen einer Bankkarte Speicherplatz für 79, 40 bzw. 108 Zeichen. Jedes Zeichen besteht aus 4 Bits, so daß entsprechend 316, 160 bzw. 432 Bits gespeichert werden können. Der übliche Standard verlangt jedoch, daß nur Dezimalwerte von 0 bis 9 in jedem 4-Bit-Zeichen gespeichert werden, so daß effektiv jeder Spur nur 79, 40 bzw. 108 Dezimalstellen speichern kann. Im Vergleich dazu entspricht eine Zahl mit 400 Bits 120 Dezimalstellen, somit ist es offensichtlich, daß die 400-Bit RSA Kryptovariablen nicht mehr auf einer Bankkarte gespeichert werden können. Um es genau zu sagen, würde der 400-Bit Geheimschlüssel SKi und der 400-Bit Modul Ni, um auf einer Bankkarte gespeichert zu werden, insgesamt 240 Dezimalstellen erfordern, aber die Karte kann nicht mehr als 227 Dezimalstellen aufnehmen, selbst wenn die ganze Karte für die Speicherung dieser zwei Parameter verwendet wird.
Damit der RSA-Algorithmus für Bankzwecke anwendbar wird, muß entweder eine neue Magnetkarte mit mehr Speicherplatz eingeführt werden, oder eine wirksamerer Weise zum Abspeichern des Geheimschlüssels und des Moduls auf der jetzigen Magnetkarte muß gefunden werden. Die Inkompatibilität mit den derzeitigen Magnetstreifenkarten ist ein Haupthinderungsgrund, der höchstwahrscheinlich die Einführung des öffentlichen Schlüsselalgorithmus behindern würde. Anwendungen mit persönlichen Schlüsseln (ein besonders wichtiges Merkmal der Verschlüsselung mit öffentlichen Schlüsseln) wird somit negativ beeinflußt, falls nicht eine wirksame Technik zur Abspeicherung der Parameter auf den Magnetstreifenkarten gefunden werden kann oder die derzeitige Speicherkapazität auf den Karten erweitert wird.

Zusammenfassung der Erfindung

Es ist daher eine Aufgabe der vorliegenden Erfindung, eine Technik zum effizienten Abspeichern der für die öffentlichen Schlüsselalgorithmen erforderlichen Parameter auf einer Magnetstreifenkarte bereitzustellen.
Eine genauere Aufgabe der vorliegenden Erfindung ist es, eine Technik zum Abspeichern von RSA-Kryptovariablen auf derzeitigen Magnetstreifenkarten bereitzustellen.
Noch eine weitere Aufgabe der vorliegenden Erfindung ist es, den öffentlichen RSA-Schlüsselalgorithmus unter Verwendung derzeitiger Magnetstreifenkarten an das EFT-System anzupassen.
Erfindungsgemäß wird ein Verfahren zum Identifizieren einer Person für einen Benutzer eines Systems mit mehreren Datenstationen vorgesehen, wobei das Verfahren auf einem Verschlüsselungssystem für bekannte Schlüssel von der Art mit einer Modulo-Potenzierung beruht, dessen Modul das Produkt zweier binärer Primzahlen ist und die folgenden Schritte umfaßt:
Lesen einer dem Benutzer zugewiesenen Kontonummer und einer äußeren Kryptovariablen in ein Terminal, wobei die äußere Kryptovariable n Bits aufweist, von denen m Bits geheimgehalten werden und die restlichen n-m Bits öffentlich bekannt sind, und die Kontonummer und die äußere Kryptovariable auf einer Magnetstreifenkarte gespeichert sind;
Durchführen einer Vorausberechnung an dieser äußeren Kryptovariablen, um einen geheimen persönlichen Schlüssel und ein dem Benutzer zugewiesenes öffentliches Modul zu regenerieren;
Empfangen einer geheimen persönlichen Identifizierungsnummer, die vom Benutzer in die Datenstation eingegeben wurde; und
Überprüfen der Identifizierung des Benutzers auf der Grundlage der Kontonummer des Benutzers, des regenerierten geheimen Personenschlüssels und des öffentlichen Moduls und der persönlichen Identifizierungsnummer, die vom Benutzer eingegeben wurde.
Gemäß einem Aspekt der Erfindung wird eine Technik vorgesehen, die die Speicherung der RSA-Kryptovariablen von 1200 Bits (400 Bits Öffentlicher Schlüssel, 400 Bits Geheimer Schlüssel, und 400 Bits Modul) auf 106 Bits reduziert. Von diesen 106 Bits müssen nur 56 Bits (bezeichnet mit "X") geheimgehalten werden. Die Größe von X wurde so gewählt, daß die Äquivalenz mit dem DES beibehalten wird. Die restlichen 50 Bits sind nicht geheim. Diese 106 Bits werden benutzt, um zwei 200-Bits-Primzahlen P und Q (aus denen der Modul N=PQ gewonnen wird) und zwei 400-Bit-Schlüssel PK und SK zu berechnen. Durch die Durchführung einer Vorabberechnung zum Gewinnen des Moduls und der Schlüssel wird nämlich Speicherplatz eingespart.
Gemäß einem anderen Aspekt der Erfindung wird eine Technik vorgesehen, die Speicherung des öffentlichen Schlüssels und des Moduls als RSA-Kryptovariable von 800 Bits auf 242 Bits zu reduzieren. Diese 242 Bits können später jederzeit benutzt werden, den 400-Bit öffentlichen Schlüssel PK und den 400-Bit Modul N=PQ abzuleiten. Es wird jedoch darauf hingewiesen, daß das erfindungsgemäße Verfahren auf RSA-Kryptovariable jeder Größe, z.B. 800 Bits oder auch 1200 Bits anstatt 400 Bits angewandt werden kann.

Kurze Beschreibung der Zeichnungen

Die obigen Ausführungen sowie weitere Aufgaben, Aspekte und Vorteile der Erfindung werden leichter verständlich aus der nachstehenden genauen Beschreibung der Erfindung anhand der Zeichnungen, in denen:
Fig. 1 ist ein Blockschaltbild und Flußdiagramm, das die Anwendung eines RSA-Verschlüsselungssystems zum Nachweis der Berechtigung der Benutzer in einem elektronischen Geldüberweisungs- bzw. Kassenterminal-System (EFT/POS) zeigt;
Fig. 2 ist ein Blockdiagramm, das das Format für die Schlüsselverteilung mit dem Schlüsselerweiterungsalgorithmus zeigt;
Fig. 3 ist eine Blockschaltbild, das den Prozeß der Schlüsselerweiterung im RSA-Algorithmus vor dem Entschlüsseln von Daten mit dem Geheimschlüssel und dem öffentlichen Modul zeigt;
Fig. 4 ist eine Blockschaltbild, das den Prozeß der Schlüsselerweiterung im RSA-Algorithmus vor dem Verschlüsseln von Daten mit dem Geheimschlüssel und dem öffentlichen Modul zeigt;
Fig. 5 ist ein Blockschaltbild und Flußdiagramm, das den Prozeß des Generierens der Kryptovariablen zeigt;
Fig. 6A, 6B und 6C sind zusammen ein Blockschaltbild und Flußdiagramm, das den Berechnungsprozeß PRECOMPUTATION ONE zeigt; und
Fig. 7 ist ein Blockschaltbild und Flußdiagramm, das den Berechnungsprozeß PRECOMPUTATION TWO zeigt.

Detaillierte Beschreibung einer bevorzugten Ausführungsform der Erfindung.

Die Erfindung sieht die Personenüberprüfung und den Echtheitsbeweis für eine Nachricht auf der Grundlage des RSA- Verschlüsselungssystems mit öffentlichem Schlüssel in einem elektronischen Geldüberweisungssystem oder elektronischen Kassenterminalsystem vor. Elektronische Geldüberweisung (Electronic Funds Transfer - EFT) heißt ein System, bei dem man Konten von Kunden und Dienstleistungsunternehmen direkt belasten oder auf diese gutschreiben kann. Die Konten werden bei einer Bank geführt, die an ein Netz von Datenverarbeitungsgeräten in Einzelhandelsgeschäften oder Leistungsbetrieben angeschlossen ist. Kassenterminals (Point of Sale - POS) heißen die Datenverarbeitungssysteme der Einzelhändler, in denen Kontroll- oder Registrierkassen mit einem Datenverarbeitungsystem verbunden sind. Ein solches System gibt dem Kunden die Möglichkeit, auf elektronischem Weg Einkäufe auf Kredit zu tätigen.
Betrachten wir eine Konfiguration vernetzter Rechner und angeschlossener Endgeräte. Der Eingabepunkt, an dem die finanzielle Transaktionsanforderung eingeleitet wird, wie z.B. ein POS-Terminal oder eine automatische Kasse (Automated Teller Machine - ATM) ist als EFT-Terminal definiert. Die Rechnerzentrale des Instituts, das die angeschlossenen EFT-Terminals verwaltet, wird als Hauptrechner (Host Processing Centre - HPC) bezeichnet. Mehrere HPCs können über einen "intelligenten" Schalter zusammengeschaltet werden. Dieser Schalter, der selbst ein HPC sein kann, stellt die Verbindung zwischen den HPCs her.
Die Benutzer sind im Normalfall mit einer vorgeprägten magnetischen Streifen-Identitätskarte oder Bankkarte versehen, die u.a. eine Kontogrundnummer (Primary Account Number - PAN) enthält. Das Institut, bei dem der Kunde sein Konto eröffnet und das dem Kunden die Bankteilnehmerkarte ausstellt, wird als Aussteller bezeichnet. An der Einsprungstelle in das System wird die Information auf der Bankkarte des Benutzers in das System eingelesen und der Kunde gibt eine geheime Zahl, genannt die Personenidentifizierungsnummer (PIN) ein, die seine angebliche Identität (PAN) bestätigt. Wenn der Karteninhaber die richtige PIN eingegeben hat und das Guthaben auf seinem Konto für die Transaktion ausreicht, läßt das System die Geldüberweisung zu.
Im Normalfall ist die in das System eingegebene PIN durch Verschlüsselung geschützt. Bei dem hier angenommenen Verschlüsselungsalgorithmus handelt es sich um den öffentlichen Verschlüsselungsalgorithmus nach Rivest, Shamir und Adleman auf der Grundlage der modularen Potenzierung. Auch der persönliche Berechtigungsnachweis beruht auf einem Geheimschlüssel, der auf der Bankkarte gespeichert ist und der als Personenschlüssel (Personal Key - KP) bezeichnet wird. Fig. 1 zeigt die Anwendung eines RSA Verschlüsselungssystems zum Nachweis der Berechtigung der Benutzer in einem EFT/POS- System. Für die Zwecke der vorliegenden Diskussion soll angenommen werden, daß die Karte 10 hinreichend Speicherplatz für die Speicherung der RSA-Kryptovariablen aufweist. Wie in der nachfolgenden Diskussion erklärt wird, ist die Anzahl der zum Speichern der RSA-Kryptovariablen benötigten Bits so reduziert worden, daß sie auf der Magnetstreifenkarte 10 Platz finden, und die RSA-Kryptovariablen werden mit Hilfe einer bestimmten Entwicklungstechnik regeneriert. Wie in Fig. 1 ersichtlich, besteht die vom Benutzer 1 eingeleitete Transaktion aus den folgenden Schritten:
Zunächst wird die IDi (identification of the ith user - Identifizierung des i-ten Benutzers), die KPi (personal key of the ith user - geheimer Personenschlüssel des i-ten Benutzers) und der Ni (dem Benutzer zugewiesenes öffentliches Modul) auf der Bankkarte in das EFT-Terminal 12 eingelesen und die PINi (ith user's Personal Identification Number - dem i-ten Benutzer zugewiesene persönliche Identifizierungsnummer) wird über die PIN-Tastatur in das EFT-Terminal eingegeben. Die IDi und die TIDj (Identifier of the jth Terminal - Kennung des j-ten Terminals) werden in der ersten Meldung an den HPC 14 geschickt.
Als nächstes reagiert der HPC 14 durch Generieren einer Zufallszahl T1 im Zufallszahlengenerator 141, die in einer zweiten Meldung an das EFT-Terminal 12 geschickt wird. Im Terminal wird in Block 120 die Zufallszahl T1 mit der TRM verkettet, wobei die TRM (Transaction Request Message) die Transaktionsanforderungsmeldung darstellt, und KPi und PINi werden im Exklusiv-ODER-Gatter 121 in Exklusiv-ODER-Verknüpfung verknüpft und bilden den Geheimschlüssel SKi (Secret Key). Dieser Geheimschlüssel SKi wird dann zusammen mit dem öffentlichen Modul Ni benutzt, um die Meldung TRM, T1 im Entschlüsselungsmodul 122 zu entschlüsseln und bilden die dSKi (TRM, T1). Das EFT Terminal 12 reagiert durch Bilden einer eigenen Zufallszahl T2 im Zufallszahlengenerator 123 und schickt in einer dritten Meldung die dsKi (TRM, T1) und T2 an den HPC 14.
Im HPC 14 wird die dsKi (TRM, T1) in Block 142 mit dem öffentlichen Schlüssel und dem Modul des Benutzers 1 verschlüsselt, die der Schlüsseltabelle 143 unter Verwendung der IDi und der TIDj entnommen werden, um TRM, T1 in Klarform zu erhalten. Die wiederhergestellte Zufallszahl T1 wird dann im Komparator 144 auf Gleichheit mit der ursprünglichen Zufallszahl T1 verglichen, die vom HPC 14 generiert und abgespeichert worden war. Wenn der Verglich positiv ausfällt, wird der eingegangene Wert der Zufallszahl T2 mit dem geheimen Bankschlüssel und dem Bankmodul, Skb und Nb, im Entschlüsselungsmodul 145 entschlüsselt und ergibt dSKb (T2), die dann in einer vierten Meldung an das EFT-Terminal 12 geschickt wird. Anderenfalls wird die Transaktion abgelehnt.
Im EFT-Terminal 12 wird der eingegangene Wert dSKb (T2) im Verschlüsselungsmodul 124 mit dem öffentlichen Bankschlüssel und dem Bankmodul, PKb und Nb, verschlüsselt, um die Zufallszahl T2 in Klarform zu erhalten. Die erhaltene Zufallszahl T2 wird dann im Komparator 125 auf Gleichheit mit der Originalzahl T2 verglichen, die im EFT-Terminal 12 generiert und abgespeichert worden war. Wenn der Vergleich positiv ausfällt, akzeptiert das EFT-Terminal 12 den Benutzer i als berechtigt, anderenfalls wird er zurückgewiesen.
Das hier beschriebene Verfahren ist rein theoretisch, weil es sich auf die Annahme gründet, daß die Karte 10 genügend Speicherplatz zum Abspeichern der RSA-Kryptovariablen hat. Die derzeitigen Magnetstreifenkarten haben jedoch nicht genügend Speicherkapazität. Gemäß einer bevorzugten Ausführungsform der vorliegenden Erfindung werden Ni und KPi auf der Karte 10 durch 106 Bits ersetzt, und diese werden expandiert, um Ni und KPi zu erhalten mittels einer Technik, die jetzt beschrieben werden soll. Die Erfindung macht also das beschriebene Verfahren für den Nachweis der Berechtigung der Transaktion in Fig. 1 erst möglich dadurch, daß sie die derzeitigen Magnetstreifenkarten für den öffentlichen RSA- Schlüsselalgorithmus anwendbar macht.
Bei vielen Anwendungen von Verschlüsselungssystemen mit öffentlichem RSA-Schlüssel wird es wahrscheinlich erforderlich, öffentliche Schlüssel und Module der Systembenutzer auf andere Systembenutzer zu übertragen. Z.B. könnte ein Benutzer mit einem anderen Benutzer durch Verschlüsseln von Daten mit dem öffentlichen Schlüssel und Modul dieses anderen Benutzers in Verkehr treten wollen, oder er könnte wünschen, in der Lage zu sein, die Authentizität der Mitteilungen eines anderen Benutzers zu überprüfen. Das setzt voraus, daß er zuerst den öffentlichen Schlüssel und Modul dieses anderen Benutzers von einem dazu bestimmten Schlüsselverteilungszentrum (KDC - Key Distribution Centre) in Erfahrung bringt. In der Regel wird das Schlüsselverteilungszentrum die Integrität der übertragenen Kryptovariablen durch Entschlüsseln derselben mit seinem Geheimschlüssel und Modul vor der Übertragung nachweisen. Es darf angenommen werden, daß jeder Benutzer eine Kopie des entsprechenden öffentlichen Schlüssels und Moduls des Schlüsselverteilungszentrums im Besitz hat. Das kann sichergestellt werden z.B. durch Registrierung des öffentlichen Schlüssels und Moduls in einem öffentlichen Register oder durch Veröffentlichung derselben in einer Zeitung wie dem Wall Street Journal oder einer sonstigen weitverbreiteten Zeitschrift. Der öffentliche Schlüssel und Modul des Schlüsselverteilungszentrums können auf diese Weise von jedem Benutzer des Systems benutzt werden, um die vom Schlüsselverteilungszentrum verteilten Kryptovariablen wiederzugewinnen. Das wird erreicht durch Entschlüsseln der verschlüsselten Kryptovariablen unter Verwendung des öffentlichen Schlüssels und Moduls des Schlüsselverteilungszentrums. Wenn auch ein Gegner verschlüsselte Kryptovariable austauschen könnte, so könnte er doch nicht bewirken, daß der Empfänger einen (vom Gegner) gewählten Schlüssel und Modul benutzen könnte.
Beim Entziffern dieser öffentlichen Schlüssel und Module tritt jedoch ein Problem auf, wenn der öffentliche Schlüssel oder Modul des Benutzers einen höheren Wert hat, als der öffentliche Modul des Schlüsselverteilungszentrums. In einem solchen Fall muß die bestimmte Kryptovariable in zwei Blöcke aufgeteilt und verschlüsselt werden anstatt nur in einem. Das macht die Schlüsselverteilungsarchitektur sehr komplex und erfordert die Übertragung zusätzlicher, unnötiger Daten. Die vorliegende Erfindung löst dieses Problem durch ein Verfahren, das die Regenerierung des öffentlichen Schlüssels und Moduls (die bis zu 800 Bits lang sein können) aus nur 250 Bits öffentlicher Information zuläßt. Durch Verschlüsseln dieser 250 Bits werden nicht mehr als 400 Datenbits produziert, die übertragen werden müssen. Das ist das Minimum, das übertragen werden muß, und stellt das beste dar was unter beliebigen Bedingungen gemacht werden kann. Da jedoch diese 250 Bits mit, grob gesprochen, 150 Bits aufgefüllt werden müssen, um einen vollen Block zu bilden, bevor das Verschlüsseln mit dem geheimen Schlüssel und dem öffentlichen Modul des Schlüsselverteilungszentrums durchgeführt werden kann, sind ja effektiv 150 Extrabits verfügbar, die sehr gut benützt werden können, um die Sicherheit des Verteilungsprotokolls zu erhöhen und zwar nicht auf Kosten der Anzahl der übertragenen Bits. Z.B. könnten diese Bits 56 redundante 0-Bits enthalten, um den Block der wiedergewonnen Daten ordnungsgemäß zu bestätigen, oder einen zeitveränderlichen Parameter bzw. eine Folgenummer, damit der Empfänger überprüfen kann, daß die Kryptovariable nicht veraltet ist und in der richtigen Reihenfolge eingegangen ist, sowie eine ID des Benutzers, dem der öffentliche Schlüssel und Modul gehört, um sicherzustellen, daß die Kryptovariable auch wirklich dem Benutzer gehört, für den die Anforderung gemacht wird.
Fig. 2 erläutert das allgemeine Format zur Übertragung eines öffentlichen Schlüssels und Moduls vom Schlüsselverteilungszentrum an einen anfordernden Benutzer. Es wird angenommen, daß das öffentliche Modul des KDC 400 Bits lang ist und ein führendes 1-Bit enthält. Das wird automatisch garantiert durch das Verfahren der Schlüsselgenerierung, das Teil der vorliegenden Erfindung ist. Wie in Fig. 2 gezeigt wird, werden die höherwertigen Bits des Blocks, die Redundanzbits zur Bestätigung des Blocks sind, auf eine vereinbarte Konstante gesetzt, wobei das Bit höchster Ordnung zwangsläufig auf 0 gesetzt wird. Z.B. besteht die vereinbarte Konstante möglicherweise nur aus 0-Bits, wie in Fig. 2 gezeigt wird. Wenn das höchstwertige Bit zwangsweise auf 0 gesetzt wird, ist garantiert, daß die Zahl, die die Daten im Block darstellt und die mit dem öffentlichen Schlüssel und Modul des Schlüsselverteilungszentrums entschlüsselt werden muß, kleiner ist als die Zahl, die das Modul repräsentiert, was seinerseits sicherstellt, daß die Entschlüsselung immer ordnungsgemäß erfolgen kann. Der öffentliche Schlüssel und Modul des Benutzers, dessen Kennung = ID ist, wird dann aus den Daten im Feld regeneriert, das als NONSECRET CRYPTO VARIABLE (nichtgeheime Kryptovariable) bezeichnet ist.
Derzeit ist das oben beschriebene Schlüsselverteilungsprotokoll, in dem redundante 0-Bits, Folgeziffer und Benutzerkennung in die Meldung aufgenommen werden, die den öffentlichen Schlüssel und Modul vom Schlüsselverteilungszentrum an einen anfordernden Benutzer überträgt, etwas, das wahrscheinlich immer gemacht werden würde, unabhängig davon, ob ein Schlüsselerweiterungsalgorithmus angewandt wird oder nicht. Ohne einen Schlüsselerweiterungsalgorithmus bedeutet das ganz automatisch, daß mehr als zwei Datenblöcke übertragen werden müssen, um einen öffentlichen Schlüssel und Modul an den anfordernden Benutzer zu senden. In diesem Falle könnte man versuchen, die Anzahl der übertragenen Bits durch Anwenden einer Verkettungsmethode zu minimieren, um die Daten zu entschlüsseln, die die zu übertragende Meldung enthalten. Mit einem Schlüsselerweiterungsalgorithmus kann jedoch der elektronische Codebuchmodus (ECB - Electronic Codebook) zur Schlüsselübertragung benutzt werden, was das Protokoll vereinfacht.
Der erfindungsgemäße Schlüsselerweiterungsalgorithmus sollte wohl richtiger Kryptovariablen-Erweiterungsalgorithmus heißen. Das ist so, weil der RSA-Algorithmus zusätzlich zu zwei Schlüsseln ein Modul enthält. Dieses Modul ist nicht eigentlich ein Schlüssel, ist jedoch erforderlich, um sowohl mit öffentlichen als auch mit privaten Schlüsseln ver- und entschlüsseln zu können. Das Konzept der Schlüsselerweiterung wurde bereits als Teil des Datenverschlüsselungsstandard- (DES)-Algorithmus beschrieben. Der DES benützt einen Schlüsselplanalgorithmus, der aus den 56 Schlüsselbits im 64-Bit langen externen Schlüssel 16 48-Bit lange interne Schlüssel oder Unterschlüssel produziert. Somit erzeugt der Schlüsselerweiterungsalgorithmus 768 Bits internen Schlüssel aus dem einzigen 56-Bit-Schlüssel, der an den Algorithmus gegeben wird. Der Schlüsselerweiterungsalgorithmus erweitert faktisch 56 Bits auf 768 Bits.
Die vorliegende Erfindung benutzt zwei externe Kryptovariable genannt EXTERNAL CRYPTO VARIABLE ONE und EXTERNAL CRYPTO VARIABLE TWO. Die externe Kryptovariable Eins besteht aus einem geheimen Teil und einem nichtgeheimen Teil. Derzeit besteht der nichtgeheime Teil der externen Kryptovariablen Eins aus sieben Einzelparametern, die vom Schlüsselerweiterungsalgorithmus benutzt werden. Wie diese einzelnen Parameter im Schlüsselerweiterungsalgorithmus benutzt werden, ist für die gegenwärtige Diskussion unwichtig. Im Beispiel, in dem das Modul 400 Bits beträgt, enthält der geheime Teil 56 Bits und der nichtgeheime Teil 50 Bits. Wenn das Modul größer wäre, würde der geheime Teil mit 56 Bits gleich bleiben, aber der nichtgeheime Teil würde sich vergrößern. Z.B. wären für ein 800-Bit Modul etwa 60 Bits für seinen nichtgeheimen Teil erforderlich. Nehmen wir ein 400-Bit-Modul an, dann wird externe Kryptovariable Eins (106 Bits) mit PRECOMPUTATION ONE (Vorberechnung Eins) benutzt, um den Geheimschlüssel (400 Bit) und das öffentliche Modul (400 Bits) zu regenerieren. In Wirklichkeit würde er auch den 400-Bits langen öffentlichen Schlüssel regenerieren, obwohl diese Fähigkeit bei der oben umrissenen Anwendung anscheinend keinen Vorteil brächte.
Fig. 3 zeigt den Vorgang der Schlüsselerweiterung im RSA- Algorithmus vor der Datenentschlüsselung mit dem Geheimschlüssel und dem öffentlichen Modul. Auf diese Weise wird die externe Kryptovariable Eins mit der "Vorberechnung Eins" behandelt, um den internen Geheimschlüssel und das interne Modul zu generieren. Der interne Geheimschlüssel und das interne Modul werden sodann benutzt, um den Chiffretext zu entschlüsseln und den Klartext zu erstellen.
Die externe Kryptovariable Zwei ist eine nichtgeheime Variable. In Wirklichkeit besteht sie aus drei Einzelparametern. Im betrachteten Beispiel, in dem das Modul 400 Bits umfaßt, umfaßt diese Variable 250 Bits. Wenn das Modul größer als 400 Bits wäre, würde auch dieser Parameter größer sein. Z.B. würde eine 800-Bit-Modul etwa 460 Bits für die externe Kryptovariable Zwei erfordern. Unter der Annahme eines 400-Bits-Moduls wird die externe Kryptovariable Zwei (250 Bits) mit PRECOMPUTATION TWO (Vorberechnung Zwei) benutzt, um den öffentlichen Schlüssel (400 Bits) zu regenerieren. Es ist rechnerisch unpraktisch, den Geheimschlüssel aus der externen Kryptovariablen Zwei zu gewinnen.
Fig. 4 zeigt das Verfahren der Schlüsselerweiterung im RSA- Algorithmus vor der Datenverschlüsselung. Hier wird die externe Kryptovariable Zwei mit der "Vorberechnung Zwei" behandelt, um den internen öffentlichen Schlüssel und das interne Modul zu generieren. Der interne öffentliche Schlüssel und das interne Modul werden sodann benutzt, um den Klartext zu verschlüsseln und den Chiffretext zu erstellen.
Fig. 5 zeigt den Vorgang der Generierung der Kryptovariablen. Dieser Prozeß ist ein empirisches Ermittlungsverfahren. Eine 56-Bit-Zufallszahl wird generiert und als Versuchswert für die externe geheime Kryptovariable X definiert. Auf der Stufe der Generierung der Kryptovariablen wird der Wert X benutzt, um die Werte D1, ..., D7, R und S abzuleiten. Falls das gelingt, definieren die abgeleiteten Werte die externen Kryptovariablen Eins und Zwei, sonst wird ein weiterer Versuchswert X gewählt und der Prozeß wiederholt sich, bis geeignete Werte gefunden sind. Da das Verfahren zum Generieren X, D1, ..., D7 sehr genau dem Verfahren PRECOMPUTATION ONE folgt, läßt sich das Verfahren zur Erzeugung dieser Variablen am besten beschreiben, wenn zuerst das Verfahren PRECOMPUTATION ONE beschrieben wird. Das Verfahren zur Generierung R und S ist einfacher und beinhaltet nur vier einfache Rechenschritte unter Verwendung der Werte für P, D4, D5 und D6, die als Teil des Verfahrens zur Generierung X, D1, ..., D7 anfallen.
Betrachten wir jetzt den Prozeß PRECOMPUTATION ONE. Nehmen wir an, wir wollen b-Bit-Primzahlen P und Q, ein 2b-Bit-Modul N, die Parameter D1, ..., D6 mit i Bits und den Parameter D7 mit i+1 Bits erzeugen. Üblicherweise ist i ≤ 10 für b ≤ 400. Die Werte
2b-2(i+2), 2b-2(i+2), 22b-3(i+2), j und D0,
die von b oder i oder von beiden abhängig sind, werden vorberechnet sobald b und i festgelegt sind, werden abgespeichert und werden ein integraler Teil des PRECOMPUTATION ONE Algorithmus. Wahlweise können diese Werte auch dem Vorberechnungsalgorithmus als Parameter eingegeben werden. Insbesondere die Werte
2b-2(i+2), 2b-2(i+2)-1, 22b-3(i+2)
in Binärform bestehen nur aus einem 1-Bit gefolgt von der richtigen Anzahl 0-Bits, was ermöglicht, daß sie im komprimierten Format abgespeichert und nach Bedarf rekonstruiert werden. Der Wert j wird berechnet mittels der Gleichung
j = 2k+4 - 1 (1)
wobei k die kleinstmögliche positive Ganzzahl ist, so daß 2kk-1 56 > b wird. Die Konstante D0, die die kleinstmögliche positive Ganzzahl ist so daß
Z = 2b-2(i+2) - (2D0 + 1)
eine Primzahl ist, wird interaktiv berechnet durch Auswählen der Versuchswerte für D0 = 0, 1, 2, ... usw. bis ein Wert D0 gefunden wird, so daß Z eine Primzahl ist. Große Zahlen lassen sich auf Primzahleigenschaften auf verschiedene Weise testen wie noch unter Hinweis auf die Generierung der Kryptovariablen diskutiert wird. Die allgemeine Form der PRECOMPUTATION ONE Berechnung, bei denen Werte für b und i Variable bleiben, wird wie folgt definiert:
1. Calc Z: Z = 2b-2(i+2) - (2D0 + 1)
2. Calc X1: X1 = xj mod Z
3. Calc X2: X2 = X1(D1+1) mod Z
4. Calc P": p" = X2 ODER (2b-2(i+2)-1 + 1)
5. Calc P': p' = 2(D2 + 2i)p" + 1
6. Calc P: P = 2(D3 + 2i) p' + 1
7. Calc X3: X3 = Quotient von 22b-3(i+2)/p
8. Calc X4: X4 = X3 wenn X3 ungerade = X3 + 1 wenn X3 gerade
9. Calc Q": Q" = 2(D4 + 2i)X4 + 1
10. Calc Q': Q' = 2(D5 + 2i)Q" + 1
11. Calc Q: Q = 2(D6 + 2i)Q' + 1
12. Calc N: N = PQ
13. Calc X5: X5 = N mod Z
14. Calc X6: X6 = X54(D7+1) mod N
15. Calc PK: PK = X6 wenn X6 ungerade = X6 + 1 wenn X6 gerade
16. Calc SK: PKxSK = 1 mod [1 cm (P-1) (Q-1)]
Bei einer praktischen Ausführung der beschriebenen Technik zur Reduzierung des für die RSA-Kryptovariablen benötigten Speicherplatzes würden die Parameter b und i wahrscheinlich durch diese Anwendung festgelegt werden. Deshalb betrachten wir, um das Vorberechnungsverfahren besser verstehen und leichter verfolgen zu können, den Fall, daß b=200 ist, das heißt 200-Bit-Primzahlen und ein 400-Bit-Modul sind vorgeschrieben. Setzen wir i=7, d.h. die Parameter D1, ..., D6 haben 7 Bits und Parameter D7 hat 8 Bits. Für einen Wert von b=200 kann sehr wahrscheinlich ein D0 mit 8 Bits oder weniger gefunden werden. Es kann z.B. gezeigt werden, daß die Wahrscheinlichkeit, einen 8-Bit-Wert für D0 zu finden, der eine Primzahl Z gemäß dieser Berechnung erzeugt, 0,9827 beträgt. Somit läßt sich ein Wert Z für b-2(i+2) Bits leicht aus einem D0 mit verhältnismäßig weniger Bits, 7 oder 8 Bits, rückberechnen und nur diese verhältnismäßig weniger Bits müssen als Teil des PRECOMPUTATION ONE Algorithmus abgespeichert werden. Für einen Wert b=200 gibt Gleichung (1) auch einen Wert von j=127 an, der auch als Teil des Algorithmus leicht abgespeichert wird.
Die PRECOMPUTATION ONE Berechnung für b=200 und i=7 ist in den Fig. 6A, 6B und 6C dargestellt und läßt sich mit reihen- und parallelgeschalteten Prozessoren verwirklichen. Zunächst wird Z im Berechnungsblock 600 berechnet, in dem der im Register 601 abgespeicherte Wert D0 durch Verschieben um eine Stelle nach links im Block 602 mit 2 multipliziert wird, dann wird 1 addiert durch zwangsweises Setzen des niedrigstwertigen Bits (LSB) auf "1", wie im Block 603 angedeutet wird, und dann wird im Subtrahierer 604 das Ergebnis von 2¹&sup8;² abgezogen. Auf diese Weise läßt sich, lediglich durch Abspeichern von D0, das verhältnismäßig wenige Bits enthält, die 182-Bit-Primzahl Z leicht rückberechnen.
Dann wird die geheime 56-Bit-Zufallszahl X aus Register 605 eingelesen und zur 127. Potenz erhoben, und unter Benutzung des in Block 600 berechneten Werts Z wird X1 im Berechnungsblock 606 mit Hilfe der Modulo-Arithmetik berechnet. Das bedeutet sechs Quadrier- und Modulo-Operationen, was mehr als genug ist, die 56-Bit-Zahl X in eine 182-Bit-Zahl zu erweitern.
Dann wird D1 aus dem Register 605 eingelesen, und im Addierer 607 wird "1" zu dieser 7-Bit-Zahl addiert. Die in Block 606 berechnete Zahl X1 wird mit D1+1 potenziert und in Block 608 wird X2 berechnet unter Benutzung der Modulo-Arithmetik und des Werts Z, der in Block 600 berechnet wurde. Der berechnete Wert für X2 aus Block 608 wird in Block 609 mit 2¹&sup8;¹ + 1 ODER-verknüpft und erzeugt die Primzahl P". Die Berechnung von P" garantiert, daß P" ein höherwertiges "1"-Bit aufweist (d.h. daß eine 128-Bit-Zahl erzeugt wird) und daß P" ein niederwertiges "1"-Bit aufweist (d.h. daß P" ungerade ist). Hier ist anzumerken, daß die ODER-Operation lediglich eine andere Art ist, zu sagen, daß wir das höchstwertige Bit und das niedrigstwertige Bit in P" auf "1" setzen.
Jetzt wird der Parameter D2 aus Register 605 eingelesen und im Addierer 610 im Berechnungsblock 611 zu 128 addiert und das Ergebnis durch Verschieben um eine Stelle nach links mit 2 multipliziert, wie in Block 612 angedeutet wird. Der Ausgang von Block 612 wird im Multiplizierer 613 mit dem in Block 609 berechneten P" multipliziert und zu dem Produkt wird im Addierer 614 eine "1" addiert und ergibt so die Primzahl P'. Als nächstes wird der Parameter D3 aus dem Register 605 eingelesen und im Addierer 615 im Berechnungsblock 616 zu 128 addiert und das Ergebnis wird durch Verschieben um eine Stelle nach links mit 2 multipliziert, wie in Block 617 angedeutet ist. Der Ausgang des Blocks 617 wird im Multiplizierer 618 mit dem in Block 611 berechneten P' multipliziert und im Addierer 619 wird zu diesem Produkt eine "1" addiert und ergibt die Primzahl P.
In der nächsten Berechnungsreihe wird die Primzahl Q erzeugt. Zunächst wird das in Block 616 berechnete P in Block 620 durch 2³&sup7;³ dividiert und ergibt den Quotienten X3. Dann wird in Block 621 das niedrigstwertige Bit von X3 zwangsweise auf "1" gesetzt, um eine ungerade Zahl X4 zu erzeugen. Der Parameter D4 wird aus Register 605 eingelesen und im Addierer 622 im Berechnungsblock 623 zu 128 addiert und das Ergebnis durch den Berechnungsblock 623 und das Ergebnis Multiplizierer 625 und zum Produkt im Addierer eine "1" addiert, um die Primzahl Q" zu erzeugen.
Dann wird aus dem Register 605 der Parameter D5 eingelesen und im Addierer 627 im Berechnungsblock 628 zu 128 addiert und das Ergebnis durch Verschieben um eine Stelle nach links mit 2 multipliziert, wie in Block 629 angedeutet ist. Der Ausgang von Block 629 wird im Multiplizierer 630 mit dem in Block 623 berechneten Q" multipliziert, und zu dem Produkt wird im Addierer 631 eine "1" addiert, um die Primzahl Q' zu erzeugen.
Dieser Vorgang wiederholt sich durch Einlesen des Parameters D6 aus dem Register 605 und Addieren desselben zu 128 im Addierer 632 im Berechnungsblock 633 und Multiplizieren des Ergebnisses mit 2 durch Verschieben um eine Stelle nach links, wie in Block 634 angedeutet ist. Der Ausgang des Blocks 634 wird im Multiplizierer 635 mit dem im Block 628 berechneten Q' multipliziert, und zu dem Produkt wird im Addierer 636 eine "1" addiert, um die Primzahl Q zu erzeugen.
Wie in den Fig. 6A, 6B und 6C gezeigt wird, ist der nächste Schritt im Prozeß die Ableitung der öffentlichen und geheimen Schlüssel PK und SK. Zunächst wird das Modul N berechnet durch Multiplizieren des in Block 616 berechneten P mit dem in Block 633 berechneten Q im Multiplizierer 637. Das Produkt N wird zusammen mit dem in Block 600 berechneten Z benutzt, um in Block 638 mit der Modulo-Arithmetik X5 zu berechnen. Jetzt wird der Parameter D7 aus dem Register 605 eingelesen und im Addierer 639 wird eine "1" aufaddiert und das Ergebnis wird durch Verschieben um zwei Stellen nach links mit 4 multipliziert, wie im Block 640 angedeutet wird. Dann wird in Block 641 X5 mit dem Ergebnis aus Block 640 potenziert und mit dem berechneten N zum Berechnen von X6 unter Verwendung der Modulo-Arithmetik in Block 641 benutzt. In Block 642 wird das niedrigstwertige Bit von X6 auf zwangsweise auf "1" gesetzt, um PK zu erzeugen. Von dem in Block 616 berechneten P und von dem in Block 633 berechneten Q werden in den Subtrahierern 643 und 644 jeweils eine "1" abgezogen. Die Ausgänge der Subtrahierer 643 und 644 werden im Multiplizierer 645 multipliziert und das Produkt wird in den Berechnungsblock 646 eingespeist, der auch das in Block 642 berechnete PK aufnimmt. Im Berechnungsblock 646 wird SK i bestimmt als Zahl, die die Bedingung erfüllt, daß das Produkt von PK und SK gleich 1 mod ((P-1) (Q-1)) ist.
Die für dieses spezifische Beispiel durchgeführten Rechnungen sind wie folgt zusammengefaßt:
1. Calc Z: Z = 2¹&sup8;² - (2D0 + 1)
2. Calc X1: X1 = X¹²&sup7; mod Z
3. Calc X2: X2 = X1(D1+1) mod Z
4. Calc P": P" = X2 ODER (2¹&sup8;¹ + 1)
5. Calc P': P' = 2(D2 + 128) P" + 1
6. Calc P: P = 2(D3 + 128) P' + 1
7. Calc X3: X3 = Quotient von 2³&sup7;³/P
8. Calc X4: X4 = X3 wenn X3 ungerade = X3 + 1 wenn X3 gerade
9. Calc Q": Q" = 2(D4 + 128)X4 + 1
10. Calc Q': Q' = 2(D5 + 128)Q" + 1
11. Calc Q: Q = 2(D6 + 128)Q' + 1
12. Calc N: N = PQ
13. Calc X5: X5 = N mod Z
14. Calc X6: X6 = X54(D7+1) mod N
15. Calc PK: PK = X6 wenn X6 ungerade = X6 + 1 wenn X6 gerade
16. Calc SK: PKxSK = 1 mod [1 cm(P-1)(Q-1)]
Jetzt, nach der Beschreibung des Verfahrens PRECOMPUTATION ONE können die erforderlichen Abänderungen dieses Verfahrens beschrieben werden, die die Generierung der Kryptovariablen ermöglichen, die wiederum Werte von b=200 und i=7 annehmen. Da X eine Zufallszahl ist, muß es jetzt die Aufgabe sein, zu diskutieren, wie die Variablen D1, ..., D7 gewählt werden.
Der Generierungsprozeß beruht auf der Auswahl einer 56-Bit- Zufallszahl X und dann Finden der Primzahlen P", P', P, Q", Q' und Q. Auf jeder Stufe wird unter den 128 möglichen Indizes einer willkürlich ausgewählt, und Umkehr ist nicht zulässig; d.h. wenn ein Index gewählt wurde, der zur Primzahl P" führt gewählt wurde und es sich herausstellt, daß kein Index zu einer Primzahl P' führt, erfolgt eine Fehlermeldung und X wird zurückgewiesen. Somit entwickelt sich das Verfahren durch Finden eines Index D1, der eine Primzahl P" erzeugt, eines Index D2, der eine Primzahl P' erzeugt und so weiter, wobei die Indexwerte D1, ..., D6 den Primzahlen P", P', P, Q", Q' und Q in dieser Reihenfolge entsprechen. Es kann gezeigt werden, daß für dieses Beispiel durchschnittlich 2,5 Versuchswahlen für den Anfangswert X (einschließlich des letzten, erfolgreichen Versuchs) erforderlich sind, damit die sechs Primzahlen produziert werden. Eine geeignete Technik zum Testen großer Zahlen auf die Primzahleigenschaft ist der Einsatz des wirksamen "Probabilitätsalgorithmus", den R. Solovay und V. Strassen in ihrem Schreiben mit dem Titel "A Fast Monte-Carlo Test for Primality", erschienen in SIAM Journal on Computing, März 1977, Seiten 84 und 85, angegeben haben. Offensichtlich vergrößert die Erhöhung der Anzahl Bits in D1, ..., D6 von sieben auf vielleicht acht oder neun die Wahrscheinlichkeit für das Auffinden der sechs Primzahlen und verringert damit die durchschnittliche Anzahl der Versuchswerte für X. Mit anderen Worten, es gibt einen Kompromiß zwischen der Rechnerzeit zur Generierung der Kryptovariablen und der Anzahl der abgespeicherten Bits, die erforderlich sind, die Wiederherstellung der Primzahlen P und Q zu ermöglichen, wobei das Produkt von P und Q das Modul N wird. Auf ähnliche Weise wird D7 durch willkürliche Auswahl eines Index unter den 256 möglichen Werten bestimmt, so daß ein Wert für X6 erzeugt wird, der seinerseits einen öffentlichen Schlüssel PK erzeugt, der zum Produkt von P-1 und Q-1 relativ prim ist. Zwei Ganzzahlen a und b sind als relativ prim definiert, wenn sie keine gemeinsamen Primfaktoren enthalten. Ein einfaches Verfahren zur Prüfung der Eigenschaft relativ prim zweier Zahlen ist in der Technik wohlbekannt.
Unter erneuter Bezugnahme auf die Fig. 6A, 6B und 6C wird jetzt eine genaue Beschreibung der Ableitung der Parameter D1, ..., D7 gegeben. Das Verfahren zum Erzeugen der Kryptovariablen ist das gleiche, wie das Verfahren PRECOMPUTATION ONE, nur mit dem nachstehend angegeben Unterschied. Zunächst wird ein 56 Bits langer Zufallswert für X erzeugt und an einer Stelle X in Block 605 abgespeichert. Aus den 128 möglichen Werten 0, ... 127 wird ein Versuchswert für D1 gewählt. Dieser Wert wird an der Stelle D1 in Block 605 abgespeichert und auch in den Block 607 eingegeben. Jetzt folgen die gleichen Schritte wie im Vorberechnungsverfahren zur Erzeugung des Ausgangs P" aus Block 609. Das Kriterium für P" ist, daß es die Prüfung auf Primzahleigenschaft bestehen muß. Ist P" keine Primzahl, müssen die Berechnungen in den Blöcken 607, 608 und 609 mit einem anderen Versuchswert des Index D1 wiederholt werden, bis eine Primzahl P" am Ausgang vom Block 609 erzeugt ist, oder alle möglichen Indexwerte durchprobiert wurden und keine Primzahl P" gefunden wurde. Das wird erreicht durch Wählen eines anderen Werts für D1, Abspeichern dieses Wertes an der Stelle, die mit D1 im Block 605 gekennzeichnet ist, Eingabe des Wertes in Block 607 und Wiederholen der Vorberechnungsschritte der Blöcke 607, 608 und 609. Wenn nach Durchprobieren aller möglichen Indexwerte keine Primzahl P" gefunden wurde, wird eine neuer Versuchswert für X durch Zufall bestimmt und der Prozeß wiederholt sich, d.h. D1 wird für das neue X gefunden. Wenn jedoch eine Primzahl P" erzeugt wurde, enthält D1 im Block 605 den Index, der die Primzahl P" aus Block 609 erzeugt. Somit wurde ein Wert für D1 gefunden und der Prozeß geht weiter.
Aus den 128 möglichen Werten 0, ... 127 wird ein Versuchswert für D2 gewählt. Dieser Wert wird an der Stelle D2 in Block 605 abgespeichert und auch in den Block 610 eingegeben. Jetzt folgen die gleichen Schritte wie im Vorberechnungsverfahren zur Erzeugung des Ausgangs P' aus Block 614. Das Kriterium für P' ist, daß es die Prüfung auf Primzahleigenschaft bestehen muß. Ist P' keine Primzahl, müssen die Berechnungen in den Blöcken 610, 612, 613 und 614 mit einem anderen Versuchswert des Index D2 wiederholt werden, bis eine Primzahl P' am Ausgang vom Block 614 erzeugt ist, oder alle möglichen Indexwerte durchprobiert wurden und keine Primzahl P' gefunden wurde. Das wird erreicht durch Wählen eines anderen Werts für D2, Abspeichern dieses Wertes an der Stelle, die mit D2 im Block 605 gekennzeichnet ist, Eingabe des Wertes in Block 611 und Wiederholen der Vorberechnungsschritte der Blöcke 610, 612, 613 und 614. Wenn nach Durchprobieren aller möglichen Indexwerte keine Primzahl P' gefunden wurde, wird eine neuer Versuchswert für X durch Zufall bestimmt und der Prozeß wiederholt sich, d.h. D1 und D2 werden für das neue X gefunden. Wenn jedoch eine Primzahl P' erzeugt wurde, enthält D2 im Block 605 den Index, der die Primzahl P' aus Block 614 erzeugt. Somit wurden Werte für D1 und D2 gefunden und der Prozeß geht weiter.
Aus den 128 möglichen Werten 0, ... 127 wird ein Versuchswert für D3 gewählt. Dieser Wert wird an der Stelle D3 in Block 605 abgespeichert und auch in den Block 615 eingegeben. Jetzt folgen die gleichen Schritte wie im Vorberechnungsverfahren zur Erzeugung des Ausgangs P aus Block 619. Das Kriterium für P ist, daß es die Prüfung auf Primzahleigenschaft bestehen muß. Ist P keine Primzahl, müssen die Berechnungen in den Blöcken 615, 617, 618 und 619 mit einem anderen Versuchswert des Index D3 wiederholt werden, bis eine Primzahl P am Ausgang vom Block 619 erzeugt ist, oder alle möglichen Indexwerte durchprobiert wurden und keine Primzahl P gefunden wurde. Das wird erreicht durch Wählen eines anderen Werts für D3, Abspeichern dieses Wertes an der Stelle, die mit D3 im Block 605 gekennzeichnet ist, Eingabe des Wertes in Block 615 und Wiederholen der Vorberechnungsschritte der Blöcke 615, 617, 618 und 619. Wenn nach Durchprobieren aller möglichen Indexwerte keine Primzahl P gefunden wurde, wird eine neuer Versuchswert für X durch Zufall bestimmt und der Prozeß wiederholt sich, d.h. D1, D2 und D3 werden für das neue X gefunden. Wenn jedoch eine Primzahl P erzeugt wurde, enthält D3 im Block 605 den Index, der die Primzahl P aus Block 619 erzeugt. Somit wurden Werte für D1, D2 und D3 gefunden und der Prozeß geht weiter.
Aus den 128 möglichen Werten 0, ... 127 wird ein Versuchswert für D4 gewählt. Dieser Wert wird an der Stelle D4 in Block 605 abgespeichert und auch in den Block 622 eingegeben. Jetzt folgen die gleichen Schritte wie im Vorberechnungsverfahren zur Erzeugung des Ausgangs Q" aus Block 626. Das Kriterium für Q" ist, daß es die Prüfung auf Primzahleigenschaft bestehen muß. Ist Q" keine Primzahl, müssen die Berechnungen in den Blöcken 622, 624, 625 und 626 mit einem anderen Versuchswert des Index D4 wiederholt werden, bis eine Primzahl A" am Ausgang vom Block 626 erzeugt ist, oder alle möglichen Indexwerte durchprobiert wurden und keine Primzahl Q" gefunden wurde. Das wird erreicht durch Wählen eines anderen Werts für D4, Abspeichern dieses Wertes an der Stelle, die mit D4 im Block 605 gekennzeichnet ist, Eingabe des Wertes in Block 622 und Wiederholen der Vorberechnungsschritte der Blöcke 622, 624, 625 und 626. Wenn keine Primzahl Q" erzeugt wurde, enthält D4 im Block 605 den Index, der die Primzahl Q" aus Block 626 erzeugt. Somit wurden Werte für D1, D2, D3 und D4 gefunden und der Prozeß geht weiter.
Aus den 128 möglichen Werten 0, ... 127 wird ein Versuchswert für D5 gewählt. Dieser Wert wird an der Stelle D5 in Block 605 abgespeichert und auch in den Block 627 eingegeben. Jetzt folgen die gleichen Schritte wie im Vorberechnungsverfahren zur Erzeugung des Ausgangs Q' aus Block 631. Das Kriterium für Q' ist, daß es die Prüfung auf Primzahleigenschaft bestehen muß. Ist Q' keine Primzahl, müssen die Berechnungen in den Blöcken 627, 629, 630 und 631 mit einem anderen Versuchswert des Index D5 wiederholt werden, bis eine Primzahl Q' am Ausgang vom Block 631 erzeugt ist, oder alle möglichen Indexwerte durchprobiert wurden und keine Primzahl Q' gefunden wurde. Das wird erreicht durch Wählen eines anderen Werts für D5, Abspeichern dieses Wertes an der Stelle, die mit D5 im Block 605 gekennzeichnet ist, Eingabe des Wertes in Block 627 und Wiederholen der Vorberechnungsschritte der Blöcke 627, 629, 630 und 631. Wenn nach Durchprobieren aller möglichen Indexwerte keine Primzahl Q' gefunden wurde, wird eine neuer Versuchswert für X durch Zufall bestimmt und der Prozeß wiederholt sich, d.h. D1, D2, D3, D4 und D5 werden für das neue X gefunden. Wenn jedoch eine Primzahl Q' erzeugt wurde, enthält D5 im Block 605 den Index, der die Primzahl Q' aus Block 631 erzeugt. Somit wurden Werte für D1, D2, D3, D4 und D5 gefunden und der Prozeß geht weiter.
Aus den 128 möglichen Werten 0, ... 127 wird ein Versuchswert für D6 gewählt. Dieser Wert wird an der Stelle D6 in Block 605 abgespeichert und auch in den Block 632 eingegeben. Jetzt folgen die gleichen Schritte wie im Vorberechnungsverfahren zur Erzeugung des Ausgangs Q aus Block 636. Das Kriterium für Q ist, daß es die Prüfung auf Primzahleigenschaft bestehen muß. Ist Q keine Primzahl, müssen die Berechnungen in den Blöcken 632, 634, 635 und 636 mit einem anderen Versuchswert des Index D6 wiederholt werden, bis eine Primzahl Q am Ausgang vom Block 636 erzeugt ist, oder alle möglichen Indexwerte durchprobiert wurden und keine Primzahl Q gefunden wurde. Das wird erreicht durch Wählen eines anderen Werts für D6, Abspeichern dieses Wertes an der Stelle, die mit D6 im Block 605 gekennzeichnet ist, Eingabe des Wertes in Block 632 und Wiederholen der Vorberechnungsschritte der Blöcke 632, 634, 635 und 636. Wenn nach Durchprobieren aller möglichen Indexwerte keine Primzahl Q gefunden wurde, wird eine neuer Versuchswert für X durch Zufall bestimmt und der Prozeß wiederholt sich, d.h. neue D1, ..., D6 werden für das neue X gefunden. Wenn jedoch eine Primzahl Q erzeugt wurde, enthält D6 im Block 605 den Index, der die Primzahl Q aus Block 636 erzeugt. Somit wurden Werte für D1, ..., D6 gefunden und der Prozeß geht weiter.
Aus den 256 möglichen Werten 0, ... 255 wird ein Versuchswert für D7 gewählt. Dieser Wert wird an der Stelle D7 in Block 605 abgespeichert und auch in den Block 639 eingegeben. Jetzt folgen die gleichen Schritte wie im Vorberechnungsverfahren zur Erzeugung des Ausgangs PK aus Block 642. Das Kriterium für PK ist, daß es relativ prim mit dem Produkt aus P-1 und Q-1 sein muß, das als Ausgang aus Block 645 erhalten wird. Wenn diese Bedingung nicht erfüllt wird, müssen die Berechnungen in den Blöcken 639, 640, 641 und 642 mit einem anderen Versuchswert des Index D7 wiederholt werden, bis am Ausgang vom Block 642 ein PK erzeugt ist, das relativ prim mit dem Produkt aus P-1 und Q-1 ist, oder alle möglichen Indexwerte durchprobiert wurden und kein geeignetes PK gefunden wurde. Das wird erreicht durch Wählen eines anderen Werts für D7, Abspeichern dieses Wertes an der Stelle, die mit D7 im Block 605 gekennzeichnet ist, Eingabe des Wertes in Block 639 und Wiederholen der Vorberechnungsschritte der Blöcke 639, 640, 641 und 642. Wenn nach Durchprobieren aller möglichen Indexwerte keine geeignetes PK gefunden wurde, wird eine neuer Versuchswert für X durch Zufall bestimmt und der Prozeß wiederholt sich, d.h. neue D1, ..., D7 werden für das neue X gefunden. Wenn jedoch PK relativ prim mit dem Produkt aus P-1 und Q-1 erzeugt wurde, enthält D7 im Block 605 den Index, der das geeignete PK aus Block 642 erzeugt. Somit wurden Werte für D1, ..., D7 gefunden und der Generierungsprozeß ist abgeschlossen.
Die durch das Verfahren zum Generieren der Kryptovariablen erzeugten und für das Verfahren PRECOMPUTATION ONE benötigten Größen sind in Tabelle 1 zusammengefaßt. Tabelle 1 Name Geheim/nicht geheim Größe Auswahlmethode Wert Gehiem Nicht gehiem 56 Bits Zufall Abgeleitet Gemischt 0en und 1en
Wie ersichtlich sind insgesamt 106 Bits erforderlich, aus denen die Kryptovariablen N=PQ, PK und SK (insgesamt 1200 Bits) regeneriert werden können. Das gibt Anregungen für einige neuartige Ausführungsformen auf der Grundlage einer 56-Bit-Geheimnummer. Z.B. könnte der 56-Bit-Wert X eine Doppelfunktion übernehmen und zwar als DES-Schlüssel in Systemen, die nur eine DES-Verschlüsselung bieten, während der 56-Bit-Wert plus zusätzlich 50 Bits nichtgeheimer Daten benützt werden könnten, die RSA-Kryptovariable in Systemen zu generieren, in denen der RSA-Algorithmus implementiert ist. Somit hat das beschriebene Verfahren den Vorteil der Möglichkeit, ein reines RSA-Verschlüsselungssystem für Anwendungen zu nutzen, die sonst wegen der Parametergrößen des betreffenden Algorithmus nicht in Frage kämen.
Um den Vorberechnungsprozeß noch näher darzulegen, wollen wir annehmen, die Parameter aus Tabelle 1 seien generiert und auf eine Magnetstreifenkarte geschrieben worden. Der Benutzer trägt die Karte bei sich und steckt sie in ein EFT-Terminal, wie unter Bezugnahme auf Fig. 1 beschrieben wurde. Zusätzlich zum durchzuführenden normalen Ver- und Entschlüsselungsprozeß ist jedes EFT-Terminal 12 mit einem Verfahren zur Berechnung der Kryptovariablen des Benutzers (öffentlicher Schlüssel PK, geheimer Schlüssel SK und öffentliches Modul N=PQ) noch vor der Durchführung der Verschlüsselung bzw. Entschlüsselung programmiert. Die Vorberechnung ist die gleiche wie sie bei der ursprünglichen Generierung angewandt wurde, jedoch werden jetzt alle Größen direkt berechnet, d.h. es gibt kein empirisches Suchverfahren wie im Falle der Generierung der Kryptovariablen.
Die im PRECOMPUTATION TWO benutzten Variablen R und S werden aus den Variablen P, D4, D5 und D6 generiert, die ihrerseits als Teil des Verfahrens zur Generierung der Variablen X, D1, ..., D7 erzeugt werden, die im PRECOMPUTATION ONE Verfahren benutzt wurden. Die allgemeine Form der Berechnungsschritte zur Erzeugung von R und S aus P, D4, D5 und D6, wobei die Werte für b und i als Variable belassen werden, ist wie folgt definiert:
1. Calc X7: X7 = 22b-3(i+2)+3 mod P
2. Calc X8: X8 = X7 wenn X3 ungerade = X7 + P wenn X3 gerade
3. Calc R: R = (D4 + 2i) (D5 + 2i)
4. Calc S: S = -8(X8)R + 4P(D5 + 2i) (D5 + 2i) (D6 + 2i) + 2P(D6 + 2i) (D6 + 2i) +P
Wie man sieht, beinhalten die Schritte zur Generierung von R und S aus P, D4, D5 und D6 kein empirisches Suchverfahren wie im Falle der Generierung der Werte X, D1, ..., D7. Stattdessen sind die Berechnungen einfach und vollständig determiniert.
Die Berechnungsschritte für R und S im hier betrachteten Fall, in dem b=200 und i=7 ist, sind wie folgt definiert:
1. Calc X': X7 = 2³&sup7;³ mod P
2. Calc X8: X8 = X7 wenn X3 ungerade = X7 + P wenn X3 gerade
3. Calc R: R = (D4 + 128) (D5 + 128) (D6 + 128)
4. Calc S: S = -8(X8)R + 4P(D5 + 128) (D6 + 128) + 2P(D6 + 128) +P
Jetzt, nachdem das Verfahren zur Generierung der Variablen R und S diskutiert ist, ist das PRECOMPUTATION TWO Verfahren definiert. Die allgemeine Form für die Berechnungsschritte zur Erzeugung von PK und N aus R, S und D7, bei denen b und i als Variable bleiben und D0 als Verfahrensparameter angenommen wird, ist wie folgt definiert:
1. Calc Z: Z = 1b-2(i+2) - (2D0 + 1)
2. Calc N: N = (22b-3(i+2)+3R) + S
3. Calc X5: X5 = N mod Z
4. Calc X6: X6 = X54(D7+1) mod N
5. Calc PK: PK = X6 wenn X6 ungerade = X6 + 1 wenn X6 gerade
Das PRECOMPUTATION TWO Verfahren zur Berechnung von PK und N im hier betrachteten Fall, in dem b=200 und i=7 ist, ist wie folgt definiert:
1. Calc Z: Z = 2¹&sup8;² - (2D0 + 1)
2. Calc N: N = (2³&sup7;&sup6;R) + S
3. Calc X5: X5 = N mod Z
4. Calc X6: X6 = X54(D7+1) mod N
5. Calc PK: PK = X6 wenn X6 ungerade = X6 + 1 wenn X6 gerade
Die PRECOMPUTATION TWO Berechnung im vorliegenden Fall, in dem b=200 und i=7 ist, ist auch in Fig. 7 dargestellt. Zunächst erfolgt die Berechnung von Z im Berechnungsblock 700, in dem die in Register 701 abgespeicherte Variable D0 durch Verschieben um eine Stelle nach links mit 2 multipliziert wird wie in Block 702 angedeutet wird, dann Aufaddieren von 1 durch zwangsweises Setzen des niedrigstwertigen Bits (LSB) auf "1", wie in Block 703 angedeutet wird, und dann Abziehen des Ergebnisses von 2¹&sup8;² im Subtrahierer 704. Als nächstes wird das 400-Bit Register 705 durch Nullsetzen aller Bits durch den Schaltkreis 706 vorinitialisiert. Der nichtgeheime Wert von S wird dann aus dem Register 707 gelesen und durch den Schaltkreis 708 rechtsbündig in das Register 705 geladen. Der nichtgeheime Wert R wird ebenfalls durch den Schaltkreis 709 aus dem Register 705 gelesen. Als Ergebnis dieses Ladens von R und S in das Register 705 enthält jetzt das Register 705 von links nach rechts einen 24-Bit-Wert R, 158 0-Bits und einen 218-Bit-Wert S. Das erzeugt in Register 705 den Wert N.
Die Inhalte des Registers 705 werden jetzt mit dem in Block 700 berechneten Z benutzt, um X5 unter Anwendung der Modulo- Arithmetik in Block 710 zu berechnen; d.h. X5 ist der Rest der Division der Zahl in Register 705 durch den Wert Z. Der Parameter D7 wird aus dem Register 707 gelesen und im Addierer 711 wird "1" aufaddiert und das Ergebnis wird mit 4 multipliziert durch Verschieben um zwei Stellen nach links, wie in Block 712 angedeutet ist. Dann wird in Block 713 X5 mit dem Ergebnis aus Block 712 potenziert und mit dem Wert N aus Register 705 benutzt, um X6 mit Modulo-Arithmetik zu berechnen. In Block 714 wird das niedrigstwertige Bit von X6 zwangsweise auf "1" gesetzt um PK zu erzeugen. Damit liefert das Berechnungsverfahren das Modul N in Register 705 und den öffentlichen Schlüssel pK als Ausgang von Block 714.
Die Technik zur Reduzierung des Speicherplatzes für Kryptovariable kann wie folgt zusammengefaßt werden.
Die PRECOMPUTATION ONE Berechnung erfordert Speicherplatz für 106 Bits (56 geheime Bits und 50 nicht geheime Bits).
Die PRECOMPUTATION TWO Berechnung erfordert Speicherplatz für 250 Bits und alle 250 Bits sind nicht geheim. Etwa zweimal so viel Berechnungen sind für die Generierung der Kryptovariablen erforderlich. Beide Vorberechnungsverfahren, gleichbedeutend mit weniger als 10% einer RSA-Verschlüsselung, sind erforderlich jedesmal, wenn das Modul und die Schlüssel aus den abgespeicherten Bits regeneriert werden.
Zwar wurde die Erfindung im einzelnen im Hinblick auf eine bevorzugte Ausführungsform gezeigt und beschrieben, jedoch ist dem Fachmann ohne weiteres klar, daß die obigen und weitere Änderungen in Form und Details vorgenommen werden können, ohne vom Umfang der Ansprüche abzuweichen.

Claims

1. Verfahren um Identifizieren einer Person für einen Benutzer eines Systems mit mehreren Datenstationen, wobei das Verfahren auf einem Verschlüsselungssystem für bekannte Schlüssel von der Art mit einer Modulo-Potenzierung beruht, dessen Modul das Produkt zweier binärer Primzahlen ist und die folgenden Schritte umfaßt:

Lesen einer dem Benutzer zugewiesenen Kontonummer und einer äußeren Kryptavariable bei einer Datenstation (12) des Systems mit mehreren Datenstationen, wobei die äußere Kryptovariable n Bits aufweist, bei welchem m Bits geheimgehalten werden und die restlichen n-m Bits bekannt sind, und die Kontonummer und die äußere Kryptovariable auf einer Magnetstreifenkarte (10) gespeichert sind,

Durchführen einer Vorausberechnung für die äußere Kryptovariable, um einen geheimen Personenschlüssel (KPi) und einen dem Benutzer zugewiesenen bekannten Modul (Ni) zu regenerieren,

Empfangen einer geheimen Nummer (PINi) für eine Personenidentifizierung, die von dem Benutzer bei der Datenstation eingegeben wurde und

Prüfen der Identifizierung des Benutzers auf der Grundlage der Kontozahl des Benutzers, des regenerierten geieimen Personenschlüssels und des bekannten Moduls und der Zahl für eine Personenidentifizierung, die von dem Benutzer eingegeben wurde.

2. Verfahren nach Anspruch 1, bei welchem die äußere, auf der Magnetstreifenkarte gespeicherte Kryptovariable nicht mehr als 108 Bits aufweist.

3. Verfahren nach Anspruch 1 oder Anspruch 2, bei welchem die äußere Kryptovariable auf der Magnetstreifenkarte 106 Bits aufweist, bei welchen 56 geheimgehalten werden und bei welchem der Schritt des Durchführens einer Vorausberechnung einen Geheimschüssel und einen bekannten Modul mit 400 Bits für jeden erzeugt.

4. Verfahren nach irgendeinem vorgehenden Anspruch, bei welchem der Schritt des Prüfens die folgenden Schritte umfaßt:

Übertragen der Kontonummer des Benutzers und einer Kennzeichnung der Datenstation zu einem zentralen Verarbeitungssystem in dem System mit mehreren Datenstationen,

Erzeugen einer ersten Zufallszahl bei dem zentralen Verarbeitungssystem und Übertragen der ersten Zufallszahl zu der Datenstation,

Verketten einer Nachricht einer Transaktionsanforderung mit der ersten Zufallszahl,

Unterwerfen der Zahl für eine Personenidentifizierung, die von dem Benutzer bei der Datenstation eingegeben wurde mit dem regenerierten Geheimschlüssel einer Exklusiv-Oder-Verknüpfung, um einen Entzifferungsschlüssel zu erzeugen,

Entziffern der verketteten Nachricht einer Transaktionsanforderung und der ersten Zufallszahl unter Verwendung des Entzifferungsschlüssels und des bekannten Moduls des Benutzers und Übertragen der entzifferten Nachricht einer Transaktionsanforderung und der ersten Zufallszahl zu dem zentralen Verarbeitungssystem,

Erzeugen einer zweiten Zufallszahl bei der Datenstation und Übertragen der zweiten Zufallszahl zu dem zentralen Verarbeitungssystem,

Verwenden der Kontozahl des Benutzers, um bei dem zentralen Verarbeitungssystem einen bekannten Schlüssel und einen dem Benutzer zugewiesenen Modul zu erzeugen,

Verschlüsseln der empfangenen, entzifferten Nachricht einer Transaktionsanforderung und der ersten Zufallszahl unter Verwendung des erzeugten bekannten Schlüssels und des dem Benutzer zugewiesenen Moduls, um die erste Zufallszahl wiederherzustellen,

Vergleichen der wiederhergestellten ersten Zufallszahl mit der ersten Zufallszahl, die bei dem zentralen Verarbeitungssystem erzeugt wurde,

Entziffern der empfangenen zweiten Zufallszahl unter einem zweiten Geheimschlüssel und einem Modul und Übertragen der entzifferten zweiten Zufallszahl zu der Datenstation, falls die wiederhergestellte erste Zufallszahl gleich ist der ersten Zufallszahl, die bei dem zentralen Verarbeitungssystem erzeugt wurde,

Verschlüsseln der empfangenen entzifferten zweiten Zufallszahl bei der Datenstation, um die zweite Zufallszahl wiederherzustellen und

Vergleichen der wiederhergestellten zweiten Zufallszahl mit der zweiten Zufallszahl, die bei der Datenstation erzeugt wurde.

5. Verfahren nach irgendeinem vorgehenden Anspruch, bei welchem der Schritt des Durchführens der Vorausberechnung die folgenden Schritte umfaßt:

Erweitern der Bitlänge der geheimen m Bits entsprechend einer vorher definierten, nicht geheimen Funktion unter Verwendung der bekannten n-m Bits, um eine erste Primzahl zu erzeugen,

Dividieren einer vorbestimmten Konstante durch die erste Primzahl, um einen Quotienten zu erhalten,

Erweitern der Bitlänge des Quotienten entsprechend einer vorher definierten, nicht geheimen Funktion unter Verwendung der bekannten n-m Bits, um eine zweite Primzahl zu erzeugen,

Multiplizieren der ersten und zweiten Primzahlen miteinander um als ein Produkt den bekannten Modul zu erhalten und

Bilden des Geheimschlüssels aus den ersten und zweiten Primzahlen.

6. EFT-Datenstation (12), die folgendes aufweist:

Mittel zum Lesen einer Kontozahl, die einem Benutzer der Datenstation zugewiesen ist und einer äußeren Kryptovariable aus einer Magnetstreifenkarte (10), wobei die äußere Kryptovariable n Bits aufweist, bei welchen m Bits geheimgehalten werden und die restlichen n-m Bits bekannt sind,

Mittel zum Empfangen einer geheimen Nummer (PINi) für eine Personenidentifizierung, die von dein Benutzer eingegeben wurde,

Mittel zum Regenerieren eines geheimen Personenschlüssels (KPi) und eines dem Benutzer zugewiesenen bekannten Moduls (Ni) aus der äußeren Kryptovariable, zum Verwenden in einem Verschlüsselungssystem für bekannte Schlüssel von der Art mit einer Modulo-Potenzierung, dessen Modul das Produkt zweier binärer Primzahlen ist, wobei das Prüfen der Identifizierung des Benutzers auf der Kontozahl, dem regenerierten geheimen Personenschlüssel und dem bekannten Modul und der Zahl für eine Personenidentifizierung beruht, die von dem Benutzer eingegeben wurde.