System-Digital Signatures

DigitalSignatureAlgorithm
This class implements the Digital Signature Algorithm (DSA) of the U.S. government's "Digital Signature Standard" (DSS). The DSA algorithm was proposed in 1991 and became a standard in May 1994. The official description is available as a Federal Information Processing Standards Publication (FIPS PUB 186, May 19, 1994). A companion standard, the Secure Hash Standard, or SHS (FIPS PUB 180-1, April 17, 1995), describes a 160-bit message digest algorithm known as the Secure Hash Algorithm (SHA). This message digest is used to compute the document signature.
Here's how to use it:
1. The "signer" creates a pair of keys. One of these must be kept private. The other may be freely distributed. For example, it could be built into the signature checking code of an application.
2. When the signer wishes to sign a packet of data (a "message") , he uses the secure hash algorithm to create a 160-bit message digest (hash) which is used as the input to DSA. The result of this is a pair of large numbers called a "signature" that is attached to the original message.
3. When someone receives a signed message purported to have come from the signer, they compute the 160-bit hash of the message and pass that, along with the message signature and the signer's public key, to the signature verification algorithm. If the signature checks, then it is virtually guaranteed that the message originated from someone who had the signer's private key. That is, the message is not a forgery and has not been modified since it was signed. For example, if the message contains a program, and the recipient trusts the signer, then the recipient can run the program with the assurance that it won't do anything harmful. (At least, not intentionally. A digital signature is no guarantee against bugs! :->)
The signer must keep the private key secure, since anyone who has the private key can forge the signer's signature on any message they like. As long as the secret key is not stolen, cryptographers believe it to be virtually impossible either to forge a signature, to find a message that matches an existing sigature, or to discover the signer's private key by analyzing message signatures. Knowing the public key (which, for example, could be recovered from an application that had it built in), does not weaken the security at all.
An excellent reference work on digital signatures and cryptography in general is:
Schneier, Bruce
"Applied Cryptography: Protocols, Algorithms, and Source Code in C"
John Wiley and Sons, 1996.
I used this book as a guide to implementing many of the numerical algorithms required by DSA.
Patents and Export Restrictions:
Many digital signature technologies are patented. DSA is also patented, but the patent is owned by the U.S. government which has made DSA available royalty-free. There is a claim that the government patent infringes on an earlier patent by Schnorr, but the government is requiring the use of DSA, so they apparently believe this claim is not strong enough to be a serious threat to their own patent.
Most cryptography technology, including digital signature technology, requires an export license for it to be distributed outside the U.S. Recent legislation may have relaxed the export license requirements, but it would be prudent to check the current regulations before exporting this code.
computeSignatureForMessageHash:privateKey:
Answer the digital signature of the given message hash using the given private key. A signature is a pair of large integers. The private key is an array of four large integers: (p, q, g, x).
example
generateKeySet
Generate and answer a key set for DSA. The result is a pair (<private key><public key>). Each key is an array of four large integers. The private key is (p, q, g, x); the public one is (p, q, g, y). The signer must be sure to record (p, q, g, x), and must keep x secret to prevent someone from forging their signature.
generateQandP
Generate the two industrial-grade primes, q (160-bits) and p (512-bit) needed to build a key set. Answer the array (q, p, s), where s is the seed that from which q and p were created. This seed is normally discarded, but can be used to verify the key generation process if desired.
generateRandomLength:s:n:
Answer a random number of bitLength bits generated using the secure hash algorithm.
generateSandQ
Generate a 160-bit random seed s and an industrial grade prime q.
initRandom:
Initialize the the secure random number generator with the given value. The argument should be a positive integer of up to 512 bits chosen randomly to avoid someone being able to predict the sequence of random values generated.
initRandomFromString:
Ask the user to type a long random string and use the result to seed the secure random number generator.
initRandomFromUser
Ask the user to type a long random string and use the result to seed the secure random number generator.
initRandomNonInteractively
initialize
Subclasses should redefine this method to perform initializations on instance creation
inverseOf:mod:
Answer the inverse of x modulus n. That is, the integer y such that (x * y) \\ n is 1. Both x and n must be positive, and it is assumed that x < n and that x and n are integers.
isProbablyPrime:
Answer true if p is prime with very high probability. Such a number is sometimes called an 'industrial grade prime'--a large number that is so extremely likely to be prime that it can assumed that it actually is prime for all practical purposes. This implementation uses the Rabin-Miller algorithm (Schneier, p. 159).
logOfLargestPowerOfTwoDividing:
Answer the base-2 log of the largest power of two that divides the given integer. For example, the largest power of two that divides 24 is 8, whose log base-2 is 3. Do this efficiently even when the given number is a large integer. Assume that the given integer is > 0.
nextRandom160
Answer a newly generated 160-bit random number in the range [1..(2^160 - 1)].
sign:privateKey:
sign:privateKey:dsa:
signatureToString:
Answer a string representation of the given signature. This string can be parsed using the stringToSignature: method.
stringToSignature:
Answer the signature stored in the given string. A signature string has the format:
'[DSA digital signature <r> <s>]'
where <r> and <s> are large positive integers represented by strings of hexidecimal digits.
testExamplesFromDisk
testKeySet
time:as:count:
timeDecode:
timeDirect:as:count:
verify:isSignatureOf:publicKey:
verifySignature:ofMessageHash:publicKey:
Answer true if the given signature is the authentic signature of the given message hash. That is, if the signature must have been computed using the private key set corresponding to the given public key. The public key is an array of four large integers: (p, q, g, y).
writeExamplesToDisk
SecureHashAlgorithm
This class implements the Secure Hash Algorithm (SHA) described in the U.S. government's Secure Hash Standard (SHS). This standard is described in FIPS PUB 180-1, "SECURE HASH STANDARD", April 17, 1995.
The Secure Hash Algorithm is also described on p. 442 of 'Applied Cryptography: Protocols, Algorithms, and Source Code in C' by Bruce Scheier, Wiley, 1996.
See the comment in class DigitalSignatureAlgorithm for details on its use.
Implementation notes:
The secure hash standard was created with 32-bit hardware in mind. All arithmetic in the hash computation must be done modulo 2^32. This implementation uses ThirtyTwoBitRegister objects to simulate hardware registers; this implementation is about six times faster than using LargePositiveIntegers (measured on a Macintosh G3 Powerbook). Implementing a primitive to process each 64-byte buffer would probably speed up the computation by a factor of 20 or more.
constantForStep:
Answer the constant for the i-th step of the block hash loop. We number our steps 1-80, versus the 0-79 of the standard.
expandedBlock:
Convert the given 64 byte buffer into 80 32-bit registers and answer the result.
finalHash
Concatenate the final totals to build the 160-bit integer result.
hashFunction:of:with:with:
Compute the hash function for the i-th step of the block hash loop. We number our steps 1-80, versus the 0-79 of the standard.
hashInteger:
Hash the given positive integer. The integer to be hashed should have 512 or fewer bits. This entry point is used in key generation.
hashInteger:seed:
Hash the given positive integer. The integer to be hashed should have 512 or fewer bits. This entry point is used in the production of random numbers
hashMessage:
Hash the given message using the Secure Hash Algorithm.
hashStream:
Hash the contents of the given stream from the current position to the end using the Secure Hash Algorithm. The SHA algorithm is defined in FIPS PUB 180-1. It is also described on p. 442 of 'Applied Cryptography: Protocols, Algorithms, and Source Code in C' by Bruce Scheier, Wiley, 1996.
initialize
Subclasses should redefine this method to perform initializations on instance creation
initializeTotals
Initialize totalA through totalE to their seed values.
initializeTotalsArray
Initialize the totals array from the registers for use with the primitives.
primExpandBlock:into:
Expand the given 64-byte buffer into the given Bitmap of length 80.
primHasSecureHashPrimitive
Answer true if this platform has primitive support for the Secure Hash Algorithm.
primHashBlock:using:
Hash the given block (a Bitmap) of 80 32-bit words, using the given workingTotals.
processBuffer:
Process given 64-byte buffer, accumulating the results in totalA through totalE.
processBufferUsingPrimitives:
Process given 64-byte buffer using the primitives, accumulating the results in totals.
processFinalBuffer:bitLength:
Process given buffer, whose length may be <= 64 bytes, accumulating the results in totalA through totalE. Also process the final padding bits and length.
storeLength:in:
Fill in the final 8 bytes of the given ByteArray with a 64-bit big-endian representation of the original message length in bits.
ThirtyTwoBitRegister
I represent a 32-bit register. An instance of me can hold any non-negative integer in the range [0..(2^32 - 1)]. Operations are performed on my contents in place, like a hardware register, and results are always modulo 2^32.
This class is primarily meant for use by the SecureHashAlgorithm class.
+=
Replace my contents with the sum of the given register and my current contents.
asByteArray
asInteger
Answer the integer value of my current contents.
asReverseInteger
Answer the byte-swapped integer value of my current contents.
bitAnd:
Replace my contents with the bitwise AND of the given register and my current contents.
bitInvert
Replace my contents with the bitwise inverse my current contents.
bitOr:
Replace my contents with the bitwise OR of the given register and my current contents.
bitShift:
Replace my contents with the bitShift of anInteger.
bitXor:
Replace my contents with the bitwise exclusive OR of the given register and my current contents.
byte1:byte2:byte3:byte4:
byteAt:
copy
Use the clone primitive for speed.
hi
leftRotateBy:
Rotate my contents left by the given number of bits, retaining exactly 32 bits.
load:
Set my contents to the value of given integer.
loadFrom:at:
Load my 32-bit value from the four bytes of the given ByteArray starting at the given index. Consider the first byte to contain the most significant bits of the word (i.e., use big-endian byte ordering).
low
new
printOn:
Print my contents in hex with a leading 'R' to show that it is a register object being printed.
reverseLoadFrom:at:
Load my 32-bit value from the four bytes of the given ByteArray
starting at the given index. Consider the first byte to contain the most
significant bits of the word (i.e., use big-endian byte ordering).
storeInto:at:
Store my 32-bit value into the four bytes of the given ByteArray starting at the given index. Consider the first byte to contain the most significant bits of the word (i.e., use big-endian byte ordering).