BlackBerry Limited v. Facebook, Inc. et al

Filing 1

COMPLAINT Receipt No: 0973-21360760 - Fee: $400, filed by Plaintiff BlackBerry Limited. (Attachments: # 1 Exhibit A, # 2 Exhibit B, # 3 Exhibit C, # 4 Exhibit D, # 5 Exhibit E, # 6 Exhibit F, # 7 Exhibit G, # 8 Exhibit H, # 9 Exhibit I, # 10 Exhibit J) (Attorney James R Asperger added to party BlackBerry Limited(pty:pla))(Asperger, James)

EXHIBIT A

EXHIBIT A

US007372961B2

(12) United States Patent

(10) Patent N0.:
(45) Date of Patent:

Vanstone et a].
(54)

METHOD OF PUBLIC KEY GENERATION

(56)

References Cited

AShOk Vadekar, ROCkWOOd
Robert J. Lambert, Cambridge (CA);

*

Robert P. Gallant, Mississauga (CA);
Daniel R Brown Toronto (CA)_
’

_

’

_

_

4/2001 Backal ...................... .. 380/28

6,307,938 B1*

(*)

Not1ce:

_

2/2001

6,219,421 B1 *

_

_

380/44

713/193

A1 *

patent is extended or adjusted under 35
U.S.C. 154(b) by 563 days.

8/2002

2003/0084332 Al*

Matyas et al.

......... .. 380/285

.

2002/0116527

SubJectto any dlsclalmer, the term of thls

10/2001

Vanstone et al.

6,327,660 B1 * 12/2001 Patel ........... ..

Asslgneei Certlwm Corp” Mlsslssauga (CA)
_

/
380 30
713/176

6,195,433 Bl *

(73)

_

/

5’073’935 A * 12 1991
6,088,798 A
7/2000

Alfred Menezes, West Canada (CA)
_

May 13, 2008

See application ?le for complete search history.

(75) Inventors: Scott A. Vanstone, Campbellville (CA);

'

US 7,372,961 B2

Chen et al.

..... ..

709/245

5/2003 Krasinski et a1. ......... .. 713/200

OTHER PUBLICATIONS
_

_

_

Schneier, Bruce, “Applied Cryptography”, 1996, John W1ley &

_

Sons, Inc., 2nd editiion, pp. 483-490.*

(21)
(22)

Appl' No" 10/025924
Filed:
Dec_ 26, 2001

Nel et a1., “Generation of Keys for use With the Digital Signature
Standard (DSS) , 1993, IEEE, pp. 6 10.
* cited by examiner

(65)

Pnor Pubhcatlon Data
US 2002/0090085 A1
Jul. 11, 2002

Primary ExamineriEmmanuel L. Moise
Assistant ExamineriMichael PyZocha

(30)

(CA)

_

>1<

(74) Attorney, Agent, or FirmiBlake, Cassels & Graydon
LLP; John R. S. Orange; Brett J. Slaney

Foreign Application Priority Data

Dec. 27, 2000

(51)

5,

.................................. .. 2329590

Int. Cl.

(57)

ABSTRACT

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 Classi?cation Search ................ .. 380/44,

380/277; 708/250

30 Claims, 7 Drawing Sheets

26 \

Output RNG

v
28 “\

\

Perform Hash

Store as k

EXHIBIT A
Page 118

4

U.S. Patent

Fig. 1

May 13, 2008

Sheet 1 0f 7

/

EXHIBIT A
Page 119

US 7,372,961 B2

U.S. Patent

May 13, 2008

26

Sheet 2 0f 7

X

Output RNG

28 X
\

Perform Hash

Is H(seed) < q?

Store as k

EXHIBIT A
Page 120

US 7,372,961 B2

U.S. Patent

May 13, 2008

Sheet 3 0f 7

US 7,372,961 B2

Output RNG

/
Store Value

v

<

Increment

Perform Hash

Is H(seed) < q?

Store as k

Fig. 3

EXHIBIT A
Page 121

-—>

Re] ect

U.S. Patent

May 13, 2008

Sheet 4 0f 7

US 7,372,961 B2

Output RNG

l
Store Value

<

j

Increment
V

I

Perform Hash

L

V
Combine

H(seed) ll H(seed +1)
V

Reject Surplus Bits

Is H(seed) < q?

Store as k

Fig. 4

EXHIBIT A
Page 122

Reject

U.S. Patent

May 13, 2008

Sheet 5 0f 7

US 7,372,961 B2

Output RNG

Store Value

A

Increment

Perform Hash

/
Combine

H(seed) I H(seed +1)
V
Select 1 bits

Is H(seed) < q?

Store as k

Fig. 5

EXHIBIT A
Page 123

Increment 1 bit Window

U.S. Patent

May 13, 2008

US 7,372,961 B2

Sheet 6 0f 7

26

K1

Output RNG

_\

Apply Hash

{r
Select 1 bits

A

Increment 1 bit Window

Is H(seed) < q?

Store as k

Fig. 6

EXHIBIT A
Page 124

U.S. Patent

May 13, 2008

Sheet 7 0f 7

US 7,372,961 B2

26

Output RNG

1

Combine

Compute oak

Reduce mod q
V
Store as k"

)

Combine

V
Store as a

kn

Fig. 7

EXHIBIT A
Page 125

A

Compute 0ck‘

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 veri?ed by computing
FIELD OF THE INVENTION

The present invention relates to public key cryptosystems
and more particularly to key generation Within such systems.
BACKGROUND OF THE INVENTION

v:0t”l[3”2mod p, Where [3:061 mod p is the long term
public key of the signatory and ?nally verifying that r:v

The basic structure of a public key cryptosystem is Well
known and has become ubiquitous With security in data
communication systems. Such systems use a private key k
and a corresponding public key (Xk Where 0t is a generator of

mod q. The use of both the ephemeral and long-term keys in
the signature binds the identity of the signatory to the

ephemeral key but does not render the long-term key vul
nerable.
A similar signature protocol knoWn as ECDSA may be
used for elliptic curve cryptosystems. In this protocol k is
selected in the interval 1 to n-l Where n is an 1 bit prime. The

the group. Thus one party may encrypt a message m With the

intended recipients public key and the recipient may apply
his private key to decrypt it.
Similarly, the cryptosystems may be used for key agree
ment protocols Where each party exponentiates the other
party’s public key With their oWn private key. Thus party A
Will take B’s public key otb and exponentiate it With A’s

signature component r is generated by converting the x
coordinate of the public key kP, Where P is the seed point on
20

take A’s public key 0t“ and exponentiate it With B’s private
key b to obtain the same session key 06”’. Thereafter data

may be transferred using a symmetric key protocol utiliZing
25

the common session key.

Public key cryptosystems may also be used to sign
messages to authenticate the author and/or the contents. In

about the public key k. They both require the selection of k
to be performed by a random number generator and it Will
therefore have a uniform distribution throughout the de?ned
interval. HoWever the implementation of the DSA may be
done in such a Way as to inadvertently introduce a bias in to

the selection of k. This small bias may be exploited to extract
35

lates the manner in Which an integer is to be selected for use
40

public keys, referred to as long term and short term or

ephemeral key pairs respectively. The ephemeral private key
correspondents, usually by a random number generator. The

corresponding, ephemeral public key is generated and the

45

expressed as:
50

55

of the message. The DSA domain parameters are prese

lected. They consist of a prime number p of a predetermined

length, by Way of example 1024 bits; a prime number q of
a predetermined bit length, by Way of example 160 bits,
Where q divides p-l; a generator 0t lying betWeen 2 and p-l
and Which satis?es the condition (aqmodp):l, and; a cryp
tographic hash function H, such as SHA-l.
The DSA requires the signatory to select an ephemeral

than the prime q and so the DSS requires the reduction of the

integer mod q, i.e. k:SHA—l(seed) mod q.
Accordingly the algorithm for selecting k may be

a neW session.

Some of the more popular protocols for signature are the
ElGamal family of signature schemes such as the Digital
Signature Algorithm or DSA. The DSA algorithm utiliZes
both long term and ephemeral keys to generate a signature

as a private key. A seed value, SV, is generated from a
random number generator Which is then hashed by a SHA-l

hash function to yield a bit string of predetermined length,
typically 160 bits. The bit string represents an integer
betWeen 0 and 21 60—l. HoWever this integer could be greater

is generated at the start of each session betWeen a pair of

resultant key pair used in one of the possible operations
described above. The long-term public key is utiliZed to
authenticate the correspondent through an appropriate pro
tocol. Once the session is terminated, the ephemeral key is
securely discarded and a neW ephemeral key generated for

a value of the private key d and thereafter render the security
of the system vulnerable. One such implementation is the
DSS mandated by the National Institute of Standards and

Technology (NIST) FIPS 186-2 Standard. The DSS stipu

tunity of disclosing the private key, protocols have been
developed that use a pair of private keys and corresponding

the DSA and ECDSA, that if an ephemeral key k and the
associated message m and signature (r,s) is obtained it may
be used to yield the long term private key d and thereafter
each of the ephemeral keys k can be obtained. Neither the
DSA nor the ECDSA inherently disclose any information

this case the sender Will sign a message using his private key
and a recipient can verify the message by applying the public
key of the sender. If the received message and the recovered

message correspond then the authenticity is veri?ed.
The public key cryptosystems rely on the intractability of
the discrete log problem in ?nite ?eld arithmetic, that is even
When the generator 0t and public key is knoWn, it is
computationally infeasible to obtain the corresponding pri
vate key. The security of such systems does therefore depend
on the private key remaining secret. To mitigate the oppor

the curve, to an integer mod n, i.e. rqkp mod n. The

component s:k_l(H(m)+dr) mod n and the signature on the
message m is (r,s).
It Will be apparent in ElGamal signature schemes such as

private key a to obtain a session key 06”’. Similarly, B Will

if SHA- 1 (seed) Eq then k<—SHA— l (seed)—q else
k<—SHA— 1 (seed).

With this algorithm it is to be expected that more values Will
lie in the ?rst interval than the second and therefore there is
a potential bias in the selection of k.
Recent Work by Daniel Bleichenbacher suggests that the
modular reduction to obtain k introduces suf?cient bias in to
the selection of k that an examination of 222 signatures could

yield the private key d in 264 steps using 240 memory units.
60

This suggests that there is a need for the careful selection of

the ephemeral key k.
SUMMARY OF THE INVENTION

key k lying between 1 and q-l. A ?rst signature component
r is generated from the generator 0t such that I:((Xk mod p)
mod q, A second signature component s is generated such
that s:k_l(H(m)+dr) mod q, and d is the long term private

65

It is therefore an object of the present invention to obviate
or mitigate the above disadvantages in the generation of a

private key.
EXHIBIT A
Page 126

US 7,372,961 B2
3

4

In general terms the present invention provides a key
generation technique in Which any bias is eliminated during
the selection of the key.

function is performed over a group of order q, Where q is a

prime represented as a bit string of predetermined length L.
By Way of example only it Will be assumed that the length
L is 160 bits, although, of course, other orders of the ?eld

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, eg a 160 bit output. The bit

Way of example only With reference to the accompanying
draWings in Which:

string generated by the random number generator 26 is
greater than L bits and is therefore hashed by the function 28
to produce an output H(seed) of L bits.
The resultant output H(seed) is tested against the value of

FIG. 1 is a schematic representation of a data communi

cation system;
FIG. 2 is a How chart shoWing a ?rst embodiment of key

q and a decision made based on the relative values. If

generation;
FIG.
FIG.
FIG.
FIG.
FIG.

3
4
5
6
7

is
is
is
is
is

H(seed)<q then it is accepted for use as k. If not, the value
a
a
a
a
a

How
How
How
How
How

chart
chart
chart
chart
chart

shoWing
shoWing
shoWing
shoWing
shoWing

a
a
a
a
a

second embodiment;
third embodiment;
fourth embodiment;
?fth embodiment; and
sixth embodiment.

DESCRIPTION OF THE PREFERRED
EMBODIMENTS

is rejected and the random number generator is conditioned

20

Referring, therefore to FIG. 1, a data communication
system 10 includes a pair of correspondents 12, 14 con
nected by a communication link 16. The link 16 may be a
dedicated link, a multipurpose link such as a telephone
connection or a Wireless link depending on the particular

25

mented by applying a non-linear deterministic function to
the seed value. For example, the output may be incremented
30

pagers or any other device enabled For communication over
a link 16.

A further embodiment is shoWn in FIG. 4 Which has
35

40

frequently. It Will be appreciated that each of these functions
is controlled by a processor executing instructions to provide
functionality and inter-operability as is Well knoWn in the
art.

The secure memory 22 includes a register 30 for storing

45

a long-term private key, d, and a register 32 for storing an

?rst output H(seed).
The seed value SV is incremented by a selected function
to provide a seed value SV+ Which is further processed by
the hash function 28 to provide a second output H(seed+).
The tWo outputs are then combined, typically by cocat
enation, to produce a 320 bit string H(seed)//H(seed+). The
excess bits, in this case 157 are rejected and the resultant

value tested against the value of q. If the resultant value is
less than q, it is accepted as the key k, if not the value is

ephemeral private key k. The contents of the registers 30, 32
may be retrieved for use by the processor 24 for performing

rejected.

signatures, key exchange and key transport functions in
accordance With the particular protocols to be executed

particular applicability to an elliptic curve cryptosystem. By
Way of example it Will be assumed that a 163 bit string is
required and that the output of the hash function 28 is 160
bits.
The random number generator 26 generates a seed value
SV 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

by applying the function f(seed):a.seed2+b mod 2160, Where
a and b are integer constants.

Each of the correspondents 12, 14 includes a secure
cryptographic function 20 including a secure memory 22, an

arithmetic processor 24 for performing ?nite ?eld opera
tions, a random number generator 26 and a cryptographic
hash function 28 for performing a secure cryptographic hash
such as SHA-l. The output of the function 28 Will be a bit

value of q. If the H(seed) value is not accepted, the output
of the random number generator 26 is incremented by a
deterministic function and rehashed by function 28.
The resultant value H(seed) is again tested and the pro
cedure repeated until a satisfactory value of k is obtained.
The output may be incremented by adding a particular
value to the seed value at each iteration, or may be incre

applications. Similarly, the correspondents 12, 14 may be
computer terminals, point-of-sale devices, automated teller
machines, constrained devices such as PDA’s, cellphones,

to generate a neW value Which is again hashed by the
function 28 and tested. This loop continues until a satisfac
tory value is obtained.
A further embodiment is shoWn in FIG. 3. In this embodi
ment, the output of the random number generator 26 is
hashed by hash function 28 as before and tested against the

50

Upon rejection, the random number generator may gen
erate a neW value as disclosed in FIG. 2 or may increment

under control of the processor.

the seed value as disclosed in FIG. 3.
A further embodiment is shoWn in FIG. 5 Which is similar
to that of FIG. 4. In the embodiment of FIG. 5, the selection

The long term private key, d, is generated and embedded
at the time of manufacture or initialiZation of the crypto

graphic function and has a corresponding long-term public
key otd. The long-term public key otd is stored in the memory

55

22 and is generally made available to other correspondents
of the system 10.
The ephemeral key, k, is generated at each signature or
other cryptographic exchange by one of the routines dis
closed beloW With reference to FIGS. 2 to 9. Once the key,

of the required L bit string is obtained by applying a L-bit
Wide masking WindoW to the combined bit string.
This is tested against the value of q and if acceptable is
used as the value of k. If it is not acceptable it is rejected and
the L bit WindoW incremented along the combined bit string

60 to obtain a neW value.

k, and corresponding public key (Xk is generated, it is stored

The values are tested and the WindoW incremented until a

in the register 32 for use in the cryptographic protocol, such

satisfactory value is obtained.

as the DSA or ECDSA described above.

A similar procedure may be used directly on an extended
output of the hash function 28 as shoWn in FIG. 6 by
applying a WindoW to obtain the required L bit string. The

Referring, therefore, to FIG. 2, a ?rst method of gener

ating a key, k, originates by obtaining a seed value (SV)
from the random number generator 26. For the purposes of
an example, it Will be assumed that the cryptographic

65

bit string is tested against q and the WindoW incremented
until a satisfactory value of k is obtained.

EXHIBIT A
Page 127

US 7,372,961 B2
5

6

As shown in FIG. 7, the value of k may be generated by
utilizing a loW Hamming Weight integer obtained by com
bining the output of the random number generator 26 to

mented output to produce a neW output; a determination
being made as to Whether said neW output is acceptable as
a key.

facilitate computation of an intermediate public key 0t . The

8. The method of claim 7, Wherein said step of incre
menting includes a further step of adding a particular value

integer is masked by combination With predetermined pre
computed value k' to obtain the requisite Hamming Weight
for security. Such a procedure is disclosed in copending
Canadian application 2,217,925. This procedure is modi?ed

to said seed value.
9. A method of generating a key k for use in a crypto
graphic function performed over a group of order q, said

to generate the loW Hamming Weight integer k as a bit string
greater than L, for example a 180 bit string. The masking
value k' is distributed throughout the 180 bit string and the

method including the steps of:
generating a seed value SV from a random number

generator;

resultant value reduced mod q to obtain a 163 bit value k".

performing a hash function H( ) on said seed number SV
to provide a ?rst output H(SV);
incrementing said seed value SV by a predetermined

Note that the value otk" can be e?iciently computed by
combining the precomputed value 0t With the ef?ciently

computable value (Xk'

function f( ) and performing said hash function H( ) on

A similar technique may be used by relying on multipli
cative masking. In this embodiment the value of k is

said incremented seed value to provide a second output

H(f(SV));

combined With a value [3 Where [3:0t”. The value of u is a

secret value that is used to mask the loW Hamming Weight
of k. Again, the values of u and the loW Hamming Weight
number k can be chosen to have bit lengths greater than L,
for example, bit lengths of 180. The resultant value is k"q1k
mod q. It Will be appreciated that otk" can be ef?ciently

combining said ?rst output H(SV) and second output
20

said order q prior to reducing mod q;

computed since [3:0t” is precomputed, and since k has loW

Hamming Weight.

25

Although the invention has been described With reference
to certain speci?c embodiments, various modi?cations

in performing said cryptographic function, Wherein
said key k is equal to said neW output.
10. The method of claim 9 Wherein upon rejection of said
neW output a neW seed value is generated by said random

outlined in the claims appended hereto.
The embodiment of the invention in Which an exclusive
property or privilege is claimed are de?ned as folloWs:
1. A method of generating a key k for use in a crypto

method including the steps of:

number generator.
35

generating a seed value SV from a random number

generator;
performing a hash function H( ) on said seed value SV to

provide an output H(SV);
determining Whether said output H(SV) is less than said
order q prior to reducing mod q;
accepting said output H(SV) for use as said key k if the
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
less than said order q;

40

45

selected.
14. The method of claim 9 Wherein said step of combining
said ?rst and second outputs includes a further step of
rejecting excess bits such that said neW output is a bit string

of length L.
15. A computer readable medium comprising computer

and
50

executable instructions for generating a key k for use in a
cryptographic function performed over a group of order q,

said instructions including instructions for:

2. The method of claim 1 Wherein another seed value is

generating a seed value SV from a random number

generated by said random number generator if said output is

generator;

rejected.

performing a hash function H( ) on said seed value SV to

3. The method of claim 1 Wherein the step of accepting
said output as a key includes a further step of storing said

key.
4. The method of claim 1 Wherein said key is used for

generation of a public key.
5. The method of claim 1 Wherein said order q is a prime

11. The method of claim 9 Wherein upon rejection of said
neW output said seed value is incremented by a predeter
mined function and revised values for said ?rst output and
said second output are obtained.
12. The method of claim 9 Wherein a bit string greater
than a predetermined length L is obtained and an L bit string
selected therefrom for comparison With said order q.
13. The method of claim 12 Wherein upon rejection of said

bit string of predetermined length L, a further L bit string is

if said output H(SV) is rejected, repeating said method;
if said output H(SV) is accepted, providing said key k for
use in performing said cryptographic function, Wherein
said key k is equal to said output H(SV).

accepting said neW output for use as said key k if said neW
output has a value less than said order q;
rejecting said neW output as said key k if said value is not
less than said order q;

if said neW output is rejected, repeating said method, and
if said neW output is accepted, providing said key k for use

thereof Will be apparent to those skilled in the art Without
departing from the spirit and scope of the invention as

graphic function performed over a group of order q, said

H(f(SV)) to produce a neW output;
determining Whether said neW output has a value less than

60

number represented by a bit string of predetermined length

provide an output H(SV);
determining Whether said output H(SV) is less than said
order q prior to reducing mod q;
accepting said output H(SV) for use as said key k if the
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
less than said order q;

L.

6. The method of claim 5 Wherein said output from said
hash function is a bit string of predetermined length L.
7. The method of claim 1 Wherein if said output is
rejected, said output is incremented by a deterministic
function and a hash function is performed on said incre

if said output H(SV) is rejected, repeating said method;
and
65

if said output H(SV) is accepted, providing said key k for
use in performing said cryptographic function, Wherein
said key k is equal to said output H(SV).

EXHIBIT A
Page 128

US 7,372,961 B2
8

7
16. The computer readable medium of claim 15 Wherein

accepting said output H(SV) for use as said key k if the
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
less than said order q;

another seed value is generated by said random number
generator if said output is rejected.
17. The computer readable medium of claim 15 Wherein
the step of accepting said output as a key includes a further

if said output H(SV) is rejected, repeating said method;

step of storing said key.

and

if said output H(SV) is accepted, providing said key k for
use in performing said cryptographic function, Wherein
said key k is equal to said output H(SV).

18. The computer readable medium of claim 15 Wherein

said key is used for generation of a public key.
19. The computer readable medium of claim 15 Wherein
said order q is a prime number represented by a bit string of
20. The computer readable medium of claim 19 Wherein
said output from said hash function is a bit string of

24. The cryptographic unit of claim 23 Wherein another
seed value is generated by said random number generator if
said output is rejected.
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
if said output is rejected, said output is incremented by a

storing said key.

predetermined length L.

deterministic function and a hash function is performed on
said incremented output to produce a neW output; a deter
mination being made as to Whether said neW output is
acceptable as a key.

20

22. The computer readable medium of claim 21, Wherein
said step of incrementing includes a further step of adding a
particular value to said seed value.

23. A cryptographic unit con?gured for generating a key
k for use in a cryptographic function performed over a group

25

istic function and a hash function is performed on said
incremented output to produce a neW output; a determina
tion being made as to Whether said neW output is acceptable

of order q, said cryptographic unit having access to com

puter readable instructions and comprises:
an arithmetic processor for:

generating a seed value SV from a random number

generator;

as a key.
30

performing a hash function H( ) on said seed value SV to

provide an output H(SV);

26. The cryptographic unit of claim 23 Wherein said key
is used for generation of a public key.
27. The cryptographic unit of claim 23 Wherein said order
q is a prime number represented by a bit string of predeter
mined length L.
28. The cryptographic unit of claim 27 Wherein said
output from said hash function is a bit string of predeter
mined length L.
29. The cryptographic unit of claim 23 Wherein if said
output is rejected, said output is incremented by a determin

30. The cryptographic unit of claim 29, Wherein said step
of incrementing includes a further step of adding a particular
value to said seed value.

determining Whether said output H(SV) is less than said
order q prior to reducing mod q;

EXHIBIT A
Page 129

UNITED STATES PATENT AND TRADEMARK OFFICE

CERTIFICATE OF CORRECTION
PATENT NO.

2 7,372,961 B2

APPLICATION NO.

: 10/025924

DATED
INVENTOR(S)

Page 1 Ofl

: Scott A. Vanstone et a1.

: May 13, 2008

It is certified that error appears in the above-identi?ed 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 “rzxkp” and replace with “rzxkp”.
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 “1 1”.

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 “or” and replace with “ark”.

Signed and Sealed this
Twelfth Day of July, 2011

David J. Kappos
Director afthe United States Patent and Trademark O?ice

EXHIBIT A
Page 130