Cryptography Reference
In-Depth Information
•
Let
e
= 1896837 = (111001111000110000101)
2
, and let
l
=3
. Beginning
with the least-significant binary digit,
e
is decomposed as follows:
e
= 111 001 111 00 011 0000 101
.
The choice
l
=4
leads to the following decomposition of
e
:
e
= 111 00 1111 0 0011 000 0101
.
The
2
k
-ary exponentiation considered above yields, for example for
k
=2
,
the following decomposition:
e
=
0111
00
11 11
00
01 10
00
01 01
.
The window decomposition of
e
for
l
=3
contains five
1
-windows, while
that for
l
=4
has only four, and for each the same number of additional
multiplications is required. On the other hand, the
2
2
-ary decomposition
of
e
contains eight
1
-windows, requires double the number of additional
multiplications compared to the case
l
=4
, and is thus significantly less
favorable.
•
The same procedure, but beginning with the most-significant binary digit,
yields for
l
=4
and
e
= 123
the decomposition
e
= 1110 0 1111 000 1100 00 101
,
likewise with four
1
-windows, which, as already established above, are not
all odd.
Finally, then, exponentiation with a window decomposition of the exponent
can be formalized by the following algorithm. Both directions of window
decomposition are taken into account.
Algorithm for exponentiation
a
e
mod
m
with the representation of
e
in
windows of (maximal) length
l
for odd 1-windows
1.
Decompose the exponent
e
into
0
-and
1
-windows
(
ω
k
−
1
...ω
0
)
of
respective lengths
l
k
−
1
,...,l
0
.
2.
Calculate and store
a
3
mod
m
,
a
5
mod
m
,
a
7
mod
m
,
...
,
a
2
l
−
1
mod
m
.
3.
Set
p ← a
ω
k
−
1
mod
m
and
i ← k −
2
.
4.
Set
p ← p
l
i
mod
m
.
=0
, set
p ← pa
ω
i
mod
m
.
5.
If
ω
i
6.
Set
i ← i −
1
;if
i ≥
0
, go to step 4.
7.
Output
p
.
