roca_proof_of_equivalence.py

#!/usr/bin/python
import detect

# Original constants
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]

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]

# New implementation constants (after pre-calculation)
tests = detect.RocaFingerprinter().tests

index = 0
for i in range(0, len(primes)):
    # prints are bitmasks of integers < prime
    print("prime=%d, mask=0x%x" % (primes[i], prints[i]))
    assert prints[i] <= ((1 << primes[i]) - 1)
    if prints[i] == ((1 << primes[i]) - 2):
        # all-1 bits except bit 0, which means this test is redundant because it
        # will consider all moduli as potentially vulnerable (Infineon bug)
        # unless they have the prime as a factor (residue=0), in which case they
        # are trivially factorizable anyway. In other words, the impact of this
        # optimization is that a *completely* broken, factorizable key with a
        # small integer factor would, under the previous code, *never* be
        # reported as vulnerable, and under the optimized code, *may* be
        # reported as vulnerable if it also matches all the other tests. This is
        # obviously strictly a good thing.
        print("-> Redundant!")
        new_test = lambda x: True
    else:
        new_prime, new_set = tests[index]
        assert new_prime == primes[i]
        new_test = lambda x: x in new_set
        index += 1

    # Original test:
    #   if (1 << (modulus % self.primes[i])) & self.prints[i] == 0:
    # For every possible value of modulus % self.primes[i]
    for b in range(primes[i]):
        orig_result = (1 << b) & prints[i] == 0
        new_result = new_test(b) is False
        if orig_result != new_result:
            print("-> Fails for residue=%d (orig=%r, new=%r)" % (
                b, orig_result, new_result))

assert len(tests) == index