Cryptography Reference
In-Depth Information
Show how anyone can factorize all moduli for which at least one prime factor has
been used in at least one other modulus.
Exercise 9.4 (Small exponent and known variations).
Let us assume that e
3
and
that we obtain the encryption of two unknown messages x
1
and x
2
for which we know
that x
2
−
=
x
1
=
δ
. Show that we can decrypt both messages by solving polynomial
equations.
P
(
x
1
)
where P
(
X
)
is a polynomial of low degree.
11
Extend this attack for x
2
=
Exercise 9.5 (Rabin cryptosystem).
Let us consider the following cryptosystem.
Setup:
find two prime numbers p and q, set N
=
pq, and pick a random B
∈
Z
N
Messages:
x
∈
Z
N
Public key:
B
,
N
Secret key:
B
,
p
,
q
Encryption:
E
(
x
)
B
) mod
N
Decryption:
D
(
y
)
is one of the four square roots of
=
x
(
x
+
B
2
B
2
4
+
y minus
Explain how we can compute the square roots in
Z
N
.
Show that we can make decryption deterministic by adding redundancy in the
plaintexts.
Show that the cryptosystem can be broken by a chosen ciphertext attack.
Show that the ability to decrypt is equivalent to the ability to factorize N.
12
Exercise 9.6.
Let p be a prime number such that p
≡
3 (mod 4)
. Let g be a generator
of
Z
p
. Given y
g
x
mod
p (with x unknown), how can we efficiently compute the
parity bit x
mod 2
of x?
=
Show that if y is a quadratic residue modulo p, then y
p
+
1
4
mod
p is a square root
of y. What is the link between the discrete logarithm of y and the discrete logarithm of
y
p
+
1
mod
p?
4
g
x
We assume that we are given an oracle
O
which for any y
=
mod
p outputs
x
the second parity bit
mod 2
of the logarithm of y. Show how to efficiently compute
discrete logarithms by using
2
O
.
3 (mod 4)
, computing the second parity bit of the discrete
logarithm is polynomially equivalent to computing the discrete logarithm in terms of
complexity.
Deduce that for p
≡
11
This exercise was inspired by Ref. [50].
12
This exercise was inspired by Ref. [153].
Search WWH ::
Custom Search