Lab 2: making and breaking RSA

The purpose of this lab is to achieve deeper understanding of the concepts behind an asymmetric cryptographic system - RSA. The lab consists of two (conceptual) parts: implementing the RSA system, and mounting a successful attack on the RSA system.

Friday's lab introduction: slides.

1. Making RSA

1.1. Key generation

To implement RSA, you must also implement key generation. Algorithm 5.4, page 175, describes this.

• Generate two different large primes, p and q
• n := p * q
• phi(n) = (p - 1) * (q - 1) Euler's totient
• Choose random e between log2(n) and phi(n) such that gcd(e, phi(n)) = 1
• Set d := inv(e, phi(n)) Multiplicative inverse
  

See Algorithm 5.2 page 164 (the extended Euclidean algoritm for gcd) or 5.3 page 166 (more efficient).

• Public key is (e,n) and private key is (d,n)

1.1.1. Prime number generation

To generate large primes, guess an odd random number and use probabilistic tests to check if it is (most likely) a prime. Useful algorithms for testing primality are the Solovay-Strassen (alg. 5.6, page 182) and the Miller-Rabin (alg 5.7, page 188, slightly more efficient).

A sample implementation of Miller-Rabin can be found on the Wikipedia page (see "Sample Code").

If you insist on not using Miller-Rabin, the Solovay-Strassen algorithm can be reformulated as

SV-Test(b):
if, for 100 random numbers ''a'' less than b
    gcd(a,b) == 1 and Jacobi(a,b) mod b == pow(a,(b-1)/2) mod b
then b is a prime with very high probability

The Jacobi symbol is used in the Solovay-Strassen algorithm. Here is an algoritm to evaluate it in the case gcd(a,b)==1.

Jacobi(a,b):

if a == 1 then return 1
else if a mod 2 == 0 then 
    if (b * b - 1)/8 mod 2 == 0 then
	return Jacobi(a/2, b)
    else return -(Jacobi(a/2, b)
else if (a - 1)*(b - 1)/4 mod 2 == 0 then
    return Jacobi(b mod a, a)
else
     return -(Jacobi(b mod a,a))
end

1.2. Encryption/Decryption

The RSA encryption/decryption functions should be well known to you:

c = pow(m, e) mod n

m = pow(c, d) mod n

pow(a,b) raises a to the b:th power.
c - cipher text
m - plain text
(e, n) - public key
(d, n) - private key

Algorithm 5.5, page 177 in the course book is an efficient algorithm for RSA enc/decryption. Square-and-Multiply(x,c,n) computes pow(x,c) mod n.

Square-and-Multiply(x,c,n)
z := 1
for i := len-1 downto 0
  do
    z := pow(z,2) mod n
    if bit(c,i) == 1
    then z := (z * x) mod n
done
return z

where

len

the number of bits in the binary representation of c

bit(c,i)

returns the ith bit in c; e.g. bit(c,0) == 1 when c is odd

Example: bit(4,2) == 1, while bit(4,1) == 0.

Note: if you don't have the book, use Wikipedia or Google to find other descriptions.
Note 2: if the links to the algorithms for some reason don't work, notify TA by email.

1.3. Large numbers

To implement the algorithms above, you must handle use integer numbers (>> 64 bits). In Java, use the java.math.BigInteger class. In C, use the GNU multiple precision library (see in particular 1, 2, 3, 4, 5).

1.4. Handin

You should hand in a program which can

• generate a new RSA keypair, given the desired size of n
• encrypt a plaintext, given a key (and n)
• decrypt a ciphertext, given a key (and n).

Test your code by generating keys of different sizes (e.g. 10 digits, 50 digits, 200 digits), encrypting and decrypting examples, and by checking that your exponentiation-modulo-n and prime-number-generation functions give the same results as the pre-defined versions.

---

2. Breaking RSA

If used the wrong way, RSA can be very insecure. One such case is when the plaintexts encrypted are small.

Your task is to implement the attack on RSA, and apply it to some ciphertexts. (Below, a^b means a to the b:th power.)

2.1. Short m in RSA

Given the public key (e,n) a brute-force ciphertext-only attack may require us to encrypt all possible m to see which one matches the ciphertext.

Factorising c = m^e (mod n) = (m1 * m2)^e (mod n) = (m1^e)*(m2^e) (mod n) = c1*c2 (mod n) makes the required encryptions fewer: if m < 2^k for some k, then with reasonable probability, m1 and m2 < 2^(k/2).

Attack description: given ciphertext c, public key (e,n):

• Generate possible cipher texts

for i := 1 to 2^(k/2)

table[i] = i^e mod n

The main idea here, that you should be able to easily get i from i^e mod n and i^e mod n from i in your datastructure.

• Find i, j such that c * inv(i^e mod n, n) mod n = X. This value X is actually j^e mod n for i, j < 2^(k/2).
• If such X can be found in table among all generated ciphertexts, then m = i * j mod n, where j is found by looking at index of X value.

Implement these two steps in separate functions.

You can test your program by creating input for it using the "Making RSA" part, encrypting 8-bit (character) values separately.

Note:
You are supposed to pick K number yourself. It is part of cracking the code.

Tips:

• Keeping the table sorted may be efficient, but is not necessary.
• It could also help to improve efficiency is to calculate inverses inv(i^e mod n, n) for every i.

2.2. Handin

You should hand in:

• a program that can read a sequence of cipher texts (e.g. line by line from a file), a public key, and a value of k, and output the decrypted plain texts. (Hint: you need only do step 1 of the attack once for a given k.)
• the plain texts corresponding to the following cipher text/key pairs, where the plain text sequences are 8-bit character values.

D in files are kind of typo, disregard it, it is a public key. Will be fixed later.

1. key, cipher sequence - not hard
2. key, cipher sequence - less trivial
3. key, cipher sequence - a bit more complicated