Generate 10-digit primes for Alice and Bob.

xxxxxxxxxx

p_a = next_prime(10^10)

q_a = next_prime(p_a)

p_b = next_prime(10^10*(3/2))

q_b = next_prime(p_b)

n_a = p_a * q_a

n_b = p_b * q_b

n_a, n_b

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

xxxxxxxxxx

m_a = euler_phi(n_a)

m_b = euler_phi(n_b)

m_a, m_b

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.

xxxxxxxxxx

E_a = 

print gcd(E_a, m_a) == 1

D_a = inverse_mod(E_a, m_a)

D_a

xxxxxxxxxx

E_b = 

print gcd(E_b, m_b) == 1

D_b = inverse_mod(E_b, m_b)

D_b

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

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.

xxxxxxxxxx

ord('A'), ord('Z'), 128^4

xxxxxxxxxx

word = 'FORT'

message = sum( [ord(word[i])*128^i for i in range(4)] )

message

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

xxxxxxxxxx

signed = power_mod(message, D_a, n_a)

signed

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

xxxxxxxxxx

encrypted = power_mod(signed, E_b, n_b)

encrypted

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.

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

xxxxxxxxxx

decrypted = power_mod(encrypted, D_b, n_b)

decrypted

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.

xxxxxxxxxx

received = power_mod(decrypted, E_a, n_a)

received

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).

xxxxxxxxxx

base = received.digits(base=128)

map(chr, base)