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.
e is called the public key exponent.
So the public key would be (n = 3233, e = 17). The encryption function is
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:
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
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:
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:
That is some serious exponentiation.
From the terminal I do:
The file has this:
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:
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.