DE10061997A1

DE10061997A1 - Kryptographieprozessor

Info

Publication number: DE10061997A1
Application number: DE10061997A
Authority: DE
Inventors: Astrid Elbe; Norbert Janssen; Holger Sedlak
Original assignee: Infineon Technologies AG
Current assignee: Infineon Technologies AG
Priority date: 2000-12-13
Filing date: 2000-12-13
Publication date: 2002-07-18
Also published as: EP1342148A2; EP1589413A3; WO2002048845A2; WO2002048845A3; US20040105541A1; US20080140739A1; KR20030062422A; CN1481524A; EP1342148B1; ATE467172T1; US8369520B2; EP1589413A2; DE50115478D1; EP1342148B9; AU2002231668A1; EP1589413B1; CN1273876C; US7430293B2

Abstract

Ein Kryptographieprozessor umfasst eine zentrale Verarbeitungseinheit und einen Coprozessor, wobei der Coprozessor eine Mehrzahl von Teilrechenwerken sowie eine einzige Steuereinheit, die mit jedem der Mehrzahl von Teilrechenwerken gekoppelt ist, aufweist. Eine kryptographische Operation wird durch die Steuereinheit auf die einzelnen Teilrechenwerke in Form von Teiloperationen aufgeteilt. Die zentrale Verarbeitungseinheit, die Mehrzahl von Teilrechenwerken und die Steuereinheit sind auf einem einzigen Chip integriert, wobei der Chip einen gemeinsamen Versorgungsstromzugang zum Versorgen der Mehrzahl von Teilrechenwerken und der Steuereinheit mit Strom aufweist. Durch die parallel Anordnung der Teilrechenwerke wird einerseits der Durchsatz des Kryptographieprozessors erhöht. Andererseits wird jedoch auch das Stromprofil, das an dem Versorgungsstromzugang erfasst werden kann, derart zufällig gemacht, dass ein Angreifer nicht mehr auf in den einzelnen Teilrechenwerken verarbeitete Zahlen rückschließen kann.

Description

Die vorliegende Erfindung bezieht sich auf Kryptographietech niken und insbesondere auf die Architektur von für kryptogra phische Anwendungen verwendeten Kryptographieprozessoren.

Mit zunehmender Verbreitung von bargeldlosem Zahlungsverkehr, elektronischer Datenübertragung über öffentliche Netze, Aus tausch von Kreditkartennummern über öffentliche Netze und allgemein gesagt der Verwendung von sogenannten Smart Cards für Zahlungs-, Identifikations- oder Zugriffszwecke entsteht ein immer größerer Bedarf nach Kryptographietechniken. Kryp tographietechniken umfassen einerseits Kryptographiealgorith men und andererseits geeignete Prozessorenlösungen, welche die durch die Kryptographiealgorithmen vorgeschriebenen Be rechnungen ausführen. Wurden früher Kryptographiealgorithmen mit Allzweckrechnern ausgeführt, so spielten die Kosten, der Rechenzeitbedarf und die Sicherheit gegenüber verschiedenar tigsten Fremdattacken keine derart entscheidende Rolle wie heutzutage, wo kryptographische Algorithmen immer mehr auf Chipkarten oder speziellen Sicherheits-ICs ausgeführt werden, für die besondere Anforderungen gelten. So müssen solche Smart Cards einerseits preisgünstig verfügbar sein, da sie Massenprodukte sind, andererseits jedoch eine große Sicher heit gegenüber Fremdattacken aufweisen, da sie vollständig in der Gewalt des potentiellen Angreifers sind.

Darüber hinaus müssen kryptographische Prozessoren eine be achtliche Rechenleistung zur Verfügung stellen, zumal die Si cherheit von vielen kryptographischen Algorithmen, wie z. B. dem bekannten RSA-Algorithmus, entscheidend von der hänge der verwendeten Schlüssel abhängt. In anderen Worten ausgedrückt bedeutet dies, dass mit zunehmender Länge der zu verarbeiten den Zahlen auch die Sicherheit ansteigt, da ein Angriff, der auf dem Ausprobieren aller Möglichkeiten basiert, aus Rechen zeitgründen unmöglich gemacht wird.

In Zahlenwerten ausgedrückt bedeutet dies, dass Kryptogra phieprozessoren mit Integers, d. h. Ganzzahlen, umgehen müs sen, welche eine Länge von vielleicht 1024 Bits, 2048 Bits oder vielleicht sogar noch mehr haben können. Zum Vergleich verarbeiten Prozessoren in einem üblichen PC 32-Bit- bzw. 64- Bit-Ganzzahlen.

Ein hoher Rechenaufwand bedeutet jedoch auch eine hohe Re chenzeit, so dass für Kryptographieprozessoren gleichzeitig auch die wesentliche Anforderung darin besteht, einen hohen Rechendurchsatz zu erreichen, damit beispielsweise eine Iden tifikation, ein Zugang zu einem Gebäude, eine Bezah lungstransaktion oder eine Kreditkartenübermittlung nicht viele Minuten dauert, was für die Marktakzeptanz sehr schäd lich wäre.

Zusammenfassend lässt sich daher feststellen, dass Kryptogra phieprozessoren sicher, schnell und daher außerordentlich leistungsstark sein müssen.

Eine Möglichkeit, um den Durchsatz durch einen Prozessor zu erhöhen, besteht darin, eine zentrale Verarbeitungseinheit mit einem oder mehreren Coprozessoren, welche parallel arbei ten, auszustatten, wie es beispielsweise bei modernen PCs oder aber auch bei modernen Graphikkarten der Fall ist. Ein solches Szenario ist in Fig. 7 gezeigt. Fig. 7 zeigt eine Computerplatine 800, auf der eine CPU 802, ein Arbeitsspeicher (RAM) 804, ein erster Coprozessor 806, ein zweiter Co prozessor 808 sowie ein dritter Coprozessor 810 angeordnet sind. Die CPU 802 ist mit den drei Coprozessoren 806, 808, 810 über einen Bus 812 verbunden. Ferner kann für jeden Co prozessor ein eigener Speicher vorgesehen sein, welcher nur für Operationen des Coprozessors dient, d. h. ein Speicher 1 814, ein Speicher 2 816 für den Coprozessor 2 sowie ein Spei cher 3 818 für den Coprozessor 3.

Ferner wird jeder Chip, der auf der in Fig. 7 gezeigten Com puterplatine 800 angeordnet ist, über einen eigenen Strom- bzw. Spannungsversorgungsanschluss I₁ bis I₈ mit der für das Funktionieren der elektronischen Komponenten innerhalb der einzelnen Elemente benötigten elektrischen Leistung versorgt. Für die Platine kann alternativ auch nur eine Stromversorgung vorhanden sein, die dann über die Platine zu den einzelnen Chips auf der Platine verteilt wird. Dabei stehen jedoch die Versorgungsleitungen zu den einzelnen Chips für einen Angrei fer zur Verfügung.

Das in Fig. 7 gezeigte Konzept für übliche Computeranwendun gen ist aus mehreren Gründen für Kryptographieprozessoren un geeignet. Zum einen sind alle Elemente für die Kurzzahl- Arithmetik aufgeführt, während Kryptographieprozessoren Lang zahlarithmetik-Operationen durchführen müssen.

Des weiteren weist jeder Chip auf der Computerplatine 800 ei nen eigenen Strom- bzw. Leistungszugang auf, auf den ohne weiteres von einem Angreifer zugegriffen werden kann, um Lei stungsprofile oder Stromprofile über der Zeit abzugreifen. Das Abgreifen von Leistungsprofilen über der Zeit ist die Ba sis für eine Vielzahl von effizienten Attacken gegenüber Kryptographieprozessoren. Weitere Hintergründe bzw. eine detaillierte Darstellung verschiedener Attacken gegen Krypto graphieprozessoren sind in "Information Leakage Attacks Against Smart Card Implementations of Cryptographic Algo rithms and Countermeasures", Hess u. a., Eurosmart Security Conference, 13. Juni bis 15. Juni 2000, dargestellt. Als Ge genmaßnahmen werden Implementationen vorgeschlagen, welche darauf aufbauen, dass verschiedene Operationen immer die gleiche Zeit benötigen, so dass ein Angreifer aufgrund eines Leistungsprofils nicht ersehen kann, ob der Kryptoprozessor eine Multiplikation, eine Addition oder irgend etwas anderes ausgeführt hat.

In "Design of Long Integer Arithmetic units for Public-Key Algorithms", Hess u. a. Eurosmart Security Conference, 13. Juni bis 15. Juni 2000 wird auf verschiedene Rechenoperatio nen eingegangen, welche von Kryptographie-Prozessoren aus führbar sein müssen. Insbesondere wird auf die modulare Mul tiplikation, Verfahren zur modularen Reduktion sowie auf das sogenannten ZDN-Verfahren eingegangen, das in dem deutschen Patent DE 36 31 992 C2 dargestellt ist.

Das ZDN-Verfahren basiert auf einer Seriell/Parallel- Architektur unter Verwendung von parallel ausführbaren Look- Ahead Algorithmen für die Multiplikation und die modulare Re duktion, um eine Multiplikation zweier Binärzahlen in eine iterative 3-Operanden-Addition unter Verwendung von Look- Ahead-Parametern für die Multiplikation und die modulare Re duktion zu transformieren. Hierzu wird die modulare Multipli kation in eine serielle Berechnung von Partialprodukten zer legt. Zu Beginn der Iteration werden zwei Partialprodukte ge bildet und dann unter Berücksichtigung der modularen Redukti on zusammenaddiert, um ein Zwischenergebnis zu erhalten. Hierauf wird ein weiteres Partialprodukt gebildet und wieder unter Berücksichtigung der modularen Reduktion zu dem Zwi schenergebnis hinzuaddiert. Diese Iteration wird fortgesetzt, bis sämtliche Stellen des Multiplikators abgearbeitet sind. Für die Drei-Operanden-Addition umfasst ein Kryptocoprozessor ein Addierwerk, welches in einem aktuellen Iterationsschritt die Summation eines neuen Partialprodukts zu dem Zwischener gebnis des vorausgehenden Iterationsschritts durchführt.

So könnte jeder Coprozessor von Fig. 7 mit einer eigenen ZDN- Einheit ausgestattet sein, um mehrere modulare Multiplikatio nen parallel auszuführen, um für bestimmte Anwendungen den Durchsatz zu erhöhen. Diese Lösung würde jedoch wiederum dar an scheitern, dass ein Angreifer von jedem Chip einzeln die Stromprofile eruieren könnte, so dass zwar eine Erhöhung des Durchsatzes erreicht worden ist, jedoch auf Kosten der Si cherheit des Kryptographie-Rechners.

Die Aufgabe der vorliegenden Erfindung besteht darin, einen schnellen und sicheren Kryptographieprozessor zu schaffen.

Diese Aufgabe wird durch einen Kryptographieprozessor nach Patentanspruch 1 gelöst.

Der vorliegenden Erfindung liegt die Erkenntnis zugrunde, dass ein schneller Kryptographieprozessor nur erreicht werden kann, wenn eine Kryptographie-Rechenoperation in mehrere Tei loperationen zerlegt wird, und diese Teiloperationen von par allel angeordneten Teilrechenwerken ausgeführt werden. Ande rerseits kann eine Sicherheit insbesondere gegen Leistungsab hörattacken nur erreicht werden, wenn sämtliche Teilrechen werke einschließlich der Steuereinheit für die Teilrechenwer ke und der zentralen Verarbeitungseinheit auf einem einzigen Chip angeordnet werden, so dass die Leistungszugänge für die einzelnen Komponenten nicht für einen äußeren Angreifer zur Verfügung stehen.

Anders ausgedrückt sind die zentrale Verarbeitungseinrichtung und der Coprozessor, der eine einzige Steuereinheit sowie die Mehrzahl von Teilrechenwerken aufweist, auf einem einzigen Chip integriert. Darüber hinaus weist dieser einzige Chip le diglich einen einzigen Versorgungszugang zum Versorgen der Mehrzahl von Teilrechenwerken, der Steuereinheit und der zen tralen Verarbeitungseinheit mit Strom auf.

Das Integrieren dieser Komponenten auf einem Chip und das Versorgen des Chips mit einem Versorgungsstromzugang hat den Vorteil, dass sich am Stromanschluss des Kryptographieprozes sors die Stromprofile, die den Operationen der Teilrechenwer ke zugeordnet sind, überlagern. Wenn beispielsweise zwei Teilrechenwerke parallel arbeiten, so überlagern sich die Stromprofile dieser beiden Teilrechenwerke, derart, dass es für den Angreifer schwierig wird, anhand des Leistungsversor gungsprofils zu erkennen, welche Operationen mit welchen Zah len die beiden Teilrechenwerke gleichzeitig durchführen. Wird die Anzahl der Teilrechenwerke erhöht, so wird auch das Stromprofil an dem einzigen Versorgungsanschluss immer homo gener. Durch zunehmende parallele Verarbeitung mit zunehmen der Anzahl von parallelen Teilrechenwerken steigt jedoch auch der Durchsatz, so dass sich beim erfindungsgemäßen Konzept mit zunehmendem Durchsatz auch die Sicherheit erhöht. Im Stand der Technik war dies nicht der Fall, ganz im Gegenteil verringerte sich die Sicherheit mit zunehmendem Durchsatz.

Eine Grenze der parallelen Verarbeitung ist dann erreicht, wenn der Rechenaufwand in der Steuereinheit zum Verteilen der Teiloperationen auf die Teilrechenwerke und zum Ansteuern der einzelnen Teilrechenwerke stark zunimmt. Für relativ lang dauernde Operationen, wie z. B. die Multiplikation von zwei sehr langen Ganzzahlen, ist jedoch das Verhältnis von Rechen zeit in einem Teilrechenwerk zu der Rechenzeit der Steuerein heit für Organisations- und Verwaltungsaufgaben so groß, dass ein beachtlicher Grad an Parallelität erreicht werden kann, ohne dass der Verwaltungsaufwand in problematische Größenord nungen kommt.

Dieser Grad an Parallelität ist jedoch nötig, um den Durch satz so weit zu erhöhen, dass Geschwindigkeitsverluste der Logikeinheiten ausgeglichen werden können, welche auftreten, wenn sowohl Logikbausteine als auch Speicherbausteine auf demselben Chip integriert werden. Allgemein besteht die Be strebung, Logikbausteine und Speicherbausteine auf getrennten Chips anzuordnen, da sich die Technologien für diese beiden Bauelemente unterscheiden. Anders ausgedrückt erlaubt eine Speicher-Technologie, mit der Logikbausteine hergestellt wer den, keine so schnellen Logikbausteine, als wenn die Logik bausteine mit einer speziell für Logikbausteine angepassten Technologie hergestellt werden. Daher sind bei dem in Fig. 7 gezeigten Beispiel der einfachen Parallelschaltung verschie dener Coprozessoren immer Speicher und Rechenwerke auf ge trennten Bausteinen implementiert.

Für eine hohe Sicherheit ist es jedoch gerade wichtig, dass ein Angreifer nicht die Kommunikation zwischen einem Rechen werk und einem Register abhören kann.

Bevorzugte Ausführungsbeispiele der vorliegenden Erfindung werden nachfolgend bezugnehmend auf die beiliegenden Zeich nungen detailliert erläutert. Es zeigen:

Fig. 1 einen erfindungsgemäßen Kryptoprozessor, der auf einem einzigen Chip integriert ist;

Fig. 2 eine detailliertere Darstellung des Coprozessors, welcher verschiedene Teilrechenwerke mit unter schiedlich langen Registern aufweist;

Fig. 3 eine detailliertere Darstellung einer Arithmeti keinheit, welche für eine Drei-Operanden-Addition geeignet ist;

Fig. 4a ein schematisches Flussdiagramm zum Durchführen ei ner modularen Multiplikation auf seriell/parallele Art und Weise;

Fig. 4b ein Zahlenbeispiel zur Veranschaulichung der seri ell/parallelen Arbeitsweise einer Arithmetikeinheit am Beispiel einer Multiplikation;

Fig. 5 ein Beispiel zum Aufteilen einer modularen Exponen tation in eine Anzahl von modularen Multiplikatio nen;

Fig. 6 ein weiteres Beispiel zum Aufteilen einer modularen Multiplikation auf verschiedene Teilrechenwerke; und

Fig. 7 eine Computerplatine mit einer Vielzahl von ge trennt versorgten Bauelementen.

Bevor detaillierter auf die einzelnen Figuren eingegangen wird, wird im nachfolgenden ausgeführt, weshalb durch Paral lelschaltung mehrerer Teilrechenwerke, die auf einem Chip angeordnet sind und durch eine Steuereinheit, die auf demselben Chip angeordnet ist, gesteuert werden, eine höhere Sicherheit erreicht wird.

Kryptoprozessoren werden für sicherheitskritische Anwendung benutzt, beispielsweise für digitale Signaturen, Authentifi kationen oder Verschlüsselungsaufgaben. Ein Angreifer möchte beispielsweise den geheimen Schlüssel herausfinden, um da durch das Kryptographieverfahren zu brechen. Kryptographie prozessoren werden beispielsweise in Chipkarten eingesetzt, welche, wie es bereits ausgeführt worden ist, Smart Cards oder Signaturkarten für eine rechtsverbindliche elektronische Unterschrift oder auch für Homebanking oder zum Bezahlen mit dem Mobiltelephon usw. umfassen. Alternativ werden solche Kryptoprozessoren auch in Computern und Servern als Sicher heits-IC eingesetzt, um eine Authentifikation durchzuführen, oder um Verschlüsselungsaufgaben wahrnehmen zu können, welche beispielsweise im sicheren Bezahlen über das Internet, in so genannten SSL-Sessions (SSL = Secure Socket Layer), d. h. der sicheren Übermittlung von Kreditkartennummern, bestehen kön nen.

Typische physikalische Angriffe messen den Stromverbrauch (SPA, DPA, Timing-Attacken) oder die elektromagnetische Ab strahlung. Bezüglich einer näheren Erläuterung der Angriffe sei auf die eingangs erwähnten Literaturstellen verwiesen.

Da die Angreifer bei der heutigen Halbleitertechnologie, wel che Strukturen im Bereich von typischerweise kleiner oder gleich 250 Nanometern erreicht, nur sehr schwer lokale Strom messungen durchführen können, wird bei einem Angriff typi scherweise der Stromverbrauch der gesamten Chipkarte ein schließlich CPU und Coprozessor gemessen, welcher sich aus der Summe der einzelnen Stromverbräuche von beispielsweise der CPU, dem RAM, einem ROM, einem EPROM, einem Flash- Memory, einer Zeitsteuereinheit, einem Zufallszahlengenerator (RNG), einem DES-Modul und dem Kryptocoprozessor zusammen setzt.

Da der Kryptocoprozessor typischerweise den größten Stromver brauch hat, kann ein Angreifer sehen, wann der Kryptocopro zessor zu rechnen beginnt. Um dies zu vermeiden, wäre ein über der Zeit vollständig konstanter Stromverbrauch das Ziel, ein Angreifer würde dann nicht mehr erkennen, wann der Kryp tocoprozessor zu rechnen beginnt. Dieses ideale Ziel kann nicht erreicht werden, es wird jedoch durch das erfindungsge mäße Parallelschalten von Teilrechenwerken ein möglichst gleichförmiges "Rauschen" um einen Mittelwert angestrebt.

Der Stromverbrauch eines beispielsweise in CMOS-Technologie gefertigten Chips ändert sich bei einer Umschaltung von einer "0" auf eine "1". Daher ist der Stromverbrauch datenabhängig sowie abhängig von den verwendeten Befehlen der CPU und des Kryptocoprozessors.

Schaltet man nun mehrere Teilrechenwerke parallel und lässt sie mehrere Operationen bzw. Teiloperationen parallel abar beiten, oder wird eine Operation auf mehrere Teilrechenwerke aufgeteilt, so überlagern sich, wie es ausgeführt worden ist, die Stromprofile, welche durch die Daten- und Befehlsverar beitung entstehen.

Je mehr Teilrechenwerke parallel arbeiten, desto schwieriger kann auf Daten und Befehle in den einzelnen Teilrechenwerken bzw. in der Steuereinheit zurückgeschlossen werden, da die Daten und Befehle in jedem Teilrechenwerk üblicherweise unterschiedlich sein werden, der Angreifer jedoch nur die Über lagerung unterschiedlicher Befehle sieht.

Fig. 1 zeigt einen erfindungsgemäßen Kryptoprozessor zum Durchführen von Operationen für kryptographische Anwendungen. Der Kryptoprozessor ist auf einem einzigen Chip 100 implemen tiert und umfasst eine zentrale Verarbeitungseinheit (CPU) 102 und einen Coprozessor 104. Der Coprozessor 104 ist, wie es in Fig. 1 gezeigt ist, auf demselben Chip angeordnet wie die zentrale Verarbeitungseinheit 102. Der Coprozessor um fasst eine Mehrzahl von Teilrechenwerken 106, 108, 110 und 112, wobei jedes Teilrechenwerk 106 bis 112 eine eigene arithmetische Einheit AU aufweist. Vorzugsweise umfasst jedes Teilrechenwerk 106 bis 112 neben der AU auch zumindest ein Register (REG), um, wie es bezugnehmend auf Fig. 2 ausgeführt wird, Zwischenergebnisse speichern zu können.

Ein typischer Kryptoprozessor wird eine Eingangsschnittstelle 114 und eine Ausgangsschnittstelle 116 umfassen, welche mit äußeren Anschlüssen für eine Dateneingabe bzw. eine Datenaus gabe sowie mit der CPU 102 verbunden sind. Typischerweise ist der CPU 102 ein eigener Speicher 118 zugeordnet, der in Fig. 1 mit RAM bezeichnet ist. Unter anderem kann der Kryptopro zessor noch einen Taktgenerator 120, weitere Speicher, Zu fallszahlengeneratoren etc. umfassen, welche in Fig. 1 nicht gezeigt sind.

Es sei darauf hingewiesen, dass sämtliche in Fig. 1 darge stellten Elemente auf einem einzigen Chip implementiert sind, welcher durch einen einzigen Stromversorgungsanschluss 122 mit Leistung versorgt wird. Der Chip 100 umfasst intern Stromversorgungsleitungen zu sämtlichen in Fig. 1 gezeigten Elementen, welche jedoch aus oben angegebenen Gründen nicht einzeln abgehört werden können. Dagegen stellt es ein Leich tes dar, den Stromversorgungsanschluss 122 abzuhören. Im Ge gensatz zu der in Fig. 7 gezeigten Platine, bei der die Stromversorgungsanschlüsse jeder einzelnen Komponente sehr leicht abhörbar sind, und daher sehr "ausdrucksstarke" Strom profile haben, ist das am Stromversorgungsanschluss 122 an liegende Stromprofil nahezu konstant bzw. weist ein möglichst homogenes Rauschen um einen konstanten Wert auf. Dies ist darauf zurückzuführen, dass der Coprozessor 104, welcher am meisten zum Stromverbrauch beiträgt, eine Mehrzahl von paral lel angeordneten Teilrechenwerken aufweist, die unabhängig voneinander beispielsweise von "0" auf "1" umschalten und da her unkorreliert voneinander Strom verbrauchen.

Die Parallelschaltung der einzelnen Teilrechenwerke führt zu dem dazu, dass der Durchsatz des Kryptonprozessors erhöht werden kann, so dass im Falle der Ausführung eines Speichers auf dem Chip die damit einhergehenden Geschwindigkeitseinbu ßen, welche aufgrund unterschiedlicher Technologien für Speicher und Rechenwerke auftreten, mehr als ausgeglichen werden können.

Gemäß einem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung können zwei oder mehr Teilrechenwerke als sogenann te Cluster zusammengefasst werden, derart, dass z. B. ein er ster Cluster Teiloperationen einer ersten Operation durch führt, während ein zweiter Cluster Teiloperationen einer zweiten kryptographischen Operation durchführt. So könnte beispielsweise der erste Cluster, der aus den Teilrechenwer ken 106 und 108 besteht, z. B. zwei modulare Exponentiationen mit jeweils der halben Länge durchführen, welche aus einer einzigen modularen Exponentation mit voller Länge hergeleitet sind, während der zweite Cluster, der aus den Teilrechenwerken 110 und 112 besteht eine modulare Multiplikation durch führen könnte, wie es in Fig. 6 dargestellt ist.

Alternativ könnte ein Cluster eine RSA-Operation durchführen, während ein anderer Cluster eine DES-Operation durchführt, und wieder ein anderer Cluster beispielsweise eine Hash-Summe berechnet.

An dieser Stelle sei ausgeführt, dass die angesprochenen Kryptographiealgorithmen in der Literatur bekannt sind und daher nicht näher ausgeführt werden. Lediglich beispielhaft sei darauf hingewiesen, dass beispielsweise bei einer RSA- Verschlüsselung Operanden mit einer Länge von 2048 Bit verar beitet werden. Bei der Entschlüsselung ist es mit Hilfe des chinesischen Restsatzes (CRT) möglich, mit halb so langen Operanden und zwei Teiloperationen zu arbeiten. Ist ein Kryp tographieprozessor lediglich auf einen solchen Algorithmus ausgelegt, so beträgt die Anzahl der Teilrechenwerke 2 und die Länge der arithmetischen Einheiten würde statt 2048 für eine einzige arithmetische Einheit lediglich 1024 betragen. Die Teiloperationen gemäß dem chinesischen Restsatz werden parallel bearbeitet und dann gesteuert durch die Steuerein heit in einem der beiden Teilrechenwerke kombiniert, um das Ergebnis zu erhalten.

Fig. 2 zeigt eine detailliertere Darstellung des in Fig. 1 gezeigten Coprozessors 104. Das Teilrechenwerk 106 umfasst neben der arithmetischen Einheit 106a z. B. drei Register 106b, 106c, 106d. Das Teilrechenwerk 108 umfasst analog dazu die arithmetische Einheit 108a sowie beispielsweise ebenfalls drei Register 108b, 108c, 108d. Dasselbe trifft für das Teil rechenwerk 112 zu. Wie es in Fig. 2 gezeigt ist, kann sich die Länge der Register eines Teilrechenwerks von der Länge des Registers eines anderen Teilrechenwerks unterscheiden, so dass beispielsweise mit dem Teilrechenwerk 106 Operationen mit Zahlen einer Länge L₁ durchgeführt werden können, während mit dem Teilrechenwerk 102 Operationen mit Zahlen einer Länge L₂ durchgeführt werden können.

Die Steuereinheit 105 kann die beiden Teilrechenwerke 106 und 108 beispielsweise auch derart ansteuern, dass die arithme tischen Einheiten AU₁ und AU₂ so miteinander verkoppelt wer den, dass beide Teilrechenwerke, welche dann einen Cluster bilden, arithmetische Operationen mit Zahlen einer Länge L₁ + L₂ durchführen. Die Register der beiden Teilrechenwerke kön nen somit zusammengeschaltet werden.

Alternativ kann einem Teilrechenwerk jedoch auch eine Anzahl von Registern exklusiv zugewiesen werden, welche so groß ist, dass die Operanden für mehrere Teiloperationen, wie z. B. mo dulare Multiplikationen oder modulare Exponentiationen, aus reichen. Zur Vermeidung von Informationslecks können die Tei loperationen dann beispielsweise durch eine Einrichtung zum Variieren der Reihenfolge derselben, die in Fig. 2 mit 200 bezeichnet ist, überlagert oder sogar zufällig vermischt wer den, um noch eine weitere Verschleierung des Stromprofils zu erreichen. Dies wird besonders dann vorteilhaft sein, wenn beispielsweise lediglich zwei Teilrechenwerke vorhanden sind bzw. lediglich zwei Teilrechenwerke arbeiten, während die an deren Teilrechenwerke eines Kryptographieprozessors gerade stillstehen.

Gemäß einem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung umfasst die Steuereinheit 105 ferner eine in Fig. 2 nicht gezeigte Einrichtung zum Abschalten von Teilrechenwer ken bzw. Registern von Teilrechenwerken, wenn dieselben nicht benötigt werden, was besonders für batteriebetriebene Anwen dungen von Vorteil sein kann, um den Stromverbrauch der Ge samt-Schaltung zu sparen. CMOS-Bauelemente benötigen zwar nur signifikant Strom, wenn umgeschaltet wird, sie haben jedoch auch einen Ruhestromverbrauch, welcher dann ins Gewicht fal len kann, wenn die zur Verfügung stehende Leistung begrenzt ist.

Wie es bereits ausgeführt worden ist, hat ein Kryptoprozessor aufgrund der langen Zahlen, die er verarbeiten muss, die Ei genschaft, dass bestimmte Teiloperationen, wie z. B. eine Se riell/Parallel-Multiplikation, wie sie bezugnehmend auf die Fig. 4a und 4b dargestellt wird, ziemlich viel Zeit benötigt. Bevorzugterweise sind die Teilrechenwerke derart ausgeführt, dass sie eine solche Teiloperation selbständig ohne Eingriffe der Steuereinheit 105 durchführen können, nachdem die Steuer einheit den erforderlichen Befehl an das Rechenwerk abgegeben hat. Hierzu benötigt jedes Teilrechenwerk selbstverständlich Register zum Speichern der Zwischenlösungen.

Aufgrund der Tatsache, dass ein Teilrechenwerk ohne Input der Steuereinheit 105 relativ lange arbeitet, kann die Steuerein heit 105 eine Vielzahl von einzelnen Teilrechenwerken gewis sermaßen seriell, also nacheinander, mit den nötigen Befehlen versehen, derart, dass sämtliche Teilrechenwerke parallel ar beiten, jedoch gewissermaßen gestaffelt zueinander.

Zum Beispiel wird das erste Teilrechenwerk zu einem bestimm ten Zeitpunkt aktiviert. Ist die Steuereinheit 105 mit der Aktivierung des ersten Teilrechenwerks fertig, so führt die selbe unmittelbar die Aktivierung des zweiten Rechenwerks durch, während das erste Rechenwerk bereits arbeitet. Das rung des zweiten Teilrechenwerks vollendet ist. Dies bedeu tet, dass während der Aktivierung des dritten Teilrechenwerks das erste und das zweite Teilrechenwerk bereits rechnen. Wenn dies für alle n Teilrechenwerke durchgeführt wird, so arbei ten alle Telirechenwerke zeitlich versetzt. Wenn alle Teilre chenwerke derart arbeiten, dass ihre Teiloperationen gleich lang dauern, so wird das erste Teilrechenwerk als erstes fer tig sein. Nun kann die Steuereinheit die Ergebnisse vom er sten Teilrechenwerk zur zentralen Verarbeitungseinheit über mitteln und ist mit dieser Übermittlung idealerweise fertig, bevor das zweite Teilrechenwerk fertig ist. Damit kann der Durchsatz wesentlich erhöht werden, wobei auch eine optimale Ausnutzung der Rechenkapazität der Steuereinheit 105 erreicht wird. Wenn sämtliche Teilrechenwerke identische Operationen ausführen, so entsteht dennoch ein stark verschleiertes Stromprofil, da sämtliche Teilrechenwerke zeitlich versetzt arbeiten. Anders wäre der Fall, wenn sämtliche Teilrechenwer ke durch die Steuereinheit zum gleichen Zeitpunkt aktiviert werden und gewissermaßen vollständig synchron arbeiten. Dann würde ein nicht verschleiertes Stromprofil und sogar noch verstärktes Stromprofil resultieren. Daher ist das serielle Aktivieren der Teilrechenwerke auch im Hinblick auf die Si cherheit des Kryptographieprozessors vorteilhaft.

Im nachfolgenden wird auf Fig. 3 eingegangen, welche eine Vorrichtung zum Durchführen einer Drei-Operanden-Addition darstellt, wie sie rechts in Fig. 3 formelmäßig angegeben ist. In der Formel rechts in Fig. 3 ist dargestellt, dass Ad dition und Subtraktion gleichermaßen ausgeführt werden, da ein Operand einfach mit dem Faktor "-1" multipliziert werden muss, um zu einer Subtraktion zu kommen. Die Drei-Operanden- Addition wird mittels eines Drei-Bit-Addierers, welcher ohne Übertrag arbeitet, d. h. eines Halbaddierers, und eines nachgeschalteten Zwei-Bit-Addierers, durchgeführt, welcher mit Übertrag arbeitet, d. h. welcher ein Volladdierer ist. Alter nativ kann auch der Fall auftreten, daß zum Operanden Z nur der Operand N, nur der Operand P oder gar kein Operand hinzu zuaddieren bzw. zu subtrahieren ist. Dies ist in Fig. 3 durch die "Null" unter dem Plus/Minus-Zeichen symbolisiert und wird durch die in Fig. 4a dargestellten sogenannten Look-Ahead parameter a_i, b_i symbolisiert, die in jedem Iterationsschritt erneut berechnet werden.

Fig. 3 zeigt einen sogenannten Bit-Slice eines solchen Ad dierwerks. Für die Addition von drei Zahlen mit beispielswei se 1024 Binärstellen würde die in Fig. 3 gezeigte Anordnung für einen vollständig parallelen Betrieb 1024 mal in der arithmetischen Einheit eines Rechenwerks 106 vorhanden sein.

Bei einem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung ist jedes Teilrechenwerk 106 bis 112 (Fig. 1) ange ordnet, um eine modulare Multiplikation unter Verwendung des Look-Ahead-Algorithmus auszuführen, der in der DE 36 31 992 C2 dargelegt ist.

Eine hierfür erforderliche modulare Multiplikation wird an hand von Fig. 4b erläutert. Es besteht die Aufgabe, die Bi närzahlen "111" und "101" miteinander zu multiplizieren. Hierzu wird in einem Teilrechenwerk diese Multiplikation ana log einer Multiplikation zweier Zahlen gemäß der bekannten "Schulmathematik" ausgeführt, jedoch mit binärer Zahlendar stellung. Aufgrund der Einfachheit der Darstellung wird nach folgend der Fall betrachtet, in dem kein Look-Ahead- Algorithmus und keine Modulo-Reduktion eingesetzt wird. Wenn dieser Algorithmus durchgeführt wird, so ergibt sich zunächst ein erstes Partialprodukt "111". Dieses Partialprodukt wird dann, um seine Signifikanz zu berücksichtigen, um eine Stelle nach links verschoben. Zu dem ersten nach links verschobenen Partialprodukt, das als Zwischenergebnis eines ersten Itera tionsschritts aufgefaßt werden kann, wird dann, in einem zweiten Iterationsschritt das zweite Partialprodukt "000" hinzuaddiert. Das Ergebnis dieser Addition wird dann wieder um eine Stelle nach links verschoben. Das verschobene Ergeb nis dieser Addition ist dann das aktualisierte Zwischenergeb nis. Zu diesem aktualisierten Zwischenergebnis wird dann das letzte Partialprodukt "111" hinzuaddiert. Das erhaltene Er gebnis ist dann das Endergebnis der Multiplikation. Es ist zu sehen, daß die Multiplikation in zwei Additionen und zwei Verschiebungsoperationen aufgeteilt worden ist.

Es ist ferner zu sehen, daß der Multiplikand M das Partial produkt darstellt, wenn die betrachtete Stelle des Multipli kators eine binäre "1" ist. Das Partialprodukt ist hingegen 0, wenn die betrachtete Stelle des Multiplikators eine binäre "0" ist. Ferner werden durch die jeweiligen Verschiebungsope rationen die Stellen bzw. die Wertigkeiten der Partialproduk te berücksichtigt. In Fig. 4b ist dies durch das versetzte Auftragen der Partialprodukte dargestellt. Hardwaremäßig wer den für die Addition von Fig. 4b zwei Register Z₁ und Z₂ be nötigt. Das erste Partialprodukt könnte in dem Register Z₁ gespeichert werden und dann in diesem Register um ein Bit nach links geschoben werden. Das zweite Partialprodukt könnte in dem Register Z₂ gespeichert werden. Die Zwischensumme könnte dann wieder im Register Z₁ gespeichert werden und dann wieder um ein Bit nach links geschoben werden. Das dritte Partialprodukt würde wieder im Register Z₂ gespeichert wer den. Das Endergebnis würde dann im Register Z₁ stehen.

Ein schematisches Flussdiagramm für das in Fig. 4b gezeigte Verfahren findet sich in Fig. 4a. Zunächst werden in einem Schritt S10 die in einem Teilrechenwerk vorhandenen Register initialisiert. In einem Schritt S12 wird anschließend, nach dem Initialisieren, eine Drei-Operanden-Addition durchge führt, um das erste Partialprodukt zu berechnen. Es sei dar auf hingewiesen, dass für das einfache in Fig. 4b gegebene Beispiel, das eine Multiplikation ohne Modulo-Operation dar stellt, die in Figur S12 bezeichnete Gleichung lediglich Z, a₁ und P₁ umfassen würde. a₁ kann als erster Look-Ahead- Parameter bezeichnet werden. In der allereinfachsten Ausfüh rung hat a einen Wert von "1", wenn die betrachtete Stelle des Multiplikators O eine 1 ist. a ist gleich Null, wenn die betrachtete Stelle des Multiplikators eine Null ist.

Die in Block S12 dargestellte Operation wird parallel für al le beispielsweise 1024 Bit durchgeführt. Daraufhin wird in einem Schritt S14 im einfachsten Fall eine Verschiebungsope ration um eine Position nach rechts durchgeführt, um zu be rücksichtigen, dass das höchstwertige Bit des 2. Partialpro dukts eine Stelle niedriger angeordnet ist als das höchstwer tige Bit des 1. Partialprodukts. Haben mehrere aufeinander folgende Bits des Multiplikators 0 eine Null, so findet eine Verschiebung um mehrere Positionen nach rechts statt. Schließlich wird in einem Schritt S16 wieder die parallele Drei-Operanden-Addition beispielsweise unter Verwendung der in Fig. 3 gezeigten Addiererkette, durchgeführt.

Dieses Verfahren wird fortgesetzt, bis alle beispielsweise 1024 Partialprodukte aufaddiert sind. Seriell/Parallel bedeu tet also die parallele Durchführung in dem Block S12 oder S16, und das serielle Verarbeiten, um nacheinander alle Par tialprodukte miteinander zu kombinieren.

Im nachfolgenden wird auf die Fig. 5 bis 7 eingegangen, um einige Beispiele dafür zu geben, wie eine Operation in be stimmte Teiloperationen aufgeteilt werden kann. Betrachtet wird in Fig. 5 die Operation x^d mod N. Zur Zerlegung dieser modularen Exponentiation wird der Exponent d in binärer Schreibweise dargestellt. Wie es in Fig. 5 dargestellt ist, ergibt sich dadurch eine Kette von modularen Multiplikatio nen, wobei, wie es ebenfalls in Fig. 5 dargestellt ist, jede modulare Einzeloperation je einem Teilrechenwerk zugeordnet werden kann, derart, dass sämtliche modularen Operationen parallel durch den in Fig. 1 gezeigten Kryptographieprozessor ausgeführt werden. Die dann erhaltenen Zwischenergebnisse werden, nachdem sie parallel ermittelt worden sind, aufmulti pliziert, um das Ergebnis zu erhalten. Die Steuereinheit 105 steuert dabei die Aufteilung auf die einzelnen Teilrechenwer ke TRW₁ bis TRW_k und dann das abschließende Aufmultiplizieren der einzelnen Zwischenergebnisse.

In Fig. 6 ist ein weiteres Beispiel für eine Aufteilung einer Operation (a.b) mod c in mehrere modulare Operationen ge zeigt. Wieder kann das Teilrechenwerk TRW₁ ein erstes Zwi schenergebnis ermitteln. Die Teilrechenwerke TRW₂ bis TRW_n berechnen ebenfalls Zwischenergebnisse, woraufhin, nach Er halten der Zwischenergebnisse, die Steuereinheit 105 die Auf multiplikation der Zwischenergebnisse steuert. Die Steuerein heit steuert die Aufsummation z. B. so, daß sie ein Teilre chenwerk auswählt, das dann die Zwischenergebnisse zur Auf summation erhält. Auch hier wird also eine Operation in meh rere voneinander unabhängige Teiloperationen aufgeteilt.

Es sei darauf hingewiesen, dass viele Möglichkeiten bestehen, um die eine oder andere Operation in Teiloperationen aufzuteilen. Die in Fig. 5 und 6 gegebenen Beispiele dienen ledig lich zur Veranschaulichung der Möglichkeiten zur Aufteilung einer Operation in eine Mehrzahl von Teiloperationen, wobei durchaus günstigere Aufteilungen hinsichtlich der erreichba ren Performance existieren können. Wesentlich an den Beispie len ist somit nicht die Performance des Prozessors, sondern daß Aufteilungen existieren, so dass jedes Teilrechenwerk ei ne unabhängige Teiloperation durchführt, und dass eine Mehr zahl von Teiloperationen von einer Steuereinheit gesteuert wird, um ein möglichst verschleiertes Stromprofil am Stro meingang in den Chip zu erhalten.

Bezugszeichenliste

100

Chip

102

CPU

104

Coprozessor

105

Steuereinheit

106

Teilrechenwerk

1

108

Teilrechenwerk

2

110

Teilrechenwerk

3

112

Teilrechenwerk n

114

Eingangsschnittstelle

116

Ausgangsschnittstelle

118

RAM

120

Taktgenerator

122

Stromversorgungsanschluß

106

a arithmetische Einheit

1

106

b Register

1

106

c Register

2

106

d Register

3

108

a arithmethische Einheit

2

108

b Register

1

108

c Register

2

108

d Register

3

200

Einrichtung zum Variieren der Reihenfolge

800

Computerplatine

802

CPU

804

RAM

806

erster Coprozessor

808

zweiter Coprozessor

810

dritter Coprozessor

812

Bus

814

Speicher

1

816

Speicher

2

818

Speicher

3

I₁

-I₈

Stromversorgungsanschlüsse

Claims

1. Kryptographieprozessor zum Durchführen von Operationen für kryptographische Anwendungen, mit folgenden Merkmalen:
einer zentralen Verarbeitungseinheit (102) zum Erhalten von Befehlen für das Ausführen einer Operation und zum Ausgeben von Ergebnissen einer Operation;
einem Coprozessor (104), der mit der zentralen Verarbeitungs einheit (102) gekoppelt ist, wobei der Coprozessor folgende Merkmale aufweist:
eine Mehrzahl von Teilrechenwerken (106, 108, 110, 112), wobei jedes Teilrechenwerk zumindest eine arithmetische Einheit (AU₁, AU₂, AU₃, AU_n) aufweist; und
eine einzige Steuereinheit (105), die mit jedem der Mehrzahl von Teilrechenwerken gekoppelt ist, und die an geordnet ist, um eine Operation in Teiloperationen auf zuteilen, die Teiloperationen auf die Mehrzahl von Teil rechenwerken zu verteilen, und um die Ausführung der Operation durch die Mehrzahl von Teilrechenwerken zu steuern,
wobei die Mehrzahl von Teilrechenwerken (106, 108, 110, 112) und die Steuereinheit (105) auf einem einzigen Chip (100) in tegriert sind, und
wobei der Chip (100) einen gemeinsamen Versorgungsstromzugang (122) zum Versorgen der Mehrzahl von Teilrechenwerken und der Steuereinheit mit Strom aufweist.

2. Kryptographieprozessor nach Patentanspruch 1, bei dem die Operationen für kryptographische Anwendungen eine modulare Exponentation und/oder eine modulare Multiplikation umfassen.

3. Kryptographieprozessor nach Anspruch 1 oder 2, bei dem je des Teilrechenwerk angeordnet ist, um binäre Zahlen mit zu mindest 512 Stellen und bevorzugterweise zumindest 1024 oder 2048 Stellen zu verarbeiten.

4. Kryptographieprozessor nach einem der vorhergehenden An sprüche, der ferner einen nur der zentralen Verarbeitungsein richtung (102) zugeordneten Speicher (118) aufweist.

5. Kryptographieprozessor nach einem der vorhergehenden An sprüche, der ferner folgendes Merkmal aufweist:
eine Takterzeugungseinrichtung (120) zum Liefern eines Taktes zu der Verarbeitungseinrichtung (102), der Mehrzahl von Teil rechenwerken und der Steuereinheit (105), wobei die Takter zeugungseinrichtung ebenfalls auf dem einzigen Chip inte griert ist.

6. Prozessor nach einem der vorhergehenden Ansprüche, bei dem jedes Teilrechenwerk ferner eine Mehrzahl von Registern (106b, 106c, 106d, 108b, 108c, 108d) aufweist, die der arith metischen Einheit (106a, 108a) des jeweiligen Teilrechenwerks exklusiv zugewiesen sind.

7. Prozessor nach Anspruch 6, bei dem sich die Länge (L₁, L₂) der Mehrzahl von Registern, die einem Teilrechenwerk zugewiesen sind, und der Länge der Mehrzahl von Registern, die einem anderen Teilrechenwerk zugeordnet sind, unterscheiden, derart, dass die Teilrechenwer ke arithmetische Berechnung mit jeweils unterschiedlichen langen Zahlen durchführen können.

8. Kryptographieprozessor nach Anspruch 6 oder Anspruch 7, bei dem die Anzahl der Register, die einem Teilrechenwerk zu geordnet ist, ausreichend ist, um Operanden für zumindest zwei Teiloperationen zu halten, so dass für zumindest zwei Teiloperationen keine Übertragung von Operanden zwischen dem Coprozessor (104) und der zentralen Verarbeitungseinrichtung (102) erforderlich ist.

9. Kryptographieprozessor nach Anspruch 8, bei dem die Steu ereinheit (105) ferner folgendes Merkmal aufweist:
eine Einrichtung (200) zum zeitlichen Steuern des Betriebs der Teilrechenwerke, derart, dass die Reihenfolge der zumin dest zwei Teiloperationen, deren Operationen in den Registern eines Teilrechenwerkes gespeichert werden, einstellbar ist.

10. Kryptographieprozessor nach einem der Ansprüche 6 bis 9, der ferner folgendes Merkmal aufweist:
eine Einrichtung zum Abschalten von einem Teilrechenwerk, falls von der Steuereinrichtung bestimmt wird, dass für das eine Teilrechenwerk keine Teiloperationen vorhanden sind, um den Stromverbrauch des Prozessors zu verringern.

11. Kryptographieprozessor nach einem der vorhergehenden An sprüche, bei dem die Steuereinrichtung (105) angeordnet ist, um zumindest zwei Teilrechenwerke zu einem Cluster zu verbin den, derart, dass eine Teiloperation dem Cluster zugewiesen wird, so dass diese Teiloperation durch die Teilrechenwerke des Clusters zusammen ausführbar ist.

12. Kryptographieprozessor nach einem der Ansprüche 6 bis 11, bei dem jedes Teilrechenwerk eine Wortlänge hat, die durch die Zahlenbreite der arithmetischen Einheit vorgegeben ist, und bei dem die Steuereinheit (105) angeordnet ist, um zumin dest zwei Teilrechenwerke so zusammenzuschalten, dass die zu sammengeschalteten Teilrechenwerke eine Berechnung mit Zahlen durchführen können, deren Wortlänge gleich der Summe der Zah lenbreiten der zusammengeschalteten Teilrechenwerke ist.

13. Kryptographieprozessor nach einem der vorhergehenden An sprüche, bei dem die arithmetische Einheit zumindest eines Teilrechenwerks ein Seriell/Parallel-Rechenwerk aufweist, das so ausgestaltet ist, dass in einem Zyklus eine Anzahl von Rechnungen parallel ausführbar ist, wobei die Anzahl gleich den Stellen einer in der Rechnung verwendeten Zahl ist, und in einem anderen späteren Zyklus auf serielle Art und Weise unter Verwendung des Ergebnisses des einen Zyklus dieselbe Rechnung wie im ersten Zyklus durchgeführt wird.

14. Kryptographieprozessor nach Patentanspruch 13, bei dem ein Teilrechenwerk für eine modulare Multiplikation ausführt ist, um in dem einen Zyklus ein Partialprodukt zu einem Er gebnis eines vorherigen Zyklus hinzu zu addieren, und in ei nem weiteren Zyklus das Ergebnis des letzten Zyklus zu einem nächsten Partialprodukt hinzu zu addieren.

15. Kryptographieprozessor nach Patentanspruch 14, bei dem die arithmetische Einheit einen Drei-Operanden-Addierer für eine modulare Multiplikation aufweist, welcher für jede Stel le einer verarbeiteten Zahl folgende Merkmale aufweist:
einen Halbaddierer für eine Addition ohne Übertrag mit drei Eingängen und zwei Ausgängen; und
einen nachgeschalteten Volladdierer mit zwei Eingängen und einem Ausgang.