FM / rsa

/usr/lib/python2.6/site-packages/rsa

Name	Size	Mode	Actions
asn1.py	1781	0644	edit dl rm
asn1.pyc	1653	0644	edit dl rm
asn1.pyo	1653	0644	edit dl rm
bigfile.py	5185	0644	edit dl rm
bigfile.pyc	4786	0644	edit dl rm
bigfile.pyo	4786	0644	edit dl rm
cli.py	12185	0644	edit dl rm
cli.pyc	13319	0644	edit dl rm
cli.pyo	13319	0644	edit dl rm
common.py	4640	0644	edit dl rm
common.pyc	4235	0644	edit dl rm
common.pyo	4235	0644	edit dl rm
core.py	1656	0644	edit dl rm
core.pyc	1485	0644	edit dl rm
core.pyo	1485	0644	edit dl rm
key.py	22867	0644	edit dl rm
key.pyc	23986	0644	edit dl rm
key.pyo	23986	0644	edit dl rm
parallel.py	2299	0644	edit dl rm
parallel.pyc	2098	0644	edit dl rm
parallel.pyo	2098	0644	edit dl rm
pem.py	3537	0644	edit dl rm
pem.pyc	2843	0644	edit dl rm
pem.pyo	2843	0644	edit dl rm
pkcs1.py	12230	0644	edit dl rm
pkcs1.pyc	11173	0644	edit dl rm
pkcs1.pyo	11126	0644	edit dl rm
prime.py	4560	0644	edit dl rm
prime.pyc	3664	0644	edit dl rm
prime.pyo	3618	0644	edit dl rm
randnum.py	2643	0644	edit dl rm
randnum.pyc	2074	0644	edit dl rm
randnum.pyo	2074	0644	edit dl rm
transform.py	6892	0644	edit dl rm
transform.pyc	5856	0644	edit dl rm
transform.pyo	5856	0644	edit dl rm
util.py	3059	0644	edit dl rm
util.pyc	2520	0644	edit dl rm
util.pyo	2449	0644	edit dl rm
varblock.py	5406	0644	edit dl rm
varblock.pyc	4856	0644	edit dl rm
varblock.pyo	4856	0644	edit dl rm
_compat.py	3890	0644	edit dl rm
_compat.pyc	3655	0644	edit dl rm
_compat.pyo	3655	0644	edit dl rm
_version133.py	11764	0644	edit dl rm
_version133.pyc	13639	0644	edit dl rm
_version133.pyo	13639	0644	edit dl rm
_version200.py	15123	0644	edit dl rm
_version200.pyc	15264	0644	edit dl rm
_version200.pyo	15264	0644	edit dl rm
__init__.py	1476	0644	edit dl rm
__init__.pyc	1112	0644	edit dl rm
__init__.pyo	1112	0644	edit dl rm

Edit: /usr/lib/python2.6/site-packages/rsa/prime.py (4560B)

# -*- 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')

cmd: