Fix #162: Blinding uses slow algorithm

Store blinding factor + its inverse, so that they can be reused & updated
on every blinding operation. This avoids expensive computations.

The reuse of the previous blinding factor is done via squaring (mod n), as
per section 9 of 'A Timing Attack against RSA with the Chinese Remainder
Theorem' by Werner Schindler, https://tls.mbed.org/public/WSchindler-RSA_Timing_Attack.pdf

1 files changed, 32 insertions, 20 deletions

diff --git a/rsa/key.py b/rsa/key.py
index b1e2030..e0e7b11 100644
--- a/rsa/key.py
+++ b/rsa/key.py
@@ -49,12 +49,15 @@ DEFAULT_EXPONENT = 65537
 class AbstractKey:
     """Abstract superclass for private and public keys."""
 
-    __slots__ = ('n', 'e')
+    __slots__ = ('n', 'e', 'blindfac', 'blindfac_inverse')
 
     def __init__(self, n: int, e: int) -> None:
         self.n = n
         self.e = e
 
+        # These will be computed properly on the first call to blind().
+        self.blindfac = self.blindfac_inverse = -1
+
     @classmethod
     def _load_pkcs1_pem(cls, keyfile: bytes) -> 'AbstractKey':
         """Loads a key in PKCS#1 PEM format, implement in a subclass.
@@ -145,7 +148,7 @@ class AbstractKey:
         method = self._assert_format_exists(format, methods)
         return method()
 
-    def blind(self, message: int, r: int) -> int:
+    def blind(self, message: int) -> int:
         """Performs blinding on the message using random number 'r'.
 
         :param message: the message, as integer, to blind.
@@ -159,10 +162,10 @@ class AbstractKey:
 
         See https://en.wikipedia.org/wiki/Blinding_%28cryptography%29
         """
+        self._update_blinding_factor()
+        return (message * pow(self.blindfac, self.e, self.n)) % self.n
 
-        return (message * pow(r, self.e, self.n)) % self.n
-
-    def unblind(self, blinded: int, r: int) -> int:
+    def unblind(self, blinded: int) -> int:
         """Performs blinding on the message using random number 'r'.
 
         :param blinded: the blinded message, as integer, to unblind.
@@ -174,8 +177,27 @@ class AbstractKey:
         See https://en.wikipedia.org/wiki/Blinding_%28cryptography%29
         """
 
-        return (rsa.common.inverse(r, self.n) * blinded) % self.n
+        return (self.blindfac_inverse * blinded) % self.n
 
+    def _initial_blinding_factor(self) -> int:
+        for _ in range(1000):
+            blind_r = rsa.randnum.randint(self.n - 1)
+            if rsa.prime.are_relatively_prime(self.n, blind_r):
+                return blind_r
+        raise RuntimeError('unable to find blinding factor')
+
+    def _update_blinding_factor(self):
+        if self.blindfac < 0:
+            # Compute initial blinding factor, which is rather slow to do.
+            self.blindfac = self._initial_blinding_factor()
+            self.blindfac_inverse = rsa.common.inverse(self.blindfac, self.n)
+        else:
+            # Reuse previous blinding factor as per section 9 of 'A Timing
+            # Attack against RSA with the Chinese Remainder Theorem' by Werner
+            # Schindler.
+            # See https://tls.mbed.org/public/WSchindler-RSA_Timing_Attack.pdf
+            self.blindfac = pow(self.blindfac, 2, self.n)
+            self.blindfac_inverse = pow(self.blindfac_inverse, 2, self.n)
 
 class PublicKey(AbstractKey):
     """Represents a public RSA key.
@@ -414,13 +436,6 @@ class PrivateKey(AbstractKey):
     def __hash__(self) -> int:
         return hash((self.n, self.e, self.d, self.p, self.q, self.exp1, self.exp2, self.coef))
 
-    def _get_blinding_factor(self) -> int:
-        for _ in range(1000):
-            blind_r = rsa.randnum.randint(self.n - 1)
-            if rsa.prime.are_relatively_prime(self.n, blind_r):
-                return blind_r
-        raise RuntimeError('unable to find blinding factor')
-
     def blinded_decrypt(self, encrypted: int) -> int:
         """Decrypts the message using blinding to prevent side-channel attacks.
 
@@ -431,11 +446,9 @@ class PrivateKey(AbstractKey):
         :rtype: int
         """
 
-        blind_r = self._get_blinding_factor()
-        blinded = self.blind(encrypted, blind_r)  # blind before decrypting
+        blinded = self.blind(encrypted)  # blind before decrypting
         decrypted = rsa.core.decrypt_int(blinded, self.d, self.n)
-
-        return self.unblind(decrypted, blind_r)
+        return self.unblind(decrypted)
 
     def blinded_encrypt(self, message: int) -> int:
         """Encrypts the message using blinding to prevent side-channel attacks.
@@ -447,10 +460,9 @@ class PrivateKey(AbstractKey):
         :rtype: int
         """
 
-        blind_r = self._get_blinding_factor()
-        blinded = self.blind(message, blind_r)  # blind before encrypting
+        blinded = self.blind(message)  # blind before encrypting
         encrypted = rsa.core.encrypt_int(blinded, self.d, self.n)
-        return self.unblind(encrypted, blind_r)
+        return self.unblind(encrypted)
 
     @classmethod
     def _load_pkcs1_der(cls, keyfile: bytes) -> 'PrivateKey':