최소의 안전성 손실을 갖는 MNT 타원곡선 생성 최소의 안전성 손실을 갖는 MNT 타원곡선 생성 대한수학회 봄 연구발표회 Copyright ⓒ 2009 Samsung SDS Co., Ltd. All rights reserved | Confidential 삼성 SDS 통합보안컨설팅그룹 선동규 책임컨설턴트 /Ph.D. 삼성 SDS 통합보안컨설팅그룹 선동규 책임컨설턴트 /Ph.D.

2009 대한수학회 봄 연구발표회 Elliptic Curves Suitable for Pairing Based Cryptography For pairing based cryptography we need elliptic curves defined over finite fields F q whose group order is divisible by some prime r with r | q k -1 where k is relatively small k=2,3,4,6 q=p m ( 단, p=2 또는 3) Weil Descent 공격 (m 은 소수 ) k 는 임의의 양의 정수, 일반적으로 매우 큼 (k 는 6~20 정도가 적합함 ) q=p 안전성 측면에서 pairing 에 적합한 ordinary 타원곡선은 아직 검증이 안되었음 Pairing Based Cryptography K (Embedding degree) Supersingular Ordinary Special Elliptic Curves

2009 대한수학회 봄 연구발표회 Hard Problem & Pairing-friendly Elliptic Curves For prime p, Elliptic Curve over F p E(F p ): y 2 =x 3 +Ax+B ( 단, A, B ∈ F p ) #(E(F p ))=n=hr(order), r l p k -1 단, h 는 cofactor, r 은 소수 P(x g, y g ): generator of E[r] 효율성 안전성 ρ:= (logp)/(logr) 이 1 에 가까워야 함 k 는 상대적으로 작음 ECDLP. ECDHP r 은 160 비트, p k 은 1024 비트 이상을 만족해야 함 K 는 상대적으로 커야함 Bob Alice Eve

2009 대한수학회 봄 연구발표회 History of Pairing-friendly Elliptic Curves Scott, Barreto 방법 원리 Hasse 방정식 Pell 방정식 CM 방법 k=3,4,6 소수 위수 (MNT: Miyaji, Nakabayashi, Takano, 2001) → 타원곡선의 개수가 매우 적음 k=3,4,6 작은 cofactor(Scott, Barreto, “Generating More MNT Elliptic Curves”, 2006) → 상당히 많은 양의 타원곡선의 생성 가능 ! k=10 소수위수를 갖는 타원곡선 생성 (Freeman, 2006) k=12 소수위수를 갖는 타원곡선 생성 (Paulo, Barreto, Michael Naehrig, 2006) k=3,4,6 k=10k=12 k=2 a 3 b

2009 대한수학회 봄 연구발표회 E(F p ): y 2 =x 3 +Ax+B( 단, p 는 소수, A, B ∈ F p ) #(E(F p ))=n=hr( 단, r 은 소수 ) r l p k -1 기본 변수 성질 Pell 방정식 정리로부터 적당한 정수 d 에 대하여 Ф k (x)=dr DV 2 =4hФ k (x)/d-(x-1) 2 변수 치환 : a k =-2([k/2]+4)h+d, b=4h-d( 단, b>0), x=(y- a k )/b, f k = a k 2 -b 2, g=dbD y 2 -gV 2 =f k → (y, V) K=3,4,6 에 대하여 Ф k 는 이차다항식을 만족 ( 예 : Ф 6 (x)=x 2 -x+1) CM 방법 (y, V) → (p, r, h, D) → A, B, 생성자를 구함 D 에 따라 구현시간이 오래 걸리는 경우도 있음 Hasse 방정식 n=p+1-t ( 단, t 는 E(F p ) 의 trace) t 2 +DV 2 =4p ( 단 D>0 는 squarefree 정수, discriminant) 정리 : r l p k -1 ⇔ r l Ф k (x) ( 단, x=t-1) Cyclotomic polynomial Ф (k 의 정보 내포 ) Scott, Barreto MNT EC

2009 대한수학회 봄 연구발표회 Result of Scott, Barreto k=6 인 경우의 결과 (h max =4, D max =10 4 ) k=6 인 경우에서 많은 타원곡선이 생성 소수 p 는 ~2 256 의 조건에서 생성 총 353 개 중 34 개가 ρ≤1.2 을 만족 이상적인 경우 즉, n=p 인 경우는 2 개 출현 구현 시간은 D 에 따라 크게 의존

2009 대한수학회 봄 연구발표회 Definition of Security Loss 정리 (cheon): P 를 소수 위수 r 를 갖는 G 의 생성자로 가정하고 α ∈ Z r 라고 할 때, (1) r-1 의 약수 d 에 대하여 P, αP 와 α d P 이 주 어지면 의 group 연산시간으 로 비밀 키 α 를 복구할 수 있고, (2) r+1 의 약수 d 에 대하여 α i P (0≤i≤d) 이 주 어지면 의 group 연산시간으 로 비밀 키 α 를 복구할 수 있다. 정의 : G=E(F p )[r] 으로 고려할 때, 생성자 P 와 i=1,2, …, q 에 대하여 α i P 가 주어지면 (1) α -1 P 를 구하는 문제를 q-weak Diffie- Hellman (wDH) 문제, (2) α q+1 P 를 구하는 문제를 q-Strong Diffie- Hellman (SDH) 문제라고 한다. P ααPααP αdPαdPαdPαdP …+…+ Cheon, 2006Comuta, 2007 d<r 1/2 안전성손실 비트 단,단,

2009 대한수학회 봄 연구발표회 General Analysis Scott, Barreto 의 MNT 타원곡선 (r=229 비트 ) 774< <2 16 충분히 큰 q 에 대하여 안정 성 손실 L=8 비트 Supersingular 타원곡선의 안전성 이상적인 MNT 타원곡선의 안전성 (n=r) 모든 경우에 Cheon 의 알고리즘에 취약 작은 크기의 q 에 대하여 모두 취약 (4 개의 타원곡선 )

2009 대한수학회 봄 연구발표회 Our Algorithm (k=6 Case) 최소의 안전성 손실을 갖는 MNT 타원곡선 생성 알고리 즘 Scott, Barreto 의 알고리즘 이용 → 12,353 개 Cheon 의 알고리즘에 강한 r 의 조건추가 → 13 개 (type1:3 개, type2:10 개 ) ρ≤1.2 의 조건 추가 → 2,205 개 L=7, q=2 77 h max =4, D max =10 7

2009 대한수학회 봄 연구발표회 Results E(F p ): y 2 =x 3 -3x+B( 단, B ∈ F p ) → 효율적인 측면 고려 (x g,y g ) ∈ F p XF p 는 E(F p )[r] 의 생성자 예제 1) r+1 이 두 개의 큰 소수를 갖는 경우 (3 개 ) r=161 비트 소수, L=2 비트, ρ=1.10 예제 2) r-1 과 r+1 이 큰 소수를 한 개 갖는 경우 (10 개 ) r=180 비트 소수, L=5 비트, ρ=1.05 다른 예제 )

2009 대한수학회 봄 연구발표회 Conclusion pairing 기반 암호에 적용할 수 있는 최소의 안전성 손실을 갖는 타원곡선 생성 1 키사이즈를 늘리지 않고도 160 비트이상의 안전성을 요구하는 암호알고리즘에 적용가능 3 방대한 양의 계산으로 희소성 있는 타원곡선 발견 2 짧은 전자서명 및 ID 기반 암호에 효율적으로 사용가능 4

2009 대한수학회 봄 연구발표회