5Modular arithmetic

IA Numbers and Sets

5.4 Public-key (asymmetric) cryptography

Tossing a coin over a phone

Suppose we have Alice and Bob who wish to toss a coin fairly over the phone.

Alice chooses two 100 digit primes with

p, q ≡

3 (

mod

4). Then she tells Bob the

product

n

=

pq

. Bob picks a number

u

coprime to

n

, computes

a ≡ u

2

(

mod n

)

and tells Alice the value of a.

Alice can compute the square roots of

a

by the above algorithm (

O

(

log n

)),

obtain ±u, ±v and tells Bob one of these pairs.

Now if Alice picks

±u

, Bob says “you win”. Otherwise, Bob says “you lose”.

Can Bob cheat? If he says “you lose” when Alice says

±u

, Bob must produce

the other pair

±v

, but he can’t know

±v

without factorizing

n

. (If he knows

±u

and

±v

, then

u

2

≡ v

2

(

mod n

), then

n |

(

u −v

)(

u

+

v

). But

n -

(

u −v

) and

n -

(

u

+

v

). So

p |

(

u −v

) and

q |

(

u

+

v

). Then

p

= (

n, u −v

) and

q

= (

n, u

+

v

)

which we can calculate efficiently by Euclid’s algorithm)

Thus cheating is as hard as prime factorization.

Note that a difficult part is to generate the 100-digit prime. While there are

sufficiently many primes to keep trying random numbers until we get one, we

need an efficient method to test whether a number is prime. We cannot do this

by factorization since it is slow. So we need an efficient prime-checking function.

We can test whether a large number is prime by doing Fermat-like checks.

We choose random numbers and take it to the (

p −

1)th power and see if they

become 1. If it is not 1, then it is definitely not a prime. If we do sufficiently

many tests that all result in 1, we can be sufficiently certain that it is a prime

(even though not with 100% certainty).

(Recent advancements in algorithms have found efficient ways of deterministic

prime test, but they are generally slower than the above algorithm and is not

widely used)

It is currently believed that it is hard to prime factorize a number, so this is

secure as far as we know.

RSA encryption

Theorem

(RSA Encryption)

.

We want people to be able to send a message to

Bob without Eve eavesdropping. So the message must be encrypted. We want

an algorithm that allows anyone to encrypt, but only Bob to decrypt (e.g. many

parties sending passwords with the bank).

Let us first agree to write messages as sequences of numbers, e.g. in ASCII

or UTF-8.

After encoding, the encryption part is often done with RSA encryption

(Rivest, Shamier, Adleman). Bob thinks of two large primes

p, q

. Let

n

=

pq

and pick

e

coprime to

φ

(

n

) = (

p −

1)(

q −

1). Then work out

d

with

de ≡

1

(mod φ(n)) (i.e. de = kφ(n) + 1). Bob then publishes the pair (n, e).

For Alice to encrypt a message, Alice splits the message into numbers

M < n

.

Alice sends M

e

(mod n) to Bob.

Bob then computes (

M

e

)

d

=

M

kφ(n)+1

≡ M

(

mod n

) by Fermat-Euler

theorem.

How can Eve find

M

? We can, of course, factorize

n

, find

d

efficiently, and

be in the same position as Bob. However, it is currently assumed that this is

hard. Is there any other way? Currently we do not know if RSA can be broken

without factorizing (cf. RSA problem).