Actually, let's be careful not to misinterpret the code. The fingerprint is detected if *every* remainder from each of the primes hits a *one* bit (not a zero bit). So 0s are actually the "good" remainders (and the fact that the low order bit is zero is a red herring, as the public key modulus should never be divisible by such a small prime). If my interpretation is correct, they can simply drop all the "1" cases from the list. They are then left with about 17 primes with effective tests, so the chances of a false positive are nontrivial. On Tue, Oct 17, 2017 at 9:40 AM, Tomas Rokicki <rokicki@gmail.com> wrote:
For 3, 5, and 7, the only bad remainders are 0. For 11, there are (strangely) a *ton* of bad remainders; all those but 10 and 2.
Here's a count of "bad" remainders for each prime. Very odd.
3 1 5 1 7 1 11 9 13 7 17 9 19 10 23 1 29 1 31 1 37 34 41 1 43 1 47 1 53 27 59 1 61 41 67 1 71 36 73 49 79 66 83 1 89 1 97 91 101 1 103 52 107 54 109 55 113 1 127 85 131 1 137 1 139 1 149 1 151 101 157 79 163 1 167 1
On Tue, Oct 17, 2017 at 9:24 AM, Henry Baker <hbaker1@pipeline.com> wrote:
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 <(214)%20748-3646>, 67109890, 2199023255550, 8796093022206, 140737488355326, 5310023542746834, 576460752303423486, 1455791217086302986, 147573952589676412926, 20052041432995567486, 6041388139249378920330, 207530445072488465666, 9671406556917033397649406, 618970019642690137449562110, 79228162521181866724264247298, 2535301200456458802993406410750, 1760368345969468176824550810518, 50079290986288516948354744811034, 473022961816146413042658758988474, 10384593717069655257060992658440190, 144390480366845522447407333004847678774, 2722258935367507707706996859454145691646 <(414)%20569-1646>, 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.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
-- -- http://cube20.org/ -- http://golly.sf.net/ --