Interleaved scalar multiplication for elliptic curve cryptography

1. A method for performing scalar multiplication between a scalar and a parameter, the method comprising:

obtaining, by a device comprising a memory storing instructions and a processor in communication with the memory, a bit-number of a scalar, wherein the bit-number of the scalar is a number of bits in the scalar in a binary format;

factorizing, by the device, the bit-number of the scalar into a product of a plurality of factors, the plurality of factors comprising s, d, and w, wherein s, d, and w are positive integers;

generating, by the device, d tables based on a parameter, each table comprising N entries, wherein N is a positive integer and a function of w;

for each iteration of s iterations:

multiplying, by the device, a result by two,

constructing, by the device, an index for each table from w bits in the scalar in the binary format,

selecting, by the device, a value from each table based on the constructed index for each table, and

adding, by the device, the value selected from each table to the result and starting next iteration; and

in response to completing the s iterations, determining, by the device, the result for a scalar multiplication between the scalar and the parameter.

2. The method according to claim 1 , wherein:

N is equal to 2{circumflex over ( )}w.

3. The method according to claim 1 , wherein:

an entry in the table with a table index of j is generated according to:

( b _0+ b _1*2{circumflex over ( )}64+ . . . + b _( w− 1)*2{circumflex over ( )}(( w− 1)* d*s ))*2{circumflex over ( )}( j*s )* P,

wherein b_0, b_1, . . . , b_(w−1) are one-bit binary numbers, {b_0, b_1, . . . , b_(w−1)) is an entry index for the entry, j is an integer between 0 and 3, inclusive, and P is the parameter.

4. The method according to claim 1 , further comprising:

before starting a first iteration of the s iterations, setting the result as zero.

5. The method according to claim 1 , wherein:

the scalar comprises n bits {k_0, k_1, . . . , k_(n−1)} in a bit-level little-endian order, n being the bit-number of the scalar;

i corresponds to an iteration index among the s iterations, i being an integer between 0 and (s−1), inclusive; and

j corresponds to a table index among the d tables, j being an integer between 0 and (d−1), inclusive.

6. The method according to claim 5 , wherein the constructing the index for each table from w bits in the scalar in the binary format comprises:

constructing the index for each table from the w bits, k_(i+j*s+h*d*s), in the scalar in the bit-level little-endian order, h being an integer between 0 and (w−1), inclusive.

7. The method according to claim 5 , wherein:

the constructed index comprises w bits of

{ k _( i+j*s ), k _( i+j*s+d*s ), . . . , k _( i+j*s +( w− 1)* d*s )}.

8. The method according to claim 5 , wherein the selecting the value from each table based on the constructed index for each table comprises:

selecting the value from each table by a constant-time table look-up process based on the constructed index for each table.

9. The method according to claim 1 , wherein:

in response to the bit-number of the scalar being 256, s is 16, d is 4, and w is 4; and

an entry in the table with a table index of j is generated according to:

( b _0+ b _1*2{circumflex over ( )}64+ b _2*2{circumflex over ( )}128+ b _3*2{circumflex over ( )}192)*2{circumflex over ( )}( j* 16)* P,

wherein b_0, b_1, b_2, and b_3 are one-bit binary numbers, {b_0, b_1, b_2, b_3} is an entry index for the entry, j being an integer between 0 and 3, inclusive, and P is the parameter.

10. The method according to claim 9 , wherein:

an entry in a first table is generated according to

( b _0+ b _1*2{circumflex over ( )}64+ b _2*2{circumflex over ( )}128+ b _3*2{circumflex over ( )}192)* P;

an entry in a second table is generated according to

( b _0+ b _1*2{circumflex over ( )}64+ b _2*2{circumflex over ( )}128+ b _3*2{circumflex over ( )}192)*2{circumflex over ( )}16* P;

an entry in a third table is generated according to

( b _0+ b _1*2{circumflex over ( )}64+ b _2*2{circumflex over ( )}128+ b _3*2{circumflex over ( )}192)*2{circumflex over ( )}32* P ; and

an entry in a fourth table is generated according to

( b _0+ b _1*2{circumflex over ( )}64+ b _2*2{circumflex over ( )}128+ b _3*2{circumflex over ( )}192)*2{circumflex over ( )}48* P.

11. The method according to claim 1 , wherein:

in response to the bit-number of the scalar being 256, s is 16, d is 4, and w is 4;

the scalar is represented by n bits {k_0, k_1, . . . k_255} in a bit-level little-endian order;

i corresponds to an iteration index among the 16 iterations, i being an integer between 0 and 15, inclusive;

j corresponds to a table index among the 4 tables, j being an integer between 0 and 3, inclusive; and

the constructed index comprises 4 bits of

{ k _( i+j* 16), k _( i+j* 16+64), k _( i+j* 16+128), k _( i+j* 16+192)}.

12. The method according to claim 1 , wherein:

in response to the bit-number of the scalar being 384, s is 24, d is 4, and w is 4.

13. The method according to claim 1 , wherein:

in response to the bit-number of the scalar being 512, s is 32, d is 4, and w is 4.

14. An apparatus for performing scalar multiplication between a scalar and a parameter, the apparatus comprising:

a memory storing instructions; and

a processor in communication with the memory, wherein, when the processor executes the instructions, the processor is configured to cause the apparatus to:

obtain a bit-number of a scalar, wherein the bit-number of the scalar is a number of bits in the scalar in a binary format;

factorize the bit-number of the scalar into a product of a plurality of factors, the plurality of factors comprising s, d, and w, wherein s, d, and w are positive integers;

generate d tables based on a parameter, each table comprising N entries, wherein N is a positive integer and a function of w;

for each iteration of s iterations:

multiply a result by two,

construct an index for each table from w bits in the scalar in the binary format,

select a value from each table based on the constructed index for each table, and

add the value selected from each table to the result and start next iteration; and

in response to completing the s iterations, determine the result for a scalar multiplication between the scalar and the parameter.

15. The apparatus according to claim 14 , wherein:

an entry in the table with a table index of j is generated according to:

( b _0+ b _1*2{circumflex over ( )}64+ . . . + b _( w− 1)*2{circumflex over ( )}(( w− 1)* d*s ))*2{circumflex over ( )}( j*s )* P,

wherein b_0, b_1, . . . , b_(w−1) are one-bit binary numbers, {b_0, b_1, . . . , b_(w−1)) is an entry index for the entry, j is an integer between 0 and 3, inclusive, and P is the parameter.

16. The apparatus according to claim 14 , wherein:

the scalar comprises n bits {k_0, k_1, . . . , k_(n−1)} in a bit-level little-endian order, n being the bit-number of the scalar;

i corresponds to an iteration index among the s iterations, i being an integer between 0 and (s−1), inclusive;

j corresponds to a table index among the d tables, j being an integer between 0 and (d−1), inclusive; and

the constructed index comprises w bits of

{ k _( i+j*s ), k _( i+j*s+d*s ), . . . , k _( i+j*s +( w− 1)* d*s )}.

17. The apparatus according to claim 14 , wherein:

in response to the bit-number of the scalar being 256, s is 16, d is 4, and w is 4; and

an entry in the table with a table index of j is generated according to:

( b _0+ b _1*2{circumflex over ( )}64+ b _2*2{circumflex over ( )}128+ b _3*2{circumflex over ( )}192)*2{circumflex over ( )}( j* 16)* P,

wherein b_0, b_1, b_2, and b_3 are one-bit binary numbers, {b_0, b_1, b_2, b_3} is an entry index for the entry, j being an integer between 0 and 3, inclusive, and P is the parameter.

18. A non-transitory computer readable storage medium storing instructions, wherein, when the instructions are executed by a processor, the instructions are configured to cause the processor to:

obtain a bit-number of a scalar, wherein the bit-number of the scalar is a number of bits in the scalar in a binary format;

factorize the bit-number of the scalar into a product of a plurality of factors, the plurality of factors comprising s, d, and w, wherein s, d, and w are positive integers;

generate d tables based on a parameter, each table comprising N entries, wherein N is a positive integer and a function of w;

for each iteration of s iterations:

multiply a result by two,

construct an index for each table from w bits in the scalar in the binary format,

select a value from each table based on the constructed index for each table, and

add the value selected from each table to the result and start next iteration; and

in response to completing the s iterations, determine the result for a scalar multiplication between the scalar and the parameter.

19. The non-transitory computer readable storage medium according to claim 18 , wherein:

an entry in the table with a table index of j is generated according to:

( b _0+ b _1*2{circumflex over ( )}64+ . . . + b _( w− 1)*2{circumflex over ( )}(( w− 1)* d*s ))*2{circumflex over ( )}( j*s )* P,

wherein b_0, b_1, . . . , b_(w−1) are one-bit binary numbers, {b_0, b_1, . . . , b_(w−1)) is an entry index for the entry, j is an integer between 0 and 3, inclusive, and P is the parameter.

20. The non-transitory computer readable storage medium according to claim 18 , wherein:

the scalar comprises n bits {k_0, k_1, . . . , k_(n−1)} in a bit-level little-endian order, n being the bit-number of the scalar;

i corresponds to an iteration index among the s iterations, i being an integer between 0 and (s−1), inclusive;

j corresponds to a table index among the d tables, j being an integer between 0 and (d−1), inclusive; and

the constructed index comprises w bits of

{ k _( i+j*s ), k _( i+j*s+d*s ), . . . , k _( i+j*s +( w− 1)* d*s )}.