Apparatus and method to compute in Jacobian of hyperelliptic curve defined over Galois field of characteristic 2
AssigneeInternational Business Machines Corporation
InventorTetsuya Tamura
Life of this patent
Estimating the term…
Abstract
To implement an operation in Jacobian with improved computation complexity, the sum is computed of a divisor D1=g.c.d. (a1(x),y−b1(x)) and a divisor D2=g.c.d. (a2(x),y−b2(x)) on Jacobian of a hyperelliptic curve y2+y=f(x) defined over GF(2n) by: storing a1(x), a2(x), b1(x) and b2(x); and calculating q(x)=s1(b1(x)+b2(x)) mod a2(x) by using s1(x) in s1(x)a1(x)+s2(x)a2(x)=1 in case of GCD(a1(x),a2(x))=1 where GCD denotes a greatest common polynomial. Thus, a new function q(x) is provided so as to reduce the entire computational complexity and the hardware size. Moreover, in the case of D1=D2, a1(x) and b1(x) is stored; and q(x)=Q(b12(x)+f(x) mod a12(x), a1(x)) where Q(A,B) is a quotient of A/B is calculated.
Claims8
A cryptographic apparatus for computing the sum of a divisor D1=g.c.d. ((a1(x)), (y−b1(x))) and a divisor D2=g.c.d. ((a2(x)), (y−b2(x))) on Jacobian of a hyperelliptic curve y2+y=f(x) defined over GF(2n), said apparatus comprising:
- a storage for storing a1(x), a2(x), b1(x) and b2(x);
- means for calculating q(x)={s1(x) (b1(x)+b2(x))} mod a2(x) or q(x)={s2(x) (b1(x)+b2(x))} mod a1(x) by using s1(x) or s2(x) in s1(x)a1(x)+s2(x)a2(x)=1 in case of GCD(a1(x)), a2(x))=1 where GCD denotes a greatest common divisor of two polynomials;
- and
- means responsive to said means for calculating for permitting or denying access to a secure environment.
A cryptographic apparatus for calculating a′(x) and b′(x) of a reduced divisor D′=g.c.d. ((a′(x)), (y−b′(x))) which is a linearly equivalent to D1+D2 for a divisor D1=g.c.d. ((a1(x)), (y−b1(x))) and a divisor D2=g.c.d. ((a2(x)), (y−b2(x))) on Jacobian of a hyperelliptic curve y2+y=f(x) defined over GF(2n), said appratus comprising:
- means for calculating q(x)=s1(x) (b1(x)+b2(x)) mod a2(x) by using s1(x) in s1(x)a1(x)+s2(x)a2(x)=1 in case of GCD(a1(x), a2(x))=1 where GCD denotes a greatest common divisor of two polynomials;
- means for calculating α(x)=Q(q2(x)a1(x), a2(x))+Q(f(x), a1(x)a2(x) which is rendered a monic polynomial where Q(A,B) is a quotient of A/B;
- means for calculating β(x)=(q(x)a1(x)+b1(x)+1 mod α(x);
- means for calculating a′(x)=Q(f(x)+β2(x), α(x));
- means for calculating b′(x)=(β(x)+1) mod a′(x);
- and
- means responsive to said last mentioned means for calculating for permitting or denying access to a secure environment.
A cryptographic apparatus for computing the sum of a divisor D1=g.c.d. ((a1(x)), (y−b1(x))) on Jacobian of a hyperelliptic curve y2+y=f(x) defined over GF(2n), said apparatus comprising:
- a storage for storing a1(x), and b1(x);
- means for calculating q(x)=Q(b12(x)+f(x) mod a12(x), a1(x)) where Q(A,B) is a quotient of A/B;
- and
- means responsive to said means for calculating for permitting or denying access to a secure environment.
A cryptographic apparatus for calculating a′(x) and b′(x) of a reduced divisor D′=g.c.d. ((a′(x)), (y−b′(x))) which is a linearly equivalent to D1+D1 for a divisor D1=g.c.d. ((a1(x)), y−b1(x))) on Jacobian of a hyperelliptic curve y2+y=f(x) defined over GF(2n), said apparatus comprising:
- means for calculating q(x)=Q(b12(x)+f(x) mod a12(x), a1(x)) where Q(A,B) is a quotient of A/B;
- means for calculating α(x)=q2(x)+Q(f(x), a12(x)) which is rendered a monic polynomial;
- means for calculating β(x)=b12(x)+f(x) mod a12(x)+1) mod α(x);
- means for calculating a′(x)Q(f(x)+β2(x), α(x));
- means for calculating b′(x)=(β(x)+1 mod a′(x);
- and
- means responsive to said last mentioned means for calculating for permitting or denying access to a secure environment.
A computer implemented cryptographic method for calculating a′(x) and b′(x) of a reduced divisor D′=g.c.d. ((a′(x)), (y−b′(x))) which is a linearly equivalent to D1+D2 for a divisor D1=g.c.d. ((a1(x)), (y−b1(x))) and a divisor D2=g.c.d. ((a2(x)), y−b2(x))) on Jacobian of a hyperelliptic curve y2+y=f(x) defined over GF(2n), said method comprising the steps of:
- calculating and storing in a storage q(x)={s1(x) (b1(x)+b2(x))} mod a2(x) by using s1(x) in s1(x)a1(x)+s2(x)a2(x)=1 in case of GCD(a1(x), a2(x))=1 where GCD denotes a greatest common divisor of two polynomials;
- calculating and storing in a storage α(x)=Q(q2(x)a1(x), a2(x))+Q(f(x), a1(x)a2(x)) which is rendered a monic polynomial where Q(A,B) is a quotient of A/B;
- calculating and storing in a storage β(x)=(q(x)a1(x)+b1(x)+1) mod α(x);
- calculating and storing in a storage a′(x)=Q(f(x)+β2(x), α(x));
- calculating and storing in a storage b′(x)=(β(x)+1) mod a′(x);
- and
- permitting or denying access to a secure environment depending on an outcome of said calculating steps.
A computer implemented cryptographic method for calculating a′(x) and b′(x) of a reduced divisor D′=g.c.d. ((a′(x)), y−b′(x))) which is a linearly equivalent to D1+D1 for a divisor D1=g.c.d. ((a1(x)), (y−b1(x))) on Jacobian of a hyperelliptic curve y2+y=f(x) defined over GF(2n), said method comprising the steps of:
- calculating and storing in a storage q(x)=Q(b12(x)+f(x) mod a12(x), a1) where Q(A,B) is a quotient of A/B;
- calculating and storing in a storage α(x)=q2(x)+Q(f(x), a12(x) which is rendered a monic polynomial;
- calculating and storing in a storage β(x)=(b12(x)+f(x) mod a12(x)+1) mod α(x);
- calculating and storing in a storage a′(x)=Q(f(x)+β2(x), α(x));
- calculating and storing in a storage b′(x)=(β(x)+1) mod a′(x);
- and
- permitting or denying access to a secure environment depending on an outcome of said calculating steps.
A computer implemented cryptographic method for computing the sum of a divisor D1=g.c.d. ((a1(x)), (y−b1(x))) and a divisor D2=g.c.d. ((a2(x)), (y−b2(x))) on Jacobian of a hyperelliptic curve y2+y=f(x) defined over GF(2n), said method comprising the steps of:
- storing a1(x), a2(x), b1(x) and b2(x);
- calculating and storing in a storage q(x)={s1(x) (b1(x)+b2(x))} mod a2(x) or q(x)={s2(x) (b1(x)+b2(x))} mod a1(x) by using s1(x) or s2(x) in s1(x)a1(x)+s2(x)a2(x)=1 in case of GCD(a1(x), a2(x))=1;
- and
- permitting or denying access to a secure environment depending on an outcome of said calculating step.
A computer implemented cryptographic method for computing the sum of a divisor D1=g.c.d. ((a1(x)), (y−b1(x))) on Jacobian of a hyperelliptic curve y2+y=f(x) defined over GF(2n), said method comprising the steps of:
- storing a1(x), and b1(x);
- calculating and storing in a storage q(x)=Q(b12(x)+f(x) mod a12(x), a1(x)) where Q(A,B) is a quotient of A/B;
- and
- permitting or denying access to a secure environment depending on an outcome of said calculating step.
Dependencies are inferred from the claim text.