aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--modexpng_fpga_model.py335
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")
#