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.