Added blinding support to test vector generation scripts.

2 files changed, 87 insertions, 27 deletions

diff --git a/vector/vector_format.py b/vector/vector_format.py
index accf691..67a50f0 100644
--- a/vector/vector_format.py
+++ b/vector/vector_format.py
@@ -40,7 +40,8 @@ SCRIPT_USAGE = "USAGE: vector_format.py [openssl_binary]"
 
 KEY_LENGTH = 1024
 
-RNG_SEED = 0
+RNG_SEED_MESSAGE = 1
+RNG_SEED_BLINDING = 2
 
 
 if __name__ == "__main__":
@@ -49,10 +50,11 @@ if __name__ == "__main__":
 
     if len(OPENSSL_BINARY) > 0:
 
-        MESSAGE = vector_util.random_message(RNG_SEED, KEY_LENGTH)
-        VECTOR = vector_util.load_vector(OPENSSL_BINARY, KEY_LENGTH)
+        MESSAGE  = vector_util.random_message(RNG_SEED_MESSAGE, KEY_LENGTH)
+        BLINDING = vector_util.random_blinding(RNG_SEED_BLINDING, KEY_LENGTH)
+        VECTOR   = vector_util.load_vector(OPENSSL_BINARY, KEY_LENGTH)
 
-        vector_ok = VECTOR.selfcheck(MESSAGE)
+        vector_ok = VECTOR.selfcheck(MESSAGE, BLINDING)
         if vector_ok:
             vector_util.save_vector(VECTOR)
             print("Test vector formatted.")
diff --git a/vector/vector_util.py b/vector/vector_util.py
index 413cb61..37e4fb6 100644
--- a/vector/vector_util.py
+++ b/vector/vector_util.py
@@ -42,18 +42,21 @@ from enum import Enum, auto
 
 
 class VectorPiece(Enum):
-    VectorPieceX    = auto()
-    VectorPieceN    = auto()
-    VectorPieceD    = auto()
-    VectorPieceP    = auto()
-    VectorPieceQ    = auto()
-    VectorPieceDP   = auto()
-    VectorPieceDQ   = auto()
-    VectorPieceQINV = auto()
+    VectorPieceOther = auto()
+    VectorPieceN     = auto()
+    VectorPieceD     = auto()
+    VectorPieceP     = auto()
+    VectorPieceQ     = auto()
+    VectorPieceDP    = auto()
+    VectorPieceDQ    = auto()
+    VectorPieceQINV  = auto()
 
 
 class Vector:
 
+    # public exponent
+    _f4 = 0x10001
+
     def __init__(self, length):
         self._bits = length
         self._n    = ""
@@ -101,7 +104,25 @@ class Vector:
 
         return r
 
-    def selfcheck(self, message):
+    def _calc_blind_y(self, x, modulus):
+        x_inv = self._modinv(x, modulus)
+        return pow(x_inv, self._f4, modulus)
+
+    def _egcd(self, a, b):
+        if a == 0:
+            return (b, 0, 1)
+        else:
+            g, y, x = self._egcd(b % a, a)
+        return (g, x - (b // a) * y, y)
+
+    def _modinv(self, a, m):
+        g, x, y = self._egcd(a, m)
+        if g != 1:
+            raise Exception("_modinv() failed!")
+        else:
+            return x % m
+
+    def selfcheck(self, message, blinding):
 
         self.m    = message             # message (padded)
         self.n    = int(self._n,    16) # modulus
@@ -112,6 +133,9 @@ class Vector:
         self.dq   = int(self._dq,   16) # smaller exponent
         self.qinv = int(self._qinv, 16) # helper coefficient
 
+        self.x    = blinding
+        self.y    = self._calc_blind_y(self.x, self.n)
+
         # check modulus
         if self.n == 0:
             print("ERROR: n == 0")
@@ -130,22 +154,40 @@ class Vector:
             print("ERROR: dq != (d % (q-1))")
             return False
 
-        # sign
-        s = pow(message, self.d, self.n)
+        # sign to obtain known good value
+        s_reference = pow(message, self.d, self.n)
+
+        # blind message
+        message_blinded = (message * self.y) % self.n
+
+        # sign blinded message
+        s_blinded = pow(message_blinded, self.d, self.n)
+
+        # unblind signature
+        s_unblinded = (s_blinded * self.x) % self.n
+
+        # check, that x and y actually work
+        if s_unblinded != s_reference:
+            print("ERROR: s_unblinded != s_reference!")
+            return False
+
+        # try to do crt with the blinded message
+        sp_blinded = pow(message_blinded, self.dp, self.p)
+        sq_blinded = pow(message_blinded, self.dq, self.q)
 
-        # try to do crt
-        sp = pow(message, self.dp, self.p)
-        sq = pow(message, self.dq, self.q)
+        # recover full blinded signature
+        sr_blinded = sp_blinded - sq_blinded
+        if sr_blinded < 0: sr_blinded += self.p
 
-        sr = sp - sq
-        if sr < 0: sr += self.p
+        sr_qinv_blinded = (sr_blinded * self.qinv) % self.p
 
-        srqinv = (sr * self.qinv) % self.p
+        s_crt_blinded = sq_blinded + self.q * sr_qinv_blinded
 
-        s_crt = sq + self.q * srqinv
+        # unblind crt signature
+        s_crt_unblinded = (s_crt_blinded * self.x) % self.n
 
-        if s_crt != s:
-            print("ERROR: s_crt != s!")
+        if s_crt_unblinded != s_reference:
+            print("ERROR: s_crt_unblinded != s_reference!")
             return False
 
         self.n_factor = self._calc_mont_factor(self._bits      + 16, self.n)
@@ -204,19 +246,33 @@ def random_message(seed, length):
     return message
 
 
+def random_blinding(seed, length):
+
+    blinding = 0
+    num_bytes = length // 8 - 1
+
+    random.seed(seed)
+
+    for i in range(num_bytes):
+        blinding <<= 8
+        blinding += random.getrandbits(8)
+
+    return blinding
+
+
 def load_vector(binary, length):
 
     vector = Vector(length)
-    piece_type = VectorPiece.VectorPieceX
+    piece_type = VectorPiece.VectorPieceOther
 
     filename = str(length) + "_randomized.key"
     openssl_command = [binary, "rsa", "-in", filename, "-noout", "-text"]
     openssl_stdout = subprocess.check_output(openssl_command).decode("utf-8").splitlines()
 
     for line in openssl_stdout:
-        if   line.startswith("RSA Private-Key:"): piece_type = VectorPiece.VectorPieceX
+        if   line.startswith("RSA Private-Key:"): piece_type = VectorPiece.VectorPieceOther
         elif line.startswith("modulus:"):         piece_type = VectorPiece.VectorPieceN
-        elif line.startswith("publicExponent:"):  piece_type = VectorPiece.VectorPieceX
+        elif line.startswith("publicExponent:"):  piece_type = VectorPiece.VectorPieceOther
         elif line.startswith("privateExponent:"): piece_type = VectorPiece.VectorPieceD
         elif line.startswith("prime1:"):          piece_type = VectorPiece.VectorPieceP
         elif line.startswith("prime2:"):          piece_type = VectorPiece.VectorPieceQ
@@ -252,6 +308,8 @@ def save_vector(vector):
     f.write("    n_coeff  = 0x%x\n" % vector.n_coeff)
     f.write("    p_coeff  = 0x%x\n" % vector.p_coeff)
     f.write("    q_coeff  = 0x%x\n" % vector.q_coeff)
+    f.write("    x        = 0x%x\n" % vector.x)
+    f.write("    y        = 0x%x\n" % vector.y)
 
     f.close()