Assignment 3
Question 1 - Textbook RSA
a) Given:
N = 68292993516845601180026039012
e = 288546253195154448765672969661
Find d.
752304375247267 × 907784080006169 (2 distinct prime factors of N)
Use EEA to find d.
Code:
def find_d(e, phi_N):
pre_r, r = e, phi_N
pre_s, s = 1, 0
pre_t, t = 0, 1
print(f"{'Step':>5} {'Quotient':>30} {'Remainder (r)':>30} {'Coefficient
(s)':>35} {'Coefficient (t)':>35}")
print("-" * 140)
step = 0
while r != 0:
quotient = pre_r // r
pre_r, r = r, pre_r - quotient * r
pre_s, s = s, pre_s - quotient * s
pre_t, t = t, pre_t - quotient * t
step += 1
print(f"{step:>5} {quotient:>30} {r:>30} {s:>35} {t:>35}")
print("\nThe modular inverse d is:", pre_s % phi_N)
return pre_s % phi_N
# Prime factors of N - p, q
p = 752304375247267
q = 907784080006169
# public exponent
e = 288546253195154448765672969661
# Compute phi(N)
phi_N = (p - 1) * (q - 1)
d = find_d(e, phi_N)
# Check my answer
d_verified = pow(e, -1, phi_N)
print(f"Verified d: {d_verified}")
From the code, d = 613.
b) N = pq
φ(N) = (p-1)(q-1)
= pq - p - q + 1
=N-p-q+1
p + q = N - φ(N) + 1
Let p + q = S
we can express q as q=S−p
Substituting this into N = pq gives us a quadratic equation in terms of p
p(S - p) = N
pS - p2 = N
p2 - Sp + N = 0
This is a standard quadratic equation in the form ax2 + bx + c = 0, where a = 1, b = -S, and c = N. We can
solve this using the quadratic formula.
c) c = me mod N = 19700101
d) c = me mod N = 1000200030004000500060007000800090000
Question 2:
The final output is 01010110 10101110 01100110 10100110 01011011 (56 ae 66 a6 5b)
Code:
import hashlib
def compute_MGF1(mgf_seed, mask_length):
# Convert mgf_seed from decimal to binary, assuming 16 bits
mgf_seed_binary = format(mgf_seed, '016b')
# Initialize
mask_T = ''
counter = 0
algorithm_trace = []
# Continue until we have the required number of bits in the mask
while len(mask_T.replace(' ', '')) < mask_length * 8: # 8 bits per byte
# Convert counter to a 32-bit
counter_binary = format(counter, '032b')
# Combine the mgf_seed and counter and encode to bytes for hashing
to_hash = (mgf_seed_binary + counter_binary).encode('utf-8')
# Compute the hash and add the result to the mask
blake2b_hash = hashlib.blake2b(to_hash, digest_size=32).hexdigest()
mask_T += blake2b_hash[:mask_length * 2] # Two hex chars per byte
algorithm_trace.append({
'counter': counter,
'mgf_seed|counter': mgf_seed_binary + ' ' + counter_binary,
'hash': blake2b_hash,
'mask_T': mask_T
})
counter += 1
# Cut the mask into chunks and truncate to the ideal length
mask_T = ' '.join([mask_T[i:i+2] for i in range(0, mask_length * 2, 2)])
return mask_T, algorithm_trace
final_output, trace_of_algorithm = compute_MGF1(1544, 5)
print('Final output mask:', final_output)
print('Trace of algorithm:')
for step in trace_of_algorithm:
print(f"Counter: {step['counter']}")
print(f"Seed|Counter: {step['mgf_seed|counter']}")
print(f"hash(seed|counter): {step['hash']}")
print(f"T <- T|hash: {step['mask_T']}\n")
