US7372960B2 — 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.
USOO7372960B2
(12) United States Patent (10) Patent No.: US 7,372,960 B2
Lambert (45) Date of Patent: May 13, 2008
(54) METHOD AND APPARATUS FOR 6,199,086 B1* 3/2001 Dworkin et al. ............ TO8/492
PERFORMING FINITE FIELD 6,230,179 B1* 5/2001 Dworkin et al. ............ 708/492
CALCULATIONS 6,263,081 B1* 7/2001 Miyaji et al. ................. 380/28
6,430.588 B1* 8/2002 Kobayashi et al. ......... 708/492
75 6,466,668 B1 * 10/2002 Miyazaki et al. ............. 380,30
(75) Inventor: Robert J. Lambert, Cambridge (CA) 6,480,606 B1 * 1 1/2002 Kurumatani ......... ... 380,30
6,618,483 B1* 9/2003 Vanst tal. ............. 380,30
(73) Assignee: Certicom Corp., Mississauga (CA) 6,714,648 B2* 3/2004 NCE A. - - - - - - - - - - - - - 380,30
7,286.666 B1 * 10/2007 Coron ... ... 380,30
(*) Notice: Subject to any disclaimer, the term of this 2002 ois040. As oooo vanston. ... 380,30
past its, s
M YW- y
listed under 35
ayS.
2003/0021410 A1* 1/2003 Miyazaki et al. ............. 380,30
* cited by examiner
(21) Appl. No.: 10/058,212 Primary Examiner Christopher Revak
22) Filed: Jan. 29, 2002 Assistant Examiner Kaveh Abrishamkar
(22) File an. Ad (74) Attorney, Agent, or Firm Blake, Cassels & Graydon
(65) Prior Publication Data LLP, John R. S. Orange: Brett J. Slaney
US 2003/O123654 A1 Jul. 3, 2003 (57) ABSTRACT
Related U.S. Application Data In general terms, the invention provides a finite field engine
(60) Provisional application No. 60/343,227, filed on Dec. and methods for operating on elements in a finite field. The
31, 2001, provisional a lication No. 60/343,226 finite field engine provides finite field sub-engines suitable
filed on D. 31, 2001 El application No. for any finite field size requiring a fixed number of machine
6O7343.223 filedon Dec. 31, 2001, provisional appli- words. The engine reuses these engines, along with some
cation No 60f343,220, filed O De 31, 2001 general purpose component or specific component providing
s1-1 ws • - us modular reduction associated with the exact reduction (poly
(51) Int. Cl. nomial or prime) of a specific finite field. The engine has
HD4L 9/00 (2006.01) wordsized
- 0 Suitable code capab
capable of adding, 9. Subtracting,
9.
(52) U.S. Cl 380/28: 380/44: 713/169 multiplying, squaring, or inverting finite field elements, as
Oa - -- - ---- ----- ------ --- ------ -- s 73/7 long as the elements are representable in no more than the
given number of words. The wordsized code produces
(58) Field Elisatist Stars, 'search hist 380/47
ee appl1cauon Ille Ior complete searcn n1story.
unreduced values. Specific reduction is then applied to the
unreduced value, as is suitable for the specific finite field. In
(56) References Cited this way, fast engines can be produced for many specific
finite fields, without duplicating the bulk of the engine
U.S. PATENT DOCUMENTS instructions (program).
5,982,895 A * 11/1999 Dworkin et al. ............ 380,271
6,049,815. A * 4/2000 Lambert et al. ............ TO8/492 9 Claims, 15 Drawing Sheets
Finite Field Engine
Finite field
parameters 410
Finite field routines Wordsized
Algorithms
FFAddition -
w 8 Addition
F. Field FF Multiplication Multiplication
eduction FF Squaring Squaring
Inversion
FF Subtraction Subtraction
U.S. Patent May 13, 2008 Sheet 1 of 15 US 7,372,960 B2
22
20 24
2s
Network 18
100 List of Curves
200 Cryptographic Engine
300 Elliptic Curve Engine
400 Finite Field Engine
U.S. Patent May 13, 2008 Sheet 2 of 15 US 7,372,960 B2
00
First Elliptic Curve Second Elliptic
Curve
Parameters 102 Parameters 112
Finitefield 103 Finite field 113
Private key 104 Private key 114
Public key 105
Cryptographic engine
Protocols
ECSA 2
MOW 2 4.
6
Elliptic Curve Pointers Finite Field Pointers
ECAddition
EC Scalar Multiplication
EC Double
Figure 3
U.S. Patent May 13, 2008 Sheet 3 of 15 US 7,372,960 B2
Elliptic Curve Routines Finite Field Pointers
ECAdditi FFAddition
Of Th FF Multiplication
EC Scalar Multiplication FF Squaring
EC Oouble
FF inversion
FF Subtraction
Finite Field Engine
Finite field
parameters 410
43 O.
Finite field routines Wordsized
Algorithms
-
u v r Addition
Finite Field FF Multiplication Multiplication
Reduction FF Squaring Squaring
inversion
FF Subtraction Subtraction
Figure 5
U.S. Patent May 13, 2008 Sheet 4 of 15 US 7,372,960 B2
20
Protocol
Protocol Steps
Retrieve P from curve
parameters 100 (Figure 1)
was w w w - we as a s a w w v v vs - - - - - a a - - - - - w w - - - - - - - - - - as
Select Scalar Elliptic
pti Curve Operations
710 f : 8
Multiplication
Figure 7
as a ww w w w w s - as a a a a a is w w w w w - - a few is a v a wwy
v w w w w w we as a sara as A as to a a is us w w y was a as a a v y y vs see h is as a
714 Call FFEngine Finite Field Operations
U.S. Patent May 13, 2008 Sheet 5 of 15 US 7,372,960 B2
. . . . . . . . . . . . . . . . . . . . . . . . ss w w w - - - - a a n us v v e n v r u v v was vv u v Y -
Initialization
804
Retrievek, r from memory Retrieved from curve
16 (Figure 1)
ses as s - a sy, as a a us gru o or - as as a P was we r - 4a air rv r - - -
Finite Field Operations
904 Wordsize Multiply e, r
U.S. Patent May 13, 2008 Sheet 6 of 15 US 7,372,960 B2
1002
7AN
MY
VV e
d|AN
V1
/N
V/
w2
LL - -
Figure 11
U.S. Patent May 13, 2008 Sheet 7 of 15 US 7,372,960 B2
Store wo as wol, ... wOn 1202
Store was w11, ..., Wiln 1204
1206
X0(XOR) X1 1208
Store w? = X0CXOR) Xli
Figure 12
U.S. Patent May 13, 2008 Sheet 8 of 15 US 7,372,960 B2
W01 W02 WO3-...... wOn-2 wOn-WOn
T TOT...I -
W11 W12 w3 W1 n-2 win-1 win
us r - a a
Figure 13
U.S. Patent May 13, 2008 Sheet 9 Of 15 US 7,372,960 B2
Store wo as woi, w11,..., won 0.
Store wi as will, ... win 404
Establishwa, wi 1406
Accumulate partial products 408
(wOi)(wlj) into w}, w2
Provide convolution as was, w) 140
Figure 14
U.S. Patent May 13, 2008 Sheet 10 of 15 US 7,372,960 B2
1512 1510
tooloowo
1514
locom
)) 1520
1536
up to P 8 1522
Shift )D
1524
to 1534 s
Intermediate Register from 1536
Figure 15
U.S. Patent May 13, 2008 Sheet 11 of 15 US 7,372,960 B2
1512a 1S10a
coloronto
154a
locom
D 1S20a
1536a
Shift . a O. P. p. 8 or u u ur so us 152
1524a
w
1526a
)) 1530a
1528a word Shift
Intermediate Register 1534a
--real- 1540a
accumulae
from 1536a Figure 15a
U.S. Patent May 13, 2008 Sheet 12 of 15 US 7,372,960 B2
1602
Method of inversion
Multiplication
Wordsized Wordsized Wordsized
Addition Inversion Multiplication
1622 1624 1626 628
Figure 16
U.S. Patent May 13, 2008 Sheet 13 of 15 US 7,372,960 B2
U.S. Patent May 13, 2008 Sheet 14 of 15 US 7,372,960 B2
1912
1,6
l,6
1914 1916
2.5 2.5
16 2.5
1918 3,4 3,4 1920
2,5 34
1722
1922 4,3 4,3 1924
3,4 43
1722
1928 1930
1926 5.2 5.2 5.2
4,3 5,2 6,1
1722
Figure 19 6,1
6, 1
1932
U.S. Patent May 13, 2008 Sheet 15 of 15 US 7,372,960 B2
2002
2003 2004
2008
2008
2014
2014 Register 2012
Figure 20
US 7,372,960 B2
1. 2
METHOD AND APPARATUS FOR a higher security level than do Smaller key sizes, since the
PERFORMING FINITE FIELD time required for an attack on the system depends on the
CALCULATIONS total number of possible keys, however, different key sizes
require defining different elliptic curves over different finite
This application claims the benefit of U.S. Provisional fields. Generally, the greater the desired cryptographic
Applications Nos. 60/343,226, 60/343,227, 60/343,220, strength of the ECC, the larger will be the size of the finite
60/343,223, all filed on Dec. 31, 2001, the contents of each field.
of which are incorporated herein by reference. Thus an implementation of elliptic curve cryptography
may need to support several different finite fields for use in
FIELD OF THE INVENTION 10 particular applications. Implementing an elliptic curve cryp
tosystem therefore requires either the implementation of
The invention relates to finite fields, and more particularly specific methods for each finite field or a generic method
to a finite field engine for use with cryptographic systems. usable in any finite field. Each approach offers different
advantages.
BACKGROUND OF THE INVENTION 15 The use of specific methods for each finite field leads to
more efficient code since it may be optimized to take
Cryptography is commonly used to provide data security, advantage of the specific finite field However, Supporting
integrity, and authentication over unsecured communication several finite fields in this way will increase the code size
charnels. For example, a connection between two correspon dramatically.
dents over the Internet or a wireless network could easily be The use of a generic method prevents the use of optimi
monitored by an eavesdropper. To protect their confidenti Zation techniques, since the code cannot take advantage of
ality, the correspondents could encrypt their transmissions any particular properties of the finite field. This makes the
with a secret key. They could also use various cryptographic code less efficient but has the advantage of much smaller
protocols to provide authentication of the other party. Tra code size.
ditional protocols using symmetric-key cryptography 25 Many implementations of elliptic curve cryptosystems
require that the correspondents share a secret key before employ binary finite fields, that is fields of characteristic 2.
initiating secure communications. This key must be shared In these fields, elements may be represented as polynomials
through some secure channel, which may be difficult and with binary coefficients, which may be represented as bits in
expensive to obtain. However, the correspondents can avoid hardware or software. These bits must then be represented in
having to share a secret key ahead of time by using public 30 the memory storage of the computer system. Other imple
key cryptography. mentations use fields of prime characteristic p greater than
Correspondents using public key cryptography each have 2. In these fields, elements are usually represented as inte
a private key and a corresponding public key. The derivation gers less than p.
of the public key is such that it is computationally infeasible Software implementation of finite fields raises the ques
to compute the private key given only the public key. 35 tion of how to arrange the storage of the bits corresponding
However, the mathematical relationship between the keys to the finite field elements.
allows them to be used to provide security, integrity, or When using a general purpose computational engine (for
authentication in various protocols where the public keys are example a typical CPU), finite field elements are often too
shared and the private keys are kept secret. long to be represented in a single machine word of the
Elliptic curve cryptography (ECC) is a particularly effi 40 engine (engine word lengths are typically 16, 32 or 64bit).
cient form of public key cryptography that is especially Since the finite field used in ECC operations are typically
useful in constrained environments such as personal digital 160 bits or more, these elements must be represented in
assistants, pagers, cellular phones, and Smart cards. To several machine words.
specify an elliptic curve, a finite field and an equation over Engine routines (programs) that provide finite field cal
that finite field are needed. The points on the elliptic curve 45 culations must therefore deal with multiple machine words
are the pairs of finite field elements satisfying the equation to complete their calculations. If the finite field irreducible,
of the curve, as well as a special point at infinity. To carry or prime is known in advance, then the number of words that
out calculations involving points on the elliptic curve, cal must be dealt with is also known in advance, and more
culations are done in the underlying finite field, according to efficient code can be written that expressly deals with
well-known formulas that use parameters of the curve. 50 exactly the right number of components.
These formulas define an addition operation on a pair of If the finite field irreducible (F2m), or prime (Fp) is not
elliptic curve points. A scalar multiplication operation is known in advance, typically general purpose code is built
defined by repeated additions, analogously to regular integer that can handle any number of word components in the finite
multiplication. An integer n, called the order of the curve, is fields, but this code is typically much slower because of the
the order of the elliptic curve group. 55 overhead of dealing with the unspecified number of com
An elliptic curve cryptosystem may have certain param ponents. The advantage of this general purpose, wordsize
eters common to all users of the system. These could include non-specific code is that the engine description (program
the finite field, the elliptic curve, and a generator point on the size) is Small when compared against specific engines each
curve. These system parameters are often common to a tailored to a specific fete field.
group of users who each generate a key pair comprising a 60 With either type of codes, it is necessary to provide finite
private key and a public key. A correspondent’s private key field operations including multiplication, addition, inver
is an integer less than the order of the elliptic curve, Sion, squaring and modular reduction.
preferably generated at random. The correspondent's public Generally, multiplication of two bit strings representing
key is the elliptic curve point obtained by scalar multipli elements in F" is performed in a similar manner as integer
cation of the private key with a generator point. 65 multiplication between a multiplicand and a multiplier and
The security level of a cryptographic system mainly uses bit shifting and Zero placement. Beginning with the
depends on the key size that is used. Larger key sizes give right most bit (0" position) of the multiplier, the multipli
US 7,372,960 B2
3 4
cand is multiplied by the selected bit. The resulting inter There are several variants on the Extended Euclidean
mediate value is then stored in an accumulator. The multi Algorithm that perform similar computations, such as
plicand is then multiplied by a second bit of the multiplier almost inverses.
located in the 1 position, adjacent to the bit in the 0" Accordingly, there is a need for a method of performing
position. The resulting intermediate value is then stored in a calculations in a binary finite field which obviates or miti
predetermined intermediate value register and shifted to gates some of the above disadvantages.
represent a Zero placeholder, similar to the tens placeholder
in base 10 multiplication. The exclusive or (XOR) of these SUMMARY OF THE INVENTION
two intermediate values, stored in the accumulator and the
predetermined intermediate value register is computed and 10 In general terms, the invention provides a finite field
the result stored in the accumulator. The multiplicand is then engine and methods for operating on elements in a finite
multiplied by the bit in the 2" position of the multiplier and field. The finite field engine provides finite field sub-engines
the intermediate value stored in the predetermined interme suitable for any finite field size requiring a fixed number of
diate value register. The intermediate value is then shifted by machine words. The engine reuses these engines, along with
two places to represent the Zero placeholders and the XOR 15 Some general purpose component or specific component
of the intermediate value and the accumulator is computed. providing modular reduction associated with the exact
The accumulator is then updated with tile new result. These reduction (polynomial or prime) of a specific finite field. The
steps are repeated until the multiplicand has been multiplied engine has wordsized suitable code capable of adding,
with each of the bits of the multiplier ending with the left Subtracting, multiplying, squaring, or inverting finite field
most bit of the multiplier. It will be understood that the bit elements, as long as the elements are representable in no
shifting of the intermediate values corresponds to the place more than the given number of words. The wordsized code
ment of the bit with respect to the number of Zero place produces unreduced values. Specific reduction is then
holders that are required. The final value stored in the applied to the unreduced value, as is suitable for the specific
accumulator is then retrieved and is the product of the finite field. In this way, fast engines can be produced for
multiplicand and the multiplier. 25
many specific finite fields, without duplicating the bulk of
As will be understood, by separately multiplying the the engine instructions (program).
multiplicand and each bit of the multiplier, many bit shifts In accordance with one aspect of the present invention,
are required. In particular, it is necessary to perform bit shifts there is provided a method of adding elements of a finite
for each bit of the multiplier. This results in longer process field Fan where m is less than a predetermined number n is
ing time and also extra processor operation. 30
provided, the method comprising the steps of
Inversion a) storing a first and a second element in a pair of
Inversion in a finite field is usually performed using the registers, each of the pair of registers comprising the
Extended Euclidean Algorithm. In a field with prime char predetermined number of machine words;
acteristic p or irreducible f an element X may be inverted by 35 b) establishing an accumulator having the predetermined
using the EEA to find a solution to the equation: number of machine words:
c) computing for each of the machine words in the
Then ax=1 mod p and asX' mod p accumulator the exclusive-or of the corresponding
(or ax=1 modf and asx' modf) machine words representing each of the first and sec
40 ond elements.
A common technique is to use two starting equations:
In accordance with a further aspect of the present inven
tion, there is provided a device for adding a pair of elements
13+1p=x<p
of a finite field Fin where m is less than a predetermined
number n, comprising: a pair of registers for storing said pair
45
A multiple of the second equation is then subtracted from the words; of elements, each of the registers consisting of n machine
first equation; an accumulator consisting of n machine words; an
output register consisting of n machine words; an XOR gate
connected to a respective machine word in each of the pair
of registers and providing an output to a respective one of
The process continues until a 1 is obtained on the right hand 50 the machine words.
side (RHS).
This process is often shown using a table as in the In accordance with another aspect of the invention, there is
following example of computing 113 mod 239. provided a finite field multiplier operable to multiply two
elements of one of a plurality of finite fields, said finite fields
55 being partitioned into Subsets, said multiplier comprising:
a) a plurality of wordsized finite field multipliers, each
8. b a 113 + b : 239
suitable for multiplying elements of each finite field in
O 1 239 a respective subset of said plurality of finite fields:
-2
1 O
1
113
13 60
b) a finite field reducer configured to perform reduction in
17 -8 9 said one finite field;
-19 9 4 c) a processor configured to
55 -25 1
i) operate the wordsizcd finite field multiplier suitable
for use with said one finite field to obtain an inter
Thus 55-113-25-239=1 and 55=113 mod 239. 65 mediate product; and
It will be recognized that it is not necessary to keep track ii) operate said finite field reducer on said intermediate
of the “b’ values. product to obtain the product of the two elements.
US 7,372,960 B2
5 6
In accordance with yet another aspect of the present inven FIG. 9 is a schematic representation of a finite field
tion, there is provided a method of performing a finite field multiplication in the method of FIG. 8
operation on two elements r, S of a finite field, comprising FIG. 10 is a schematic representation of a memory
the steps of: segment used by the finite field engine 400 of FIG. 5.
a) performing a wordsized operation of r and S, said FIG. 11 is a schematic representation of a device used by
wordsized operation corresponding to said finite field the finite field engine 400 shown in FIG. 5 to add two finite
operation; field elements.
b) performing a modular reduction of the result of step a); FIG. 12 is a flowchart illustrating the steps of a method
In accordance with still another aspect of the present inven using the device of FIG. 11.
tion, there is provided a finite field engine for performing a 10 FIG. 13 is a schematic representation of a finite field
finite field operation on at least one element of a finite field multiplication operation performed by the finite field engine
chosen from a set of finite fields, said set of finite fields being 4OO of FIG.S.
divided into Subsets according to their word size, compris FIG. 14 is a flow chart illustrating the steps of a method
1ng: 15
according to FIG. 13.
a) a finite field operator for each of said subsets; FIG. 15 is a schematic representation of a multiplication
b) a finite field reducer for each of said finite fields: method performed by the finite field engine of FIG. 5.
c) a processor configured to choose the finite field opera FIG. 16 is a schematic representation of a finite field
tor corresponding to the Subset containing said chosen inversion method performed by the finite field engine 400 of
finite field and the finite field reducer for said chosen FIG.S.
finite field and apply the chosen finite field operator to FIGS. 17-19 is a schematic representation of an inversion
said element to produce an intermediate result and method performed by the finite field engine 400 of FIG. 5.
apply the chosen finite field reducer to said intermedi FIG. 20 us a schematic representation of a modular
ate result to obtain the result of said finite field opera reduction method performed by the finite field engine 400 of
tion. FIG.S.
25
In accordance with a still further aspect of the invention,
there is provided a cryptographic system comprising: DESCRIPTION OF THE PREFERRED
a) a plurality of elliptic curves, each specifying elliptic EMBODIMENTS
curve parameters and a respective finite field;
b) a plurality of finite field settings corresponding to each 30 Referring to FIG. 1, a communication system having at
finite field; least two correspondents is shown generally by numeral 10.
c) a plurality of wordsized finite fields, each having A correspondent 12 is connected through a network 18 to a
routines, each finite field being assigned to one of said plurality of correspondents, shown in the example of FIG. 1
wordsized finite fields; as 20, 22, 24, and 26. The to correspondent 12 has a
d) a reduction routine for each finite field; 35 cryptographic unit 13 including a processor 14, a bus 15, a
e) a computational apparatus configured to perform a memory 16, a set of elliptic curves 100 with corresponding
cryptographic operation by the steps of: parameters, a cryptographic engine 200, an elliptic curve
i) selecting one of said elliptic curves; engine 300, and a finite field engine 400. Each of the
ii) performing a cryptographic function using the rou correspondents 20, 22, 24, 26 has a cryptographic unit
tines from the wordsized finite field to which the 40 providing at least one elliptic curve shown as 21, 23, 25, and
respective finite field corresponding to said selected 27, respectively. The correspondent 12 can communicate
elliptic curve is assigned. using public key cryptography with any correspondent
BRIEF DESCRIPTION OF THE DRAWINGS
which has at least one elliptic curve in common with it. In
operation, data is stored in the memory 16 and communi
45 cated over the bus 15. The processor 14 operates to execute
These and other features of the preferred embodiments of an appropriate engine 200,300.400 on the data. The engines
the invention will become more apparent in the following may be software instructions executed by the processor, or
detailed description in which reference is made by way of they may have dedicated coprocessors.
example only to the appended drawings wherein: Referring to FIG. 27, the set of elliptic curves 100 contains
FIG. 1 is a schematic representation of a data communi 50 a plurality of elliptic curves exemplified as a first elliptic
cation system. curve 101, and a second elliptic curve 111. Each curve 101,
FIG. 2 is a detailed view of the list of parameters 100 111 has associated parameters 102, 112 for indicating its
shown in FIG. 1. elliptic curve equation. Each curve 101, 111 also has an
FIG. 3 is a detailed view of the cryptographic engine 200 associated finite field 103, 113. A private key 104, 114 is
shown in FIG. 1. 55 provided for use with each curve, and a corresponding
FIG. 4 is a detailed view of the elliptic curve engine 300 public key 105, 115 derived from a seed point P and the
shown in FIG. 1. private key 104.
FIG. 5 is a detailed view of the finite field engine 400 Referring to FIG. 3, the cryptographic engine 200 com
shown in FIG. 1. prises instruction sets to implement selectively a plurality of
FIG. 6 is a schematic representation of a protocol per 60 protocols 210, exemplified by the ECDSA protocol 212, the
formed by the cryptographic engine 200 in FIG. 3. MQV protocol 214, and others 216. The implementation of
FIG. 7 is a schematic representation of an elliptic curve the protocols 210 requires the use of both elliptic curve
scalar multiplication operation provided by the elliptic curve operations and finite field operations. The protocols 210 are
engine 300 of FIG. 4 and used by the protocol shown in FIG. configured to treat the elliptic curve operations and finite
7. 65 field operations abstractly. Accordingly, the cryptographic
FIG. 8 is a schematic representation of a signature com engine provides pointers 220 to elliptic curve operations and
ponent provided by the protocol 210 of FIG. 8. pointers 230 to finite field operations. The protocols 210 use
US 7,372,960 B2
7 8
the pointers 220 and 230 to perform selectively the elliptic To computer, the ECDSA protocol 212 operates as shown
curve and finite field operations. in FIG. 7. In the initialization phase, the protocol begins the
In use, the processor 14 executes the cryptographic engine computation of kP (702). In this first retrieve k from memory
200 to set the pointers 220 and 230 to use the appropriate 16 of FIG. 1 (704). It must also retrieve P from curve
operations in the elliptic curve engine 300 and the finite field parameters 100 in FIG. 1 (706). The protocol then proceeds
engine 400. More specifically, pointer 222 references an to the elliptic curve operations, by calling the elliptic curve
elliptic curve addition operation, pointer 224 references an engine (708). 2. It selects scalar multiplication (710) with
elliptic curve Scalar multiplication operation, and pointer the input being kP. The scalar multiplication executes double
226 references an elliptic curve double operation. Further, and add routines (712). These routines in turn direct finite
pointer 232 references a finite field (FF) addition operation, 10 field operations by calling the finite field engine (714).
pointer 234 references a finite field multiplication operation, To compute the signature component s, the ECDSA
pointer 236 references a finite field Squaring operation, and protocol 212 operates as shown in FIG.8. In the initializa
pointer 238 references a finite field inversion operation. A tion phase, it is desired to computes (802). The protocol
pointer 239 references a finite field subtraction operation for must first retrieve k and r from the memory 16 of FIG. 1
use in finite field F of prime characteristic. (A separate 15 (804). It must also retrieved, the long-term private key, from
Subtraction operation is not necessary in Fn because Sub the curve parameters 100 of FIG. 1 (806). It then inputs the
traction is the same as addition since the field of character hash of a message e (808). The protocol proceeds with finite
istic 2). field operations by calling a finite field multiplication (810)
As can be seen from FIG. 4, the elliptic curve engine 300 ofe and r to obtain er. The protocol then executes a finite
comprises a plurality of elliptic curve routines 320 corre field addition of d and er (812) to obtain der. The protocol
sponding to the pointers 220 in the cryptographic engine executes a finite field inversion of k (814) to obtain k". The
200. There is a corresponding operation for each pointer protocol then executes a finite field multiplication ofk' and
222, 224, 226 namely an elliptic curve addition operation d+er (816). The result of this multiplication is a signature
322, an elliptic curve scalar multiplication operation 324 and component S (818). The signature component S is then
an elliptic curve double operation 326. Each elliptic curve 25 provided to the remainder of the protocol.
operation 320 requires certain finite field operations, and so Referring particularly to FIG. 9, the finite field multipli
accordingly pointers 330 are provided to operations in the cation 810 within the finite field engine 400 is shown
finite field engine 400, corresponding to the pointers 230 in generally by the numeral 900. To perform finite field mul
the cryptographic engine 200. tiplication 902 of e and r, the finite field engine executes 904
30 a wordsized multiplication of e and r. The result of the
Referring to FIG. 5, the finite field engine 400 is shown
in more detail. Each finite field has associated parameters wordsized multiplication is passed 906 to the finite field
410, which detail the characteristic of that finite field and its reduction 450. The finite field is first identified 908, and then
word size. A plurality of finite field operations shown a specific reduction 910 is executed. The specific reduction
generally at numeral 430 are provided, corresponding to the corresponds to the particular finite field identified.
set of pointers 230 and 330 in the cryptographic engine and 35 It may be seen that computations on finite field elements
the elliptic curve engine, respectively. Accordingly, a finite are performed by the finite field engine 400. Accordingly, the
field addition operation 432, a finite field multiplication data storage in the finite field engine 400 determines the
operation 434, a finite field squaring operation 436, and a nature of the data that is passed between the various engines
finite field inversion operation 438 is provided. A finite field 40 and computed by them.
subtraction operation 439 is provided for use in finite fields Finite field elements are stored by the finite field engine
F. Each finite field operation 430 makes use of wordsized The inmost 400 memory segments larger than are actually required.
significant bits are set to 0. Operations can be
algorithms 440, which are provided for each word size and
described below. A plurality of specialized reduction algo performed on these elements by acting on the memory
rithms 450 is provided, there being one reduction algorithm 45 segment as a whole, while ignoring the extra bits. This
for each field in the list 410. representation is referred to as a “wordsized’ representation.
The data passed between the engines 200, 300, 400 The finite field engine 400 provides finite field routines
comprises finite field elements, since an elliptic curve point 430 for use by the cryptographic engine 200 and the elliptic
consists of two finite field elements. The finite field elements curve engine 300. When these finite field routines 430 are
are only operated on directly by the finite field engine 400, 50 called, the finite field engine 400 uses the parameters of the
and are stored as a set of words in the format shown below finite field 410 to choose the appropriate wordsized algo
in FIG. 10. rithm 440. After applying the wordsized algorithm 440, the
Referring to FIGS. 6 through 9, one of the protocols 210 finite field450. engine reduces the result using a finite field
requires steps 610 which call operations from the elliptic reduction a certain finite
The finite field reduction may be specific to
field, or a wordsize reduction. The reduction
curve engine 300 and the finite field engine 400. Typically, 55 should lower the length
a protocol 210 may call elliptic curve scalar multiplication length of the underlying of the result to the appropriate word
622, elliptic curve addition 624, elliptic curve double 626 may be consistently stored inThis field. way, finite field elements
and may call finite field operations directly such as addition length. The reduction need not to be the of
registers the same word
632, multiplication 634, and inversion 636. The order of the but need only be enough to ensure that the result fitsreduction
minimal
into the
calls and the data passed to them is determined by the 60 given number of words.
specific one of the protocols 210. Referring therefore to FIG. 10, an exemplary memory
In one exemplary protocol, the ECDSA protocol 212 segment 1000 provides a fixed number of machine words
requires the computation of two signature components rand w0, w1, ..., wis. The use of 6 words is by way of example
S, which are given by the formulas: only and to provide for clearer presentation. An element is
65 stored with the least bit on the least bit of w0 and ending
before the most significant bit of wis, as shown generally by
numeral 1001. Certain bits 1002 are unused in this repre
US 7,372,960 B2
10
sentation. Alternative representations and orderings of the words. When the finite field is Fp, the addition is composed
bits are possible. In order to perform the operations taking of integer addition of the components, proceeding from the
advantage of the data structure of the memory segment least significant to the 1-5 most significant word of the
1000, the finite field engine 400 has to implement funda representations, and also propagating the carry into the
mental finite field operations of addition, multiplication, addition of the next most significant words.
inversion, and modular reduction. Particular implementa Similarly, for subtraction (which is distinct from addition
tions of these operations are described below. in Fp), word-wise subtraction is composed of word-wise
Wordsized Addition Subtractions, proceeding from the least significant to the
most significant word of the representations. Since a nega
Referring to FIG. 11, a wordsized circuit 1100 implement 10 tive value
ing finite field addition 432 of two finite field elements w0 must handlecanthisbepossibility.
generated by this process, the reduction
and w1 of a given word length is shown. Each element is
stored comprising 6 machine words as shown in FIG. 10. Wordsized Multiplication
The memory segment corresponding to the first element w0 Referring to FIG. 13, a wordsized data storage used for
is made up of the machine words w00, w01, . . . . w05. 15 multiplying two elements is shown generally by the numeral
Similarly, the memory segment corresponding to the second 1300. The first element w() is stored in a register 1302 and
element w 1 is made up of the machine words w10, the second element is stored in a register 1304. A pair of
w11, . . . . w15. Each corresponding pair is connected to a registers 1306 w2 and w8 are provided to store the product
respective XOR circuit x0, x1,..., x5. That is, w00 and w 10 of w() and w1. The use of two registers is merely to use
connect to X0, w01 and W11 connect to X1, and so on. registers of consistent size for convenience of presentation,
Each XOR circuit is further connected to memory seg however, the registers 1306 could be provided by one
ment W2 comprising the 6 machine words w20, W21, . . . . register of greater length.
w25. Each XOR circuit is connected to the corresponding Referring to FIG. 14, a wordsized method of multiplying
machine word. That is, XO connects to w20, x1 connects to the elements of FIG. 13 is shown generally by the numeral
w21, and so on. To add two elements, the XOR circuits X0, 1400. To begin, the element w0 is stored 1402 as words wO1,
X1, . . . , X5 each XOR the corresponding machine words 25 w02. . . . . wOn in the register 1302, and the element w 1 is
(w00, w10), . . . , (w05, w 15) and store the result in the stored 1404 as words w11, w12, . . . . wiln in the register
corresponding output machine words w20, W11, . . . . w25. 1304. Then the registers w2 and w? are established 1406.
so that w2=w00+w 10 and so on. The method then entails accumulating 1408 partial products
The XOR circuits may be implemented by an arithmetic 30 formed from a word of wo and a word of w 1 into the
logic unit and a bus structure in a CPU. To add two elements registers w2 and w8. After all of the partial products are
w0, w1 of a finite field stored in this representation, the accumulated, it provides 1410 the convolution as the regis
processor cycles through the 6 machine words w01, . . . . ters w3 and w2.
w05 and w10, . . . . w 15 representing each finite field Referring therefore to FIG. 15, a finite field multiplier
element, and applies an exclusive-or (XOR) operation 35 1510 includes a pair of registers 1512, 1514. The register
denoted by €D to the corresponding machine words. The 1512 contains the multiplicand, indicated by the binary
result of this exclusive-or operation is stored in the corre string 100101011110, and the register 1514 the multiplier
sponding machine word of the set of machine words represented by the binary string 10100111. The register 1514
w20, . . . . w25 reserved for the result of the addition is subdivided into words, in this example each of 4 bit length
operation. That is: 40 and a pointer 1516, 1518 is associated with one bit of each
word.
The register 1512 and the output of each pointer 1516,
1518 are connected to an XOR function 1520, 1522 respec
w21 = w01 (ew 11 tively and the result of the XOR stored in registers 1524,
45 1526.
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 word to the left.
Then, the memory segment W2 contains the Sum of the 50 The output of the registers 1524, 1526 is connected to an
two finite field elements w() and w1, represented as the 6 XOR function 1530 whose result is stored in an intermediate
machine words w20, . . . , w25. register 1532. A shift signal 1534 is applied to register 1532
Referring therefore to FIG. 12, a wordsized method for from a shift control 1536 that also controls the position of
adding two elements 1200 of a given word length involves pointers 1516, 1518 on register 1514. The intermediate
first storing the first element in a memory segment compris 55 register 1532 is connected to a XOR function 1538 that also
ing a plurality of machine words 1202, and storing the receives the output of an accumulating register 1540.
second element in a memory segment comprising a plurality The shift control 1536 operates to consider all bit posi
of machine words 1204, as in FIG. 3. Then a counter is tions within 1 word in a specified order. In this example,
initialized 1206 to initiate a loop through the machine words. there are 4 bit positions to consider. The following are
At each iteration, an XOR of two machine words is com 60 performed for each bit position. The pointers 1516, 1518 are
puted 1208, and stored in the appropriate output machine set to a bit position by the shift control 1536. The pointer
word 1210. When the counter is less than the number of 1516 reads the bit in the bit position in the first word. The
machine words 1212, the counter is incremented 1214, and pointer 1518 reads the bit in the bit position in the second
the loop repeated. When the counter reaches the number of word. For example, when the 2" bit position is considered,
machine words 1212, the method terminates 1216. 65 the second bit of each word is read by the respective pointer.
The above method describes a wordsize addition for F2m, After the bits are retrieved, the contents of the register
where the addition is composed of XOR's of the component 1512 is read and XOR'd by the functions 1520, 1522. The
US 7,372,960 B2
11 12
results are stored in the registers 1524, 1526. For the bit of (AB)+high (AB)+high (AB)+high (AoE)+C. low
the first word, the value of register 1512 is simply stored in (AB)+low(AB)+low(AB)+low(AB)+high (AB)+
the register 1524 since the value of the bit is 1. The result of high (A,B)+high (A.B.)+C, low(A,B)+low(A,B)+low
multiplication between the multiplicand and the bit of the (AB)+high (AB)+high (AoE)+C low(AB)+low
second word is stored in the register 1526. Since the bit of 5 (AB)+high (AB)+Co., low(AB) P.P.P.P.P.P.,
the second word is 0, the register 1526 has a value of 0. P.P., the unreduced Product.
Register 1526 is then shifted by shift function 1528 accord Here C, is the carry out of word i of the Product (not
ing to the bit size of the word. In the present example, since necessarily 0 or 1, but in general possibly larger).
the word size is 4 bits, the intermediate value is shifted 4
places in the form of a single word shift. The word shift may 10 Similarly, specific wordsize squaring for F is constructed
be effected by offsetting the registers 1524, 1526 at the input similarly to multiplication. Since for squaring, Ai-Bi,
slightly more than half the products need to be computed.
to XOR 1530. The two intermediate values in registers 1524,
1526 are then XOR'ed by the function 1530 with the Wordsized Inversion
resulting value stored in the intermediate register 1532. The Referring to FIG. 16, a wordsized method of inverting an
shift signal 1534 performs bit shifts on register 1532 in 15 element is shown generally by the numeral 1600. Finite field
accordance with the bit position of pointers 1516, 1518. In inversion is performed using the Extended Euclidean Algo
this way, one bit shift is applied to each component 1524, rithm, which is based on computing the following remain
1526 of the intermediate register instead of performing ders:
separate bit shifts as in the prior art. The contents of register
1532 are XOR'd with the contents of an accumulator 1540
by the function 1538 and the result stored in the accumulator fo = q1 + 2
1540. The process is repeated for each bit and at its con
clusion, the accumulator holds the result of the multiplica rl = 42 2 + 3
tion.
Whilst, it is recognized that the bits may be considered in 25
any order, it is generally simpler to order the bits by their in-2 in-lin-1 in
significance. One option is to consider the bits from least in-1 in in
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 30 Each remainder requires the computation of a quotient q.
second word, i.e. 0. The pointers move to the next more and then determining the remainder by multiplication and
significant bit on each repetition and finish with the most
significant bit. subtraction. Intermediate values are stored, one of which is
An alternative order, which provides a further reduction in equal to the inverse at the end of the algorithm. There are
the number of bit shifts required, is to consider the bits from as thevariants
35 many of the extended Euclidean Algorithm, known
binary inverse, almost inverse etc. Each of these
most-significant to least significant. In this case, a circuit as
shown in FIG. 15a may be used. This circuit differs from methods uses certain fundamental operations of addition,
FIG. 15 in that bit shifts are performed on the accumulator. division, multiplication, Subtraction, etc.
In this way, each bit shift affects previous computations, so When the elements are stored as shown in FIG. 6, the
that only 1 bit shift is required for each bit considered. 40 inversion is implemented by following the same steps, but
Referring therefore to FIG. 15a, a finite field multiplier is using generic methods for the addition, division, multipli
shown with like components to FIG. 15 having a suffix a for cation, and Subtraction. Accordingly, a finite field inversion
clarity. Accordingly, registers 1512a, 1514a, pointers 1516a, method 1602 calls addition 1612, division 1614, multipli
1518a, XOR functions 1520a, 1522a, registers 1524a, cation are
1616, and subtraction 1618. These basic operations
implemented by using generic methods for addition
1526a, intermediate register 1532a, XOR function 1538a, 45
1622, division 1624, multiplication 1626, and subtraction
and accumulating register 1540a are provided as in FIG. 15.
However, a shift signal 1534a is applied to accumulator 1628. In fact, inversion will after re-implement these opera
tions as function calls.
1540.
The above method describes a wordsize multiplication for In a preferred method of inversion it is recognized that
Fr. For F, the multiplication operation is composed of 50 whilst two values (“b' and “ax-i-bp') must be stored for each
iteration, the number of words required to store each
wordsized multiplications. Again the finite field multiplica
tion is composed of a wordsized non-reducing multiplica changes. There is a leveling process such that the “ax+bp'
tion, coupled with a specific reduction engine preferably quantity is always getting Smaller and the 'a' quantity tends
tailored to the specific finite field. to get bigger.
If the element A is composed of four words A3, A2, A1, 55 Referring to FIG. 17, a schematic drawing of sample
AO), and this value is to be (non-reducing) multiplied with calculations paths is shown. A plurality of dedicated com
B, also composed of four words B3, B2, B1, BO, then the putationalong
engines 1712, 1716, 1718, and 1720 are provided
with general purpose computational engines 1722.
non reducing multiplication contains instructions that con
struct the unreduced product. Multiplying the words A, B, 60 The calculation paths used by the engines are shown gen
yields two words. Let the high word be denoted by high erally as numeral 1710. The dedicated engines 1712, 1716,
and 1720 are specially optimized to process a pair of
(A,B), and the low word by low(A, B).
The non-reducing multiplication to be used in Fp multi parameters with equal word lengths. It is expected these
engines would be used the most and accordingly they are the
plication would then compose the unreduced product most optimized. The dedicated engines 1714, 1718, are
high (AB)+C6, low(AB)+high (AB)+high (AB)+C5. 65 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 word length engines, since they are
US 7,372,960 B2
13 14
expected to be used a bit less. Accordingly, the fastest 54 steps follow at this alignment until the following is
calculation path is to involve only the dedicated engines obtained
1712, 1716, and 1720. Occasionally, the word length of the 114BC058 60000000 00000000, 50628345 A834DC60
parameters will vary further, and the dedicated engines CA40E435 809ECB43 EAE015AD C0000000, 00000006
1714, 1718 may need to be used. In this case however, the 3F872A57 1FCBF672 6C3ET9F3 6633CEBB
leveling process of the Euclidean Algorithm will tend to At this stage the RHS differs by 1 since the word sizes are
yield the result which lies on the most efficient calculation 3, 4 and 2, 5 and so the dedicated processor indicated at 1918
path. In some situations, the parameters will require the use is used.
of a general-purpose engine 1722. These engines need not
optimized and their use usually imposes a performance 10 are2 obtained.
steps follow at this alignment until equal word lengths
penalty when compared with the fastest calculation path.
However, the output of the general-purpose engine is likely FBABD5F5 AO000000 00000000, 50628345 A834DC60
to be closer to the optimal calculation path. Engine 1724 CA40E435 809ECB43 IDSC02B5 B8000000 00000000,
show this tendency of the general purpose entrance to direct CDFCB52256FFE542 54CFD3B8 DCDSAO1F
calculations to the optimal path. 15 54 steps follow at this alignment using engine 1920
The number of dedicated computational engines which 1D3C34DB F2D87350 20000000 00000000, BBF6F1DF
are constructed and used as a matter of trade off between
cost and speed benefit. Each dedicated computational engine CE734830 490EA789 A5080FC5 OAEBD71 20000000,
requires more resources then a general-purpose computa OOOOOOO2 EOC945FEB 2C4C933O EFO4A985
2 steps follow at this alignment using engine 1922
tional engine, however dedicated computational engines
allow for faster execution. While using only dedicated B8343B1E F8337E21 00000000 00000000, BBF6F1DF
computational engines would be quite fast, there would be CET34830 49 OEAT89 2942O3F1 42BAC35C 48OOOOOO
a prohibitive resource requirement. 00000000, 96CFED09 388FF6C0 298.28383
An exemplary circuit used in the method of inversion is 58 steps follow at this alignment using engine 1924
shown generally in FIG. 18. The method of inversion 25 000623FE 2C204627 76BEF5F7 3A000000 00000000,
operates on two equations, having parameters referred to as
L1 (1802) R1 (1804), L2 (1806) and R2 (1808). The 00000000, 00000006 890.9F4B1 346B7361
parameters L1 and L2 correspond to the parameter 'a' and 4 steps follow at this alignment using engine 1926
description of the extended Euclidean Algorithm and the
parameters R1 and R2 correspond the parameters “ax+bp' in 30 BOEABA7E90B7D3CD DD40337D BAO00000 00000000,
description of the extended Euclidean Algorithm. A pair of
results are stored in 1810 and 1812, referred to as L3 and R3. 40000000 00000000, C18D3AFD 898A2FC3
There is a method of determining a multiple (1820), and 52 steps follow at this alignment using engine 1928
subtractors 1822, 1824. In use, component 1820 determines
a multiple of R2 to be subtracted from RI. Then the 35 OOOOOOO1 884.353A4 5D8C8177 E383COC5 A845C9D7 70000000,
B63B14D1 17295.514 353C12F7 8E69441A
subtractors 1822, 1824 subtract the multiple of L2 and R2
from L1 and R1 respectively. The results are stored in L3 A8477158 D8000000 00000000, OEE15DED
(1810), and R3 (1812). The values in L2 and R2 are then 2 steps follow at this alignment using engine 1930
placed in L1 and R1 and the results from L3 and R3 are 221 OD4E9 17632O5D F8EOFO31 6A117275 DCOOOOOO
placed in L2 and R2, for the next iteration. 40
00000000, 6E36924F 9F6A06130 68B09380 6DEA84DF
The following example illustrates a particular sequence of 0002B88F A8000000 00000000, OEE15DED
computations. The calculation path used is shown in FIG. and finally, 38 steps follow at this alignment using engine
19. In this example, it is desired to compute the inverse of 1932 O3A2221E F276742E A140A272 B799BAA1
a value in the finite field F-163. The irreducible is x'+x+ 58A492F7 70000000, 00000001 EBE8CB36 E8AB15
x+x+1. 45
588F9267 7FBCS5589E7D8C26 00000000, 00000013
The first parameters operated on are as follows. Their At each alignment the appropriate dedicated processor is
word sizes are 1, 6 and 1, 6 so engine 1912 is used. selected and used until the alignment conditions are no
80000000, 00000008 00000000 00000000 00000000 longer met. If during the reduction a condition is obtained
OOOOOOOOOOOOOOC9 that in not met by a dedicated processor than the general
50
00000000, 00000007 COAD7A37 E056B29D 011E70FA purpose engines are used until an alignment is again
8D9A9887 58894F25 obtained that meets one of the dedicated processors condi
While decreasing the RHS, 7 steps are performed in the tions. At the final step, the RHS corresponds to a value of a
1 and therefore the inverse for 00000007 COAD7A37
processor 1912 with the RHS of equal word length to arrive
at: 55
E0546B29D 011E70FA 8D9A9887 58894F25 using x'+
x+x+x+1 as the modulus is:
28000000 00000000, 7A1A1334 3DOD08EE 983 ADA97
2D062ESC A45DF765 E0000000, 00000002 1843.125D O3A2221E F276742E A140A272 B799BAA1 58A492F7
OC218F1D 20ACF662. 177E1F53 7OOOOOOO.
It will be recognized that the equal word length processor
47558E6FAt this stage, the RHS differ by 1 since the word 60 is used the most, and the engines located Per from the
sizes are 2, 5 and 1, 6 and therefore processor 1914 is used
for a further 4 steps. The alignment then has equal word optimal path of equal word length engines are used less
often. This embodiment of inversion has been shown with
lengths of five words on the RHS as indicated below so the special purpose engines to handle the case when the right
dedicated processor 1916 can be used on the representation; hand sides have equal word length and when the word
B8000000 00000000, 7A1A1334 3DOD08EE 983 ADA97 65 lengths of the right hand sides differ by one.
2D062E5C A45DF765 03800000 00000000, OA59B49C In another embodiment of inversion, the only special
O52CDA58 BA238E67 6D81 D1B6 DAAECESF purpose engines deployed are those for right hand sides with
US 7,372,960 B2
15 16
equal word length. This embodiment results in Smaller code, required, with the ends of the memory segments falling on
and the equal word length engine is expected to be used the a machine 32-bit word boundary. Operations can be per
most, as exemplified above. With this embodiment, the formed on these elements by acting on the memory segment
engines 1912, 1916, 1920, 1924, 1928, and 1932 are special as a whole, while ignoring the extra bits. These 192-bit
purpose engines, while a general-purpose engine performs segments are suitable for representing elements of fields Fm
the functions of engines 1914, 1918, 1922, 1926, and 1930. with 161sms 192. Each finite field element is represented
It will be recognized that the provision of general-purpose as 6 machine words, regardless of the size of the finite field.
engines and special-purpose engines may be applied to other When implementing an elliptic curve cryptosystem, it will
methods with a similar leveling process, Such as almost be known that certain size finite fields will need to be used.
inverses and other variants of the Extended Euclidean Algo 10 These will usually lie in a particular range, and there will be
rithm. some limit to the maximum size of field needed. With
Modular Reduction current standards, such a range might be 155 to 239 bits.
Modular reduction is preferably provided for each finite Alternatively, in a higher security application, 256 to 512
field that is needed. The modular reduction routine is pro 15 bits might be the known range.
vided with instructions specific to the modulus used. Spe In order to deal with several sizes of finite fields, the size
cialized routines such as those in the EEE P1363 standard of the largest finite field needed is first computed. From this
may be used to perform the modular reduction 450 of the FF size, a value may be computed indicating how many
engine 400. It will be appreciated that by providing particu machine words are needed to store finite field elements. This
lar modular reduction for each finite field, the speed of the value may be precomputed and used during the implemen
method may be optimized. tation of software. With the upper limit of 239 bits shown
In a further embodiment, a method of modular reduction above and a 16-bit word size, 15 machine words would be
using precomputation is provided that may be useful for necessary.
certain reductions. Referring to FIG. 20, a method of per
forming the modular reduction 450 of the FF engine 400 is 25
shown generally by the numeral 2000. Number of Machine
Each finite field will have a constant value associated with Maximum Field Size Machine Word Size Words Needed
it. This value Z is equal to 2 (“") mod n. The value Zallows 163 bit 8 bit 21
the portion of e above the (k+1) to be reduced. 163 bit 16 bit 11
In operation, the register 2002 is loaded with the value e 163 bit 32 bit 6
and is split into an upper portion 2003 and a lower portion 30 163 bit 64 bit 2
2004.
The upper portion 2003 holds all words past the (k+1)
word of e. Computing the necessary number of machine words
The upper portion 2003 and the constant Z 2008 are 35 requires a simple calculation of the maximum field size
provided to the multiplier 2006. The result of the multipli needed divided by the machine word size, rounded up to an
cation is stored in register 2008. The registers 2008 and 2004 integer.
are operated on by XOR 2010 to provide a result in register Once this number is found, a multiplier may be imple
2012. mented that is able to use any finite field with m less than the
predetermined number. Elements may be stored in registers
The result in register 2012 will typically be fewer words in 40 as in the preferred embodiment, with unused bits. These
length than the value e, since the constant Z 2008 is smaller elements may be added by using an adder as in FIG. 3 with
than n.
Further repetitions 2014 may be necessary to further more machine words in each register and more XOR gates.
Although the invention has been described with reference
reduce the value 2012.
After a suitable number of repetitions, the register 2012 45 to certain specific embodiments, various modifications
will contain a value V, which is 1 word longer than n. The thereof will be apparent to those skilled in the art without
departing from the spirit and scope of the invention as
extra word is reduced by computing a value outlined in the claims appended hereto.
50
The embodiments of the invention in which an exclusive
property or privilege is claimed are defined as follows:
1. A method of adding elements of a finite field compris
ing the steps of
Then a quotient a) storing a first element and a second element in respec
55
tive ones of a pair of registers, each of said pair of
registers comprising a first predetermined number of
machine words;
b) establishing an accumulator having a second predeter
60 mined number of machine words;
is computed. The value V is then equivalent to V-qn mod n, c) performing a non-reducing computation of the corre
but V-qn is relatively easy to compute and has a relatively sponding machine words representing each of said first
small value. Its value may not be less than n, but it will be and second elements by taking the exclusive-or of said
equivalent to v modulo n and the number of words it first and second elements to obtain, in said accumulator,
occupies will be no more than the number of words in n. 65 a representation of a unreduced result of the addition of
In the preferred embodiment, finite field elements are thus said elements, and, upon computing said unreduced
stored in memory segments larger than the minimum bit size result:
US 7,372,960 B2
17 18
d) performing a specific modular reduction of said unre a) a finite field operator for each of said subsets;
duced result to reduce said unreduced result to that of b) a finite field reducer for each of said finite fields:
a field element of said finite field to obtain a reduced c) a processor configured to choose the finite field opera
result; and tor corresponding to the Subset containing said selected
e) using said reduced result in a cryptographic operation. 5 finite field and the finite field reducer for said selected
2. A finite field multiplier operable to multiply two finite field and perform a non-reducing computation by
elements of a selected one of a plurality of finite fields, said applying a plurality of applications of the chosen finite
finite fields being partitioned into subsets, said multiplier field operator to said elements to produce an unreduced
comprising: intermediate result and, upon computing said unre
a) a plurality of wordsized finite field multipliers, each 10 duced intermediate result, apply the chosen finite field
suitable for multiplying elements of each finite field in reducer to said unreduced intermediate result to reduce
a respective subset of said plurality of finite fields: said unreduced result to that of a field element of said
b) a finite field reducer configured to perform reduction in selected finite field to obtain the result of said finite
said selected one of said plurality of finite fields; and field operation.
c) a processor configured to: 15 5. A cryptographic system comprising:
i) operate a corresponding one of said plurality of a) a plurality of elliptic curves, each specifying elliptic
wordsized finite field multipliers being suitable for curve parameters and a respective finite field;
use with said selected one of said finite fields to b) a plurality of finite field settings corresponding to each
perform a non-reducing computation of said two finite field;
elements to obtain an unreduced intermediate prod c) a plurality of wordsized finite fields, each having
uct; and routines, each finite field being assigned to one of said
ii) upon computing said unreduced intermediate prod wordsized finite fields;
uct, determine a specific modular reduction corre d) a reduction routine for each finite field;
sponding to said selected one of said finite fields and e) a processor configured to perform a cryptographic
operate said finite field reducer on said unreduced 25 operation by the step of:
intermediate product to reduce said unreduced inter i) selecting one of said elliptic curves; and
mediate product to that of a field element of said ii) performing a non-reducing cryptographic function
selected one of said finite fields to obtain the product using the routines from the wordsized finite field to
of the two elements.
3. A method of performing a finite field operation on 30 which the respective finite field corresponding to said
elements of a finite field, comprising the steps of Selected elliptic curve is assigned to obtain an unre
a) representing each element as a predetermined number duced result, said routines including at least one finite
of machine words; field operation and, upon obtaining said unreduced
b) performing a non-reducing wordsized operation on said result Subsequent thereto, performing a modular reduc
representations, said wordsized operation correspond 35 tion according to said respective finite field to reduce
said unreduced result to that of a field element of said
ing to said finite field operation; respective finite field to obtain a reduced result of said
c) completing said non-reducing wordsized operation for operation in a predetermined number of words.
each word of said representations to obtain an unre
duced result: 6. A method according to claim 3 wherein said modular
d) upon computing said unreduced result, performing a 40 reduction is determined by said finite field.
specific modular reduction of said unreduced result to 7. A method according to claim 3 wherein said finite field
reduce said unreduced result to that of a field element operation is addition.
of said finite field to obtain a reduced result; and 8. A method according to claim 3 wherein said finite field
e) using said reduced result in a cryptographic operation. operation is subtraction.
4. A finite field engine for performing a finite field 45 9. A method according to claim 3 wherein said finite field
operation on elements of a selected finite field chosen from operation is multiplication.
a set of finite fields, said set of finite fields being divided into
Subsets according to their word size, comprising: k k k k k