Patent Publication Number: US-2023155828-A1

Title: Reduction and conversion of a scalar to a tau-adic representation

Description:
BACKGROUND 
     Technical Field 
     The present disclosure relates generally to the domain of cryptography and in particular to a method and device for implementing a cryptography operation based on elliptic curve cryptography. 
     Description of the Related Art 
     Elliptic curve cryptography (ECC) is well adapted to public key cryptography methods since it enables a cryptographic key of decreased size to be used. For example, elliptic curve cryptography can be used to implement an encryption, key-exchange, key-agreement, digital signature or authentication operation. 
     Furthermore, the use of a Koblitz curve enables the speed of some cryptographic operations, in particular the multiplication of a point by a scalar, to be increased. However, to be efficient, the scalar should generally be converted to a particular representation before being used in cryptographic operations on Koblitz curve. 
     It would be desirable to make the process of conversion faster and/or to render the value of the scalar difficult to detect during the execution, by an electronic device, of cryptographic operations involving it. 
     BRIEF SUMMARY 
     In an embodiment, a method comprises performing a cryptographic operation, and protecting the performing of the cryptographic operation. The performing the cryptographic operation and the protecting including execution, by a cryptographic circuit, of an algorithm applied to a scalar to generate an output vector, of length l+n, having digits d 0 , . . . , d l+n−1 , the algorithm comprising a number of iterations i, each iteration i taking an input data value (ρ), initially equal to said scalar and an input vector of length c, having digits d′ i , . . . , d′ i+c−1 , where for each j∈{i, . . . , i+c−1}, the digit d′ j  is determined according to 
     
       
         
           
             
               d 
               j 
               ′ 
             
             = 
             
               { 
               
                 
                   
                     
                       
                         
                           d 
                           j 
                         
                         ⁢ 
                             
                         if 
                         ⁢ 
                             
                         j 
                       
                       &lt; 
                       l 
                     
                   
                 
                 
                   
                     
                       
                         
                           d 
                           
                             j 
                             - 
                             m 
                           
                         
                         ⁢ 
                             
                         otherwise 
                       
                       , 
                     
                   
                 
               
             
           
         
       
     
     where m, l and n are positive integers and each iteration i comprises:
         a) calculating a first intermediate data value (u) by a first operation applied, modulo τ, to the first input data (ρ) and to the input vector, wherein τ is a complex number;   b) updating the value of the first input data value (ρ) by a second operation applied to the first input data value, to the input vector, to the first intermediate data value (u), and to τ; and   c) setting a digit (d i ) at position i of the output vector equal to the first intermediate data value (u),       

     wherein the number of iterations is determined by the cryptographic circuit based on a stop criterion. 
     In an embodiment, a non-transitory computer readable medium&#39;s contents cause a cryptographic circuit to perform a method, the method comprising: performing a cryptographic operation; and protecting the performing of the cryptographic operation. The performing the cryptographic operation and the protecting including: executing an algorithm applied to a scalar to generate an output vector, of length l+n, having digits d 0 , . . . , d l+n−1 , the algorithm comprising a number of iterations i, each iteration i taking an input data value (ρ), initially equal to said scalar and an input vector of length c, having digits d′ i , . . . , d′ i+c−1 , where for each j∈{i, . . . , i+c−1}, the digit d′ j  is determined according to 
     
       
         
           
             
               d 
               j 
               ′ 
             
             = 
             
               { 
               
                 
                   
                     
                       
                         
                           d 
                           j 
                         
                         ⁢ 
                             
                         if 
                         ⁢ 
                             
                         j 
                       
                       &lt; 
                       l 
                     
                   
                 
                 
                   
                     
                       
                         
                           d 
                           
                             j 
                             - 
                             m 
                           
                         
                         ⁢ 
                             
                         otherwise 
                       
                       , 
                     
                   
                 
               
             
           
         
       
     
     where m, l and n are positive integers and each iteration i comprises:
         a) calculating a first intermediate data value (u) by a first operation applied, modulo τ, to the first input data (ρ) and to the input vector, wherein τ is a complex number;   b) updating the value of the first input data value (ρ) by a second operation applied to the first input data value, to the input vector, to the first intermediate data value (u), and to τ; and   c) setting a digit (d i ) at position i of the output vector equal to the first intermediate data value (u),       

     wherein the number of iterations is determined by the cryptographic circuit based on a stop criterion. 
     In an embodiment, a device comprises a memory and cryptographic circuitry coupled to the memory. The cryptographic circuitry, in operation, performs a cryptographic operation and protects the performing of the cryptographic operation, the performing the cryptographic operation and the protecting including: executing an algorithm applied to a scalar to generate an output vector, of length l+n, having digits d 0 , . . . , d l+n−1 , the algorithm comprising a number of iterations i, each iteration i taking an input data value (ρ), initially equal to said scalar and an input vector of length c, having digits d′ i , . . . , d′ i+c−1 , where for each j∈{i, . . . , i+c−1}, the digit d′ j  is determined according to 
     
       
         
           
             
               d 
               j 
               ′ 
             
             = 
             
               { 
               
                 
                   
                     
                       
                         
                           d 
                           j 
                         
                         ⁢ 
                             
                         if 
                         ⁢ 
                             
                         j 
                       
                       &lt; 
                       l 
                     
                   
                 
                 
                   
                     
                       
                         
                           d 
                           
                             j 
                             - 
                             m 
                           
                         
                         ⁢ 
                             
                         otherwise 
                       
                       , 
                     
                   
                 
               
             
           
         
       
     
     where m, l and n are positive integers and each iteration i comprises:
         a) calculating a first intermediate data value (u) by a first operation applied, modulo τ, to the first input data (ρ) and to the input vector, wherein τ is a complex number;   b) updating the value of the first input data value (ρ) by a second operation applied to the first input data value, to the input vector, to the first intermediate data value (u), and to τ; and   c) setting a digit (d i ) at position i of the output vector equal to the first intermediate data value (u),       

     wherein the number of iterations is determined by the cryptographic circuit based on a stop criterion. 
     In an embodiment, a system comprises a host processor and cryptographic circuitry coupled to the host processor. The cryptographic circuitry, in operation, performs a cryptographic operation and protects the performing of the cryptographic operation, the performing the cryptographic operation and the protecting including: executing an algorithm applied to a scalar to generate an output vector, of length l+n, having digits d 0 , . . . , d l+n−1 , the algorithm comprising a number of iterations i, each iteration i taking an input data value (ρ), initially equal to said scalar and an input vector of length c, having digits d′ i , . . . , d′ i+c−1 , where for each j∈{i, . . . , i+c−1}, the digit d′ j  is determined according to 
     
       
         
           
             
               d 
               j 
               ′ 
             
             = 
             
               { 
               
                 
                   
                     
                       
                         
                           d 
                           j 
                         
                         ⁢ 
                             
                         if 
                         ⁢ 
                             
                         j 
                       
                       &lt; 
                       l 
                     
                   
                 
                 
                   
                     
                       
                         
                           d 
                           
                             j 
                             - 
                             m 
                           
                         
                         ⁢ 
                             
                         otherwise 
                       
                       , 
                     
                   
                 
               
             
           
         
       
     
     where m, l and n are positive integers and each iteration i comprises:
         a) calculating a first intermediate data value (u) by a first operation applied, modulo τ, to the first input data (ρ) and to the input vector, wherein τ is a complex number;   b) updating the value of the first input data value (ρ) by a second operation applied to the first input data value, to the input vector, to the first intermediate data value (u), and to τ; and   c) setting a digit (d i ) at position i of the output vector equal to the first intermediate data value (u),       

     wherein the number of iterations is determined by the cryptographic circuit based on a stop criterion. 
    
    
     
       BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS 
       The foregoing features and advantages, as well as others, will be described in detail in the following description of specific embodiments given by way of illustration and not limitation with reference to the accompanying drawings, in which: 
         FIG.  1    schematically illustrates an example of an electronic device according to an embodiment of the present disclosure; 
         FIG.  2    is a flow diagram illustrating operations of a method of performing scalar conversion according to an embodiment; 
         FIG.  3    illustrates an example of an initial state of an l-digit value used in the method of  FIG.  2   ; 
         FIG.  4    is a flow diagram illustrating operations of a method of performing scalar conversion according to an embodiment; 
         FIG.  5    illustrates an example of an initial state of an l-digit value used in the method of  FIG.  4   ; and 
         FIG.  6    is a flow diagram illustrating an example of a cryptographic method according to an embodiment of the present disclosure. 
     
    
    
     DESCRIPTION OF EMBODIMENTS 
     Like features have been designated by like references in the various figures. In particular, the structural and/or functional features that are common among the various embodiments may have the same references and may dispose identical structural, dimensional and material properties, unless the context indicates otherwise. 
     For the sake of clarity, only the operations and elements that are useful for an understanding of the embodiments described herein have been illustrated and described in detail. In particular, the cryptographic operation of multiplication of a point on an elliptic curve by a scalar (scalar multiplication), the properties of Koblitz curves, and various choices of scalar representations are not described in detail. 
     Unless indicated otherwise, when reference is made to two elements connected together, this signifies a direct connection without any intermediate elements other than conductors, and when reference is made to two elements coupled together, this signifies that these two elements can be connected or they can be coupled via one or more other elements. 
     In the following disclosure, unless indicated otherwise, when reference is made to absolute positional qualifiers, such as the terms “front.” “back,” “top,” “bottom,” “left,” “right,” etc., or to relative positional qualifiers, such as the terms “above,” “below,” “higher,” “lower,” etc., or to qualifiers of orientation, such as “horizontal,” “vertical,”, etc., reference is made to the orientation shown in the figures. 
     Unless specified otherwise, the expressions “around,” “approximately,” “substantially” and “in the order of” signify within 10%, and within 5%, etc. 
       FIG.  1    schematically illustrates a device  100  according to an embodiment. Device  100  is for example a computer, mobile telephone, or an integrated circuit card. 
     Device  100  for example comprises a main processor  102  (MAIN PROCESSOR), which is for example a host processor of device  100 , and a cryptographic coprocessor  104  (CRYPTOGRAPHIC COPROCESSOR). Device  100  further comprises a memory  106  (MEMORY) storing instructions  108  (INSTRUCTIONS) for controlling the main processor  102  and/or the cryptographic coprocessor  104 . A communication interface  110  (COMMUNICATIONS INTERFACE) is for example coupled to the main processor  102 , and for example allows wireless communications, for example, over a LAN (“Local Area Network,” not shown). As illustrated, host processor  102  and cryptographic coprocessor  104  have respective internal memories  103 ,  105 , such as registers or cache memories, which may be used during the performance one or more of the methods described herein, alone or in combination with the memory  106 . For example, an application executing on the main or host processor  102  may be stored in whole or part in memory  103 . The application may initiate the performance of a cryptographic operation on the cryptographic processor  104 , and the cryptographic operation may be performed using the memory  105 , or combinations of the memory  106  and the memory  105 . 
     Device  100 , and particularly cryptographic coprocessor  104 , is for example adapted to perform elliptic curve cryptographic operations. In particular, cryptographic coprocessor  104  is for example configured to perform a multiplication by a scalar k of a point P belonging to a Koblitz curve E having the following form: 
         E :={( x,y )∈ K×K:y   2   +xy=x   3   +ax   2 +1}  Math 1
 
     with a∈{0, 1} and where K is a binary finite field of the form K=GF(2 m ), where m is a prime number. 
     The operation of multiplication by a scalar is for example used during the ciphering of data, scalar k being the cipher key, and is for example performed by execution of an algorithm of “double-and-add type” or a variant thereof, such as “double-and-add-or-subtract” and generalizations to windowed multiplication. In the “double-and-add-or-subtract” algorithm, the digits of the scalar k can take values 1, −1 or 0. A “double” operation is done on the accumulator for each digit, and for each nonzero digit, point P is added to the accumulator when the digit is 1, or subtracted from the accumulator when the digit is −1. In a windowed multiplication, digits belong to a larger set of values, and the scalar multiplication is performed similarly to double-and-add-or-subtract, except that each addition or subtraction involves, instead of P, a small pre-computed multiple of P, which depends on the value of the digit. This type of algorithm is of iterative type. Each iteration for example involves modifying the value of an elliptic curve point called the accumulator, depending on the digits of scalar k. In one example, the digits of the scalar k are bits, and each iteration involves processing a corresponding one of the bits of scalar k from the most significant bit to the least significant bit, or inversely, by performing an operation on the point according to the value of the read bit. In the left-to-right double-and-add multiplication method, in other words double-and-add multiplication performed starting with the most significant digit and going towards the least significant digit, a so-called double operation is performed on the accumulator, whatever the value of the bit that is read, and is followed by a so-called add operation adding P into the accumulator only in the case where the read bit is non-null. 
     In the case of a Koblitz curve, the double operation is generally replaced with a Frobenius operation, that consists in squaring the coordinates of a point. A Frobenius operation has the advantage over a regular double operation in that it is faster and less expensive to execute. 
     However, to use the Frobenius operation, the scalar k should to be converted to a τ-adic representation, where τ is a complex number equal to (μ−i√{square root over (7)})/2, where μ is equal to (−1) 1−a , and a is the coefficient of the Koblitz curve E above. In the τ-adic representation, the scalar k is represented as a sequence of digits d i  such that: 
     
       
         
           
             
               
                 
                   
                     k 
                     = 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           0 
                         
                         
                           M 
                           - 
                           1 
                         
                       
                       
                         
                           d 
                           i 
                         
                         ⁢ 
                         
                           τ 
                           i 
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   Math 
                   ⁢ 
                       
                   2 
                 
               
             
           
         
       
     
     where the coefficients d i  belong for example to {0, 1} or to {−1, 0, 1}. The integer M is the length of the scalar k under τ-adic form. Scalar k can either be an integer, or a so-called τ-adic integer of the form a+bτ where a and b are integers. A difficulty is that the τ-adic representation of an integer is about twice as long as its binary form. As long representations are less efficient, scalar k is generally reduced before being converted into the τ-adic form. The reduction of the scalar k comprises replacing k by a smaller complex number ρ that is equivalent to the scalar k modulo τ m −1, where, as mentioned above, m defines through K=GF(2 m ) the finite field K underlying the Koblitz curve. Then, for any point P of the considered Koblitz curve, kP=ρP, where the multiplication of P by a complex number τ is defined by applying the Frobenius endomorphism to the point P. 
     A drawback of existing methods for performing the reduction, and τ-adic conversion, of the scalar k is that they tend to be relatively complex and time consuming. Moreover, in certain cases, when the size of the scalar k is relatively high, there is a need to perform several reduction operations before the conversion operation if a short representation is needed. 
     In the present disclosure, the following symbols are defined:
         k is the scalar to be converted, that may either be an integer or a τ-adic integer; and   n is a non-negative integer.       

     According to embodiments described herein, the scalar k is converted into the τ-adic representation composed of the group of digits (d 0 , . . . , d m+n−1 ) where each digit belongs to a set D and possibly according to a predicate or relationship C(d i , . . . , d i+c−1 ) that holds for groups of c consecutive digits after the end of the conversion. 
     According to some embodiments, the scalar k is converted to τ-adic non-adjacent form (τNAF), in which the digits belong to D={−1,0,1} and in which c=2 and the product of two consecutive digits is equal to zero. In other words, C(d i , d i+1 )⇔(d i ×d i+1 )=0. In that case, the τ-adic conversion can be accomplished, for example, with n=4. 
       FIG.  2    is a flowchart illustrating operations of a method of scalar reduction and conversion according to an embodiment. The method of  FIG.  2    is for example implemented by the cryptographic coprocessor  104  of the electronic device  100 . For example, the method of  FIG.  2    is used as one step in a method of elliptic curve cryptography such as an encryption, key-exchange, key-agreement, digital signature or authentication operation. 
     In an operation  200  (INITIALIZATION ρ=k; i=0; (d 0 , . . . , d m+n−1 )) a current value i is initialized, for example to zero. A vector (d 0 , . . . , d m+n−1 ) of length m+n, is also for example initialized. 
       FIG.  3    illustrates an example of the initialization of the accumulator (d 0 , . . . , d m+n ). In this example, all coefficients (d 0 , . . . , d m+n−1 ) are initialized at zero. 
     In  FIG.  3   , only the m first coefficients (d 0 , . . . , d m−1 ) of the accumulator are represented. The n last coefficients (d m , . . . , d m+n−1 ) of the accumulator are for example initialized to zero and are only updated at the end of the algorithm of  FIG.  2   . Indeed, the n last coefficients (d m , . . . , d m+n−1 ) are not provided as input data values in the iterations of the algorithm. 
     Returning to  FIG.  2   , the operation  200  for example further comprises the initialization of a current value ρ to zero. 
     The process for example continues with a sequence of operations (OP SEQ) composed, for example, of operations  201  to  203 , after operation  200 . 
     In the operation  201  (u←OP 1 (ρ; d′ i ; . . . ; d′ i+c−1 ; τ)), an intermediate value u is computed as a function of the input data values and of the complex number τ according to: 
     
       
         
           
             
               
                 
                   
                     u 
                     = 
                     
                       
                         ( 
                         
                           ρ 
                           + 
                           
                             d 
                             i 
                             ′ 
                           
                         
                         ) 
                       
                       ⁢ 
                       
                         
                           mod 
                           
                             
                               d 
                               
                                 i 
                                 + 
                                 1 
                               
                               ′ 
                             
                             ; 
                                 
                             … 
                                 
                             ; 
                             
                               d 
                               
                                 i 
                                 + 
                                 c 
                                 - 
                                 1 
                               
                               ′ 
                             
                           
                         
                         ( 
                         τ 
                         ) 
                       
                     
                   
                   , 
                 
               
               
                 
                   Math 
                   ⁢ 
                       
                   3 
                 
               
             
           
         
       
     
     where mod returns a valid digit u belonging to set D, such that ρ+d′ i −u is divisible by τ. The subscript to mod indicates that the exact choice of u may depend on digits d′ i+1  to d′ i+c−1 . Each digit d′ i  corresponds to a cyclic indexation of the m lower digits of the accumulator (d 0 , . . . , d m+n−1 ). In other words, if the index i is lower than m, then d′ i =d i , otherwise d′ i =d i−m . For example, to obtain a τNAF representation, 
     
       
         
           
             mod 
             
               d 
               
                 i 
                 + 
                 1 
               
               ′ 
             
           
         
       
     
     τ is defined as follows for all τ-adic integers represented as a+bτ, where a and b are integers: 
     
       
         
           
             
               
                 
                   
                     
                       ( 
                       
                         a 
                         + 
                         
                           b 
                           ⁢ 
                           τ 
                         
                       
                       ) 
                     
                     ⁢ 
                     
                       mod 
                       
                         d 
                         
                           i 
                           + 
                           1 
                         
                         ′ 
                       
                     
                     ⁢ 
                     τ 
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               
                                 0 
                                 ⁢ 
                                     
                                 if 
                                 ⁢ 
                                     
                                 a 
                               
                               ≡ 
                               
                                 0 
                                 ⁢ 
                                     
                                 
                                   ( 
                                   
                                     mod 
                                     ⁢ 
                                         
                                     2 
                                   
                                   ) 
                                 
                               
                             
                           
                         
                         
                           
                             
                               
                                 
                                   1 
                                   ⁢ 
                                       
                                   if 
                                   ⁢ 
                                       
                                   a 
                                 
                                 + 
                                 
                                   2 
                                   ⁢ 
                                   
                                     ( 
                                     
                                       b 
                                       + 
                                       
                                         d 
                                         
                                           i 
                                           + 
                                           1 
                                         
                                         ′ 
                                       
                                     
                                     ) 
                                   
                                 
                               
                               ≡ 
                               
                                 1 
                                 ⁢ 
                                     
                                 
                                   ( 
                                   
                                     mod 
                                     ⁢ 
                                         
                                     4 
                                   
                                   ) 
                                 
                               
                             
                           
                         
                         
                           
                             
                               
                                 - 
                                 1 
                               
                               ⁢ 
                                   
                               otherwise 
                             
                           
                         
                       
                       . 
                     
                   
                 
               
               
                 
                   Math 
                   ⁢ 
                       
                   4 
                 
               
             
           
         
       
     
     In other words, the intermediate value u is for example equal to a remainder in the Euclidean division of (ρ+d i ) by the complex number τ. This remainder is not necessarily minimal and the choice of the exact remainder for example depends on the rest of the vector (d′ i+1 , . . . , d′ i+c−1 ). 
     In the operation  202  (ρ←OP 2 (ρ; d i ; u; τ)), after operation  201 , the current value ρ is for example updated to a new current value ρ resulting from the division of (ρ+d i −u) by the complex number τ. 
     In the operation  203  (d i ←u), after operation  202 , the intermediate value u is for example stored into digit d i . 
     In an operation  204  (STOP CRITERION?), the cryptographic coprocessor  104  for example checks whether a stop criterion has been reached. If the stop criterion has not been reached (branch N), the current value i is updated, (bloc  205 , i=i+1 mod m), to the value i+1 modulo m. The method then returns to the operation  201 . In other words, if in operation  205  the current value i is less than or equal to m−2, then it is updated to i+1. However, if the current value i is equal to m−1, the rank i of the position is reset to zero. Thus, the algorithm loops on updating digits d 0  to d m−1  one after another until the stop criterion is reached. 
     The stop criterion is for example based on the value of ρ and on the index i. In one example, when the expected representation of the converted scalar k is the τNAF representation and the number of most significant digits is n=4, the stop criterion is for example: 
       ρ=0 or (|ρ|≤2 and  i=m− 1),  Math 5
 
     where |ρ| is modulus of the value ρ considered as a usual complex number. 
     Once the stop criterion has been reached (branch Y), the process for example ends in an operation  206  (END). At this stage, the values of the n most significant digits are still the initial values, for example zero. During the operation  206 , the n last coefficients (d m , . . . , d m+n−1 ) of the accumulator are for example set to the representation of current value ρ, for example by executing operations  201  to  203  for each of the n digits in order. The accumulator (d 0 , . . . , d m+n−1 ) then for example provides the output data of the method, wherein the coefficients d 0  to d m+3  represent the digits of the reduced and τ-adic converted form of the scalar k: 
     
       
         
           
             
               
                 
                   k 
                   ≡ 
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         0 
                       
                       
                         m 
                         + 
                         n 
                         - 
                         1 
                       
                     
                     
                       
                         d 
                         i 
                       
                       ⁢ 
                       
                         
                           
                             τ 
                             i 
                           
                           [ 
                           
                             
                               τ 
                               m 
                             
                             - 
                             1 
                           
                           ] 
                         
                         . 
                       
                     
                   
                 
               
               
                 
                   Math 
                   ⁢ 
                       
                   6 
                 
               
             
           
         
       
     
     In another example, we set n=0 and the method outputs the reduced scalar in a hybrid form by outputting both the coefficients d 0  to d m+1  and the final value of ρ, so that 
     
       
         
           
             
               
                 
                   
                     k 
                     ≡ 
                     
                       ρ 
                       + 
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             0 
                           
                           
                             m 
                             - 
                             1 
                           
                         
                         
                           
                             d 
                             i 
                           
                           ⁢ 
                           
                             
                               τ 
                               i 
                             
                             [ 
                             
                               
                                 τ 
                                 m 
                               
                               - 
                               1 
                             
                             ] 
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   Math 
                   ⁢ 
                       
                   7 
                 
               
             
           
         
       
     
     where the size of ρ is relatively small, and bounded by the stop criterion. For example, when the expected representation of the converted scalar k is the τNAF representation and the number of most significant digits is n=4, ρ has a modulus less than or equal to 2. 
       FIG.  4    is another flowchart illustrating operation of a method of implementation of scalar conversion according to an embodiment. This method is for example implemented by the cryptographic coprocessor  104  of the electronic device  100 . 
     The method of  FIG.  4    has operations similar to those of the method of  FIG.  2   , and like operations have been labelled with like reference numerals. 
     A difference in the method of  FIG.  4    with respect to the method of  FIG.  2    is that the accumulator is a vector (d 0 , . . . , d l+n−1 ) of length l+n, where l=m+l′ is an integer greater than the integer m with l′ being an integer greater than 0. To avoid confusion with the number 1, integer l will be represented as integer L in addition to being represented as integer L. 
     Furthermore, in the embodiment of  FIG.  4   , the output digits of the accumulator represent the digits of the scalar k after a τ-adic reduction and conversion, where the reduction is deliberately not optimal. In other words, since the conversion is correct, the method outputs the τ-adic representation of a τ-adic integer ρ such that ρ=k(mod τ m −1), but the reduction being not optimal means that ρ is not necessarily the smallest τ-adic integer respecting that equivalence. 
     In an operation  400  (INITIALIZATION ρ=0; i=0; (d 0 , . . . , d l+n−1 )) a current value i is initialized, for example to zero. The vector (d 0 , . . . , d l+n−1 ) is also initialized, for example to the τ-adic representation of a multiple of τ m −1. 
     An example of initialization of the accumulator (d 0 , . . . , d l+n−1 ) is illustrated in  FIG.  5   . This example is valid when the set of digits D is symmetric around 0, meaning that for any digit d∈D, its opposite −d also belongs to the set D. 
     In  FIG.  5   , only the l first coefficients (d 0 , . . . , d l−1 ) of the accumulator are represented. The n last coefficients (d l , . . . , d l+n−1 ) of the accumulator are for example initialized to zero and are only updated at the end of the algorithm of  FIG.  4   . Indeed, the n last coefficients (d l , . . . , d l+n−1 ) are not provided as input data values in the iterations of the algorithm. 
     The l first coefficients (d 0 , d l , . . . , d l′−1 , d l′ , . . . , d m−1 , d m , . . . , d l−1 ) of the accumulator are initialized to encode the digits of a random or pseudo-random multiple of τ m −1 in τ-adic form. Indeed, the multiplication of any point P of the considered Koblitz curve by the scalar k gives the same result as the multiplication of the point P by the scalar k added with a multiple of τ m −1. In other words, for any point P belonging to Koblitz curve and for any integer or τ-adic integer r 
         k·P =( k+r (τ m −1))· P.   Math 8
 
     Adding a random multiple of τ m −1 to the scalar k allows device  100  to perform the scalar multiplication using a pseudo-random multiplier, while maintaining the expected result for a multiplication by the scalar k. This makes attacks against the value of the scalar k by exploiting a power-consumption analysis of the value of the scalar k more difficult to succeed. 
     For this purpose, given l′ random coefficients (r 0 , . . . , r l′−1 ), for example with values in D, the value r=Σ i=0   l′ r i τ i  represents a random τ-adic integer. These l′ coefficients (r 0 , . . . , r l′−1 ) are then chosen to respect the predicate C(d i , . . . , d i+c−1 ), for example if the output is expected in a τNAF, the product of two consecutive coefficients in (r 0 , . . . , r l′−1 ) is null. Then, a multiple of r by τ m −1 for example has the following τ-adic form: 
         r (τ m −1)=Σ i=0   l′−1   r   i τ m+i −Σ i=0   l′−1   r   i τ i .  Math 9
 
     Initializing the first l coefficients (d 0 , . . . , d l−1 ) of the accumulator to encode a random multiple of τ m −1 in τ-adic form corresponds to choosing the value of l′ digits (r 0 , . . . , r l′−1 ) at random, for example belonging to D, and to setting: 
         d   j   =−r   j  and  d   j+m   =r   j  for  j∈{ 0, . . . , l′− 1} and 
         d   j =0 for  j∈{l′, . . . ,m− 1}.  Math 10
 
     After operation  400 , the method illustrated in  FIG.  4    continues with a sequence of operations (OP SEQ)  401 ,  202  and  203  where operations  202  and  203  are described above in relation to  FIG.  2   . 
     Operation  401  (u←OP 1 (ρ; d′ i , . . . , d′ i+c−1 ; τ) is similar to operation  201 , except that digits d′ i  to d′ i+c−1  are an extract from the l lower digits of the accumulator (d 0 , . . . , d l+n−1 ). If the index i is strictly smaller than l, then d′ i =d i , otherwise d′ i =d i−m . 
     After operation  203 , the method continues with the verification operation  204 , also described in relation to  FIG.  2   . In one example, if the stop criterion is not reached (branch N), another verification (bloc  405 , i≤l−2?) is performed, for example by the cryptographic coprocessor  104 . If the current value i is less than or equal to the value l−2 (branch Y), then the current value i is set to the value i+1 in an operation  407  (i=i+1). If the current value i is greater than the value l−1 (branch N), the current value i is set to the value i+1−m in an operation  407 ′ (i=i+1−m), and a subsequent loop is started. After operation  407 , the method for example returns to the operation  201 . 
     After operation  407 ′, an operation  408  ((d l′−c+1 , . . . , d l′−1 , ρ)←CORRECT(d l′−c+1 , . . . , d l′ , ρ)) is executed. Operation  408  conditionally modifies the c−1 digits of (d 0 , . . . , d l−1 ) directly before index l′, depending on the value of ρ. It consists in inputting (d l′−c+1 , . . . , d l′ , ρ) to a function CORRECτ, described hereafter, and writing the vector that is output by the function into (d l′−c+1 , . . . , d l′−1 , ρ). This optional correction is for example used when a predicate is to be verified by all groups of c consecutive digits. After operation  408 , the method for example returns to operation  201 . 
     The CORRECT function respects the three following properties:
         (1) the value Σ i=l′−c+1   l′−1 d i τ i +ρτl′ is kept unchanged by the application of the function;   (2) the digits d i  output by the function all belong to the set D;   (3) the digits d i  and the new value of ρ output by the function are such that the next execution of operations  201  to  203  generates a valid digit d l , ∈D, such that predicate C(d l′−c+1 , . . . , d l′ ) holds.       

     In one example, the output of the algorithm is expected to be in the τNAF representation, which corresponds to D={−1,0,1}, c=2 and C(d i , d i+1 )⇔(d i ×d i+1 =0), for all index i. In that case, function CORRECT for example returns (d l′−1 , ρ) unchanged when either d l′ +ρ≡0(mod τ) or d l′−1 =0, and returns 
     
       
         
           
             ( 
             
               
                 - 
                 
                   d 
                   
                     
                       l 
                       ⁢ 
                       ′ 
                     
                     - 
                     1 
                   
                 
               
               , 
               
                 ρ 
                 + 
                 
                   
                     2 
                     τ 
                   
                   ⁢ 
                   
                     d 
                     
                       
                         l 
                         ⁢ 
                         ′ 
                       
                       - 
                       1 
                     
                   
                 
               
             
             ) 
           
         
       
     
     otherwise. 
     Once the stop criterion has been reached, the process for example ends in the operation  206  (END). At this stage, the values of the n last coefficients of the accumulator are still the initial values, for example zero. During operation  206 , the n last coefficients (d l , . . . , d l+n−1 ) of the accumulator are for example set to the current value ρ, as already described in relation to  FIG.  2   . The output data of the method is the accumulator (d l , . . . , d l+n−1 ), with coefficients d 0  to d l+n−1  representing the digits of the reduced and τ-adic converted form of the value k: 
         k≡Σ   i=0   l+3   d   i τ i ·[τ m −1].  Math 11
 
     In this embodiment, the coefficients d 0  to d l′−c  are for example only taken once as input data values, and processed. Indeed, once each of the coefficients d 0  to d l−1  has been provided as an input data value once, only the last m+c−1 coefficients (d l′−c+1 , . . . , d l−1 ) of the accumulator are taken as input data values, one after the other, in each new loop of the algorithm, until the stop criterion is reached. 
     The embodiments described in relation with  FIGS.  2  and  4    allow to reduce and to convert the scalar k, or an equivalent of scalar k, into τ-adic representation, one digit after another, using a same sequence of operations, based on the equivalence of τ i  and τ i mod(m)  modulo τ m −1. 
     The result of the method of  FIG.  2    and/or of  FIG.  4    can for example be used in the scalar multiplication of a point on a Koblitz curve, as will now be described in more detail with reference to  FIG.  6   . Such scalar multiplication can for example be used as part of elliptic-curve-cryptography operations. 
       FIG.  6    illustrates an embodiment of performing a cryptographic operation and protecting the performing of the cryptographic operation. In particular,  FIG.  6    is a flow diagram illustrating an example of a scalar multiplication according to an embodiment of the present disclosure. 
     For example, the method illustrated in the flow diagram of  FIG.  6    is implemented by the electronic device  100  of  FIG.  1   . 
     For example, in an operation  600  (RECEIPT OF k AND P), the electronic device  100  receives, for example by the communication interface  110 , data values corresponding to an integer or a τ-adic integer k and to encoded data or plaintext to be encoded. In another example, the scalar k is already stored in the memory  106  and only the point is received via the communication interface  110 . The cryptographic key k and the point are then for example sent to the cryptographic coprocessor  104 . 
     In an operation  601  (REDUCTION AND τ-ADIC CONVERSION), after operation  600 , the cryptographic coprocessor  104  performs the reduction and conversion of the scalar k according to the embodiment described in relation with  FIG.  2    or according to the embodiment described in relation with  FIG.  4   , in order to generate a more appropriate representation of scalar k. 
     In an operation  602  (SCALAR MULTIPLICATION OF P), after operation  601 , the cryptographic coprocessor  104  for example performs the multiplication of the modified scalar k with the point P. The result of the operation is then used, for example in a cryptographic operation  604 , according to the relevant protocols. In some cases, the multiplication is performed according to the method described in the patent application “Protection d&#39;une opération cryptographique sur une courbe elliptique,” in the name of the present applicant filed on 31 Aug. 2021 and assigned application number FR2109096 (Attorney reference B20909). 
     An advantage of the described embodiments is that the τ-adic conversion may be made on the fly, one digit after another, during the scalar reduction. Moreover, the length of the converted scalar does not depend on the size of the input scalar. 
     Another advantage of the described embodiments is that they render it difficult to exploit differential power analysis and related attacks. Indeed, adding a random multiple of τ m −1 to the scalar k at each cryptographic operation involving the scalar k changes the visible operation of the device. Moreover, in some τ-adic representations such as τNAF and variants thereof, generating random multiples of τ m −1 comprises the generation of a number l′ of random numbers. 
     Various embodiments and variants have been described. Those skilled in the art will understand that certain features of these embodiments can be combined and other variants will readily occur to those skilled in the art. 
     Finally, the practical implementation of the embodiments and variants described herein is within the capabilities of those skilled in the art based on the functional description provided hereinabove. In particular, regarding the generation of the random digits. 
     A cryptographic method may be summarized as including the execution, by a cryptographic circuit ( 104 ), of an algorithm applied to a scalar (k) in order to generate an output vector, of length l+n, which digits are d 0 , . . . , d l+n−1 , the algorithm including iterations i, each iteration i taking an input data value (ρ), initially equal to said scalar and an input vector of length c, which digits are d′ i , . . . , d′ i+c−1 , where for each j∈{i, . . . , i+c−1}, the digit d′ j  is such that 
     
       
         
           
             
               d 
               j 
               ′ 
             
             = 
             
               { 
               
                 
                   
                     
                       
                         
                           
                             d 
                             j 
                           
                           ⁢ 
                               
                           if 
                           ⁢ 
                               
                           j 
                         
                         &lt; 
                         1 
                       
                     
                   
                   
                     
                       
                         
                           d 
                           
                             j 
                             - 
                             m 
                           
                         
                         ⁢ 
                             
                         otherwise 
                       
                     
                   
                 
                 , 
               
             
           
         
       
     
     where m is a positive integer and each iteration i including a) calculating a first intermediate data value (u) by a first operation applied, modulo τ, to the first input data (ρ) and to the input vector, wherein τ is a complex number; b) updating the value of the first input data value (ρ) by a second operation applied to the first input data value, to the input vector, to the first intermediate data value (u), and to τ; and c) updating the digit (d i ) at position i of the output vector equal to the first intermediate data value (u), wherein the total number of iterations is determined by the cryptographic circuit based on a stop criterion. 
     Each iteration may further include d) updating i to i+1; and e) when i=l, resetting i to i−m. 
     The first integer l may be greater than the second integer m, the method may further include, after execution of step e) of iteration l−1, the application of a function (CORRECT) to c−1 digits of the output vector (d 0 , . . . dl+n−1) of position j, with j belonging to {l−m−c+1, . . . , l−m}, together with the first input data value (ρ), and the updating of these digits of the output vector, as well as the first input data value (ρ), by the ones resulting of the application of the function, the function being such that a quantity equals to Σ j=l−m−c+1   l−m d j τ j +ρτ l−m  remains the same before and after the updating of the digits by the function; and the updated digits d l−m−c+1  to d l−m  satisfy a predicate C, the predicate C depending on a base-τ representation. 
     Cryptographic method may include the setting of the n last coordinates of the output vector to a base-τ representation of the first input data value (ρ) of the last iteration. 
     The coordinates of the output vector (d 0 , . . . , d l+n−1 ) may correspond to digits of the scalar (k) in a reduced τ-adic form. 
     The length of the τ-adic reduced conversion of the scalar (k) may not depend on the value of said scalar. 
     The stop criterion may include that the first input data value (ρ) is sufficiently low that it can be represented in n base-τ digits. 
     The result of the first operation may be a remainder, not necessarily minimal, of an Euclidean division of the sum of the first input data value (ρ) and the first digit of the input vector (d′ i ) by the complex number (τ). 
     The integer m may be defined according to a Koblitz curve (E) defined by a set of points of the following form: 
       {( x,y )∈ K×K:y   2   +xy=x   3   +ax   2 +1}  Math 9
 
     where a is equal 0 or 1 and K=GF(2 m ) is a finite field of cardinality 2 m . 
     Cryptographic method may include the scalar multiplication of a datum corresponding to a point P belonging to the Koblitz curve (E) by the scalar (k). 
     The complex number τ may be equal to (μ−i√{square root over (7)})/2, where μ is equal to (−1) 1−a . 
     The scalar (k) may be a cryptographic key stored in a memory of an electronic device. 
     The integer l may be equal to m and the output vector (d 0 , . . . , d m+n−1 ) may be composed of a number of m+n coordinates, and, before execution of steps a) to c) of the first iteration i=0, each coordinate being equal to 0. 
     The first integer l may be greater than the second integer m and, before execution of step a) to c) of the first iteration i=0, the l first digits of the output vector (d 0 , . . . , d l+n−1 ) may be the digits of a multiple of τ m −1 in a τ-adic form. 
     Before execution of steps a) to c) of the first iteration i=0, the l first digits the output vector (d 0 , . . . , d l+n−1 ) are being such that the digit of position j, with j between 0 and l−m−1, may be the opposite of the digit of position m+j; and each digit of position j, with j between l−m and m−1, may be equal to 0. 
     Non-transitory memory may be summarized as including storing instructions for the implementation of the cryptographic method, when these instructions are executed by a cryptographic circuit. 
     Electronic device may be summarized as including a cryptographic circuit configured for the implementation of the cryptographic method. 
     In an embodiment, a method comprises performing a cryptographic operation, and protecting the performing of the cryptographic operation. The performing the cryptographic operation and the protecting including execution, by a cryptographic circuit, of an algorithm applied to a scalar to generate an output vector, of length l+n, having digits d 0 , . . . , d l+n−1 , the algorithm comprising a number of iterations i, each iteration i taking an input data value (ρ), initially equal to said scalar and an input vector of length c, having digits d′ i , . . . , d′ i+c−1 , where for each j∈{i, . . . , i+c−1}, the digit d′ j  is determined according to 
     
       
         
           
             
               d 
               j 
               ′ 
             
             = 
             
               { 
               
                 
                   
                     
                       
                         
                           
                             d 
                             j 
                           
                           ⁢ 
                               
                           if 
                           ⁢ 
                               
                           j 
                         
                         &lt; 
                         l 
                       
                     
                   
                   
                     
                       
                         
                           d 
                           
                             j 
                             - 
                             m 
                           
                         
                         ⁢ 
                             
                         otherwise 
                       
                     
                   
                 
                 , 
               
             
           
         
       
     
     where m, l and n are positive integers and each iteration i comprises:
         a) calculating a first intermediate data value (u) by a first operation applied, modulo τ, to the first input data (ρ) and to the input vector, wherein τ is a complex number;   b) updating the value of the first input data value (ρ) by a second operation applied to the first input data value, to the input vector, to the first intermediate data value (u), and to τ; and   c) setting a digit (d i ) at position i of the output vector equal to the first intermediate data value (u),       

     wherein the number of iterations is determined by the cryptographic circuit based on a stop criterion. 
     In an embodiment, each iteration comprises: d) updating i to i+1; and e) when i=l, resetting i to i−m. In an embodiment, the integer l is greater than the integer m, and the method comprises, after execution of step e) of iteration l−1, application of a function (CORRECT) to c−1 digits of the output vector (d 0 , . . . dl+n−1) of position j, with j belonging to {l−m−c+1, . . . , l−m}, together with the first input data value (ρ), and updating of these digits of the output vector, as well as the first input data value (ρ), by the ones resulting of the application of the function, the function being such that: a quantity equal to Σ j=l−m−c+1   l−m d j τ j +ρτ l−m  remains the same before and after the updating of the digits by the function; and the updated digits d l−m−c+1  to d l−m  satisfy a predicate C, the predicate C depending on a base-τ representation. In an embodiment, the method comprises setting of an n last coordinates of the output vector to a base-τ representation of the first input data value (ρ) of the last iteration. In an embodiment, coordinates of the output vector (d 0 , . . . , d l+n−1 ) correspond to digits of the scalar in a reduced τ-adic form. In an embodiment, a length of a τ-adic reduced conversion of the scalar does not depend on the value of said scalar. In an embodiment, the stop criterion is satisfied when the first input data value (ρ) can be represented in n base-r digits. In an embodiment, a result of the first operation is a remainder of an Euclidean division of the sum of the first input data value (ρ) and a first digit of the input vector (d′i) by the complex number (τ). In an embodiment, the result of the first operation is not a minimal result of the Euclidean division. In an embodiment, the integer m is defined according to a Koblitz curve (E) defined by a set of points having a following form: 
       {( x,y )∈ K×K:y   2   +xy=x   3   +ax   2 +1}
 
     where a is equal 0 or 1 and K=GF(2 m ) is a finite field of cardinality 2 m . In an embodiment, the method comprises scalar multiplication of a datum corresponding to a point P belonging to the Koblitz curve (E) by the scalar (k). In an embodiment, the complex number τ is equal to (μ−i√{square root over (7)})/2, where μ is equal to (−1) 1−a . In an embodiment, the scalar (k) is a cryptographic key stored in a memory of an electronic device. In an embodiment, the integer l is equal to m and the output vector (d 0 , . . . , d m+n−1 ) is composed of a number of m+n coordinates, and, before execution of steps a) to c) of a first iteration i=0, each coordinate being equal to 0. In an embodiment, the integer l is greater than the integer m and wherein, before execution of step a) to c) of a first iteration i=0, 1 first digits of the output vector (d 0 , . . . , dl+n−1) are digits of a multiple of τ m −1 in a τ-adic form. In an embodiment, before execution of steps a) to c) of the first iteration i=0, the l first digits the output vector (d 0 , . . . , dl+n−1) satisfy: a digit of position j, with j between 0 and l−m−1, is an opposite of a digit of position m+j; and each digit of position j, with j between l−m and m−1, is equal to 0. 
     In an embodiment, a non-transitory computer readable medium&#39;s contents cause a cryptographic circuit to perform a method, the method comprising: performing a cryptographic operation; and protecting the performing of the cryptographic operation. The performing the cryptographic operation and the protecting including: executing an algorithm applied to a scalar to generate an output vector, of length l+n, having digits d 0 , . . . , d l+n−1 , the algorithm comprising a number of iterations i, each iteration i taking an input data value (ρ), initially equal to said scalar and an input vector of length c, having digits d′ i , . . . , d′ i+c−1 , where for each j∈{i, . . . , i+c−1}, the digit d′ j  is determined according to 
     
       
         
           
             
               d 
               j 
               ′ 
             
             = 
             
               { 
               
                 
                   
                     
                       
                         
                           
                             d 
                             j 
                           
                           ⁢ 
                               
                           if 
                           ⁢ 
                               
                           j 
                         
                         &lt; 
                         l 
                       
                     
                   
                   
                     
                       
                         
                           d 
                           
                             j 
                             - 
                             m 
                           
                         
                         ⁢ 
                             
                         otherwise 
                       
                     
                   
                 
                 , 
               
             
           
         
       
     
     where m, l and n are positive integers and each iteration i comprises:
         a) calculating a first intermediate data value (u) by a first operation applied, modulo τ, to the first input data (ρ) and to the input vector, wherein τ is a complex number;   b) updating the value of the first input data value (ρ) by a second operation applied to the first input data value, to the input vector, to the first intermediate data value (u), and to τ; and   c) setting a digit (d i ) at position i of the output vector equal to the first intermediate data value (u),       

     wherein the number of iterations is determined by the cryptographic circuit based on a stop criterion. In an embodiment, each iteration comprises: d) updating i to i+1; and e) when i=l, resetting i to i−m. In an embodiment, the integer l is greater than the integer m, and the method comprises, after execution of step e) of iteration l−1, application of a function (CORRECT) to c−1 digits of the output vector (d 0 , . . . dl+n−1) of position j, with j belonging to {l−m−c+1, . . . , l−m}, together with the first input data value (ρ), and updating of these digits of the output vector, as well as the first input data value (ρ), by the ones resulting of the application of the function, the function being such that: a quantity equal to Σ j=l−m−c+1   l−m d j τ j +ρτ l−m  remains the same before and after the updating of the digits by the function; and the updated digits d l−m−c+1  to d l−m  satisfy a predicate C, the predicate C depending on a base-τ representation. In an embodiment, the method comprises setting of an n last coordinates of the output vector to a base-τ representation of the first input data value (ρ) of the last iteration. In an embodiment, the stop criterion is satisfied when the first input data value (ρ) can be represented in n base-τ digits. In an embodiment, a result of the first operation is a remainder of an Euclidean division of the sum of the first input data value (ρ) and a first digit of the input vector (d′i) by the complex number (τ). In an embodiment, the integer m is defined according to a Koblitz curve (E) defined by a set of points having a following form: 
       {( x,y )∈ K×K:y   2   +xy=x   3   +ax   2 +1}
 
     where a is equal 0 or 1 and K=GF(2 m ) is a finite field of cardinality 2 m . In an embodiment, the complex number τ is equal to (μ−i√{square root over (7)})/2, where μ is equal to (−1) 1−a . In an embodiment, the contents comprise instructions executable by the cryptographic circuit. 
     In an embodiment, a device comprises a memory and cryptographic circuitry coupled to the memory. The cryptographic circuitry, in operation, performs a cryptographic operation and protects the performing of the cryptographic operation, the performing the cryptographic operation and the protecting including: executing an algorithm applied to a scalar to generate an output vector, of length l+n, having digits d 0 , . . . , d l+n− 1, the algorithm comprising a number of iterations i, each iteration i taking an input data value (ρ), initially equal to said scalar and an input vector of length c, having digits d′ i , . . . , d′ i+c−1 , where for each j∈{i, . . . , i+c−1}, the digit d′ j  is determined according to 
     
       
         
           
             
               d 
               j 
               ′ 
             
             = 
             
               { 
               
                 
                   
                     
                       
                         
                           
                             d 
                             j 
                           
                           ⁢ 
                               
                           if 
                           ⁢ 
                               
                           j 
                         
                         &lt; 
                         l 
                       
                     
                   
                   
                     
                       
                         
                           d 
                           
                             j 
                             - 
                             m 
                           
                         
                         ⁢ 
                             
                         otherwise 
                       
                     
                   
                 
                 , 
               
             
           
         
       
     
     where m, l and n are positive integers and each iteration i comprises:
         a) calculating a first intermediate data value (u) by a first operation applied, modulo τ, to the first input data (ρ) and to the input vector, wherein τ is a complex number;   b) updating the value of the first input data value (ρ) by a second operation applied to the first input data value, to the input vector, to the first intermediate data value (u), and to τ; and   c) setting a digit (d i ) at position i of the output vector equal to the first intermediate data value (u),       

     wherein the number of iterations is determined by the cryptographic circuit based on a stop criterion. In an embodiment, each iteration also comprises: 
     d) updating i to i+1; and 
     e) when i=l, resetting i to i−m. 
     In an embodiment, the integer l is greater than the integer m, and the method comprises, after execution of step e) of iteration l−1, application of a function (CORRECT) to c−1 digits of the output vector (d 0 , . . . dl+n−1) of position j, with j belonging to {l−m−c+1, . . . , l−m}, together with the first input data value (ρ), and updating of these digits of the output vector, as well as the first input data value (ρ), by the ones resulting of the application of the function, the function being such that: 
     a quantity equal to Σ j=l−m−c+1   l−m d j τ j +ρτ l−m  remains the same before and after the updating of the digits by the function; and 
     the updated digits d l−m−c+1  to d l−m  satisfy a predicate C, 
     the predicate C depending on a base-τ representation. 
     In an embodiment, the cryptographic circuitry, in operation, sets an n last coordinates of the output vector to a base-τ representation of the first input data value (ρ) of the last iteration. In an embodiment, the stop criterion is satisfied when the first input data value (ρ) can be represented in n base-τ digits. In an embodiment, a result of the first operation is a remainder of an Euclidean division of the sum of the first input data value (ρ) and a first digit of the input vector (d′i) by the complex number (τ). In an embodiment, the integer m is defined according to a Koblitz curve (E) defined by a set of points having a following form: 
       {( x,y )∈ K×K:y   2   +xy=x   3   +ax   2 +1}
 
     where a is equal 0 or 1 and K=GF(2 m ) is a finite field of cardinality 2 m . In an embodiment, the complex number τ is equal to (μ−i√{square root over (7)})/2, where μ is equal to (−1) 1−a . 
     In an embodiment, a system comprises a host processor and cryptographic circuitry coupled to the host processor. The cryptographic circuitry, in operation, performs a cryptographic operation and protects the performing of the cryptographic operation, the performing the cryptographic operation and the protecting including: executing an algorithm applied to a scalar to generate an output vector, of length l+n, having digits d 0 , . . . , d l+n−1 , the algorithm comprising a number of iterations i, each iteration i taking an input data value (ρ), initially equal to said scalar and an input vector of length c, having digits d′ i , . . . , d′ i+c−1 , where for each j∈{i, . . . , i+c−1}, the digit d′ j  is determined according to 
     
       
         
           
             
               d 
               j 
               ′ 
             
             = 
             
               { 
               
                 
                   
                     
                       
                         
                           
                             d 
                             j 
                           
                           ⁢ 
                               
                           if 
                           ⁢ 
                               
                           j 
                         
                         &lt; 
                         l 
                       
                     
                   
                   
                     
                       
                         
                           d 
                           
                             j 
                             - 
                             m 
                           
                         
                         ⁢ 
                             
                         otherwise 
                       
                     
                   
                 
                 , 
               
             
           
         
       
     
     where m, l and n are positive integers and each iteration i comprises:
         a) calculating a first intermediate data value (u) by a first operation applied, modulo τ, to the first input data (ρ) and to the input vector, wherein τ is a complex number;   b) updating the value of the first input data value (ρ) by a second operation applied to the first input data value, to the input vector, to the first intermediate data value (u), and to τ; and   c) setting a digit (d i ) at position i of the output vector equal to the first intermediate data value (u),       

     wherein the number of iterations is determined by the cryptographic circuit based on a stop criterion. 
     In an embodiment, each iteration also comprises: 
     d) updating i to i+1; and 
     e) when i=l, resetting i to i−m. 
     In an embodiment, in operation, an application executing on the host processor initiates the performance of the cryptographic operation by the cryptographic circuitry. 
     Some embodiments may take the form of or comprise computer program products. For example, according to one embodiment there is provided a computer readable medium comprising a computer program adapted to perform one or more of the methods or functions described above. The medium may be a physical storage medium, such as for example a Read Only Memory (ROM) chip, or a disk such as a Digital Versatile Disk (DVD-ROM), Compact Disk (CD-ROM), a hard disk, a memory, a network, or a portable media article to be read by an appropriate drive or via an appropriate connection, including as encoded in one or more barcodes or other related codes stored on one or more such computer-readable mediums and being readable by an appropriate reader device. 
     Furthermore, in some embodiments, some or all of the methods and/or functionality may be implemented or provided in other manners, such as at least partially in firmware and/or hardware, including, but not limited to, one or more application-specific integrated circuits (ASICs), digital signal processors, discrete circuitry, logic gates, standard integrated circuits, controllers (e.g., by executing appropriate instructions, and including microcontrollers and/or embedded controllers), field-programmable gate arrays (FPGAs), complex programmable logic devices (CPLDs), etc., as well as devices that employ RFID technology, and various combinations thereof. 
     The various embodiments described above can be combined to provide further embodiments. Aspects of the embodiments can be modified, if necessary to employ concepts of the various patents, applications and publications to provide yet further embodiments. 
     These and other changes can be made to the embodiments in light of the above-detailed description. In general, in the following claims, the terms used should not be construed to limit the claims to the specific embodiments disclosed in the specification and the claims, but should be construed to include all possible embodiments along with the full scope of equivalents to which such claims are entitled. Accordingly, the claims are not limited by the disclosure.