Efficient squaring with loop equalization in arithmetic logic units
AssigneeCryptography Research, Inc.
InventorMichael Alexander Hamburg
Life of this patent
Estimating the term…
Abstract
Aspects of the present disclosure describe a method and a system to support execution of the method to perform a cryptographic operation involving identifying an N-word number, X=XN−1 . . . X1Xo, to be squared, performing a first loop comprising M first loop iterations, wherein M is a largest integer not exceeding (N+1)/2, each of the M first loop iterations comprising a second loop that comprises a plurality of second loop iterations, wherein an iteration m of the second loop that is within an iteration j of the first loop comprises computing a product Xa*Xb of a word Xa and a word Xb, wherein a+b=2j+m, j≥0 and m≥0, and wherein all second loops have an equal number of second loop iterations.
Claims20
A method to perform a cryptographic operation, the method comprising:
- receiving an input data associated with one or more messages communicated between two or more nodes associated with a common cryptography system;
- identifying an N-word number, X=XN−1 . . . X1 X0, associated with the input data;
- computing, by a processing device, a square of the N-word number X, by performing a first loop comprising M first loop iterations, wherein M is a largest integer number not exceeding (N+1)/2, each of the M first loop iterations comprising a second loop that comprises a plurality of second loop iterations, wherein an iteration m of the second loop that is within an iteration j of the first loop comprises computing a product Xa*Xb of a word Xa and a word Xb, wherein a+b=2j+m, j≥0 and m≥0, and wherein all second loops have an equal number of second loop iterations;
- and
- obtaining, using the computed square of the N-word number X, an output data;
- and
- performing the cryptographic operation comprising at least one of:
- obtaining, using the output data, a cryptographic key, and processing, using the cryptographic key to obtain at least one of:
- (i) a ciphertext for the one or more messages or (ii) a plaintext for the one or more messages,
- or
- obtaining, using the output data, a digital signature authentication of the one or more messages.
A system comprising:
- a first memory device to store an N-word number X=XN−1 . . . X1 X0, associated with an input data, wherein the input data is associated with one or more messages communicated between two or more nodes associated with a common cryptography system;
- and
- an arithmetic logic unit (ALU) communicatively coupled to the first memory device, wherein the ALU is to:
- receive words of the N-word number X,
- compute a square of the N-word number X by performing a first loop comprising M first loop iterations, wherein M is a largest integer number not exceeding (N+1)/2, each of the M first loop iterations comprising a second loop that comprises a plurality of second loop iterations, wherein during an iteration m of the second loop that is within an iteration j of the first loop the ALU is to compute a product Xa*Xb of a word Xa and a word Xb, wherein a+b=2j+m, wherein j≥0 and m≥0, and wherein all second loops have an equal number of second loop iterations;
- obtain, using the computed square of the N-word number X, an output data;
- and
- perform the cryptographic operation comprising at least one of:
- obtain, using the output data, a cryptographic key, and process, using the cryptographic key to obtain at least one of:
- (i) a ciphertext for the one or more messages or (ii) a plaintext for the one or more messages,
- or
- obtain, using the output data, a digital signature authentication of the one or more messages.
A non-transitory computer-readable medium storing instruction thereon, wherein the instructions, when executed by a processing device performing a cryptographic operation, cause the processing device to:
- receive an input data associated with one or more messages communicated between two or more nodes associated with a common cryptography system;
- identify an N-word number, X=XN−1 . . . X1 X0, associated with the input data;
- compute a square of the N-word number X by performing a first loop comprising M first loop iterations, wherein M is a largest integer number not exceeding (N+1)/2, each of the M first loop iterations comprising a second loop that comprises a plurality of second loop iterations, wherein an iteration m of the second loop that is within an iteration j of the first loop comprises computing a product Xa*Xb of a word Xa and a word Xb, wherein a+b=2j+m, wherein j≥0 and m≥0, and wherein all second loops have an equal number of second loop iterations;
- and
- obtain, using the computed square of the N-word number X, an output data, and;
- perform the cryptographic operation comprising at least one of:
- obtain, using the output data, a cryptographic key, and process, using the cryptographic key to obtain at least one of:
- (i) a ciphertext for the one or more messages or (ii) a plaintext for the one or more messages,
- or
- obtain, using the output data, a digital signature authentication of the one or more messages.
Dependencies are inferred from the claim text.