# 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:

- Generate two large prime numbers,
`p`

and `q`

. These numbers must remain your secret.
- Compute
`n=p*q`

and `phi=(p-1)(q-1)`

. `phi`

is ϕ(n). `n`

will be a public number, but keep `phi`

secret.
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*.)

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 ...:

This page last modified
Thu Jan 10 15:13:36 PST 2019
bic - turing