Back to results
US 12,657,007 B2Granted
Sign-based partial reduction of modular operations in arithmetic logic units
AssigneeCryptography Research, Inc.
InventorMichael Alexander Hamburg
Life of this patent
Estimating the term…
Abstract
Aspects of the present disclosure involve a method and a system to execute the method to perform a cryptographic operation involving a modulo N computation, the method comprising loading a first integer number and a second integer number, wherein the first integer number and the second integer number are within an interval of 2N integer numbers, and performing an arithmetic operation involving the first integer number and the second integer number, wherein the arithmetic operation is to produce a third integer number, and wherein the arithmetic operation comprises a shifting operation to ensure that the third integer number is inside the interval of 2N integer numbers.
Claims20
A method to perform a modulo-N cryptographic operation, the method comprising:
- identifying, by a processing device, one or more n-bit inputs into the modulo-N cryptographic operation, wherein n is equal or greater than 256, and wherein the one or more n-bit inputs are within a first interval of N integer numbers;
- computing, by the processing device and based on the one or more n-bit inputs into the modulo-N cryptographic operation, a first integer number and a second integer number that are within a second interval of 2N integer numbers, wherein the second interval of 2N integer numbers comprises a first subinterval of N integer numbers and a second subinterval of N integer numbers, wherein each of the first integer number and the second integer number comprises a respective sign bit indicative of a subinterval associated with a respective integer number, and wherein each of the first integer number and the second integer number comprises a plurality of words;
- performing, using an arithmetic logic unit (ALU) configured to process word-size inputs, an arithmetic operation comprising a plurality of cycles to obtain a third integer number, wherein at least one cycle of the plurality of cycles comprises:
- loading, from a first memory device, a word of the plurality of words of at least one of the first integer number or the second integer number,
- reading, using a read port of a dual-port second memory device, an accumulator word from the dual-port second memory device,
- computing, by the ALU and based at least on the word and the accumulator word, an updated accumulator word, and
- writing, using a write port of the dual-port second memory device, a previously computed accumulator word in the dual-port second memory device, wherein the reading and the writing are performed concurrently during a single cycle of the ALU;
- and
- wherein performing the arithmetic operation further comprises:
- processing, by an XOR gate of the ALU, a first sign bit of the first integer number and a second sign bit of the second integer number to determine a selector bit;
- applying a shifting operation, selected based on the selector bit, to the third integer number;
- and
- wherein the method further comprises:
- obtaining an output of the modulo-N cryptographic operation using the third integer number, wherein the modulo-N cryptographic operation comprises one or more of:
- an encryption of the one or more n-bit inputs,
- a decryption of the one or more n-bit inputs, or
- a digital signature for the one or more n-bit inputs.
14 more elements
A system to perform a modulo-N cryptographic operation, the system comprising:
- a first memory device;
- a dual-port second memory device;
- and
- a processing device to:
- identify one or more n-bit inputs into the modulo-N cryptographic operation, wherein n is equal or greater than 256, and wherein the one or more n-bit inputs are within a first interval of N integer numbers;
- store, in the first memory device, a first integer number and a second integer number computed based on the one or more n-bit inputs into the modulo-N cryptographic operation, wherein the first integer number and the second integer number are within a second interval of 2N integer numbers, wherein the second interval of 2N integer numbers comprises a first subinterval of N integer numbers and a second subinterval of N integer numbers, wherein each of the first integer number and the second integer number comprises a respective sign bit indicative of a subinterval associated with a respective integer number, and wherein each of the first integer number and the second integer number comprises a plurality of words;
- and
- perform, using an arithmetic logic unit (ALU) configured to process word-size inputs, an arithmetic operation comprising a plurality of cycles to obtain a third integer number, wherein at least one cycle of the plurality of cycles comprises:
- loading, from the first memory device, a word of the plurality of words of at least one of the first integer number or the second integer number,
- reading, using a read port of the dual-port second memory device, an accumulator word from the dual-port second memory device,
- computing, by the ALU and based at least on the word and the accumulator word, an updated accumulator word, and
- writing, using a write port of the dual-port second memory device, a previously computed accumulator word in the dual-port second memory device, wherein the reading and the writing are performed concurrently during a single cycle of the ALU, and
- wherein the arithmetic operation comprises:
- processing, by an XOR gate of the ALU, a first sign bit of the first integer number and a second sign bit of the second integer number to determine a selector bit;
- and
- applying a shifting operation, selected based on the selector bit, to the third integer number;
- and
- wherein the processing device is further to:
- obtain an output of the modulo-N cryptographic operation using the third integer number, wherein the modulo-N cryptographic operation comprises one or more of:
- an encryption of the one or more n-bit inputs,
- a decryption of the one or more n-bit inputs, or
- a digital signature for the one or more n-bit inputs.
19 more elements
A non-transitory computer-readable medium storing instructions thereon, wherein the instructions, when executed by a processing device performing a modulo-N cryptographic operation, cause the processing device to:
- identify one or more n-bit inputs into the modulo-N cryptographic operation, wherein n is equal or greater than 256, and wherein the one or more n-bit inputs are within a first interval of N integer numbers;
- compute, based on the one or more n-bit inputs into the modulo-N cryptographic operation, a first integer number and a second integer number that are within a second interval of 2N integer numbers, wherein the second interval of 2N integer numbers comprises a first subinterval of N integer numbers and a second subinterval of N integer numbers, wherein each of the first integer number and the second integer number comprises a respective sign bit indicative of a subinterval associated with a respective integer number, and wherein each of the first integer number and the second integer number comprises a plurality of words;
- perform, using an arithmetic logic unit (ALU) configured to process word-size inputs, an arithmetic operation comprising a plurality of cycles to obtain a third integer number, wherein at least one cycle of the plurality of cycles comprises:
- loading, from a first memory device, a word of the plurality of words of at least one of the first integer number or the second integer number,
- reading, using a read port of a dual-port second memory device, an accumulator word from the dual-port second memory device,
- computing, by the ALU and based at least on the word and the accumulator word, an updated accumulator word, and
- writing, using a write port of the dual-port second memory device, a previously computed accumulator word in the dual-port second memory device, wherein the reading and the writing are performed concurrently during a single cycle of the ALU;
- and
- wherein performing the arithmetic operation further comprises:
- processing, by an XOR gate of the ALU, a first sign bit of the first integer number and a second sign bit of the second integer number to determine a selector bit;
- and
- applying a shifting operation, selected based on the selector bit, to the third integer number;
- and
- wherein the processing device is further to:
- obtain an output of the modulo-N cryptographic operation using the third integer number, wherein the modulo-N cryptographic operation comprises one or more of:
- an encryption of the one or more n-bit inputs,
- a decryption of the one or more n-bit inputs, or
- a digital signature for the one or more n-bit inputs.
15 more elements
Dependencies are inferred from the claim text.