일반적으로 타원 곡선은 다음 방정식으로 표시됩니다. 여기서 a,b,c,d 는 계수입니다.
예를 들어 a=1,b=,c=-2,d=4 인 경우 결과 타원 곡선은 다음과 같습니다.
이 타원 곡선 e 의 이미지는 그림 X-1 과 같이 타원형이 아닙니다.
곡선의 두 점 a, b 는 선을 그리고 선과 타원 곡선의 교차점을 찾습니다. x 축 대칭 위치에 대한 교차점은 덧셈으로 정의된 A+B 로 정의됩니다. 다음 그림과 같이 A+B = C
위의 방법은 A+A, 즉 두 점이 일치하는 상황을 해석할 수 없습니다. 따라서 이 경우 a 점에서 타원 곡선의 접선과 타원 곡선의 교차점, x 축 대칭 위치에 대한 교차 점은 A+A, 즉 2A, 즉 2 배 연산으로 정의됩니다.
x 축 대칭 위치에 대한 a 점을 -A, 즉 타원 커브의 양수 및 음수 반전으로 정의합니다. 다음 그림과 같이
a 를 -A 에 추가하고 a 와 -A 를 통과하는 선이 y 축에 평행한 경우 선이 타원 곡선과 무한히 교차하는 것으로 간주됩니다. < P > 요약하면 A+B, 2A 연산이 정의되므로 타원 곡선의 한 점인 G 가 2G, 3G (G+2G), 4G ... 즉, GP 가 주어질 때 X 를 알고 xG 점을 찾는 것은 어렵지 않습니다. 반대로, 알려진 xG 점, x 를 찾는 것은 매우 어렵습니다. 이것은 타원 곡선 암호화 알고리즘의 수학적 원리입니다.
타원 곡선은 부드러운 곡선을 형성하기 위해 x,y 값이 모두 실수, 즉 실수 필드의 타원 곡선이어야 합니다. 그러나 타원 곡선 암호화 알고리즘은 실수 필드가 아니라 유한 필드를 사용합니다. 수 이론에 따르면 유한 필드 GF(p) 는 , 1, 2 ... P-1 * * * P 개 요소로 구성된 정수 세트에 정의된 더하기 및 빼기 곱셈 및 나눗셈 연산을 지정된 소수 P 를 가리킵니다.
타원 곡선이 y 라고 가정합니다. = x? +x+1, 유한 필드 GF(23) 에 있을 때 쓰기: y? X? +x+1 (mod 23)
이제 타원 곡선은 더 이상 부드러운 곡선이 아니라 다음 그림과 같이 불연속적인 점입니다. 점 (1,7) 을 예로 들어 7? ≤ 1? +1+1 Ͱ 3 (mod 23).
(,1) (,22) (1,7) (1,16) (3,1) (3,13) (4,) 과 같은 점도 있습니다
또한 P(x,y) 가 타원 곡선 위의 점인 경우 -P 는 (x,-y) 타원 곡선 위의 점이기도 합니다. 점 P(,1), -P=(,-1)=(,22) 도 타원 곡선 위의 점입니다.
관련 공식은 다음과 같습니다. 유한 필드 GF(p) 의 타원 곡선 y? = x? +ax+b, P(Xp, Yp), Q(Xq, Yq) 및 P≠-Q 인 경우 R(Xr,Yr) = P+Q 는 다음 규칙에 따라 결정됩니다. < p -XP-xq) mod p yr = (λ (XP-xr)-yp) mod p 여기서 λ = (Yq-Yp)/(Xq-Xp) mod p (p ≠ 인 경우) +a)/2Yp mod p (p = q 인 경우)
따라서 유한 필드 GF(23) 의 타원 곡선 y? X? +x+1 (mod 23), (,1) 을 gt 점으로 가정하고 2G, 3G, 4G...xG 등을 다음과 같이 계산합니다.
2g 계산: λ = (3x? +1)/2x1mod23 = (1/2) mod23 = 12xr = (12? --) mod 23 = 6 yr = (12 (-6)-1) mod 23 = 19 는 2G 를 점 (6,19) 으로
계산 3g: 3g = g = --6) mod 23 = 3 yr = (3 (-3)-1) mod 23 = 13 은 점 (3, 13)
에 대한 타원 곡선 기반 암호화 메커니즘을 작성하며 비슷한 RSA 품질을 찾아야 합니다 타원 곡선에서 알려진 G 와 xG 가 X 를 찾는 것은 매우 어렵습니다. 이것은 타원 곡선상의 이산대수 문제입니다. 여기서 x 는 개인 키이고 xG 는 공개 키입니다. < P > 타원 곡선 암호화 알고리즘은 다음과 같이 작동합니다. < P > 개인 키 설정, 공개 키는 각각 K, K, 즉 K = kG 입니다. 여기서 G 는 GP 입니다.
공개 키 암호화: 난수 r 을 선택하면 메시지 m 이 점 쌍인 암호문 c 를 생성합니다. C = {rG, M+rK} 여기서 k 는 공개 키
개인 키 암호 해독: m+rk-k (;
타원 곡선 서명 알고리즘, 즉 ECDSA. 개인 키와 공개 키를 각각 k, k, 즉 K = kG 로 설정합니다. 여기서 g 는 gp 입니다.
개인 키 서명: 1, 난수 선택 r, 계산 지점 rG(x, y). 2, 난수 R, 메시지 M 의 해시 H, 개인 키 K 에 따라 s = (h+kx)/r 을 계산합니다. 3, 메시지 M 및 서명 {rG, s} 을 수신자에게 보냅니다.
공개 키 인증 서명: 1, 수신자가 메시지 m 수신 및 서명 {rG=(x,y), s}. 2, 메시지에 따라 해시 h 를 찾으십시오. 3, 발신자 공개 키 K 계산 사용: hG/s+xK/s 및 rG 와 비교 (예: 같음, 검증 성공).
원리는 다음과 같습니다. Hg/s+xk/s = Hg/s+x (kg)/s = (h+xk) g/s = r (h+xk) g 。 DSA 서명의 첫 번째 단계는 서명된 메시지에 대한 메시지 요약을 생성하는 것입니다. 서명 알고리즘마다 다른 메시지 다이제스트 알고리즘을 사용합니다. 반면 ECDSA256 은 SHA256 을 사용하여 256 비트 요약을 생성합니다. < P > 다이제스트 생성이 끝나면 서명 알고리즘을 적용하여 다이제스트에 서명합니다. < P > 난수 생성 k
난수 K 를 사용하여 두 개의 큰 수의 R 과 S 를 계산합니다. R 과 S 를 합치면 메시지 다이제스트에 대한 서명이 된다. < P > 여기서 주목해야 할 것은 난수 K 의 존재로 인해 같은 메시지에 대해 같은 알고리즘을 사용하여 생성된 서명이 다르다는 점이다. 함수의 관점에서 볼 때 서명 함수는 동일한 입력에 대해 다른 출력을 생성합니다. 함수 내에서 임의 값을 서명에 혼합하는 프로세스입니다. < P > 검증 프로세스와 관련하여 알고리즘 세부 사항은 여기서 다루지 않습니다. 거시적으로 메시지 수신자는 서명에서 R 과 S 를 분리한 다음 공개 키 정보와 S 를 사용하여 R 을 계산합니다. 계산된 r 과 수신된 r 값이 같으면 검증이 성공한 것입니다. 그렇지 않으면 인증에 실패한 것입니다.