DE60109805T2

DE60109805T2 - Verfahren und system zur benützung eines ungesicherten krypto-beschleunigers

Info

Publication number: DE60109805T2
Application number: DE60109805T
Authority: DE
Inventors: Paul Dent; Michael Kornby; Ben Smeets
Original assignee: Ericsson Inc
Current assignee: Ericsson Inc
Priority date: 2000-10-25
Filing date: 2001-09-24
Publication date: 2006-05-04
Anticipated expiration: 2021-09-25
Also published as: US6769062B1; AU2002211260A1; EP1330702A2; WO2002035341A2; WO2002035341A3; JP2004512570A; DE60109805D1; EP1330702B1; ATE292301T1

Description

HINTERGRUND DER ERFINDUNG
Die vorliegende Erfindung betrifft kryptografische Verfahren und insbesondere ein Verfahren und ein System zum Verwenden sicherer und nicht-sicherer Prozessoren, um kryptografische Berechnungen durchzuführen, während die Sicherheit privater Daten auf recht erhalten wird.
Das Internet hat sich von einem Netz, das primär zum Austausch von Information verwendet wird, zu einem Kommunikationsmedium entwickelt, das für geschäftliche und kommerzielle Transaktionen verwendet wird. Diese Entwicklung des Internets zu einem Kommunikationsmedium für geschäftliche und konventionelle Transaktionen hat zu der Erfordernis geführt, Kommunikationen über öffentliche Netze sicher auszuführen. Eine Verschlüsselungstechnologie wird üblicherweise verwendet, um sichere Kommunikationen über unsichere Netze, wie etwa das Internet, aufrecht zu erhalten. Zusätzlich hat der Zuwachs eines E-Handels zu einer Erfordernis nach Authentifizierungsverfahren für Fern-Log-in und eine Dokumentenverifikation geführt.
Eine Verschlüsselungstechnologie mit öffentlichem Schlüssel stellt sowohl eine Sicherheit als auch eine Authentifizierungsfähigkeit bereit. Bei Kryptosystemen mit öffentlichem Schlüssel hält jeder Benutzer ein angepasstes Paar von Schlüsseln, die einen privaten Schlüssel und einen öffentlichen Schlüssel einschließen. Der private Schlüssel und der öffentliche Schlüssel bilden ein einzigartiges, angepasstes Paar. Dokumente oder Kommunikationen, die mit einem privaten Schlüssel verschlüsselt sind, können nur mit dem angepassten öffentlichen Schlüssel entschlüsselt werden, und umgekehrt. Der öffentliche Schlüssel kann öffentlich offenbart werden und kann von jedermann verwendet werden, um Kommunikationen, die für den Besitzer des öffentlichen Schlüssels vorgesehen sind, zu verschlüsseln. Der private Schlüssel wird geheim gehalten. Somit kann eine Kommunikation, die mit dem öffentlichen Schlüssel verschlüsselt ist, nur von dem Besitzer des angepassten privaten Schlüssels entschlüsselt werden.
Verschlüsselungsverfahren mit öffentlichem Schlüssel können auch verwendet werden, um digitale Signaturen für elektronische Dokumente und Kommunikationen zu schaffen. Diese digitale Signatur kann verwendet werden, Dokumente zu verifizieren. Eine Person kann ein elektronisches Dokument oder eine Kommunikation durch ein verschlüsseltes Dokument zur Kommunikation mit seinem oder ihrem privaten Schlüssel unterzeichnen. Ein unterzeichnetes Dokument kann dann durch ein Entschlüsseln des unterzeichneten Dokuments mit dem angepassten öffentlichen Schlüssel verifiziert werden. Wenn das Dokument oder die Kommunikation unter Verwendung des angepassten öffentlichen Schlüssels erfolgreich entschlüsselt wird, kann nur der Besitzer des privaten Schlüssels die Nachricht gesendet haben.
Um die Integrität von kommerziellen Transaktionen herzustellen und einen Betrug zu verhindern, ist es notwendig, dass die Benutzer ihren privaten Schlüssel geheim halten. Jedermann, der Zugriff auf den privaten Schlüssel eines Benutzers hat, kann sich als dieser Benutzer mit einer vollständigen Anonymität ausgeben. Somit wird die weit verbreitete Verwendung digitaler Signaturen für elektronischen Handel und andere Anwendungen eine Technologie für eine sichere Speicherung privater Schlüssel erfordern.
Es ist bekannt, private Schlüssel gegen Eingriff einer gesicherten Hardware-Vorrichtungen, wie etwa einer entnehmbaren Smart-Card zu speichern. Die Zertifikate des privaten Schlüssels und des öffentlichen Schlüssels des Benutzers werden in den Speicher der Smart-Card geschrieben. Um die Smart-Card zu verwenden, führt der Benutzer die Smart-Card in einen Kartenleser ein, der mit einer Host-Vorrichtung verbunden ist, und gibt dann ein ID/Passwort ein, um die Smart-Card zu aktivieren. Wenn das korrekte ID/Passwort eingegeben ist, gibt der Prozessor auf der Karte den privaten Schlüssel zur Verwendung durch die Host-Vorrichtung frei. Wenn ein inkorrektes ID/Passwort eine vorbestimmte Anzahl aufeinanderfolgender Versuche eingegeben wird, sperrt sich die Smart-Card permanent. Manche intelligente Smart-Cards (oft als Kryptokarten bezeichnet) können kryptografische Betriebsschritte durchführen, so dass der private Schlüssel nicht aus ihrer gegen Eingriffe gesicherten Umgebung ausgegeben werden muss. Die Bytes, die zu verarbeiten sind, werden in die Smart-Card durch die Host-Vorrichtung eingegeben und von der Smart-Card verarbeitet. Nur das Ergebnis wird aus der Smart-Card zu der Host-Vorrichtung ausgegeben.
Ein Verfahren und ein Gerät zum Sichern kryptografischer Vorrichtungen gegenüber Angriffen, die ein externe Überwachung und eine Analyse einschließen, ist in der internationalen Patentanmeldung WO 99 35782 A offenbart.
KURZE ZUSAMMENFASSUNG DER ERFINDUNG
Die vorliegende Erfindung ist auf ein Verfahren und ein System zum Verwenden sicherer und nicht-sicherer Vorrichtungen zum Durchführen kryptografischer Berechnungen, wie etwa einer Verschlüsselung und einer Entschlüsselung von Nachrichten gerichtet, ohne eine geheime Information zu offenbaren. Zumindest ein Abschnitt einer geheimen Information wird innerhalb der sicheren Vorrichtung gehalten. Die sichere Vorrichtung ist nicht durch irgendeine praktische Einrichtung von dem offenbarten Teil der Geheiminformation aufdeckbar.
Eine Ausführungsform schließt ein Verfahren ein, wie es in dem unabhängigen Anspruch 1 definiert ist. Der Chiffre-Schlüssel ist in zwei Partialwerte geteilt, die hierin als der modifizierte Chiffre-Schlüssel und der Indikator bezeichnet werden. Der modifizierte Chiffre-Schlüssel wird dann zu einem externen Prozessor ausgegeben. Der modifizierte Chiffre-Schlüssel kann zufallsmäßig durch ein Ändern ausgewählter Bits des Chiffre-Schlüssels erzeugt werden. Ein Indikator, der dem modifizierten Chiffre-Schlüssel entspricht, wird auch erzeugt und schließt eine Mehrzahl von Indikatorbits ein. Der Indikator ist eine Bitkette, welche, wenn sie dem modifizierten Chiffre-Schlüssel hinzugefügt wird, den ursprünglichen Chiffre-Schlüssel erzeugt. Ein erstes Produkt wird von dem unsicheren Prozessor berechnet und ist eine Funktion der Bitkette und des modifizierten Chiffre-Schlüssels. Ein zweites Produkt wird innerhalb des sicheren Prozessors berechnet und ist eine Funktion der Bitkette und des Indikators. Ein Endprodukt wird innerhalb des sicheren Prozessors durch ein Kombinieren des ersten und des zweiten Produkts berechnet.
Eine zweite Ausführungsform der vorliegenden Erfindung, wie sie in dem unabhängigen Anspruch 6 definiert ist, teilt den Chiffre-Schlüssel in drei Partialwerte, die hierin als der kurze Teil, der modifizierte lange Teil und der Indikator bezeichnet werden. Der unsichere Schlüssel berechnet ein erstes Produkt, das mit einem zweiten Produkt kombiniert wird, das von dem sicheren Prozessor berechnet wird. Das erste Produkt ist eine Funktion eines dritten Produkts, das von dem sicheren Prozessor berechnet wird, und eines vierten Produkts. Der sichere Prozessor berechnet zunächst das dritte Produkt und gibt das Ergebnis zu dem unsicheren Prozessor aus. Das dritte Produkt ist eine Funktion der Bitkette und des kurzen Teils des Chiffre-Schlüssels. Das vierte Produkt ist eine Funktion der Bitkette und des modifizierten langen Teils des Chiffre-Schlüssels. Der unsichere Prozessor modifiziert das dritte Produkt mit einem vierten Produkt, um das erste Produkt zu erhalten. Das erste Produkt wird dann in dem sicheren Prozessor eingegeben, der ein zweites Produkt berechnet und das zweite Produkt mit dem ersten Produkt kombiniert, um das Endprodukt zu erhalten. Das zweite Produkt ist eine Funktion der Bitkette und des Indikators.
Ein weiterer Aspekt der Erfindung ist eine Berechnungsvorrichtung, wie in dem unabhängigen Anspruch 12 definiert.
Weitere Ausführungsformen der Erfindung sind in den angehängten abhängigen Ansprüchen spezifiziert.
KURZE BESCHREIBUNG DER ZEICHNUNGEN
In den Zeichnungen zeigen:
1 ein schematisches Diagramm, das ein Kommunikationsterminal gemäß der vorliegenden Erfindung zum Kommunizieren über einen unsicheren Kommunikationskanal veranschaulicht;
2 ein schematisches Diagramm eines Sicherheitsmoduls, das in dem Kommunikationsterminal der 1 verwendet wird;
3 ein Funktionsblockdiagramm, das die Verarbeitung veranschaulicht, die von dem unsicheren Prozessor und dem sicheren Prozessor durchgeführt wird;
4 ein Flussdiagramm, das ein Verfahren zum Durchführen kryptografischer Berechnungen gemäß eine Ausführungsform der vorliegenden Erfindung veranschaulicht;
5 ein Diagramm, das eine beispielhafte Berechnung gemäß der vorliegenden Erfindung veranschaulicht; und
6 ein Flussdiagramm, das ein alternatives Verfahren zum Durchführen kryptografischer Berechnungen gemäß einer zweiten Ausführungsform der vorliegenden Erfindung veranschaulicht;
7 ein Diagramm, das eine beispielhafte Berechnung gemäß der zweiten Ausführungsform veranschaulicht.
DETAILLIERTE BESCHREIBUNG DER ERFINDUNG
Unter Bezugnahme nun auf die Zeichnungen zeigt 1 ein Kommunikationsterminal 10 zum Senden und Empfangen verschlüsselter Nachrichten über einen unsicheren Kommunikationskanal 14. Der Ausdruck "Kommunikationskanal", wie er hierin verwendet wird, bezieht sich auf jedwede Vorrichtung, die in der Lage ist, Information über einen Kommunikationskanal 14 zu senden und/oder zu empfangen. Der Kommunikationskanal 14 kann ein drahtloser Kanal oder ein drahtgebundener Kanal sein. Das Kommunikationsterminal 10 kann beispielsweise ein Mobiltelefon; ein persönliches Kommunikationssystem-(PCS)-Terminal umfassen, das ein Mobiltelefon mit Datenverarbeitungs-, Fax- und Datenkommunikations-Fähigkeiten kombinieren kann; ein persönlicher digitaler Assistent (PDA), der ein Funktelefon, einen Pager, einen Internet/Intranet-Zugriff, einen Web-Browser, einen Organizer, einen Kalender und/oder einen Empfänger für ein globales Positionierungssystem (GPS) umfassen. Der Ausdruck Kommunikationsterminal 10 umfasst auch Berechnungsvorrichtungen, wie etwa einen Personalcomputer, einen Laptop-Computer oder einen Palmtop-Computer, die eine Kommunikationsschnittstelle zum Kommunizieren mit anderen Vorrichtungen einschließen.
Das Kommunikationsterminal 10 schließt eine Kommunikationsschnittstelle 16, einen Prozessor 18, ein Sicherheitsmodul 20 und einen unsicheren Prozessor, der hierin als ein Beschleuniger 100 bezeichnet wird, ein. Der Prozessor 18 steuert den Betrieb des Kommunikationsterminals 10 und kann entweder einen internen oder einen externen Speicher zum Speichern von Steuerprogrammen und Daten, die während des Betriebs verwendet werden, einschließen. Der Prozessor kann auch verwendet werden, um Berechnungsfunktionen während der Verschlüsselungs- und Entschlüsselungsschritte einer Kommunikationssitzung durchzuführen. Der Prozessor 18 ist jedoch nicht eine sichere Vorrichtung, derart, dass Daten, die darin gespeichert sind, einer Entdeckung durch Parteien von außerhalb unterworfen sind.
Die Kommunikationsschnittstelle 16 stellt eine Einrichtung zum Verbinden des Kommunikationsterminals 10 mit dem Kommunikationskanal 14 bereit. Die Schnittstelle 16 kann eine Vielfalt von Ausführungsformen aufweisen, einschließlich eines Funkfrequenz-Sendeempfängers, einer Ethernet-Schnittstelle, eines Modems, etc.
Das Sicherheitsmodul 20 wird verwendet, um kryptografische Berechnungen durchzuführen, z.B. eine Verschlüsselung und eine Entschlüsselung, und andere Sicherheitsfunktionen. Das Sicherheitsmodul 20 kann beispielsweise eine entnehmbare Smart-Card sein, die durch eine obere Metallisierungsschicht abgedeckt ist, um ein Abtasten interner Knoten zur verbotenen Verwendung eines Extrahierens gespeicherter privater Information, wie etwa eines privaten Schlüssels, zu verhindern. Auf Daten, die berechnet und innerhalb des Sicherheitsmoduls 20 gespeichert sind, kann von einer Quelle von außen nicht zugegriffen werden, womit eine Sicherheit für den Chiffrierprozess bereitgestellt wird. Das Sicherheitsmodul 20 speichert Schlüsselungsvariable, wie etwa die öffentlichen und privaten Schlüssel des Benutzers, die in Chiffrieralgorithmen verwendet werden, um Daten zu verschlüsseln und zu entschlüsseln. Obzwar in 1 als eine getrennte Vorrichtung gezeigt, kann das Sicherheitsmodul 20 tatsächlich in sichere Abschnitte des Prozessors 18 eingeschlossen sein.
Der Beschleuniger 100 ist ein Co-Prozessor, der verwendet wird, um kryptografische Berechnungen, die von dem Sicherheitsmodul 20 durchgeführt werden, zu beschleunigen. Der Beschleuniger 100 ist außerhalb des Sicherheitsmoduls 20 angeordnet und muss nicht ein sicherer Prozessor sein. Die Funktion des Beschleunigers 100 kann von dem Prozessor 18 durchgeführt werden oder in diesen eingeschlossen sein. Die vorliegende Erfindung lässt es zu, dass der Beschleuniger 100 kryptografische Berechnungen durchführt, ohne eine Geheiminformation freizugeben. Der Beschleuniger 100 wird detaillierter untenstehend beschrieben.
2 veranschaulicht das Sicherheitsmodul 20 detaillierter. Das Sicherheitsmodul 20 schließt einen sicheren Prozessor 30, eine I/O-Schnittstelle 32, einen Lesespeicher (ROM) 34, einen löschbaren, programmierbaren Lesespeicher (EPROM) 38, einen Schreiblesespeicher 40 und optional einen Zufallszahlengenerator 42 ein. Die I/O-Schnittstelle 32 verbindet das Sicherheitsmodul 20 mit dem Hauptprozessor 18 des Kommunikationsterminals 10. Der sichere Prozessor 30 führt Programme aus, die in dem ROM 34 gespeichert sind und spricht auf Befehle an, die dem sicheren Prozessor 30 an der I/O-Schnittstelle 30 präsentiert werden. Die Befehle können Anforderungen einschließen, Daten unter Verwendung gespeicherter Schlüssel oder extern zugeführter Schlüssel zu verschlüsseln oder zu entschlüsseln und die Ergebnisse als Ausgangsbits zu der I/O-Schnittstelle 32 zurückzugeben.
Der ROM 34 speichert Programme, die für eine Verschlüsselung, eine Entschlüsselung und andere Sicherheitsfunktionen verwendet werden. Die Programme sollten nicht veränderlich sein, um ein Eingreifen zu verhindern. Andere Daten, die die Benutzer spezifisch sein können, wie etwa öffentliche und private Schlüssel, ein Modulo und ein Identitätszertifikat sind feld-programmierbar und werden in dem EPROM 38 gespeichert. Der private Schlüssel K_PRIV sollte auf eine Weise gespeichert werden, der einen Zugriff von Quellen von außerhalb verhindert. Es ist möglich, den privaten Schlüssel auf eine zerhackte oder unzulängliche Weise zu speichern, die eine Verwendung verhindert, bis ein korrektes, von einem Benutzer zugeführtes Passwort eingegeben wird. Der RAM 40 stellt einen Arbeitsspeicher zum vorübergehenden Speichern von Datenvariablen bereit.
Das Sicherheitsmodul 20 kann auch einen Zufallszahlengenerator 42 einschließen, der verwendet werden kann, um Zufallszahlen zu erzeugen. Die Zufallszahlen können beispielsweise verwendet werden, um Schlüssel zu berechnen oder um Zufalls-Bitketten für Schlüsselaustauschalgorithmen zu erzeugen, wie auch für andere Zwecke, die in dem Stand der Technik alt bekannt sind.
Daten, die von dem Kommunikationsterminal 10 gesendet und von diesen empfangen werden, können verschlüsselt werden, um sie vor einer Offenbarung gegenüber dritten Parteien zu schützen. Eine Verschlüsselung und eine Entschlüsselung kann unter Verwendung von Schlüsselalgorithmen durchgeführt werden. Ein üblicher öffentlicher Schlüsselalgorithmus ist der RSA-Algorithmus. Der RSA-Algorithmus und andere öffentliche Schlüsselalgorithmen verwenden einen ersten Schlüssel, der als der öffentliche Schlüssel bezeichnet wird, für Verschlüsselungs-Betriebsschritte, und einen entsprechenden zweiten Schlüssel, der als der private Schlüssel bezeichnet wird, für Entschlüsselungs-Betriebsschritte. Der öffentliche Schlüssel und der private Schlüssel bilden ein angepasstes Paar. Eine Nachricht, die mit dem öffentlichen Schlüssel verschlüsselt ist, kann nur mit dem angepassten privaten Schlüssel entschlüsselt werden. Deswegen verschlüsselt, um sichere Kommunikationen einzugehen, der Sender die Nachricht unter Verwendung des öffentlichen Schlüssels des Empfängers. Nur der vorgesehene Empfänger kann die Nachricht unter Verwendung des entsprechenden privaten Schlüssels entziffern. Der RSA-Algorithmus ist in dem U.S. Patent Nr. 4,405,829 offenbart.
In dem RSA-Algorithmus wird eine Informationssequenz oder eine Nachricht in eine Mehrzahl von Nachrichtenblöcken geteilt. Jeder Nachrichtenblock umfasst eine Sequenz von Bits, die einen Wert von 1 oder 0 aufweisen, der als eine Binärzahl X angesehen werden kann. Eine Verschlüsselung wird durch ein Potenzieren der Binärzahl X (d.h. des Binärwerts des Nachrichtenblocks) unter Verwendung des öffentlichen Schlüssels K_PUB oder des privaten Schlüssels K_PRIV als der Exponent und ein Reduzieren des Ergebnismodulo des zugeordneten Verschlüsselungsmodulo N durchgeführt. IM Allgemeinen wird der öffentliche Schlüssel K_PUB des Empfängers verwendet, um eine Nachricht zu verschlüsseln, die geheim bleiben soll, und der private Schlüssel K_PRIV des Empfängers wird verwendet, um die verschlüsselte Nachricht zu entschlüsseln. Unter manchen Umständen kann ein Nachrichtenblock mit dem privaten Schlüssel K_PRIV des Senders verschlüsselt werden, um die Nachricht eigentlich zu unterzeichnen. In diesem Fall wird die resultierende unterzeichnete Nachricht mit dem öffentlichen Schlüssel K_PUB des Senders entschlüsselt, um den ursprünglichen Volltext wieder zu gewinnen.
In den RSA-Algorithmus weist der private Schlüssel K_PRIV typischerweise eine Länge von ungefähr 2.048 Bit auf. Der Nachrichtenblock und der Verschlüsselungsmodulo N sind typischerweise in der gleichen Größenordnung einer Wortlänge. Somit bringt eine Verschlüsselung oder Entschlüsselung mit dem privaten Schlüssel K_PRIV ein Potenzieren eines 2.048 Bit-Nachrichtenblocks mit einem 2.048 Bit-Exponenten und ein Reduzieren des Ergebnismodulo mit einer weiteren 2.048 Bit- Zahl mit sich. Diese Berechnungen erfordern eine beträchtliche Rechenleistung zum Durchführen.
Zwei Algorithmen sind in der Vergangenheit verwendet worden, um die Komplexität des Verschlüsselns und Entschlüsselns von Nachrichtenblöcken mit einem Schlüssel zu verringern, der einen großen Binärwert aufweist. Ein Algorithmus, der hierin als der Algorithmus der sukzessiven Quadrate bezeichnet wird, wird verwendet, um eine erste große Zahl in die Potenz einer zweiten großen Zahl zu erheben. Der zweite Algorithmus, der hierin als der Modulo-Reduktionsalgorithmus bezeichnet wird, wird verwendet, um eine erste große Zahl Modulo um eine zweite große Zahl zu reduzieren. Beide dieser Algorithmen werden in einer modifizierten Form in der vorliegenden Erfindung eingesetzt.
Der Algorithmus der sukzessiven Quadrate wird verwendet, um eine Bitkette X auf eine große Potenz Y zu erheben. Bei einer Entschlüsselung ist die Bitkette X die verschlüsselte Nachricht, und die Potenz Y ist der Entschlüsselungsschlüssel. Bei der Verschlüsselung ist die Bitkette X der volle Nachrichtenblock, und die Potenz Y ist der Verschlüsselungsschlüssel. Die aufeinanderfolgenden Quadrate der Bitkette X werden berechnet und verwendet, um einen akkumulierten Wert Z zu multiplizieren, der von dem Wert eines entsprechenden Bits der Potenz Y abhängt. Die aufeinanderfolgenden Quadrate werden hierin als X₁ = X¹, X₂ = X²,
bezeichnet. In dem Algorithmus der sukzessiven Quadrate entspricht das niedrigstwertige Bit in der Potenz Y, bezeichnet als B₁, der ersten Potenz von X, das zweite Bit B₂ entspricht der zweiten Potenz von X, das dritte Bit B₃ entspricht der vierten Potenz von X, usw., bis das letzte Bit B_L erreicht ist. Jedes sukzessive Quadrat X₁, X₂, X₃, ... X_n wird verwendet, um den akkumulierten Wert Z, der von dem Wert des entsprechenden Bits B_n abhängt, in die Potenz Y zu multiplizieren. Insbesondere wird der akkumulierte Wert Z mit dem sukzessiven Quadrat multipliziert, wenn das entsprechende Bit B_n in der Potenz Y 1 ist. Sukzessive Quadrate, die "0" Bits der Potenz Y entsprechen, multiplizieren den akkumulierten Wert Z nicht. Der Algorithmus der sukzessiven Quadrate verringert die Anzahl von Werten, die multipliziert werden müssen, von 2^2.048 auf die Größenordnung von 2.048, wobei X und Y in der Länge 2048 Bit aufweisen.
Nach jedem Multiplikations- oder Quadrierungs-Betriebsschritt weist der akkumulierte Wert Z eine Wortlänge in der Größenordnung von 4.096 Bit auf. Bei der Verschlüsselung und der Entschlüsselung wird dieser akkumulierte Wert Z durch eine Modulo-Reduktion auf einen Wert in der Größenordnung von 2.048 in der Länge reduziert. Insbesondere wird das Ergebnis jedes Quadrierungs-Betriebsschrittsmodulo des Verschlüsselungsmodulos N mit der Wortlänge 2048 reduziert. Dies erfordert ein Subtrahieren einer Anzahl von Vielfachen von N, bis der Wert des akkumulierten Gesamt-Z geringer als N ist. Die Anzahl von Vielfachen von N, die subtrahiert werden müssen, ist in der Größenordnung von 2^2.048 oder 10⁶⁰⁰ was die Möglichkeit einer sukzessiven Subtraktion eliminiert. Die Anzahl von Vielfachen von N, die subtrahiert werden müssen, ist in der Größenordnung von 2^2.048 oder 10⁶⁰⁰ was die Möglichkeit einer sukzessiven Subtraktion eliminiert.
Der Modulo-Reduktionsalgorithmus wird verwendet, um eine erste große Zahl Modulo einer zweiten großen Zahl zu reduzieren. Gemäß dem Modulo-Reduktionsalgorithmus wird der ungefähre Reziprokwert von N auf 2.048 signifikante Bit berechnet, wobei führende Nullen nach dem Binärpunkt ignoriert werden. Jedes Mal, wenn ein 4.096 Bit-Z-Wert Modulo N zu reduzieren ist, wird die ungefähre Anzahl von Malen T, die N von Z subtrahieren, unter Verwendung der Gleichung T = Z 1/N berechnet, was eine einzelne lange Multiplikation von Z mit dem ungefähren Reziprokwert von N ist. Das Produkt von TxN wird dann von dem akkumulierten Wert Z subtrahiert, was Z auf innerhalb ein oder zwei Mal N des erforderlichen Ergebnisses reduziert. Die Reduktion wird dann durch ein Subtrahieren der Verschlüsselung Modulos N um ein oder zwei Mal mehr von dem akkumulierten Wert Z vervollständigt, bis der Rest geringer als N, aber nicht negativ ist. Dieser Modulo-Reduktionsalgorithmus erfordert zwei lange Multiplikationen und zwei Subtraktionen anstelle von 10⁶⁰⁰ sukzessiven Subtraktionen.
Gemäß der vorliegenden Erfindung wird ein unsicherer Prozessor oder Beschleuniger 100 verwendet, um den Hauptteil der kryptografischen Berechnungen durchzuführen, ohne eine geheime Information in dem Prozess preiszugeben. Eine Ausführungsform der vorliegenden Erfindung kann beispielsweise verwendet werden, um einen Wert mit einem geheimen Exponenten zu potenzieren. Somit kann die erste Ausführungsform beispielsweise verwendet werden, um eine verschlüsselte Nachricht zu entschlüsseln, ohne entweder den privaten Schlüssel K_PRIV oder den Volltext der Nachricht preiszugeben. Diese Ausführungsform der Erfindung kann auch verwendet werden, um eine nicht-geheime Nachricht mit dem privaten Schlüssel K_PRIV zu unterzeichnen, wiederum ohne ein Enthüllen des Schlüssels K_PRIV. Eine andere Ausführungsform kann verwendet werden, um einen geheimen Wert einem geheimen Exponenten zu potenzieren. Diese Ausführungsform kann beispielsweise verwendet werden, um eine geheime Information unter Verwendung K_PUB oder eines privaten Schlüssels K_PRIV zu verschlüsseln, ohne die Geheiminformation oder den Schlüssel preiszugeben.
In der ersten Ausführungsform der Erfindung muss der private Schlüssel K_PRIV geheim bleiben, während kryptografische Berechnungen durchgeführt werden. Die kryptografischen Berechnungen können ein Verschlüsseln oder ein Entschlüsseln von Nachrichten mit dem privaten Schlüssel K_PRIV umfassen. Um den privaten Schlüssel K_PRIV zu schützen, aber es dennoch zuzulassen, dass ein signifikanter Teil der Verarbeitung, die für die Verschlüsselung/Entschlüsselung erforderlich ist, außerhalb des Sicherheitsmoduls 20 ausgeführt wird, wird der private Schlüssel in zwei oder mehrere Teile geteilt, die manchmal hierin als Partialwerte bezeichnet werden. In der ersten beispielhaften Ausführungsform wird der private Schlüssel K_PRIV modifiziert, um einen modifizierten privaten Schlüssel K_PRIVM (den ersten Partialwert) und einen Indikator INDIC (den zweiten Partialwert) zu erhalten. Das Sicherheitsmodul 20 führt den modifizierten privaten Schlüssel K_PRIVM und die Bitkette X einem unsicheren Prozessor außerhalb des Sicherheitsmoduls 20, wie etwa bei dem Beschleuniger 100, zu. Der Beschleuniger 100 führt einen signifikanten Teil der notwendigen Berechnungen auf der Grundlage von K_PRIVM durch und führt dem Sicherheitsmodul 20 den resultierenden Wert (der hierin als das erste Produkt P₁ bezeichnet wird) zu. Zusätzlich kann der Beschleuniger 100 das Sicherheitsmodul 20 auch mit anderen Werten versorgen, die von dem Sicherheitsmodul 20 benötigt werden, um die Berechnungen zu vervollständigen. Das Sicherheitsmodul 20 führt dann bestimmte zusätzliche Berechnungen auf der Grundlage des Indikators IDIC und der Bitkette X durch, um einen zweiten Wert zu erzeugen (der hierin als das zweite Produkt P₂ bezeichnet wird). Das Sicherheitsmodul 20 kombiniert dann das erste Produkt P₁ und das zweite Produkt P₂ auf eine geeignete Weise, um ein Endprodukt P_F zu erzeugen. In dem Fall einer Entschlüsselung ist das Endprodukt P_F der ursprüngliche Volltext. Im Fall einer Verschlüsselung ist das Endprodukt P_F der resultierende Chiffre-Text.
3 ist ein Funktionsblockdiagramm, das die Verarbeitung, die von dem Beschleuniger 100 und dem sicheren Prozessor 30 durchgeführt wird, für eine Ausführungsform veranschaulicht. Der Beschleuniger 100 umfasst einen Quadratzahlengenerator 102, einen Akkumulator 104 und eine Verzögerungsschaltung 106. Der Quadratzahlengenerator 102 empfängt die zugeführte Bitkette X als Eingang. Die Bitkette X kann entweder den Chiffre-Text, der mit dem privaten Schlüssel K_PRIV zu entschlüsseln ist, oder den Volltext, der mit dem privaten Schlüssel K_PRIV zu verschlüsseln ist, umfassen. Der Quadratzahlengenerator 102 quadriert iterativ die zugeführte Bitkette X und reduziert jedes sukzessive Quadratmodulo ein Verschlüsselungsmodulo N. Die sukzessiven Quadrate werden als X₁, X₂, ... X_n bezeichnet. Der Verschlüsselungsmodulo N ist der Modulo, der dem zugeführten privaten Schlüssel K_PRIV zugeordnet ist. Der Ausgang des Quadratzahlengenerators 102 wird dem Akkumulator 104 während jeder Iteration zugeführt. Der Ausgang des Quadratzahlengenerators 102 wird auch in den Sicherheitsprozessor 30 während jeder Iteration rückgekoppelt.
Der multiplikative Akkumulator 104 wird auf einen Startwert von 1 initialisiert. Wie oben erwähnt, empfängt der multiplikative Akkumulator 104 die sukzessiven Quadrate X₁, X₂, X₃, X₄, ... X_n, die aus dem Quadratzahlengenerator 102 ausgegeben werden. Der multiplikative Akkumulator 104 empfängt auch an einem zweiten Eingang einen akkumulierten Wert Z, der um einen Zyklus durch die Verzögerungsschaltung 106 verzögert wird. Der multiplikative Akkumulator 104 multipliziert iterativ den vorangehenden akkumulierten Wert Z mit dem Ausgang des Quadratzahlengenerators 102 in Abhängigkeit von dem Wert eines entsprechenden Bits B_n des modifizierten privaten Schlüssels K_PRIVM. Somit steuern die Bits des modifizierten Schlüssels K_PRIVM den Betrieb des multiplikativen Akkumulators 104. Wenn das entsprechende B_n des modifizierten Schlüssels gleich 0 ist, wird der akkumulierte Wert Z mit 1 multipliziert, d.h. keine Multiplikation muss durchgeführt werden. Wenn das entsprechende Bit B_n des modifizierten Schlüssels K_PRIVM einen Wert von 1 aufweist, multipliziert der multiplikative Akkumulator 104 den vorangehenden Wert Z mit einem entsprechenden sukzessiven Quadrat X_n, das von dem Quadratzahlengenerator 102 ausgegeben wird, um einen neuen Wert von Z zu berechnen. Nach jedem Multiplikationsbetrieb wird der resultierende Wert Z Modulo um den Verschlüsselungsschlüssel N reduziert. Dieser Prozess wird für jedes Bit des modifizierten Schlüssels K_PRIVM wiederholt, beginnend mit dem niedrigstwertigen Bit und endend mit dem höchstwertigen Bit. Der Endwert von Z ist das erste Produkt P₁ und wird in das Sicherheitsmodul 20 eingegeben, um die kryptografischen Berechnungen zu vollenden.
3 zeigt auch die Verarbeitung, die von dem sicheren Prozessor 30 innerhalb des Sicherheitsmoduls 20 durchgeführt wird, was die Berechnungen, die durch den Beschleuniger 100 gestartet sind, vollendet. Der Prozessor 30 umfasst einen selektiven Multiplizierer 44 und einen Produktknoten 46. Der selektive Multiplizierer 44 empfängt die sukzessiven Quadrate X₁, X₂, ... X_n, die aus dem Quadratzahlengenerator 102 ausgegeben werden. Der selektive Multiplizierer 44 empfängt auch den Indikator INDIC, der untenstehend diskutiert wird. Die Betriebsschritte des selektiven Multiplizierers 44 werden durch den Indikator INDIC gesteuert. Es besteht eine Eins-zu-Eins-Übereinstimmung zwischen den Bits INDIC und der Zahl sukzessiver Quadrate X_n. Insbesondere wählt der selektive Multiplizierer 44 jene Fälle der sukzessiven Quadrate X_n, die einen Bitwert von 1 in dem Indikator INDIC entsprechen, und verwirft die sukzessiven Quadrate, die einem Bitwert von 0 entsprechen. Die ausgewählten sukzessiven Quadrate X_n können in dem RAM 40 gesichert werden. Somit wählt der Indikator INDIC sukzessive Quadrate X_n, die von dem Quadratzahlengenerator 102 ausgegeben werden, und verwirft den Rest.
Der selektive Multiplizierer 44 kann das Produkt der ausgewählten sukzessiven Quadrate X_n berechnen, um einen Wert zu erzeugen, der hierin als das zweite Produkt P₂ bezeichnet wird, das dem Produktknoten 46 zugeführt wird. Der Produktknoten 46 multipliziert das zweite Produkt P₂ mit dem ersten Produkt P₁, das von dem Beschleuniger 100 erzeugt wird, um das Endprodukt P_F zu erzeugen. Dieses Endprodukt P_F umfasst den Volltext (Entschlüsselung) oder den chiffrierten Text (Verschlüsselung), der aus dem Chiffrierbetrieb hervorgeht. Alternativ kann das erste Produkt P₁, das von dem Beschleuniger 100 ausgegeben wird, mit den ausgewählten sukzessiven Quadraten X_n, eines nach dem anderen, multipliziert werden, um das Endprodukt P_F zu berechnen. Zu Zwecken dieser Anmeldung schließt ein Multiplizierer eines ersten Produkts P₁ mit einem zweiten Produkt P₂ einen Multiplizierer des ersten Produkts P₁ mit den Faktoren ein, die das zweite Produkt P₂ umfassen. Auch schließt ein Bestimmen und Berechnen eines zweiten Produkts P₂, wie hierin verwendet, ein Bestimmen oder Berechnen der Faktoren des zweiten Produkts P₂ ein.
4 veranschaulicht die Schritte, die bei einem Entschlüsseln einer verschlüsselten Nachricht unter Verwendung des privaten Schlüssels K_PRIV des Empfängers eingeschlossen sind, der geheim bleiben soll. Das Sicherheitsmodul 20 bestimmt den privaten Schlüssel K_PRIV in einem Schritt 400. Um den externen Beschleuniger 100 zu verwenden, ohne den privaten Schlüssel K_PRIV preiszugeben, wird der private Schlüssel K_PRIV durch ein Ändern ausgewählter Bits des ursprünglichen privaten Schlüssels K_PRIV modifiziert, um einen modifizierten privaten Schlüssel K_PRIVM zu erhalten (Schritt 402). Ein Indikator INDIC wird dann gebildet, um die Änderungen, die an dem privaten Schlüssel K_PRIV ausgeführt sind, anzuzeigen (Schritt 402). Der Indikator INDIC umfasst die gleiche Zahl von Bits wie der private Schlüssel K_PRIV.
Zahlreiche Verfahren können verwendet werden, um den modifizierten privaten Schlüssel K_PRIVM und den Indikator INDIC zu berechnen. Im Wege eines Beispiels weist ein privater Schlüssel K_PRIV der eine Länge von 2048 Bits aufweist, einen Mittelwert von 1024 Bitpositionen mit einem Wert von "1" auf. Zwanzig dieser Bitpositionen können von "1" auf "0" geändert werden, um K_PRIVM zu bilden. Der Indikator INDIC umfasst in diesem Fall eine Bitkette einer gleichen Länge wie der private Schlüssel K_PRIV der eine "1" in jeder Bitposition aufweist, die den geänderten Bits in dem privaten Schlüssel K_PRIV entspricht, und Nullen anderenfalls.
Andere Verfahren können auch verwendet werden, um den K_PRIV und den Indikator INDIC zu verwenden, einschließlich ein Ersetzen mancher Einsen durch Nullen oder mancher Nullen durch Einsen. Ein Zugang besteht darin, zuerst einen Indikator INDIC durch ein zufallsmäßiges Auswählen eines kleinen Prozentsatzes von Bits in INDIC aufzubauen, um binäre Einsen zu enthalten, und dann INDIC von dem privaten Schlüssel K_PRIV mit Übertrag-Ausbreitung zu subtrahieren, um den modifizierten privaten Schlüssel K_PRIVM zu erhalten. Auf ähnliche Weise können Bits K_PRIV zufallsmäßig ausgewählt und geändert werden, entweder von "1" auf "0" oder von "0" auf "1", um einen modifizierten privaten Schlüssel K_PRIVM mit einem Wert geringer als K_PRIV zu erhalten. Der modifizierte private Schlüssel K_PRIVM kann dann von dem ursprünglichen privaten Schlüssel K_PRIV subtrahiert werden, ohne den Indikator INDIC zu erhalten. Im Allgemeinen werden der modifizierte private Schlüssel K_PRIVM und der Indikator INDIC derart gewählt, dass die Summe des modifizierten privaten Schlüssels K_PRIVM und der Indikator INDIC dem Wert des privaten Schlüssels K_PRIV gleicht.
Zur Entschlüsselung wird die verschlüsselte Bitkette, die mit X bezeichnet ist, dem Beschleuniger 100 zusammen mit dem modifizierten privaten Schlüssel K_PRIVM und dem Modulo N zugeführt (Block 404). Der Beschleuniger 100 berechnet das erste Produkt P₁ als eine Funktion des modifizierten privaten Schlüssels K_PRIVM und der Bitkette X unter Verwendung des Algorithmus der sukzessiven Quadrate und des Modulo-Reduktionsalgorithmus. Der multiplikative Akkumulator 104 wird initialisiert (Block 406), indem der Wert Z des multiplikativen Akkumulators 104 auf einen Startwert von "1" gesetzt wird. Das erste Produkt P₁ wird dann durch eine Modulo-Potenzierung von X unter Verwendung des modifizierten privaten Schlüssels K_PRIVM berechnet (Block 408). Für jedes Bit B_n des modifizierten privaten Schlüssels K_PRIVM wird der Wert Z mit einem entsprechenden sukzessiven Quadrat X_n der verschlüsselten Bitkette X in Abhängigkeit von dem Wert des gegenwärtigen Bits B_n in K_PRIVM multipliziert. Wenn das Bit B_n einen Wert "1" aufweist, setzt der Akkumulator 104 Inkremente Z gemäß der Gleichung
wobei X gleich dem Wert der zugeführten Bitkette ist und n die Bitposition
ist, ist das sukzessive Quadrat von X, das dem Bit B_n von K_PRIVM entspricht. Wenn B_n "0" ist, bleibt der akkumulierte Z der gleiche. Der Akkumulationsprozess setzt sich für jedes Bit B_n innerhalb des modifizierten privaten Schlüssels K_PRIVM fort. Nachdem das letzte Bit B_L in K_PRIVM verarbeitet ist, wird der Endwert von Z dann zu dem Sicherheitsmodul als das erste Produkt P₁ gesendet (Block 410).
Jedes sukzessive Quadrat X_n, z.B. X₁, X₂, ... X_n wird von dem externen Beschleuniger 100 zu dem Sicherheitsmodul 20 zurückgekoppelt. Der gegen Eingriffe gesicherte Chip 20 sichert die sukzessiven Quadrate X_n, die dem "1er" in dem Indikator INDIC entsprechen und verwirft den Rest auf eine Weise, die der Welt außerhalb verheimlicht, welche der sukzessiven Quadrate X_n gesichert wurden und welche verworfen wurden. Die gesicherten sukzessiven Quadrate X_n werden dann zusammen durch den Sicherheitsprozessor 30 multipliziert, um ein zweites Produkt P₂ zu erhalten (Block 412).
Das erste Produkt P₁, das von dem externen Beschleuniger 100 ausgegeben wird, wird mit dem zweiten Produkt P₂ multipliziert, um ein Endprodukt P_F zu erhalten (Block 414). Dieser Endschritt wird von dem Sicherheitsprozessor 30 durchgeführt. Auf äquivalente Weise kann das erste Produkt P₁ mit jedem der gesicherten sukzessiven Quadrate X_n unabhängig multipliziert werden, um das Endprodukt P_F zu erhalten. Somit muss das zweite Produkt P₂ nicht getrennt berechnet werden.
Eine Partei, die die externen Berechnungen beobachtet, kann nicht wissen, welche der "0er" in dem modifizierten privaten Schlüssel K_PRIVM "1er" gewesen sein sollten. Die Zahl unterschiedlicher Weisen, auf welche zwanzig "1er" in "0er" geändert worden sein können, ist in der Größenordnung von 10⁴², und kann deswegen auf sinnvolle Weise durch Versuch und Irrtum nicht bestimmt werden. Trotzdem kann der externe Beschleuniger 100 98% oder mehr der erforderlichen Multiplikationen durchführen.
5 veranschaulicht ein Beispiel einer kryptografischen Berechnung (ohne Modulo-Reduktion) gemäß der vorliegenden Erfindung unter Verwendung eines Fünf-Bit K_PRIV und einer Fünf-Bit-Bitkette X. Wie in dem Beispiel der 5 veranschaulicht, ist K_PRIV = 10111 = 23. Der modifizierte private Schlüssel K_PRIVM wird durch ein Ändern von Bits an Positionen 2 und 3 von "1" auf "0" erhalten, wobei die Bitposition 1 dem niedrigstwertigen Bit entspricht. Somit ist der modifizierte private Schlüssel K_PRIVM = 10001 = 17. Der Indikator InDIC weist einen Wert von "1" an der Bitposition 2 und 3 und Nullen anderenfalls auf. Somit ist INDIC = 6.
Das niedrigstwertige Bit von K_PRIVM weist einen Wert von "1" auf. Deswegen multipliziert der multiplikative Akkumulator 104 den Startwert von Z (der 1 ist) mit X. Der Endwert von Z nach der Anfangsiteration ist deswegen X. Das zweite Bit in K_PRIVM ist 0. Deswegen wird der akkumulierte Wert Z während der zweiten Iteration nicht multipliziert. Auf ähnliche Weise enthalten die Bits 3 und 4 von K_PRIVM Nullen, so dass der Wert von Z während jeder dieser Iterationen konstant bleibt. Das Bit bei der Position 5 ist eine "1", so dass der akkumulierte Wert Z gemäß der Formel
hochgesetzt wird, um einen Endwert von 5,8 × 10²³ zu erhalten. Da dies das letzte Bit ist, sendet der Beschleuniger 100 Z zu dem Sicherheitsmodul 20 als das erste Produkt P₁.
Das Sicherheitsmodul 20 bestimmt die von dem Quadratzahlengenerator 102 rückgekoppelte sukzessiven Quadrate X_n, die jeder Bitposition innerhalb des Indikators INDIC entsprechen, die einen Wert von "1" enthält. In diesem Beispiel werden die sukzessiven Quadrate X₂= X² und X₃ = X⁴ durch INDIC ausgewählt. Das zweite Produkt P₂ ist deswegen gleich X₂·X₃, was gleich 2,44 × 10⁸ ist. Ein Endprodukt P_F wird dann durch ein Multiplizieren des ersten Produkts P₁ mit dem zweiten Produkt P₂ bestimmt, derart, dass der Endwert P_F gleich 1,42 × 10³² ist.
Eine zweite Ausführungsform kann verwendet werden, um einen geheimen Volltext mit entweder einem öffentlichen oder einem privaten Schlüssel zu verschlüsseln, ohne den geheimen Volltext aufzudecken. Um den Volltext unter Verwendung des RSA-Algorithmus zu verschlüsseln, muss der geheime Volltext auf eine Potenz gehoben werden, der durch den öffentlichen oder den privaten Schlüssel dargestellt wird. Gemäß der vorliegenden Erfindung wird dies ohne ein Aufdecken des geheimen Volltexts gegenüber einem unsicheren Prozessor ausgeführt, um diese Potenzierung durchzuführen. In der zweiten Ausführungsform wird ein erstes Produkt P₁ von dem Beschleuniger 100 berechnet, und ein zweites Produkt P₂ wird innerhalb des Sicherheitsmoduls 20 berechnet. Das Sicherheitsmodul 20 kombiniert dann das erste Produkt P₁ und das zweite Produkt P₂, um ein Endprodukt P_F zu erhalten. Das erste Produkt P₁ in der zweiten Ausführungsform ist eine Funktion eines dritten Produkts P₃, das innerhalb des Sicherheitsmoduls 20 berechnet wird, und eines vierten Produkt P₄. Das dritte Produkt wird verwendet, um den Akkumulator 104 zu initialisieren.
Gemäß einer zweiten Ausführungsform wird der private Schlüssel K_PRIV zunächst in zwei Partialwerte geteilt, die hierin als der kurze Teil K_SHORT und der lange Teil K_LONG bezeichnet werden. Der kurze Teil K_SHORT, kann beispielsweise die niedrigstwertigen Bits des privaten Schlüssels K_PRIV umfassen. Der lange Teil K_LONG ist in diesem Fall das Segment, das die höchstwertigen Bits in K_PRIV umfasst. Im Wege eines Beispiels können, wenn der private Schlüssel K_PRIV 2,048 Bits enthält, die 16 niedrigstwertigen Bits den kurzen Teil K_SHORT umfassen, und die 2,032 höchstwertigen Bits können den langen Teil K_LONG umfassen. Der lange Teil K_LONG wird dann, wie oben beschrieben, modifiziert, um den modifizierten langen Teil K_LONGMund den Indikator INDIC zu erhalten. Somit wird der private Schlüssel K_PRIV effektiv in drei Partialwerte geteilt: K_SHORT, K_LONGM und INDIC, deren Summe gleich K_PRIV ist.
Der geheime Volltext X wird anfänglich unter Verwendung des kurzen Teils K_SHORT innerhalb des Sicherheitsmoduls 20 verschlüsselt, und das Ergebnis ist das dritte Produkt P₃. Das dritte Produkt P₃ wird verwendet, um den multiplikativen Akkumulator 104 zu initialisieren und wird hierin als der Startwert bezeichnet. Dies wird durch Modulo-Potenzierung des geheimen Volltextes unter Verwendung des kurzen Schlüssels K_SHORT des privaten Schlüssels K_PRIV ausgeführt. Die Modulo-Potenzierung kann unter Verwendung des Algorithmus der sukzessiven Quadrate und des Modulo-Reduktionsalgorithmus durchgeführt werden, wie zuvor beschrieben. Dieser Prozess erfordert es notwendigerweise, dass der geheime Prozessor 30 die ersten 16 sukzessiven Quadrate von X berechnet. Das letzte der berechneten 16 sukzessiven Quadrate, das mit X₁₆ bezeichnet ist, wäre der Volltext, gehoben in die Potenz von 32,768, reduziert Modulo den Verschlüsselungsmodulo N.
Der Wert X₁₆ wird zu dem Beschleuniger 100 freigegeben, der X₁₆ verwendet, um den Quadratzahlengenerator 102 zu initialisieren. Der Quadratzahlengenerator 102 berechnet die letzten 2,032 sukzessiven Quadrate von X durch ein sukzessives Quadrieren von X₁₆. Der multiplikative Akkumulator 104, der auf den Wert des dritten Produkts P₃ initialisiert ist, berechnet das erste Produkt P₁ als eine Funktion des dritten Produkts P₃ und des modifizierten langen Teils K_LONGM des privaten Schlüssels K_PRIV unter Verwendung des Algorithmus der sukzessiven Quadrate und des Modulo-Reduktionsalgorithmus, wie zuvor beschrieben. Somit ist es gemäß der vorliegenden Erfindung nicht notwendig, den geheimen Volltext X gegenüber der Welt außerhalb freizugeben, statt dessen ist es nur notwendig, X₁₆ freizugeben. Versuche, X auf der Grundlage von X₁₆ zu berechnen, würden eine 1/32.768-te Wurzeloperation erfordern, was in der Modulo-Arithmetik praktisch nicht möglich ist. Deswegen offenbart die Offenbarung von X₁₆ und P₃ der Welt außerhalb X nicht.
6 veranschaulicht das Verfahren zum Verschlüsseln gemäß der zweiten Ausführungsform der vorliegenden Erfindung. Der Wert des privaten Schlüssels K_PRIV wird bestimmt und innerhalb des Sicherheitsmoduls 20 gespeichert (Block 600). Zwei zusätzliche Werte, K_SHORT und K_LONG, werden bestimmt (Block 602), indem der private Schlüssel K_PRIV in zwei Teile aufgeteilt wird. K_SHORT umfasst die 16 niedrigstwertigen Bits, und K_LONG umfasst die 2.032 höchstwertigen Bits. Der Wert K_LONGwird dann auf die zuvor beschriebene Weise modifiziert, um K_LONGM und einen Indikator INDIC zu erhalten (Block 604).
Der Wert K_SHORT wird innerhalb des Sicherheitsmoduls 20 gehalten und wird verwendet, um den geheimen Volltext, der mit X bezeichnet ist, zu potenzieren, um das dritte Produkt P₃ zu erhalten. Der Wert X wird auf die Potenz K_SHORT innerhalb des Sicherheitsmoduls 20 durch den Prozessor 30 unter Verwendung des Algorithmus der sukzessiven Quadrate und des Modulo-Reduktionsalgorithmus gehoben, um das dritte Produkt P₃und den Wert X₁₆ = X⁶⁵³⁶ zu erhalten (Block 606). Das dritte Produkt ist X, gehoben auf die Potenz von K_SHORT und verringert Modulo N (z.B. P₁=X^KSHORTmod N). Die Werte K_LONGM, P₃ und X₁₆ werden in dem Beschleuniger 100 ausgegeben (Block 610). Der multiplikative Akkumulator 104 wird auf den Wert P₃ initialisiert (Block 612). Von diesem Punkt setzt sich der Prozess, wie oben unter Bezugnahme auf 4 beschrieben, fort. Der Quadratzahlengenerator 102 berechnet die sukzessiven Quadrate X_n von X, beginnend mit X₁₇ und andauernd bis X₂₀₄₈. Jedes der sukzessiven Quadrate X_n wird durch Quadrieren des vorherigen Werts berechnet. Somit wird X₁₇ durch ein Quadrieren von X₁₆ berechnet, X₁₈ wird durch ein Quadrieren von X₁₇ berechnet, usw., bis X₂₀₄₈ erreicht ist. Jedes der sukzessiven Quadrate, z.B. X₁₇, X₁₈, X_n wird in das Sicherheitsmodul 20 rückgekoppelt, das jene sukzessiven Quadrate X_n sichert, die Einsen in dem Indikator INDIC entsprechen, um das zweite Produkt P₂ zu berechnen. Die sukzessiven Quadrate X_n werden auch in dem Akkumulator 104 eingegeben, der den akkumulierten Wert Z mit dem sukzessiven Quadrat X_n multipliziert, wenn ein entsprechendes Bit B_n in K_LONGM gleich 1 ist, wie zuvor beschrieben. Der multiplikative Akkumulator 104 multipliziert effektiv das dritte Produkt P₃ mit einem vierten Produkt P₄, das gleich der Bitkette X gehoben in die Potenz von K_LONGM ist. Der Endwert des Akkumulators 104, der als das erste Produkt P₁ bezeichnet wird, wird zu dem Sicherheitsmodul 20 zurückgegeben. Das Sicherheitsmodul 20 berechnet ein zweites Produkt P₂, das die Bitkette X, gehoben auf die Potenz des Indikators INDIC ist. Das Endprodukt P_F wird dann durch ein Multiplizieren des ersten Produkts P₁ mit dem zweiten Produkt P₂ erhalten.
Es sei darauf hingewiesen, dass die Bitkette K_LONGM und K_SHORT äquivalent zu dem modifizierten Chiffre-Schlüssel in der ersten Ausführungsform ist. Das heißt, K_LONGM + K_SHORT K_PRIVM in der ersten Ausführungsform. Somit könnte das erste Produkt P₁ in der zweiten Ausführungsform auch als eine Funktion von K_LONGM und K_SHORT ausgedrückt werden. Spezifischer bezieht sich das erste Produkt P₁ auf K_LONGM und
Das obige Protokoll ist sicher für eine Verschlüsselung des geheimen Volltextes unter Verwendung des privaten Schlüssels K_PRIV, wie auch für die übliche Entschlüsselung eines verschlüsselten Textes zur Verwendung des privaten Schlüssels K_PRIV. Wenn das Kommunikationsterminal 10 sowohl für die Verschlüsselung als auch für die Entschlüsselung verwendet wird, sollten die gleichen Modifikationen des privaten Schlüssels K_PRIVM für beide Betriebsschritte verwendet werden.
7 veranschaulicht ein Beispiel einer kryptografischen Berechnung ohne einer Moduloreduktion gemäß der zweiten Ausführungsform unter Verwendung eines 5-Bit privaten Schlüssels K_PRIV und eines 5-Bits X. Wie in dem Beispiel der 7 veranschaulicht ist, ist K_PRIV gleich 10111 = 23. K_LONGM ist gleich 10000 = 16. K_SHORT ist gleich 00011 = 3. Der Indikator INDIC ist gleich 00100 = 4.
Der Startwert des Akkumulators 104 wird von dem Sicherheitsmodul 20 durch ein Erheben des Werts der Bitkette X in die Potenz von K_SHORT berechnet, was gleich 15.625 ist, was das dritte Produkt P₃ ist. In diesem Beispiel umfasst K_SHORT die ersten beiden Bits von K_PRIV, wobei die übrigen Bits auf 0 gesetzt sind. Somit berechnet das Sicherheitsmodul 20 auch die ersten beiden aufeinanderfolgenden Quadrate von X, d.h. X₁ = X und X₂ = X². Das letzte sukzessive Quadrat X₂ wird verwendet, um den Quadratzahlengenerator 102 zu initialisieren. Der Beschleuniger 100 berechnet das erste Produkt P₁ als eine Funktion des dritten Produkts P₃ und des modifizierten langen Teils K_LONGM des privaten Schlüssels K_PRIV. In diesem Beispiel sind die ersten vier Bits von K_LONGM gleich 0. Deswegen multiplizieren die ersten vier sukzessiven Quadrate von X nicht den akkumulierten Wert X.
Das Endbit von K_LONGM, das X¹⁶ entspricht, weist einen Wert von 1 auf. Deswegen wird der akkumulierte Wert Z mit 2,32 × 10²², dem vierten Produkt P₄ multipliziert, und um zu dem ersten Produkt P₁ gleich 3,64 × 10²⁶ zu gelangen.
Das erste Produkt P₁ wird in das Sicherheitsmodul 20 eingegeben. Das Sicherheitsmodul 20 berechnet das zweite Produkt P₂, das in diesem Beispiel gleich 390.625 ist. Das erste Produkt P₁ und das zweite Produkt P₂ werden multipliziert, um das Endprodukt P_F zu erhalten, welches gleich 1,42 × 10³² ist.
Die zweite Ausführungsform teilt den privaten Schlüssel K_PRIV effektiv in drei Teile: einen kurzen oder niedrigstwertigen Teil K_SHORT, einen modifizierten höchstwertigen Teil K_LONGM und einen Indikator INDIC. Eine Potenzierung unter Verwendung des niedrigstwertigen Teils K_SHORT findet innerhalb des Sicherheitsmoduls 20 statt, während eine Potenzierung mit dem modifizierten höchstwertigen Teil K_LONGM, das den Hauptteil der Multiplikationen umfasst, von dem Beschleuniger 100 durchgeführt wird. Eine Fachperson wird erkennen, dass andere Arten vorhanden sind, um den geheimen Schlüssel zu partitionieren, um die gleichen Ziele zu erreichen.
Als ein Beispiel wird der oben beschriebene Prozess auf einen beispielhaften geheimen Schlüssel wie folgt angewandt:

K_PRIV 11011001011101

K_LONG 11011001010000

K_SHORT 00000000001101

K_LONGM 11000000010000

INDIC 00011001000000
In diesem Fall kann der PRIVATE Schlüssel K_PRIV ausgedrückt werden als 16 (K_LONGM ODER INDIC) + K_SHORT. Jedoch kann eine alternative Teilung des privaten Schlüssels K_PRIV wie folgt ausgeführt werden:

K_PRIV 11011001011101

K_LONG 11011001010000

K_SHORT 00000000001101

K_LONGM 11010110010000

INDIC 00000011000000
In diesem Fall kann der private Schlüssel K_PRIV ausgedrückt werden als 16 (K_LONGM + INDIC) + K_SHORT.
Es sei darauf hingewiesen, dass die letztere Formel die erstere umfasst, aber unterschiedliche Arten zulässt, K_LONG zu modifizieren. Das heißt, dass in dem ersten Beispiel der einzig zugelassenen Bit K_LONG von einer Binären "1" zu einer Binären "0" ist. In dem zweiten Beispiel kann eine "0" in K_LONG durch eine "1" ersetzt werden, indem eine Binäre "1" von dieser Position mit einer Vorwärts-Untertragsausbreitung subtrahiert wird. In gleicher Weise kann eine "1" in K_LONG in eine "0" durch eine Addition einer "1" zu jener Position mit einer Vorwärts-Übertragungsausbreitung konvertiert werden. Was immer an K_LONG ausgeführt wird (eine Bitposition mit einer Übertragungs-/Untertragsausbreitung) ausgeführt wird, wird das Gegenteil an dem Indikator INDIC ausgeführt, so dass ihre Summe aus K_LONGM und INDIC kontinuierlich gleich dem unmodifizierten langen Teil K_LONG ist. Somit können "1er" in "0en" konvertiert werden, indem sie entweder in K_LONG heruntergesetzt oder die entsprechende Position in INDIC ohne eine Übertragungs-/Untertragsausbreitung hochgesetzt wird, oder weiter durch ein Hochsetzen derselben mit einer Übertrags-Ausbreitung in K_LONG, während die entsprechende Position in INDIC mit einer Untertrags-Ausbreitung herabgesetzt wird. Umgekehrt können "0en" in K_LONG in "1er" konvertiert werden, indem entweder diese Position in K_LONG hochgesetzt wird, während (mit einer Untertrags-Ausbreitung) die entsprechende Bitposition in INDIC herabgesetzt wird, oder weiter, indem (mit einer Übertrags-Ausbreitung) diese Position in K_LONG herabgesetzt wird, während die entsprechende Bitposition in INDIC hochgesetzt wird.
Es kann unnötig sein, den unsicheren Prozessor 100 für Betriebsschritte zu verwenden, die den öffentlichen Schlüssel K_PUB einschließen, da öffentliche Schlüssel im Allgemeinen viel kürzer (weniger als 16 Bits) als private Schlüssel sind. Jedoch kann die vorliegende Erfindung auch verwendet werden, um einen geheimen Volltext mit dem öffentlichen Schlüssel K_PUB durch Durchführen einer Potenzierung des geheimen Volltexts mit einem niedrigstwerten Abschnitt des öffentlichen Schlüssels K_PUB und ein Vervollständigen der Potenzierung mit dem höchstwertigen Teil des öffentlichen Schlüssels K_PUB zu verschlüsseln. Das Ergebnis, das von dem unsicheren Prozessor 100 zurückgegeben wird, kann dann mit dem Wert kombiniert werden, der innerhalb des Sicherheitsmoduls 20 berechnet ist. Wenn ein geheimer Text mit einem öffentlichen Schlüssel K_PUB verschlüsselt wird, ist es nicht notwendig, die Bits des öffentlichen Schlüssels K_PUB, wie oben beschrieben, zu modifizieren, da der öffentliche Schlüssel K_PUB bereits öffentlich ist. Somit bringt eine dritte Ausführungsform der Erfindung ein Verschlüsseln eines Volltexts durch ein Teilen des Verschlüsselungsschlüssels in zwei Teile mit sich, indem ein erster Teil des Verschlüsselungsbetriebs mit einem sicheren Prozessor durchgeführt wird, ein zweiter Teil des Verschlüsselungsbetriebs in einem unsicheren Prozessor durchgeführt wird und die Ergebnisse innerhalb des sicheren Prozessors kombiniert werden.
Die vorliegende Erfindung kann auf andere spezifische Arten als jene ihrer offenbarten ausgeführt werden, ohne von den wesentlichen Eigenschaften der Erfindung abzuweichen. Die vorliegenden Ausführungsformen sind deswegen in jeder Hinsicht als veranschaulichend und nicht einschränkend anzusehen, und sämtliche Änderungen, die innerhalb des Bedeutungs- und Äquivalenzbereichs der angehängten Ansprüche liegen, sind als hierin eingeschlossen anzusehen.

Claims

Verfahren zum Durchführen kryptografischer Berechnungen an einer Bitkette (X) unter Verwendung eines geheimen Chiffre-Schlüssels (K_PRIV), dadurch gekennzeichnet, dass das Verfahren umfasst: Modifizieren (402) des Chiffre-Schlüssels durch ein Ändern ausgewählter Bits des Chiffre-Schlüssels, um einen modifizierten Chiffre-Schlüssel (K_PRIVM) zu erhalten; Erzeugen (402) eines Indikators (INDIC), der dem modifizierten Chiffre-Schlüssel entspricht, wobei der Indikator eine Mehrzahl von Indikatorbits aufweist, die die Änderungen, die an dem Chiffre-Schlüssel ausgeführt sind, anzeigen; Berechnen (408) eines ersten Produkts (P₁) als eine Funktion der Bitkette (X) und des modifizierten Chiffre-Schlüssels in einem unsicheren Prozessor (100); Berechnen (412) eines zweiten Produkts (P₂) als eine Funktion der Bitkette (X) und des Indikators (INDIC) in einem sicheren Prozessor (30); und Berechnen eines Endprodukts (P_F) als eine Funktion der ersten und zweiten Produkte in dem sicheren Prozessor (30), um ein kryptografisches Ergebnis an der Bitkette (X) bereit zu stellen.
Verfahren nach Anspruch 1, wobei ein Modifizieren des Chiffre-Schlüssels (K_PRIV), um einen modifizierten Chiffre-Schlüssel zu enthalten, ein Ändern zufällig ausgewählter Bits des Chiffre-Schlüssels umfasst, um den modifizierten Chiffre-Schlüssel (K_PRIVM) zu erhalten.
Verfahren nach Anspruch 2, wobei ein Erzeugen eines Indikators (INDIC), der dem modifizierten Chiffre-Schlüssel entspricht, ein Berechnen des additiven Komplements des modifizierten Chiffre-Schlüssels (K_PRIVM) umfasst, das, wenn es dem modifizierten Chiffre-Schlüssel hinzugefügt wird, den Chiffre-Schlüssel (K_PRIV) ergibt.
Verfahren nach Anspruch 1, wobei ein Berechnen des ersten Produkts (P₁) als eine Funktion der Bitkette (X) und des modifizierten Chiffre-Schlüssels (K_PRIVM) in dem unsicheren Prozessor (100) ein Durchführen einer Modulo-Potenzierung der Bitkette unter Verwendung des modifizierten Chiffre-Schlüssels als ein Exponent umfasst.
Verfahren nach Anspruch 1, wobei ein Berechnen des ersten Produkts (P₁) als eine Funktion der Bitkette (X) und des modifizierten Chiffre-Schlüssels (K_PRIVM) durch den unsicheren Prozessor (100) ein Berechnen des ersten Produkts als eine Funktion eines dritten Produkts (P₃), das von dem sicheren Prozessor (30) berechnet ist, und eines vierten Produkts (P₄) umfasst, wobei das dritte Produkt eine Funktion der Bitkette und eines kurzen Teils (K_SHORT) des Chiffre-Schlüssels ist, und wobei das vierte Produkt eine Funktion der Bitkette (X) und eines modifizierten langen Teils (K_LONGM) des Chiffre-Schlüssels ist.
Verfahren zum Durchführen von Berechnungen unter Verwendung einer geheimen Bitkette (X) und eines Chiffre-Schlüssels (K_PRIV) unter Verwendung eines unsicheren Prozessors (100), dadurch gekennzeichnet, dass das Verfahren umfasst: Teilen (602) des Chiffre-Schlüssels in erste und zweite Teile (K_SHORT, K_LONG); Berechnen, in einem sicheren Prozessor (30), eines dritten Produkts (P₃) als eine Funktion der Bitkette (X) und des ersten Teils (K_SHORT) des Chiffre-Schlüssels; Ausgeben des dritten Produkts (P₃) zu dem unsicheren Prozessor (100); Modifizieren des zweiten Teils (K_LONG) des Chiffre-Schlüssels mit dem sicheren Prozessor (30) durch ein Ändern ausgewählter Bits des zweiten Teils des Chiffre-Schlüssels, um einen modifizierten zweiten Teil (K_LONGM) des Chiffre-Schlüssels zu erhalten; Erzeugen (604) eines Indikators (INDIC), der dem modifizierten zweiten Teil des Chiffre-Schlüssels entspricht, wobei der Indikator eine Mehrzahl von Indikatorbits aufweist, die die Änderungen anzeigen, die an dem zweiten Teil (K_LONG) des Chiffre-Schlüssels ausgeführt sind; Berechnen eines ersten Produkts (P₁) mit dem unsicheren Prozessor (100) als eine Funktion des dritten Produkts (P₃) und des modifizierten zweiten Teils des Chiffre-Schlüssels; Berechnen eines zweiten Produkts (P₂) mit dem sicheren Prozessor (30) als eine Funktion der Bitkette (X) und des Indikators (INDIC); und Berechnen eines Endprodukts (P_F) mit dem sicheren Prozessor als eine Funktion des ersten Produkts (P₁) und des zweiten Produkts (P₂), um ein kryptografisches Ergebnis an der Bitkette (X) bereit zu stellen.
Verfahren nach Anspruch 6, wobei ein Teilen des Chiffre-Schlüssels (K_PRIV) in erste und zweite Teile (K_SHORT, K_LONG) ein Teilen des Chiffre-Schlüssels in einen niedrigstwertigen Teil und einen höchstwertigen Teil umfasst.
Verfahren nach Anspruch 7, wobei ein Berechnen des dritten Produkts (P₃) als eine Funktion der Bitkette (X) und des ersten Teils des Chiffre-Schlüssels ein Berechnen des dritten Produkts als eine Funktion der Bitkette und des niedrigstwertigen Teils (K_SHORT) des Chiffre-Schlüssels umfasst.
Verfahren nach Anspruch 8, wobei ein Modifizieren des zweiten Teils (K_LONG) des Chiffre-Schlüssels mit dem sicheren Prozessor (30), um den modifizierten zweiten Teil (K_LONGM) des Chiffre-Schlüssels zu erhalten, ein Modifizieren des höchstwertigen Teils des Chiffre-Schlüssels umfasst.
Verfahren nach Anspruch 9, wobei ein Berechnen des ersten Produkts (P₁) mit dem unsicheren Prozessor (100) als eine Funktion des dritten Produkts (P₃) und des modifizierten zweiten Teils (K_LONGM) des Chiffre-Schlüssels ein Auswählen sukzessiver Rechtecke (X_n) der Bitkette auf der Grundlage des modifizierten zweiten Teils des Chiffre-Schlüssels und ein Multiplizieren des dritten Produkts mit den ausgewählten sukzessiven Rechtecken umfasst.
Verfahren nach Anspruch 9, wobei ein Berechnen des zweiten Produkts (P₂) mit dem sicheren Prozessor (30) als eine Funktion der Bitkette (X) und des Indikators (INDIC) ein Auswählen eines oder mehrerer sukzessiver Rechtecke (X_n) der Bitkette auf der Grundlage des Indikators umfasst, wobei das zweite Produkt das Produkt der ausgewählten sukzessiven Rechtecke umfasst.
Berechnungsvorrichtung (10) zum Potenzieren einer Bitkette (X) mit einem geheimen Exponenten (K_PRIV), wobei die Berechnungsvorrichtung einen sicheren Prozessor (30) und einen unsicheren Prozessor (100) umfasst, umfassend eine Einrichtung, die sämtliche der Schritte, die in Anspruch 1 definiert sind, ausführt.
Berechnungsvorrichtung nach Anspruch 12, wobei das erste Produkt (P₁), das von dem unsicheren Prozessor (100) berechnet ist, die Bitkette (X) angehoben auf die Potenz des ersten Partialwerts (K_PRIVM) umfasst.
Berechnungsvorrichtung nach Anspruch 13, wobei das zweite Produkt (P₂), das von dem sicheren Prozessor (30) berechnet ist, die Bitkette (X) angehoben auf die Potenz des zweiten Partialwerts (INDIC) umfasst.
Berechnungsvorrichtung nach Anspruch 14, wobei das Endprodukt (P_F) das Produkt der ersten und zweiten Produkte (K_PRIVM, INDIC) umfasst.
Berechnungsvorrichtung nach Anspruch 12, wobei das erste Produkt (P₁), das von dem unsicheren Prozessor (100) berechnet ist, weiter als eine Funktion eines dritten Produkts (P₃) berechnet wird.
Berechnungsvorrichtung nach Anspruch 16, wobei das dritte Produkt (P₃) von dem sicheren Prozessor (30) als eine Funktion eines dritten Partialwerts (K_SHORT) und der Bitkette (X) berechnet wird.
Berechnungsvorrichtung nach Anspruch 17, wobei das dritte Produkt (P₃) die Bitkette (X) angehoben auf die Potenz des dritten Partialwerts (K_SHORT) umfasst.
Berechnungsvorrichtung nach Anspruch 18, wobei das erste Produkt (P₁) das dritte Produkt (P₃) multipliziert mit einem vierten Produkt (P₄) umfasst.
Berechnungsvorrichtung nach Anspruch 19, wobei das vierte Produkt (P₄) die Bitkette (X) angehoben auf die Potenz des ersten Partialwerts (K_LONGM) umfasst.