Special-Purpose Hardware in Cryptanalysis: The Case of 1,024-Bit RSAWILLI GEISELMANN
UniversitätKarlsruhe
RAINER STEINWANDT
Florida Atlantic University
For efficiency, we should implement cryptographic subsystems with short keys, but reliably estimating minimal key lengths is a rather involved and complicated process—especially for systems with long life cycles and limited update capabilities. In symmetric cryptography, experts consider 56-bit DES (Data Encryption Standard) keys to be inadequate for most applications: new
devices can efficiently derive a DES key from known plaintext–ciphertext pairs.
Discussion in asymmetric cryptography circles currently focuses on 1,024-bit RSA key security. Interestingly, in this discussion, a major argument put forward for the insecurity of 1,024-bit RSA isn’t due to paramount theoretical progress but to hypothetical hardware devices for factoring
large numbers. Unlike quantum computers, these special-purpose designs try to work within the bounds of existing technology; in this article, we look at the ideas underlying some of these designs and their potential.
RSA-based cryptography
The idea underlying the original RSA encryption scheme1 (named after its authors, Ronald Rivest, Adi Shamir, and Leonard Adleman) serves as the mathematical basis for several of today's cryptographic systems, including applications in low-cost devices in which processing long keys is costly. A crucial common point underlying RSA-based cryptographic schemes is the assumption that it's hard to factor large numbers that are the product of (typically) two prime factors. A list of
challenge numbers documents the capabilities of known factoring algorithms, and the current world record is 193 decimal digits, (factored in 2005; www.rsasecurity.com/rsalabs/node.asp?id=2093). Common minimum requirements suggest the use of numbers with at least 1,024 bits, which
corresponds to 309 decimal digits. All recent factorization records have relied on an algorithm known
as the number field sieve (NFS).2 So far, no one has made paramount progress in the design of new factoring algorithms, so the NFS seems to be the algorithm of choice when aiming at a 1,024-bit number. Due to RSA's eminent relevance, researchers have devoted significant effort to speeding up the NFS via special-purpose hardware.
