rsa._version200.randint() - Code Metrics - ospaceteam/outerspace - Measure and Improve Code Quality continuously with Scrutinizer

rsa._version200.randint() A
last analyzed 2021-09-11 21:46 UTC

↳ Parent: rsa._version200

Complexity

Conditions

Size

Total Lines	20
Code Lines	7

Duplication

Lines	20
Ratio	100 %

Importance

Changes

Metric	Value
cc	1
eloc	7
nop	2
dl	20
loc	20
rs	10
c	0
b	0
f	0

"""RSA module

Module for calculating large primes, and RSA encryption, decryption,
signing and verification. Includes generating public and private keys.

WARNING: this implementation does not use random padding, compression of the
cleartext input to prevent repetitions, or other common security improvements.
Use with care.

"""

__author__ = "Sybren Stuvel, Marloes de Boer, Ivo Tamboer, and Barry Mead"
__date__ = "2010-02-08"
__version__ = '2.0'

import math
import os
import random
import sys
import types

# Display a warning that this insecure version is imported.
import warnings
warnings.warn('Insecure version of the RSA module is imported as %s' % __name__)


def bit_size(number):
    """Returns the number of bits required to hold a specific long number"""

    return int(math.ceil(math.log(number,2)))

def gcd(p, q):
    """Returns the greatest common divisor of p and q
    >>> gcd(48, 180)
    12
    """
    # Iterateive Version is faster and uses much less stack space
    while q != 0:
        if p < q: (p,q) = (q,p)
        (p,q) = (q, p % q)
    return p


def bytes2int(bytes):

    """Converts a list of bytes or a string to an integer

    >>> (((128 * 256) + 64) * 256) + 15
    8405007
    >>> l = [128, 64, 15]
    >>> bytes2int(l)              #same as bytes2int('\x80@\x0f')
    8405007
    """

    if not (type(bytes) is types.ListType or type(bytes) is types.StringType):
        raise TypeError("You must pass a string or a list")

    # Convert byte stream to integer
    integer = 0
    for byte in bytes:
        integer *= 256
        if type(byte) is types.StringType: byte = ord(byte)
        integer += byte

    return integer

def int2bytes(number):

    """Converts a number to a string of bytes

    >>>int2bytes(123456789)
    '\x07[\xcd\x15'
    >>> bytes2int(int2bytes(123456789))
    123456789
    """

    if not (type(number) is types.LongType or type(number) is types.IntType):
        raise TypeError("You must pass a long or an int")

    string = ""

    while number > 0:
        string = "%s%s" % (chr(number & 0xFF), string)
        number /= 256

    return string

def to64(number):
    """Converts a number in the range of 0 to 63 into base 64 digit
    character in the range of '0'-'9', 'A'-'Z', 'a'-'z','-','_'.

    >>> to64(10)
    'A'
    """

    if not (type(number) is types.LongType or type(number) is types.IntType):
        raise TypeError("You must pass a long or an int")

    if 0 <= number <= 9:            #00-09 translates to '0' - '9'
        return chr(number + 48)

    if 10 <= number <= 35:
        return chr(number + 55)     #10-35 translates to 'A' - 'Z'

    if 36 <= number <= 61:
        return chr(number + 61)     #36-61 translates to 'a' - 'z'

    if number == 62:                # 62   translates to '-' (minus)
        return chr(45)

    if number == 63:                # 63   translates to '_' (underscore)
        return chr(95)

    raise ValueError(u'Invalid Base64 value: %i' % number)


def from64(number):
    """Converts an ordinal character value in the range of
    0-9,A-Z,a-z,-,_ to a number in the range of 0-63.

    >>> from64(49)
    1
    """

    if not (type(number) is types.LongType or type(number) is types.IntType):
        raise TypeError("You must pass a long or an int")

    if 48 <= number <= 57:         #ord('0') - ord('9') translates to 0-9
        return(number - 48)

    if 65 <= number <= 90:         #ord('A') - ord('Z') translates to 10-35
        return(number - 55)

    if 97 <= number <= 122:        #ord('a') - ord('z') translates to 36-61
        return(number - 61)

    if number == 45:               #ord('-') translates to 62
        return(62)

    if number == 95:               #ord('_') translates to 63
        return(63)

    raise ValueError(u'Invalid Base64 value: %i' % number)


def int2str64(number):
    """Converts a number to a string of base64 encoded characters in
    the range of '0'-'9','A'-'Z,'a'-'z','-','_'.

    >>> int2str64(123456789)
    '7MyqL'
    """

    if not (type(number) is types.LongType or type(number) is types.IntType):
        raise TypeError("You must pass a long or an int")

    string = ""

    while number > 0:
        string = "%s%s" % (to64(number & 0x3F), string)
        number /= 64

    return string


def str642int(string):
    """Converts a base64 encoded string into an integer.
    The chars of this string in in the range '0'-'9','A'-'Z','a'-'z','-','_'

    >>> str642int('7MyqL')
    123456789
    """

    if not (type(string) is types.ListType or type(string) is types.StringType):
        raise TypeError("You must pass a string or a list")

    integer = 0
    for byte in string:
        integer *= 64
        if type(byte) is types.StringType: byte = ord(byte)
        integer += from64(byte)

    return integer

def read_random_int(nbits):
    """Reads a random integer of approximately nbits bits rounded up
    to whole bytes"""

    nbytes = int(math.ceil(nbits/8.))
    randomdata = os.urandom(nbytes)
    return bytes2int(randomdata)

def randint(minvalue, maxvalue):

    """Returns a random integer x with minvalue <= x <= maxvalue"""

    # Safety - get a lot of random data even if the range is fairly
    # small
    min_nbits = 32

    # The range of the random numbers we need to generate
    range = (maxvalue - minvalue) + 1

    # Which is this number of bytes
    rangebytes = ((bit_size(range) + 7) / 8)

    # Convert to bits, but make sure it's always at least min_nbits*2
    rangebits = max(rangebytes * 8, min_nbits * 2)

    # Take a random number of bits between min_nbits and rangebits
    nbits = random.randint(min_nbits, rangebits)

    return (read_random_int(nbits) % range) + minvalue

def jacobi(a, b):

    """Calculates the value of the Jacobi symbol (a/b)
    where both a and b are positive integers, and b is odd
    """

    if a == 0: return 0
    result = 1
    while a > 1:
        if a & 1:
            if ((a-1)*(b-1) >> 2) & 1:
                result = -result
            a, b = b % a, a
        else:
            if (((b * b) - 1) >> 3) & 1:
                result = -result
            a >>= 1
    if a == 0: return 0
    return result

def jacobi_witness(x, n):

    """Returns False if n is an Euler pseudo-prime with base x, and
    True otherwise.
    """

    j = jacobi(x, n) % n
    f = pow(x, (n-1)/2, n)

    if j == f: return False
    return True

def randomized_primality_testing(n, k):
    """Calculates whether n is composite (which is always correct) or
    prime (which is incorrect with error probability 2**-k)

    Returns False if the number is composite, and True if it's
    probably prime.
    """

    # 50% of Jacobi-witnesses can report compositness of non-prime numbers

    for i in range(k):
        x = randint(1, n-1)
        if jacobi_witness(x, n): return False

    return True

def is_prime(number):
    """Returns True if the number is prime, and False otherwise.

    >>> is_prime(42)
    0
    >>> is_prime(41)
    1
    """

    if randomized_primality_testing(number, 6):
        # Prime, according to Jacobi
        return True

    # Not prime
    return False


def getprime(nbits):
    """Returns a prime number of max. 'math.ceil(nbits/8)*8' bits. In
    other words: nbits is rounded up to whole bytes.

    >>> p = getprime(8)
    >>> is_prime(p-1)
    0
    >>> is_prime(p)
    1
    >>> is_prime(p+1)
    0
    """

    while True:
        integer = read_random_int(nbits)

        # Make sure it's odd
        integer |= 1

        # Test for primeness
        if is_prime(integer): break

        # Retry if not prime

    return integer

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)
    1
    >>> are_relatively_prime(2, 4)
    0
    """

    d = gcd(a, b)
    return (d == 1)

def find_p_q(nbits):
    """Returns a tuple of two different primes of nbits bits"""
    pbits = nbits + (nbits/16)  #Make sure that p and q aren't too close
    qbits = nbits - (nbits/16)  #or the factoring programs can factor n
    p = getprime(pbits)
    while True:
        q = getprime(qbits)
        #Make sure p and q are different.
        if not q == p: break
    return (p, q)

def extended_gcd(a, b):

    """Returns a tuple (r, i, j) such that r = gcd(a, b) = ia + jb
    """
    # r = gcd(a,b) i = multiplicitive inverse of a mod b
    #      or      j = multiplicitive inverse of b mod a
    # Neg return values for i or j are made positive mod b or a respectively
    # Iterateive Version is faster and uses much less stack space
    x = 0
    y = 1
    lx = 1
    ly = 0
    oa = a                             #Remember original a/b to remove
    ob = b                             #negative values from return results
    while b != 0:
        q = long(a/b)

        (a, b)  = (b, a % b)
        (x, lx) = ((lx - (q * x)),x)
        (y, ly) = ((ly - (q * y)),y)
    if (lx < 0): lx += ob              #If neg wrap modulo orignal b
    if (ly < 0): ly += oa              #If neg wrap modulo orignal a
    return (a, lx, ly)                 #Return only positive values

# Main function: calculate encryption and decryption keys
def calculate_keys(p, q, nbits):

    """Calculates an encryption and a decryption key for p and q, and
    returns them as a tuple (e, d)"""

    n = p * q
    phi_n = (p-1) * (q-1)

    while True:
        # Make sure e has enough bits so we ensure "wrapping" through
        # modulo n
        e = max(65537,getprime(nbits/4))
        if are_relatively_prime(e, n) and are_relatively_prime(e, phi_n): break

    (d, i, j) = extended_gcd(e, phi_n)

    if not d == 1:
        raise Exception("e (%d) and phi_n (%d) are not relatively prime" % (e, phi_n))
    if (i < 0):
        raise Exception("New extended_gcd shouldn't return negative values")
    if not (e * i) % phi_n == 1:
        raise Exception("e (%d) and i (%d) are not mult. inv. modulo phi_n (%d)" % (e, i, phi_n))

    return (e, i)


def gen_keys(nbits):
    """Generate RSA keys of nbits bits. Returns (p, q, e, d).

    Note: this can take a long time, depending on the key size.
    """

    (p, q) = find_p_q(nbits)
    (e, d) = calculate_keys(p, q, nbits)

    return (p, q, e, d)

def newkeys(nbits):
    """Generates public and private keys, and returns them as (pub,
    priv).

    The public key consists of a dict {e: ..., , n: ....). The private
    key consists of a dict {d: ...., p: ...., q: ....).
    """
    nbits = max(9,nbits)           # Don't let nbits go below 9 bits
    (p, q, e, d) = gen_keys(nbits)

    return ( {'e': e, 'n': p*q}, {'d': d, 'p': p, 'q': q} )

def encrypt_int(message, ekey, n):
    """Encrypts a message using encryption key 'ekey', working modulo n"""

    if type(message) is types.IntType:
        message = long(message)


    if not type(message) is types.LongType:
        raise TypeError("You must pass a long or int")

    if message < 0 or message > n:
        raise OverflowError("The message is too long")

    #Note: Bit exponents start at zero (bit counts start at 1) this is correct
    safebit = bit_size(n) - 2                   #compute safe bit (MSB - 1)
    message += (1 << safebit)                   #add safebit to ensure folding

    return pow(message, ekey, n)

def decrypt_int(cyphertext, dkey, n):
    """Decrypts a cypher text using the decryption key 'dkey', working
    modulo n"""

    message = pow(cyphertext, dkey, n)

    safebit = bit_size(n) - 2                   #compute safe bit (MSB - 1)
    message -= (1 << safebit)                   #remove safebit before decode

    return message

def encode64chops(chops):
    """base64encodes chops and combines them into a ',' delimited string"""

    chips = []                              #chips are character chops

    for value in chops:
        chips.append(int2str64(value))

    #delimit chops with comma
    encoded = ','.join(chips)

    return encoded

def decode64chops(string):
    """base64decodes and makes a ',' delimited string into chops"""

    chips = string.split(',')               #split chops at commas

    chops = []

    for string in chips:                    #make char chops (chips) into chops
        chops.append(str642int(string))

    return chops

def chopstring(message, key, n, funcref):
    """Chops the 'message' into integers that fit into n,
    leaving room for a safebit to be added to ensure that all
    messages fold during exponentiation.  The MSB of the number n
    is not independant modulo n (setting it could cause overflow), so
    use the next lower bit for the safebit.  Therefore reserve 2-bits
    in the number n for non-data bits.  Calls specified encryption
    function for each chop.

    Used by 'encrypt' and 'sign'.
    """

    msglen = len(message)
    mbits = msglen * 8
    #Set aside 2-bits so setting of safebit won't overflow modulo n.
    nbits = bit_size(n) - 2             # leave room for safebit
    nbytes = nbits / 8
    blocks = msglen / nbytes

    if msglen % nbytes > 0:
        blocks += 1

    cypher = []

    for bindex in range(blocks):
        offset = bindex * nbytes
        block = message[offset:offset+nbytes]
        value = bytes2int(block)
        cypher.append(funcref(value, key, n))

    return encode64chops(cypher)   #Encode encrypted ints to base64 strings

def gluechops(string, key, n, funcref):
    """Glues chops back together into a string.  calls
    funcref(integer, key, n) for each chop.

    Used by 'decrypt' and 'verify'.
    """
    message = ""

    chops = decode64chops(string)  #Decode base64 strings into integer chops

    for cpart in chops:
        mpart = funcref(cpart, key, n) #Decrypt each chop
        message += int2bytes(mpart)    #Combine decrypted strings into a msg

    return message

def encrypt(message, key):
    """Encrypts a string 'message' with the public key 'key'"""
    if 'n' not in key:
        raise Exception("You must use the public key with encrypt")

    return chopstring(message, key['e'], key['n'], encrypt_int)

def sign(message, key):
    """Signs a string 'message' with the private key 'key'"""
    if 'p' not in key:
        raise Exception("You must use the private key with sign")

    return chopstring(message, key['d'], key['p']*key['q'], encrypt_int)

def decrypt(cypher, key):
    """Decrypts a string 'cypher' with the private key 'key'"""
    if 'p' not in key:
        raise Exception("You must use the private key with decrypt")

    return gluechops(cypher, key['d'], key['p']*key['q'], decrypt_int)

def verify(cypher, key):
    """Verifies a string 'cypher' with the public key 'key'"""
    if 'n' not in key:
        raise Exception("You must use the public key with verify")

    return gluechops(cypher, key['e'], key['n'], decrypt_int)

# Do doctest if we're not imported
if __name__ == "__main__":
    import doctest
    doctest.testmod()

__all__ = ["newkeys", "encrypt", "decrypt", "sign", "verify"]



1		"""RSA module
2
3		Module for calculating large primes, and RSA encryption, decryption,
4		signing and verification. Includes generating public and private keys.
5
6		WARNING: this implementation does not use random padding, compression of the
7		cleartext input to prevent repetitions, or other common security improvements.
8		Use with care.
9
10		"""
11
12		__author__ = "Sybren Stuvel, Marloes de Boer, Ivo Tamboer, and Barry Mead"
13		__date__ = "2010-02-08"
14		__version__ = '2.0'
15
16		import math
17		import os
18		import random
19		import sys
20		import types
21
22		# Display a warning that this insecure version is imported.
23		import warnings
24		warnings.warn('Insecure version of the RSA module is imported as %s' % __name__)
25
26
27		def bit_size(number):
28		"""Returns the number of bits required to hold a specific long number"""
29
30		return int(math.ceil(math.log(number,2)))
31
32		def gcd(p, q):
33		"""Returns the greatest common divisor of p and q
34		>>> gcd(48, 180)
35		12
36		"""
37		# Iterateive Version is faster and uses much less stack space
38		while q != 0:
39		if p < q: (p,q) = (q,p)
40		(p,q) = (q, p % q)
41		return p
42
43
44	View Code Duplication	def bytes2int(bytes):
		0 ignored issues – show Duplication introduced 2018-06-13 22:14 UTC by Report Bug Copy Issue Report This code seems to be duplicated in your project. Loading history...
45		"""Converts a list of bytes or a string to an integer
46
47		>>> (((128 * 256) + 64) * 256) + 15
48		8405007
49		>>> l = [128, 64, 15]
50		>>> bytes2int(l) #same as bytes2int('\x80@\x0f')
51		8405007
52		"""
53
54		if not (type(bytes) is types.ListType or type(bytes) is types.StringType):
55		raise TypeError("You must pass a string or a list")
56
57		# Convert byte stream to integer
58		integer = 0
59		for byte in bytes:
60		integer *= 256
61		if type(byte) is types.StringType: byte = ord(byte)
62		integer += byte
63
64		return integer
65
66	View Code Duplication	def int2bytes(number):
		0 ignored issues – show Duplication introduced 2018-06-13 22:14 UTC by Report Bug Copy Issue Report This code seems to be duplicated in your project. Loading history...
67		"""Converts a number to a string of bytes
68
69		>>>int2bytes(123456789)
70		'\x07[\xcd\x15'
71		>>> bytes2int(int2bytes(123456789))
72		123456789
73		"""
74
75		if not (type(number) is types.LongType or type(number) is types.IntType):
76		raise TypeError("You must pass a long or an int")
77
78		string = ""
79
80		while number > 0:
81		string = "%s%s" % (chr(number & 0xFF), string)
82		number /= 256
83
84		return string
85
86		def to64(number):
87		"""Converts a number in the range of 0 to 63 into base 64 digit
88		character in the range of '0'-'9', 'A'-'Z', 'a'-'z','-','_'.
89
90		>>> to64(10)
91		'A'
92		"""
93
94		if not (type(number) is types.LongType or type(number) is types.IntType):
95		raise TypeError("You must pass a long or an int")
96
97		if 0 <= number <= 9: #00-09 translates to '0' - '9'
98		return chr(number + 48)
99
100		if 10 <= number <= 35:
101		return chr(number + 55) #10-35 translates to 'A' - 'Z'
102
103		if 36 <= number <= 61:
104		return chr(number + 61) #36-61 translates to 'a' - 'z'
105
106		if number == 62: # 62 translates to '-' (minus)
107		return chr(45)
108
109		if number == 63: # 63 translates to '_' (underscore)
110		return chr(95)
111
112		raise ValueError(u'Invalid Base64 value: %i' % number)
113
114
115		def from64(number):
116		"""Converts an ordinal character value in the range of
117		0-9,A-Z,a-z,-,_ to a number in the range of 0-63.
118
119		>>> from64(49)
120		1
121		"""
122
123		if not (type(number) is types.LongType or type(number) is types.IntType):
124		raise TypeError("You must pass a long or an int")
125
126		if 48 <= number <= 57: #ord('0') - ord('9') translates to 0-9
127		return(number - 48)
128
129		if 65 <= number <= 90: #ord('A') - ord('Z') translates to 10-35
130		return(number - 55)
131
132		if 97 <= number <= 122: #ord('a') - ord('z') translates to 36-61
133		return(number - 61)
134
135		if number == 45: #ord('-') translates to 62
136		return(62)
137
138		if number == 95: #ord('_') translates to 63
139		return(63)
140
141		raise ValueError(u'Invalid Base64 value: %i' % number)
142
143
144		def int2str64(number):
145		"""Converts a number to a string of base64 encoded characters in
146		the range of '0'-'9','A'-'Z,'a'-'z','-','_'.
147
148		>>> int2str64(123456789)
149		'7MyqL'
150		"""
151
152		if not (type(number) is types.LongType or type(number) is types.IntType):
153		raise TypeError("You must pass a long or an int")
154
155		string = ""
156
157		while number > 0:
158		string = "%s%s" % (to64(number & 0x3F), string)
159		number /= 64
160
161		return string
162
163
164		def str642int(string):
165		"""Converts a base64 encoded string into an integer.
166		The chars of this string in in the range '0'-'9','A'-'Z','a'-'z','-','_'
167
168		>>> str642int('7MyqL')
169		123456789
170		"""
171
172		if not (type(string) is types.ListType or type(string) is types.StringType):
173		raise TypeError("You must pass a string or a list")
174
175		integer = 0
176		for byte in string:
177		integer *= 64
178		if type(byte) is types.StringType: byte = ord(byte)
179		integer += from64(byte)
180
181		return integer
182
183		def read_random_int(nbits):
184		"""Reads a random integer of approximately nbits bits rounded up
185		to whole bytes"""
186
187		nbytes = int(math.ceil(nbits/8.))
188		randomdata = os.urandom(nbytes)
189		return bytes2int(randomdata)
190
191	View Code Duplication	def randint(minvalue, maxvalue):
		0 ignored issues – show Duplication introduced 2018-06-13 22:14 UTC by Report Bug Copy Issue Report This code seems to be duplicated in your project. Loading history...
192		"""Returns a random integer x with minvalue <= x <= maxvalue"""
193
194		# Safety - get a lot of random data even if the range is fairly
195		# small
196		min_nbits = 32
197
198		# The range of the random numbers we need to generate
199		range = (maxvalue - minvalue) + 1
200
201		# Which is this number of bytes
202		rangebytes = ((bit_size(range) + 7) / 8)
203
204		# Convert to bits, but make sure it's always at least min_nbits*2
205		rangebits = max(rangebytes * 8, min_nbits * 2)
206
207		# Take a random number of bits between min_nbits and rangebits
208		nbits = random.randint(min_nbits, rangebits)
209
210		return (read_random_int(nbits) % range) + minvalue
211
212	View Code Duplication	def jacobi(a, b):
		0 ignored issues – show Duplication introduced 2018-06-13 22:14 UTC by Report Bug Copy Issue Report This code seems to be duplicated in your project. Loading history...
213		"""Calculates the value of the Jacobi symbol (a/b)
214		where both a and b are positive integers, and b is odd
215		"""
216
217		if a == 0: return 0
218		result = 1
219		while a > 1:
220		if a & 1:
221		if ((a-1)*(b-1) >> 2) & 1:
222		result = -result
223		a, b = b % a, a
224		else:
225		if (((b * b) - 1) >> 3) & 1:
226		result = -result
227		a >>= 1
228		if a == 0: return 0
229		return result
230
231	View Code Duplication	def jacobi_witness(x, n):
		0 ignored issues – show Duplication introduced 2018-06-13 22:14 UTC by Report Bug Copy Issue Report This code seems to be duplicated in your project. Loading history...
232		"""Returns False if n is an Euler pseudo-prime with base x, and
233		True otherwise.
234		"""
235
236		j = jacobi(x, n) % n
237		f = pow(x, (n-1)/2, n)
238
239		if j == f: return False
240		return True
241
242		def randomized_primality_testing(n, k):
243		"""Calculates whether n is composite (which is always correct) or
244		prime (which is incorrect with error probability 2**-k)
245
246		Returns False if the number is composite, and True if it's
247		probably prime.
248		"""
249
250		# 50% of Jacobi-witnesses can report compositness of non-prime numbers
251
252		for i in range(k):
253		x = randint(1, n-1)
254		if jacobi_witness(x, n): return False
255
256		return True
257
258		def is_prime(number):
259		"""Returns True if the number is prime, and False otherwise.
260
261		>>> is_prime(42)
262		0
263		>>> is_prime(41)
264		1
265		"""
266
267		if randomized_primality_testing(number, 6):
268		# Prime, according to Jacobi
269		return True
270
271		# Not prime
272		return False
273
274
275		def getprime(nbits):
276		"""Returns a prime number of max. 'math.ceil(nbits/8)*8' bits. In
277		other words: nbits is rounded up to whole bytes.
278
279		>>> p = getprime(8)
280		>>> is_prime(p-1)
281		0
282		>>> is_prime(p)
283		1
284		>>> is_prime(p+1)
285		0
286		"""
287
288		while True:
289		integer = read_random_int(nbits)
290
291		# Make sure it's odd
292		integer \|= 1
293
294		# Test for primeness
295		if is_prime(integer): break
296
297		# Retry if not prime
298
299		return integer
300
301		def are_relatively_prime(a, b):
302		"""Returns True if a and b are relatively prime, and False if they
303		are not.
304
305		>>> are_relatively_prime(2, 3)
306		1
307		>>> are_relatively_prime(2, 4)
308		0
309		"""
310
311		d = gcd(a, b)
312		return (d == 1)
313
314		def find_p_q(nbits):
315		"""Returns a tuple of two different primes of nbits bits"""
316		pbits = nbits + (nbits/16) #Make sure that p and q aren't too close
317		qbits = nbits - (nbits/16) #or the factoring programs can factor n
318		p = getprime(pbits)
319		while True:
320		q = getprime(qbits)
321		#Make sure p and q are different.
322		if not q == p: break
323		return (p, q)
324
325	View Code Duplication	def extended_gcd(a, b):
		0 ignored issues – show Duplication introduced 2018-06-13 22:14 UTC by Report Bug Copy Issue Report This code seems to be duplicated in your project. Loading history...
326		"""Returns a tuple (r, i, j) such that r = gcd(a, b) = ia + jb
327		"""
328		# r = gcd(a,b) i = multiplicitive inverse of a mod b
329		# or j = multiplicitive inverse of b mod a
330		# Neg return values for i or j are made positive mod b or a respectively
331		# Iterateive Version is faster and uses much less stack space
332		x = 0
333		y = 1
334		lx = 1
335		ly = 0
336		oa = a #Remember original a/b to remove
337		ob = b #negative values from return results
338		while b != 0:
339		q = long(a/b)
		0 ignored issues – show Comprehensibility Best Practice introduced 2018-06-13 22:14 UTC by Report Bug Copy Issue Report The variable `long` does not seem to be defined. Loading history...
340		(a, b) = (b, a % b)
341		(x, lx) = ((lx - (q * x)),x)
342		(y, ly) = ((ly - (q * y)),y)
343		if (lx < 0): lx += ob #If neg wrap modulo orignal b
344		if (ly < 0): ly += oa #If neg wrap modulo orignal a
345		return (a, lx, ly) #Return only positive values
346
347		# Main function: calculate encryption and decryption keys
348	View Code Duplication	def calculate_keys(p, q, nbits):
		0 ignored issues – show Duplication introduced 2018-06-13 22:14 UTC by Report Bug Copy Issue Report This code seems to be duplicated in your project. Loading history...
349		"""Calculates an encryption and a decryption key for p and q, and
350		returns them as a tuple (e, d)"""
351
352		n = p * q
353		phi_n = (p-1) * (q-1)
354
355		while True:
356		# Make sure e has enough bits so we ensure "wrapping" through
357		# modulo n
358		e = max(65537,getprime(nbits/4))
359		if are_relatively_prime(e, n) and are_relatively_prime(e, phi_n): break
360
361		(d, i, j) = extended_gcd(e, phi_n)
362
363		if not d == 1:
364		raise Exception("e (%d) and phi_n (%d) are not relatively prime" % (e, phi_n))
365		if (i < 0):
366		raise Exception("New extended_gcd shouldn't return negative values")
367		if not (e * i) % phi_n == 1:
368		raise Exception("e (%d) and i (%d) are not mult. inv. modulo phi_n (%d)" % (e, i, phi_n))
369
370		return (e, i)
371
372
373		def gen_keys(nbits):
374		"""Generate RSA keys of nbits bits. Returns (p, q, e, d).
375
376		Note: this can take a long time, depending on the key size.
377		"""
378
379		(p, q) = find_p_q(nbits)
380		(e, d) = calculate_keys(p, q, nbits)
381
382		return (p, q, e, d)
383
384		def newkeys(nbits):
385		"""Generates public and private keys, and returns them as (pub,
386		priv).
387
388		The public key consists of a dict {e: ..., , n: ....). The private
389		key consists of a dict {d: ...., p: ...., q: ....).
390		"""
391		nbits = max(9,nbits) # Don't let nbits go below 9 bits
392		(p, q, e, d) = gen_keys(nbits)
393
394		return ( {'e': e, 'n': p*q}, {'d': d, 'p': p, 'q': q} )
395
396		def encrypt_int(message, ekey, n):
397		"""Encrypts a message using encryption key 'ekey', working modulo n"""
398
399		if type(message) is types.IntType:
400		message = long(message)
		0 ignored issues – show Comprehensibility Best Practice introduced 2018-06-13 22:14 UTC by Report Bug Copy Issue Report The variable `long` does not seem to be defined. Loading history...
401
402		if not type(message) is types.LongType:
403		raise TypeError("You must pass a long or int")
404
405		if message < 0 or message > n:
406		raise OverflowError("The message is too long")
407
408		#Note: Bit exponents start at zero (bit counts start at 1) this is correct
409		safebit = bit_size(n) - 2 #compute safe bit (MSB - 1)
410		message += (1 << safebit) #add safebit to ensure folding
411
412		return pow(message, ekey, n)
413
414		def decrypt_int(cyphertext, dkey, n):
415		"""Decrypts a cypher text using the decryption key 'dkey', working
416		modulo n"""
417
418		message = pow(cyphertext, dkey, n)
419
420		safebit = bit_size(n) - 2 #compute safe bit (MSB - 1)
421		message -= (1 << safebit) #remove safebit before decode
422
423		return message
424
425		def encode64chops(chops):
426		"""base64encodes chops and combines them into a ',' delimited string"""
427
428		chips = [] #chips are character chops
429
430		for value in chops:
431		chips.append(int2str64(value))
432
433		#delimit chops with comma
434		encoded = ','.join(chips)
435
436		return encoded
437
438		def decode64chops(string):
439		"""base64decodes and makes a ',' delimited string into chops"""
440
441		chips = string.split(',') #split chops at commas
442
443		chops = []
444
445		for string in chips: #make char chops (chips) into chops
446		chops.append(str642int(string))
447
448		return chops
449
450		def chopstring(message, key, n, funcref):
451		"""Chops the 'message' into integers that fit into n,
452		leaving room for a safebit to be added to ensure that all
453		messages fold during exponentiation. The MSB of the number n
454		is not independant modulo n (setting it could cause overflow), so
455		use the next lower bit for the safebit. Therefore reserve 2-bits
456		in the number n for non-data bits. Calls specified encryption
457		function for each chop.
458
459		Used by 'encrypt' and 'sign'.
460		"""
461
462		msglen = len(message)
463		mbits = msglen * 8
464		#Set aside 2-bits so setting of safebit won't overflow modulo n.
465		nbits = bit_size(n) - 2 # leave room for safebit
466		nbytes = nbits / 8
467		blocks = msglen / nbytes
468
469		if msglen % nbytes > 0:
470		blocks += 1
471
472		cypher = []
473
474		for bindex in range(blocks):
475		offset = bindex * nbytes
476		block = message[offset:offset+nbytes]
477		value = bytes2int(block)
478		cypher.append(funcref(value, key, n))
479
480		return encode64chops(cypher) #Encode encrypted ints to base64 strings
481
482		def gluechops(string, key, n, funcref):
483		"""Glues chops back together into a string. calls
484		funcref(integer, key, n) for each chop.
485
486		Used by 'decrypt' and 'verify'.
487		"""
488		message = ""
489
490		chops = decode64chops(string) #Decode base64 strings into integer chops
491
492		for cpart in chops:
493		mpart = funcref(cpart, key, n) #Decrypt each chop
494		message += int2bytes(mpart) #Combine decrypted strings into a msg
495
496		return message
497
498		def encrypt(message, key):
499		"""Encrypts a string 'message' with the public key 'key'"""
500		if 'n' not in key:
501		raise Exception("You must use the public key with encrypt")
502
503		return chopstring(message, key['e'], key['n'], encrypt_int)
504
505		def sign(message, key):
506		"""Signs a string 'message' with the private key 'key'"""
507		if 'p' not in key:
508		raise Exception("You must use the private key with sign")
509
510		return chopstring(message, key['d'], key['p']*key['q'], encrypt_int)
511
512		def decrypt(cypher, key):
513		"""Decrypts a string 'cypher' with the private key 'key'"""
514		if 'p' not in key:
515		raise Exception("You must use the private key with decrypt")
516
517		return gluechops(cypher, key['d'], key['p']*key['q'], decrypt_int)
518
519		def verify(cypher, key):
520		"""Verifies a string 'cypher' with the public key 'key'"""
521		if 'n' not in key:
522		raise Exception("You must use the public key with verify")
523
524		return gluechops(cypher, key['e'], key['n'], decrypt_int)
525
526		# Do doctest if we're not imported
527		if __name__ == "__main__":
528		import doctest
529		doctest.testmod()
530
531		__all__ = ["newkeys", "encrypt", "decrypt", "sign", "verify"]
532
533

ospaceteam / outerspace

rsa._version200.randint() A last analyzed 2021-09-11 21:46 UTC

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

rsa._version200.randint() A
last analyzed 2021-09-11 21:46 UTC