Method for publishing certification information certified by a plurality of authorities and apparatus and portable data storage media used to practice said method
AssigneePitney Bowes Inc.
InventorRobert A. Cordery
Life of this patent
Estimating the term…
Abstract
A method for certifying the public key of a user wishing to communicate using a public key encryption system by a plurality of certifying authorities. A plurality of certifying stations and a user station exchange information and the user station derives a public key from the exchanged information. The certifying stations also publish related information and their public keys. A third party can derive the public key corresponding to the user's private key by operating on the published information with a summation of the certifying station keys.
Claims20
A method for controlling, and distributing information among, a plurality of stations, one of said stations being a user station operated by a user U to generate a private encryption key KeyU and others of said stations being certifying stations operated by a plurality of certifying authorities for publishing related information, so that a corresponding public key KeyU*P of said user U can be determined by a party communicating with said user U from said published related information with assurance that said public key KeyU*P has been certified by each of said plurality of certifying authorities CA, said method comprising the steps of:
- a) defining a finite group [P] with a binary operation [+] and publishing a particular point P in said group;
- b) defining and publishing a binary operation K*p, where K is an integer and p is a point in said group, such that K*p, is a point in said group computed by applying said operation [+] to K copies of said point p, and computation of K from knowledge of the definition of said group [P], said point p, and K*p is hard;
- c) controlling one of said certifying stations to publish a certificate CERTU for said user U, wherein;
- CERTU=(rU+sum(rCAi))*P;
- and wherein
- rU is a random integer known only to said user U and sum(rCAi) is a sum of a plurality of random integers rCAi, an ith one of said certifying stations generating an ith one of said random integers rCAi;
- d) controlling one of said certifying stations to publish a message M;
- e) controlling said certifying stations to generate a plurality of integers Ii, and send at least sum(Ii) to said user station, wherein;
- Ii=rCAi+H(M)KeyCAi;
- and wherein
- H(M) is an integer derived from said message M in accordance with a publicly known algorithm H, and rCAi is one of said random integers generated by, and KeyCAi is a private key of, an ith one of said certifying authorities CA;
- f) publishing a public key KeyCAi*P for each of said certifying authorities CA;
- and
- g) controlling said user station to compute a private key KeyU, wherein KeyU=rU+sum(Ii)=rU+sum(rCAi)+sum(H(M)KeyCAi);
- whereby
- h) said communicating party can compute said user's public key KeyU*P as
- KeyU*P=CERTU+H(M)*sum[+](KeyCAi*P)=(rU+sum(rCAi))*P+sum(H(M)KeyCAi)*P
- from knowledge of H, M, [P], said public keys KeyCAi*P, and CERTU.
A method for certification of a public key of a user by a plurality of certifying authorities, each of said certifying authorities having a published public key and a corresponding private key, said method comprising the steps of:
- a) said certifying authorities providing said user with integers, each of said integers being a first function of one of said private keys for a corresponding one of said authorities;
- b) said user computing a private key as a second function of said integers;
- and
- c) at least one of said certifying authorities publishing related information;
- wherein
- d) said first function, said second function and said published related information are chosen so that a party communicating with said user can compute said user public key, corresponding to said computed private key, by operating on said published related information with a summation of said published public keys of said authorities.
A method for controlling and distributing information among a plurality of certifying stations used by a plurality of certifying authorities for publishing related information so that a public key KeyU of a user U can be determined by a party communicating with said user U from said published related information with assurance that said public key KeyU has been certified by each of said plurality of certifying authorities CA, said method comprising the steps of:
- a) defining a finite group [P] with a binary operation [+] and publishing a particular point P in said group;
- b) defining and publishing a binary operation K*p, where K is an integer and p is a point in said group, such that K*p, is a point in said group computed by applying said operation [+] to K copies of said point p, and computation of K from knowledge of the definition of said group [P], said point p, and K*p is hard;
- c) for each of said authorities storing in an corresponding one of said certifying stations a private encryption key Keyi, where Keyi is a key for an ith one of said certifying authorities;
- d) publishing a corresponding public encryption key Keyi*P for each one of said certifying authorities;
- e) controlling one of said certifying stations to publish a certificate CERTU for said user U, wherein;
- CERTU=(rU+sum(rCAi))*P;
- and wherein
- rU is a random integer known only to said user U and sum(rCAi) is a sum of a plurality of random integers rCAi, an ith one of said certifying stations generating an ith one of said random integers rCAi;
- f) controlling said one of said certifying stations to publish a message M;
- and
- g) controlling said certifying stations to send to said user station a at least the sum of a plurality of integers Ii, wherein;
- Ii=rCAi+H(M)KeyCAi;
- and wherein
- H(M) is an integer derived from said message M in accordance with a publicly known algorithm H, and KeyCAi is a private key of, an ith one of said certifying authorities CA;
- whereby
- h) said user station can compute a private key KeyU, wherein
- KeyU=rU+sum(Ii)=rU+sum(rCAi)+sum(H(M)KeyCAi);
- and whereby
- i) said communicating party can compute said user's public key KeyU*P as
- KeyU*P=CERTU[+]H(M)*sum[+](KeyCAi*P)=(rU+sum(rCAi))*P[+]sum(H(M)KeyCAi)*P
- from knowledge of H, M, [P], said public keys KeyCAi*P, and CERTU.
Data processing apparatus including a programmable processor programmed to control said apparatus as one of a plurality of certifying stations used by a plurality of certifying authorities for distributing information among said certifying stations and publishing related information, so that a public key KeyU*P of a user U can be determined by a party communicating with said user U from said published related information with assurance that said public key KeyU*P of said user U has been certified by each of said plurality of certifying authorities, each of said certifying stations storing a private encryption key KeyCAi, where KeyCAi is a key for an ith one of said certifying authorities and a corresponding public encryption key KeyCAi*P for each one of said certifying authorities CA being publicly known, said processor being programmed control said apparatus to:
- a) communicate with and receive from said user station and other certifying stations a point in said group [P], either as a single point or as one or more points to be summed to form said received point, said received point being equal to:
- (rU+sum(rCAi))*P;
- wherein
- rU is a random integer known only to said user U, P is a particular, published point in [P] and sum(rCAi) is a sum of a plurality of random integers rCAi, an ith one of said other certifying stations generating an ith one of said random integers rCAi;
- b) generate a final random number rCAF;
- c) controlling said one of said certifying stations to publish a certificate CERTU for said user U, wherein;
- CERTU=(rU+sum(rCAi)+rCAF)*P
- d) controlling said one of said certifying stations to publish a message M;
- wherein
- e) said certifying stations, including said one station, send to said user station a plurality of integers Ii, wherein;
- Ii=rCAi+H(M)KeyCAi;
- and wherein
- H(M) is an integer derived from said message M in accordance with a publicly known algorithm H, and rCAi is one of said random integers rCAi generated by, and KeyCAi is a private key of an ith one of said certifying authorities;
- whereby
- f) said user station can compute a private key KeyU, wherein
- KeyU=rU+sum(Ii)=rU+sum(rCAi)+sum(H(M)KeyCAi);
- and whereby
- g) said communicating party can compute said user's public key KeyU*P as
- KeyU*P=CERTU[+]H(M)*sum[+](KeyCAi*P)=(rU+sum(rCAi))*P[+]sum(H(M)KeyCAi)*P
- from knowledge of H, M, [P], said public keys KeyCAi*P, and CERTU.
Dependencies are inferred from the claim text.