Mathematics 5
Winter Term 2000
The World According to Mathematics

Dwight Lahr and Josh Laison

Monday Discussion: Week #9

Today we are going to be using the RSA encryption algorithm to send and receive secret
messages. The situation is this. Some groups will be successful corporations recruiting recent
Dartmouth graduates. Some groups will be the recent Dartmouth graduates. Each corporation is
looking for only one new employee. The goal of the corporations is to pay their new employees
as little as possible. The goal of the recent graduates is to obtain the highest possible starting
salary.

1.

Each group should create a public key (a, n) and retain a private key b. The primes used for
these keys should be about 40 digits long to ensure that Maple can’t crack the encryption
algorithm. (This means that your nwill be about 80 digits long.)To find a 40-digit prime p,
start with an arbitrary 40-digit number, and write the Maple line:

p:=nextprime(xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx);

replacing the x’s with your number. The public keys will be published in a common text
document that will be accessible to every group. Also included in the text document will be
a blitz name where the group can receive messages.

2.

Using the public key of the intended receiver, encrypt messages to your intended employees
or employers to negotiate for the best deal. Each message should be sent by blitz to the
intended receiver and also printed on the local printer and stored for public inspection. You
may try to crack the encrypted messages of your competitors.

3.

When you have secured a deal with the employee/employer of your choice, each group
should send the other an electronic signatureto seal the deal. Do this in the following way:

a. Send a message including your name and encrypt it by computing
your private key, and a2 is your receiver’s public key.

, where b1 is

a2
b. To decrypt an electronic signature, compute b 1

C, (C^b1^a2), where b1 is your private key, and a2 is
the sender’s public key.

4.

Explain why encrypting and decrypting a message in this way (the way outlined in part 3)
ensures that the receiver knows that the sender is who they say they are. Why do you think
this is called an electronic signature?