248 15. A Glimpse of Complexity and Cryptography
e, herpublic key(the numberspandqshe may even forget; they will not
be needed to operate the system, just to set it up).
Suppose that Bob wants to send a message to Alice. He writes the mes-
sage as a numberx(we have seen before how to do this). This numberx
must be a non-negative integer less thanm(if the message is longer, he
can just break it up into smaller chunks).
The next step is the trickiest: Bob computes the remainder ofxemodulo
m. Since bothxandeare huge integers (200 digits), the numberxdhas
more than 10^200 digits; we could not even write it down, let alone compute
it! Luckily, we don’t have to compute this number, only its remainder when
dividing bym. This is still a large number, but at least it can be written
down in 2 or 3 lines.
So letrbe this remainder; this is sent to Alice. When she receives it,
she can decrypt it using her private keydby carrying out essentially the
same procedure as Bob did: She computes the remainder ofrdmodulom.
And—a black magic of number theory, until you see the explanations—this
remainder is just the plain textx.
What if Alice wants to send a message to Bob? He also needs to go
through the trouble of generating his private and public keys. He has to
pick two primesp′andq′, compute their productm′, select two positive
integersd′ande′such that (p′−1)(q′−1) is a divisor ofe′d′−1, and finally
publishm′ande′. Then Alice can send him a secure message.
The black math magic behind the protocol.The key fact from math-
ematics we use is Fermat’s Theorem, Theorem 6.5.1. Recall thatxis the
plain text (written as an integer) and the encrypted messageris the re-
mainder ofxemodulom. So we can write
r≡xe (modm).To decrypt, Alice raises this to thedth power to get
rd≡xed (modm).To be more precise, Alice computes the remainderx′ofrdmodulom, which
is the same as the remainder ofxedmodulom. We want to show that this
remainder is preciselyx. Since 0≤x<m, it suffices to argue thatxed−x
is divisible bym. Sincem=pqis the product of two distinct primes, it
suffices to prove thatxed−xis divisible by bothpandq.
Let us consider divisibility byp, for example. The main property ofe
anddis thated−1 is divisible by (p−1)(q−1), and hence also byp−1.
This means that we can writeed=(p−1)l+1, wherelis a positive integer.
We have
xed−x=x
(
x(p−1)l− 1)
.
Here x(p−1)l−1 is divisible by xp−^1 −1 (see Exercise 6.1.6), and so
x
(
x(p−1)l− 1)
is divisible byxp−x, which in turn is divisible bypby
Fermat’s Theorem.