Page 355 - Hardware Implementation of Finite-Field Arithmetic

Binary Fields 335

end K233_addition;
package K233_package is
constant m: natural := 233;
end K233_package;
entity K233_point_multiplication is
port (
xP, yP, k: in std_logic_vector(m-1 downto 0);
clk, reset, start: in std_logic;
xQ, yQ: inout std_logic_vector(m-1 downto 0);
done: out std_logic
);
end K233_point_multiplication;
The corresponding architectures are similar to those of the K163_
addition and K163_point_multiplication entities. Nevertheless, apart
from the operand length, another difference is that K-163 is a Type-1
Koblitz curve [Eq. (10.53)] while K-233 is a Type-0 curve [Eq. (10.52)].
In the first case a = 1, b = 1, and μ = 1, and in the second case a = 0, b =
1, and μ = −1. The addition formulas [Eq. (10.16)] are slightly different
(a = 1 or 0, in function of the curve type) and the same occurs with the
base-τ representation algorithms (μ = 1 or −1, in function of the curve
type). In the case of K-233 the following rules are used:
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) and
0 1 0
b’ = − ( ⎣ a/2⎦ + 1)

The point multiplication circuit of Fig. 10.2 has been implemented
within a Spartan3 (speed-5) programmable device with P defined by
its coordinates:

x = 17232ba853a7e731af129f22ff4149563a419c26bf50a4c9d6eefad6126
P
y = 1db537dece819b7f70f555a67c427a8cd9bf18aeb9b56e0c11056fae6a3
P
The order of P is equal to
n = 08000000000000000000000000000069d5bb915bcd46efb1ad5f173abdf

The circuit computes kP for any k belonging to the interval 0 < k < n.
All the source files are available at www.arithmetic-circuits.org.

FFs LUTs Slices Period AverCycles AverTime
3,080 4,640 2,888 8.1 110,051.3 891,416