From 0beee226e63b3a62ba32bc588e40eaeef01eac2b Mon Sep 17 00:00:00 2001 From: "Pavel V. Shatov (Meister)" Date: Mon, 19 Aug 2019 14:04:27 +0300 Subject: * More cleanup (got rid of .wide. and .narrow.) * Working microcode for non-CRT exponentiation (i.e. when only d is known) --- modexpng_fpga_model.py | 254 ++++++++++++++++++++++++++++++++----------------- 1 file changed, 169 insertions(+), 85 deletions(-) diff --git a/modexpng_fpga_model.py b/modexpng_fpga_model.py index 71a4b91..325f544 100644 --- a/modexpng_fpga_model.py +++ b/modexpng_fpga_model.py @@ -1085,7 +1085,7 @@ class ModExpNG_Core(): # copy from CRT_(X|Y).LADDER_X.NARROW to OUTPUT # def set_output_from_narrow(self, sel_output, bank_crt, sel_narrow): - self.out._set_value(sel_output, bank_crt.ladder_x.narrow._get_value(sel_narrow)) + self.out._set_value(sel_output, bank_crt.ladder_x._get_narrow(sel_narrow)) # # copy from INPUT to CRT_(X|Y).LADDER_{X,Y}.NARROW @@ -1102,7 +1102,7 @@ class ModExpNG_Core(): bank_crt.ladder_y._set_wide(sel_wide, self.inp._get_value(sel_input)) # - # copy from CRT_Y.LADDER_{X,Y).{WIDE,NARROW} to CRT_X.LADDER_{X,Y}.{WIDE,NARROW} + # copy from CRT_Y.LADDER_{X,Y}.{WIDE,NARROW} to CRT_X.LADDER_{X,Y}.{WIDE,NARROW} # def copy_crt_y2x(self, sel_wide, sel_narrow): @@ -1123,6 +1123,17 @@ class ModExpNG_Core(): self.bnk.crt_x.ladder_y._set_narrow(sel_narrow_out, self.bnk.crt_x.ladder_x._get_narrow(sel_narrow_in)) self.bnk.crt_y.ladder_y._set_narrow(sel_narrow_out, self.bnk.crt_y.ladder_x._get_narrow(sel_narrow_in)) + # + # copy from CRT_{X,Y}.LADDER_Y.{WIDE,NARROW} to CRT_{X,Y}.LADDER_X.{WIDE,NARROW} + # + def copy_ladders_y2x(self, sel_wide_in, sel_narrow_in, sel_wide_out, sel_narrow_out): + + self.bnk.crt_x.ladder_x._set_wide(sel_wide_out, self.bnk.crt_x.ladder_y._get_wide(sel_wide_in)) + self.bnk.crt_y.ladder_x._set_wide(sel_wide_out, self.bnk.crt_y.ladder_y._get_wide(sel_wide_in)) + + self.bnk.crt_x.ladder_x._set_narrow(sel_narrow_out, self.bnk.crt_x.ladder_y._get_narrow(sel_narrow_in)) + self.bnk.crt_y.ladder_x._set_narrow(sel_narrow_out, self.bnk.crt_y.ladder_y._get_narrow(sel_narrow_in)) + # # copy from CRT_{X,Y}.LADDER_X.{WIDE,NARROW} to CRT_{Y,X}.LADDER_Y.{WIDE,NARROW} # @@ -1143,23 +1154,23 @@ class ModExpNG_Core(): # def modular_multiply(self, sel_wide_in, sel_narrow_in, sel_wide_out, sel_narrow_out, num_words, mode=(True, True), d=False): - 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 = self.bnk.crt_x.ladder_x._get_wide(ModExpNG_WideBankEnum.N) + yn = self.bnk.crt_y.ladder_x._get_wide(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) + xn_coeff = self.bnk.crt_x.ladder_x._get_narrow(ModExpNG_NarrowBankEnum.N_COEFF) + yn_coeff = self.bnk.crt_y.ladder_x._get_narrow(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) + xxa = self.bnk.crt_x.ladder_x._get_wide(sel_wide_in) + xya = self.bnk.crt_x.ladder_y._get_wide(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) + yxa = self.bnk.crt_y.ladder_x._get_wide(sel_wide_in) + yya = self.bnk.crt_y.ladder_y._get_wide(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) + xxb = self.bnk.crt_x.ladder_x._get_narrow(sel_narrow_in) + xyb = self.bnk.crt_x.ladder_y._get_narrow(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) + yxb = self.bnk.crt_y.ladder_x._get_narrow(sel_narrow_in) + yyb = self.bnk.crt_y.ladder_y._get_narrow(sel_narrow_in) if not mode[0]: xb = xxb else: xb = xyb @@ -1189,22 +1200,22 @@ class ModExpNG_Core(): # def modular_subtract(self, sel_narrow_in, sel_narrow_out, sel_wide_out, num_words): - xa = self.bnk.crt_x.ladder_x.narrow._get_value(sel_narrow_in) - xb = self.bnk.crt_x.ladder_y.narrow._get_value(sel_narrow_in) - xn = self.bnk.crt_x.ladder_x.wide._get_value(ModExpNG_WideBankEnum.N) + xa = self.bnk.crt_x.ladder_x._get_narrow(sel_narrow_in) + xb = self.bnk.crt_x.ladder_y._get_narrow(sel_narrow_in) + xn = self.bnk.crt_x.ladder_x._get_wide(ModExpNG_WideBankEnum.N) - ya = self.bnk.crt_y.ladder_x.narrow._get_value(sel_narrow_in) - yb = self.bnk.crt_y.ladder_y.narrow._get_value(sel_narrow_in) - yn = self.bnk.crt_y.ladder_x.wide._get_value(ModExpNG_WideBankEnum.N) + ya = self.bnk.crt_y.ladder_x._get_narrow(sel_narrow_in) + yb = self.bnk.crt_y.ladder_y._get_narrow(sel_narrow_in) + yn = self.bnk.crt_y.ladder_x._get_wide(ModExpNG_WideBankEnum.N) xd = self.wrk.serial_subtract_modular(xa, xb, xn, num_words) yd = self.wrk.serial_subtract_modular(ya, yb, yn, num_words) - self.bnk.crt_x.ladder_x.narrow._set_value(sel_narrow_out, xd) - self.bnk.crt_y.ladder_x.narrow._set_value(sel_narrow_out, yd) + self.bnk.crt_x.ladder_x._set_narrow(sel_narrow_out, xd) + self.bnk.crt_y.ladder_x._set_narrow(sel_narrow_out, yd) - self.bnk.crt_x.ladder_x.wide._set_value(sel_wide_out, xd) - self.bnk.crt_y.ladder_x.wide._set_value(sel_wide_out, yd) + self.bnk.crt_x.ladder_x._set_wide(sel_wide_out, xd) + self.bnk.crt_y.ladder_x._set_wide(sel_wide_out, yd) # # modular reduce sel_narrow_in @@ -1212,27 +1223,27 @@ class ModExpNG_Core(): # def modular_reduce(self, sel_narrow_in, sel_wide_out, sel_narrow_out, num_words): - 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 = self.bnk.crt_x.ladder_x._get_wide(ModExpNG_WideBankEnum.N) + yn = self.bnk.crt_y.ladder_x._get_wide(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) + xn_coeff = self.bnk.crt_x.ladder_x._get_narrow(ModExpNG_NarrowBankEnum.N_COEFF) + yn_coeff = self.bnk.crt_y.ladder_x._get_narrow(ModExpNG_NarrowBankEnum.N_COEFF) - xb = self.bnk.crt_x.ladder_x.narrow._get_value(sel_narrow_in) - yb = self.bnk.crt_y.ladder_x.narrow._get_value(sel_narrow_in) + xb = self.bnk.crt_x.ladder_x._get_narrow(sel_narrow_in) + yb = self.bnk.crt_y.ladder_x._get_narrow(sel_narrow_in) xp = self.wrk.multipurpose_multiply(None, xb, xn, xn_coeff, num_words, reduce_only=True) yp = self.wrk.multipurpose_multiply(None, yb, yn, yn_coeff, num_words, reduce_only=True) - self.bnk.crt_x.ladder_x.wide._set_value(sel_wide_out, xp) - self.bnk.crt_x.ladder_y.wide._set_value(sel_wide_out, xp) - self.bnk.crt_y.ladder_x.wide._set_value(sel_wide_out, yp) - self.bnk.crt_y.ladder_y.wide._set_value(sel_wide_out, yp) + self.bnk.crt_x.ladder_x._set_wide(sel_wide_out, xp) + self.bnk.crt_x.ladder_y._set_wide(sel_wide_out, xp) + self.bnk.crt_y.ladder_x._set_wide(sel_wide_out, yp) + self.bnk.crt_y.ladder_y._set_wide(sel_wide_out, yp) - self.bnk.crt_x.ladder_x.narrow._set_value(sel_narrow_out, xp) - self.bnk.crt_x.ladder_y.narrow._set_value(sel_narrow_out, xp) - self.bnk.crt_y.ladder_x.narrow._set_value(sel_narrow_out, yp) - self.bnk.crt_y.ladder_y.narrow._set_value(sel_narrow_out, yp) + self.bnk.crt_x.ladder_x._set_narrow(sel_narrow_out, xp) + self.bnk.crt_x.ladder_y._set_narrow(sel_narrow_out, xp) + self.bnk.crt_y.ladder_x._set_narrow(sel_narrow_out, yp) + self.bnk.crt_y.ladder_y._set_narrow(sel_narrow_out, yp) # # propagate carries (convert to non-redundant representation) content in sel_narrow @@ -1274,20 +1285,20 @@ class ModExpNG_Core(): # def regular_multiply(self, sel_wide_in, sel_narrow_in, num_words): - 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 = self.bnk.crt_x.ladder_x._get_wide(ModExpNG_WideBankEnum.N) + yn = self.bnk.crt_y.ladder_x._get_wide(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) + xn_coeff = self.bnk.crt_x.ladder_x._get_narrow(ModExpNG_NarrowBankEnum.N_COEFF) + yn_coeff = self.bnk.crt_y.ladder_x._get_narrow(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) + xxa = self.bnk.crt_x.ladder_x._get_wide(sel_wide_in) + xya = self.bnk.crt_x.ladder_y._get_wide(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) + yxa = self.bnk.crt_y.ladder_x._get_wide(sel_wide_in) + yya = self.bnk.crt_y.ladder_y._get_wide(sel_wide_in) - xb = self.bnk.crt_x.ladder_x.narrow._get_value(sel_narrow_in) - yb = self.bnk.crt_y.ladder_x.narrow._get_value(sel_narrow_in) + xb = self.bnk.crt_x.ladder_x._get_narrow(sel_narrow_in) + yb = self.bnk.crt_y.ladder_x._get_narrow(sel_narrow_in) xxp = self.wrk.multipurpose_multiply(xxa, xb, None, None, num_words, multiply_only=True) xyp = self.wrk.multipurpose_multiply(xya, xb, None, None, num_words, multiply_only=True) @@ -1307,15 +1318,15 @@ class ModExpNG_Core(): yyp_lsb = yyp.lower_half() yyp_msb = yyp.upper_half() - self.bnk.crt_x.ladder_x.wide._set_value(ModExpNG_WideBankEnum.L, xxp_lsb) - self.bnk.crt_x.ladder_y.wide._set_value(ModExpNG_WideBankEnum.L, xyp_lsb) - self.bnk.crt_y.ladder_x.wide._set_value(ModExpNG_WideBankEnum.L, yxp_lsb) - self.bnk.crt_y.ladder_y.wide._set_value(ModExpNG_WideBankEnum.L, yyp_lsb) + self.bnk.crt_x.ladder_x._set_wide(ModExpNG_WideBankEnum.L, xxp_lsb) + self.bnk.crt_x.ladder_y._set_wide(ModExpNG_WideBankEnum.L, xyp_lsb) + self.bnk.crt_y.ladder_x._set_wide(ModExpNG_WideBankEnum.L, yxp_lsb) + self.bnk.crt_y.ladder_y._set_wide(ModExpNG_WideBankEnum.L, yyp_lsb) - self.bnk.crt_x.ladder_x.wide._set_value(ModExpNG_WideBankEnum.H, xxp_msb) - self.bnk.crt_x.ladder_y.wide._set_value(ModExpNG_WideBankEnum.H, xyp_msb) - self.bnk.crt_y.ladder_x.wide._set_value(ModExpNG_WideBankEnum.H, yxp_msb) - self.bnk.crt_y.ladder_y.wide._set_value(ModExpNG_WideBankEnum.H, yyp_msb) + self.bnk.crt_x.ladder_x._set_wide(ModExpNG_WideBankEnum.H, xxp_msb) + self.bnk.crt_x.ladder_y._set_wide(ModExpNG_WideBankEnum.H, xyp_msb) + self.bnk.crt_y.ladder_x._set_wide(ModExpNG_WideBankEnum.H, yxp_msb) + self.bnk.crt_y.ladder_y._set_wide(ModExpNG_WideBankEnum.H, yyp_msb) # # adds sel_narrow_a_in to sel_narrow_b_in @@ -1345,7 +1356,7 @@ class ModExpNG_Core(): # # dump working variables before ladder step # - def dump_before_step_crt(self, pq, m): + def dump_before_step_using_crt(self, pq, m): print("num_words = %d" % pq) print("\rladder_mode_x = %d" % m[0]) print("\rladder_mode_y = %d" % m[1]) @@ -1361,7 +1372,7 @@ class ModExpNG_Core(): # # dump working variables after ladder step # - def dump_after_step_crt(self): + def dump_after_step_using_crt(self): self.bnk.crt_x.ladder_x._get_narrow(N.C).format_verilog_concat("X_X") self.bnk.crt_x.ladder_y._get_narrow(N.C).format_verilog_concat("X_Y") self.bnk.crt_y.ladder_x._get_narrow(N.C).format_verilog_concat("Y_X") @@ -1429,6 +1440,17 @@ def get_ladder_mode_using_crt(v, bit): return (bit_value_p, bit_value_q) +# +# get current ladder mode based on private exponent's bit +# +def get_ladder_mode_without_crt(v, bit): + + bit_value_d = (v.d.number() & (1 << bit)) >> bit + + bit_value_d = bit_value_d > 0 + + return (not bit_value_d, bit_value_d) + # # print current exponentiation progress # @@ -1487,7 +1509,7 @@ def sign_using_crt(): c.set_output_from_narrow(O.XM, c.bnk.crt_x, N.D) # | [XY] / N_FACTOR | [XY]F | [XY]YM | [XY]M | M | c.set_output_from_narrow(O.YM, c.bnk.crt_y, N.D) # | [XY] / N_FACTOR | [XY]F | [XY]YM | [XY]M | M | # +------------------------+-------+------------------+---------+-----------+ - c.modular_multiply(W.E, N.B, W.C, N.C, n) # | [XY] / N_FACTOR | [XY]F | [XY]MB | [XY]M | M | [XY]MB = M*[XY]F + c.modular_multiply(W.E, N.B, W.C, N.C, n) # | [XY] / N_FACTOR | [XY]F | [XY]MB | [XY]M | M | [XY]MB = M * [XY]F # +------------------------+-------+------------------+---------+-----------+ c.propagate_carries(N.C, n_num_words) # | [XY] / N_FACTOR | [XY]F | [XY]MB | [XY]M | M | # +------------------------+-------+------------------+---------+-----------+ @@ -1508,7 +1530,6 @@ def sign_using_crt(): c.set_narrow_from_input(c.bnk.crt_x, N.E, I.QINV) # | [PQ]_FACTOR | [XY]F | YMB | [XY]M | QINV | # +------------------------+-------+------------------+---------+-----------+ c.modular_reduce(N.C, W.D, N.D, pq) # | [PQ]_FACTOR | [XY]F | YMB | [PQ]MBZ | QINV | [PQ]MBZ = YMB mod [PQ] - # +------------------------+-------+------------------+---------+-----------+ c.modular_multiply(W.D, N.A, W.C, N.C, pq) # | [PQ]_FACTOR | [XY]F | [PQ]MB | [PQ]MBZ | QINV | [PQ]MB = [PQ]MBZ * [PQ]_FACTOR c.modular_multiply(W.C, N.A, W.D, N.D, pq) # | [PQ]_FACTOR | [XY]F | [PQ]MB | [PQ]MBF | QINV | [PQ]MBF = [PQ]MB * [PQ]_FACTOR c.modular_multiply(W.A, N.I, W.C, N.C, pq) # | [PQ]_FACTOR | [XY]F | [PQ]IF | [PQ]MBF | QINV | [PQ]IF = 1 * [PQ]_FACTOR @@ -1526,11 +1547,11 @@ def sign_using_crt(): # | | | | | | if dbg: # | | | | | | if FORCE_OVERFLOW: c._force_overflow(c.bnk.crt_x, N.C) # | | | | | | - if DUMP_VECTORS: c.dump_before_step_crt(pq, m) # | | | | | | + if DUMP_VECTORS: c.dump_before_step_using_crt(pq, m) # | | | | | | # +------------------------+-------+------------------+---------+-----------+ c.modular_multiply(W.C, N.C, W.C, N.C, pq, mode=m, d=dbg) # | [PQ]_FACTOR | [XY]F | [PQ]SBF | [PQ]MBF | QINV | # +------------------------+-------+------------------+---------+-----------+ - if dbg and DUMP_VECTORS: c.dump_after_step_crt() # | | | | | | + if dbg and DUMP_VECTORS: c.dump_after_step_using_crt() # | | | | | | print_ladder_progress(bit, pq) # | | | | | | # | | | | | | ######################### # | | | | | | @@ -1576,6 +1597,87 @@ def sign_using_crt(): # +------------------------+-------+------------------+---------+-----------+ c.set_output_from_narrow(O.S, c.bnk.crt_x, N.A) # | S | | | | | # +------------------------+-------+------------------+---------+-----------+ + +# +# try to exponentiate using only half of the quad-multiplier (one dual-ladder core) +# +def sign_without_crt(): + + c = core + v = vector + n = n_num_words + + ff = (False, False) + + c.set_wide_from_input (c.bnk.crt_x, W.N, I.N) + c.set_wide_from_input (c.bnk.crt_y, W.N, I.N) + c.set_wide_from_input (c.bnk.crt_x, W.A, I.X) + c.set_wide_from_input (c.bnk.crt_y, W.A, I.Y) + c.set_wide_from_input (c.bnk.crt_x, W.E, I.M) + c.set_wide_from_input (c.bnk.crt_y, W.E, I.M) + + c.set_narrow_from_input (c.bnk.crt_x, N.N_COEFF, I.N_COEFF) + c.set_narrow_from_input (c.bnk.crt_y, N.N_COEFF, I.N_COEFF) + c.set_narrow_from_input (c.bnk.crt_x, N.A, I.N_FACTOR) + c.set_narrow_from_input (c.bnk.crt_y, N.A, I.N_FACTOR) + c.set_narrow_from_input (c.bnk.crt_x, N.E, I.M) + c.set_narrow_from_input (c.bnk.crt_y, N.E, I.M) + + c.modular_multiply(W.A, N.A, W.B, N.B, n) # [XY]F = [XY] * N_FACTOR + c.modular_multiply(W.B, N.B, W.C, N.C, n, mode=ff) # [XY]MF = [XY]F * [XY]F + c.modular_multiply(W.C, N.I, W.D, N.D, n) # [XY]M = [XY]MF * 1 + + c.propagate_carries(N.D, n) + + c.set_output_from_narrow(O.XM, c.bnk.crt_x, N.D) + c.set_output_from_narrow(O.YM, c.bnk.crt_y, N.D) + + c.modular_multiply(W.E, N.B, W.C, N.C, n) # [XY]MB = M * [XY]F + + XF = c.bnk.crt_x.ladder_x._get_narrow(N.B) + + c.set_wide_from_input(c.bnk.crt_x, W.A, I.N_FACTOR) + c.set_wide_from_input(c.bnk.crt_y, W.A, I.N_FACTOR) + + c.modular_multiply(W.C, N.A, W.D, N.D, n) # MBF = MB * N_FACTOR + c.modular_multiply(W.A, N.I, W.C, N.C, n) # IF = 1 * N_FACTOR + + c.copy_ladders_x2y(W.D, N.D, W.C, N.C) + + ########################### + # Begin Montgomery Ladder # + ########################### + + for bit in range(_WORD_WIDTH * n - 1, -1, -1): + + m = get_ladder_mode_without_crt(v, bit) + dbg = bit == DUMP_LADDER_INDEX + + if dbg: + if FORCE_OVERFLOW: c._force_overflow(c.bnk.crt_x, N.C) + if DUMP_VECTORS: c.dump_before_step_without_crt(n, m) + + c.modular_multiply(W.C, N.C, W.C, N.C, n, mode=m, d=dbg) + + if dbg and DUMP_VECTORS: c.dump_after_step_without_crt() + print_ladder_progress(bit, n) + + ######################### + # End Montgomery Ladder # + ######################### + + c.cross_ladders_x2y(W.B, N.B, W.B, N.B) + + c.modular_multiply(W.C, N.I, W.D, N.D, n) # SB = SBF * 1 + c.modular_multiply(W.B, N.D, W.A, N.A, n, mode=ff) # S = XF * SB + + c.copy_ladders_y2x(W.A, N.A, W.B, N.B) + + c.propagate_carries(N.B, n) + + c.set_output_from_narrow(O.S, c.bnk.crt_y, N.B) + + # # main() # @@ -1627,35 +1729,17 @@ if __name__ == "__main__": xm_known = pow(vector.x.number(), 2, vector.n.number()) ym_known = pow(vector.y.number(), 2, vector.n.number()) - # sign using CRT + # sign using CRT and check print("Signing using CRT...") sign_using_crt() compare_signature() - # sign without CRT - # ... + # sign without CRT and check + print("Signing without CRT...") + sign_without_crt() + compare_signature() # # End-of-File # - - - - # bring one into Montgomery domain (glue 2**r to one) - # bring blinding coefficients into Montgomery domain (glue 2**(2*r) to x and y) - # blind message - # convert message to non-redundant representation - # first reduce message, this glues 2**-r to the message as a side effect - # unglue 2**-r from message by gluing 2**r to it to compensate - # bring message into Montgomery domain (glue 2**r to message) - # do "easier" exponentiations - # return "easier" parts from Montgomery domain (unglue 2**r from result) - # do the "Garner's formula" part - # r = sp - sq mod p - # sr_qinv = sr * qinv mod p - # q_sr_qinv = q * sr_qinv - # s_crt = sq + q_sr_qinv - # unblind s - # mutate blinding factors - -- cgit v1.2.3