Math 310 - RSA Part 1

10/10/18

Letters and Numbers

We write words using letter of the alphabet. Our messages are sent as numbers. We need to have some method of translating (encoding) text to numbers, and untranslating (decoding) numbers back to text.

Be sure to Evaluate this code:

Steps for RSA

Here is an overview:

1. Generate two large prime numbers, p and q. These numbers must remain your secret.
2. Compute n=p*q and phi=(p-1)(q-1). phi is ϕ(n). n will be a public number, but keep phi secret.

3. Select e to be some number, less than n and relatively prime to phi. n and e will be your public key.
   Note: This e is the name of an positive integer that will be used for encyrption, not the irrational e.)

4. Since e is coprime (another word for relatively prime) to phi, there is an integer f such that
   $$e \cdot f \equiv 1 \bmod(\phi(n))$$
   Be sure to keep f a secret.
   Note: Dr Crisman (the author of NTIC) uses f for the secret key exponent. Many authors use d, for decryption

Using RSA

Setup a public key-- n and e

You'll need two large primes p and q that are never revealed.

Now choose a value for e. It will need to be relatively prime to phi. This code will check that.

We're ready to try encoding a message, but we need to check that the encoded message is less than n

Setup a private key -- f

We need f the multiplicative inverse of e \bmod \phi(n)

Recall that the Sage command xgcd(a,b) returns (g,u,v) where:

• g is the gcd(a, b)
• u and v are the coefficients in the linear combination:
  u ⋅ a + v ⋅ b = g
  

Take a look at:

Use xgcd(e,phi) in the next cell to find f

You can test you result here:

Finally, let's see ...: