타원 곡선에서의 운영 비용 표

이 글에는 여러 가지 문제가 있다.이 문제를 개선하거나 대화 페이지에서 토의하십시오.(이러한 템플릿 메시지를 제거하는 방법 및 시기 알아보기) 이 글은 대부분의 독자들이 이해하기에는 너무 기술적인 것일 수도 있다. 기술 세부 정보를 제거하지 않고 비전문가가 이해할 수 있도록 개선하십시오.(2010년 2월) (이 템플릿 메시지를 제거하는 방법 및 시기 학습) 이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "타원 곡선 운영 비용 표" – 뉴스 · 신문 · 도서 · 학자 · JSTOR (2014년 5월) (이 템플릿 메시지 제거 방법과 시기 학습) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

타원곡선 암호는 타원곡선의 수학적 이론에 근거한 공용키 암호화의 일반적인 형태다.타원곡선의 점들은 이 추가 연산에 따라 추가될 수 있고 그룹을 형성할 수 있다.이 글은 타원 곡선 암호 알고리즘에 사용되는 이 그룹 추가 및 특정 관련 작업에 대한 계산 비용을 설명한다.

작업에 대한 약어

다음 절에서는 타원곡선으로 가능한 일부 연산의 모든 시간비용 표를 제시한다.표의 열은 다양한 계산 연산에 의해 라벨로 표시된다.표의 행은 타원곡선의 다른 모델에 대한 것이다.다음은 고려된 작업이다.

타원형 곡선의 추가(ADD) 및 이중화(DBL) 점이 어떻게 정의되는지 보려면 그룹 법칙을 참조하십시오.빠른 메스커 곱셈을 위해 곱셈을 하는 것의 중요성은 표 뒤에 논의된다.타원 곡선에서의 기타 가능한 연산에 대한 자세한 내용은 http://hyperelliptic.org/EFD/g1p/index.html을 참조하십시오.

표

일부 고정 분야의 요소에 대한 곱셈, 덧셈, 뒤집기에 대한 다른 가정 하에서, 이러한 운영의 시간 비용은 다양하다.이 표에서는 다음과 같이 가정한다.

I = 100M, S = 1M, *param = 0M, add = 0M, *const = 0M

즉, 원소를 반전시키려면 100 곱하기(M)가 필요하며, 원소의 제곱(S)을 계산하려면 1 곱하기, 매개변수(*param), 상수(*const)로 원소를 곱하거나 두 개의 원소를 추가하기 위해서는 어떤 곱하기 위해서도 필요하지 않다.

다른 가정으로 얻은 다른 결과에 대한 자세한 내용은 http://hyperelliptic.org/EFD/g1p/index.html을 참조하십시오.

원곡선 모양, 표현	DBL	추가	madd	mDBL	TPL	DBL+ADD
쇼트 위어스트라스 투영	11	14	11	8
a4=-1로 짧은 Weierstrass 투영	11	14	11	8
a4=-3으로 짧은 Weierstrass 투영	10	14	11	8
쇼트 위어스트라스 상대 야코비안[1]	10	11	(7)	(7)		18
트리플링 지향 도체-이카르트-코헬 곡선	9	17	11	6	12
헤시안 곡선 확장	9	12	11	9
헤시안 곡선 투영	8	12	10	6	14
자코비 쿼틱 XYZ	8	13	11	5
자코비 쿼틱 더블링 지향 XYZ	8	13	11	5
비틀린 헤시안 곡선 투영	8	12	12	8	14
더블 위주 도체-아이카르트-코헬 곡선	7	17	12	6
자코비 교차로 투영	7	14	12	6	14
자코비 교차로 확장	7	12	11	7	16
트위스트 에드워즈 투영	7	11	10	6
트위스트 에드워즈 반전	7	10	9	6
트위스트 에드워즈 연장	8	9	8	7
에드워즈 투영	7	11	9	6	13
자코비 쿼틱 더블링 지향 XXYZ	7	11	9	6	14
자코비 쿼틱 XXYZ	7	11	9	6	14
자코비 쿼틱 XXYZr	7	10	9	7	15
에드워즈 곡선 반전	7	10	9	6
몽고메리 곡선	4			3

두 배의 중요성

타원 곡선 암호화와 타원 곡선 인자화 방법(ECM)의 일부 적용에서는 스칼라 곱셈[n]P를 고려할 필요가 있다.이를 위한 한 가지 방법은 다음과 같이 연속적으로 계산하는 것이다.

${\displaystyle P,\quad [2]P=P+P,\quad [3]P=[2]P+P,\dots, [n]P=[n-1]P+P}$

그러나, [5]P = [2]([2]P) + P. 일반적으로 [k]P를 계산하려면 [k]P를 쓰는 것이 빠르다.

${\displaystyle k=\sum _{i\leq l}k_{i}2^{i}}}}$

{0_i,1} 및 $l{\displaystyle }$=${\displaystyle }$[ ${\displaystyle l}$ ${\displaystyle o}$ g ${\displaystyle {}_{}}$ ${\displaystyle {k\mathrm{}}_{}}$ ${\displaystyle ]}$ ${\displaystyle l=[log_{2}k$ k_l = 1인 경우:

${\displaystyle [2](....([2]([2]([2]([2]([2]P+[k_{(l-1)}]P)+[k_{(l-2)}]P)+[k_$${(l-3)}]P+\dots )\dots +[k_{1}]P)$$+[k_{0}]P=[2^{l}]P+[k_{{(l-1)}2^{l-1}]P+\dots +[k_{$1}$2]P+[k_{0}]P}$.

이 간단한 알고리즘은 최대 2l 스텝을 밟으며 각 스텝은 두 점을 추가하는 더블링 및 (k_i ≠ 0인 경우)로 구성된다.따라서, 이것은 추가와 두 배의 공식이 정의되는 이유 중 하나이다.나아가 이 방법은 어느 집단에나 적용이 가능하며, 집단법이 승법적으로 작성되면 대신 2중·다중 알고리즘을 정방·다중 알고리즘이라고 한다.

참조

• http://hyperelliptic.org/EFD/g1p/index.html