이강좌는 C S Technology 사의지원으로제작되었으며 copyrght 가없으므로비영리적인목적에한하여누구든지복사, 배포가가능합니다. 연구실홈페이지에는고성능마이크로프로세서에관련된많은강좌가있으며누구나무료로다운로드받을 수있습니다. 연세대학교전기전자공학과프로세서연구실박사과정김문경 E-mal: yonglee@yonse.ac.kr 암호화칩의 VLSI 설계와구조의개요 (Introducton to VLSI Desgn and Archtecture o Cryptography Chps 4..3 연세대학교이용석교수연구실박사과정김문경 E-mal: yonglee@yonse.ac.kr Homepage: http://mpu.yonse.ac.kr 전화 : -39 39-794 -- -- -- eerences Smart Cards, Unverste Catholque de Louvan,, 998, 5 [4] 김철, 암호학의이해, 영풍문고, 996 [5] 한국정보통신기술협회, 88비트블록암호 알고리즘표준 (SEED,, 999, 4. [6] 이용석, 고성능마이크로프로세서 ALU 와 egster Fle 의구조, 고성능마이크로프로세서구조와설계강좌시리즈, 연세대학교,,. [7] SA Cryptosystem : http://www.rsa.com [8] Cetn Kaya Koc et al, Analyzng and Comparng Montgomery Multplcaton Algorthms,, IEEE Mcro, 996, 6. [9] http://www.certcom.com [] E. Mastrovto.. : VLSI Archtectures or Computaton n Galos Felds, PhD thess, Dept. o Electrcal Eng., Lnkopng Unv., Sweden, 99. [] NBS, Data Data Encrypton Standard, FIPS Pub. 46, U.S, Natonal Bureau o Standards, Washngton DC, Jan. 977. [] Bruce Schneer, Appled Cryptography, second edton, John Wleysons, 996 [3] J.F.Dhem, Desgn Desgn o an Ecent Publc- Key Cryptographc Lbrary or ISC-Based -3- -4- -5-
[] S. Moon, J. Park and Y. Lee, Fast VLSI Algorthms or Hgh-Securty Ellptc Curve Cryptographc Applcatons, IEEE Transactons on Consumer Electroncs,, Vol. 47, Num. 3, pp. 7-78, 78,. [] 문상국, 타원곡선암호용프로세서를위한고속 VLSI 알고리즘의연구와구현, 연세대학교전기전자공학과박사학위논문,,. [3] N. Kobltz, A Course n Number Theory and Cryptography, Sprnger-Verlag, 99. Topcs 암호화이론개요 비밀키 (secret key 암호시스템 공개키 (publc key 암호시스템 암호화의필요성 기본적인암호시스템 정보시스템의사회적중요성 네트웍을통한서비스의급증 ( 전자상거래, 전자금융, 가장경제적으로정보시스템이요구하는정보의보안수준에따라효율적이면서도계층적인보안대책을마련해야함 M Sender Encrypton C = E Ke [M] M : Plantext C : Cphertext E : Encrypton algorthm D : Decrypton algorthm Ke : Encrypton key Kd : Decrypton key C Decrypton D Kd [C] = M M ecever -6- -7- -8- -9- 암호시스템의기능 Securty Attacks Authentcaton( 인증 Condentalty( 기밀성 Message ntegrty( 무결성 Nonrepudaton( 부인봉쇄 Message replay preventon( 전달방지 Access control( 접근제어 Avalablty( 유용성 Interrupton Modcaton Intercepton Fabrcaton -- --
암호용알고리즘 Symmetrc-Key Cryptosystem 대칭키암호시스템 DES, trple-des SEED 공개키암호시스템 SA, DSA, KCDSA Ellptc Curve Cryptography(ECC HASH uncton, Pseudo-random number generaton Plantext Lockng Key (Encrypton Cphertext????????? Plantext Unlockng Key (Decrypton -- -3- Publc-Key Cryptosystem 비밀키와공개키의비교 Plantext One Way Plantext Symmetrc-key Encrypton 빠른속도 Publc-key Encrypton 비교적느림 동일한키사용 암 / 복호화에다른키사용 알고리즘과키의사전협의 서로다른키의분배소유 Cphertext????????? 전자서명기능없음 공유키보관의비밀성 전자서명기능 두키중하나만비밀리에보관 Publc Key (Encrypton Prvate Key (Decrypton 알고리즘과암호문공개가능 DES, SEED 알고리즘, 암호문, 공개키공개가능 SA, ECC -4- -5- Bob Dgtal Sgnature Ths s Bob. One Way Ths s Bob. Alce Bob Dgtal Sgnature wth Hash Functon Hash Functon Message: Ths s rom Bob. D bob Hash Functon Message: Ths s rom Bob. E bob ##### # ##### # Alce Dgtal Sgnature ##### # Prvate Key (Sgnng Publc Key (Vercaton Message: Ths s rom Bob. ##### # Compare -6- -7-
암호시스템의요구사항 비밀키암호시스템 임의의키에대해암 / 복호화가능 키의비밀성 키스페이스 암호문의랜덤성 저항력 비가역성 DES (Data( Encrypton Standard Trple-DES SEED -8- -9- DES(Data Encrypton Standard M 64bts DES C 64bts ( 참고문헌 [] DES - K e = K 6 K 5 K K d = K K K 6 M 64bts -- DES 의암호화블록 (Festel 구조 입 력 초기치환 L K = L, K L = K = L, K L = K3 ( 참고문헌 [] 5 = L 4 4, K 5 L 5 = 4 K6 L 6 = 5 6 = L 5 5, K 6 역초기치환 출 력 -- 초기치환, 역초기치환테이블 키블록 K K K6 58 5 4 34 6 8 4 8 48 6 56 4 64 3 압축치환 압축치환 압축치환 6 5 44 36 8 4 6 54 46 38 3 4 6 64 56 48 4 3 4 6 8 57 49 4 33 5 7 9 59 5 43 35 9 3 6 53 45 37 9 3 5 63 55 47 39 3 3 5 7 39 7 47 5 55 3 63 3 38 6 46 4 54 6 3 37 5 45 3 53 6 9 36 4 44 5 6 8 35 3 43 5 9 59 7 34 4 5 8 58 6 33 4 9 49 7 57 5 64 비트키 ( 외부 초기치환 8 비트 D 8 비트 C 왼쪽쉬프트 왼쪽쉬프트 D C 왼쪽쉬프트 왼쪽쉬프트 D C 왼쪽쉬프트 왼쪽쉬프트 D 6 C 6 - 초기치환 - - 역초기치환 - -- -3-
키블록치환테이블 57 49 4 33 5 7 9 58 5 4 34 6 8 59 5 43 35 7 9 3 6 5 44 36 63 55 47 39 3 3 5 7 6 54 46 38 3 4 6 6 53 45 37 9 3 5 8 4 - 키생성과정의초기치환 - 4 7 4 5 3 8 5 6 3 9 4 6 8 6 7 7 3 4 5 3 37 47 55 3 4 5 45 33 48 44 49 39 56 34 53 46 4 5 36 9 3 - 키생성과정의압축치환 --4- Weak Key F F E E F E F E F E Sem-weak key F E F E,, F E -5- 함수의구조 함수치환테이블 - :- 번째의오른쪽 3 비트 3 3 4 5 6 7 표에의한확장 K : 번째라운드의키 4 5 6 7 8 9 8 9 3 3 4 5 6 7 9 8 7 5 3 6 5 8 3 6 7 8 9 8 4 4 S S S3 S4 S5 S6 S7 S8 3 4 5 3 7 3 9 4 5 6 7 8 9 9 3 3 6 표에의한치환 8 9 3 3 3 4 5 ( -, K -6- - 확장치환 - - 출력치환 - -7- S-box a 6 a 5 a 4 a 3 a a 행 : {a 6, a } 열 : {a 5, a 4, a 3, a } => s 6 번째행 번째열 4 => S I S S 6 4 3 S 8 5 S-box 설계기준 각 S-box 의임의의행은 -5 의적당한치환이다. 어떤 S-box 도입력의선형함수가아니다. S-box 에하나의입력비트를변환시키면적어도두개의출력비트가변한다. 어떤 S-box 나임의의길이 6인비트문자열인입력 x에대해서도 S(x 와 S(x 는적어도두비트가다르다. 어떤 e나 에대해서도 (e, {, }, S(x S(x e 이다. -8- S-box 는임의의하나의입력비트가고정될때임의의 S-box 출력에서 과 의개수차이가최소화되도록선택되었다. -9-
andom Number Generaton True NG(andom Number Generator Frequency varatons between two oscllators Instablty o a ree runnng oscllator Thermal nose o varous semconductors lke zener dodes Charge o a semconductor capactor charged durng a xed tme Inluence o turbulence o varous luds n some devces lke hard dsks Etc. PNG(Pseudo-NG NG Usng DES INC K FLASH A FLASH B 3 INC AM 3 ( 참고문헌 [3] 64 64 DES PN -3- -3- Block Cpher Modes( ECB mode m 비트키 ( 참고문헌 [4] Block Cpher Modes( CFB mode m 비트키 n- 비트입력쉬프트레지스터 A 블록암호알고리즘 n- 비트데이터블록 블록암호알고리즘 n- 비트암호블록 n- 비트출력쉬프트레지스터 B OFB mode n- 비트입력쉬프트레지스터 CBC mode 암호문평문 n비트데이터블록 n비트블록레지스터 m 비트키 블록암호알고리즘 n- 비트레지스터 A n- 비트출력쉬프트레지스터 m 비트키 블록암호알고리즘 평문 k 비트 암호문 n- 비트레지스터 B 암호문 -3- -33- Trple-DES Plantext Encpher DES DES - DES K (56bts K K DES - DES DES - Cphertext SEED ( 참고문헌 [5] Global structure : Festel block cpher Block length : 8bts Key length : 8bts # o rounds : 6 round Symmetrc block cpher Decpher -34- -35-
SEED 의구조도 K K K3 K6 K =(K =(K, ;K, SEED 의 함수구조 C D 입 = L, K = L, K 5 = L 4 4, K 5 L 6 = 5 출 K, + + + G + K, 력 L L = L = L 5 = 4 6 = L 5 5, K 6 력 -36- G + G + C D : 라운드수 -37- G 함수구조 MSB X3 X X X LSB SEED ound Block 구현 m3 m m m m3 m S S S S m m m3 m m m m3 m SS3 SS SS SS m m 라운드공유방식 6 라운드를하나의블록을반복사용 6 라운드펼침방식 6 라운드를별도로하나씩구현 n 라운드혼합방식 n 개의라운드를하나의블록으로처리 Z3 Z Z Z -38- -39- Exclusve O (XO Gate ( A B A B O ( 참고문헌 [6] O Exclusve O (XO Gate ( A B O -4- -4-
Exclusve O (XO Gate (3 Exclusve O (XO Gate (4 Weak B A O B N O A -4- -43- 공개키암호시스템 비밀키관리의어려움해소 디지털서명가능 EDI(Electronc Data Interchange SA ECC SA 공개암호시스템 ( 참고문헌 [7] vest, Shamr, Adleman 안전성 : 약 자리십진정수의소인수분해의어려움 오일러의정리를사용 : (n : 양의정수의집합 {,,,, n-} n 중 n과서로소의관계에있는원소들의개수 (p : p- p (p 는소수 (n : (pq = (p-(q (q- 서로소인두양의정수 a, n 에대해 a (n (mod n -44- -45- SA Procedure( 단계 두개의큰소수 p, q 를선정하여자신의비밀열쇠로함 단계 n = pq 를공개, (n 과서로소인임의의정수 e를선택하여공개자물쇠로함 단계 3 ed (mod (n 이되는 d를 Eucld 호제법등으로계산하여비밀열쇠로함 p, q, d 는비밀키, n, e 는공개자물쇠 -46- SA Procedure( 암호화단계 평문 M을공개자물쇠 e를사용하여암호화 C M e (mod n 복호화 암호문 C를비밀열쇠 d를사용하여복호화 C d = (M e d = M tφ(n (n + = M tφ(n M M (mod n 여기서 ed = tφ(n + (Qed( mod φ(n -47-
Example( Example( 단계 p = 47, q = 59 로정하고비밀로함 단계 n = pxq = 773 을공개, (773 = (47-(59 (59- = 668 과서로소인임의의정수 e = 7 을선택하여공개 단계 3 7x57 (mod 668 d = 57 (668 을알아야만알수있음 -48- 암호화 상대편이공개자물쇠 n = 773 e = 7 을찾아암호화 평문 M = 5 일때 C = 5 7 = 769394535 58(mod 773 복호화 58 57 (mod 773 = 5-49- Example(3 평문 : ITS ALL GEEK TO ME M = 9 9 78 55 5 3 5 C = 9 7 948(mod 773 C = 948 34 84 444 663 39 778 774 9 655 M = 948 57 9(mod 773 Montgomery Algorthm( A = A(modN B = B(modN U = AB(modN U = AB = AB = A ( 참고문헌 [8] B = AB (modn -5- -5- Montgomery Algorthm( ECC 공개암호시스템 I GCD(, N = and N N = -N - mod Then : U + (UN mod N U- mod N Group 에서의이산대수문제에기반한암호알고리즘 유한체위에서정의된타원곡선덧셈군을이용 고속의유한체연산필수 동일 base eld 를사용하더라도다른곡선사용가능 -5- -53-
타원곡선의형태와연산개념 ( 타원곡선의형태와연산개념 ( P + Q = P + (-P = O P = P = O ( 무한원점 y y y y (3.89,5.6 P Q(.,.836 (.,.64 P(,.65 P(., P(.35,.86 x y = x 3 7x x 3 y = x 6x+ 6 (.,.64 x 3 y = x 3x+ 5 x 3 y = x + 5x 7 ( 3.89, 5.6 P -54- -55- ECC Encrypton Arthmetc Herarchy Pont Addton GF Multplcaton/ Squarng GF Dvson GF Addton Pont Multplcaton Pont Double GF Multplcaton/ Squarng GF Dvson GF Addton EC Elgamal Cryptosystem Publc actors : 수신자 비밀키 : k a k a P 를계산하여전달 k a k b P를계산복호화 : M = C M / k a k b P 3 EC : y + xy = x + ax + b m p(x = x + pm x +... + px + p P(x,y k b P C M k a P 송신자 비밀키 : k b k b P 를계산하여전달메시지 M(m x, m y 준비 k a k b P= (x k, y k 를계산암호화 : C M (m x x k, m y y k -56- -57- GF( m 에서의 ECC Pont Multplcaton GF(p 에서의연산 SA 와거의같은회로를요구 Carry 를고려한연산 y = x 3 + ax + b GF( m 에서의연산 정수가아닌 진벡터를이용한연산 Carry 를고려하지않고 vector 간연산만수행 진벡터이므로벡터내의 addton 연산은 xor 로대치가능 y + xy = x 3 + ax + b Double Add algorthm kp = P + P + P +... + P t k = λ λ {, = t kp = λ ( P = } -58- -59-
Pont Addton ule Pont Double ule Ellptc curve : y + xy = x 3 + ax + b Pont addton : I ether o P or Q s O,, the result s the other pont. I P = Q, use Double routne I x p = x q and y p y q then P + Q = O. O I P Q then P + Q = where s = (y P + y Q / (x P + x Q x = s + s + x P + x Q + a y = s(x P + x + x + y P -6- Ellptc curve : y + xy = x 3 + ax + b Pont double : I x p = and the result s O. I x p then P = where s = x P + y P / x P x = s + s + a y = x P + (s + * x -6- Pont Negaton ule GF( m 에서의기본연산 ( Ellptc curve : y + xy = x 3 + ax + b A(α = a m- α m- + + a α + a B(α = b m- α m- + + b α + b Pont negaton : P = where (x y = (x p, x p + y p -6- Addton(=subtracton=XO Multplcaton(mod p(x Z( α = A( α bα = b ( α A( α = (z,z,...,z = = (b,b,...,b A( α αa( α α A( α... α A( α -63- GF( m 에서의기본연산 ( Addton Squarng Z(a = A (a mod p(x A(α = a m- α m- + + a α + a B(α = b m- α m- + + b α + b Exponentaton Square multply e = e m- m- + e m- m- + + e + e e e em em 3 e e A = (...((A A A...A A A(α + B(α = ( (a m- + b m- α m- + + ( (a + b α + ( (a + b Inverson(dvson m β = β (b GF( m m β = β -64- -65-
Multplcaton( Multplcaton( Polynomal bass Seral multplcaton Parallel multplcaton p(x = x m + p m- x m- + p m- x m- +... + p x + p x + p p(α = Z( α = A( α bα = b ( α A( α = = Z( α = (...(((b A( α α + ba( α α + ba( α α +... + bm A( α αa( α = α( a + a α + a α... + a α αa( α = a α + a α... + a m α + a (p + p α... p α m + = α am p + ( a + am p α + ( a + am p α +... + ( am + am p α m = p m- α m- + p m- α m- +... + p α + p α + p -66- A(x a a a a 3 a 4 a 5 a m-6 a m-5 a m-4 a m-3 a m- a m- x A(x a a a a 3 a 4 a m-7 a m-6 a m-5 a m-4 a m-3 a m- p p p p 3 p 4 p 5 p m-6 p m-5 p m-4 p m-3 p m- p m- a m- a m- a m- a m- a m- a m- a m- a m- a m- a m- a m- a m- x A(x a a a a 3 a m-8 a m-7 a m-6 a m-5 a m-4 a m-3 a-multplyng Crcut ( 참고문헌 [] p p p p 3 p 4 p m-7 p m-6 p m-5 p m-4 p m-3 p m- a m- a m- a m- a m- a m- a m- a m- a m- a m- a m- a m- p p p p m- p p p p 3 p 4 p 5 p m-6 p m-5 p m-4 p m-3 p m- p m- a a a a m- a m- a m- a m- a m- a m- a m- a m- a m- a m- a m- a m- a m- p m- p m- p m- p m- p m- p m- p m- p m- p m- p m- p m- p m- a m- a m- a m- a m- a m- a m- a m- a m- a m- a m- a m- a m- -68-67- 68- -69- Tradtonal Seral Multpler Z(x = A(x = bx = = b (x A(x mod P(x = (...(((b A(x + b A(xx + b A(xx +... + b A(xx mod P(x Parallel Array Multpler on GF( 5 a a a a 3 a 4 P(x = x 5 + x + b 4 b b m- b m- x-multplyng crcut b 3 b a a a m- z z z m- b b p p p m- TSM TSM TSM m- z z z z 3 z 4-7- -7-
유한체나눗셈 P(x = x 93 5 + x + 9 94 9 93 x (x + = x + x = x x+ 9 x 5 = (x + x+ x 9 6 x + x + x 9 9 9 5 93 x x + x (x + ( = x x + 9 94 9 x x + x x 9 9 6 = x + x + x!!! Step. Fnd the nverse o B(x Step. Z(x = A(x/B(x = A(x B - (x mod P(x 9 6 x + x + x + x x + 89 87 x + x +...??? 9 6 x + x + x x 9 + x 89 89 6 x + x + x 89 87 x +x 87 6 x + x +... 유한체나눗셈방법 Projectve coordnate 나눗셈기가있는경우비효율적임 Table look-up method Table 이커질경우비효율적임 Usng Fermat s s theorem B m = B B m = B Usng Eucldean GCD algorthm Almost nverse, Etc. -7- -73- 유클리드기반유한체나눗셈기 ( Algorthm dvson (A(x,( B(x P := P(x; S := P(x; V : = ; /* degs = m */ := B(x; U : = A(x; /* assume degs = m */ delta := ; /* delta = degs-deg deg */ or := to m do r m = then begn := x ; U := ( (x U mod P delta += ; /* deg -= = */ else begn /* r = */ m s m = then begn S := S - ; V := ( (V - U mod P; end S := x S; /* deg S -= - */ delta = then begn /* degs < deg : dvson done */ <-> S; U <-> V; U := ( (x U mod P; ; delta := ; /* deg <-> degs */ else U := ( (U / x mod P; delta -= = end end end /* A(x B - (x = U */ end algorthm -74- 유클리드기반유한체나눗셈기 ( An mproved verson o exstng dvson algorthm usng extended Eucldan GCD algorthm Exstng dvson algorthm (by Brunner S, V,, U 라는임시레지스터를사용 S = P(x, V =, = B(x, U = A(x 의초기값사용 과 S의각각최상위비트를참조하여조건에따른알고리즘 m 회반복 최종적으로 U 레지스터에 A(x/B(x 의결과가남게됨 -75- Brunner 알고리즘의, S, U, V 블록의기능 Example( r m Control Sgnal s m - δ > - x xs x(s- S S xs egster U xu xv U/x x(v-u V V U V U Counter δ δ + δ + δ - δ + Fnte Feld GF( 3 Irreducble polynomal p=x 3 +x+ Generator g=( g =(, g =(, g 3 =(, g 4 =(, g 5 =(, g 6 =(, g 7 =( Ellptc Curve : y +xy=x 3 +g x +g 6 x(s- U/x V-U δ - -76- -77-
Example( Ellptc Curve : y +xy=x 3 +g x +g 6 Does P(g, g 6 le on the ellptc curve? Let sde : (g 6 +g 6 g = g +g 8 = g 7+5 +g 7+ = ( + ( = ( = g 6 ght sde : (g 3 +g (g +g 6 = g 6 +g 6 +g 6 = g 6 On the ellptc curve Does P(g 5, g le on the ellptc curve? Let sde : (g +g 5 g = g 4 +g 7 = ( + ( = ( = g 5 ght sde : (g 5 3 +g (g 5 +g 6 = g 5 +g +g 6 = g 7+7+ +g 7+5 +g 6 = ( + ( + ( = ( Not on the ellptc curve -78- Example(3 Ellptc Curve : y +xy=x 3 +g x +g 6 What s 4P P = (x( p, y p = (g, g 6? 4P = (P Use quadruplng s s = x p +y p /x p x p s 4p x 4p y 4p p = s +s+g 4p = x p +s++x p /x 4p = s 4p 4p +s 4p +g +g /x p 4p = x p +(s 4p +x 4p -79- Example(4 Dvson o g 6 /g = (/( s = x p +y p /x p g +g 6 /g = (+( = ( = g x p = s +s+g g +g +g = g s 4p = x p +s++x p /x p g +g +g 7 +(g /g = (+( = ( = g x 4p = s 4p +s 4p +g g +g +g = g y 4p = x p +(s 4p +x 4p g +(g +(g = g +g 3 g = (+( = ( = g 4P = (g, g = ((,( -8-3 4 5 6 B= *x = _*x = _- = *x = S P= _- = *x = _- = *x = _- = *x = _ U A= (*x mod P =_ =+= (/x mod P =_ =+= *x = /x = -= (*x mod P =_ =+= (/x mod P =_ =+= V -= = - = - = δ += -= = += -= = += -= = -8- Dvson o g 4 /g = (/( Summary 3 4 5 B= *x = *x = - = *x = _ S P= - = *x = *x = U A= (*x mod P =_ =+= (*x mod P =_ =+= (/x mod P =_ =+= (/x mod P =_ =+= - = *x = V - = δ += += -= = -= = += 정보사회와암호화 비밀키, 공개키암호시스템 DES, SEED, SA, ECC Hgh-speed cable modem, ATM, nternet, 전자상거래에적용 6 -_ = *x = _ /x = - = -= = -8- -83-