System and method for guaranteeing software integrity via combined hardware and software authentication

• US 7,240,200 B2
• Filed: 09/26/2002
• Issued: 07/03/2007
• Est. Priority Date: 09/26/2002
• Status: Expired due to Fees

• Current Assignee: Atreus Labs LLC
• Original Assignee: International Business Machines Corporation
• Inventors: Lotspiech, Jeffrey Bruce
• Primary Examiner(s): Barron, Jr.; Gilberto
• Assistant Examiner(s): Sandoval; Kristin D.
• Application Number:
  US10/259,542
• Publication Number:
  US 20040064695A1
• Time in Patent Office: 1,741 Days
• Field of Search: None
• US Class Current: 713/168
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders
• CPC Class Codes: H04L 2209/127 Trusted platform modules [TPM]
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 2209/603 Digital right managament [DRM]
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/3249 using RSA or related signature schemes, e.g. Rabin scheme

Abstract

A system, method, and computer program product enabling individual user devices to authenticate and validate a digital message sent by a distribution center, without requiring transmissions to the distribution center. The center transmits the message with an appended modulus that is the product of two specially selected primes. The transmission also includes an appended authentication value that is based on an original message hash value, a new message hash value, and the modulus. The new message hash value is designed to be the center'"'"'s public RSA key; a corresponding private RSA key is also computed. Individual user devices combine a digital signet, a public modulus, preferably unique hardware-based numbers, and an original message hash to compute a unique integrity value K. Subsequent messages are similarly processed to determine new integrity values K′, which equal K if and only if new messages originated from the center and have not been corrupted.

Claims

1. A system for guaranteeing message integrity, comprising:

a distribution center that transmits a transmission including a message and appended values; and

a user device that receives said transmission and computes an integrity value K′

that depends on said transmission and at least one stored value, where K′

selectively enables successful further processing of said message if and only if a computed hash value h matches a correct hash value h₁, guaranteeing the integrity of said message,

wherein said appended values include a modulus pq and an authentication value a tat is an encrypted version of an original hash value h₀, said modulus pq, and a private RSA key z, where s=h₀^z mod pq,

wherein said modulus pq is a product of two prime numbers p and q, neither of said prime numbers p and q being separately included in said transmission,

wherein said prime numbers p and q are selected by said distribution center such that the likelihood of a product (p−

1)(q−

1) and an odd-valued correct hash value h₁ of said transmitted message having a greatest common denominator other than 1 is substantially zero, whereby h₁z=1 mod Φ

(pq), where Φ

(pq)=(p−

1)(q−

1), and said correct hash value h₁ is a public RSA key corresponding to said private RSA key z, and

wherein said integrity value K′

equals g₁^xg₂^a mod M, where x=s^h mod pq, h is a hash value of said message computed by said user device in a similar manner as said correct hash value h₁, M is a public modulus, a is a stored digital signet, and g₁ and g₂ are preferably unique stored values.

2. A system for guaranteeing message integrity, comprising:

a distribution center that transmits a transmission including a message and at least one appended value; and

a user device that receives said transmission and computes an integrity value K′

that depends on said transmission and at least one stored value, where K′

selectively enables successful further processing of said message if and only if a computed hash value h matches a correct hash value h₁, guaranteeing the integrity of said message,

wherein said stored values include a predetermined integrity value K=g₁^h0 g₂^a mod M, where a is a digital signet M is a public modulus, and g₁ and g₂ are preferably unique values.

3. A method for guaranteeing message integrity, comprising:

transmitting a transmission including a message and appended values from a distribution center;

receiving said transmission with a user device;

computing an integrity value K′

that depends on said transmission and at least one stored value, where K′

selectively enables successful further processing of said message if and only if a computed hash value h matches a correct hash value h₁ guaranteeing the integrity of said message,

wherein said appended values include a modulus pq and an authentication value s that is an encrypted version of an original hash value h₀, said modulus pq, and a private RSA key z, where s=h₀^z mod pq,

wherein said modulus pq is a product of two prime numbers p and q, neither of said prime numbers p and q being separately included in said transmission,

wherein said prime numbers p and q are selected by said distribution center such that the likelihood of a product (p−

1)(q−

1) and an odd-valued correct hash value h₁ of said transmitted message having a greatest common denominator otter than 1 is substantially zero, whereby h₁z=1 mod Φ

(pq), where Φ

(pq)=(p−

1)(q−

1), and said correct hash value h₁ is a public RSA key corresponding to said private RSA key z, and

wherein said integrity value K′

equals g₁^x g₂^a mod M, where x=s^h mod pq, h is a hash value of said message computed by said user device in a similar manner as said correct hash value h₁, M is a public modulus, a is a stored digital signet, and g₁ and g₂ are preferably unique stored values.

4. A method for guaranteeing message integrity, comprising:

transmitting a transmission including a message and at least one appended value from a distribution center;

receiving said transmission with a user device;

computing an integrity value K′

that depends on said transmission and at least one stored value, where K′

selectively enables successful further processing of said message if and only if a computed hash value h matches a correct hash value h₁, guaranteeing the integrity of said message,

wherein said stored values include a predetermined integrity value K=g₁^h0 g₂^a mod M, where a is a digital signet, M is a public modulus, and g₁ and g₂ are preferably unique values.