--1..L ... ...
`
`w
`
`!::"""
`
`PATENT APPLICATION TRANSMITTAL LETTER
`(Large Entity)
`
`~'II
`--1
`0
`
`TO THE ASSISTANT COMMISSIONER FOR PATENTS
`
`I
`
`_
`
`Docket No.
`00001-0417
`
`Transmitted herewith for filing under 35 U.S.C. 111 and 37 C.F.R. 1.53 is the patent application of:
`
`Scott A. Vanstone et al.
`
`For: METHOD OF PUBLIC KEY GENERATION
`
`Enclosed are:
`0
`Certificate of Mailing with Express Mail Mailing Label No.
`181
`sheets of drawings.
`seven
`A certified copy of a
`□
`181
`□ Signed.
`Declaration
`181
`Power of Attorney
`Information Disclosure Statement
`□
`D
`Preliminary Amendment
`~. 0 Other:
`
`181 Unsigned.
`
`application.
`
`::;:;:;
`
`CLAIMS AS FILED
`t;,*· ___ F_o_r _____ #_F-il_e_d ___ #_A_ll_ow-ed ___ #_E_x-tr_a ______ R_a-te------~-F_e_e-------1
`
`f! Total Claims
`$0.00
`-20 =
`14
`$18.00
`0
`,"t----------;---------1------,----+-------------------1
`$0.00
`lndep. Claims
`$84.00
`0
`2
`- 3 =
`
`X
`
`X
`
`$0.00
`
`f~ Multiple Dependent Claims (check if applicable)
`0
`~ + ~r _____________________________ B_A_S_I_C_F_E_E-++-___ $_74_0_.o_o_
`TOTAL FILING FEE
`$740.00
`i:::~•1-· - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ' - ' - - - - - - - - - I
`181 A check in the amount of
`to cover the filing fee is enclosed.
`$740.00
`181 The Commissioner is hereby authorized to charge and credit Deposit Account No.
`as described below. A duplicate copy of this sheet is enclosed.
`0 Charge the amount of
`as filing fee.
`0 Credit any overpayment.
`181 Charge any additional filing fees required under 37 C.F.R.
`.1 and 1.17.
`□ Charge the issue fee set in 37 C.F.R. 1.18 at the mailing of e otice of Allowance,
`pursuant to 37 C.F.R. 1.311(b).
`
`j
`
`Dated: December 21, 2001
`
`I'
`
`,
`
`cc:
`
`\ Signature
`
`P01 LARGE/REV06
`
`MOBILEIRON, INC. - EXHIBIT 1003
`Page 001
`
`

`

`PTO/SB/17 (XX-XX)
`Approved for use through 10/31/2002. 0MB 0651-0032
`Patent and Trademark Office: U s.
`DEPARTMENT OF COMMErCE
`Under the Papeiwork Reduction Act of 1995, no persons are required to respond to a collection of information unless it disp avs a valid 0MB control num er.
`1
`
`"
`
`,,J
`
`Fee Paid
`
`r FEE TRANSMITTAL
`for FY 2002
`
`Patent tees are subject to annual revision.
`
`"-- TOTAL AMOUNT OF PAYMENT I
`
`$740.00
`
`Complete if Known
`
`Application Number
`
`Not Yet Assigned
`
`Filing Date
`
`Not Yet Assigned
`
`First Named Inventor
`
`Scott A. Vanstone
`
`Examiner Name
`Group Art Unit
`
`Not Yet Assigned
`
`Not Yet Assigned
`
`Attorney Docket No.
`
`00001-0417
`
`METHOD OF PAYMENT
`1 l'v'I The Commissioner is hereby authorized to charge
`Deposit I
`• IQJ indicated fees and credit any overpayments to:
`Orange & Chari
`Account
`Deposit I
`Number ~:::::::::::::::::::::::::::::::::;
`150633
`Account
`Name ________________ _
`
`Payment Enclosed:
`
`FEE CALCULATION (continued)
`3. ADDITIONAL FEES
`Large Entity Small Entity
`Fee
`Fee Fee
`Fee
`Fee Description
`Code
`($) Code
`($)
`105
`130
`205
`65 Surcharge - late filing fee or oath
`
`127
`
`50
`
`139
`
`130
`
`147 2,520
`
`112 920·
`
`1131,840*
`
`115
`
`116
`
`110
`
`400
`
`117
`920
`118 1,440
`
`128 1,960
`
`119
`
`120
`
`320
`
`320
`
`280
`121
`138 1,510
`
`227
`
`25 Surcharge - late provisional filing fee or cover
`sheet
`130 Non - English specification
`139
`147 2,520 For filing a request for ex parte reexamination
`112 920* Requesting publication of SIR prior to Examiner
`action
`1131,840* Requesting publication of SIR after Examiner
`action
`55 Extension for reply within first month
`200 Extension for reply within second month
`
`215
`
`216
`
`217
`218
`
`228
`
`219
`
`220
`
`460 Extension for reply within third month
`720 Extension for reply within fourth month
`
`980 Extension for reply within fifth month
`
`160 Notice of Appeal
`160 Filing a brief in support of an appeal
`
`140 Request for oral hearing
`
`221
`138 1,510 Petition to institute a public use proceeding
`
`140
`
`110
`
`240
`
`55 Petition to revive - unavoidable
`
`Charge Any Add1t1onal Fee Required
`~
`Under 37 CFR §§ 1.16 and 1.17
`Applicant clauns small entity status
`□
`See 37 CFR § 1.27
`1:81 Check D Credit card D ~~J!Y D Other
`FEE CALCULATION
`1. BASIC FILING FEE
`Large Entity Small Entity
`Fee Fee Fee Fee Fee Description
`Code {$) Code ($)
`101 740 201 370 Utility filing fee
`106 330 206 165 Design filing fee
`107 510 207 255 Plant filing fee
`108 740 208 370 Reissue filing fee
`114 160 214 80 Provisional filing,.:;fe:::e:__-'=====.
`
`Fee from
`below
`
`Fee Paid
`
`SUBTOTAL (1) I
`2. EXTRA CLAIM FEES
`Extra Claims
`-20** ==
`_ 3** =
`
`Total Claims
`~,~f~:ndent
`Multiple Dependent
`
`Large Entity Small Entity
`Fee Fee Fee Fee
`Code ($) Code ($)
`9
`103 18 203
`102 84 202 42
`104 280 204 140
`
`109 84 209 42
`
`Fee Description
`
`Claims in excess of 20
`Independent claims in excess of 3
`Multiple dependent claim, if not paid
`•• Reissue independent claims
`over original patent
`
`110 18 210
`
`9
`
`•• Reissue claims in excess of 20
`and over original patent
`
`SUBTOTAL (2)
`
`$0.00
`
`141 1,280
`
`241
`
`640 Petition to revive - unintentional
`
`142 1,280
`143
`460
`144
`620
`
`122
`
`123
`
`126
`
`130
`
`50
`
`180
`
`242
`243
`244
`
`122
`
`123
`
`126
`
`581
`
`40
`
`581
`
`146
`
`740
`
`246
`
`149
`
`740
`
`249
`
`179
`169
`
`740
`900
`
`279
`169
`
`640 Utility issue fee (or reissue)
`
`230 Design issue fee
`
`31 O Plant issue fee
`
`130 Petitions to the Commissioner
`
`50 Processing fee under 37 CFR § 1.17(q)
`
`180 Submission of Information Disclosure
`Statement
`40 Recording each patent assi1;1nment per property
`(times number of properties)
`370 Filing a submission after final rejection
`(37 CFR § 1.129(a))
`370 For each additional invention to be examined
`(37CFR § 1.129(b))
`370 Request for Continued Examination (RCE)
`
`900 Request for expedited examination
`of a design application
`Other fee (specify) _______________ _
`
`*Reduced by Basic Filing Fee Paid
`
`SUBTOTAL (3)
`
`Registration No.
`(Attorney/Agent)
`
`29,725
`
`Telephone
`
`{416)601-8440
`
`Com lete ,r a
`
`//cable
`
`Date
`
`December 21, 2001
`
`· Information on this form may become public. Credit card information should
`d on this form. Provide credit card information and authorization on
`not be incl
`Burden Hour Statement: This form is estimated to take 0.2 hours to complete. Time will vary depending upon the needs of the individual case Any comments on
`the amount of time you are required to complete this form should be sent to the Chief Information Officer, Patent and Trademark Office, Washington, DC 20231.
`DO NOT SEND FEES OR COMPLETED FORMS TO THIS ADDRESS. SEND TO: Assistant Commissioner for Patents, Washington, DC 20231.
`
`MOBILEIRON, INC. - EXHIBIT 1003
`Page 002
`
`

`

`--1..L ... ...
`
`w
`
`!::"""
`
`PATENT APPLICATION TRANSMITTAL LETTER
`(Large Entity)
`
`~'II
`--1
`0
`
`TO THE ASSISTANT COMMISSIONER FOR PATENTS
`
`I
`
`_
`
`Docket No.
`00001-0417
`
`Transmitted herewith for filing under 35 U.S.C. 111 and 37 C.F.R. 1.53 is the patent application of:
`
`Scott A. Vanstone et al.
`
`For: METHOD OF PUBLIC KEY GENERATION
`
`Enclosed are:
`0
`Certificate of Mailing with Express Mail Mailing Label No.
`181
`sheets of drawings.
`seven
`A certified copy of a
`□
`181
`□ Signed.
`Declaration
`181
`Power of Attorney
`Information Disclosure Statement
`□
`D
`Preliminary Amendment
`~. 0 Other:
`
`181 Unsigned.
`
`application.
`
`::;:;:;
`
`CLAIMS AS FILED
`t;,*· ___ F_o_r _____ #_F-il_e_d ___ #_A_ll_ow-ed ___ #_E_x-tr_a ______ R_a-te------~-F_e_e-------1
`
`f! Total Claims
`$0.00
`-20 =
`14
`$18.00
`0
`,"t----------;---------1------,----+-------------------1
`$0.00
`lndep. Claims
`$84.00
`0
`2
`- 3 =
`
`X
`
`X
`
`$0.00
`
`f~ Multiple Dependent Claims (check if applicable)
`0
`~ + ~r _____________________________ B_A_S_I_C_F_E_E-++-___ $_74_0_.o_o_
`TOTAL FILING FEE
`$740.00
`i:::~•1-· - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ' - ' - - - - - - - - - I
`181 A check in the amount of
`to cover the filing fee is enclosed.
`$740.00
`181 The Commissioner is hereby authorized to charge and credit Deposit Account No.
`as described below. A duplicate copy of this sheet is enclosed.
`0 Charge the amount of
`as filing fee.
`0 Credit any overpayment.
`181 Charge any additional filing fees required under 37 C.F.R.
`.1 and 1.17.
`□ Charge the issue fee set in 37 C.F.R. 1.18 at the mailing of e otice of Allowance,
`pursuant to 37 C.F.R. 1.311(b).
`
`j
`
`Dated: December 21, 2001
`
`I'
`
`,
`
`cc:
`
`\ Signature
`
`P01 LARGE/REV06
`
`MOBILEIRON, INC. - EXHIBIT 1003
`Page 003
`
`

`

`PTO/SB/17 (XX-XX)
`Approved for use through 10/31/2002. 0MB 0651-0032
`Patent and Trademark Office: U s.
`DEPARTMENT OF COMMErCE
`Under the Papeiwork Reduction Act of 1995, no persons are required to respond to a collection of information unless it disp avs a valid 0MB control num er.
`1
`
`"
`
`,,J
`
`Fee Paid
`
`r FEE TRANSMITTAL
`for FY 2002
`
`Patent tees are subject to annual revision.
`
`"-- TOTAL AMOUNT OF PAYMENT I
`
`$740.00
`
`Complete if Known
`
`Application Number
`
`Not Yet Assigned
`
`Filing Date
`
`Not Yet Assigned
`
`First Named Inventor
`
`Scott A. Vanstone
`
`Examiner Name
`Group Art Unit
`
`Not Yet Assigned
`
`Not Yet Assigned
`
`Attorney Docket No.
`
`00001-0417
`
`METHOD OF PAYMENT
`1 l'v'I The Commissioner is hereby authorized to charge
`Deposit I
`• IQJ indicated fees and credit any overpayments to:
`Orange & Chari
`Account
`Deposit I
`Number ~:::::::::::::::::::::::::::::::::;
`150633
`Account
`Name ________________ _
`
`Payment Enclosed:
`
`FEE CALCULATION (continued)
`3. ADDITIONAL FEES
`Large Entity Small Entity
`Fee
`Fee Fee
`Fee
`Fee Description
`Code
`($) Code
`($)
`105
`130
`205
`65 Surcharge - late filing fee or oath
`
`127
`
`50
`
`139
`
`130
`
`147 2,520
`
`112 920·
`
`1131,840*
`
`115
`
`116
`
`110
`
`400
`
`117
`920
`118 1,440
`
`128 1,960
`
`119
`
`120
`
`320
`
`320
`
`280
`121
`138 1,510
`
`227
`
`25 Surcharge - late provisional filing fee or cover
`sheet
`130 Non - English specification
`139
`147 2,520 For filing a request for ex parte reexamination
`112 920* Requesting publication of SIR prior to Examiner
`action
`1131,840* Requesting publication of SIR after Examiner
`action
`55 Extension for reply within first month
`200 Extension for reply within second month
`
`215
`
`216
`
`217
`218
`
`228
`
`219
`
`220
`
`460 Extension for reply within third month
`720 Extension for reply within fourth month
`
`980 Extension for reply within fifth month
`
`160 Notice of Appeal
`160 Filing a brief in support of an appeal
`
`140 Request for oral hearing
`
`221
`138 1,510 Petition to institute a public use proceeding
`
`140
`
`110
`
`240
`
`55 Petition to revive - unavoidable
`
`Charge Any Add1t1onal Fee Required
`~
`Under 37 CFR §§ 1.16 and 1.17
`Applicant clauns small entity status
`□
`See 37 CFR § 1.27
`1:81 Check D Credit card D ~~J!Y D Other
`FEE CALCULATION
`1. BASIC FILING FEE
`Large Entity Small Entity
`Fee Fee Fee Fee Fee Description
`Code {$) Code ($)
`101 740 201 370 Utility filing fee
`106 330 206 165 Design filing fee
`107 510 207 255 Plant filing fee
`108 740 208 370 Reissue filing fee
`114 160 214 80 Provisional filing,.:;fe:::e:__-'=====.
`
`Fee from
`below
`
`Fee Paid
`
`SUBTOTAL (1) I
`2. EXTRA CLAIM FEES
`Extra Claims
`-20** ==
`_ 3** =
`
`Total Claims
`~,~f~:ndent
`Multiple Dependent
`
`Large Entity Small Entity
`Fee Fee Fee Fee
`Code ($) Code ($)
`9
`103 18 203
`102 84 202 42
`104 280 204 140
`
`109 84 209 42
`
`Fee Description
`
`Claims in excess of 20
`Independent claims in excess of 3
`Multiple dependent claim, if not paid
`•• Reissue independent claims
`over original patent
`
`110 18 210
`
`9
`
`•• Reissue claims in excess of 20
`and over original patent
`
`SUBTOTAL (2)
`
`$0.00
`
`141 1,280
`
`241
`
`640 Petition to revive - unintentional
`
`142 1,280
`143
`460
`144
`620
`
`122
`
`123
`
`126
`
`130
`
`50
`
`180
`
`242
`243
`244
`
`122
`
`123
`
`126
`
`581
`
`40
`
`581
`
`146
`
`740
`
`246
`
`149
`
`740
`
`249
`
`179
`169
`
`740
`900
`
`279
`169
`
`640 Utility issue fee (or reissue)
`
`230 Design issue fee
`
`31 O Plant issue fee
`
`130 Petitions to the Commissioner
`
`50 Processing fee under 37 CFR § 1.17(q)
`
`180 Submission of Information Disclosure
`Statement
`40 Recording each patent assi1;1nment per property
`(times number of properties)
`370 Filing a submission after final rejection
`(37 CFR § 1.129(a))
`370 For each additional invention to be examined
`(37CFR § 1.129(b))
`370 Request for Continued Examination (RCE)
`
`900 Request for expedited examination
`of a design application
`Other fee (specify) _______________ _
`
`*Reduced by Basic Filing Fee Paid
`
`SUBTOTAL (3)
`
`Registration No.
`(Attorney/Agent)
`
`29,725
`
`Telephone
`
`{416)601-8440
`
`Com lete ,r a
`
`//cable
`
`Date
`
`December 21, 2001
`
`· Information on this form may become public. Credit card information should
`d on this form. Provide credit card information and authorization on
`not be incl
`Burden Hour Statement: This form is estimated to take 0.2 hours to complete. Time will vary depending upon the needs of the individual case Any comments on
`the amount of time you are required to complete this form should be sent to the Chief Information Officer, Patent and Trademark Office, Washington, DC 20231.
`DO NOT SEND FEES OR COMPLETED FORMS TO THIS ADDRESS. SEND TO: Assistant Commissioner for Patents, Washington, DC 20231.
`
`MOBILEIRON, INC. - EXHIBIT 1003
`Page 004
`
`

`

`METHOD OF PUBLIC KEY GENERATION
`
`5
`
`The present invention relates lo public key cryptosystems and more particularly to key
`
`generation within such systems.
`
`BACKGROUND OF THE INVENTION
`
`10
`
`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 a k where a is a generator of 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 agreement 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 cl and exponentiate it with A's private key a to obtain a session key aab_ Similarly, B
`will take A's ·public key a.a and exponentiate it with B's private key b to obtain the same session
`
`key a.ab_ Thereafter data may be transferred using a symmetric key protocol utilizing the common
`
`20
`
`session key.
`
`Public key cryptosystems may also be used to sign messages to authenticate the author
`
`and/or the contents. In 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
`
`25 message and the recovered message correspond then the authenticity is verified.
`
`The public key cryptosystems rely on the intractability of the discrete log problem in
`
`finite field arithmetic, that is even when the generator a and public key is known, it is
`
`computationally infeasible to obtain the corresponding private key. The security of such systems
`
`30
`
`does therefore depend on the private key remaining secret. To mitigate the opportunity of
`
`disclosing the private key, protocols have been developed that use a pair of private keys and
`
`MOBILEIRON, INC. - EXHIBIT 1003
`Page 005
`
`

`

`..
`
`5
`
`correspo,nding public keys, referred to as long term and short term or ephemeral key pairs
`is generated at the start of each session between a pc,:r uf
`
`respectively. The '-I-'•'"'·•''~•,...
`correspondents, usually by a ranaom number generator. The correspondi:1g ephemeral public key
`is generated and the resuitant key pair used in one of the possible operations described above.
`The long-tenn public key is utilized to authenticate the correspondent through an appropriate
`
`,.,,,
`
`protocol. Once the session is terminated, the ephemeral key is securely discarded ar.d a new
`ephemeral key generated for a new session.
`
`Some of,he 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
`tenn and ephemeral keys to generate a signature of the message. The DSA domain parameters
`
`are preselected. 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! 60 bits, where q
`
`divides p-1; a generator a lying between 2 and p-1 and which satisfies the condition
`
`(a9modp)=l, and; a cryptographic hash function H, such as SHA-1.
`The DSA requires the signatory to select an ephemeral key k lying between 1 and q-1. A
`first signature component r is generated from the generator a such that r = ( cl mod p) mod q, A
`second signature components is generated such thats= k- 1(H(m)+dr) mod q, and dis the long
`term private key of the signatory. The signature on the message mis (r,s). The signature maybe
`verified by computing
`
`H(m),
`u1 = s"1H(m)mod q
`u2 = s·1r modq
`v == au 1Pu:mod p, where p == ad mod pis the long term public key of the signatory and
`finally verifying that r = v 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(cid:173)
`
`tem1 key vulnerable.
`
`A similar signature protocol known as ECDSA may be used for elliptic curve
`cryptosystems. In this protocol k is selected in the interval l to n-1 where n is an l bit prime. The
`signature component r is generated by converting the x coordinate of the public key kP, where P
`
`t!
`;:,'.120
`~~A
`
`25
`
`30
`
`- 2 -
`
`MOBILEIRON, INC. - EXHIBIT 1003
`Page 006
`
`

`

`..
`
`:.:: :>: seed point on the cui-:...:, ~o J.n integer mu<l n, i.e. r = XkP .noJ n. ihe components== k.
`1(H(m)+dr) mod n and tl1e signature on the message mis (r,s).
`
`5
`
`It will be apparent in ElGamal signature schemes such as the DSA and ECDSA, that if an
`ephemer;:;.i ;..;.-:1 :.<. an.l :::.:: 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 about the public key k.
`
`They both require the selection ofk to be performed by a random number generator and it will
`
`therefore have a uniform distribution throughout the defined interval. However the
`
`10
`
`implementation of the DSA may be done in such a way as to inadvertently introduce a bjas in to
`
`the selection of k. This small bias may be exploited to extract 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 stipulates the manner in which an integer is to be selected for use as a private key. A
`seed value, SV, is generated from a random number generator which is then hashed by a SHA-1
`
`hash function to yield a bit string of predetermined length, typically 160 bits. The bit string
`represents an integer between O and 2160-1. However this integer could be greater than the prime
`q and so the DSS requires the reduction of the integer mod q, i.e. k=SHA-l(seed) mod q.
`
`t~o
`
`Accordingly the algorithm for selecting k may be expressed as :-
`
`if SHA-l(seed) 2:: q then k+- SHA-l(seed)-q
`
`else k+-SHA-l(seed).
`
`With this algorithm it is to be expected that more values will lie in the first interval than the
`
`second and therefore there is a potential bias in the selection of k.
`
`25
`
`30
`
`Recent work by Daniel Bleichenbacher suggests that the modular reduction to obtain k
`introduces sufficient bias in to the selection ofk that an examination of 222 signatures could yield
`the private key din 264 steps using l4° memory units. This suggests that there is a need for the
`careful selection of the ephemeral key k.
`
`.., - .., -
`
`MOBILEIRON, INC. - EXHIBIT 1003
`Page 007
`
`

`

`....
`
`Su1.iIMARY OF THE INVE~TIC>f
`
`It is th;;:-:::fore J.11 object of the present invention to 0c•,
`
`or mitigate the above
`
`disadvantages in the generation of a private key.
`
`In general terms the present invention provides a key generation teclL.'1ique in which any
`bias is eliminated during the selection of the key.
`
`BRlEF DESCRIPTION OF THE DRAWINGS
`
`Embodiments of the invention will now be described by way of example only with reference to
`the accompanying drawings in which:-
`
`Figure 1 is a schematic representation of a data communication system;
`
`Figure 2 is a flow chart showing a first embodiment of key generation;
`
`Figure 3 is a flow chart showing a second embodiment;
`
`Figure 4 is a flow chart showing a third embodiment;
`
`Figure 5 is a flow chart showing a fourth embodiment;
`
`Figure 6 is a flow chart showing a fifth embodiment; and
`
`Figure 7 is a flow chart showing a sixth embodiment.
`
`DESCRIPTION OF THE PREFERRED EMBODIMENTS
`
`Referring, therefore to figure 1, a data communication system 10 includes a pair of
`correspondents 12, 14 connected by a communication link 16. The link 16may be a dedicated
`link, a multipurpose link such as a telephone connection or a wireless link depending on the
`particular applications. Similarly, the correspondents 12, 14 may be computer terminals, point-
`of-sale devices, automated teller machines, constrained devices such as PDA's, cellphones,
`pagers or any other device enabled for communication over a link 16.
`
`10
`
`~d~
`
`i"tfO
`nJ
`
`25
`
`30
`
`35
`
`MOBILEIRON, INC. - EXHIBIT 1003
`Page 008
`
`

`

`Each of the correspondents 12, 14 includes a secure cryptographic function:~ .1.1.,~ilding
`a secure memory 22, an arithmetic processor 24 for performing finite fieid operations, a random
`number generator :6 and a cryptographic hash function 28 for perfonning a secure cryptographic
`hash such as SHA-1. The outpl:t of the function 23 will be a bit string of predetermined length,
`typically 160 bits a1ti1ough other lengths such as 256, 384 or 5 i2 are being used more frequently.
`It will be appreci:ited that each of these functions is controlled by a processor executing
`instructions to provide functionality and ;nter-oper2.bility as is ·vell '.mown in the art.
`
`The secure memory 22 includes a register 30 for storing a long-term private key1 d, and a
`register 32 for storing an ephemeral private key k. The contents of the registers 30, 32 may be
`retrieved for use by the processor 24 for performing signatures, key exchange and key transport
`functions in accordance with the particular protocols to be executed under control of the
`
`processor.
`
`The long term private key, d, is generated and embedded at the time of manufacture or
`
`initialization of the cryptographic function and has a corresponding long-term public key a.ct.
`
`The long-term public key ad is stored in the memory 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 disclosed below with reference to figures 2 to 9. Once the key, k, and
`
`corresponding public key a.k is generated, it is stored in the register 32 for use in the
`
`cryptographic protocol, such as the DSA or ECDSA described above.
`
`Referring, therefore, to figure 2, a first method of generating 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 function is performed over a group of order q,
`where q is a prime represented as a bit string of predetennined length/. By way of example only
`it will be assumed that the length l is 160 bits, although, of course, other orders of the field may
`
`be used.
`
`5
`
`10
`
`25
`
`30
`
`MOBILEIRON, INC. - EXHIBIT 1003
`Page 009
`
`

`

`5
`
`10
`
`To provide a value of k of the appropriate order, the hash function 28 has an l bit output,
`e.2. a 1 l)n l:,it outout. The bit 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 q and a decision made based on
`
`the relative values. If H(seed) < q then it is accepted for use ask. If not. the value is rejected
`and the random number generator is conditioned to generate a new value which is again hashed
`by the function 28 and tested. This loop continues until a satisfactory value is obtained.
`
`A further embodiment is shown in figure 3. In this embodiment, the output of the
`random number generator 26 is 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 deterministic function and rehashed by function 28.
`
`The resultant value H(seed) is again tested and the procedure 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 incremented by applying a non-linear deterministic function to the seed
`value. For example, the output may be incremented by applying the function JC seed) a.seed2 +b
`mod i1 60
`, where a and bare integer constants.
`
`25
`
`A further embodiment is shown in figure 4 which has 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 first output H(seed).
`
`30
`
`MOBILEIRON, INC. - EXHIBIT 1003
`Page 010
`
`

`

`The seed value SV is incremented by a selected function to provide a seed value SV+
`:3 ::.::-:her precessed ½y t-he hash function 28 to provide a second output H(seed+).
`
`The two outputs are then combined, typically by cocatenation, to produce a 320 bit string
`5 H(seed)//H(seed..:...). The excess bits, in this case 157 are rejected :ind the resuitant value tested
`::ig2inst the value of q. If the resultant value is less than q, it is accepted as the key k, if not the
`
`value is rejected.
`
`Upon rejection, the random number generator may generate a new value as disclosed in
`figure 2 or may increment the seed value as disclosed in figure 3.
`
`A further embodiment is shown in figure 5 which is similar to that of figure 4. In the
`embodiment of figure 5, the selection of the required l bit string is obtained by applying a !-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 to obtain
`
`nJ
`
`a new value.
`
`The values are tested and the window incremented until a satisfactory value is obtained.
`
`A similar procedure may be used directly on an extended output of the hash function 28
`as shown in figure 6 by applying a window to obtain the required l bit string. The bit string is
`tested against q and the window incremented until a satisfactory value ofk is obtained.
`
`25
`
`30
`
`As shown in_ figure 7, the value ofk may be generated by utilizing a low Hamming
`weight integer obtained by combing the output of the random number generator 26 to facilitate
`
`computation of an intem1ediate public key rl. The integer is masked by combination with
`
`predetennined precomputed value k' to obtain the requisite Hamming weight for security. Such
`a procedure is disclosed in copending Cmadian application 2,217,925. This procedure is
`mo<lifoed to generate the low Hamming weight integer k as a bit string greater than l, for
`
`- 7 -
`
`MOBILEIRON, INC. - EXHIBIT 1003
`Page 011
`
`

`

`example, a l 30 !Jit string. The masking value k' ~s dist;ibuted throughout the 180 1:J,: .)~:-::;,g and
`
`the resultant vaiue reduced mod q to obtain a 163 bit value k". Note that the value a.'i<" can be
`
`efficiently computed by combining the precomputed valuecl' With the effic:cntly compmabie
`value cl.
`
`5
`
`10
`
`A similar technique may be used by relying on multiplicative masking. In this embodiment the
`
`. The value of u is a secret value that is used
`value cf:( is combined with a value~ where
`to mask the low Hamming weight ofk. Again, the values ofu and the low H~~i",,s .veigh.:
`number k can be chosen to have bit lengths greater than l, for example, bit lengths of 180. The
`resultant value is k" = uk mod q. It will be appreciated that cl" can be efficiently computed since
`~=c/1 is precomputed, and since k has low Hamming weight.
`
`Although the invention has been described with reference to certain specific
`embodiments, various modifications thereof will be apparent to those skilled in the art without
`departing from the spirit and scope of the invention as outlined in the claims appended hereto.
`
`- 8 -
`
`MOBILEIRON, INC. - EXHIBIT 1003
`Page 012
`
`

`

`THE EMBODIMENTS OF THE INVENTION IN WIDCH AN EXCLUSIVE
`PROPERTY OR PRIVILEGE IS CLAIMED ARE DEFINED AS FOLLOWS:
`
`I.
`
`A method of generating a key over a group of order q, said method including the
`
`steps of:
`generating a seed value from a random number generator;
`performing a hash function on said seed number to provide an output;
`
`determining whether said output is less than said prime number q;
`
`accepting said output for use as a key if the value thereof is less than said
`
`prime number q; and
`rejecting said output as a key if said value is not less than said order q.
`The method of claim I wherein another seed value is generated by said random
`number generator if said output is rejected.
`The method of claim I wherein the step of accepting said output as a key includes
`a further step of storing said key.
`The method of claim 1 wherein said key is used for generation of a public key.
`
`The method of claim 1 wherein said order q is prime number represented by a bit
`string of predetermined length I.
`The method of claim 5 wherein said output from said hash function is a bit string
`of predetermined length I.
`
`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
`incremented output to produce a new output; a determination being made as to
`whether said new output is acceptable as a key.
`
`The method of claim 7, wherein said step of incrementing includes a further step
`of adding a particular value to said seed value.
`A method of generating a key over a group of order q, said method including the
`steps of:
`
`generating a seed value from a random number generator;
`
`performing a hash function on said seed number to provide a first output;
`
`2.
`
`3.
`
`4.
`
`5.
`
`6.
`
`7.
`
`8.
`
`9.
`
`9
`
`MOBILEIRON, INC. - EXHIBIT 1003
`Page 013
`
`

`

`incrementing said seed value by a predetermined function and performing
`said hash function on said incremented seed value to provide a second
`output;
`
`combining said first output and second output to produce a new output;
`determining whether said new output has a value less than said order q;
`accepting said new output as a key k if said new output has a value less
`than order q; and rejecting said new output as a key if said new output has
`a value less than order q
`The method of claim 9 wherein upon rejection of said new output a new seed
`
`value is generated by said random number generator.
`
`The method of claim 9 wherein upon rejection of said new output said seed value
`is incremented by a predetermined function and revised values for said first output
`and said second output are obtained.
`The method of claim 9 wherein a bit string greater than a predetermined length I
`is obtained and an I bit string selected therefrom for comparison with said order q.
`The method of claim 12 wherein upon rejection of said bit string of predetermined
`length I, a further I bit string is selected.
`The method of claim 9 wherein said step of combining said first and second
`outputs includes a further step ofrejecting excess bits such that said new output is
`a bit string of length I.
`
`10.
`
`11.
`
`12.
`
`13.
`
`14.
`
`MOBILEIRON, INC. - EXHIBIT 1003
`Page 014
`
`

`

`ABSTRACT
`
`A potential bias in the generation or a private key is avoided by selecthl5 c1lc iey and comparing
`ic against the system parameters. If a predetermined condition is attained it is accepted. If not it is
`
`rejected and a new key is generated.
`
`MOBILEIRON, INC. - EXHIBIT 1003
`Page 015
`
`

`

`
`
`
`
`12
`
`20
`
`14
`
`20
`
`
`
`22
`
`30
`
`32
`
`24
`
`26
`
`28
`
`Fig. 1
`Fig. 1
`
`MOBILEIRON, INC. - EXHIBIT 1003
`
`Page 016
`
`MOBILEIRON, INC. - EXHIBIT 1003
`Page 016
`
`

`

`26
`
`28
`
`OutputRNG
`
`Perform Hash
`
`H(seed)
`
`y
`
`Store ask
`
`Fig. 2
`
`MOBILEIRON, INC. - EXHIBIT 1003
`Page 017
`
`

`

`OutputRNG
`
`Store Value
`
`Perform Hash
`
`Increment
`
`N
`
`Reject
`
`y
`
`St