Python builtins 模块，pow() 实例源码

def test_wiener(tries=10):
    print("\nTest: wiener")
    for _ in range(tries):
        n_size = 1024
        p = random_prime(n_size / 2)
        q = random_prime(n_size / 2)
        n = p*q
        phi = (p-1)*(q-1)
        while True:
            d = random.getrandbits(n_size / 4)
            if gmpy2.gcd(phi, d) == 1 and 81 * pow(d, 4) < n:
                break
        e = invmod(d, phi)
        key = RSAKey.construct(int(n), int(e))
        key_recovered = wiener(key.publickey())
        if key_recovered:
            assert key_recovered.d == d
        else:
            print("Not recovered")

def small_e_msg(key, ciphertexts=None, max_times=100):
    """If both e and plaintext are small, ciphertext may exceed modulus only a little

    Args:
        key(RSAKey): with small e, at least one ciphertext
        ciphertexts(list)
        max_times(int): how many times plaintext**e exceeded modulus maximally

    Returns:
        list: recovered plaintexts
    """
    ciphertexts = get_mutable_texts(key, ciphertexts)
    recovered = []
    for ciphertext in ciphertexts:
        log.debug("Find msg for ciphertext {}".format(ciphertext))
        times = 0
        for k in range(max_times):
            msg, is_correct = gmpy2.iroot(ciphertext + times, key.e)
            if is_correct and pow(msg, key.e, key.n) == ciphertext:
                msg = int(msg)
                log.success("Found msg: {}, times=={}".format(i2b(msg), times//key.n))
                recovered.append(msg)
                break
            times += key.n
    return recovered

def pow(x, y, z=_SENTINEL):
        """
        pow(x, y[, z]) -> number

        With two arguments, equivalent to x**y.  With three arguments,
        equivalent to (x**y) % z, but may be more efficient (e.g. for ints).
        """
        # Handle newints
        if isinstance(x, newint):
            x = long(x)
        if isinstance(y, newint):
            y = long(y)
        if isinstance(z, newint):
            z = long(z)

        try:
            if z == _SENTINEL:
                return _builtin_pow(x, y)
            else:
                return _builtin_pow(x, y, z)
        except ValueError:
            if z == _SENTINEL:
                return _builtin_pow(x+0j, y)
            else:
                return _builtin_pow(x+0j, y, z)

    # ``future`` doesn't support Py3.0/3.1. If we ever did, we'd add this:
    #     callable = __builtin__.callable

def pow(x, y, z=_SENTINEL):
        """
        pow(x, y[, z]) -> number

        With two arguments, equivalent to x**y.  With three arguments,
        equivalent to (x**y) % z, but may be more efficient (e.g. for ints).
        """
        # Handle newints
        if isinstance(x, newint):
            x = long(x)
        if isinstance(y, newint):
            y = long(y)
        if isinstance(z, newint):
            z = long(z)

        try:
            if z == _SENTINEL:
                return _builtin_pow(x, y)
            else:
                return _builtin_pow(x, y, z)
        except ValueError:
            if z == _SENTINEL:
                return _builtin_pow(x+0j, y)
            else:
                return _builtin_pow(x+0j, y, z)

    # ``future`` doesn't support Py3.0/3.1. If we ever did, we'd add this:
    #     callable = __builtin__.callable

def pow(x, y, z=_SENTINEL):
        """
        pow(x, y[, z]) -> number

        With two arguments, equivalent to x**y.  With three arguments,
        equivalent to (x**y) % z, but may be more efficient (e.g. for ints).
        """
        # Handle newints
        if isinstance(x, newint):
            x = long(x)
        if isinstance(y, newint):
            y = long(y)
        if isinstance(z, newint):
            z = long(z)

        try:
            if z == _SENTINEL:
                return _builtin_pow(x, y)
            else:
                return _builtin_pow(x, y, z)
        except ValueError:
            if z == _SENTINEL:
                return _builtin_pow(x+0j, y)
            else:
                return _builtin_pow(x+0j, y, z)

    # ``future`` doesn't support Py3.0/3.1. If we ever did, we'd add this:
    #     callable = __builtin__.callable

def test_faulty():
    print("\nTest: faulty")
    for _ in range(5):
        key = RSAKey.generate(1024)
        m = randint(0x13373371, key.n)
        sp = pow(m, key.d % (key.p - 1), key.p)
        sq = pow(m, key.d % (key.q - 1), key.q)
        sq_f = sq ^ randint(1, sq)  # random error

        s_f = crt([sp, sq_f], [key.p, key.q]) % key.n
        s = crt([sp, sq], [key.p, key.q]) % key.n

        key.texts.append({'cipher': s_f, 'plain': m})
        key_recovered = faulty(key.publickey())
        assert key_recovered and key_recovered.d == key.d

        key.texts = [{'cipher': s}, {'cipher': s_f}]
        key_recovered = faulty(key.publickey())
        assert key_recovered and key_recovered.d == key.d

        key.texts = [{'cipher': s}, {'cipher': s_f}, {'cipher': randint(1, key.n)},
                     {'cipher': randint(1, key.n), 'plain': randint(1, key.n)}]
        key_recovered = faulty(key.publickey())
        assert key_recovered and key_recovered.d == key.d

        key.texts = [{'cipher': s, 'plain': m}]
        key_recovered = faulty(key.publickey())
        assert key_recovered is None

def legendre(a, p):
    """Legendre symbol"""
    tmp = pow(a, (p-1)//2, p)
    return -1 if tmp == p-1 else tmp

def tonelli_shanks(n, p):
    """Find r such that r^2 = n % p, r2 == p-r"""
    if legendre(n, p) != 1:
        log.critical_error("Not a square root")

    s = 0
    q = p-1
    while q & 1 == 0:
        s += 1
        q >>= 1

    if s == 1:
        return pow(n, (p+1)//4, p)

    z = 1
    while legendre(z, p) != -1:
        z += 1
    c = pow(z, q, p)

    r = pow(n, (q+1)//2, p)
    t = pow(n, q, p)
    m = s
    while t != 1:
        i = 1
        while i < m:
            if pow(t, 2**i, p) == 1:
                break
            i += 1
        b = pow(c, 2**(m-i-1), p)
        r = (r*b) % p
        t = (t * (b**2)) % p
        c = pow(b, 2, p)
        m = i
    return r

def encrypt(self, plaintext):
        """Raw encryption

        Args: plaintext(int/string)
        Returns: pow(plaintext,e,n)
        """
        if not isinstance(plaintext, Number):
            try:
                plaintext = b2i(plaintext)
            except:
                log.critical_error(
                    "Plaintext to decrypt must be number or be convertible to number ({})".format(plaintext))
        return self.pyrsa_key.encrypt(int(plaintext), 0)[0]

def factors_from_d(n, e, d):
    k = e * d - 1
    while True:
        g = random.randint(2, n - 2)
        b = k // (2**power_of_two(k))
        while b < k:
            gb = pow(g, b, n)
            if gb != 1 and gb != n-1 and pow(gb, 2, n) == 1:
                if gcd(gb-1, n) != 1:
                    p = gcd(gb-1, n)
                else:
                    p = gcd(gb+1, n)
                return p, n//p
            b *= 2

def faulty(key, padding=None):
    """Faulty attack against crt-rsa, Boneh-DeMillo-Lipton
    sp = padding(m)**(d % p-1) % p
    sq' = padding(m)**(d % q-1) % q <--any error during computation
    s' = crt(sp, sq') % n <-- broken signature
    s = crt(sp, sq) % n <-- correct signature
    p = gcd(s'**e - padding(m), n)
    p = gcd(s - s', n)

    Args:
        key(RSAKey): with at least one broken signature (key.texts[no]['cipher']) and corresponding
                     plaintext (key.texts[no]['plain']), or valid and broken signature
        padding(None/function): function used before signing message

    Returns:
        NoneType/RSAKey: False on failure, recovered private key otherwise
    """
    log.debug("Check signature-message pairs")
    for pair in key.texts:
        if 'plain' in pair and 'cipher' in pair:
            signature = gmpy2.mpz(pair['cipher'])
            message = pair['plain']
            if padding:
                message = padding(message)
            p = gmpy2.gcd(pow(signature, key.e) - message, key.n)
            if p != 1 and p != key.n:
                log.info("Found p={}".format(p))
                new_key = RSAKey.construct(key.n, key.e, p=p, identifier=key.identifier + '-private')
                new_key.texts = key.texts[:]
                return new_key

    log.debug("Check for valid-invalid signatures")
    signatures = [tmp['cipher'] for tmp in key.texts if 'cipher' in tmp]
    for pair in itertools.combinations(signatures, 2):
        p = gmpy2.gcd(pair[0] - pair[1], key.n)
        if p != 1 and p != key.n:
            log.info("Found p={}".format(p))
            new_key = RSAKey.construct(key.n, key.e, p=p, identifier=key.identifier + '-private')
            new_key.texts = key.texts[:]
            return new_key
    return None

def pow(x, y, z=_SENTINEL):
        """
        pow(x, y[, z]) -> number

        With two arguments, equivalent to x**y.  With three arguments,
        equivalent to (x**y) % z, but may be more efficient (e.g. for ints).
        """
        # Handle newints
        if isinstance(x, newint):
            x = long(x)
        if isinstance(y, newint):
            y = long(y)
        if isinstance(z, newint):
            z = long(z)

        try:
            if z == _SENTINEL:
                return _builtin_pow(x, y)
            else:
                return _builtin_pow(x, y, z)
        except ValueError:
            if z == _SENTINEL:
                return _builtin_pow(x+0j, y)
            else:
                return _builtin_pow(x+0j, y, z)

    # ``future`` doesn't support Py3.0/3.1. If we ever did, we'd add this:
    #     callable = __builtin__.callable

def pow(x, y, z=_SENTINEL):
        """
        pow(x, y[, z]) -> number

        With two arguments, equivalent to x**y.  With three arguments,
        equivalent to (x**y) % z, but may be more efficient (e.g. for ints).
        """
        # Handle newints
        if isinstance(x, newint):
            x = long(x)
        if isinstance(y, newint):
            y = long(y)
        if isinstance(z, newint):
            z = long(z)

        try:
            if z == _SENTINEL:
                return _builtin_pow(x, y)
            else:
                return _builtin_pow(x, y, z)
        except ValueError:
            if z == _SENTINEL:
                return _builtin_pow(x+0j, y)
            else:
                return _builtin_pow(x+0j, y, z)

    # ``future`` doesn't support Py3.0/3.1. If we ever did, we'd add this:
    #     callable = __builtin__.callable

def pow(x, y, z=_SENTINEL):
        """
        pow(x, y[, z]) -> number

        With two arguments, equivalent to x**y.  With three arguments,
        equivalent to (x**y) % z, but may be more efficient (e.g. for ints).
        """
        # Handle newints
        if isinstance(x, newint):
            x = long(x)
        if isinstance(y, newint):
            y = long(y)
        if isinstance(z, newint):
            z = long(z)

        try:
            if z == _SENTINEL:
                return _builtin_pow(x, y)
            else:
                return _builtin_pow(x, y, z)
        except ValueError:
            if z == _SENTINEL:
                return _builtin_pow(x+0j, y)
            else:
                return _builtin_pow(x+0j, y, z)

    # ``future`` doesn't support Py3.0/3.1. If we ever did, we'd add this:
    #     callable = __builtin__.callable

def pow(x, y, z=_SENTINEL):
        """
        pow(x, y[, z]) -> number

        With two arguments, equivalent to x**y.  With three arguments,
        equivalent to (x**y) % z, but may be more efficient (e.g. for ints).
        """
        # Handle newints
        if isinstance(x, newint):
            x = long(x)
        if isinstance(y, newint):
            y = long(y)
        if isinstance(z, newint):
            z = long(z)

        try:
            if z == _SENTINEL:
                return _builtin_pow(x, y)
            else:
                return _builtin_pow(x, y, z)
        except ValueError:
            if z == _SENTINEL:
                return _builtin_pow(x+0j, y)
            else:
                return _builtin_pow(x+0j, y, z)

    # ``future`` doesn't support Py3.0/3.1. If we ever did, we'd add this:
    #     callable = __builtin__.callable

def pow(x, y, z=_SENTINEL):
        """
        pow(x, y[, z]) -> number

        With two arguments, equivalent to x**y.  With three arguments,
        equivalent to (x**y) % z, but may be more efficient (e.g. for ints).
        """
        # Handle newints
        if isinstance(x, newint):
            x = long(x)
        if isinstance(y, newint):
            y = long(y)
        if isinstance(z, newint):
            z = long(z)

        try:
            if z == _SENTINEL:
                return _builtin_pow(x, y)
            else:
                return _builtin_pow(x, y, z)
        except ValueError:
            if z == _SENTINEL:
                return _builtin_pow(x+0j, y)
            else:
                return _builtin_pow(x+0j, y, z)

    # ``future`` doesn't support Py3.0/3.1. If we ever did, we'd add this:
    #     callable = __builtin__.callable

def pow(x, y, z=_SENTINEL):
        """
        pow(x, y[, z]) -> number

        With two arguments, equivalent to x**y.  With three arguments,
        equivalent to (x**y) % z, but may be more efficient (e.g. for ints).
        """
        # Handle newints
        if isinstance(x, newint):
            x = long(x)
        if isinstance(y, newint):
            y = long(y)
        if isinstance(z, newint):
            z = long(z)

        try:
            if z == _SENTINEL:
                return _builtin_pow(x, y)
            else:
                return _builtin_pow(x, y, z)
        except ValueError:
            if z == _SENTINEL:
                return _builtin_pow(x+0j, y)
            else:
                return _builtin_pow(x+0j, y, z)

    # ``future`` doesn't support Py3.0/3.1. If we ever did, we'd add this:
    #     callable = __builtin__.callable

def _do_sign(self,msg,pv_key,k):
        if (pv_key.curve == None):
            raise ECPyException('private key haz no curve')
        curve = pv_key.curve
        n = curve.order
        G = curve.generator
        k = k%n

        msg = int.from_bytes(msg, 'big')

        Q = G*k
        kinv = pow(k,n-2,n)
        r = Q.x % n
        if r == 0:
            return None

        s = (kinv*(msg+pv_key.d*r)) %n
        if s == 0:
            return None

        sig = encode_sig(r,s,self.fmt)

        # r = r.to_bytes((r.bit_length()+7)//8, 'big')
        # s = s.to_bytes((s.bit_length()+7)//8, 'big')
        # if (r[0] & 0x80) == 0x80 :
        #     r = b'\0'+r
        # if (s[0] & 0x80) == 0x80 :
        #     s = b'\0'+s
        # sig = (b'\x30'+int((len(r)+len(s)+4)).to_bytes(1,'big') +
        #        b'\x02'+int(len(r)).to_bytes(1,'big') + r        +
        #        b'\x02'+int(len(s)).to_bytes(1,'big') + s      )
        return sig

def verify(self,msg,sig,pu_key):
        """ Verifies a message signature.                

        Args:
            msg (bytes)                   : the message hash to verify the signature
            sig (bytes)                   : signature to verify
            pu_key (ecpy.keys.ECPublicKey): key to use for verifying
        """
        curve = pu_key.curve
        n     = curve.order
        G     = curve.generator

        r,s = decode_sig(sig, self.fmt)
        if (r == None or
            r > n     or
            s > n     ) :
            return False

        h = int.from_bytes(msg,'big')

        c   = pow(s, n-2, n)
        u1  = (h*c)%n
        u2  = (r*c)%n
        u1G = u1*G
        u2Q = u2*pu_key.W
        GQ  =  u1G+u2Q
        x   = GQ.x % n

        return x == r

def _jac2aff(x,y,z, q):
        invz = pow(z,q-2,q)
        sqinvz = (invz*invz)%q
        x = (x*sqinvz)%q
        y = (y*sqinvz*invz)%q
        return (x,y)

def x_recover(self, y, sign=0):        
        """ Retrieves the x coordinate according to the y one, \
            such that point (x,y) is on curve.

        Args:
            y (int): y coordinate
            sign (int): sign of x

        Returns:
           int: the computed x coordinate
        """
        q = self.field
        d = self.d
        I = pow(2,(q-1)//4,q)


        if sign:
            sign = 1
        a = (y*y-1)%q
        b = pow(d*y* y+1,q-2,q)
        xx = (a*b)%q
        x = pow(xx,(q+3)//8,q)
        if (x*x - xx) % q != 0:
            x = (x*I) % q
        if x &1 != sign:
            x = q-x
        return x

def _ext2aff(x,y,z,xy, q):
        invz = pow(z,q-2,q)
        x = (x*invz)%q
        y = (y*invz)%q
        return (x,y)

def pow(x, y, z=_SENTINEL):
        """
        pow(x, y[, z]) -> number

        With two arguments, equivalent to x**y.  With three arguments,
        equivalent to (x**y) % z, but may be more efficient (e.g. for ints).
        """
        # Handle newints
        if isinstance(x, newint):
            x = long(x)
        if isinstance(y, newint):
            y = long(y)
        if isinstance(z, newint):
            z = long(z)

        try:
            if z == _SENTINEL:
                return _builtin_pow(x, y)
            else:
                return _builtin_pow(x, y, z)
        except ValueError:
            if z == _SENTINEL:
                return _builtin_pow(x+0j, y)
            else:
                return _builtin_pow(x+0j, y, z)

    # ``future`` doesn't support Py3.0/3.1. If we ever did, we'd add this:
    #     callable = __builtin__.callable

def pow(x, y, z=_SENTINEL):
        """
        pow(x, y[, z]) -> number

        With two arguments, equivalent to x**y.  With three arguments,
        equivalent to (x**y) % z, but may be more efficient (e.g. for ints).
        """
        # Handle newints
        if isinstance(x, newint):
            x = long(x)
        if isinstance(y, newint):
            y = long(y)
        if isinstance(z, newint):
            z = long(z)

        try:
            if z == _SENTINEL:
                return _builtin_pow(x, y)
            else:
                return _builtin_pow(x, y, z)
        except ValueError:
            if z == _SENTINEL:
                return _builtin_pow(x+0j, y)
            else:
                return _builtin_pow(x+0j, y, z)

    # ``future`` doesn't support Py3.0/3.1. If we ever did, we'd add this:
    #     callable = __builtin__.callable