Cryptography Reference
In-Depth Information
2. Calculate
t
=
ϕ
(
n
) = (
p
- 1)(
q
- 1), which is the Euler totient of n.
3. Let
e
be a positive integer, greater than 1 and less than
t
, that is relative prime to t. Mathematically,
e
∈
,1
< e <
t, gcd(e, t) = 1. One way to do this, for example, is to make
e
also be prime.
4. Calculate
d
=
e
-1
in
t,
that is, such that
ed
= 1 (mod
t).
Now, these numbers we have calculated,
e
and
d,
have an interesting property. Assume we have a message,
M,
represented as an integer less than
n
. Here we derive that
M
ed
≡
M
de
≡
M
t
+
1
≡
M
1
≡
M
(mod
n
)
Why does this work? It's just using Euler's totient theorem (specifically, the last corollary). Here,
t
is the
totient of
n
, and we know that
ed
≡ 1 (mod
t
) from the construction of
e
and
d.
The last corollary from Euler's
theorem lets us state that
M
de
≡
M
1
(mod
n
)
The significance is that if we represent our message as an integer, then we can use
e
as an encryption expo-
nent, and
d
as a decrypting exponent, and have ciphertext
C
≡
M
e
(mod
n)
We will then be able to calculate back the plaintext
M
≡
C
d
≡
M
ed
(mod n)
The real slickness comes in the fact that we can have
anybody
know
e
and
n
, so that they can encrypt mes-
sages, but it is extremely difficult to compute
d
knowing these two numbers without being able to factor
n
. Most
proposed methods of breaking this algorithm simply involve factoring
n
to obtain
p
and
q,
so that the totient can
be calculated.
We now use the pair (
e, n
) as the public key and the pair (
d, n
) as a private key.
Let's do a quick example of some cryptography using RSA. Let's say
p
= 11 and
q
= 17, two prime numbers.
Inreal-lifescenarios,wewouldhavethesenumbersbehundredsofdigitslong;otherwise,factoringtheresultant
product would be very easy. For this case, we can see that
n
= 11 × 17 = 187, and
t
=
ϕ
(187) = 10 × 16 = 160.
Let's pick
e
to be a nice prime number, say, 3.
Now, we can calculate
d
= 3
-1
using the extended Euclidean algorithm from before, getting the result
d
=
107.
Let'sencrypt ourmessage. Here,consider ourmessage tobeencoded asthenumber15(forexample, itcould
be the 15th letter of the Latin alphabet, O). It should be easy to see that 15
3
= 3, 375 ≡ 9 (mod 187), so that our
encrypted number is
C
= 9. Going the other way is a bit trickier. We don't really want to multiply 9 by itself 107
times. It turns out there is a shortcut, using the binary representation of 107, that is to say, representing 107 as
the sum of powers of 2. In binary, 107 is 1101011, meaning 107 = 2
6
+ 2
5
+ 2
3
+ 2
1
+ 2
0
= 64 + 32 + 8 + 2 + 1.
We can then write
9
107
≡ 9
64
+
32
+
8
+
2
+
1
(mod 187)
It's easy to see that 9
1
= 9, thus we have
9
107
≡ 9
64+32+8+2
× 9 (mod 187)
From the last equation, we know that 9
1
≡ 9 (mod 187), so then 9
2
≡ (9
1
) × (9
1
) ≡ 9 × 9 ≡ 81 (mod 187), and we
have
9
107
≡ 9
64+32+8
× 81 × 9 (mod 187)
Search WWH ::
Custom Search