Public-Key Cryptography - A Classical Introduction to Cryptography: Applications for Communications Security - page 245

Here is the list of reductions that we have proven.

EGDP ⇐ EGKRP

DHP ⇐ DLP

Note that we have variants of the ElGamal encryption with the exclusive or ⊕

( y r mod p ). This is typically
used when adopting the ElGamal encryption over elliptic curves.

instead of the multiplication for v : we can define v = m ⊕

9.5 Exercises

Exercise 9.1. Let N = pq be the product of two odd primes p and q such that 3 divides

ϕ ( N ) .

1. Under which condition on p mod 3 and q mod 3 does 3 divide ( N ) ?

2. We call cubic residue modulo N an element x of Z N such that there exists y
such that x

ϕ

y 3 (mod N ) . Let CR N denote the set of all cubic residues modulo

≡

N.

Given a cubic residue x ∈ CR N , how many cubic roots of x do we have

when p ≡ 1 (mod 3) and q ≡ 2 (mod 3) ? How many cubic roots do we have

when p 1 (mod 3) ?

Let y be one cubic root of x. We pick z uniformly at random in the set of all
cubic roots of x. Show how y

≡ q ≡

− z may lead to the factorization of N? What is

the probability?
3. Let us assume that we have an oracle which for any x

CR N outputs one cubic
root. Show that we can use it in order to factorize N in polynomial time in log N.
Deduce that computing cubic roots modulo N is equivalent to factorizing N
when 3 divides

∈

ϕ ( N ) .

Exercise 9.2 (Common modulus). Let us assume that A and B use RSA public keys
with the same modulus N but different exponents e 1 and e 2 .

Prove that A can decrypt messages sent to B.

Prove that C can decrypt a message sent to A and B provided that gcd ( e 1 , e 2 ) = 1 . 10

Exercise 9.3. We want to set up the RSA cryptosystem in a network of n users. How
many prime numbers do we have to generate?

We want to reduce this number by generating a smaller pool of prime numbers and
making combinations of two of these primes: for each user, we pick a new pair of two
of these primes in order to set up his key. Show how one user can factorize the modulus
of some other user.

10

This exercise was inspired by Ref. [172].