Methods and devices for fixed execution flow multiplier recoding and scalar multiplication

Patent metadata

Field	Value
Publication number	US-9531531-B2
Application number	US-201514705686-A
Country	US
Kind code	B2
Filing date	May 6, 2015
Priority date	May 6, 2015
Publication date	Dec 27, 2016
Grant date	Dec 27, 2016

Abstract

One feature pertains to an electronic device that includes a memory circuit and a processing circuit. The processing circuit computes a scalar multiplication output Z where Z=k·P by receiving an input multiplier k and a base P, and adds a modifier s to the input multiplier k to generate k′. The processing circuit also computes an intermediate scalar multiplication output Z′ where Z′=k′·P by using a digit expansion of k′ that includes a sequence of digits k i belonging to a digit set D. Additionally, the processing circuit subtracts s·P from Z′ to obtain the scalar multiplication output Z if k′ is odd or subtracts (s+1)·P from Z′ to obtain the scalar multiplication output Z if k′ is even. The scalar multiplier output Z may be used in a cryptographic security algorithm to secure data.

First claim

What is claimed is:

1. An electronic device comprising:
a memory circuit; and
a processing circuit communicatively coupled to the memory circuit, the processing circuit adapted to compute a scalar multiplication output Z where Z=k·P by:
receive an input multiplier k and a base P;
add a modifier s to the input multiplier k to generate k′, wherein the same modifier s is added to the input multiplier k to generate k′ regardless of whether k is odd or even;
compute an intermediate scalar multiplication output Z′ where Z′=k′·P by using a digit expansion of k′ that includes a sequence of digits k i belonging to a digit set D; and
subtract s·P from Z′ to obtain the scalar multiplication output Z if k′ is odd or subtract (s+1)·P from Z′ to obtain the scalar multiplication output Z if k′ is even; and

wherein the scalar multiplier output Z is used in a cryptographic security algorithm to secure data.

2. The electronic device of claim 1 , wherein the digit expansion of k′ is based on k′=Σ i=0 l k i 2 wi −c, and the sequence of digits k i are from the digit set D={±1, ±3, ±5, . . . , ±2 w −1}, w is an integer value greater than or equal to one (1), and c equals 0 or 1.

3. The electronic device of claim 2 , wherein the modifier s equals one (1) or two (2).

4. The electronic device of claim 1 , wherein compute the intermediate scalar multiplication output Z′ includes:
initialize a carry value c equal to zero (0);
determine, for a window length value w equal to or greater than one (1), a digit sequence (k l , k l-1 , . . . , k 1 , k 0 ) by performing for all integer values i=l down to i=0 operations:
k i :=k i −2 w c;
if k i is even:
k i :=k i +1;
c:=1;

else:
c:=0.

5. The electronic device of claim 4 , wherein compute the intermediate scalar multiplication output Z′ further includes one of:
initialize Z′ as Z′=k l ·P; and
perform, for i=l−1 down to i=0, operations:
Z′=2·Z′ a number of times equal to w;
Z′=Z′+k i ·P; or

initialize Z′ as Z′=0; and
perform, for i=l down to i=0, operations:
Z′=2·Z′ a number of times equal to w;
Z′=Z′+k i ·P.

6. The electronic device of claim 5 , wherein the processing circuit is further adapted to:
precompute at least one of a plurality of values d·P and/or −d·P for all values |d| where |d|εD; and
store the precomputed plurality of values d·P and/or −d·P in the memory circuit.

7. The electronic device of claim 6 , wherein Z′=Z′+k i ·P is performed by retrieving k i ·P from the precomputed plurality of values d·P and/or −d·P stored in the memory circuit.

8. The electronic device of claim 1 , wherein a digit set D includes a plurality of integer values {d 0 , d 1 , . . . , d n }, and the processing circuit is further adapted to:
precompute and store a plurality of values d i ·P for i=0 to i=n.

9. The electronic device of claim 8 , wherein the processing circuit is further adapted to:
precompute and store m·P for at least one integer intermediate value m where m is greater than a smallest value in the digit set D and less than a greatest value in the digit set D, and wherein the modifier s and s+1 are both in the set {d 0 , d 1 , . . . , d n }∪{m}.

10. The electronic device of claim 1 , wherein compute the intermediate scalar multiplication output Z′ includes:
initialize a carry value c equal to zero (0); and
determine, for a window length value w equal to or greater than one (1), a digit sequence (k l , k l-1 , . . . , k 1 , k 0 ) by performing for all integer values i=l down to i=0 operations:
k i :=k i −2 w c;
c:=1−LSB(k i );
k i =k i +c.

11. A method for securing data in an electronic device by computing a scalar multiplication output Z where Z=k·P, the method comprising:
receiving an input multiplier k and a base P;
adding, via a processing circuit, a modifier s to the input multiplier k to generate k′, wherein the same modifier s is added to the input multiplier k to generate k′ regardless of whether k is odd or even;
computing, via the processing circuit, an intermediate scalar multiplication output Z′ where Z′=k′·P by using a digit expansion of k′ that includes a sequence of digits k i belonging to a digit set D; and
subtracting, via the processing circuit, s·P from Z′ to obtain the scalar multiplication output Z if k′ is odd or subtracting (s+1)·P from Z′ to obtain the scalar multiplication output Z if k′ is even; and
wherein the scalar multiplier output Z is configured to be used in a cryptographic security algorithm to secure the data.

12. The method of claim 11 , wherein the digit expansion of k′ is based on k′=Σ i=0 l k i 2 wi −c, and the sequence of digits k i are from the digit set D={±1, ±3, ±5, . . . , ±2 w −1}, w is an integer value greater than or equal to one (1), and c equals 0 or 1.

13. The method of claim 12 , wherein the modifier s equals one (1) or two (2).

14. The method of claim 11 , wherein computing the intermediate scalar multiplication output Z′ includes:
initializing a carry value c equal to zero (0);
determining, for a window length value w equal to or greater than one (1), a digit sequence (k l , k l-1 , . . . , k 1 , k 0 ) by performing for all integer values i=l down to i=0 operations:
k i :=k i −2 w c;
if k i is even:
k i :=k i +1;
c:=1;

else:
c:=0.

15. The method of claim 14 , wherein computing the intermediate scalar multiplication output Z′ further includes one of:
initializing Z′ as Z′=k l ·P; and
performing, for i=l−1 down to i=0, operations:
Z′=2·Z′ a number of times equal to w;
Z′=Z′+P; or

initializing Z′ as Z′=0; and
performing, for i=l down to i=0, operations:
Z′=2·Z′ a number of times equal to w;
Z′=Z′+k i ·P.

16. The method of claim 15 , wherein the method further comprises:
precomputing at least one of a plurality of values d·P and/or −d·P for all values |d| where |d| εD; and
storing the precomputed plurality of values d·P and/or −d·P in a memory circuit.

17. The method of claim 16 , wherein Z′=Z′+k i ·P is performed by:
retrieving k i ·P from the precomputed plurality of values d·P and/or −d·P stored in the memory circuit.

18. The method of claim 11 , wherein a digit set D includes a plurality of integer values {d 0 , d 1 , . . . , d n }, and the method further comprises:
precomputing and storing a plurality of values d i ·P for i=0 to i=n.

19. The method of claim 18 , further comprising:
precomputing and storing m·P for at least one integer intermediate value m where m is greater than a smallest value in the digit set D and less than a greatest value in the digit set D, and wherein the modifier s and s+1 are both in the set {d 0 , d 1 , . . . , d n }∪{m}.

20. The method of claim 11 , wherein computing the intermediate scalar multiplication output Z′ includes:
initializing a carry value c equal to zero (0); and
determining, for a window length value w equal to or greater than one (1), a digit sequence (k l , k l-1 , . . . , k 1 , k 0 ) by performing for all integer values i=l down to i=0 operations:
k i :=k i −2 w c;
c:=1−LSB(k i );
k i =k i +c.

21. An electronic device adapted to secure data in an electronic device by computing a scalar multiplication output Z where Z=k·P, the electronic device comprising:
means for receiving an input multiplier k and a base P;
means for adding a modifier s to the input multiplier k to generate k′, wherein the same modifier s is added to the input multiplier k to generate k′ regardless of whether k is odd or even;
means for computing an intermediate scalar multiplicat

Assignees

• Qualcomm Inc

Inventors

• Avanzi Roberto
• Jacobson David

Classifications

• G06F7/4812 Primary

  Complex multiplication · CPC title

• H04L9/0693 Primary

  Electricity · mapped topic

• H04L9/003 Primary

  for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA] · CPC title

• H04L9/004

  for fault attacks · CPC title

• H04L9/3066

  involving algebraic varieties, e.g. elliptic or hyper-elliptic curves · CPC title