Secure transformation from a residue number system to a radix representation

Patent metadata

Field	Value
Publication number	US-11755288-B2
Application number	US-201716347715-A
Country	US
Kind code	B2
Filing date	Oct 30, 2017
Priority date	Nov 8, 2016
Publication date	Sep 12, 2023
Grant date	Sep 12, 2023

Abstract

An electronic calculating device (100) arranged to convert an input number (y) represented ((y1, y2, . . . , yk)) m a residue number system (RNS) to an output number represented in a radix representation ((e0, e1, . . . es−1)), the calculating device comprising an input interface (110) arranged to receive the input number (y) represented in the residue number system, and a processor circuit (120) configured to iteratively update an intermediate number (ŷ) represented in the residue number system, wherein iterations produce the digits (e0, e1, . . . es−1) in the radix representation with respect to the bases (b0, b1, . . . , bs−1), at least one iteration comprises computing the intermediate number modulo a base (bt) of the radix representation to obtain a digit (et=(ŷ)bt) of the radix representation, updating the intermediate number (ŷ←(ŷ−et+F)/bt) by subtracting the digit from the intermediate number, adding an obfuscating number (F; Ft), and dividing by the base (bt).

First claim

The invention claimed is:

1. A cryptographic computer device that is configured to perform cryptologic functions in an environment (white-box) wherein the operation of the cryptographic computer device during the execution of the cryptologic functions can be openly monitored and consequently at-risk for leakage of cryptologic information, the cryptographic computer device comprising:
a computer device circuit that executes a cryptographic function,
wherein the cryptographic function requires conversion of a first encoded number that is represented in a residue number system (RNS) into a second encoded number that is represented in a Radix representation;

a calculating device comprising:
an input interface circuit,
wherein the input interface circuit receives the first encoded number in the RNS representation as an encoded input number, and

a processor circuit,
wherein the processor circuit converts the encoded input number in the RNS representation into an encoded output number in the Radix representation,
wherein the processor circuit provides the encoded output number to the cryptographic function as the second encoded number;

wherein the Radix representation of the encoded output number comprises a set of bases,
wherein the encoded output number comprises digits in the Radix representation corresponding to the bases,
wherein the processor circuit iteratively updates an intermediate number represented in the residue number system,
wherein each iteration produces an iteration digit of the encoded output number,
wherein at least one iteration comprises:
computing a modulo of the intermediate number relative to an iteration base of the set of bases corresponding to the at least one iteration to obtain the iteration digit of the encoded output number corresponding to the at least one iteration,
updating the intermediate number by subtracting the iteration digit from the intermediate number,
adding an obfuscating number to the intermediate number, and
dividing the intermediate number by the iteration base,

wherein the obfuscating number is a multiple of a product of one or more of the bases of the set of bases,
wherein the obfuscating number is greater than 0,
wherein the adding of the obfuscating number spreads the intermediate number over a substantially larger range of the intermediate numbers than a range of the intermediate numbers without the adding, thereby reducing the cryptologic leakage of information.

2. The calculating device of claim 1 , wherein all the bases of the set of bases are equal.

3. The calculating device of claim 1 ,
wherein the iteration digit is larger-than or equal-to 0, and
wherein the iteration digit is less than a predetermined multiple of the iteration base.

4. The calculating device of claim 3 , wherein the iteration digit is less than the iteration base.

5. The calculating device of claim 1 , wherein at least one iteration digit is less than 0, or, larger-than or equal-to the iteration base.

6. The calculating device of claim 1 ,
wherein the processor circuit computes a correction term,
wherein the correction term indicates a difference between the encoded input number and a number represented by the digits of the output number.

7. The calculating device of claim 1 ,
wherein the processor circuit computes a correction term,
wherein the correction term is a difference between a final iteration digit and the modulo of the intermediate number relative to the iteration base,
wherein the modulo of the intermediate number is configured to produce a result that is at least 0, and less than the iteration base.

8. The calculating device of claim 1 wherein at least one of the bases of the set of bases is a modulus of the residue number system.

9. The calculating device of claim 1 , further comprising a memory, wherein the encoded input number and the intermediate numbers are stored in the memory in an encoded form.

10. The calculating device of claim 1 ,
wherein the processor circuit processes multiple numbers in the RNS representation to produce a resulting number in the RNS representation,
wherein the resulting number is the encoded input number,
wherein the multiple in the obfuscation number depends on one or more of the multiple numbers in the RNS representation.

11. The calculating device of claim 1 , wherein the processor circuit executes a digit-based Montgomery-multiplication with the encoded output number as a multiplicand of the Montgomery-multiplication.

12. The calculating device of claim 1 , wherein a first intermediate number of the first iteration is the encoded input number.

13. The calculating device of claim 1 , wherein the encoded output number is represented by the digits of the encoded output number and a correction term.

14. The calculating device as in claim 1 ,
wherein the RNS system is a redundant RNS system having at least one redundant modulus,
wherein the updating of the intermediate number for the redundant modulus provides a residue for the redundant modulus that is greater-than or equal-to 0 and less than the redundant modulus.

15. The calculating device of claim 1 , wherein the digits of the encoded output number are stored in a memory of the calculating device in an encoded form.

16. The calculating device of claim 7 , wherein the difference is divided by the iteration base.

17. A method of improving the security of a cryptologic computer device that is configured to perform cryptologic functions in an environment (white-box) wherein the operation of the cryptographic computer device during the execution of the cryptologic functions can be openly monitored and consequently at-risk for leakage of cryptologic information, the method comprising:
executing a cryptologic function that requires conversion of a first encoded number that is represented in a residue number system (RNS) into a second encoded number that is represented in a Radix representation,
receiving, at a calculating device of the cryptographic computer device, the first encoded number in the RNS representation as an encoded input number,
converting the encoded input number in the RNS representation into an encoded output number in the Radix representation, and
providing the encoded output number to the cryptographic function as the second encoded number;
wherein the Radix representation comprises a set of bases,
wherein the encoded output number comprises a set of digits corresponding to the set of bases;
wherein the conversion of the encoded input variable comprises:
iteratively updating an intermediate number represented in the RNS to produce the encoded output number in the Radix representation,
wherein at least one iteration comprises:
computing a modulo of the intermediate number relative to an iteration base of the set of bases corresponding to the at least one iteration to obtain a corresponding iteration digit of the set of digits,
subtracting the iteration digit from the intermediate number,
adding an obfuscating number to the intermediate number, and
dividing the intermediate number by the iteration base;

wherein the obfuscating number is a multiple of the product of one or more of the bases of the set of bases,
wherein the obfuscating number is greater than 0,
wherein the adding of the obfuscating number spreads the intermediate numbers over a substantially larger range of the intermediate numbers than a range of the intermediate numbers without the adding, thereby reducing the leakage of cryptologic information.

18. The method of claim 17 , wherein a

Assignees

• Koninklijke Philips Nv

Inventors

• Hollmann Hendrik Dirk Lodewijk
• Rietman Ronald
• Tolhuizen Ludovicus Marinus Gerardus Maria
• De Hoogh Sebastiaan Jacobus Antonius

Classifications

• G06F7/729 Primary

  using representation by a residue number system · CPC title

• H04L9/002

  Countermeasures against attacks on cryptographic mechanisms (network architectures or network communication protocols for protection against malicious traffic H04L63/1441) · CPC title

• H04L2209/16

  Obfuscation or hiding, e.g. involving white box · CPC title

• G06F7/728

  using Montgomery reduction · CPC title