Re: [math-fun] prime targets for Coppersmith hacking

17 Oct 2017


      ...
What does this tell us about how the keys were poorly generated, and
what does it tell us about how to factor them?
...
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
...
That's an enormous hint. Each set of remainders has the Nth-order
    residues modulo the prime, for some N.
    This python program tests and proves it.

#!/usr/bin/python

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 ) # all odd primes from 3 to 167

Generators = ( \
    2, 2, 3, 2, 2, 3, 2, 5, \
    2, 3, 2, 6, 3, 5, 2, 2, \
    2, 2, 7, 5, 3, 2, 3, 5, \
    2, 5, 2, 6, 3, 3, 2, 3, \
    2, 2, 6, 5, 2, 5 )

Rems = ( \
    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 )

def countBits(x):
    qu = 0
    while x != 0:
        qu += 1
        x = x & (x-1)
    return qu

def computeResidues(pr, gen, order):
    power = 1
    res = 1 << power
    gen = (gen ** order) % pr
    for kk in range(order, pr, order):
        power = (power * gen) % pr
        res |= 1 << power
    return res

for pr,gen,rem in zip(Primes,Generators,Rems):
    qu = countBits(rem)
    if ((pr-1) % qu) != 0:
        print pr, qu, hex(rem)
    else:
        order = (pr-1) / qu
        residues = computeResidues(pr, gen, order)
        if residues == rem:
            print pr, qu, str(order) + "-order residues"
        else:
            print pr, qu, hex(rem), hex(residues)

-- 
Don Reble  djr@nk.ca