ArticleRSA Cryptography

Alice will send a signed, encrypted message to Bob.

Section1Key Generation

Generate 10-digit primes for Alice and Bob.

Euler phi-function, with Sage, but this is simpler in practice.

Create random \(E\), and then compute \(D\), for encoding and decoding (encryption and decryption). Compute \(D\) so that these two numbers are multiplicative inverses mod \(m\). \(E\) and \(n\) are made public, but \(D\) is kept private.

Now we have keys, public and private, for both Alice and Bob.

Section2Message Creation

Alice makes a message from a four-letter word. The ord() function converts characters to integer ASCII values (0 to 127). Make one big integer, base 128. \(128^4=268\,435\,456\), so any word will encode to \(9\) digits or less. This is part of why our two primes were chosen to at least 10-digit numbers.

Alice “signs” her message using her private decoding key, since only she can do this.

Now Alice encrypts with Bob's public encoding key. Anybody else could do the same thing. This is what goes out on the wire.

The value of encrypted is unusable to anybody who intercepts it, since they do not have Bob's decryption key, and we believe it is computationally infeasible to deduce it from Bob's public values of \(E\) and \(n\).

A “man in the middle” could intercept the message and replace it with a new one encrypted for Bob. We will see how Alice's signature frustrates this attack.

Section3Message Reception

Now Bob decodes with his private decoding key, only he can do this.

Good. Now Bob will verify Alice's signature. He uses Alice's public encryption key, which anybody could do. Thius reverses Alice's use of her decryption key.

We can see that this message is correct, since we saw the original message. How does Bob know this is correct? He converts back to letters, and sees an intelligible message. Garbage here would indicate a tampered transmission or a “fake” Alice (i.e., a man-in-the-middle attack).