Page 327 - Hardware Implementation of Finite-Field Arithmetic

An Example of Application—Elliptic Curve Cryptography 307

if a = 0, then a’ = b + a/2 = b +⎣a/2⎦ and b’ = − ⎣a/2⎦
0
if a = 1 and a ⊕ b = 0, then a’ = b + (a − 1)/2 = b +⎣a/2⎦ and
0 1 0
b’ = − ⎣a/2⎦
if a = 1 and a ⊕ b = 1, then a’ = b + (a + 1)/2 = b + ⎣a/2⎦+ 1
0 1 0
and b’ = − ( ⎣a/2⎦+ 1)
The corresponding modified algorithm, in which div_2(a)
computes ⎣a/2⎦, is the following.

Algorithm 10.10—Point multiplication (Q = kP), Koblitz curve, s-ary
representation of k

Q_infinity := true; a := k; b := 0;
while ((a /= 0) or (b /= 0)) loop
a_div_2 := div_2(a);
if a mod 2 = 0 then
a := b + a_div_2; b := -a_div_2;
elsif (a/2) mod 2 = b mod 2 then
if Q_infinity then xQ := xP; yQ := yP;
Q_infinity := false;
else point_addition(xP, yP, xQ, yQ, f, new_xQ,
new_yQ); xQ := new_xQ; yQ := new_yQ;
end if;
a := b + a_div_2; b := -a_div_2;
else
if Q_infinity then xQ := xP; yQ := add(xP, yP);
Q_infinity := false;
else point_addition(xP, add(xP, yP), xQ, yQ, f,
new_xQ, new_yQ); xQ := new_xQ; yQ := new_yQ;
end if;
a := b + a_div_2 + 1; b := -(a_div_2 + 1);
end if;
xP := product_mod_f(xP, xP, f); yP := product_mod_f
(yP, yP, f);
end loop;

An executable Ada file frobenius_point_multiplication3.adb, inclu-
ding Algorithm 10.10, is available at www.arithmetic-circuits.org.
In order to implement the preceding algorithm, an upper bound
of a and b must be known. It can be demonstrated that

m
− 2 ≤ a < 2 and − 2 m − 1 ≤ b < 2 m − 1 (10.73)
m
so that a is an (m + 1)-bit 2s complement number and b an m-bit 2s
complement number. A datapath for executing Algorithm 10.10 is
shown in Fig. 10.2.