# US 2014/0192977 A1 · Mutiplication method and modular multiplier using redundant form recoding

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

- Number: US 2014/0192977 A1
- Document ID: US20140192977A1
- Status: Published application
- Kind: A1
- Application number: 14/139,113
- Filed: 2013-12-23
- Published: 2014-07-10
- Earliest claimed: 2013-01-04
- Assignees: Samsung Electronics Co., Ltd.
- Applicants: Samsung Electronics Co., Ltd.
- Inventors: Yong Ki LEE; Sun-Soo SHIN; Jonghoon SHIN; Kyoung Moon AHN; Ji-Su KANG; Kee Moon CHUN
- Web page: https://patentgrep.com/patent/US20140192977A1

## CPC

- G06F 7/722: {Modular multiplication (G06F7/724, G06F7/727, G06F7/728 take precedence)}
- G06F 7/728: {using Montgomery reduction}
- H04L 9/3013: {involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems}
- H04L 9/302: {involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes}
- 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 multiplication method and a modular multiplier are provided. The multiplication method includes transforming a redundant-form multiplier by adding a recoding constant to the multiplier, performing recoding by using the transformed multiplier, and performing partial multiplication between the multiplier and a multiplicand using result values of the recoding.

## Claims

### Claim 1

A multiplication method comprising:
transforming a redundant-form multiplier by adding a recoding constant to the multiplier to generate a transformed multiplier;
performing recoding by using the transformed multiplier; and
performing partial multiplication between the transformed multiplier and a multiplicand using result values of the recoding.

### Claim 2 (depends on 1)

The multiplication method of claim 1, wherein the recoding constant is ‘1010 . . . 1010’ having a same bit size as the multiplicand.

### Claim 3 (depends on 1)

The multiplication method of claim 1, wherein the transforming of the redundant-form multiplier comprises:
performing an operation bitwise,
wherein each bitwise operation value of the transformed multiplier comprises a 2-bit sum bit and a 1-bit carry bit.

### Claim 4 (depends on 1)

The multiplication method of claim 1, wherein the transforming of the redundant-form multiplier comprises:
performing an operation bitwise,
wherein the bitwise operation comprises inverting and full addition.

### Claim 5 (depends on 1)

The multiplication method of claim 1, wherein the transforming of the redundant-form multiplier comprises:
performing an operation bitwise,
wherein the bitwise operation comprises full addition, half addition, and modified half addition, and
the modified half addition comprises adding a first input bit, a second input bit, and 1.

### Claim 6 (depends on 5)

The multiplication method of claim 5, wherein each of the bitwise operation values ri satisfies the following equation:
0≦ri≦4

### Claim 7 (depends on 1)

The multiplication method of claim 1, wherein each of result values of the recoding is determined to be one of 0, the multiplicand, a 2's compliment of the multiplicand, a shifted value of the multiplicand, and a 2's compliment of the shifted value.

### Claim 8 (depends on 1)

The multiplication method of claim 1, wherein the performing of the recoding satisfies the following equation:
B
′
=

B
C
′
+
B
S
′
=

B
C
+
B
S
+
1010


…


1010
C
=

A
·
B
=

A
·
(
B
S
+
B
C
)
=

∑
i
=
0
⌊
n
/
2
⌋

A
·
(
2

s
2

i
+
1
′
+
s
2

i
′
+
c
2

i
′
-
2
)
·
2
2

i
=

∑
i
=
0
⌊
n
/
2
⌋

P
2

i
·
2
2

i
where A is the multiplicand, B is the multiplier, n is a bit size of the multiplicand, P2i=(2s′2i+1+s′2i+c′2i−2)A, B′S=Σi=0ns′i2i,B′C=Σi=1nc′i2i, C′i=0 when i is an odd number, P2i is a partial product, si denotes an accumulated value, Bs is a sum bit, Bc is a carry bit, B′S is a sum bit of the transformed multiplier, and B′C is a carry bit of the transformed multiplier.

### Claim 9

A modular multiplier comprising:
a partial multiplication unit configured to multiply a multiplier and a multiplicand bit;
a modulus multiplication unit configured to multiply a modulus and a transformed quotient bit;
an accumulator configured to receive a previous accumulated value and output values of the partial multiplication unit and the modulus multiplication unit, and calculate an accumulated value according to a Montgomery algorithm;
a register configured to store the accumulated value calculated by the accumulator; and
a quotient generator configured to generate a quotient using the previous accumulated value,
wherein the transformed quotient bit has a value obtained by recoding a redundant-form quotient.

### Claim 10 (depends on 9)

The modular multiplier of claim 9, further comprising:
a first recoding unit configured to transform the previous accumulated value by adding a recoding constant to the redundant-form previous accumulated value, and recode the transformed previous accumulated value; and
a second recoding unit configured to transform the redundant-form quotient by adding a recoding constant thereto, and recode the transformed quotient.

### Claim 11 (depends on 10)

The modular multiplier of claim 10, wherein each of the first and second recoding units comprises:
a first column in which half adders and modified half adders are repeatedly alternately arranged; and
a second column in which full adders and half adders are repeatedly alternately arranged,
wherein the modified half adder adds a first input bit, a second input bit, and 1.

### Claim 12 (depends on 10)

The modular multiplier of claim 10, wherein each of the first and second recoding units comprises:
a first column in which inverters are intermittently arranged; and
a second column in which full adders are repeatedly arranged.

### Claim 13 (depends on 10)

The modular multiplier of claim 10, wherein a size of the recoding constant is the same as a size of the multiplicand.

### Claim 14 (depends on 9)

The modular multiplier of claim 9, wherein the quotient generator uses a value obtained by recoding a least significant digit of the previous accumulated value as a multiplier.

### Claim 15 (depends on 14)

The modular multiplier of claim 14, wherein the value obtained by recoding the least significant digit exists in a redundant form.

### Claim 16

A public key calculator that calculates a public key, the calculator comprising:
a central processing unit;
a crypto-memory; and
a crypto-processor that comprises:
a partial multiplication unit configured to multiply a multiplier and a multiplicand bit of the public key;
a modulus multiplication unit configured to multiply a modulus and a transformed quotient bit;
an accumulator configured to receive a previous accumulated value and output values of the partial multiplication unit and the modulus multiplication unit, and calculate an accumulated value according to a Montgomery algorithm;
a register configured to store the calculated accumulated value; and
a quotient generator configured to generate a quotient using the previous accumulated value,
wherein the transformed quotient bit has a value obtained by recoding a redundant-form quotient, and
wherein the central processing unit receives a request to calculate a public key, and the central processing unit calculates the public key using the crypto-processor.

### Claim 17 (depends on 16)

The public key calculator of claim 16, wherein the public key is at least 1024 bits.

### Claim 18 (depends on 16)

The public key calculator of claim 16, further comprising:
a first recoding unit configured to transform the previous accumulated value by adding a recoding constant to the redundant-form previous accumulated value, and recode the transformed previous accumulated value; and
a second recoding unit configured to transform the redundant-form quotient by adding a recoding constant thereto, and recode the transformed quotient,
wherein a size of the recoding constant is the same as that of the multiplicand.

### Claim 19 (depends on 18)

The public key calculator of claim 18, wherein each of the first and second recoding units comprises:
a first column in which half adders and modified half adders are repeatedly alternately arranged; and
a second column in which full adders and half adders are repeatedly alternately arranged,
wherein the modified half adder adds a first input bit, a second input bit, and 1.

### Claim 20 (depends on 18)

The public key calculator of claim 18, wherein each of the first and second recoding units comprises:
a first column in which inverters are intermittently arranged; and
a second column in which full adders are repeatedly arranged.