11406610559

Committed 18 Oct 2024 03:31PM UTC coverage: 83.889% (+0.07%) from 83.82%

Build # 11406610559

Build Type

Pull #530

github

Committed by

web-flow

Commit Message

Merge bfae6e1f1 into ba52c6b01

Pull Request Pull Request #530: support for ML-KEM hybrid key exchange groups

Run Details

4551 of 6048 branches covered (75.25%)

Branch coverage included in aggregate %.

137 of 149 new or added lines in 5 files covered. (91.95%)

2 existing lines in 1 file now uncovered.

12220 of 13944 relevant lines covered (87.64%)

43.73 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

96.5

/tlslite/utils/cryptomath.py

# Authors: 
#   Trevor Perrin
#   Martin von Loewis - python 3 port
#   Yngve Pettersen (ported by Paul Sokolovsky) - TLS 1.2
#
# See the LICENSE file for legal information regarding use of this file.

"""cryptomath module

This module has basic math/crypto code."""
from __future__ import print_function
import os
import math
import base64
import binascii

from .compat import compat26Str, compatHMAC, compatLong, \
        bytes_to_int, int_to_bytes, bit_length, byte_length
from .codec import Writer

from . import tlshashlib as hashlib
from . import tlshmac as hmac


# **************************************************************************
# Load Optional Modules
# **************************************************************************

# Try to load M2Crypto/OpenSSL
# pylint: disable=invalid-name
try:
    from M2Crypto import m2
    m2cryptoLoaded = True
    M2CRYPTO_AES_CTR = False
    if hasattr(m2, 'aes_192_ctr'):
        M2CRYPTO_AES_CTR = True

    try:
        with open('/proc/sys/crypto/fips_enabled', 'r') as fipsFile:
            if '1' in fipsFile.read():
                m2cryptoLoaded = False
    except (IOError, OSError):
        # looks like we're running in container, likely not FIPS mode
        m2cryptoLoaded = True

    # If AES-CBC is not available, don't use m2crypto
    if not hasattr(m2, 'aes_192_cbc'):
        m2cryptoLoaded = False

except ImportError:
    m2cryptoLoaded = False
# pylint: enable=invalid-name

#Try to load GMPY
try:
    import gmpy
    gmpy.mpz
    gmpyLoaded = True
except ImportError:
    gmpyLoaded = False


# Try to load GMPY2
try:
    from gmpy2 import powmod
    GMPY2_LOADED = True
except ImportError:
    GMPY2_LOADED = False


# Use the faster mpz
if GMPY2_LOADED:
    from gmpy2 import mpz
elif gmpyLoaded:
    from gmpy import mpz


#Try to load pycrypto
# pylint: disable=invalid-name
try:
    import Crypto.Cipher.AES
    # check if we're not using pycryptodome
    try:
        # pycrypto defaults to ECB when just key is provided
        # pycryptodome requires specifying the mode of operation
        Crypto.Cipher.AES.AESCipher(b'2' * (128//8))
        pycryptoLoaded = True
    except AttributeError:
        pycryptoLoaded = False
except ImportError:
    pycryptoLoaded = False
# pylint: enable=invalid-name


# **************************************************************************
# PRNG Functions
# **************************************************************************

# Check that os.urandom works
import zlib
assert len(zlib.compress(os.urandom(1000))) > 900

def getRandomBytes(howMany):
    b = bytearray(os.urandom(howMany))
    assert(len(b) == howMany)
    return b

prngName = "os.urandom"

# **************************************************************************
# Simple hash functions
# **************************************************************************

def MD5(b):
    """Return a MD5 digest of data"""
    return secureHash(b, 'md5')

def SHA1(b):
    """Return a SHA1 digest of data"""
    return secureHash(b, 'sha1')

def secureHash(data, algorithm):
    """Return a digest of `data` using `algorithm`"""
    hashInstance = hashlib.new(algorithm)
    hashInstance.update(compat26Str(data))
    return bytearray(hashInstance.digest())

def secureHMAC(k, b, algorithm):
    """Return a HMAC using `b` and `k` using `algorithm`"""
    k = compatHMAC(k)
    b = compatHMAC(b)
    return bytearray(hmac.new(k, b, getattr(hashlib, algorithm)).digest())

def HMAC_MD5(k, b):
    return secureHMAC(k, b, 'md5')

def HMAC_SHA1(k, b):
    return secureHMAC(k, b, 'sha1')

def HMAC_SHA256(k, b):
    return secureHMAC(k, b, 'sha256')

def HMAC_SHA384(k, b):
    return secureHMAC(k, b, 'sha384')

def HKDF_expand(PRK, info, L, algorithm):
    N = divceil(L, getattr(hashlib, algorithm)().digest_size)
    T = bytearray()
    Titer = bytearray()
    for x in range(1, N+2):
        T += Titer
        Titer = secureHMAC(PRK, Titer + info + bytearray([x]), algorithm)
    return T[:L]

def HKDF_expand_label(secret, label, hashValue, length, algorithm):
    """
    TLS1.3 key derivation function (HKDF-Expand-Label).

    :param bytearray secret: the key from which to derive the keying material
    :param bytearray label: label used to differentiate the keying materials
    :param bytearray hashValue: bytes used to "salt" the produced keying
        material
    :param int length: number of bytes to produce
    :param str algorithm: name of the secure hash algorithm used as the
        basis of the HKDF
    :rtype: bytearray
    """
    hkdfLabel = Writer()
    hkdfLabel.addTwo(length)
    hkdfLabel.addVarSeq(bytearray(b"tls13 ") + label, 1, 1)
    hkdfLabel.addVarSeq(hashValue, 1, 1)

    return HKDF_expand(secret, hkdfLabel.bytes, length, algorithm)

def derive_secret(secret, label, handshake_hashes, algorithm):
    """
    TLS1.3 key derivation function (Derive-Secret).

    :param bytearray secret: secret key used to derive the keying material
    :param bytearray label: label used to differentiate they keying materials
    :param HandshakeHashes handshake_hashes: hashes of the handshake messages
        or `None` if no handshake transcript is to be used for derivation of
        keying material
    :param str algorithm: name of the secure hash algorithm used as the
        basis of the HKDF algorithm - governs how much keying material will
        be generated
    :rtype: bytearray
    """
    if handshake_hashes is None:
        hs_hash = secureHash(bytearray(b''), algorithm)
    else:
        hs_hash = handshake_hashes.digest(algorithm)
    return HKDF_expand_label(secret, label, hs_hash,
                             getattr(hashlib, algorithm)().digest_size,
                             algorithm)

# **************************************************************************
# Converter Functions
# **************************************************************************

def bytesToNumber(b, endian="big"):
    """
    Convert a number stored in bytearray to an integer.

    By default assumes big-endian encoding of the number.
    """
    return bytes_to_int(b, endian)


def numberToByteArray(n, howManyBytes=None, endian="big"):
    """
    Convert an integer into a bytearray, zero-pad to howManyBytes.

    The returned bytearray may be smaller than howManyBytes, but will
    not be larger.  The returned bytearray will contain a big- or little-endian
    encoding of the input integer (n). Big endian encoding is used by default.
    """
    if howManyBytes is not None:
        length = byte_length(n)
        if howManyBytes < length:
            ret = int_to_bytes(n, length, endian)
            if endian == "big":
                return ret[length-howManyBytes:length]
            return ret[:howManyBytes]
    return int_to_bytes(n, howManyBytes, endian)


def mpiToNumber(mpi):
    """Convert a MPI (OpenSSL bignum string) to an integer."""
    byte = bytearray(mpi)
    if byte[4] & 0x80:
        raise ValueError("Input must be a positive integer")
    return bytesToNumber(byte[4:])


def numberToMPI(n):
    b = numberToByteArray(n)
    ext = 0
    #If the high-order bit is going to be set,
    #add an extra byte of zeros
    if (numBits(n) & 0x7)==0:
        ext = 1
    length = numBytes(n) + ext
    b = bytearray(4+ext) + b
    b[0] = (length >> 24) & 0xFF
    b[1] = (length >> 16) & 0xFF
    b[2] = (length >> 8) & 0xFF
    b[3] = length & 0xFF
    return bytes(b)


# **************************************************************************
# Misc. Utility Functions
# **************************************************************************


# pylint: disable=invalid-name
# pylint recognises them as constants, not function names, also
# we can't change their names without API change
numBits = bit_length


numBytes = byte_length
# pylint: enable=invalid-name


# **************************************************************************
# Big Number Math
# **************************************************************************

def getRandomNumber(low, high):
    assert low < high
    howManyBits = numBits(high)
    howManyBytes = numBytes(high)
    lastBits = howManyBits % 8
    while 1:
        bytes = getRandomBytes(howManyBytes)
        if lastBits:
            bytes[0] = bytes[0] % (1 << lastBits)
        n = bytesToNumber(bytes)
        if n >= low and n < high:
            return n

def gcd(a,b):
    a, b = max(a,b), min(a,b)
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return (a * b) // gcd(a, b)

# pylint: disable=invalid-name
# disable pylint check as the (a, b) are part of the API
if GMPY2_LOADED:
    def invMod(a, b):
        """Return inverse of a mod b, zero if none."""
        if a == 0:
            return 0
        return powmod(a, -1, b)
else:
    # Use Extended Euclidean Algorithm
    def invMod(a, b):
        """Return inverse of a mod b, zero if none."""
        c, d = a, b
        uc, ud = 1, 0
        while c != 0:
            q = d // c
            c, d = d-(q*c), c
            uc, ud = ud - (q * uc), uc
        if d == 1:
            return ud % b
        return 0
# pylint: enable=invalid-name


if gmpyLoaded or GMPY2_LOADED:
    def powMod(base, power, modulus):
        base = mpz(base)
        power = mpz(power)
        modulus = mpz(modulus)
        result = pow(base, power, modulus)
        return compatLong(result)
else:
    powMod = pow


def divceil(divident, divisor):
    """Integer division with rounding up"""
    quot, r = divmod(divident, divisor)
    return quot + int(bool(r))


#Pre-calculate a sieve of the ~100 primes < 1000:
def makeSieve(n):
    sieve = list(range(n))
    for count in range(2, int(math.sqrt(n))+1):
        if sieve[count] == 0:
            continue
        x = sieve[count] * 2
        while x < len(sieve):
            sieve[x] = 0
            x += sieve[count]
    sieve = [x for x in sieve[2:] if x]
    return sieve

def isPrime(n, iterations=5, display=False, sieve=makeSieve(1000)):
    #Trial division with sieve
    for x in sieve:
        if x >= n: return True
        if n % x == 0: return False
    #Passed trial division, proceed to Rabin-Miller
    #Rabin-Miller implemented per Ferguson & Schneier
    #Compute s, t for Rabin-Miller
    if display: print("*", end=' ')
    s, t = n-1, 0
    while s % 2 == 0:
        s, t = s//2, t+1
    #Repeat Rabin-Miller x times
    a = 2 #Use 2 as a base for first iteration speedup, per HAC
    for count in range(iterations):
        v = powMod(a, s, n)
        if v==1:
            continue
        i = 0
        while v != n-1:
            if i == t-1:
                return False
            else:
                v, i = powMod(v, 2, n), i+1
        a = getRandomNumber(2, n)
    return True


def getRandomPrime(bits, display=False):
    """
    Generate a random prime number of a given size.

    the number will be 'bits' bits long (i.e. generated number will be
    larger than `(2^(bits-1) * 3 ) / 2` but smaller than 2^bits.
    """
    assert bits >= 10
    #The 1.5 ensures the 2 MSBs are set
    #Thus, when used for p,q in RSA, n will have its MSB set
    #
    #Since 30 is lcm(2,3,5), we'll set our test numbers to
    #29 % 30 and keep them there
    low = ((2 ** (bits-1)) * 3) // 2
    high = 2 ** bits - 30
    while True:
        if display:
            print(".", end=' ')
        cand_p = getRandomNumber(low, high)
        # make odd
        if cand_p % 2 == 0:
            cand_p += 1
        if isPrime(cand_p, display=display):
            return cand_p


#Unused at the moment...
def getRandomSafePrime(bits, display=False):
    """Generate a random safe prime.

    Will generate a prime `bits` bits long (see getRandomPrime) such that
    the (p-1)/2 will also be prime.
    """
    assert bits >= 10
    #The 1.5 ensures the 2 MSBs are set
    #Thus, when used for p,q in RSA, n will have its MSB set
    #
    #Since 30 is lcm(2,3,5), we'll set our test numbers to
    #29 % 30 and keep them there
    low = (2 ** (bits-2)) * 3//2
    high = (2 ** (bits-1)) - 30
    q = getRandomNumber(low, high)
    q += 29 - (q % 30)
    while 1:
        if display: print(".", end=' ')
        q += 30
        if (q >= high):
            q = getRandomNumber(low, high)
            q += 29 - (q % 30)
        #Ideas from Tom Wu's SRP code
        #Do trial division on p and q before Rabin-Miller
        if isPrime(q, 0, display=display):
            p = (2 * q) + 1
            if isPrime(p, display=display):
                if isPrime(q, display=display):
                    return p

1	# Authors:
2	# Trevor Perrin
3	# Martin von Loewis - python 3 port
4	# Yngve Pettersen (ported by Paul Sokolovsky) - TLS 1.2
5	#
6	# See the LICENSE file for legal information regarding use of this file.
7
8	"""cryptomath module	22✔
9
10	This module has basic math/crypto code."""
11	from __future__ import print_function	54✔
12	import os	54✔
13	import math	54✔
14	import base64	54✔
15	import binascii	54✔
16
17	from .compat import compat26Str, compatHMAC, compatLong, \	54✔
18	bytes_to_int, int_to_bytes, bit_length, byte_length
19	from .codec import Writer	54✔
20
21	from . import tlshashlib as hashlib	54✔
22	from . import tlshmac as hmac	54✔
23
24
25	# **************************************************************************
26	# Load Optional Modules
27	# **************************************************************************
28
29	# Try to load M2Crypto/OpenSSL
30	# pylint: disable=invalid-name
31	try:	54✔
32	from M2Crypto import m2	54✔
33	m2cryptoLoaded = True	54✔
34	M2CRYPTO_AES_CTR = False	54✔
35	if hasattr(m2, 'aes_192_ctr'):	54!
36	M2CRYPTO_AES_CTR = True	54✔
37
38	try:	54✔
39	with open('/proc/sys/crypto/fips_enabled', 'r') as fipsFile:	54✔
40	if '1' in fipsFile.read():	54!
41	m2cryptoLoaded = False	54✔
42	except (IOError, OSError):	54✔
43	# looks like we're running in container, likely not FIPS mode
44	m2cryptoLoaded = True	54✔
45
46	# If AES-CBC is not available, don't use m2crypto
47	if not hasattr(m2, 'aes_192_cbc'):	54!
48	m2cryptoLoaded = False	×
49
50	except ImportError:	54✔
51	m2cryptoLoaded = False	54✔
52	# pylint: enable=invalid-name
53
54	#Try to load GMPY
55	try:	54✔
56	import gmpy	54✔
57	gmpy.mpz	12✔
58	gmpyLoaded = True	12✔
59	except ImportError:	42✔
60	gmpyLoaded = False	42✔
61
62
63	# Try to load GMPY2
64	try:	54✔
65	from gmpy2 import powmod	54✔
66	GMPY2_LOADED = True	16✔
67	except ImportError:	38✔
68	GMPY2_LOADED = False	38✔
69
70
71	# Use the faster mpz
72	if GMPY2_LOADED:	54✔
73	from gmpy2 import mpz	16✔
74	elif gmpyLoaded:	38✔
75	from gmpy import mpz	6✔
76
77
78	#Try to load pycrypto
79	# pylint: disable=invalid-name
80	try:	54✔
81	import Crypto.Cipher.AES	54✔
82	# check if we're not using pycryptodome
83	try:	5✔
84	# pycrypto defaults to ECB when just key is provided
85	# pycryptodome requires specifying the mode of operation
86	Crypto.Cipher.AES.AESCipher(b'2' * (128//8))	5✔
87	pycryptoLoaded = True	4✔
88	except AttributeError:	1✔
89	pycryptoLoaded = False	1✔
90	except ImportError:	49✔
91	pycryptoLoaded = False	49✔
92	# pylint: enable=invalid-name
93
94
95	# **************************************************************************
96	# PRNG Functions
97	# **************************************************************************
98
99	# Check that os.urandom works
100	import zlib	54✔
101	assert len(zlib.compress(os.urandom(1000))) > 900	54✔
102
103	def getRandomBytes(howMany):	54✔
104	b = bytearray(os.urandom(howMany))	54✔
105	assert(len(b) == howMany)	54✔
106	return b	54✔
107
108	prngName = "os.urandom"	54✔
109
110	# **************************************************************************
111	# Simple hash functions
112	# **************************************************************************
113
114	def MD5(b):	54✔
115	"""Return a MD5 digest of data"""
116	return secureHash(b, 'md5')	54✔
117
118	def SHA1(b):	54✔
119	"""Return a SHA1 digest of data"""
120	return secureHash(b, 'sha1')	54✔
121
122	def secureHash(data, algorithm):	54✔
123	"""Return a digest of `data` using `algorithm`"""
124	hashInstance = hashlib.new(algorithm)	54✔
125	hashInstance.update(compat26Str(data))	54✔
126	return bytearray(hashInstance.digest())	54✔
127
128	def secureHMAC(k, b, algorithm):	54✔
129	"""Return a HMAC using `b` and `k` using `algorithm`"""
130	k = compatHMAC(k)	54✔
131	b = compatHMAC(b)	54✔
132	return bytearray(hmac.new(k, b, getattr(hashlib, algorithm)).digest())	54✔
133
134	def HMAC_MD5(k, b):	54✔
135	return secureHMAC(k, b, 'md5')	54✔
136
137	def HMAC_SHA1(k, b):	54✔
138	return secureHMAC(k, b, 'sha1')	54✔
139
140	def HMAC_SHA256(k, b):	54✔
141	return secureHMAC(k, b, 'sha256')	54✔
142
143	def HMAC_SHA384(k, b):	54✔
144	return secureHMAC(k, b, 'sha384')	54✔
145
146	def HKDF_expand(PRK, info, L, algorithm):	54✔
147	N = divceil(L, getattr(hashlib, algorithm)().digest_size)	54✔
148	T = bytearray()	54✔
149	Titer = bytearray()	54✔
150	for x in range(1, N+2):	54✔
151	T += Titer	54✔
152	Titer = secureHMAC(PRK, Titer + info + bytearray([x]), algorithm)	54✔
153	return T[:L]	54✔
154
155	def HKDF_expand_label(secret, label, hashValue, length, algorithm):	54✔
156	"""
157	TLS1.3 key derivation function (HKDF-Expand-Label).
158
159	:param bytearray secret: the key from which to derive the keying material
160	:param bytearray label: label used to differentiate the keying materials
161	:param bytearray hashValue: bytes used to "salt" the produced keying
162	material
163	:param int length: number of bytes to produce
164	:param str algorithm: name of the secure hash algorithm used as the
165	basis of the HKDF
166	:rtype: bytearray
167	"""
168	hkdfLabel = Writer()	54✔
169	hkdfLabel.addTwo(length)	54✔
170	hkdfLabel.addVarSeq(bytearray(b"tls13 ") + label, 1, 1)	54✔
171	hkdfLabel.addVarSeq(hashValue, 1, 1)	54✔
172
173	return HKDF_expand(secret, hkdfLabel.bytes, length, algorithm)	54✔
174
175	def derive_secret(secret, label, handshake_hashes, algorithm):	54✔
176	"""
177	TLS1.3 key derivation function (Derive-Secret).
178
179	:param bytearray secret: secret key used to derive the keying material
180	:param bytearray label: label used to differentiate they keying materials
181	:param HandshakeHashes handshake_hashes: hashes of the handshake messages
182	or `None` if no handshake transcript is to be used for derivation of
183	keying material
184	:param str algorithm: name of the secure hash algorithm used as the
185	basis of the HKDF algorithm - governs how much keying material will
186	be generated
187	:rtype: bytearray
188	"""
189	if handshake_hashes is None:	54✔
190	hs_hash = secureHash(bytearray(b''), algorithm)	54✔
191	else:
192	hs_hash = handshake_hashes.digest(algorithm)	54✔
193	return HKDF_expand_label(secret, label, hs_hash,	54✔
194	getattr(hashlib, algorithm)().digest_size,
195	algorithm)
196
197	# **************************************************************************
198	# Converter Functions
199	# **************************************************************************
200
201	def bytesToNumber(b, endian="big"):	54✔
202	"""
203	Convert a number stored in bytearray to an integer.
204
205	By default assumes big-endian encoding of the number.
206	"""
207	return bytes_to_int(b, endian)	54✔
208
209
210	def numberToByteArray(n, howManyBytes=None, endian="big"):	54✔
211	"""
212	Convert an integer into a bytearray, zero-pad to howManyBytes.
213
214	The returned bytearray may be smaller than howManyBytes, but will
215	not be larger. The returned bytearray will contain a big- or little-endian
216	encoding of the input integer (n). Big endian encoding is used by default.
217	"""
218	if howManyBytes is not None:	54✔
219	length = byte_length(n)	54✔
220	if howManyBytes < length:	54✔
221	ret = int_to_bytes(n, length, endian)	54✔
222	if endian == "big":	54✔
223	return ret[length-howManyBytes:length]	54✔
224	return ret[:howManyBytes]	54✔
225	return int_to_bytes(n, howManyBytes, endian)	54✔
226
227
228	def mpiToNumber(mpi):	54✔
229	"""Convert a MPI (OpenSSL bignum string) to an integer."""
230	byte = bytearray(mpi)	54✔
231	if byte[4] & 0x80:	54✔
232	raise ValueError("Input must be a positive integer")	54✔
233	return bytesToNumber(byte[4:])	54✔
234
235
236	def numberToMPI(n):	54✔
237	b = numberToByteArray(n)	54✔
238	ext = 0	54✔
239	#If the high-order bit is going to be set,
240	#add an extra byte of zeros
241	if (numBits(n) & 0x7)==0:	54✔
242	ext = 1	54✔
243	length = numBytes(n) + ext	54✔
244	b = bytearray(4+ext) + b	54✔
245	b[0] = (length >> 24) & 0xFF	54✔
246	b[1] = (length >> 16) & 0xFF	54✔
247	b[2] = (length >> 8) & 0xFF	54✔
248	b[3] = length & 0xFF	54✔
249	return bytes(b)	54✔
250
251
252	# **************************************************************************
253	# Misc. Utility Functions
254	# **************************************************************************
255
256
257	# pylint: disable=invalid-name
258	# pylint recognises them as constants, not function names, also
259	# we can't change their names without API change
260	numBits = bit_length	54✔
261
262
263	numBytes = byte_length	54✔
264	# pylint: enable=invalid-name
265
266
267	# **************************************************************************
268	# Big Number Math
269	# **************************************************************************
270
271	def getRandomNumber(low, high):	54✔
272	assert low < high	54✔
273	howManyBits = numBits(high)	54✔
274	howManyBytes = numBytes(high)	54✔
275	lastBits = howManyBits % 8	54✔
276	while 1:	41✔
277	bytes = getRandomBytes(howManyBytes)	54✔
278	if lastBits:	54✔
279	bytes[0] = bytes[0] % (1 << lastBits)	54✔
280	n = bytesToNumber(bytes)	54✔
281	if n >= low and n < high:	54✔
282	return n	54✔
283
284	def gcd(a,b):	54✔
285	a, b = max(a,b), min(a,b)	54✔
286	while b:	54✔
287	a, b = b, a % b	54✔
288	return a	54✔
289
290	def lcm(a, b):	54✔
291	return (a * b) // gcd(a, b)	54✔
292
293	# pylint: disable=invalid-name
294	# disable pylint check as the (a, b) are part of the API
295	if GMPY2_LOADED:	54✔
296	def invMod(a, b):	16✔
297	"""Return inverse of a mod b, zero if none."""
298	if a == 0:	16✔
299	return 0	16✔
300	return powmod(a, -1, b)	16✔
301	else:
302	# Use Extended Euclidean Algorithm
303	def invMod(a, b):	38✔
304	"""Return inverse of a mod b, zero if none."""
305	c, d = a, b	38✔
306	uc, ud = 1, 0	38✔
307	while c != 0:	38✔
308	q = d // c	38✔
309	c, d = d-(q*c), c	38✔
310	uc, ud = ud - (q * uc), uc	38✔
311	if d == 1:	38✔
312	return ud % b	38✔
313	return 0	38✔
314	# pylint: enable=invalid-name
315
316
317	if gmpyLoaded or GMPY2_LOADED:	54✔
318	def powMod(base, power, modulus):	22✔
319	base = mpz(base)	22✔
320	power = mpz(power)	22✔
321	modulus = mpz(modulus)	22✔
322	result = pow(base, power, modulus)	22✔
323	return compatLong(result)	22✔
324	else:
325	powMod = pow	32✔
326
327
328	def divceil(divident, divisor):	54✔
329	"""Integer division with rounding up"""
330	quot, r = divmod(divident, divisor)	54✔
331	return quot + int(bool(r))	54✔
332
333
334	#Pre-calculate a sieve of the ~100 primes < 1000:
335	def makeSieve(n):	54✔
336	sieve = list(range(n))	54✔
337	for count in range(2, int(math.sqrt(n))+1):	54✔
338	if sieve[count] == 0:	54✔
339	continue	54✔
340	x = sieve[count] * 2	54✔
341	while x < len(sieve):	54✔
342	sieve[x] = 0	54✔
343	x += sieve[count]	54✔
344	sieve = [x for x in sieve[2:] if x]	54✔
345	return sieve	54✔
346
347	def isPrime(n, iterations=5, display=False, sieve=makeSieve(1000)):	54✔
348	#Trial division with sieve
349	for x in sieve:	54✔
350	if x >= n: return True	54✔
351	if n % x == 0: return False	54✔
352	#Passed trial division, proceed to Rabin-Miller
353	#Rabin-Miller implemented per Ferguson & Schneier
354	#Compute s, t for Rabin-Miller
355	if display: print("*", end=' ')	54✔
356	s, t = n-1, 0	54✔
357	while s % 2 == 0:	54✔
358	s, t = s//2, t+1	54✔
359	#Repeat Rabin-Miller x times
360	a = 2 #Use 2 as a base for first iteration speedup, per HAC	54✔
361	for count in range(iterations):	54✔
362	v = powMod(a, s, n)	54✔
363	if v==1:	54✔
364	continue	54✔
365	i = 0	54✔
366	while v != n-1:	54✔
367	if i == t-1:	54✔
368	return False	54✔
369	else:
370	v, i = powMod(v, 2, n), i+1	54✔
371	a = getRandomNumber(2, n)	54✔
372	return True	54✔
373
374
375	def getRandomPrime(bits, display=False):	54✔
376	"""
377	Generate a random prime number of a given size.
378
379	the number will be 'bits' bits long (i.e. generated number will be
380	larger than `(2^(bits-1) * 3 ) / 2` but smaller than 2^bits.
381	"""
382	assert bits >= 10	54✔
383	#The 1.5 ensures the 2 MSBs are set
384	#Thus, when used for p,q in RSA, n will have its MSB set
385	#
386	#Since 30 is lcm(2,3,5), we'll set our test numbers to
387	#29 % 30 and keep them there
388	low = ((2 ** (bits-1)) * 3) // 2	54✔
389	high = 2 ** bits - 30	54✔
390	while True:	41✔
391	if display:	54!
392	print(".", end=' ')	×
393	cand_p = getRandomNumber(low, high)	54✔
394	# make odd
395	if cand_p % 2 == 0:	54✔
396	cand_p += 1	54✔
397	if isPrime(cand_p, display=display):	54✔
398	return cand_p	54✔
399
400
401	#Unused at the moment...
402	def getRandomSafePrime(bits, display=False):	54✔
403	"""Generate a random safe prime.
404
405	Will generate a prime `bits` bits long (see getRandomPrime) such that
406	the (p-1)/2 will also be prime.
407	"""
408	assert bits >= 10	54✔
409	#The 1.5 ensures the 2 MSBs are set
410	#Thus, when used for p,q in RSA, n will have its MSB set
411	#
412	#Since 30 is lcm(2,3,5), we'll set our test numbers to
413	#29 % 30 and keep them there
414	low = (2 ** (bits-2)) * 3//2	54✔
415	high = (2 ** (bits-1)) - 30	54✔
416	q = getRandomNumber(low, high)	54✔
417	q += 29 - (q % 30)	54✔
418	while 1:	41✔
419	if display: print(".", end=' ')	54✔
420	q += 30	54✔
421	if (q >= high):	54!
UNCOV 422	q = getRandomNumber(low, high)	×
UNCOV 423	q += 29 - (q % 30)	×
424	#Ideas from Tom Wu's SRP code
425	#Do trial division on p and q before Rabin-Miller
426	if isPrime(q, 0, display=display):	54✔
427	p = (2 * q) + 1	54✔
428	if isPrime(p, display=display):	54✔
429	if isPrime(q, display=display):	54!
430	return p	54✔

tlsfuzzer / tlslite-ng / 11406610559

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous