Fast modular multiplication of large integers

1 . A computer-implemented method comprising:

performing, by one or more processors, elliptic curve cryptography (ECC) operations for an approach to public-key cryptography based on algebraic structure of elliptic curves over finite fields by combining a key agreement with a symmetric encryption scheme, the ECC operations comprising:

receiving, by one or more processors, a plurality of first operand values, wherein:

the plurality of first operand values are integer values; and

the plurality of first operand values originate from a Solinas reduction operation;

adding, by a hardware n-way binary adder comprising a carry sum adder and a binary adder, using binary addition, the plurality of first operand values, resulting in a sum value, wherein:

the carry sum adder receives the plurality of first operand values and outputs, to the binary adder, a carry/sum vector pair represented in a redundant number form; and

the redundant number form is a reduced-radix form;

determining, by one or more processors, a single combined modular correction term for a binary sum of all operand values based on: (i) leading bits of the sum value and (ii) by using a lookup table that gives a modulus number represented by the leading bits of the sum value; and

performing, by a hardware modular adder comprising a second hardware binary adder and a multiplexer, a modular addition of the sum value and the single combined modular correction term, resulting in a modular sum of the plurality of first operand values.

2 . The computer-implemented method of claim 1 , further comprising:

performing, by one or more processors, a binary multiplication of second integer values, resulting in a binary product, wherein the binary product is represented by a plurality of adjacent words of a predefined number of bits; and

using, by one or more processors, a plurality of coarse-grained modular correction terms as the plurality of first operand values, producing a result of a modular multiply operation.

3 . The computer-implemented method of claim 2 , wherein the second integer values are represented in a redundant number form.

4 . The computer-implemented method of claim 3 , wherein the redundant number form of the second integer values is a reduced-radix form.

5 . The computer-implemented method of claim 2 , wherein the second integer values each comprise an integer value having a number of bits between 255 bits and 521 bits.

6 . The computer-implemented method of claim 1 , wherein the plurality of first operand values are operand values for elliptic curve operations.

7 . A computer system comprising:

a processor set;

one or more computer-readable storage media; and

program instructions stored on the one or more computer-readable storage media to cause the processor set to perform operations comprising:

performing elliptic curve cryptography (ECC) operations for an approach to public-key cryptography based on algebraic structure of elliptic curves over finite fields by combining a key agreement with a symmetric encryption scheme, the ECC operations comprising:

receiving a plurality of first operand values, wherein:

the plurality of first operand values are integer values; and

the plurality of first operand values originate from a Solinas reduction operation;

adding, by a hardware n-way binary adder comprising a carry sum adder and a binary adder, using binary addition, the plurality of first operand values, resulting in a sum value, wherein:

the carry sum adder receives the plurality of first operand values and outputs, to the binary adder, a carry/sum vector pair represented in a redundant number form; and

the redundant number form is a reduced-radix form;

determining a single combined modular correction term for a binary sum of all operand values based on: (i) leading bits of the sum value and (ii) by using a lookup table that gives a modulus number represented by the leading bits of the sum value; and

performing, by a hardware modular adder comprising a second hardware binary adder and a multiplexer, a modular addition of the sum value and the single combined modular correction term, resulting in a modular sum of the plurality of first operand values.

8 . A computer program product comprising:

one or more computer-readable storage media; and

program instructions stored on the one or more computer-readable storage media to perform operations comprising:

performing elliptic curve cryptography (ECC) operations for an approach to public-key cryptography based on algebraic structure of elliptic curves over finite fields by combining a key agreement with a symmetric encryption scheme, the ECC operations comprising:

receiving a plurality of first operand values, wherein:

the plurality of first operand values are integer values; and

the plurality of first operand values originate from a Solinas reduction operation;

adding, by a hardware n-way binary adder comprising a carry sum adder and a binary adder, using binary addition, the plurality of first operand values, resulting in a sum value, wherein:

the carry sum adder receives the plurality of first operand values and outputs, to the binary adder, a carry/sum vector pair represented in a redundant number form; and

the redundant number form is a reduced-radix form;

determining a single combined modular correction term for a binary sum of all operand values based on: (i) leading bits of the sum value and (ii) by using a lookup table that gives a modulus number represented by the leading bits of the sum value; and

performing, by a hardware modular adder comprising a second hardware binary adder and a multiplexer, a modular addition of the sum value and the single combined modular correction term, resulting in a modular sum of the plurality of first operand values.