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)
Disclaimer: Justia Dockets & Filings provides public litigation records from the federal appellate and district courts. These filings and docket sheets should not be considered findings of fact or liability, nor do they necessarily reflect the view of Justia.
Why Is My Information Online?