From eb859f8df6013c673e570799c73da0057848a06c Mon Sep 17 00:00:00 2001 From: "Pavel V. Shatov (Meister)" Date: Sat, 23 Mar 2019 10:48:24 +0300 Subject: Added blinding support to test vector generation scripts. --- vector/vector_format.py | 10 +++-- vector/vector_util.py | 104 +++++++++++++++++++++++++++++++++++++----------- 2 files changed, 87 insertions(+), 27 deletions(-) (limited to 'vector') 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() -- cgit v1.2.3