Electrical computers and digital processing systems: support – Multiple computer communication using cryptography – Security kernel or utility
Reexamination Certificate
1999-03-30
2004-03-09
Jean, Frantz B. (Department: 2132)
Electrical computers and digital processing systems: support
Multiple computer communication using cryptography
Security kernel or utility
C705S060000, C705S061000, C705S040000, C705S410000, C713S157000, C713S171000, C380S030000, C380S055000, C380S282000, C380S286000
Reexamination Certificate
active
06704867
ABSTRACT:
BACKGROUND OF THE INVENTION
The subject invention relates to encryption of information using public key encryption technology. (By “public key” encryption herein is meant encryption technology which uses pairs of keys: a public key, which is published or made publicly known; and a corresponding private key, kept secret by a user.) More particularly it relates to the certification of public keys by a plurality of certifying authorities.
Using public key encryption anyone can encrypt a message with a public key and have assurance that only a user (i.e. a party having the corresponding private key) can decrypt it, and a user can “sign” a message using a private key and anyone can use the corresponding public key to ascertain if the message originated with the user. (A message is “signed” by deriving encrypted information in a known manner from the message.)
Because public keys can be distributed so widely, it will in general be the case that persons communicating with users of public key systems will not be in direct contact with the users and will not be able to directly determine the identity and/or characteristics of the putative users of a public key system. For example a vendor who receives a purchase order signed by the user of a public key which is purportedly that of an authorized agent of the buyer may need to know, but have no way of directly determining, the actual authority of the user. Similarly proof of payment systems, in particular postage meters, which generate indicia encrypted using public key systems as proof of payment have recently been developed by the assignee of the present application and others; and, given the hundreds of thousands of postage meters in service, it is clear that the postal services will face a severe problem in assuring that indicia purportedly generated by a meter corresponding to a particular public key is in fact generated by an authorized postage meter.
To overcome the difficulties inherent in authenticating public keys numerous schemes for issuing certificates for public keys have been proposed. In such schemes, a trusted third party (hereinafter sometimes a “certifying authority”) provides parties who wish to communicate with a user with a certificate containing the user's public key, the certificate serving to evidence the third party's assurances as to the identity or characteristics of the user. In the simplest case such certificates are no more than entries in a directory delivered through a secure channel. More generally the certifying authority will use an encryption technology to deliver the certificate.
In U.S. Pat. No. 4,853,961; for: “Reliable Document Authentication System”; to: Pastor, a public key for a postage meter is encrypted with a third party's private key and included in the meter indicia. The postal service uses the third party's public key to recover the meter public key and decrypt the encrypted message which serves to validate the indicia.
In U.S. Pat. No. 5,661,803; for: “Method of Token Verification in a Key Management System”; to: Cordery et al., a method of token verification in a key management system is disclosed.
In U.S. Pat. No. 5,680,456; for: “Method of Manufacturing Generic Meters in a Key Management System”; to: Baker et al., a method for manufacturing transaction evidencing devices such as postage meters includes the steps of generating a master key in a logical security domain of a key management system and installing the master key in a postage meter.
In U.S. Pat. No. 5,742,682; for: “Method of Manufacturing Secure Boxes in a Key Management System”; to: Baker et al., a method of manufacturing a secure box in a key management system is taught.
In U.S. Pat. No. 5,805,701; for: “Enhanced Encryption Control System for a Mail Processing System Having Data Center Verification”; to: Ryan, Jr., a key control system comprising generation of a first set of master keys and assigning the keys to a corresponding plurality of postage meters is taught.
In U.S. application Ser. No. 08/133,416; by: Kim et al.; filed Oct. 8, 1993, a key control system comprising generation of a first set of master keys and assigning the keys to a corresponding plurality of postage meters is taught. Keys may be changed by entry of a second key via encryption with a first key.
In U.S. application Ser. No. 08/772,739; by: Cordery; filed Dec. 23, 1996, a method for controlling keys used in the verification of encoded information generated by a transaction evidencing device and printed on a document is taught.
While the above methods are successful in achieving their intended purpose they are disadvantageous in that they are computationally complex, may produce certificates which are large and inflexible, and may require special hardware.
The following references contain information useful to a general understanding of elliptic curve encryption and certification of public keys.
Secure Hash Standard—FIPS PUB 180-1,” Apr. 17, 1995.
Digital Signature Standard—FIPS PUB 186,” May 19, 1994 and Change 1, Dec. 30, 1996.
ANSI X9.62, Elliptic Curve Digital Signature Algorithm Standard (ECDSA), Working Draft, Jan. 15, 1997.
ISO/IEC 9594-8 (1995). Information Technology—Open Systems Interconnection—The Directory: Authentication Framework.”
PKCS #10: Certification Request Syntax Standard, An RSA Laboratories Technical Note,” Version 1.0, December 1993.
Another method of key certification based upon elliptic curve public key encryption technology has been developed by the Certicom Corporation. (The use of elliptic curve encryption technology is known and a more detailed description of its use, beyond what is given below in the context of certification of public keys, is not required for an understanding of the subject invention.)
Elliptic curve encryption is an example of a cryptographic algorithm based on application of an binary additive operator to points in a finite group. In elliptic curve encryption a finite group of points [P] of order n is defined on an elliptic curve. A binary additive operator [+] (hereinafter sometimes “point addition”) is defined on the group [P] such that P[+]P′ is a point in [P]. A more detailed, graphical description of point addition is shown in FIG.
1
. As is known to those skilled in the cryptographic art, disjoint curve
10
has the general form y
2
=x
3
+ax+b defined over the finite Galois field GF(p
m
) where p is a prime number other than 2 and m is an integer. Over the Galois field GF(2
m
) the curve has the form y
2
+xy=x
3
+ax+b. It can be shown that groups of discrete points [P] of order n can be defined on curve
10
, where n is preferably a number on the order of at least 50 decimal digits in order to provide sufficient security for encrypted information.
As is seen in
FIG. 1
curve
10
is symmetric about the x axis so that for any point (x,y) on curve
10
its reflection around the x axis R(x,y)=(x,−y) is also on curve
10
.
For two points P,P′ in [P] it can be show that there exists a unique point R(P[+]P′) which is a third point common to straight line
12
defined by P and P′ and curve
10
. P[+]P′ is defined as R(R(P[+]P′)).
FIG. 2
shows the special case for computation of P[+]P. Straight line
14
is defined as tangent to the closed portion of curve
10
and intersecting point P, and R(P[+]P) is defined as the second point common to line
14
and curve
10
.
A second operation K*P (herein after sometimes “point multiplication”) is defined as the application of [+] to K copies of a point P.
FIG. 3
geometrically illustrates computation of 5*P by successive computation of the points P[+]P=2*P, 2*P[+]2*P=4*P, 4*P[+]P=5*P. Point multiplication is the basic operation underlying elliptic curve encryption and has the property that computation of K from kno
Arani Taghi T.
Bitney Bowes, Inc.
Chaclas Angelo N.
Jean Frantz B.
Malandra, Jr. Charles R.
LandOfFree
Method for publishing certification information... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for publishing certification information..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for publishing certification information... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3286452