Page 323 - Hardware Implementation of Finite-Field Arithmetic

An Example of Application—Elliptic Curve Cryptography 303

i
and if r τ i − 1 (P) + r τ i − 2 (P) + . . . + r τ(P) + r P = − r τ (P), then
i − 1 i − 2 1 0 i
r τ (P) + r τ i − 1 (P) + r τ i − 2 (P) + . . . + r τ(P) + r P =∞ (10.68)
i
i i − 1 i − 2 1 0
If k is smaller than the order of P, it can be shown that the preced-
ing Eqs. (10.67) and (10.68) are never satisfied unless r = r = . . . = r =
i i − 1 1
r = 0. Thus, if Q ≠∞ the values of Q + P and Q − P are computed with
0
Eqs. (10.15) and (10.16).
Assume that the following procedure, computing x and y
3 3
according to Eq. (10.16), has been previously defined:
procedure point_addition(x1, y1, x2, y2, f: in Polynomial;
x3, y3: out Polynomial);

The following executable algorithm computes kP.

Algorithm 10.8—Point multiplication (Q = kP), Koblitz curve, right to left

Q_infinity := true;
for i in 0 .. t-1 loop
if r(i) = 1 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;
elsif r(i) = -1 then
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;
end if;
xP := product_mod_f(xP, xP, f); yP := product_mod_f
(yP, yP, f);
end loop;

The base-τ conversion Algorithm 10.5 successively computes r ,
0
r , . . . , r , and the right-to-left point-multiplication Algorithm 10.7
1 t − 1
successively uses r , r , . . . , r . So, both algorithms can be executed
0 1 t − 1
in parallel.
Algorithm 10.9—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
if A mod 2 = 0 then R_I := 0;
elsif 2 - ((A - 2*B) mod 4) = 1 then