Kryptogeräte im Hochsicherheitsbereich (II) Einsatz von elliptischen Kurven auf FPGAs

Ordnungsmerkmale

erschienen in: <kes> 2004^#3, Seite 52

Zusammenfassung: Eine vom BSI erstellte Implementierung von auf elliptischen Kurven basierenden Kryptomechanismen zeigt, dass Field-Programmable Gate Arrays (FPGAs) aus funktionaler Sicht für den Einsatz im Hochsicherheitsbereich sehr attraktiv sind. Dieser Beitrag stellt elliptische Kurven im Überblick und ausgewählte Implementierungsergebnisse dar.

Autor: Von Uwe Dornseifer und Dr. Manfred Lochter, BSI

Das Bundesamt für Sicherheit in der Informationstechnik (BSI) stellt im Rahmen seiner Aufgaben informationstechnische Sicherheitssysteme zur verschlüsselten Übertragung von Verschlusssachen sowie zur Sicherstellung der Authentizität und Integrität von Informationen bereit. Dabei wird sowohl zur Vereinbarung von Schlüsseln für symmetrische Verschlüsselungsverfahren wie auch zur Sicherstellung der Integrität und Authentizität von Daten häufig auf Public-Key-Verfahren zurückgegriffen.

Als einer der ersten Anwender entschied sich das BSI schon zu Beginn der 90er Jahre bei der Auswahl von Public-Key-Verfahren dafür, auf elliptischen Kurven (Elliptic Curves, EC) basierende Mechanismen dem RSA-Verfahren vorzuziehen. In diesem Artikel werden unter anderem die Gründe für diese Entscheidung diskutiert.

Mittlerweile gibt es eine Reihe von Firmen und Institutionen, die sich mit der Implementierung von elliptischen Kurven für kryptographische Zwecke und der Sicherheitsanalyse von elliptischen Kurven befassen. In Deutschland hat sich der ECC-Brainpool [1] gegründet, wobei die Abkürzung ECC für Elliptic Curve Cryptography steht. Der ECC-Brainpool ist eine Arbeitsgruppe, in der Firmen und Institutionen wie beispielsweise das BSI mitarbeiten, welche sich im Bereich der Kryptographie auf Basis elliptischer Kurven engagieren. Die Mitglieder des ECC-Brainpools beobachten und fördern Standardisierungsbemühungen im Bereich der ECC, wobei die Vorgehensweise miteinander abgestimmt wird. Ziel ist es unter anderem, künftige Standards so zu gestalten, dass sie die entsprechenden Sicherheitsvorgaben erfüllen und den Stand der Technik wiedergeben.

Projekte des BSI, in denen elliptische Kurven verwendet werden, sind beispielsweise das ISDN-Verschlüsselungsgerät Elcrodat 6.2 [2], die Sichere Inter-Netzwerk Architektur SINA [3] und der Krypto-ASIC PLUTO [4].

Während bisher Kryptogeräte für den Hochsicherheitsbereich typischerweise Krypto-ASICs verwenden, gewinnt bei Neuentwicklungen unter anderem aus Kosten- und Flexibilitätsgründen der Einsatz von rekonfigurierbarer Hardware an Bedeutung. Eine der Technologien, deren Verwendung infrage kommt, sind Field Programmable Gate Arrays (FPGAs) in verschiedensten Ausprägungen. In Ausgabe 2004^#1 der <kes> [5] wurde bereits über den Einsatz von FPGAs in Sicherheitsmodulen im Hochsicherheitsbereich berichtet. Das BSI hat in Studien [20] und eigenen Analysen die Implementierung von elliptischen Kurven auf FPGAs untersucht.

Dieser Beitrag gibt einen groben Überblick über kryptographisch geeignete elliptische Kurven, auf ihnen aufbauende Sicherheitsmechanismen, eine ausgewählte Implementierung und erzielte Ergebnisse.

Auch wenn sich elliptische Kurven für kryptographische Anwendungen bisher bewährt haben, sei angemerkt, dass ihre Sicherheit, ebenso wie die Sicherheit aller anderen praktikablen Public-Key-Verfahren, auf der unbewiesenen Annahme der Schwierigkeit eines bestimmten mathematischen Problems, hier des Diskreten-Logarithmus-Problems auf elliptischen Kurven, beruht.

Elliptische Kurven

Elliptische Kurven lassen sich über den verschiedensten Grundkörpern betrachten (das sind Bereiche, in denen, grob formuliert, dieselben Rechenregeln wie für die reellen Zahlen gelten). Kryptographische Relevanz haben allerdings nur über endlichen Körpern, die oft mit Galois Field (GF) oder Finite Field (FF) bezeichnet werden, definierte Kurven.

Aber auch von über endlichen Körpern definierten elliptischen Kurven existieren unterschiedliche Ausprägungen. Aus Performancegründen werden oft Kurven über Erweiterungen des endlichen Körpers GF(2) bevorzugt. Vom BSI werden allerdings nur Kurven verwendet, die über einem endlichen Körper GF(p) für eine große Primzahl p definiert sind. Eine elliptische Kurve E über GF(p) besitzt für p>3 eine affine Darstellung als Lösungsmenge einer Weierstraßgleichung

E: Y² = X³ + a·X + b

zusammen mit einem "unendlich fernen Punkt" O. Dabei stammen a und b aus GF(p) und genügen der Nebenbedingung, dass 4·a³ + 27·b² von Null verschieden ist. Wesentlich ist, dass man die Punkte einer elliptischen Kurve addieren kann und bei dieser Addition eine abelsche Gruppe mit Nullpunkt O entsteht. Das heißt informell: Für jeden Punkt P der Kurve gilt P+O =P und existiert ein Punkt Q mit P+Q=O. Weiterhin ist stets P+R=R+P und (P+Q)+R=P+(Q+R).

Die Addition wird geometrisch begründet. Um eine grobe Erklärung für diese geometrische Addition zu geben, gehen wir vom Bild der Punkte einer elliptischen Kurve über den reellen Zahlen aus (vgl. Abb. 1).

Abbildung 1: Elliptische Kurve Y²= X³-15·X+7 über den reellen Zahlen

Anschaulich bedeutet die Addition von P und Q in Abbildung 1: Eine Gerade durch P und Q schneidet die Kurve in genau einem dritten Punkt. P+Q wird definiert als Schnittpunkt der Parallelen zur y-Achse durch diesen dritten Punkt mit der Kurve. Falls P verdoppelt werden soll, betrachtet man die Tangente an P, die dann genau einen von P verschiedenen Schnittpunkt S mit der Kurve hat. Als 2·P wird der zweite Schnittpunkt mit E der Parallelen zur y-Achse durch S definiert. Diese anschauliche Operation lässt sich leicht in Formeln fassen und auf GF(p) übertragen (siehe [6]), wodurch eine Gruppenstruktur entsteht.

Für P=(x_P, y_P) und Q=(x_Q, y_Q) aus der Menge E(GF(p)) der über GF(p) definierten Punkte von E gilt:

• P+Q=P, falls Q=O
• P+Q=O, falls x_P=x_Q und y_P= −y_Q – das heißt −(x_P, y_P) =(x_P, −y_P)
• ansonsten setze P+Q=R=(x_R, y_R) mit
  • x_R = λ² − x_P − x_Q
  • y_R = λ · ( x_P − x_R) −- y_P
    • wobei λ = (y_Q−y_P) / (x_Q−x_P), falls x_P≠x_Q
    • wobei λ = (3· (x_P)2+a)/(2·y_P), falls P=Q (Punktverdoppelung).

Natürlich kann die Punktaddition über endlichen Körpern nicht mehr so "schön" visualisiert werden. Abbildung 2 zeigt die Menge der über GF(11) definierten Punkte der Kurve Y2=X3+5·X+7. Der "unendlich ferne Punkt" O ist in dieser Darstellung nicht sichtbar.

Abbildung 2: Y²=X³+5·X+7 über GF(11)

Offenbar liegt der Punkt P₀=(2,5) auf der Kurve. Man kann mithilfe der obigen Formeln leicht nachrechnen, dass 2·P₀=(10,10) und 3·P₀=(3,4). Insbesondere ist 2·P₀ nicht gleich (4,10), wie man es nach der Vektorrechnung vermuten könnte. Vielfache k·P eines Punktes sind definiert als (P+P+.... +P) mit k Summanden P. Abbildung 3 zeigt die Vielfachen des Punktes P₀ auf der Beispielkurve. Es ist dabei 8·P₀= O. Man beachte, dass nicht jeder der 16 Kurvenpunkte als Vielfaches von (2,5) auftritt.

Abbildung 3: Vielfache von P₀=(2,5)

Kryptographisch geeignete elliptische Kurven

Nach dem Satz von Hasse-Weil [6] weicht die Anzahl #E(GF(p)) der Elemente der Gruppe E(GF(p)) kaum von p ab. Genauer:

|#E(GF(p)) − (p+1)| ≤ 2 (p)^1/2

Man wählt E aus Sicherheitsgründen so, dass #E(GF(p)) einen Primteiler q in ähnlicher Größenordnung besitzt. Public-Key-Verfahren, die elliptische Kurven verwenden, arbeiten in der Regel in einer Untergruppe U von E(GF(p)) mit q Elementen. Solche Gruppen U sind zyklisch, dass heißt, zu je zwei Punkten P₀≠O und Q in U gibt es genau ein s zwischen 1 und q, sodass s·P₀=Q gilt. Die Sicherheit der Public-Key-Verfahren, die elliptische Kurven verwenden, beruht auf der vermuteten Schwierigkeit dieses s bei Kenntnis von P₀ und Q zu bestimmen. Man spricht vom Diskreten-Logarithmus-Problem (DLP) auf elliptischen Kurven.

Mit Ausnahme von einigen Spezialfällen, beispielsweise supersingulären [6] elliptischen Kurven, wird das DLP auf elliptischen Kurven heute als schwierig erachtet. Allerdings können bei geeignet großer Parameterwahl auch schwächere elliptische Kurven für kryptographische Zwecke verwendet werden. Beispielhaft genannt seien identitätsbasierte Signaturen und 3-Parteien-Schlüssel-Einigungsverfahren; einen Überblick gibt Joux [7].

Das BSI erstellt jedes Jahr unter Beteiligung von Experten aus Wirtschaft und Wissenschaft ein Dokument über die Eignung von Kryptoalgorithmen, mit denen elektronische Signaturen erzeugt werden können, die den Vorgaben des deutschen Signaturgesetzes genügen. Die Regulierungsbehörde für Post und Telekommunikation (RegTP, [8]) veröffentlicht im Bundesanzeiger auf Grundlage der BSI-Angaben jährlich die Übersicht über die geeigneten Algorithmen. Die offiziellen Übersichten geordnet nach Jahreszahlen finden sich ebenfalls unter [8]. Der Entwurf der Angaben für das Jahr 2005 ist voraussichtlich ab Herbst 2004 auf im Webangebot des BSI [9] zu finden.

In den Algorithmenpapieren wird eine Reihe von Kriterien angegeben, die kryptographisch gute Kurven erfüllen müssen. Diese Kriterien sind bei naturgemäß höher zu wählenden Sicherheitsparametern auch im Hochsicherheitsbereich zu beachten. Der Qualitätsnachweis für elliptische Kurven führt unter anderem auf zwei Faktorisierungsprobleme, nämlich bei der Berechnung des Endomorphismenringes geeigneter Kurven und beim Nachweis der Resistenz gegen Angriffe mittels der so genannten Weil- oder Tate-Paarung. Die vermutete Schwierigkeit der Faktorisierung eines Produkts zweier Primzahlen wiederum bildet die Grundlage für das noch derzeit populärste Public-Key-Verfahren, das RSA-System.

Zurzeit ist kein Angriff auf gut gewählte elliptische Kurven bekannt, der besser ist als das Pollard-Rho-Verfahren [10], welches ungefähr einen Aufwand von p^1/2 (Quadratwurzel aus p) Rechenoperationen benötigt: Für Zahlen p der Länge l-Bit ist das DLP auf einer geeignet gewählten elliptischen Kurve ein l/2-Bit Problem. Dieses Problem ist wesentlich schwieriger als die Faktorisierung einer l-Bit Zahl n, wofür der Aufwand des besten zurzeit bekannten Algorithmus, des Zahlkörpersiebes, bei

e^{(1,9229+o(1))) ln(n)1/3 ln(ln(n))2/3}

liegt (vgl. bspw. [11]).

In der wissenschaftlichen Öffentlichkeit herrscht zurzeit im Prinzip Konsens über die in Tabelle 1 dargestellte Aufwandsgegenüberstellung der gegenwärtig besten Angriffsmethoden. Tabelle 1 ist folgendermaßen zu lesen: Das Lösen eines symmetrischen Verschlüsselungsalgorithmus mit 112 Bit Schlüssellänge durch Probieren aller Schlüssel (Brute Force) erfordert gleich viele Schritte wie das Lösen des DLP auf einer 224-Bit-Kurve oder das Brechen von 2048-Bit-RSA. Dabei sind die Zahlenwerte eher als grobe Richtschnur zu sehen und stark vom wissenschaftlichen Fortschritt abhängig. Die angegebenen Zahlenwerte sind dem Entwurf der NIST Special Publication 800-57 "Recommendations for Key-Management" [12] angelehnt, Ähnliches findet sich mit teilweise aber höheren Parameterlängen in [11]. Die angegebenen Werte sind auch Basis für die im Hochsicherheitsbereich zugrunde gelegten Schlüssellängen bei der Implementierung von elliptischen Kurven auf FPGAs.

Wegen des subexponentiellen Charakters des Zahlkörpersiebes steigt die Bitlänge von RSA-Zahlen bei mit elliptischen Kurven vergleichbarer Sicherheit stark an. In jüngster Zeit wurden ausgehend von einem Vorschlag von D. Bernstein [13] mehrere hardwarebasierte Lösungsansätze zur Faktorisierung von RSA-Zahlen vorgestellt, denen zufolge es bereits heute möglich ist mit genügend Kapitaleinsatz eine Maschine zu bauen, die eine 1024-Bit-RSA-Zahl innerhalb eines Jahres in ihre Primfaktoren zerlegt. Ein Überblick über diese Ansätze wird in [14] gegeben.

Der derzeitige Weltrekord für die Faktorisierung von RSA-Zahlen wurde Ende 2003 durch eine von Prof. Jens Franke (Universität Bonn) geleitete Forschergruppe mit der Faktorisierung der 576-Bit-Zahl RSA-576 aufgestellt [15]. Ein Teil der benötigten Rechenkapazität wurde vom BSI zur Verfügung gestellt. Motivation hierzu war, dass das BSI sowohl zur Evaluierung von kryptographisch geeigneten Kurven als auch bei der Beurteilung von Signaturverfahren Kenntnis der zurzeit besten Faktorisierungsverfahren benötigt.

Steigende Bitlängen machen die Implementierung des RSA-Verfahrens insbesondere auf Chipkarten schwierig, ebenso steigt der Datenübertragungsaufwand beim RSA-Verfahren sehr stark an. Das BSI hat sich aus diesen Gründen schon Anfang der 90er Jahre für elliptische Kurven entschieden. Hinzu kam der Wunsch nach der Verwendung eines vom RSA-Problem verschiedenen Problemes, für das es keinen bekannten subexponentiellen Algorithmus gibt.

Sicherheitsdienste

Jeder Nutzer A eines EC-Systems verfügt über einen geheimen Schlüssel s_A und einen zugehörigen öffentlichen Schlüssel P_A= s_A ·P₀. Während es sich bei dem geheimen Schlüssel s_A um eine Zahl zwischen 2 und q−1 handelt, ist der öffentliche Schlüssel ein Kurvenpunkt. Öffentlich bekannt sind weiterhin die Kurvengleichung, der Grundkörper und die Ordnung q der von P₀ erzeugten Untergruppe.

Elliptische Kurven werden für eine Reihe von Sicherheitsdiensten eingesetzt. Im Folgenden sind zwei Basisroutinen beschrieben, die in verschiedenen Protokollen zur Schlüsseleinigung und digitalen Signatur Verwendung finden. Die Betrachtung dieser Basisroutinen wird bei den nachfolgenden Überlegungen zur Laufzeitbeschleunigung eine große Rolle spielen.

Der einfachste Mechanismus zur Schlüssel-Einigung ist die so genannte Diffie-Hellman-Schlüssel-Einigung. Wollen A und B ein gemeinsames Geheimnis, beispielsweise einen Schlüssel, für ein symmetrisches Verschlüsselungsverfahren aushandeln, so gehen sie folgendermaßen vor:

• A erzeugt eine Zufallszahl r und sendet r·P₀ an B,
• B erzeugt eine Zufallszahl s und sendet s·P₀ an A,
• B berechnet s·(r·P₀) =r·s·P₀,
• A berechnet r·(s·P₀) =r·s·P₀.

Beide verfügen dann mit dem Punkt r·s·P₀ über ein gemeinsames Geheimnis. Üblicherweise werden aus der x-Koordinate dieses Punktes Schlüssel für ein symmetrisches Verschlüsselungsverfahren abgeleitet. Die Schwäche des reinen Diffie-Hellman-Verfahrens liegt in seiner Verwundbarkeit durch Man-in-the-Middle-Angriffe. Daher wird zur Schlüsseleinigung in der Regel ein Protokoll verwendet, mit dem die Authentizität der empfangenen Daten garantiert wird. Wichtigster Baustein kann dabei ein Verfahren zur digitalen Signatur sein. Vom BSI wird in der Regel ECGDSA [16], eine Version des im Digital Signature Standard DSS [17] definierten Digital Signature Algorithm (DSA) für elliptische Kurven, verwendet:

Zur Signaturerzeugung geht A wie folgt vor:

• A erzeugt eine Zufallszahl k, berechnet R=k·P₀ und setzt r= x_R mod q,
• A berechnet s=(k·r−H(m)) ·s_A⁻¹ mod q, wobei H eine kryptographische Hashfunktion und m die zu signierende Nachricht ist,
• Falls r und s von 0 verschieden sind, ist (r,s) eine digitale Signatur für m, ansonsten wiederholt man die ersten beiden Schritte so lange, bis die Bedingung erfüllt ist. Wäre r=0, so könnte man den geheimen Schlüssel von A ablesen, falls s=0 ist die Signatur unabhängig von As geheimem Schlüssel.

Zur Signaturprüfung werden von B nacheinander folgende Schritte ausgeführt:

• berechne s·P_A=(k·r−H(m)) ·P₀,
• berechne t= r⁻¹ mod q,
• berechne t· (s·P_A+H(m) ·P₀) =S.
• Die Signatur ist gültig, falls x_S mod q=r

Von besonderer Bedeutung für das beschriebene Signaturverfahren ist die Güte der verwendeten Zufallszahlen. So kann das Verfahren beispielsweise angegriffen werden, wenn die Zufallszahlen durch Reduktion von – etwa mit einem physikalischen Rauschgenerator erzeugten – Zufallszahlen mod q entstehen. Eine solche Attacke wurde für den DSA von Daniel Bleichenbacher (unveröffentlicht) beschrieben und führte zur Revision des DSS. Die Bleichenbacher-Attacke lässt sich problemlos auf die EC-Varianten des DSA übertragen. Andere Methoden arbeiten mit der Kenntnis von einigen wenigen Bits der verwendeten Zufallszahlen (vgl. bspw. [18]). Jedes Kryptosystem, das elliptische Kurven verwendet, muss folglich auch geeignete Zufallszahlen zur Verfügung stellen.

Signaturverfahren wie der ECGDSA können im Rahmen einer Public-Key-Infrastruktur (PKI) generell zum Nachweis der Authentizität von Nachrichten eingesetzt werden. Mit dem nach seinen Erfindern Menezes, Qu und Vanstone benannten MQV-Verfahren findet zurzeit ein Schlüssel-Einigungsverfahren mit impliziter Authentisierung zunehmendes Interesse, wie unter anderem der Erwerb von Lizenzrechten durch die amerikanische National Security Agency belegt [19]. Auch für zukünftige PKIs im militärischen Bereich wird die Ablösung von RSA durch ähnliche Verfahren diskutiert.

Arithmetik

Kurvenoperationen erfordern in der zuvor beschriebenen affinen Darstellung elliptischer Kurven den in Tabelle 2 dargestellten Aufwand. Zur Beschleunigung der Kurvenoperation gibt es mehrere Möglichkeiten:

• Man wählt eine Darstellung der Kurve, bei der weniger und/oder billigere arithmetische Operationen in GF(p) benötigt werden.
• Man findet eine besonders schnelle Implementierung der GF(p)-Arithmetik.
• Man beschleunigt einzelne in den verwendeten Protokollen häufig genutzte Basisroutinen mit Vorberechnungen und geschickte Abarbeitung von Additionen und Multiplikationen.

Zur optimalen Realisierung und Kombination der genannten Möglichkeiten gibt es keine universell richtige Lösung. Man muss sich stets an der Zielplattform und der vorgesehenen Anwendung der elliptischen Kurven orientieren. Im Rahmen dieses Beitrages ist naturgemäß keine umfassende Darstellung möglich, was eine Beschränkung auf grundlegende Anmerkungen und einige wesentliche Schlagwörter notwendig macht; eine gute Einführung findet sich in [24].

Kurvendarstellung

Die neben der bisher verwendeten affinen Darstellung elliptischer Kurven bekannteste Darstellungsform ist die so genannte projektive Form elliptischer Kurven. Dabei betrachtet man die homogenisierte Gleichung:

Y² Z=X³+a·XZ²+b·Z³ mit a, b aus GF(p).

Hier sind nur Lösungen (x,y,z) dieser Gleichung von Interesse, die von (0,0,0) verschieden sind. Für jede solche Lösung ist auch (tx,ty,tz) für von Null verschiedenes t aus GF(p) eine Lösung. Die Äquivalenzklassen unter der so definierten Äquivalenzrelation werden mit (x:y:z) bezeichnet. Aus jeder Lösung (x:y:z) mit z≠0 erhält man unabhängig vom gewählten Repräsentanten der Lösung genau eine Lösung der affinen Gleichung, nämlich (x/z,y/z). Umgekehrt ergibt jede affine Lösung (x,y) die projektive Lösung (x:y:1). Hinzu kommt die Lösung (0:1:0), die dem unendlich fernen Punkt entspricht. Die Additionsformeln für die projektive Darstellung kommen ohne die in der Regel besonders zeitaufwändigen Inversionen in GF(p) aus. Besonders schnell wird die Arithmetik im projektiven Fall, wenn ein Punkt P in affiner Form vorliegt und zu einem Punkt Q in projektiver Form addiert wird.

Körperarithmetik

Zur Durchführung von Multiplikationen hat sich die Montgomery-Multiplikation [10] bewährt. Inversenbildung wird mithilfe des kleinen Fermat'schen Satzes durchgeführt: In GF(p) gilt für r≠0 die Identität r^p−2=r⁻¹, daher kann eine Inversion durch mehrere Multiplikationen ersetzt werden.

Kurvenmultiplikationen und Additionen

Zur Berechnung von Vielfachen s·P und Summen s·P+t·Q gibt es eine Reihe von effizienten Verfahren, wie Sliding-Window-Verfahren, reduzierte Normalformen, Lim-Lee-Verfahren und so weiter. Bei Diensten, die Vielfache eines festen Punktes P berechnen, wie das Diffie-Hellman-Verfahren oder die ECGDSA-Signaturerzeugung, kann eine deutliche Beschleunigung durch Vorberechnung von Vielfachen s·P mit s<L mit einer speicherabhängigen Schranke L erreicht werden. Statt mit der Binärdarstellung eines Multiplikators arbeitet man dann mit der Darstellung zur Basis L. Nach Vorberechnung von P+Q erfolgt die Berechnung von s·P+t·Q fast genauso schnell wie die Berechnung von s·P oder t·Q. Noch bessere Ergebnisse liefern Kombinationen der genannten Beschleunigungsmethoden.

Elliptic Curve Processor

Der vom BSI entwickelte GF(p)-basierte Elliptic Curve Processor (ECP) wurde für den Einsatz in rekonfigurierbarer Hardware entwickelt. Aus Sicherheitssicht stand die Verfügbarkeit und Erprobung einer vertrauenswürdigen technischen Realisierung von Elliptic-Curve-Basismechanismen im Vordergrund. Aus funktionaler Sicht sind universeller Einsatz und hohe Effizienz wünschenswert. Damit lassen sich als primäre technische Designziele eine technologieunabhängige Architektur, eine technologieunabhängige Hardwarebeschreibung, hohe Durchsatzraten und kleinstmögliche Bausteinkosten nennen. Allerdings stehen diese Designziele teilweise im Widerspruch zueinander und lassen sich nicht gleichzeitig realisieren oder optimieren.

Am einfachsten ist eine technologieunabhängige Beschreibung zu erreichen. Hierzu wurde die Hardwarebeschreibungssprache VHDL verwendet. Aber selbst dieses Ziel wurde an ausgewählten Stellen durch die Instanziierung spezieller Technologiezellen (Multiplizierer, Speicher, Takterzeugung) aufgebrochen. Die Architektur ist zwar abstrakt technologieunabhängig, das heißt sie kann in ähnlicher Weise auf verschiedenen Zielplattformen realisiert werden, im Detail wurde aber eine beispielhafte Implementierung für eine ausgewählte Technologie durchgeführt. Größe und Durchsatz des zwischen 160 Bit und 512 Bit skalierbaren Designs wurden für ausgewählte Bitbreiten ermittelt. Die Implementierungsergebnisse wurden unter Verwendung einer PCI-FPGA-Karte verifiziert.

Im Vorfeld zu der vom BSI durchgeführten Entwicklung wurde eine Studie an die TU Darmstadt vergeben [20]. Im Rahmen dieser Studie wurde von der TU Darmstadt unter anderm auch eine PCI-FPGA-Karte ausgewählt, die nunmehr dem BSI zur Verfügung steht. Die Studienergebnisse sowie die Auswahl und Inbetriebnahme der Hardwareplattform haben einen wichtigen Beitrag zur ECP-Entwicklung des BSI geleistet, da das BSI somit direkt mit der Optimierungsphase beginnen konnte.

Für die Implementierung wurde vorausgesetzt, dass der EC-FPGA Teil eines Sicherheitsmoduls ist (vgl. [5]). Ausgehend von der Annahme, dass Sidechannel-Attacken auf die geschützte FPGA-Implementierung somit nicht möglich sind, wurde bei der Referenzimplementierung auf algorithmische Schutzmechanismen verzichtet. Solche Mechanismen – wie Randomisierung, Doppelberechnung oder Laufzeitsteuerung – führen in der Regel zu verminderter Performanz.

ECP-Funktionalität

Der ECP umfasst die GF(p)-Arithmetik sowie die EC-Arithmetik. Die EC-Arithmetik wird durch den wiederholten Aufruf von Funktionen der GF(p)-Arithmetik realisiert.

GF(p)-Arithmetik / FF-Operationen

• modulare Addition und Subtraktion,
• modulare Multiplikation in der Ausprägung Montgomery-Multiplikation [10], 16 Bit,
• modulare Exponentiation auf Basis der modularen Multiplikation,
• modulare Inversion auf Basis der modularen Multiplikation und des kleinen Fermat'schen Satzes.

EC-Arithmetik / EC-Operationen

• Punktverdopplung und Punktaddition unter Verwendung projektiver Koordinaten,
• Punktmultiplikation durch wiederholtes Anwenden der Punktverdopplung und Punktaddition in Kombination mit einem Sliding-Window-Verfahren der Fensterbreite 4 Bit,
• Transformation zwischen projektivem und affinem Koordinatensystem.

Zur Ausführung von FF-Operationen erforderliche Kommandoaufrufe werden hier als FF-Kommandos bezeichnet, solche zur Ausführung von EC-Operationen als EC-Kommandos.

ECP-Architektur

Das auf dem FPGA realisierte Gesamtdesign besteht aus einem Anteil des PCI-Interfaces sowie dem ECP (vgl. Abb. 4). Der ECP besteht aus mehreren Modulen, die zum Teil wiederum modular aufgebaut sind.

• ECP-Controller: Zustandsautomat, der FF-Kommandos an den FF-Controller weiterleitet und EC-Kommandos durch den wiederholten Aufruf von FF-Kommandos realisiert.
• FF-Controller: Zustandsautomat, der die Hardwarekomponenten in FF-Slices derart koordiniert steuert, dass die Eingangsoperanden entsprechend den FF-Kommandos verknüpft und im Datenspeicher abgelegt werden.
• FF-Slices: Skalierbares, aus 32 Bit breiten Modulen aufgebautes Langzahl-Rechenwerk (160–512 Bit), das neben einem Dual-Port-Datenspeicher aus Addierern, Multiplizierern und Schieberegistern besteht. Über den Dual-Port-Datenspeicher werden insbesondere auch die interne und externe Taktdomäne für die Daten entkoppelt.
• Cmd-FIFO, FinishedCmd-FIFO: Zwischenspeicher für Kommandos und abgearbeitete Kommandos, die der Entkopplung der internen und externen Schnittstelle und damit auch der zugeordneten Taktdomänen dienen
• Ctrl-Register, Status-Register: Register zur Steuerung oder Zustandsdarstellung des gesamten ECP

Abbildung 4: Gesamtarchitektur des ECP-Designs

Daten werden in einem Dual-Port-RAM (Schreib-Lese-Speicher mit zwei unabhängigen Schnittstellen) gespeichert, der bis zu 512 Langzahlen aufnehmen kann. Jede Langzahl hat die Länge der vorkonfigurierten Bitlänge des Designs, liegt also zwischen 160 und 512 Bit. Daten werden grundsätzlich in 32-Bit-Worten über das PCI-Interface in den Datenspeicher geladen. Nicht alle Speicherbereiche des ECP sind von außen zugreifbar. Der ECP bietet von außen adressierbaren Speicherplatz für zwei Parametersätze, jeweils bestehend aus dem Modul p sowie den Kurvenparametern a und b, für 16 Langzahlen sowie für 8 Punkte in affiner Darstellung.

Aus Modul und Kurvenparameter werden vor deren Verwendung intern automatisch die für die Montgomery-Multiplikation erforderlichen Parameter generiert, die erforderlichen Transformationen durchgeführt und die Ergebnisse intern abgespeichert. Punkte in affiner Darstellung werden vor deren Verwendung intern automatisch in die projektive Darstellung umgewandelt und in einem "Schattenspeicher" abgelegt. Die Rücktransformation ist relativ aufwändig und wird durch ein Flag im Kommando gesteuert. Bei Ausführung des Kommandos "EC-Multiplikation" werden intern automatisch die Vorberechnungen für das Sliding-Window-Verfahren durchgeführt und die vorberechneten Punkte in Form einer Tabelle im Datenspeicher gespeichert. "Schattenspeicher" und Tabelle existieren intern für jeden von außen adressierbaren Punkt.

Der ECP arbeitet mit zwei Takten, die völlig asynchron zueinander sein können. Der externe Takt beeinflusst beziehungsweise bestimmt die Datenübertragungsgeschwindigkeit über das PCI-Interface. Alle Designanteile der EC-Arithmetik laufen mit dem internen Takt oder dem doppelten internen Takt.

Ansteuerung des ECP

Inbetriebnahme und Betrieb des ECP auf einem rekonfigurierbaren Hardwarebaustein stellen sich wie folgt dar:

• Laden der Konfiguration in den FPGA (nur bei flüchtigen FPGAs),
• Speicherelemente in definierten Zustand bringen (Reset),
• Schreiben des Kontrollregisters,
• Modul p in den Datenspeicher schreiben,
• Kurvenparameter a, b in den Datenspeicher schreiben,
• Operanden in den Datenspeicher schreiben,
• Kommando an ECP geben und auf Beendigung warten (Interrupt oder Polling),
• Ergebnis aus dem Datenspeicher auslesen.

Typischerweise erfolgen die ersten fünf Schritte nur zur Initialisierung, zum Beispiel nach dem Einschalten der Komponente. Die Schritte sechs bis acht wiederholen sich hingegen zyklisch.

Implementierung und Verifikation

Das Design wurde in der Hardwarebeschreibungsprache VHDL modelliert. Zwecks Simulation und Synthese des VHDL-Models kam das Produkt "FPGA Advantage" (Modelsim, Precision) der Firma Mentor Graphics [21] zum Einsatz. Zur physikalischen Implementierung wurde das ISE-Entwicklungssystem des FPGA-Herstellers XILINX [22] verwendet. Implementierungsergebnis war eine Konfigurationsdatei, die auf das im Rahmen der Studie ausgewählte PCI-FPGA-Board der Firma Alpha Data [23] geladen werden kann. Das PCI-FPGA-Board verfügt über den Xilinx-FPGA XC2V6000-4-FF1152 (Config-Stepping 0), wird derzeit zu Testzwecken in einem handelsüblichen PC-Host-System betrieben und bildet zusammen mit dem zugehörigen softwareseitigen Entwicklungssystem die Grundlage für die Verifikation. Der Nachweis der korrekten Funktion des ECP basiert auf Referenzdaten, die Ergebnis einer vom BSI entwickelten EC-Software sind. Die Testprozeduren für das Host-System wurden in C++ kodiert.

Die eingesetzten Implementierungswerkzeuge sind parametrisierbar. Die Parameterwahl und die Optimierungsvorgaben (Constraints) haben starke Auswirkungen auf die Implementierungsergebnisse. Durch Vorgabe hoher Geschwindigkeitsanforderungen wurde von den Implementierungswerkzeugen schwerpunktmäßig die Laufzeit des Designs minimiert. Für alle Designs wurde eine mittlere "Optimierungstiefe" verwendet. Auf einem 2-GHz-PC dauert die Durchlaufzeit für eine physikalische Implementierung, in Abhängigkeit von der Bitbreite des Designs, zwischen 10 und 50 Minuten.

Implementierungsergebnisse

Im Implementierungsprozess werden neben der Konfigurationsdatei, die in den FPGA geladen werden kann, automatisch verschiedene Zwischenergebnisse und Reports generiert. Die Ergebnisse der Tabelle 3 wurden den Map- und P&R-Reports entnommen.

Die genannten Implementierungen wurden auf der PCI-FPGA-Karte getestet und funktionierten auch bei einer Taktrate von 48 MHz noch fehlerfrei. Diese Tests wurden allerdings bei unbestimmten bis eher typischen Umweltbedingungen durchgeführt. Im Wirkbetrieb sollten ausschließlich die vom FPGA-Hersteller in den Reports genannten und damit garantierten Werte (siehe Tabelle 3) als Berechnungsgrundlage dienen. Diese Werte berücksichtigen die ungünstigsten Umweltbedingungen (insbesondere Temperatur), unter denen der FPGA eingesetzt werden darf.

Die maximal mögliche Taktfrequenz wird durch den längsten Datenpfad zwischen zwei getakteten Speicherelementen (Flip-Flops) bestimmt. Das ECP-Design ist so ausgelegt, dass die verwendeten Hardware-Multiplizierer den kritischen Pfad darstellen. Der auf dem PCI-FPGA-Board verwendete FPGA verfügt noch über Multiplizierer der ersten Generation und ist mit dem Speed Grade 4 der langsamste Typ der Virtex-II Familie. Inzwischen sind Bausteine verfügbar, deren Multiplizierer optimiert wurden und die damit eine deutlich reduzierte Laufzeit aufweisen. Zum Vergleich wurde auch eine Implementierung des 320-Bit-Designs für einen schnellen Baustein der Virtex-II-Pro Familie durchgeführt. Die Implementierungsergebnisse wurden nicht auf dem FPGA verifiziert, sind aber durch die Reports der Implementierungswerkzeuge vom FPGA-Hersteller garantiert. In Tabelle 4 ist in eckigen Klammern die jeweilige Ausnutzung der auf dem Baustein verfügbaren Hardwareressourcen angegeben.

Eine Erhöhung des Taktes bedeutet zugleich eine umgekehrt proportionale Verringerung der Ausführungszeiten von ECP-Operationen. Bei einer Implementierung, die mit 70 MHz getaktet ist, sind die Laufzeiten der ECP-Operationen gegenüber einer mit 37 MHz getakteten Implementierung auf circa 53 % reduziert.

Laufzeiten

Alle genannten Laufzeiten beziehen sich auf die Ausführung der EC-Punktmultiplikation. Die EC-Punktmultiplikation ist die zeitaufwändigste ECP-Operation, die gleichzeitig alle anderen Operationen des ECP verwendet. Die Länge der verwendeten Parameter und Operanden liegt jeweils in der Größenordnung der Bitbreite des Designs. Die Ansteuerung des ECP erfolgte gemäß bschnitt "Ansteuerung des ECP". Die dort genannten Schritte sechs bis acht wurden in einer Schleife abgearbeitet, das heißt alle Operanden wurden vom Host-System wiederholt an die PCI-Karte übertragen und von dort ausgelesen. Durch die Verwendung des Sliding-Window-Verfahrens hat das Hamming-Gewicht (Anzahl der gesetzten Bits) des Multiplikators sowie die Bitverteilung Auswirkungen auf die Ausführungsgeschwindigkeit. Im Test wurden – praxisnah – zufällig gewählte Multiplikatoren verwendet.

Ausblick

Es ist vorgesehen, den ECP in Kombination mit symmetrischen Kryptoverfahren in konkreten Anwendungen einzusetzen. In einem ersten Schritt soll ein schnelles PCI-Board entwickelt werden, das ein Sicherheitsmodul enthält und für den Einsatz im Projekt SINA geeignet ist. Das Sicherheitsmodul beinhaltet unter anderem einen FPGA und bietet damit aufgrund seiner Rekonfigurierbarkeit auch die Voraussetzungen für die Verwendung mehrerer unterschiedlicher Algorithmenfamilien in flexiblen Einsatzszenarien.

zurück zum Inhalt
© SecuMedia-Verlags-GmbH, 55205 Ingelheim (DE),
<kes> 2004^#3, Seite 52