암호알고리즘 (INS301 강의노트 10 전자서명 한국기술교육대학교인터넷미디어공학부 1
교육목표 전자서명개요 RS 전자서명 ElGamal 전자서명 DSS Nber-Rueel 전자서명 KCDS 일회용전자서명 2/40
전자서명의요구사항 인증 (authentic: 누가서명하였는지확인이가능해야함 각서명자마다서명이독특해야한다. 위조불가 (unforeable: 위조가불가능해야함 재사용불가 (not reusable: 서명을다시사용할수없어야함 (cut-and-aste aste. 서명은메시지에의존해야한다. 전체의재사용을방지하기위해서는서명시간이포함되어야한다. 변경불가 (unalterable: 서명된문서의내용을변경할수없어야함 부인방지 (non-reudiation: 나중에부인할수없어야한다. M M 인증요구사항 M M' 재사용불가요구사항변경불가요구사항 Si (M Si B (M Si (M Si (M' 3/40
일반서명과전자서명의차이점 전자서명은수학적으로서명자를검증할수있다. 일반서명은원서명과눈으로대조하여검증한다. 위조될확률이높으므로이측면에서는전자서명이보다안전하다. 일반서명은문서위에하지만전자서명은보통문서와별도로존재한다. 하지만전자서명은여전히문서에의존해야한다. 일반서명은서명마다동일한형태를지니지만전자서명은서명하는문서마다다른형태를지닌다. 전자서명은원본과복사본을구분하기가어렵다. 4/40
문제점전자서명 Electronic sinature Diital Sinature Electronic Sinature Diital Sinature 개컴퓨터이미지공개키암호방식이용 30 81 89 02 81 81 00 d4 47 37 78 5c b4 21 념e9 66 49 6f 7e ce a7 91 70 7a fc 36 24 ba 36 54 d8 55 cc 72 f9 be1 85 4c 56 6e c7 48 5d 25 9f e1 e5 d2 a6 0 59 be d1 c6 1d f6 24 51 b8 d3 1f b6 38 49 02 03 01 00 0146 395 39 재사용가능 5/40
공개키암호방식 공개키암호방식 공개키암호방식구조. K e K eb K ec K ed K ef 공개키저장소 K eb K db 가입자 가입자 B 암호문 C 암호화 복호화 6/40
공개키암호와전자서명 공개키 (Public Ke 개인키 (Private Ke 공개키암호암호화키복호화키 전자서명확인키 서명검증키서명키 서명생성키 7/40
전자서명방식의종류 직접서명방식 (direct diital sinature: 서명자가홀로서명알고리즘을수행하여서명하는방식문제점 : 서명키의분실 / 도난서명자가직접서명시간을서명에포함할경우에는서명키를획득한공격자의부정을증명할방법이없다. 중재서명방식 (arbitrated diital sinature: 중재자와프로토콜을수행하여서명하는방식중재자는서명의증인역할을하게된다. 서명자가시간에대한부정을할수없다. User: U M, Si U (H(M T U rbiter: Si (T Si U (H(M T U 8/40
공개키방식과전자서명 lice 에게 Bob 은메시지를비밀스럽게전달하고싶다. {M}.+K +K : 의공개키 +K B : B의공개키 누구나 lice의공개키만있으면 Bob lice 이와같은방식을메시지의 K B, +K B, +K K, +K, +K B 기밀성이보장되도록 lice에게메시지를전달할수있다. lice 는 Bob 에게자신을인증하고싶다. 오직 lice만복호화할수있음 Bob K B B, +K B, +K {M}. K lice K, +K, +K B 누구나 lice의공개키만있으면이메시지는 lice 가생성한메시지임을확인할수있다. 오직 lice만생성할수있음 전자서명역할을할수있음 두가지방식에서모두중요한것은공개키의인증이다. 9/40
전자서명알고리즘의분류 메시지복구여부에따른분류 서명으로부터메시지를복구할수있는서명알고리즘 (DSS with recover 검증에원메시지가필요한서명알고리즘 (DSS with aendix 결정 vs. 확률서명알고리즘 결정 (deterministic 서명알고리즘 : 메시지가같으면항상결과서명이같은알고리즘확률 (robabilistic, randomized 서명알고리즘 : 메시지가같아도서명할때마다그결과가달라지는알고리즘 10/40
인증서의필요성 전자서명은보통공개키암호알고리즘을사용하며, 이때개인키가서명키가되고, 공개키가확인키가된다. 전자서명된메시지를인증할때가장중요한것은확인키가실제로주장된서명자의확인키인지확신할수있어야한다. 이것의해결책으로가장널리사용되는것이인증서 (certificate 이다. 인증서는신뢰할수있는기관에서발행한보증서로서, 공개키와그것의소유자를바인딩하여주는전자문서이다. 보통신뢰할수있는기관의서명키로공개키와그것의소유자정보를서명하여만들어진다. 예 10.1 Si C (H(+K 소유자 유효기간 인증서를발급하는기관을인증기관 (C, Certification uthorit 이라한다. 11/40
금융결국증권무역국전국정인증보통신산소공인증기관 (ccredited C 우리나라인증체계 한국정보보호진흥원 (RootC -전자서명인증관리센터한제원전한자한국정한보인증전자서명인증관리센터 : htt://www.kisa.or.kr/kisa/kcac/js/kcac.js 12/40
전자서명에대한공격결과 공격의목표는서명을위조하는것이다. 공격결과의분류 완전파괴 (total break: 공격자가서명자의서명키를계산한경우 완전위조 (universal forer: 서명자의서명알고리즘과등가인또다른효율적인서명알고리즘을찾은경우 선택위조 (selective forer: 특정한메시지또는특정한종류의메시지에대해서는서명위조가가능한경우존재위조 (existential forer: 최소한하나의메시지에대한서명을위조한경우로서, 공격자가위조가능한메시지를선택할수없는경우 13/40
전자서명에대한공격의종류 키단독공격 (ke-onl attack 메시지공격 (messae attack 알려진메시지공격 (known-messae attack 선택메시지공격 (chosen-messae attack 적응적선택메시지공격 (adative chosen-messae attack: 가장안전한전자서명알고리즘이란적응적선택메시지공격에대해존재위조가계산적으로어렵다고증명된알고리즘을말한다. 14/40
RS 단계 1. 두개의소수와 를선택 단계 2. n 를계산 단계 3. φ(n ( 1( 1 를계산 단계 4. cd(k e, φ(n 1인 K e 를선택 단계 5. K e K d 1 ( φ(n 인 K d 를선택 공개키 : (n, K e, 개인키 : (n, K d 키쌍을구한다음에는 와 는더이상필요가없다. 15/40
RS 암호화방식 RS 암호방식구성 암호화 C M Ke n 복호화 M C Kd n 16/40
RS 전자서명 서명자 공개목록검증자 B e, n n cd( e, φ ( n 1 e d M : 서명문 H h( M S H 1φ( n d n M, S H ' H h( M S e n H H ' 확인 17/40
RS 전자서명 RS 를이용한전자서명예 5, 11 인 RS 암호방식을이용한전자서명방식을구성해보자. 서명문 M5로해쉬함수를사용하지않는다. 즉 HM5로간주함 서명자 공개목록검증자 B e 7, n 55 n M 5 서명문 서명 M 5 M ' S e 15 7 n 55 S H 5 d 5 23 n 55 M5, S15 555 M M ' 확인 1555 18/40
ElGamal 공개키암호알고리즘 이산대수문제 x : 원시원소 : 소수 Ex m14의원시원소는? φ( 14 (2 1(7 1 6 개의기약잉여계존재 * {1, 3, 5, 9, 11, 13} 정수 1 3 5 9 11 13 위수 1 6 6 3 3 2 Z 14 b r 1 m 위수 b φ ( m 1 m 원시원소 19/40
ElGamal 공개키암호알고리즘 계속 이산대수문제예 Ζ 23 20/40
ElGamal 공개키암호알고리즘 계속 이산대수문제예제계속 - 원시원소계산 φ( 1 φ(22 cd( i,22 1 i 1, 3, 5, 7, 9, 13, 15, 17, 19, 21, 5 1 5 23, 5 3 10 23, 5 5 20 23, 5 7 17 23, 5 9 11 23, 5 13 21 23, 5 15 19 23, 5 17 15 23, 5 19 7 23, 5 21 14 23 21/40
ElGamal 공개키암호알고리즘 계속암호방식암호화 ( Z 소수 ( : ( K Z r X B r B R b 소수 2 1 : ( M KM C C r 평문 2 1 2, ( C C C 22 22/40 /40
ElGamal 공개키암호알고리즘 계속 암호방식 복호화 K ( r X B C X 1 B M C 2 / K 23/40
ElGamal 전자서명 서명자 공개목록검증자 B,, k R Z X 1 R k M : 서명문 M, S, R R R S M S ( M X R k 1 1 확인 24/40
ElGamal 전자서명의안전성 서명검증과정 25/40
ElGamal 전자서명 ElGamal 전자서명예 P23, 5, X 9일때 Elamal 전자서명을구성해보자. 서명문은 M10이다. 서명자 공개목록검증자 B 11, 23, 5 5 9 23 11 23 k 7 k 1 R 5 R Z 22 19 22 7 23 17 23 M :10 S (10 9 17 19 22 M10, S11, R17 11 R 17 R S 17 11 M 5 10 확인 23 11 22 26/40
전자서명표준 전자서명표준 (DSS:Diital Sinature Standard 미국의전자서명표준으로 ElGamal 전자서명개량한방식 FIPS-186 등록, 1994년표준으로체택 서명자 공개목록검증자 B,,, X 1 k R Z R k M : 서명문 H h( M M, S, R H ' h ( M R 확인 S 1R S 1H ' 1 S k ( X R + H 27/40
전자서명표준 검증과정 28/40
전자서명표준 전자서명표준예 23, X7, 6, 11로전자서명표준을구성해보자. 서명문은 M5(H5 로해쉬함수는사용하지않는다. 서명자 공개목록검증자 B 3, 23, 11, 6 6 7 23 3 23 k 2 R 6 k 2 R Z 11 2311 2 2311 1 6 11 M 5 S 6(2 7 + 5 11 4 11 M5, S4, R2 1 S R 2 3 311 S 1R 3 2 6 3 5 확인 S 1H 2311 29/40
Nber-Rueel 의전자서명 ElGamal 전자서명방식과유사한방식 계산량을개선시킨방식 서명자 공개목록검증자 B,,, k Z X 1 R 1 H ' h ( M S R H ' M, S, R H h ( M 확인 k R H S k RX R 30/40
Nber-Rueel 의전자서명 Nber-Rueel 서명검증과정 31/40
Nber-Rueel 의전자서명 Nber-Rueel 서명방식예 23, X 7, 6, 11 로전자서명방식을구성해보자. 서명문 M6 으로해쉬함수는사용하지않는다. 서명자 공개목록검증자 B 6 7 23 3, 11, 23, 6 3 23 k 2 M 6 R Z R 6 6 2 2311 9 2311 S 2 7 911 511 M6, S5, R9 R H S R 6 6 5 R 3 9 2311 6 2 18 2311 9 2311 확인 32/40
KCDS(Korea Certificate-based DS 전자상거래등에서사용되는표준화된전자서명은한집단, 한그룹내 에서서명효율성높임 국내국가표준전자서명방식필요 한국정보보호학회표준안제안 1996 년 ElGamal 전자서명방식을개선한방식의 KCDS 완성 안전성평가후 1998 년국가표준으로채택 2000 년개정안발표 33/40
KCDS(Korea Certificate-based DS 시스템파라미터이고소수소수, ( 2 2 1, : (0 256 1024, ( 2 2, : 1 1 r i i < < + < < β α α β β α α 이고소수 3 (0 32 160, ( 2 2 1, : j j + < < β β 의비밀키사용자상의원소원소상의 1, : Z Z 의공개키사용자의비밀키사용자상의원소, :, : 1 Z x x 비트이하인해쉬함수출력이 : h( 34 34/40 /40
KCDS(Korea Certificate-based DS 서명자 공개목록검증자 B X 1,,, k 1 난수 ( ' 2 M Z h H Z l M S R W h R W k ( ' ' ' ( ' ( ' ' ' W H R E M Z h H E s M, S, R M Z h H Z l ( 2 확인 ' ' ( R W h W E k X S H R E ( ( 확인 35 35/40 /40
KCDS(Korea Certificate-based DS KCDS 서명검증과정 E S X E S ( 1 E X X E k ( ( ( 1 k 36 36/40 /40
KCDS(Korea Certificate-based DS KCDS 전자서명예 서명자 공개목록 검증자 B X 12, X 14 W 14 2 k 13 R 13 1 2 47 8 47 Z 23 47 21 47 8, 23, 47, 14 M 16 E (21 16 23 00101 23 W R, Z Y, H M, M E ( R H (21 16 23 16 M16, S4, R21 5 23 R 8 4 14 5 47 00101 23 7 3 47 S 5 23 X ( k E 12(13 5 23 21 4 23 37/40
일회용전자서명 일방향함수를이용한일회용서명 검증반복가능 f : X Y x ij X 비밀서명정보 ij Y 공개검증정보 38/40
일회용전자서명 Lamort 일회용전자서명 서명자 공개목록 검증자 B,, 10, 11, 20, 21K, k 0, k1 ij x ij 비밀서명정보 x 10 x11, x20, x21k, x k 0, x k, 1 서명문 S' S 1 S 2 M : m m m KS S x, j ij ij k 1 m i 2 3 Km k M, S ij Si 확인 39/40
일회용전자서명 Lamort 일회용전자서명예서명자 공개목록검증자 B 21 14, 17, 11, 5, 22, 2, 19, 10, 23, 41 40 31 30 21 20 11 10 19 7, 17, 3, 15 11, 8, 5, 41 40 31 30 21 20 11 10 x x x x x x x x 5 22, 2, 19, 23 10 19 7, 17, 3, 21 20 11 10 41 40 31 30 x x x x x ij ij 23 10 5 23 10 2 15 21 8 11 M1101, S8,15,3,19 1101 21 14, 17, 11, 5 22, 2, 19, 41 40 31 30 21 20 11 10 M 23 10 21 23 10 11 19 31 3 30 19 3, 15, 8, S 40 40/40 /40