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