Hi Petr, Matúš, and Marek, Tanja and I took another look at this today. We checked something on the scale of a million published PGP keys and found hundreds of keys that are weak according to the test that you put online. We tried the keys modulo all small primes, finding (e.g.) 331 as another case where N (along with presumably p and q) is in a very small subgroup (1 and 330). We then followed up on the guess that Tanja mentioned in her previous message, namely that Infineon could be (stupidly) using a power generator _without_ CRT. This drastically reduces the number of powers that are possible---even the best possible choice of generator produces a limited set of primes. We tried the keys modulo various products of small primes that had small subgroups, and found that the remainders modulo primes were correlated, matching the power-generator-without-CRT theory. When we tried a product of several primes, we immediately saw 65537 as a suspiciously small and simple generator. Of course 65537 is very easy to multiply by, and maybe it's already sitting in memory somewhere as an exponent. We then compared the list of weak 2048-bit keys to the powers of 65537 modulo every small prime. For each prime <709, every weak key was a power of 65537; but for 709 this was no longer true. 691 and various smaller primes have relatively few powers of 65537, and those powers show up as weak keys. This data doesn't show whether 701 is included. Actually doing some factorizations would show whether 701 is included. Summary: Presumably Infineon is computing each prime as a power of 65537 modulo L, where L is the product of primes <=701, or perhaps the product of primes <=691. Both of these products are somewhat below 2^1024. Infineon is then adding a multiple of L. Looking at the range of keys, and assuming that p and q have the same range, suggests that Infineon is aiming for [3*2^1022,4*2^1022] or maybe something slightly narrower. We then wrote the attack script shown below, first generating a public key in this way and then taking a subset of L with enough primes to apply the "divisors in residue classes" algorithm, specifically primes where the order of 65537 divides 2^7*3^3*5^2*7*11*13*17*19*23. The LLL step has to be repeated (at most) 2^7*3^3*5^2*7*11*13*17*19*23 times, but for testing we skipped this and simply assumed a correct guess of the residue class. We also assumed that 701 is included. This is a little slower than the speeds you announced, but not much. Probably 2^7*3^3*5^2*7*11*13*17*19*23 isn't optimal, and there are many techniques in the literature that we didn't implement for speeding up "divisors in residue classes". ---Dan from sage.doctest.util import Timer t = Timer() L = 27771430913146044712156219115012732149015337058745243774375474371978395728107173008782747458575903820497344261101333156469136833289328084229401057505005215261077328417649807720533310592783171487952296983742789708502518237023426083874832018749447215424764928016413509553872836856095214672430 L *= 701 # if 701 is included g = Mod(65537,L) pmin = 3*2**1022 pmax = 4*2**1022 t.start() u = lift(g^randrange(L)) while True: p = u + randrange(ceil(pmin/L),floor(pmax/L)) * L if p.is_prime(): break print 'time for first prime',t.stop().cputime t.start() u = lift(g^randrange(L)) while True: q = u + randrange(ceil(pmin/L),floor(pmax/L)) * L if q.is_prime(): break print 'time for second prime',t.stop().cputime n = p * q print 'public key',n smooth = 2^7*3^3*5^2*7*11*13*17*19*23 print 'smooth',smooth def smoothorder(l): return smooth % Mod(g,l).multiplicative_order() == 0 v = prod(l for l,e in factor(L) if smoothorder(l)) print v u = p % v print 'p residue class',(p-u)/v t.start() H = 10 + 2**1021 // v u += floor((7*2**1021) // v) * v w = lift(1/Mod(v,n)) R. = QQ[] f = (w*u+H*x)/n g = H*x k = 3 m = 7 print 'multiplicity',k print 'lattice rank',m basis = [f^j for j in range(0,k)] + [f^k*g^j for j in range(m-k)] basis = [b*n^k for b in basis] basis = [b.change_ring(ZZ) for b in basis] M = matrix(m) for i in range(m): M[i] = basis[i].coefficients(sparse=False) + [0]*(m-1-i) print 'time for creating matrix',t.stop().cputime t.start() M = M.LLL() print 'time for basis reduction',t.stop().cputime Q = sum(z*(x/H)^i for i,z in enumerate(M[0])) for r,multiplicity in Q.roots(): print 'root is',r if u+v*r > 0: g = gcd(n,u+v*r) if g > 1: print 'successful factorization',[g,n/g]