DE69611605T2

DE69611605T2 - System zur sicherstellung, dass das "blinding" von geheimschlüsselzertifikaten begrenzt ist, auch wenn das vergabeprotokoll im parallelmodus ausgefürht wird

Info

Publication number: DE69611605T2
Application number: DE69611605T
Authority: DE
Inventors: Stefanus Alfonsus Brands
Original assignee: Individual
Current assignee: Individual
Priority date: 1995-03-27
Filing date: 1996-03-27
Publication date: 2001-06-13
Anticipated expiration: 2016-03-28
Also published as: US6052467A; DE69611605D1; WO1996031034A1; AU4958396A; EP0818095A1; EP0818095B1

Description

Hintergrund der Erfindung

1. Technisches Gebiet der Erfindung

Die vorliegende Erfindung bezieht sich auf kryptographische Techniken und insbesondere auf ein Verfahren zur Realisierung von Protollausgabezertifikaten, die nur begrenzt verdeckt werden können, selbst wenn die Ausgabe im parallelen Modus durchgeführt wird.

2. Beschreibung des Standes der Technik

Es können zwei Grundtypen von Zertifikaten unterschieden werden, und zwar öffentliche Schlüsselzertifikate und Geheimschlüsselzertifikate. Ein öffentliches Schlüsselzertifikat ist eine digitale Signatur eines Herausgebers, der hier als Zertifikatsinstanz bezeichnet werden soll, und zwar mit einem öffentlichen Schlüssel. Die andere Grundtype, die Geheimschlüsselzertifikate, sind in der US-A-5 606 617 beschrieben und beansprucht. Ebenso wie bei öffentlichen Schlüsselzertifikaten können Tripel, die aus einem Geheimschlüssel, einem entsprechenden öffentlichen Schlüssel und einem Geheimschlüsselzertifikat bestehen auf dem öffentlichen Schlüssel nur dadurch wiedererlangt werden, daß ein Ausgabeprotokoll in Verbindung mit der Zertifikatsinstanz benutzt wird. Der Unterschied gegenüber öffentlichen Schlüsselzertifikaten besteht darin, daß Paare, bestehend aus einem öffentlichen Schlüssel und einem Geheimschlüsselzertifikat, auf dem öffentlichen Schlüssel von jedem erzeugt werden können.
Zahlreiche Signatur-Übertragungsmechanismen erfordern eine Zertifikatsinstanz, um Tripel auszugeben, die aus einem Geheimschlüssel, einem anpassenden öffentlichen Schlüssel und einem Zertifikat der Zertifikatsinstanz auf dem öffentlichen Schlüssel bestehen. Von besonderem Interesse für private Schutzmechanismen für Signaturübertragungen sind sogenannte restriktive verdeckte Ausgabeprotokollzertifikate, in denen der Empfänger den ausgegebenen öffentlichen Schlüssel und das Zertifikat verdecken kann, aber nicht eine vorbestimmte nicht-triviale Aussage des Geheimschlüssels; dieser Teil des Geheimschlüssels wird als Verdeckungs-Invariable bezeichnet. Restriktive verdeckte Protokollausgabezertifikate und Verfahren zur Anwendung derselben bei Privatschutzmechanismen zur Wertübertragung, insbesondere bei elektronischen Off-Line-Zahlungen, sind in der US-A-5 521 980 beschrieben und beansprucht.
Die US-A-5 521 980 und die US-A-5 606 617 beschreiben und beanspruchen restriktive verdeckte Protokollausgabezertifikate für Geheimschlüsselzertifikate. Nur ein restriktives verdecktes Ausgabeprotokoll für öffentliche Schlüsselzertifikate wird in der US-A-5 521 980 beschrieben; sämtliche anderen beispielsweisen Schemen sind für die Ausgabe von Geheimschlüsselzertifikaten bestimmt. Diese Geheimschlüssel-Protokollausgabezertifikate werden als sicher angesehen, wenn sie sequenziell durchgeführt werden. Sie sollten jedoch nicht parallel laufen, wenn unterschiedliche verdeckte invariable Zahlen enthalten sind: Dies würde einen Angriff ermöglichen, mit welchem vollständige verdeckte Tripels wiedererlangt werden können. In anderen Worten ausgedrückt heißt dies, daß selbst die angenommenen verdeckten invariablen Zahlen dann verdeckt werden können.
Für Transaktionen mit hohen Anforderungen glaubt man, daß es erwünscht ist, Protokollausgabezertifikate zur Verfügung zu haben, die selbst dann sicher sind, wenn sie parallel verarbeitet werden. Dies ermöglicht auch, die Ausgabe verteilt durchzuführen, ohne daß eine Koordinierung zwischen den verteilten Ausgabeagenten erforderlich wäre. Die Erfindung beschreibt ein erfindungsgemäßes Verfahren zur Erzeugung von Protokollausgabezertifikaten, die begrenzt verdeckt sind, selbst wenn der Programmablauf des Ausgabeprotokolls parallel in bezug auf die verschiedenen verdeckten invariablen Zahlen durchgeführt wird. Das erfindungsgemäße Verfahren kann auf wenigstens alle jene Geheimschlüssel-Zertifikatsschemen angewandt werden, die in den US-A-5 521 980 und US-A-5 606 617 beschrieben sind.

Aufgaben der Erfindung

Demgemäß liegt der vorliegenden Erfindung die Aufgabe zugrunde, wirksame und sicher begrenzt verdeckte Protokollausgabezertifikate zu erzeugen, durch die ein Ausgabeteilnehmer Tripel ausgeben kann, die aus einem Geheimschlüssel, einem angepaßten öffentlichen Schlüssel und einem entsprechenden Zertifikat bestehen, derart, daß der öffentliche Schlüssel und das Zertifikat in perfekter Weise durch den Empfangsteilnehmer verdeckt werden kann, aber wenigstens ein Teil des Geheimschlüssels nicht verdeckt werden kann, wenn der Programmablauf des Protokolls parallel durchgeführt wird.
Ein weiteres Ziel der vorliegenden Erfindung besteht darin, es dem Ausgabeteilnehmer zu ermöglichen, in diesen begrenzt verdeckten Ausgabeprotokollen durch verteilte Ausgabeagenten repräsentiert zu werden, die sicher das Ausgabeprotokoll durchführen können, ohne daß eine zentrale Koordinierung zwischen den Agenten stattfindet.
Ein weiteres Ziel der vorliegenden Erfindung besteht darin, einen Zeitgebermechanismus für die Ausgabeprotokolle zu schaffen, um einen noch größeren Schutz gegen Angriffe gegen einen parallelen Programmablauf der Ausgabeprotokolle zu liefern.
Ein weiteres Ziel der Erfindung besteht darin, eine wirksame ökonomische und zweckmäßige Vorrichtung und Verfahren zu schaffen, die die weiteren Ziele der Erfindung verwirklichen.
Weitere Merkmale, Ziele und Vorteile der Erfindung ergeben sich aus der Beschreibung und den beigefügten Ansprüchen in Verbindung mit den Zeichnungen.

Kurzbeschreibung der Zeichnungen

Fig. 1 zeigt ein Flußdiagramm eines begrenzt verdeckten Geheimschlüssel-Ausgabeprotokollzertifikats für das erste bevorzugte Ausführungsbeispiel gemäß den Lehren der vorliegenden Erfindung.
Fig. 2 zeigt ein Flußdiagramm eines begrenzt verdeckten Geheimschlüssel-Ausgabeprotokollzertifikats für das zweite bevorzugte Ausführungsbeispiel gemäß den Lehren der vorliegenden Erfindung.

Zusammenfassung der Erfindung

Gemäß diesem und weiteren Zielen der Erfindung wird im folgenden eine kurze Zusammenfassung der Erfindung präsentiert. Gewisse Vereinfachungen und Auslassungen können in der folgenden Zusammenfassung vorhanden sein, die gewisse Aspekte der vorliegenden Erfindung betonen und vorstellen soll, aber nicht bezüglich des Schutzumfanges begrenzt ist. Detallierte Beschreibungen der bevorzugten Ausführungsbeispiele ermöglichen dem Fachmann, die Erfindung zu verstehen und zu benutzen, wie dies weiter unten ausgeführt wird.
Bei einem Ausgabeprotokoll für Geheimschlüsselzertifikate gibt eine Zertifikatsinstanz Tripel aus. Jedes Tripel besteht aus einem Geheimschlüssel, einem entsprechenden öffentlichen Schlüssel und einem Zertifikat der Zertifikatsinstanz auf dem öffentlichen Schlüssel. Wenn ein solches Ausgabeprotokoll begrenzt verdeckt ist, dann kann ein Empfängerteilnehmer, der ein solches Tripel abnimmt, gewährleisten, daß der öffentliche Schlüssel und das Zertifikat vollständig unbabhängig für die Ansicht der Zertifikationsinstanz sind; aber andererseits kann der Empfängerteilnehmer nicht eine bestimmte Aussage des Geheimschlüssels aufstellen, und demgemäß kann die Zertifikationsinstanz Informationen in diese Aussage des Geheimschlüssels hinein kodieren.
Bei den Geheimschlüssel-Ausgabeprotokollzertifikaten, wie sie in der US-A-5 521 980 und der US-A-5 606 617 beschrieben sind, werden die Geheimschlüssel-Ausgabeprotokollzertifikate beschrieben, die begrenzt verdeckt sind, wenn das Ausgabeprotokoll mit sequenziellem Programmablauf durchgeführt wird. Bei jedem dieser Protokolle beginnt die Zertifikationsinstanz damit, dem Empfängerteilnehmer gewisse anfängliche Informationen zu übermitteln. Danach verdeckt der Empfängerteilnehmer den öffentlichen Schlüssel und berechnet eine Kennzahl, die er an die Zertifikationsinstanz schickt. Die Zertifikationsinstanz berechnet dann eine Antwort und bildet eine logische Beziehung zwischen dem verdeckt invarianten Teil des Geheimschlüssels für den Empfängerteilnehmer und dem eigenen Geheimschlüssel und sendet die Antwort an den Empfängerteilnehmer ab. Zum Schluß verifiziert der Empfängerteilnehmer die Richtigkeit der Antwort durch Benutzung des öffentlichen Schlüssels der Zertifikationsinstanz und korrigiert die Antwort, um das verdeckte Zertifikat auf dem verdeckten öffentlichen Schlüssel zu erhalten. Die Durchführung einer derartigen sequenziellen Protokollübermittlung bedeutet, daß die Zertifikationsinstanz nur neue anfängliche Informationen für einen zweiten Programmablauf des Protokolls sendet, nachdem sie eine Kennzahl für den ersten Programmablauf des Protokolls erhalten hat. (Um ein Schlangestehen zu vermeiden, sollte die Zertifikationsinstanz auf eine Kennzahl des Empfängerteilnehmers nur antworten, wenn die Kennzahl innerhalb der gleichen vorbestimmten Zeitperiode aufgetreten ist, nachdem die anfängliche Information ausgesandt wurde.)
Obgleich die Zertifikationsinstanz Programmabläufe dieser Ausgabeprotokolle parallel zueinander durchführen kann, falls die gleiche verdeckt invariante Information benutzt wird, können diese Ausgabeprotokolle nicht generell parallel zueinander durchgeführt werden. Um es der Zertifikationsinstanz zu erlauben, Programmabläufe des Ausgabeprotokolls parallel ohne jegliche Beschränkung durchzuführen, kann das erfindungsgemäße in der Anmeldung beschriebene Verfahren benutzt werden, um diese Ausgabeprotokolle zu modifizieren. Um die anfängliche Information zu bezeichnen, die durch die Ausgabe bei dem i-ten Programmablauf dieser Ausgabeprotokolle mit ai geliefert wurde, besteht die Modifikation darin, stattdessen f(ai) aussenden zu lassen. Hier ist f( ) eine Funktion, für die leicht f(ab) aus f(a) und b berechnet werden kann, wobei es jedoch im wesentlichen undurchführbar ist, die algebraischen Beziehungen, wie z. B. f(ab) oder f(a³b&sup5;) aus f(a) und f(b) zu berechnen. Da a und b aus einigen mathematischen Gruppen erzeugt werden, beispeilsweise der multiplikativen Gruppe von ganzzahligen Modulen einer großen Primzahl p oder der multiplikativen Gruppe *n eines ganzzahligen Moduls einer Zusammensetzung n, die das Produkt von wenigstens zwei großen Primzahlen ist, muß das Produkt ab in f(ab) das Gruppenprodukt sein. Ein spezielles Ausführungsbeispiel für f( ), das in der detaillierten Beschreibung erläutert wird, nimmt f(a) als gleich Fa an, wobei F ein Element einer geeigneten Gruppe ist, in der es unmöglich ist, diskrete Logarithmen zu berechnen, und derart, daß die Größenordnung von F in jener Gruppe gleich ist dem Modul der Gruppe, in der a liegt.
Bei dem ersten Ausführungsbeispiel, das in der detallierten Beschreibung erläutert wird, ist a ein Element von *p, die multiplikative Gruppe von ganzzahligen Moduln ist eine Primzahl p und F wird entsprechend so gewählt, daß es ein Element der Ordnung p in einer gewissen multiplikativen Gruppe ist, deren Ordnung ein Vielfaches von p ist und in der es im wesentlichen nicht möglich ist, diskrete Logarithmen der Basis F zu berechnen. Es ist ersichtlich, daß für a,b in *p es leicht ist, Fab mod P aus Fa und b zu berechnen, indem Fa auf die Potenz b angehoben wird. Jedoch scheinen Berechnungsformen wie Fiat mod P aus Fa und Fb die Möglichkeit zu erfordern, ein vermutlich sehr hartes Problem zu lösen, welches auf diesem Gebiet der Technik als Diffie- Hellman-Problem bekannt ist. Wenn die Zertifikationsinstanz in dem modifizierten Ausgabeprotokoll die Empfängerteilnehmer auffordert, schnell auf die anfängliche Information zu antworten, dann scheint diese Aufgabe besonders schwierig zu lösen zu sein.
Bei dem zweiten Ausführungsbeispiel, das in der detallierten Beschreibung erläutert wird, ist a ein Element von *n und die multiplikative Gruppe des ganzzahligen Moduls ist ein zusammengesetztes Modul n. Wie bei dem ersten Ausführungsbeispiel wird F als Element der Ordnung n in gewissen multiplikativen Gruppen angenommen, deren Ordnung ein Mehrfaches von n ist, und wobei es schwierig ist, diskrete Logarithmen mit der Basis F zu berechnen.
Zusammenfassend beschreibt die vorliegende Erfindung ein Verfahren zur Verhinderung von Angriffen, die algebraische Beziehungen zwischen der anfänglichen Information aufdecken, die von der Zertifikationsinstanz in parallelen Programmabläufen von begrenzt verdeckten Ausgabeprotokollzertifikaten geliefert wurden.

Detaillierte Beschreibung der Erfindung

Es wird angenommen, daß die Angaben gemäß Fig. 1 und 2 für den Fachmann klar sind, jedoch soll zur Überprüfung zunächst eine Definition getroffen werden.
Die Flußdiagramme beschreiben beschränkt verdeckte Ausgabeprotokolle für Geheimschlüsselzertifikate. Die Aktionen, die durch die partizipierenden Teilnehmer bei diesen Ausgabeprotokollen durchgeführt werden, sind in Flußdiagramm-Kästchen gruppiert. Jener Teilnehmer, der die in einem Flußdiagramm-Kästchen beschriebenen Aktionen durchführt, wird durch die Reihe angezeigt, in der das Kästchen sich befindet. Die Reihen sind durch ein Symbol gekennzeichnet, welches die Type des Teilnehmers bezeichnet. Der Ausdruck "Teilnehmer" wird benutzt, um ein Wesen anzugeben, das eine Kontrolle über wenigstens die Geheimhaltung einiger Informationen verfügt. Es wird vorausgesetzt, daß die Mehrzahl der Menschen sämtlich jeden Schlüssel oder einen Teil des Schlüssels kennen, und daß sie kollektiv als ein "Teilnehmer" betrachtet werden können. In anderen Fällen kann ein Schlüssel im wesentlichen für die Leute unbekannt sein und in einer gewissen physikalischen Vorrichtung liegen und die Vorrichtung selbst oder jene, die sie von Zeit zu Zeit steuern, können als "Teilnehmer" betrachtet werden. Demgemäß können die Teilnehmer, die durch einzelne Kästchen oder kollektive Kästchen dargestellt sind, gelegentlich als Agenten betrachtet werden, die einen Schritt oder eine Kollektion von Schritten in einem Protokoll durchführen. Sie können ebenfalls als Mittel betrachtet werden, um jene Schritte durchzuführen, und sie können aus jeder geeigneten Konfiguration digitaler Logikkreise zusammengesetzt sein. Beispielsweise könnte jedes Kästchen oder jede Kollektion von Kästchen der Figuren durch Hardware und zugeeignete kombinatorische Logik oder durch gewisse geeignet programmierte Maschinen, beispielsweise einen Prozessor, realisiert werden, wie dies auf dem technischen Gebiet üblich ist, und zwar so lange, wie es möglich ist, um die Speicherung, Eingang/Ausgang und Übertragungsschritte durchzuführen, wie dies durch die entsprechenden Kästchen beschrieben ist (möglicherweise unabhängig von zufälligen Quellfunktionen).
Wie es auf diesem Gebiet bekannt ist, bezeichnet für jede ganze Zahl l das Symbol l die Gruppe von Ziffern {0, ..., l - 1}. Eine Addition und Multiplikation der Elemente in l werden im Modul l definiert. In gleicher Weise bezeichnet das Symbol *l die Gruppe von Zahlen in {0, ..., l - 1}, die Primzahlen für l sind. Eine Multiplikation von Elementen von *l ist definiert als Modul l. l wird als Ring von ganzzahligen Moduln l bezeichnet und l wird als multiplikative Gruppe von ganzahligen Moduln l bezeichnet.
Falls ein Element von einem Ring oder einer Gruppe ausgewählt wird, wird implizit angenommen, daß dies der kleinste positive Vertreter ist. Das gleiche gilt für die Ergebnisse von Berechnungen.
Das Symbol "←" bezeichnet eine Zuordnung, was bedeutet, daß die Variable oder das Symbol auf der linken Seite dem Wert auf der rechten Seite zugeordnet wird. Die Zuordnungen bedeuten nicht notwendigerweise, daß Speicherraum tatsächlich reserviert werden muß, und sie können Zwischenwerte anzeigen, die in einem flüchtigen Speicher manipuliert werden.
Ein weiterer Arbeitsgang ist ein Gleichheitstest, und dieser wird durch das -Symbol angezeigt. Wie auf diesem Gebiet üblich, bricht das Protokoll ab, falls eine Gleichheit nicht Besteht. Das Symbol R zeigt die Zahl oder jede der Zahlen auf der linken Seite an, die aus dem Ring oder aus der Gruppe auf der rechten Seite gemäß einer gleichförmigen Wahrscheinlichkeitsverteilung und unabhängig von irgendetwas sonst ausgewählt wurden. In der Praxis können pseudozufällige Techniken benutzt werden, und die Abweichung von der gleichförmigen Verteilung kann beträchtlich sein, ohne einen beträchtlichen Verlust an Sicherheit zu bewirken.
Eine weitere Wirkung wird durch das Wort "Send" bezeichnet, gefolgt durch einen Doppelpunkt und eine Zahl. Dies zeigt an, daß die Zahlen durch jenen Teilnehmer gesendet werden, der die Aktionen durchführt, die in den Kästchen beschrieben sind, und diese dem anderen Teilnehmer übermittelt, der an dem Protokoll teilnimmt. Die gerichteten Verbindungen zwischen den Kästchen zeigen die Ordnung an, in denen die Wirkungen, die in den Kästchen gruppiert sind, durchgeführt werden.
Die Zertifikatsinstanz wird im folgenden als CA abgekürzt und der Empfängerteilnehmer mit . Bei beiden bevorzugten Ausführungsbeispielen, die im folgenden beschrieben werden, sind beispielsweise Geheimschlüsselzertifikate und entsprechende begrenzt verdeckte Ausgabeprotokolle Modifikationen der Geheimschlüssel-Zertifikatsschemen, die in der US-A-5 606 617 beschrieben sind. Da die erfindungsgemäße Technik für diese Modifikationen auf alle Geheimschlüssel-Zertifikatsschemen zutrifft, die in der US-A-5 606 617 beschrieben sind, wird nur eine beispielsweise ausgewählte detallierte Beschreibung für jedes der bevorzugten Ausführungsbeispiele beschrieben.
Dabei ist zu berücksichten, daß die Ausführungsbeispiele lediglich suggestiv und in keiner Weise beschränkend angesehen werden sollen. Es wird angenommen, daß der Fachmann in der Lage ist, die erfindungsgemäße Modifikationstechnik direkt auf andere Zertifikatsschemen zu übertragen.

Erstes bevorzugtes Ausführungsbeispiel

Nunmehr wird als Beispiel ein Geheimschlüsselzertifikat im ersten bevorzugten Ausführungsbeispiel im einzelnen beschrieben. Die Beschreibung zeigt die erfindungsgemäße Modifikationstechnik, die auf das erste beispielshafte Geheimschlüssel- Zertifikatsschema des ersten bevorzugten Ausführungsbeispiels der US-A-5 606 617 angewandt wurde.
Der Geheimschlüssel der CA ist ein Paar (x&sub0;, y) in q x q, wobei q eine Primzahl ist. Der entsprechende öffentliche Schlüssel der CA ist (p, g, h&sub0;, g&sub1;, M, F), wobei: p ist eine Primzahl, derart, daß q p - 1 gleichmässig teilt; g ist ein Element der Ordnung q in der Gruppe *p; h&sub0; ist gleich gx0 mod p; g&sub1; ist gleich gy mod p; M ist eine Zahl derart, daß p die Ordnung von *M gleichmäßig teilt; und F ist ein Element der Ordnung p in *M. M ist vorzugsweise eine Primzahl, obgleich sie auch zusammengesetzt sein kann, solange es unmöglich erscheint, diskrete Logarithmen auf der Basis F in *M zu berechnen. Hierbei ist zu bemerken, daß diese Konstruktion gewährleistet, daß in Berechnungen, wie beispielsweise Fab mod M die Berechnung im Exponenten als Modul p durchgeführt wird. Tatsächlich kann eine Berechnung wie Fgr mod M dadurch durchgeführt werden, daß erst gr mod p berechnet wird und daß dann F Modul M auf das Ergebnis von gr mod p angehoben wird.
Die CA macht außerdem öffentlich bekannt eine Hash-Funktion ( ), die ihre Argumente auf &sub2;l für einige geeignete Sicherheitsparameter l überträgt, und dies ist im wesentlichen unmöglich zu invertieren. Vorzugsweise ist ( ) kollisionsfrei, was bedeutet, daß es unmöglich ist, zwei bestimmte Argumente zu berechnen, die durch ( ) auf denselben Ausgang übertragen wurden.
Ein Geheimschlüsselzertifikat auf einem öffentlichen Schlüssel h in *p Von ist ein Paar (c, r) in &sub2;l · q derart, daß c gleich (h,Fgr(h&sub0;h)·c mod M) ist. (Es ist für den Fachmann klar, daß das Geheimschlüsselzertifikat alternativ als ein Paar (a, r) in *M · q angenommen werden kann. In jenem Fall ist das Paar ein Geheimschlüsselzertifikat auf h, wenn Fgr(h&sub0;h)·c mod M gleich a ist, und wenn c als (h,a) berechnet ist. Ausserdem kann man in jenem Fall a durch einige Ein-Wege-Hash- Kodierungen von a ersetzen, um die Länge des Zertifikats zu kürzen).
Nunmehr wird auf Fig. 1 Bezug genommen. Ein Flußdiagramm eines begrenzt verdeckten Ausgabeprotokolls für diese Geheimschlüsselzertifikate wird nun im einzelnen beschrieben.
Ein Geheimschlüssel von ist ein Paar (x, I) in q · q derart, daß gxg mod p gleich h ist. Die zweite Zahl dieses Paares I wird durch CA in den Geheimschlüssel von während des begrenzt verdeckten Ausgabeprotokollzertifikats kodiert; I mod q ist der verdeckt invariable Teil des Geheimschlüssels. Er kann nicht verdeckt werden, selbst wenn die CA-Programmabläufe des Ausgabeprotokolls parallel für bestimmte verdeckte invariable Zahlen verlaufen.
Das Kästchen 11 zeigt zuerst die Erzeugung einer Zufallszahl w&sub0; durch die CA in q. Die zweite Zeile zeigt die CA-Berechnung Fgw0 mod M, die für eine weitere Bezugnahme mit a&sub0; bezeichnet wird. Wie in der dritten Zeile beschrieben, überträgt die CA dann a&sub0; auf .
Das Kästchen 12 zeigt zunächst, wie eine Zahl x in q erzeugt. Das Paar (x, I) ist der Geheimschlüssel. Die zweite Zeile zeigt, wie den entsprechenden öffentlichen Schlüssel h berechnet, indem es gleich gxg mod p gesetzt wird. Zusätzlich erzeugt , wie in der dritten Zeile dargestellt, zwei Zufallszahlen t, u in q, die dazu dienen, verdeckte r und c zu erzeugen. Die vierte Zeile zeigt, wie a (h&sub0;g )u mod M berechnet, und dies wird für eine weitere Bezugnahme als a bezeichnet. Wie in der fünften Zeile angegeben, berechnet dann (h, a), was mit c bezeichnet ist. Die sechste Zeile zeigt, wie c + u mod q berechnet, und dies wird als c&sub0; bezeichnet. Wie in der siebenten Zeile dargestellt, überträgt dann c&sub0; auf die CA.
Das Kästchen 13 zeigt, wie die CA c&sub0; (x&sub0; + yI) + w&sub0; mod q berechnet, und dies wird zur weiteren Bezugnahme als r&sub0; bezeichnet. Wie in der zweiten Zeile beschrieben, überträgt die CA dann r&sub0; auf .
Das Kästchen 14 zeigt zunächst, wie verifiziert, ob Fgr0(h&sub0;g )-c0 mod M gleich a&sub0; ist. Wie in der zweiten Zeile beschrieben: wenn dies der Fall ist, dann berechnet r&sub0; + cx + t mod q, und dies wird mit r bezeichnet.
Der Fachmann kann leicht verifizieren, daß das Paar (c, r) ein Geheimschlüsselzertifikat auf dem öffentlichen Schlüssel h von ist, derart, daß weiß, daß der Geheimschlüssel (x, I) h entspricht. Dieses Ausgabeprotokoll-Zertifikat wird als begrenzt verdeckt betrachtet, wobei die verdeckte invariante Zahl I mod q ist, selbst wenn die von der CA durchgeführten Programmabläufe des Protokolls für unterschiedliche verdeckte invariante Zahlen parallel durchgeführt werden.
Um Angriffe auf parallele Programmabläufe dieses Ausgabeprotokolls noch schwieriger zu gestalten, kann der folgende Zeitgebermechanismus eingebaut werden. Die CA bestimmt ursprünglich einige geeignete Zeitbegrenzungen (die sich pro Programmablauf des Ausgabeprotokolls oder pro Empfängerteilnehmer ändern). Wenn die Zeitverzögerung zwischen Aussendung der Zahl a&sub0; nach wie in Kästchen 11 dargestellt und Empfang der Anforderung c&sub0; von wie in Kästchen 12 dargestellt, diese Zeitbegrenzung überschreitet, dann liefert die CA keine Antwort r&sub0;. Die CA kann diese Verzögerung durch einen genügend genauen Taktgeber bestimmen. Wenn dann keine Anforderung zeitgerecht erfolgt, bedeutet dies, daß die Empfängerteilnehmer erneut einen weiteren Programmablauf des Ausgabeprotokolls durchführen müssen.

Zweites bevorzugtes Ausführungsbeispiel

Ein beispielweises Geheimschlüsselzertifikat bei dem zweiten bevorzugten Ausführungsbeispiel wird nunmehr im einzelnen beschrieben. Diese Beschreibung zeigt die erfindungsgemäße Modifikationstechnik, die auf das erste exemplarische Geheimschlüssel-Zertifikatsschema des zweiten bevorzugten Ausführungsbeispiels von US-A-5 606 617 angewandt wird.
Der Geheimschlüssel der CA ist ein Paar (x&sub0;, y) in *n · *n, wobei n das Produkt von zwei bestimmten Primzahlen ist. (Stattdessen kann die Primzahlfaktorisierung von n als Geheimschlüssel dienen.) Der entsprechende öffentliche Schlüssel von CA ist (n, v, h&sub0;, g&sub1;, M, F), wobei: v ist ein Element in *n zur Verdeutlichung und ohne Verlust einer Allgemeingültigkeit, die bestimmt, daß es eine Primzahl ist, welche eine Primzahl der Zahl von Elementen φ (n) in *n ist; h&sub0; ist gleich x mod n; g&sub1; ist gleich yv mod n; M ist eine derartige Zahl, daß n die Ordnung von *M gleichmäßig teilt; und F ist ein Element der Ordnung n in *M · M ist vorzugsweise eine Primzahl, obgleich es in gleicher Weise als Zusammensetzung benutzt werden kann, solange es unmöglich erscheint, diskrete Logarithmen der Basis F in *M zu berechnen.
Die CA macht öffentlich eine vorzugsweise kollisionsfreie Ein-Weg-Hash-Funktion ( ) bekannt, die ihre Argumente auf &sub2;l für einige geeignete Sicherheitsparameter l überträgt.
Ein Geheimschlüsselzertifikat auf einem öffentlichen Schlüssel h in *n von ist ein Paar (c, r) in *&sub2;l · *n derart, daß c gleich (h,Frv(h&sub0;h)·-c mod M)ist. (Das Geheimschlüsselzertifikat kann stattdessen auch von einem Paar (a, r) in *M · *n gebildet werden. In diesem Fall ist das Paar ein Geheimschlüsselzertifikat von h, wenn Frv(h&sub0;h)·-c gleich a ist, wobei c als (h, a) berechnet wird. Außerdem kann man in diesem Falle a durch einige Ein-Weg-Hash-Funktionen von a ersetzen, um die Länge des Zertifikats zu verringern).
In Verbindung mit Fig. 2 wird ein Flußdiagramm eines begrenzt verdeckten Ausgabeprotokolls für diese Geheimschlüsselzertifikate im einzelnen beschrieben.
Ein Geheimschlüssel von ist ein Paar (x, I) in *n · v derart, daß xvg mod n gleich h ist. Die zweite Zahl dieses Paares I wird nunmehr durch die CA zu einem Geheimschlüssel von während des begrenzt verdeckten Ausgabeprotokollzertifikats kodiert; I mod v ist der verdeckt invariante Teil des Geheimschlüssels. Er kann nicht verdeckt werden, selbst wenn die CA-Programmabläufe des Ausgabeprotokolls parallel für bestimmte verdeckt invariante Zahlen verlaufen.
Das Kästchen 21 zeigt zunächst, wie die CA zufallsbedingt eine Zahl w&sub0; in *n erzeugt. Die zweite Zeile zeigt, wie die CA Fw mod M berechnet, was als a&sub0; zur weiteren Bezugnahme bezeichnet wird. Wie in der dritten Zeile beschrieben, überträgt die CA dann a&sub0; nach .
Das Kästchen 22 zeigt zunächst, wie eine Zahl x in *n erzeugt; das Paar (x, I) wird sein Geheimschlüssel. Die zweite Zeile zeigt, wie den entsprechenden öffentlichen Schlüssel h berechnet, indem dieser gleich xvg mod n gesetzt wird. Zusätzlich erzeugt, wie in der dritten und vierten Zeile dargestellt, zwei Zufallszahlen t in *n und u in v. Diese dienen dazu, um verdeckte Werte r und c zu erhalten. Die fünfte Zeile zeigt, wie a (h&sub0;h )u mod M berechnet, und dies wird zur weiteren Bezugnahme mit a bezeichnet. Wie in der sechsten Zeile angegeben, berechnet dann (h, a), was mit c bezeichnet wird. Die siebente Zeile zeigt, wie c + u mod v berechnet, und dies wird mit c&sub0; bezeichnet. Wie in der achten Zeile beschrieben, überträgt dann c&sub0; auf CA.
Das Kästchen 23 zeigt zuerst, wie die CA (x&sub0;yI)c0w&sub0; mod n berechnet, und dies wird mit r&sub0; zur weiteren Bezugnahme bezeichnet. Wie in der zweiten Zeile beschrieben, überträgt dann die CA r&sub0; auf .
Das Kästchen 24 zeigt zuerst, wie verifiziert, ob Fr (h&sub0;g )-c0 mod M gleich a&sub0; ist. Wie in der zweiten Zeile beschrieben, berechnet r&sub0;xct(h&sub0;g )c+u div v mod n, wenn dies der Fall ist. Dies wird mit r bezeichnet.
Wie der Fachmann leicht feststellen kann, ist das Paar (c, r) ein Geheimschlüsselzertifikat des öffentlichen Schlüssels h von , derart, daß weiß, daß der Geheimschlüssel (x, I) h entspricht. Es wird angenommen, daß dieses Ausgabeprotokollzertifikat begrenzt verdeckt ist, wobei die verdeckte invariante Zahl I mod v ist, selbst wenn die CA-Programmabläufe des Protokolls parallel mit unterschiedlichen abgedeckten invarianten Zahlen durchführt.
Um Angriffe auf parallele Programmabläufe dieses Ausgabeprotokolls noch schwieriger zu gestalten, kann der bei dem ersten bevorzugten Ausführungsbeispiel beschriebene Zeitgebermechanismus eingebaut werden.

Schlußfolgerung

Dies ist die Schlußfolgerung der detallierten Beschreibungen der beiden bevorzugten Ausführungsbeispiele. Diese Beschreibungen der vorliegenden Erfindung wurden lediglich als Beispiele angeführt, und es ist klar, daß verschiedene Modifikationen, abgewandelte Konfigurationen und Äquivalente benutzt werden können, ohne vom Rahmen und Schutzumfang der vorliegenden Erfindung abzuweichen. Beispielsweise gibt es zahlreiche wesentliche äquivalente Ordnungen der berechneten Ausdrücke und Möglichkeiten der Berechnungen der Ausdrücke; es gibt weiter Möglichkeiten, um Ausdrücke, Tests und Übertragungen innerhalb der Flußdiagramme durchzuführen und Möglichkeiten, um die Operationen in Flußdiagrammkästchen zu gruppieren. Es gibt ferner verschiedene Möglichkeiten, um die Flußdiagrammkästchen zu ordnen. Die spezielle Wahl, die hier beschrieben wurde, dient lediglich der Klarheit der Beschreibung.
Es ist klar, daß alle Techniken, die in der US-A- 5 521 980 zur Anwendung der begrenzt verdeckten Ausgabeprotokolle in Privat-Schutzmechanismen für Wertetransport, beispielsweise in elektronischen Off-Line-Zahlungsanlagen, geradeso in Verbindung mit den modifizierten Ausgabeprotokollen benutzt werden können.
Gewisse Variationen und Substitutionen sind für den Fachmann naheliegend. Obgleich zahlreiche derartige Variationen und Substitutionen im Text angegeben wurden, soll dies im Licht des folgenden Beispiels noch erläutert werden.
Die beispielhaften Ausgabeprotokolle, die beschrieben wurden, sind Modifikationen der begrenzt verdeckten Ausgabeprotokollzertifikate, die in der US-A-5 521 980 und US-A- 5 606 617 beschrieben sind. Die erfindungsgemäße Modifikationstechnik ist auf alle Geheimschlüssel-Zertifikatsschemen anwendbar, die in diesen Dokumenten beschrieben sind und auch in Variationen hiervon. Allgemein kann man die erfindungsgemäße Modifikationstechnik in Verbindung mit Funktionen f(·) benutzen, die anders sind als die definierten, und zwar durch das Paar (F,M) bei den dargestellten Ausführungsbeispielen. Die erfindungsgemäße Modifikationstechnik arbeitet für jede Funktion f(·) derart, daß: gegeben f(a) und b für a, b in *p(bzw. in *n für das zweite bevorzugte Ausführungsbeispiel) es leicht ist, f(ab mod p) (bzw. f(ab mod n) zu berechnen; und wenn f(a) und f(b) für a,b in *p gegeben sind (bzw. in *n für das zweite bevorzugte Ausführungsbeispiel), sollte es unmöglich sein, die algebraischen Relationen wie beispielsweise f(ab mod p), f(a&sup5;b&sup7; mod p) (bzw. f(ab mod n), f(a&sup5;b&sup7; mod n)) zu berechnen. Wenn außerdem der beschriebene erfindungsgemäße Zeitgebermechanismus benutzt wird, genügt es, daß die Berechnung solcher algebraischer Relationen innerhalb der aufgeprägten Zeitbegrenzung unmöglich wird (wobei diese Zeitbegrenzung nicht mehr als einen Bruchteil einer Sekunde beträgt).
Es ist für den Fachmann außerdem klar, wie Teile der erfindungsgemäßen Techniken und Protokolle, wie sie hier beschrieben wurden, mit Vorteil benutzt werden können.

Claims

1. Kryptographisches Verfahren zur Erzeugung eines Ausgabeprotokollzertifikats, bei welchem ein Ausgabeteilnehmer Tripel ausgibt, die aus einem Geheimschlüssel, einem angepaßten öffentlichen Schlüssel und einem Zertifikat des Ausgabeteilnehmers auf dem öffentlichen Schlüssel bestehen, derart, daß ein Empfängerteilnehmer den öffentlichen Schlüssel und das entsprechende Zertifikat verdecken kann, nicht aber eine nicht-triviale verdeckte invariable Aussage des Geheimschlüssels, selbst wenn der Programmablauf des Ausgabeprotokolls parallel durchgeführt wird, wobei das Verfahren die folgenden Schritte aufweist:

es wird von dem Ausgabeteilnehmer ein Geheimschlüssel (x&sub0;, y), ein öffentlicher Schlüssel (p, g, h&sub0;, g&sub1;) und die Beschreibung einer Funktion f( ) erzeugt, wobei:

q ist eine Primzahl;

x&sub0; und y sind Elemente des Rings q von ganzzahligen Moduln q;

p ist eine Primzahl derart, daß q den Ausdruck p - 1 gleichmäßig teilt;

g ist ein Element der Ordnung q in der Gruppe *p des ganzzahligen Moduls p;

h&sub0; ist gleich gx0 mod p;

g&sub1; ist gleich gy mod p; und

für a, b in *p ist es leicht, f(ab mod p) gegeben durch f(a) und b zu berechnen, aber im wesentlichen unmöglich, f(aabβ mod p) aus f(a) und f(b) bei bekannten a und β zu berechnen.

es wird für öffentlichen Gebrauch eine Hash-Funktion (·) erzeugt, die ihre Argumente auf &sub2;l für einen geeigneten Sicherheitsparameter l überträgt und der im wesentlichen unmöglich zu invertieren ist;

es wird im Ausgabeprotokoll durch den Ausgabeteilnehmer eine im wesentlichen zufällige Zahl w&sub0; in q erzeugt, es wird a&sub0; ← f(gw0 mod p) berechnet, und es wird ein Signal, welches für repräsentativ ist, dem Empfängerteilnehmer übermittelt;

es wird im Ausgabeprotokoll durch den Empfängerteilnehmer eine Zahl x in q erzeugt, es wird ein öffentlicher Schlüssel h ← gx mod p berechnet, wobei I mod q den verdecjct invariablen Teil des entsprechenden Geheimschlüssels (x, I) repräsentiert;

es werden im Ausgabeprotokoll durch den Empfängerteilnehmer zwei im wesentlichen zufällige Zahlen t und u in q erzeugt, es wird α ← f(gw&sub0; gt(h&sub0;h )u mod p) aus a&sub0; und gt(h&sub0;g )u mod p berechnet, und es wird c ← (h, a) berechnet;

es wird im Ausgabeprotokoll durch den Empfängerteilnehmer die Anforderung c&sub0; ← c + u mod q berechnet, und es wird ein Signal, welches repräsentativ ist für c&sub0; nach dem Ausgabeteilnehmer übertragen;

es wird in dem Ausgabeprotokoll durch den Ausgabeteilnehmer die Antwort r&sub0; ←, c&sub0; (x&sub0; + x&sub0;yI) + w&sub0; mod d berechnet, und es wird ein Signal, welches für r&sub0; repräsentativ ist, nach dem Empfängerteilnehmer übertragen, und

es wird durch den Empfängerteilnehmer verifiziert, daß f(gr&sub0;(h&sub0;g )-c&sub0; mod p) gleich a&sub0; ist, und es wird r ← r&sub0; + cx + t mod q berechnet, um das Zertifikat (c, r) auf dem öffentlichen Schlüssel h zu vervollständigen.

2. Verfahren nach Anspruch 1, bei welchem f(·) durch ein Modul M derart spezifiziert ist, daß p die Ordnung von *M gleichmäßig teilt und ein Element F in *M der Ordnung p und ( ) ein Element a in *p der Zahl Fa mod M zuordnet.

3. Verfahren nach Anspruch 1, bei welchem der Ausgabeteilnehmer die Verzögerung zeitlich einstellt, die zwischen dem Aussenden des Signales repräsentativ für a&sub0; nach dem Empfängerteilnehmer und dem Empfang verstreicht, zu dem der Empfängerteilnehmer das Signal empfängt, welches repräsentativ für c&sub0; ist, wobei die Verzögerung durch Benutzung eines genügend genauen Taktgebers eingestellt wird, wobei die entsprechende Antwort r&sub0; zurückgehalten wird, falls diese Verzögerungszeit eine vorbestimmte zeitliche Grenze überschreitet.

4. Kryptographisches Verfahren zur Erzeugung eines Ausgabeprotokollzertifikats, bei welchem ein Ausgabeteilnehmer ein Tripel ausgibt, das aus einem Geheimschlüssel, einem angepaßten öffentlichen Schlüssel und einem Zertifikat des Ausgabeteilnehmers auf dem öffentlichen. Schlüssel besteht, derart, daß der Empfängerteilnehmer den öffentlichen Schlüssel und das entsprechende Zertifikat verdecken kann, nicht aber eine nicht-triviale verdeckte invariable Aussage des Geheimschlüssels, selbst wenn der Programmablauf des Ausgabeprotokolls parallel durchgeführt wird, wobei das Verfahren die folgenden Schritte umfaßt:

es wird durch den Ausgabeteilnehmer ein Geheimschlüssel (x&sub0;, y), ein öffentlicher Schlüssel (n, v, h&sub0;, g&sub1;) und die Beschreibung einer Funktion f(·) erzeugt, wobei:

n ist das Produkt von zwei Primzahlen;

x&sub0; und y sind Elemente der Gruppe *n der ganzzahligen Moduln n;

v ist ein Element von *n, das ein Primzahlenbestandteil der Ordnung von *n ist;

h&sub0; ist gleich x mod n;

g&sub1; ist gleich yv mod n; und

für a, b in *n ist es leicht, f(ab mod n) gegeben durch f(a) und b zu berechnen, aber es ist im wesentlichen unmöglich, f(aabβ mod n) von f(a) und f(b) bei bekannten α und β zu berechnen;

es wird für öffentlichen Gebrauch eine Hash-Funktion ( ) erzeugt, die ihr Argument auf &sub2;l für einen geeigneten Sicherheitsparameter l überträgt und im wesentlichen unmöglich zu invertieren ist;

es wird im Ausgabeprotokoll durch den Ausgabeteilnehmer eine im wesentlichen zufällige Zahl w&sub0; in *n erzeugt, es wird a&sub0; ← f(w mod n) berechnet, und es wird ein Signal, welches für a&sub0; repräsentativ ist, nach dem Empfängerteilnehmer übertragen;

es wird im Ausgabepretokoll durch den Empfängerteilnehmer eine Zahl x in *n erzeugt, es wird ein öffentlicher Schlüssel h ← xvg mod n erzeugt, wobei I mod v den verdeckt invariablen Teil des entsprechenden Geheimschlüssels (x, I) repräsentiert;

es werden im Ausgabeprotokoll durch den Empfängerteilnehmer zwei im wesentlichen zufällige Zahlen t in *n und u in v erzeugt, es wird a ← f(w tv(h&sub0;g )u mod n) aus a&sub0; und tv(h&sub0;g )u mod n erzeugt, und es wird c ← (h, a) berechnet;

es wird im Ausgabeprotokoll durch den Empfängerteilnehmer die Anforderung c&sub0; ← c + u mod v berechnet, und es wird ein Signal, welches repräsentativ für c&sub0; ist, an den Ausgabeteilnehmer übertragen;

es wird im Ausgabeprotokoll durch den Ausgabeteilnehmer die Antwort r&sub0; ← (x&sub0;yI)c0w&sub0; mod n berechnet, und es wird ein Signal, welches repräsentativ für r&sub0; ist, an den Empfängerteilnehmer übertragen; und

es wird durch den Empfängerteilnehmer verifiziert, daß f(r (h&sub0;y )-c0 mod n) gleich ist a&sub0;, und es wird r ← r&sub0;xct(h&sub0;g )c+u div v mod n berechnet, um das Zertifikat (c, r) auf dem öffentlichen Schlüssel h zu vervollständigen.

5. Verfahren nach Anspruch 4, bei welchem f( ) durch einen Modul M derart spezifiziert wird, daß n die Ordnung von *M gleichmäßig teilt, und ein Element F in *M der Ordnung n, und f(·) überträgt die Zahl Fa mod M auf ein Element a in *n.

6. Verfahren nach Anspruch 4, bei welchem der Ausgabeteilnehmer eine zeitliche Verzögerung zwischen dem Aussenden des Signals repräsentativ für a&sub0; nach dem Empfängerteilnehmer und dem Zeitpunkt einführt, zu dem der Empfängerteilnehmer das für c&sub0; repräsentative Signal empfängt, wobei die Zeitverzögerung unter Benutzung eines genügend genauen Zeitgebers erfolgt und die entsprechende Antwort r&sub0; zurückgehalten wird, falls diese Verzögerungszeit eine vorbestimmte zeitliche Grenze überschreitet.