CSIT 5710 Problem Set 2
CSIT 5710 Problem Set 2: Public-Key Cryptography
Due Date: May 10, 11:59pm
Submit your answers via Canvas
Problem 1: Repeated Squaring (15pts)
Calculate 5
532
mod 36 using the efficient modular exponentiation approach based on repeated
squaring that we discussed in class. Show all intermediate steps of your computation.
Problem 2: Factoring (16pts)
Letp,q,r, andr
′
be distinct large primes. ESpeciallyp,qaresafe primes, i.e, there exist two
other primesp
′
, q
′
such thatp= 2p
′
+ 1 andq= 2q
′
+ 1. LetN
1
=pqr,N
2
=pqr
′
,N
3
=pq. Assume
that there doesnotexist an efficient (probabilistic polynomial time) factoring algorithm that can
factor theseN
1
, N
2
, N
3
in practice. Say whether each of the following statements are TRUE or
FALSE, and justify your answer with one sentence.
(a) (3pts)There is an efficient algorithm that takesN
1
as input and outputsr.
(b) (3pts)There is an efficient algorithm that takesN
1
andN
2
as input and outputsr.
(c) (3pts)There is an efficient algorithm that takesN
1
andN
2
as input and outputsq.
(d) (3pts)There is an efficient algorithm that takesN
3
andφ(N
3
) as input and outputsq.
Problem 3: Collision-Resistant Hashing from RSA (25pts)
LetN=pqbe an RSA modulus and takee∈Nto be a prime that is also relatively prime to
φ(N). Letu
$
←Z
∗
N
, and define the hash function
H
N,e,u
:Z
∗
N
×{0, . . . , e−1}→Z
∗
N
whereH
N,e,u
(x, y) =x
e
u
y
∈Z
∗
N
.
In this problem, we will show that under the RSA assumption,H
N,e,u
defined above is collision-
resistant. Namely, suppose there is an efficient adversaryAthat takes as input (N, e, u) and outputs
(x
1
, y
1
)̸= (x
2
, y
2
) such thatH
N,e,u
(x
1
, y
1
) =H
N,e,u
(x
2
, y
2
). We will useAto construct an efficient
adversaryBthat takes as input (N, e, u) whereu
$
←Z
∗
N
and outputsxsuch thatx
e
=u∈Z
∗
N
.
(a) (10pts)Show that using algorithmAdefined above, algorithmBcan efficiently compute
a∈Z
N
andb∈Zsuch thata
e
=u
b
(modN) and 0̸=|b|< e. Remember to argue why any
inverses you compute will exist.
(b) (15pts)Use the above relation to show howBcanefficientlycomputex∈Z
N
such thatx
e
=u.
Note thatBdoesnotknow the factorization ofN, soBcannot computeb
−1
(modφ(N)).
Hint:What is gcd(b, e)?
1
CSIT 5710 Problem Set 2
Problem 4: RSA system with lost keys (24pts)
Bob generates his RSA modulusNusing two safe primesp, qand generates his RSA signature key
by settinge= 17 andd=e
−1
modφ(N). However, he lost his trapdoor (p, q, φ(N)) and only
remembers (N, d, e). Bob wants to generate a new key paird
′
withe
′
= 3. Please write a program
to findd
′
for Bob with the following parameters. In your answer writed
′
and include your code.
N=120602310321771355340273775538196643691740564098885912086710043456626057852782
0376179271770418007333028084125971523178481958153414948933557138178391044420486098721
1293688819463712469576725279610595379182525456612086545826036873428434326463744453411
9445487988350740954146961632821414435356232236600606576131241.
d=99319549676752880868460756325573706569668699846141339365525918140750871172879325
0971164987403064862493716339035372029338083185165252062929407911616154228454491619224
2116753773029944596240878790598973063695573110675034972940491888847065957229606309620
1954550469273953893150105313819181367554895947881968977417.
2
