# 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 minutessuccess 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 = 1024half = size // 2 - 8stop = Falsefor 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```