Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(400)

Unified Diff: third_party/google-endpoints/rsa/prime.py

Issue 2666783008: Add google-endpoints to third_party/. (Closed)
Patch Set: Created 3 years, 11 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « third_party/google-endpoints/rsa/pkcs1.py ('k') | third_party/google-endpoints/rsa/randnum.py » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: third_party/google-endpoints/rsa/prime.py
diff --git a/third_party/google-endpoints/rsa/prime.py b/third_party/google-endpoints/rsa/prime.py
new file mode 100644
index 0000000000000000000000000000000000000000..6f23f9dac562d78d2209de25c632e204e190455a
--- /dev/null
+++ b/third_party/google-endpoints/rsa/prime.py
@@ -0,0 +1,178 @@
+# -*- coding: utf-8 -*-
+#
+# Copyright 2011 Sybren A. Stüvel <sybren@stuvel.eu>
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# https://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+"""Numerical functions related to primes.
+
+Implementation based on the book Algorithm Design by Michael T. Goodrich and
+Roberto Tamassia, 2002.
+"""
+
+import rsa.randnum
+
+__all__ = ['getprime', 'are_relatively_prime']
+
+
+def gcd(p, q):
+ """Returns the greatest common divisor of p and q
+
+ >>> gcd(48, 180)
+ 12
+ """
+
+ while q != 0:
+ (p, q) = (q, p % q)
+ return p
+
+
+def miller_rabin_primality_testing(n, k):
+ """Calculates whether n is composite (which is always correct) or prime
+ (which theoretically is incorrect with error probability 4**-k), by
+ applying Miller-Rabin primality testing.
+
+ For reference and implementation example, see:
+ https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
+
+ :param n: Integer to be tested for primality.
+ :type n: int
+ :param k: Number of rounds (witnesses) of Miller-Rabin testing.
+ :type k: int
+ :return: False if the number is composite, True if it's probably prime.
+ :rtype: bool
+ """
+
+ # prevent potential infinite loop when d = 0
+ if n < 2:
+ return False
+
+ # Decompose (n - 1) to write it as (2 ** r) * d
+ # While d is even, divide it by 2 and increase the exponent.
+ d = n - 1
+ r = 0
+
+ while not (d & 1):
+ r += 1
+ d >>= 1
+
+ # Test k witnesses.
+ for _ in range(k):
+ # Generate random integer a, where 2 <= a <= (n - 2)
+ a = rsa.randnum.randint(n - 4) + 2
+
+ x = pow(a, d, n)
+ if x == 1 or x == n - 1:
+ continue
+
+ for _ in range(r - 1):
+ x = pow(x, 2, n)
+ if x == 1:
+ # n is composite.
+ return False
+ if x == n - 1:
+ # Exit inner loop and continue with next witness.
+ break
+ else:
+ # If loop doesn't break, n is composite.
+ return False
+
+ return True
+
+
+def is_prime(number):
+ """Returns True if the number is prime, and False otherwise.
+
+ >>> is_prime(2)
+ True
+ >>> is_prime(42)
+ False
+ >>> is_prime(41)
+ True
+ >>> [x for x in range(901, 1000) if is_prime(x)]
+ [907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
+ """
+
+ # Check for small numbers.
+ if number < 10:
+ return number in [2, 3, 5, 7]
+
+ # Check for even numbers.
+ if not (number & 1):
+ return False
+
+ # According to NIST FIPS 186-4, Appendix C, Table C.3, minimum number of
+ # rounds of M-R testing, using an error probability of 2 ** (-100), for
+ # different p, q bitsizes are:
+ # * p, q bitsize: 512; rounds: 7
+ # * p, q bitsize: 1024; rounds: 4
+ # * p, q bitsize: 1536; rounds: 3
+ # See: http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf
+ return miller_rabin_primality_testing(number, 7)
+
+
+def getprime(nbits):
+ """Returns a prime number that can be stored in 'nbits' bits.
+
+ >>> p = getprime(128)
+ >>> is_prime(p-1)
+ False
+ >>> is_prime(p)
+ True
+ >>> is_prime(p+1)
+ False
+
+ >>> from rsa import common
+ >>> common.bit_size(p) == 128
+ True
+ """
+
+ assert nbits > 3 # the loop wil hang on too small numbers
+
+ while True:
+ integer = rsa.randnum.read_random_odd_int(nbits)
+
+ # Test for primeness
+ if is_prime(integer):
+ return integer
+
+ # Retry if not prime
+
+
+def are_relatively_prime(a, b):
+ """Returns True if a and b are relatively prime, and False if they
+ are not.
+
+ >>> are_relatively_prime(2, 3)
+ True
+ >>> are_relatively_prime(2, 4)
+ False
+ """
+
+ d = gcd(a, b)
+ return d == 1
+
+
+if __name__ == '__main__':
+ print('Running doctests 1000x or until failure')
+ import doctest
+
+ for count in range(1000):
+ (failures, tests) = doctest.testmod()
+ if failures:
+ break
+
+ if count and count % 100 == 0:
+ print('%i times' % count)
+
+ print('Doctests done')
« no previous file with comments | « third_party/google-endpoints/rsa/pkcs1.py ('k') | third_party/google-endpoints/rsa/randnum.py » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698