diff options
| -rw-r--r-- | modexpng_fpga_model.py | 335 |
1 files changed, 285 insertions, 50 deletions
diff --git a/modexpng_fpga_model.py b/modexpng_fpga_model.py index cc3e868..4ef6576 100644 --- a/modexpng_fpga_model.py +++ b/modexpng_fpga_model.py @@ -41,6 +41,7 @@ import sys import importlib +from enum import Enum, auto # -------------- @@ -63,6 +64,7 @@ _KEY_LENGTH_HALF = KEY_LENGTH // 2 # width of internal math pipeline _WORD_WIDTH = 16 +_WORD_WIDTH_EXT = 18 # folder with test vector scripts _VECTOR_PATH = "/vector" @@ -122,7 +124,7 @@ class ModExpNG_Operand(): for i in range(count): # word must not exceed 18 bits - if words[i] >= (2 ** (_WORD_WIDTH + 2)): + if words[i] >= (2 ** (_WORD_WIDTH_EXT)): raise Exception("Word is too large!") self.words = words @@ -158,7 +160,7 @@ class ModExpNG_Operand(): ret += word << shift shift += _WORD_WIDTH return ret - + # # Test Vector @@ -200,6 +202,118 @@ class ModExpNG_TestVector(): self.x = ModExpNG_Operand(vector_inst.x, KEY_LENGTH) self.y = ModExpNG_Operand(vector_inst.y, KEY_LENGTH) +class ModExpNG_WideBankEnum(Enum): + A = auto() + B = auto() + C = auto() + D = auto() + E = auto() + N = auto() + +class ModExpNG_NarrowBankEnum(Enum): + A = auto() + B = auto() + C = auto() + D = auto() + E = auto() + N_COEFF = auto() + I = auto() + +class ModExpNG_WideBank(): + + def __init__(self): + self.a = None + self.b = None + self.c = None + self.d = None + self.e = None + self.n = None + + def _get_value(self, sel): + if sel == ModExpNG_WideBankEnum.A: return self.a + elif sel == ModExpNG_WideBankEnum.B: return self.b + elif sel == ModExpNG_WideBankEnum.C: return self.c + elif sel == ModExpNG_WideBankEnum.D: return self.d + elif sel == ModExpNG_WideBankEnum.E: return self.e + elif sel == ModExpNG_WideBankEnum.N: return self.n + else: raise Exception("ModExpNG_WideBank._get_value(): Invalid selector!") + + def _set_value(self, sel, value): + if sel == ModExpNG_WideBankEnum.A: self.a = value + elif sel == ModExpNG_WideBankEnum.B: self.b = value + elif sel == ModExpNG_WideBankEnum.C: self.c = value + elif sel == ModExpNG_WideBankEnum.D: self.d = value + elif sel == ModExpNG_WideBankEnum.E: self.e = value + elif sel == ModExpNG_WideBankEnum.N: self.n = value + else: raise Exception("ModExpNG_WideBank._set_value(): Invalid selector!") + +class ModExpNG_NarrowBank(): + + def __init__(self, i): + self.a = None + self.b = None + self.c = None + self.d = None + self.e = None + self.n_coeff = None + self.i = i + + def _get_value(self, sel): + if sel == ModExpNG_NarrowBankEnum.A: return self.a + elif sel == ModExpNG_NarrowBankEnum.B: return self.b + elif sel == ModExpNG_NarrowBankEnum.C: return self.c + elif sel == ModExpNG_NarrowBankEnum.D: return self.d + elif sel == ModExpNG_NarrowBankEnum.E: return self.e + elif sel == ModExpNG_NarrowBankEnum.N_COEFF: return self.n_coeff + elif sel == ModExpNG_NarrowBankEnum.I: return self.i + else: raise Exception("ModExpNG_NarrowBank._get_value(): Invalid selector!") + + def _set_value(self, sel, value): + if sel == ModExpNG_NarrowBankEnum.A: self.a = value + elif sel == ModExpNG_NarrowBankEnum.B: self.b = value + elif sel == ModExpNG_NarrowBankEnum.C: self.c = value + elif sel == ModExpNG_NarrowBankEnum.D: self.d = value + elif sel == ModExpNG_NarrowBankEnum.E: self.e = value + elif sel == ModExpNG_NarrowBankEnum.N_COEFF: self.n_coeff = value + else: raise Exception("ModExpNG_NarrowBank._set_value(): Invalid selector!") + +class ModExpNG_BanksPair(): + + def __init__(self, i): + self.wide = ModExpNG_WideBank() + self.narrow = ModExpNG_NarrowBank(i) + + def _get_value_wide(self, sel): + return self.wide._get_value(sel) + + def _get_value_narrow(self, sel): + return self.narrow._get_value(sel) + +class ModExpNG_BanksLadder(): + + def __init__(self, i): + self.ladder_x = ModExpNG_BanksPair(i) + self.ladder_y = ModExpNG_BanksPair(i) + + def set_modulus(self, n, n_coeff): + self.ladder_x.wide._set_value(ModExpNG_WideBankEnum.N, n) + self.ladder_y.wide._set_value(ModExpNG_WideBankEnum.N, n) + self.ladder_x.narrow._set_value(ModExpNG_NarrowBankEnum.N_COEFF, n_coeff) + self.ladder_y.narrow._set_value(ModExpNG_NarrowBankEnum.N_COEFF, n_coeff) + + def set_operand(self, sel_wide, sel_narrow, x, y): + if sel_wide is not None: + self.ladder_x.wide._set_value(sel_wide, x) + self.ladder_y.wide._set_value(sel_wide, y) + if sel_narrow is not None: + self.ladder_x.narrow._set_value(sel_narrow, x) + self.ladder_y.narrow._set_value(sel_narrow, y) + +class ModExpNG_BanksCRT(): + + def __init__(self, i): + self.crt_x = ModExpNG_BanksLadder(i) + self.crt_y = ModExpNG_BanksLadder(i) class ModExpNG_PartRecombinator(): @@ -348,7 +462,6 @@ class ModExpNG_PartRecombinator(): return words - class ModExpNG_WordMultiplier(): def __init__(self): @@ -641,7 +754,6 @@ class ModExpNG_WordMultiplier(): return parts - class ModExpNG_LowlevelOperator(): def __init__(self): @@ -687,7 +799,6 @@ class ModExpNG_LowlevelOperator(): return (dif_b, dif_d) - class ModExpNG_Worker(): def __init__(self): @@ -888,15 +999,109 @@ class ModExpNG_Worker(): print(" = 0x%05x" % R[i]) return ModExpNG_Operand(None, ab_num_words, R) - - def reduce(self, a): + + def reduce(self, a, num_words): carry = 0 - for x in range(len(a.words)): + for x in range(num_words): a.words[x] += carry carry = (a.words[x] >> _WORD_WIDTH) & 3 a.words[x] &= self.lowlevel._word_mask +class ModExpNG_CoreOutputEnum(Enum): + XM = auto() + YM = auto() + S = auto() + +class ModExpNG_CoreOutput(): + + def __init__(self): + self._xm = None + self._ym = None + self._s = None + + def _set_value(self, sel, value): + if sel == ModExpNG_CoreOutputEnum.XM: self._xm = value + elif sel == ModExpNG_CoreOutputEnum.YM: self._ym = value + elif sel == ModExpNG_CoreOutputEnum.S: self._s = value + else: raise Exception("ModExpNG_CoreOutput._set_value(): invalid selector!") + + def get_value(self, sel): + if sel == ModExpNG_CoreOutputEnum.XM: return self._xm + elif sel == ModExpNG_CoreOutputEnum.YM: return self._ym + elif sel == ModExpNG_CoreOutputEnum.S: return self._s + else: raise Exception("ModExpNG_CoreOutput.get_value(): invalid selector!") + +class ModExpNG_Core(): + + def __init__(self, i): + self.wrk = ModExpNG_Worker() + self.bnk = ModExpNG_BanksCRT(i) + self.out = ModExpNG_CoreOutput() + + def multiply(self, sel_wide_in, sel_narrow_in, sel_wide_out, sel_narrow_out, num_words, mode=(True, True)): + + xn = self.bnk.crt_x.ladder_x.wide._get_value(ModExpNG_WideBankEnum.N) + yn = self.bnk.crt_y.ladder_x.wide._get_value(ModExpNG_WideBankEnum.N) + + xn_coeff = self.bnk.crt_x.ladder_x.narrow._get_value(ModExpNG_NarrowBankEnum.N_COEFF) + yn_coeff = self.bnk.crt_y.ladder_x.narrow._get_value(ModExpNG_NarrowBankEnum.N_COEFF) + + xxa = self.bnk.crt_x.ladder_x.wide._get_value(sel_wide_in) + xya = self.bnk.crt_x.ladder_y.wide._get_value(sel_wide_in) + + yxa = self.bnk.crt_y.ladder_x.wide._get_value(sel_wide_in) + yya = self.bnk.crt_y.ladder_y.wide._get_value(sel_wide_in) + + xxb = self.bnk.crt_x.ladder_x.narrow._get_value(sel_narrow_in) + xyb = self.bnk.crt_x.ladder_y.narrow._get_value(sel_narrow_in) + + yxb = self.bnk.crt_y.ladder_x.narrow._get_value(sel_narrow_in) + yyb = self.bnk.crt_y.ladder_y.narrow._get_value(sel_narrow_in) + + if not mode[0]: xb = xxb + else: xb = xyb + + if not mode[1]: yb = yxb + else: yb = yyb + + xxp = self.wrk.multiply(xxa, xb, xn, xn_coeff, num_words) + xyp = self.wrk.multiply(xya, xb, xn, xn_coeff, num_words) + + yxp = self.wrk.multiply(yxa, yb, yn, yn_coeff, num_words) + yyp = self.wrk.multiply(yya, yb, yn, yn_coeff, num_words) + + if sel_wide_out is not None: + self.bnk.crt_x.ladder_x.wide._set_value(sel_wide_out, xxp) + self.bnk.crt_x.ladder_y.wide._set_value(sel_wide_out, xyp) + self.bnk.crt_y.ladder_x.wide._set_value(sel_wide_out, yxp) + self.bnk.crt_y.ladder_y.wide._set_value(sel_wide_out, yyp) + + if sel_narrow_out is not None: + self.bnk.crt_x.ladder_x.narrow._set_value(sel_narrow_out, xxp) + self.bnk.crt_x.ladder_y.narrow._set_value(sel_narrow_out, xyp) + self.bnk.crt_y.ladder_x.narrow._set_value(sel_narrow_out, yxp) + self.bnk.crt_y.ladder_y.narrow._set_value(sel_narrow_out, yyp) + + def simply_reduce(self, sel_narrow, num_words): + self.wrk.reduce(self.bnk.crt_x.ladder_x.narrow._get_value(sel_narrow), num_words) + self.wrk.reduce(self.bnk.crt_x.ladder_y.narrow._get_value(sel_narrow), num_words) + self.wrk.reduce(self.bnk.crt_y.ladder_x.narrow._get_value(sel_narrow), num_words) + self.wrk.reduce(self.bnk.crt_y.ladder_y.narrow._get_value(sel_narrow), num_words) + + def set_output(self, sel_output, banks_ladder, sel_narrow): + self.out._set_value(sel_output, banks_ladder.ladder_x.narrow._get_value(sel_narrow)) + + def mirror_yx(self, sel_wide, sel_narrow): + + if sel_wide is not None: + self.bnk.crt_x.ladder_x.wide._set_value(sel_wide, self.bnk.crt_y.ladder_x.wide._get_value(sel_wide)) + self.bnk.crt_x.ladder_y.wide._set_value(sel_wide, self.bnk.crt_y.ladder_y.wide._get_value(sel_wide)) + if sel_narrow is not None: + self.bnk.crt_x.ladder_x.narrow._set_value(sel_narrow, self.bnk.crt_y.ladder_x.narrow._get_value(sel_narrow)) + self.bnk.crt_x.ladder_y.narrow._set_value(sel_narrow, self.bnk.crt_y.ladder_y.narrow._get_value(sel_narrow)) + + if __name__ == "__main__": # load test vector @@ -906,16 +1111,16 @@ if __name__ == "__main__": # create helper quantity # mutate blinding quantities with built-in math - vector = ModExpNG_TestVector() - worker = ModExpNG_Worker() - n_num_words = KEY_LENGTH // _WORD_WIDTH pq_num_words = n_num_words // 2 - s_known = pow(vector.m.number(), vector.d.number(), vector.n.number()) - i = ModExpNG_Operand(1, KEY_LENGTH) + vector = ModExpNG_TestVector() + core = ModExpNG_Core(i) + + s_known = pow(vector.m.number(), vector.d.number(), vector.n.number()) + x_mutated_known = pow(vector.x.number(), 2, vector.n.number()) y_mutated_known = pow(vector.y.number(), 2, vector.n.number()) @@ -936,67 +1141,97 @@ if __name__ == "__main__": # s_crt = sq + q_sr_qinv # unblind s # mutate blinding factors - - XF = worker.multiply(vector.x, vector.n_factor, vector.n, vector.n_coeff, n_num_words) # mod_multiply (mod n) - YF = worker.multiply(vector.y, vector.n_factor, vector.n, vector.n_coeff, n_num_words) # mod_multiply (mod n) - XMF = worker.multiply(XF, XF, vector.n, vector.n_coeff, n_num_words) # mod_multiply (mod n) - YMF = worker.multiply(YF, YF, vector.n, vector.n_coeff, n_num_words) # mod_multiply (mod n) + W = ModExpNG_WideBankEnum + N = ModExpNG_NarrowBankEnum + O = ModExpNG_CoreOutputEnum - XM = worker.multiply(i, XMF, vector.n, vector.n_coeff, n_num_words) # mod_multiply (mod n) - YM = worker.multiply(i, YMF, vector.n, vector.n_coeff, n_num_words) # mod_multiply (mod n) + core.bnk.crt_x.set_modulus(vector.n, vector.n_coeff) + core.bnk.crt_y.set_modulus(vector.n, vector.n_coeff) + + core.bnk.crt_x.set_operand(W.A, N.A, vector.x, vector.n_factor) + core.bnk.crt_y.set_operand(W.A, N.A, vector.y, vector.n_factor) + + core.bnk.crt_x.set_operand(W.E, N.E, vector.m, vector.m) + core.bnk.crt_y.set_operand(W.E, N.E, vector.m, vector.m) + + # | W | N + # --+-----+----------- + # A | + # B | ? | ? + # C | ? | ? + # D | ? | ? + # E | M | M + + # | A | B | C | D | E | + # +----------------+-------+---------+-------+---+ + # (YF, XF) =(Y,X)*N_FACTOR | X,Y ; N_FACTOR | ? | ? | ? | M | + core.multiply(W.A, N.A, W.B, N.B, n_num_words) # (YF, XF) =(Y,X)*N_FACTOR | X,Y ; N_FACTOR | XF,YF | ? | ? | M | + core.multiply(W.B, N.B, W.C, N.C, n_num_words, mode=(False, False)) # (YMF,XMF)=(YF*YF,XF*XF) | X,Y ; N_FACTOR | XF,YF | YMF,XMF | ? | M | + core.multiply(W.C, N.I, W.D, N.D, n_num_words) # (YM, XM) =(YMF,XMF)*1 | X,Y ; N_FACTOR | XF,YF | YMF,XMF | XM,YM | M | + core.simply_reduce(N.D, n_num_words) # | | | | | | + core.set_output(O.XM, core.bnk.crt_x, N.D) # | | | | | | + core.set_output(O.YM, core.bnk.crt_y, N.D) # | | | | | | + core.multiply(W.E, N.B, W.C, N.C, n_num_words, mode=(False, False)) # (MB, _) =(M*YF,M*XF) | X,Y ; N_FACTOR | XF,YF | MB,_ | XM,YM | M | + core.mirror_yx(W.C, N.C) # | X,Y ; N_FACTOR | XF,YF | MB,MB | XM,YM | M | + core.simply_reduce(N.C, n_num_words) # | | | | | | + + + XF = core.bnk.crt_x.ladder_x.wide._get_value(W.B) + YF = core.bnk.crt_y.ladder_x.wide._get_value(W.B) + + MB = core.bnk.crt_y.ladder_x.narrow._get_value(N.C) - MB = worker.multiply(vector.m, YF, vector.n, vector.n_coeff, n_num_words) # mod_multiply (mod n) + PMBZ = core.wrk.multiply(MB, None, vector.p, vector.p_coeff, pq_num_words, reduce_only=True) # mod_reduce (mod p) + QMBZ = core.wrk.multiply(MB, None, vector.q, vector.q_coeff, pq_num_words, reduce_only=True) # mod_reduce (mod q) - worker.reduce(MB) # just_reduce + mp_blind = core.wrk.multiply(PMBZ, vector.p_factor, vector.p, vector.p_coeff, pq_num_words) # mod_multiply + mq_blind = core.wrk.multiply(QMBZ, vector.q_factor, vector.q, vector.q_coeff, pq_num_words) # mod_multiply - mp_blind_inverse_factor = worker.multiply(MB, None, vector.p, vector.p_coeff, pq_num_words, reduce_only=True) # mod_reduce (mod p) - mq_blind_inverse_factor = worker.multiply(MB, None, vector.q, vector.q_coeff, pq_num_words, reduce_only=True) # mod_reduce (mod q) + mp_blind_factor = core.wrk.multiply(mp_blind, vector.p_factor, vector.p, vector.p_coeff, pq_num_words) # mod_multiply + mq_blind_factor = core.wrk.multiply(mq_blind, vector.q_factor, vector.q, vector.q_coeff, pq_num_words) # mod_multiply - mp_blind = worker.multiply(mp_blind_inverse_factor, vector.p_factor, vector.p, vector.p_coeff, pq_num_words) # mod_multiply - mq_blind = worker.multiply(mq_blind_inverse_factor, vector.q_factor, vector.q, vector.q_coeff, pq_num_words) # mod_multiply + ip_factor = core.wrk.multiply(i, vector.p_factor, vector.p, vector.p_coeff, pq_num_words) # mod_multiply + iq_factor = core.wrk.multiply(i, vector.q_factor, vector.q, vector.q_coeff, pq_num_words) # mod_multiply - mp_blind_factor = worker.multiply(mp_blind, vector.p_factor, vector.p, vector.p_coeff, pq_num_words) # mod_multiply - mq_blind_factor = worker.multiply(mq_blind, vector.q_factor, vector.q, vector.q_coeff, pq_num_words) # mod_multiply - ip_factor = worker.multiply(i, vector.p_factor, vector.p, vector.p_coeff, pq_num_words) # mod_multiply - iq_factor = worker.multiply(i, vector.q_factor, vector.q, vector.q_coeff, pq_num_words) # mod_multiply - sp_blind_factor = worker.exponentiate(ip_factor, mp_blind_factor, vector.dp, vector.p, vector.p_factor, vector.p_coeff, pq_num_words, dump_index=99, dump_mode="P") # mod_multiply - sq_blind_factor = worker.exponentiate(iq_factor, mq_blind_factor, vector.dq, vector.q, vector.q_factor, vector.q_coeff, pq_num_words, dump_index=99, dump_mode="Q") # mod_multiply + sp_blind_factor = core.wrk.exponentiate(ip_factor, mp_blind_factor, vector.dp, vector.p, vector.p_factor, vector.p_coeff, pq_num_words, dump_index=99, dump_mode="P") # mod_multiply + sq_blind_factor = core.wrk.exponentiate(iq_factor, mq_blind_factor, vector.dq, vector.q, vector.q_factor, vector.q_coeff, pq_num_words, dump_index=99, dump_mode="Q") # mod_multiply - SPB = worker.multiply(i, sp_blind_factor, vector.p, vector.p_coeff, pq_num_words) # mod_multiply - SQB = worker.multiply(i, sq_blind_factor, vector.q, vector.q_coeff, pq_num_words) # mod_multiply + SPB = core.wrk.multiply(i, sp_blind_factor, vector.p, vector.p_coeff, pq_num_words) # mod_multiply + SQB = core.wrk.multiply(i, sq_blind_factor, vector.q, vector.q_coeff, pq_num_words) # mod_multiply - worker.reduce(SPB) # just_reduce - worker.reduce(SQB) # just_reduce + core.wrk.reduce(SPB, len(SPB.words)) # just_reduce + core.wrk.reduce(SQB, len(SQB.words)) # just_reduce - sr_blind = worker.subtract(SPB, SQB, vector.p, pq_num_words) # mod_subtract + sr_blind = core.wrk.subtract(SPB, SQB, vector.p, pq_num_words) # mod_subtract - sr_qinv_blind_inverse_factor = worker.multiply(sr_blind, vector.qinv, vector.p, vector.p_coeff, pq_num_words) # mod_multiply - sr_qinv_blind = worker.multiply(sr_qinv_blind_inverse_factor, vector.p_factor, vector.p, vector.p_coeff, pq_num_words) # mod_multiply + sr_qinv_blind_inverse_factor = core.wrk.multiply(sr_blind, vector.qinv, vector.p, vector.p_coeff, pq_num_words) # mod_multiply + sr_qinv_blind = core.wrk.multiply(sr_qinv_blind_inverse_factor, vector.p_factor, vector.p, vector.p_coeff, pq_num_words) # mod_multiply - q_sr_qinv_blind = worker.multiply(vector.q, sr_qinv_blind, None, None, pq_num_words, multiply_only=True) # just_multiply + q_sr_qinv_blind = core.wrk.multiply(vector.q, sr_qinv_blind, None, None, pq_num_words, multiply_only=True) # just_multiply - worker.reduce(q_sr_qinv_blind) # just_reduce + core.wrk.reduce(q_sr_qinv_blind, n_num_words) # just_reduce - SB = worker.add(SQB, q_sr_qinv_blind, pq_num_words) # just_add + SB = core.wrk.add(SQB, q_sr_qinv_blind, pq_num_words) # just_add - S = worker.multiply(SB, XF, vector.n, vector.n_coeff, n_num_words) # mod_multiply + S = core.wrk.multiply(SB, XF, vector.n, vector.n_coeff, n_num_words) # mod_multiply - worker.reduce(S) # just_reduce - worker.reduce(XM) # just_reduce - worker.reduce(YM) # just_reduce + core.wrk.reduce(S, len(S.words)) # just_reduce # check - if S.number() != s_known: print("ERROR: s_crt_unblinded != s_known!") - else: print("s is OK") + XM = core.out.get_value(O.XM) + YM = core.out.get_value(O.YM) + + if S.number() != s_known: print("ERROR: s_crt_unblinded != s_known!") + else: print("s is OK") if XM.number() != x_mutated_known: print("ERROR: x_mutated != x_mutated_known!") - else: print("x_mutated is OK") + else: print("x_mutated is OK") if YM.number() != y_mutated_known: print("ERROR: y_mutated != y_mutated_known!") - else: print("y_mutated is OK") + else: print("y_mutated is OK") # |