Private key operations don't use CRT

[tomato42]

The private key operations:

python-rsa/rsa/pkcs1.py

Lines 270 to 300 in 4beb68d

	def sign_hash(hash_value: bytes, priv_key: key.PrivateKey, hash_method: str) -> bytes:
	"""Signs a precomputed hash with the private key.
	Hashes the message, then signs the hash with the given key. This is known
	as a "detached signature", because the message itself isn't altered.
	:param hash_value: A precomputed hash to sign (ignores message).
	:param priv_key: the :py:class:`rsa.PrivateKey` to sign with
	:param hash_method: the hash method used on the message. Use 'MD5', 'SHA-1',
	'SHA-224', SHA-256', 'SHA-384' or 'SHA-512'.
	:return: a message signature block.
	:raise OverflowError: if the private key is too small to contain the
	requested hash.
	"""
	# Get the ASN1 code for this hash method
	if hash_method not in HASH_ASN1:
	raise ValueError('Invalid hash method: %s' % hash_method)
	asn1code = HASH_ASN1[hash_method]
	# Encrypt the hash with the private key
	cleartext = asn1code + hash_value
	keylength = common.byte_size(priv_key.n)
	padded = _pad_for_signing(cleartext, keylength)
	payload = transform.bytes2int(padded)
	encrypted = priv_key.blinded_encrypt(payload)
	block = transform.int2bytes(encrypted, keylength)
	return block

python-rsa/rsa/key.py

Lines 440 to 453 in 4beb68d

	def blinded_encrypt(self, message: int) -> int:
	"""Encrypts the message using blinding to prevent side-channel attacks.
	:param message: the message to encrypt
	:type message: int
	:returns: the encrypted message
	:rtype: int
	"""
	blind_r = self._get_blinding_factor()
	blinded = self.blind(message, blind_r) # blind before encrypting
	encrypted = rsa.core.encrypt_int(blinded, self.d, self.n)
	return self.unblind(encrypted, blind_r)

python-rsa/rsa/core.py

Lines 29 to 53 in 4beb68d

	def encrypt_int(message: int, ekey: int, n: int) -> int:
	"""Encrypts a message using encryption key 'ekey', working modulo n"""
	assert_int(message, 'message')
	assert_int(ekey, 'ekey')
	assert_int(n, 'n')
	if message < 0:
	raise ValueError('Only non-negative numbers are supported')
	if message > n:
	raise OverflowError("The message %i is too long for n=%i" % (message, n))
	return pow(message, ekey, n)
	def decrypt_int(cyphertext: int, dkey: int, n: int) -> int:
	"""Decrypts a cypher text using the decryption key 'dkey', working modulo n"""
	assert_int(cyphertext, 'cyphertext')
	assert_int(dkey, 'dkey')
	assert_int(n, 'n')
	message = pow(cyphertext, dkey, n)
	return message

Use simple pow(x, d, n) operation to calculate the signature or decrypt a message. Because n is composite, it's possible to use Chinese remainder theorem. This will speed up the private key operations by a factor of 2 up to 4.

I.e. Instead of doing:

pow(message, ekey, n)

the code should precompute values for the CRT (with d used instead of ekey as the private exponent):

d_p = d % (p - 1)
d_q = d % (q - 1)
q_inv = rsa.common.inverse(q, p)

and then it can compute the power modulo like so:

s1 = pow(message, d_p, p)
s2 = pow(message, d_q, q)
h = ((s1 - s2) * q_inv) % p
c = s2 + q * h
return c

(or course, as the CRT parameters are closely related to p and q, they should be considered part of the private key and treated accordingly)

[tomato42]

This is despite the code actually calculating the values necessary for CRT:

python-rsa/rsa/key.py

Lines 370 to 379 in 4beb68d

	def __init__(self, n: int, e: int, d: int, p: int, q: int) -> None:
	AbstractKey.__init__(self, n, e)
	self.d = d
	self.p = p
	self.q = q
	# Calculate exponents and coefficient.
	self.exp1 = int(d % (p - 1))
	self.exp2 = int(d % (q - 1))
	self.coef = rsa.common.inverse(q, p)

[sybrenstuvel]

I think I initially just added the code for computing those values for exporting to some PKCS standard file. Good catch, thanks.

[sybrenstuvel]

I wrote this little benchmark, just to see the effect:

import timeit

import rsa
from rsa import common, transform, core, pkcs1

with open("privatekey.pem", "rb") as infile:
    priv_key: rsa.PrivateKey = rsa.PrivateKey.load_pkcs1(infile.read())

with open(__file__, "rb") as infile:
    message = infile.read(500)


keylength = common.byte_size(priv_key.n)
padded = pkcs1._pad_for_encryption(message, keylength)
payload = transform.bytes2int(padded)


def decrypt_standard():
    return core.decrypt_int(payload, priv_key.d, priv_key.n)


def decrypt_crt():
    s1 = pow(payload, priv_key.exp1, priv_key.p)
    s2 = pow(payload, priv_key.exp2, priv_key.q)
    h = ((s1 - s2) * priv_key.coef) % priv_key.p
    c = s2 + priv_key.q * h
    return c


crypto_standard = decrypt_standard()
crypto_crt = decrypt_crt()
assert crypto_standard == crypto_crt, f"Expected {crypto_standard} == {crypto_crt}"

number = 10

time = timeit.timeit(decrypt_standard, globals=locals(), number=number) / number
print(f"decrypt_standard: {time:.4f} sec average")

time = timeit.timeit(decrypt_crt, globals=locals(), number=number) / number
print(f"decrypt_crt     : {time:.4f} sec average")

The result:

$ python benchmark_encryption.py 
decrypt_standard: 0.1458 sec average
decrypt_crt     : 0.0424 sec average

So yes, CRT is 3x faster in this case.

Update: this is for decryption, not encryption.

[tomato42]

the same change can be applied to creation of signatures