Cryptography Reference
In-Depth Information
Give a reduction from STRONG-RSA to RSA. This shows that the STRONG-RSA problem
is not harder than the RSA problem.
5
Exercise 24.1.17
Let
N
pq
be an RSA modulus. Let
A
be an oracle that takes as input
an integer
a
and returns
a
(mod
ϕ
(
N
)). Show how to use
A
to factor
N
.
=
Exercise 24.1.18
Consider the following variant of RSA encryption. Alice has a public key
N
and two public exponents
e
1
,e
2
such that
e
1
=
e
2
and gcd(
e
i
,λ
(
N
))
=
1for
i
=
1
,
2. To
m
e
1
m
e
2
encrypt to Alice one is supposed to send
c
1
=
(mod
N
) and
c
2
=
(mod
N
). Show
that if gcd(
e
1
,e
2
)
=
1 then an attacker can determine the message given the public key and
a ciphertext (
c
1
,
c
2
).
Exercise 24.1.19
Consider the following signature scheme based on RSA. The public key is
an integer
N
1.
Theprivatekeyistheinverseof
e
modulo
λ
(
N
) as usual. Let
H
be a collision-resistant
hash function. The signature on a message
m
is an integer
s
such that
=
pq
, an integer
e
coprime to
λ
(
N
) and an integer
a
such that gcd(
a,N
)
=
s
e
a
H
(
m
)
≡
(mod
N
)
where
H
(
m
) is interpreted as an integer. Explain how the signer can generate signatures
efficiently. Find a known message attack on this system that allows an adversary to make
selective forgery of signatures.
24.2 The textbook Rabin cryptosystem
The textbook Rabin cryptosystem [
444
]isgiveninBox
24.2
. Rabin is essentially RSA
with the optimal choice of
e
, namely
e
2.
6
As we will see, the security of Rabin is more
closely related to factoring than RSA. We first have to deal with the problem that if
N
=
pq
where
p
and
q
are distinct primes then squaring is a four-to-one map (in general) so it is
necessary to have a rule to choose the correct solution in decryption.
=
Lemma 24.2.1
Suppose p and q are primes such that p
≡
q
≡
3(mod4)
. Let N
=
pq
and
1
<x<Nbe such that
(
N
)
=
1
. Then either x or N
−
x is a square modulo N.
Exercise 24.2.2
Prove Lemma
24.2.1
.
Definition 24.2.3
Let
p
≡
q
≡
3 (mod 4) be primes. Then
N
=
pq
is called a
Blum
integer
.
Note that, as with RSA, the value
m
in encryption is actually a symmetric key (passed
through a padding scheme) while in signing it is a hash of the message. The choice
5
The word “strong” is supposed to indicate that the
assumption
that STRONG-RSA is hard is a
stronger assumption
than the
assumption that RSA is hard. Of course, the computational problem is weaker than RSA, in the sense that it might be easier to
solve STRONG-RSA than RSA.
6
The original paper [
444
] proposed encryption as
E
N,b
(
x
)
=
x
(
x
+
b
)(mod
N
) for some integer
b
. However, there is a gain in
efficiency with no loss of security by taking
b
=
0.
