DE102011117219A1

DE102011117219A1 - Bestimmen eines Divisionsrests und Ermitteln von Primzahlkandidaten für eine kryptographische Anwendung

Info

Publication number: DE102011117219A1
Application number: DE102011117219A
Authority: DE
Inventors: Jürgen Pulkus
Original assignee: Giesecke and Devrient GmbH
Current assignee: Giesecke and Devrient Mobile Security GmbH
Priority date: 2011-10-28
Filing date: 2011-10-28
Publication date: 2013-05-02
Also published as: EP2772005A2; WO2013060466A2; WO2013060466A3; US20140286488A1; CN104012029A

Abstract

Bei einem Verfahren zum Bestimmen des Divisionsrests eines ersten Wertes (b) modulo eines zweiten Wertes (p') wird eine erste Montgomery-Multiplikation mit dem ersten Wert (b) als einem der Faktoren und dem zweiten Wert (p') als Modul ausgeführt (74.1), ein Korrekturfaktor wird bestimmt (74.2), und eine zweite Montgomery-Multiplikation wird mit dem Ergebnis der ersten Montgomery-Multiplikation als einem der Faktoren und dem Korrekturfaktor als dem anderen Faktor- und dem zweiten Wert (p') als Modul ausgeführt (74.3). Bei einem Verfahren zum Ermitteln von Primzahlkandidaten wird ein Basiswert (b) für ein Sieb bestimmt, und es werden mehrere Siebdurchläufe ausgeführt, bei denen jeweils ein Markierungswert (p') ermittelt wird (72) und Vielfache des Markierungswertes (p') in dem Sieb als zusammengesetzte Zahlen markiert werden, wobei bei jedem Siebdurchlauf ein Divisionsrest des Basiswertes (b) modulo des Markierungswertes (p') mit einem Restbestimmungsverfahren bestimmt wird (74), das mindestens eine Montgomery-Operation umfasst. Eine Vorrichtung und ein Computerprogrammprodukt weisen entsprechende Merkmale auf. Die genannten Verfahren lassen sich auf geeigneten Plattformen effizient implementieren.

Description

Die Erfindung betrifft allgemein das technische Gebiet der effizient implementierbaren kryptographischen Verfahren. Spezieller betrifft ein erster Aspekt der Erfindung das Bestimmen eines Divisionsrests, während ein zweiter Aspekt der Erfindung das Ermitteln von Primzahlkandidaten – dies sind Werte, die mit gewisser Wahrscheinlichkeit Primzahlen darstellen – betrifft. Besonders eignet sich die Erfindung zur Verwendung in einem tragbaren Datenträger. Ein solcher tragbarer Datenträger kann z. B. eine Chipkarte (smart card) in unterschiedlichen Bauformen oder ein Chipmodul oder ein vergleichbares ressourcenbeschränktes System sein.
Effiziente Verfahren zur Primzahlermittlung sind für viele kryptographische Anwendungen erforderlich. So müssen z. B. zur Schlüsselgenerierung bei dem im US-Patent 4,405,829 beschriebenen RSA-Verfahren zwei geheime Primzahlen festgelegt werden, deren Produkt einen Teil des öffentlichen Schlüssels bildet. Die Größe dieser Primzahlen hängt von den Sicherheitsanforderungen ab und beträgt in der Regel mehrere hundert bis einige tausend Bit. Voraussichtlich wird die geforderte Größe in Zukunft noch deutlich ansteigen.
Insgesamt ist die Primzahlsuche der mit Abstand rechenintensivste Schritt bei der RSA-Schlüsselgenerierung. Aus Sicherheitsgründen wird oft gefordert, dass die Schlüsselgenerierung durch den Datenträger selbst ausgeführt wird. Je nach dem Typ das Datenträgers kann dieser Vorgang während der Produktion des Datenträgers (z. B. der Komplettierung oder Initialisierung oder Personalisierung) einen Zeitaufwand verursachen, der stark variiert und gegebenenfalls mehrere Minuten betragen kann. Da Produktionszeit teuer ist, stellt die zur Schlüsselgenerierung erforderliche Zeit einen erheblichen Kostenfaktor dar. Es ist daher wünschenswert, die Schlüsselgenerierung zu beschleunigen und damit den erzielbaren Durchsatz einer Produktionsanlage für tragbare Datenträger zu erhöhen.
Ein wichtiger Schritt zur Verringerung der Produktionszeit ist es, ein effizientes Verfahren zur Primzahlsuche zu verwenden, das ferner einige Randbedingungen hinsichtlich der erzeugten Primzahlen erfüllt. Derartige Verfahren sind bereits vorgeschlagen worden und beispielsweise aus den Offenlegungsschriften DE 10 2004 044 453 A1 und EP 1 564 649 A2 bekannt.
Bei RSA-Verfahren sind auch die nach der Schlüsselgenerierung erfolgenden Ver- und Entschlüsselungsvorgänge relativ rechenaufwendig. Insbesondere für tragbare Datenträger mit ihrer beschränkten Rechenleistung wird daher oft eine Implementierung eingesetzt, die bei der Entschlüsselung und der Signaturerzeugung den Chinesischen Restklassensatz (CRT = Chinese remainder theorem) verwendet und daher auch als RSA-CRT-Verfahren bezeichnet wird. Durch Verwendung des RSA-CRT-Verfahrens reduziert sich der für die Entschlüsselung und Signaturerzeugung erforderliche Rechenaufwand ungefähr um den Faktor 4.
Zur Vorbereitung des RSA-CRT-Verfahrens werden bei der Bestimmung des privaten Schlüssels neben den beiden geheimen RSA-Primfaktoren weitere Werte berechnet und als Parameter des privaten Schlüssels abgespeichert. Nähere Informationen hierzu sind beispielsweise in der Offenlegungsschrift WO 2004/032411 A1 enthalten. Da die Berechnung der weiteren RSA-CRT-Schlüsselparameter in der Regel ebenfalls während der Produktion des tragbaren Datenträgers ausgeführt wird, ist es wünschenswert, auch hierfür möglichst effiziente Verfahren zu verwenden.
Viele tragbare Datenträger enthalten Koprozessoren, die bestimmte Berechnungsvorgänge unterstützen. Insbesondere sind Datenträger bekannt, deren Koprozessoren eine als Montgomery-Multiplikation bekannte Operation unterstützen, die in dem Artikel "Modular multiplication without trial division" von Peter L. Montgomery, erschienen in Mathematics of Computation, Vol. 44, Nr. 170, April 1985, Seiten 519–521 beschrieben ist, Montgomery-Koprozessoren unterstützen üblicherweise weder die modulare noch die nicht-modulare ”normale” Multiplikation mit den für kryptographische. Aufgaben erforderlichen Bitlängen. Für andere Koprozessoren könnte möglicherweise gelten, dass modulare oder nicht-modulare Multiplikation zwar unterstützt, aber weniger effizient als die Montgomery-Multiplikation ausgeführt werden. Auch Divisionsoperationen werden von vielen üblichen Montgomery-Koprozessoren nicht oder nicht effizient oder nicht mit den für kryptographische Aufgaben erforderlichen Bitlängen unterstützt. Es wäre wünschenswert, die Fähigkeiten von gegenwärtig verfügbaren oder zukünftig auf den Markt kommenden Koprozessoren möglichst gut auszunutzen.
Die Erfindung hat demgemäß die Aufgabe, eine effiziente Technik zum Bestimmen eines Divisionsrests bzw. zum Ermitteln von Primzahlkandidaten bereitzustellen.
Erfindungsgemäß wird diese Aufgabe ganz oder zum Teil gelöst durch ein Verfahren mit den Merkmalen des Anspruchs 1 bzw. des Anspruchs 8, ein Computerprogrammprodukt gemäß Anspruch 14 und eine Vorrichtung, insbesondere einen tragbaren Datenträger, gemäß Anspruch 15. Die abhängigen Ansprüche betreffen optionale Merkmale einiger Ausgestaltungen der Erfindung.
Ein erster Aspekt der Erfindung geht von der Grundüberlegung aus, zum Bestimmen eines Divisionsrests eine Montgomery-Multiplikation statt einer sonst üblichen modularen Division durchzuführen. Der durch die Montgomery-Multiplikation hervorgerufene Fehler wird dann durch eine weitere Montgomery-Multiplikation ausgeglichen, wobei ein geeignet bestimmter Korrekturfaktor als einer der Faktoren dieser weiteren Montgomery-Multiplikation dient. Dieses Verfahren lässt sich auf vielen üblichen Hardware-Plattformen weit effizienter implementieren als eine modulare Division mit Rest.
In manchen Ausgestaltungen ist die erste Montgomery-Multiplikation eine Montgomery-Reduktion, also eine Multiplikation mit 1 als einem der beiden Faktoren. Vorzugsweise werden die beiden Montgomery-Multiplikationen mit unterschiedlichen Montgomery-Koeffizienten ausgeführt.
Der Korrekturfaktor wird in manchen Ausführungsformen als modulare Zweierpotenz in einer Schleife berechnet, wobei jeder Schleifendurchlauf eine Verdopplung eines Zwischenergebnisses und eine bedingte Subtraktion aufweist. In anderen Ausführungsformen wird der Korrekturfaktor dagegen als modulare Potenz mit einem positiven und ganzzahligen Korrekturfaktor-Exponenten und der Basis ½ berechnet. Hierzu können wiederum Montgomery-Operationen eingesetzt werden.
Ein zweiter Aspekt der Erfindung geht von der Grundidee aus, Primzahlkandidaten in einem Siebverfahren zu ermitteln. Ausgehend von einem Basiswert werden hierbei mehrere Siebdurchläufe ausgeführt, bei denen jeweils ein Markierungswert bestimmt wird und Vielfache des Markierungswertes in dem Sieb als zusammengesetzte Zahlen markiert werden. Ferner wird bei jedem Siebdurchlauf ein Divisionsrest des Basiswertes modulo des Markierungswertes mit einem Restbestimmungsverfahren bestimmt, das auf üblichen Hardware-Plattformen besonders effizient implementierbar ist, weil es mindestens eine Montgomery-Operation umfasst.
In bevorzugten Ausführungsformen ist der (zumindest eine) Markierungswert eine Primzahl. Vorteilhaft können mehrere Primzahlen als Markierungswerte für einen Siebdurchlauf verwendet werden. Das Sieb kann beispielsweise, ausgehend von dem Basiswert, nur Zahlen einer vorbestimmten Schrittweite repräsentieren. In manchen Ausgestaltungen werden weitere Primzahltests ausgeführt, um aus den Primzahlkandidaten wahrscheinliche Primzahlen zu ermitteln. In vielen Ausgestaltungen des Verfahrens gemäß dem zweiten Aspekt der Erfindung wird ein Restbestimmungsverfahren gemäß dem ersten Aspekt der Erfindung verwendet.
Die Aufzählungsreihenfolge der Schritte in den Verfahrensansprüchen soll nicht als Einschränkung des Schutzbereichs verstanden werden. Es sind vielmehr auch Ausgestaltungen der Erfindung vorgesehen, in denen diese Schritte ganz oder teilweise in anderer Reihenfolge und/oder ganz oder teilweise ineinander verschachtelt (interleaved) und/oder ganz oder teilweise parallel ausgeführt werden.
Das erfindungsgemäße Computerprogrammprodukt weist Programmbefehle auf, um das erfindungsgemäße Verfahren zu implementieren. Ein derartiges Computerprogrammprodukt kann ein körperliches Medium sein, z. B. ein Halbleiterspeicher oder eine Diskette oder eine CD-ROM. Das Computerprogrammprodukt kann jedoch in manchen Ausführungsformen auch ein nicht-körperliches Medium sein, z. B. ein über ein Computernetzwerk übermitteltes Signal. Insbesondere kann das Computerprogrammprodukt Programmbefehle enthalten, die im Zuge der Produktion eines tragbaren Datenträgers in diesen eingebracht werden.
Die erfindungsgemäße Vorrichtung kann insbesondere ein tragbarer Datenträger, z. B. eine Chipkarte oder ein Chipmodul, sein. Ein derartiger Datenträger enthält in an sich bekannter Weise mindestens einen Prozessor, mehrere in unterschiedlichen Technologien ausgestaltete Speicher und diverse Hilfsbaugruppen. In der Wortwahl des vorliegenden Dokuments soll der Begriff ”Prozessor” sowohl Hauptprozessoren als auch Koprozessoren umfassen.
In bevorzugten Weiterbildungen weisen das Computerprogrammprodukt und/oder die Vorrichtung Merkmale auf, die den in der vorliegenden Beschreibung erwähnten und/oder den in den abhängigen Verfahrensansprüchen genannten Merkmalen entsprechen.
Weitere Merkmale, Aufgaben und Vorteile der Erfindung ergeben sich aus der folgenden Beschreibung mehrerer Ausführungsbeispiele und Ausführungsalternativen. Es wird auf die schematische Zeichnung verwiesen.
1 zeigt ein Flussdiagramm eines Verfahrens zur Bestimmung zweier Primzahlen sowie weiterer Parameter eines RSA-CRT-Schlüssels,
2 zeigt ein Flussdiagramm eines Verfahrens zur Bestimmung eines Primzahlkandidaten,
3 zeigt eine schematische Darstellung von Komponenten eines tragbaren Datenträgers, der zur Ausführung der Verfahren von 1 und 2 geeignet ist,
4 zeigt ein Flussdiagramm eines Verfahrens zum Erzeugen eines Kandidatenfeldes, und
5 zeigt einen beispielhaften Ablauf eines Verfahrens zur modularen Potenzberechnung mit der Basis ½ und einem positiven und ganzzahligen Exponenten e unter Verwendung von Montgomery-Operationen.
Im vorliegenden Dokument wird die Erfindung insbesondere in Zusammenhang mit der Bestimmung eines, mehrerer oder aller Parameter eines RSA-CRT-Schlüsselpaars beschrieben. Die Erfindung ist jedoch auch für andere Anwendungszwecke einsetzbar, insbesondere für die Bestimmung relativ großer und zufälliger Primzahlen, wie sie für diverse kryptographische Verfahren benötigt werden.
Allgemein sind die Parameter eines RSA-CRT-Schlüsselpaars von zwei geheimen Primzahlen p und q sowie einem öffentlichen Exponenten e abgeleitet. Hierbei ist der öffentliche Exponent e eine zum Wert (p – 1)·(q – 1) teilerfremde Zahl, die zufällig gewählt oder fest vorgegeben sein kann. Beispielsweise wird in manchen Ausführungsbeispielen die vierte Fermat'sche Primzahl F₄ = 2¹⁶ + 1 als öffentlicher Exponent e verwendet. Der öffentliche Schlüssel enthält den öffentlichen Exponenten e und einen öffentlichen Modul N := p·q. Der private RSA-CRT-Schlüssel enthält neben den beiden Primzahlen p und q das modulare Inverse p_inv := p^–1 mod q sowie die beiden CRT-Exponenten d_p und d_q, die durch d_p := e^–1 mod (p – 1) beziehungsweise d_q := e^–1 mod (q – 1) definiert sind.
Das Verfahren gemäß 1 zeigt die Berechnung aller Parameter eines geheimen RSA-CRT-Schlüssels bei vorgegebenem öffentlichen Exponenten e. Das Verfahren besteht aus zwei Teilen, die in einer linken bzw. rechten Spalte von 1 dargestellt sind. Der erste Teil (Schritte 10, 12, 16 und 20) umfasst die Bestimmung der einen Primzahl p und des damit zusammenhängenden Schlüsselparameters d_p, während der zweite Teil (Schritte 24, 26; 30, 34 und 38) die Bestimmung der anderen Primzahl q und der Schlüsselparameter d_q und p_inv betrifft.
Es versteht sich, dass das Verfahren in Ausführungsalternativen derart abgewandelt werden kann, dass nur manche der gerade genannten Parameter berechnet werden. Hierzu können beispielsweise Verfahrensschritte weggelassen oder verkürzt werden, wenn manche Schlüsselparameter anderweitig berechnet oder gar nicht benötigt werden. Insbesondere kann vorgesehen sein, nur einen der beiden in 1 gezeigten Verfahrensteile (also entweder nur die Schritte 10, 12, 16 und 20 oder nur die Schritte 24, 26, 30, 34 und 38) auszuführen, wenn nur eine einzige Primzahl bestimmt zu werden braucht.
In 1 und den weiteren Zeichnungsfiguren zeigen die durchgezogenen Pfeile den regulären Programmfluss, und die gestrichelten Pfeile zeigen alternative Programmabläufe, die unter gewissen Bedingungen – insbesondere, wenn sich ein Primzahlkandidat oder eine voraussichtliche Primzahl als zusammengesetzt erweisen – ausgeführt werden. Die gepunkteten Pfeile veranschaulichen den Datenfluss.
Der in 1 dargestellte Ablauf beginnt in Schritt 10 mit der Erzeugung eines ersten Primzahlkandidaten m, der gewisse Randbedingungen (insbesondere die Randbedingung m ≡ 3 mod 4) erfüllt. In den hier beschriebenen Ausführungsbeispielen wird bei der Bestimmung jedes Primzahlkandidaten m eine Vorauswahl getroffen, die sicherstellt, dass der Primzahlkandidat m nicht schon durch eine kleine Primzahl (z. B. 2, 3, 5, 7, ...) teilbar ist. Ein geeignetes Bestimmungsverfahren mit Vorauswahl ist in 2 gezeigt und wird unten genauer beschrieben.
In Schritt 12 wird der Primzahlkandidat m einem Fermat-Test unterzogen. Der Fermat-Test ist ein probabilistischer Primzahltest, der eine zusammengesetzte Zahl mit hoher Wahrscheinlichkeit als solche erkennt, während eine Primzahl nie fälschlich als zusammengesetzte Zahl angesehen wird. Der Fermat-Test beruht auf dem kleinen Fermat'schen Satz, der besagt, dass für jede Primzahl p und jede natürliche Zahl a die Beziehung a^p ≡ a mod p gilt. Die Umkehrung gilt nicht notwendigerweise, aber Gegenbeispiele sind so selten, dass ein Primzahlkandidat m, der den Fermat-Test besteht, mit an Sicherheit grenzender Wahrscheinlichkeit eine Primzahl ist.
Falls der Primzahlkandidat m bei dem Fermat-Test in Schritt 12 als zusammengesetzte Zahl erkannt wird, erfolgt ein Rücksprung 14 nach Schritt 10, in dem ein neuer Primzahlkandidat bestimmt wird. Andernfalls wird das Verfahren fortgesetzt, wobei der Primzahlkandidat m als voraussichtliche Primzahl p angesehen wird.
In Schritt 16 wird der CRT-Exponent d_p, der vermöge d_p := e mod (p – 1) definiert ist, berechnet. Hierfür wird ein an sich bekanntes Inversionsverfahren verwendet. Der CRT-Exponent d_p als modulares Inverses des öffentlichen Exponenten e existiert genau dann, wenn e und p – 1 teilerfremd sind, also wenn ggT(p – 1, e) = 1 gilt. Ist dies nicht der Fall, so erfolgt ein Rücksprung 18 zum Anfang des Verfahrens. Sonst wird der CRT-Exponent d_p in Schritt 16 bestimmt und das Verfahren dann in Schritt 20 mit einem Miller-Rabin-Test der voraussichtlichen Primzahl p fortgesetzt.
Der Miller-Rabin-Test ist also solcher aus dem Artikel "Probabilistic algorithms for testing primality" von Michael O. Rabin, erschienen im Journal of Number Theory 12, 1980, Seiten 128–138, bekannt. Bei jeder Testrunde des Miller-Rabin-Tests wird eine zusammengesetzte Zahl mit gewisser Wahrscheinlichkeit als solche erkannt, während eine Primzahl nie fälschlich als zusammengesetzte Zahl angesehen wird. Die Fehlerwahrscheinlichkeit des Miller-Rabin-Tests hängt von der Anzahl der Testrunden ab und kann, indem hinreichend viele Testrunden ausgeführt werden, beliebig klein gehalten werden.
Wegen der bereits erwähnten hohen Treffsicherheit des Fermat-Tests in Schritt 12 ist die Wahrscheinlichkeit, dass die voraussichtliche Primzahl p bei dem Miller-Rabin-Test in Schritt 20 als zusammengesetzte Zahl erkannt wird, vernachlässigbar. Die Wahrscheinlichkeit, dass die Berechnung des CRT-Exponenten d_p in Schritt 16 wegen ggT(p – 1, e) ≠ 1 fehlschlägt und der Rücksprung 18 ausgeführt werden muss, ist dagegen um Größenordnungen höher. Es ist daher effizienter, den Schritt 16 vor Schritt 20 auszuführen, weil dadurch unnötige Miller-Rabin-Tests vermieden werden. Dennoch umfasst die Erfindung auch Ausführungsbeispiele, bei denen der CRT-Exponent d_p erst nach dem Miller-Rabin-Test oder zu einem anderen Zeitpunkt berechnet wird. Ferner kann in Ausführungsalternativen vorgesehen sein, die Berechnung des CRT-Exponenten d_p getrennt von dem hier beschriebenen Verfahren zur Primzahlermittlung auszuführen; der Schritt 16 kann dann weggelassen werden.
Der Miller-Rabin-Test in Schritt 20 wird ausgeführt, um eine gewünschte maximale Fehlerwahrscheinlichkeit, die beispielsweise 2^–100 betragen kann, mathematisch nachweisen zu können. Bei dem Miller-Rabin-Test werden mehrere Testrunden ausgeführt, deren Anzahl von dieser Fehlerwahrscheinlichkeit abhängt. Eine Testrunde für die voraussichtliche Primzahl p besteht darin, dass eine Zufallszahl zur ((p – 1)/2)-ten Potenz modulo p erhoben wird, und dass geprüft wird, ob das Ergebnis ±1 modulo p ist. Hierbei wird die Randbedingung p ≡ 3 mod 4 vorausgesetzt.
In dem höchst unwahrscheinlichen Fall, dass die voraussichtliche Primzahl p bei einer der Testrunden des Miller-Rabin-Tests in Schritt 20 als zusammengesetzte Zahl erkannt wird, erfolgt ein Rücksprung 22 zum Anfang des Verfahrens. Andernfalls wird die Primzahl p als eines der Ergebnisse des hier beschriebenen Verfahrens ausgegeben.
Der zweite Verfahrensteil, der in der rechten Spalte von 1 gezeigt ist, ist bis auf Schritt 34 eine Wiederholung des ersten Verfahrensteils gemäß der linken Spalte von 1, wobei die zweite Primzahl q berechnet wird. Es wird daher weitgehend auf die obigen Erläuterungen verwiesen.
Die Schritte 24, 26 und 30 sind analog zu den Schritten 10, 12 und 16. Wenn sich der in Schritt 24 ausgewählte Primzahlkandidat m bei dem Fermat-Test in Schritt 26 als zusammengesetzt erweist, wird ein Rücksprung 28 zur Auswahl eines neuen Primzahlkandidaten in Schritt 24 ausgeführt. Andernfalls wird in Schritt 30 der CRT-Exponent d_q := e^–1 mod (q – 1) berechnet. Ein Rücksprung 32 zu Schritt 24 erfolgt, falls e und q – 1 nicht teilerfremd sind. Andernfalls wird das Verfahren mit der voraussichtlichen Primzahl q fortgesetzt. Ähnlich wie im ersten Verfahrensteil sind auch hier Abwandlungen vorgesehen, bei denen der CRT-Exponent d_q zu einem anderen Zeitpunkt im Zusammenhang mit dem hier beschriebenen Verfahren oder getrennt davon berechnet wird.
In Schritt 34 wird ein kombiniertes Test- und Inversionsverfahren ausgeführt, bei dem eine erste Testrunde eines Miller-Rabin-Tests für die voraussichtliche Primzahl q mit der Berechnung des Inversen p_inv := p^–1 mod q gekoppelt ist. Weil q eine Primzahl ist, kann das Inverse p_inv vermöge des kleinen Fermat'schen Satzes als p_inv = p^–1 = p^q–2 mod q bestimmt werden. Weil p eine Zufallszahl ist, kann bei dieser Berechnung mit geringem Mehraufwand sogleich eine erste Miller-Rabin-Testrunde für die voraussichtliche Primzahl q ausgeführt werden, wobei geprüft wird, ob die ((q – 1)/2)-te Potenz von p modulo q gleich ±1 ist.
In Schritt 34 erfolgt ein Rücksprung 36 zu Schritt 24, falls die voraussichtliche Primzahl q die erste Miller-Rabin-Testrunde nicht besteht. Andernfalls werden in Schritt 38 die weiteren noch erforderlichen Testrunden des Miller-Rabin-Tests ausgeführt. Schlägt eine dieser Testrunden fehl, so erfolgt ein Rücksprung 40 nach Schritt 24 zur Auswahl eines neuen Primzahlkandidaten. Andernfalls steht die zweite Primzahl q fest, und das Verfahren endet.
In manchen Ausführungsformen ist das in 1 gezeigte Verfahren dahingehend abgewandelt, dass kein kombiniertes Test- und Inversionsverfahren vorgesehen ist. So kann beispielsweise statt des Schritts 36 eine zusätzliche Runde des Miller-Rabin-Tests in Schritt 38 ausgeführt werden. Die Berechnung des Inversen p_inv kann dann als separater Schritt – als Teil des hier beschriebenen Verfahrens oder getrennt davon – ausgeführt werden, sofern eine solche Berechnung überhaupt erforderlich ist. So dient beispielsweise das Inverse p_inv bei RSA-CRT-Berechnungen lediglich zur Effizienzsteigerung. Bei RSA-Berechnungen ohne Verwendung des Chinesischen Restklassensatzes wird das Inverse p_inv gar nicht gebraucht.
2 veranschaulicht die Bestimmung eines Primzahlkandidaten m, wie sie in den Schritten 10 und 24 von 1 ausgeführt wird. In den vorliegend beschriebenen Ausführungsbeispielen wird hierbei ein Kandidatenfeld verwendet, das mehrere Primzahlkandidaten m bereitstellt. Das Kandidatenfeld kann beispielsweise ein gepacktes Bitfeld (bit array) S sein, dessen Bits S[i] angeben, ob eine Zahl, die einen von der Bitposition i abhängigen Versatz von einem Basiswert b aufweist, ein Primzahlkandidat m ist oder nicht.
Bei dem Verfahren gemäß 2 wird zunächst in Test 42 überprüft, ob ein geeignetes und nicht-leeres Kandidatenfeld vorhanden ist. Wenn dies nicht der Fall ist, wird in Schritt 44 ein zufälliger Basiswert b erzeugt, der die Bedingungen b ≡ 3 mod 4 erfüllt.
In Schritt 46 wird dann das Kandidatenfeld erzeugt. Als Datenstruktur für das Kandidatenfeld wird im vorliegenden Ausführungsbeispiel ein Bitfeld S verwendet, dessen Bitpositionen i jeweils einem Versatz von SWi zum Basiswert b entsprechen (mit SW als Schrittweite). Jedes Bit S[i] des fertiggestellten Kandidatenfeldes zeigt somit an, ob die Zahl b + SWi als Primzahlkandidat m verwendet werden kann oder nicht.
Zur Erzeugung des Kandidatenfeldes in Schritt 46 werden zunächst alle Bits S[i] auf einen ersten Wert – z. B. den Wert ”1” – initialisiert. Dann werden nach dem Prinzip des Siebes des Eratosthenes diejenigen Bits S[i] auf einen zweiten Wert – z. B. den Wert ”0” – geändert, die einer durch eine kleine Primzahl teilbaren Zahl b + SWi entsprechen. Die Größe des Kandidatenfeldes und die Anzahl der Siebdurchläufe werden – in Abhängigkeit von dem verfügbaren Speicherplatz – so gewählt, dass die durchschnittliche Laufzeit des Gesamtverfahrens minimiert wird. Dies ist eine Optimierungsaufgabe, deren Lösung von dem relativen Aufwand für die Vorauswahl verglichen mit dem Aufwand für einen fehlgeschlagenen Fermat-Test abhängt. Für RSA-Schlüssel mit 2048 Bit können beispielsweise mehrere Tausend Siebdurchläufe ausgeführt werden, wobei dann ungefähr 40 Fermat-Tests zur Bestimmung einer der Primzahlen p und q erforderlich sind.
In Schritt 48 wird schließlich ein Primzahlkandidat m aus dem gefüllten Kandidatenfeld ausgewählt. Diese Auswahl kann beispielsweise zufällig oder nach einer vorgegebenen Reihenfolge erfolgen. Bei weiteren Aufrufen des in 2 gezeigten Verfahrens wird Schritt 48 unmittelbar nach dem Test 42 ausgeführt, und es werden so lange weitere Primzahlkandidaten m aus dem einmal angelegten Kandidatenfeld ausgewählt, bis des Feld leer ist oder eine vorgegebene Mindestfüllmenge unterschritten wird.
Das in 1 und 2 gezeigte Verfahren wird in manchen Ausführungsformen von mindestens einem Prozessor eines tragbaren Datenträgers ausgeführt. 3 zeigt einen solchen Datenträger 50, der beispielsweise als Chipkarte oder Chipmodul ausgestaltet ist. Der Datenträger 50 weist einen Mikrocontroller 52 auf, in dem in an sich bekannter Weise ein Hauptprozessor 54, ein Koprozessor 56, eine Kommunikationsschnittstelle 58 und eine Speicherbaugruppe 60 auf einem einzigen Halbleiterchip integriert und über einen Bus 62 miteinender verbunden sind.
Die Speicherbaugruppe 60 weist mehrere in unterschiedlichen Technologien ausgestaltete Speicherfelder auf, die beispielsweise einen Festwertspeicher 64 (maskenprogrammiertes ROM), einen nicht-flüchtigen überschreibbaren Speicher 66 (EEPROM oder Flash-Speicher) und einen Arbeitsspeicher 68 (RAM) umfassen. Die hier beschriebenen Verfahren sind in Form von Programmbefehlen 70 implementiert, die im Festwertspeicher 64 und zum Teil auch im nicht-flüchtigen überschreibbaren Speicher 66 enthalten sind.
Der Koprozessor 56 des Datenträgers 50 ist zur effizienten Ausführung diverser kryptographischer Operationen ausgelegt. Insbesondere ist für die hier beschriebenen Ausführungsbeispiele relevant, dass der Koprozessor 56 die Montgomery-Multiplikation mit Bitlängen, wie sie für kryptographische Anwendungen benötigt werden, unterstützt. In manchen Ausgestaltungen unterstützt der Koprozessor 56 keine ”normale” modulare Multiplikation, so dass derartige Multiplikationen mit erheblich höherem Aufwand durch den Hauptprozessor 54 ausgeführt werden müssen.
Für natürliche Zahlen x, y und eine ungerade natürliche Zahl m mit x, y < m sowie eine als Montgomery-Koeffizient bezeichnete Zweierpotenz R mit R > m ist das Montgomery-Produkt von x und y modulo m bezüglich R allgemein wie folgt definiert: x *_m,R y := x·y·R^–1 mod m
Allgemein wird im vorliegenden Dokument bei der Angabe einer Modulo-Beziehung der Form ”a = z mod m” das Gleichheitszeichen ”=” bzw. das Definitionszeichen ”:=” verwendet, um auszudrücken, dass a das eindeutig definierte Element aus (z +
) ∩ [0, ..., m[ ist, für das die Modulo-Beziehung gilt. Die Schreibweise ”a = z mod m” drückt dagegen lediglich aus, dass die Äquivalenz modulo m gilt.
Wenn sich der Montgomery-Koeffizient R aus dem Kontext ergibt, wird im vorliegenden Dokument oft auch die abgekürzte Schreibweise x *_m y statt der ausführlichen Schreibweise x *_m,R y für das Montgomery-Produkt verwendet.
Obwohl die oben definierte Montgomery-Multiplikation eine modulare Operation ist, kann sie ohne Division implementiert werden, wie dies an sich gut bekannt und z. B. in dem eingangs genannten Artikel ”Modular multiplication without trial division” beschrieben ist. Für eine Montgomery-Multiplikation werden zwei nicht-modulare Multiplikationen, ein vorab in Abhängigkeit von m und R berechneter Hilfswert, einige Additionen und eine abschließende bedingte Subtraktion von m benötigt. Diese Berechnungen können durch den Koprozessor 56 effizient ausgeführt werden.
Bei gegenwärtig kommerziell verfügbaren Mikrocontrollern 52 sind Ausgestaltungen von Koprozessoren 56', 56'', 56''' bekannt, die nicht genau die oben definierte Montgomery-Multiplikation, sondern Abwandlungen davon ausführen. Der Grund für diese Abwandlungen liegt primär darin, dass die Entscheidung, ob die abschließende bedingte Subtraktion der Montgomery-Multiplikation ausgeführt werden soll, auf unterschiedliche Weisen optimiert werden kann. Allgemein liefern die abgewandelten Koprozessoren 56', 56'', 56''' bei der Berechnung der Montgomery-Multiplikation ein Ergebnis, das sich von dem oben definierten Ergebnis potentiell um ein kleines Vielfaches des Moduls m unterscheidet. Ferner ist der zulässige Wertebereich für die Faktoren x und y bei den abgewandelten Koprozessoren 56', 56'', 56''' derart erweitert, dass ein berechnetes Ergebnis stets wieder einen zulässigen Eingabewert als Faktor der Montgomery-Multiplikation darstellt.
Genauer berechnet ein erster abgewandelter Koprozessor 56' ein erstes abgewandeltes Montgomery-Produkt x *'_m y, das wie folgt definiert ist: x *'_m y := (x·y·R^–1 mod m) + k·m
Hierbei beträgt R = 2ⁿ für bestimmte Registergrößen n, die Vielfache von 16 sind. Der Wertebereich für die Faktoren x und y ist auf [0, ..., R – 1] erweitert, und k ist eine natürliche Zahl, die so klein ist, so dass x *'_m y < R gilt.
Ein zweiter abgewandelter Koprozessor 56'' berechnet dagegen ein zweites abgewandeltes Montgomery-Produkt x *''_m y, das wie folgt definiert ist: x *''_m y := (x·y·2^–n ^' mod m) – ε·m
Die Faktoren x und y sind hierbei ganze Zahlen im Bereich –m ≤ x, y < m. Ferner gilt ε ∊ {0, 1}, und der Exponent n' hat den Wert n' = n + 16p für eine Präzision p = 1, 2 oder 4, eine Blockgröße c mit 160 ≤ c ≤ 512, die ein Mehrfaches von 32 ist, und eine Registergröße n = c·p. Für den Modul m gilt m < 2ⁿ, und der Wert R ist als R := 2^n' definiert.
Ein dritter abgewandelter Koprozessor 56''' berechnet schließlich ein drittes abgewandeltes Montgomery-Produkt x *'''_m y, das wie folgt definiert ist x *'''_m y := (x·y·2^–t·c mod m) + ε·m
Die Faktoren x und y sind hierbei natürliche Zahlen mit x < 2^t·c und y < 2·m. Ferner gilt ε ∊ {0, 1}. Die Blockgröße c ist fest und beträgt c = 128. Die Registergröße für den Faktor x betragt t·c. Die Registergröße für die anderen Variablen wird mit n bezeichnet und beträgt ein Vielfaches der Blockgröße c. Wenn n = t·c gilt, dann braucht der Faktor x statt der Bedingung x < 2^t·c lediglich der Bedingung x < max {2·m, 2ⁿ} zu genügen.
Im vorliegenden Dokument wird das Montgomery-Produkt zweier Faktoren x und y bezüglich des Moduls m allgemein durch x *_m y bezeichnet, wenn es keine Rolle spielt oder aus dem Kontext hervorgeht, ob es sich um genau das Montgomery-Produkt x *_m y des Koprozessors 56 gemäß der ursprünglich gegebenen Definition oder eines der drei abgewandelten Montgomery-Produkte x *'_m y bzw. x *''_m y bzw. x *'''_m y eines der Koprozessoren 56', 56'', 56''' handelt.
Generell kann jede ”normale” modulare Multiplikation x·y = z mod m durch eine Montgomery-Multiplikation x' *_m y' = z' ersetzt werden, wenn die Eingangswerte x, y zunächst mittels je einer Montgomery-Transformation in ihre entsprechenden Montgomery-Repräsentationen x', y' umgewandelt werden und dann der Ergebniswert von seiner Montgomery-Repräsentation x' zum Wert x zurücktransformiert wird. Die Montgomery-Transformation kann beispielsweise durch die Berechnung x' := x·R mod m erfolgen. Bei der Rücktransformation kann das Ergebnis z := z'·R^–1 mod m effizient durch eine Montgomery-Multiplikation mit dem Faktor 1, also durch die Berechnung z := z' *_m 1, bestimmt werden.
Wegen der erforderlichen Hin- und Rücktransformationen ist es in der Regel nicht effizient, eine einzige modulare Multiplikation durch eine Montgomery-Multiplikation zu ersetzen. Wenn aber mehrere Multiplikationen nacheinander ausgeführt werden sollen – wie dies beispielsweise bei einer modularen Potenzierung der Fall ist –, dann können diese Multiplikationen vollständig im Montgomery-Zahlenraum durchgeführt werden. Es ist dann nur eine einzige Hintransformation am Anfang der Berechnungssequenz und eine einzige Rücktransformation am Ende der Berechnungssequenz erforderlich.
Nach dem gerade beschriebenen Prinzip können bei dem in 1 und 2 gezeigten Verfahren einige oder alle modulare Multiplikationen als Montgomery-Multiplikationen implementiert werden. Es versteht sich, dass hierbei Berechnungsabschnitte, die im Montgomery-Zahlenraum erfolgen, möglichst zusammengefasst werden sollten, um die Anzahl der erforderlichen Hin- und Rücktransformationen zu reduzieren. Additionen und Subtraktionen können ohne Unterschied im ”normalen” Zahlenraum und im Montgomery-Zahlenraum ausgeführt werden.
Die Verwendung von Montgomery-Multiplikationen ist besonders vorteilhaft, wenn der Datenträger 50 einen Koprozessor 56, 56', 56'', 56''' aufweist, der zwar die Montgomery-Multiplikation, nicht aber die normale modulare Multiplikation unterstützt. Auch wenn der Koprozessor 56, 56', 56'', 56''' beide Multiplikationsarten unterstützt, wird die Montgomery-Multiplikation häufig effizienter ausgeführt. Je nach der Anzahl der erforderlichen Transformationen – insbesondere der im Vergleich zu den Rücktransformationen aufwendigeren Hintransformationen – ergibt sich eine erhebliche Ersparnis sogar dann, wenn eine Montgomery-Multiplikation nur geringfügig effizienter als eine normale modulare Multiplikation ausgeführt werden sollte.
In den hier beschriebenen Ausführungsbeispielen ist das in 1 und 2 gezeigte Verfahren insbesondere im Hinblick auf die Erzeugung das Kandidatenfeldes in Schritt 46 (2) optimiert. Wie bereits erwähnt, geht die vorliegend beschriebene Lösung von der Grundidee aus, Primzahlkandidaten durch einen Siebvorgang nach dem Prinzip des Siebes des Eratosthenes zu ermitteln. Bei den hier beschriebenen Ausführungsbeispielen beginnt das Sieb jedoch bei einem zufälligen Basiswert b, der bereits ungefähr die Größenordnung der zu ermittelnden Primzahl aufweist, und es enthält Einträge, die jeweils den Werten b + SWi entsprechen (mit Schrittweite SW).
Ferner wird in den hier beschriebenen Ausführungsbeispielen nur eine vorgegebene Anzahl von Siebdurchläufen mit je einer kleinen Primzahl p' oder einem Produkt p' mehrerer Primzahlen als Markierungswerte r, r' durchgeführt. Nach diesen Siebdurchläufen stellen die im Sieb verbleibenden Werte, die als Primzahlkandidaten m bezeichnet werden, nur mit gewisser Wahrscheinlichkeit eine Primzahl dar. Wie bereits erwähnt, wird die Anzahl der Siebdurchläufe im Zuge einer Optimierung der Rechenzeit für das Gesamtverfahren festgelegt. Beispielweise können mehrere Tausend Siebdurchläufe durchgeführt werden, wobei dann eine im Sieb verbliebene Zahl mit einer Wahrscheinlichkeit von ungefähr 2,5% eine Primzahl ist.
Da das Sieb nicht bei Null beginnt, muss für jeden Siebdurchlauf der Rest des Basiswertes b modulo des Markierungswertes p', der als Grundlage für den Siebdurchlauf dient, bestimmt werden. Aus diesem Rest wird dann die erste aus dem Sieb zu löschende zusammengesetzte Zahl b + SWk ermittelt, und ausgehend von dieser Zahl b + SWk werden die weiteren Vielfachen b + SWk + SWp', b + SWk + 2·SWp', b + SWk + 3·SWp', ... aus dem Sieb gelöscht.
Die hier beschriebenen Ausführungsbeispiele betreffen insbesondere die effiziente Bestimmung des gerade genannten Rests z := b mod p'. Grundidee dieser Ausführungsformen ist es, zur Bestimmung des Rests z nicht eine ”normale” modulare Division mit Rest, sondern eine Montgomery-Operation mit mindestens einem weiteren Korrekturschritt zu verwenden. Diese Montgomery-Operation kann insbesondere eine Montgomery-Reduktion mit p' als Modul sein. Unter einer Montgomery-Reduktion wird hier eine Montgomery-Multiplikation verstanden, bei der einer der Faktoren den Wert 1 aufweist.
In einem ersten Ausführungsbeispiel wird angenommen, dass der für den Schleifendurchlauf herangezogene Markierungswert p' – z. B. eine Primzahl eine Breite von d Bit (z. B. 16 Bit) aufweist, und dass die Basis b eine Breite von n·d Bit aufweist. Es wird dann die Montgomery-Reduktion
ausgeführt, die definitionsgemäß den Wert b·1·2^–d·n mod p' liefert. Zum gewünschten Ergebnis von b mod p hat sich somit ein ”Fehler” um den Faktor 2^–d·n mod p' ergeben, der durch einen oder mehrere Korrekturschritte ausgeglichen wird.
Die erforderliche Korrektur kann in beliebiger Weise ausgeführt werden. Im vorliegenden Ausführungsbeispiel ist jedoch vorgesehen, hierfür wieder eine Montgomery-Operation, nämlich eine Montgomery-Multiplikation modulo p' bezüglich des Montgomery-Koeffizienten 2^d, durchzuführen.
Durch diese Montgomery-Multiplikation wird eine weitere Abweichung von dem gewünschten Ergebnis verursacht, nämlich um den zusätzlichen Faktor 2^–d mod p'. Es ist daher vorteilhaft, diesen zusätzlichen Faktor bei der Korrektur bereits zu berücksichtigen, so dass diese Korrektur als Montgomery-Multiplikation des Ergebnisses der Montgomery-Reduktion mit dem Faktor 2^d·2^d·n mod p' = 2^d·(n+1) mod p' durchgeführt wird.
Insgesamt wird somit der Rest b mod p' wie folgt berechnet:
Hierbei kann der Korrekturfaktor 2^{d·(n+1)modp'} in einem besonders einfachen. Verfahren durch eine Schleife bestimmt werden. Ausgehend von einem Startwert 1 wird in dieser Schleife in jedem Schleifendurchlauf der jeweils aktuelle Wert verdoppelt, und es wird p' subtrahiert, falls das Ergebnis mindestens p' beträgt.
Die folgende Darstellung des gerade beschriebenen Verfahrens spiegelt einen beispielhaften Berechnungsablauf genauer wider. Die Darstellung betrifft die allgemeinere Aufgabe, für einen d Bit breiten Wert X in einem Register X und einen (n·d) Bit breiten Wert Y in einem Register Y den Rest Z mit Z := Y mod X in einem Register Z zu bestimmen. Offensichtlich kann das Verfahren leicht zur hier benötigten Ermittlung des Restes z := b mod p' verwendet werden, indem der Markierungswert p' im Register X und die Basis b im Register Y gespeichert werden. Das Verfahren kann jedoch auch in Zusammenhang mit anderen kryptographischen Berechnungen verwendet werden, bei denen ein Rest bestimmt werden muss: Verfahren A

Eingabewerte: d Bit breiter Wert (z. B. Primzahl p') im Register X n·d Bit breiten Wert (z. B. Basis b) im Register Y

Register: B, C, X, Y, Z

Ausgabewert: Rest Y mod X in Register Z

Verfahrensablauf:
Der Vorgang in Zeile (A.1) wird durch eine Montgomery-Multiplikation
ausgeführt, deren Faktoren Y und 1 unterschiedliche Längen aufweisen. Der Vorgang in Zeile (A.3) wird durch eine Montgomery-Multiplikation
mit den Faktoren B und C ausgeführt.
Das allgemeine Verfahren A kann jedoch optimiert werden, wie im Folgenden für die modifizierten Verfahren A' und A'' dargestellt wird.
Ist der Markierungswert eine Primzahl p', so kann die erste Montgomery-Multiplikation entfallen. Verfahren A'

Eingabewerte: d Bit breiter Wert (z. B. Primzahl p') im Register X n·d Bit breiten Wert (z. B. Basis b) im Register Y

Register: C, X, Y, Z

Ausgabewert: Rest Y mod X in Register Z

Verfahrensablauf:
Der Vorgang in Zeile (A'.2) besteht darin, Register C auf den von X abhängigen Korrekturwert zu setzen. Der Vorgang in Zeile (A'3) wird durch eine Montgomery-Multiplikation
ausgeführt, deren Faktoren Y und C unterschiedliche Längen aufweisen.

Wird dagegen ein Markierungslauf gleichzeitig mit zwei (oder mehr) Markierungswerten r und r' durchgeführt, so ist die folgende Ausgestaltung vorteilhaft. Verfahren A'' (beispielhaft für zwei Primzahlen r und r')

Eingabewerte:	d Bit breiter Wert (z. B. Produkt p' = r*r' von Primzahlen rund r') im Register X n·d Bit breiten Wert (z. B. Basis b) im Register Y
Register:	B, C, C', X, X', Y, Z, Z'
Ausgabewerte:	Rest Y mod r in Register Z Rest Y mod r' in Register Z'

Verfahrensablauf:

Der Vorgang in Zeile (A''.1) wird, wie im Verfahren A, durch eine Montgomery-Multiplikation
ausgeführt, deren Faktoren Y und 1 unterschiedliche Längen aufweisen. Der Vorgang in Zeile (A''.3a) und (A''.3b) wird, wie im Verfahren A, durch eine Montgomery-Multiplikation
mit den Faktoren B und C ausgeführt.
Es wird demnach für jeden Markierungswert der Restwert (b MOD r und b MOD r') berechnet, um beide Markierungswerte in einem Markierungslauf aus dem Sieb streichen zu können.
Die modulare Potenzierung in Zeile (A.2), (A'.2) und (A''.2a und 2b) kann, wie bereits oben erwähnt, durch eine Schleife implementiert werden, die in d·(n + 1) Schleifendurchläufen jeweils eine Verdopplung (bitweise Verschiebung um eine Bitposition nach links) und eine bedingte Subtraktion durchführt. In der hier verwendeten Pseudocode-Notation kann also beispielsweise Zeile (A.2) durch die folgenden Zeilen (A.2.1)–(A.2.5) ersetzt werden:
Dadurch, dass die hier beschriebenen Ausführungsbeispiele eine Division mit einem langen Dividenden durch mindestens eine Montgomery-Multiplikation ersetzen, eignen sie sich besonders gut zur Verwendung bei einem Datenträger 50, der lange Divisionen nicht oder weniger effizient als Montgomery-Multiplikationen unterstützt. Diese Konstellation ist bei vielen üblichen Datenträgern 50 gegeben, weil eine effiziente Hardware-Unterstützung für lange Divisionen hohen Aufwand erfordern würde.
So unterstützt beispielsweise der Datenträger 50 mit dem Koprozessor 56'' gar keine Divisionsoperationen, während der Koprozessor 56''' zwar eine Divisionsfunktion bereitstellt, aber ungefähr 128-mal länger zum Ausführen einer Division als für eine Montgomery-Multiplikation gleicher Bitlänge benötigt. Bei dem Datenträger 50 mit dem Koprozessor 50 kann es dagegen sogar vorteilhaft sein, die hier beschriebenen Techniken nicht zu verwenden, weil sich auf dem Hauptprozessor 54 dieses Datenträgers 50 eine schnelle Restwertberechnung modulo einer kleinen Primzahl implementieren lässt.
Es versteht sich, dass die vorliegend beschriebenen Verfahrensschritte in unterschiedlichem Maße auf den Hauptprozessor 54 und den Koprozessor 56, 56', 56'', 56''' des Datenträgers 50 verteilt werden können. So ist es beispielsweise bei dem Datenträger 50 mit dem Koprozessor 56'' vorteilhaft, alle Verfahrensschritte der Zeilen (A.1)–(A.3) von dem Hauptprozessor 54 ausführen zu lassen, weil der Koprozessor 56'' für Montgomery-Multiplikationen mit unterschiedlich langen Faktoren wenig effizient arbeitet und überdies auf Faktoren, deren Absolutbetrag kleiner als der Modul p' ist, beschränkt ist. Bei dem Datenträger 50 mit dem Koprozessor 56''' ist der Hauptprozessor 54 dagegen relativ langsam und unterstützt keine Divisionen, während der Koprozessor 56''' für das hier beschriebene Verfahren sehr gut geeignet ist. Es ist daher vorteilhaft, diesen Koprozessor 56''' für alle Verfahrensschritte der Zeilen (A.1)–(A.3) zu nutzen.
4 zeigt beispielhaft die einzelnen Verfahrensschritte des Erzeugens des Kandidatenfeldes in Schritt 46 (2). Als Eingabewert liegt bereits der Basiswert b vor, der im vorhergehenden Schritt 44 ermittelt wurde. Das Verfahren umfasst eine vorbestimmte Anzahl von Siebdurchlaufen, in denen jeweils die Schritte 72–78 ausgeführt werden.
Zu Beginn jedes Siebdurchlaufs wird in Schritt 72 ein Markierungswert p' bestimmt, dessen Vielfache im Sieb als zusammengesetzte Zahlen markiert werden sollen. In den bislang beschriebenen Ausgestaltungen ist der Markierungswert p' eine kleine Primzahl mit z. B. maximal 16 Bit Länge, während in anderen Ausführungsformen zusammengesetzte Zahlen – beispielsweise Produkte von zwei oder mehr Primzahlen r, r''- als Produkt p' = r*r' für die Primzahlen r und r' als Markierungswerte verwendet werden können.
In Schritt 74 wird dann der Rest des Basiswerts b modulo des Markierungswertes p ermittelt. Hierzu wird z. B. das bereits beschriebene Verfahren A oder eine der im folgenden darzustellenden Abwandlungen ausgeführt. Schritt 74 gemäß 4 umfasst drei Teilschritte 74.1, 74.2 und 74.3. Im ersten Teilschritt 74.1, der der Zeile (A.1) von Verfahren A entspricht, wird die Montgomery-Reduktion
ausgeführt. Der zweite Teilschritt 74.2 entspricht der Zeile (A.2) bzw. den Zeilen (A.2.1)–(A.2.5). Hierbei wird der Korrekturfaktor C berechnet. Im dritten Teilschritt 74.3, der der Zeile (A.3) von Verfahren A entspricht, wird die erforderliche Korrektur des Ergebnisses der Montgomery-Reduktion von Teilschritt 74.1 mittels der Montgomery-Multiplikation
ausgeführt.
Auf Grundlage des Rests b mod p' wird dann in Schritt 76 ein Markierungslauf ausgeführt. Hierzu wird zunächst das erste Bit S[k] im Bitfeld S ermittelt, dessen zugeordneter Wert b + SW·k einem Vielfachen des Markierungswertes p', also einer zusammengesetzten Zahl, entspricht. Dieses Bit S[k] wird entsprechend markiert, also z. B. auf den Wert ”0” gesetzt. Ausgehend von diesem k-ten Bit werden dann der Reihe nach die weiteren Bits im Abstand von p' – also die Bits S[k + p'], S[k + 2·p'], S[k + 3·p'], ... – jeweils auf den Wert gesetzt, der für zusammengesetzte Zahlen steht. Diese Bits entsprechen den Werten b + SWk + SWp', b + SWk + 2·SWp', b + SWk + 3·SWp', und so weiter. Dazwischenliegende Vielfache von p' brauchen nicht berücksichtigt zu werden, weil diese Vielfachen nicht im Bitfeld S repräsentiert werden.
Wie in dem Verfahren A' bereits angedeutet, kann die Montgomery-Reduktion in Schritt 74.1 entfallen, wenn der Markierungswert eine Primzahl ist.
Sollte dagegen – wie in Verfahren A'' angedeutet – p' ein Produkt von (zwei oder mehr) Primzahlen sein, so wird ein Markierungslauf für jede dieser Primzahlen als Markierungswert durchgeführt. Auf einen Schritt 74.1 folgen die Schritte 74.2 und 74.3 für jeden der (beiden) Markierungswerte r, r'. Ausgehend von dem für jeden Markeringswert getrennt bestimmten Rest (b mod r) kann auch Schritt 76 für jeden Markierungswert erfolgen.
Nach dem Ende des Markierungslaufs von Schritt 76 wird in Schritt 78 geprüft, ob ein weiterer Siebdurchlauf erfolgen soll. Ist dies der Fall, so erfolgt ein Rücksprung zu Schritt 72. Andernfalls ist die Erzeugung des Kandidatenfeldes abgeschlossen, und das Verfahren wird mit Schritt 48 (2) fortgesetzt.
In den bisher beschriebenen Ausführungsbeispielen wurde der Korrekturfaktor in Schritt 74.2 – entsprechend Zeile (A.2) bzw. Zeilen (A.2.1)–(A.2.5) durch eine modulare Potenzberechnung mit der Basis 2 bestimmt. Der Erfinder hat erkannt, dass auf den hier behandelten Hardware-Plattformen eine erhebliche Geschwindigkeitssteigerung möglich ist, wenn eine Potenz von ½ statt einer Zweierpotenz berechnet wird; geeignete Verfahren unter Verwendung von Montgomery-Multiplikationen werden unten ausführlich beschrieben. Zunächst wird jedoch angegeben, wie der Korrekturfaktor C im Register C, der in Zeile (A.2) durch C = 2^d·(n+1) mod X angegeben ist, als Potenz von ½ ausgedrückt werden kann.
Zunächst ist zu bemerken, dass die Faktorisierung des Moduls X bekannt ist, weil X z. B. eine Primzahl p' oder – in Ausführungsalternativen – ein Produkt von Primzahlen ist. Damit ist auch der Wert der Euler'schen Totientenfunktion φ(X) bekannt, weil z. B. φ(p') = p' – 1 ist und φ(p₀·p₁) = (p₀ – 1)·(p₁ – 1) für Primzahlen p₀ und p₁ ist. Ferner gilt für alle a, die teilerfremd zu X sind, a^φ(X) = 1 mod X. Daher gilt 2^d·(n+1) mod X = 2^{–(k·φ(X)–d·(n+1))} mod X für ein geeignet gewähltes k. Es kann dann die Berechnung C = 2^d·(n+1) mod X in Zeile (A.2) durch C = (½)^{k·φ(X)–d·(n+1)} mod X ersetzt werden.
Im folgenden werden Verfahren zur effizienten Bestimmung einer positiven Potenz von ½ unter Verwendung von Montgomery-Operationen beschrieben, wie sie für die gerade genannte Berechnung C = (½)^{k·φ(X)–d·(n+1)} mod X eingesetzt werden können. Zum besseren Verständnis wird jedoch zunächst ein Vergleichsverfahren (”Verfahren 1”) dargestellt, das ”normale” modulare Multiplikationen a *_M b := a·b mod M verwendet, um eine Zweierpotenz zu berechnen.
Das Vergleichsverfahren 1 geht von der an sich bekannten Quadriere-und-Multipliziere-Technik aus, bei der für jedes Bit des Exponenten eine Quadrierung eines Zwischenergebnisses und – in Abhängigkeit von dem Wert des Exponentenbits – ferner eine Multiplikation des Zwischenergebnisses mit der zu potenzierenden Basis erfolgt. Diese Quadriere-und-Multipliziere-Technik ist aber potentiell für Nebenkanalangriffe anfällig, wenn sich durch Messung des Stromverbrauchs oder sonstiger Parameter feststellen lässt, ob bei der Verarbeitung eines Bits des Exponenten das Zwischenergebnis verdoppelt – also nach links verschoben – wird oder nicht. Daher wird bei dem Vergleichsverfahren 1 eine modifizierte Technik verwendet, die als ”Quadriere-achtmal-und-Multipliziere-einmal-Technik” bezeichnet werden könnte.
Bei der ”Quadriere-achtmal-und-Multipliziere-einmal-Technik” werden jeweils acht Quadrierungen ausgeführt, aber die dazugehörigen potentiellen Multiplikationen zu je einer einzigen Multiplikation zusammengefasst. Die Exponentenbits für die aufgeschobenen Multiplikationen werden jeweils in einem Byte e_i gesammelt, und die durchgeführte Multiplikation erfolgt dann mit dem Faktor
. Insgesamt lässt sich dieses Verfahren mit der folgenden Pseudocode-Notation beschreiben: Verfahren 1

Eingabewerte: Exponent e = e₀ + e₁·256 + ... + e_n·256ⁿ Modul im Register M

Register: M, X, Y

Ausgabewert: Potenz 2^e mod M in Register Y

Verfahrensablauf:
In der obigen Pseudonotation bedeutet die Schreibweise A *= B mod M, dass der Inhalt des Registers A durch A·B mod M ersetzt wird. Die Register M, X und Y haben jeweils eine Größe von mindestens 256 Bit. Die Werte e_i stellen für 0 ≤ i ≤ n die ”Ziffern” des Exponenten e in einem Stellenwertsystem mit der Basis 256 dar; es gilt also 0 ≤ e_i ≤ 255.
In Zeile (1.1) erfolgt die Initialisierung des Registers Y. Für jedes Byte des Exponenten e wird dann ein Schleifendurchlauf ausgeführt, der jeweils die Zeilen (1.3)–(1.7) umfasst. Hierbei wird in den Zeilen (1.3) und (1.4) der Inhalt des Registers Y achtmal quadriert. In den Zeilen (1.6) und (1.7) erfolgt eine Multiplikation des Zwischenergebnisses im Register Y mit dem Faktor
. Die Potenzberechnungen in den Zeilen (1.1) und (1.6) können effizient dadurch ausgeführt werden, dass z. B. zur Berechnung von A =
zunächst das Register A auf Null gesetzt wird, und dann das (k + 1)-te Bit – gerechnet vom geringstwertigen Bit aus – zu einer ”1” invertiert wird.
Das obige Vergleichsverfahren 1 ist sicher gegen Nebenkanalangriffe, sofern Multiplikationen mit unterschiedlichen Zweierpotenzen durch einen Angreifer nicht unterschieden werden können.
Der Erfinder hat erkannt, dass das gerade beschriebene Vergleichsverfahren 1 so weitergebildet werden kann, dass es Montgomery-Multiplikationen verwendet und somit effizient auf Datenträgern 50 mit geeigneten Koprozessoren 56, 56', 56'', 56''' ausführbar ist. Überraschenderweise ist dies mit relativ geringen Modifikationen des Verfahrensablaufs möglich. Insbesondere wird bei dem weitergebildeten Verfahren, das im folgenden als ”Verfahren 2” bezeichnet wird, eine negative Zweierpotenz als Ergebnis berechnet, also 2^–e = (1/2)^e statt des beim Verfahren 1 berechneten Wertes 2^e. Ferner ist in Verfahren 2 ein zusätzlicher Schritt vorgesehen, in dem der Exponent e geeignet umcodiert wird, um die Verwendung der Montgomery-Operationen statt der ”normalen” modularen Multiplikationen und Quadrierungen in Verfahren 1 auszugleichen.
Ebenso wie bei dem Vergleichsverfahren 1 werden bei Verfahren 2 zwei Register X und Y sowie ein konstantes drittes Register M für den Modul m verwendet. Das Register Y hat dieselbe Größe wie M, während das Register X gegebenenfalls kleiner sein kann. Alle drei Register weisen mindestens 256 Bit auf, und der Modul m beträgt mindestens 2²⁵⁵.
Das Verfahren 2 ist für alle oben genannten Koprozessoren 56, 56', 56'', 56''' verwendbar. Diese Universalität wird dadurch erreicht, dass das Verfahren 2 nur zwei generische Montgomery-Befehle verwendet, die auf allen üblichen Plattformen verfügbar sind. Diese Befehle sind erstens die Montgomery-Quadrierung des Registers Y und zweitens die Montgomery-Multiplikation der Register X und Y. Bei der Montgomery-Quadrierung wird der Wert des Registers Y durch Y *_m,R Y ersetzt. Diese Montgomery-Quadrierung wird im folgenden durch den Pseudocode-Befehl ”SETZE Y *= Y * R^–1 mod M” ausgedrückt, Die Montgomery-Multiplikation, bei der der Wert des Registers Y durch X *_m,R Y ersetzt wird, wird folgenden durch den Pseudocode-Befehl ”SETZE Y *= X * R^–1 mod M” ausgedrückt.
Ferner wird im Verfahren 2 ein Register (entweder X oder Y) der Breite r mit einer Zweierpotenz 2^k mit 0 ≤ k < r initialisiert. Dieser Vorgang wird durch den Pseudocode-Befehl ”SETZE Z = 2^k” ausgedrückt. Das Verfahren 2 lässt sich dann wie folgt beschreiben: Verfahren 2

Eingabewerte: Exponent e = e₀ + e₁·256 + ... + e_n·256ⁿ Modul im Register M

Register: M, X, Y

Ausgabewert: Potenz 2^–e mod M in Register Y

Verfahrensablauf:
Bis auf den vorbereitenden Schritt in Zeile (2.0) entspricht die Struktur des Verfahrens 2 genau der Struktur von Verfahren 1. Nach der Initialisierung des Registers Y in Zeile (2.1) wird wiederum eine Schleife mit den Zeilen (2.3)–(2.7) als Schleifenkörper ausgeführt. In den Zeilen (2.3) und (2.4) wird dabei eine achtmalige Montgomery-Quadrierung des Zwischenergebnisses im Register Y ausgeführt, und in den Zeilen (2.6) und (2.7) erfolgt eine Montgomery-Multiplikation des Registers Y mit dem Faktor
. Die Verfahren 1 und 2 unterscheiden sich also lediglich durch die Umcodierung des Exponenten in Schritt (2.0) und dadurch, dass Montgomery-Multiplikationen und -Quadrierungen statt normaler modularer Multiplikationen und Quadrierungen verwendet werden.
In einer Abwandlung des oben beschriebenen Verfahrens 2 können die beiden Zeilen (2.6) und (2.7) zu einem einzigen Befehl zusammengefasst werden, in dem der Wert des Registers Y durch das Produkt
ersetzt wird; hierbei ist n' der binäre Logarithmus des Montgomery-Parameters R, so dass R = 2^n' gilt. In der hier verwendeten Pseudonotation könnte dieser zusammengefasste Befehl mit ”SETZE
” ausgedrückt werden.
Das Ergebnis des Verfahrens 2 kann für manche der hier behandelten Koprozessoren 56, 56', 56'', 56''' gegebenenfalls um ein kleines Vielfaches des Moduls M von dem gewünschten Endergebnis 2^–e mod M abweichen. Es kann daher erforderlich sein, als abschließenden Korrekturschritt eine modulare Reduktion des Registers Y modulo M auszuführen.

Im hier beschriebenen Ausführungsbeispiel erfolgt die Umcodierung des Exponenten e in Zeile (2.0) gemäß dem folgenden Verfahren: Verfahren 3

Eingabewerte:	Exponent e = e₀ + e₁·256 + ... + e_n·256ⁿ Logarithmus n' des Montgomery-Parameters R zur Basis 2 (es gilt also R = 2^n')
Ausgabewert:	Umcodierter Exponent f = f₀ + f₁·256 + ... + f_n·256ⁿ zur Verwendung in Verfahren 2

Verfahrensablauf:

Durch die folgende Argumentation lässt sich veranschaulichen, dass das Verfahren 2 mit der Umcodierung des Exponenten e gemäß Verfahren 3 das korrekte Ergebnis liefert: Zunächst ist zu bemerken, dass während des Verfahrensablaufs alle Werte in den Registern X und Y stets modulare Zweierpotenzen (mit Modul M) sind, weil die Register mit Zweierpotenzen initialisiert werden, und weil die Montgomery-Operationen als modulare Multiplikationen mit (gegebenenfalls negativen) Zweierpotenzen als Faktoren geschrieben werden können. Die ausgeführten Berechnungen können daher übersichtlicher in Form ihrer Logarithmen zur Basis 2 bezüglich des Moduls M geschrieben werden.
Für Y = 2^y und R = 2^n' lässt sich die Montgomery-Quadrierung in Zeile (2.4) als Verdopplung und Subtraktion schreiben, bei der y durch 2·y – n' ersetzt wird (Operation ”S”). Die kombinierte Operation aus den Zeilen (2.7) und (2.8), die auf Registerebene als ”SETZE Y *= 2^k * 2^–n' mod M” geschrieben werden kann, ersetzt in der logarithmischen Darstellung y durch y + k – n' (Operation ”M_k”).
In Verfahren 2 wird die Operation S jeweils achtmal ausgeführt und dann die kombinierte Operation M_k einmal ausgeführt. In der logarithmischen Schreibweise lässt sich dieser Verfahrensablauf wie folgt darstellen: y →s 2·y – n' →s 4·y – 3·n' →s 8·y – 7·n' →s ... ... →s 256·y – 255·n' →M_k 256·(y – n') + k
Um eine geeignete Umcodierung des Exponenten e darzustellen, müssen die Bytes f_n, f_n–1, ..., f₀ des umcodierten Exponenten f die Eigenschaft aufweisen, dass die im folgenden definierte Sequenz y_n, y_n-1, ..., y₀ das Ergebnis y₀ = –e ergibt; die Hintereinanderschaltung von Funktionen wird durch das Symbol ”o” ausgedrückt:
Es lässt sich durch Induktion über n zeigen, dass die in Verfahren 3 definierte Umcodierung die gerade genannte Eigenschaft aufweist und somit zu einem korrekten Ergebnis des Verfahrens 2 führt.
5 veranschaulicht einen beispielhaften Ablauf der gerade beschriebenen Verfahren 2 und 3. In Schritt 80 erfolgt die Umcodierung des Exponenten e gemäß Verfahren 3, um aus dem ursprünglichen Exponenten e mit seien Bitgruppen 82 – hier die Bytes e_n, e_n-1, ..., e₀ – den umcodierten Exponenten f mit seinen Bitgruppen 84 – hier die Bytes f_n, f_n-1, ..., f₀ – zu erhalten.
Der auf die Umcodierung in Schritt 80 folgende Verfahrensablauf lässt sich in eine Initialisierung 86 und n Abschnitte 88 unterteilen. Im Zuge der Initialisierung 86 wird in Schritt 90 der Befehl ”SETZE
” gemäß Zeile (2.1) des Verfahrens 2 ausgeführt. Jeder der n Abschnitte 88 entspricht je einem Schleifendurchlauf des Verfahrens 2 und ist je einer der Bitgruppen 84 des umcodierten Exponenten f zugeordnet.
Jeder Abschnitt 88 weist drei wesentliche Schritte 92, 94 und 96 auf. In Schritt 92 werden gemäß den Zeilen (2.3) und (2.4) von Verfahren 2 acht Montgomery-Quadrierungen des im Register Y enthaltenen Zwischenergebnisses ausgeführt. In Schritt 94, der der Zeile (2.6) entspricht, wird im Register X eine Zweierpotenz mit einem Exponenten gespeichert, der durch die zugeordnete Bitgruppe 84 des umcodierten Exponenten f gebildet wird. Dieser Schritt 94 lässt sich effizient dadurch implementieren, dass das Register X zunächst gelöscht wird und dann das eine Bit, dessen Bitposition durch die zugeordnete Bitgruppe 84 angegeben wird, auf den Wert ”1” gesetzt wird. Schritt 96 entspricht Zeile (2.7) von Verfahren 2 und beinhaltet eine Montgomery-Multiplikation der Register Y und X.
Nachdem insgesamt n Abschnitte 88 ausgeführt worden sind, liegt – nach einer gegebenenfalls noch erforderlichen Korrektur durch eine modulare Reduktion in Schritt 98 – das gewünschte Endergebnis 2^–e mod M in Register Y vor.
Im folgenden werden einige optionale Verfeinerungen und Weiterentwicklungen der bisher beschriebenen Verfahren 2 und 3 dargestellt. In unterschiedlichen Ausführungsalternativen können unterschiedliche Kombinationen dieser Verfeinerungen und Weiterentwicklungen genutzt werden, um beispielsweise die eingesetzten Verfahren besonders gut an bestimmte Montgomery-Koprozessoren 56, 56', 56'', 56''' anzupassen oder um die Ausspähungssicherheit weiter zu erhöhen.
Zunächst wird auf die potentielle Schwierigkeit bei der Exponenten-Umcodierung gemäß Verfahren 3 eingegangen, dass für f_n ein Wert größer als 255 auftreten kann. Für ein kleines e_n ist dann möglicherweise der in Schritt (2.1) von Verfahren 2 bestimmte Wert
größer als der Modul m und damit zu groß, um als Initialwert in dem Register Y gespeichert zu werden. Allerdings kann bei allen hier behandelten Montgomery-Koprozessoren 56, 56', 56'', 56''' die Registergröße für den Modul m so gewählt werden, dass für den jeweiligen Montgomery-Koeffizienten n' die Ungleichung 2^(4/5)·n' < m < 2^n' erfüllt ist. Die Bedingung
kann dann für ein sehr kleines ε > 0 wie folgt verstärkt werden: f_n = n'·(256/255)·(1 – ε) – e_n ∊ [0, (4/5)·n']
Die gerade genannte Bedingung ist auf jeden Fall erfüllt, wenn die Ungleichung ¼·n' < e_n < n', die im folgenden mit (*) bezeichnet wird, gilt.
Falls Verfahren 3 einen zu großen Wert für f_n ergibt, kann dieser Wert vor Schritt 90 von 5 mit dem Modul m modular reduziert werden, so dass dann in Schritt 90 das Register Y auf den sich ergebenden Rest gesetzt wird. Für sehr kleine e_n (e_n < n'/256) ist es auch möglich, den n-ten Abschnitt 82 in den (n – 1)-ten Abschnitt 82 aufzunehmen. In diesem Fall wird n um 1 verringert, und e_n–1 wird um e_n·256 erhöht. Ferner kann in manchen Ausgestaltungen vorgesehen sein, den Wert des Exponenten e so zu setzen, dass f_n hinreichend klein bleibt.
Zusammenfassend kann also die Berechnung des Korrekturfaktors C in Schritt 74.2 (4) durch das folgende Verfahren B erfolgen: Verfahren B

Eingabewerte: d Bit breiter Wert (z. B. Primzahl p') im Register X n·d Bit breiten Wert (z. B. Basis b) im Register Y

Register: B, C, X, Y, Z

Ausgabewert: Rest Y mod X in Register Z

Verfahrensablauf:
Die Zeilen (B.1) und (B.3) entsprechen den Zeilen (A.1) und (A.3) des Verfahrens A und beinhalten je eine Montgomery-Multiplikation. In Zeile (B.2) werden die oben beschriebenen Verfahren 2 und 3 zur modularen Potenzberechnung zur Basis ½ ausgeführt. Hierbei wird der Wert k so ausgewählt, dass der Exponent k·φ(X) – d·(n + 1) positiv ist, und dass die Ungleichung (*) erfüllt ist. In vielen Ausführungsformen weisen der Modul X und die Exponenten jeweils eine Länge von höchstens 16 Bit auf, so dass zur Berechnung des Korrekturfaktors in Zeile (B.2) 16 Montgomery-Quadrierungen und 4 Montgomery-Multiplikationen ausreichen.
Im folgenden wird eine weiter optimierte Abwandlung des gerade dargestellten Verfahrens B beschrieben, die sich besonders gut zur Ausführung durch den Koprozessor 56''' eignet. Bei Datenträgern 50 mit einem Koprozessor 56'' kann das Verfahren mit geringfügigen Modifikationen durch den Hauptprozessor 54 ausgeführt werden.
Das im folgenden beschriebene Verfahren ist sowohl hinsichtlich seiner Ausführungsgeschwindigkeit als auch hinsichtlich seiner Ausspähungssicherheit optimiert. Im Hinblick auf die Ausspähungssicherheit besteht nämlich eine potentielle Angriffsmöglichkeit aufgrund der Tatsache, dass der Rest zum Basiswert b des Siebes modulo vieler kleiner Primzahlen berechnet wird. Ein Angreifer könnte theoretisch die Stromverlaufskurve – oder andere Nebenkanalinformationen – dieser modularen Reduktionen ermitteln und für einen Nebenkanalangriff auswerten, bei dem das höchste bzw. niedrigste Wort des Basiswertes b geraten wird und dann Daten über den Beginn jeder Reduktion ausgespäht werden.
Um derartige Angriffe abzuwehren, ist in manchen Ausführungsbeispielen – wie z. B. in dem folgenden Verfahren – vorgesehen, die Montgomery-Reduktionen nicht modulo je einer Primzahl, sondern modulo je eines Paares von Primzahlen durchzuführen. Als positiver Nebeneffekt wird dadurch auch der Siebvorgang beschleunigt, weil nur halb so viele zeitaufwändige lange Reduktionen durchgeführt zu werden brauchen. In weiteren Abwandlungen können auch Tupel mit mehr als zwei Primzahlen verwendet werden.
Für das folgende Verfahren seien p₀ und p₁ je eine kleine Primzahl, und m = p₀·p₁ sei das Produkt dieses Primzahlpaars. Zunächst wird die Montgomery-Reduktion des Basiswertes b modulo dieses Primzahlprodukts m ausgeführt, wie dies Schritt 74.1 in 4 oder Zeile (A.1) in Verfahren A entspricht. Es wird also durch eine Montgomery-Multiplikation ein Wert r mit der folgenden Eigenschaft berechnet: r = b *_m 1 = b·R^–1 mod m
Der Montgomery-Koeffizient R beträgt hierbei 2^128·t, wobei die kleinstmögliche Registergröße 128·t gewählt wird, die ausreicht, um den Basiswert b aufzunehmen. Es wird vorliegend angenommen, dass die Register, in denen die Faktoren b und 1 der Montgomery-Reduktion gespeichert sind, jeweils 128 Bit lang sind.

Für jeder der beiden Primzahlen p₀ und p₁ werden nun die folgenden Schritte (Verfahren C) ausgeführt, um den Rest b mod p' aus dem Zwischenergebnis r zu erhalten. Bei der ersten Ausführung des Verfahrens C wird also p' = p₀ gesetzt, und bei der zweiten Ausführung p' = p₁. Das Verfahren C entspricht somit den Schritten 74.2 und 74.3 in 4 beziehungsweise den Zeilen (A.2) und (A.3) des Verfahrens A: Verfahren C

Eingabewerte:	d Bit breiter zusammengesetzter Wert m Primzahl p' mit p' < 2¹⁴, die m teilt Wert r = b·2^–d·n mod m wie oben angegeben
Register:	A, B, F, R, X, Y
Ausgabewert:	Rest b mod p' in Register R

Verfahrensablauf:

In dem oben beschriebenen Verfahren stellt X >> n die bitweise Verschiebung des Registers bzw. der Konstanten X um n Bitpositionen nach rechts dar, und X << n stellt die entsprechende Verschiebung nach links dar.
In den Zeilen (C.1)–(C.6) wird ein geeigneter Korrekturfaktor-Exponent f im Register F berechnet, der eine Form wie in Zeile (B.2) hat, aber zusätzlich wie in Verfahren 3 umcodiert ist. Hierbei wird zunächst in den Zeilen (C.1) und (C.2) die 16-Bit-Ganzzahl im Register X verdoppelt, bis sie negativ ist. Dann wird in Zeile (C.3) ein Wert zwischen 2 und 33 zum höherwertigen Byte von –X addiert, wobei X der im Register X enthaltene Wert ist. In den Zeilen (C.4) und (C.5) wird das Zwischenergebnis korrigiert, wenn es zu groß ist. Schließlich wird in Zeile (C.6) der Korrekturfaktor-Exponent f in Register F durch eine Halbierung des Zwischenergebnisses im Register Y berechnet.
In den Zeilen (C.7)–(C.14) wird der Korrekturfaktor im Register R mit Schritten ähnlich wie im Verfahren 2 berechnet. Wegen der Voraussetzung p' < 2¹⁴ sind die maximal erforderlichen beiden Schleifendurchläufe des Verfahrens 2 hier ”aufgerollt”. Genauer entsprechen die Zeilen (C.7)–(C.9) einer ersten Montgomery-Multiplikation wie in Zeile (2.7) von Verfahren 2, die Zeilen (C.10)–(C.12) entsprechen einer 7-maligen Montgomery-Quadrierung, und die Zeilen (C.13) und (C.14) entsprechen einer zweiten Montgomery-Multiplikation wie in Zeile (2.7) von Verfahren 2. Wenn in einer Ausführungsalternative größere Primzahlen p' auftreten können, so kann das Verfahren C geeignet abgewandelt werden, indem entsprechend viele weitere Schleifendurchläufe des Verfahrens 2 aufgenommen werden. Beispielsweise kann vorgesehen dass, dass weitere 7 Montgomery-Quadrierungen und eine weitere Montgomery-Multiplikation ausgeführt werden.
In den Zeilen (C.15) und (C.16) wird schließlich der Korrekturfaktor, der nach Ausführung der Zeile (C.14) in Register R enthalten ist, auf das Ergebnis r der Montgomery-Reduktion angewendet. Insgesamt entsprechen somit die Zeilen (C1)–(C.15) von Verfahren C dem Teilschritt 74.2 in 4, während die Zeilen (C.15) und (C.16) dem Teilschritt 74.3 entsprechen.
Es versteht sich, dass die hier beschriebenen Ausgestaltungen einer effizienten Restberechnung und einer Bestimmung von Primzahlkandidaten nicht auf den Verfahrensablauf gemäß 1 und 2 beschränkt sind, sondern dass sie in Ausführungsalternativen auch für andere Anwendungszwecke, insbesondere auf dem Gebiet der Kryptographie zur Ausführung durch einen oder mehrere Prozessoren, vorgesehen sein können. Ferner versteht sich, dass die hier beschriebenen Ausführungsformen und Ausführungsvarianten lediglich als Beispiele zu sehen sind. Weitere Abwandlungen und Kombinationen der hier beschriebenen Merkmale sind für den Fachmann unmittelbar ersichtlich.
ZITATE ENTHALTEN IN DER BESCHREIBUNG
Diese Liste der vom Anmelder aufgeführten Dokumente wurde automatisiert erzeugt und ist ausschließlich zur besseren Information des Lesers aufgenommen. Die Liste ist nicht Bestandteil der deutschen Patent- bzw. Gebrauchsmusteranmeldung. Das DPMA übernimmt keinerlei Haftung für etwaige Fehler oder Auslassungen.
Zitierte Patentliteratur

US 4405829 [0002]
DE 102004044453 A1 [0004]
EP 1564649 A2 [0004]
WO 2004/032411 A1 [0006]

Zitierte Nicht-Patentliteratur

”Modular multiplication without trial division” von Peter L. Montgomery, erschienen in Mathematics of Computation, Vol. 44, Nr. 170, April 1985, Seiten 519–521 [0007]
”Probabilistic algorithms for testing primality” von Michael O. Rabin, erschienen im Journal of Number Theory 12, 1980, Seiten 128–138 [0034]

Claims

Verfahren zum Bestimmen des Divisionsrests eines ersten Wertes (b) modulo eines zweiten Wertes (p') für eine kryptographische Anwendung, wobei das Verfahren durch mindestens einen Prozessor (54, 56, 56', 56'', 56''') ausgeführt wird und beinhaltet: – Ausführen (74.1) einer Montgomery-Multiplikation mit dem ersten Wert (b) als einem der Faktoren und dem zweiten Wert (p') als Modul, – Bestimmen (74.2) eines Korrekturfaktors, wobei in einer korrigierenden Montgomery-Multiplikation der Korrekturfaktor als Faktor verwendet wird, um den Divisionsrest des ersten Wertes (b) modulo des zweiten Wertes (p') zu erhalten.
Verfahren nach Anspruch 1 dadurch gekennzeichnet, dass das Ausführen der Montgomery-Multiplikation mit dem ersten Wert (b) als einem der Faktoren und dem zweiten Wert (p') als Modul, eine erste Montgomery-Multiplikation ist und durch – Ausführen (74.3) einer zweiten Montgomery-Multiplikation, als die korrigierende Montgomery-Multiplikation, mit dem Ergebnis der ersten Montgomery-Multiplikation als einem der Faktoren und dem Korrekturfaktor als dem anderen Faktor und dem zweiten Wert (p') als Modul, um den Divisionsrest des ersten Wertes (b) modulo des zweiten Wertes (p') zu erhalten.
Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass die erste Montgomery-Multiplikation eine Montgomery-Reduktion ist.
Verfahren nach Anspruch 2 oder 3 dadurch gekennzeichnet, dass der Korrekturfaktor nach der ersten Montgomery-Multiplikation für die zweite Montgomery-Multiplikation bestimmt wird.
Verfahren nach einem der Ansprüche 2 bis 4, dadurch gekennzeichnet, dass der Korrekturfaktor zum Ausgleich des durch die erste und die zweite Montgomery-Multiplikation hervorgerufenen Fehlers dient.
Verfahren nach einem der Ansprüche 2 bis 5, dadurch gekennzeichnet, dass die erste und die zweite Montgomery-Multiplikation mit unterschiedlichen Montgomery-Koeffizienten ausgeführt werden.
Verfahren nach Anspruch 1 dadurch gekennzeichnet, dass die ausgeführte Montgomery-Multiplikation mit dem ersten Wert (b) als einem der Faktoren und dem zweiten Wert (p') als Modul, die korrigierende Montgomery-Multiplikation ist, welche den Korrekturfaktor als den anderen Faktor verwendet.
Verfahren nach Anspruch 4 und 7 dadurch gekennzeichnet, dass falls der zweite Wert (p') ein Produkt von Primzahlen ist das Verfahren nach Anspruch 4 gestaltet wird und ansonsten das Verfahren nach Anspruch 7 gestaltet wird.
Verfahren nach einem der Ansprüche 1 bis 8, dadurch gekennzeichnet, dass der Korrekturfaktor als modulare Zweierpotenz in mehreren Schleifendurchläufen berechnet wird, wobei jeder Schleifendurchlauf eine Verdopplung eines Zwischenergebnisses und eine bedingte Subtraktion aufweist.
Verfahren nach einem der Ansprüche 1 bis 9, dadurch gekennzeichnet, dass der Korrekturfaktor als modulare Potenz mit einem positiven und ganzzahligen Korrekturfaktor-Exponenten und der Basis ½ berechnet wird.
Verfahren nach Anspruch 10, dadurch gekennzeichnet, dass die Berechnung des Korrekturfaktors eine Folge von mehreren Montgomery-Quadrierungen eines Zwischenergebnisses aufweist, nach denen eine Montgomery-Multiplikation des Zwischenergebnisses mit einem von dem Korrekturfaktor-Exponenten abhängigen Faktor ausgeführt wird.
Verfahren zum Ermitteln von Primzahlkandidaten, die mit einer bestimmten Wahrscheinlichkeit Primzahlen darstellen, für eine kryptographische Anwendung, wobei das Verfahren durch mindestens einen Prozessor (54, 56, 56', 56'', 56''') ausgeführt wird und beinhaltet: – Bestimmen (44) eines Basiswertes (b) für ein Sieb, und – Ausführen mehrerer Siebdurchläufe, bei denen jeweils ein Markierungswert (p'; r, r') ermittelt wird (72) und Vielfache des Markierungswertes (p'; r, r') in dem Sieb als zusammengesetzte Zahlen markiert werden, wobei bei jedem Siebdurchlauf ein Divisionsrest des Basiswertes (b) modulo des Markierungswertes (p'; r, r') mit einem Restbestimmungsverfahren bestimmt wird (74), das mindestens eine Montgomery-Operation umfasst.
Verfahren nach Anspruch 12, dadurch gekennzeichnet, dass der Markierungswert (p'; r, r') eine Primzahl ist.
Verfahren nach Anspruch 12 oder 13, dadurch gekennzeichnet, dass das Sieb durch ein Bitfeld (S) repräsentiert wird, dessen Bits (S[i]) Werten entsprechen, die, ausgehend von dem Basiswert (b), eine vorbestimmte Schrittweite aufweisen, die größer gleich oder größer als 2 ist.
Verfahren nach einem der Ansprüche 12 bis 14, dadurch gekennzeichnet, dass jeder ermittelte Primzahlkandidat mindestens einem probabilistischen Primzahltest (12, 20, 28, 34, 38) unter zogen wird.
Verfahren nach einem der Ansprüche 12 bis 15, dadurch gekennzeichnet, dass als das Restbestimmungsverfahren ein Verfahren nach einem der Ansprüche 1 bis 11 verwendet wird.
Verfahren nach Anspruch 16, dadurch gekennzeichnet, dass in einem der Siebdurchläufe: – die erste Montgomery-Operation für ein Produkt (p') von Markierungswerten (r, r') ausgeführt wird, – die zweite Montgomery-Operation jeweils für die Markierungswerte (r, r') ausgeführt wird und – jeweils die Vielfachen der Markierungswerte (r, r') markiert werden.
Verfahren nach einem der Ansprüche 1 bis 17, dadurch gekennzeichnet, dass das Verfahren zur Bestimmung mindestens eines Parameters eines RSA-Schlüssels oder eines RSA-CRT-Schlüssels dient.
Computerprogrammprodukt mit einer Vielzahl von Programmbefehlen, die mindestens einen Prozessor (54, 56, 56', 56'', 56'''), insbesondere mindestens einen Prozessor (54, 56, 56', 56'', 56''') eines tragbaren Datenträgers (50), dazu veranlassen, ein Verfahren nach einem der Ansprüche 1 bis 18 auszuführen.
Vorrichtung, insbesondere tragbarer Datenträger (50), mit mindestens einem Prozessor (54, 56, 56', 56'', 56''') und mindestens einem Speicher (60, 64, 66, 68), wobei die Vorrichtung dazu eingerichtet ist, ein Verfahren nach einem der Ansprüche 1 bis 18 auszuführen.