From 483700ada63972e600c7770c124f5aa0568dabf7 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Sybren=20A=2E=20St=C3=BCvel?= Date: Mon, 29 Mar 2021 23:24:28 +0200 Subject: Use Chinese Remainder Theorem when decrypting with private key Use the Chinese Remainder Theorem when decrypting with private key, as that makes the decryption 2-4x faster. This fixes #163. --- CHANGELOG.md | 3 +++ rsa/key.py | 11 ++++++++++- 2 files changed, 13 insertions(+), 1 deletion(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index 82a9ab7..3078332 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -8,6 +8,9 @@ - Added marker file for PEP 561. This will allow type checking tools in dependent projects to use type annotations from Python-RSA ([#136](https://github.com/sybrenstuvel/python-rsa/pull/136)). +- Use the Chinese Remainder Theorem when decrypting with a private key. This + makes decryption 2-4x faster + ([#163](https://github.com/sybrenstuvel/python-rsa/pull/163)). ## Version 4.7.2 - released 2021-02-24 diff --git a/rsa/key.py b/rsa/key.py index 63f3f70..e4644d1 100644 --- a/rsa/key.py +++ b/rsa/key.py @@ -473,7 +473,16 @@ class PrivateKey(AbstractKey): # Blinding and un-blinding should be using the same factor blinded, blindfac_inverse = self.blind(encrypted) - decrypted = rsa.core.decrypt_int(blinded, self.d, self.n) + + # Instead of using the core functionality, use the Chinese Remainder + # Theorem and be 2-4x faster. This the same as: + # + # decrypted = rsa.core.decrypt_int(blinded, self.d, self.n) + s1 = pow(blinded, self.exp1, self.p) + s2 = pow(blinded, self.exp2, self.q) + h = ((s1 - s2) * self.coef) % self.p + decrypted = s2 + self.q * h + return self.unblind(decrypted, blindfac_inverse) def blinded_encrypt(self, message: int) -> int: -- cgit v1.2.1