**CRT: Uniqueness**

What if x, y are both solutions to the equations ?

• x ≡ y (mod m_{i}) => m_{i} | (x − y), for i = 1, . .
. , n

• **Claim:**

• so x ≡ y (mod M)

Theorem 10: If
are pairwise relatively

prime and m_{i} | b for i = 1, . . . , n, then
| b.

**Proof:** By induction on n.

• For n = 1 the statement is trivial.

Suppose statement holds for n = N.

• Suppose
relatively prime, m_{i} | b for

i = 1, . . . ,N + 1.

• by IH,
c for some c

• By as sumption ,
| b, so

•
(since m_{i}’s pairwise relatively

prime => no common factors )

• by Corollary 3,

• so

• so
.

**An Application of CRT: Computer**

Arithmetic with Large Integers

Suppose we want to perform arithmetic operations (addition,

multiplication) with extremely large integers

• too large to be re presented easily in a computer

Idea:

• Step 1: Find suitable moduli
so that m_{i}’s

are relatively prime and
is bigger than the

answer.

• Step 2: Perform all the operations mod m_{j}, j =

1, . . . , n.

o This means we’re working with much smaller numbers

(no bigger than m_{j})

o The ope rations are much faster

o Can do this in parallel

• Suppose the answer mod m_{j} is a_{j}:

o Use CRT to find x such that x ≡ a_{j} (mod m_{j})

o The unique x such that 0 < x <
is the

answer to the original problem.

**Example:** The fol lowing are pairwise relatively
prime:

We can add and multiply positive integers up to

**Fermat’s Little Theorem**

Theorem 11 (Fermat’s Little Theorem):

(a) If p prime and gcd(p, a) = 1, then (mod
p).

(b) For all (mod p).

**Proof. **Let

A = {1, 2, . . . , p − 1}

B = {1a mod p, 2a mod p, . . . , (p − 1)a mod p}

Claim: A = B.

• 0 B, since
, so B A.

• If i ≠ j, then ia mod p ≠ ja mod p

since

Thus |B| = p − 1, so A = B.

Therefore,

(mod p)

[since gcd(p, (p − 1)!) = 1]

(mod p)

It follows that a^{p} ≡ a (mod p)

• This is true even if gcd(p, a) ≠ 1; i.e., if p | a

Why is this being taught in a CS course?

**Private Key Crypto graphy **

Alice (aka A) wants to send an encrypted message to Bob

(aka B).

• A and B might share a private key known only to

them.

• The same key serves for encryption and decryption.

• Example: Caesar’s cipher f(m) = m + 3 mod 26

(shift each letter by three)

o WKH EXWOHU GLG LW

o THE BUTLER DID IT

This particular crypto system is very easy to solve

• Idea: look for common letters (E, A, T, S)

** One Time Pads**

Some private key systems are completely immune to cryptanalysis:

• A and B share the only two copies of a long list of

random integers s_{i} for i = 1, . . . ,N.

• A sends B the message encrypted as:

c_{i} = (m_{i} + s_{i}) mod 26

• B decrypts A’s message by computing c_{i}−s_{i} mod 26.

The good news: bulletproof cryptography

The bad news: horrible for e-commerce

• How do random users ex change the pad ?

**Public Key Cryptography**

Idea of public key cryptography (Diffie-Hellman)

• Everyone’s encryption scheme is posted publically

o e.g. in a “telephone book”

• If A wants to send an encoded message to B, she looks

up B’s public key (i.e., B’s encryption algorithm) in

the telephone book

• But only B has the decryption key corresponding to

his public key

BIG advantage: A need not know nor trust B.

There seems to be a problem though:

• If we publish the encryption key, won’t everyone be

able to decrypt?

Key observation: decrypting might be too hard, unless

you know the key

• Computing f^{ -1} could be much harder than computing

f

Now the problem is to find an appropriate (f, f^{ -1}) pair

for which this is true

• Number theory to the rescue

**RSA: Key Generation**

Generating encryption/decryption keys

• Choose two very large (hundreds of digits) primes p, q.

o This is done using probabilistic primality testing

o Choose a random large number and check if it is

prime

o By the prime number theorem, there are lots of

primes out there

• Let n = pq.

• Choose e ∈ N relatively prime to (p − 1)(q − 1).

Here’s how:

o Choose
prime and about

o One must be relatively prime to (p − 1)(q − 1)

* Otherwise
| (p − 1)(q − 1)

Find out which one using Euclid’s algorithm

• Compute d, the inverse of e modulo (p − 1)(q − 1).

o Can do this using using Euclidean algorithm

• Publish n and e (that’s your public key)

• Keep the decryption key d to yourself.

**RSA: Sending encrypted messages**

How does someone send you a message?

• The message is divided into blocks each represented

as a numberM between 0 and n. To encryptM, send

C = M^{e} mod n.

Need to use fast exponentiation (2 log (n) multiplications)

to do this efficiently

**Example:** Encrypt “stop” using e = 13 and n = 2537:

• s t o p
18 19 14 15 $ 1819 1415

• 1819^{13} mod 2537 = 2081 and

1415^{13} mod 2537 = 2182 so

• 2081 2182 is the encrypted message.

• We did not need to know p = 43, q = 59 for that.