Cryptography – Key management – Key distribution
Reexamination Certificate
1998-05-08
2001-02-27
Swann, Tod R. (Department: 2767)
Cryptography
Key management
Key distribution
C380S030000, C380S046000, C713S176000
Reexamination Certificate
active
06195433
ABSTRACT:
The present invention relates to secure digital data communication stems and, in particular, to a method for ensuring a particular random cryptographic private key value has adequate randomness properties (considered by itself) and a method for validating cryptographic private keys in such systems.
BACKGROUND OF THE INVENTION
Secure data communication systems are used to transfer information between a pair of correspondents. At least part of the information that is exchanged is encoded (enciphered) by a predetermined mathematical operation by the sender. The recipient may then perform a complimentary mathematical operation to unencode (decipher) the information. The enciphering and deciphering of information is normally performed utilizing a cryptographic key determined by the particular graphic scheme implemented between the correspondents. Consequently, there are certain parameters that must be known beforehand between the correspondents. For example, in public key or symmetric key systems, various schemes and protocols have been devised to validate the sender's public key, the identity of the sender and such like.
In all of these schemes, it is assumed that the cryptographic keys, be it the private key, the public key or the symmetric key, is derived and valid as specified in the protocol scheme. Problems, however, will arise if these parameters are either bogus or defective in some way.
Digital signature methods have been derived to prove to a id part that a message was signed by the actual originator. Practical public key signature schemes are based on the difficulty of solving certain mathematical problems to make alteration or forgery by unauthorized parties difficult. Most of the proposed schemes have been based either on the problem of factoring large integers or in the difficulty of computing discrete logarithms over finite fields (or over finite grog in general). For example, the RSA system depends on the difficulty of factoring large integers.
A digital signature of a message is a number which is dependent on some secret known only to the signor, and additionally, on the content of the message being signed. Signatures must be verifiable. If a dispute arises as to whether a party signed (caused by either a signor trying to repudiate a signature it did ate or a fraudulent claimant), an unbiased third party should be able to resolve the matter equitably without requiring access to the signor's secret information, i.e., private key.
The ElGamal signature scheme is a randomized signatures mechanism. In order to generate keys for the ElGamal signature scheme, each entity creates a public key and corresponding private key. Thus, each entity generates a large random prime p and a generator &agr; of the multiplicative group Z*
p
. Next, the entities select a random integer a such that 1≦&agr;≦p−2 and computes the value y=&agr;
3
modp. Thus, for example, entity A's public key is (y) along with the system parameters p and &agr;, while A's private key is &agr;.
The security of the above system is generally based on the difficulty of the discrete log problem. The RSA cryptosystem uses a modulus of the form n=pq where p and q are distinct odd primes. The primes p and q must be of sufficient size that factorization of the product is beyond computational reach. Moreover, there should be random primes in the sense that they are chosen as a function of a random input through a process defining a pool of candidates of sufficient cardinality that an exhaustive attack is infeasible. In practice, the resulting primes must also be of a predetermined bit length to meet systems specifications. Without these constraints on the selection of the primes p and q, the RSA system is vulnerable to a so-called “first person attack”.
In elliptic curve cryptosystems, the elliptic curve private key is a statistically unique and unpredictable value selected between 1 and n−1 where n is the prime order of G, the generating point of the large subgroup specified by the associated EC domain parameters.
In a possible “first person attack”, entity A the attacker, creates a private key that is weak and uses it to obtain services and such like. Later, the dishonest entity repudiates or disavows its private key as being weak and then claims that it did not request these services. That is, party A alleges it inadvertently used a weak private key resulting in a public key that was easily attacked, allowing a third party to derive its private key and thus, was able to impersonate the original entity A For example, where the key is generated using a seeded hash to produce a 161 bit private EC key by generating 2
64
, party A may select the one (expected) key with a high order 64 bits of 0s. The first party goes to a judge with a repudiation request and points out that an adversary could attack remaining 97 bits in feasible time. He therefore repudiates his key as it has already been shown that 97 bit keys can be broken. Clearly, in high security applications, it is desirable to avoid the fit person attack.
One way to address this possible concern about first party repudiation is simply to deny all fat party repudiation requests. However, this may result in a problem if a key is generated that actually is weak. What is needed is the ability of the owner to be assured that his particular private key is not weak. In some applications it may not be sufficient to claim that generation of weak key pairs is statistically improbable. The owner wants to be assured that his specific key has no properties that might make it weak, as no matter what value it might be, he is not able to later repudiate it.
The cryptographic strength of the key depends to a large extent on the random distribution of bits in the binary representation used as the key. Thus, although the key may be generated by a pseudorandom number generator and is therefore random, it may be weak if the digits are distributed in a recognizable pattern or grouped to provide a shorter key.
Thus, it is desirable to implement an ECC ElGamal type scheme in which the probability of private key repudiation is minimized.
SUMMARY OF THE INVENTION
In general terms, the present invention provides a method of generating a private key for use in a public key data communication system implemented between a pair of correspondents, said method comprising the steps of generating a random number for use as a private key, testing said number against a predetermined set of criteria to determine the statistical randomness of said numbers and utilizing said random number upon satisfying said criteria.
REFERENCES:
patent: 5016274 (1991-05-01), Micali et al.
patent: 5161244 (1992-11-01), Maurer
patent: 5299262 (1994-03-01), Brickell et al.
patent: 5347581 (1994-09-01), Naccache et al.
patent: 5442707 (1995-08-01), Miyaji et al.
patent: 5475763 (1995-12-01), Kaufman et al.
patent: 5625695 (1997-04-01), M'Raihi et al.
“Applied Cryptography”, second edition, Bruce Schneier, John Wiley & Sons, Inc., U.S.A., pp. 169-187, p. 173.
“Cipher Systems”, Henry Beker & Fred Piper, Northwood Books, London, pp. 170-174.
“A Universal Statistical Test for Random Bit Generators”, U.M. Maurer, Journal of Cryptology, vol. 5, No. 2, 1992, pp. 89-105, pp. 91-92.
PCT International Search Report mailed Aug. 25, 1999 (2 pages).
Johnson Donald B.
Vanstone Scott A.
Certicom Corp.
Darrow Justin T.
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
Swann Tod R.
LandOfFree
Private key validity and validation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Private key validity and validation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Private key validity and validation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2615098