DE68907717T2

DE68907717T2 - Diversifizierungsverfahren für öffentliche schlüssel.

Info

Publication number: DE68907717T2
Application number: DE89909280T
Authority: DE
Inventors: Jeffrey Austin
Original assignee: NCR International Inc
Current assignee: NCR International Inc
Priority date: 1988-08-19
Filing date: 1989-07-27
Publication date: 1994-02-17
Anticipated expiration: 2009-07-28
Also published as: DE68907717D1; AU4052489A; AU607351B2; EP0400103A1; JPH03505033A; EP0400103B1; WO1990002456A1

Description

Die Erfindung betrifft die Verschlüsselung mit öffentlichem Schlüssel.
Die Verschlüsselung mit öffentlichem Schlüssel ist beispielsweise in dem Aufsatz: Communications of the ACM, Band 21, Nr. 2, Februar 1978, Seiten 120 - 126 von R. L. Rivest u. a. "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems" beschrieben. Kurz gesagt, wird bei der Verschlüsselung mit öffentlichem Schlüssel eine Nachricht dadurch verschlüsselt, daß sie als eine Zahl M dargestellt, M zu einer öffentlich angegebenen Potenz e erhoben und dann der Rest verwendet wird, der sich beim Dividieren des Ergebnisses durch ein öffentlich angegebenes Produkt N zweier großer geheimer Primzahlen p und Q ergibt. Die Entschlüsselung ist ähnlich, mit der Ausnahme, daß eine andere geheime Potenz d verwendet wird, wobei
e.d = 1 (mod (P-1).(Q-1)).
Die Sicherheit eines derartigen Systems hängt teilweise von der Schwierigkeit der Faktorbildung des öffentlich angegebenen Wertes N ab. Ein weiteres Merkmal eines derartigen Systems besteht darin, daß Nachrichten "unterschrieben" werden können unter Verwendung eines geheimgehaltenen Entschlüsselungsschlüssel d, wobei jedermann diese Unterschrift unter Verwendung des öffentlich bekannten Verschlüsselungsschlüssels e verifizieren kann.
Ist insbesondere N das Produkt zweier Primzahlen P, Q, d. h. wenn
N = P.Q
und wenn e relativ teilerfremd zu φ(N) ist, wobei
φ(N) = (P-1). (Q-1)
die Euler'sche Totientenfunktion von N (die Anzahl von ganzen Zahlen kleiner N, die relativ teilerfremd zu N sind) ist, dann kann in der modul-N-Arithmetik ein Wert d bestimmt werden (siehe beispielsweise der vorgenannte Aufsatz von Rivest u. a.), der multiplikativ invers zu e ist derart, daß
e.d = 1 (mod φ(N)).
Der Wert d wird allgemein als das Geheimschlüsselgegenstück zu dem öffentlichen Schlüssel e bezeichnet.
Wenn somit
X = Ye (mod N),
dann
Y = Xd (mod N)
für alle Werte von Y mit 0 ≤ Y < N.
Wie zuvor erwähnt, wurde dieses Wissen auf dem Gebiete der Verschlüsselung dazu verwendet, verschiedene Verschlüsselungssysteme zu entwerfen, wobei typischerweise die ganzen Zahlen e und N Teilnehmern von Verschlüsselungssitzungen als ein öffentlicher Verschlüsselungsschlüssel genannt werden und die ganze Zahl d von dem die Schlüssel ausgebenden Teilnehmer als Geheimschlüsselwert gehalten wird.
Benutzer dieser Techniken können somit Daten Y unter Verwendung des öffentlichen Schlüssels (e, N) in akzeptabler Kenntnis verschlüsseln, daß nur der Halter des geheimen Schlüsselwertes d die Daten Y entschlüsseln kann.
In gleicher Weise kann der Halter des geheimen Schlüsselwertes d Daten X unter Verwendung von (d, N) verschlüsseln, so daß irgendein Teilnehmer mit Kenntnis der öffentlichen Schlüsselwerte (e, N) feststellen kann, daß nur der Halter des geheimen Schlüsselwertes d die Quelle für die Daten X gewesen sein kann.
Diese Prozeduren erlauben es Benutzern der Technik, 10 sensitive Daten zu verschlüsseln und auch diese Daten digital zu unterzeichnen, um ihre Quelle zu authentifizieren.
Der Beweis der zurvor erwähnten Beziehungen wird nun gegeben.
Angenommen, daß
N = P.Q
und
e.d = 1 mod φ(N) (1)
wobei sowohl P und Q ganze Primzahlen sind, dann ist
φ(N) = φ(P).φ(Q) = (P-1).(Q-1).
Es wird gezeigt, daß, wenn
X = Ye (mod N) (2)
dann
Y = Xd (mod N). (3)
Es ist zu beachten, wenn (3) wahr ist, dann sich aus (2) ergibt, daß
X = Xe.d (mod N).
Aus (1) ergibt sich dann, daß Xe.d = X1+Kφ(N) (mod N), wobei K irgendeine ganze Zahl ist.
Da P eine Primzahl ist, so ist es bekannt (Fermat'sches "klein"-Theorem), daß
XP-1 = 1 (mod P) für alle X, 0 < X < P.
Da P-1 dividiert φ(N) = (P-1).(Q-1)
X1+Kφ(N) = X (mod P) für alle X, 0 ≤ X < P. (4)
In ähnlicher Weise, da Q eine Primzahl ist, so ist
X1-kφ(N) = X (mod Q) für alle X, 0 ≤ X < Q. (5)
Aus den Gleichungen (4) und (5) ergibt sich, daß
X1+Kφ(N) = X (mod P.Q) für alle X, 0 ≤ X < N,
d. h. daß
X = Ye - Xe.d = X1+Kφ(N) = X (mod N).
Wenn somit
X = Ye (mod N),
dann ist
Y = Xd (mod N)
für alle Y für 0 ≤ Y < N.
Eine Aufgabe der vorliegenden Erfindung ist es, ein Verfahren anzugeben, durch das eine aus einer Vielzahl von Mitgliedern oder Stellen bestehende Gruppe irgendein Mitglied der Gruppe mit einem geheimen Schlüssel zum Zwecke der Entschlüsselung von Daten oder digitalen Signierung von Daten versehen wird, welcher geheime Schlüssel nur diesem Mitglied bekannt ist, wobei jedoch der dazu passende öffentliche Schlüssel leicht von irgendeiner Stelle (ob Gruppenmitglied oder nicht) abgeleitet werden kann und wodurch verifiziert werden kann, daß das den geheimen Schlüssel verwendende Mitglied ein rechtmäßiges Mitglied der Gruppe ist.
Erfindungsgemäß wird somit ein Verfahren zum Diversifizieren eines Schlüsselpaares zur Verwendung bei der Verschlüsselung mittels öffentlichem Schlüssel durch eine anfragende Stelle mit dem Schritt Erzeugen bei einer übergeordneten Stelle eines öffentlichen Schlüssels N, e, wobei modul N das Produkt einer ersten und zweiten Primzahl P, Q und e ein entsprechender ganzzahliger öffentlicher Schlüssel ist, angegeben, das gekennzeichnet ist durch die Schritte: Auswählen einer dritten und vierten Primzahl R, S und Übertragen zur anfordernden Stelle eines ersten Wertes Nmi und eines zweiten Wertes φ(Nmi), wobei der erste Nmi = N.R.S und wobei der zweite Wert
φ(Nmi) = φ(N).(R-1).(S-1)
ist, wobei das Symbol φ die Euler'sche Totientenfunktion darstellt; Auswählen bei der anfordernden Stelle einer fünften und sechsten Primzahl T, U; und Berechnen bei der anfordernden Stelle eines dritten Wertes Nm und eines vierten Wertes dm, wobei
Nm = Nmi.T.U,
und wobei
dm = (1+Kφ(Nm))/e,
wobei
φ(Nm) = φ(Nmi).(T-1).(U-1)
und wobei K und dm ganze Zahlen sind, so daß dm geeignet ist, von der anfordernden Stelle als das Geheimschlüsselgegenstück des öffentlichen Schlüsselwertes e bezüglich modul Nm verwendet zu werden.
Bei einer besonderen Anwendung kann die Gruppe von Mitgliedern oder Stellen eine internationale Vorgangskarten ausgebende Institution sein, die viele Mitglieder hat, beispielsweise in der Größenordnung von tausenden von Mitgliedern.
Eine Ausführungsform der Erfindung wird nun als Beispiel unter Bezugnahme auf die Zeichnungen beschrieben, in denen
Fig. 1 ein Blockdiagramm eines Verarbeitungsgerätes ist, das bei der Gruppenstammstelle angeordnet ist;
Fig. 2 ein Flußdiagramm ist, das die Erzeugungs- oder Aufbauphase der Operation des Stammverarbeitungsgerätes veranschaulicht;
Fig. 3 ein Flußdiagramm ist, das eine Arbeitsphase des Stammverarbeitungsgerätes unter Ansprechen auf eine Mitgliederanforderung veranschaulicht;
Fig. 4 ein Blockdiagramm des Verarbeitungsgerätes ist, das sich bei einem Gruppenmitglied befindet;
Fig. 5 ein Flußdiagramm ist, das die Erzeugungsphase der Operation für das Mitgliedverarbeitungsgerät veranschaulicht;
Fig. 6 ein Flußdiagramm ist, das die Betriebsphase des Mitgliedverarbeitungsgerätes veranschaulicht; und
Fig. 7 ein Flußdiagramm ist, daß die Betriebsphase einer Stelle veranschaulicht, die mit einem Gruppenmitglied kommuniziert.
Um das Verständnis der vorliegenden Erfindung zu erleichtern, wird zuerst das der Erfindung zugrundeliegende mathematische Prinzip erläutert. Somit sind die mathematischen Beziehungen, die vorstehend erstellt wurden, für den Fall, bei dem
N = P.Q
das Produkt zweier Primzahlen ist, deutlich ersichtlich gleichermaßen gültig für den Fall, bei dem N das Produkt von mehr als zwei Primzahlen ist, da für eine derartige Zahl N alle ganzen Zahlen I, die Faktoren von N sind,
XI-1 = 1 (mod I)
genügen. Wenn somit beispielsweise
N = P.Q.R.S.T.U
das Produkt von sechs Primzahlen ist, dann ist für
X = Ye(mod N)
auch
Y = Xd(mod N)
für alle Y für 0 ≤ Y < N
vorausgesetzt daß
e.d = 1 (mod φ(N))
wobei
(φN) = (P-1).(Q-1).(R-1).(S-1).(T-1).
Die bevorzugte Ausführungsform der Erfindung wird nun mit Bezug auf eine Gruppe von Mitgliedern oder Stellen beschrieben, von denen ein spezifiziertes Mitglied ein damit betrautes Mitglied ist, das als "Stamm"-Mitglied bezeichnet sei. Für eine derartige Gruppe von Mitgliedern sind drei Probleme anzugehen:
1. Prüfung der Gruppenmitgliedschaft.
2. Schutz der individuellen Mitgliedgeheimschlüssel.
3. Einfache Ableitung der passenden öffentlichen Mitgliederschlüssel.
Es wird nun auf Fig. 1 Bezug genommen, wo ein Blockschaltbild des Gerätes gezeigt ist, das bei dem Stamm- Mitglied angeordnet ist. Ein derartiges Gerät enthält einen Sicherheitsprozessor 10, der Sicherheitsprozessor 10 umfaßt ein Gehäuse 12, das einen Mikroprozessor 14, einen Programmspeicher PROM 16, einen RAM Arbeitsspeicher 18 (RAM = Speicher mit wahlfreiem Zugriff), einen sicheren nichtflüchtigen Speicher 20, einen Zufallszahlgenerator 22, eine Eindringfeststellschaltung 24 und eine Eingabe-/Ausgabeeinheit 26 umfaßt. Die Vorrichtungen 14, 16, 18, 20, 22 und 26 sind durch einen internen Bus 28 verbunden. Die Eindringfeststellschaltung 24 ist geeignet, jegliches unautorisiertes Eindringen bezüglich des Gehäuses 12 festzustellen, etwa einen Versuch, das Gehäuse zu durchdringen, und ein Rückstellsignal über Leitung 30 abzugeben, mit dem der sichere nichtflüchtige Speicher 20 unter Ansprechen auf die Feststellung eines derartigen Eindringens rückgestellt wird. Ein Beispiel eines geeigneten Sicherheitsprozessors ist in größerer Einzelheit in dem U.S. Patent Nr. 4,593,384 beschrieben.
Der Sicherheitsprozessor 10 ist über einen externen Bus 32 mit einer Vielzahl peripherer Einrichtungen verbunden, einschließlich eines Tastenfeldes 34, über das Daten manuell eingegeben werden können, einer Anzeige 36, eines Druckers 38, über den Ausgangsdaten gedruckt werden können, und einer Kommunikationsschnittstelle 40 (etwa einem Modem), die ermöglicht, daß eine Datenübertragung mit entfernten Vorrichtungen über einen Kanal 42 stattfindet.
Es wird nun auf Fig. 2 Bezug genommen, wo ein Flußdiagramm für den an der Stammstelle angeordneten Sicherheitsprozessor 10 während der Erzeugung eines öffentlichen Schlüssels (e, N) zeigt. In einem anfänglichen Eingangsschritt wird, wie bei Rechteck 50 gezeigt, ein Initialisierungs- oder Einstellbefehl angelegt, um den Sicherheitsprozessor 10 für die Durchführung der gewünschten Operation zu konditionieren. Als nächstes sorgt, wie in Rechteck 52 gezeigt, eine Routine für die Auswahl zweier großer Zufallsprimzahlen P und Q. Derartige Routinen sind allgemein bekannt. Beispielsweise können ungerade Zufallszahlen der gewünschten Größe durch einen Zufallszahlgenerator 22 erzeugt und durch Wahrscheinlichkeitsprüfmethoden auf Primäreigenschaft geprüft werden, wie dies in dem vorgenannten Aufsatz von Rivest u. a. erläutert ist.
Wie im Rechteck 54 angegeben, werden als nächstes drei Werte abgeleitet, nämlich der Wert N, der das Produkt von P und Q ist; der Wert φ(N), der das Produkt von P-1 und Q-1 ist; und ein Wert e, der teilerfremd bezüglich φ(N) ist, was bedeutet, daß der größte gemeinsame Teiler (ggT) von e und φ(N) gleich 1 ist. Vorzugsweise ist e eine Primzahl aus einem Grunde, der später noch erläutert wird. Wie im Rechteck 56 gezeigt, werden dann die Werte N, φ(N) und e in dem sicheren nichtflüchtigen Speicher 20, Fig. 1, gespeichert. Die Werte N und e sind auf ein an den Sicherheitsprozessor 10 angelegtes geeignetes Anforderungssignal gemäß Rechteck 58 erhältlich.
Es wird nun auf Fig. 3 Bezug genommen, die ein Flußdiagramm für den an der Stammstelle angeordneten Sicherheitsprozessor 10 in der Betriebsphase unter Ansprechen auf ein von einem Gruppenmitglied angelegten Anforderungssignal zeigt. Gemäß Rechteck 70 empfängt somit der Sicherheitsprozessor 10 ein Eingangssignal, einen Mitglied-Anforderungsbefehl zusammen mit einer Mitglied- Identifizierung ID, die das die Anforderung anlegende Gruppenmitglied identifiziert.
Wie in Rechteck 72 gezeigt, besorgt dann eine Routine die Auswahl zweier großer Primzahlen R und S, die von den Primzahlen P und Q verschieden sind. Wie in Rechteck 74 gezeigt, wird als nächstes der Wert Nmi berechnet, der ein Produkt aus N, R und S ist:
Nmi = N.R.S
und auch der Wert φ(Nmi), wobei
φ(Nmi) = φ(N).(R-1).(S-1).
Wie in Rechteck 76 gezeigt, wird als nächstes der Wert der Mitglieds-ID in dem Sicherheitsspeicher 20 zusammen mit den Werten Nmi, φ(Nmi) gespeichert. Diese gespeicherten Werte stehen nun für eine Ausgabe aus dem Sicherheitsprozessor 10 zur Verfügung, wie dies in Rechteck 78 angegeben ist, und können angezeigt, gedruckt oder einem Sicherheitsprozessor 110 (Fig. 4) zugeführt werden, der bei dem anfordernden Mitglied angeordnet ist, was nun beschrieben wird.
Fig. 4 zeigt ein Blockdiagramm eines Gerätes, das bei jedem Mitglied der Gruppe angeordnet ist. Das vorgesehene Gerät gleicht demjenigen, das an der Stammstelle angeordnet ist und zuvor unter Bezugnahme auf Fig. 1 beschrieben wurde. Somit umfaßt das Mitgliedgerät einen Sicherheitsprozessor 110, mit einem Gehäuse 112, das einen Mikroprozessor 114, einen Programmspeicher PROM 116, einen RAM Arbeitsspeicher 118, einen sicheren nichtflüchtigen Speicher 120, einen Zufallszahlgenerator 122, eine Eindringfeststellschaltung 124 und eine Eingangs-/Ausgangseinheit 126. Ein interner Bus 128 verbindet die verschiedenen Vorrichtungen, wie dies in Fig. 4 gezeigt ist. Die Eindringfeststellschaltung 124 kann ein Rückstellsignal über eine Leitung 130 unter Ansprechen auf die Feststellung eines Versuchs abgeben, in das Gehäuse 112 einzudringen. Es wird wiederum auf das U.S. Patent Nr. 4,593,384 für eine nähere Beschreibung eines geeigneten Sicherheitsprozessors verwiesen. Der Sicherheitsprozessor 110 ist über einen externen Bus 132 mit einem Tastenfeld 134, einer Anzeige 136, einem Drucker 138 und einer Kommunikationsschnittstelle 140 verbunden, die ermöglicht, daß eine Datenübertragung mit entfernten Vorrichtungen über einen Kanal 142 stattfinden kann.
Es wird nun auf Fig. 5 Bezug genommen, die ein Flußdiagramm für den bei dem Gruppenmitglied angeordneten Sicherheitsprozessor 110 während einer Schlüsselerzeugungsphase für das Gruppenmitglied zeigt. Anfangs wird ein Initialisierungsbefehl an den Prozessor 110 zusammen mit den Werten N, e, Nmi und φ(Nmi) angelegt, der von einer von dem Sicherheitsprozessor 10 an der Stammstelle erzeugten und über die Kanäle 42 und 142 zu dem Sicherheitsprozessor 110 übertragenen Verschlüsselung abgeleitet sein kann. Gemäß Rechteck 152 wird als nächstes eine Routine zur Auswahl zweier großer Primzahlen T und U bewirkt. Es ist zu beachten, daß alle Primzahlen P, Q, R, S, T, U verschieden sind. Die Stammstelle wählt P, Q, R und S aus und kann ihre Verschiedenheit gewährleisten. Das Mitglied kennt diese Werte jedoch nicht und könnte zufälligerweise T oder U gleich P, Q, R oder S wählen. Für große Primzahlen ist die Wahrscheinlichkeit jedoch entfernt. Für kleine Primzahlen kann die Wahrscheinlichkeit jedoch ein Problem sein. Diese Wahrscheinlichkeit kann dadurch vermieden werden, daß die Stammstelle dem Sicherheitsprozessor 110 eine Größengrenze für T-, U-Werte zuführt.
Wenn beispielsweise
P, Q, R, S > 2¹&sup5;&sup0;
ist, dann kann
T, U < 2¹&sup5;&sup0;
sein. Um die Auswahl von Primzahlen beim Mitglied nicht einzuschränken, ist ferner zu beachten, daß der von der Stammstelle anfänglich gewählte Wert von e eine Primzahl sein sollte, wodurch die relative Teilerfremdheit von e bezüglich irgendeines φ(Nm)-Wertes gewährleistet wird.
Wie in Rechteck 154 gezeigt, werden als nächstes vier Werte berechnet. Zuerst ein Wert Nm, der das Produkt von Nmi, T und U ist:
Nm = Nmi T.U.
Als zweites durch Dividieren von Nm durch N wird ein Wert Nmv berechnet:
Nmv = Nm/N
Der Wert Nmv sei hier als "Mitgliedsvariante" bezeichnet.
Drittens wird der Wert φ(Nm) als das Produkt von φ(Nmi), T- 1 und U-1 berechnet:
φ(Nm) = φ(Nmi).(T-1).(U-1).
Schließlich wird eine ganze Zahl dm mit der Formel berechnet
dm = 1+Kφ(Nm)/e.
In dieser Formel ist K ein ganzzahliger Wert, der wunschgemäß derart gewählt wird, daß dm, was der geheime Schlüssel des Mitglieds ist, die kleinste ganze Zahl ist, die aus der Formel berechnet werden kann. Es wird darauf hingewiesen, daß die Schritte 152 und 154, die bei dem Mitgliedsprozessor 110 ausgeführt werden, die Wirkung haben, daß verhindert wird, daß die Stammstelle φ(Nm) des Mitglieds und damit den geheimen Schlüssel des Mitglieds bestimmt, da die Stammstelle den Faktor T.U = Nm/Nmi benötigen würde, um T-1 und U-1 zu bestimmen und somit eine derartige Faktorbildung nicht machbar ist, wenn T und U geeignet große Primzahlen sind. In ähnlicher Weise kann das Mitglied in Kenntnis von N, Nmi und φ(Nmi) praktisch φ(N) der Stammstelle und damit P, Q nicht bestimmen, da dies die Faktorbildung R.S = Nmi/N erfordert. Es ist somit ersichtlich, daß der Wert φ(Nm) von dem "Saatwert" N stammt, jedoch "doppelt diversifiziert" ist, um die Berechnung durch irgendeine andere Person oder Stelle als dem Mitgliedschaftseigner zu verhindern, der nur ein zulässiges φ(Nm) und somit ein zulässiges dm unter Verwendung der von der Stammstelle gelieferten Werte ableiten kann.
Es wird nun wieder auf Fig. 5, Rechteck 156 Bezug genommen, gemäß dem die Werte Nm, dm, e, N und Nmv in dem sicheren nichtflüchtigen Speicher 120 gespeichert werden. Schließlich wird gemäß Rechteck 158 der Mitgliedsvariantenwert Nmv als ein Ausgangssignal zum Drucken, Anzeigen und/oder einer Fernübertragung abgegeben. Dieser Mitgliedsvariantenwert wird "veröffentlicht" oder auf Anforderung verfügbar gemacht, und das öffentliche Schlüsselmodul des Mitglieds kann einfach durch Multiplizieren von Nmv mit N abgeleitet werden:
Nm = Nmv.N.
Somit hat das Mitglied den öffentlichen Schlüssel (e, Nm) mit dem entsprechenden Geheimschlüsselgegenstück dm. Es wird jedoch der Mitgliedsvariantenwert Nmv und nicht Nm selbst durch das Mitglied bekanntgegeben.
Unter Berücksichtigung des vorstehenden ist ersichtlich, daß die Authentizität der von dem Mitglied ausgehenden Daten Y dadurch erstellt werden kann, daß das Mitglied die Daten mit dm digital signiert, nämlich
X = Ydm (mod Nm)
und daß eine derartige Unterschrift X von irgendeiner Stelle (ob ein Mitglied der Gruppe oder nicht) durch Berechnen von
Y = Xe (mod N.Nmv)
verifiziert werden kann. Diese Prozedur bestimmt nicht nur die Gültigkeit der durch das Mitglied über Nmv abgegebenen Unterschrift, sondern bestimmt auch die gültige Mitgliedschaft der Gruppe über N. Wenn somit der Beweis über die Gruppenmitgliedschaft erstellt wurde, dann kann auch dem Wert Nmv Vertrauen geschenkt werden, auch wenn er unmittelbar vor dem Authentizitätstest unbekannt sein kann. Er kann somit mit der digitalen Unterschrift geliefert werden, was der Notwendigkeit für irgendeine frühere Kenntnis durch den Unterschriftsverifizierer mit Ausnahme für die veröffentlichten Gruppenwerte N und e enthebt.
Ferner können verschlüsselte Daten Y praktisch nur durch das Mitglied unter Verwendung einer mod Nm-Exponentierung mit der Potenz dm entschlüsselt werden, vorausgesetzt, daß der Sender derartiger verschlüsselter Daten den für die Gruppe öffentlichen e-Wert und den durch die Mitgliedsvariante Nmv modifizierten N-Wert verwendet.
Es wird nun auf Fig. 6 Bezug genommen, die ein Flußdiagramm für die Betriebsphase des Mitgliedssicherheitsprozessors 110 zeigt. Wie im Rechteck 170 gezeigt, wird zusammen mit den verschlüsselten Daten oder Klartext ein Entschlüsselungsbefehl eingegeben. Gemäß Rechteck 172 werden die Eingangsdaten unter Verwendung des gespeicherten geheimen Schlüssels dm des Mitglieds zu der Exponentenpotenz dm erhoben und das Resultat wird als Rest mod Nm unter Verwendung des Modulwertes Nm des öffentlichen Schlüssels des Mitglieds ausgedrückt, wodurch Klartext oder eine digitale Unterschrift abgegeben wird. Schließlich wird, wie in Rechteck 174 gezeigt, der abgegebene Klartext oder die digitale Unterschrift als ein Ausgangssignal zum Drucken, Anzeigen oder für eine Fernübertragung zusammen mit der im Mitgliedsvariantenwert Nmv verfügbar gemacht.
Es ist ersichtlich, daß eine derartige Kommunikation mit einem Gruppenmitglied durch eine Stelle aufgebaut werden kann, die nicht ein Gruppenmitglied ist. Eine Kommunikation durch eine derartige Stelle ist in dem Flußdiagramm in Fig. 7 veranschaulicht, wobei verständlich ist, daß die Stelle ein üblicher Prozessor, etwa ein PC (Personalcomputer) ist, mit Rechen- und Speicherfähigkeiten. So zeigt Rechteck 180 ein Eingangssignal, das einen Verschlüsselungsbefehl, die von der Gruppenstammstelle abgegebenen oder von veröffentlichten Listen abgeleiteten Werte N und e, Eingangsdaten in Form von Klartext oder einer Unterschrift und einen Mitgliedsvariantenwert Nmv umfassen, der dem Mitglied entspricht, mit dem die Stelle kommunizieren will. Als nächstes wird, wie in Rechteck 182 gezeigt, das Produkt von Nmv und N berechnet, um Nm zu erzeugen, was das modul des öffentlichen Schlüssels des kommunizierenden Gruppenmitglieds ist. Dann werden die Eingangsdaten (Klartext oder Unterschrift) der Exponentierung mit der Potenz e, modulo Nm unterworfen, um verschlüsselte Daten oder Klartext zu erzeugen, wobei so berechnete Daten, falls erwünscht, gespeichert werden, wie dies in Rechteck 184 gezeigt ist. Die verschlüsselten Daten oder Klartext sind dann verfügbar, um als Ausgangssignale abgegeben zu werden, wie dies in Rechteck 186 gezeigt ist.
Ein Vorteil der hier beschriebenen Anordnung ist, daß ein Fälscher, der N kennt, praktisch nicht ein geeignetes Nmv und ein dazu passendes dm berechnen kann, um eine gültige Unterschrift ohne die Kenntnis eines geeigneten φ(Nm) zu erzeugen. Es ist zu beachten, daß
dm = 1 + Kφ(Nm)/e
φ(Nm) = φ(N).φ(Nmv).
Obwohl φ(Nmv) durch einen Fälscher durch Auswählen seines eigenen Nmv bestimmt werden kann, erfordert die Berechnung von φ(N) die Kenntnis von P und Q. Diese Werte sind nur der Stammstelle bekannt und werden geheimgehalten. Vorausgesetzt, daß die Geheimhaltung von P und Q aufrechterhalten werden kann, kann ein Fälscher abgewehrt werden.
Zum Schutz gegen eine zufällige Offenbarung eines φ(Nmi) eines Mitglieds kann als weitere Sicherung die Stammstelle oder die Gruppe entscheiden, daß die Nmv-Werte aller Gruppenmitglieder veröffentlicht oder einfach verfügbar gemacht werden, wodurch die Verwendung von betrügerischen Nmv-Werten ausgeschlossen wird.
Auch kann sich ein Mitglied nicht als ein anderes Mitglied ausgeben, da ein korrektes dm die Kenntnis von φ(Nmi) erfordert und es nicht möglich ist, das φ(Nmi) eines anderen Mitglieds zu bestimmen ohne Kenntnis von φ(N) und der R- und S-Werte des Mitglieds. Alle diese Werte werden durch die Stammstelle geheimgehalten.
Somit wird aufgrund der vorliegenden Erfindung jedes Gruppenmitglied vor anderen Mitgliedern geschützt, es kann jedoch sowohl sich selbst spezifisch beweisen als auch seine Mitgliedschaft der Gruppe im allgemeinen. Auch die Gruppenstammstelle kann sich nicht als ein anderes Mitglied maskieren.
Die Erfindung ist somit geeignet in Umgebungen, wie eine internationale Institution für Vorgangskarten, die viele tausende von Kartenausgabemitgliedern haben kann. Jeder dieser Kartenausgeber kann sich selbst gegen Fälschung seiner Karten ohne die Notwendigkeit sichern, zuvor die für die Erstellung der Authentizität erforderliche Information seiner Karten für verschiedene Authentizitätsprüfer, wie Karten akzeptierende Kaufleute, zu veröffentlichen. Der Kartenannehmer benötigt nur die vorherige Kenntnis der globalen Werte N und e der Institution, um sehr einfach die Authentizität der Karte zu bestimmen. Die Karte würde es nur erfordern, daß sie, wie erforderlich, die Mitgliedsvariante Nmv und einen Wert trägt, von dem festgestellt werden kann, daß er unter Verwendung des spezifischen geheimen Schlüssels dm des Mitglieds erzeugt wurde. Der Kartenannehmer könnte dann diesen Wert unsigniert machen und mit einem bekannten Wert vergleichen, der für diese Karte oder diesen Vorgang geeignet ist.

Claims

1. Ein Verfahren zum Diversifizieren eines Schlüsselpaares zur Verwendung bei der Verschlüsselung mittels öffentlichem Schlüssel durch eine anfragende Stelle mit dem Schritt Erzeugen bei einer übergeordneten Stelle eines öffentlichen Schlüssels N, e, wobei modul N das Produkt einer ersten und zweiten Primzahl P, Q und e ein entsprechender ganzzahliger öffentlicher Schlüssel ist, gekennzeichnet durch die Schritte: Auswählen einer dritten und vierten Primzahl R, S und Übertragen zur anfordernden Stelle eines ersten Wertes Nmi und eines zweiten Wertes φ(Nmi), wobei der erste Nmi = N.R.S und wobei der zweite Wert φ(Nmi) = φ(N).(R-1).(S-1) ist, wobei das Symbol φ die Euler'sche Totientenfunktion darstellt; Auswählen bei der anfordernden Stelle einer fünften und sechsten Primzahl T, U; und Berechnen bei der anfordernden Stelle eines dritten Wertes Nm und eines vierten Wertes dm, wobei Nm = Nmi.T.U und wobei

dm= 1+Kφ(Nm)/e

wobei

φ(Nm) = φ(Nmi).(T-1).(U-1)

und wobei K und dm ganze Zahlen sind, so daß dm geeignet ist, von der anfordernden Stelle als das Geheimschlüsselgegenstück des öffentlichen Schlüsselwertes e bezüglich modul Nm verwendet zu werden.

2. Verfahren nach Anspruch 1, gekennzeichnet durch die Schritte: Speichern der Werte N, φ(N) und e in Speichervorrichtungen (20) bei der ersten Stelle.

3. Verfahren nach Anspruch 2, gekennzeichnet durch den Schritt Speichern einer die anfordernde Stelle identifizierenden Identifikationscodierung des ersten Wertes Nmi und des zweiten Wertes φ(Nmi) in den Speichervorrichtungen (20).

4. Verfahren nach Anspruch 3, gekennzeichnet durch den Schritt Berechnen eines fünften Wertes Nmv bei der anfordernden Stelle, wobei

Nmv = Nm/N

und Speichern des fünften Wertes in weiteren Speichervorrichtungen (20) bei der anfordernden Stelle.

5. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, daß der Wert des ganzzahligen öffentlichen Schlüssels e eine Primzahl ist.

6. Verfahren nach Anspruch 4 oder Anspruch 5, gekennzeichnet durch den Schritt Multiplizieren des Wertes Nmv mit dem Wert N, um den Wert Nm zu erhalten, dessen Verwendung mit dem Wert e die Verifizierung digitaler Unterschriften oder die Verschlüsselung von von oder zu der anfordernden Stelle gesandten Daten ermöglicht.