NIST
`;' · PUBLJCATIONS
`a,_ ·:. 1,.' 11, '
`;iii •, . . , -►----
`U.S. DEPARTMENT OF COMMERCE
`Technology Administration
`National Institute of Standards and Technology
`
`•
`
`FIPS PUB 186
`
`FEDERAL INFORMATION PROCESSING STANDARDS PUBLICATION
`
`DIGITAL SIGNATURE STANDARD (DSS)
`
`•
`
`CATEGORY: COMPUTER SECURITY
`
`SUBCATEGORY: CRYPTOGRAPHY
`
`1994 May 19
`
`CD co ,-
`m
`::,
`0..
`u,
`0.. u:
`
`(
`• ~
`
`·lf-1( -
`468
`.A8A3
`N0.186
`-1994
`
`MOBILEIRON, INC. - EXHIBIT 1004
`Page 001
`
`

`

`•
`
`FIPS PUB 186
`
`FEDERAL INFORMATION PROCESSING STANDARDS PUBLICATION
`
`DIGITAL SIGNATURE STANDARD (DSS)
`
`•
`
`CATEGORY: COMPUTER SECURITY
`
`SUBCATEGORY: CRYPTOGRAPHY
`
`Computer Systems Laboratory
`National Institute of Standards and Technology
`Gaithersburg, MD 20899
`
`Issued May 19, 1994
`
`U.S. Department of Commerce
`Ronald H. Brown, Secretary
`
`Technology Administration
`Mary L. Good, Under Secretary for Technology
`
`•
`
`National Institute of Standards
`and Technology
`Arati Prabhakar, Director
`
`MOBILEIRON, INC. - EXHIBIT 1004
`Page 002
`
`

`

`Foreword
`
`The Federal Information Processing Standards Publication Series of the National
`Institute of Standards and Technology (NIST) is the official publication relating to
`standards and guidelines adopted and promulgated under the provisions of Section
`111 (d) of the Federal Property and Administrative Services Act of 1949 as amended by
`the Computer Security Act of 1987, Public Law 100-235. These mandates have given
`the Secretary of Commerce and NIST important responsibilities for improving the
`utilization and management of computer and related telecommunications systems in
`the Federal Government. The NIST, through its Computer Systems Laboratory,
`provides leadership, technical guidance, and coordination of Government efforts in the
`development of standards and guidelines in these areas.
`Comments concerning Federal Information Processing Standards Publications are
`welcomed and should be addressed to the Director, Computer Systems Laboratory,
`National Institute of Standards and Technology, Gaithersburg, MD 20899.
`
`James H. Burrows, Director
`Computer Systems Laboratory
`
`Abstract
`
`This standard specifies a Digital Signature Algorithm (DSA) which can be used to
`generate a digital signature. Digital signatures are used to detect unauthorized modifi(cid:173)
`cations to data and to authenticate the identity of the signatory. In addition, the recipi(cid:173)
`ent of signed data can use a digital signature in proving to a third party that the
`signature was in fact generated by the signatory. This is known as nonrepudiation
`since the signatory cannot, at a later time, repudiate the signature.
`
`Key words: ADP security; computer security; digital signatures; Federal Information
`Processing Standard; public-key cryptography.
`
`National Institute of Standards
`and Technology
`FIPS PUB 186
`23 pages (May 19, 1994)
`CODEN: FIPPAT
`
`U.S. Government Printing Office
`Washington: 1994
`
`For sale by the National
`Technical Information
`Service
`U.S. Department of Commerce
`Springfield, VA 22161
`
`MOBILEIRON, INC. - EXHIBIT 1004
`Page 003
`
`

`

`•
`
`FIPS PUB 186
`
`Federal Information
`Processing Standards Publication 186
`
`1994 May 19
`
`Announcing the
`
`DIGITAL SIGNATURE STANDARD (DSS)
`
`Federal Information Processing Standards Publications (FIPS PUBS) are issued by the National
`Institute of Standards and Technology (NIST) after approval by the Secretary of Commerce
`pursuant to Section 11 l(d) of the Federal Property and Administrative Services Act of 1949 as
`amended by the Computer Security Act of 1987, Public Law 100-235.
`
`Name of Standard: Digital Signature Standard (DSS).
`
`•
`
`Category of Standard: Computer Security, Cryptography.
`
`Explanation: This Standard specifies a Digital Signature Algorithm (DSA) appropriate for
`applications requiring a digital, rather than written, signature. The DSA digital signature is a pair
`of large numbers represented in a computer as strings of binary digits. The digital signature is
`computed using a set of rules (i.e., the DSA) and a set of parameters such that the identity of the
`signatory and integrity of the data can be verified. The DSA provides the capability to generate
`and verify signatures. Signature generation makes use of a private key to generate a digital
`signature. Signature verification makes use of a public key which corresponds to, but is not the
`same as, the private key. Each user possesses a private and public key pair. Public keys are
`assumed to be known to the public in general. Private keys are never shared. Anyone can verify
`the signature of a user by employing that user's public key. Signature generation can be
`performed only by the possessor of the user's private key.
`
`A hash function is used in the signature generation process to obtain a condensed version of data,
`called a message digest (see Figure 1 ). The message digest is then input to the DSA to generate
`the digital signature. The digital signature is sent to the intended verifier along with the signed
`data (often called the message). The verifier of the message and signature verifies the signature
`by using the sender's public key. The same hash function must also be used in the verification
`process. The hash function is specified in a separate standard, the Secure Hash Standard (SHS),
`FIPS 180. Similar procedures may be used to generate and verify signatures for stored as well
`as transmitted data .
`
`1
`
`•
`
`MOBILEIRON, INC. - EXHIBIT 1004
`Page 004
`
`

`

`Signature Generation
`
`Signature Verification
`
`Message
`
`Secure Hash Algorithm
`
`~
`~ Message Digest
`Private ~ Digital
`
`......
`...... .--D_S._'.A_S_i_· gn--..
`- , Operation - ,
`Signature
`Key
`
`Received Message
`
`Secure Hash Algorithm
`
`Message Digest
`
`~
`~
`Digital ___ l-"-__ Public
`
`...... DSA Verify ~
`- , Operation ~
`Signature
`Key
`
`Yes - Signature Verified
`or
`No - Signature Veri:t1.cation Fail
`
`Figure 1: Using the SHA with the DSA
`
`Approving Authority: Secretary of Commerce.
`
`Maintenance Agency: U.S. Department of Commerce, National Institute of Standards and
`Technology (NIST), Computer Systems Laboratory (CSL).
`
`Applicability: This standard is applicable to all Federal departments and agencies for the
`protection of unclassified information that is not subject to section 2315 of Title 10, United States
`Code, or section 3502(2) of Title 44, United States Code. This standard shall be used in
`designing and implementing public-key based signature systems which Federal departments and
`agencies operate or which are operated for them under contract. Adoption and use of this
`standard is available to private and commercial organizations.
`
`Applications: The DSA authenticates the integrity of the signed data and the identity of the
`signatory. The DSA may also be used in proving to a third party that data was actually signed
`
`2
`
`MOBILEIRON, INC. - EXHIBIT 1004
`Page 005
`
`

`

`•
`
`•
`
`•
`
`by the generator of the signature. The DSA is intended for use in electronic mail, electronic
`funds transfer, electronic data interchange, software distribution, data storage, and other
`applications which require data integrity assurance and data origin authentication.
`
`Implementations: The DSA may be implemented in software, firmware, hardware, or any
`combination thereof. NIST is developing a validation program to test implementations for
`conformance to this standard. Information about the planned validation program can be obtained
`from the National Institute of Standards and Technology, Computer Systems Laboratory, Attn:
`DSS Validation, Gaithersburg, MD 20899.
`
`Export Control: Implementations of this standard are subject to Federal Government export
`controls as specified in Title 15, Code of Federal Regulations, Parts 768 through 799. Exporters
`are advised to contact the Department of Commerce, Bureau of Export Administration for more
`information.
`
`Patents: The Department of Commerce is not aware of any patents that would be infringed by
`this standard.
`
`Implementation Schedule: This standard becomes effective December 1, 1994.
`
`Specifications: Federal Information Processing Standard (FIPS 186) Digital Signature Standard
`(affixed) .
`
`Cross Index:
`
`a. Federal Information Resources Management Regulations (FIRMR) subpart 201.20.303,
`Standards, and subpart 201.39.1002, Federal Standards.
`
`b. FIPS PUB 46-2, Data Encryption Standard.
`
`c. FIPS PUB 73, Guidelines for Security of Computer Applications.
`
`d. FIPS PUB 140-1, Security Requirements for Cryptographic Modules.
`
`e. FIPS PUB 171, Key Management Using ANSI X9.17.
`
`f. FIPS PUB 180, Secure Hash Standard.
`
`Qualifications: The security of a digital signature system is dependent on maintaining the secrecy
`of users' private keys. Users must therefore guard against the unauthorized acquisition of their
`private keys. While it is the intent of this standard to specify general security requirements for
`generating digital signatures, conformance to this standard does not assure that a particular
`implementation is secure. The responsible authority in each agency or department shall assure
`that an overall implementation provides an acceptable level of security. This standard will be
`
`3
`
`MOBILEIRON, INC. - EXHIBIT 1004
`Page 006
`
`

`

`reviewed every five years in order to assess its adequacy.
`
`Waiver Procedure: Under certain exceptional circumstances, the heads of Federal departments
`and agencies may approve waivers to Federal Information Processing Standards (FIPS). The
`head of such agency may redelegate such authority only to a senior official designated pursuant
`to section 3506(b) of Title 44, United States Code. Waiver shall be granted only when:
`
`a. Compliance with a standard would adversely affect the accomplishment of the mission of
`an operator of a Federal computer system; or
`
`b. Cause a major adverse financial impact on the operator which is not offset by
`Government wide savings.
`
`Agency heads may act upon a written waiver request containing the information detailed above.
`Agency heads may also act without a written waiver request when they determine that conditions
`for meeting the standard cannot be met. Agency heads may approve waivers only by a written
`decision which explains the basis on which the agency head made with required finding(s). A
`copy of each such decision, with procurement sensitive or classified portions clearly identified,
`shall be sent to: National Institute of Standards and Technology; ATTN: FIPS Waiver Decisions,
`Technology Building, Room B-154, Gaithersburg, MD 20899.
`
`In addition, notice of each waiver granted and each delegation of authority to approve waivers
`shall be sent promptly to the Committee on Government Operations of the House of
`Representatives and the Committee on Governmental Affairs of the Senate and shall be published
`promptly in the Federal Register.
`
`When the determination on a waiver applies to the procurement of equipment and/or services,
`a notice of the waiver determination must be published in the Commerce Business Daily as a part
`of the notice of solicitation for offers of an acquisition or, if the waiver determination is made
`after that notice is published, by amendment to such notice.
`
`A copy of the waiver, any supporting documents, the document approving the waiver and any
`supporting and accompanying documents, with such deletions as the agency is authorized and
`decides to make under 5 U.S.C. Sec. 552(b), shall be part of the procurement documentation and
`retained by the agency.
`
`Where to Obtain Copies of the Standard: Copies of this publication are for sale by the
`National Technical Information Service, U.S. Department of Commerce, Springfield, VA 22161.
`When ordering, refer to Federal Information Processing Standards Publication 186 (FIPS PUB
`186), and identify the title. When microfiche is desired, this should be specified. Prices are
`published by NTIS in current catalogs and other issuances. Payment may be made by check,
`money order, deposit account or charged to a credit card accepted by NTIS.
`
`4
`
`MOBILEIRON, INC. - EXHIBIT 1004
`Page 007
`
`

`

`•
`
`•
`
`•
`
`Federal Information
`Processing Standards Publication 186
`
`1994 May 19
`
`Specifications for the
`
`DIGITAL SIGNATURE STANDARD (DSS)
`
`1. INTRODUCTION
`
`This publication prescribes the Digital Signature Algorithm (DSA) for digital signature generation
`and verification. Additional information is provided in Appendices 1 through 5.
`
`2. GENERAL
`
`When a message is received, the recipient may desire to verify that the message has not been
`altered in transit. Furthermore, the recipient may wish to be certain of the originator's identity.
`Both of these services can be provided by the DSA. A digital signature is an electronic analogue
`of a written signature in that the digital signature can be used in proving to the recipient or a
`third party that the message was, in fact, signed by the originator. Digital signatures may also
`be generated for stored data and programs so that the integrity of the data and programs may be
`verified at any later time.
`
`This publication prescribes the DSA for digital signature generation and verification. In addition,
`the criteria for the public and private keys required by the algorithm are provided.
`
`3. USE OF THE DSA ALGORITHM
`
`The DSA is used by a signatory to generate a digital signature on data and by a verifier to verify
`the authenticity of the signature. Each signatory has a public and private key. The private key
`is used in the signature generation process and the public key is used in the signature verification
`process. For both signature generation and verification, the data which is referred to as a
`message, M, is reduced by means of the Secure Hash Algorithm (SHA) specified in FIPS 180.
`An adversary, who does not know the private key of the signatory, cannot generate the correct
`signature of the signatory. In other words, signatures cannot be forged. However, by using the
`signatory's public key, anyone can verify a correctly signed message .
`
`5
`
`MOBILEIRON, INC. - EXHIBIT 1004
`Page 008
`
`

`

`A means of associating public and private key pairs to the corresponding users is required. That
`is, there must be a binding of a user's identity and the user's public key. This binding may be
`certified by a mutually trusted party. For example, a certifying authority could sign credentials
`containing a user's public key and identity to form a certificate. Systems for certifying
`credentials and distributing certificates are beyond the scope of this standard. NIST intends to
`publish separate document(s) on certifying credentials and distributing certificates.
`
`The DSA makes use of the following parameters:
`
`4. DSA PARAMETERS
`
`1. p = a prime modulus, where 2L·1 < p < 2L for 512 ~ L ~ 1024 and L a multiple of 64
`
`2. q = a prime divisor of p - 1, where 2 159 < q < 2160
`
`3. g = h(p-l)tq mod p, where h is any integer with 1 < h < p - 1 such that h(p-l)tq mod p > 1
`(g has order q mod p)
`
`4. x = a randomly or pseudorandomly generated integer with O < x < q
`5. y = t mod p
`
`6. k = a randomly or pseudorandomly generated integer with O < k < q
`
`The integers p, q, and g can be public and can be common to a group of users. A user's private
`and public keys are x and y, respectively. They are normally fixed for a period of time.
`Parameters x and k are used for signature generation only, and must be kept secret. Parameter
`k must be regenerated for each signature.
`
`Parameters p and q shall be generated as specified in Appendix 2, or using other FIPS approved
`security methods. Parameters x and k shall be generated as specified in Appendix 3, or using
`other FIPS approved security methods.
`
`5. SIGNATURE GENERATION
`
`The signature of a message M is the pair of numbers r and s computed according to the equations
`below:
`
`r = (gk mod p) mod q
`
`and
`
`s = (k"1(SHA(M) + xr)) mod q.
`
`6
`
`MOBILEIRON, INC. - EXHIBIT 1004
`Page 009
`
`

`

`• In the above, k 1 is the multiplicative inverse of k, mod q; i.e., (k· 1 k) mod q = 1 and 0 < k 1 <
`
`q. The value of SHA(M) is a 160-bit string output by the Secure Hash Algorithm specified in
`FIPS 180. For use in computing s, this string must be converted to an integer. The conversion
`rule is given in Appendix 2.2.
`
`As an option, one may wish to check if r = 0 ors = 0. If either r = 0 ors = 0, a new value of
`k should be generated and the signature should be recalculated (it is extremely unlikely that r =
`0 or s = 0 if signatures are generated properly).
`
`The signature is transmitted along with the message to the verifier.
`
`6. SIGNATURE VERIFICATION
`
`Prior to verifying the signature in a signed message, p, q and g plus the sender's public key and
`identity are made available to the verifier in an authenticated manner.
`
`Let M', r', ands' be the received versions of M, r, ands, respectively, and let y be the public key
`of the signatory. To verify the signature, the verifier first checks to see that 0 < r' < q and 0 <
`s' < q; if either condition is violated the signature shall be rejected. If these two conditions are
`satisfied, the verifier computes
`
`•
`
`w = (s')" 1 mod q
`
`ul = ((SHA(M'))w) mod q
`
`u2 = ((r')w) mod q
`
`v = (((gt1 (yt2
`
`) mod p) mod q.
`
`If v = r', then the signature is verified and the verifier can have high confidence that the received
`message was sent by the pa11y holding the secret key x corresponding to y. For a proof that v
`= r' when M' = M, r' = r, ands'= s, see Appendix 1.
`
`If v does not equal r', then the message may have been modified, the message may have been
`incorrectly signed by the signatory, or the message may have been signed by an impostor. The
`message should be considered invalid .
`
`•
`
`7
`
`MOBILEIRON, INC. - EXHIBIT 1004
`Page 010
`
`

`

`APPENDIX 1. A PROOF THAT v = r'
`
`This appendix is for informational purposes only and is not required to meet the standard.
`
`The purpose of this appendix is to show that if M' = M, r' = r and s' = s in the signature
`verification then v = r'. We need the following easy result.
`
`LEMMA. Let p and q be primes so that q divides p - 1, h a positive integer less than p, and g
`= h(p-l)tq mod p. Then gq mod p = 1, and if m mod q = n mod q, then gm mod p = gn mod p.
`
`Proof: We have
`t mod p = (h<P· 1>'q mod p)q mod p
`
`= h<P· 1> mod p
`
`= 1
`by Fermat's Little Theorem. Now let m mod q = n mod q, i.e., m = n + kq for some integer k.
`Then
`
`gm mod p = gn+kq mod p
`
`= ((( mod p) (gq mod ph mod p
`= t mod p
`
`since gq mod p = 1. ■
`
`We are now ready to prove the main result.
`
`THEOREM. If M' = M, r' = r, and s' = s in the signature verification, then v = r'.
`
`Proof: We have
`
`w = (s')" 1 mod q = s· 1 mod q
`
`ul = ((SHA(M'))w) mod q = ((SHA(M))w) mod q
`
`u2 = ((r')w) mod q = (rw) mod q.
`
`8
`
`MOBILEIRON, INC. - EXHIBIT 1004
`Page 011
`
`

`

`• Now y = g< mod p, so that by the lemma,
`
`v = ((gu1 y112
`
`) mod p) mod q
`
`= ( (gSHA(M)w yrw) mod p) mod q
`
`= ( (gSHA(M)w gxrw) mod p) mod q
`
`= ((g(SHA(M}+xr)w) mod p) mod q.
`
`Also
`
`s = (k" 1(SHA(M) + xr)) mod q.
`
`Hence
`
`w = (k(SHA(M) + xr)" 1
`) mod q
`
`(SHA(M) + xr)w mod q = k mod q.
`
`Thus by the lemma,
`
`•
`
`v = (t mod p) mod q
`
`=r
`
`= r'. ■
`
`•
`
`9
`
`MOBILEIRON, INC. - EXHIBIT 1004
`Page 012
`
`

`

`APPENDIX 2. GENERATION OF PRIMES FOR THE DSA
`
`This appendix includes algorithms for generating the primes p and q used in the DSA. These
`algorithms require a random number generator (see Appendix 3), and an efficient modular
`exponentiation algorithm. Generation of p and q shall be performed as specified in this appendix,
`or using other FIPS approved security methods.
`
`2.1. A PROBABILISTIC PRIMALITY TEST
`
`In order to generate the primes p and q, a primality test is required.
`
`There are several fast probabilistic algorithms available. The following algorithm is a simplified
`version of a procedure due to M.O. Rabin, based in part on ideas of Gary L. Miller. [See Knuth,
`The Art of Computer Programming, Vol. 2, Addison-Wesley, 1981, Algorithm P, page 379.] If
`this algorithm is iterated n times, it will produce a false prime with probability no greater than
`1/4°. Therefore, n ~ 50 will give an acceptable probability of error. To test whether an integer
`is prim~
`
`Step 1. Set i = 1 and n ~ 50.
`
`Step 2. Set w = the integer to be tested, w = 1 + 23m, where m is odd and 2a is the largest
`power of 2 dividing w - 1.
`
`Step 3. Generate a random integer b in the range 1 < b < w.
`
`Step 4. Set j = 0 and z = bm mod w.
`
`Step 5. If j = 0 and z = 1, or if z = w - 1, go to step 9.
`
`Step 6. If j > 0 and z = 1, go to step 8.
`
`Step 7. j = j + 1. If j < a, set z = z2 mod w and go to step 5.
`
`Step 8. w is not prime. Stop.
`
`Step 9. If i < n, set i = i + 1 and go to step 3. Otherwise, w is probably prime.
`
`2.2. GENERATION OF PRIMES
`
`The DSS requires two primes, p and q, satisfying the following three conditions:
`
`a. 21s9 < q < 2 160
`
`b. 2L- 1 < p < 2L for a specified L, where L = 512 + 64j for some 0 ~ j ~ 8
`
`MOBILEIRON, INC. - EXHIBIT 1004
`Page 013
`
`

`

`•
`
`•
`
`•
`
`c. q divides p - 1.
`
`This prime generation scheme starts by using the SHA and a user supplied SEED to construct
`a prime, q, in the range 2159 < q < 2160
`. Once this is accomplished, the same SEED value is used
`to construct an X in the range 2L-I < X < 2L. The prime, p, is then formed by rounding X to a
`number congruent to 1 mod 2q as described below.
`
`An integer x in the range O ~ x < 28 may be converted to a g-long sequence of bits by using its
`binary expansion as shown below:
`
`Conversely, a g-long sequence of bits { x1, ••. ,x8
`
`} is converted to an integer by the rule
`
`Note that the first bit of a sequence corresponds to the most significant bit of the corresponding
`integer and the last bit to the least significant bit.
`
`Let L - 1 = n*160 + b, where both band n are integers and O ~ b < 160.
`
`Step 1. Choose an arbitrary sequence of at least 160 bits and call it SEED. Let g be the length
`of SEED in bits .
`
`Step 2. Compute
`
`U = SHA[SEED] XOR SHA[(SEED+l) mod 28 ].
`
`Step 3. Form q from U by setting the most significant bit (the 2159 bit) and the least significant
`bit to 1. In terms of boolean operations, q = U OR 2159 OR 1. Note that 2159 < q < 2160
`•
`
`Step 4. Use a robust primality testing algorithm to test whether q is prime1
`
`•
`
`Step 5. If q is not prime, go to step 1.
`
`Step 6. Let counter = 0 and offset = 2.
`
`Step 7. Fork = O, ... ,n let
`
`Vk = SHA[(SEED + offset + k) mod 28 ].
`
`1A robust primality test is one where the probability of a non-prime number passing the test is
`at most 2-so_
`
`11
`
`MOBILEIRON, INC. - EXHIBIT 1004
`Page 014
`
`

`

`Step 8. Let W be the integer
`
`
`
`and let X = W + 2L· 1• Note that 0 ::; W < 2L· 1 and hence 2L· 1
`
`::; X < 2L.
`
`Step 9. Let c = X mod 2q and set p = X - (c - 1). Note that p is congruent to 1 mod 2q.
`
`Step 10. If p < 2L· 1
`
`, then go to step 13.
`
`Step 11. Perform a robust primality test on p.
`
`Step 12. If p passes the test performed in step 11, go to step 15.
`
`Step 13. Let counter = counter + 1 and offset = offset + n + 1.
`
`Step 14. If counter~ 212 = 4096 go to step 1, otherwise (i.e. if counter < 4096) go to step 7.
`
`Step 15. Save the value of SEED and the value of counter for use in certifying the proper
`generation of p and q.
`
`12
`
`MOBILEIRON, INC. - EXHIBIT 1004
`Page 015
`
`

`

`•
`
`APPENDIX 3. RANDOM NUMBER GENERATION FOR THE DSA
`
`Any implementation of the DSA requires the ability to generate random or pseudorandom
`integers. Such numbers are used to derive a user's private key, x, and a user's per message
`secret number, k. These randomly or pseudorandomly generated integers are selected to be
`between 0 and the 160-bit prime q (as specified in the standard). They shall be generated by the
`techniques given in this appendix, or using other FIPS approved security methods.
`
`One FIPS approved pseudorandom integer generator is supplied in Appendix C of ANSI X9 .17,
`"Financial Institution Key Management (Wholesale)."
`
`Other pseudorandom integer generators are given in this appendix. These permit generation of
`pseudorandom values of x and k for use in the DSA. The algorithm in section 3.1 may be used
`to generate values for x. An algorithm fork and r is given in section 3.2. The latter algorithm
`allows most of the signature computation to be precomputed without knowledge of the message
`to be signed.
`
`The algorithms employ a one-way function G(t,c), where tis 160 bits, c is b bits (160::; b::; 512)
`and G(t,c) is 160 bits. One way to construct G is via the Secure Hash Algorithm (SHA), as
`defined in the Secure Hash Standard (SHS). The 160-bit message digest output of the SHA
`algorithm when message M is input is denoted by SHA(M). A second method for constructing
`G is to use the Data Encryption Standard (DES). The construction of G by these techniques is
`discussed in sections 3.3 and 3.4 of this appendix.
`
`•
`
`In the algorithms in sections 3.1 and 3.2, a secret b-bit seed-key is used. The algorithm in
`section 3.1 optionally allows the use of a user provided input. If G is constructed via the SHA
`as defined in section 3.3, then b is between 160 and 512. If DES is used to construct G as
`defined in section 3.4, then b is equal to 160.
`
`3.1. ALGORITHM FOR COMPUTING m VALUES OF x
`
`Let x be the signer's private key. The following may be used to generate m values of x:
`
`Step 1. Choose a new, secret value for the seed-key, XKEY.
`
`Step 2. In hexadecimal notation let
`
`t = 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0.
`
`This is the initial value for H0 II H1 II H2 II H3 II H4 in the SHS.
`
`Step 3. For j = 0 to m - 1 do
`
`a. XSEEDj = optional user input.
`
`13
`
`•
`
`MOBILEIRON, INC. - EXHIBIT 1004
`Page 016
`
`

`

`b. XVAL = (XKEY + XSEEDj) mod 2b.
`
`c. xj = G(t,XV AL) mod q.
`
`d. XKEY = (1 + XKEY + x) mod 2b.
`
`3.2. ALGORITHM FOR PRECOMPUTING ONE OR MORE k AND r VALUES
`
`This algorithm can be used to precompute k, k 1
`
`, and r form messages at a time. Algorithm:
`
`Step 1. Choose a secret initial value for the seed-key, KKEY.
`
`Step 2. In hexadecimal notation let
`
`t = EFCDAB89 98BADCFE 10325476 C3D2E1FO 67452301.
`
`This is a cyclic shift of the initial value for H0 II H1 II H2 II H 3 II H4 in the SHS.
`
`Step 3. For j = 0 to m - 1 do
`
`a. k = G(t,KKEY) mod q.
`b. Compute is· 1 = k- 1 mod q.
`
`c. Compute rj = (gk mod p) mod q.
`
`d. KKEY = (1 + KKEY + k) mod 2b.
`
`Step 4. Suppose Mo , ... , Mm-i are the next m messages. For j = 0 to m - 1 do
`
`a. Let h = SHA(M/
`
`c. The signature for Mj is (rj,s/
`
`Step 5. Let t = h.
`
`Step 6. Go to step 3.
`
`Step 3 permits precomputation of the quantities needed to sign the next m messages. Step 4 can
`begin whenever the first of these m messages is ready. The execution of step 4 can be suspended
`whenever the next of the m messages is not ready. As soon as steps 4 and 5 have completed,
`step 3 can be executed, and the results saved until the first member of the next group of m
`
`14
`
`MOBILEIRON, INC. - EXHIBIT 1004
`Page 017
`
`

`

`•
`
`messages is ready.
`
`In addition to space for KKEY, two arrays of length m are needed to store r0 , ••• rm.1 and 1co·1,
`... , kui.1·1 when they are computed in step 3. Storage for s0
`, sm.1 is only needed if the
`, •••
`signatures for a group of messages are stored; otherwise sj in step 4 can be replaced by s and a
`single space allocated.
`
`3.3. CONSTRUCTING THE FUNCTION G FROM THE SHA
`
`G(t,c) may be constructed using steps (a) - (e) in section 7 of the Specifications for the Secure
`Hash Standard. Before executing these steps, { Hj} and M1 must be initialized as follows:
`
`i. Initialize the { Hj} by dividing the 160 bit value t into five 32-bit segments as follows:
`
`Then Hj = ½ for j = 0 through 4.
`
`ii. There will be only one message block, M 1, which is initialized as follows:
`
`Ml = C II 0512-b
`
`(The first b bits of M1 contain c, and the remaining (512-b) bits are set to zero).
`
`Then steps (a) through (e) of section 7 are executed, and G(t,c) is the 160 bit string represented
`by the five words:
`
`•
`
`at the end of step (e).
`
`3.4. CONSTRUCTING THE FUNCTION G FROM THE DES
`
`Let a XOR b denote the bitwise exclusive-or of bit strings a and b. Suppose al, a2, bl, b2 are
`32-bit strings. Let bl' be the 24 least significant bits of bl. Let K = bl' II b2 and A= al II a2.
`Define
`
`In the above, DESK(A) represents ordinary DES encryption of the 64-bit block A using the 56-bit
`key K. Now suppose t and c are each 160 bits. To compute G(t,c):
`
`Step 1. Write
`
`•
`
`15
`
`MOBILEIRON, INC. - EXHIBIT 1004
`Page 018
`
`

`

`t = t1 11 ~ 11 t3 11 t4 11 t5
`
`C = C1
`
`II C2 II C3 II C4 II C5
`
`In the above, each ti and ci is 32 bits.
`
`Step 2. For i = 1 to 5 do
`
`xi=½ XOR ci
`
`Step 3. For i = 1 to 5 do
`
`b 1 = c((i+3) mod 5) + I
`
`b2 = C((i+2) mod 5) + I
`
`al = xi
`
`a2 = x(i mod 5) + I XOR x((i+3) mod 5) + I
`
`Yi.I 11 Yi,2 = DESb1,bi(al,a2)
`
`(Yi.1• Yi.2 = 32 bits)
`
`Step 4. For i = 1 to 5 do
`
`Zi = Yi.I XOR Y((i+l) mod 5)+1,2 XOR Y((i+2) mod 5)+1,l
`
`Step 5. Let
`
`16
`
`MOBILEIRON, INC. - EXHIBIT 1004
`Page 019
`
`

`

`•
`
`•
`
`•
`
`APPENDIX 4. GENERATION OF OTHER QUANTITIES
`
`This appendix is for informational purposes only and is not required to meet the standard.
`
`The algorithms given in this appendix may be used to generate the quantities g, k" 1
`in the DSS.
`
`, and s· 1 used
`
`To generate g:
`
`Step 1. Generate p and q as specified in Appendix 2.
`
`Step 2. Let e = (p - 1)/q.
`
`Step 3. Set h = any integer, where 1 < h < p - 1 and h differs from any value previously tried.
`
`Step 4. Set g = he mod p.
`
`Step 5. If g = 1, go to step 3.
`
`To compute the multiplicative inverse n· 1 mod q for n with 0 < n < q, where 0 < n· 1 < q:
`
`Step 1. Set i = q, h = n, v = 0, and d = 1.
`
`Step 2. Let t = i DIV h, where DIV is defined as integer division.
`
`Step 3. Set x = h.
`
`Step 4. Set h = i - tx.
`
`Step 5. Set i = x.
`
`Step 6. Set x = d.
`
`Step 7. Set d = v - tx.
`
`Step 8. Set v = x.
`
`Step 9. If h > 0, go to step 2.
`
`Step 10. Let n·1 = v mod q.
`
`Note that in step 10, v may be negative. The v mod q operation should yield a value between
`1 and q - 1 inclusive .
`
`17
`
`MOBILEIRON, INC. - EXHIBIT 1004
`Page 020
`
`

`

`APPENDIX S. EXAMPLE OF THE DSA
`
`This appendix is for informational purposes only and is not required to meet the standard.
`
`Let L = 512 (size of p). The values in this example are expressed in hexadecimal notation. The
`p and q given here were generated by the prime generation standard described in appendix 2
`using the 160-bit SEED:
`
`d5014e4b
`
`60ef2ba8
`
`b6211b40
`
`62ba3224
`
`e0427dbd
`
`With this SEED, the algorithm found p and q when the counter was at 38.
`
`x was generated by the algorithm described in appendix 3, section 3.1, using the SHA to
`construct G (as in appendix 3, section 3.3) and a 160-bit XSEED:
`
`XSEED =
`
`bd029bbe
`
`7f51960b
`
`cf9edb2b
`
`61f06f0f
`
`eb5a38b6
`
`t =
`
`67452301
`
`EFCDAB89 98BADCFE 10325476
`
`C3D2E1F0
`
`x = G(t,XSEED) mod q
`
`k was generated by the algorithm described in appendix 3, section 3.2, using the SHA to
`construct G (as in appendix 3, section 3.3) and a 160-bit KSEED:
`
`KSEED =
`
`687a66d9
`
`0648f993
`
`867e121f
`
`4ddf9ddb
`
`01205584
`
`t =
`
`EFCDAB89 98BADCFE 10325476
`
`C3D2E1F0
`
`67452301
`
`k = G(t,KSEED) mod q
`
`Finally:
`
`h=2
`
`18
`
`MOBILEIRON, INC. - EXHIBIT 1004
`Page 021
`
`

`

`• p=
`
`d41 la4a0
`3fe365cf
`6afl 7ac8
`
`e393f6aa
`71c86224
`a9fe5f24
`
`b0f08b14
`12db6e7d
`9cc81f42
`
`d1845866
`d02bbe13
`7fc543f7
`
`5b3e4dbd
`d88c58d7
`
`ce254454
`263e9023
`
`b20db0bl
`
`0ldf0c66
`
`24fc1392
`
`ba55f77d
`
`577481e5
`
`b3085510
`25248b58
`43ecld3e
`
`021f9990
`a3dc4f71
`020dadab
`
`49a9e7cd
`781d21f2
`bf782257
`
`3872ce99
`df89b717
`8255c104
`
`58186b50
`47bd54b3
`
`07e7adaf
`23bbecc4
`
`6b2cd935
`
`d0192d54
`
`e2c942b5
`
`74c80102
`
`c8f8ef67
`
`q=
`
`g=
`
`x=
`
`k=
`
`•
`
`•
`
`79577ddc
`
`aafddc03
`
`8b865b19
`
`f8eblada
`
`8a2838c6
`
`kinv =
`
`2784e3d6
`
`72d972a7
`
`4e22c67f
`
`4f4f726e
`
`cc751efa
`
`M = ASCII form of "abc" (See FIPS PUB YY, Appendix A)
`
`SHA(M) =
`
`0164b8a9
`
`14cd2a5e
`
`74c4f7ff
`
`082c4d97
`
`fledf880
`
`y=
`
`r=
`
`b32fbec0
`9bb12d6c
`37f655cb
`
`3175791d
`628784fb
`3ea4767c
`
`f08c3f86
`742e66ed
`878cbd2d
`
`lc81df7d
`315754df
`783ee662
`
`e7e0cba7
`e38b5984
`
`flc4f726
`e94d3725
`
`9b77f705
`
`4c81531c
`
`4e46a469
`
`2fbfe0f7
`
`7f7ebff2
`
`19
`
`MOBILEIRON, INC. - EXHIBIT 1004
`Page 022
`
`

`

`s =
`
`w=
`
`95b4f608
`
`lf8f890e
`
`4b5a199e
`
`f10ffe21
`
`f52b2d68
`
`Oceb5f6b
`
`875f6b67
`
`7e093134
`
`df70b0d4
`
`3226680c
`
`ul =
`
`347089a2
`
`9897273b
`
`fc7a774f
`
`a70e0e0e
`
`153bcc95
`
`u2 =
`
`793d9312
`gul mod p =
`
`a41b88af
`
`aa2clbd9
`
`49ec3bee
`
`2e75d2f5
`
`57a198ab
`96b60b9c
`dl4ldc4d
`
`2c8ea0b6
`1285b848
`71925ef0
`
`4810767a
`ld08505e
`6acde0a5
`
`ff732fb2
`201a5c68
`b89c5671
`
`da5fcafb
`523a15ee
`
`278889fl
`2fb62a56
`
`y112 mod p =
`
`