Cryptography Reference
In-Depth Information
24
The RSA and Rabin cryptosystems
The aim of this chapter is to briefly present some cryptosystems whose security is based
on computational assumptions related to the integer factorisation problem. In particular,
we study the RSA and Rabin cryptosystems. We also present some security arguments and
techniques for efficient implementation.
Throughout the chapter we take 3072 bits as the benchmark length for an RSA modulus.
We make the assumption that the cost of factoring a 3072-bit RSA modulus is 2
128
bit
operations. These figures should be used as a very rough guideline only.
24.1 The textbook RSA cryptosystem
Box
24.1
recalls the “textbook” RSA cryptosystem, which was already presented in Sec-
tion
1.2
. We remind the reader that the main application of RSA encryption is to transport
symmetric keys, rather than to encrypt actual documents. For digital signatures we always
sign a hash of the message, and it is necessary that the hash function used in signatures is
collision resistant.
In Section
1.3
we noted that the security parameter
κ
is not necessarily the same as the
bit-length of the RSA modulus. In this chapter it will be convenient to ignore this, and use
the symbol
κ
to denote the bit-length of an RSA modulus
N
. We always assume that
κ
is
even.
As we have seen in Section
1.2
certain security properties can only be satisfied if the
encryption process is randomised. Since the RSA encryption algorithm is deterministic
it follows that the message
m
used in RSA encryption should be obtained from some
randomised padding scheme
. For example, if
N
is a 3072-bit modulus then the “message”
itself may be a 256-bit AES key and may have 2815 random bits appended to it.
Exercise 24.1.1
Give a KeyGen algorithm that takes as input a security parameter
κ
(assumed to be even) and an
l
-bit string
u
(where
l<κ/
2) and outputs a
κ
-bit product
N
=
pq
of two
κ/
2-bit primes such that the
l
most significant bits of
N
are equal to
u
.In
particular, one can ensure that 2
κ
−
1
<N<
2
κ
and so
N
is a
κ
-bit integer.
Exercise 24.1.2
Let
N
. Prove that the Carmichael function
λ
(
N
) divides the Euler
function
ϕ
(
N
). Prove that RSA decryption does return the message.
∈ N
