Decrypt the following ciphertext that is encrypted using RSA:

5433065902986267632605533071412313607849042001231487725752160944543337634764776942780551811154931702225666567112761402854245945771790200374756020087742730448029511549378258035341909089954945069377423917666095579241594583655805469852654975413725915810650231239021446353034249591165382217733674640

RSA public key (N, e):

N =

9443933355875323479428701223436866003317020345062337184168866482442741746051755875714077225424938697068202237079691276886895796347334130227954217861122456746475811995655599937678751969288324093545863325957721247606698180886906068377558846502707583137394885329858060292972366775543495590847656457

e = 65537

Hint.

• A modulus N of the standard RSA consists of only the two large prime p and q.

• But the modulus N in this assignment consists of many primes, which may weaken the security of RSA (so making this assignment practicable).

• Students can use the following website for integer factorization: https://www.alpertron.com.ar/ECM.HTM

• Refer to the provided example code (example.py).

# This is a Python 3 script
“””
egcd(): Extended Euclidean Algorithm
– inputs: positive integers x, y
– return: gcd(x,y), s, t, where gcd(x,y) = sx + ty
“””
def egcd(x, y):
# initialize s0, t0, s1, t1
old_s, old_t, s, t = 1, 0, 0, 1
while(y > 0):
q = x // y
r = x % y
x = y
y = r
old_s, s = s, old_s – (q*s)
old_t, t = t, old_t – (q*t)
return x, old_s, old_t
N = 9443933355875323479428701223436866003317020345062337184168866482442741746051755875714077225424938697068202237079691276886895796347334130227954217861122456746475811995655599937678751969288324093545863325957721247606698180886906068377558846502707583137394885329858060292972366775543495590847656457
e = 65537
# Q1. What are the factors of N?
# Q2. What is phi(N) (i.e., Euler’s totient)?
# phi =
# Q3. What is the private exponent d?
# _, s, _ = egcd(e, phi)
# d = s % phi
ciphertext = 5433065902986267632605533071412313607849042001231487725752160944543337634764776942780551811154931702225666567112761402854245945771790200374756020087742730448029511549378258035341909089954945069377423917666095579241594583655805469852654975413725915810650231239021446353034249591165382217733674640
#decrypted = pow(ciphertext, d, N)
#print(“decrypted message (ascii decoding): “, bytearray.fromhex(hex(decrypted)[2:]).decode())

CSCI4621/5621: Intro to Cyber Security

Spring 2021 Assignment # 2 (10 points)

DUE April 16, 2021 @ 11:59pm

Decrypt the following ciphertext that is encrypted using RSA:

543306590298626763260553307141231360784904200123148772575216094454333763476

477694278055181115493170222566656711276140285424594577179020037475602008774

273044802951154937825803534190908995494506937742391766609557924159458365580

5469852654975413725915810650231239021446353034249591165382217733674640

RSA public key (N, e):

N =

944393335587532347942870122343686600331702034506233718416886648244274174605

175587571407722542493869706820223707969127688689579634733413022795421786112

245674647581199565559993767875196928832409354586332595772124760669818088690

6068377558846502707583137394885329858060292972366775543495590847656457

e = 65537

Hint.

• A modulus N of the standard RSA consists of only the two large prime p and q.

• But the modulus N in this assignment consists of many primes, which may weaken
the security of RSA (so making this assignment practicable).

• Students can use the following website for integer factorization:
https://www.alpertron.com.ar/ECM.HTM

• Refer to the provided example code (example.py).

Submission guideline

Students will need to submit a PDF file on Moodle containing the following information:

• All the prime factors of N

• Euler’s totient ø(N)
• Private key d

• Decrypted message

https://www.alpertron.com.ar/ECM.HTM

“RSA”