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.

## No comments:

Post a Comment