Cryptography Reference
In-Depth Information
Even though we don't have a 9
4
term, we will go ahead and calculate the value for it anyway, by taking 9
4
= 9
2
× 9
2
≡ 81 × 81 ≡ 16 (mod 187). Repeating again, we know that 9
8
= 9
4
× 9
4
≡ 16 × 16 ≡ 69 (mod 187). So far,
we then have
9
107
≡ 9
64+32
× 69 × 81 × 9 (mod 187)
Repeating again, we have 9
16
= 9
8
× 9
8
≡ 69× 69≡ 86(mod 187).But we have no9
16
term, sowe repeat, getting
9
32
= 9
16
× 9
16
≡ 86 × 86 ≡ 103 (mod 187). We then have, so far
9
107
≡ 9
64
× 103 × 69 × 81 × 9 (mod 187)
Finally, we can calculate 9
64
= 9
32
× 9
32
≡ 103 × 103 ≡ 137 (mod 187), giving us
9
107
≡ 137 × 103 × 69 × 81 × 9 (mod 187)
Not much of a shortcut is left here, so we just multiply it out and take the remainder, with the result:
9
107
≡ 137 × 103 × 69 × 81 × 9 ≡ 15 (mod 187)
Therefore, the decryption worked, since
C
d
≡
M
≡ 15 (mod 187).
2.5 Discrete Logarithm-Based
Cryptography
From high school mathematics, we might recall that a normal logarithm takes an exponential and “reverses” it,
so that if we know that 10
x
= 100, then we can take the logarithm of both sides to know that
x
= log 100.
The
discrete logarithm
has the exact same goal, except instead of acting on continuous numbers, such as
the reals or the complex numbers, we are concerned with solving algebraic equations of the form
a
x
=
b
where
a
and
b
are known elements of a finite field
F
(instead of or ), with
a
x
representing
a
operating on
itself
x
times with the field operation. Solving for
x
is known as “calculating the discrete logarithm”.
Another difference between the continuous and the discrete logarithm is that there are known, simple for-
mulas to compute arbitrary logarithms of real-valued or complex-valued numbers. There is currently no known
way to easily solve the discrete logarithm problem for
x
even if
a
and
b
are known. In fact, the difficulty of
this problem is such that many cryptosystems rely on the difficulty of calculating discrete logarithms for their
security.
2.5.1 The Diffie-Hellman Algorithm
Probably one of the simplest and most widely used cryptosystems that relies on the discrete logarithm being
hard is the
Diffie-Hellman Key Exchange Protocol.
Keyexchange algorithms, ingeneral, sufferfromafatal flaw.Ifwehaveafoolproof,secure waytoexchange
a key between two users, then why not just exchange the message we want to send through this channel?
Normally, this is simply because the key is a small, fixed-size object, and only has to be exchanged once. But
any messages may not have these properties.
Search WWH ::
Custom Search