# Omni Crypto

* classic RSA,
* given N, e = 65537, cipher
* but broken prime generator

## Prime generator

* size 1024 bit per prime
* split into 3 parts,
`len(middle) = random(16,504)`
`len(first) = random(8,middle)`
* first and third part of p,q are the same !!

* $p = c|x|d = c\cdot 2^* + d + x\cdot 2^{**}$
* $q = c|y|d = c\cdot 2^* + d + y\cdot 2^{**}$

## Solution

* use Coppersmith https://doi.org/10.1007%2F3-540-68339-9_14 (2nd part of paper)
* if we know half the bits of p, we can get everything
* brute-force, where the split happened (< 125.000 cases)
* better: assume unknown part is maximal, and just try `len(first)` (<500 cases)
### upper bits:
* playing around with formulas, to find out how many valid bits we get from $n$
* $n = (c\cdot 2^r+x)(c\cdot 2^r+y)$
* $n >> 2048 - r = c^2 >> r$
* because everything else is too small
* so we get `len(first)` bits,
* via bisection

### lower bits
* Hensel-Lifting (or something the like)
* determine one bit after the other, starting at lowest
* $n = (x\cdot 2^s+d)(y\cdot 2^s+d)$
* $n \bmod 2^s = d^2 \bmod 2^s$
* mod 8 we have solution 1,3,5,7
* for every further bit, must extend one of these solutions,
* we have 8 candidates, but only 4 are solutions
* yields: square-root(s) modulo $2^{foo}$

### middle part
* equation with 2 variables, degree 2
* Coppersmith finds small solution
* challenge: find an implementation: https://github.com/ubuntor/coppersmith-algorithm/blob/master/coppersmith.sage

Code takes a few minutes
success at rand = 130

```
# copy function coron from ubuntor, see link

def int_to_str(n):
if n == 0:
return ''
return int_to_str(n // 256) + chr(n % 256)

n,cipher = [int(x[4:],16) for x in open('output.txt','r').read().splitlines()]
size = 1024
half = size // 2 - 8
stop = False
for rand in range(8,half):
#for rand in [130]:
print(rand)
rest = size - half - rand
upper = 8
candidates = [1,3,5,7]
for digits in range(4, rest):
candidates += [c + upper for c in candidates]
upper <<= 1
candidates = [c for c in candidates if pow(c,2,upper) == n % upper]

upper_cand = [3]
c0 = '0b1'
base = 1023
for i in range(1,rand):
if (int(c0 + '1',2) << base - i)**2 > n:
c0 += '0'
else:
c0 += '1'
c0 = int(c0,2)

P.<x,y> = PolynomialRing(ZZ)
X = Y = 2**half
for c2 in candidates:
pol = (c0 * 2**(size - rand) + c2 + x * 2**rest)*(c0 * 2**(size - rand) + c2 + y * 2**rest) - n
res = coron(pol, X, Y)
if len(res) > 0:
p = (c0 * 2**(size - rand) + c2 + res[0][0] * 2**rest)
q = (c0 * 2**(size - rand) + c2 + res[0][1] * 2**rest)
#print(res)
print('%d, %d' % (p,q))

phi = (p-1)*(q-1)
e = 65537
d = pow(e,-1,phi)
print(int_to_str(pow(cipher,int(d),n)))
stop = True
break
if stop:
break
```