Cryptography Reference
In-Depth Information
1. Obtain an authentic copy of Alice's public key (
N,e
). This step may require trusted
third parties and public key infrastructures, which are outside the scope of this topic;
see Chapter 11 of Smart [
513
] or Chapter 11 of Stinson [
532
]. We suppress this issue in
this topic.
2. Encode the message as an integer 1
m
<N
.
Note that
m
does not necessarily lie in (
≤
≈
√
N
then the
)
∗
. However, if
p
,q
Z
/N
Z
2
/
√
N
. Hence, in practice
probability that gcd(
m
,N
)
>
1is(
p
+
q
−
1)
/
(
N
−
1)
≈
)
∗
.
1
3. Compute and transmit the
ciphertext
one may assume that
m
∈
(
Z
/N
Z
m
e
(mod
N
)
.
=
c
To
decrypt
the ciphertext, Alice computes
m
=
c
d
(mod
N
) and decodes this to obtain the
original message.
1 then (
m
e
)
d
Exercise 1.2.1
Show that if gcd(
m
,N
)
=
≡
m
(mod
N
). Show that if
1 then (
m
e
)
d
gcd(
m
,N
)
=
≡
m
(mod
N
).
The RSA system can also be used as a digital signature algorithm. When sending a
message
m
to Bob, Alice computes the signature
s
m
d
(mod
N
). When Bob receives
(
m
,
s
) he obtains an authentic copy of Alice's public key and then verifies that
m
=
≡
s
e
(mod
N
). If the verification equation holds then Bob believes that the message
m
does
come from Alice. The value
m
is not usually an actual message or document (which might
be huge) but a short integer that is the output of some (non-injective) compression function
(such as a hash function). We sometimes call
m
a
message digest
.
The idea is that exponentiation to the power
e
modulo
N
is a
one-way function
:a
function that is easy to compute but such that it is hard to compute preimages. Indeed,
exponentiation modulo
N
is a
one-way permutation
on (
)
∗
when
e
is co-prime to
ϕ
(
N
). The private key
d
allows the permutation to be efficiently inverted and is known as
a
trapdoor
. Therefore, RSA is often described as a
trapdoor one-way permutation
.
A number of practical issues must be considered:
Z
/N
Z
1. Can public keys be efficiently generated?
2. Is the cryptosystem efficient in the sense of computation time and ciphertext size?
3. How does Bob know that Alice's public key is authentic?
4. Is the scheme secure?
5. What does “security” mean anyway?
One aim of this topic is to explore the above issues in depth. We will study RSA (and some
other cryptosystems based on integer factorisation) as well as cryptosystems based on the
discrete logarithm problem.
1
If
N
is a product of two 150 digit primes (which is the minimum size for an RSA modulus) then the expected number of trials
to find 1
≤
m
<N
with gcd(
m
,N
)
>
1 is therefore
≈
10
150
. Note that the age of the universe is believed to be less than 10
18
seconds.
