Method for certifying public keys used to sign postal indicia and indicia so signed
AssigneePitney Bowes Inc.
InventorsRobert A. Cordery, Leon A Pintsov, Scott A Vanstone
Life of this patent
Estimating the term…
Abstract
A method for certifying the public key of a digital postage meter using a public key encryption system by a certifying authority. A certifying station and a user station, or a digital postage meter, exchange information and the user station and downloads, or the meter derives, a public key from the exchanged information. The certifying station also publishes related information and its public key. A third party can derive the public key corresponding to the meter's private key by operating on the published information with the certifying station public key.
Claims20
A method for controlling, and distributing information between a digital postage meter and a certifying station operated by a certifying authority CA for publishing information, so that a public key KeyDM*P of said digital postage meter can be determined by a party seeking to verify indicia printed by said digital postage meter from said published information with assurance that said public key KeyDM*P has been certified by said certifying authority CA, said method comprising the steps of:
- a) defining and publishing 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;
- c) controlling a certifying station to publish a certificate OMCDM for said digital postage meter, wherein;
- OMCDM=(rDM+rCA)* P;
- and wherein
- rDM is a random integer generated by said digital postage meter and rCA is a random integer generated by said certifying station;
- d) controlling said certifying station to publish a message M;
- e) controlling said certifying station to generate an integer IDM, and send said integer to said digital postage meter, wherein;
- IDM=rCA+H(M)KeyCA;
- and wherein
- H(M) is an integer derived from said message M in accordance with a publicly known algorithm H and KeyCA is a private key of said certifying authority CA;
- f) publishing a public key KeyCA*P for said certifying authority CA;
- and
- g) controlling said digital postage meter to compute a private key KeyDM,
- KeyDM=rDM+IDM=rDM+rCA+H(M)KeyCA;
- and
- h) controlling said digital postage meter to print an indicium and digitally sign said indicium with said key KeyDM;
- whereby
- i) said verifying party can compute said user's public key KeyDM*P as
- KeyDM*P=OMCDM+H(M)KeyCA*P=(rDM+rCA)*P+H(M)KeyCA*P
- from knowledge of H, M, [P], said public key KeyCA*P, and OMCDM.
A method for controlling a digital postage meter to print indicia signed with a private key KeyDM based upon a published a finite group [P] with a binary operation [+] and a published particular point P in said group and a published 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, so that a public key KeyDM*P of said digital postage meter can be determined by a party seeking to verify indicia printed by said digital postage meter from published information with assurance that said public key KeyDM*P has been certified by a certifying authority CA, said method comprising the steps of:
- a) controlling said digital postage meter to generate a random number rDM and send a point rDM*P to a certifying station;
- b) controlling said digital postage meter to receive a certificate OMCDM from a certifying station operated by said certifying authority CA, wherein;
- OMCDM=(rDM+rCA)*P;
- and wherein
- rDM is a random integer generated by said digital postage meter and rCA is a random integer generated by said certifying station;
- c) controlling said digital postage meter to receive an integer IDM from said certifying station, wherein;
- IDM=rCA+H(M)KeyCA;
- and wherein
- M is a message published by said certifying station and H(M) is an integer derived from said message M in accordance with a publicly known algorithm H and KeyCA is a private key of said certifying authority CA;
- d) controlling said digital postage meter to compute a private key KeyDM,
- KeyDM=rDM+IDM=rDM+rCA+H(M)KeyCA;
- and
- e) controlling said digital postage meter to print an indicium and digitally sign said indicium with said key KeyDM;
- whereby
- f) said verifying party can compute said digital postage meter public key KeyDM*P as
- KeyDM*P=OMCDM+H(M)KeyCA=(rDM+rCA)*P+H(M)KeyCA*P
- from knowledge of H, M, [P], said public key KeyCA*P, and OMCDM.
A method for controlling a certifying station operated by a certifying authority CA to publish information relating to a digital postage meter for printing indicia signed with a private key KeyDM based upon a published a finite group [P] with a binary operation [+] and a published particular point P in said group and a published 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, so that a public key KeyDM*P of said digital postage meter can be determined by a party seeking to verify indicia printed by said digital postage meter from said published information with assurance that said public key KeyDM*P has been certified by a certifying authority CA, said method comprising the steps of:
- a) controlling said certifying station to receive a point rDM*P from a user station, where rDM is a random number generated by said user station;
- b) controlling said certifying station to generate and send to said digital postage meter a certificate OMCDM, wherein;
- OMCDM=(rDM+rCA)*P;
- and wherein
- rCA is a random integer generated by said certifying station;
- c) controlling said certifying station to generate and send to said user station an integer IDM, wherein;
- IDM=rCA+H(M)KeyCA;
- and wherein
- M is a message published by said certifying station and H(M) is an integer derived from said message M in accordance with a publicly known algorithm H and KeyCA is a private key of said certifying authority CA;
- whereby
- d) said digital postage meter can compute said private key KeyDM,
- KeyDM=rDM+IDM=rDM+rCA+H(M)KeyCA;
- and
- and digitally sign said indicium with said key KeyDM;
- and whereby
- e) said verifying party can compute said digital postage meter public key KeyDM*P as
- KeyDM*P=OMCDM+H(M)KeyCA*P=(rDM+rCA)*P+H(M)KeyCA*P
- from knowledge of H, M, [P], said public key KeyCA*P, and CERTDM.
A method for controlling, and distributing information among a user station, a digital postage meter and a certifying station operated by a certifying authority CA for publishing information, so that a public key Key50*P of said digital postage meter can be determined by a party seeking to verify indicia printed by said digital postage meter from said published information with assurance that said public key Key50*P has been certified by said certifying authority CA, said method comprising the steps of:
- a) defining and publishing 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;
- c) controlling a certifying station to publish a certificate OMC50 for said digital postage meter, wherein;
- OMC50=(r50+rCA)*P;
- and wherein
- r50 is a random integer generated by said digital postage meter and rCA is a random integer generated by said certifying station;
- d) controlling said certifying station to publish a message M;
- e) controlling said certifying station to generate an integer I50, and send said integer to said user station, wherein;
- I50=rCA+H(M)KeyCA;
- and wherein
- H(M) is an integer derived from said message M in accordance with a publicly known algorithm H and KeyCA is a private key of said certifying authority CA;
- f) publishing a public key KeyCA*P for said certifying authority CA;
- and
- g) controlling said user station to compute a private key Key50,
- Key50=r50+I50=r50+rCA+H(M)KeyCA;
- and
- h) transmitting said key Key50 to said postage meter;
- whereby
- said digital postage meter can print an indicium and digitally sign said indicium with said key Key50;
- and whereby
- i) said verifying party can compute said user's public key Key50*P as
- Key50*P=OMC50+H(M)KeyCA*P=(r50+rCA)*P+H(M)KeyCA*P
- from knowledge of H, M, [P], said public key KeyCA*P, and OMC50.
A method for controlling a certifying station operated by a certifying authority CA to publish information relating to a digital postage meter for printing indicia signed with a private key KeyDM based upon a published a finite group [P] with a binary operation [+] and a published particular point P in said group and a published 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, so that a public key KeyDM*P of said digital postage meter can be determined by a party seeking to verify indicia printed by said digital postage meter from said published information with assurance that said public key KeyDM*P has been certified by a certifying authority CA, said method comprising the steps of:
- a) controlling said certifying station to receive a point rDM*P from a user station, where rDM is a random number generated by said user station;
- b) controlling said certifying station to generate and send to said user station a certificate OMC50, wherein;
- OMC50=(r50+rCA)*P;
- and wherein
- rCA is a random integer generated by said certifying station;
- c) controlling said certifying station to generate and send to said user station an integer I50, wherein;
- I50=rCA+H(M)KeyCA;
- and wherein
- M is a message published by said certifying station and H(M) is an integer derived from said message M in accordance with a publicly known algorithm H and KeyCA is a private key of said certifying authority CA;
- whereby
- d) said user station can compute said private key KeyDM,
- Key50=r50+I50=r50+rCA+H(M)KeyCA;
- and
- and transmit said key Key50 to said digital postage meter;
- whereby
- e) said digital postage meter can digitally sign said indicium with said key Key50;
- and whereby
- f) said verifying party can compute said digital postage meter public key Key50*P as
- Key50*P=OMC50+H(M)KeyCA*P=(rDM+rCA)*P+H(M)KeyCA*P
- from knowledge of H, M, [P], said public key KeyCA*P, and CERTDM.
A method for determining a public key KeyDM*P of a digital postage meter with assurance that said key KeyDM has been certified by a group of one or more certifying authorities CA, said method comprising the steps of:
- a) scanning an indicium produced by said postage meter to obtain a certificate OMCDM for said postage meter, wherein;
- OMCDM=(rDM+sum(rCAi))*P;
- and wherein
- rDM is a random integer known only to a party generating said key KeyDM 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;
- b) scanning said indicium produced by said postage meter to obtain a message M said message M being published by a certifying station operated by one of said certifying authorities CA;
- c) computing a hash H(M) of said message M in accordance with a predetermined hashing function H;
- d) obtaining at least one public keyCAi*P corresponding to said one or more certifying authorities CA, an ith one of said authorities having an ith one of said keys KeyCAi;
- and
- e) computing 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;
- wherein
- f) a binary operation [+] is defined on a finite group [P] having a published particular point P;
- and
- g) K*p, is a second binary operation defined on said group [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.
A method of digitally signing a postal indicium comprising the steps of:
- a) generating a message m, said message m including indicia data;
- b) generating a digital signature with message recovery for said message m;
- and
- c) incorporating said digital signature into said indicium;
- wherein
- d) said generating step further comprises the substeps of:
- d1) generating a random integer rS, rS<n, where n is the order of a group [P] defined on an elliptic curve;
- d2) generating a integer K,
- K=K(rS*P)
- where K(p) is a mapping of points in [P] onto the integers, and P is a particular published point in [P];
- d3) generating e,
- e=SKEK(m)
- where SKEK is a symmetric key encryption algorithm using key K;
- d4) generating H(M), where H is a hashing function and M is a message which can be recovered from said indicium;
- d5) generating s=KeyDMH(M)+rS, where KeyDM is the private key of a postage meter which produced said indicium;
- and
- d6) setting said digital signature for said message m equal to the pair (s,e).
A method of verifying a digital signature of a postal indicium comprising the steps of:
- a) recovering a message m from a digital signature of a postal indicium;
- and
- b) accepting said signature as valid if said message m is internally consistent;
- wherein
- c) said recovering step further comprises the substeps of:
- c1) recovering a public key KeyDM*P for a postage meter which produced said indicium;
- c2) obtaining the signature (s,e) of said indicium, where s=KeyDMH(M)+rS and e=SKEK(m), where SKEK is a symetric key encryption algorithm using key K, m is indicia data, and M is a message recoverable from said indicium;
- c3) obtaining M from said indicium;
- c4) generating
- s*P[−]H(M)KeyDM*P=H(M)KeyDM*P[+]rS*P[−]H(M)KeyDM*P=rS*P
- where [−] is the inverse of [+];
- c5) generating
- K=K(rS*P)
- where K(p) is a mapping of points in [P] onto the integers, and P is a particular published point in [P];
- c6) generating
- m=SKE−1K(e)
- where SKE−1K is the inverse of SKEK.
Dependencies are inferred from the claim text.