RSA|PUBLIC-KEY ENCRYPTION

RSA

Public-key encryption was outlined in [DH76], but the best-known technique is arguably the RSA algorithm of [RSA78]. (The RSA algorithm was discovered in 1973 by Clifford Cocks at GCHQ, but was classified.) RSA is based on the idea that most arithmetic operations on a large number N take time that is polynomial in the number of bits in N, but factoring a large number N requires time that is exponential in the number of bits in N.

To construct RSA keys, one first finds two very large primes p and q, perhaps 1024 binary digits each. These primes should be chosen at random, by choosing random N’s in the right range and then testing them for primality until success. Let n = pˆq.

It now follows from Fermat’s little theorem that, for any integer m, m(p-1)(q-1) = 1 mod n (it suffices to show m(p-1)(q-1) = 1 mod p and m(p-1)(q-1) = 1 mod q).

One then finds positive integers e and d so that eˆd = 1 mod (p-1)(q-1); given any e relatively prime to both p-1 and q-1 it is possible to find d using the Extended Euclidean Algorithm (a simple Python implementation appears below in 29.8 RSA Key Examples). From the claim in the previous paragraph, we now know meˆd = (me ) d = m mod p.

If we take m as a message (that is, as a bit-string of length less than the bit-length of n, rather than as an integer), we encrypt it as c = me mod n. We can decrypt c and recover m by calculating cd mod n = meˆd mod n = m.

The public key is the pair xn,ey; the private key is d.

An Introduction to Computer Networks, Release 2.0.4

As with Diffie-Hellman-Merkle (28.8.1 Fast Arithmetic), the operations above can all be done in polynomial time with respect to the bit-lengths of p and q.

The theory behind the security of RSA is that, if one knows the public key, the only way to find d in practice is to factor n. And factoring is a hard problem, with a long history. There are much faster ways to factor than to try every candidate less than ?n, but it is still believed to require, in general, close-to-exponential time with respect to the bit-length of n. See 29.1.2 Factoring RSA Keys below.

RSA encryption is usually thousands of times slower than comparably secure shared-key ciphers. However, RSA needs only to be used to encrypt a secret key for a shared-key cipher; it is this latter key that actually protects the document.

For this reason, if a message is encrypted for multiple recipients, it is usually not much larger than if it were encrypted for only one: the additional space needed for each additional recipient is just the encrypted key for the shared-key cipher.

Similarly, for digital-signature purposes Alice doesn’t have to encrypt the entire message with her private key; it is sufficient (and much faster) to encrypt a secure hash of the message.

If Alice and Bob want to negotiate a session key using public-key encryption, it is sufficient for Alice to know Bob’s public key; Alice does not even need a public key. Alice can choose a session key, encrypt it with Bob’s public key, and send it to Bob.

We will look at an actual calculation of an RSA key and then an encrypted message in 29.8 RSA Key Examples.

RSA and Digital Signatures

RSA can also be used for strong digital signatures (as can any public-key system in which the roles of the encryption and decryption keys are symmetric, and can be reversed). Suppose, as above, Alice’s public key is the pair xn,ey and her private key is the exponent d. If Alice wants to sign a message m to Bob, she simply encrypts it using the exponent d from her private key; that is, she computes c = md mod n. Bob, along with everyone else in the world, can then decrypt the resulting ciphertext c with Alice’s public exponent e (that is, ce ). If this yields a valid message, then Alice (or someone in possession of her key) must have been the sender.

Generally, for signature purposes Alice will encrypt not her entire message but simply a secure hash of it, and then send both the message and the RSA-encrypted hash. Bob decrypts the encrypted hash, and the signature checks out if the result matches the hash of the corresponding message.

An Introduction to Computer Networks, Release 2.0.4

The advantage of a public-key signature over an HMAC signature is that the former uses a key with longterm persistence, and can be used to identify the individual who sent the message. The drawback is that HMAC signatures are much faster.

It is common for Alice to sign her message to Bob and then encrypt the message plus signature – perhaps with Bob’s public key – before sending it all to Bob.

Just as Alice probably prefers not to sign undated documents with her handwritten signature, she will likely prefer to apply her digital signature only to documents containing a timestamp. This helps deter replay attacks.

Factoring RSA Keys

The security of RSA depends largely on the difficulty in factoring the key modulus n = pq (though it is theoretically possible that an RSA vulnerability exists that does not entail factoring). As of 2015, the factoring algorithm that appears to be the fastest for larger keys is the so-called number-field sieve; an early version of this technique was introduced in [JP88]. A heuristic estimate of the time needed to factor a number n via this algorithm is exp(1.923ˆlog(n)1/3ˆlog(log(n))2/3), where exp(x) = ex and log(x) is the natural logarithm. To a first approximation this is exp(kˆL 1/3), where L is the bit-length of N. This is sub-exponential (because of the exponent 1/3) but still extremely slow.

The first factorization of an RSA modulus with 512 bits occurred in 1999 and was published in [CDLMR00]; this was part of the RSA factoring challenge. It took seven calendar months, using up to 300 processors in parallel. Fifteen years later, [ABDGHSTVWZ15] reported being able to do such a factorization in eight days on a 24-core machine (~5,000 core-hours), or in seven hours using 1800 cores. Some of the speedup is due to software implementation improvements, but most is due to faster hardware.

If we normalize the number-field-sieve factoring time of a 512-bit n to 1, we get the following table of estimated relative costs for factoring larger n:

From this we might conclude that 1024-bit keys are potentially breakable by a very determined and wellfunded adversary, while the 2048-bit key length appears to be much safer. In 2011 NIST’s recommended key length for RSA encryption increased to 2048 bits (publication 800-131A, Table 6). This is quite a bit

An Introduction to Computer Networks, Release 2.0.4

larger than the 128-to-256-bit recommendation for shared-key ciphers, but RSA factoring attacks are much faster than trying all keys by brute force.

Note that some parts of the factoring algorithm are highly parallelizable while other parts are less so; relative factoring times when using highly parallel hardware may therefore differ quite a bit. See also 29.8.1 Breaking the key.

Frequently Asked Questions