RSA Encryption - Tutorial

In the last 3 months I've really started to hear lots about RSA and its use in software protections, Hiew for example uses a 256-bit key, Advanced Disk Catalog uses 64-bits and IDA an effectively irreversible 1024-bits. In 1976 three researchers at M.I.T. (Ron Rivest, Adi Shamir and Les Adleman) introduced a public key cryptosystem, prior to this only private key cryptosystems had been used.

The RSA cryptosystem is based on modular exponentiation modulo the product of 2 large primes. Each individual has an encrypting key consisting of a modulus n = pq, where p & q are large primes, say with 200 digits each, and an exponent e that is relatively prime to (p-1)(q-1). To produce a usable key, 2 large primes must be found (this can be done quickly on a computer using probabilistic primality tests). However the product of these primes n = pq, with approximately 400 digits, cannot be factored in a reasonable length of time.

RSA Encryption

In the RSA encryption method, messages are translated into sequences of integers. This can be done by translating each letter into an integer, as is done with the Caesar cipher. These integers are grouped together to form larger integers, each representing a block of letters. The encryption proceeds by transforming the integer M, representing the plaintext (the original message) to an integer C, representing the ciphertext (the encrypted message) using the function.

C = Me mod n

We select 2 primes, p = 43 & q = 59 so that n = 43 · 59 = 2537, and with e = 13.

gcd (e,(p-1)(q-1) = gcd(13,42.58) = 1   (gcd = greatest common divisor)

Lets take the hypothetical message STOP, first we'll convert the letters into their numerical equivalents (position in the alphabet-1) and then group those numbers into blocks of 4.

1819 1415 = ST OP

We encrypt each block using the mapping:

C = M¹³ mod 2537

Computations using modular multiplication show that 1819¹³ mod 2537 = 2081, and 1415¹³ mod 2537 = 2182. The encrypted message is thus 2081 2182.

RSA Decryption

The plaintext message can be quickly recovered when the decryption key d, an inverse of e modulo (p-1)(q-1) is known. (Such an inverse exists since gcd(e,(p-1)(q-1))=1). To see this, note that if d e ║ 1 (mod (p-1)(q-1)), there is an integer k such that d e = 1 + k(p-1)(q-1). It follows that.

C^d = (M^e)^d = M^de = M^{1+k (p-1)(q-1)}

By Fermat's theorem (assuming that gcd(M,p) = gcd(M,q) = 1, which holds except in rare cases, it follows that M^p-1 ║ 1 (mod p) and M^q-1 ║ 1 (mod q), consequently.

C^d = M · (M^{p-1) k (q-1)} ║ M · 1 ║ M (mod p)

and:-

C^d = M · (M^{q-1) k (p-1)} ║ M · 1 ║ M (mod q)

Since gcd(p,q) = 1, it follows that:-

C^d ║ M (mod pq)

Example Decryption

Using the simple cipher above we receive the message 0981 0461, lets go about decrypting it.

n = 43 · 59 and e (exponent) = 13, we can work out that d = 937 is an inverse of 13 modulo 42 · 58 = 2436. We therefore use 937 as our decryption exponent, therefore.

P = C⁹³⁷ mod 2537

Using fast modular exponentiation (an algorithm) we compute 0981⁹³⁷ mod 2537, = 0704 and 0461⁹³⁷ mod 2537 = 1115. Quick translation reveals that this message was HELP.

RSA Security

Well, why is the RSA cryptosystem suitable for public key cryptography?, when we know the factorization of the modulus n, that is, when we know p and q we can use the Euclidean algorithm to quickly find an exponent d inverse to e modulo (p-1)(q-1). This lets us decrypt messages sent using our key.

However no method is known to decrypt messages that is not based on finding a factorization of n. The most efficient factorization methods in 1995 required billions of years to factor 400-digit integers. Consequently when p and q are 200-digit primes, messages encrypted using n = pq as the modulus cannot be found in a reasonable time unless the primes p and q are known.

I've heard a few people talk about breaking RSA, finding all the primes for example which don't exceed a specified integer isn't particularly difficult, an application of Eratosthenes sieve will serve this purpose, yet you should always be on the look out for potential implementation and key choice weaknesses (authors prime choices might be careless). If however you encounter a Russian author using a 1024-bit keyfile, forget it, the suns going to burn out before current desktop technologies can factor it, unless of course you ask very nicely for the key :-).

Addition - Factoring Techniques

As breaking RSA is a matter of simply factoring the public modulus, several techniques have been developed which are considered much more efficient and intelligent than just trying all the possibilities.

GNFS - General Field Number Sieving is as far as I know the latest factoring technology which involves sieving sets of "Q-values", the results are then accumulated and sorted before being run through a graphing algorithm followed by bitmatrix reduction, as you can see this isn't trivial :-).

MPQS - The Multiple Polynomial Quadratic Sieve is somewhat simpler and is the predecessor to the NFS (Number Field Sieve), basic theory is as follows:

Find x, y such that x ^ 2 == y ^ 2 mod RSA-N.

This is based on the good probability that: gcd(x+y, RSA-N) is not 1 or RSA-N, hence you'd have a factor. Apparently Hiew's 256-bit key was broken in this fashion.

Sieving the Q-Interval is another technique which is based around the fact that quadratic residues given by a certain polynomial and divisible by a particular prime are regularly spaced (I've seen the maths behind this and its not really for me :-) ). Essentially in sieving you add the log of the prime every such regular distance through initially zeroed memory, for each prime in the factor base. When thats done you pick out places where the accumulation exceeds a threshold; thats where you find quadratic residues divisible by lots of small primes, hence these are more likely to be double-partial, partial or full relations.