DE60000649T2

DE60000649T2 - Authentifizierungs- oder unterschriftsverfahren mit verringter zahl an berechnungen

Info

Publication number: DE60000649T2
Application number: DE60000649T
Authority: DE
Inventors: Marc Girault; Jean-Claude Pailles
Original assignee: France Telecom SA
Current assignee: Callahan Cellular LLC
Priority date: 1999-01-27
Filing date: 2000-01-26
Publication date: 2003-08-07
Anticipated expiration: 2020-01-27
Also published as: FR2788909B1; DE60000649D1; WO2000045549A1; JP2002536875A; CA2360953A1; ATE226773T1; EP1145483A1; USRE42517E1; JP4945026B2; FR2788909A1; US7184547B1; CA2360953C; ES2184691T3; EP1145483B1

Description

Gebiet der Technik

Die vorliegende Erfindung bezieht sich auf ein Authentifizierungs- oder Signaturverfahren mit einer reduzierten Anzahl von Berechnungen.
Die Erfindung betrifft im einzelnen das Gebiet der sogenannten Verschlüsselung mit öffentlichem Schlüssel. Bei solchen Verfahren besitzt die zu authentifizierende Einheit einen Geheimschlüssel und einen zugeordneten öffentlichen Schlüssel. Die authentifizierende Einheit braucht nur diesen öffentlichen Schlüssel, um die Authentifizierung zu vollziehen.
Die Erfindung betrifft im einzelnen auch noch das Gebiet der sogenannten Authentifizierungsverfahren mit Null-Kenntnis ("zero-knowledge") oder ohne Beisteuerung von Kenntnis. Bei dieser Art von Verfahren verläuft die Authentifizierung gemäß einem Protokoll, welches auf erprobte Art und Weise und mit Hypothesen, die von Wissenschaftlern als vollkommen vernünftig anerkannt sind, nichts über den Geheimschlüssel der zu authentifizierenden Einheit verrät.
Genauer gesagt betrifft die Erfindung Verfahren ohne Beisteuerung von Kenntnissen, die auf dem Problem der Faktorenzerlegung beruhen (d. h. auf der Schwierigkeit, große ganze Zahlen in ein Produkt aus Primzahlen zu zerlegen).
Die Erfindung findet Anwendung bei allen Systemen, die eine Authentifizierung von Einheiten oder Nachrichten benötigen oder eine Signatur der Nachrichten benötigen, und insbesondere bei Systemen, bei denen die Anzahl von ausgeführten Berechnungen pro authentifizierter Einheit einen kritischen Parameter darstellt. Vor allem bei Mikroschaltungs-Standardkarten oder billigen Karten, die mit keinem arithmetischen Co-Prozessor versehen sind (oft Kryptoprozessoren genannt), um die kryptographischen Berechnungen zu beschleunigen.
Eine typische Anwendung der Erfindung ist die elektronische Geldbörse, die ein sehr hohes Sicherheitsniveau erfordert und dabei die Verwendung eines Kryptoprozessors ausschließt, sei es aus Kostengründen oder aus technischen Gründen (beispielsweise die Verwendung einer Schnittstelle ohne Kontakt), oder aus beiden Gründen.
Eine weitere mögliche Anwendung ist die Telekarte der nächsten Generation, für welche die Kostenzwänge noch strikter sind als für die elektronische Geldbörse.

Stand der Technik

Zahlreiche Identifizierungsprotokolle des Typs ohne Beisteuerung von Kenntnissen sind bekannt. Darunter fallen beispielsweise:
- das Protokoll von FIAT-SHAMIR beschreibt in dem Artikel von A. FIAT und A. SHAMIR mit dem Titel "How to prove yourself: Practical solutions to identification and signature problems", veröffentlicht in "Advances in Cryptology: Proceedings of CRYPTO'86, Lecture Notes in Computer Science", Vol. 263, Springer-Verlag, Berlin 1987, SS. 186-194,
- das Protokoll von GUILLOU-QUISQUATER, beschrieben im Artikel von L. C. GUILLOU und J. J. QUISQUATER, mit dem Titel "A practical zero-knowledge protocole fitted to security microprocessors minimizing both transmission and memory", veröffentlicht in "Advances in Cryptology: Proceedings of EUROCRYPT'88, Lecture Notes in Computer Science", Vol. 330, Springer-Verlag, Berlin, 1988, SS. 123-128,
- das Protokoll von GIRAULT, das in der französischen Patentanmeldung FR-A-2 716 058 beschrieben ist und auf dem sogenannten Problem des diskreten Logarithmus beruht.
Allgemein gesehen laufen die meisten Identifizierungsprotokolle (oder Nachrichten-Authentifizierungsprotokolle) mit Null-Kenntnis-Beisteuerung in drei Austauschvorgängen ab. Um die Beschreibung zu vereinfachen, geht man davon aus, daß die authentifizierende Einheit B bereits alle charakteristischen öffentlichen Parameter der zu authentifizierenden Einheit kennt, d. h. ihre Identität, ihren öffentlichen Schlüssel etc.
Während des ersten Austauschs liefert A an B einen Wert c, "Verbindlichkeit" oder "Zusage" ("engagement") genannt, ein Abbild über eine pseudo-zufällige Funktion h eines Parameters x (der selbst anhand einer zufällig von A gewählten Zahl r berechnet wird), sowie gegebenenfalls der zu authentifizierenden oder zu signierenden Nachricht: c = h (x, [M]), wobei der Begriff [M] ausdrückt, daß M optional ist. Dies ist der erste Schritt. In gewissen Protokollen kann es mehrere Verbindlichkeiten bzw. Zusagen geben.
Bei einem zweiten Austausch schickt B an A einen Parameter e, der zufällig ausgewählt ist (die "Frage"), Dies ist der zweite Schritt.
Während des dritten Austauschs liefert A an B eine "Antwort", und kohärent mit der Frage e die Verbindlichkeit c und den Geheimschlüssel v von A (dritter Schritt).
Schließlich kontrolliert B die empfangene Antwort. Genauer gesagt berechnet B x anhand der Elemente y, e und v durch x = φ (y/ e, v); schließlich prüft er, daß:
c = h (φ(v, e, y), [M]) (vierter Schritt).
Wenn es keine zu authentifizierende Nachricht gibt, ist der Rückgriff auf die pseudo-zufällige Funktion h optional. Dabei kann c = x genommen werden. Die Prüfung besteht dabei, nachzuprüfen, ab x = φ(y, e, v).
In bestimmten Protokollen gibt es einen oder zwei zusätzliche Austausche zwischen den zu authentifizierenden und authentifizierenden Einheiten.
Im Fall einer Nachrichtensignatur werden die zwei ersten Austausche unterdrückt, da der Parameter e gleich c gewählt wird; A berechnet dabei nacheinander - und nur - c, e(= c) und y.
Die Zahl u von möglichen Fragen ist direkt mit dem Sicherheitsniveau des Protokolls verknüpft. Letzteres ist definiert als die Wahrscheinlichkeit p der Erfassung eines Betrügers (d. h. einer Einheit C, die auf betrügerische Art und Weise versucht, sich als A auszugeben), und ist durch einen Parameter k gekennzeichnet. Die Zahlen p und k sind durch die Gleichung verbunden: p = 1 - 2-k. Mit anderen Worten hat der Betrüger nur eine von 2-k Chancen auf Erfolg seines Betrugversuchs. Im vorliegenden Fall kann nachgewiesen werden, daß, wenn das Protokoll auf einem schwierigen mathematischen Problem beruht und die Zusagen bzw. Verbindlichkeiten eine ausreichende Länge aufweisen, es genügt, daß die Länge von u gleich k Bits ist. Typischerweise ist k gleich 32 Bits, was eine Chance unter vier Milliarden ergibt, mit dem Betrug Erfolg zu haben. Bei den Anwendungen, bei denen das Fehlschlagen einer Identifizierung sehr ernste Folgen haben kann (z. B. gerichtliche Verfolgung), kann diese Länge auf einige Bits reduziert werden.
In den auf der Zerlegung in Faktoren basierenden Protokollen impliziert bzw. implizieren die Berechnung von x anhand von r oder die Berechnung von y anhand von e oder beide Operationen modulo n, wobei n eine schwer in Faktoren zu zerlegende zusammengesetzte Zahl ist. Diese Zahl ist von universeller Art, d. h. von einer dritten Vertrauensinstanz generiert, gespeichert und von allen Einheiten, die daran angeschlossen sind, verwendet. Der universelle Charakter von n impliziert, daß sie sehr groß ist (typischerweise 1024 Bits), da die Entdeckung der Faktorisierung von n die Geheimschlüssel aller Anwender bzw. Benutzer kompromittieren würde.
In ihrer Basisversion kann keines der oben genannten Protokolle in einer starken Zwangen unterworfenen Anwendung eingesetzt werden (geringe Kosten, geringe Komplexität), wie sie in dem vorangehenden Abschnitt beschrieben wurden, da die erforderlichen Berechnungen von keiner Mikroschaltungskarte ausgeführt werden könnten, die nicht mit einem Kryptoprozessor ausgestattet ist.
Die französische Patentanmeldung FR-A-2 752 122 beschreibt eine Optimierung dieser Protokolle, diese Optimierung bleibt jedoch auf Protokolle beschränkt, die auf dem Geheimlogarithmus in einem sogenannten "Vorberechnungs"- Modus basieren, der den Nachteil hat, Wiederaufladungen in regelmäßigen Abständen zu implizieren.
Das Dokument von J. BRANDT et al. mit dem Titel "Zeroknowledge Authentication Scheme with Secret Key Exchange" veröffentlicht in "Advances in Cryptology-Crypto 88 Proceedings, XP 000090662, Seiten 583-588, beschreibt ein Authentifizierungsschema ohne Beisteuerung von Kenntnissen, mit einem Austausch eines Geheimschlüssels zwischen zwei Benutzern, wobei in diesem Schema die zu authentifizierende Einheit ihr eigenes Modul n = pq berechnet und eine Operation des Typs md (mod n) anwendet.
Die vorliegende Erfindung zielt darauf ab, die Anzahl von Berechnungen zu verringern, die von der authentifizierten Einheit in den Identifizierungsprotokollen (oder Nachrichten- Authentifizierungs- oder Signaturprotokollen) ohne Beisteuerung von Kenntnissen auf der Basis der Faktorisierung ausgeführt werden, wobei diese Verringerung einen Faktor 2 oder 3 im Rahmen einer bestimmten Operation des Typs v = s-t (mod n) erreichen kann.
Sie ermöglicht auf diese Weise, und insbesondere, wenn man sie mit dem Guillou-Quisquater-Protokoll koppelt, die schnelle Ausführung eines Identifizierungsalgorithmus (oder einer Nachrichten-Authentifizierung oder -Signatur) mit öffentlichem Schlüssel in einer billigen Standard- Mikroschaltungskarte für Anwendungen wie z. B. die elektronische Geldbörse oder die Telekarte der nächsten Generation.

Abriß der Erfindung

Da das Modul n ein Parameter von individuellem Typ ist (mit anderen Worten besitzt jeder Anwender seinen eigenen Wert von n), kann man diese Wahl auf die beiden folgenden Weisen (die übrigens vorteilhafterweise kombiniert werden können) verwerten:
1) Zunächst durch Wahl einer Größe von n, die unter dem üblichen Wert liegt (typischerweise unter 1000 und beispielsweise zwischen 700 und 800); dies ist möglich, da die Entdeckung der Faktorisierung von n nur den Geheimschlüssel des entsprechenden Anwenders und keineswegs denjenigen der anderen Anwender kompromittiert; diese einzige Modifikation ermöglicht schon eine Reduktion von etwa. 40% der Dauer der ausgeführten modulo-n-Berechnungen;
2) wenn der Anwender die Primfaktoren von n in dem Speicher seiner Sicherheitsvorrichtung aufbewahrt hat, kann man die sogenannte Technik der chinesischen Reste anwenden, um die Dauer der ausgeführten modulo-n-Berechnungen, nochmals um etwa 40% zu reduzieren, wenn die Anzahl der Primfaktoren 2 beträgt; diese Reduktion kann noch verstärkt werden, indem mehrere Primfaktoren (typischerweise 3 oder 4) verwendet werden.
Insgesamt können also die modulo-n-Berechnungszeiten auf mindestens 60% verringert werden, d. h. um mindestens einen Faktor 2.
Aufgabe der Erfindung ist im einzelnen ein Authentifizierungsverfahren, welche eines erste sogenannte "zu identifizierende" Einheit, welche einen öffentlichen Schlüssel v und einen Geheimschlüssel s besitzt, wobei diese Schlüssel durch eine Operation modulo-n verknüpft sind, wobei n eine Modul genannte ganze Zahl ist, die der zu authentifizierenden Einheit eigen ist, sowie eine zweite, sogenannte "authentifizierende" Einheit besitzt, die den öffentlichen Schlüssel v kennt, wobei diese Einheiten Mittel umfassen, die Informationen des Typs vom Null-Kenntnis- Beitrag austauschen können und kryptographische Berechnungen zu diesen Informationen ausführen können, wobei bestimmte Berechnungen modulo-n ausgeführt werden, wobei dieses Verfahren dadurch gekennzeichnet ist, daß das Operationsmodul modulo-n vom Typ v = s-t (mod n) ist, und wobei t ein Parameter ist.
Die in Frage kommenden Einheiten können beispielsweise Mikroschaltungskarten, elektronische Geldbörsen, Telekarten etc. sein.
In einem vorteilhaften Anwendungsmodus sind die Informationsaustausche des Typs mit Null-Kenntnis-Beitrag und die kryptographischen Berechnungen die folgenden:
- Die zu identifizierende Einheit wählt zufällig eine ganze Zahl bzw. eine der ganzen Zahlen r, die zwischen 1 und n-1 liegen, und berechnet einen (der) Parameter (x) gleich rt (mod n), und dann eine Zahl bzw. eine der Zahlen c, die Zusage(n) bzw. Verbindlichkeit(en) genannt wird/werden, und eine (der) Funktion(en) dieser/dieses Parameter(s) und eventuell einer Nachricht (M) ist/sind, und schickt diese Zusage(n) bzw. Verbindlichkeit (en) an die authentifizierende Einheit;
- die identifizierende Einheit empfängt die Verbindlichkeit(en) c, wählt zufällig eine Zahl e, "Frage" genannt, und sendet diese Frage der zu identifizierenden Einheit;
- die zu identifizierende Einheit empfängt die Frage e, führt eine bzw. eine der Berechnungen unter Verwendung dieser Frage e und des Geheimschlüssels s aus, wobei das Ergebnis dieser Berechnung(en) eine (der) Antwort(en) y darstellt, und sendet diese Antwort(en) der authentifizierenden Einheit;
- die authentifizierende Einheit (B) empfängt die Antwort(en) y, führt eine Berechnung unter Verwendung des öffentlichen Schlüssels v und des Moduls n aus, und überprüft durch eine Operation modulo n, ob das Ergebnis dieser Berechnung kohärent mit der/den empfangenen Verbindlichkeit(en) ist.
Die Größe der Zahl n, ausgedrückt in der Anzahl von Bits, ist kleiner als 1000. Sie kann beispielsweise zwischen 700 und 800 liegen.
Aufgabe der vorliegenden Erfindung ist auch ein Nachrichten-Signaturverfahren durch eine sogenannte "signierende" Einheit, wobei diese Einheit einen öffentlichen Schlüssel v und einen Geheimschlüssel s besitzt, wobei diese Schlüssel durch eine Operation modulo n verbunden sind, bei der n eine "Modul" genannte ganze Zahl und t ein Parameter ist, wobei im Verfahren die signierende Einheit eine Verbindlichkeit c berechnet, die insbesondere Funktion der zu signierenden Nachricht ist, sowie eine Zahl y, die eine Funktion des Geheimschlüssels ist, die Zahlen y und c, welche die Signatur der Nachricht und die Nachricht darstellen, emittiert bzw. sendet, wobei dieses Verfahren dadurch gekennzeichnet ist, daß die Operation modulo n dem Signierenden eigen ist.
In einer vorteilhaften Ausführungsform wählt der Signierende zufällig eine ganze Zahl r, die zwischen 1 und n- 1 liegt, berechnet einen Parameter x gleich rt (mod n), berechnet eine Zahl c als Funktion des Parameters x und der zu signierenden Nachricht, berechnet eine Zahl y mit Hilfe seines Geheimschlüssels s und als Funktion der Zahlen r und e und emittiert die Zahlen c und y als Signatur.

Detaillierte Beschreibung spezieller Ausführungsformen der Erfindung

In der folgenden Beschreibung wird davon ausgegangen, daß die Erfindung auf das GUILLOU-QUISQUATER-Protokoll angewandt ist, wobei es sich natürlich nur um ein Beispiel handelt und die Erfindung keineswegs auf dieses Protokoll beschränkt ist.
Es ist anzumerken, daß im GUILLOU-QUISQUATER-Protokoll die universellen Parameter das Modul n, Produkte aus Primzahlen und mit mindestens 1024 Bits, sowie eine ganze Zahl t sind.
Der öffentliche Schlüssel v und der Geheimschlüssel s sind durch die folgende Gleichung verknüpft: v = s-t (mod n).
Das gewählte Sicherheitsniveau ist u (kleiner oder gleich t, und am häufigsten u = t).
Die Authentifizierung von A durch B, die Alice bzw. Bob gemäß der gebräuchlichen Terminologie genannt werden können, läuft wie folgt ab:
1. Alice wählt r im Intervall [1, n-1], berechnet x = rt (mod n), dann c = h(x, [M]), und sendet c an Bob.
2. Bob wählt e im Intervall [0, u-1] und sendet e an Alice.
3. Alice berechnet y = rse (mod n) und sendet y an Bob.
4. Bob berechnet x = ytve (mod n) und prüft, ob c = h (x, [M]) ist.
Wenn es keine zu authentifizierende Nachricht gibt, ist der Rückgriff zu der Pseudo-Zufallsfunktion h optional: man kann c = x nehmen. Die Prüfung besteht dabei darin, zu überprüfen, ob x = ytve (modulo n) ist.
Bei dem modifizierten Protokoll gemäß der Erfindung ist der einzige universelle Parameter t.
Der öffentliche Schlüssel ist (n, v), wobei n mindestens 768 Bits aufweist. Der öffentliche Schlüssel v und der Geheimschlüssel s von Alice sind durch die Gleichung: v = s-t (mod n) verknüpft.
Der Geheimschlüssel kann auch Primfaktoren von n aufweisen, um den zweiten Aspekt der Erfindung zu nutzen.
Der Parameter t kann in den öffentlichen Schlüssel aufgenommen werden (in diesem Fall gibt es keinen universellen Parameter).
Das von Alice und Bob gewählte Sicherheitsniveau ist u (kleiner oder gleich t; häufig u = t).
Die Authentifizierung von Alice durch Bob läuft nach obiger Beschreibung ab, jedoch mit schnelleren Berechnungen Dank eines kleineren Moduls.
Da alle Berechnungen von Alice modulo n ausgeführt werden, wirkt sich der bei einer einzigen modularen Multiplikation erhaltene Verstärkungsfaktor auf die Gesamtheit der von Alice ausgeführten Berechnungen während der Ausführung des Protokolls aus. Ebenso würde es sich beispielsweise mit den Fiat-Shamir-Protokollen oder den Girault-Protokollen verhalten (in letzterem Fall kommt es zu keiner Verstärkung im Schritt 3, da keine modularen Berechnungen mehr vorkommen, die Ausführungszeit dieses Schritts ist jedoch ohnehin im Verhältnis zur modularen Exponentierung des ersten Schritts vernachlässigbar).
Die Erfindung kann auch durch die sogenannte Technik der chinesischen Reste umgesetzt werden, die darin besteht, modulo-Berechnungen jeder der n bildenden Primzahlen auszuführen. Da diese Zahlen notwendigerweise viel kleiner sind, sind diese Berechnungen schneller. Es bleibt das Ergebnis modulo n mittels einer sogenannten Wiederherstellungsoperation zu berechnen. Diese Technik ist im Artikel von J. J. QUISQUATER und C. COUVREUR mit dem Titel "Fast decipherment algorithm for RSA public-key cryptosystem", veröffentlicht in "Elecronic letters". Vol. 18, Oktober 1982, SS. 905-907 beschrieben.
Im folgenden wird der Fall in Betracht gezogen, bei dem n das Produkt zweier Primfaktoren p und q ist.
Nach dem Theorem von Bezout existieren zwei ganze Zahlen a und b, wie z. B. ap + bq = 1.
Um y = xe (mod n) zu berechnen, beginnt man mit der "Reduzierung" von x modulo jeder der Primzahlen durch Berechnen von xp = x (mod p) und xq = x (mod q). Man reduziert auch e modulo (p - 1) und (q - 1) durch Berechnung von ep = emod(p-1) und eq = emod(q-1). (Im Guillou- Quisquater-Protokoll ist e immer kleiner als p-1 und q-1, und folglich ep = eq = e).
Nun berechnet man yp = xp ep (mod p) und yq = xq eq (mod q). Wenn p und q ähnliche Größen aufweisen, ist jede dieser Berechnungen etwa 8 mal schneller als die Berechnung y = xe (mod n), wenn die Größe von e gleich der von n ist (erster Fall); 4 mal schneller, wenn sie kleiner oder gleich der von p ist (zweiter Fall wie beispielsweise im Algorithmus). Beide Berechnungen zusammengenommen sind also 4 mal schneller oder 2 mal schneller.
Es bleibt y anhand von yp und yq wiederherzustellen, was durch die folgende Operation erfolgt:
y = yp + ap (yq - yp) (mod n)
Insgesamt gesehen ermöglicht das Verfahren der chinesischen Reste eine Beschleunigung der Berechnung um einen zwischen 3 und 4 liegenden Faktor im ersten Fall und einen zwischen 1,5 und 2 liegenden Faktor im zweiten Fall. Wenn die Anzahl von Primfaktoren (ausgehend von ähnlichen Größen) über 2 und gleich k ist, liegt der Beschleunigungsfaktor nahe an k² im ersten Fall und nahe an k im zweiten Fall.

Claims

1. Authentifizierungsverfahren, das eine erste, "zu authentifizierende" Einheit (A), welche eine öffentlichen Schlüssel v und einen Geheimschlüssel s besitzt, wobei diese Schlüssel durch eine Operation modulo n verbunden sind, wobei n eine Modul genannte ganze Zahl ist, und der Modul n der zu authentifizierenden Einheit A eigen ist, sowie eine zweite, "authentifizierende" Einheit (B), welche den öffentlichen Schlüssel v kennt, verwendet, wobei diese Einheiten Einrichtungen umfassen, die Informationen vom Typ mit Null- Beitrag an Kenntnis bzw. Wissen austauschen können und auf diese Informationen gestützt, kryptographische Berechnungen ausführen können, wobei bestimmte Berechnungen modulo n ausgeführt werden, wobei dieses Verfahren dadurch gekennzeichnet ist, daß die Operation modulo n vom Typ v = s-t (mod n) ist, wobei t ein Parameter ist.

2. Verfahren nach Anspruch 1, wobei die Informationsaustausche vom Typ mit Nullbeitrag an Kenntnis bzw. Wissen und die kryptographischen Berechnungen die folgenden sind:

- Die zu authentifizierende Einheit (A) wählt zufällig eine oder mehrere ganze Zahlen r, die zwischen 1 und n-1 liegen, und berechnet einen (der) Parameter (x) gleich rt (mod n), und dann eine Zahl bzw. Zahlen c, die Zusage(n) (engagement(s)) genannt wird/werden, und eine Funktion bzw. Funktionen dieser/dieses Parameter(s) und eventuell einer Nachricht (M) ist/sind, und schickt diese Zusage(n) an die authentifizierende Einheit (B);

- die authentifizierende Einheit (B) empfängt die Zusage(n) c, wählt zufällig eine Zahl e, als "Frage" bezeichnet, und sendet diese Frage der zu authentifizierenden Einheit (A);

- die zu authentifizierende Einheit (A) empfängt die Frage e, führt eine Berechnung bzw. Berechnungen unter Verwendung dieser Frage e und des geheimen Schlüssels s aus, wobei das Ergebnis dieser Berechnung(en) eine Antwort bzw. Antworten y bildet, und sendet diese Antwort(en) der authentifizierenden Einheit (B);

- die authentifizierende Einheit (B) empfängt die Antwort(en) y, führt eine Berechnung unter Verwendung des öffentlichen Schlüssels y und des Moduls n aus, und überprüft durch eine Operation modulo n, ob das Ergebnis dieser Berechnung kohärent mit der/den empfangenen Zusage(n) ist.

3. Verfahren nach Anspruch 2, wobei die Größe der Zahl n, als Zahl der Bits ausgedrückt, unter 1000 liegt.

4. Verfahren nach Anspruch 3, wobei die Größe der Zahl n zwischen 700 und 800 liegt.

5. Verfahren nach einem der Ansprüche 1 bis 4, wobei n das Produkt aus mindestens zwei Primzahlen (p, q) ist, und wobei die Operationen modulo n mit dem sogenannten Verfahren "der chinesischen Reste" ausgeführt werden.

6. Nachrichten-Signaturverfahren durch eine sogenannte "signierende" Einheit (A), wobei diese Einheit einen öffentlichen Schlüssel v und einen geheimen Schlüssel s besitzt, wobei diese Schlüssel durch eine Operation modulo n verbunden sind, wobei n eine als "Modul" bezeichnete ganze Zahl ist, die dem Signierenden eigen ist, wobei das Verfahren Einrichtungen umfaßt, welche eine Verbindlichkeit c, die insbesondere Funktion der zu signierenden Nachricht M ist, sowie eine Zahl y, die eine Funktion des geheimen Schlüssels ist, berechnen und die Zahlen y und c, die die Signatur der Nachricht M und die Nachricht M darstellen, senden können, wobei dieses Verfahren dadurch gekennzeichnet ist, daß die Operation modulo n die Operation v = s-t (mod n) ist, wobei t ein Parameter ist.

7. Signaturverfahren nach Anspruch 6, wobei der Signierende zufällig eine ganze Zahl r wählt, die zwischen 1 und n-1 liegt, einen Parameter x gleich (mod n) berechnet, eine Zahl c als Funktion des Parameters x und der zu signierenden Nachricht M berechnet, eine Zahl y mit Hilfe seines geheimen Schlüssels s und als Funktion der Zahlen r und e berechnet und die Zahlen c und y als Signatur sendet.