FYI -- More info...
Date: Mon, 16 Oct 2017 18:25:18 -0700 From: John Gilmore <gnu@toad.com>
The essence of the test for broken keys is a list of primes and a list of remainder masks.
"git clone https://github.com/crocs-muni/roca" and examine roca/roca/detect.py:
Here's the test:
for i in range(0, len(self.primes)): if (1 << (modulus % self.primes[i])) & self.prints[i] == 0: return False self.primes = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167] self.prints = [6, 30, 126, 1026, 5658, 107286, 199410, 8388606, 536870910, 2147483646, 67109890, 2199023255550, 8796093022206, 140737488355326, 5310023542746834, 576460752303423486, 1455791217086302986, 147573952589676412926, 20052041432995567486, 6041388139249378920330, 207530445072488465666, 9671406556917033397649406, 618970019642690137449562110, 79228162521181866724264247298, 2535301200456458802993406410750, 1760368345969468176824550810518, 50079290986288516948354744811034, 473022961816146413042658758988474, 10384593717069655257060992658440190, 144390480366845522447407333004847678774, 2722258935367507707706996859454145691646, 174224571863520493293247799005065324265470, 696898287454081973172991196020261297061886, 713623846352979940529142984724747568191373310, 1800793591454480341970779146165214289059119882, 126304807362733370595828809000324029340048915994, 11692013098647223345629478661730264157247460343806, 187072209578355573530071658587684226515959365500926]
So you divide the RSA public key by this set of small primes, and examine the remainder.
If the bit in the matching "prints" number that matches the remainder is on, the key is not vulnerable.
If any of the remainders indexes a bit that's zero, the key is vulnerable.
All the "prints" numbers are even, i.e. their low order bit is zero:
if the remainder when dividing by any small prime is zero, then, ahem, the number is easy to factor!
What does this tell us about how the keys were poorly generated, and what does it tell us about how to factor them?
(We'll find out in early November, but we might as well think about it.)