Back to results
US 2023/0198739 A1Published application
Correcting the almost binary extended greatest common denominator (gcd)
AssigneeCryptography Research, Inc.
InventorMichael Tunstall
Life of this patent
Estimating the term…
Abstract
Computing devices, methods, and systems for corrections to the “almost” binary extended GCD in a cryptographic operation of a cryptographic process are disclosed. Exemplary implementations may: receive, from a cryptographic process, a command to compute a binary extended greatest common denominator of a first input value and a second input value for a cryptographic operation; compute, by a binary extended GCD algorithm, the binary extended GCD using a multiplication with an inverse of two, instead of a division by two, to obtain a first output value; compute, by the binary extended GCD algorithm, a second output value and a third output value; and return, to the cryptographic process, the first output value, the second output value, and the third output value.
Claims20
A computing system comprising:
- a memory device to store instructions of a binary extended greatest common denominator (GCD) algorithm;
- and
- a processing device coupled to the memory device, wherein the instructions, when executed by the processing device, perform the following operations comprising:
- receive, from a cryptographic process, a command to compute a binary extended GCD of a first input value (x) and a second input value (y) for a cryptographic operation;
- compute the binary extended GCD of the first input value (x) and the second input value (y) using the binary extended GCD algorithm to obtain a first output value (α), wherein the binary extended GCD algorithm computes the binary extended GCD using a multiplication with an inverse of two instead of a division by two, wherein the binary extended GCD algorithm computes a second output value (u) and a third output value (v), wherein the second output value is a first integer (α) and the third output value is a second integer (b), wherein a sum of a first product of the first integer and the first input value (x) and a second product of the second integer and the second input value (y) is equal to the first output value;
- and
- return, to the cryptographic process, the first output value (α), the second output value (u), and the third output value (v).
4 more elements
A method comprising:
- receiving, from a cryptographic process, a command to compute a binary extended greatest common denominator (GCD) of a first input value (x) and a second input value (y) for a cryptographic operation;
- computing, by a binary extended GCD algorithm, the binary extended GCD using a multiplication with an inverse of two, instead of a division by two, to obtain a first output value (α);
- computing, by the binary extended GCD algorithm, a second output value (u) and a third output value (v), wherein the second output value is a first integer (α) and the third output value is a second integer (b), wherein a sum of a first product of the first integer and the first input value (x) and a second product of the second integer and the second input value (y) is equal to the first output value;
- and
- returning, to the cryptographic process, the first output value (α), the second output value (u) , and the third output value (v).
2 more elements
A computing system comprising:
- a memory device to store instructions of a binary extended greatest common denominator (GCD) algorithm;
- a first processor coupled to the memory device;
- and
- a second processor coupled to the first processor and the memory device, wherein the instructions, when executed by the first processor, cause the first processor to:
- compute, as part of a cryptographic operation, a binary extended GCD of a first input value (x) and a second input value (y) using the binary extended GCD algorithm to obtain a first output value (α), a second output value (u), and a third output value (v), wherein the binary extended GCD algorithm computes the binary extended GCD using a multiplication with an inverse of two instead of a division by two, wherein the second output value is a first integer (α) and the third output value is a second integer (b), wherein a sum of a first product of the first integer and the first input value (x) and a second product of the second integer and the second input value (y) is equal to the first output value;
- track a first number of times a first identity is applied by the binary extended GCD algorithm until a condition is met, wherein the condition comprises a first variable (α) being equal to a second variable (β) or the second variable (β) being equal to zero;
- multiply the first output value (α) by two to the power of the first number to obtain the binary extended GCD;
- issue one or more commands to the second processor to compute, using a Montgomery multiplication, a product of the first variable (α) and the second variable (β) modulus n, where n is an input modulus value specified by the cryptographic operation;
- receive the second output value (u) and the third output value (v) from the second processor;
- and
- output the first output value (α), the second output value (u), and the third output value (v).
8 more elements
Dependencies are inferred from the claim text.