|
By Vladyslav Kovtun
Senior Software Developer
QArea
and
Stanyslav Zbitnev
Senior Software Developer
QArea
The authors propose a modification of method of divisors development in Jacobian of hyperelliptic curve over both even and odd characteristic fields in projective coordinates, this transform enhancing cryptographic security subsystem efficiency in information and telecommunications systems.
1. Foreword
The sweeping progress in Information Technologies implies severe requirements on modern information and telecommunication systems (ITS) as to securing confidence level, integrity, observability and authenticity of the information that is created, circulates and is being stored there. The most typical example of such ITS is the one of the bank. Survey [20] shows that such requirements of ITS can be ensured by applying a cryptographic data protection system which employs a public key cryptographic transformation subsystem.
As grounds for modern methods of public key cryptographic data protection, there accepted is transformation in the group of points over an elliptic curve (EC). In some countries, such cryptoprimitives are the grounds for cryptographic standards [16-19]. Nowadays transforms in Jacobian of hyperelliptic curve (HEC) are considered the most promising substitution of EC, since this allows to form multiple Abelian groups; while the significantly smaller baseline field this ensures the commensurable security. Standards [16-19] describe cryptographic primitives with the main operator of EC point scalar multiplication. The cryptographic transformation in Jacobian HEC is grounded on scalar multiplication [12] of no point but of reduced divisors. Main operators for scalar multiplication of reduced representation divisors (hereinafter referred to as divisors) are the addition and doubling of divisors.
At the same time, the increasing number of savers and growing popularity of remote tools for bank account management leads to continuous increase of load pressure on information protection system, and specifically on the public key cryptographic transformation subsystem, which affects operational efficiency when customer servicing. Thus, significant decrease in computational complexity (hereinafter, complexity) when dealing with labor effort in cryptographic primitives based on divisor multiplication in Jacobian HEC can be achieved, as it was said above, by means of reducing complexity of divisor scalar multiplication.
Until recently, arithmetic transforms in Jacobian HEC were performed in Cantor method [11] but with modifications introduced by Koblitz [4] and were considered elaborate both in terms of description and in terms of calculations, which kept them from practical application for cryptographic purposes.
In this context, it is lately that in Ukraine and abroad science people [1-15] pay much attention to enhancing efficiency of transforms in Jacobian HEC of fixed genus, which leads to developing improved methods of arithmetic transforms in Jacobian HEC. Methods of superposition and doubling for curves of genus 2 were considered in papers [9, 10]. The first practical implementation of these methods was performed by Harley [8]. The extension of the results [8] for curves over even characteristic fields is given in [6]. Further development of methods of superposition and doubling is given in papers [3, 14] and the results have also been extended for curves over even characteristic fields in [7, 15].
Yet, analysis of computational complexity of the known methods of arithmetic transforms in Jacobian genius 2 HEC over even and odd characteristics demonstrates that the existent methods fail to provide the required level of operational efficiency when servicing bank clients.
In fact, as it was shown in research paper [7], the time required for divisor scalar multiplication after Harley method in Jacobian genus 2 HEC over GF(281) field performed on workstation equipped with Intel Pentium IV@1.5 GHz processor 18.87 msec. does not provide for the target level of operational efficiency when servicing bank clients. In this light, the task of efficiency increase in an information security system, and in particular of divisor scalar multiplication in Jacobian HEC, gains particular topicality.
Since, these are genus 2 curves over fields of both even and odd characteristics that are of our main interest when decreasing difficulty of arithmetic transform methods in Jacobian HEC, let us consider the curves of the kind.
As can be seen in [1, 4], in operators of divisor addition and doubling in Jacobian HEC there exists the most complex field operation – inversion. As per [1, 2], in case of odd characteristic field the complexity of inversion operation Iinv takes on value within interval Iinv takes on value within interval 40Imul, 80Imul [2], while in case of even characteristic field – within interval 6Imul, 11Imul [1], where Imul – is the complexity of multiplication in the field. In [3], for the first time there is proposed an approach for implementing arithmetic operations in Jacobian genus 2 HEC but with no need to resort to field inversion. Further development of the proposed approach is given in papers [4, 5] while the results are improved and spread to a wider class of HEC over even characteristic field in papers [4, 5]. These methods are then considered as prototype for their further and more efficient modification.
By analogy with EC, let us denominate custom Mumford representation of divisors [u, v], u(x)=x2+u1x+u0, v(x)=v1x+v0, degv < degu ≤ 2 as affine, while let us denominate representation, arithmetic that do not use field inversion operation as projective; in this case divisor [u, v], u(x)=x2+U1/Z x + U0/Z, v(x)=V1/Z x + V0/Z is represented as [U1, U0, V1, V0, Z] [4], while weighted in case divisor [u, v], u(x)=x2+U1/Z12 x + U0/Z12, v(x)=V1/Z13Z2 x + V0/Z13Z2 is represented as [U1, U0, V1, V0, Z1, Z2] [5].
In compliance with the introduced constructions, the objective of the paper is in providing a modification of arithmetic method transforms in Jacobian genus 2 HEC in projective coordinates, in regard of decreasing complexity of the method, in order to increase efficiency of scalar multiplication operation.
In compliance with the adopted model [7, 8], as typical addition we shall denominate addition of [u1(x), v1(x)] and [u2(x), v2(x)] divisors with the resultant [r(u1(x), u2(x))] nonzero, while Doubling shall be Doubling of divisor [u1(x), v1(x)] with the resultant [r(u1(x), h(x)+2v1(x))] nonzero.
2. Decreased complexity projective arithmetic’s in Jacobian HEC projective coordinates
The proposed modification providing the decrease in complexity is based on Harley method [8] and modifications thereof [6]. In this connection in the method described it is suggested to apply the projective representation of divisors.
The Harley method [6, 8] divisor addition algorithm in typical case can be assumed as follows.
Algorithm A. Adding genus 2 HEC divisors
INPUT: Reduced divisor D1 = [u1, v1] and D2 = [u2, v2]
OUTPUT: Reduced divisor D3 = [u3, v3] = D1 + D2
| 1. |
| k = | f - v1h - v12 | ; (exact division) |
| u1 |
|
| 2. |
| s ≡ | v2 - v1 | modu1; |
| h + 2v1 |
|
| 3. | z = su1 |
| 4. |
| u' = | k - s(z + h + 2v1) | ; (exact division) |
| u2 |
|
| 5. | u3 = monic(u'); |
| 6. | v3 ≡ -(h + z + v1)modu3; |
| 7. | Return [u3, v3] |
The Harley method [6, 8] divisor Doubling algorithm in typical case can be assumed as follows.
Algorithm B. Doubling genus 2 HEC divisor
INPUT: Reduced divisor D1 = [u1, v1]
OUTPUT: Reduced divisor D2 = [u2, v2] = 2D1
| 1. |
| k = | v12 - v1h - f | ; (exact division) |
| u1 |
|
| 2. |
|
| 3. |
| u' = s2 + | k - s(h + 2v1) | ; (exact division) |
| u1 |
|
| 4. | u2 = monic(u'); |
| 5. | v2 ≡ -(h + su1 + v1)modu'; |
| 6. | Return (u2, v2) |
In A and B algorithms, the most elaborate in terms of manpower effort are operations in the ring of polynomial functions: division, multiplicative inversion, modular reduction, multiplication. For the sake of reduction the number of these operations is suggested to modify A and B algorithms in the following manner (in brackets, given are algorithm steps concerned by the modifications):
- In order to limit the power of polynomial functions, that specifies the devisor, along with transition from operations within the ring of polynomial functions to operations themselves in the field, there are used small fixed genus HECs (in our case it is genus 2) [8, 9] (at all steps);
- In order to simplify arithmetic operation procedures in the ring of polynomial functions, there is performed normalization thereof (A.3, B.2);
- In order to normalize and minimize Hamming weights of HEC parameters h(x) and f(x) there is applied HEC of particular view [3, 7] (A.1, A.2, A.4, A.6, B.1, B.2, B.3, B.5);
- In order to simultaneously invert several field elements, there is applied the Montgomery method [6-8] (A.2, B.2);
- In order to multiply polynomial functions with different powers, there is applied the Karatsuba method [6] (A.1, A.2, A.3, A.4, B.1, B.2, B.3, B.5);
- In order to modular reduce in polynomial functions with different powers, there is applied the Karatsuba method [8] (A.3, B.2);
- In order to exclude operations of multiplicative inversion over field, there are applied projective representation of divisors [3, 4] (A.2, A.5, B.2, B.4).
Arithmetic's in Jacobian HEC over uneven characteristics field
Grounded on the modifications proposed above, we obtain the following arithmetic transforms algorithms for HEC which is specified by the equation v2 + h(u)v = f(u) over Fq odd characteristic field, in projective coordinates, where h=h2x2+h1x+h0, hi  F2 and f=x5+f4x4+f3x3+f2x2+f1x+f0, f4 F2, fi Fq.
| Algorithm 1. Addition of reduced divisors |
| Input: | [U11, U10, V11, V10, Z1], [U21, U20, V21, V20, Z2] |
| Output: | [U1', U0', V1', V2', Z'] = [U11, U10, V11, V10, Z1] + [U21, U20, V21, V20, Z2] |
|
| |
Expression |
Operations
number |
| 1 |
Precomputation:
Z = Z1*Z2,
 21 = Z1*U21,
20 = Z1*U20,
 21 = Z1*V21,
20 = Z1*V20 |
5Imul |
| 2 |
Computation of r resultant for u1 and u2:
y1 = U11*Z2 - 21,
y2 = 20 - U10*Z2,
y3 = U11*y1 + y2*Z1,
r = y2*y3 + y12*U10
|
1Isqr, 6Imul |
| 3 |
Computation of almost inversion inv = r/u2 mod u1,
inv = inv1x + inv0:
inv1 = y1, inv0 = y3
|
|
| 4 |
Computation of s = (v1 - v2)inv mod u1, s = s1x + s0:
w0 = V10*Z2 - 20,
w1 = V11*Z2 - 21,
w2 = inv0*w0,
w3 = inv1*w1,
s1 = (inv0 + Z1*inv1)*(w0 + w1) - w2 - w3*(Z1 + U11),
s0 = w2 - U10*w3
If s1 = 0 then <Special case is considered>
|
8Imul |
| 5 |
Precomputation:
R = r*Z,
s2 = s0*Z,
s3 = s1*Z,
 = R*s3,
w0 = s1*s0,
w1 = s1*s3,
w2 = s0*s3,
w3 = w1*21,
w4 = R*s1
|
9Imul |
| 6 |
Computation of
l = x3 + l2x2 + l1x + l0:
l0 = w0*20,
l2 = w3 + w2,
l1 = (w1 + w0)*(21 + 20) - l0 - w3
|
2Imul |
| 7 |
Computation of
u' = (s(l + h + 2v1) - k)u1-1,
k = (f - v1h - v12)/u1,
u' = x2 + u1'x + u0':
0' = s22 + s1*y1*(s1*11 - 2s2) + y2*w1 + 2w4*21 +
+ h1* + R*[h2(s2 - s111) + r(y1 + 221 - f4Z)]
1' = 2w2 - s3s1y1 + h2 - R2
|
2Isqr, 8Imul |
| 8 |
Correction:
U0' = 0'*,
U1' = 1'*,
Z' = s32*
|
1Isqr, 3Imul |
| 9 |
Computation of
v' ≡ -(h + s1l + v2) mod u',
v' = v1'x + v0':
V1' = 1'*(l2 - 1' + h2) + s32(0' - h1 - w421 - l1),
V0' = 0'*(l2 - 1' + h2) - s32(l0 + h0 + w420)
|
5Imul |
| |
4Isqr , 46Imul |
|
In particular, with algorithm of addition one of the input divisors is often an affine (Z coordinate equals 1), while the other is projective. Thus, the result of addition comes projective. These input data with algorithm 1 allows its reduction to algorithm 2 which includes less number of field operations, and thus, provides reduction in complexity.
| Algorithm 2. Mixed addition of reduced divisors |
| Input: | [U11, U10, V11, V10, 1], [U21, U20, V21, V20, Z2] |
| Output: | [U1', U0', V1', V2', Z'] = [U11, U10, V11, V10, 1] + [U21, U20, V21, V20, Z2] |
|
| |
Expression |
Operations
number |
| 1 |
Precomputation:
11 = Z2*U11 |
1Imul |
| 2 |
Computation of r resultant for u1 and u2:
y1 = 11 - U21,
y2 = U20 - U10*Z2,
y3 = U11*y1 + y2,
r = y2*y3 + y12*U10
|
1Isqr, 4Imul |
| 3 |
Computation of almost inversion inv = r/u2 mod u1,
inv = inv1x + inv0:
inv1 = y1, inv0 = y3
|
|
| 4 |
Computation of s = (v1 - v2)inv mod u1, s = s1x + s0:
w0 = V10*Z2 - V20,
w1 = V11*Z2 - V21,
w2 = inv0*w0,
w3 = inv1*w1,
s1 = (inv0 + inv1)*(w0 + w1) - w2 - w3*U11),
s0 = w2 - U10*w3
If s1 = 0 then <Special case is considered>
|
7Imul |
| 5 |
Precomputation:
R = r*Z2,
s2 = s0*Z2,
s3 = s1*Z2,
= R*s3,
w0 = s1*s0,
w1 = s1*s3,
w2 = s0*s3,
w3 = w1*21,
w4 = R*s1
|
9Imul |
| 6 |
Computation of
l = su2,
l = l2x2 + l1x + l0:
l0 = w0*U20,
l2 = w3 + w2,
l1 = (w1 + w0)*(U21 + U20) - l0 - w3
|
2Imul |
| 7 |
Computation of
u' = (s(l + h + 2v1) - k)u1-1,
k = (f - v1h - v12)/u1,
u' = x2 + u1'x + u0':
0' = s22 + s1*y1*(s1*11 - 2s2) + y2*w1 + 2w4*V21 +
+ h1* + R*[h2(s2 - s111) + r(y1 + 2U21 - f4Z2)],
1' = 2w2 - s3s1y1 + h2 - R2
|
2Isqr, 8Imul |
| 8 |
Correction:
U0' = 0'*,
U1' = 1'*,
Z' = s32*
|
1Isqr, 3Imul |
| 9 |
Computation of
v' ≡ -(h + s1l + v2) mod u',
v' = v1'x + v0':
V1' = 1'*(l2 - 1' + h2) + s32(0' - h1 - w4V21 - l1),
V0' = 0'*(l2 - 1' + h2) - s32(l0 + h0 + w4V20)
|
5Imul |
| |
4Isqr , 39Imul |
|
Divisor doubling algorithm in its typical case has the following view.
| Algorithm 3. Doubling of reduced divisor |
| Input: | [U1, U0, V1, V0, Z] |
| Output: | [U1', U0', V1', V2', Z'] = 2[U1, U0, V1, V0, Z] |
|
| |
Expression |
Operations
number |
| 1 |
Precomputation:
Z2 = Z2,
1 = h1Z + 2V1 - h2U1,
0 = h0Z + 2V0 - h2U2
|
1Isqr |
| 2 |
Computation of r resultant for u and h +2v
(while  ≡ (h + 2v) mod u):
w0 = V12,
w1 = U12,
w2 = 12 = h12Z2 + 4w0 - h22w1,
w3 = 0*Z - U11,
r = 0*w3 + w2*U0
|
2Isqr, 4Imul |
| 3 |
Computation of almost inversion inv = r/ mod u,
inv = inv1x + inv0:
inv1 = -1, inv0 = w3
|
|
| 4 |
Computation of k ≡ [(f - hv - v2)/u] mod u, k = k1x + k0:
w3 = f3*Z2 + w1,
w4 = 2U0,
k1 = 2w1 + w3 - Z*(w4 + 2f4U1 + h2V1),
k0 = U1(Z*(2w4 + f4U1 + h2V1) - w3) +
+ Z*(Z*(f2Z - h1V1 - h2V0 - 2f4U0) - w0)
|
7Imul |
| 5 |
Computation of
s = k*inv mod u,
s = s1*x + s0
w0 = k0*inv0,
w1 = k1*inv1,
s0 = w0 - ZU0w1,
s3 = (inv0 + inv1)*(k0 + k1) - w0 - w1(1 + U1),
s1 = s3*Z
If s1 = 0 then <Special case is considered>
|
7Imul |
| 6 |
Precomputation:
R = r*Z2,
= R*s1,
w0 = s1*s3,
w1 = s0*s3,
w3 = w1*Z,
w4 = R*s3
|
6Imul |
| 7 |
Computation of
l = su,
l = l2x2 + l1x + l0:
l0 = U0*w1,
l2 = U1*w0,
l1 = (w1 + w0)*(U1 + U0) - l0 - l2
|
3Imul |
| 8 |
| Computation of
u' = [l2+ | 1 | * l(2v+h) - | 1 | *(f - vh - v2)]/u2, |
| 5 | 52 |
u' = x2 + u1'x + u0':
0' = s02 + 2w4*V1 + R*(h1s1 + U1*(2r*Z - h2s3) +
+ h2s0 - f4R),
1' = 2w3 + h2 - R2.
|
2Isqr, 4Imul |
| 9 |
Correction:
U0' = 0'*,
U1' = 1'*,
Z' = s12*
|
1Isqr, 3Imul |
| 10 |
Computation of
v' ≡ -(h + s1l + v2) mod u',
v' = v1'x + v0'
V1' = 1'*(l2 - 1' + w3 + h2) + s12*(1' - h1 - w4V1 - l1),
V0' = 0'*(l2 - 1' + w3 + h2) - s12(l0 + h0 + w4V0).
|
5Imul |
| |
6Isqr , 39Imul |
|
In particular, with algorithm of doubling one of the input divisors is often an affine (Z coordinate equals 1), while the other is projective. Thus, the result of doubling comes projective. These input data with algorithm 3 allows its reduction to algorithm 4 which includes less number of field operations, and thus, provides reduction in complexity.
| Algorithm 4.Mixed Doubling of reduced divisor |
| Input: | [U1, U0, V1, V0, 1] |
| Output: | [U1', U0', V1', V2', Z'] = 2[U1, U0, V1, V0, 1] |
|
| |
Expression |
Operations
number |
| 1 |
Precomputation:
1 = h1 + 2V1 - h2U1,
0 = h0 + 2V0 - h2U2
|
|
| 2 |
Computation of r resultant for u and h +2v
(while ≡ (h + 2v) mod u):
w0 = V12,
w1 = U12,
w2 = 12 = h12 + 4w0 - h22w1,
w3 = 0 - U11,
r = 0*w3 + w2*U0
|
2Isqr, 3Imul |
| 3 |
Computation of almost inversion inv = r/ mod u,
inv = inv1x + inv0:
inv1 = -1, inv0 = w3
|
|
| 4 |
Computation of k ≡ [(f - hv - v2)/u] mod u, k = k1x + k0:
w3 = f3 + w1,
w4 = 2U0,
k1 = 2w1 + w3 - (w4 + 2f4U1 + h2V1),
k0 = U1((2w4 + f4U1 + h2V1) - w3) +
+ (f2 - h1V1 - h2V0 - 2f4U0) - w0
|
1Imul |
| 5 |
Computation of
s = k*inv mod u, s = s1*x + s0:
w0 = k0*inv0,
w1 = k1*inv1,
s0 = w0 - U0w1,
s1 = (inv0 + inv1)*(k0 + k1) - w0 - w1(1 + U1).
If s1 = 0 then <Special case is considered>
|
5Imul |
| 6 |
Precomputation:
= r*s1,
w0 = s12,
w1 = s0*s1,
|
1Isqr, 2Imul |
| 7 |
Computation of
l = su,
l = l2x2 + l1x + l0:
l0 = U0*w1,
l2 = U1*w0,
l1 = (w1 + w0)*(U1 + U0) - l0 - l2
|
3Imul |
| 8 |
| Computation of
u' = [l2 + | 1 | *l(2v+h) - | 1 | * (f - vh - v2)]/u2, |
| 5 | 52 |
u' = x2 + u1'x + u0' :
0' = s02 + 2*V1 + h1 + r(h2s0 - U1*(2r - h2s1) - f4r),
1' = 2w1 + h2 - r2.
|
2Isqr, 3Imul |
| 9 |
Correction:
U0' = 0'*,
U1' = 1'*,
Z' = w0*
|
3Imul |
| 10 |
Computation of
v' ≡ -(h + s1l + v2) mod u',
v' = v1'x + v0':
V1' = 1'*(l2 - 1' + w1 + h2) + w0*(1' - h1 - V1 - l1),
V0' = 0'*(l2 - 1' + w1 + h2) - w0*(l0 + h0 + V0).
|
5Imul |
| |
5Isqr , 25Imul |
|
Now, let us consider arithmetic transforms with divisors in Jacobian HEC over even characteristic fields. HEC application over such fields allows a fortiori decrease the number of field operations in algorithms of arithmetic transforms at the cost of affine summands reduction.
Arithmetics in Jacobian HEC over even characteristics field
Grounded on the modifications of typical case algorithms of reduced divisor addition and Doubling proposed above, let us reduce the developed transforms algorithms for HEC which is specified by the equation v2 + h(u)v = f(u) over Fq even characteristic field, in projective coordinates, where h(x) = x and f = x5 + f1x + f0, fi F2.
| Algorithm 5. Addition of reduced divisors |
| Input: | [U11, U10, V11, V10, Z1], [U21, U20, V21, V20, Z2]
|
| Output: | [U1', U0', V1', V2', Z'] = [U11, U10, V11, V10, Z1] + [U21, U20, V21, V20, Z2] |
|
| |
Expression |
Operations
number |
| 1 |
Precomputation:
Z = Z1*Z2,
21 = Z1*U21,
20 = Z1*U20,
21 = Z1*V21,
20 = Z1*V20.
|
5Imul |
| 2 |
Computation of r resultant for u1 and u2:
y1 = U11Z2 + 21,
y2 = 20 + U10Z2,
y3 = y1U11 + y2Z1,
r = y2*y3 + y12*U10
|
1Isqr, 6Imul |
| 3 |
Computation of almost inversion inv = r/u2 mod u1,
inv = inv1x + inv0:
inv1 = y1, inv0 = y3
|
|
| 4 |
Computation of s = (v1 - v2) inv mod u1, s = s1x + s0:
w0 = V10Z2 + 20,
w1 = V11Z2 + 21,
w2 = inv0w0,
w3 = inv1w1
s1 = (inv0 + Z1inv1)*(w0 + w1) + w2 + w3(Z1 + U11),
s0 = w2 + U10*w3.
If s1 = 0 then <Special case is considered>
|
8Imul |
| 5 |
Precomputation:
R = r*Z,
s2 = s0*Z,
s3 = s1*Z,
= R*s3,
w0 = s1*s0,
w1 = s1*s3,
w2 = s0*s3,
w3 = w1*21,
w4 = R*s1
|
9Imul |
| 6 |
Computation of
l = su2,
l = x3 + l2x2 + l1x + l0:
l0 = w0*20,
l2 = w3 + w2,
l1 = (w1 + w0)*(21 + 20) + l0 + w3
|
2Imul |
| 7 |
Computation of
u' = (s(l + h + 2v1) - k)u1-1,
k = (f - v1h - v12) / u1,
u' = x2 + u1'x + u0':
0' = s22 + y1(s12*(y1 + U21) + R*r) + y2w1,
1' = w1*y1 + R2.
|
2Isqr, 5Imul |
| 8 |
Correction:
U0' = 0'*,
U1' = 1'*,
Z' = s32*
|
1Isqr, 3Imul |
| 9 |
Computation of
v' ≡ -(h + s1l + v2) mod u',
v' = v1'x + v0':
V1' = 1'*(l2 + 1') + s32*(0' + w421 + + l1),
V0' = 0'*(l2 + 1') + s32*(l0 + w420)
|
6Imul |
| |
4Isqr , 44Imul |
|
Divisor mixed addition algorithm has the following view.
| Algorithm 6. Mixed addition of reduced divisors |
| Input: | [U11, U10, V11, V10, 1], [U21, U20, V21, V20, Z2]
|
| Output: | [U1', U0', V1', V2', Z'] = [U11, U10, V11, V10, 1] + [U21, U20, V21, V20, Z2] |
|
| |
Expression |
Operations
number |
| 1 |
Precomputation:
11 = Z2*U11.
|
1Imul |
| 2 |
Computation of r resultant for u1 and u2:
y1 = 11 + U21,
y2 = U20 + U10Z2,
y3 = y1U11 + y2,
r = y2*y3 + y12*U10
|
1Isqr, 4Imul |
| 3 |
Computation of almost inversion inv = r/u2 mod u1,
inv = inv1x + inv0:
inv1 = y1, inv0 = y3
|
|
| 4 |
Computation of s = (v1 - v2) inv mod u1, s = s1x + s0:
w0 = V10Z2 + V20,
w1 = V11Z2 + V21,
w2 = inv0w0,
w3 = inv1w1,
s1 = (inv0 + inv1)*(w0 + w1) + w2 + w3U11,
s0 = w2 + U10*w3
If s1 = 0 then <Special case is considered>
|
7Imul |
| 5 |
Precomputation:
R = r*Z2,
s2 = s0*Z2,
s3 = s1*Z2,
= R*s3,
w0 = s1*s0,
w1 = s1*s3,
w2 = s0*s3,
w3 = w1*U21,
w4 = R*s1
|
9Imul |
| 6 |
Computation of
l = su2,
l = l2x2 + l1x + l0:
l0 = w0*U20,
l2 = w3 + w2,
l1 = (w1 + w0)*(U21 + U20) + l0 + w3
|
2Imul |
| 7 |
Computation of
u' = (s(l + h + 2v1) - k)u1-1,
k = (f - v1h - v12) / u1,
u' = x2 + u1'x + u0'
0' = s22 + s12*y1*U11 + y2*w1 + + R*r*y1,
1' = w1*y1 + R2.
|
3Isqr, 5Imul |
| 8 |
Correction:
U0' = 0'*,
U1' = 1'*,
Z' = s32*
|
1Isqr, 3Imul |
| 9 |
Computation of
v' ≡ -(h + s1l + v2) mod u',
v' = v1'x + v0':
V1' = 1'*(l2 + 1') + s32*(0' + w4V21 + l1),
V0' = 0'*(l2 + 1') + s32*(l0 + w4V20)
|
6Imul |
| |
5Isqr , 37Imul |
|
Divisor Doubling algorithm in its typical case has the following view.
| Algorithm 7. Doubling of reduced divisor |
| Input: | [U1, U0, V1, V0, Z] |
| Output: | [U1', U0', V1', V2', Z'] = 2[U1, U0, V1, V0, Z] |
|
| |
Expression |
Operations
number |
| 1 |
Precomputation:
Z2 = Z2,
w0 = V12,
w1 = U12
|
3Isqr |
| 2 |
Computation of r resultant for u and h +2v
(while ≡ (h + 2v) mod u):
R = U0*Z22.
|
1Isqr, 1Imul |
| 3 |
Computation of almost inversion inv = r/ mod u,
inv = inv1x + inv0:
inv1 = Z, inv0 = Z*U1
|
1Imul |
| 4 |
Computation of k ≡ [(f - hv - v2)/u] mod u, k = k1x + k0:
k1 = w1,
k0 = U1*w1 + Z*(Z*V1 + w0)
|
3Imul |
| 5 |
Computation of
s = k*inv mod u, s = s1*x + s0:
w0 = k0*inv0,
w1 = k1*Z,
s0 = w0 + Z*U0w1,
s3 = (inv0 + Z)*(k0 + k1) + w0 + w1(1 + U1),
s1 = s3*Z
If s1 = 0 then <Special case is considered>
|
7Imul |
| 6 |
Precomputation:
= R*s1,
w0 = s1*s3,
w1 = s0*s3,
w3 = w1*Z,
w4 = R*s3
|
5Imul |
| 7 |
Computation of
l = su,
l = l2x2 + l1x + l0:
l0 = U0*w1,
l2 = U1*w0,
l1 = (w1 + w0)*(U1 + U0) + l0 + l2
|
3Imul |
| 8 |
| Computation of
u' = [l2 + | 1 | * l(2v+h) - | 1 | * (f - vh - v2)]/u2, |
| 5 | 52 |
u' = x2 + u1'x + u0' :
0' = s02 + ,
1' = R2.
|
2Isqr |
| 9 |
Correction:
U0' = 0'*,
U1' = 1'*,
Z' = s12*
|
1Isqr, 3Imul |
| 10 |
Computation of
v' ≡ -(h + s1l + v2) mod u',
v' = v1'x + v0':
V1' = 1'*(l2 + 1' + w3) + s12*(0' + + w4*V1 + l1),
V0' = 0'*(l2 + 1' + w3) + s12(l0 + w4V0)
|
6Imul |
| |
7Isqr , 29Imul |
|
Divisor mixed Doubling algorithm in its typical case is given below.
| Algorithm 8. Mixed Doubling of reduced divisor |
| Input: | [U1, U0, V1, V0, 1] |
| Output: | [U1', U0', V1', V2', Z'] = 2[U1, U0, V1, V0, 1] |
|
| |
Expression |
Operations
number |
| 1 |
Computation of almost inversion for inv ≡ r/ mod u,
inv = inv1x + inv0:
inv1 = 1,
inv0 = U1
|
|
| 2 |
Computation of
k ≡ [(f - hv - v2)/u] mod u,
k = k1x + k0:
w0 = V12,
w1 = U12,
k1 = w1,
k0 = U1*w1 + V1 + w0,
|
2Isqr, 1Imul |
| 3 |
Computation of s = k*inv mod u, s = s1x + s0:
w0 = k0*inv0,
w1 = k1,
s0 = w0 + U0*w1,
s1 = k0
|
2Imul |
| 4 |
Precomputation:
= U0*s1,
w0 = s12,
w1 = s0*s1
|
2Imul |
| 5 |
Computation of
l = su,
l = l2x2 + l1x + l0:
l0 = U0*w1,
l2 = U1*w0,
l1 = (w1 + w0)*(U1 + U0) + l0 + l2.
|
3Imul |
| 6 |
| Computation of
u' = [l2 + | 1 | * l(2v+h) - | 1 | * (f - vh - v2)]/u2, |
| 5 | 52 |
u' = x2 + u1'x + u0' :
0' = s02 + ,
1' = U02.
|
2Isqr |
| 7 |
Correction:
U0' = 0'*,
U1' = 1'*,
Z' = w0*
|
3Imul |
| 8 |
Computation of
v' ≡ -(h + s1l + v2) mod u',
v' = v1'x + v0':
V1' = 1'*(l2 + 1' + w1) + w0*(0' + + *V1 + l1),
V0' = 0'*(l2 + 1' + w1) + w0*(l0 + *V0).
|
6Imul |
| |
4Isqr , 17Imul |
|
Analysis of computational complexity
In Table 1, there is given the complexity evaluation of known [3-5, 7] and above suggested algorithms of arithmetic transforms in Jacobian HEC with typical cases. The algorithm complexity is shown in field operations.
| Table 1 |
| Genius 2 HEC parameters | Algorithms |
| Addition |
Mixed
addition |
Doubling |
Mixed
Doubling |
| 0-1 |
^2 |
* |
0-1 |
^2 |
* |
0-1 |
^2 |
* |
0-1 |
^2 |
* |
| Odd characteristic field |
| Affine coordinates |
| f4 = 0 [7] |
1 |
3 |
22 |
|
|
|
1 |
5 |
22 |
|
|
|
| Projective coordinates [U1, U0, V1, V0, Z] |
| deg(h) = 2, hi F2 [4] |
|
4 |
47 |
|
3 |
40 |
|
6 |
40 |
|
5 |
25 |
| deg(h) = 2, hi F2 [*] |
|
4 |
46 |
|
4 |
39 |
|
6 |
39 |
|
5 |
25 |
| Weighted coordinates [U1, U0, V1, V0, Z1, Z2, Z12, Z22] |
| f4 = 0, h(x) = 0 [5] |
|
7 |
47 |
|
5 |
36 |
|
7 |
34 |
|
5 |
21 |
| Even characteristic field |
| Affine coordinates |
| f4 = 0 [7] |
1 |
3 |
21 |
|
|
|
1 |
5 |
20 |
|
|
|
| h2 = 0, f4 = 0 [7] |
1 |
3 |
21 |
|
|
|
1 |
5 |
17 |
|
|
|
| h(x) = x, f4 = 0, f3 = f2 = 0 [6] |
|
|
|
|
|
|
1 |
6 |
9 |
|
|
|
| Projective coordinates [U1, U0, V1, V0, Z] |
| h(x) = x, f4 = 0, f3 = f2 = 0 [6] |
|
5 |
45 |
|
5 |
38 |
|
6 |
31 |
|
5 |
18 |
| h(x) = x, f4 = 0, f3 = f2 = 0 [*] |
|
4 |
44 |
|
5 |
37 |
|
7 |
29 |
|
4 |
17 |
| Weighted coordinates [U1, U0, V1, V0, Z1, Z2, Z12, Z22, Z1Z2, Z13Z2] |
| f4 = 0, h2 ≠ 0 [5] |
|
4 |
46 |
|
5 |
35 |
|
6 |
35 |
|
5 |
24 |
| f4 = 0, h2 = 0 [5] |
|
6 |
44 |
|
6 |
34 |
|
6 |
29 |
|
6 |
19 |
With asterisk [*] signed are conditions that are used in the suggested modifications of the algorithm.
As it can be seen in Table 1, of the least complexity are algorithms of addition, mixed addition, Doubling and mixed Doubling in projective coordinates over even and uneven characteristic fields constructed in accordance with the method modified by the authors, which results in reduction by one multiplication operation over field if compared to [4, 6].
Conclusion
In accordance with the paper objective, there was developed a method of arithmetic transforms in Jacobian genus 2 HEC in projective coordinates which provides a lower complexity if compared to the existent methods [4, 6] and, thus, allowing for increase in the efficiency of scalar multiplication. This modification is characterized by the following:
- in order to reduce the number of recomputable values, there is performed a precomputation and keeping of the results which reduces time complexity if compared to [6-8];
- in order to increase the number of recomputable values, the queue of field operations is changed if compared to the existent methods [6-8];
- n order to increase the number of precomputable values, considered are some earlier unknown dependencies between the resultant polynomial functions.
The suggested modification of method of arithmetic transforms in Jacobian genus 2 HEC results in 3 to 15 per cent reduction of computational complexity dependant on arithmetic operations used and curve type. It is known [1-2] that average scalar multiplication complexity is:
| I |
D |
= |
1 |
tI |
D |
+ tI |
D |
| mul |
2 |
add |
dbl |
|
where t — is bit length of scalar factor,
| I |
D |
, I |
D |
- are complexities of divisor addition and Doubling respectively. |
| add |
dbl |
|
Thus, applying the suggested method of transforms may reduce computational complexity when scalar multiplication by 4 per cent is compared to known concurrents [4, 6].
To be more specific, when processing transactions in a bank processing center this can cause some 4 per cent time reduction when verifying digital signatures.
References
1. D. Hankerson, J. Lopez Hernandez, A. Menezes. Software implementation of elliptic curve cryptography over binary fields.
2. M. Brown, D. Hankerson, J. Lopez, A. Menezes. Software implementation of the NIST elliptic curves over prime fields.
3. Y. Miyamoto, H. Doi, K. Matsuo, J. Chao, S.Tsujii. A fast addition algorithm of genius two hyperelliptic curve. In the 2002 Symposium on cryptography and information security – SCIS 2002, IEICE Japan, pp.497-502, 2002. In Japanese.
4. T. Lange. Inversion-free arithmetic on genius 2 hyperelliptic curves. Cryptology ePrint Archive, report 2002/147, 2002. Available http://eprint.iacr.org.
5. T. Lange. Weighted coordinates on genius 2 hyperelliptic curves. Cryptology ePrint Archive, report 2002/153, 2002. Available http://eprint.iacr.org.
6. T. Wollinger. Software and hardware implementation of hyperelliptic curve cryptosystems. PhD dissertation. Bochum, Germany, May 2004.
7. T. Lange. Efficient arithmetic on genius 2 hyperelliptic curves over finite fields via explicit formulae. Cryptology ePrint Archive, report 2002/121, 2002. Available http://eprint.iacr.org.
8. R. Harley. Fast arithmetic on genius 2 curves. Available at: http://cristal.infra.fr/~harley/hyper. 2000.
9. A.M. Spallek. Kurven vom geschlecht 2 und ihre anwendung in public-key-kryptosystemen. PhD thesis, Universitat Gesamthochschule Essen, 1994.
10. U. Kriger. Anwendung hyperellipischer kurven in der kryptographie. Master’s thesis, Universitat Gesamthochschule Essen, 2001.
11. D.G. Cantor. Computing in the jacobian of hyperelliptic curve. Math. Comp., No 48. pp. 95-101, 1987.
12. N. Koblitz. Hyperelliptic cryptosystems. Journal of cryptology, No 1. pp.139-150, 1989.
13. T. Lange. Efficient arithmetic on hyperelliptic curves. PhD thesis, Universitat Gesamthochschule Essen, 2001.
14. M. Takahashi. Improving Harley algorithms for jacobians of genius 2 hyperelliptic curves. In Proc. of SCIS2002, IEICE Japan, 2002. in Japanese.
15. H. Suguzaki, K. Matsuo, J. Chao, S. Tsujii. An extension of Harley algorithm addition algorithm for hyperelliptic curves over finite fields of characteristic two. Technical report ISEC2002-9 (2002-5), IEICE Japan, 2002. pp. 49-56.
16. International Organization for Standardization. ISO/IEC FCD 15946-2: Information technology - Security techniques - Cryptographic techniques based on elliptic curves - Part 2: Digital signatures, Final Committee Draft, 1999.
17. IEEE P1363-2000. Standard Specifications for Public Key Cryptography. Available at: http://www.ieee.org
18. ???? ? 34.10-2001. ??????????????? ???????? ?????????? ?????????. ?????????????? ??????????. ????????????????? ?????? ??????????. ???????? ???????????? ? ???????? ??????????? ???????. ?. ???????????.
19. ???? 4145-2002. ???????????? ??????????. ??????????????? ?????? ??????????. ???????? ??????, ?? ??????????? ?? ?????????? ??????. ?????????? ?? ?????????.
20. W. Diffie, M. Hellman. New directions in cryptography. IEEE Transactions on information theory. pp. 644-654. November 1976.
Zbitnev, Stanyslav, Doctor of Science
Professor at IT Security chair at Kharkiv National Technical University of Radioelectronics, Lenin Ave., 14, Kharkiv, 61166, Ukraine.
Range of scientific interests: IT security, cryptographic transforms on algebraic curves.
Kovtun, Vladyslav, Doctor of Science
Senior Staff Scientist at Computer Systems chair at Kharkiv University of Air Force, Sumskaya St., 77/79, Kharkiv, 61023, Ukraine.
Range of scientific interests: IT security, cryptographic transforms on algebraic curves.
|
QArea Newsletter
