# US 8,280,042 B2 · Decryption processor and decryption processing method

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

- Number: US 8,280,042 B2
- Document ID: US8280042B2
- Status: Granted
- Kind: B2
- Application number: 12/689,670
- Filed: 2010-01-19
- Published: 2010-09-16
- Granted: 2012-10-02
- Earliest claimed: 2009-01-19
- Assignees: Fujitsu Limited
- Inventors: Kouichi Itoh
- Web page: https://patentgrep.com/patent/US8280042B2

## CPC

- G06F 7/723: {Modular exponentiation (G06F7/724, G06F7/727, G06F7/728 take precedence)}
- H04L 9/003: {for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA]}
- G06F 2207/7242: Exponent masking, i.e. key masking, e.g. A**(e+r) mod n; (k+r).P
- H04L 2209/08: Randomization, e.g. dummy operations or using noise
- 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 decryption processor for calculating a plaintext through decryption of a ciphertext c includes, a first part that calculates m′p through modular exponentiation modulo a first prime number p wherein an exponent is a shifted value of d(mod(p−1)), and a base is a value of c(mod p); a second modular exponentiation part that calculates m′q through modular exponentiation modulo a second prime number q, wherein an exponent is a value of d(mod(q−1)) and a base is a value of c(mod q); a composition part that calculates ms through calculation of ((u×(m′q−m′p)(mod q))×p+m′p by using the values m′p and m′q and a private key u corresponding to p−1(mod q); and a shift release part that calculates the plaintext m through calculation of ms×(cs(mod n))(mod n) by using the value ms.

## Claims

### Claim 1

A decryption processor for calculating a plaintext m through decryption of a ciphertext c by using a first prime number p, a second prime number q, a public key e, and a private key d, the decryption processor comprising:
a first modular exponentiation part that calculates a value m′p through modular exponentiation modulo the first prime number p, wherein an exponent is a value obtained by shifting, with a numerical value s, a value dp calculated in accordance with d(mod(p−1)), and a base is a value cp calculated in accordance with c(mod p);
a second modular exponentiation part that calculates a value m′q through modular exponentiation modulo the second prime number q, wherein an exponent is a value obtained by shifting, with the numerical value s, a value dq calculated in accordance with d(mod(q−1)), and a base is a value cq calculated in accordance with c(mod q);
a composition part that calculates a value ms through calculation of ((u×(m′q−m′p)(mod q))×p+m′p by using the values m′p and m′q calculated respectively by the first modular exponentiation part and the second modular exponentiation part and a private key u corresponding to a calculation result of p−1(mod q); and
a shift release part that calculates the plaintext m through calculation of ms×(cs(mod n))(mod n) by using the value ms calculated by the composition part.

### Claim 2 (depends on 1)

The decryption processor according to claim 1,
wherein the first modular exponentiation part, the second modular exponentiation part, and the shift release part use a random number of two bits or less as the numerical value s.

### Claim 3 (depends on 1)

The decryption processor according to claim 1,
wherein the first modular exponentiation part, the second modular exponentiation part, and the shift release part use a constant of two bits or less as the numerical value s.

### Claim 4 (depends on 1)

The decryption processor according to claim 1,
wherein the shift release part calculates the plaintext m by calculating cs(mod n) by a left-to-right binary method.

### Claim 5 (depends on 1)

The decryption processor according to claim 1,
wherein the shift release part calculates the plaintext m by a right-to-left binary method.

### Claim 6

A non-transitory computer readable medium recording a program causing a computer to execute a decryption processing method for calculating a plaintext m through decryption of a cipher text c by using a first prime number p, a second prime number q, a public key e, and a private key d, the method comprising:
calculating a value m′.sub.p through modular exponentiation modulo the first prime number p, wherein an exponent is a value obtained by shifting, with a numerical value s, a value d.sub.p calculated in accordance with d(mod(q−1)), and a base is a value c.sub.p calculated in accordance with c(mod p);
calculating a value m′.sub.q through modular exponentiation modulo the second prime number q, wherein an exponent is a value obtained by shifting, with the numerical value s, a value d.sub.q calculated in accordance with d(mod(q−1)), and a base is a value c.sub.q calculated in accordance with c(mod q);
calculating a value m.sub.s through calculation of ((u.times.(m′.sub.q−m′.sub.p) (mod q)).times.p+m′.sub.p by using the values m′.sub.p and m′.sub.q calculated respectively by the value m′.sub.p calculation step and the value m′.sub.q calculation step, and a private key u corresponding to a calculation result of p.sup.−1(mod q); and
generating the plaintext m through calculation of m.sub.s.times.(c.sup.s (mod n))(mod n) by using the value m.sub.s calculated in the value m.sub.s calculation step.

### Claim 7 (depends on 6)

The non-transitory computer readable medium according to claim 6, wherein the value m′p calculation step, the value m′q calculation step, and the plaintext m calculation step use a random number of two bits or less as the numerical value s.

### Claim 8 (depends on 6)

The non-transitory computer readable medium according to claim 6, wherein the value m′p calculation step, the value m′q calculation step, and the plaintext m calculation step use a constant of two bits or less as the numerical value s.

### Claim 9 (depends on 6)

The non-transitory computer readable medium according to claim 6, wherein the plaintext m calculation step uses a left-to-right binary method to calculate cs(mod n).

### Claim 10 (depends on 6)

The non-transitory computer readable medium according to claim 6, wherein the plaintext m calculation step uses a right-to-left binary method.

### Claim 11

A method for calculating a plaintext m through decryption of a cipher text c by using a first prime number p, a second prime number q, a public key e, and a private key d, to be executed by a computer, the method comprising:
calculating, by a processor of the computer, a value m′.sub.p through modular exponentiation modulo the first prime number p, wherein an exponent is a value obtained by shifting, with a numerical value s, a value d.sub.p calculated in accordance with d(mod(p−1)), and a base is a value c.sub.p calculated in accordance with c(mod P);
calculating a value m′.sub.q through modular exponentiation modulo the second prime number q, wherein an exponent is a value obtained by shifting, with the numerical value s, a value d.sub.q calculated in accordance with d(mod(q−1)), and a base is a value c.sub.q calculated in accordance with c(mod q);
calculating a value m.sub.s through calculation of ((u.times.(m′.sub.q−m′.sub.p) (mod q)).times.p+m′.sub.p by using the values m′.sub.p and m′.sub.q calculated respectively by the value m′.sub.p calculation step and the value m′.sub.q calculation step, and a private key u corresponding to a calculation result of p.sup.−1(mod q); and
generating the plaintext m through calculation of m.sub.s.times.(c.sup.s (mod n))(mod n) by using the value m.sub.s calculated by the value m.sub.s calculation step.

### Claim 12 (depends on 11)

The method according to claim 11, wherein the value m′p calculation step, the value m′q calculation step, and the plaintext m calculation step use a random number of two bits or less as the numerical value s.

### Claim 13 (depends on 11)

The method according to claim 11, wherein the value m′p calculation step, the value mq calculation step, and the plaintext m calculation step use a constant of two bits or less as the numerical value s.

### Claim 14 (depends on 11)

The method according to claim 11, wherein the plaintext m calculation step uses a left-to-right binary method to calculate cs(mod n).

### Claim 15 (depends on 11)

The method according to claim 11, wherein the plaintext m calculation step uses a right-to-left binary method.
