Table of contents
This challenge follows the principle of its predecessor AdveRSArial Crypto (Baby) (check it before if you haven’t already), we still have a sparse key (with a low number of ones in its binary representation, i.e., a low Hamming weight) but now on 2048 bits and with more collisions (explained below).
We know that the key is sparse because the descrition of the challenge suggests it and we can simply check that by observing that the Hamming weight on $n$ is only 82 (which is very low for a 2048-bit number):
>>> n = 32317006071311007300714876688669951960444102669715484116646415746394635540935921521724498858714153019942728273207389351392489359055364847068112159175081645180751388138858639873796530441238955101568733568176426113140426646976937052525918530731769533330028543775101205176486450544323218351858348091394877603920443607214945787590258064663918917740728042628406529049644873974905470262922605695823668958842546472908325174694333334844222696779786423580284135591089906934014814106737656354549850191740172203279085863986305338341130808123659535483768004216490879857791785965848808238698345641038729244197829259714168491081729
>>> bin(n)
'0b100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000010000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000010000000100000000000000000000000000000000000000000000000000000000000000000000100000001000000000000000000000000000000000000000100000000000000000000000000000000000000000001000000000000000000000000000000001000001000011000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000010001000000000000000000000000000000000010000000010000000000000000000000000000010000110100010100000000000000000000000010000000000000000010000000100000000000000001000010000000000000100010101000000000000000100000100000000000000000000000000000000000000000000000001000000000100000001000000000000000000000000001000000000000000000000000000000000000000000000000000100000001000000000000000000000000100001000000000000000000000000000000001000011000000010000000000000000000000000000100000100000001000000000000000000000000000000000000000000110001001000000001000000000000000000000000011000010000000000000000000000000000000000001000010000000010000000000000000000000000000000010000000000100000000000000000000000000000000000000000100000000000000000000000000000000000001000001000100000000000000000000000000000000000000000000001000000000000000000000000000000000000000000010000000000000000000000000000000100000000000000000000000000000000000000100001100000000000010000000000000000000000000000000000000100000000000000000000000000000000000000000001000100000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001'
>>> sum([int(b) for b in bin(n)[2:]])
82
The weakness
The fact is that if the key $n = p\times q$ is sparse then $p$ and $q$ are sparse too, because if we note $hw(n)$ the Hamming weight of $n$ then we have $hw(n) <= hw(p)\times hw(q)$. Then from each bits of $n$ we can deduce a few possible bits from $p$ or $q$ and then we try combinations from the possible bits we found.
For example
Let’s take $3\times 40 = 120$,
We have 3 = 0b0011, 40 = 0b101000 both of Hamming weight equal to 2, and 120 = 0b1111000.
We observe that $hw(120) = 2\times 2 = 4$, and if we go deeper in the analysis of this simple product we have :
- $40 = 2^5 + 2^3$,
- $3 = 2^0 + 2^1$, and
- $120 = 2^6 + 2^5 + 2^4 + 2^3 = 2^{5+1} + 2^{5+0} + 2^{3+1} + 2^{3+0}$.
As you can see, the exponents in the decomposition (that are also the position of the bits at one) of 120 are exactly the sums of the exponent of 40 and 3 but this is the easy case…
Another example
- $3\times 12 = 36,$
- $3 = 2^1 + 2^0,$
- $12 = 2^3 + 2^2,$
- $36 = (2^1 + 2^0)(2^3 + 2^2) = 2^{2+0} + 2^{3+0} + 2^{3+1} + 2^{2+1} = 2^{2+0} + 2\times 2^3 + 2^4 = 2^{2+0} + 2^4 + 2^4 = 2^5 + 2^2$.
You can see that the term $2^5$ has been generated from two $2^3$ and one $2^4$ and that’s what I called a collision earlier(here it’s even a double collision as two $2^3$ merged and then the result merged with another $2^4$ to produce the $2^5$).
Solving the challenge
We need to get the list of the positions of the bits at one:
n = 32317006071311007300714876688669951960444102669715484116646415746394635540935921521724498858714153019942728273207389351392489359055364847068112159175081645180751388138858639873796530441238955101568733568176426113140426646976937052525918530731769533330028543775101205176486450544323218351858348091394877603920443607214945787590258064663918917740728042628406529049644873974905470262922605695823668958842546472908325174694333334844222696779786423580284135591089906934014814106737656354549850191740172203279085863986305338341130808123659535483768004216490879857791785965848808238698345641038729244197829259714168491081729
def binary_position(n):
binary = bin(n)[2:]
bit_positions = []
for i in range(len(binary)):
if binary[-i-1] == '1':
bit_positions.append(i)
return bit_positions
print(binary_position(n))
It gives:
[0, 172, 267, 353, 357, 401, 439, 452, 453, 458, 497, 529, 573, 620, 624, 630, 668, 710, 721, 754, 763, 768, 805, 810, 811, 837, 846, 849, 853, 854, 897, 905, 911, 940, 948, 949, 954, 987, 992, 1017, 1025, 1077, 1104, 1112, 1122, 1172, 1178, 1194, 1196, 1198, 1202, 1216, 1221, 1238, 1246, 1264, 1289, 1291, 1295, 1297, 1298, 1303, 1333, 1342, 1377, 1381, 1425, 1476, 1477, 1482, 1488, 1521, 1565, 1605, 1613, 1682, 1690, 1744, 1792, 1861, 1870, 2048]
The ideas of the attack:
- As the two factor are prime, they are also odd so $2^0$ is in both decomposition and these two $2^0$ are the cause of the presence of all the terms from the decomposition of $p$ and $q$ but possibly $+1$ or $+2$ or even $+3$ (if multiple collisions happen) in the decomposition of $n$. And to assess if a term from $n$ (or the term $-1$, $-2$ or $-3$ in cases of collisions) is probably in $p$ or $q$ we count if, when adding it with another potential term of $p$ or $q$, it gives some terms of $n$ more than 9 times. Why 9? Because $hw(n) = 82$ so $82 \leq hw(p)\times hw(q)$ and then we reasonably assume that $hw(p)$ and $hw(q)$ are greater or equal to 9.
Necessary lib:
from Crypto.Util.number import *
from itertools import combinations
Looking for candidate terms of a factor:
def check_sums(bit_positions):
#count will keep the count of the participation of each bit in the production of the bits of n
count = [0]*2048
l = len(bit_positions)
for i in range(1, l):
for j in range(i+1, l):
x = bit_positions[i]
y = bit_positions[j]
#if 2^(x + y) is in the binary representation of n increase their counter
if x + y in bit_positions:
count[x] +=1
count[y] +=1
y -=1
if x + y in bit_positions:
count[x] +=1
count[y] +=1
x -=1
if x + y in bit_positions:
count[x] +=1
count[y] +=1
x -=1
if x + y in bit_positions:
count[x] +=1
count[y] +=1
y -=1
if x + y in bit_positions:
count[x] +=1
count[y] +=1
x -=1
if x + y in bit_positions:
count[x] +=1
count[y] +=1
lst = []
for i,c in enumerate(count):
if c > 9 :
lst.append(i)
return lst
Then from the produced list of potential terms we try all the combinations until it divides n:
def check_divisibility(x, lst):
n = len(lst)
i = 8
while i <= n:
for comb in combinations(lst, i):
prod = 1
for j in comb:
prod += 2**j
if x % prod == 0 and prod != 1:
print("gg")
return prod
i += 1
print(i)
print("No combination divides", x)
bit_positions = binary_position(n)
l= check_sums(bit_positions)
print(l)
p = check_divisibility(n, l)
# p = 179769313486231590772930519078902473361797697894230657508956426983270756750641042203250349075618771236153547580726603916895893944444813538033577585678487280125223971579128535422517006226698354463073263231618819178369912979902740062477559652404959229975372598382213816270253945896540199960864997790157857882113
Finally a classic RSA decryption:
c = 0x00bae65fbca88fea74202821d1773fa90e1a6e3532b3e60f1516ad8e04c84c1c42b733206d5b10bfeada9facd35adc426234b31183398adc4d0e842a3a2d09756f9e0bcdfdfe5b553dab4b21ea602eba4dc7db589f69360e1a598048ea0b719e7ab3ca25dec80acdaec582140877da1ce4c912425c43b1e19757309c2383b3b48ebbfcdac5bddfa167bbf1f7a31ec2a7758a52579956600306ca0dab86d5b37d3a7dfc9429a757f978905c01e46bd6d7c32f314a5916107545ad1cb17d76962b4ac11bbb6020a3ff0175d72081cc47cfd486ff05ed8799e2dd0991ce7b4f4ba2f2eae9dbddecc43e9d7a3899f6b493a839d5be7f9fe856fbe238e10047a7ad2945
e = 65537
q = n//p
phi = (p-1)*(q-1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))