Reverse Engineering ROCA Key fingerprinting

detect.py

# Taken (and commented, a lot) from https://github.com/crocs-muni/roca/blob/master/roca/detect.py

# The name of the paper`The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli`
# Hints that the Coppersmith atttack will come into play. The Coppersmith attack is a class of attacks
# based on the Coppersmith method (https://en.wikipedia.org/wiki/Coppersmith_method).
# From my limited understanding, it uses complex maths to factorize the modulus given already known information
# about one of the prime factors.

# From deduction, it seems like this fingerprinting function is to determine whether or not the required information
# from one prime factor can be deduced, and hence determining if the modulus is vulnerable to the coppersmith attakck

    def has_fingerprint_real(self, modulus):
        """
        Returns true if the fingerprint was detected in the key
        :param modulus:
        :return:
        """

        self.tested += 1
        print("modulus is " + str(modulus))

        # Checking if the key matches a particular finger print

        # The fingerprint is that a modified modulus masked with a corresponding special number
        # is not zero, for a set of prime numbers and corresponding numbers

        # Testing every prime up to 167, but why?
        for prime, marker in zip(self.primes, self.prints):
            print("prime is " + str(prime))
            print("prints is " + str(marker))  # Not sure what this number is

            # Remainder after modulus is divided by the prime (This would be 0 if the prime is one of the factors)
            # Since the keys we are testing are large, this will not happen. So the exponent will always be a positive number
            # thats bounded by the prime

            exponent = modulus % prime
            # Fermat's little theorem; Might be useful for understanding?
            # a^n (mod n) = a (mod n); when n is prime
            assert exponent == ((modulus**prime) % prime)

            print("exponent is " + str(exponent))

            # 2^(modulus mod prime) ?? What the heck does this represent?
            # The number of possible states in exponent number of bits?
            power_of_two = 2**exponent
            assert power_of_two == 1 << exponent
            print("power of two is " + str(power_of_two))

            # If the power of two, and the marker are mutually exclusive, then
            # the key is not vulnerable. But if EVERY marker and the corresponding power of two
            # are not mutually exclusive (there is some overlap every time), then the key
            # is vulnerable

            # Example of a key without the fingerprint
            # The marker is 5658
            # The power of two is 256
            # 00000000 00000000 00000001 00000000
            # 00000000 00000000 00010110 00011010

            print("power_of_two & self.prints[i] is " + str(power_of_two & marker))
            if power_of_two & marker == 0:
                return False

        # So basically, we have 3 questions
        # 1) What is the meaning of the power of two
        # 2) Where does the marker come from
        # 3) What does the masking tell us about the modulus?
        
        # Also, whats the information we get about one of the prime factors?

        self.found += 1
        return True