Tags: modulus rsa-crypto crypto rsa
Rating:
`p` and `q` are splitted into chunks of 2 bytes. Noticing that mod 65536^i gives us the possible last bytes of `p` and `q` with a relatively low false positive rate, we can reconstruct `p, q` starting from the least significant 2 bytes.
```python
N = 20258342755030699342765611614877226774887411463378181451840683524015047892651973850627359327237027774356720466793903228878105456871700095061940512708020098618057571729943083434709826167248620306311075548853347901271259447873417249634361203320669711383057513256692645763182907367630873827308387269636636289231405813338687900835089134983309705316926805886077666050520726687030034195743282451467528496315178642323807316904673350899061558504836111406826196935670026969650853021793806021689762347770412960223358347923518483267323592429810806182091459339480461991545802571444958728299104188325433443437138511489545219679697
c = 7123414739023542748810203483709689015408917851116023820618517477707107834968496358236168325897320226453721626392832959216652528045703210750125701176032827942299755718368878395927764432908785593372611140758024558283573960529417102003625606595077755879081211049268879243499173403440059239858308427266558935817943602623773418104985260309484175243613311427707700872120183486969325635776183186398996045018265812500716946531309303922788481972201938026485853049867490332841823037660486595790337519475108241096821738281828388702502632013367441754603384687444518555226345985885414563346111755133096794599057161802602344386709
p_splitted = [1648, 26443, 23758, 59540, 54722, 64595, 54876, 56461, 37559, 58038, 62190, 48794, 3685, 15347, 37807, 65456, 27238, 43839, 27847, 38403, 26704, 6902, 13361, 48888, 40733, 30039, 2759, 31739, 10053, 15206, 32185, 8727, 53066, 51903, 33778, 57075, 7384, 34279, 55988, 26971, 15381, 10770, 14264, 30253, 11971, 50652, 14420, 7242, 54046, 21582, 26535, 42340, 43335, 52478, 60716, 21061, 2633, 24288, 44532, 50813, 49308, 30582, 3906, 4989]
q_splitted = [17900, 40783, 35173, 58646, 30439, 8839, 14895, 33243, 40515, 60827, 39626, 23436, 11739, 48698, 26830, 44120, 9651, 38993, 3295, 4606, 57793, 57260, 63312, 38766, 33916, 15401, 37856, 21410, 23082, 4751, 12279, 60843, 26791, 61740, 8570, 31666, 55249, 23535, 64786, 26597, 3997, 60330, 28810, 21136, 20487, 55594, 10618, 34867, 55177, 33728, 60147, 62991, 36041, 50205, 44371, 40864, 36657, 32481, 5885, 12358, 6736, 8984, 5618, 27045]
def find_nexts(p_lsb, q_lsb):
new_mod = mod * (2**16)
pairs = []
for p_s in p_splitted:
for q_s in q_splitted:
p_next = (p_lsb + p_s * mod)
q_next = (q_lsb + q_s * mod)
if (N - p_next * q_next) % new_mod == 0:
print(p_s, q_s)
pairs.append((p_s, q_s))
return pairs
p_lsb = 0
q_lsb = 0
mod = 1
l = len(p_splitted)
for _ in range(l):
pairs = find_nexts(p_lsb, q_lsb)
print(pairs)
assert len(pairs) > 0
idx = 0
if len(pairs) > 1 and pairs[1][0] == 44532:
idx = 1
p_lsb += pairs[idx][0] * mod
q_lsb += pairs[idx][1] * mod
mod *= 2**16
p_splitted.remove(pairs[idx][0])
q_splitted.remove(pairs[idx][1])
assert p_lsb * q_lsb == N
print(f'p = {p_lsb}')
print(f'q = {q_lsb}')
d = pow(e, -1, (p_lsb-1)*(q_lsb-1))
m = pow(c, d, N)
print(m.to_bytes((m.bit_length() + 7) // 8, 'big'))
```
