Abstract Algebra: Theory and Applications

We will suppose that Alice wants to send a secret message to Bob, along with message verification (also known as a message with a digital signature). So we begin with the construction of key pairs (private and public) for both Alice and Bob. We first need two large primes for both individuals, and their product. In practice, values of $n$ would have hundreds of digits, rather than just $21$ as we have done here.

xxxxxxxxxx

p_a = next_prime(10^10)

q_a = next_prime(p_a)

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

q_b = next_prime(p_b)

n_a = p_a * q_a

n_b = p_b * q_b

n_a, n_b

Computationally, the value of the Euler $\varphi$-function for a product of primes $pq$ can be obtained from $(p-1)(q-1)\text{,}$ but we could use Sage’s built-in function just as well.

xxxxxxxxxx

m_a = euler_phi(n_a)

m_b = euler_phi(n_b)

m_a, m_b

Now we can create the encryption and decryption exponents. We choose the encryption exponent as a (small) number relatively prime to the value of $m\text{.}$ With Sage we can factor $m$ quickly to help us choose this value. In practice we would not want to do this computation for large values of $m\text{,}$ so we might more easily choose “random” values and check for the first value which is relatively prime to $m\text{.}$ The decryption exponent is the multiplicative inverse, mod $m\text{,}$ of the encryption exponent. If you construct an improper encryption exponent (not relatively prime to $m$), the computation of the multiplicative inverse will fail (and Sage will tell you so). We do this twice —- for both Alice and Bob.

xxxxxxxxxx

factor(m_a)

xxxxxxxxxx

E_a = 5*23

D_a = inverse_mod(E_a, m_a)

D_a

xxxxxxxxxx

factor(m_b)

xxxxxxxxxx

E_b = 7*29

D_b = inverse_mod(E_b, m_b)

D_b

At this stage, each individual would publish their values of $n$ and $E\text{,}$ while keeping $D$ very private and secure. In practice $D$ should be protected on the user’s hard disk by a password only the owner knows. For even greater security a person might only have two copies of their private key, one on a USB memory stick they always carry with them, and a backup in their sage deposit box. Every time the person uses $D$ they would need to provide the password. The value of $m$ can be discarded. For the record, here are all the keys:

xxxxxxxxxx

print("Alice's public key, n:", n_a, "E:", E_a)

xxxxxxxxxx

print("Alice's private key, D:", D_a)

xxxxxxxxxx

print("Bob's public key, n:", n_b, "E:", E_b)

xxxxxxxxxx

print("Bob's private key, D:", D_b)

xxxxxxxxxx

# Practice area (not linked for Sage Cell use)

Alice is going to construct a message as an English word with four letters. From these four letters we will construct a single number to represent the message in a form we can use in the RSA algorithm. The function ord() will convert a single letter to its ASCII code value, a number between 0 and 127. If we use these numbers as “digits” mod 128, we can be sure that Alice’s four-letter word will encode to an integer less than ${128}^4=268,435,456\text{.}$ The particular maximum value is not important, so long as it is smaller than our value of $n$ since all of our subsequent arithmetic is mod $n\text{.}$ We choose a popular four-letter word, convert to ASCII “digits” with a list comprehension, and then construct the integer from the digits with the right base. Notice how we can treat the word as a list and that the first digit in the list is in the “ones” place (we say the list is in “little-endian” order).

xxxxxxxxxx

word = 'Sage'

digits = [ord(letter) for letter in word]

digits

xxxxxxxxxx

message = ZZ(digits, 128)

message

First, Alice will sign her message to provide message verification. She uses her private key for this, since this is an act that only she should be able to perform.

xxxxxxxxxx

signed = power_mod(message, D_a, n_a)

signed

Then Alice encrypts her message so that only Bob can read it. To do this, she uses Bob’s public key. Notice how she does not have to even know Bob — for example, she could have obtained Bob’s public key off his web site or maybe Bob announced his public key in an advertisement in the New York Times.

xxxxxxxxxx

encrypted = power_mod(signed, E_b, n_b)

encrypted

Alice’s communication is now ready to travel on any communications network, no matter how insecure the network may be, and no matter how many snoops may be monitoring the network.

xxxxxxxxxx

# Practice area (not linked for Sage Cell use)

Now assume that the value of encrypted has reached Bob. Realize that Bob may not know Alice, and realize that Bob does not even necessarily believe what he has received has genuinely originated from Alice. An adversary could be trying to confuse Bob by sending messages that claim to be from Alice. First, Bob must unwrap the encyption Alice has provided. This is an act only Bob, as the intended recipient, should be able to do. And he does it by using his private key, which only he knows, and which he has kept secure.

xxxxxxxxxx

decrypted = power_mod(encrypted, D_b, n_b)

decrypted

Right now, this means very little to Bob. Anybody could have sent him an encoded message. However, this was a message Alice signed. Lets unwrap the message signing. Notice that this uses Alice’s public key. Bob does not need to know Alice — for example, he could obtain Alice’s key off her web site or maybe Alice announced her public key in an advertisement in the New York Times.

xxxxxxxxxx

received = power_mod(decrypted, E_a, n_a)

received

Bob needs to transform this integer representation back to a word with letters. The chr() function converts ASCII code values to letters, and we use a list comprehension to do this repeatedly.

xxxxxxxxxx

digits = received.digits(base=128)

letters = [chr(ascii) for ascii in digits]

letters

If we would like a slightly more recognizable result, we can combine the letters into a string.

xxxxxxxxxx

''.join(letters)

Bob is pleased to obtain such an informative message from Alice. What would have happened if an imposter had sent a message ostensibly from Alice, or what if an adversary had intercepted Alice’s original message and replaced it with a tampered message? (The latter is known as a “man in the middle” attack.)

In either case, the rogue party would not be able to duplicate Alice’s first action — signing her message. If an adversary somehow signs the message, or tampers with it, the step where Bob unwraps the signing will lead to total garbage. (Try it!) Because Bob received a legitimate word, properly capitalized, he has confidence that the message he unsigned is the same as the message Alice signed. In practice, if Alice sent several hundred words as her message, the odds that it will unsign as cohrent text are astronomically small.

What have we demonstrated?

Of course, without making new keys, you can reverse the roles of Alice and Bob. And if Carol makes a key pair, she can communicate with both Alice and Bob in the same fashion.

If you want to use RSA public-key encryption seriously, investigate the open source software GNU Privacy Guard, aka GPG, which is freely available at www.gnupg.org/

⁸

www.gnupg.org

. Notice that it only makes sense to use encryption programs that allow you to look at the source code.

xxxxxxxxxx

# Practice area (not linked for Sage Cell use)