Cryptography Reference
In-Depth Information
3. As we are going to see, a minimal security requirement for RSA is that the
modulus should be hard to factor. This is the reason why
Gen
RSA
is required
to return a modulus which is the product of two primes of (approximately) the
same length.
4. Observe that plain RSA satisfies the correctness condition (iv) in the definition of
public-key encryption scheme (Definition 8.2) as a consequence of Proposition
8.1, which shows that in plain RSA, decryption always recovers the encrypted
message.
0 and
a
m
Exercise 8.4
For a positive integer
n
,let
λ(
n
)
=
min
{
m
∈ Z|
m
>
≡
∈ Z
n
}
1
be the Carmichael function we mentioned in Remarks
8.5. Prove the following facts:
(i)
(
mod
n
)
for all
a
Z
n
and
λ(
n
)
is the maximum of all orders of elements of the group
λ(
n
)
|
φ(
n
)
.
(ii) If
n
(where lcm
denotes the least common multiple) so that in this case we have that
=
pq
is an RSA modulus, then
λ(
n
)
=
lcm
(
p
−
1
,
q
−
1
)
λ(
n
)<
φ(
n
)
.
(iii) If
(
n
,
e
)
is an RSA public key, then any positive integer
d
such that
ed
≡
1
may be used as the exponent for RSA decryption. In particular,
one may choose
d
equal to the inverse of
e
in
(
mod
λ(
n
))
Z
λ(
n
)
. Give an example where
Z
φ(
n
)
this inverse is smaller than the inverse of
e
in
.
Let us now analyze the security properties of plain RSA. We have:
Proposition 8.3
Under the RSA assumption, plain RSA is OW-CPA secure.
Proof
Suppose that plain RSA is not OW-CPA secure. Then, according to Defini-
tion 8.4, there exists a PPT adversary
PubK
ow-cpa
A
such that Pr
(
A
,
RSA
(
k
)
=
1
)
is non-
negligible. Thenwemay show that there exists a PPT adversary
B
that solves the RSA
problem with non-negligible probability, i.e., such that Pr
(
RSA
B
,
Gen
RSA
(
k
)
=
1
)
is
non-negligible.
B
is given
n
,
e
, and
y
, and it has to output
x
such that RSA
(
n
,
e
)
(
x
)
=
y
.
For this,
B
proceeds as follows:
•
After being given its input,
B
defines the public RSA key
pk
:=
(
n
,
e
)
and sets
c
:=
y
.
•
Then
B
runs
A
on input the public key
pk
and the challenge ciphertext
c
and
eventually
A
returns a message
m
∈ Z
n
.
•
Finally
B
returns
x
:=
m
.
succeeds in the
PubK
ow-cpa
Observe that if
A
A,
RSA
(
k
)
experiment, then
c
=
RSA
)
(
m
)
(
n
,
e
and hence also
y
=
RSA
)
(
x
)
, so that
B
succeeds in the RSA experiment
(
n
,
e
RSA
B,
Gen
RSA
(
k
)
. Since
A
succeeds with non-negligible probability, so does
B
,
breaking the RSA assumption.
It is easily seen that the argument above is reversible and hence the RSA assump-
tion is actually equivalent to one-wayness security of plain RSA. By Proposition
8.2, the RSA assumption implies the factoring assumption and hence the latter is
a necessary condition for plain RSA to be OW-CPA secure. However, as we have
