Next Article in Journal
Flash-Based Security Primitives: Evolution, Challenges and Future Directions
Previous Article in Journal
Acknowledgment to Reviewers of Cryptography in 2020
Article

Montgomery Reduction for Gaussian Integers

Institute for System Dynamics (ISD), HTWG Konstanz, University of Applied Sciences, 78462 Konstanz, Germany
*
Author to whom correspondence should be addressed.
This paper is an extended version of our paper Safieh, M.; Freudenberger, J. Montgomery Modular Arithmetic over Gaussian Integers. In Proceedings of the 24th International Information Technology Conference (IT), Zabljak, Montenegro, 18–22 February 2020; pp. 1–4.
Received: 13 January 2021 / Revised: 27 January 2021 / Accepted: 29 January 2021 / Published: 1 February 2021

Abstract

Modular arithmetic over integers is required for many cryptography systems. Montgomery reduction is an efficient algorithm for the modulo reduction after a multiplication. Typically, Montgomery reduction is used for rings of ordinary integers. In contrast, we investigate the modular reduction over rings of Gaussian integers. Gaussian integers are complex numbers where the real and imaginary parts are integers. Rings over Gaussian integers are isomorphic to ordinary integer rings. In this work, we show that Montgomery reduction can be applied to Gaussian integer rings. Two algorithms for the precision reduction are presented. We demonstrate that the proposed Montgomery reduction enables an efficient Gaussian integer arithmetic that is suitable for elliptic curve cryptography. In particular, we consider the elliptic curve point multiplication according to the randomized initial point method which is protected against side-channel attacks. The implementation of this protected point multiplication is significantly faster than comparable algorithms over ordinary prime fields.
Keywords: public-key cryptography; elliptic curve point multiplication; Gaussian integers; Montgomery modular reduction public-key cryptography; elliptic curve point multiplication; Gaussian integers; Montgomery modular reduction

1. Introduction

Montgomery reduction is an efficient method that performs modulo reduction after an integer multiplication. The reduction algorithm uses multiplication and simple bit-wise operations instead of an expensive division [1]. Public-key cryptography based on the Rivest-Shamir-Adleman (RSA) system benefits from the efficient Montgomery modulo reduction [2,3]. Similarly, elliptic curve cryptography (ECC) systems over prime fields apply Montgomery reduction to support arbitrary prime curves [4,5,6,7,8,9,10,11,12,13,14].
In this work, we consider the modulo reduction for Gaussian integers. Gaussian integers are complex numbers such that the real and imaginary parts are integers. Arithmetic over Gaussian integers for the RSA system was proposed in [15,16,17,18]. In [17,18], it was shown for the RSA system that a significant complexity reduction can be achieved with Gaussian integers. Due to the isomorphism between Gaussian integer rings and ordinary integer rings, this arithmetic is suitable for many cryptography systems. The Rabin cryptography system and elliptic curve cryptography over Gaussian integers were considered in [19,20,21,22]. Moreover, coding applications over Gaussian integers use Gaussian integer arithmetic [23,24,25,26,27,28].
To reduce the complexity of the modular reduction, we investigate Montgomery reduction algorithms for finite Gaussian integer rings. However, it is not trivial to generalize Montgomery reduction to Gaussian integers. The final step of the reduction algorithm is based on the total order of integers which does not exist for complex numbers. In [29], a Montgomery reduction algorithm was proposed that utilizes the absolute value to measure the size of a Gaussian integer. This study is an extension of our paper [29]. In this work, we present a new approach that aims on reducing the complexity of the reduction presented in [29]. In this algorithm, the absolute value is replaced by the Manhattan weight. The calculation of the Manhattan weight requires only a single addition, whereas the calculation of the absolute value requires addition and two squaring operations. On the other hand, the reduction using the Manhattan weight may not always obtain a unique solution. There are at most two possible solutions that are congruent. For many applications uniqueness is not an issue for the intermediate results in calculations, which require many subsequent reduction steps. For the final result, the correct representative can be calculated using absolute values.
The proposed concept of Montgomery reduction was applied in [22] for the efficient calculation of the elliptic curve point multiplication. In particular, an area-efficient coprocessor was designed in [22]. This processor uses the proposed Montgomery modular arithmetic over Gaussian integers. It is shown in [21,22] that a key representation with a Gaussian integer expansion is beneficial for the calculation of the point multiplication. This key representation reduces the computational complexity and the memory requirements of a secure hardware implementation, which is protected against side-channel attacks [30,31,32,33,34,35,36,37]. In this work, we provide the theoretical justification for the reduction algorithms applied in [22]. Furthermore, we present new results for protected implementations of the point multiplication. In particular, we consider the randomized initial point method proposed in [38]. This method is protected against several side-channel attacks, i.e., differential power analysis (DPA), zero-value point attacks (ZPA), and refined power analysis (RPA) [32,38]. We present synthesis results for a field-programmable gate array (FPGA) based on the architecture proposed in [22]. The protected implementation of the point multiplication is significantly faster with Gaussian integers. Moreover, it requires less memory and fewer flip-flops than the PM algorithms over ordinary prime fields reported in [39,40].
This publication is organized as follows. We review the Montgomery multiplication of ordinary integers and discuss some properties of Gaussian integers in Section 2. In Section 3, Montgomery reduction based on the absolute value is investigated. We present a low-complexity reduction algorithm based on the Manhattan weight in Section 4. To demonstrate that the arithmetic over Gaussian integers is useful, we consider the complexity for the elliptic curve point multiplication according to the randomized initial point method in Section 5. In Section 6, we discuss the results and conclude our work.

2. Preliminaries and Problem Statement

In this section, we briefly discuss Montgomery reduction of ordinary integers. Moreover, we review some properties of Gaussian integer rings.

2.1. Montgomery Reduction of Ordinary Integers

Montgomery reduction is considered in several ECC and RSA cryptography systems to decrease the complexity of the arithmetic in prime fields [9,11,14] as well as in rings [2,3]. The Montgomery multiplication uses the arithmetic over a ring R n that is isomorphic to the integer ring Z n = x mod n : x = 0 , , n 1 , x Z [1]. Montgomery reduction algorithm reduces the complexity of the modulo reduction. The expensive calculation mod n is replaced by mod R , where R > n is a power of two. Hence, the modulo reduction in the ring R n is a simple bitwise AND operation with R 1 .
For the Montgomery arithmetic, an element x Z n is mapped to the Montgomery domain as
X = x R mod n .
Addition in the Montgomery domain is isomorphic to ordinary integer modular arithmetic, because
( X + Y ) mod n = ( x R + y R ) mod n = ( x + y ) R mod n .
The multiplication in the Montgomery domain needs Montgomery reduction function μ ( Z ) = Z R 1 mod n described in Algorithm 1. This function defines the inverse mapping, since μ ( X ) = x R R 1 mod n = x mod n . Using the reduction function, we obtain the product
μ ( X Y ) = X Y R 1 mod n = x y R mod n
in the Montgomery domain.
Algorithm 1 Montgomery reduction according to [1].
input: Z, with 0 Z < n R , n = n 1 mod R , and R = 2 l n
output: M = μ ( Z ) = Z R 1 mod n
1:
t = Z n mod R            // bitwise AND with R 1
2:
q = ( Z + t n ) div R               // shift right by l
3:
if ( q n ) then
4:
M = q n
5:
else
6:
M = q
7:
end if
Typically, all variables are mapped at the beginning of the calculation into the Montgomery domain using this reduction function as
X = μ ( x R 2 ) = x R 2 R 1 mod n = x R mod n ,
since only one precomputed value R 2 mod n is required.
We illustrate the Montgomery reduction of ordinary integers with an example. The binary representation of positive integers is denoted by brackets ( · ) 2 with the subscript 2.
Example 1.
We consider the product of two numbers x = 14 and y = 7 from Z 29 . The two integers x and y are mapped to the integers X = x R mod n = 13 and Y = y R mod n = 21 with R = 32 = 2 5 > n = 29 in the Montgomery domain. Hence, all elements of the Montgomery domain can be represented with five binary digits. The product x y mod n = 98 mod 29 = 11 corresponds to x y R mod n = 4 in the Montgomery domain.
With Algorithm 1, we can reduce the product Z = X Y = 273 as follows. With n = 11 , we first calculate t = Z n mod R = 3003 mod 32 = 27 . Note that the modulo reduction of the binary representation is a simple bitwise AND operation with R 1 = 31 or equivalently the truncation of all bits except the five least significant bits. The integer 3003 has the binary representation ( 1011 1011 1011 ) 2 and the five least significant bits ( 1 1011 ) 2 represent the value t = 27 .
Next, we calculate the quotient q = ( Z + t n ) div R = 1056 div 32 = 33 . For R = 32 , the division by R without remainder in the binary representation is a simple right-shift by five bits or equivalently the truncation of the five least significant bits. The integer 1056 has the binary representation ( 100 0010 0000 ) 2 . The division without remainder results in ( 10 0001 ) 2 which is the binary representation of 33. The final result in the Montgomery domain is M = μ ( Z ) = q 29 = 4 because q = 33 > n = 29 . To obtain the result in Z 29 , we apply Montgomery reduction for the inverse mapping M = μ ( M ) = μ ( 4 ) = 11 .

2.2. Rings of Gaussian Integers

The modulo arithmetic over Gaussian integers is based the modulo function
x mod π = x x π * π π * · π ,
where x and π are Gaussian integers. π * is the conjugate of the Gaussian integer π . The brackets · denote rounding to the closest Gaussian integer [23], i.e., for a complex number x = c + d i , we have x = c + d i . The set
G p = x mod π : x = 0 , , p 1 , x Z
is a finite ring. For primes p of the form p 1 mod 4 , G p is a finite field which is isomorphic to the prime field G F ( p ) over ordinary integers [23]. Such fields are suitable for elliptic curve cryptography [21,22]. A prime of the form p 1 mod 4 is the sum of two perfect squares, i.e., p = π π * = a 2 + b 2 with the Gaussian integer π = a + b i .
Moreover, for integers n = c d such that c and d are primes of the form c d 1 mod 4 and c d , the set G n is a ring that is isomorphic to the ring Z n over ordinary integers [26]. Such Gaussian integers are suitable for the RSA public-key system [17,18].
Consider Montgomery reduction in Algorithm 1. Lines 3 to 7 of this algorithm uniquely determine the smallest integer that is congruent to Z R 1 mod n . However, complex numbers cannot be totally ordered [24]. Hence, it is not possible to directly apply this reduction algorithm to Gaussian integers. This reduction problem is not regarded in [17,18].
In this work, we consider two reduction strategies using different norms. One algorithm uses the absolute value x = | c | 2 + | d | 2 of the Gaussian integer x = c + d i . The second approach is based on the Manhattan weight x = c + d . Calculating the Manhattan weight is less complex than calculating the absolute value, because only addition is required, whereas squaring is necessary to determine x . Note that
x     x
holds for any x which follows from squaring both sides of the inequality.

2.3. Finding Primes of the Form p = a 2 + b 2

An algorithm for primes of the form p 1 mod 4 to find a , b such that p = a 2 + b 2 is proposed in [23]. This algorithm consists of two steps.
  • Find x such that x 2 1 mod p , which can be done using the Tonelli-Shanks algorithm [41].
  • Use the Euclidean algorithm to determine the greatest common divisor of p and x. The first two remainders less than p are a and b.
On the other hand, there exist many primes of the form p 1 mod 4 such that p = a 2 + ( a 1 ) 2 or p = a 2 + 1 . Exploiting this observation we can search for a such that the sum p = a 2 + 1 or p = 2 a 2 2 a + 1 is prime. This can significantly reduce the search complexity. Table 1 illustrates some examples of such primes with sufficient bit lengths for ECC applications.

3. Montgomery Reduction for Gaussian Integers

In this section, we consider some important properties of Gaussian integers and derive Montgomery reduction for Gaussian integers using the absolute value. First, we show that the set G n is symmetric and that the absolute value of any element of this ring is bounded.
Lemma 1.
For any x G n we have the following symmetry
x , i x , i x G n .
The absolute value x is bounded by
x   <   π 2 .
Moreover, for any x G n with x = x mod π we have
x   <   x .
Proof. 
Consider the quotient x π = x π * n = c + d i , where c and d are the real part and the imaginary part of x π . For x G n we have x = x mod π . Hence, the rounded quotient satisfies
x π * π π * = 0 .
This implies [ c ] = [ d ] = 0 and c < 1 / 2 , d < 1 / 2 . Hence, we can bound the absolute value of the quotient x π as
x π   <   1 2 .
Multiplying both sides by π results in (9). Note that x , x , i x , or i x have the same absolute value. Hence, (8) holds.
Finally, consider a Gaussian integer x G n which is congruent to x, i.e., x = x mod π . We use the notation x π = c + d i . Note that x = x mod π implies c = c [ c ] and d = d [ d ] . Moreover, at least one rounded value [ c ] or [ d ] is nonzero because x G n , where [ c ] 0 results in c < 1 / 2 < c . Similarly, [ d ] 0 implies d < 1 / 2 < d . Hence, we have (10). □
The next example demonstrates that x   <   π 2 is not a sufficient condition for x G n .
Example 2.
We consider the finite field G 29 for the Gaussian integer π = 5 + 2 i . All elements of this field are depicted in Figure 1. Consider q = 3 with q = 3 mod π = 2 2 i , i.e., q G 29 and q G 29 . Both Gaussian integers satisfy q < π 2 and q < π 2 3.8079 . Hence, it is not possible to determine the representative based on the bound (9). The representative q = 2 2 i follows from (10), as q 2.8284 < q = 3 .
Next, we consider now Montgomery reduction. The reduction for Gaussian integers can be performed according to Algorithm 2, where
α = argmin α { 0 , ± 1 , ± i } q α π ,
α = argmin α { ± 1 , ± i , ± 1 ± i } q α π .
Steps 1 and 2 in Algorithm 2 are applied separately for the real- and imaginary part. We demonstrate that Algorithm 2 always obtains a precision reduction resulting in the correct representative.
Algorithm 2 Montgomery reduction for Gaussian integers
input: Z = X Y , π = π 1 mod R , R = 2 l > π 2
output: M = μ ( Z ) = Z R 1 mod π
1:
t = Z π mod R            // bitwise AND of Re , Im with R 1
2:
q = ( Z + t π ) div R                 // shift Re , Im right by l
3:
if ( q < 2 1 2 π ) then
4:
M = q
5:
else if ( q < π 2 ) then
6:
 determine α according to (11)
7:
M = q α π
8:
else
9:
 determine α according to (12)
10:
M = q α π
11:
end if
Proposition 1.
For M and Z according to Algorithm 2, we have
M = Z R 1 mod π .
Proof. 
We consider the sum Z + t π in step 2 of Algorithm 2, where
Z + t π Z + Z π π mod R Z + Z ( π 1 ) π mod R Z Z mod R 0 ,
implies that R divides Z + t π . Considering the corresponding quotient q = ( Z + t π ) div R , we have
q mod π ( Z + t π ) div R mod π ( Z + t π ) R 1 mod π Z R 1 + t π R 1 mod π Z R 1 mod π .
This shows that q is congruent to Z R 1 mod π or Z R 1 = q α π . The absolute value of Z R 1 mod π is bounded, i.e.,
Z R 1   =   X Y R 1 π 2 2 R < R π 2 R = π 2 .
As shown in Example 2, the quotient q may not be the correct representative Z R 1 mod π even for q < π 2 . The congruent values q α π with α { ± 1 , ± i } are also possible candidates. However, for any x G n and α { ± 1 , ± i } , the lower bound
x α π     π x > 2 1 2 π ,
follows from the triangle inequality and Lemma 1. Consequently, the quotient q is the unique solution for q < 2 1 2 π . Furthermore, for any x G n the condition α > 2 implies
x α π     α π x > π 2 .
Hence, only the candidates according to (11) are possible for 2 1 2 π q < π 2 . Using Lemma 1, it follows that the correct candidate can be found by minimizing the absolute value among all candidates according to (11).
If q π 2 , the result M is calculated as M = q α π with α according to (12). To demonstrate that (12) is correct, we derive the bound α   2 . Consider again the quotient q = ( Z + t π ) div R . We aim to compensate the offset t π R 1 by α π , where the absolute values are bounded by
α π   =   t π R 1   =   t π R 1     2 π .
This follows from t     R 2 + R 2 = 2 R due to the reduction mod R and implies the bound α     2 . □
Example 3.
As an example for Montgomery reduction, we consider the product of two numbers x = 6 and y = 7 from Z 29 or the corresponding field G 29 of Gaussian integers with π = 5 + 2 i . The two integers x and y are mapped to the Gaussian integers X = x R mod π = 2 i and Y = y R mod π = 2 with R = 8 in the Montgomery domain. The product x y mod p = 42 mod 29 = 13 corresponds to x y R mod π = i in the Montgomery domain.
With Algorithm 2, we can reduce the product Z = X Y = 4 + 2 i as follows. With π = 1 + 2 i , we first calculate t = Z π mod R = 10 i mod 8 = 2 i . Note that the modulo reduction is a simple bitwise AND operation with R 1 = 7 .
Next, we calculate the quotient q = ( Z + t π ) div R = 8 i div 8 = i . For R = 8 = 2 3 , the division by R without remainder is a simple right-shift by three bits. The quotient M = μ ( Z ) = q = i is the final result without further reduction steps because q = 1 < 2 1 2 π = 1.5773 .
The product x y mod p = 13 corresponds to x y mod π = 1 + i in the field G 29 . To obtain this result, we apply Montgomery reduction for the inverse mapping M = μ ( M ) = M R 1 . With M = i , we have t = Z π mod R = 2 + i mod 8 = 2 + i and the result M = q = ( Z + t π ) div R = 8 + 8 i div 8 = 1 + i . Again, no reduction is required because the condition q = 2 < 2 1 2 π = 1.5773 is satisfied.
We illustrate the final reduction procedure of Algorithm 2 in the following example. There are up to eight possible values α according to (11) and (12). However, not all potential values have to be considered for the reduction. The number of valid candidates α can be reduced based on the signs of the real and imaginary part of q.
Example 4.
We consider again the finite field G 29 of Gaussian integers with π = 5 + 2 i . Figure 2 depicts all possible quotients q in the Montgomery domain after the first two steps of Algorithm 2. For q = 3 we have 2 1 2 π 1.5773 < q = 3 < π 2 3.8079 . Thus, α should be determined according to (11). However, there are only two possible values for α, i.e., α { 0 , 1 } , as q is in the first quadrant. Calculating q 0 = 3 and q π 2.3852 leads to α = 1 . Consequently, we obtain the representative M = q α π = 2 2 i .
Algorithm 2 achieves the desired precision reduction, where the final reduction step always results in the correct representative M = q mod π . This result satisfies the bound M π 2 . The number of possible candidates α is restricted depending on the absolute value of q, as illustrated in (11) and (12).
Nonetheless, the reduction according to Algorithm 2 can be rather complex due to the squaring to determine the absolute values. This complexity may not be required in all applications of the Montgomery multiplication. For applications in cryptography, it is adequate to find the unique representative Z R 1 mod π only in the last calculation step, whereas for intermediates results a reduction that achieves M Z R 1 mod π is sufficient. This motivates a low complexity Montgomery reduction based on the Manhattan weight, which is considered in the next section.

4. Precision Reduction for Gaussian Integers Using the Manhattan Weight

In this section, we present a low complexity precision reduction for Gaussian integers based on the Manhattan weight, i.e., the absolute value in the reduction algorithm is replaced by the Manhattan weight. The calculation of the absolute value requires squaring, whereas the Manhattan weight requires only addition. On the other hand, this algorithm may not obtain a unique solution. However, there are at most two possible solutions that are congruent. In ECC or RSA systems that require many reduction steps, this algorithm can be used for the intermediate results.
Without loss of generality we consider π = a + b i with a > b 1 . The precision reduction is described in Algorithm 3, where
α ^ = argmin α { ± 1 , ± i , ± 1 ± i } q α π ,
and N = a 1 . We demonstrated that this algorithm always obtains M Z R 1 mod π , where M N .
Algorithm 3 Precision reduction for Gaussian integers
input: Z = X Y , π = π 1 mod R , R = 2 l > N
output: M μ ( Z ) = Z R 1 mod π
1:
t = Z π mod R            // bitwise AND of Re , Im with R 1
2:
q = ( Z + t π ) div R               // shift Re and Im right by l
3:
if ( q N ) then
4:
M = q
5:
else
6:
 determine α ^ according to  (14)
7:
M = q α ^ π
8:
end if
First, we note that using the symmetry according to Lemma 1, we can restrict the following derivations to the elements of the first quadrant. Next, we consider some important properties of the Manhattan weight.
Lemma 2.
For x G p the Manhattan weight is upper bounded by
x     a 1 = N .
Proof. 
Let c and d be the real part and the imaginary part of x π . For x G p we have x = x mod π and consequently
x π * π π * = 0 .
This implies [ c ] = [ d ] = 0 and c < 1 / 2 , d < 1 / 2 . Hence, we consider ( 1 / 2 + 1 / 2 i ) π to upper bound the real and imaginary parts of x as
Re { x } < a b 2 , Im x < a + b 2 .
Note that either a is odd and b is even or vice versa because p is an odd prime. Furthermore, the real- and imaginary parts of x are integers. Consequently, we have
Re { x } a b 2 1 2 , Im x a + b 2 1 2 .
We can bound the Manhattan weight of x as
x     a b 1 2 + a + b 1 2 i .
With a > b 1 , the Manhattan weight of x is upper bounded by
x     a b 1 2 + a + b 1 2 = a 1 .
Hence (15) holds. □
Next, we consider bounds on the Manhattan weight for the sum and product of two elements x , y G p . Note that we consider arithmetic without modulo reduction.
Lemma 3.
For x , y G p we have the upper bounds
x + y 2 N ,
x y N 2 ,
for arithmetic without modulo reduction.
Proof. 
The bound on the sum follows from the triangle inequality and (15), i.e.,
x + y     x + y     2 N .
Without loss of generality we consider two elements x = c + d i and y = e + f i from the first quadrant for the product in (19). This implies x = c + d N or d N c . Similarly, we have f N e . For the product x y we have
x y = ( c e d f ) + ( e d + c f ) i .
First, consider the absolute value of the imaginary part Im xy
Im xy   =   e d + c f e ( N c ) + c ( N e ) = e N + c N 2 c e .
To determine the maximum value, we consider the bivariate function g ( e , c ) = e N + c N 2 c e and its partial derivatives
g ( e , c ) e = N 2 c = 0 ,
g ( e , c ) c = N 2 e = 0 .
This results in a maximum for c = e = N / 2 and the bound Im xy = e d + c f N 2 / 2 . Due to symmetry this bound also holds for the absolute value of the real part. Hence, we have
x y     N 2 2 + N 2 2 = N 2 .
The following proposition demonstrates that Algorithm 3 results in the desired reduction.
Proposition 2.
For M and Z according to Algorithm 3, we have
M Z R 1 mod π ,
M N .
Proof. 
The first two steps are identical in Algorithm 3 and Algorithm 2. Hence, the first statement (25) follows from the same arguments as in the proof of Proposition 1.
For q N , we immediately have (26). For q > N , we consider again the corresponding quotient q = ( Z + t π ) div R . The Manhattan weight of Z R 1 mod π is bounded by
Z R   = Z R = X Y R N 2 R N R R = N ,
where we have used (24) and the assumption R N .
Similar to the proof of Proposition 1, we aim to compensate t π R 1 with α π . From Proposition 1 follows that α 2 . Hence, the minimization in (14) over α { ± 1 , ± i , ± 1 ± i } is sufficient. From (27) follows that there is at least one solution with M = q α ^ π N . Consequently, the minimization in (14) will find a solution satisfying (26). □
Finally, we can now describe the final reduction step of Algorithm 3. Note that there are eight possible values for α according to (14), but not all potential values have to be considered. The reduction procedure is demonstrated in the following example.
Example 5.
Again, we consider the finite field G 29 of Gaussian integers with π = 5 + 2 i , where all possible values of q after the first two steps of Algorithm 3 are depicted in Figure 2.
For instance, consider the product of x = 19 and y = 7 from Z 29 . The two integers x and y are mapped to the Gaussian integers X = x R mod π = 2 2 i and Y = y R mod π = 2 with R = 8 in the Montgomery domain. The product x y mod p = 133 mod 29 = 17 corresponds to x y R mod π = 3 i in the Montgomery domain.
With Algorithm 2, we can reduce the product Z = X Y = 4 + 4 i as follows. We calculate t = Z π mod R = 4 + 4 i and the quotient q = ( Z + t π ) div R = 1 + 4 i . A valid solution of the reduction is a Gaussian integer M with M N . We have q = 5 > N = 4 . Hence, further reduction is required. As q is in the first quadrant, we have three possible values for α, i.e., α { 1 , i , 1 + i } . Calculating q α π results in 4 + 2 i , 3 i , 2 3 i , where only the solution M = 3 i satisfies the condition M N = 4 . Hence, we choose M = 3 i as the final result.
The final reduction step results in a Gaussian integer x with x N . Hence, Algorithm 3 achieves the desired precision reduction using the Manhattan weight. However, the result may not always be an element of the ring. For instance, for some π the value x = a 1 is a ring element. Alternatively, the point x = x π = 1 b i can be a ring element. Both values are congruent and can satisfy x = a 1 N , x = b + 1 N depending on π . The ring element is the value with the smallest absolute value. There exist at most two congruent values with Manhattan weight less or equal N. Consequently, the correct representation can be selected by minimizing the absolute value of these two congruent values. Depending on the application this step might be required once to obtain the final result x = q mod π .

5. Elliptic Curve Point Multiplication

In this section, we consider the elliptic curve point multiplication to demonstrate that the arithmetic over Gaussian integers enables an efficient calculation. Calculations of the elliptic curve point multiplication are prone to side-channel attacks. For example, an attacker can estimate the secret key based on the required power consumption of the different arithmetic operations over time. There are many known attacks on the point multiplication like timing attacks, simple power analysis, differential power analysis, refined power analysis, and zero-value point attacks [32,38].
The concept for the point multiplication over Gaussian integers was introduced in [22], where an area-efficient coprocessor design was proposed with an arithmetic unit that enables Montgomery modular arithmetic over Gaussian integers. It is shown in [22] that a key representation with a Gaussian integer expansion is beneficial to reduce the computational complexity and the memory requirements of a secure hardware implementation considering timing attacks and simple power analysis. This architecture supports different point multiplication algorithms. In contrast to [22], we consider the randomized initial point method which is additionally protected against differential power analysis, refined power analysis, and zero-value point attacks [32,38]. We refer to [22] for the architecture and the implementation details.
In the following, we consider the elliptic curve
y 2 = x 3 + α x + β ,
which is recommended for prime fields G F ( p ) [32,42]. The parameters α and β are constant coefficients. The pair x and y defines the coordinates of a point P ( x , y ) on the curve. The one-way function of elliptic-curve cryptography is the point multiplication, i.e.,  k P , where P is a point on the elliptic curve and k is an integer. The point multiplication is typically implemented based on the binary expansion k = i = 0 r 1 k i 2 i of the integer k with binary digits k i { 0 , 1 } , where r is the length in bits and k r 1 , k r 2 , , k 0 is the binary representation of the key (the integer k). This method requires two different point operations, the point addition (ADD) and the point doubling operation (DBL) [32]. Let P ( x 1 , y 1 ) and Q ( x 2 , y 2 ) be two distinct points on an elliptic curve (28), then the sum S ( x 3 , y 3 ) = P ( x 1 , y 1 ) + Q ( x 2 , y 2 ) is calculated as
x 3 = y 2 y 1 x 2 x 1 2 x 1 x 2 , y 3 = y 2 y 1 x 2 x 1 ( x 1 x 3 ) y 1 .
Similarly, the point doubling operation S ( x 3 , y 3 ) = 2 P ( x 1 , y 1 ) is defined as
x 3 = 3 x 1 2 + α 2 y 1 2 2 x 1 , y 3 = 3 x 1 2 + α 2 y 1 ( x 1 x 3 ) y 1 .
The calculations in (29) and (30) are typically performed using arithmetic over prime fields. However, we consider arithmetic over Gaussian integer fields, where x i , y i , α , β G p .
As an alternative to the binary expansion key representation, τ -adic expansions of the integer k with a non-binary basis τ were proposed to speed up the point multiplication (PM) and to improve the resistance against attacks [38,43,44,45,46,47]. The τ -adic expansion results in the point multiplication
k P = i = 0 l 1 κ i τ i P = τ ( τ ( τ κ l 1 P + κ l 2 P ) + ) + κ 0 P ,
where we consider digits κ i from a Gaussian integer field.
To demonstrate that a τ -adic expansion with arithmetic over Gaussian integers can reduce the computational complexity, we consider an example based on the curve (28) with β = 0 . For the products κ i P ( x , y ) we use the endomorphism i P ( x , y ) = P ( x , i y ) for prime fields [32,48]. Note that P ( x , i y ) is a point on the curve (28) if P ( x , y ) is a valid point. The negation of any point P ( x , y ) is P ( x , y ) according to [32]. Hence, for the products κ i P ( x , y ) with κ i { 0 , ± 1 , ± i } we have
P = P ( x , y ) ,
P = P ( x , y ) ,
i P = P ( x , i y ) ,
i P = P ( x , i y ) .
Using this endomorphism, we can calculate other products τ P , e.g.,  τ P = ( 2 + i ) P = 2 P + i P requires a DBL, the mapping i P , and an ADD operation. Several other endomorphisms for different curves over prime fields can be fund in [32,48].
For the point multiplication, we consider the randomized initial point method according to Algorithm 4. This method introduces a random point R into the calculation of the point multiplication. Consequently, all intermediate results in the calculation of the point multiplication become randomized. The algorithm starts with a precomputation phase, where the points S l 1 , , S 1 , S 0 are computed in steps 1 to 4 and stored in a memory. The point addition in step 5 results in the point Q = S l 1 + R . This point is multiplied with τ and then added to the corresponding precomputed point S j in the loop in steps 6 to 9 of this algorithm. Due to the second product of the precomputations ( τ 1 ) · R , we obtain the point Q + R after each iteration of this loop. Correspondingly, the final result is the point Q + R = k · P + R . Hence, we obtain the correct result of the point multiplication k · P by subtracting R from Q in step 10. The point addition in step 8 is computed in each iteration since the τ -adic expansion of the key according to [22] excludes all zero elements. This prevents SPA and timing attacks. Furthermore, all stored points S l 1 , , S 1 , S 0 are randomized due to the subtracting the random point ( τ 1 ) · R . Thus, the resistance against DPA, RPA, and ZPA is increased.
We can use the reduction based on the Manhattan weight in Algorithm 3 for all interim results in the point multiplication. The aim of the reduction of interim results is finding a Gaussian integer x ˜ that has a Manhattan weight satisfying x ˜ N and is congruent to the actual representative x. The reduction algorithm can be stopped once a value x ˜ = q α π with x ˜ N is found. Hence, not all offsets in (14) have to be considered in every reduction. Table 2 presents numerical results on the number of required reduction steps for different field sizes. The four columns on the right in Table 2 provide the percentage for the number of required offset reduction steps after an arithmetic operation, where no reduction is required if the result q already satisfies q N . These results illustrate that sequential processing of the offset reduction is suitable for the point multiplication because 91 % of all operations require no reduction since q N is satisfied. About 4 5 % of all operations require a single reduction step. Two or three calculation steps were required in approximately 4 % of all cases.
Algorithm 4 Point multiplication according to the randomized initial point method from [38].
input:P, k = κ l 1 , , κ 1 , κ 0 τ
output: k · P
1:
R = r a n d o m p o i n t                     // randomized initial point
2:
for ( j = l 1 down to 0) do
3:
S j = κ j · P ( τ 1 ) · R          // store all precomputed points in memory
4:
end for
5:
Q = S l 1 + τ · R ;              // ADD κ l 1 · P ( τ 1 ) · R and τ · R
6:
for ( j = l 2 down to 0) do
7:
Q = τ · Q                // use DBL and ADD operations since τ Z [ i ]
8:
Q = Q + S j      // ADD Q and κ j · P ( τ 1 ) · R that is read from the memory
9:
end for
10:
return Q R
On the other hand, the different execution times of the reduction steps may cause concerns about side-channel vulnerabilities. However, the probability for additional reduction steps is relativity low. Moreover, the randomized initial point method also randomizes the occurrence of these additional steps.
Next, we demonstrate that determining the point multiplication using Gaussian integers reduces the computational complexity. The number of required point operations per iteration of the point multiplication is similar to the results in [22]. However, some additional computations are required to subtract the random point. As in [22], we estimate the computational complexity for the point multiplication in terms of multiplication equivalent operations M. Table 3 illustrates two examples for the complexity with different bases τ . The parameter r denotes the maximum key length in bits and the value l is the number of iterations per point multiplication. A larger value of τ 2 reduces the number of iterations and speeds up the computation compared with a conventional binary PM, but requires more storage for the precomputed points.
The results are compared with the point multiplication according to randomized initial point but using ordinary integer expansions as proposed in [38] for comparable base values w. For instance, we can compare the complex base τ = 4 + i with τ 2 = 17 digits and the base w = 4 with 2 w = 16 digits from [38]. For these values, the number M of multiplications is reduced by 32.5 % . This reduction results mainly from the simpler calculation of τ · Q for Gaussian integers due to the used endomorphism. In [21], a similar PM with τ -adic expansions over Gaussian integers was proposed. This algorithm additionally reduces the number of precomputed and stored points. However, this method considers only timing and simple power analysis attacks. It is more vulnerable to statistical attacks than the randomized initial point method.
To illustrate the efficiency of Gaussian integer arithmetic, we consider latencies for the point multiplication according to Algorithm 4 using both norms in Table 4. The table provides results for a Xilinx Virtex-7 field-programmable gate array (FPGA) based on the architecture from [22]. The hardware requirements are represented by the number of look-up tables (LUT), flip-flops (FF), slices, and digital signal processor (DSP) units, as well as by the RAM size. The maximum clock frequency is denoted by f c l k . These point multiplications are significantly faster than the results from [39,40]. For instance, the design in [40] considers key lengths up to r = 256 and the unprotected PM. This design is optimized for the use of DSP units which reduces the number of LUT. The number 1990 of LUT is similar to the proposed design with key length r = 253 using DSP units. It employs much more flip-flops (1786) and memory (234 kbit). An unprotected PM of length r = 256 requires 23.5ms whereas the proposed protected PM requires only 6.87ms for r = 253 .
Note that the latency values for the reduction algorithms depend on the hardware architecture. The calculation of the Manhattan weight requires one addition which is performed in a single clock cycle with the architecture from [22]. For the absolute value, two additional multiplications are required which need four clock cycles each. Hence, the latency for calculating the Manhattan weight is only 11% of the time for the absolute value. The results in Table 4 illustrate the impact of this complexity reduction on the total latency of a point multiplication. Applying the Manhattan weight reduces the latency of a PM by 13% compared with the reduction algorithm from [29].

6. Conclusions

Gaussian integers are suitable for RSA [17,18] and ECC applications [22]. Furthermore, Gaussian integers have applications in coding theory [23,26]. The Montgomery multiplication for Gaussian integers was previously proposed in [17,18]. However, no reduction algorithm was advised.
The generalization of Montgomery reduction to Gaussian integers is not trivial, because complex numbers cannot be totally ordered. In this work, we have presented two algorithms for Montgomery reduction for Gaussian integers which use different norms. The first algorithm utilizes the absolute value to measure the size of a Gaussian integer. This algorithm can uniquely determine the correct representative. The second algorithm is based on the Manhattan weight of Gaussian integers, which reduces the computational complexity for the modulo reduction. However, two congruent solutions may occur. It is not possible to determine the correct candidate based on the Manhattan weight. The correct representative is the candidate with the smaller absolute value. Hence, the first algorithm is required to determine the final result, e.g., for the inverse mapping from the Montgomery domain to the original field representation.
It is shown in [21,22] that a key representation with a Gaussian integer expansion is beneficial to reduce the computational complexity and the memory requirements of elliptic curve point multiplication algorithms that are protected against side-channel attacks. However, only timing and simple power analysis attacks were considered. This PM is vulnerable to statistical attacks [38]. As an alternative, we have shown that Gaussian integer expansions can be used with the randomized initial point method. This method is protected against statistical attacks like DPA, RPA, and ZPA. The FPGA implementation of this protected PM with Gaussian integer expansions is significantly faster than the PM algorithms over ordinary prime fields reported in [39,40].
However, Gaussian integer fields can only be constructed for primes of the form p mod 4 = 1 , hence a generalization of this work to Eisenstein integers could be beneficial. Eisenstein integers are complex numbers of the form x = a + b ω , where ω = 1 2 · 1 + 3 , and Eisenstein integer fields can be constructed for primes of the form p mod 6 = 1 . An elliptic curve point multiplication using Eisenstein integers was considered in [49] showing similar properties as the point multiplication over Gaussian integers. Up to now no efficient modulo operation for Eisenstein integers is known. We believe that a generalization of the Montgomery modular multiplication to Eisenstein integers would be a promising direction for further research.

Author Contributions

The research for this article was exclusively undertaken by M.S. and J.F. Conceptualization and investigation, M.S. and J.F.; writing–review and editing, M.S. and J.F.; writing–original draft preparation, M.S.; supervision, project administration, and funding acquisition J.F.; All authors have read and agreed to the published version of the manuscript.

Funding

The German Federal Ministry of Economics and Technology (ZF4559701ED8) supported the research for this article.

Acknowledgments

The authors would like to thank Hyperstone GmbH, Konstanz for supporting the research for this article.

Conflicts of Interest

The authors declare no conflict of interest. The funders had no role in the design of the study; in the collection, analyses, or interpretation of data; in the writing of the manuscript, or in the decision to publish the results.

References

  1. Montgomery, P.L. Modular multiplication without trial division. Math. Comput. 1985, 44, 519–521. [Google Scholar] [CrossRef]
  2. Mahapatra, P.P.; Agrawal, S. RSA Cryptosystem with Modified Montgomery Modular Multiplier. In Proceedings of the IEEE International Conference on Computational Intelligence and Computing Research (ICCIC), Coimbatore, India, 14–16 December 2017; pp. 1–6. [Google Scholar] [CrossRef]
  3. Parihar, A.; Nakhate, S. Fast Montgomery modular multiplier for Rivest-Shamir-Adleman cryptosystem. IET Inf. Secur. 2019, 13, 231–238. [Google Scholar] [CrossRef]
  4. Koblitz, N. Elliptic Curve Cryptosystems. Math. Comput. 1987, 48, 203–209. [Google Scholar] [CrossRef]
  5. Loi, K.C.C.; Ko, S. Scalable Elliptic Curve Cryptosystem FPGA Processor for NIST Prime Curves. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 2015, 23, 2753–2756. [Google Scholar] [CrossRef]
  6. Khan, Z.U.A.; Benaissa, M. Throughput/Area-efficient ECC Processor Using Montgomery Point Multiplication on FPGA. IEEE Trans. Circuits Syst. II Express Briefs 2015, 62, 1078–1082. [Google Scholar] [CrossRef]
  7. Hossain, M.S.; Saeedi, E.; Kong, Y. High-Speed, Area-Efficient, FPGA-Based Elliptic Curve Cryptographic Processor over NIST Binary Fields. In Proceedings of the IEEE International Conference on Data Science and Data Intensive Systems, Sydney, NSW, Australia, 11–13 December 2015; pp. 175–181. [Google Scholar] [CrossRef]
  8. Bosmans, J.; Roy, S.S.; Jarvinen, K.; Verbauwhede, I. A Tiny Coprocessor for Elliptic Curve Cryptography over the 256-bit NIST Prime Field. In Proceedings of the 29th International Conference on VLSI Design (VLSID), Kolkata, India, 4–8 January 2016; pp. 523–528. [Google Scholar] [CrossRef]
  9. Ma, Y.; Zhang, Q.; Liu, Z.; Tu, C.; Lin, J. Low-Cost Hardware Implementation of Elliptic Curve Cryptography for General Prime Fields. In Information and Communications Security; Lecture Notes in Computer Science; Lam, K.Y., Chi, C.H., Qing, S., Eds.; Springer International Publishing: Berlin/Heidelberg, Germany, 2016; pp. 292–306. [Google Scholar]
  10. Mozhi, S.A.; Ramya, P. Efficient bit-parallel systolic multiplier over GF(2m). In Proceedings of the International Conference on Electrical, Electronics, and Optimization Techniques (ICEEOT), Chennai, India, 3–5 March 2016; pp. 4899–4902. [Google Scholar] [CrossRef]
  11. Amiet, D.; Curiger, A.; Zbinden, P. Flexible FPGA-Based Architectures for Curve Point Multiplication over GF(p). In Proceedings of the Euromicro Conference on Digital System Design (DSD), Limassol, Cyprus, 31 August–2 September 2016; pp. 107–114. [Google Scholar] [CrossRef]
  12. Khan, Z.U.A.; Benaissa, M. High-Speed and Low-Latency ECC Processor Implementation Over GF(2m) on FPGA. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 2017, 25, 165–176. [Google Scholar] [CrossRef]
  13. Safieh, M.; Thiers, J.P.; Freudenberger, J. Area Efficient Coprocessor for the Elliptic Curve Point Multiplication. In Proceedings of the 12th International ITG Conference on Systems, Communications and Coding (SCC), Rostock, Germany, 11–14 February 2019; pp. 1–6. [Google Scholar]
  14. Roy, D.B.; Mukhopadhyay, D. High-Speed Implementation of ECC Scalar Multiplication in GF(p) for Generic Montgomery Curves. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 2019, 27, 1587–1600. [Google Scholar] [CrossRef]
  15. Elkamchouchi, H.; Elshenawy, K.; Shaban, H. Extended RSA cryptosystem and digital signature schemes in the domain of Gaussian integers. In Proceedings of the 8th International Conference on Communication Systems (ICCS), Singapore, 28 November 2002; Volume 1, pp. 91–95. [Google Scholar] [CrossRef]
  16. Koval, A.; Verkhovsky, B.S. Analysis of RSA over Gaussian Integers Algorithm. In Proceedings of the Fifth International Conference on Information Technology: New Generations (ITNG), Las Vegas, NV, USA, 7–9 April 2008; pp. 101–105. [Google Scholar] [CrossRef]
  17. Koval, A. Security Systems Based on Gaussian Integers: Analysis of Basic Operations and Time Complexity of Secret Transformations; New Jersey Institute of Technology: Newark, NJ, USA, 2011. [Google Scholar]
  18. Koval, A. Algorithm for Gaussian Integer Exponentiation. In Information Technology: New Generations; Springer International Publishing: Berlin/Heidelberg, Germany, 2016; pp. 1075–1085. [Google Scholar]
  19. Bhargava, K.; Soni, V. A novice cryptosystem based on nth root of Gaussian integers. In Proceedings of the 2017 International Conference on Computer, Communications and Electronics (Comptelix), Jaipur, India, 1–2 July 2017; pp. 271–274. [Google Scholar] [CrossRef]
  20. Awad, Y.; El-Kassar, A.N.; Kadri, T. Rabin Public-Key Cryptosystem in the Domain of Gaussian Integers. In Proceedings of the International Conference on Computer and Applications (ICCA), Beirut, Lebanon, 25–26 August 2018; pp. 336–340. [Google Scholar] [CrossRef]
  21. Safieh, M.; Thiers, J.; Freudenberger, J. Side Channel Attack Resistance of the Elliptic Curve Point Multiplication using Gaussian Integers. In Proceedings of the Zooming Innovation in Consumer Technologies Conference (ZINC), Novi Sad, Serbia, 26–27 May 2020; pp. 231–236. [Google Scholar]
  22. Safieh, M.; Thiers, J.; Freudenberger, J. A Compact Coprocessor for the Elliptic Curve Point Multiplication over Gaussian Integers. Electronics 2020, 9, 2050. [Google Scholar] [CrossRef]
  23. Huber, K. Codes over Gaussian integers. IEEE Trans. Inf. Theory 1994, 40, 207–216. [Google Scholar] [CrossRef]
  24. Martinez, C.; Beivide, R.; Gabidulin, E. Perfect Codes for Metrics Induced by Circulant Graphs. IEEE Trans. Inf. Theory 2007, 53, 3042–3052. [Google Scholar] [CrossRef]
  25. Quilles, C.; Palazzo, R. Quasi-Perfect Geometrically Uniform Codes Derived from Graphs over Gaussian Integer Rings. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), Austin, TX, USA, 13–18 June 2010. [Google Scholar]
  26. Freudenberger, J.; Ghaboussi, F.; Shavgulidze, S. New Coding Techniques for Codes over Gaussian Integers. IEEE Trans. Commun. 2013, 61, 3114–3124. [Google Scholar] [CrossRef]
  27. Freudenberger, J.; Ghaboussi, F.; Shavgulidze, S. Set Partitioning and Multilevel Coding for Codes Over Gaussian Integer Rings. In Proceedings of the 9th International ITG Conference on Systems, Communications and Coding (SCC), Munich, Germany, 21–24 January 2013; pp. 1–5. [Google Scholar]
  28. Rohweder, D.; Freudenberger, J.; Shavgulidze, S. Low-Density Parity-Check Codes over Finite Gaussian Integer Fields. In Proceedings of the 2018 IEEE International Symposium on Information Theory (ISIT), Vail, CO, USA, 17–22 June 2018; pp. 481–485. [Google Scholar] [CrossRef]
  29. Safieh, M.; Freudenberger, J. Montgomery Modular Arithmetic over Gaussian Integers. In Proceedings of the 24th International Information Technology Conference (IT), Zabljak, Montenegro, 18–22 February 2020; pp. 1–4. [Google Scholar]
  30. Kocher, P. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. In Proceedings of the Annual International Cryptology Conference, Santa Barbara, CA, USA, 18–22 August 1996. [Google Scholar]
  31. Kocher, P.; Jaffe, J.; Jun, B. Differential Power Analysis. In Proceedings of the Annual International Cryptology Conference, Santa Barbara, CA, USA, 15–19 August 1999. [Google Scholar]
  32. Hankerson, D.; Menezes, A.J.; Vanstone, S. Guide to Elliptic Curve Cryptography; Springer: New York, NY, USA, 2003. [Google Scholar]
  33. Goubin, L. A Refined Power-Analysis Attack on Elliptic Curve Cryptosystems. In Public Key Cryptography—PKC 2003; Desmedt, Y.G., Ed.; Springer: Berlin/Heidelberg, Germany, 2002; pp. 199–211. [Google Scholar]
  34. Akishita, T.; Takagi, T. Zero-Value Point Attacks on Elliptic Curve Cryptosystem. In Information Security; Boyd, C., Mao, W., Eds.; Springer: Berlin/Heidelberg, Germany, 2003; pp. 218–233. [Google Scholar]
  35. Mulder, E.D.; Örs, S.B.; Preneel, B.; Verbauwhede, I. Differential power and electromagnetic attacks on a FPGA implementation of elliptic curve cryptosystems. Comput. Electr. Eng. 2007, 33, 367–382. [Google Scholar] [CrossRef]
  36. Lerman, L.; Bontempi, G.; Markowitch, O. Side channel attack: An approach based on machine learning. In Proceedings of the Proc. 2nd International Workshop on Constructive Side-Channel Analysis and Secure Design, Darmstadt, Germany, 14 February 2011; pp. 29–41. [Google Scholar]
  37. Maghrebi, H.; Portigliatti, T.; Prouff, E. Breaking cryptographic implementations using deep learning techniques. In Proceedings of the International Conference on Security, Privacy, and Applied Cryptography Engineering, Hyderabad, India, 14–18 December 2016; pp. 3–26. [Google Scholar]
  38. Hedabou, M.; Pinel, P.; Bénéteau, L. Countermeasures for Preventing Comb Method Against SCA Attacks. In Information Security Practice and Experience; Deng, R.H., Bao, F., Pang, H., Zhou, J., Eds.; Springer: Berlin/Heidelberg, Germany, 2005; pp. 85–96. [Google Scholar]
  39. Salman, A.; Ferozpuri, A.; Homsirikamol, E.; Yalla, P.; Kaps, J.; Gaj, K. A scalable ECC processor implementation for high-speed and lightweight with side-channel countermeasures. In Proceedings of the International Conference on ReConFigurable Computing and FPGAs (ReConFig), Cancun, Mexico, 4–6 December 2017; pp. 1–8. [Google Scholar] [CrossRef]
  40. Matutino, P.M.; Araújo, J.; Sousa, L.; Chaves, R. Pipelined FPGA coprocessor for elliptic curve cryptography based on residue number system. In Proceedings of the International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS), Pythagorion, Greece, 17–20 July 2017; pp. 261–268. [Google Scholar] [CrossRef]
  41. Diekert, V.; Kufleitner, M.; Rosenberger, G.; Hertrampf, U. Discrete Algebraic Methods: Arithmetic, Cryptography, Automata and Groups; De Gruyter: Berlin, Germany, 2016. [Google Scholar]
  42. Krisell, M. Elliptic Curve Digital Signatures in RSA Hardware; Scholar’s Press: Riga, Latvia, 2012. [Google Scholar]
  43. Jarvinen, K.; Tommiska, M.; Skytta, J. A scalable architecture for elliptic curve point multiplication. In Proceedings of the IEEE International Conference on Field—Programmable Technology, Brisbane, NSW, Australia, 6–8 December 2004; pp. 303–306. [Google Scholar] [CrossRef]
  44. Okeya, K.; Takagi, T.; Vuillaume, C. Efficient Representations on Koblitz Curves with Resistance to Side Channel Attacks. In Information Security and Privacy; Boyd, C., Gonza’lez Nieto, J.M., Eds.; Springer: Berlin/Heidelberg, Germany, 2005; pp. 218–229. [Google Scholar]
  45. Thériault, N. SPA Resistant Left-to-Right Integer Recodings. In Selected Areas in Cryptography; Preneel, B., Tavares, S., Eds.; Springer: Berlin/Heidelberg, Germany, 2006; pp. 345–358. [Google Scholar]
  46. Tao, Z.; Mingyu, F.; Xiaoyu, Z. Secure and efficient elliptic curve cryptography resists side-channel attacks. J. Syst. Eng. Electron. 2009, 20, 660–665. [Google Scholar]
  47. Liu, S.; Yao, H.; Wang, X.A. SPA Resistant Scalar Multiplication Based on Addition and Tripling Indistinguishable on Elliptic Curve Cryptosystem. In Proceedings of the 10th International Conference on P2P, Parallel, Grid, Cloud and Internet Computing (3PGCIC), Krakow, Poland, 4–6 November 2015; pp. 785–790. [Google Scholar] [CrossRef]
  48. Gallant, R.; Lambert, R.; Vanstone, S. Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms. In Advances in Cryptology—CRYPTO 2001; Springer: Berlin/Heidelberg, Germany, 2001; pp. 190–200. [Google Scholar]
  49. Thiers, J.P.; Safieh, M.; Freudenberger, J. Side Channel Attack Resistance of the Elliptic Curve Point Multiplication using Eisenstein Integers. In Proceedings of the IEEE 10th International Conference on Consumer Electronics (ICCE), Berlin, Germany, 9–13 November 2020. [Google Scholar]
Figure 1. Elements of the Gaussian integer field G 29 with π = 5 + 2 i .
Figure 1. Elements of the Gaussian integer field G 29 with π = 5 + 2 i .
Cryptography 05 00006 g001
Figure 2. Illustration of the the Montgomery domain for p = 29 and π = 5 + 2 i . Circles centered with a point are possible quotients q after Montgomery reduction and filled circles are possible offsets α π .
Figure 2. Illustration of the the Montgomery domain for p = 29 and π = 5 + 2 i . Circles centered with a point are possible quotients q after Montgomery reduction and filled circles are possible offsets α π .
Cryptography 05 00006 g002
Table 1. Examples for primes of the form p = a 2 + b 2 with b = 1 or b = a 1 .
Table 1. Examples for primes of the form p = a 2 + b 2 with b = 1 or b = a 1 .
bitspab
1568 × 10 46 + 74 × 10 24 + 17113 2 × 10 23 + 93 2 × 10 23 + 92
169 4 × 10 50 + 216 × 10 25 + 2917 2 × 10 25 + 54 1
170 8 × 10 50 + 6 × 10 26 + 113 2 × 10 25 + 8 2 × 10 25 + 7
190 8 × 10 56 + 3 × 10 30 + 2813 2 × 10 28 + 38 2 × 10 28 + 37
256 8 × 10 76 + 2516 × 10 38 + 197821 2 × 10 38 + 315 2 × 10 38 + 314
382 9 × 10 114 + 384 × 10 57 + 4097 3 × 10 57 + 64 1
Table 2. Primes of the form p = a 2 + b 2 suitable for elliptic curve cryptography (ECC) applications and the percentage of occurrences of offset reduction steps.
Table 2. Primes of the form p = a 2 + b 2 suitable for elliptic curve cryptography (ECC) applications and the percentage of occurrences of offset reduction steps.
log 2 ( p ) abNo Reduction1 Reduction2 Reductions3 Reductions
188 2 94 150 1 91.7 % 4.4 % 2.4 % 1.5 %
189 2 94 94 a 1 91.9 % 5.0 % 1.5 % 1.6 %
198 2 99 34 1 91.6 % 4.1 % 2.5 % 1.6 %
199 2 99 37 a 1 91.6 % 5.3 % 1.5 % 1.7 %
208 2 104 120 1 91.5 % 4.0 % 2.7 % 1.8 %
209 2 104 10 a 1 91.6 % 4.2 % 2.7 % 1.6 %
Table 3. Complexity results for Algorithm 4 with different τ -adic expansions in comparison with ordinary integer expansions from [38] for a binary key of length r = 163 .
Table 3. Complexity results for Algorithm 4 with different τ -adic expansions in comparison with ordinary integer expansions from [38] for a binary key of length r = 163 .
Reference τ 2 or 2 w lM per PM
incl. Precomputations
proposed5 0.430 r 2372
[38]4 0.506 r 3054
proposed17 0.245 r 1866
[38]16 0.2515 r 2763
Table 4. Field-programmable gate array (FPGA) synthesis results for the point multiplication according to Algorithm 4 using the absolute value (abs.) and the Manhattan weight (Man).
Table 4. Field-programmable gate array (FPGA) synthesis results for the point multiplication according to Algorithm 4 using the absolute value (abs.) and the Manhattan weight (Man).
τ rLUTFFRAM
[kbit]
SlicesDSP f clk
[ MHz ]
Protected PM Latency
[ ms
abs.Man
2 + i 189154052117.342642277.596.60
4 + i 189154052119.142642275.684.93
4 + i 253189167820.453242127.926.87
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Back to TopTop