KMS11 : C language ECC 키 연산 결과 보고

KMS11 : ECC algorithm

이 글이 공개되는 시점은 5월 초 쯤이겠지만, 이 글을 작성하는, 지금 2월 16일쯤에, ECC프로젝트를 적절히 테스트한 후 마무리 하기로 하였다.

 개인적으로 몽고메리를 구현해보고자 하는 욕심이 있었지만, 그럴려면 Divide와 powMod연산을 다 갈아엎어야 해서... 이제 새로 시작되는 고등학교 생활을 위해 접어두기로 했다. 물론 시간이 많이 나게 된다면, 그때 구현할 의향은 있다,

 작년 7월쯤에 RSA끝나고 시작해서 2월까지 왔으니 8개월쯤 한 셈이다;; RSA구현할 때 보다 거의 1.6배가 걸렸다.
(물론 마지막 한달간은 간단한 최적화만 했지만)

 

개인이 혼자 하는 프로젝트라서 특히 초반 자료조사가 힘들었다.

특히 타원곡선 자료들 긁어오는게 너무 힘들었다.

많은 것을 공개하지는 못하지만, 표준 타원곡선 값 pdf를 올리도록 하겠다. 

ECC 타원 곡선 규격.pdf

0.29MB

* 여담으로 말하자면, 이 프로젝트를 하면서 인터넷은 연구 자료 조사에 쓰는 것이 아니란걸 느꼈다. 인터넷은 딱 고등학교 수준의 정보만 방대하게 가지고 있다. 그 정도 수준을 넘어가면 인터넷은 더이상 정보의 바다가 아니다.

 

참고로 아래 그림은 ECC개발중 현타왔을때 캡쳐한 사진이다. 

지금은 소스코드를 많이 줄여서 1800줄 정도 된다.

내가 만든 프로젝트중 가장 긴 길이이다.

---

made by KMS_STUDIO

​

KMS11_ECC

made by 2021 KMS studio

Copyright 2021 KMS studio all rights reserved.

Thank to 

Kyung Taek Park

Si Hyun Kim

---

테스트 구조

Private key : 단순히 rand()함수를 이용해서 256bit의 랜덤한 수를 입력받음. 테스트의 수월성을 위해서, 랜덤시드는 사용자가 지정할 수 있게 만들어놓았슴.

Public key : Private key와 타원곡선등의 정보를 입력받아 키를 계산함.

이때, 이 과정을 빠르게 하기 위해 프로그램을 시작할때22Kbyte정도의 메모리 공간을 할당받음.

Secret Key : 자신의 Private키와 상대방의 Public 키, 타원곡선들의 정보를 이용하여 Secret키를 계산함.

 

테스트 과정

1. 한 프로그램 내에서 각각 사용자 1, 사용자 2의 입장에서 Private key 1, 2를 만든 뒤에, Public key 1, 2또한 계산한 후, 
Pri key 1과 pub key 2를 이용해 계산한 Secret key 1, Pri key 2와 pub key 1을 이용해 계산한 Secret key 2이 둘을 비교해 두 키가 하나의 비트라도 다르면 바로 에러처리로 만듬. (모든 키는 256bit임)

 최신 버전 기준으로 100,000개의 상황에서 테스트했을때, 에러가 나지 않았슴.

 

2. 약 5 ~ 6bit의 타원곡선을 직접 만든 뒤에, 직접 Private키를 입력하여 계산기로 계산한 것과 같은 Public, Secret키가 나오는지 확인함 단, 이 테스트는 최적화 이우 구조적으로 테스트가 어려워져서 작년 12월때 테스트를 한 이후 더 하지는 않음.

 2020년 12월 테스트를 기준으로, 5개의 상황에서 모두 정상작동

---

테스트 코드 구조

함수이름 = 설명 급으로 함수이름이 잘 지정되어있다 생각하기 떄문에, 소스 설명을 따로하지 않겠다. 애초에 헤더파일 공개를 안할꺼라 분석하셔도 쓸데는 거의 없다. (참고로 테스트 소스가 말 그대로 테스트용이라서 좀 허접하다. 이해해주기를 바란다.)

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#include "KMS11.h"

int main(void) {
	CURVE cur;
	POINT PuA, PuB;
	POINT SeA, SeB;
	KMS A, B;
	clock_t st;
	double tval;
	double mean[3] = { 0, };
	int start_seed, lng;

	double maxv[3] = { 0, 0, 0 };
	double minv[3] = { 200, 200, 200 };

	// ************************* base setup ************************* //
	HEADER_SETUP(); //setup base value, array in header
	VLABL_SETUP(); //allocation memory to pointer in header
	CURVE_SETUP(&cur); //allocation memory to pointer in curve structure

	// ************************* pakg setup ************************* //
	KEY_PACKAGE_SETUP(&SeA, &PuA, &A); //allocation memory to pointer in key package
	KEY_PACKAGE_SETUP(&SeB, &PuB, &B); //allocation memory to pointer in key package

	printf("main seed : ");
	scanf("%d", &start_seed);
	srand(start_seed);

	printf("key length : ");
	scanf("%d", &lng);

	// ************************* prepareing ************************* //
	kECC_setSecp256r1(&cur); //set curve to secp256r1
	// ************************* strt setup ************************* //
	kECC_registArr(&cur, lng); //make structure (structure's form is curve's form)
	for (int now_seed = start_seed, cnt = 1; ; now_seed++, cnt++) {
		srand(now_seed);
		printf("{ seed %d }\n", now_seed);

		st = clock();
		TEMP_RAND(&A, &cur.n, lng); //temporary (lng bit) random function
		TEMP_RAND(&B, &cur.n, lng); //temporary (lng bit) random function
		tval = (double)(clock() - st) / 2;
		mean[0] += tval;
		printf(" : random number claculated\t   %4.1fms\t[%7.3f ms]\n", tval, mean[0] / cnt);

		st = clock();
		kECC_PublicKey(&PuA, &A, &cur); //make userA's public key
		kECC_PublicKey(&PuB, &B, &cur); //make userB's spublic key
		tval = (double)(clock() - st) / 2;
		mean[1] += tval;
		maxv[1] = (maxv[1] > tval) ? maxv[1] : tval;
		minv[1] = (minv[1] < tval) ? minv[1] : tval;
		printf(" : public key claculated\t%s %4.1fms\t[%7.3f ms] %f %f \n", (tval <= (mean[1] / cnt)) ? "▼" : "▲", tval, mean[1] / cnt, maxv[1], minv[1]);

		st = clock();
		kECC_SecretKey(&SeA, &PuB, &A, &cur); //make userA's secret key
		kECC_SecretKey(&SeB, &PuA, &B, &cur); //make userB's secret key
		tval = (double)(clock() - st) / 2;
		mean[2] += tval;
		maxv[2] = (maxv[2] > tval) ? maxv[2] : tval;
		minv[2] = (minv[2] < tval) ? minv[2] : tval;
		printf(" : secret key claculated\t%s %4.1fms\t[%7.3f ms] %f %f \n", (tval <= (mean[2] / cnt)) ? "▼" : "▲", tval, mean[2] / cnt, maxv[2], minv[2]);

		if ((kECC_cmp(&SeA.x, &SeB.x)) || (kECC_cmp(&SeA.y, &SeB.y))) {
			system("cls");
			printf("[ Here is some error to calculate ECC key pair ]\n");
			printf("srand seed = %d\n", now_seed);

			printf("\n== Pri b state ==\n");
			kECC_print(&A);
			kECC_print(&B);

			printf("\n== Pub x state ==\n");
			kECC_print(&PuA.x);
			kECC_print(&PuB.x);
			printf("\n== Pub y state ==\n");
			kECC_print(&PuA.y);
			kECC_print(&PuB.y);

			printf("\n== Sec x state ==\n");
			kECC_print(&SeA.x);
			kECC_print(&SeB.x);
			printf("\n== Sec y state ==\n");
			kECC_print(&SeA.y);
			kECC_print(&SeB.y);
			break; 
		}
		else {
			printf(" : normal state\n\n");
		}
	}

	// ************************* unlod base ************************* //
	VLABL_FREE();
	CURVE_FREE(&cur);
	// ************************* unlod pakg ************************* //
	KEY_PACKAGE_FREE(&SeA, &PuA, &A);
	KEY_PACKAGE_FREE(&SeB, &PuB, &B);
	// ************************* unlod strt ************************* //
	ARRAY_FREE();

	return 0;
}

---

테스트 사양

테스트 사양은 다음과 같습니다. 사용감 있는 10년 전의 최고급 노트북입니다.

---

ECC 256(secp256r1) 테스트 결과

약 45,000번 산출 후 계산하였음. 타원 곡선 값은 secp256r1의 규격을 따름. 랜덤 한 256비트 수를 Private키로 생성함

visual studio(...)에서 Release버전으로 실행하였음 

(단위는 milliseconds)

{Public key}

최저값	4
최고값	21
평균값	5.277

{Secret key}

최고값	48
최저값	16
평균값	18.282

 

참고로 네이버 블로그에는 2차 중간 보고를 올렸었는데, 그것보다 더 개선된 시간이다.

---

추가 정보

아는 사람을 알아차렸겠지만 이 테스트 노트북은 매우 구린 노트북이다. 심지어 새것도 아닌 지금까지 계속 사용한

그래서 아는 분에게 테스트를 해달라 하였으나, 아직까지 테스트를 해주고 있지 않고 있다. ...

어느정도 가늠할 수 있게 말씀을 들이자면, 그분 은 1 ~ 2년전 노트북으로 테스트를 해주시는데

이 노트북에서 프로그램이 디버그로 60ms가 걸릴때, 그분 노트북에서는 23ms가 걸렸다고 한다.

---

Thanks for watching

오류가 난 테스트 케이스나 문의는 tomskang@naver.com으로 보내주시면 감사하겠습니다.

Copyright 2021 KMS studio all rights reserved

---

relation content

ECC 중간보고

RSA 최종보고