RSA Algorithm

The RSA algorithm is named after Ron Rivest, Adi Shamir and Len Adleman, who invented it in
1977 [RIVE78]. The basic technique was first discovered in 1973 by Clifford Cocks [COCK73]
of CESG (part of the British GCHQ) but this was a secret until 1997. The patent taken out by
RSA Labs has expired.

The RSA algorithm can be used for both public key encryption and digital signatures. Its security
is based on the difficulty of factoring large integers.

Contents
 Key generation algorithm
 Encryption
 Decryption
 Digital signing
 Signature verification
 Notes on practical application
 Summary of RSA
 Key length
 Computational efficiency and the Chinese Remainder Theorem
 Theory and proof of the RSA algorithm
 A very simple example
 A slightly less simple example
 A real example
 PKCS#1 Schemes
o Encryption using PKCS#1v1.5
o Signing using PKCS#1v1.5
 Weaknesses in RSA
 More Advanced Schemes
o RSAES-OAEP
o RSASSA-PSS
o ANSI X9.31 Signature Scheme
o ISO/IEC 9796
o RSA-KEM
o Ferguson-Schneier Encryption
 Notation and Conventions
 Implementation in C and VB
 References
 Contact
 Comments
Key Generation Algorithm
1. Generate two large random primes, p and q, of approximately equal size such that their
product n = pq is of the required bit length, e.g. 1024 bits. [See note 1].
2. Compute n = pq and (φ) phi = (p-1)(q-1).
3. Choose an integer e, 1 < e < phi, such that gcd(e, phi) = 1. [See note 2].
4. Compute the secret exponent d, 1 < d < phi, such that ed ≡ 1 (mod phi). [See note 3].
5. The public key is (n, e) and the private key is (n, d). Keep all the values d, p, q and phi
secret.

 n is known as the modulus.

 e is known as the public exponent or encryption exponent or just the exponent.
 d is known as the secret exponent or decryption exponent.

Encryption
Sender A does the following:-

1. Obtains the recipient B's public key (n, e).

2. Represents the plaintext message as a positive integer m [see note 4].
3. Computes the ciphertext c = me mod n.
4. Sends the ciphertext c to B.

Decryption
Recipient B does the following:-

1. Uses his private key (n, d) to compute m = cd mod n.

2. Extracts the plaintext from the message representative m.

Digital signing
Sender A does the following:-

1. Creates a message digest of the information to be sent.

2. Represents this digest as an integer m between 0 and n-1. [See note 5].
3. Uses her private key (n, d) to compute the signature s = md mod n.
4. Sends this signature s to the recipient, B.

Signature verification
Recipient B does the following:-

1. Uses sender A's public key (n, e) to compute integer v = se mod n.

 2. Extracts the message digest from this integer.
3. Independently computes the message digest of the information that has been signed.
4. If both message digests are identical, the signature is valid.

Notes on practical applications

1. To generate the primes p and q, generate a random number of bit length b/2 where b is
the required bit length of n; set the low bit (this ensures the number is odd) and set the
two highest bits (this ensures that the high bit of n is also set); check if prime (use the
Rabin-Miller test); if not, increment the number by two and check again until you find a
prime. This is p. Repeat for q starting with a random integer of length b-b/2. If p<q, swop
p and q (this only matters if you intend using the CRT form of the private key). In the
extremely unlikely event that p = q, check your random number generator. Alternatively,
instead of incrementing by 2, just generate another random number each time.

There are stricter rules in ANSI X9.31 to produce strong primes and other restrictions on
p and q to minimise the possibility of known techniques being used against the algorithm.
There is much argument about this topic. It is probably better just to use a longer key
length.

2. In practice, common choices for e are 3, 17 and 65537 (216+1). These are Fermat primes,
sometimes referred to as F0, F2 and F4 respectively (Fx=2^(2^x)+1). They are chosen
because they make the modular exponentiation operation faster. Also, having chosen e, it
is simpler to test whether gcd(e, p-1)=1 and gcd(e, q-1)=1 while generating and testing
the primes in step 1. Values of p or q that fail this test can be rejected there and then.
(Even better: if e is prime and greater than 2 then you can do the less-expensive test (p
mod e)!=1 instead of gcd(p-1,e)==1.)
3. To compute the value for d, use the Extended Euclidean Algorithm to calculate d = e-1
mod phi, also written d = (1/e) mod phi. This is known as modular inversion. Note that
this is not integer division. The modular inverse d is defined as the integer value such that
ed = 1 mod phi. It only exists if e and phi have no common factors.
4. When representing the plaintext octets as the representative integer m, it is usual to add
random padding characters to make the size of the integer m large and less susceptible to
certain types of attack. If m = 0 or 1 or n-1 there is no security as the ciphertext has the
same value. For more details on how to represent the plaintext octets as a suitable
representative integer m, see PKCS#1 Schemes below or the reference itself [PKCS1]. It
is important to make sure that m < n otherwise the algorithm will fail. This is usually
done by making sure the first octet of m is equal to 0x00.
5. Decryption and signing are identical as far as the mathematics is concerned as both use
the private key. Similarly, encryption and verification both use the same mathematical
operation with the public key. That is, mathematically, for m < n,

m = (me mod n)d mod n = (md mod n)e mod n

However, note these important differences in implementation:-

 o The signature is derived from a message digest of the original information. The
recipient will need to follow exactly the same process to derive the message
digest, using an identical set of data.
o The recommended methods for deriving the representative integers are different
for encryption and signing (encryption involves random padding, but signing uses
the same padding each time).

Summary of RSA
 n = pq, where p and q are distinct primes.
 phi, φ = (p-1)(q-1)
 e < n such that gcd(e, phi)=1
 d = e-1 mod phi.
 c = me mod n, 1<m<n.
 m = cd mod n.

Key length
When we talk about the key length of an RSA key, we are referring to the length of the modulus,
n, in bits. The minimum recommended key length for a secure RSA transmission is currently
1024 bits. A key length of 512 bits is now no longer considered secure, although cracking it is
still not a trivial task for the likes of you and me. The longer your information is needed to be
kept secure, the longer the key you should use. Keep up to date with the latest recommendations
in the security journals.

There is small one area of confusion in defining the key length. One convention is that the key
length is the position of the most significant bit in n that has value '1', where the least significant
bit is at position 1. Equivalently, key length = ceiling(log2(n+1)). The other convention,
sometimes used, is that the key length is the number of bytes needed to store n multiplied by
eight, i.e. ceiling(log256(n+1)).

The key used in the RSA Example paper [KALI93] is an example. In hex form the modulus is
0A 66 79 1D C6 98 81 68 DE 7A B7 74 19 BB 7F B0
C0 01 C6 27 10 27 00 75 14 29 42 E1 9A 8D 8C 51
D0 53 B3 E3 78 2A 1D E5 DC 5A F4 EB E9 94 68 17
01 14 A1 DF E6 7C DC 9A 9A F5 5D 65 56 20 BB AB

The most significant byte 0x0A in binary is 00001010'B. The most significant bit is at position
508, so its key length is 508 bits. On the other hand, this value needs 64 bytes to store it, so the
key length could also be referred to by some as 64 x 8 = 512 bits. We prefer the former method.
You can get into difficulties with the X9.31 method for signatures if you use the latter
convention.
Computational Efficiency and the Chinese Remainder
Theorem (CRT)
Key generation is only carried out occasionally and so computational efficiency is less of an
issue.

The calculation a = be mod n is known as modular exponentiation and one efficient method to
carry this out on a computer is the binary left-to-right method. To solve y = x^e mod n let e be
represented in base 2 as

e = e(k-1)e(k-2)...e(1)e(0)

where e(k-1) is the most significant non-zero bit and bit e(0) the least.

set y = x
for bit j = k - 2 downto 0
begin
y = y * y mod n /* square */
if e(j) == 1 then
y = y * x mod n /* multiply */
end
return y

The time to carry out modular exponentation increases with the number of bits set to one in the
exponent e. For encryption, an appropriate choice of e can reduce the computational effort
required to carry out the computation of c = me mod n. Popular choices like 3, 17 and 65537 are
all primes with only two bits set: 3 = 0011'B, 17 = 0x11, 65537 = 0x10001.

The bits in the decryption exponent d, however, will not be so convenient and so decryption
using the standard method of modular exponentiation will take longer than encryption. Don't
make the mistake of trying to contrive a small value for d; it is not secure.

An alternative method of representing the private key uses the Chinese Remainder Theorem
(CRT). The private key is represented as a quintuple (p, q, dP, dQ, and qInv), where p and q are
prime factors of n, dP and dQ are known as the CRT exponents, and qInv is the CRT coefficient.
The CRT method of decryption is four times faster overall than calculating m = cd mod n. For
more details, see [PKCS1]. The extra values for the private key are:-

dP = (1/e) mod (p-1)

dQ = (1/e) mod (q-1)
qInv = (1/q) mod p where p > q

where the (1/e) notation means the modular inverse (see note 3 above). These values are pre-
computed and saved along with p and q as the private key. To compute the message m given c do
the following:-

m1 = c^dP mod p
m2 = c^dQ mod q
h = qInv(m1 - m2) mod p
m = m2 + hq

Even though there are more steps in this procedure, the modular exponentation to be carried out
uses much shorter exponents and so it is less expensive overall.

[2008-09-02] Chris Becke has pointed out that most large integer packages will fail when
computing h if m1 < m2. This can be easily fixed by computing

h = qInv(m1 + p - m2) mod p

\--===-=-=-=-=\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

Weaknesses in RSA
Small encryption exponent

If you use a small exponent like e=3 and send the same message to different recipients and just
use the RSA algorithm without adding random padding to the message, then an eavesdropper
could recover the plaintext.

Using the same key for encryption and signing

Given that the underlying mathematics is the same for encryption and signing, only in reverse, if
an attacker can convince a key holder to sign an unformatted encrypted message using the same
key then she gets the original.

Acting as an oracle

There are techniques to recover the plaintext if a user just blindly returns the RSA
transformation of the input. So don't do that.

Solutions

1. Don't use the same RSA key for encryption and signing.
2. If using PKCS#v1.5 encoding, use e=0x10001 for your public exponent.
3. Always format your input before encrypting or signing.
4. Always add fresh random padding - at least 8 bytes - to your message before encrypting.
5. When decrypting, check the format of the decrypted block. If it is not as expected, return an
error, not the decrypted string.
6. Similarly, when verifying a signature, if there is any error whatsoever, just respond with "Invalid
Signature".