[Cryptech-Commits] [core/math/modexpng] 17/92: Intermediate version to fix recombinaton overflow bug.
git at cryptech.is
git at cryptech.is
Sat Mar 14 18:18:56 UTC 2020
This is an automated email from the git hooks/post-receive script.
paul at psgd.org pushed a commit to branch master
in repository core/math/modexpng.
commit 345be7560678db312767ae3a798123d7feb86003
Author: Pavel V. Shatov (Meister) <meisterpaul1 at yandex.ru>
AuthorDate: Thu Apr 4 13:52:07 2019 +0300
Intermediate version to fix recombinaton overflow bug.
---
modexpng_fpga_model.py | 119 ++++++++++++++++++++++++++++++++++++++-----------
1 file changed, 92 insertions(+), 27 deletions(-)
diff --git a/modexpng_fpga_model.py b/modexpng_fpga_model.py
index 0726eaa..d33f314 100644
--- a/modexpng_fpga_model.py
+++ b/modexpng_fpga_model.py
@@ -79,7 +79,7 @@ DUMP_INDICES = False
DUMP_MACS_CLEARING = False
DUMP_MACS_ACCUMULATION = False
DUMP_MULT_PARTS = False
-DUMP_RCMB = True
+DUMP_RCMB = False
#
@@ -119,7 +119,7 @@ class ModExpNG_Operand():
for i in range(count):
# word must not exceed 17 bits
- if words[i] >= (2 ** (_WORD_WIDTH + 1)):
+ if words[i] >= (2 ** (_WORD_WIDTH + 2)):
raise Exception("Word is too large!")
self.words = words
@@ -274,13 +274,12 @@ class ModExpNG_PartRecombinator():
# merge upper half adding the two overlapping words
for x in range(ab_num_words):
next_word = words_msb[x]
- if x < 2:
+ if x < 2:
next_word += words_lsb[x + ab_num_words]
words.append(next_word)
return words
-
def recombine_triangle(self, parts, ab_num_words, dump):
# empty result so far
@@ -303,21 +302,62 @@ class ModExpNG_PartRecombinator():
def recombine_rectangle(self, parts, ab_num_words, dump):
# empty result so far
+ words_lsb = list() # n words
+ words_msb = list() # n+1 words
+
+ # recombine the lower half (n parts)
+ # the first tick produces null result, the last part
+ # produces three words and needs two extra ticks
+ self._flush_pipeline(dump)
+ for i in range(ab_num_words + 1 + 2):
+ next_part = parts[i] if i < ab_num_words else 0
+ next_word = self._push_pipeline(next_part, dump)
+
+ if i > 0:
+ words_lsb.append(next_word)
+
+ # recombine the upper half (n parts)
+ # the first tick produces null result, the last part
+ # produces two words and needs an extra tick
+ self._flush_pipeline(dump)
+ for i in range(ab_num_words + 2):
+ next_part = parts[i + ab_num_words] if i < ab_num_words else 0
+ next_word = self._push_pipeline(next_part, dump)
+
+ if i > 0:
+ words_msb.append(next_word)
+
+ # merge words
words = list()
+ # merge lower half
+ for x in range(ab_num_words):
+ next_word = words_lsb[x]
+ words.append(next_word)
+
+ # merge upper half adding the two overlapping words
+ for x in range(ab_num_words + 1):
+ next_word = words_msb[x]
+ if x < 2:
+ next_word += words_lsb[x + ab_num_words]
+ words.append(next_word)
+
+ return words
+
+
# flush recombinator pipeline
- self._flush_pipeline(dump)
+ #self._flush_pipeline(dump)
# the first tick produces null result, the last part produces
# two words, so we need 2 * n + 2 ticks total and should only save
# the result word during the last 2 * n + 1 ticks
- for i in range(2 * ab_num_words + 2):
+ #for i in range(2 * ab_num_words + 2):
- next_part = parts[i] if i < (2 * ab_num_words) else 0
- next_word = self._push_pipeline(next_part, dump)
+ #next_part = parts[i] if i < (2 * ab_num_words) else 0
+ #next_word = self._push_pipeline(next_part, dump)
- if i > 0:
- words.append(next_word)
+ #if i > 0:
+ #words.append(next_word)
return words
@@ -369,11 +409,11 @@ class ModExpNG_WordMultiplier():
if b > 0xFFFF:
self._b_seen_17 = True
- if a > 0x1FFFF:
- raise("a > 0x1FFFF!")
+ if a > 0x3FFFF:
+ raise Exception("a > 0x3FFFF!")
if b > 0x1FFFF:
- raise("b > 0x1FFFF!")
+ raise Exception("b > 0x1FFFF!")
p = a * b
self._macs[x] += p
@@ -451,6 +491,8 @@ class ModExpNG_WordMultiplier():
for col in range(num_cols):
+ bt_carry = 0
+
for t in range(ab_num_words):
# take care of indices
@@ -469,7 +511,10 @@ class ModExpNG_WordMultiplier():
if dump and DUMP_INDICES: self._dump_indices(t, col)
# current b-word
- bt = b_narrow.words[t]
+ bt = b_narrow.words[t] + bt_carry
+ bt_carry = bt >> _WORD_WIDTH
+ bt &= 0xffff
+
# multiply by a-words
for x in range(NUM_MULTS):
@@ -659,6 +704,8 @@ class ModExpNG_LowlevelOperator():
class ModExpNG_Worker():
+ max_zzz = 0
+
def __init__(self):
self.recombinator = ModExpNG_PartRecombinator()
self.multiplier = ModExpNG_WordMultiplier()
@@ -764,26 +811,40 @@ class ModExpNG_Worker():
m = ModExpNG_Operand(None, 2 * ab_num_words + 1, m_words)
# 4.
- r_xwords = list()
- for i in range(2*ab_num_words):
- r_xwords.append(ab.words[i] + m.words[i])
-
- r_xwords.append(m.words[2 * ab_num_words])
-
cy = 0
- for i in range(ab_num_words+1):
- s = r_xwords[i] + cy
+ for i in range(ab_num_words + 1):
+ s = ab.words[i] + m.words[i] + cy
cy = s >> 16
-
+
R = list()
for i in range(ab_num_words):
R.append(0)
- R[0] += cy # !!!
-
+ R[0] = cy # !!! (cy is 2 bits, i.e. 0..3)
+
+ if dump:
+ if ab.words[ab_num_words + 2] > 0:
+ ab.words[ab_num_words + 2] -= 1
+ ab.words[ab_num_words + 1] += 0x10000
+ if m.words[ab_num_words + 2] > 0:
+ m.words[ab_num_words + 2] -= 1
+ m.words[ab_num_words + 1] += 0x10000
+
for i in range(ab_num_words):
- R[i] += r_xwords[ab_num_words + i + 1]
-
+ ab_word = ab.words[ab_num_words + i + 1] if i < (ab_num_words - 1) else 0
+ m_word = m.words[ab_num_words + i + 1]
+
+ R[i] += ab_word + m_word
+
+ #if i == 0:
+ #if R[i] > self.max_zzz:
+ #self.max_zzz = R[i]
+ #print("self.max_zzz = %05x" % R[i])
+ #if R[i] > 0x1ffff:
+ #sys.exit(123)
+
+
+
return ModExpNG_Operand(None, ab_num_words, R)
def reduce(self, a):
@@ -816,6 +877,7 @@ if __name__ == "__main__":
x_mutated_known = pow(vector.x.number(), 2, vector.n.number())
y_mutated_known = pow(vector.y.number(), 2, vector.n.number())
+
# 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
@@ -864,6 +926,7 @@ if __name__ == "__main__":
else:
print("17-bit wide B's not detected.")
+
sp_blind = worker.multiply(i, sp_blind_factor, vector.p, vector.p_coeff, pq_num_words)
sq_blind = worker.multiply(i, sq_blind_factor, vector.q, vector.q_coeff, pq_num_words)
@@ -874,6 +937,8 @@ if __name__ == "__main__":
sr_qinv_blind = worker.multiply(sr_qinv_blind_inverse_factor, vector.p_factor, vector.p, vector.p_coeff, pq_num_words)
q_sr_qinv_blind = worker.multiply(vector.q, sr_qinv_blind, None, None, pq_num_words, multiply_only=True)
+ worker.reduce(q_sr_qinv_blind)
+
s_crt_blinded = worker.add(sq_blind, q_sr_qinv_blind, pq_num_words)
s_crt_unblinded = worker.multiply(s_crt_blinded, x_factor, vector.n, vector.n_coeff, n_num_words)
More information about the Commits
mailing list