我们从Python开源项目中，提取了以下34个代码示例，用于说明如何使用Crypto.Util.number.GCD。
def test_getStrongPrime(self): """Util.number.getStrongPrime""" self.assertRaises(ValueError, number.getStrongPrime, 256) self.assertRaises(ValueError, number.getStrongPrime, 513) bits = 512 x = number.getStrongPrime(bits) self.assertNotEqual(x % 2, 0) self.assertEqual(x > (1L << bits-1)-1, 1) self.assertEqual(x < (1L << bits), 1) e = 2**16+1 x = number.getStrongPrime(bits, e) self.assertEqual(number.GCD(x-1, e), 1) self.assertNotEqual(x % 2, 0) self.assertEqual(x > (1L << bits-1)-1, 1) self.assertEqual(x < (1L << bits), 1) e = 2**16+2 x = number.getStrongPrime(bits, e) self.assertEqual(number.GCD((x-1)>>1, e), 1) self.assertNotEqual(x % 2, 0) self.assertEqual(x > (1L << bits-1)-1, 1) self.assertEqual(x < (1L << bits), 1)
def test_getStrongPrime(self): """Util.number.getStrongPrime""" self.assertRaises(ValueError, number.getStrongPrime, 256) self.assertRaises(ValueError, number.getStrongPrime, 513) bits = 512 x = number.getStrongPrime(bits) self.assertNotEqual(x % 2, 0) self.assertEqual(x > (1 << bits-1)-1, 1) self.assertEqual(x < (1 << bits), 1) e = 2**16+1 x = number.getStrongPrime(bits, e) self.assertEqual(number.GCD(x-1, e), 1) self.assertNotEqual(x % 2, 0) self.assertEqual(x > (1 << bits-1)-1, 1) self.assertEqual(x < (1 << bits), 1) e = 2**16+2 x = number.getStrongPrime(bits, e) self.assertEqual(number.GCD((x-1)>>1, e), 1) self.assertNotEqual(x % 2, 0) self.assertEqual(x > (1 << bits-1)-1, 1) self.assertEqual(x < (1 << bits), 1)
def _nfold(str, nbytes): # Convert str to a string of length nbytes using the RFC 3961 nfold # operation. # Rotate the bytes in str to the right by nbits bits. def rotate_right(str, nbits): nbytes, remain = (nbits//8) % len(str), nbits % 8 return ''.join(chr((ord(str[i-nbytes]) >> remain) | ((ord(str[i-nbytes-1]) << (8-remain)) & 0xff)) for i in xrange(len(str))) # Add equal-length strings together with end-around carry. def add_ones_complement(str1, str2): n = len(str1) v = [ord(a) + ord(b) for a, b in zip(str1, str2)] # Propagate carry bits to the left until there aren't any left. while any(x & ~0xff for x in v): v = [(v[i-n+1]>>8) + (v[i]&0xff) for i in xrange(n)] return ''.join(chr(x) for x in v) # Concatenate copies of str to produce the least common multiple # of len(str) and nbytes, rotating each copy of str to the right # by 13 bits times its list position. Decompose the concatenation # into slices of length nbytes, and add them together as # big-endian ones' complement integers. slen = len(str) lcm = nbytes * slen / gcd(nbytes, slen) bigstr = ''.join((rotate_right(str, 13 * i) for i in xrange(lcm / slen))) slices = (bigstr[p:p+nbytes] for p in xrange(0, lcm, nbytes)) return reduce(add_ones_complement, slices)
def gcd(a, b): """Fallback implementation when Crypto is missing, and fractions does not exist (Python 2.5) """ if b > a: a, b = b, a c = a % b return b if c == 0 else gcd(c, b)
def _lcm(a, b): """ Least Common Multiple between 2 integers. """ if a == 0 or b == 0: return 0 else: return abs(a * b) / gcd(a, b)
def decrypt(c, p, q): if GCD(c, p*q) != 1: return None if legendreSymbol(c, p) != 1: return None if legendreSymbol(c, q) != 1: return None return pow(c, ((p-1)*(q-1) + 4) / 8, p*q)
def rsa_construct(n, e, d=None, p=None, q=None, u=None): """Construct an RSAKey object""" assert isinstance(n, long) assert isinstance(e, long) assert isinstance(d, (long, type(None))) assert isinstance(p, (long, type(None))) assert isinstance(q, (long, type(None))) assert isinstance(u, (long, type(None))) obj = _RSAKey() obj.n = n obj.e = e if d is None: return obj obj.d = d if p is not None and q is not None: obj.p = p obj.q = q else: # Compute factors p and q from the private exponent d. # We assume that n has no more than two factors. # See 8.2.2(i) in Handbook of Applied Cryptography. ktot = d*e-1 # The quantity d*e-1 is a multiple of phi(n), even, # and can be represented as t*2^s. t = ktot while t%2==0: t=divmod(t,2)[0] # Cycle through all multiplicative inverses in Zn. # The algorithm is non-deterministic, but there is a 50% chance # any candidate a leads to successful factoring. # See "Digitalized Signatures and Public Key Functions as Intractable # as Factorization", M. Rabin, 1979 spotted = 0 a = 2 while not spotted and a<100: k = t # Cycle through all values a^{t*2^i}=a^k while k<ktot: cand = pow(a,k,n) # Check if a^k is a non-trivial root of unity (mod n) if cand!=1 and cand!=(n-1) and pow(cand,2,n)==1: # We have found a number such that (cand-1)(cand+1)=0 (mod n). # Either of the terms divides n. obj.p = GCD(cand+1,n) spotted = 1 break k = k*2 # This value was not any good... let's try another! a = a+2 if not spotted: raise ValueError("Unable to compute factors p and q from exponent d.") # Found ! assert ((n % obj.p)==0) obj.q = divmod(n,obj.p)[0] if u is not None: obj.u = u else: obj.u = inverse(obj.p, obj.q) return obj
def rsa_construct(n, e, d=None, p=None, q=None, u=None): """Construct an RSAKey object""" assert isinstance(n, int) assert isinstance(e, int) assert isinstance(d, (int, type(None))) assert isinstance(p, (int, type(None))) assert isinstance(q, (int, type(None))) assert isinstance(u, (int, type(None))) obj = _RSAKey() obj.n = n obj.e = e if d is None: return obj obj.d = d if p is not None and q is not None: obj.p = p obj.q = q else: # Compute factors p and q from the private exponent d. # We assume that n has no more than two factors. # See 8.2.2(i) in Handbook of Applied Cryptography. ktot = d*e-1 # The quantity d*e-1 is a multiple of phi(n), even, # and can be represented as t*2^s. t = ktot while t%2==0: t=divmod(t,2)[0] # Cycle through all multiplicative inverses in Zn. # The algorithm is non-deterministic, but there is a 50% chance # any candidate a leads to successful factoring. # See "Digitalized Signatures and Public Key Functions as Intractable # as Factorization", M. Rabin, 1979 spotted = 0 a = 2 while not spotted and a<100: k = t # Cycle through all values a^{t*2^i}=a^k while k<ktot: cand = pow(a,k,n) # Check if a^k is a non-trivial root of unity (mod n) if cand!=1 and cand!=(n-1) and pow(cand,2,n)==1: # We have found a number such that (cand-1)(cand+1)=0 (mod n). # Either of the terms divides n. obj.p = GCD(cand+1,n) spotted = 1 break k = k*2 # This value was not any good... let's try another! a = a+2 if not spotted: raise ValueError("Unable to compute factors p and q from exponent d.") # Found ! assert ((n % obj.p)==0) obj.q = divmod(n,obj.p)[0] if u is not None: obj.u = u else: obj.u = inverse(obj.p, obj.q) return obj
