> I personally thus find the term "deterministic version of M-R" somewhat confusing in this context.<div><br></div><div>The paper shows how to build a "fake" prime that passes the deterministic version of the Rabin Miller test. To test Rabin Miller you can take random bases OR you can always run it with the same set of bases (which is the deterministic version of the test). They show that you can choose a number n = p * q, where p and q are somehow related and they will pass the test for every base b if b is coprime to p and b is a square modulo q.<br>As I said this method works if you know in advance the bases that will be used (which is rarely the case I suppose). Also it seems like you are really limited in the number of witness you fool, but this is an old paper and we might be able to do better now.</div><div><br></div><div>> <span style="line-height: 1.4;">Could you sketch how you implement the backdoor? From what I know from</span></div><br style="font-family: Nylas-Pro, Helvetica, 'Lucidia Grande', sans-serif; font-size: 14.5px; line-height: 21.75px;"><div>I have two techniques so far: hiding a subgroup in a composite modulus or hiding a smooth order in a composite modulus.</div><div><br></div><div>In both you generate your modulus n = pq with two fairly strong primes (to avoid any factorization algorithms).</div><div><br></div><div>In the first technique p and q both hide a small subgroup for your generator, so by taking a public key modulo p and q you only have a small discrete logarithm to compute (so you can use Pollard Rho)</div><div><br></div><div>The second technique has p-1 and q-1 both B-smooth, with B large enough to avoid the p-1 factorization algorithm (so >10^15 according to the records of p-1). This way you can use Pohlig-Hellman.</div><div><br></div><div>The implementation/exploitation of TLS is a bit more verbose, gotta extract some information, recompute the premaster key, derive the master key, derive the keys, decrypt</div><div><br></div><div>David</div>