Saturday, February 5, 2011

Secure communications (2)

The wikipedia article has a worked example of RSA. I'm going to shamelessly appropriate it for the following discussion.


Choose p = 61 and q = 53
Compute n = pq = 3233
Compute φ(n) = (p-1)(q-1) = 60 times 52 = 3120
Choose a number 1 < e < 3120 that is coprime to 3120


Coprime (or relatively prime) means that e and 3120 should have no common (positive) factor other than 1. Let's try e = 17. Since e is prime, we just have to check that e does not divide 3120 exactly.


>>> 17 * 183 
3111
>>> 17 * 184
3128
>>> 3120 % 17
9


e is called the public key exponent.

So the public key would be (n = 3233, e = 17). The encryption function is


m**17 (mod 3233)


The plaintext message would be padded first with extra bits. Now, suppose we want to encrypt the message m = 65. In Python we do m**e % n:


>>> (65**17) % 3233
2790L


Our ciphertext is 2790.

We compute the private key exponent, d, as the modular multiplicative inverse of e (mod φ(n)).

Consider an integer a. The modular multiplicative inverse of a is designated a-1 where


a a-1 = 1 (mod m)


Here then, we want d such that d * e = 1 (mod 3120). There is an algorithm called the extended Euclidean algorithm to do this. Here we simply note that d = 2753 is a solution since:


>>> (2753 * 17) % 3120
1


Note that the calculation required (effective) knowledge of p and q through the use of φ(n).

In order to decrypt the ciphertext 2790, we do c**d % n:


m = (c**2753) % 3233

(2790**2753) % 3233
65L


That is some serious exponentiation.

From the terminal I do:


> ssh-keygen


The file has this:


ssh-rsa AAAAB3NzaC1yc2EAAAAB..


I'm very surpised to see that this is like ascii alphanumeric or something. I'll have to look into that.

[ UPDATE: it is base 64 (RSA format here), which I'd never heard of but makes a lot of sense: uppercase + lowercase + digits = 62. We just need two more symbols, which are '+' and '/' (here). ]

A key size of 2048 bits would be common for RSA. This would give about a 600 digit number in base 10:


>>> len(str(2**2048))
617


Not sure what part of that is e versus n, but most of it is probably n, and since pq = n we're talking about quite large prime numbers.