Lab 7: Public Key Cryptography, Part I

Introduction

In this lab, we will explore the mathematical foundations of public key cryptography.  The explorations are based on exercises 3.5.2-3.5.6 in the text.

Read section 3.5 before coming to lab.  Print out this worksheet, before you start editing it.

Recollection of some facts

Suppose k and n are two positive integers.  When is k invertible modulo n?

Suppose p is a prime.  What is ϕ(p)?

Suppose we have two primes (Subscript[p, 1]) and (Subscript[p, 2]).  What is ϕ((Subscript[p, 1])(Subscript[p, 2]))?

The key relationship (3.5.2)

The set-up

Suppose we have the following set-up:

(Subscript[p, 1]) and (Subscript[p, 2]) are two primes

m=(Subscript[p, 1])(Subscript[p, 2])

n=ϕ(m)

k is an integer relatively prime to n

k'≡(k^(-1)) (mod n)

Now, given a positive integer a, we compute (a^k) modulo m.  Let b be the outcome of that computation, i.e.

({{({{(a^k)≡b   (mod m)}})}})

The goal of this exploration is to determine (b^(k')) modulo m.  Let c be the outcome of that computation, i.e.

({{({{(b^(k'))≡c   (mod m)}})}})

We want to find a relationship between c and a.

We will use Mathematica to help us look at lots of examples at once.

Using Mathematica

First we will define (Subscript[p, 1]), (Subscript[p, 2]), m, and n.  Evaluate by pressing (shift + enter).  You should see what n is, given this choice of (Subscript[p, 1]) and (Subscript[p, 2]).

p1 = 3; p2 = 5;
m = p1*p2;
n = EulerPhi[m]

Next we pick a number k that is relatively prime to n and compute its inverse modulo n, using the Mathematica command PowerMod.  The command PowerMod[p,r,q] gives (p^r) modulo q.  We use it to find an inverse by letting the power be -1.

k = 3;
k2 = PowerMod[k, -1, n]

Now we make a table, whose columns are values for a, b, c, with a varying from 2 to m-1.

RSATable = Table[{a, PowerMod[a,k,m], PowerMod[PowerMod[a,k,m], k2, m]}, {a, 2, m-1}];
TableForm[RSATable]

What do you notice about a and c?

Now play with some more examples.  First change the value of k, keeping the same (Subscript[p, 1]) and (Subscript[p, 2]).  Then change (Subscript[p, 1]) and (Subscript[p, 2]), and choose several values of k accordingly.  For each “experiment,” list the values of (Subscript[p, 1]), (Subscript[p, 2]), and k that you chose, list n and m, and list the outcome of the experiment, i.e. describe what you notice about  a and c.  Finally state a conjecture.

Encoding a message (3.5.4)

Using the mathematical background from the previous exercise, you will now encode the message “GAUSS.”  (You may find it helpful to reread the paragraphs of section 3.5 entitled “The RSA public key cryptosytem.”)

First, each letter of the message “GAUSS” needs to be converted to a number.  The ASCII code is a standard code that assigns a three digit number to each letter.  See the text for the details of this code.

Write down the number below using the ASCII code.

Now that the message has been converted to a (long) number, it needs to be encrypted.  We will use the set-up described in the previous section.   Let  (Subscript[p, 1])=13, (Subscript[p, 2])=73, and k=5.

We split the message number into blocks of three digits.  Let a be the number that is the first block of three digits and compute (a^k) modulo m.  This is first part of the encrypted message.  Repeat the process for each of the three-digit blocks of numbers.  Record the encrypted message below.

Decoding a message (3.5.4)

Suppose that a message has been encoded using the RSA cyrptosystem.  How could a person decode the message?

If a person only knew the values of m and k from the set-up,  how could they break the code?

Conclusion (3.5.6)

In one paragraph, in your own words, describe methods for encoding, decoding and breaking a code, if we use Public Key Cryptography.  What is “public” in public key cryptography?  Why is it “public”?  What are the advantages in Public Key Cryptography?  Does number theory have a role in all this?