# CSCE 222 Lecture 34

(and 35)« previous | *Friday, April 29, 2011* | next »

## RSA Public Key Encryption

RSA stands for last names of inventors

RSA invented to solve problem of easy crackability of bitstreams. Basically It establishes a common secret between two parties. But before we begin…

### Euler's Totient Function

Denoted by

When the product ranges over all primes that divide (prime factorization).

#### Example

Suppose is a product of two distinct primes and , then:

### Key Generation

Alice selects two distinct *large* (2000 bits) prime numbers and , and computes their product .

She selects an odd integer such that

She then computes positive integers and such that .

- In other words,

She publishes the pair ( and are kept secret because factoring is very difficult to do)

### Encryption and Decryption

**Overview:** Suppose we want to send Alice a message. This message is chopped into blocks of 1024 bits and encrypt it using the public key. To decrypt it, Alice uses her private key.

**Process:**

- For simplicity, we'll assume that the message is encoded as an integer in the range [2,n).
- If Bob wants to send the message to Alice, he gets the public key …
- and raises it to the , modulo :
- alice uses her secret key and raises it to the power:

### Correctness of RSA

*Why does this work?*

Prerequisites:

The RSA Algorithm States:

- Let be a product of two distinct primes and .
- Let such that .

#### Proof

By the Chinese Remainder Theorem, we can show that

since are distinct primes.

Hence,