RSA for Math 103 section 99

# The homework problem(s)

Each person individually or in a group should try to "break RSA". The major part of the assignment, however, follows.

Each working group has a public key in the table below. This public key should be used to send messages to that group. I will send every member of each group the private key for that group. The group members should use the group's private key to decrypt encrypted messages sent to them by other groups. You will need to be very careful! Words are changed to numbers as in previous assignments: A --> 01, B --> 02, etc. There's a table below which you can use. Each group should do the following:

• Step 0 Read the group's entries in the columns "Sending instructions" and "The message". Both of these were written using RSA with the group's own public key. The group should decrypt each of these entries with their private key. The sending instructions will ask the group to send "The message" to another group.
• Step 1 Encrypt the message (using the receiving group's public key), and send the encrypted message to every member of the receiving group. Also send me a message (with decrypted content!) telling me that you have accomplished this step. I'll change the Step 1 column entry from (red) to (blue) to record your achievement.
• Step 2 When you get a message from another group, decrypt it, and send me a copy of the decrypted message. I'll change the Step 2 column entry from (red) to (blue) to record your achievement.

The modulus (N=pq) for the RSA messages mentioned will be the same for all groups and is

 2213050170599396381609356104023201375003

Group Student Name Public (encoding) exponent Sending instructions The message Step 1 Step 2
The FBI group Edward DeGuzman 620824941440951262241141618109861 1516278584305359453942605866613311523491 1003850437965516516115166073936410071777
Kim Fife
Alyna Jacobs
Daniel Shavitz
The ACLU group Julie Anastasi 104967988466866445473859997769153 638253924627777747499179654402232573085 1273437156156126338206627965608179218087
Nolan Henry
Mark Ryan
Margaret Wu
The Electronic Freedom Group Craig Gargano 378204911693968634982102786776777 1657174845786267133114042771481273738230 987614685652633706392530424705530737555
Amy Joh
Hanna Schwartz
Miroslaw Szatko
The Russia group Michael Civins 717884810696514914832595842165833 1071181025049728975173727782415875975501 1715434844546319083525267780615488025707
Jonathan Hammer
Peter Samet
Lee Walker
The European Union group Juraj Dlhopolcek 719398767580126746722889917738099 1526311105773428436204884664538204833854 371616379107110176348152115674929789668
Sunit Jariwala
Dan Ksepka
Frank J. Miles
The Latin American group Adriana Garriga López 576973768067410299701441951459651 802052230853151541812341856765345484275 928885417104581061235905919044008042223
Derek Kanarek
Carlos Ron
The Far East group Helen Lloyd-Williams 480006769848893409203522895394751 341393421285880500166246944855364471903 2203100607923917378801736491909567945151
Kim Shah

Please note that although RSA and close relatives are widely used now for highly secure applications, what I've done here should not be viewed as secure or useful in the "real world". It is a class exercise and isn't really safe for industrial secrets, love letters, or espionage (!). The N used here isn't big enough and "good" key selection has not been practiced: keys should be selected using somewhat more constraints than I have suggested. Finally, consquences could result not only from government reaction (as the policy discussion might suggest) but also from corporations asserting copyright or patent protection (see, for example, rsa.com or pgp.com).

I am interested in furthering your education at every opportunity. I therefore have made each message the title of one of the Sherlock Holmes short stories written by Arthur Conan Doyle. There are fifty-six of them. In fact, each of these short stories cited is in public domain and can be read on the web: see http://www.citsoft.com/holmes3.html for some really nice fiction. I was going to use the sonnets of Shakespeare, but I am not literate enough.

# Breaking RSA

This might be the last contest. The prize budget is running low ... In an effort to spread around the joy, previous winners will earn my respect and congratulations but only previous non-winners are eligible for the new valuable prize. Previous non-winners may work with previous winners, however. Every student should enter the contest either individually or as a member of a group -- it is part of the homework assignment.

What's known

The public sees the following information:

 Today's number is 108683791246377552930889

Public keys
Alice 558222976314833
Bob 91486227764076404995459

These messages are then observed:

Bob (to Alice)   53397684690326489272244
Note: this is a message to Alice, so it uses Alice's public key.

Alice (to Bob)   26563411027343523303980
Note: this is a message to Bob, so it uses Bob's public key.

The Contest

Break the encryption. Find the messages, and send me the content. You'll certainly need help from some tool like Maple. Try to find and use the appropriate Maple instruction which will make reading these messages very easy.

# Using Maple for RSA

We need to have Maple compute AB (mod C) for numbers A, B, and C whose lengths are quite large in order to do the homework problems and to try the contest. Ordinarily we could just write A^B mod C; and Maple would compute the desired answer. For example, 32 is 9, so the command 3^2 mod 7 returns the value 2.

I don't know the internal workings of Maple, but I guess that when Maple encounters A^B modC;, it computes AB in a rather direct fashion, multiplying A by itself B times, divides the result by C, and then prints the remainder. If B is large, straightforward computation of AB takes a long time and may result in a number too large for Maple to handle. Several people had this problem doing the Diffie-Hellman homework assignment.

The instruction 3^12345 mod 2; just took about a quarter of a second on one of the Math Department computers (not a particularly fast machine). 12345^12345 mod 2; then took over 17 seconds, and asking for 123456789^123456789 mod 2; resulted in the message Error, object too large with no answer provided. By the way, the answer in all cases should have been 1 since the numbers involved were powers of odd integers. We need something better if we want to use Maple to do RSA encryption and decryption. Here we will need to compute AB (mod C) when A, B, and C are each 20 digits or more long.

The computations can be done efficiently by taking advantage of repeated squaring to do exponentiation, as discussed in class. I've written a small Maple procedure to exponentiate using this idea. Here is the procedure. You do not need to know or worry about what happens "inside" it. I'll describe how to use it in the text following.

```ES:=proc(base,power,modulus)
local A,B,C;
A:=1; B:=power;C:=base;
while type(B,positive) do
if type(B,odd) then A:=A*C mod modulus; B:=B-1; fi;
B:=B/2; C:=C^2 mod modulus
od;
RETURN(A);
end;```
This provides a much faster way to do exponentiation. It also allows us to use Maple to compute powers fast for larger exponents. After Maple has been told about this procedure, it can be used to compute AB (mod C) by typing ES(A,B,C). For example, the command ES(3,12345,2) took one-hundredth of a second, and the command ES(12345,12345,2) also took one-hundredth of a second. And, last, ES(123456789,123456789,2), which requests a number Maple previously refused to compute, is also computed in less than one-hundredth of a second!

Maybe that's enough chatter. To use ES, you must copy the procedure into your Maple session. You should be able to use your mouse to point and grab the material above (take exactly what's in boldface type). I'll show and comment on a Maple session below using RSA. Please read this material. Questions are welcome.

First the RSA setup: I will assume that there are two users, Charlie and Deborah. What do we need to know?

 N will be 1783854152318969 here.

For your information, N is the product of the primes P=19669087 and Q=90693287. This is unknown to the "public". Otherwise the security of the encryption would be effectively compromised.

 Public key Private key Charlie 604305623921 155833484920913 Deborah 745580047409 889041818372597

Charlie would normally not know Deborah's private key, nor would Deborah know Charlie's private key. Only the column of public keys would be known generally.

Charlie will send the message TOAD to Deborah. Deborah will reply with the message FROG. We'll need to translate these alphabetic messages into numbers. Let's continue using our simple-minded technique, which is helped by using the table below. In reality, people could use the ASCII code which is described in the text. You may use this table for the other parts of the homework.

 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Using this scheme, T   O   A   D becomes the number 20   15   01   04 -- just 20150104 without the spaces, and FROG becomes the number 06181507 . Note that the initial 0 in the number will not be reported by Maple. For example, the number 0123 is just 123 to Maple. So Charlie will send the number to Deborah encrypted with Deborah's public key, and Deborah will decrypt it with her private key. She then will reply to Charlie, encrypted with his public key. In turn, Charlie will decrypt this message with his private key.

Here is a record of an actual Maple session which will accomplish the computations needed by Charlie and Deborah. The Maple commands and replies will be in this typeface and I will add comments in this typeface, indented. The comments were not part of the Maple session.

```lagrange>maple

Instead of "xmaple" I typed maple at the prompt.
This is a different way to use the program, with
no snazzy icons, colors, etc. Here we're just doing
a few computations. The buttons and windows may not
be useful and could indeed be distracting.

|\^/|     Maple V Release 4 (Rutgers University)
._|\|   |/|_. Copyright (c) 1981-1996 by Waterloo Maple Inc. All rights
\  MAPLE  /  reserved. Maple and Maple V are registered trademarks of
<____ ____>  Waterloo Maple Inc.
|       Type ? for help.
> ES:=proc(base,power,modulus)
> local A,B,C;
> A:=1; B:=power;C:=base;
> while type(B,positive) do
>     if type(B,odd) then A:=A*C mod modulus; B:=B-1; fi;
>         B:=B/2; C:=C^2 mod modulus
>         od;
> RETURN(A);
> end;
ES := proc(base, power, modulus)
local A, B, C;
A := 1;
B := power;
C := base;
while type(B, positive) do
if type(B, odd) then A := A*C mod modulus; B := B - 1 fi;
B := 1/2*B;
C := C^2 mod modulus
od;
RETURN(A)
end

All that I've done here is exactly copy the text
of the ES procedure to an input line. Maple then
indicated it understood the procedure by writing
it back to me. It only remembers this procedure
during this session. If I want to use ES during
another Maple session, I must copy it again.

> 231^456 mod 789;
186

Now I'll check that things are working the way
they're supposed to. I asked Maple to compute
231456 (mod 789) and got the answer 186.

> ES(231,456,789);
186

This command returned the same answer, so I now do
believe things are working well. I check things like
this almost always. The checks don't use much time or
effort. They help me find typing errors or any other
problems.

> N:=1783854152318969;
N := 1783854152318969

I told Maple N's value. I used the mouse to
grab this and other long numbers but I check
the first and last digits of numbers that I
copy. My mouse technique isn't perfect.

> C_pub_key:=604305623921;
C_pub_key := 604305623921

And I now told it Charlie's public key. I tend
to use long identifying names for variables in
situations like this. Confusion is too easy.

> C_priv_key:=155833484920913;
C_priv_key := 155833484920913

Charlie's private key.

> D_pub_key:= 745580047409;
D_pub_key := 745580047409

> D_priv_key:=889041818372597;
D_priv_key := 889041818372597

Deborah's public and private keys.

> ES(20150104,D_pub_key,N);
1654115086409835

This is Charlie's encryption of TOAD using
Deborah's public key. With this instruction,
Charlie has Maple compute 20150104(D_pub_key)
(mod N). This number is 20150104745580047409
(mod 1783854152318969). Wow! I don't think
anyone would want or could do computations
like this by hand! Charlie sends this number
to Deborah.

> ES(1654115086409835,D_priv_key,N);
20150104

Deborah decodes the message by exponentiating it
with her private key. We get back 20150104, TOAD
again. We have accomplished meaningful secret
communication (if you like toads). You can
practice with various messages until you feel
comfortable with this method.

> ES(06181507,C_pub_key,N);
199543635933342

Now it is Deborah's turn. She sends a message to
Charlie, encrypting it with Charlie's public key.
The long number is what is sent to him in public.
The word FROG seems well disguised!

> ES(199543635933342,C_priv_key,N);
6181507

Charlie decodes the message by exponentiating it
with his private key. He should read the digits
in pairs from right to left. The missing "0" in
"F" will be apparent. The word FROG appears to
Charlie.

> quit;```
Although Lagrange is not an especially fast computer, the entire session described above took less than a quarter of a second of computation time. This isn't very much. I only had to erase one typing error in what's shown above (sigh!). The number of typing errors can be decreased by using a mouse to grab and copy long numbers. Questions are welcome.