Method and apparatus for authenticating messages

• US 5,142,577 A
• Filed: 12/17/1990
• Issued: 08/25/1992
• Est. Priority Date: 12/17/1990
• Status: Expired due to Term

• Current Assignee: Pitney Bowes Incorporated (Böwe Systec AG)
• Original Assignee: Pitney Bowes Incorporated (Böwe Systec AG)
• Inventors: Pastor, Jose
• Primary Examiner(s): Swann, Tod R.
• Application Number:
  US07/628,820
• Time in Patent Office: 617 Days
• Field of Search: 380/21, 380/23, 380/28, 380/29, 380/30, 380/51, 380/55, 364/464.02
• US Class Current: 705/62
• CPC Class Codes: G06F 7/725 over elliptic curves
• CPC Class Codes: G07B 17/00733 Cryptography or similar special procedures in a franking system
• CPC Class Codes: G07B 2017/0087 Key distribution
• CPC Class Codes: G07B 2017/00895 Key verification, e.g. by using trusted party
• CPC Class Codes: G07B 2017/00911 Trusted party
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/321 involving a third party or a trusted authority

Abstract

A method and system for authenication of communications. More particularly the subject application discloses a method and apparatus whereby a third party may validate that a communication is an authentic communication from a second party sent with the authorization of a first party. For example, the third party may be a postal service, the second party may be a mailer, and the communication may be a postal indicia showing that a mail piece has been properly franked. The first party and the second party share an encryption key, or a series of keys. The first party also has a second encryption key which the third party has the ability to decrypted. In the subject invention the first party encrypts a key shared with the second party with the first party'"'"'s second key and transmits this to the second party. The second party then uses its copy of the key to encrypt information and appends its encrypted information to the message received from the first party and transmits all this to the third party. The third party may then decrypt the copy of the key encrypted by the first party and use this information to decrypt the information encrypted by the second party. The known technique of eliptical logarithms may be used to provide highly secure encryption of short messages. The second party may be a mailer and the apparatus of the subject invention may include a postage meter which prints the information transmitted to the third party, who may be a postal service, on a mail piece as a postal indicia.

Claims

1. A method for authenticating communications comprising the steps of:

generating;

an encryption/decryption key pair consisting of key E_s and D_s said keys being of a first order selected to provide a predetermined level of security;

a set numbers of {a'"'"'} wherein numbers a'"'"' which are members of set {a'"'"'} are approximately of said first order, and have the property that when encrypted with said key E_s resulting encrypted numbers D_s [a'"'"'] are of a second order substantially less than said first order;

hashing function H for mapping number of said first order onto a third, smaller order; and

,

an encrypting key K_i ;

providing said key E_s, said set {a'"'"'} said hashing function H and said key K_i to a first party;

providing said key K_i to a second party;

providing said key D_s and said hashing function H to a third party;

said first party;

selecting a particular one of said numbers a'"'"';

encrypting said selected number a'"'"' with said key E_s to obtain a particular value E_s [a'"'"'];

operating on said selected number a'"'"' with said hashing function H to obtain a second encrypting key K_j, equal to H(a'"'"');

forming a first level message M1 including said encryption key K_i ;

encrypting said first level message M1 with said second encrypting key K_j ;

forming a second level message M2 including said encrypted first level message K_j [M1 ] and said particular value E_s [a'"'"'];

sending said second level message M2 to said second party;

said second party then;

encrypting information P with said key K_j ;

combining said second level message M2 with said encrypted information K_i [P] to form a third level message M3; and

sending a communication comprising said third level message M3 to said third party;

said third party then;

recovering said particular value E_s [a'"'"'] from said second level message M2 comprised in said third level message M3;

decrypting said particular value E_s [a'"'"'] with said key D_s to obtain said selected number a'"'"';

operating on said selected number a'"'"' with said hashing function H to obtain said second encryption key K_j ;

recovering said encrypted first level message K_j [M1] from said second level message M2 and decrypting said encrypted first level message K_j [M1] with said second encryption key K_j to obtain said first level message M1;

recovering said encrypted information K_i [P] from said third level message M3 and said encryption key K_i from said first level message M1; and

decrypting said encrypted information K_i [P] with said encryption key K_i to obtain said information P;

whereby said third party acquires a basis to believe that said information P is an authentic communication sent by said second party with the authorization of said first party.

2. A method as described in claim 1, wherein said second level message M2 is encrypted with said key K₁ prior to being sent to said second party and is decrypted by said second party.

3. A method described in claim 1, wherein said key K₁ varies as for each transaction between said first and second users and is determined by an initial key K_i (0) and a function F such that K_i (t)=F(K_i (t-1)), where K_i (t) is the key for transaction number t.

4. A method as described in claim 1, wherein said numbers a'"'"' share a recognizable property such that it is hard for an unauthorized person in possession of said key D_s to find values of a'"'"' having said property.

5. A method as described in claim 2, wherein said numbers a'"'"' share a recognizable common property such that it is hard for an unauthorized person in possession of said key D_s to find values of a'"'"' having said property.

6. A method as described in claim 3, wherein said numbers a'"'"' share a recognizable property such that it is hard for an unauthorized person in possession of said key D_s to find values of a'"'"' having said property.

7. A method as described in claims 1, 2, 3, 4, 5 or 6, wherein said first level message M1 is encrypted with an eliptical logarithm technique.

8. A method as described in claim 7, wherein said third level message M3 is incorporated as part of a postal indicia on a mail piece.

9. A method as described in claim 1, 2, 4, 5, or 6, wherein said third level message M3 is incorporated as part of a postal indicia on a mail piece.

10. A system for authenticating postal indicia, comprising:

authorizing apparatus, said authorizing apparatus further comprising;

first storage means for storing one key E_s, D_s, and keys E_s, D_s, being of a first order selected to provide a predetermined level of security;

second storage means for storing;

a set of number {a'"'"'} each number a'"'"' having the property that when encrypted with said key E_s the resulting values E_s [a '"'"'] are of a second order substantially less than said first order;

a hashing function H for mapping number a'"'"' onto numbers of a third smaller order; and

,

an encryption key K_i ;

first data processing means for;

selecting a particular one of said number a'"'"';

encrypting said selected number a'"'"' with said key E_s to obtain a particular value E_s [a'"'"'];

operating on said selected number a'"'"' with said hashing function H to obtain a second encryption key K_j, equal to H(a'"'"');

forming a first level message M1 including said encryption key k_j ;

encrypting said first level message M1 with said second encryption key K_j [M1];

forming a second level message M2 including said encrypted first level message K_j [M1] and said particular value E_s [a'"'"']; and

,

transmission means responsive to said first data processing means for sending said second level message M2;

franking apparatus, for franking a mail piece, said franking apparatus comprising;

first receiving means for receiving said second level message M2

second receiving means for receiving postal information P relating to a mail piece;

accounting means responsive to said second receiving means for accounting for funds expended in franking said mail piece;

encryption means responsive to said accounting means for encrypting said postal information P with said key K_i only if said funds have been accounted for by said accounting means;

second data processing means responsive to said first and second receiving means and to said encryption means for;

inputting said encrypted postal information K_i [P] from said encryption means;

inputting said second level message M2 from said first receiving means

inputting said postal information P from said second receiving means; and

forming a third level message M3 including said second level message M2 and said encrypted postal information K_i [P]; and

,

printing means responsive to said second data processing means for printing an indicia on said mail piece, said second data processing means controlling said printing means to print said indicia including said third level message M3 and said postal information P in plain text; and

,

authenticating apparatus, said authenticating apparatus further comprising;

scanning means for scanning said indicia, upon receipt of said mail piece, to read said third level message M3 and said postal information P form said plain text;

third storage means for securely storing said key D_s ;

fourth storage means for storing said hashing function H;

third data processing means responsive to said third and forth storage means, and said scanning means for;

recovering said particular value E_s [a'"'"'] from said third level message M3;

decrypting said particular value E_s [a'"'"'] with said key D_s to obtain said selected number a'"'"';

operating on said selected number a'"'"' with said hashing function H to obtain H(a'"'"') equal to said second encryption key K_j ;

recovering said encrypted first level message K_j [M1] from said third level message M3;

decrypting said encrypted first level message K_j [M1] with said key K_j to obtain said first level message M1;

recovering said encryption key K_i from said first level message M1;

decrypting said encrypted postal information K_i [P] to obtain said information P,

inputting said information P as scanned from said plane text and comparing said information P, as input, with said information P, as decrypted, to authenticate said indicia.

11. A system as described in claim 10, wherein said second level message M2 is encrypted with said key K_i prior to being sent to said franking apparatus and is decrypted by said franking apparatus.

12. A system as described in claim 10, wherein said key K_i varies as for each transaction between said first and second users and is determined by an initial key K_i (0) and a function F such that K_i (t)=F(K_i (t-1)), where K_i (t) is the key for transaction number t.

13. A system as described in claim 10, wherein said numbers a'"'"' share a recognizable property such that it is hard for an unauthorized person in possession of said key D_s to find values of a'"'"' having said property.

14. A system as described in claim 11, wherein said numbers a'"'"' share a recognizable property such that it is hard for an unauthorized person in possession of said key D_s to find values of a'"'"' having said property.

15. A system as described in claim 12, wherein said numbers a'"'"' share a recognizable property such that it is hard for an unauthorized person in possession of said key D_s to find values of a'"'"' having said property.

16. A system as described in claims 10, 11, 12, 13, 14 or 15, wherein said numbers a'"'"' share a recognizable property such that it is hard for an unauthorized person in possession of said key D_s to find values of a'"'"' having said property.

17. A method as described in claim 16, wherein said third level message M3 is incorporated as part of a postal indicia on a mail piece.

18. A method as described in claims 10, 11, 12, 13, 14 or 15, wherein said third level message M3 is incorporated as part of a postal indicia on a mail piece.

19. An apparatus for providing an authenticating message, comprising:

first storage means for storing one key E_s of an encrypting/decryption key pair E_s,D_s, said keys E_s, D_s being of a first order selected to provide a predetermined level of security;

second storage means for storing;

a set of number {a'"'"'} each number a'"'"' having the property that when encrypted with said key E_s the resulting values E_s [a'"'"'] are of a second order substantially less than said first order;

a hashing function H for mapping number a'"'"' onto number of third smaller order; and

,

an encryption key K_i ;

data processing means for;

selecting a particular one of said number a'"'"';

encrypting said selected number a'"'"' with said key E_s to obtain a particular value E_s [a'"'"'];

operating on said selected number a'"'"' with said hashing function H to obtain a second encryption key K_j, equal to H(a'"'"');

forming a first level message M1 including said encryption key K_i ;

encrypting said first level message M1 with said second encryption key K_j to obtain K_j [M1];

forming a second level message M2 including said encrypted first level message K_j [M1] and said particular value E_s [a'"'"']; and

,

transmission means responsive to said data processing means for sending said second level message M2.

20. Franking apparatus for franking a mail piece, said franking apparatus comprising:

first receiving means for receiving a message M2;

second receiving means for receiving postal information P relating to a mail piece;

accounting means responsive to said second receiving means for accounting for funds expended in franking said mail piece;

encryption means responsive to said accounting means for encrypting said postal information P with a key K_i only if said funds have been accounted for by said accounting means;

data processing means responsive to said first and second receiving means and to said encryption means for;

inputting said encrypted postal information K_i [P] from said encrypting means;

inputting said second level message M2 from said first receiving means

inputting said postal information P from said second receiving means; and

forming a message M3 including said message M2 and said encrypted postal information K_i [P]; and

,

printing means responsive to said data processing means for printing an indicia on said mail piece, said data processing means controlling said printing means to print said indicia including said third level message M3 and said postal information P in plain text.

21. Authenticating apparatus for authenticating an indicia for a mail piece comprising:

scanning means for scanning said indicia, upon receipt of said mail piece, to read a message M3 and postal information P from plain text in said indicia;

first storage means for securely storing a key D_s ;

second storage means for storing a hashing function H;

data processing means responsive to said first and second storage means, and said scanning means, for;

recovering particular value E_s [a'"'"'] from said message M3;

decrypting said particular value E_s [a'"'"'] with said key D_s to obtain a'"'"';

operating on a'"'"' with said hashing function H to obtain H(a'"'"') equal to a second encryption key K_j ;

recovering a encrypted message K_j [M1] from said message M3;

decrypting said encrypted message K_j [M1] with said key K_j to obtain message M1;

recovering an encryption key K_i from said first level message M1;

recovering encrypted postal information K_i [P] from said third level message M3 and decrypting said said encrypted postal information K_i [P] to obtain information P;

inputting said information P as scanned from said plain text and comparing said information P, as input, with said information P, as decrypted, to authenticate said indicia.