( Appeared in the Federal Register dated August 30, 1991 ) DEPARTMENT OF COMMERCE National Institute of Standards and Technology A PROPOSED FEDERAL INFORMATION PROCESSING STANDARD FOR DIGITAL SIGNATURE STANDARD (DSS) AGENCY: National Institute of Standards and Technology (NIST), Commerce. ACTION: Notice; Request for Comments. SUMMARY: A Federal Information Processing Standard (FIPS) for Digital Signature Standard (DSS) is being proposed. This proposed standard specifies a public-key based digital signature algorithm (DSA) appropriate for Federal digital signature applications. The proposed DSS uses a public key to verify to a recipient the integrity of data and the identity of the sender of the data. The DSS can also be used by a third party to ascertain the authenticity of a signature and the data associated with it. This proposed standard adopts a public-key signature system that uses a pair of transformations to generate and verify a digital value called a signature. The government has applied to the U.S. Patent Office for a patent on this technique. The government will also seek foreign patents as appropriate. NIST intends to make this DSS technique available world-wide on a royalty-free basis in the public interest. We believe this technique is patentable and that no other patents would apply to the DSS, but we cannot give firm assurances to such effect in advance of issuance of the patent. The purpose of this notice is to solicit views from the public, manufacturers, and Federal, state, and local government users so that their needs can be considered prior to submission of this proposed standard to the Secretary of Commerce for review and approval. The proposed standard contains two sections: (1) an announcement section, which provides information concerning the applicability, implementation, and maintenance of the standard; and (2) a specifications section which deals with the technical aspects of the standard. Only the announcement section of the standard is provided in this notice. Interested parties may obtain copies of the specifications section from the Standards Processing Coordinator (ADP), National Institute of Standards and Technology, Technology Building, Room B-64, Gaithersburg, MD 20899, telephone (301) 975-2816. DATE: Comments on this proposed standard must be received on or before (please insert date which is ninety (90) days from the date of publication of this notice in the Federal Register). ADDRESS: Written comments concerning the proposed standard should be sent to: Director, Computer Systems Laboratory, ATTN: Proposed FIPS for DSS, Technology Building, Room B-154, National Institute of Standards and Technology, Gaithersburg, MD 20899. Written comments received in response to this notice will be made part of the public record and will be made available for inspection and copying in the Central Reference and Records Inspection Facility, Room 6020, Herbert C. Hoover Building, 14th Street between Pennsylvania and Constitution Avenues, NW, Washington, DC 20230. FOR FURTHER INFORMATION CONTACT: Mr. Miles Smid, National Institute of Standards and Technology, Gaithersburg, MD 20899, telephone (301) 975-2938. SUPPLEMENTARY INFORMATION: This proposed FIPS is the result of evaluating a number of alternative digital signature techniques. In making the selection, the NIST has followed the mandate contained in section 2 of the Computer Security Act of 1987 that NIST develop standards and guidelines to "... assure the cost- effective security and privacy of sensitive information in Federal systems". In meeting this statutory responsibility, NIST has placed primary emphasis on selecting the technology that best assures the appropriate security of Federal information and, among technologies offering comparable protection, on selecting the option with the most desirable operating and use characteristics. Among the factors that were considered during this process were the level of security provided, the ease of implementation in both hardware and software, the ease of export from the U.S., the applicability of patents, impact on national security and law enforcement and the level of efficiency in both the signing and verification functions. A number of techniques were deemed to provide appropriate protection for Federal systems. The technique selected has the following desirable characteristics: -- NIST expects it to be available for public use on a royalty-free basis. Broader use of this technique resulting from public availability should be an economic benefit to the government and the public. -- The technique selected provides for efficient implementation of the signature operations in smart card applications. In these applications the signing operations are performed in the computationally modest environment of the smart card while the verification process is implemented in a more computationally rich environment such as a personal computer, a hardware cryptographic module, or a mainframe computer. NIST has received agreement from Department of Defense authorities that this digital signature technique may be used to sign unclassified data processed by "Warner Amendment" systems (10 U.S.C. 2315 and 44 U.S.C. 3502(2)) as well as classified data in selected applications. A hashing function has not been specified by NIST at this time for use with the DSS. NIST has been reviewing various candidate hashing functions; however, we are not satisfied with any of the functions we have studied thus far. NIST does intend to publish a hashing function that is complementary to the DSS. (NOTE: Original signed by Dr. John Lyons, NIST Director) *********************************************************************** ( The following is the Proposed Digital Signature Standard) A PROPOSED DIGITAL SIGNATURE STANDARD (DSS) Foreword The Federal Information Processing Standards Publication Series of the National Institute of Standards and Technology (NIST) is the official series of publications 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 the 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 modifications to data and to authenticate the identity of the user who generates the signature. In addition, the recipient of signed data can use a digital signature in proving to a third party that the signature was in fact generated by the signer of the data. This is known as nonrepudiation since the signer of data cannot, at a later time, repudiate the signature. Key words: ADP security, computer security, digital signatures, public-key cryptography, Federal Information Processing Standard. Federal Information Processing Standards Publication XX ANNOUNCING A DIGITAL SIGNATURE STANDARD 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 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. Name of Standard: Digital Signature Standard. Category of Standard: ADP Operations, Computer Security. 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 it can be used to verify the identity of the originator and integrity of the data. The DSA includes signature generation and verification. Generation makes use of a private key to generate a digital signature. Verification of the signature makes use of a public key which corresponds to, but is not the same as, the private key used to generate the signature. Each user possesses a private and public key pair. Public keys are assumed to be known to all members of a group of users or to the public in general. Private keys must be known only by their creators. 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. The message digest is then signed. The digital signature is sent to the intended recipient along with the signed data (often called the message). The recipient 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 will be specified in a separate standard. Similar procedures may be used to generate and verify signatures for stored as well as transmitted data. Approving Authority: Secretary of Commerce. Maintenance Agency: Computer Systems Laboratory, National Institute of Standards and Technology. 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. Private and commercial organizations are encouraged to adopt and use this standard. Applications: The DSA authenticates the integrity of the signed data and the identity of the signer. The DSA may also be used in proving to a third party that data was actually signed 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 or hardware. Only implementations of the DSA that are validated by NIST will be considered as complying with this standard. Information about the requirements for validating implementations of this standard 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: Implementations of the DSA in this standard may be covered by U.S. and foreign patents. Implementation Schedule: This standard becomes effective six months after the publication date of this FIPS PUB. Specifications: Federal Information Processing Standard (FIPS XX) Digital Signature Standard (affixed). Cross Index: a. FIPS PUB 46-1, Data Encryption Standard. b. FIPS PUB 73, Guidelines for Security of Computer Applications. c. FIPS PUB 140-1, Security Requirements for Cryptographic Modules. 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 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. Compliance with a standard would 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 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 Government 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 accompanying documents, with such deletions as the agency is authorized and decides to make under 5 United States Code Section 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 XX (FIPS PUB XX), 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. Federal Information Processing Standards Publication XX Specifications for a 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 transmitted from one party to another, the recipient may desire to know that the message has not been altered in transit. Furthermore, the recipient may wish to be certain of the origin of the message. 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 a third party that the message was, in fact, signed by the originator. Unlike their written counterparts, digital signatures also verify the integrity of messages. It is also desirable to be able to generate digital signatures 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 A private and public key pair is used to generate and verify a digital signature. These keys are employed in conjunction with a hash function H, which is not specified in this standard. The holder of a private key can generate a signature for data, referred to as the message, m. A holder of the corresponding public key can verify the signature. Both signature generation and verification use H. An adversary, who does not know the private key of a user, cannot generate that user's signature for a message. In other words, signatures cannot be forged: an adversary cannot generate a correct signature for another person for any message. However, by using the appropriate public key, anyone can check that a given signature is valid. 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. 4. DSA PARAMETERS Let A. p = a prime modulus where 2^511 < p < 2^512. B. q = a prime divisor of p - 1 where 2^159 < q < 2^160. C. g = h^((p-1)/q) mod p, where h is any integer with 0 < h < p such that h^((p-1)/q) mod p > 1. D. x = an integer with 0 < x < q. E. y = g^x mod p. F. m = the message to be signed and transmitted. G. k = a random integer with 0 < k < q. H. H = a one-way hash function. 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. x and k must be secret. k must be changed for each signature. H is not specified in this standard. However, H must be chosen so that it is computationally infeasible to create a message which results in a given hash value and it must also be computationally infeasible to find any two different messages which result in the same hash value. 5. SIGNATURE GENERATION To send a signed message m the user chooses a random k and computes r = (g^k mod p) mod q s = (k^-1 (H(m) + xr)) mod q. where k^-1 is the multiplicative inverse of k, mod q; i.e., (k^-1 k) mod q = 1 and 0 < k^-1 < q. The values r and s constitute the signature of the message. These are transmitted along with the message m to the recipient. 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 recipient in an authenticated manner. Let m', r', and s' be the received versions of m, r, and s, respectively, and let y be the public key of the sender. To verify the signature, the recipient first checks to see that 0 < r' < q and 0 < s' < q; if either condition is violated the signature is rejected. If these two conditions are satisfied, the recipient computes: w = (s')^-1 mod q u1 = ((H(m'))w) mod q u2 = ((r')w) mod q v = (((g)^(u1) (y)^(u2)) mod p) mod q. If v = r', then the signature is verified and the receiver can have high confidence that the received message was sent by the party holding the secret key x corresponding to y. For a proof that v = r' when m' = m, r' = r, and s' = 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 sender, or the message may have been signed by an impostor. The message should be considered invalid. 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 provide a rigorous proof that in the signature verification (Section 6 of the DSS) we have v = r' when m' = m, r' = r, and s' = s. The proof is given by the Theorem below; it is preceded by four lemmas. LEMMA 1. For any nonnegative integer t, if g = h^((p-1)/q) mod p, then g^t mod p = g^(t mod q) mod p. Proof: By the Euler/Fermat theorem, since h is relatively prime to p, we have h^(p-1) mod p = 1. Hence for any nonnegative integer n, g^(nq) mod p = (h^((p-1)/q) mod p)^(nq) mod p = h^(((p-1)/q)nq) mod p = h^((p-1)n) mod p = ((h^(p-1) mod p)^n) mod p = 1^n mod p = 1. Thus, for any nonnegative integers n and z we have g^(nq+z) mod p = (g^(nq) g^z) mod p = ((g^(nq) mod p) (g^z mod p)) mod p = g^z mod p. Any nonnegative integer t can be represented uniquely as t = nq + z where n and z are nonnegative integers and 0 s z < q. Then g^t mod p = g^z mod p. Also, z = t mod q. The result follows. QED. LEMMA 2. For any nonnegative integers a and b, g^(a mod q + b mod q) mod p = g^((a + b) mod q) mod p. Proof: By Lemma 1 we have g^(a mod q + b mod q) mod p = g^((a mod q + b mod q) mod q) mod p = g^((a + b) mod q) mod p. QED. LEMMA 3. y^((rw) mod q) mod p = g^((xrw) mod q) mod p. Proof: Since y = g^x mod p, using Lemma 1 we have y^((rw) mod q) mod p = (g^x mod p)^((rw) mod q) mod p = g^(x((rw) mod q)) mod p = g^((x((rw) mod q)) mod q) mod p (by Lemma 1) = g^((xrw) mod q) mod p. QED. LEMMA 4. ((H(m) + xr)w) mod q = k. Proof: We have s = (k^-1 (H(m) + xr)) mod q. Since (k k^-1) mod q = 1, (ks) mod q = (k((k^-1 (H(m) + xr)) mod q)) mod q = ((k(k^-1 (H(m) + xr)))) mod q = (((k k^-1) mod q) ((H(m) + xr) mod q)) mod q = (H(m) + xr) mod q. Since w = s^-1 mod q we have (ws) mod q = 1, and thus ((H(m) + xr)w) mod q = (((H(m) + xr) mod q) (w mod q)) mod q = (((ks) mod q) (w mod q)) mod q = (kws) mod q = ((k mod q) ((ws) mod q)) mod q = k mod q. Since 0 < k < q we have k mod q = k. QED. THEOREM. If m' = m, r' = r, and s' = s, then v = r'. Proof: Using Lemmas 2, 3 and 4 we find v = ((g^(u1) y^(u2)) mod p) mod q = ((g^((H(m)w) mod q) y^((rw) mod q)) mod p) mod q = ((g^((H(m)w) mod q) g^((xrw) mod q)) mod p) mod q (by Lemma 3) = ((g^((H(m)w) mod q + (xrw) mod q)) mod p) mod q = ((g^(((H(m)w) mod q + (xrw) mod q) mod q)) mod p) mod q = ((g^((H(m)w + xrw) mod q)) mod p) mod q (by Lemma 2) = ((g^(((H(m) + xr)w) mod q)) mod p) mod q = (g^k mod p) mod q (by Lemma 4) = r = r'. QED. Appendix 2 Generation of Parameters for the DSA This appendix is for informational purposes only and is not required to meet the standard. This appendix includes suggestions for generating the parameters and performing the functions needed to implement the DSA. These algorithms require a random number generator (see Appendix 3), and an efficient modular exponentiation algorithm (see Appendix 4). 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^n. Therefore, n=50 should give an acceptable probability of error. To test whether an integer is prime: 1. Set i = 1 and n = 50. 2. Set w = the integer to be tested, w = 1 + 2^a m, where m is odd and 2^a is the largest power of 2 dividing w-1. 3. Generate a random integer b in the range 1 0 and z = 1, go to step 8. 7. j = j + 1. If j < a, set z = z^2 mod w and go to step 6. 8. w is not prime. Stop. 9. If i< n, set i = i + 1 and go to step 3. Otherwise, w is probably prime. To generate a prime q where 2^159 < q < 2^160: 1. Set n = a random number between 2^158 and 2^159 - 1, inclusive. 2. Set t = 2n + 1. 3. If t < 2^160, test whether t is prime. Otherwise, go to step 1. 4. If t is prime, set q = t. Otherwise, set t = t + 2 and go to step 3. To generate a prime p where 2^511 < p < 2^512 and q divides p - 1: 1. Generate q as specified above. 2. Generate a random integer n, where n is between (2^511-1)/(2q) and (2^512-1)/(2q). 3. Set t = 2nq + 1. 4. Test whether t is prime. 5. If t is prime, set p = t. Otherwise, go to step 2. To generate an element g of order q mod p: 1. Generate p and q as specified above. 2. Set h = a random number, where 1 < h < p-1. 3. Set t = h^((p-1)/q) mod p. 4. If t = 1 then go to step 2. Otherwise, set g = t. To generate integers x and k: Set x and k equal to random integers between 0 and q. To generate y: Set y = g^x mod p. To compute the signature (r,s) of a message m: 1. Set t = g^k mod p. 2. Set r = t mod q. 3. Set h = H(m) where H is a hash function. 4. Calculate k^-1 mod q as described below. 5. Set s = ((k^-1) (h + xr)) mod q. To verify the signature (r,s) of a message m: 1. m, r, and s are received as m', r', and s', respectively. 2. If r' <= 0 or r' >= q then reject the signature as invalid. 3. If s' <= 0 or s' >= q then reject the signature as invalid. 4. Set h = H(m'). 5. Calculate w = s'^-1 mod q as described below. 6. Set u1 = (hw) mod q. 7. Set u2 = (r'w) mod q. 8. Set a = g^(u1) mod p. 9. Set b = y^(u2) mod p. 10. Set t = (ab) mod p. 11. Set v = t mod q. 12. If v = r', signature is verified. Otherwise, reject signature as invalid. To compute the multiplicative inverse n^-1 mod q for n with 0 < n < q: 1. Set i = q, h = n, v = 0 and d = 1. 2. While h > 0 repeat steps 3 thru 5. 3. t = i DIV h where DIV is defined as integer division. 4. Set x = h, h = i - tx and i = x. 5. Set x = d, d = v - tx and v = x. 6. n^-1 = v mod q. Appendix 3 Random Number Generation for the DSA This appendix is for informational purposes only and is not required to meet the standard. Any implementation of the DSA requires the ability to generate random numbers. Random numbers are used to derive a user's private key and a user's per message random secret number. These random numbers are selected to be between 0 and the 160-bit prime q (as specified in the standard). The numbers can be generated by either a true noise hardware randomizer or via a pseudorandom function. Such a function would employ a user generated and secret "seed" key to initialize the number generator. The generator then would produce a stream of bits or numbers which could be converted into the integers mod q discussed above. One such pseudorandom number generator is the key generation methodology found in Appendix C of ANSI X9.17, "Financial Institution Key Management (Wholesale)". Appendix 4 Modular Arithmetic for the DSA This appendix is for informational purposes only and is not required to meet the standard. One key to efficient implementation of the Digital Signature Standard is the development of a modular arithmetic package suited to the processor one intends to use. For the purposes of this discussion, we will consider two types of processors: hardware and software and suggest some techniques which may allow for efficient implementation of the DSA in those systems. With respect to hardware implementations an excellent reference is "VLSI Implementation of Public Key Encryption Algorithms" by Orton, Roy, Scott, Peppard and Tavares from the Proceedings of CRYPTO-86. That paper and the references found at its end will provide a good basis for anyone looking into hardware implementations of the DSA. It is also worth noting that several commercial firms have custom processors to do modular arithmetic on the market. With respect to software implementations, there are many different ways to proceed and a rich literature containing different techniques for different computing environments. For instance, the algorithms one chooses for 32-bit processors may be substantially different than those which would be appropriate for 8-bit processors. Likewise, one can make trade offs on computation versus memory in various algorithms. Good starting places for modular arithmetic algorithms in software are found in "A Cryptographic Library for the Motorola DSP56000" by Dusse and Kaliski from the Proceedings of EUROCRYPT-90 and "Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor" by Barrett from the Proceedings of CRYPTO-86. These papers contain pseudo-code for some of the more popular techniques used in modular arithmetic. Appendix 5 Example of the DSA This appendix is for informational purposes only and is not required to meet the standard. p = Prime Modulus = d0451ffe 2c64c4ed 6b0ae636 5b7fef9c 15425e40 a37ca5f8 39865e2c fb4169a0 d825c913 0f8864ff fcf3bfbe b0273660 67aa27e2 7bfcaf40 00000000 00000001 q = Prime Divisor = d9525756 704a663e 7323caf2 6fb8fc25 77e4fbeb g = Element of Order q Mod p = acf958c4 0d301efc 5153e7dc d5ef75fe c9e8fb0f ae6a80ee 5c3b84b9 c0e51305 1b2b7542 e66b8d3a 25e93891 1ad6be5c 24395099 c6ddaa86 e18942f2 984275a x = Private Key = 12345678 9abcdef0 12345678 9abcdef y = g^x mod p = Public Key = 9d168087 c60c5cb3 aeb1e8ac c622f167 f1e97151 0b34876c 080d81b5 20329817 e3e279fa 86eb6a9d 5e9e5897 5clf3d0d 3786ce04 abb0cab4 dfd9fa13 50bb3aa3 k = Random Secret Integer = bf27aa41 6c006dd4 b4f2806c 71171cc4 ce28db r = (g^k mod p) mod q = 1c3d5143 a7beb085 9cbd08a2 039d7148 27ceddf9 h = H(m) = Hash(message) = 2a2a2a2a 2a2a2a2a 2a2a2a2a 2a2a2a2a 2a2a2a2a (h + xr) mod q = 20215b52 aa605b7f 967991de b947a07f 13413a8a 8753d457 d1897afe 786c8f82 5ecaal k^-1 mod q = 5dfb26c8 208eda68 d8bb5fce 89732bae 595392e6 s = (k^-1 (h + xr)) mod q = 6f0be90c 72350564 77c69e89 ab6416b2 f365d95c w = s^-1 mod q = 27fd6332 9e1cddf1 883b1d62 a345d9c5 f115d821 u1 = (hw) mod q = 6521b9e7 e0824239 0754396d c5327f98 c74fc641 u2 = (rw) mod q = 52d754b2 153d3c14 483e65de 9895abe9 6bbb7751 g^(u1) mod p = c50370ba af79d463 7bf6ea24 579495de d0fd1190 2e5f8c5f 8524dd53 ee13c1e8 fb4ad43c db2e86f7 b892dc81 5e7676ab 11b48803 916e453b f95bdfeb 93003009 y^(u2) mod p = 53b07663 b7078870 b640044f 592d1076 8b82fb49 1cfd10fe 4310a315 f3cf4de9 5ccff3df 926f837d 69afe707 640dd5a2 6fd41b11 1ff5cc6d 51aa7453 d79ca533 v = ((g^(u1) mod p)(y^(u2) mod p) mod p) mod q = 1c3d5143 a7beb085 9cbd08a2 039d7148 27ceddf9