# US 8,280,041 B2 · Chinese remainder theorem-based computation method for cryptosystems

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,280,041 B2
- Document ID: US8280041B2
- Status: Granted
- Kind: B2
- Application number: 11/684,842
- Filed: 2007-03-12
- Published: 2008-09-18
- Granted: 2012-10-02
- Earliest claimed: 2007-03-12
- Assignees: Inside Secure
- Inventors: Michel Douguet; Neil M. McKeeney
- Web page: https://patentgrep.com/patent/US8280041B2

## CPC

- G06F 7/723: {Modular exponentiation (G06F7/724, G06F7/727, G06F7/728 take precedence)}
- H04L 9/302: {involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes}
- G06F 2207/7247: Modulo masking, e.g. A**e mod (n*r)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A computer hardware implemented cryptography method computes a modular exponentiation, M :=Cd (mod p·q), upon a message data value C using a Chinese Remainder Theorem (CRT) based technique. To secure against cryptanalysis, the private key moduli p and q are transformed by multiplication with a generated random value s, so that p′: =p·s and q′ :=q·s, as shown in an exemplary embodiment in FIG. 2. The CRT steps of the modular exponentiation are applied using the transformed moduli p′ and q′ to obtain a random intermediate message data value M′. A final reduction of M′ modulo p·q yields the final message data value M. Values needed for the computation are loaded into data storage and accessed as needed by electronic processing hardware.

## Claims

### Claim 1

A cryptographic method implemented in an electronic processing system for performing modular exponentiation computations, comprising:
loading private key values, including at least one private key exponent and two private key moduli p and q, wherein the two private key moduli are p and q, into a data storage accessible to electronic processing hardware;
selecting, by the electronic processing hardware, a non-random pre modular exponentiation transformation factor to secure cryptographic operations utilizing modular exponentiation from cryptanalysis, wherein the transformation factor is co-prime with the private key moduli;
multiplying, by the electronic processing hardware, the private key moduli by the transformation factor to produce transformed moduli p′ :=p·s and q′ :=q·s, wherein the transformed moduli are p′ and q′ and wherein the transformation factor is s;
loading a first data value into the data storage at any time prior to performing modular exponentiation;
computing, by the electronic processing hardware, at least one transformed inverse value, R′ :=(p′)−1(mod q);
performing, by the electronic processing hardware, a modular exponentiation upon the first data value using the at least one private key exponent and the transformed moduli to obtain an intermediate data value; and
reducing, by the electronic processing hardware, the intermediate data value modulo a product of the two private key moduli to obtain a final data value.

### Claim 2 (depends on 1)

The method as in claim 1 wherein the selected transformation factor is a fixed value.

### Claim 3 (depends on 1)

The method as in claim 1, wherein performing modular exponentiation is executed using a Chinese Remainder Theorem (CRT) calculation of the intermediate data value.

### Claim 4 (depends on 3)

The method as in claim 3, wherein a pair of CRT exponents are computed from a single private key exponent as part of the performing the modular exponentiation.

### Claim 5 (depends on 3)

The method as in claim 3, wherein a pair of CRT exponents are pre-computed from a single private key exponent, the pair of CRT exponents being loaded as private key exponents into the data storage.

### Claim 6 (depends on 1)

The method as in claim 1, wherein the product of the two private key moduli is pre-computed as a public key modulus, the public key modulus also being loaded into the data storage for subsequent use in the reducing of the intermediate data value.

### Claim 7 (depends on 1)

The method as in claim 1, wherein the first data value represents a ciphertext message, the modular exponentiation is executed in the electronic processing hardware as part of a cipher program, and the final data value represents a decrypted plaintext message.

### Claim 8

A cryptographic method implemented in an electronic processing system for performing modular exponentiation computations, comprising:
loading at least one private key exponent d and two private key moduli p and q, wherein the two private key moduli are p and q, into a data storage accessible to electronic processing hardware;
selecting, by the electronic processing hardware, a non-random pre modular exponentiation transformation factor s to secure cryptographic operations utilizing modular exponentiation from cryptanalysis, wherein the transformation factor is co-prime with the private key moduli;
multiplying, by the electronic processing hardware, the private key moduli by the transformation factor to produce transformed moduli p′ :=p·s and q′ :=q·s, wherein the transformed moduli are p′ and q′;
computing, by the electronic processing hardware, at least one transformed inverse value, R′ :=(p′)−1(mod q);
loading a first data value C into the data storage at any time prior to performing modular exponentiation;
performing a modular exponentiation upon the first data value C using the at least one private key exponent d and the transformed moduli p′ and q′ to obtain an intermediate data value M′, wherein performing modular exponentiation is executed by the electronic processing hardware using a Chinese Remainder Theorem (CRT) calculation of the intermediate data value involving:
(a) computing CRT exponents d1 :=d (mod (p−1)) and d2 :=d (mod (q−1)),
(b) computing CRT message components M1 ′:=Cd1 (mod p′) and M2′:=Cd2 (mod q′), and
(c) computing an intermediate data value M′ from the CRT message components M1and M2′; and reducing, by the electronic processing hardware, the intermediate data value M′ modulo a product of the two private key moduli, n =p·q, to obtain a final data value M :=M′ (mod n).

### Claim 9 (depends on 8)

The method as in claim 8, wherein the CRT exponents are pre-computed from the private key exponent d and loaded as a pair of private key exponents d1 and d2 into the data storage.

### Claim 10 (depends on 8)

The method as in claim 8, wherein M′:=M1′+p′·{[(M2′−M1′)·R′](mod q′)}.

### Claim 11 (depends on 8)

The method as in claim 8, wherein M′:=(M1′·R1′·q′+M2′·R2′·p′) (mod p′·q′), and R1′:=(q′)−1 (mod p).

### Claim 12 (depends on 8)

The method as in claim 8, wherein M′:={[(M1′·R1′) (mod p′)]·q′+[(M2′·R′) (mod q′)]·p′}(mod p′·q′), and R1′:=(q′)−1 (mod p).

### Claim 13 (depends on 8)

The method as in claim 8, wherein M′:=q′·{[(M1′−M2′)·R′](mod p′)}+M2′.

### Claim 14 (depends on 8)

The method as in claim 8, wherein the product n=p·q is pre-computed and loaded into the data storage for subsequent use during the reducing of the intermediate data value.

### Claim 15 (depends on 8)

The method as in claim 8, wherein the first data value represents a ciphertext message, the modular exponentiation is executed in the electronic processing hardware as part of a cipher program, and the final data value represents a decrypted plaintext message.
