자코비 곡선

Jacobian curve

수학에서 자코비 곡선위어스트라스 방정식으로 정의되는 일반적인 타원곡선과 다른 타원곡선을 나타낸 것이다.때로는 단순하고 차동 전력 분석 스타일(SPA) 공격에 대한 방어를 제공할 수 있기 때문에 위어스트라스 형태 대신 암호법에 사용되기도 한다. 실제로 일반적인 추가 공식을 사용하는 것은 이 형태의 타원곡선에서 한 점을 두 배로 증가시키기 위해 가능하다. 이렇게 하면 두 운영은 구별할 수 없게 된다.일부 사이드 채널 정보를 생략한다.[1]자코비 곡선은 또한 위어스트라스 곡선에 비해 더 빠른 산수를 제공한다.

자코비 곡선은 두 표면의 교차점에 의해 주어지는 자코비 교차점과 자코비 사분위의 두 가지 유형으로 구성될 수 있다.

타원 곡선: 기본 사항

Given an elliptic curve, it is possible to do some "operations" between its points: for example one can add two points P and Q obtaining the point P + Q that belongs to the curve ; given a point P on the elliptic curve, it is possible to "double" P, that means find [2]P = P + P (the square brackets are used to indicate [n]P, the point P added n times) 또한 찾기를 의미하는 P의 부정을 찾는다.이렇게 해서 타원곡선의 점들이 그룹을 형성한다.그룹 연산의 ID 요소는 어핀 평면의 점이 아니라 투영 좌표에만 나타난다는 점에 유의하십시오. 그러면 O = (0: 1: 0)는 그룹 법칙중립 요소인 "무한의 지점"이다.공식을 추가하고 두 배로 늘리는 것은 타원곡선에 있는 점 P의 n번째 배수인 [n]P를 계산하는 데도 유용하다. 이 연산은 타원곡선 암호법에서 가장 많이 간주된다.

필드 K 위에 있는 타원 곡선 EWeierstrass 형식2 y = x3 + + b에 넣을 수 있으며, a, b는 K에 넣을 수 있다.나중에 중요해질 것은 순서 2이다. 즉 [2]P = O와 P O와 같은 EP이다. P = (p, 0)가 E의 점이라면 순서 2가 있다. 보다 일반적으로 순서 2의 지점은 다항 f(x) = x3 + 도끼 + b의 뿌리에 해당한다.

이제부터 우리는 Ea,b 이용하여 위어스트라스폼 y2 = x + 도끼3 + b로 타원곡선을 나타낼 것이다.

만약a,b E가 입방 다항식3 x + 도끼 + bK에 3개의 뚜렷한 뿌리를 가지고 있다면, 우리는 Legendre 정상 형태Ea,b 쓸 수 있다.

Ea,b: y2 = x(x + 1)(x + j)

이 경우 순서 2의 세 지점이 있다: (0, 0), (–1, 0), (–j, 0).이 경우 우리는 E[j]라는 표기법을 사용한다.ja, b 단위로 표현할 수 있다는 점에 유의한다.

정의: 자코비 교차로

P3(K)의 타원곡선은 두 개의 사분면 교차점으로 나타낼 수 있다.

타원곡선의 자코비 형태를 두 개의 사분위의 교차점으로 정의할 수 있다.Ea,b Weierstrass 형식의 타원형 곡선으로 하고, 거기에 다음과 같은 지도를 적용한다.

우리는 다음과 같은 방정식 체계가 유지된다고 본다.

E[j] 곡선은 P3(K)에서 다음과 같은 표면 교차점에 해당한다.

"특수사례" E[0], 타원곡선은 이중점을 가지므로 단수적이다.

S1다음같은 변환을 E[j]에 적용하여 얻는다.

ψ: E[j]S1

집단법

S1의 경우 그룹의 중립 요소는 지점(0, 1, 1, 1)이며, 이는 ψ 아래의 O = (0: 1: 0)의 이미지인 것이다.

덧셈 및 더블링

P1 = (X11, Y, Z1, T1)와2 P = (X2, Y, Z2, T22), S1의 두 점을 감안할 때 P3 = P1 + P 지점2 좌표는 다음과 같다.

이러한 공식은 두 배로 하는 데도 유효하다: P1 = P2 갖는 것은 충분하다. 따라서 S1에서 점의 추가 또는 배점은 16 곱하기 1 곱하기 1을 상수(k)로 해야 하는 작업이다.

P1 두 배로 늘리고 P3 = [2]P1 찾기 위해 다음과 같은 공식을 사용할 수도 있다.

이 공식을 사용하면 한 점을 두 배로 늘리기 위해 8개의 승수가 필요하다.그러나, 7배만 더하면 되는 2배의 효율적인 "전략"이 있다.[2]이렇게 하면 23배수로 한 점을 3배로 늘릴 수 있다. 실제로 [3]P1 [2]P1 경우 7배, P1 + [21[2]]P의 경우 16배의 비용으로 P1 더하면1 얻을 수 있다.

추가 및 두 배의 예

K = R 또는 C로 두고 다음과 같은 경우를 고려하십시오.

Consider the points and : it is easy to verify that P1 and P2 belong to S1 (it is sufficient to see that these points satisfy both equations of the system S1).

두 점을 추가하기 위해 위에 주어진 공식을 사용하여 P3 대한 좌표(P31 = P + P2)는 다음과 같다.

결과점은 P =( ,4 - 3, 입니다

위에 제시된 두 배의 공식으로 P3 = [2]P1:

따라서 이 경우 P3 = [2]P1 = (0, 12, –12, 12)

부정

1 P = (X1, Y, Z1, T)를11 S1에서 볼 때 부정은 -P1 = (-X1, Y, Z1, T11)

부속 좌표 추가 및 2배 증가

1 개의 부속점1 P = (x11, y, z2)와2 P = (x22, y, z)가 주어진 경우, 이들의 합은 다음과 같은 좌표를 갖는 P 지점이다3.

이러한 공식은 조건 P1 = P2 함께 두 배로 증가하는데도 유효하다.

확장좌표

자코비 교차로에서 한 점을 나타낼 수 있는 다른 종류의 좌표계가 있다.자코비 교차로 양식에서 다음과 같은 타원형 곡선이 주어진다.

확장 좌표X, Y, Z, T, XY, ZT 변수와 함께 P = (x, y, z)를 설명하고 여기서 다음을 설명한다.

어떤 특정한 상황에서는 (시간비용 측면에서) 더 편리하기 때문에 때때로 이러한 좌표를 사용한다.이러한 좌표 사용에 따른 작업에 대한 자세한 내용은 http://hyperelliptic.org/EFD/g1p/auto-jintersect-extended.html을 참조하십시오.

정의: 자코비 4중주

등식 = - 1 + 1{\의 자코비 4분위수

자코비 쿼티크 형태의 타원곡선은 적어도 하나의 순서 2의 지점이 있는 위어스트라스 형태의 E 곡선에서a,b 얻을 수 있다.다음 변환 f (X: Y: Z) = (sX: sY2: sZ)의 자코비 좌표의 점으로 Ea,b 각 점을 보낸다.

f: Ea,bJ
[3]

F를a,b E에 적용하면 다음 형태의 J로 곡선을 얻는다.

[3]

여기서:

= -( 2+ ) = e

K. C의 원소는 자코비 정사각형 형태의 타원곡선을 나타내며, 자코비 좌표로 표시된다.

아핀 좌표상의 자코비 4중주

아핀 좌표에서 자코비 정사각형 곡선의 일반적인 형태는 다음과 같다.

= x + +

여기서 e = 1을 가정한다.

집단법

C집단법의 중립적 요소는 투영점(0:1:1)이다.

부속 좌표 추가 및 2배 증가

Given two affine points and , their sum is a point , such that:

자코비 교차로에서와 마찬가지로, 이 경우에도 이 공식을 사용하여 두 배로 증가시키는 것이 가능하다.

투영 좌표 추가 및 2배 증가

C′에서 P1 = (X11: Y: Z1)와2 P = (X22: Y: Z2)의 두 점을 볼 때 P33 = (X33: Y: Z3) 지점의 좌표는 다음과 같은 공식에 의해1 P2 P1 측면에서2 주어진다.

P2 = P11: 이 상태에서 P3 = P: 1 P = P + P = [2]P1 구한다는 조건과 함께 이 공식을 두 배로 사용할 수도 있다.

두 점을 추가하는 데 필요한 승수는 13+3 상수별 승수: 특히 상수 e에 의한 승수와 상수 d에 의한 승수가 각각 2개씩 있다.

가산점과 복점화에 필요한 연산을 줄이기 위한 "전략"이 있다: 승수의 수를 상수별 11+3 배수로 줄일 수 있다(자세한 내용은 섹션 3 참조).

상수 ed: 자코비 형태의 타원형 곡선을 수정하여 증분 및 배분을 위한 연산 횟수를 줄일 수 있다.따라서 예를 들어, C의 상수 d가 유의하게 작으면 d에 의한 곱셈을 취소할 수 있다. 그러나 가장 좋은 옵션은 e: 작으면 1개뿐 아니라 2개의 곱셈을 무시하는 것이다.

추가 및 두 배의 예

타원 곡선 E4,0 고려하십시오. 이 곡선에는 2: P = (p, 0) = (0, 0)의 점이 있다.따라서 a = 4, b = p = 0이므로 e = 1과 d = 1을 가지며 관련 자코비 쿼트릭 형식은 다음과 같다.

Choosing two points and , it is possible to find their sum P3 = P1 + P2 using the formulae for adding given above:

= - 2 = - 2}=2}- 2.

그렇게

=( + : 5 + :- ) .

동일한 공식을 사용하여 P4 = [2]P1 점을 구한다.

그렇게

=( : : 0) .

부정

P1 = (X11: Y: Z1)의 부정은 다음과 같다: -P1 = (-X11: Y1: Z)

자코비 정사각형의 대체 좌표

자코비 정사각형의 한 점을 나타내기 위해 사용될 수 있는 다른 좌표계들이 있다: 그것들은 특정한 경우에 빠른 계산을 얻기 위해 사용된다.이러한 좌표를 사용하는 작업에 필요한 시간 비용에 대한 자세한 내용은 http://hyperelliptic.org/EFD/g1p/auto-jquartic.html을 참조하십시오.

아핀 자코비 4중주술을 받았어

더블링 지향 XXYZZ 좌표는 + c2 = 12 만족하는 추가 곡선 매개변수 c를 도입하며 다음과 같이 점(x, y)(X, XX, Y, Z, ZZ, R)으로 나타낸다.

더블링 지향 XYZ 좌표는 동일한 추가 가정(a2 + c2 = 1)을 갖는 점(x, y)을 나타내며 (X, Y, Z)은 다음 방정식을 만족한다.

XXYZZ 좌표를 사용하면 추가적인 가정은 없으며 다음과 같은 점(x, y)을 (X, XX, Y, Z, ZZ)으로 나타낸다.

XXYZR 좌표 (x, y)(X, XX, Y, Z, ZZ, R)로 나타내지만, 다음과 같다.

XYZ 좌표 점(x, y)(X, Y, Z)에 의해 다음과 같이 주어진다.

= /

참고 항목

특정 경우에 필요한 실행 시간에 대한 자세한 내용은 타원 곡선 운영 비용 표를 참조하십시오.

메모들

  1. ^ Olivier Billlet, 타원곡선과 측면채널 해석의 자코비 모델
  2. ^ a b P.Y.Liardet과 N.P.Jacobi Form, 페이지 397을 사용하여 ECC 시스템에서 SPA/DPA를 방지하는 스마트한 기능
  3. ^ a b 올리비에 빌렛과 마크 조예 타원곡선과 측면채널 분석의 자코비 모델, 페이지 37-38
  4. ^ 실베인 듀크스네, 자코비 모델-I3M, (UMR CNRS 5149) 및 리름, (UMR CNRS 5506), 몬펠리에 2세 우주선

참조

  • Olivier Billet, Marc Joye (2003). "The Jacobi Model of an Elliptic Curve and Side-Channel Analysis". The Jacobi Model of an Elliptic Curve and the Side-Channel Analysis. Lecture Notes in Computer Science. Vol. 2643. Springer-Verlag Berlin Heidelberg 2003. pp. 34–42. doi:10.1007/3-540-44828-4_5. ISBN 978-3-540-40111-7.
  • P.Y. Liardet, N.P. Smart (2001). "Preventing SPA/DPA in ECC Systems Using the Jacobi Form". Cryptographic Hardware and Embedded Systems — CHES 2001. Lecture Notes in Computer Science. Vol. 2162. Springer-Verlag Berlin Heidelberg 2001. pp. 391–401. doi:10.1007/3-540-44709-1_32. ISBN 978-3-540-42521-2.
  • http://hyperelliptic.org/EFD/index.html

외부 링크