ECHC 암호 스키마

타원곡선기반 동형암호 시스템(Elliptic Curve Homomorphic Cryptosystem, ECHC)^[1]은 포체인스 R&D센터에서 진행되었던 연구 주제인 ‘타원곡선기반의 동형구조 연구를 통한 암호 스키마 개발’ 을 통해 개발된 국내 기술로 개발된 암호 원천기술로서, 타원곡선이 가지는 동형구조 혹은 대응 관계를 통하여 기존의 동형암호를 대체할 차세대 암호^[2]이다.

역사 편집

포체인스 대표(이정훈)는 ‘페르마 마지막 정리’ 관련 연구를 진행하였고,‘페르마 마지막 정리페르마 마지막 정리’의 핵심 주제인 타원곡선의 수학적 구조에 대한 연구를 진행했다. 타원곡선의 암호체계를 새로운 수학적 구조에 옮겨 그 관계를 이용한 새로운 암호 스키마를 구현하는 것에 관심을 가지고 암호에 관련 연구를 시작하게 되었다고 한다. 기존의 암호 연구의 한계점인 알고리즘 변형을 통한 개선이 적용되는 동형암호의 연구가 고질적으로 문제가 있다고 판단했고, 기존의 동형암호가 실질적인 데이터 분석을 진행하기에 부족한 속도 측면의 한계점을 가진다는 점을 토대로 이를 개선하기 위하여 알고리즘 측면의 연구가 아닌 동형암호에 적합한 대수적 공간에 대한 연구와 그를 적용한 차세대 암호 스키마의 개발을 목표로 관련 연구를 진행했다.

포체인스 암호 스키마 종류 편집

모듈라 형식 암호 (Modular Form Cryptosystem, MFC)

모듈라 형식(Mordular Form)와 타원곡선의 대응구조를 활용하여 연구, 개발된 암호 스키마이다.
페르마 마지막 정리의 증명에 대한 핵심 연구였던 타니야마-시무라 추측(Taniyama–Shimura conjecture)를 기반으로 모듈라 형식 암호에 대한 연구를 진행하였다.

타원곡선 동형암호 (Elliptic Curve Homomorphic Cryptosystem, ECHC)

타원곡선과 모델 정리(Mordell’s Theorem)를 기반으로 연구, 개발된 암호 스키마이다.
타원곡선과 그 동형인 수학적 구조를 통하여 타원곡선의 경량성과 동형구조를 가지는 새로운 유사 동형암호를 개발하였다.

유사 동형암호 (Pseudo Homomorphic cryptosystem, PHC)

MFC와 ECHC를 융합하여 만든 완성형 암호 스키마이다.
Pseudo라는 말과 같이 기존 동형암호와는 다른 암호 시스템이고 강력한 보안력을 특징으로 가지고 있다.

ECHC 암호스키마 장점 편집

Elliptic Curve 위에 동형암호 구조를 적용한 암호 스키마^[3]
ECC의 경량성을 동형암호 구조에 접목하여 기존 동형암호의 속도 측면을 개선
기존 암호의 장점을 융합한 새로운 암호를 통한 보안 이슈 해결책으로서 강한 보안성 및 빠른 처리속도 그리고 인공지능 기법을 통한 공격 보호가 가능한 암호^[4]

관련 수학 배경지식 편집

(1) 타원곡선 (Elliptic Curve)의 정의

$\Bbbk$ 를 임의의 체(field)라고 하고 타원곡선 $\mathbb {E}$ 은 다음 방정식을 만족하는 점들의 집합이라고 하자.

${\begin{alignedat}{2}y^{2}&=x^{3}+Ax+B\\\end{alignedat}}$ 여기서 $\ A,B\in \Bbbk$ 임이 성립한다. 이 때 이 방정식을 타원곡선에 대한 바이어슈트라스 방정식(Weierstrass equation)라고 한다. 또한, 타원곡선은 ``무한점(point at infinity)''을 포함하고 있고, $\infty$ 로 표기한다. 이 점은 쉽게 $y$ -좌표의 맨 위에 있을 때임을 알 수 있다. 하지만 $y$ -축의 맨 아래도 맨 위로 간주할 경우를 말하는 것이다. ${\overline {\Bbbk }}$ 는 $\Bbbk$ 의 대수적 폐포(algebraic closure)라 하며 $\Bbbk$ 위에서의 타원곡선은 $\mathbb {E} ({\overline {\Bbbk }})$ 로 표기하고 다음과 같이 정의한다.

$\mathbb {E} ({\overline {K}})=\left\{\infty \right\}\cup \left\{(x,y)\in {\overline {\Bbbk }}\times {\overline {\Bbbk }}\mid y^{2}=x^{3}+Ax+B\right\}$

$p$ 를 소수, $a,b$ 를 법 $p$ 에 대해서 0이 아닌 정수라고 하자. 이제, 다음을 만족하는 정수 $k$ 가 존재함을 고려하자.

$a^{k}\equiv b{\pmod {p}}$ 위 식에서 $k$ 를 찾는 것을 이산 로그 문제(discrete logarithm problem)라고 한다. $k+(p-1)$ 또한 해이므로, 답 $k$ 는 법 $p-1$ 에서 정의되고 있음을, 혹은 만약 $a^{d}\equiv 1{\pmod {p}}$ 를 만족한다면 $p-1$ 의 약수 $d$ 임을 고려하자. 이러한 문제를 타원곡선에 대한 이산 로그 문제로 바라볼 수 있다. 타원곡선 위의 점 $A,B$ 에 대하여 적당한 정수 $k$ 가 존재해서 $B=kA(=A+A+\cdots +A)$ 이 성립한다고 하자. 우리는 $k$ 를 찾기 원하고 일반적으로 이 타원곡선에 대한 이산 로그 문제의 좋은 공격은 존재하지 않는다. 소수 $p$ 에 대하여 $\mathbb {E}$ 를 법 $p$ 에 대한 타원곡선이라고 하고, $n$ 을 $nA=\infty$ 를 만족하는 최소의 양의 정수라고 하자. 만약 $n$ 이 작은 소인수를 가진다고 하면 그것은 $n$ 을 나누는 소수의 거듭제곱을 법으로 하는 이산 로그 $k$ 를 계산하는 것이 가능하다. 그러면 중국인 나머지정리(Chinese remainder theorem)를 적용하여 $k$ 를 찾을 수 있다.

(2) 유리수체 $\mathbb {Q}$ 위에서 타원곡선의 군(Group) 구조

유리수체 $\mathbb {Q}$ 위에서 정의된 타원곡선 $\mathbb {E}$ 을 고려하자. 이 타원곡선 $\mathbb {E}$ 위의 두 점 $P_{1}=(x_{1},y_{1})$ , $P_{2}=(x_{2},y_{2})$ 를 고려하고 타원곡선 $\mathbb {E}$ 의 방정식은 $y^{2}=x^{3}+Ax+B$ 로 주어졌다고 하자. 이 때, $P_{1},P_{2}\neq \infty$ 이라 하자. 우리는 다음 각 상황에 대한 $\mathbb {E}$ 위의 점 $P_{3}$ 를 구할 수 있다. 첫번째 경우는 $P_{1}$ 와 $P_{2}$ 를 지나는 직선을 그린다. (만약 $P_{1}=P_{2}$ 인 경우는 선 $L$ 은 점 $P_{1}$ 에서의 접선(tangent line)이다.) 선 $L$ 과 타원곡선 $\mathbb {E}$ 의 교점 $P_{3}^{'}$ 를 얻을 수 있다. $P_{3}^{'}$ 를 $x$ -축에 반사시켜서 얻은 점을 $P_{3}=(x_{3},y_{3})$ 라 하자. 마지막으로 우리는 군 법칙을 다음과 같이 정의할 수 있다.

$P_{1}+P_{2}=P_{3}$

1. 만약 $x_{1}\neq x_{2}$ 이면 $m={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}$ 일 때 $x_{3}=m^{2}-x_{1}-x_{2},\;y_{3}=m(x_{1}-x_{3})-y_{1}$ 이다.
2. 만약 $x_{1}=x_{2}$ 이지만 $y_{1}\neq y_{2}$ 이면 $P_{1}+P_{2}=\infty$ 이다.
3. 만약 $P_{1}=P_{2}$ 이고 $y_{1}\neq 0$ 이면 $m={\frac {3x_{1}^{2}+A}{2y_{1}}}$ 일 때 $x_{3}=m^{2}-2x_{1},y_{3}=m(x_{1}-x_{3})-y_{1}$ 이다.
4. 만약 $P_{1}=P_{2}$ 이고 $y_{1}=0$ 이면 $P_{1}+P_{2}=\infty$ 이다.
  더욱이 $\infty$ 와 $P$ 를 지나는 선은 $x$ -축과 수직이다. 이 선은 타원곡선 $\mathbb {E}$ 의 $P=(x,y)$ 와 $(x,-y)$ 를 지난다. 점 $P$ 를 $x$ -축에 반사시키면 점 $(x,-y)$ 를 얻는다. 그러므로 $P+\infty =P$ 임을 알 수 있다. 또한, $(x,y)$ 와 $(x,-y)$ 를 지나는 선은 수직이므로 타원곡선 $\mathbb {E}$ 와의 교점은 $\infty$ 이다. 결과적으로 $(x,y)+(x,-y)=\infty$ 임을 얻는다. 이 때, $\infty$ 는 $\mathbb {E}$ 에서 항등원의 역할을 하기 때문에 $-(x,y)=(x,-y)$ 라고 정의하여야 하고, 이 사실은 $(x,-y)$ 는 $(x,y)$ 의 역원임을 의미한다.

(3) 유한체 $\mathbb {F} _{p}$ 위의 타원곡선의 군(Group) 구조

$\mathbb {F} _{p}$ 위에서 정의된 타원곡선을 고려하자. 여기서 $p$ 는 홀수 소수이고 $\mathbb {F} _{p}$ 는 유한 소체이다. 그리고 $a,b\in \mathbb {F} _{p}$ 는 $4A^{3}+27B^{2}\not \equiv 0{\pmod {p}}$ 를 만족한다고 하면 매개변수 $A,B\in \mathbb {F} _{p}$ 를 가지는 유한체 $\mathbb {F} _{p}$ 위에서 정의된 타원곡선 $\mathbb {E} (\mathbb {F} _{p})$ 은 다음 방정식의 해 혹은 점 $P=(x,y)$ 으로 구성된다.

$y^{2}\equiv x^{3}+Ax+B{\pmod {p}}$ 이외의 점 ${\mathcal {O}}$ 은 무한점을 의미한다. 방정식 $y^{2}\equiv x^{3}+Ax+B{\pmod {p}}$ 은 $\mathbb {E} (\mathbb {F} _{p})$ 을 정의하는 방정식으로 불린다. 주어진 점 $P=(x_{p},y_{p})$ 에 대해서, $x_{p}$ 는 $P$ 의 $x$ -좌표, 그리고 $y_{p}$ 는 $P$ 의 $y$ -좌표라고 불린다. $\mathbb {E} (\mathbb {F} _{p})$ 에서 원소의 개수는 $\#\mathbb {E} (\mathbb {F} _{p})$ 라고 표현한다. `하세 정리'(Hasse Theorem)는 다음과 같이 $\#\mathbb {E} (\mathbb {F} _{p})$ 를 계산하는 방법을 소개한다. 만약 $\mathbb {E} (\mathbb {F} _{p})$ 는 유한체 $\mathbb {F} _{p}$ 에서의 타원곡선이면,

$p+1-2{\sqrt {p}}\leq \#\mathbb {E} (\mathbb {F} _{p})\leq p+1+2{\sqrt {p}}$

$\mathbb {E} (\mathbb {F} _{p})$ 에서의 군 법칙은 다음과 같다.

1. 무한점끼리 합하는 규칙: ${\mathcal {O}}+{\mathcal {O}}={\mathcal {O}}$ 2. 무한점과 어떤 다른 점을 합하는 규칙: 모든 $\;(x,y)\in \mathbb {E} (\mathbb {F} _{p})$ 에 대해서, $\;(x,y)+{\mathcal {O}}={\mathcal {O}}+(x,y)=(x,y)$ 3. 점들이 각각 구별되거나, $y$ -좌표가 0일 때, $x$ -좌표가 같은 두 점을 합하는 규칙: 모든 $\;(x,y)\in \mathbb {E} (\mathbb {F} _{p})$ 에 대해서, $\;(x,y)+(x,-y)={\mathcal {O}}$ 4. $x$ -좌표가 다른 두 점을 합하는 규칙 : $(x_{1},y_{1})\in \mathbb {E} (\mathbb {F} _{p})$ 과 $(x_{2},y_{2})\in \mathbb {E} (\mathbb {F} _{p})$ 를 $x_{1}\neq x_{2}$ 를 만족하는 점이라고 하자. 그러면

$(x_{1},y_{1})+(x_{2},y_{2})=(x_{3},y_{3})$ 이고, 다음과 같다: $x_{3}\equiv \lambda ^{2}-x_{1}-x_{2},\;y_{3}\equiv \lambda (x_{1}-x_{3})-y_{1},$ 그리고 $\lambda \equiv {\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}{\pmod {p}}$ 5. 동일한 점끼리 합하는 규칙(double a point): $(x_{1},y_{1})\in \mathbb {E} (\mathbb {F} _{p})$ 을 $y_{1}\neq 0$ 을 만족하는 점이라고 하자. $x_{3}\equiv \lambda ^{2}-2x_{2},\;y_{3}\equiv \lambda (x_{1}-x_{3})-y_{1},$ 그리고 $\lambda \equiv {\frac {3x_{1}^{2}+A}{2y_{1}}}{\pmod {p}}$

$\mathbb {E} (\mathbb {F} _{p})$ 위에서의 점들의 집합은 더하기 연산을 가지는 군 형태이며 그 군은 가환군(abelian group)이다.(모든 점 $P_{1},P_{2}\in \mathbb {E} (\mathbb {F} _{p})$ 에 대해서, $P_{1}+P_{2}=P_{2}+P_{1}$ 을 만족하는 것을 의미한다.) 주어진 정수 $k$ 와 점 $P\in \mathbb {E} (\mathbb {F} _{p})$ 에 대해서, 스칼라 곱은 점 $P$ 를 $k$ 번 더하는 과정과 같다. 이 스칼라 곱의 결과는 $kP$ 로 표현된다.