US7372961B2 — Method of public key generation
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.
USOO7372961 B2
(12) United States Patent (10) Patent No.: US 7,372,961 B2
Vanstone et al. (45) Date of Patent: May 13, 2008
(54) METHOD OF PUBLIC KEY GENERATION See application file for complete search history.
(75) Inventors: Scott A. Vanstone, Campbellville (CA); (56) References Cited
Ashok Vadekar, Rockwood (CA); U.S. PATENT DOCUMENTS
Robert J. Lambert, Cambridge (CA); 5,073.935 A * 12/1991 Pastor ......................... 380,30
Robert P. Gallant, Mississauga (CA); 6,088,798 A * 7/2000 Shimbo ............ ... T13, 176
Daniel R. Brown, Toronto (CA); 6, 195,433 B1* 2/2001 Vanstone et al. ........... 380.285
Alfred Menezes, West Canada (CA) 6.219.421 B1 4/2001 Backal ........................ 380/28
6,307.938 B1 * 10/2001 Matyas et al. ................ 380, 44
(73) Assignee: Certicom Corp., Mississauga (CA) 6,327,660 B1* 12/2001 Patel ............. ... T13, 193
2002/0116527 A1* 8, 2002 Chen et al. ....... ... TO9.245
(*) Notice: Subject to any disclaimer, the term of this 2003/0084332 A1* 5/2003 Krasinski et al. r T13/200
patent is extended or adjusted under 35 OTHER PUBLICATIONS
U.S.C. 154(b) by 563 days. Schneier, Bruce, "Applied Cryptography”, 1996, John Wiley &
(21) Appl. No.: 10/025,924 Sons, Inc., 2nd edition, pp. 483-490.*
Nel et al., “Generation of Keys for use with the Digital Signature
(22) Filed: Dec. 26, 2001 Standard (DSS)”, 1993, IEEE, pp. 6-10.*
* cited by examiner
(65) Prior Publication Data
Primary Examiner Emmanuel L. Moise
US 2002/0090085A1 Jul. 11, 2002 Assistant Examiner Michael Pyzocha
(74) Attorney, Agent, or Firm Blake, Cassels & Graydon
(30) Foreign Application Priority Data LLP, John R. S. Orange: Brett J. Slaney
Dec. 27, 2000 (CA) .................................... 2329590 (57) ABSTRACT
(51) Int. Cl. A potential bias in the generation or a private key is avoided
H04L 9/08 (2006.01) by selecting the key and comparing it against the system
G06F 7/58 (2006.01) parameters. If a predetermined condition is attained it is
(52) U.S. Cl. ......................... 380/44; 380/277; 708/250 accepted. If not it is rejected and a new key is generated.
(58) Field of Classification Search .................. 380/44,
380/277; 708/250 30 Claims, 7 Drawing Sheets
26
Output RNG
28 -
Perform Hash
Is H(seed) < q? Reject
U.S. Patent May 13, 2008 Sheet 1 of 7 US 7,372,961 B2
Fig. 1 17
U.S. Patent May 13, 2008 Sheet 2 of 7 US 7,372,961 B2
26
Output RNG
28 -
Perform Hash
Is H(seed) < q2 Reject
Fig. 2
U.S. Patent May 13, 2008 Sheet 3 of 7 US 7,372,961 B2
Output RNG
Increment
Perform Hash
Is H(seed) < q2 Reject
Fig. 3
U.S. Patent May 13, 2008 Sheet 4 of 7 US 7,372,961 B2
Output RNG
Increment
Perform Hash
Combine
H(seed)|H(seed +1)
Reject Surplus Bits
Is H(seed) < q2 Reject
Fig. 4
U.S. Patent May 13, 2008 Sheet S of 7 US 7,372,961 B2
Output RNG
Increment
Perform Hash
Combine
H(seed) || H(seed +1)
Increment l bit window
Select bits
Is H(seed) < q2 N Reject
Fig. 5
U.S. Patent May 13, 2008 Sheet 6 of 7 US 7,372,961 B2
26
28
Apply Hash
Selectl bits
Increment l bit window
Is H(seed) < q? N Reject
Fig. 6
U.S. Patent May 13, 2008 Sheet 7 Of 7 US 7,372,961 B2
26
Output RNG
Fig. 7
US 7,372,961 B2
1. 2
METHOD OF PUBLIC KEY GENERATION key of the signatory. The signature on the message m is (r.s).
The signature may be verified by computing
FIELD OF THE INVENTION
The present invention relates to public key cryptosystems 5
and more particularly to key generation within Such systems.
BACKGROUND OF THE INVENTION
v=C." B"mod p, where f3–C' mod p is the long term
The basic structure of a public key cryptosystem is well 10 public key of the signatory and finally verifying that r-V
known and has become ubiquitous with security in data mod q. The use of both the ephemeral and long-term keys in
communication systems. Such systems use a private key k the signature binds the identity of the signatory to the
and a corresponding public key C where C. is a generator of ephemeral key but does not render the long-term key Vul
the group. Thus one party may encrypt a message m with the nerable.
intended recipients public key and the recipient may apply A similar signature protocol known as ECDSA may be
his private key to decrypt it. used for elliptic curve cryptosystems. In this protocol k is
Similarly, the cryptosystems may be used for key agree selected in the interval 1 to n-1 where n is an 1 bit prime. The
ment protocols where each party exponentiates the other signature component r is generated by converting the X
party's public key with their own private key. Thus party A coordinate of the public key kP, where P is the seed point on
will take B's public key C” and exponentiate it with A's the curve, to an integer mod n, i.e. r-X mod n. The
private key a to obtain a session key C.". Similarly, B will component S-k'(H(m)+dr) mod n and the signature on the
take A's public key C. and exponentiate it with B’s private message m is (r.s).
key b to obtain the same session key C.". Thereafter data It will be apparent in ElGamal signature Schemes such as
may be transferred using a symmetric key protocol utilizing 25 the DSA and ECDSA, that if an ephemeral key k and the
the common session key. associated message m and signature (r.S) is obtained it may
Public key cryptosystems may also be used to sign be used to yield the long term private key d and thereafter
messages to authenticate the author and/or the contents. In each of the ephemeral keys k can be obtained. Neither the
this case the sender will sign a message using his private key DSA nor the ECDSA inherently disclose any information
and a recipient can verify the message by applying the public 30 about the public key k. They both require the selection of k
key of the sender. If the received message and the recovered to be performed by a random number generator and it will
message correspond then the authenticity is verified. therefore have a uniform distribution throughout the defined
The public key cryptosystems rely on the intractability of interval. However the implementation of the DSA may be
done in Such a way as to inadvertently introduce a bias in to
the discrete log problem in finite field arithmetic, that is even the
when the generator C. and public key is known, it is 35 a value selection of k. This small bias may be exploited to extract
computationally infeasible to obtain the corresponding pri of the system of the private key d and thereafter render the security
vate key. The security of such systems does therefore depend vulnerable. One such implementation is the
on the private key remaining secret. To mitigate the oppor DSS mandated by the National Institute of Standards and
tunity of disclosing the private key, protocols have been Technology (NIST) FIPS 186-2 Standard. The DSS stipu
developed that use a pair of private keys and corresponding 40 lates
as a
the manner in which an integer is to be selected for use
private key. A seed value, SV, is generated from a
public keys, referred to as long term and short term or random number generator which is then hashed by a SHA-1
ephemeral key pairs respectively. The ephemeral private key hash function
is generated at the start of each session between a pair of typically 160 tobits. yield a bit string of predetermined length,
The bit string represents an integer
correspondents, usually by a random number generator. The
corresponding, ephemeral public key is generated and the 45 between 0 and 2'-1. However this integer could be greater
resultant key pair used in one of the possible operations than the prime q and so the DSS requires the reduction of the
integer mod q, i.e. k SHA-1 (seed) mod q.
described above. The long-term public key is utilized to
authenticate the correspondent through an appropriate pro Accordingly the algorithm for selecting k may be
tocol. Once the session is terminated, the ephemeral key is expressed as:
securely discarded and a new ephemeral key generated for 50 if SHA-1 (seed)2 q then ke-SHA-1 (seed)-q else
a new session. ke-SHA-1 (seed).
Some of the more popular protocols for signature are the
ElGamal family of signature Schemes Such as the Digital With this algorithm it is to be expected that more values will
Signature Algorithm or DSA. The DSA algorithm utilizes lie in the first interval than the second and therefore there is
both long term and ephemeral keys to generate a signature 55 a potential bias in the selection of k.
of the message. The DSA domain parameters are prese Recent work by Daniel Bleichenbacher suggests that the
lected. They consist of a prime number p of a predetermined modular reduction to obtain k introduces sufficient bias in to
length, by way of example 1024 bits; a prime number q of the selection of k that an examination of 2 signatures could
a predetermined bit length, by way of example 160 bits, yield the private key d in 2 steps using 2" memory units.
where q divides p-1; a generator C. lying between 2 and p-1 60 This suggests that there is a need for the careful selection of
and which satisfies the condition (C'modp)=1, and; a cryp the ephemeral key k.
tographic hash function H. Such as SHA-1.
The DSA requires the signatory to select an ephemeral SUMMARY OF THE INVENTION
key k lying between 1 and q-1. A first signature component
r is generated from the generator C. such that r (C. mod p) 65 It is therefore an object of the present invention to obviate
mod q. A second signature component S is generated Such or mitigate the above disadvantages in the generation of a
that s=k'(H(m)+dr) mod q, and d is the long term private private key.
US 7,372,961 B2
3 4
In general terms the present invention provides a key function is performed over a group of order q, where q is a
generation technique in which any bias is eliminated during prime represented as a bit string of predetermined length L.
the selection of the key. By way of example only it will be assumed that the length
L is 160 bits, although, of course, other orders of the field
BRIEF DESCRIPTION OF THE DRAWINGS may be used.
To provide a value of k of the appropriate order, the hash
Embodiments of the invention will now be described by function 28 has an L bit output, e.g. a 160 bit output. The bit
way of example only with reference to the accompanying string generated by the random number generator 26 is
drawings in which: greater than Lbits and is therefore hashed by the function 28
FIG. 1 is a schematic representation of a data communi 10 to produce an output H(seed) of L bits.
cation system; The resultant output H(seed) is tested against the value of
FIG. 2 is a flow chart showing a first embodiment of key q and a decision made based on the relative values. If
generation; H(seed)<q then it is accepted for use as k. If not, the value
FIG. 3 is a flow chart showing a second embodiment; is rejected and the random number generator is conditioned
FIG. 4 is a flow chart showing a third embodiment; 15 to generate a new value which is again hashed by the
FIG. 5 is a flow chart showing a fourth embodiment; function 28 and tested. This loop continues until a satisfac
FIG. 6 is a flow chart showing a fifth embodiment; and tory value is obtained.
FIG. 7 is a flow chart showing a sixth embodiment. A further embodiment is shown in FIG. 3. In this embodi
DESCRIPTION OF THE PREFERRED
ment, the output of the random number generator 26 is
EMBODIMENTS
hashed by hash function 28 as before and tested against the
value of q. If the H(seed) value is not accepted, the output
of the random number generator 26 is incremented by a
Referring, therefore to FIG. 1, a data communication deterministic function and rehashed by function 28.
system 10 includes a pair of correspondents 12, 14 con The resultant value H(seed) is again tested and the pro
nected by a communication link 16. The link 16 may be a 25 cedure repeated until a satisfactory value of k is obtained.
dedicated link, a multipurpose link such as a telephone The output may be incremented by adding a particular
connection or a wireless link depending on the particular value to the seed value at each iteration, or may be incre
applications. Similarly, the correspondents 12, 14 may be mented by applying a non-linear deterministic function to
computer terminals, point-of-sale devices, automated teller the seed value. For example, the output may be incremented
machines, constrained devices Such as PDAs, cellphones, 30 by applying the function f(seed)=a.seed--b mod 2", where
pagers or any other device enabled For communication over a and b are integer constants.
a link 16.
A further embodiment is shown in FIG. 4 which has
Each of the correspondents 12, 14 includes a secure particular applicability to an elliptic curve cryptosystem. By
cryptographic function 20 including a secure memory 22, an way of example it will be assumed that a 163 bit string is
arithmetic processor 24 for performing finite field opera 35 required and that the output of the hash function 28 is 160
tions, a random number generator 26 and a cryptographic bits.
hash function 28 for performing a secure cryptographic hash
such as SHA-1. The output of the function 28 will be a bit SVThe random number generator 26 generates a seed value
which is processed by the hash function 28 to obtain a
string of predetermined length, typically 160 bits although
other lengths such as 256, 384 or 512 are being used more 40 first output H(seed).
frequently. It will be appreciated that each of these functions to The seed value SV is incremented by a selected function
provide a seed value SV+ which is further processed by
is controlled by a processor executing instructions to provide
functionality and inter-operability as is well known in the the hash function 28 to provide a second output H(seed--).
art. The two outputs are then combined, typically by cocat
The secure memory 22 includes a register 30 for storing 45 enation, to produce a 320 bit string H(seed)/H(seed--). The
a long-term private key, d, and a register 32 for storing an excess bits, in this case 157 are rejected and the resultant
ephemeral private key k. The contents of the registers 30, 32 value tested against the value of q. If the resultant value is
may be retrieved for use by the processor 24 for performing less than q, it is accepted as the key k, if not the value is
signatures, key exchange and key transport functions in rejected.
accordance with the particular protocols to be executed 50 Upon rejection, the random number generator may gen
under control of the processor. erate a new value as disclosed in FIG. 2 or may increment
The long term private key, d, is generated and embedded the seed value as disclosed in FIG. 3.
at the time of manufacture or initialization of the crypto A further embodiment is shown in FIG. 5 which is similar
graphic function and has a corresponding long-term public to that of FIG. 4. In the embodiment of FIG. 5, the selection
key C". The long-term public key C." is stored in the memory 55 of the required L. bit string is obtained by applying a L-bit
22 and is generally made available to other correspondents wide masking window to the combined bit string.
of the system 10. This is tested against the value of q and if acceptable is
The ephemeral key, k, is generated at each signature or used as the value of k. If it is not acceptable it is rejected and
other cryptographic exchange by one of the routines dis the L bit window incremented along the combined bit string
closed below with reference to FIGS. 2 to 9. Once the key, 60 to obtain a new value.
k, and corresponding public key C' is generated, it is stored The values are tested and the window incremented until a
satisfactory value is obtained.
in the register 32 for use in the cryptographic protocol. Such
as the DSA or ECDSA described above. A similar procedure may be used directly on an extended
Referring, therefore, to FIG. 2, a first method of gener output of the hash function 28 as shown in FIG. 6 by
ating a key, k, originates by obtaining a seed value (SV) 65 applying a window to obtain the required L. bit string. The
from the random number generator 26. For the purposes of bit string is tested against q and the window incremented
an example, it will be assumed that the cryptographic until a satisfactory value of k is obtained.
US 7,372,961 B2
5 6
As shown in FIG. 7, the value of k may be generated by mented output to produce a new output; a determination
utilizing a low Hamming weight integer obtained by com being made as to whether said new output is acceptable as
bining the output of the random number generator 26 to a key.
facilitate computation of an intermediate public key C.. The 8. The method of claim 7, wherein said step of incre
integer is masked by combination with predetermined pre menting includes a further step of adding a particular value
computed value k to obtain the requisite Hamming weight to said seed value.
for security. Such a procedure is disclosed in copending 9. A method of generating a key k for use in a crypto
Canadian application 2.217.925. This procedure is modified graphic function performed over a group of order q, said
to generate the low Hamming weight integerk as a bit string method including the steps of
greater than L, for example a 180 bit string. The masking 10 generating a seed value SV from a random number
value k is distributed throughout the 180 bit string and the generator,
resultant value reduced mod q to obtain a 163 bit value k". performing a hash function H() on said seed number SV
Note that the value C.'" can be efficiently computed by to provide a first output H(SV):
combining the precomputed value C. with the efficiently incrementing said seed value SV by a predetermined
computable value of 15
function f() and performing said hash function H() on
A similar technique may be used by relying on multipli said incremented seed value to provide a second output
cative masking. In this embodiment the value of k is H(f(SV));
combined with a value B where 3-O.". The value of u is a combining said first output H(SV) and second output
secret value that is used to mask the low Hamming weight H(f(SV)) to produce a new output;
of k. Again, the values of u and the low Hamming weight determining whether said new output has a value less than
number k can be chosen to have bit lengths greater than L, said order q prior to reducing mod q;
for example, bit lengths of 180. The resultant value is k"—u' accepting said new output for use as said key k if said new
mod q. It will be appreciated that O'" can be efficiently output has a value less than said order q;
computed since B-O." is precomputed, and since k has low rejecting said new output as said key k if said value is not
Hamming weight. 25
Although the invention has been described with reference less than said order q;
to certain specific embodiments, various modifications if said new output is rejected, repeating said method, and
thereof will be apparent to those skilled in the art without if said new output is accepted, providing said key k for use
departing from the spirit and scope of the invention as in performing said cryptographic function, wherein
outlined in the claims appended hereto. 30 said key k is equal to said new output.
The embodiment of the invention in which an exclusive
10. The method of claim 9 wherein upon rejection of said
new output a new seed value is generated by said random
property or privilege is claimed are defined as follows: number generator.
1. A method of generating a key k for use in a crypto
graphic function performed over a group of order q, said 35 new11.output The method of claim 9 wherein upon rejection of said
said seed value is incremented by a predeter
method including the steps of mined function and revised values for said first output and
generating a seed value SV from a random number said second output are obtained.
generator,
performing a hash function H() on said seed value SV to than a predeterminedoflength
12. The method claim 9 wherein a bit string greater
L is obtained and an L. bit string
provide an output H(SV): 40 selected therefrom for comparison with said order q.
determining whether said output H(SV) is less than said
order q prior to reducing mod q; 13. The method of claim 12 wherein upon rejection of said
accepting said output H(SV) for use as said key k if the bit string of predetermined length L., a further L. bit string is
selected.
value of said output H(SV) is less than said order q;
rejecting said output H(SV) as said key if said value is not 45 14. The method of claim 9 wherein said step of combining
less than said order q; said first and second outputs includes a further step of
if said output H(SV) is rejected, repeating said method; rejecting
of length
excess bits such that said new output is a bit string
L.
and
if said output H(SV) is accepted, providing said key k for 15. A computer readable medium comprising computer
use in performing said cryptographic function, wherein 50 executable
cryptographic
instructions for generating a key k for use in a
function performed over a group of order q,
said key k is equal to said output H(SV).
2. The method of claim 1 wherein another seed value is said instructions including instructions for:
generated by said random number generator if said output is generating a seed value SV from a random number
rejected. generator,
3. The method of claim 1 wherein the step of accepting 55 performing a hash function H() on said seed value SV to
said output as a key includes a further step of storing said provide an output H(SV):
key. determining whether said output H(SV) is less than said
4. The method of claim 1 wherein said key is used for order q prior to reducing mod q;
generation of a public key. accepting said output H(SV) for use as said key k if the
5. The method of claim 1 wherein said order q is a prime 60 value of said output H(SV) is less than said order q;
number represented by a bit string of predetermined length rejecting said output H(SV) as said key if said value is not
L. less than said order q;
6. The method of claim 5 wherein said output from said if said output H(SV) is rejected, repeating said method;
hash function is a bit string of predetermined length L. and
7. The method of claim 1 wherein if said output is 65 if said output H(SV) is accepted, providing said key k for
rejected, said output is incremented by a deterministic use in performing said cryptographic function, wherein
function and a hash function is performed on said incre said key k is equal to said output H(SV).
US 7,372,961 B2
7 8
16. The computer readable medium of claim 15 wherein accepting said output H(SV) for use as said key k if the
another seed value is generated by said random number value of said output H(SV) is less than said order q;
generator if said output is rejected. rejecting said output H(SV) as said key if said value is not
17. The computer readable medium of claim 15 wherein less than said order q;
the step of accepting said output as a key includes a further 5 if said output H(SV) is rejected, repeating said method;
step of storing said key. and
18. The computer readable medium of claim 15 wherein if said output H(SV) is accepted, providing said key k for
said key is used for generation of a public key. use in performing said cryptographic function, wherein
19. The computer readable medium of claim 15 wherein said key k is equal to said output H(SV).
said order q is a prime number represented by a bit string of 10 24. The cryptographic unit of claim 23 wherein another
predetermined length L. seed value is generated by said random number generator if
20. The computer readable medium of claim 19 wherein said output is rejected.
said output from said hash function is a bit string of 25. The cryptographic unit of claim 23 wherein the step of
predetermined length L. accepting said output as a key includes a further step of
21. The computer readable medium of claim 15 wherein 15 storing said key.
if said output is rejected, said output is incremented by a 26. The cryptographic unit of claim 23 wherein said key
deterministic function and a hash function is performed on is used for generation of a public key.
said incremented output to produce a new output; a deter 27. The cryptographic unit of claim 23 wherein said order
mination being made as to whether said new output is q is a prime number represented by a bit string of predeter
acceptable as a key. mined length L.
22. The computer readable medium of claim 21, wherein 28. The cryptographic unit of claim 27 wherein said
said step of incrementing includes a further step of adding a output from said hash function is a bit string of predeter
particular value to said seed value. mined length L.
23. A cryptographic unit configured for generating a key 29. The cryptographic unit of claim 23 wherein if said
k for use in a cryptographic function performed over a group 25 output is rejected, said output is incremented by a determin
of order q, said cryptographic unit having access to com istic function and a hash function is performed on said
puter readable instructions and comprises: incremented output to produce a new output; a determina
an arithmetic processor for: tion being made as to whether said new output is acceptable
generating a seed value SV from a random number as a key.
generator, 30 30. The cryptographic unit of claim 29, wherein said step
performing a hash function H() on said seed value SV to of incrementing includes a further step of adding a particular
provide an output H(SV): value to said seed value.
determining whether said output H(SV) is less than said
order q prior to reducing mod q;
UNITED STATES PATENT AND TRADEMARK OFFICE
CERTIFICATE OF CORRECTION
PATENT NO. : 7,372,961 B2 Page 1 of 1
APPLICATIONNO. : 10/025924
DATED : May 13, 2008
INVENTOR(S) : Scott A. Vanstone et al.
It is certified that error appears in the above-identified patent and that said Letters Patent is hereby corrected as shown below:
In the drawings, Sheet 7, Fig. 7, reverse the arrow between box “k” and box “Combine k + k", delete
the box identified as “Combine and replace with a box identified as “Comb'.
In column 1, line 35, delete “public key is known and replace with “public key are known.
In column 2, line 21, delete “rx and replace with “rxkp.
In column 2, line 50, delete “else.
In column 2, line 51, add “else' at the beginning of the line to read “else k (- SHA-1 (seed).
In column 3, line 61, delete “is generated and replace with “are generated.
In column 3, line 61, delete “it is stored and replace with “k is stored.
In column 4, line 44, delete “cocatenation and replace with “concatenation.
In column 4, line 44, delete “// and replace with “11”.
In column 4, line 45, delete “157 and replace with “157.
In column 5, line 2 and 3, delete “combining and replace with “combing.
In column 5, line 14, delete “o and replace with “ok.
Signed and Sealed this
Twelfth Day of July, 2011
David J. Kappos
Director of the United States Patent and Trademark Office