RSAy - A High Speed RSA Chip

Entwurf, Fertigung und Messung eines Hochgeschwindigkeits-Langzahlen-Multiplizierer-Chips für Kryptographische Anwendungen ist im Rahmen dieses Projektes vorgesehen. Die wesentlichste Anwendung dieses Chips ist der asymmetrische Rivest Shamir Adleman (RSA) Algorithmus, welcher auch als Benchmark für diesen Chip ausgewählt wurde. Allerdings kann der vorliegende Chip auch für andere kryptographische Algorithmen verwendet werden, wie z.B. für den ElGamal Algorithmus.

Die Ziele dieses Projekts waren Entwurf und Implementierung einer Hochgeschwindigkeits-Hardware für Public- Key-Kryptosysteme. Eines der am weitesten verbreiteten Public-Key-Kryptosysteme ist das Kryptosystem von Rivest, Shamir und Adleman (RSA), welches sowohl für asymmetrische Ver- bzw. Entschlüsselung als auch für Generation bzw. Verifikation digitaler Signaturen verwendet werden kann. RSA-Public-Key-Kryptographie basiert auf Modulo-Exponentiation sehr langer Zahlen (typischerweise 1024 Bit). Die Schwerpunkte des Projekts umfassten die Untersuchung verschiedener Algorithmen bzw. Multiplizierer-Architekturen für Modulo- Multiplikation langer Zahlen, sowie den Entwurf des RSA Krypto-Chip für schnelle Ver- bzw. Entschlüsselung nach dem RSA Algorithmus. Im Gegensatz zu anderen RSA-Chips vereint der RSA effiziente Algorithmen mit einer leistungsstarken Multiplizierer-Architektur, welche mit Hilfe einer optimierten Schaltungstechnik sowie einer darauf abgestimmten Design-Methodik realisiert wurde. Implementierte Algorithmen: Der RSA verwendet eine hardware-optimierte Version des Barrett-Algorithmus für Modulo-Reduktion, genannt FastMM-Algorithmus. Dieser FastMM-Algorithmus ist sehr gut für Hardware- Implementierung geeignet, da er die Modulo Reduktion ohne Division durchführt und eine Modulo-Multiplikation mit Hilfe von drei Langzahlen-Multiplikationen sowie einer Addition realisiert. Zusätzlich ermöglicht der RSA- Krypto-Chip eine weitere Beschleunigung der RSA-Private-Key-Operationen durch Anwendung des Chinesischen Restesatzes. Multiplizierer-Architektur: Die Architektur des Multiplizierers im RSA-Krypto-Chip entspricht jener eines partiell-parallelen Multiplizierers (PPM). Der im Rahmen dieses Projektes entwickelte Prototyp enthält einen 1056*16-Bit-PPM, welcher den Multiplikand vollständig parallel erfasst und den Multiplikator sequentiell in 16- Bit-Worten abarbeitet. Aufgrund des hohen Grades an Parallelität kann eine 1024-Bit-Modulo-Multiplikation in 227 Taktperioden berechnet werden. Schaltungstechnik und Entwurfsmethodik: Obwohl die Architektur (theoretisch) mit einem beliebigen Grad von Parallelität realisiert werden kann, muss dennoch beachtet werden, dass sowohl die maximale Fläche als auch die maximale Leistungsaufnahme eines Chips limitiert sind. Deshalb müssen strom- und flächenoptimierende Entwurfsmethoden angewendet werden um die maximale Geschwindigkeit zu erzielen. Der Datenpfad des RSA wurde mit Hilfe eines dynamischen Logikstiles, der True Single Phase Clocked (TSPC) Logik, implementiert um die Generierung bzw. Verteilung des Taktsignales möglichst einfach zu gestalten. Die wesentlichen Teile des Multiplizierer-Kernes wurden in einer Full-Custom-Entwurfsmethodik realisiert.