Method and system for protecting against side channel attacks when performing cryptographic operations

A cryptographic system for decrypting an encrypted message M using a key, d, by iteratively performing a binary group operation [op] on a digital quantity G to produce a decrypted message D(M), said quantity G being derived from said encrypted message M, said system comprising:

• a plurality of first storage locations storing program code;
• one or more second storage locations storing a window width W;
• one or more third storage locations storing a value for said key, d;
• a plurality of first working storage locations for storing a corresponding plurality of values Gi;
• a plurality of second working storage locations for storing a corresponding plurality of registers positions;
• a plurality of accumulators for storing variable values A and B;
• and
• a processor communicating with said storage locations and said working storage locations, said processor having an input/output channel for input of said encrypted message M and output of said decrypted message D(M), said processor executing said program code to decrypt said message M by:
• expressing said key d in base 2W was d0 d1 . . . dk-1;
• determining said values Gi, for 0≦i≦k−1, such that Gi=[op]2iW G and storing said determined values of Gi in said first working storage locations;
• for values j such that 1≦j≦2W−1, establishing a table of said register positions [j] such that for each value of j, register position [j] stores values of i such that di=j;
• setting said values A=I, and B=I, where I is an identity element for said binary operation [op];
• setting a value j=2W−1;
• determining if register position [j] is empty;
• if register position [j] is not empty, selecting a next of said values of i stored in said register position [j], deleting said next value of i from said register position [j], setting said value B=said value B[op]Gi, where i=said next value, and repeating until register position [j] is empty;
• setting said value A=A[op]B;
• setting said index j=j−1;
• and
• if said index j≧0, returning to determine if register position [j] is empty;
• otherwise
• returning said value A;
• where said value A=[op]dG;
• and
• outputting as said decrypted message D(M) said returned value A.

A cryptographic system for generating a public key of a public/private key pair, the public key being derived from a private key, d, taken as an integer value, of the key pair by iteratively performing a binary group operation [op] on a digital representation of a group element G, said system comprising:

• a plurality of first storage locations storing program code;
• one or more second storage locations storing a window width W;
• one or more third storage locations storing the private key d;
• a plurality of first working storage locations for storing a corresponding plurality of values Gi
• a plurality of second working storage locations for storing a corresponding plurality of registers positions [j];
• a plurality of accumulators for storing variable values A and B;
• and
• a processor communicating with said storage locations and said working storage locations, said processor having an input/output channel for input of said private key and output of said public key, said processor executing said program code to generate said public key by:
• determining a series of k digital values di, where index i has values ranging from 0 to k−1, where said series represents said private key in base 2W;
• determining k digital values Gi, such that Gi=[op]2iW G;
• setting said variable value A and said variable value B equal to an identity element for said binary operation;
• for values j such that 1≦j≦2W−1, establishing a table of registers [j] such that, for each of said values of j, register position [j] stores each of said values of i such that di=j;
• set said index j=2W−1;
• determining if register position [j] is empty;
• if register position [j] is not empty, selecting a next of said values of i stored in said register position [j], deleting said next value of i from said register position [j], setting said value B=said value B[op]Gi, where i=said next value, and repeating until register position [j] is empty;
• setting said value A=A[op]B;
• setting said index j=j−1;
• and
• if said index j≧0, returning to determine if register position [j] is empty;
• otherwise
• returning said public key as said value A, where said value A=[op]dG.

A cryptographic system for creating a digital signature for a message M using a key, d, by iteratively performing a binary group operation [op] on a digital quantity G to produce said digital signature sig(M), said quantity G being derived from said message M, said system comprising:

• a plurality of first storage locations storing program code;
• one or more second storage locations storing a window width W;
• one or more third storage locations storing a value for said key, d;
• a plurality of first working storage locations for storing a corresponding plurality of values Gi;
• a plurality of second working storage locations for storing a corresponding plurality of register positions [j];
• a plurality of accumulators for storing variable values A and B;
• and
• a processor communicating with said storage locations and said working storage locations, said processor having an input/output channel for input of said message M and output of said digital signature sig(M), said processor executing said program code to create said digital signature by:
• expressing said key d in base 2W was d0 d1 . . . dk-1;
• determining said values Gi, for 0≦i≦k−1, such that Gi=[op]2iW G and storing said determined values of Gi in said first working storage locations;
• for values j such that 1≦j≦2W−1, establishing a table of said register positions [j] such that for each value of j, register position [j] stores values of i such that di=j;
• setting said values A=I, and B=I, where I is an identity element for said binary operation [op];
• setting a value j=2W−1;
• and then
• for all of said values i stored in register position [j], updating said value B=B[op]Gi;
• updating said value A=A[op]B
• setting said value j=j−1;
• and
• if said value j>0 returning to update said value=B[op]Gi;
• otherwise
• returning said value A;
• where said value A=[op]dG;
• and
• outputting as said digital signature sig(M) said returned value A.