Fast modular multiplication of large integers
In an approach, a processor receives a plurality of first operand values, where the first operand values are integer values. A processor adds, using binary addition, the plurality of first operand values resulting in a sum value S. A processor determines a single combined modular correction term D for a binary sum of all operand values based on leading bits of the sum value S. A processor performs a modular addition of S and D resulting in a modular sum of said plurality of said first operand values.
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.