슬라이드 제목 없음

Size: px

Start display at page:

Download "슬라이드 제목 없음"

서 수
5 years ago
Views:

1 Past 20 Years of Public-Key Cryptosystems 서울대학교 천정희

2 목차 고전암호와대칭키암호 RSA 및기타암호방식 타원곡선암호및그의구현 증명가능공개키암호 최근연구동향 2

3 고전암호 3

4 고전암호 단순대치암호 시저암호 영문알파벳을세자리뒤의알파벳으로대치 ( 예 ) RENAISSANCE -> UHQDLVVDQFH) ( 복호화 ) EHZDUH RI BRXU IULHQG => 아핀변환 : 시저암호의일반화 ( 예 ) f(a) = 3a + 5 (mod 26) Beware of your friend 전이 ( 轉移, transposition) 암호 : 위치바꿈 동음이의, 다표식대치암호, Vernam 암호등 영문자의빈도등을이용해해독 4

5 영문자의빈도 % A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 5

6 블록암호 설계 : Confusion 과 Diffusion 의반복 블록암호의종류 DES( 미국표준 1977~) IDEA( 유럽 ), LOKI( 호주 ), FEEL( 일본 ) Skipjack, TDES( 미국표준 ) AES( 차세대미국표준 ) NESSIE( 차세대유럽표준 ), CRYPTREC( 차세대일본표준 ) 암호화, 인증 (MAC) 에사용 6

7 DES 알고리즘구조 7

8 Rijndael - Encryption Block size: 128/192/256 bit Key size: 128/192/256 bit Component Functions ByteSubstitution(BS): S-box ShiftRow(SR): CircularShift MixColumn(MC): Linear (Branch number: 5) AddRoundKey(ARK) Omit MC in the last round. 4 4 byte array Bit-wise key addition Byte-wise substitution(bs) Shift-Low(SR) Mix-Column(MC) Bit-wise key addition BS, SR, ARK Input Input whitening Round transformation Output transformation Output 8

9 Rijndael 의특성 Substitution-Permutation Network (SPN) (Invertible) Nonlinear Layer: Confusion (Invertible) Linear Layer: Diffusion Branch Number( 확산도 ) Measure Diffusion Power of Linear Layer Let F be a linear transformation on n words. W(a): the number of nonzero words in a. (F) = min a 0 {W(a) + W(F(a))} MC of Rijndael: branch number 5 (a word = a byte) 9

10 스트림암호 10

11 스트림암호의특성 모태 : one-time pad 장점 : perfect cipher, unconditionally secure 단점 : vast amount of secret key needed 이진수열발생기요구조건 주기가길어야한다. 통계적난수특성이우수해야한다. 선형복잡도가커야한다. 상관공격에안전해야한다. 예제 : RC4(WEP), MD5, LILI 11

12 공개키암호 12

13 Motivation 대칭키시스템의키관리 비밀키의개수 : n C 2 = n(n-1)/2 n=100, n C 2 =99 x 50 = 4,950 keys 공개키의응용 기본기능 : 키교환, 암복호화, 서명, 인증 응용분야 : 전자결재, 전자투표, 전자화폐전자복권, 전자계약 시스템 : 네트웍보안, 컴퓨터보안, DB보안

14 일방향함수 One-way ft. Given x, easy to compute f(x). Difficult to compute f -1 (y) for given y=f(x). easy x f(x) difficult Ex) f(x)= x 5 + x 3 + x

15 트랩도어일방향함수 Trapdoor one-way function Given x, easy to compute f(x) Given y, difficult to compute f -1 (y) Easy to compute f -1 (y) for given y when giving certain information -> trapdoor information x easy f(x) easy extra info 15

16 공개키암호 두개의비대칭키사용 Given public key, easy to compute -> anyone can lock. Only those who has secret key compute inverse -> only those who has it can unlock, vice versa. 평문 C=E(P,K e ) P=D(C,K d ) P C ( 암호문 ) P E() Insecure channel D() Attack? 평문 K e K d 16

17 대칭키와공개키의비교 Cryptosystem Item Symmetric Asymmetric Key relation Enc. Key Dec. key Algorithm Typical ex. Key Distribution Number of keys Secure authen. E/D Speed Enc. key = Dec. key Secret Secret Secret Public DES AES Required Many Hard Fast Enc. Key Dec. key Public Private Public RSA Not required Small Easy Slow 17

18 공개키암호의종류 기존의공개키암호 인수분해계열 : RSA, Rabin, Williams, Demitko( 타원곡선 ) 등 이산로그계열 : DL(DSA), ECC, 초타원곡선등 Knapsack 계열 : Merkle-Hellman, Chor-Rivest Lattice 계열 : AD, GGH, NTRU Coding theory : McEliece 비가환군암호 (Braid), 양자암호 인수분해계열과이산로그계열이주로사용됨 Knapsack 계열은모두해독 Lattice 및 coding theory 계열은비효율적 NTRU 의안전성은분석중 ( 서명은해독 ) 향후타원곡선암호가널리쓰일것으로예측 18

19 RSA 와 ElGamal 19

20 기초정수론 a divides b if there exists c s.t. b = ac (denoted by a b) properties for all a,b,c Z a a if a b and b c, then a c if a b and a c, then a (bx+cy) for all x,y Z if a b and b a, then a = b gcd(a,b) is the largest positive integer that divides both a and b p 2 is prime if its only positive divisors are 1 and p Congruences a b mod n iff n (a-b) a a a b implies b a a b and b c implies a c 20

21 Euler s Theorem (n): the number of integers in the interval [1, n] which are relatively prime to n If p is a prime then (p)=p-1 If gcd(m,n)=1 then (mn)= (n) (m) Fermat s (little) theorem Let p be a prime if gcd(a,p)=1 then a p-1 1 (mod p) if r s mod (p-1) then a r a s (mod p) a p a (mod p) for all integers a Let n 2 be an integer, (Euler s theorem) If a Z * n, then a (n) =1 (mod n) If n is a product of distinct primes and if r s mod (n) then a r a s (mod n) Example: mod 5, mod 15 21

22 RSA 암호 (1978) n=pq (n)=(p-1)(q-1) Euler 정리 : 정수 x 에대해 x (n) = 1 mod n 준비 (Alice) 소수 p,q, n=pq 공개키 e: n보다작은정수 비밀키 d: ed = 1 mod (n)=(p-1)(q-1) 암호화 ( 아무나..): 암호문 c=m e (mod n) 을계산 복호화 ( 비밀키소유자 Alice 만가능 ) 암호문 c 를받아 c d =(m e ) d = m k (n)+1 =m(mod n) 계산 22

23 RSA 서명 준비 (Alice) 소수 p, q, n=pq 공개키 e : n보다작은정수 비밀키 d : ed = 1 mod (n)=(p-1)(q-1) 서명 ( 비밀키소유자 Alice 만가능 ) 평문 m 을 n 보다작은정수에대응 m 의서명계산 : s=m d (mod n) 을계산 서명검증 ( 아무나..) 서명 s 를받아 s e =(m d ) e = m k (n)+1 =m(mod n) 계산 23

24 가환군 G 위의원소 g 에대하여 Discrete Log Problem(DLP): 이산대수문제 (g,g x ) 가주어졌을때 x 찾기 Diffie-Hellman Problem(DHP): (g,g x,g y ) 가주어졌을때 g xy 구하기 Decisional Diffie-Hellman Problem(DDHP): (g,g x,g y,g z ) 가주어졌을때 g xy = g z 인지판별 G: 유한체의곱셈부분군, 타원곡선, 초타원곡선, Abelian variety, Class group,... G=Z/p (p 는소수 )? G=Z/n (n 은합성수 )? 24

25 Diffie-Hellman 키교환 용도 : 두사람이공개된통신로를이용하여비밀정보를공유 초기화 : 다음변수를생성하여공개 유한체 F q (q-1이큰소수약수를가짐 ) g F q 갑 : 개인키 a, 공개키 A = g a 을 : 개인키 b, 공개키 B = g b 갑과을공통비밀정보 : g ab =g ba 안전성 (DH-problem): It is hard to compute g ab from (g, g a, g b ) 25

26 ElGamal 암호시스템 초기화 : 다음변수를생성하여공개 유한체 F q (q-1 이큰소수약수를가짐 ) g F q 을의공개키 B=g b ( 비밀키 b) 암호화 ( 갑 ) 평문 m 랜덤한자연수 k를선택 ( g k, mb k ) 를계산하여을에게전송 복호화 ( 을 ) mb k /(g k ) b = m 을계산 26

27 타원곡선암호 27

28 타원곡선암호 타원곡선암호란? 타원곡선위의이산로그문제가어렵다는사실을이용한공개키암호 1985 년 Koblitz 와 Miller 에의해독립적으로제안 타원곡선암호의장점 작은키크기 ( 메모리, 전력측면에서우수 ) 빠른속도 높은안전성 : 해독에지수승시간이걸림. 확률적암호 응용분야 : 키교환, 서명, 인증, 암호화 타원곡선암호의단점 구현의어려움 ( 유한체이론및정수론에기반 ) 메시지확장이두배 28

29 유한체 I 유한체의종류 : GF(p), GF(p n ) GF(p) = Z/pZ = 정수를 p 로나눈나머지들의집합 즉, 사칙연산은정수에서와같이수행한후추가로 p로나눈나머지를취함 예 : 3+4=2 in GF(5), 3-4=4 in GF(5), 2*3=1 in GF(5) 역원 : 3-1 =2 in GF(5) from 2*3=1 in GF(5) 유클리드호제법 나누기 : 4/3=4*3-1 =4*2=8=3 in GF(5) GF(p n ) = Z/pZ[x]/(f(x)) : f(x) 는 Z/pZ 위의 n 차다항식 GF(p n ) = {Z/pZ 위의 n 차미만다항식들의집합 } 사칙연산 : 다항식의사칙연산후 f(x) 로나눈나머지들을구함 29

30 유한체 II Binary Fields GF(2 n ) 원소의표시 : binary vector = a 0 a 1 a 2 a n-1 =a 0 +a 1 x+ a n-1 x n-1 덧셈 = 뺄셈 = bitwise XOR 곱셈 : 다항식곱셈 + reduction 나눗셈 : inversion + 곱셈 ( 곱셈의 10배가량 ) Composite Fields GF((2 n ) m ) 30

31 타원곡선이란무엇인가? 타원곡선 : y 2 + xy = x 3 + a 2 x 2 + a 6 (a 2, a 6 F 2 n) 타원곡선은타원이아님 => 3 차곡선 타원곡선군 : 타원곡선상의점들의집합 E(F 2 n)={(x,y) F 2 n F 2 n y 2 + xy = x 3 + a 2 x 2 + a 6 } {O} E(F 2 n) 은타원곡선덧셈연산에대해군 (group) 을이룸 31

32 타원곡선의연산 타원곡선덧셈연산 (x 1,y 1 ) + (x 2,y 2 ) = (x 3,y 3 ) x 3 = A 2 + A - a 2 - x 1 - x 2, y 3 = - (A + a 1 ) x 3 - B - a 3 A = ( y 2 - y 1 ) / ( x 2 - x 1 ), B = ( y 1 x 2 - y 2 x 1 ) / ( x 2 - x 1 ) if x 1 x 2 타원곡선위의두점을더하는데필요한연산수 유한체곱셈 : 4번 유한체나눗셈 : 2번 유한체덧셈 ( 뺄셈포함 ) : 9번 상수배 : np = P + P + + P (n Z, P E(F 2 n)) 예 ) 3P = P + P + P 32

33 유한체 : F 23 =Z/23Z={0,1,2,,22} 연산 : 23으로나눈나머지만고려 예 : 7*9=63=2* (mod 23) 타원곡선의연산 ( 예 ) F 23 위의타원곡선 E : y 2 = x 3 + x - 4 P=(11,2) E(F 23 ) x 3 + x - 4 = = = 2 2 = y 2 (mod 23) P 의상수배들을구해보면다음과같다. 1P=(2,11), 2P=(4,15), 3P=(21,20), 4P=(18,2), 5P=(7,22), 6P=(17,2), 7P=(20,9), 8P=(3,7), 9P=(11,2), 10P=(11,21), 11P=(3,16), 12P= (20,14), 13P=(17,21), 14P=(7,1), 15P=(18,21), 16P=(21,3), 17P=(4,8), 18P=(2,12), 19P=O E(F 23 ) 의위수 = 19 33

34 Hasse 의정리 : 타원곡선의특성 q # E(F q ) 2 q 타원곡선의위수는대략유한체의크기와같다. 타원곡선의위수 다항식시간 : Schoof 알고리즘 O(log 8 q) q => 1시간이내 최근에는 Satoh 알고리즘이주목 E (F 2 n) = Z/d 1 Z Z/d 2 Z with d 1 d 2 즉, 모든원소는 np 1 + mp 2 꼴로표시 (m, n Z, P 1,P 2 E(F 2 n)) 대체로 d 1 = 1, 즉 E (F 2 n) 는순환군 34

35 타원곡선이산로그 유한체위의이산로그문제 유한체 F q 위의두원소 a,b가주어졌을때 b = a x 인정수 x를찾는문제 Diffie-Hellman 키교환, DSS(Digital Signature Standard), ElGamal 암호등에사용 Index calculus 방법에의해준지수시간 (subexponential time) 에풀림 인수분해에기반한 RSA와비슷한안전성 이산로그문제는모든가환군에서성립 타원곡선위의이산로그 Abelian variety위의이산로그 Class group위의이산로그 타원곡선위의이산로그 유한체 F q 위에정의된타원곡선 E와그위의두점 P,Q Q=mP가되는정수 m을찾는문제 특수한경우를제외하면지수시간알고리즘 Diffie-Hellman 키교환, 타원곡선 ElGamal, ECDSA등에사용 35

36 타원곡선 Diffie-Hellman 용도 : 두사람이공개된통신로를이용하여비밀정보를공유 초기화 : 다음변수를생성하여공개 갑 을 유한체 F q 와그위의타원곡선 E 큰소수위수 n을갖는타원곡선점 P 개인키 : a 공개키 : A = ap 개인키 : b 공개키 : B = bp 갑과을의공통비밀정보 : (ab)p=(ba)p 안전성 (DH-problem): It is hard to compute abp from (P,aP,bP) 36

37 타원곡선 ElGamal 용도 : 갑이을의공개키를사용하여을에게비밀정보 m 을전송 초기화 : 다음변수를생성하여공개 유한체 F q 그위의타원곡선 E 큰소수위수 n 을갖는타원곡선점 P 을의공개키 B=bP( 비밀키 b) 암호화 ( 갑 ) 평문 m 을타원곡선점 M 으로전환 랜덤한자연수 k 를선택 ( k P, M + k B) 를계산하여을에게전송 복호화 ( 을 ) (M+kB) - b(kp) = M + (kb - bk)p = M 을계산 M 에서평문 m 을복구 P1363 에서는 M+kB 대신 M 과 kb 의 x 좌표를곱한값사용 37

38 타원곡선암호공격방법 ( 일반적인경우 ) Baby-Step Giant-Step : O( q log q) (F q 위의타원곡선경우 ) => 지수시간 Pollard rho : O( q) (F q 위의타원곡선경우 ) => 지수시간알고리즘 Pohlig-Hellman 가장큰소수위수의크기에의존 타원곡선의위수가작은소수의곱으로표시될때 (Smooth case) => 다항식시간 타원곡선의위수가거의소수인경우 => 적용불가능 Index calculus 유한체위의이산로그경우 => 가장강력한공격방법 타원곡선에는적용불가능 (J. Silverman) 결론 : 일반적인타원곡선암호공격 => 지수시간소요 38

39 타원곡선암호공격방법 ( 특수한경우 ) 특이타원곡선 (Singular Elliptic Curve) 타원곡선의 discriminant 가 0 일경우 ( 엄밀히타원곡선아님 ) 유한체위의이산로그와동일 ( 준지수시간알고리즘존재 ) 비트당안전도낮음 (1024 비트필요 ) 초특이타원곡선 (Supersingular Elliptic Curve) t = 2 n # E(F 2 n) 가 2 의배수인경우 MOV 공격에의해유한체위의이산로그로바뀜 준지수시간알고리즘존재 비트당안전도가낮음 (1024 비트필요 ) 변칙타원곡선 (Anomalous Elliptic Curve) q 가소수이고, # E(F q )=q 인경우 Semaev 의공격에의해 O(log q) 시간에해독 안전한타원곡선 : 특이, 초특이, 변칙타원곡선배제 39

40 타원곡선의분류 3 차곡선 (Cubic Curve) 타원곡선 (Elliptic Curve) 특이 3 차곡선 (Singular) 정규타원곡선 (Ordinary) 초특이타원곡선 (Supersingular) 비변칙정규타원곡선 변칙타원곡선 (Anomalous) 40

41 안전한타원곡선암호 특이, 초특이, 변칙타원곡선배제 ( 위수가 p-1, p+1, p 인것배제 ) 타원곡선의위수가거의소수인것사용 이경우타원곡선이산로그를푸는가장빠른알고리즘 Pollard rho 방법 수행시간 : O( q) (F q 위의타원곡선경우 ) 지수시간알고리즘 최근 Smart 등은타원곡선을 Abelian variety 로올림하여이산로그를푸는알고리즘발표 41

42 암호시스템안전성비교 ECC 키크기 (bits) 암호시스템안전성비교 RSA 키크기 (bits) Time to Break (MIPS Years) , , , Key Size Ratio 타원곡선암호공격방법 : Pollard rho RSA 공격 : Number Field Sieve(NFS) 42

43 ECC Challenge 주최 : Certicom( 문제 타원곡선이산로그 문제유형 : q = 2 n 인경우, Koblitz curve(cm curve), q는소수인경우 풀린것 : ECC-p79 (79자리소수 p) 예제 문제이름 : ECC2K-359 유한체 : GF(2 359) 타원곡선 E : y 2 +xy = x 3 + x 2 +1 (Koblitz Curve) P,Q는랜덤하게생성된두점 (website 참조 ) 예상계산량 : 일 (Pentium 100에서 Pollard rho사용시 ) 상금 : 100,000USD( 약 1.2 억원 ) 43

44 타원곡선상수배연산 44

45 Point Multiplication General problem of exponentiation in abelian groups Shortest addition chain problem: Given a positive integer k, starting from 1, and computing at each step the sum of two previous results what is the least number of steps required to reach k? Knuth (1981): The art of computer programming Special feature to use Include addition-subtraction chains and signed representations Consider the relative complexities of point addition and point doubling Coordinate system Relative complexity of field inversion and multiplication For certain families of elliptic curves, specific shortcuts are available CM curves 45

46 Binary Method 이진방법 (Square and Multiply) 7P = 2 ( 2P + P) + P 알고리즘 Input P and k i {0,1} where x=sum of k i 2 i from i=0 to w M O For i=w to 0 by 1 M M+M If k i =1 then M M+P Return M=kP 계산량 두배 : w 덧셈 : 최대 w, 평균 w/2 m-ary 방법 k 를 2 m 진법전개. P, 2P,, (2 m -1)P 계산후저장 복잡도 : (m-1) 점저장. w/m 번 m 배와덧셈 ( 평균 ~ 최대 ) 46

47 Complexity of Binary Method Binary Method l :the length of k, W=wt(k) l-1 doublings and W-1 additions Complexity = nd+(n/2)a Affine: 1.5 ni + 3nM Proj: 10nM (a=0. Use mixed additions) m-ary method Precompute P, 2P,, mp Complexity = nd+(n/r)a where r = log 2 m 47

48 Signed Binary Method 덧셈 - 뺄셈방법 타원곡선뺄셈은덧셈과같은어려움을가짐에착안 -(x,y)=(x,-y) in GF(p) or (x,x+y) in GF(2 m ) 15P = 2(2(2(2P))) - P => 5 번연산 이진방법의경우 : 2(2(2P+P)+P)+P => 6 번연산 상수의 NAF(non-adjacent form 존재 ) 알고리즘 Input P and k i {-1,0,1} where k=sum of k i 2 i from i=0 to w M O For k=w to 0 by 1 M M+M If k i =1 then M M+P If k i =-1 then M M-P Return M=kP 계산량 : 두배는 w, 덧셈은최대 w/2, 평균 w/3 48

49 Window Method 크기 w 인 window 는 1,3,,2 w -1 혹은 0 P, 3P,, (2 w -1)P 를사전계산 주어진상수를이진전개한후 lsb 부터 w 크기의 window 로전개 알고리즘 k=w[s-1]w[s-2] W[0] Compute Q W[s-1]P For I =s-2 to 0 by 1 Compute Q 2 w Q If W[I] 0 then Q Q+W[i]P Return Q 계산량 : 2 w-1 1 precomputation, 비트수 - 첫번째윈도우의크기의제곱, 윈도의개수만큼의곱셈 49

50 -adic expansion 타원곡선의계수가작은유한체에속할때 CM 타원곡선 ( 복소수상수배를갖는타원곡선 ) 상수의프로비니어스 (Frobenius) 전개가가능 빠른상수배가능 예 ) Koblitz curve : y 2 +xy = x 3 + x 2 +1 프로비니어스전개방법의특징 현존하는가장빠른상수배알고리즘 적용되는타원곡선제한 기존방법과의비교 이진방법덧셈 - 뺄셈방법프로비니어스전개방법 다항식기저 정규기저

51 다중점에대한상수배연산 다중점의연산 (mp+nq 또는 mp+nq+lr) 기법 예를들어 34P+11Q 를계산함. 1. P, Q, P+Q 를사전계산함 = , 11= 다음의 array 를만듦 I 1 =01 2 =1, I 2 =00 2 =0, I 3 =10 2 =2, I 4 =00 2,=0 I 5 =11 2 =3, I 6 =10 2 =2 5. Q+2(P+Q+2(2(Q+2(2P)))) = 34P+11Q로계산. 복잡도 : 2 l -1+(n-1)+(n-1) ( 최대 ), 2 l -1+(n-1)+(n-1) (1-1/ 2 l ) ( 평균 ), l은다중점의개수 mp와 nq를따로계산하여더하는것보다매우이득이됨. 51

52 Structure Binary Signed binary Non-Adjacent Form (NAF) -adic expansion Koblitz curves Joint Sparse Form (JSF) -adic NAF -JSF (Eurocrypt 2003) 52

53 Other PKCs 53

54 McEliece Cryptosystem Key Generation Integers k, n, and t are fixed as common system parameters Each entity A performs Encryption Choose a k-by-n generating matrix G for a binary (n,k)-linear code which can correct t errors and for which an efficient decoding alg. is known. Select a random k-by-k binary non-singular matrix S Select a random n-by-n permutation matrix P Compute a k-by-n matrix G =SGP A s public key is (G,t); A s secret key is (S,G,P) c=mg +e with wt(e)=<t Decryption c =cp -1 and decode c to m m=m S -1 For moderate security, the public key size is about 2 19 bits ~ 64kbytes. 54

55 Knapsack-based PKC Subset Sum Problem (NP-complete problem) (problem) I=(s 1,,s n,t) for s i : integer T:target sum (question) is there 0-1 vector x=(x 1,..x n ) s.t. i=1 n x i s i = T? Schemes All of them are broken by LLL algorithm Merkle-Hellman Iterated MH Graham-Shamir Chor-Rivest etc 55

56 Key Generation (n: system parameter) MH knapsack encryption Choose a superincreasing sequence (b 1,,b n ) and modulus M s.t. M>b 1 + +b n Select a random integer W, 1 W<M with gcd(w,m)=1 Select a random permutation of {1,2,,n} Compute a i =Wb (i) mod M for i=1,2,,,n A s public key=(a 1,,a n ); A s private key=(,m,w,(b 1,,b n )) Encryption For a message m=m 1 m 2 m n, c=m 1 a 1 +m 2 a 2 + +m n a n Decryption Compute d=w -1 c mod M By solving a superincreasing SSP, find r 1,r 2,,r n s.t. d=r 1 b 1 + +r n b n m i =r (i) 56

57 Lattice Cryptography Lattice: a discrete subgroup of R n Hard Problems SVP(NP-hard) : Find a short (shortest) non-zero vector in a lattice L AD scheme CVP : Given a point in R n find a closest vector in a lattice L DDH scheme SBP : Find a smallest basis given a lattice L Analyzed by LLL algorithm NTRU(1996) Its security is based on lattice reduction Signature scheme is broken Refer to the website 57

58 Nonabelian Group Cryptography 58

59 Problems in non-abelian group Let G be a non-abelian group and a, x in G Conjugacy Problem(CP) Given (x,a -1 xa), compute a. If we denote a -1 xa by x a, it is similar to DLP CDH-type Conjugacy Problem(CDHCP) Given (x,a -1 xa,b -1 xb), compute b -1 a -1 xab DDH-type Conjugacy Problem(DDHCP) Given (x,a -1 xa,b -1 xb,c -1 xc) decide whether c -1 xc = b -1 a -1 xab 59

60 Sufficient Conditions on G 1. An element can be effectively distinguished from other elements(word Problem) 2. Elements can be efficiently expressed by binary strings 3. The group operation can be performed with trapdoor 1. There are two nontrivial commuting subgroups A and B of G. Namely, ab=ba for all a in A and b in B 2. The conjugacy problem is hard Instances: Braid Groups, Matrix Groups(?) 60

61 Key Agreement on non-abelian group G Obj: Agree on shared secret over insecure channel Key Generation Take a non-abelian group G satisfying the previous conditions Take an element x of G Alice Take a random element a and send a -1 xa to Bob Bob Take a random element b and send b -1 xb to Alice Shared Key: a -1 (b -1 xb)a=b -1 (a -1 xa)b 61

62 Encryption on non-abelian group G Key Generation System Parameter= (G,x) with x G A secret key=a G; A s public key=a -1 xa(=y) Encryption (by Bob) Take a random element b G (c 1,c 2 )=(b -1 xb, H(b -1 yb) m) Decryption (by Alice) m=h(a -1 c 1 a) c 2 62

63 What is the Braid Group? B n has the following group presentation. Generator: 1,, n-1 Relation: i) i j = j i, if i-j > 1 ii) i i+1 i = i+1 i i+1, for i=1,, n-2 i a b b -1 ab 63

64 증명가능암호 64

65 암호시스템의안전성증명방법 Try to find an attack Yes Attack found No Insecure? Prove the absence of attacks under some assumptions Yes Attack found Assumption was false 65

66 안전성개념 OW ( 일방향성 ) : given a challenge ciphertext y, adversary s inability to decrypt y and get the whole plaintext x. IND ( 구별불능성 ) : given a challenge ciphertext y, adversary s inability to learn any information about the plaintext x. NM (Non-malleability) : given a challenge ciphertext y, adversary s inability to get a different ciphertext y s.t. the corresponding plaintexts, x and x are meaningfully related. e.g., meaningful relation x = x

67 ATTACKS Security Goals and Adversay Attacks CCA CPA IND GOALS Four notions of security: IND-CCA NM-CCA IND-CPA NM-CPA NM 67

68 Relations among notions [BDPR98, DDN00] IND-CPA IND-CCA NM-CPA NM-CCA Implication: A B : Any scheme meeting notion A also meets notion B Separation: A B : There exists a scheme meeting notion A but not meeting notion B 68

69 Encrypt 128 r 896 plaintext OAEP1 Decrypt ciphertext G sk=f -1 r t H s s t r H s s pk=f G ciphertext plaintext 69

70 RSA OAEP Bleichenbacher s attack(1998): RSA-PKCS#1is not IND-CCA For 1024-RSA, the attack requires ~ chosen ciphertexts. But this attack fails on RSA-OAEP2 RSA-OAEP2 adopted as PKCS#1 v2.0 and considered for other standards. 70

71 OAEP2 Encrypt Decrypt 128 r plaintext ciphertext G sk=f -1 r t H s s t r H s s pk=f G ciphertext a plaintext Accept iff a =

72 Security Scheme Security Number - Theoretic Assumption Hash Function Assumption PSEC-1 IND-CCA2 EC-DDH Truly random PSEC-2 (one-time pad) IND-CCA2 EC-DH Truly random PSEC-3 (one-time pad) IND-CCA2 EC-GDH Truly random EC- Cramer-Shoup IND-CCA2 EC-DDH UOWHF OAEP IND-CCA2 RSA Truly random EC-DDH.distinguish a P, b P, ab P a P, b P, random EC-DH. a P, b P ab P EC-GDH. a P, b P ab P 72 EC-DDH oracle P

73 최근연구동향 73

74 Weil Pairing (P,Q): E[n] E[n] GF(q r ) * where e(p,q) = f P (A Q )/f Q (A P ) with (f P )=A p and A P ~ (P)-(O) Properties e(p,p)=1 for all P in E[n] [Bilinear] e(p 1 +P 2,Q)=e(P 1,Q)+e(P 2,Q) and e(p,q 1 +Q 2 )=e(p,q 1 )+e(p,q 2 ) [Alternating] e(p,q)=e(q,p) [Non-Degenerate] e(p,q)=1for all Q in E[n] implies P=O [n-th root] e(p,q) n =1 Applications MOV attack Three party key exchange protocols (ANTS 2000) ID-based Encryption (Crypto 2001) Short signature (AsiaCrypt 2001) 74

75 삼자간키교환 Notation G: a multiplicative group (e.g. F q ) on which DLP is hard H: a group on which DLP is hard g: an element of G f: G x G H : non-degenerate bilinear map, that is, f(a m,b)=f(a,b m )=f(a,b) m (Secret Key, Public Key) Alice: (a,g a ) Bob: (b,g b ) Chris: (c,g c ) Common Shared Secret: f(g,g) abc =f(g a,g b ) c Security: DLP on G and DLP on H Practical Example: Weil Pairing (P,Q): E(F q ) E(F q ) GF(q n ) * Open Problem: Multi-party Key Exchange Protocol 75

76 Public key = ID such as address. Set up p=6q-1, p =2 mod 3, p = 1024 ID-based Encryption E: y 2 =x 3 +1 over F p, #E(F p )=p+1 supersingular P E(F p ) of order q Pick s r Z q*. Set P pub =sp Hash ftns: H: F p^2 {0,1} n and G: {0,1}* F p Params = <p, n, P, P pub, G, H>, Master-key = s Extract: pk=q ID from ID. sk=d ID =sq ID Encrypt: C=<rP, M H(e(Q ID, P pub ) r )>, r r Z q Decrypt: M=V H(e(d ID, U)) where C=<U,V> Security based on WDH (Weil Diffie-Hellman Assumption) hard to compute e(p,p) abc from P, ap, bp, cp 76

77 ID-based Signature G: a group of prime order l in which DDHP can be solved (GDH group). Setup: G = <P> Step1: Pick a random s Z / l and set P pub = sp. * Step2: Choose two hash function H :{0,1} G Z / l, H Extract: Given an identity ID Step1: Compute a private key D ID = sh 2 (ID) Step2: Compute a public key Q ID = H 2 (ID) :{0,1 * 1 2 } G master key s Sign: Given D ID, message m Step1: Pick a random number r Z / l Step2: Signature ( U, V) where U rq, h H1( m, U), V ( r h) Verify: ID D ID Check whether (P,P pub,u+hq ID,V), where h = H 1 (m,u), is a valid DH tuple. (P,P pub,u+hq ID,V) = (P,P pub,(r+h)q ID,(r+h)D ID ) = (P,sP,(r+h)Q ID,s(r+h)Q ID ) 77

78 Short Signature Set up E: y 2 =x 3 +2x 1 over F 3^l Pick x r Z q*. Set R=xP as his public key Sign S=xM for a message M Verify e(p,xm) = e(r,m)? Weil paring should be computed efficiently. 78

79 Signature Aggregation Function: Aggregate many signatures as one signature Verify many sign s by only one verification Key Generation: publish v=g x for secret x Signing: h(m) x Aggregation S i =h(m i ) xi S= S i Aggregate Verification e(g,s)= e(v i,s i ) 79

80 Broadcast Encryption Devise an encryption algorithm which can be decrypted by multi users Trivial Solution (E 1 (K),E 2 (K),,E n (K), E K (M)) 1024 bits increase per each user for RSA-1024 Use Tree to reduce the number of key into log n Application Broadcast Pay TV Adhoc communication Digital Right Management (DRM) 80

81 Forward Secrecy What can we do if the key is compromised? Forward secure Diffie-Hellman: Ephemeral DH Forward secure signature: Time stamping Forward secure encryption: shredding Forward-secure signature: based on the GQ signature Based on the integer factorization problem (but not RSA) No known DLP-based signature Forward-secure encryption: based on hierarchical ID-based encryption 81

82 Search on encrypted data Operation of encrypted data Find an encryption function preserving specific relations: Sum preserving Order preserving Word matching is supported Application: Voting, Storage, DB 82

83 고맙습니다.

public key private key Encryption Algorithm Decryption Algorithm 1

public key private key Encryption Algorithm Decryption Algorithm 1 One-Way Function ( ) A function which is easy to compute in one direction, but difficult to invert - given x, y = f(x) is easy - given