Method for implementing a private-key communication protocol between two processing devices

• US 6,226,382 B1
• Filed: 09/24/1997
• Issued: 05/01/2001
• Est. Priority Date: 12/28/1994
• Status: Expired due to Term

• Current Assignee: Gemalto SA (Thales SA)
• Original Assignee: Gemplus (Thales SA)
• Inventors: M'Raihi, David, Naccache, David
• Primary Examiner(s): Hayes, Gail
• Assistant Examiner(s): Seal, James
• Application Number:
  US08/875,331
• Time in Patent Office: 1,315 Days
• Field of Search: 380/28, 380/30, 380/43, 380/44, 380/259, 380/170, 380/171, 380/172, 380/285
• US Class Current: 380/28
• CPC Class Codes: G06Q 20/341 Active cards, i.e. cards including their own processing means, e.g. including an IC or chip
• CPC Class Codes: G06Q 20/40975 using encryption therefor
• CPC Class Codes: G07F 7/1008 Active credit-cards provided with means to personalise their use, e.g. with PIN-introduction/comparison system
• CPC Class Codes: G07F 7/1016 Devices or methods for securing the PIN and other transaction-data, e.g. by encryption arrangements for secret communication, see H04L9/00
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC

Abstract

A method for implementing private key protocols between two processing devices of which at least one is a portable storage medium. The devices are fitted with a digital processing circuit for performing modular calculation operations with a view to executing operations such as modular multiplication, the processing circuit is used to implement a private key encryption function consisting of a series of reversible operations comprising at least a combination of two operations, i.e. a modular calculation operation and a binary logic operation, and said function is applied either for encrypting or signing messages to be transmitted, or for decrypting received messages.

Claims

1. A process for implementing a secret key protocol between first and second processing devices (Aj, Ak) wherein each device includes a digital processing circuit to perform modular calculations, comprising the steps of:

implementing in said processing circuit a secret key enciphering function composed of a sequence of reversable operations comprising at least the combination of two operations, one of the modular calculation type and the other in binary logic,

applying said function either to outgoing messages to encipher them, or to incoming messages to decipher them,

effecting in said digital processing circuit a dividing of said messages (m) into blocks (x) of N bits prior to said applying step and then processing said divided message in accordance with said applied functions, and

said sequence of operations comprises at least a combination of two operations, one of which is a permutation using modular multiplication and the other an OR-exclusive logic operation, this combination being defined by a secret-key enciphering function f such that;

 

f(x)=(x⊕

K₂)*K₁ mod n

wherein;

x represents a block of N bits of the message,

K₁ and K₂ represent a first and a second secret key over N bits,

n is an odd number of N bits,

⊕

is an exclusive OR operation.,

* is a multiplication modulo n operation.

2. Process according to claim 1, characterized in that, when a device sends messages, it performs a first action on the message (m), consisting of applying the function f iteratively to each block x_i.

3. Process according to claim 1, characterized in that the devices communicate with each other according to the following protocol:

the first device (A_j) divides the message (m) into (q+1) blocks of N bits

said first device (A_j) enciphers each block x of the message such that the enciphered block y of the message is such that;

4. Process according to claim 1, characterized in that in the first device (A_j) the message (m) is divided into (q+1) blocks (x) of N bits, in that a block x_i of one message is placed in a first register, the next block x_i+1 is placed in a second register, and the device sends the enciphered messages after the operation of applying the function f such that

5. Process according to claim 4, characterized in that the processing circuit is used to hash the message and in that, when the first device (A_j) hashes a message M of length L, the circuit performs the following steps:

6. Process according to claim 1, including generating a hashed value of the message (m) and in that when the first device (A_j)hashes the message (M) of length L, the following steps are carried out

7. Process according to claim 1, characterized in that the modular calculation involves a large number.

8. Process according to claim 1, characterized in that the devices are smart cards, PCMCIA cards, badges, contactless cards, or any other portable apparatus or device equipped with a security module possessing the same functions as said portable devices.

9. Process according to claim 1, characterized in that communication between each device is effected by exchanging radio waves or infrared signals.

10. A process for implementing a secrete-key protocol between two processing devices (Aj, Ak), at least one of them being a portable storage device, comprising the following steps:

equipping the devices with a digital processing circuit able to perform operations of the modular calculation type to carry out operations,

using this processing circuit to implement a secret-key enciphering function composed of a sequence of reversible operations comprising at least the combination of two operations, one of the modular calculation type and the other in binary logic,

applying this function either to messages for transmission to encipher them, or to received messages to decipher them,

wherein in one device the message is divided into (q+1) blocks of N bits, in that a block x_i of one message is placed in a first register, the next block x_i+1 is placed in a second register, and the device sends the enciphered messages after the operation consisting of applying a function f such that E(x_i, x_i+1)=f^p(x_i, x_i+1)

with f (x_i, x_i+1)=y_i, y_i+1

where y_i=x_i+1

and p being and iteration number

 

y_i+1=x_i⊕

((y_i⊕

K₂)*K₁ mod n)

the one device sends the (q+1) y blocks to the other device (Ak),

the other device (A_k) performs the following operation on each block y_i;

11. The process according to claim 10, wherein the processing circuit is used to hash the message and in that, when the one device (A_j) hashes a message M of length L, the circuit performs the following steps:

12. Process according to claim 3 or 4 or 6 or 8 or 10, characterized in that the iteration p is greater than or equal to 4.