1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
|
"""Provides functions for computing various scalar representations (like NAF, or different bases)."""
from typing import List
from itertools import dropwhile
from public import public
@public
def convert_base(i: int, base: int) -> List[int]:
"""
Convert an integer to base.
:param i: The scalar.
:param base: The base.
:return: The resulting digit list (little-endian).
"""
if i == 0:
return [0]
res = []
while i:
i, r = divmod(i, base)
res.append(r)
return res
@public
def sliding_window_ltr(i: int, w: int) -> List[int]:
"""
Compute the sliding-window left-to-right form.
From [BBG+17]_.
:param i: The scalar.
:param w: The width.
:return: The sliding-window LTR form.
"""
result: List[int] = []
b = i.bit_length() - 1
while b >= 0:
val = i & (1 << b)
if not val:
result.append(0)
b -= 1
else:
u = 0
for v in range(1, w + 1):
if b + 1 < v:
break
mask = ((2**v) - 1) << (b - v + 1)
c = (i & mask) >> (b - v + 1)
if c & 1:
u = c
k = u.bit_length()
result.extend([0] * (k - 1))
result.append(u)
b -= k
return list(dropwhile(lambda x: x == 0, result))
@public
def sliding_window_rtl(i: int, w: int) -> List[int]:
"""
Compute the sliding-window right-to-left form.
From [BBG+17]_.
:param i: The scalar.
:param w: The width.
:return: The sliding-window RTL form.
"""
result: List[int] = []
while i >= 1:
val = i & 1
if not val:
result = [0] + result
i >>= 1
else:
window = i & ((2**w) - 1)
result = ([0] * (w - 1)) + [window] + result
i >>= w
return list(dropwhile(lambda x: x == 0, result))
@public
def wnaf(k: int, w: int) -> List[int]:
"""
Compute width `w` NAF (Non-Adjacent Form) of the scalar `k`.
Algorithm 9.35 from [GECC]_, Algorithm 9.20 from [HEHCC]_.
.. note::
According to HEHCC this is actually not unique
A left-to-right variant to compute an NAFw expansion of an integer can be found both
in [AVA 2005a] and in [MUST 2005]. The result may differ from the expansion produced
by Algorithm 9.20 but they have the same digit set and the same optimal weight.
According to GECC it is.
:param k: The scalar.
:param w: The width.
:return: The NAF.
"""
half_width = 2 ** (w - 1)
full_width = half_width * 2
def mods(val: int) -> int:
val_mod = val % full_width
if val_mod > half_width:
val_mod -= full_width
return val_mod
result: List[int] = []
while k >= 1:
if k & 1:
k_val = mods(k)
result.insert(0, k_val)
k -= k_val
else:
result.insert(0, 0)
k >>= 1
return result
@public
def naf(k: int) -> List[int]:
"""
Compute the NAF (Non-Adjacent Form) of the scalar `k`.
Properties ([GECC]_ 3.29):
a) k has a unique NAF denoted NAF(k).
b) NAF(k) has the fewest non-zero digits of any signed digit representation of k.
c) The length of NAF(k) is at most one more than the bit-length of k.
d) If the length of NAF(k) is l, then $2^l / 3 < k < 2^(l+1) / 3$.
e) The average density of non-zero digits among all NAFs of length l is approximately 1/3.
:param k: The scalar.
:return: The NAF.
"""
return wnaf(k, 2)
@public
def booth(k: int) -> List[int]:
"""
Original Booth binary recoding, from [B51]_.
:param k: The scalar to recode.
:return: The recoded list of digits (0, 1, -1), little-endian.
"""
res = []
for i in range(k.bit_length()):
a_i = (k >> i) & 1
b_i = (k >> (i + 1)) & 1
res.append(a_i - b_i)
res.insert(0, -(k & 1))
return res
@public
def booth_word(digit: int, w: int) -> int:
"""
Modified Booth recoding, from [M61]_ and BoringSSL NIST impl.
Needs `w+1` bits of scalar in digit, but the one bit is overlapping (window size is `w`).
:param digit:
:param w:
:return:
"""
if digit.bit_length() > (w + 1):
raise ValueError("Invalid digit, cannot be larger than w + 1 bits.")
s = ~((digit >> w) - 1)
d = (1 << (w + 1)) - digit - 1
d = (d & s) | (digit & ~s)
d = (d >> 1) + (d & 1)
return -d if s else d
@public
def booth_window(k: int, w: int, blen: int) -> List[int]:
"""
Recode a whole scalar using Booth recoding as in BoringSSL.
:param k: The scalar.
:param w: The window size.
:param blen: The bit-length of the group.
:return: The big-endian recoding
"""
mask = (1 << (w + 1)) - 1
res = []
for i in range(blen + (w - (blen % w) - 1), -1, -w):
if i >= w:
d = (k >> (i - w)) & mask
else:
d = (k << (w - i)) & mask
res.append(booth_word(d, w))
return res
|
