US8666062B2 — Method and apparatus for performing finite field calculations
Document text
Research, not advice. Part of the Bitcoin research archive (October 2026). Claims labelled unverified, contested or fringe are reported, not endorsed; statuses of bills and rules are as of the date checked. Government, court and patent records are public domain; the research notes are CC BY 4.0.
USOO8666.062B2
(12) United States Patent (10) Patent No.: US 8,666,062 B2
Lambert (45) Date of Patent: *Mar. 4, 2014
(54) METHOD AND APPARATUS FOR (56) References Cited
PERFORMING FINITE FIELD
CALCULATIONS U.S. PATENT DOCUMENTS
5,982,895 A 11/1999 Dworkin et al.
(75) Inventor: Robert J. Lambert, Cambridge (CA) 6,049,815 A 4/2000 Lambert et al.
6,199,086 B1 3/2001 Dworkin et al.
(73) Assignee: Certicom Corp., Mississauga (CA) 6,230,179 B1* 5/2001 Dworkin et al. .............. TO8/492
6,263,081 B1 7/2001 Mijaji et al.
(*) Notice: Subject to any disclaimer, the term of this 6,430,588 B1 8/2002 Kobayashi et al.
patent is extended or adjusted under 35 6,466,668 B1 10/2002 Miyazaki et al.
6,480,606 B1 11/2002 Kurumatani
U.S.C. 154(b) by 1354 days. 6,618,483 B1 9, 2003 Vanstone et al.
This patent is Subject to a terminal dis 6,714,648 B2 3/2004 Miyazaki et al.
claimer. 7,111,166 B2 * 9/2006 Dror et al. ..................... T13,174
7,286.666 B1 10/2007 Coron
2002/013.6402 A1* 9, 2002 Vanstone ........................ 380,30
(21) Appl. No.: 12/101,590 2003/0021410 A1 1/2003 Miyazaki et al.
(22) Filed: Apr. 11, 2008 * cited by examiner
Primary Examiner — Kaveh Abrishamkar
(65) Prior Publication Data
(74) Attorney, Agent, or Firm — Brett J Slaney; John R. S.
US 2009/OO77144A1 Mar. 19, 2009 Orange: Blake, Cassels & Graydon LLP
(57) ABSTRACT
Related U.S. Application Data In general terms, the invention provides a finite field engine
and methods for operating on elements in a finite field. The
(63) Continuation of application No. 10/058.212, filed on finite field engine provides finite field sub-engines suitable
Jan. 29, 2002, now Pat. No. 7,372,960. for any finite field size requiring a fixed number of machine
(60) Provisional application No. 60/343,226, filed on Dec. words. The engine reuses these engines, along with some
31, 2001, provisional application No. 60/343,227, general purpose component or specific component providing
filed on Dec. 31, 2001, provisional application No. modular reduction associated with the exact reduction (poly
60/343,220, filed on Dec. 31, 2001, provisional nomial or prime) of a specific finite field. The engine has
application No. 60/334.223, filed on Dec. 31, 2001. wordsized suitable code capable of adding, Subtracting, mul
tiplying, squaring, or inverting finite field elements, as long as
(51) Int. C. the elements are representable in no more than the given
H04L 9/00 (2006.01) number of words. The wordsized code produces unreduced
(52) U.S. C. values. Specific reduction is then applied to the unreduced
USPC ................ 380/28: 380/44; 713/169; 713/171 value, as is suitable for the specific finite field. In this way, fast
(58) Field of Classification Search engines can be produced for many specific finite fields, with
None out duplicating the bulk of the engine instructions (program).
See application file for complete search history. 21 Claims, 15 Drawing Sheets
Finite Field Engine
Fite field
parameters 40
Finite field routines Wordsized
Algorithras
Addition
Finite Field Multiplication
Reduction Squaring
riversion
Subtraction
U.S. Patent Mar. 4, 2014 Sheet 1 of 15 US 8,666,062 B2
Network 8
&mdox& - 5 8
OO List of Curves s 4
Processor
200 Cryptographic Engine
Bus 13
300 Elliptic Curve Engine
400 -WXFinite Field Engine H Memory 6 10.
Figure 1
U.S. Patent Mar. 4, 2014 Sheet 2 of 15 US 8,666,062 B2
OO
First Elliptic Curve Second Elliptic
Curve
Parameters O2 Parameters 112
Firite field 3
Private key 114
Public key 5
List of Parameters
Figure 2
Cryptographic engine
2 O
Protocols
23 O.
Finite Field Pointers
Figure 3
U.S. Patent Mar. 4, 2014 Sheet 3 of 15 US 8,666,062 B2
Finite Field Pointers
Elliptic Curve Routines
EcAddition
EC Scalar Multiplication
EC Double
FF Subtractic
Finite Field Engine
Finite field
parameters 410
Finite field routines Wordsized
Algorithms
Addition
Finite Field Multiplication
Reduction Squaring
inversion
Subtraction
Figure 5
U.S. Patent Mar. 4, 2014 Sheet 4 of 15 US 8,666,062 B2
Protocol
Protocol Steps
Call EC Engine
Call FF Engine
704
Retrieve P from curve
parameters 100 (Figure 1);
Elliptic Curve Operations
Figure 7
U.S. Patent Mar. 4, 2014 Sheet 5 Of 15 US 8,666,062 B2
Computes = k (d+er) 802 Initialization
: 3O4.
Retrieve k, r from memory Retrieved from curve
k 16 (Figure 1) parameters 100 (Figure 1)
: Finite Field Operations
was an as a se - - r n w - - w w w is a we w n w arr r s is a r + n is - - - - - - a r wra r w x - r r - - - a
U.S. Patent Mar. 4, 2014 Sheet 6 of 15 US 8,666,062 B2
wO w w2 WIl-2 wn- Wi
iO W00 wo. wO2 WO3 w04. wO5 w10 will w! 2 wil3 will 4 wi5
Figure 11
U.S. Patent Mar. 4, 2014 Sheet 7 of 15 US 8,666,062 B2
Store w0 as wol,..., won 202
Store was will,..., win 1204
x XO(XOR)x1, 1208
124
Increment i Store w2= X0(XOR) X1 1210
212
Done
Figure 12
U.S. Patent Mar. 4, 2014 Sheet 8 of 15 US 8,666,062 B2
will wi2 W13 wn-2 win-wn
Figure 13
U.S. Patent Mar. 4, 2014 Sheet 9 Of 15 US 8,666,062 B2
(w0i) (wli) into w8, w?
Provide convolution as w8, W2 14 O
Figure 14
U.S. Patent Mar. 4, 2014 Sheet 10 of 15 US 8,666,062 B2
52 sS O.
| 1001 01.01-
) D 520
s
to 1534 8
Register
w
1526
Register
D S30
Word Shi n
534
Intermediate Register --from 536-se
538
--real- Accumulator
Figure 15
U.S. Patent Mar. 4, 2014 Sheet 11 of 15 US 8,666,062 B2
S 2 a. 5 Oa
«
s -
54a
-
| 101001
3.
:
&
8
8
s
8
Register
| Word Shift
from S36 Figure 15a
U.S. Patent Mar. 4, 2014 Sheet 12 of 15 US 8,666,062 B2
6.
-o-o-o-o-or
Method of Inversion
Subtraction.
were
Addition
i years
riversion -
Wordsized
Multiplication
Wordsized
subtraction
62 626 62s
Figure 16
U.S. Patent Mar. 4, 2014 Sheet 13 of 15 US 8,666,062 B2
72
7 O
im-l
s
2m-2 GPE
Subtract
U.S. Patent Mar. 4, 2014 Sheet 14 of 15 US 8,666,062 B2
1912
l,6
1,6
1914 1916
2.5 2.5
16 1 25
1918 34 3, 1920
2.5 34
1722
1922 4,3 - “.3 1924
3,4 43
1722
928 1930
1926 5,2 s 5.2 5.2
4,3 52 6,1
1722
Figure 19 6, 1
6.1
1932
U.S. Patent Mar. 4, 2014 Sheet 15 Of 15 US 8,666,062 B2
2002
200 so
2008
D 2010
2008
2014
ao Register 2O2
Figure 20
US 8,666,062 B2
1. 2
METHOD AND APPARATUS FOR at random. The correspondent’s public key is the elliptic
PERFORMING FINITE FIELD curve point obtained by scalar multiplication of the private
CALCULATIONS key with a generator point.
The security level of a cryptographic system mainly
CROSS REFERENCE TO RELATED depends on the key size that is used. Larger key sizes give a
APPLICATION higher security level than do Smaller key sizes, since the time
required for an attack on the system depends on the total
The present application is a continuation of U.S. patent number of possible keys, however, different key sizes require
application Ser. No. 10/058.212 filed on Jan. 29, 2002 now defining different elliptic curves over different finite fields.
U.S. Pat. No. 7,372,960 which claims priority from U.S. 10 Generally, the greater the desired cryptographic strength of
Provisional Patent Application Nos. 60/343,226, 60/343,227, the ECC, the larger will be the size of the finite field.
60/343,220, 60/334,223, all filed on Dec. 31, 7001, the con Thus an implementation of elliptic curve cryptography
tents of each of which are incorporated herein by reference. may need to support several different finite fields for use in
particular applications. Implementing an elliptic curve cryp
FIELD OF THE INVENTION 15 tosystem therefore requires either the implementation of spe
cific methods for each finite field or a generic method usable
The invention relates to finite fields, and more particularly in any finite field. Each approach offers different advantages.
to a finite field engine for use with cryptographic systems. The use of specific methods for each finite field leads to
more efficient code since it may be optimized to take advan
BACKGROUND OF THE INVENTION tage of the specific finite field. However, Supporting several
finite fields in this way will increase the code size dramati
Cryptography is commonly used to provide data security, cally.
integrity, and authentication over unsecured communication The use of a generic method prevents the use of optimiza
channels. For example, a connection between two correspon tion techniques, since the code cannot take advantage of any
dents over the Internet or a wireless network could easily be 25 particular properties of the finite field. This makes the code
monitored by an eavesdropper. To protect their confidential less efficient but has the advantage of much smaller code size.
ity, the correspondents could encrypt their transmissions with Many implementations of elliptic curve cryptosystems
a secret key. They could also use various cryptographic pro employ binary finite fields, that is fields of characteristic 2. In
tocols to provide authentication of the other party. Traditional these fields, elements may be represented as polynomials
protocols using symmetric-key cryptography require that the 30 with binary coefficients, which may be represented as bits in
correspondents share a secret key before initiating secure hardware or software. These bits must then be represented in
communications. This key must be shared through some the memory storage of the computer system. Other imple
secure channel, which may be difficult and expensive to mentations use fields of prime characteristic p greater than 2.
obtain. However, the correspondents can avoid having to In these fields, elements are usually represented as integers
share a secret key ahead of time by using public-key cryptog 35 less than p.
raphy. Software implementation offinite fields raises the question
Correspondents using public key cryptography each have a of how to arrange the storage of the bits corresponding to the
private key and a corresponding public key. The derivation of finite field elements.
the public key is such that it is computationally infeasible to When using a general purpose computational engine (for
compute the private key given only the public key. However, 40 example a typical CPU), finite field elements are often too
the mathematical relationship between the keys allows them long to be represented in a single machine word of the engine
to be used to provide security, integrity, or authentication in (engine word lengths are typically 16, 32 or 64bit). Since the
various protocols where the public keys are shared and the finite field used in ECC operations are typically 160 bits or
private keys are kept secret. more, these elements must be represented in several machine
Elliptic curve cryptography (ECC) is a particularly effi 45 words.
cient form of public key cryptography that is especially useful Engine routines (programs) that provide finite field calcu
in constrained environments such as personal digital assis lations must therefore deal with multiple machine words to
tants, pagers, cellular phones, and Smart cards. To specify an complete their calculations. If the finite field irreducible, or
elliptic curve, a finite field and an equation over that finite prime is known in advance, then the number of words that
field are needed. The points on the elliptic curve are the pairs 50 must be dealt with is also known in advance, and more effi
offinite field elements satisfying the equation of the curve, as cient code can be written that expressly deals with exactly the
well as a special point at infinity. To carry out calculations right number of components.
involving points on the elliptic curve, calculations are done in If the finite field irreducible (F2m), or prime (ep) is not
the underlying finite field, according to well-known formulas known in advance, typically general purpose code is built that
that use parameters of the curve. These formulas define an 55 can handle any number of word components in the finite
addition operation on a pair of elliptic curve points. A scalar fields, but this code is typically much slower because of the
multiplication operation is defined by repeated additions, overhead of dealing with the unspecified number of compo
analogously to regular integer multiplication. An integer n, nents. The advantage of this general purpose, wordsize non
called the order of the curve, is the order of the elliptic curve specific code is that the engine description (program size) is
group. 60 Small when compared against specific engines each tailored
An elliptic curve cryptosystem may have certain param to a specific finite field.
eters common to all users of the system. These could include With either type of codes, it is necessary to provide finite
the finite field, the elliptic curve, and a generator point on the field operations including multiplication, addition, inversion,
curve. These system parameters are often common to a group squaring and modular reduction.
ofusers who each generate a key pair comprising a private key 65 Generally, multiplication of two bit strings representing
and a public key. A correspondent’s private key is an integer elements in F" is performed in a similar manner as integer
less than the order of the elliptic curve, preferably generated multiplication between a multiplicand and a multiplier and
US 8,666,062 B2
3 4
uses bit shifting and Zero placement. Beginning with the right There are several variants on the Extended Euclidean Algo
most bit (0" position) of the multiplier, the multiplicand is rithm that perform similar computations, such as almost
multiplied by the selected bit. The resulting intermediate inverses.
value is then stored in an accumulator. The multiplicand is Accordingly, there is a need for a method of performing
then multiplied by a second bit of the multiplier located in the calculations inabinary finitefield which obviates or mitigates
1 position, adjacent to the bit in the 0" position. The result Some of the above disadvantages.
ing intermediate value is then stored in a predetermined inter
mediate value register and shifted to represent a Zero place SUMMARY OF THE INVENTION
holder, similar to the tens placeholder in base 10
multiplication. The exclusive or (XOR) of these two interme 10 In general terms, the invention provides a finite field engine
diate values, stored in the accumulator and the predetermined and methods for operating on elements in a finite field. The
intermediate value resister is computed and the result stored finite field engine provides finite field sub-engines suitable
in the accumulator. The multiplicandis then multiplied by the for any finite field size requiring a fixed number of machine
bit in the 2" position of the multiplier and the intermediate words. The engine reuses these engines, along with some
value stored in the predetermined intermediate value register. 15 general purpose component or specific component providing
The intermediate value is then shifted by two places to rep modular reduction associated with the exact reduction poly
resent the Zero placeholders and the XOR of the intermediate nomial or prime) of a specific finite field. The engine has
value and the accumulator is computed. The accumulator is wordsized suitable code capable of adding, Subtracting, mul
then updated with the new result. These steps are repeated tiplying, squaring, or inverting finite field elements, as long as
until the multiplicand has been multiplied with each of the the elements are representable in no more than the given
bits of the multiplier ending with the left most bit of the number of words. The wordsized code produces unreduced
multiplier. It will be understood that the bit shifting of the values. Specific reduction is then applied to the unreduced
intermediate values corresponds to the placement of the bit value, as is suitable for the specific finite field. In this way, fast
with respect to the number of Zero placeholders that are engines can be produced for many specific finite fields, with
required. The final value stored in the accumulator is then 25 out duplicating the bulk of the engine instructions (program).
retrieved and is the product of the multiplicand and the mul In accordance with one aspect of the present invention,
tiplier. there is provided a method of adding elements of a finite field
As will be understood, by separately multiplying the mul Fn, where m is less than a predetermined number n is pro
tiplicand and each bit of the multiplier, many bit shifts are vided, the method comprising the steps of
required. In particular, it is necessary to perform bit shifts for 30 a) storing a first and a second element in a pair of registers,
each bit of the multiplier. This results in longer processing each of the pair of registers comprising the predeter
time and also extra processor operation. mined number of machine words:
Inversion b) establishing an accumulator having the predetermined
Inversion in a finite field is usually performed using the number of machine words;
Extended Euclidean Algorithm. In a field with prime charac 35 c) computing for each of the machine words in the accu
teristic p or irreducible f an element X may be inverted by mulator the exclusive-or of the corresponding machine
using the EEA to find a solution to the equation: words representing each of the first and second ele
mentS.
In accordance with a further aspect of the present inven
Then ax=1 mod p and asX' modp 40 tion, there is provided a device for adding a pair of elements
(or ax=1 mod fanda=x" modf) of a finite field Fan where m is less than a predetermined
A common technique is to use two starting equations: number n, comprising: a pair of registers for storing said pair
of elements, each of the registers consisting of n machine
words; an accumulator consisting of n machine words; an
1x+1p=x<p 45 output resister consisting of n machine words; an XOR gate
A multiple of the second equation is then subtracted from connected
registers
to a respective machine word in each of the pair of
and providing an output to a respective one of the
the first equation: machine words.
-qx+1p p-qx In accordance with another aspect of the invention, there is
provided
50
The process continues untila 1 is obtained on the right hand elements of a finite field multiplier operable to multiply two
side (RHS). one of a plurality of finite fields, said finite fields
This process is often shown using a table as in the following being partitioned into Subsets, said multiplier comprising:
example of computing 113 mod 239. a) a plurality of wordsized finite field multipliers, each
suitable for multiplying elements of each finite field in a
55 respective subset of said plurality of finite fields;
b) a finite field reducer configured to perform reduction in
8. b a 113 + b : 239 said one finite field;
O 1 239
c) a processor configured to
1 O 113 i) operate the wordsized finite field multiplier suitable
-2 1 13 60 for use with said one finite field to obtain an interme
17 -8 9 diate product; and
-19 9 4
55 -25 1
ii) operate said finite field reducer on said intermediate
product to obtain the product of the two elements.
In accordance with yet another aspect of the present inven
Thus 55-113-25-239–1 and 55=113 mod 239. 65 tion, there is provided a method of performing a finite field
It will be recognized that it is not necessary to keep track of operation on two elements r, S of a finite field, comprising the
the “b’ values. steps of:
US 8,666,062 B2
5 6
a) performing a wordsized operation of rands, said word FIG. 12 is a flowchart illustrating the steps of a method
sized operation corresponding to said finite field opera using the device of FIG. 11.
tion; FIG. 13 is a schematic representation of a finite field mul
b) performing a modular reduction of the result of step a); tiplication operation performed by the finite field engine 400
In accordance with still another aspect of the present inven of FIG.S.
tion, there is provided a finite field engine for performing a FIG. 14 is a flow chart illustrating the steps of a method
finite field operation on at least one element of a finite field according to FIG. 13.
chosen from a set of finite fields, said set of finite fields being FIG. 15 is a schematic representation of a multiplication
divided into Subsets according to their word size, comprising: method performed by the finite field engine of FIG. 5.
a) a finite field operator for each of said subsets; 10 FIG.16 is a schematic representation of a finite field inver
b) a finite field reducer for each of said finite fields; sion method performed by the finite field engine 400 of FIG.
c) a processor configured to choose the finite field operator 5.
corresponding to the Subset containing said chosen finite FIG. 17-19 is a schematic representation of an inversion
field and the finite field reducer for said chosen finite method performed by the finite field engine 400 of FIG. 5.
field and apply the chosen finite field operator to said 15 FIG. 20 us a schematic representation of a modular reduc
element to produce an intermediate result and apply the tion method performed by the finite field engine 400 of FIG.
chosen finite field reducer to said intermediate result to 5.
obtain the result of said finite field operation.
In accordance with a still further aspect of the invention, DESCRIPTION OF THE PREFERRED
there is provided a cryptographic system comprising: EMBODIMENTS
a) a plurality of elliptic curves, each specifying elliptic
curve parameters and a respective finite field; Referring to FIG. 1, a communication system having at
b) a plurality of finite field settings corresponding to each least two correspondents is shown generally by numeral 10. A
finite field; correspondent 12 is connected through a network 18 to a
c) a plurality of wordsized finite fields, each having rou 25 plurality of correspondents, shown in the example of FIG. 1
tines, each finite field being assigned to one of said as 20, 22, 24, and 26. The correspondent 12 has a crypto
wordsized finite fields; graphic unit 13 including a processor 14, a bus 15, a memory
d) a reduction routine for each finite field; 16, a set of elliptic curves 100 with corresponding parameters,
e) a computational apparatus configured to perform a cryp a cryptographic engine 200, an elliptic curve engine 300, and
tographic operation by the steps of: 30 a finite field engine 400. Each of the correspondents 20, 22.
i) selecting one of said elliptic curves; 24, 26 has a cryptographic unit providing at least one elliptic
ii) performing a cryptographic function using the rou curve shown as 21, 23, 25, and 27, respectively. The corre
tines from the wordsized finite field to which the spondent 12 can communicate using public key cryptography
respective finite field corresponding to said selected with any correspondent which has at least one elliptic curve in
elliptic curve is assigned. 35 common with it. In operation, data is stored in the memory 16
and communicated over the bus 15. The processor 14 operates
BRIEF DESCRIPTION OF THE DRAWINGS to execute an appropriate engine 200, 300, 400 on the data.
The engines may be software instructions executed by the
These and other features of the preferred embodiments of processor, or they may have dedicated coprocessors.
the invention will become more apparent in the following 40 Referring to FIG. 2, the set of elliptic curves 100 contains
detailed description in which reference is made by way of a plurality of elliptic curves exemplified as a first elliptic
example only to the appended drawings wherein: curve 101, and a second elliptic curve 111. Each curve 101,
FIG. 1 is a schematic representation of a data communica 111 has associated parameters 102, 112 for indicating its
tion system. elliptic curve equation. Each curve 101, 111 also has an
FIG. 2 is a detailed view of the list of parameters 100 shown 45 associated finite field 103, 113. A private key 104, 114 is
in FIG. 1. provided for use with each curve, and a corresponding public
FIG. 3 is a detailed view of the cryptographic engine 200 key 105, 115 derived from a seed point P and the private key
shown in FIG. 1. 104.
FIG. 4 is a detailed view of the elliptic curve engine 300 Referring to FIG. 3, the cryptographic engine 200 com
shown in FIG. 1. prises instruction sets to implement selectively a plurality of
50
FIG.5 is a detailed view of the finitefield engine 400 shown protocols 210, exemplified by the ECDSA protocol 212, the
in FIG. 1. MQV protocol 214, and others 216. The implementation of
FIG. 6 is a schematic representation of a protocol per the protocols 210 requires the use of both elliptic curve opera
formed by the cryptographic engine 200 in FIG. 3. tions and finite field operations. The protocols 210 are con
FIG. 7 is a schematic representation of an elliptic curve 55 figured to treat the elliptic curve operations and finite field
scalar multiplication operation provided by the elliptic curve operations abstractly. Accordingly, the cryptographic engine
engine 300 of FIG. 4 and used by the protocol shown in FIG. provides pointers 220 to elliptic curve operations and pointers
7. 230 to finite field operations. The protocols 210 use the point
FIG. 8 is a schematic representation of a signature compo ers 220 and 230 to perform selectively the elliptic curve and
nent provided by the protocol 210 of FIG. 8. 60 finite field operations.
FIG. 9 is a schematic representation of a finite field multi In use, the processor 14 executes the cryptographic engine
plication in the method of FIG. 8. 200 to set the pointers 220 and 230 to use the appropriate
FIG.10 is a schematic representation of a memory segment operations in the elliptic curve engine 300 and the finite field
used by the finite field engine 400 of FIG. 5. engine 400. More specifically, pointer 222 references an
FIG. 11 is a schematic representation of a device used by 65 elliptic curve addition operation, pointer 224 references an
the finite field engine 400 shown in FIG. 5 to add two finite elliptic curve Scalar multiplication operation, and pointer 226
field elements. references an elliptic curve double operation. Further, pointer
US 8,666,062 B2
7 8
232 references a finite field (FF) addition operation, pointer To compute the signature component S, the ECDSA pro
234 references a finite field multiplication operation, pointer tocol 212 operates as shown in FIG. 8. In the initialization
236 references a finite field Squaring operation, and pointer phase, it is desired to computes (802). The protocol must first
238 references a finitefield inversion operation. A pointer 239 retrieve k and r from the memory 16 of FIG. 1 (804). It must
references a finite field subtraction operation for use in finite also retrieved, the long-term private key, from the curve
field F, of prime characteristic. (A separate subtraction opera parameters 100 of FIG. 1 (806). It then inputs the hash of a
tion is not necessary in Fn because subtraction is the same as message e (808). The protocol proceeds with finite field
addition since the field of characteristic 2). operations by calling a finite field multiplication (810) of e
As can be seen from FIG. 4, the elliptic curve engine 300 and r to obtain er. The protocol then executes a finite field
comprises a plurality of elliptic curve routines 320 corre 10 addition of d and er (812) to obtain der. The protocol
sponding to the pointers 220 in the cryptographic engine 200. executes a finite field inversion of k (814) to obtain k". The
There is a corresponding operation for each pointer 222, 224, protocol then executes a finite field multiplication of k and
226 namely an elliptic curve addition operation 322, an ellip d+er (816). The result of this multiplication is a signature
tic curve Scalar multiplication operation 324 and an elliptic components (818). The signature component S is then pro
curve double operation 326. Each elliptic curve operation320 15 vided to the remainder of the protocol.
requires certain finite field operations, and so accordingly Referring particularly to FIG.9, the finite field multiplica
pointers 330 are provided to operations in the finite field tion 810 within the finite field engine 400 is shown generally
engine 400, corresponding to the pointers 230 in the crypto by the numeral900. To perform finitefield multiplication 902
graphic engine 200. ofe and r, the finite field engine executes 904 a wordsized
Referring to FIG. 5, the finite field engine 400 is shown in multiplication of e and r. The result of the wordsized multi
more detail. Each finite field has associated parameters 410. plication is passed 906 to the finite field reduction 450. The
which detail the characteristic of that finite field and its word finite field is first identified 908, and then a specific reduction
size. A: plurality of finite field operations shown generally at 910 is executed. The specific reduction corresponds to the
numeral 430 are provided, corresponding to the set of point particular finite field identified.
ers 230 and 330 in the cryptographic engine and the elliptic 25 It may be seen that computations on finite field elements
curve engine, respectively. Accordingly, a finite field addition are performed by the finite field engine 400. Accordingly, the
operation 432, a finite field multiplication operation 434, a data storage in the finite field engine 400 determines the
finite field squaring operation 436, and a finite field inversion nature of the data that is passed between the various engines
operation 438 is provided. A finite field subtraction operation and computed by them.
439 is provided for use in finite fields F. Each finite field 30 Finite field elements are stored by the finite field engine
operation 430 makes use of wordsized algorithms 440, which 400 in memory segments larger than are actually required.
are provided for each word size and described below. A plu The most significant bits are set to 0. Operations can be
rality of specialized reduction algorithms 450 is provided, performed on these elements by acting on the memory seg
there being one reduction algorithm for each field in the list ment as a whole, while ignoring the extra bits. This represen
410. 35 tation is referred to as a “wordsized representation.
The data passed between the engines 200, 300, 400 com The finitefield engine 400 provides finite field routines 430
prises finite field elements, since arm elliptic curve point for use by the cryptographic engine 200 and the elliptic curve
consists of two finite field elements. The finite field elements engine 300. When these finitefield routines 430 are called, the
are only operated on directly by the finite field engine 400, finite field engine 400 uses the parameters of the finite field
and are stored as a set of words in the format shown below in 40 410 to choose the appropriate wordsized algorithm 440. After
FIG 10. applying the wordsized algorithm 440, the finite field engine
Referring to FIGS. 6 through 9, one of the protocols 210 reduces the result using a finite field reduction 450. The finite
requires steps 610 which call operations from the elliptic field reduction may be specific to a certain finite field, or a
curve engine 300 and the finite field engine 400. Typically, a wordsize reduction. The reduction should lower the length of
protocol 210 may callelliptic curve scalar multiplication 622, 45 the result to the appropriate word length of the underlying
elliptic curve addition 624, elliptic curve double 626 and may field. This way, finite field elements may be consistently
call finite field operations directly such as addition 632, mul stored in registers of the same word length. The reduction
tiplication 634, and inversion 636. The order of the calls and need not to be the minimal reduction but need only be enough
the data passed to them is determined by the specific one of to ensure that the result fits into the given number of words.
the protocols 210. 50 Referring therefore to FIG. 10, an exemplary memory seg
In one exemplary protocol, the ECDSA protocol 212 ment 1000 provides a fixed number of machine words w0.
requires the computation of two signature components rand w1,..., ws. The use of 6 words is by way of example only and
S, which are given by the formulas: to provide for clearer presentation. An element is stored with
the least bit on the least bit of wo and ending before the most
55 significant bit of w5, as shown generally by numeral 1001.
Certain bits 1002 are unused in this representation. Alterna
tive representations and orderings of the bits are possible. In
To computer, the ECDSA protocol 212 operates as shown in order to perform the operations taking advantage of the data
FIG. 7. In the initialization phase, the protocol begins the structure of the memory segment 1000, the finite field engine
computation of kP (702). In this first retrieve k from memory 60 400 has to implement fundamental finite field operations of
16 of FIG. 1 (704). It must also retrieve P from curve param addition, multiplication, inversion, and modular reduction.
eters 100 in FIG. 1 (706). The protocol then proceeds to the Particular implementations of these operations are described
elliptic curve operations, by calling the elliptic curve engine below.
(708). It selects scalar multiplication (710) with the input Wordsized Addition
being kP. The scalar multiplication executes double and add 65 Referring to FIG. 11, a wordsized circuit 1100 implement
routines (712). These routines in turn direct finite field opera ing finite field addition 432 of two finitefield elements w0 and
tions by calling the finite field engine (714). w1 of a given word length is shown. Each element is stored
US 8,666,062 B2
9 10
comprising 6 machine words as shown in FIG. 10. The 1300. The first element wo is stored in a register 1302 and the
memory segment corresponding to the first element wo is second element is stored in a register 1304. A pair of registers
made up of the machine words w00, w01,..., w05. Similarly, 1306 w2 and w8 are provided to store the product of wo and
the memory segment corresponding to the second element w1 w1. The use of two registers is merely to use registers of
is made up of the machine words w10, w11, ..., wil5. Each consistent size for convenience of presentation, however, the
corresponding pair is connected to a respective XOR circuit registers 1306 could be provided by one register of greater
x0, x1,..., X5. That is, w00 and w10 connect to x0, w01 and length.
w11 connect to X1, and so on. Referring to FIG. 14, a wordsized method of multiplying
Each XOR circuit is further connected to memory segment the elements of FIG. 13 is shown generally by the numeral
w2 comprising the 6 machine words w20, w21, . . . . w25. 10 1400. To begin, the element w0 is stored 1402 as words w01,
Each XOR circuit is connected to the corresponding machine w02. . . . . wOn in the register 13027 and the element w1 is
word. That is, x0 connects to w20, x1 connects to w21, and so stored 1404 as words w11, wil2,..., win in the register 1304.
on. To add two elements, the XOR circuits x0, x1,..., x5 each Then the registers w27 and w8 are established 1406. The
XOR the corresponding machine words (w00, wil0), . . . . method then entails accumulating 1408 partial products
(w05, wil5) and store the result in the corresponding output 15 formed from a word of wo and a word of w1 into the registers
machine words w20, w21, ..., w25, so that w2=w00+w 10 w2 and w8. After all of the partial products are accumulated,
and so on. it provides 1410 the convolution as the registers w3 and w2.
The XOR circuits may be implemented by an arithmetic Referring therefore to FIG. 15, a finite field multiplier 1510
logic unit and a bus structure in a CPU. To add two elements includes a pair of registers 1512, 1514. The register 1512
w0, will of a finite field stored in this representation, the contains the multiplicand, indicated by the binary string
processor cycles through the 6 machine words w01,..., w05 100101011110, and the register 1514 the multiplier repre
and w10, ..., wil5 representing each finite field element, and sented by the binary string 10100111. The register 1514 is
applies an exclusive-or (XOR) operation denoted by €D to the subdivided into words, in this example each of 4 bit length
corresponding machine words. The result of this exclusive-or and a pointer 1516, 1518 is associated with one bit of each
operation is stored in the corresponding machine word of the 25 word.
set of machine words w20,..., w25 reserved for the result of The register 1512 and the output of each pointer 1516,
the addition operation. That is: 1518 are connected to an XOR function 1520, 1522 respec
tively and the result of the XOR stored in registers 1524,
1526.
30 The register 1526 is associated with the pointer 1518 that
reads a bit from the second word and accordingly has a word
shift function 1528 associated with it to shift the contents one
w25 = wise w15.
word to the left.
The output of the registers 1524, 1526 is connected to an
35 XOR function 1530 whose result is stored in an intermediate
Then, the memory segment W2 contains the Sum of the two register 1532. A shift signal 1534 is applied to register 1532
finite field elements w0 and w1, represented as the 6 machine from a shift control 1536 that also controls the position of
words w20, ..., w25. pointers 1516, 1518 on register 1514. The intermediate reg
Referring therefore to FIG. 12, a wordsized method for ister 1532 is connected to a XOR function 1538 that also
adding two elements 1200 of a given word length involves 40 receives the output of an accumulating register 1540.
first storing the first element in a memory segment comprising The shift control 1536 operates to considerall bit positions
a plurality of machine words 1202, and storing the second within 1 word in a specified order. In this example, there are
element in a memory segment comprising a plurality of 4 bit positions to consider. The following are performed for
machine words 1204, as in FIG. 3. Then a counter is initial each bit position. The pointers 1516, 1518 are set to a bit
ized 1206 to initiate a loop through the machine words. At 45 position by the shift control 1536. The pointer 1516 reads the
each iteration, an XOR of two machine words is computed bit in the bit position in the first word. The pointer 1518 reads
1208, and stored in the appropriate output machine word the bit in the bit position in the second word. For example,
1210. When the counter is less than the number of machine when the 2" bit position is considered, the second bit of each
words 1212, the counter is incremented 1214, and the loop word is read by the respective pointer.
repeated. When the counter reaches the number of machine 50 After the bits are retrieved, the contents of the register 1512
words 1212, the method terminates 1216. is read and XOR'd by the functions 1520, 1522. The results
The above method describes a wordsize addition for F2m, are stored in the registers 1524, 1526. For the bit of the first
where the addition is composed of XOR's of the component word, the value of register 1512 is simply stored in the register
words. When the finite field is Fp, the addition is composed of 1524 since the value of the bit is 1. The result of multiplication
integer addition of the components, proceeding from the least 55 between the multiplicand and the bit of the second word is
significant to the most significant word of the representations, stored in the register 1526. Since the bit of the second word is
and also propagating the carry into the addition of the next 0, the register 1526 has a value of 0. Register 1526 is then
most significant words. shifted by shift function 1528 according to the bit size of the
Similarly, for subtraction (which is distinct from addition word. In the present example, since the word size is 4 bits, the
in Fp), word-wise subtraction is composed of word-wise sub 60 intermediate value is shifted 4 places in the form of a single
tractions, proceeding from the least significant to the most word shift. The word shift may be effected by offsetting the
significant word of the representations. Since a negative value registers 1524, 1526 at the input to XOR 1530. The two
can be generated by this process, the reduction must handle intermediate values in registers 1524, 1526 are then XOR'ed
this possibility. by the function 1530 with the resulting value stored in the
Wordsized Multiplication 65 intermediate register 1532. The shift signal 1534 performs bit
Referring to FIG. 13, a wordsized data storage used for shifts on register 1532 in accordance with the bit position of
multiplying two elements is shown generally by the numeral pointers 1516, 1518. In this way, one bit shift is applied to
US 8,666,062 B2
11 12
each component 1524, 1526 of the intermediate register Similarly, specific wordsize squaring for F is constructed
instead of performing separate bit shifts as in the prior art. The similarly to multiplication. Since for squaring, Ai-Bi,
contents of register 1532 are XOR'd with the contents of an slightly more than half the products need to be computed.
accumulator 1540 by the function 1538 and the result stored Wordsized Inversion
in the accumulator 1540. The process is repeated for each bit Referring to FIG. 16, a wordsized method of inverting an
and at its conclusion, the accumulator holds the result of the element is shown Generally by the numeral 1600. Finite field
multiplication. inversion is performed using the Extended Euclidean Algo
Whilst, it is recognized that the bits may be considered in rithm, which is based on computing the following remain
any order, it is generally simpler to order the bits by their ders:
significance. One option is to consider the bits from least 10 roq1 + 2
significant to most significant. In this case, the pointer 1516
initially reads the least significant bit for the first word, i.e. 1
and the pointer 1518 reads the least significant bit for the
second word, i.e. 0. The pointers move to the next more
significant bit on each repetition and finish with the most 15
significant bit. in-2 4-1-1.
An alternative order, which provides a further reduction in in-linn
the number of bit shifts required, is to consider the bits from
most-significant to least significant. In this case, a circuit as Each remainder requires the computation of a quotient q, and
shown in FIG. 15a may be used. This circuit differs from FIG. then determining the remainder by multiplication and Sub
15 in that bit shifts are performed on the accumulator. In this traction. Intermediate values are stored, one of which is equal
way, each bit shift affects previous computations, so that only to the inverse at the end of the algorithm. There are many
1 bit shift is required for each bit considered. variants of the extended Euclidean Algorithm, known as the
Referring therefore to FIG. 15a, a finite field multiplier is binary inverse, almost inverse etc. Each of these methods uses
shown with like components to FIG. 15 having a suffix a for 25 certain fundamental operations of addition, division, multi
clarity. Accordingly, registers 1512a, 1514a, pointers 1516a, plication, Subtraction, etc.
1518a, XOR functions 1520a, 1522a, registers 1524a, When the elements are stored as shown in FIG. 6, the
1526a, intermediate register 1532a, XOR function 1538a, inversion is implemented by following the same steps, but
and accumulating register 1540a are provided as in FIG. 15. using generic methods for the addition, division, multiplica
However, a shift signal 1534a is applied to accumulator 30 tion, and Subtraction. Accordingly, a finite field inversion
1540. method 1602 calls addition 1612, division 1614, multiplica
The above method describes a wordsize multiplication for tion 1616, and subtraction 1618. These basic operations are
Fr. For F, the multiplication operation is composed of implemented by using generic methods for addition 1622,
wordsized multiplications. Again the finite field multiplica division 1624, multiplication 1626, and subtraction 1628. In
tion is composed of a wordsized non-reducing multiplication, 35 fact, inversion will after re-implement these operations as
coupled with a specific reduction engine preferably tailored function calls.
to the specific finite field. In a preferred method of inversion it is recognized that
If the element A is composed of four words A3, A2, A1, whilst two values (“b” and “ax+bp') must be stored for each
A0, and this value is to be (non-reducing) multiplied with B, iteration, the number of words required to store each changes.
also composed of four words B3, B2, B1, B0, then the non 40 There is a leveling process Such that the “ax+bp' quantity is
reducing multiplication contains instructions that construct always getting Smaller and the 'a' quantity tends to get big
the unreduced product. Multiplying the words A, B, yields ger.
two words. Let the high word be denoted by high (A,B), and Referring to FIG. 17, a schematic drawing of sample cal
the low word by low (A, B). culations paths is shown. A plurality of dedicated computa
The non-reducing multiplication to be used in Fp multipli
45 tion engines 1712, 1716, 1718, and 1720 are provided along
cation would then compose the unreduced product with general purpose computational engines 1722. The cal
high (AB)+C6.low (AB)+high (AB2)+high
culation paths used by the engines are shown generally as
(AB)+C5, numeral 1710. The dedicated engines 1712, 1716, and 1720
are specially optimized to process a pair of parameters with
50 equal word lengths. It is expected these engines would be
used the most and accordingly they are the most optimized.
The dedicated engines 1714, 1718, are arranged to process a
pair of parameters in which the word lengths differ by one
word. These engines are not optimized as highly as the equal
55 word length engines, since they are expected to be used a bit
less. Accordingly, the fastest calculation path is to involve
only the dedicated engines 1712, 1716, and 1720. Occasion
ally, the word length of the parameters will vary further, and
the dedicated engines 1714, 1718 may need to be used. In this
60 case however, the leveling process of the Euclidean Algo
rithm will tend to yield the result which lies on the most
ow (AB)+low (AB)+high (AgBo)+Co. efficient calculation path. In some situations, the parameters
will require the use of a general-purpose engine 1722. These
ow (AoEo)=P.P.P.P.P.P.P.Po the unreduced
Product.
engines need not optimized and their use usually imposes a
65 performance penalty when compared with the fastest calcu
Here C, is the carry out of word i of the Product (not neces lation path. However, the output of the general-purpose
sarily 0 or 1, but in general possibly larger). engine is likely to be closer to the optimal calculation path.
US 8,666,062 B2
13 14
Engine 1724 show this tendency of the general purpose B83431B1E F8337E21 00000000 00000000, BBF6F1DF
entrance to direct calculations to the optimal path. CET3483O 490EAT89 2942O3F1 42BAC35C 48OOOOOO
The number of dedicated computational engines which are 00000000, 96CFED09388FF6C029828383
constructed and used as a matter of trade offbetween cost and 58 steps follow at this alignment using engine 1924
speed benefit. Each dedicated computational engine requires 000623FE 2C204627 76BEF5F7 3A000000 00000000,
more resources thena general-purpose computational engine, 2BB55F13 B2A7554D 958F4B55 CF461188 8998F8A2
however dedicated computational engines allow for faster 00000000, 00000006 8909F4B1346B7361
execution. While using only dedicated computational engines 4 steps follow at this alignment using engine 1926
would be quite fast, there would be a prohibitive resource BOEABA7E90B7D3CD DD40337D BAO00000 00000000,
requirement. 10 2BB55F13 B2A7554D 12B1E96A B9E8C231 11331F14
An exemplary circuit used in the method of inversion is 40000000 00000000, C19D3AFD 898A2FC3
shown generally in FIG. 18. The method of inversion operates 52 steps follow at this alignment using engine 1928
on two equations, having parameters referred to as L1 (1802) 884.353A4 5D8C8177 E383COC5 A845C9D7 70000000,
R1 (1804), L2 (1806) and E2 (1808). The parameters L1 and OOOOOOO1 B63B14D1 17295.514 353C12F7 8E69441A
L2 correspond to the parameter “a” and description of the 15 A8477158 D8000000 00000000, OEE15DED
extended Euclidean Algorithm and the parameters R1 and R2 2 steps follow at this alignment using engine 1930
correspond the parameters “ax+bp” in description of the 221 OD4E9 17632O5D F8EOFO31 6A117275 DCOOOOOO
extended Euclidean Algorithm. A pair of results are stored in 00000000, 6E36924F 9F6A06BO 68B09380 6DEA84DF
1810 and 1812, referred to as L3 and R3. There is a method of 0002B88F A8000000 00000000, OEE15DED
determining a multiple (1820), and subtractors 1822, 1824. In and finally, 38 steps follow at this alignment using engine
use, component 1820 determines a multiple of R2 to be sub 1932
tracted from R1. Then the subtractors 1822, 1824 subtract the O3A2221E F276742E A140A272 B799BAA1 58A492F7
multiple of L2 and R2 from L1 and R1 respectively. The 70000000, 00000001 EBE8CB36 E8A8AB15 588F9267
results are stored in L3 (1810), and R3 (1812). The values in 7FBC55589E7D8C26 00000000, 00000013
L2 and R2 are then placed in L1 and R1 and the results from 25 At each alignment the appropriate dedicated processor is
L3 and R3 are placed in L2 and R2, for the next iteration. selected and used until the alignment conditions are no longer
The following example illustrates a particular sequence of met. If during the reduction a condition is obtained that in not
computations. The calculation path used is shown in FIG. 19. met by a dedicated processor than the general purpose
In this example, it is desired to compute the inverse of a value engines are used until an alignment is again obtained that
in the finite field F,'. The irreducible is x+x+x+x+1. 30 meets one of the dedicated processors conditions. At the final
The first parameters operated on areas follows. Their word step, the RHS corresponds to a value of a 1 and therefore the
sizes are 1, 6 and 1, 6 so engine 1912 is used. inverse for OOOOOOO7 COAD7A37 EO546B29D O11E7OFA
80000000, 00000008 00000000 00000000 00000000 8D9A9887 58894F25 using x+x+x+x+1 as the modu
00000000 000000C9 00000000, 00000007 COAD7A37 lus is:
EO56529D O11E7OFA8D9A988.758894F25 35 O3A2221E F276742E A140A272 B799BAA1 58A492F7
While decreasing the RHS, 7 steps are performed in the 7OOOOOOO.
processor 1912 with the RHS of equal word length to arrive It will be recognized that the equal word length processor
at: is used the most, and the engines located further from the
28000000 00000000, 7A1A1334 3DOD08EE 983 ADA97 optimal path of equal word length engines are used less often.
2D062E5C A45DF765 E0000000, 00000002 1843.125D 40 This embodiment of inversion has been shown with special
0C218F1D 20ACF662 177E1F53 47558E6F At this stage, purpose engines to handle the case when the right hand sides
the RHS differ by 1 since the word sizes are 2, 5 and 1, 6 and have equal word length and when the word lengths of the right
therefore processor 1914 is used for a further 4 steps. The hand sides differ by one.
alignment then has equal word lengths of five words on the In another embodiment of inversion, the only special-pur
RHS as indicated below so the dedicated processor 1916 can 45 pose engines deployed are those for right hand sides with
be used on the representation: equal word length. This embodiment results in Smaller code,
B8000000 00000000, 7A1A1334 3DOD08EE 983 ADA97 and the equal word length engine is expected to be used the
2D062E5C A45DF765 03800000 00000000, OA59B49C most, as exemplified above. With this embodiment, the
O52CDA58 BA238E67 6D81 D1B6 DAAECESF engines 1912, 1916, 1920, 1924, 1928, and 1932 are special
54 steps follow at this alignment until the following is 50 purpose engines, while a general-purpose engine performs
obtained the functions of engines 1914, 1918, 1922, 1926, and 1930.
114BC508 60000000 00000000, 50628345 A834DC60 It will be recognized that the provision of general-purpose
CA40E435 809ECB43 EAE015AD C0000000, 00000006 engines and special-purpose engines may be applied to other
3F872A57 1FCBF6726C3ET9F3 6633CEBB methods with a similar leveling process, such as almost
At this stage the RHS differs by 1 since the word sizes are 55 inverses and other variants of the Extended Euclidean Algo
3, 4 and 2, 5 and so the dedicated processor indicated at 1918 rithm.
is used. Modular Reduction
2 steps follow at this alignment until equal word lengths are
Modular reduction is preferably provided for each finite
obtained. field that is needed. The modular reduction routine is pro
FBABD5F5 AO000000 00000000, 50628345 A834DC60 60 vided with instructions specific to the modulus used. Special
CA40E435 809ECB43 1D5C02B5 B8000000 00000000, ized routines such as those in the IEEE P1363 standard may
CDFCB52256FFE542 54CFD3B8 DCDSAOBF be used to perform the modular reduction 450 of the FF
54 steps follow at this alignment using engine 1920 engine 400. It will be appreciated that by providing particular
1D3C34DB F2D87350 20000000 00000000, BBF6F1DF modular reduction for each finite field, the speed of the
CE734830 490EA789 A5080FC5 OAEBOD71 20000000, 65 method may be optimized.
OOOOOOO2 EOC945FB2C4C933O EFO4A985 In a further embodiment, a method of modular reduction
2 steps follow at this alignment using engine 1922 using precomputation is provided that may be useful for
US 8,666,062 B2
15 16
certain reductions. Referring to FIG. 20, a method of per
forming the modular reduction 450 of the FF engine 400 is
Number of Machine
shown generally by the numeral 2000. Maximum Field Size Machine Word Size Words Needed
Each finite field will have a constant value associated with
it. This value Z is equal to 2''' mod n. The value Zallows the 5 163 bit
163 bit
8 bit
16 bit
21
11
portion of e above the (k+1) to be reduced. 163 bit 32 bit 6
163 bit 64 bit 2
In operation, the register 2002 is loaded with the value e
and is split into an upper portion 2003 and a lower portion
2004. 10 Computing the necessary number of machine words
The upper portion 2003 holds all words past the (k+1) requires a simple calculation of the maximum field size
word of e. needed divided by the machine word size, rounded up to an
integer.
The upper portion 2003 and the constant Z 2008 are pro Once this number is found, a multiplier may be imple
vided to the multiplier 2006. The result of the multiplication 15 mented that is able to use any finite field with m less than the
is stored in register 2008. The registers 2008 and 2004 are predetermined number. Elements may be stored in registers
operated on by XOR 2010 to provide a result in register 2012. as in the preferred embodiment, with unused bits. These
The result in register 2012 will typically be fewer words in elements may be added by using an adder as in FIG. 3 with
length than the value e, since the constant Z 2008 is smaller more machine words in each register and more XOR gates.
than n. Although the invention has been described with reference
Further repetitions 2014 may be necessary to her reduce to certain specific embodiments, various modifications
the value 2012. thereof will be apparent to those skilled in the art without
departing from the spirit and scope of the invention as out
After a suitable number of repetitions, the register 2012 lined in the claims appended hereto.
will contain a value V, which is 1 word longer than n. The extra 25 The embodiments of the invention in which an exclusive
word is reduced by computing a value property or privilege is claimed are defined as follows:
1. A method of performing a finite field operation on ele
ments of a finite field, the method comprising a processor:
r 30
obtaining a first set of instructions for performing the finite
field operation on values representing the elements of
the finite field;
Then a quotient executing the first set of instructions to generate an unre
duced result completing the finite field operation;
obtaining a second set of instructions for performing a
35 modular reduction for a specific finite field;
executing the second set of instructions on the unreduced
result to generate a reduced result; and
providing the reduced result as an output for use in a
is computed. The value V is then equivalent to V-qn mod n, but cryptographic operation.
V-qn is relatively easy to compute and has a relatively small 40 2. The method of claim 1, further comprising receiving a
value. Its value may not be less than n, but it will be equivalent first input indicative of the finite field operation, wherein
to v modulo n and the number of words it occupies will be no obtaining the first set of instructions comprises selecting the
more than the number of words in n. first set of instructions from a plurality of sets of instructions
In the preferred embodiment, finite field elements are thus each corresponding to a respective type of finite field opera
stored in memory segments larger than the minimum bit size 45 tion. 3. The method of claim 1, further comprising receiving a
required, with the ends of the memory segments falling on a
machine 32-bit word boundary. Operations can be performed second input indicative of the specific finite field.
on these elements by acting on the memory segment as a 4. The method of claim 1, wherein the values representing
whole, while ignoring the extra bits. These 192-bit segments 50 the elements of the finite field are a predetermined number of
are suitable for representing elements of fields Fn with words, and the first set of instructions is executed using a
161sms 192. Each finite field element is represented as 6 memory 5. The
segment large enough to hold the values.
method of claim 1, wherein the finite field operation
machine words, regardless of the size of the finite field. comprises any one of addition, Subtraction, multiplication,
When implementing an elliptic curve cryptosystem, it will Squaring, and inverting.
be known that certain size finite fields will need to be used. 55 6. The method of claim 1, further comprising determining
These will usually lie in a particular range, and there will be one of a plurality of cryptographic protocols, and initiating
some limit to the maximum size of field needed. With current the one of the plurality of cryptographic protocols, wherein
standards, such a range might be 155 to 2-39 bits. Alterna the one of the cryptographic protocols comprises the crypto
tively, in a higher security application, 256 to 512 bits might graphic operation.
be the known range. 60 7. The method of claim 6, wherein the determining the one
In order to deal with several sizes of finitefields, the size of of the plurality of cryptographic protocols comprises receiv
the largest finite field needed is first computed. From this size, ing a third input indicative of the one of the plurality of
a value may be computed indicating how many machine cryptographic protocols.
words are needed to store finitefield elements. This value may 8. A non-transitory computer readable medium comprising
be precomputed and used during the implementation of soft 65 computer executable instructions for performing a finite field
ware. With the upper limit of 239 bits shown above and a operation on elements of a finite field, the computer readable
16-bit word size, 15 machine words would be necessary. medium comprising instructions for:
US 8,666,062 B2
17 18
obtaining a first set of instructions for performing the finite tions for performing a finite field operation on elements of a
field operation on values representing the elements of finite field, the computer readable medium comprising
the finite field; instructions for:
executing the first set of instructions to generate an unre obtaining a first set of instructions for performing the finite
duced result completing the finite field operation; 5 field operation on values representing the elements of
obtaining a second set of instructions for performing a the finite field;
modular reduction for a specific finite field; executing the first set of instructions to generate an unre
duced result completing the finite field operation:
executing the second set of instructions on the unreduced obtaining a second set of instructions for performing a
result to generate a reduced result; and 10 modular reduction for a specific finite field;
providing the reduced result as an output for use in a executing the second set of instructions on the unreduced
cryptographic operation. result to generate a reduced result; and
9. The non-transitory computer readable medium of claim providing the reduced result as an output for use in a
8, further comprising instructions for receiving a first input cryptographic operation.
indicative of the finite field operation, wherein obtaining the 15 16. The cryptographic engine of claim 15, further compris
first set of instructions comprises selecting the first set of ing instructions for receiving a first input indicative of the
finite field operation, wherein obtaining the first set of instruc
instructions from a plurality of sets of instructions each cor tions comprises selecting the first set of instructions from a
responding to a respective type of finite field operation. plurality of sets of instructions each corresponding to a
10. The non-transitory computer readable medium of claim
8, further comprising instructions for receiving a second input respective
17. The
type of finite field operation.
cryptographic engine of claim 15, further compris
indicative of the specific finite field.
11. The non-transitory computer readable medium of claim ing instructions for receiving a second input indicative of the
8, wherein the values representing the elements of the finite specific finite field.
18. The cryptographic engine of claim 15, wherein the
field are a predetermined number of words, and the first set of
instructions is executed using a memory segment large is determined values representing the elements of the finite field are a pre
enough to hold the values. number of words, and the first set of instructions
12. The non-transitory computer readable medium of claim is executed using a memory segment accessible to the pro
8, wherein the finite field operation comprises any one of cessor which is large enough to hold the values.
19. The cryptographic engine of claim 15, wherein the
addition, subtraction, multiplication, squaring, and inverting. finite field operation comprises any one of addition, subtrac
13. The non-transitory computer readable medium of claim to tion, multiplication, squaring, and inverting.
8, further comprising instructions for determining one of a
plurality of cryptographic protocols, and initiating the one of ing20.instructions
The cryptographic engine of claim 15, further compris
for determining one of a plurality of crypto
the plurality of cryptographic protocols, wherein the one of graphic protocols, and initiating the one of the plurality of
the cryptographic protocols comprises the cryptographic cryptographic protocols, wherein the one of the crypto
operation.
14. The non-transitory computer readable medium of claim graphic protocols comprises the cryptographic operation.
35
13, wherein the determining the one of the plurality of cryp 21. The cryptographic engine of claim 20, wherein the
tographic protocols comprises receiving a third input indica determining the one of the cryptographic protocols comprises
tive of the one of the plurality of cryptographic protocols. receiving a third input indicative of the one of the plurality of
15. A cryptographic engine comprising a processor and cryptographic protocols.
memory, the memory storing computer executable instruc ck ck ck ck ck