Method, sender apparatus and receiver apparatus for modulo operation

• US 5,479,511 A
• Filed: 07/08/1994
• Issued: 12/26/1995
• Est. Priority Date: 11/05/1991
• Status: Expired due to Term

• Current Assignee: Thomson Consumer Electronics SA (Vantiva SA)
• Original Assignee: Thomson Consumer Electronics SA (Vantiva SA)
• Inventors: Naccache, David
• Primary Examiner(s): Gregory, Bernarr E.
• Application Number:
  US08/199,213
• Time in Patent Office: 536 Days
• Field of Search: 380/9, 380/10, 380/23, 380/25, 380/28, 380/30, 380/49, 380/24, 380/16, 235/379, 235/380
• US Class Current: 380/28
• CPC Class Codes: G06Q 20/3674 involving authentication
• CPC Class Codes: H04L 9/3234 involving additional secure or trusted devices, e.g. TPM, smartcard, USB or software token network architectures or network communication protocols for supporting authentication of entities using an additional device in a packet data network H04L63/0853

Abstract

An access control system involves a first cryptographic device communicating with a second cryptographic device using a modulo-based protocol. To transmit a message from the first device to the second device, a random number is combined with the number representing the message without using a modulo operation. As a result, the message is hidden. By performing a modulo operation in the second device on the received hidden message, the original message can be recovered. Modular operations by the first device can be avoided reducing the number of modular operations.

Claims

1. A method for encrypted communication of a message from a sender device to a receiver device, said message being represented by a set of numbers S(j)=D(j) mod X, j=1, . . . ,i, i being an integer greater than or equal to 1, X being a product of at least two big prime numbers and each D (j) being greater than X, said method comprising the steps of:

storing the value X in a first memory device of said sender device and in a second memory device of said receiver device;

producing in a first processor associated with said sender device a set of values E(j)=D(j)+A(j)*X from a set of random numbers A(j);

transmitting a signal representative of said values E(j) from said sender device to said receiver device via an interface;

processing said signal in a second processor associated with said receiver device for generating a set of numbers S(j)=E(j) mod X; and

recovering said message from said set of numbers S(j)=E(j) mod X.

2. Method according to claim 1, wherein a transmitted word length of each of said values E (j) is less than four times the word length of X.

3. A method according to claim 1, or claim 2, wherein the steps of producing and transmitting said values E(j) include the steps of:

producing in said first processor a first |X| bytes of each of said values E(j) using |X| cells of said first memory device, |X| denoting the word length of X;

transmitting a first signal representative of said first |X| bytes of each of said values E(j) to said receiver device via said interface;

producing in said first processor a second |X| bytes of each of said values E(j) using said |X| cells of said first memory device;

transmitting a second signal representative of said second |X| bytes of each of said values E(j) to said receiver device via said interface; and

wherein the step of generating said set of numbers S(j)=E(j) rood X in said second processor comprises the step of

processing said first and second signals in said second processor for concatenating said second |X| bytes and said first |X| bytes of each of said values E(j) for reconstructing each of said values E(j).

4. A method according to claim 3, wherein said word length of X is in a range from 64 to 128 bytes .

5. A method according to claim 4, wherein said sender device is a smart-card.

6. A method for encrypted communication of a message from a sender device to a receiver device, said message being represented by a set of numbers S(j)=D(j) mod X, j=1, . . . ,i, i being an integer greater than 1, X being a product of at least two big prime numbers and each D (j) being greater than X, said method comprising the steps of:

storing the value X in a first memory device of said sender device and in a second memory device of said receiver device;

generating in a first processor associated with said sender device a random number A and a number B=A*X;

storing said number B in said first memory device of said sender device;

producing in a first processor associated with said sender device a set of values E(j)=D(j)*B;

transmitting a signal representative of said values E(j) from said sender device to said receiver device via an interface;

processing said signal in a second processor associated with said receiver device for generating a set of numbers S(j)=E(j) mod X; and

recovering said message from said set of numbers S(j)=E(j) mod X.

7. Method according to claim 6, wherein a transmitted word length of each of the values E (j) is less than four times the word length of X.

8. A method according to claim 6 or claim 7, wherein the steps of producing and transmitting said values E(j) include the steps of:

producing in said first processor a first |X| bytes of each of said values E(j) using |X| cells of said first memory device, |X| denoting the word length of X;

transmitting a first signal representative of said first |X| bytes of each of said values E(j) to said receiver device via said interface;

producing in said first processor a second |X| bytes of each of said values E(j) using said |X| cells of said first memory device;

transmitting a second signal representative of said second |X| bytes of each of said values E(j) to said receiver device via said interface; and

wherein the step of generating said set of numbers S(j)=E(j) mod X in said second processor comprises the step of

processing said first and second signals in said second processor for concatenating said second |X| bytes and said first |X| bytes of each of said values E(j) for reconstructing each of said values E(j).

9. A method according to claim 8, wherein said word length of X is in a range from 64 to 128 bytes.

10. A method according to claim 9, wherein said sender device is a smart-card.

11. A sender device for encrypted communication of a message to a receiver device, said message being represented by a set of numbers S(j)=D(j) mod X, j=1, . . . ,i, i being an integer greater than or equal to 1, X being a product of at least two big prime numbers and each D(j) being greater than X, comprising:

memory means for storing X;

a processor coupled to said memory means for generating a set of values E(j)=D(j)+A(j)*X from a set of random numbers A(j);

data exchange means coupled to said processor for sending a signal representative of said values E(j) to said receiver device, said number X being stored in said receiver device and a set of values S(j)=E(j) mod X being generated in said receiver device for recovering said message from said set of values S(j)=E(j) mod X.

13. A sender device according to claim 11 or claim 12, wherein said sender device is one of a smart-card, a credit-card, a passport and a door-key.

12. A sender device for encrypted communication of a message to a receiver device, said message being represented by a set of numbers S(j)=D(j) mod X, j=1, . . . ,i, i being an integer greater than 1, X being a product of at least two big prime numbers and each D(j) being greater than X, comprising:

memory means for storing X;

a processor coupled to said memory means for generating a number B=A*X from a random number A and for generating a set of values E(j)=D(j)*B, said number B being stored in said memory means;

data exchange means coupled to said processor for sending a signal representative of said values E(j) to said receiver device, said number X being stored in said receiver device and a set of values S(j)=E(j) mod X being generated in said receiver device for recovering said message represented by said values D(j) mod X.

14. A receiver device for evaluating an encrypted communication of a message from a sender device, said message being represented by a set of numbers S(j)=D(j) mod X, j=1, . . . ,i, i being an integer greater than or equal to 1, X being a product of at least two big prime numbers and each D(j) being greater than X, said receiver device comprising:

memory means for storing X;

data exchange means for receiving a signal generated in said sender device, said signal being representative of a set of values E(j)=D(j)+A(j)*X generated in said sender device by generating a set of random numbers A(j) and generating therefrom said values E(j);

a processor coupled to said memory means and to said data exchange means for processing said signal to generate a set of values S(j)=E(j) mod X for recovering said message.

16. A receiver device according to claim 14 or claim 15 wherein said receiver device comprises one of a pay TV decoder, a credit-card verifier, a passport verifier and an electronic lock.

15. A receiver device for evaluating an encrypted communication of a message from a sender device, said message being represented by a set of numbers S(j)=D(j) mod X, j=1, . . . ,i, i being an integer greater than 1, X being a product of at least two big prime numbers and each D(j) being greater than X, said receiver device comprising:

memory means for storing X;

data exchange means for receiving a signal from said sender device, said signal being representative of a set of values E(j)=D (j)* B generated in said sender device by generating a random number A and a number B=A*X, said number B being stored in said sender device;

a processor coupled to said memory means and to said data exchange means for processing said signal to generate a set of values S(j)=E(j) mod X for recovering said message.