## 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 = 53Compute n = pq = 3233Compute φ(n) = (p-1)(q-1) = 60 times 52 = 3120Choose 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 * 1843128>>> 3120 % 179`

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) % 32332790L`

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) % 31201`

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) % 323365L`

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.