diff options
author | Sybren A. Stüvel <sybren@stuvel.eu> | 2021-03-29 23:24:28 +0200 |
---|---|---|
committer | Sybren A. Stüvel <sybren@stuvel.eu> | 2021-03-29 23:24:28 +0200 |
commit | 483700ada63972e600c7770c124f5aa0568dabf7 (patch) | |
tree | be9bdb57e8feee3d683675de8ab9bce7fba007e6 /rsa | |
parent | 35e962d9ce424ef5ea35a9787b7b165fc034712d (diff) | |
download | rsa-git-483700ada63972e600c7770c124f5aa0568dabf7.tar.gz |
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.
Diffstat (limited to 'rsa')
-rw-r--r-- | rsa/key.py | 11 |
1 files changed, 10 insertions, 1 deletions
@@ -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: |