ECC 디피-헬먼

ECC 디피-헬먼은 DH의 ECC 버전이다.

공개된 정보는 곡선과 곡선 상의 한 점으로 구성된다.

y^2 = x^3 + 11x + b (mod 167)

다음 점 (x,y)를 선정하고 b를 이 점이 곡선 상에 위치하도록 결정

(x,y) = 2,7   -> b = 19

최종적으로 공개된 정보
y^2 = x^3 + 11x + 19 (mod 167), 점 (2,7)

A와 B는 각각 자신들의 비밀 승수를 선정한다.
A의 비밀 승수 a = 15
B의 비밀 승수 b = 22

그러면 A는 다음과 같이 계산할 수 있다.
a(2,7) = 15(2,7) = (102,88) 

15(2,7)은 (2,7) + (2,7) + ... + (2,7) 총 15회는 더하는 것과 같다.
타원곡선 암호에서 두 점을 더하는 방법은 전 글에서 해보았다. 
http://ezbeat.tistory.com/335

하지만 (102,88)을 보면 타원곡선 내 없는 점 같이 보인다.
y^2 = 1062349 mod 167 = 62 mod 167
하지만 62에서 167을 계속 더해가면 88의 제곱인 7744 값이 나오게 된다.
즉, 62 mod 167 = 7744 mod 167 ( 7744 = 88^2 )

위에서 본 15회의 덧셈을 손으로 한다는 것은 시간상 문제도 있으므로 프로그램을 짜서 돌리는게 훨씬 현명하다.
ECC에서 두 점 합을 구하는 프로그램을 만들어 보았다. 단순히 두 점의 합을 구하는 것이기 때문에
15회의 덧셈을 위해선 입력을 몇 번 더 해주어야한다. 코드이다.

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <Windows.h> enum { GREY = 0x7, WHITE = 0xF, GREEN = 0xA, CYAN = 0xB, RED = 0xc, YELLOW = 0xE }; typedef struct point{ int x; int y; }point; int mod(int num,int p, int flag); int GetM(point p1, point p2,int a,int p); void Set_Color_Console(WORD color); int main(void) { int a,b; point p1,p2,p3; int m; int p; int y_2; int y_2_mod; int count = 0; printf("타원곡선 생성 (E : y^2 = x^3 + ax + b) \n"); printf("a : "); scanf("%d",&a); printf("b : "); scanf("%d",&b); printf("\n"); printf("mod p : "); scanf("%d",&p); printf("\n"); while(1) { memset(&p1,0,sizeof(point)); memset(&p2,0,sizeof(point)); memset(&p3,0,sizeof(point)); Set_Color_Console(WHITE); printf("★더할 두 점을 입력하세요 \n"); Set_Color_Console(GREY); printf("p1 : "); scanf("%d %d",&(p1.x),&(p1.y)); printf("p2 : "); scanf("%d %d",&(p2.x),&(p2.y)); if(p2.x - p1.x < 0) { Set_Color_Console(RED); printf("두 점을 바꿔서 다시 입력해주세요. ( x2-x1 < 0 ) \n"); Set_Color_Console(GREY); fflush(stdin); continue; } printf("\n"); Set_Color_Console(GREEN); printf("타원곡선 : E : y^2 = x^3 + %dx + %d (mod %d) \n",a,b,p); Set_Color_Console(GREY); printf("p1 : (%d,%d) \np2 : (%d,%d) \n",p1.x,p1.y,p2.x,p2.y); m = GetM(p1,p2,a,p); printf("m : %d \n\n",m); p3.x = m * m - p1.x - p2.x; p3.x = mod(p3.x,p,0); p3.y = m * (p1.x - p3.x) - p1.y; p3.y = mod(p3.y,p,0); printf("P1 + P2 = P3 : "); Set_Color_Console(CYAN); printf("(%d,%d) \n\n",p3.x,p3.y); Set_Color_Console(GREY); y_2 = (p3.x * p3.x * p3.x) + (a * p3.x) + b; printf("y^2 = %d \n",y_2); y_2_mod = mod(y_2,p,0); printf("y^2 mod %d = %d mod %d \n\n",p,y_2_mod,p); } //타원곡선 위의 점 중에 정수가 되는 p3.y값 찾음 ( 보류 ) /* while(1) { temp = sqrt((double)y_2_mod); if((temp - (int)temp) != 0) { y_2_mod += p; } else { p3.y = (int)temp; break; } } printf("타원곡선 위의 정수인 점 \n"); printf("P3 : (%d,%d) \n",p3.x,p3.y); */ return 0; } //(음수)^-1 처리는 안되어 있음 int mod(int num,int p, int flag) { //+,- mod 연산 if(flag == 0) { int count = 0; //- mod if(num < 0) { num *= -1; while(1) { if(((num + count++) % p) == 0) { num = --count; count = 1; break; } } } //+ mod else num %= p; return num; } //revers_mod 연산 ^-1 되어 있는 것 else if(flag == 1) { int count = 1; //^-1 mod do { if((num*count % p) == 1) { num = count; break; } } while (count++); return num; } return -1; } int GetM(point p1, point p2,int a,int p) { int count = 0; if(p1.x == p2.x && p1.y == p2.y) { //입력 시 tmp2는 음수가 안되도록 int tmp1 = 3 * (p1.x * p1.x) + a; int tmp2 = 2 * p1.y; tmp1 = mod(tmp1,p,0); tmp2 = mod(tmp2,p,1); return ((tmp1 * tmp2) % p); } else { //입력 시 tmp2는 음수가 안되도록. 즉, 두번째 x값이 첫번째 x값 보다 크게끔 입력 int tmp1 = p2.y - p1.y; int tmp2 = p2.x - p1.x; tmp1 = mod(tmp1,p,0); tmp2 = mod(tmp2,p,1); return ((tmp1 * tmp2) % p); } return -1; } void Set_Color_Console(WORD color) { HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hConsole,color); }

 

A는 이 결과를 B에게 보낸다.
B도 다음과 같이 계산하고 그 결과를 A에게 보낸다.
b(2,7) = 22(2,7) = (9,43)

A는 다음과 같이 자신의 비밀 승수 a를 B에게서 받은 값에 곱한다.
a(9,43) = 15(9,43) = (131,140)

B도 유사한 방식으로 다음과 같이 계산한다.
b(102,88) = 22(102,88) = (131,140)

이렇게 하여 A와 B는 대칭키로 사용하기에 적절한 비밀정보를 공유하게 된다.
이것이 가능한 것은 AB(2,7) = BA(2,7) 이기 때문이다. ( 간략한 그림 )

이러한 DH ECC도 중간자 공격에 취약하기는 마찬가지이다.