# US 8,542,820 B2 · Apparatus for calculating a result of a scalar multiplication

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,542,820 B2
- Document ID: US8542820B2
- Status: Granted
- Kind: B2
- Application number: 12/366,222
- Filed: 2009-02-05
- Published: 2010-08-05
- Granted: 2013-09-24
- Earliest claimed: 2009-02-05
- Assignees: Infineon Technologies AG
- Applicants: Wieland Fischer
- Inventors: Wieland Fischer
- Web page: https://patentgrep.com/patent/US8542820B2

## CPC

- G06F 7/57: Arithmetic logic units [ALU], i.e. arrangements or devices for performing two or more of the operations covered by groups G06F7/483 – G06F7/556 or for performing logical operations {(G06F7/49, G06F7/491 take precedence)}
- G06F 7/725: {over elliptic curves}
- H04L 9/003: {for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA]}
- H04L 9/004: {for fault attacks}
- H04L 9/3066: {involving algebraic varieties, e.g. elliptic or hyper-elliptic curves}
- G06F 2207/7223: Randomisation as countermeasure against side channel attacks
- G06F 2207/7261: Uniform execution, e.g. avoiding jumps, or using formulae with the same power profile
- H04L 2209/046: of operations, operands or results of the operations
- H04L 2209/08: Randomization, e.g. dummy operations or using noise
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

An apparatus for calculating a result of a scalar multiplication of a reference number with a reference point on an elliptic curve comprises a point selector and a processor. The point selector is configured to select randomly or pseudo-randomly an auxiliary point on the elliptic curve. The processor is configured to calculate the result of the scalar multiplication with a double-and-always-add process using the auxiliary point.

## Claims

### Claim 1

An apparatus for calculating a result of a scalar multiplication of a reference number with a reference point on an elliptic curve, comprising:
a point selector configured to select randomly or pseudo-randomly an auxiliary point on the elliptic curve, wherein the reference point and the auxiliary point are different points on the elliptic curve,
wherein the point selector is configured to select the auxiliary point independent from the reference point or wherein the auxiliary point is selected based on a mixing function applied to the reference point; and
a processor configured to calculate the result of the scalar multiplication with a double-and-always-add process using the auxiliary point, wherein the processor is configured to calculate the result of the scalar multiplication based on a loop, which, per execution, operates on an intermediate point, and configured to set the intermediate point equal to the auxiliary point prior to a first execution of the loop, wherein the loop is executed N-times, wherein N is a number of bits comprised by the reference number in a binary representation, wherein the processor is configured to calculate the result of a subtraction of the auxiliary point from the intermediate point, wherein the subtraction is a part of the loop.

### Claim 2

An apparatus for calculating a result of a scalar multiplication of a reference number with a reference point on an elliptic curve, comprising:
a point selector configured to select randomly or pseudo-randomly an auxiliary point on the elliptic curve, wherein the reference point and the auxiliary point are different points on the elliptic curve,
wherein the point selector is configured to select the auxiliary point independent from the reference point or wherein the auxiliary point is selected based on a mixing function applied to the reference point; and
a processor configured to calculate the result of the scalar multiplication with a double-and-always-add process using the auxiliary point, wherein the processor is configured to calculate the result of the scalar multiplication based on a loop, which, per execution, operates on an intermediate point, and configured to set the intermediate point equal to the auxiliary point prior to a first execution of the loop, wherein the loop is executed N-times, wherein N is a number of bits comprised by the reference number in a binary representation, wherein the processor is configured to calculate the result of the scalar multiplication based on an addition of the intermediate point with itself and a subtraction of the auxiliary point from the intermediate point.

### Claim 3

An apparatus for calculating a result of a scalar multiplication of a reference number with a reference point on an elliptic curve, comprising:
a point selector configured to select a random or pseudo-random auxiliary point on the elliptic curve, wherein the reference point and the auxiliary point are different points on the elliptic curve, wherein the auxiliary point is selected independent from the reference point; and
a processor configured to set an intermediate point equal to the auxiliary point and configured to execute a loop, wherein the loop is executed N-times, wherein N is a number of bits comprised by the reference number in a binary representation, and wherein the processor is configured to calculating the result of the scalar multiplication based on a subtraction of the auxiliary point from the intermediate point or an addition of the negative auxiliary point and the intermediate point.

### Claim 4

An apparatus for calculating a result of a scalar multiplication of a reference number with a reference point on an elliptic curve, comprising:
a point selector configured to select randomly or pseudo-randomly an auxiliary point on the elliptic curve, wherein the reference point and the auxiliary point are different points on the elliptic curve,
wherein the point selector is configured to select the auxiliary point independent from the reference point or wherein the auxiliary point is selected based on a mixing function applied to the reference point; and
wherein a processor is configured to calculate the result of the scalar multiplication with a double-and-always-add process using the auxiliary point and based on the following algorithm:
choose random point B on curve;
Q:= B;
for (i:=n−1) to 0 by −1 do
Q←2*Q
if (di=1) then
Q←Q+(P−B)
else
Q←Q+(−B)
end
end
Q←Q+(−B)
return Q,
wherein Q is an intermediate point, B is the auxiliary point, i is a counter, di is a value of a current bit of the reference number and P is the reference point.

### Claim 5

A method for calculating a result of a scalar multiplication of a reference number with a reference point on an elliptic curve the method comprising:
selecting randomly or pseudo-randomly an auxiliary point on the elliptic curve, wherein the reference point and the auxiliary point are different points on the elliptic curve,
wherein the auxiliary point is selected independent from the reference point or wherein the auxiliary point is selected based on a mixing function applied to the reference point; and
calculating, by a processor, the result of the scalar multiplication with a double-and-always-add process using the auxiliary point, wherein the calculation of the result of the scalar multiplication is performed based on a loop, which, per execution, operates on an intermediate point, and the intermediate point is set equal to the auxiliary point prior to a first execution of the loop, wherein the loop is executed N-times, wherein N is a number of bits comprised by the reference number in a binary representation,
wherein, as part of the loop, the result of a subtraction of the auxiliary point from the intermediate point is computed or, wherein the result of the scalar multiplication is based on an addition of the intermediate point with itself and a subtraction of the auxiliary point from the intermediate point.

### Claim 6

A non-transitory machine-readable carrier having stored thereon a computer program for performing the method for calculating a result of a scalar multiplication of a reference number with a reference point on an elliptic curve, comprising:
selecting randomly or pseudo-randomly an auxiliary point on the elliptic curve, wherein the reference point and the auxiliary point are different points on the elliptic curve,
wherein the auxiliary point is selected independent from the reference point or wherein the auxiliary point is selected based on a mixing function applied to the reference point; and
calculating the result of the scalar multiplication with a double-and-always-add process using the auxiliary point, wherein the calculation of the result of the scalar multiplication is performed based on a loop, which, per execution, operates on an intermediate point, and the intermediate point is set equal to the auxiliary point prior to a first execution of the loop, wherein the loop is executed N-times, wherein N is a number of bits comprised by the reference number in a binary representation,
wherein, as part of the loop, the result of a subtraction of the auxiliary point from the intermediate point is computed or, wherein the result of the scalar multiplication is based on an addition of the intermediate point with itself and a subtraction of the auxiliary point from the intermediate point.

### Claim 7

A method for calculating a result of a scalar multiplication of a reference number with a reference point on an elliptic curve, the method comprising:
selecting a random or pseudo-random auxiliary point on the elliptic curve, wherein the reference point and the auxiliary point are different points on the elliptic curve, wherein the auxiliary point is selected independent from the reference point or wherein the auxiliary point is selected based on a mixing function applied to the reference point; and
setting an intermediate point equal to the auxiliary point; and
executing a loop, wherein the loop is executed N-times, wherein N is a number of bits comprised by the reference number in a binary representation, and
calculating, by a processor, the result of the scalar multiplication based on a subtraction of the auxiliary point from the intermediate point or an addition of the negative auxiliary point and the intermediate point.

### Claim 8

A non-transitory machine-readable carrier having stored a computer program with a program code for performing a method for calculating a result of a scalar multiplication of a reference number with a reference point on an elliptic curve, comprising:
selecting a random or pseudo-random auxiliary point on the elliptic curve, wherein the reference point and the auxiliary point are different points on the elliptic curve, wherein the auxiliary point is selected independent from the reference point or wherein the auxiliary point is selected based on a mixing function applied to the reference point; and
setting an intermediate point equal to the auxiliary point; and
executing a loop, wherein the loop is executed N-times, wherein N is a number of bits comprised by the reference number in a binary representation, and calculating the result of the scalar multiplication based on a subtraction of the auxiliary point from the intermediate point or an addition of the negative auxiliary point and the intermediate point.

### Claim 9

An apparatus for calculating a result of a scalar multiplication of a reference number with a reference point on an elliptic curve, comprising:
a point selector configured to select randomly or pseudo-randomly an auxiliary point on the elliptic curve, wherein the reference point and the auxiliary point are different points on the elliptic curve,
wherein the point selector is configured to select the auxiliary point independent from the reference point or wherein the auxiliary point is selected based on a mixing function applied to the reference point; and
a processor configured to calculate the result of the scalar multiplication with a double-and-always-add process using the auxiliary point, wherein the processor is configured to set an intermediate point equal to the auxiliary point and configured to execute a loop, wherein the loop is executed N-times, wherein N is a number of bits comprised by the reference number in a binary representation, and wherein the processor is configured to calculating the result of the scalar multiplication based on a subtraction of the auxiliary point from the intermediate point or an addition of the negative auxiliary point and the intermediate point.