암호알고리즘 (INS301) 강의노트 01 암호알고리즘개요 한국기술교육대학교인터넷미디어공학부
교육목표 암호기술에대한개략적이해 암호기술용어 대칭암호알고리즘 vs. 비대칭암호알고리즘 전자서명 해쉬함수 암호해독과암호알고리즘의안전성 2/39
기본용어 정보통신용어표준 http://word.tta.or.kr/ 평문 (plaintext, cleartext) 암호문 (ciphertext) 암호화 (encryption, encipherment): 평문을암호문으로바꾸는과정. 비고. encrypt, encipher: 암호화하다. 복호화 (decryption, decipherment): 암호문을평문으로바꾸는과정. 비고. decrypt, decipher: 복호화하다. 암호화 복호화 평문 암호문 평문 3/39
기본용어 계속 암호기술 (cryptography): 메시지를안전하게유지하는기술과학문. 비고. 암호기술자 (cryptographer) 암호해독기술 (cryptoanalysis): 암호문으로부터평문을추정하는기술과학문. 비고. 암호해독자 (cryptoanalyst) 암호학 (cryptology): 암호기술 + 암호해독기술 비고. 암호학자 (cryptologist) 4/39
보안목적 비밀성 (confidentiality, secrecy, privacy): 인가된사용자들만데이터의내용을볼수있도록해주는서비스비밀을유지해야하는기간에따라처리하는방법이달라야한다 예 1.1) 암호키의길이 무결성 (integrity): 비인가된데이터의변경을발견할수있도록해주는서비스 변경의종류 : 삽입, 삭제, 교체 5/39
보안목적 계속 인증 (authentication): 식별 (identification)+ 검증 (verification) 주장된것을검증하는것 유형 메시지인증 : 무결성과같음 메시지원천지인증 : 메시지가송신된위치또는송신자를검증 정보보안에서는위치는보통중요하지않음 개체인증 (entity authentication): 주장된신원을검증 6/39
보안목적 계속 부인방지 (non-repudiation): 개체가지난행위나약속 (commitment) 을부인하지못하도록하는서비스송신부인방지 (Non-Repudiation of Origin, NRO) 전달부인방지 (Non-Repudiation of Delivery, NRD) 제출부인방지 (Non-Repudiation of Submission, NRS) 수신부인방지 (Non-Repudiation of Receipt, NRR) 서비스부인방지내용부인자제공자 NRO 메시지의송신송신자송신자 NRR 메시지의수신수신자수신자 NRS 메시지의제출메시지전달기관메시지전달기관 NRD 메시지의수신메시지전달기관메시지전달기관 ISO/IEC 13888 7/39
보안목적 계속 부인방지모델 송신자 NRO: 전송사실부인방지 수신자 NRR: 수신사실부인방지 제출자수신자중계자 NRS: 제출된사실부인방지 ( 중계자에의한부인 ) NRD: 중계된사실부인방지 ( 수신자에의한부인 ) 8/39
통신계층과암호기술 통신메시지의비밀성 / 무결성을보장하기위한암호기술적용과통신계층간에관계 단대단 (end-to-end) 통신망과독립적으로수행가능 (hop-by-hop) 트랙픽분석이가능하지않음 장점 기반구조를신뢰하지않아도됨 패킷단위로암호화가가능하므로 오류발생시해당패킷만재전송 단점 트래픽분석이가능 오류발생시전체메시지의재전송이필요함 암호알고리즘의특성상메시지의복호화가가능하지않음 통신망의각호스트 / 스위치에기능이포함되어있어야함 기반구조를신뢰해야함 ( 중간호스트 / 스위치는평문을보게됨 ) 반복적으로암호기술을적용하기때문에효율성이떨어짐 9/39
통신계층과암호기술 계속 암호화 단대단방식 홉바이홉방식 10/39
암호알고리즘 암호알고리즘 (cryptographic algorithm, cipher): 암호화와복호화과정에사용되는수학함수 ( 좁은의미 ) 암호기술에서사용되는모든알고리즘 ( 넓은의미 ) 현대암호화함수와복호화함수는모두키 (key) 를사용 표기법 E( M, K) = C, D( C, K) = M E ( M) = C, D ( C) = M K 암호키 (cryptographic key): 암호화 / 복호화에사용되는키 K { M} = C, { C} = M K 현대암호알고리즘의안전성은키에의존해야한다. 키대신에알고리즘의비밀성에의존할경우에는제한적알고리즘 (restricted algorithm) 이라한다. 1 K 11/39
암호알고리즘 계속 장점 단점 제한적알고리즘 해독하기가상대적으로더어렵다. 알고리즘을공유할수없다. 역공학 (reverse engineering) 의가능성이존재한다. 노출될경우에는알고리즘자체를변경해야한다 키의존알고리즘 키가노출되면키자체만변경하면된다. 알고리즘이공개되어있으므로허점의발견이용이하다. 알고리즘개선에사용가능 알고리즘이공개되어있으므로허점의발견이용이하다. 악의적인목적으로사용가능 12/39
암호시스템 다음 5개의투플을암호시스템 (cryptosystem) 또는암호계라한다. Π 가능한평문의유한집합. Μ 으로표현하기도함 Χ 가능한암호문의유한집합 Κ 키공간, 가능한암호키의유한집합 Ε: Π Χ 암호화함수 ( 전단사함수 ) Δ: Χ Π 복호화함수, p P, D( E( p)) = p 13/39
암호화 / 복호화함수 암호화 / 복호화함수는전단사함수 (bijection) 이어야한다. 전단사함수이면역함수가존재하며, 이때보통함수가암호화에사용되며, 그것의역함수가복호화에사용된다. 함수가아님 단사함수 (injection) 전사함수는아님 전사함수 (surjection) 단사함수가아님 전사함수가아님단사함수도아님 전단사함수 14/39
암호화 / 복호화함수 계속 예 1.2) P = { p, p, p }, C= { c, c, c } 1 2 3 1 2 3 3! 개의전단사함수존재 각함수마다고유키부여 : K = { k1, k2, k3, k4, k5, k6} 15/39
Kerckhoffs desiderata 암호시스템의요구사항 요구사항 1. 암호시스템은이론적으로안전하지않다면최소한실제적으로안전해야한다. ( 최소계산적안전성을제공해야함 ) 요구사항 2. 시스템의자세한내부사항의노출이시스템안전성에영향을주지않아야한다. ( 제한적알고리즘이면곤란 ) 요구사항 3. 암호키는기억가능해야하며, 쉽게변경할수있어야한다. 요구사항 4. 암호문을통신을통해전달가능해야한다. 요구사항 5. 암호장치는이동가능해야하며, 홀로사용할수있어야한다. 요구사항 6. 암호시스템을사용하는방법이쉬워야한다. 16/39
암호알고리즘의분류 결정적 (deterministic) vs. 확률적 (probabilistic) 결정적암호알고리즘 : 암호키와메시지가같으면항상같은암호문으로암호화되는암호알고리즘 확률적암호알고리즘 : 암호키와메시지가같아도항상다른암호문으로암호화되는암호알고리즘 대칭 (symmetric) vs. 비대칭 (asymetric) 대칭암호알고리즘은암호화할때사용되는암호키와복호화할때사용되는암호키가같은암호알고리즘 비대칭암호알고리즘은암호화할때사용되는암호키와복호화할때사용되는암호키가다른암호알고리즘 17/39
키용어 암호키 (cryptographic key) 암호알고리즘에사용되는모든종류의키 암호화키 (encryption key) 복호화키 (decryption key) 암호화과정에사용되는암호키 복호화과정에사용되는암호키 비밀키 (secret key) 대칭암호알고리즘에사용되는암호키 개인키 (private key) 공개키 (public key) 세션키 (session key) 비대칭암호알고리즘에서각개인이비밀로하는암호키 비대칭암호알고리즘에서각개인이공개하는암호키 특정통신세션에서만사용되는일회성비밀키 18/39
대칭암호알고리즘 대칭암호알고리즘 (symmetric, conventional, secret key algorithm): 암호화키 = 복호화키비밀키암호알고리즘암호화하여전송하는사람과그것을수신하는사람은같은키를공유하고있어야함 ( 어떻게공유?) 종류스트림 (stream) 암호방식 : 평문의각비트 (or 바이트 ) 를하나씩암호화하는방식블록 (block) 암호방식 : 평문을일정한블록크기로나누어, 각블록을암호화하는방식 19/39
대칭암호알고리즘의사용용도 공개채널로전달되는메시지에대한비밀성보장 송신자와수신자가공유하고있는비밀키로메시지를암호화하여교환함으로써제 3 자가도청할수없도록만든다. 기억장치에저장되는데이터에대한비밀성보장 다른사용자가저장된데이터를열람할수없도록데이터를암호화하여저장할수있다. 개체인증 Alice 와 Bob 이비밀키 K AB 를공유하고있을경우다음과같은프로토콜을통해인증할수있다. Bob N B {N B }.K AB Alice Bob 은응답한자가 Alice 임을확신할수있음메시지의최신성검증가능 N B : nonce(number used just ONCE) {N B }.K AB : N B 를 K AB 로암호화 20/39
비대칭암호알고리즘 비대칭암호알고리즘 (asymmetric, public key algorithm): 암호화키 복호화키두개의키를공개키 (public key) 와개인키 (private key) 라함한사용자는자신의공개키는공개하고 ( 누구나사용할수있음 ), 개인키는비밀스럽게유지한다. 다른말로공개키암호알고리즘이라함 1975년 Diffie와 Hellman이고안대칭암호알고리즘에비해역사가상대적으로짧음대칭암호알고리즘과달리사전에공유된키가없어도메시지를암호화하여교환할수있다. 공개키의인증이가장중요비대칭암호알고리즘은대칭암호알고리즘과같은용도로사용가능하지만성능때문에보통메시지자체를암호화하는데사용되지않는다. 반면에전자서명알고리즘을쉽게구현할수있다. 21/39
비밀키 VS. 공개키암호알고리즘 {M}.KK {M}.+K AB A Bob K AB Alice K AB Bob Alice K B, +K B, +K A K A, +K a, +K b +K A : A의공개키 +K B : B 의공개키 비밀키암호알고리즘 공개키암호알고리즘 키관계암호화키 = 복호화키암호화키 복호화키 키길이짧다상대적으로길다 기본연산비트조작연산수학연산 소프트웨어구현성능 ( ) 성능 ( ) 대표알고리즘 DES, AES RSA 22/39
법강화를위한키위탁 정부는비밀통신을감청할능력을유지하고싶다. 방법 1. 암호화사용금지 방법 2. 암호알고리즘을해독할수있는능력보유 방법 3. 키위탁 (key escrow): 사용자들이사용하는모든키를강제로보관주로세번째방법을사용 세번째방법을사용하기위한요구사항 정부의권한남용을방지하기위한대책필요 키를여러부분으로나누어다른기관들이보유한다음에이들기관들중일정수이상의기관이동의하여야키를다시만들수있도록함 (threshold technique) 키위탁은키분실하였을때키를복구 (recovery) 하기위해서도유용하게사용될수있다. 23/39
전자서명의요구사항 인증 (authentic): 누가서명하였는지확인이가능해야함 각서명자마다서명이독특해야한다. 위조불가 (unforgeable): 위조가불가능해야함 재사용불가 (not reusable): 서명을다시사용할수없어야함 (cut-and-paste) paste). 서명은메시지에의존해야한다. 전체의재사용을방지하기위해서는서명시간이포함되어야한다. 변경불가 (unalterable): 서명된문서의내용을변경할수없어야함 부인방지 (non-repudiation): 나중에부인할수없어야한다. M M 인증요구사항 M M' 재사용불가요구사항변경불가요구사항 Sig A (M) Sig B (M) Sig A (M) Sig A (M') 24/39
일반서명과전자서명의차이점 전자서명은수학적으로서명자를검증할수있다. 일반서명은원서명과눈으로대조하여검증한다. 위조될확률이높으므로이측면에서는전자서명이보다안전하다. 일반서명은문서위에하지만전자서명은보통문서와별도로존재한다. 하지만전자서명은여전히문서에의존해야한다. 일반서명은서명마다동일한형태를지니지만전자서명은서명하는문서마다다른형태를지닌다. 전자서명은원본과복사본을구분하기가어렵다. 25/39
전자서명 계속 전자서명의구성요소 M: 서명할수있는메시지의유한집합 S: 고정된길이의서명의유한집합 σ((m, K) S): 서명을생성하기위해사용되는함수 υ((m, s, +K) {true, false}): 서명을검증하기위해사용되는함수 K: 서명키 (signature key, signing g key), +K: 확인키 (verification key, verifying key) 요구사항 s S 가 m M 에대한유효한서명이되기위한필요충분조건은 υ(m, s, +K) = true이다. K를모르는사람이 υ(m, (, s, +K) = true인임의의 m M과 s S를찾는것은계산적으로어렵다. 26/39
해쉬함수 해쉬함수 (hash function): 임의의길이에이진문자열을고정된길이의이진문자열 ( 해쉬값, 메시지다이제스트, 메시지지문 ) 로매핑하여주는함수요구사항압축계산의용이성 : x가주어지면 H(x) 는계산하기쉬워야함 일방향성 (one-wayness): 입력을모르는해쉬값 y가주어졌을때, H(x') = y를만족하는 x' 를찾는것은계산적으로어렵다. (OWHF) 약한충돌회피성 (weak collision-resistance): x가주어졌을때 H(x') ) = H(x) 인 x'( x) 을찾는것은계산적으로어렵다. 강한충돌회피성 (strong collision-resistance): H(x') = H(x) 인서로다른임의의두입력 x와 x' 을찾는것은계산적으로어렵다. (CRHF) 27/39
해쉬함수 계속 일방향성은이주어졌을때을찾는문제 약한충돌회피성은이주어졌을때을찾는문제 강한충돌회피성은와같은쌍들을찾는문제 28/39
해쉬함수 계속 해쉬함수의용도 전자서명 : 서명크기와비용을줄이기위해전체메시지대신에메시지의해쉬값에서명한다. 무결성 패스워드해싱 해쉬함수는보통비밀키를사용하지않는다. 단순히메시지의변경여부를판단하기위해사용할경우에는조작탐지코드 (MDC, Modification/Manipulation Detection Code) 라한다. 반대로비밀키를사용하게되면데이터원천지인증과무결성을동시에제공할수있으며, 이때에는메시지인증코드 (MAC, Message Authentication Code) 라한다. 29/39
암호해독 보안을위협하는자 공격자 : attacker, intruder, penetrator, interloper, adversary, enemy, eavesdroper, interceptor, tapper 암호해독 : 키를모르는상태에서암호문으로부터평문을얻어내는행위 성공적인암호해독 : 키또는평문을얻은것 암호해독외에다른방법으로키가알려진것을노출 (compromise) 되었다고한다. 30/39
공격 암호프로토콜에대한공격 수동공격 (passive attack): 프로토콜의진행을방해하지않고공격하는것을말함. 데이터의비밀성에대한위협 또는트래픽분석이목적일수있음 수동공격을하는자를보통도청자 (eavesdropper) 라한다. 능동공격 (active attack): 프로토콜의진행에개입 ( 메시지삭제 ( 차단 ), 삽입, 변경, 재전송 ) 하여공격하는것을말함 데이터의비밀성뿐만아니라인증, 무결성에대한위협 31/39
암호해독공격의분류 전사공격 (brute-force attack): 가능한모든키를검사하는방법 (exhaustive key search) 암호해독공격은아님 암호해독공격의분류 암호문단독공격 (ciphertext-only attack) 기지평문공격 (known-plaintext attack) 선택평문공격 (chosen-plaintext attack) 적응적선택평문공격 (adaptive chosen-plaintext attack) 선택암호문공격 (chosen-ciphertext attack) 이들공격은실제이루어질수도있는공격이지만암호알고리즘이얼마나안전한지검사하기위한가상의공격으로간주하는것이더올바른접근방법이다. 32/39
암호해독공격의분류 계속 암호문단독공격 (ciphertext-only attack) 알고있는것 목표 C1, C2, K, Cn 1) 2) P1, P2, K, Pn K C P 3) 알고리즘 : n+ 1 n+ 1 키를발견하지는못하였지만키없이암호문의역을취할수있는알고리즘을발견한경우 모두같은키, 같은알고리즘으로암호화된암호문 33/39
암호해독공격의분류 계속 기지평문공격 (known-plaintext attack) ( P, C ),( P, C ), K,( P, C ) 공격자가선택할수없고 알고있는것 1 1 2 2 목표 1) K 2) 알고리즘 : C P n n + 1 n + 1 선택평문공격 (chosen-plaintext attack) ( P, C ),( P, C ), K,( P, C ) 알고있는것공격자가 P1, P2, K, Pn 를선택함 ( 공격하기전 ) 목표 1) 1 1 2 2 K C 2) 알고리즘 : n+ 1 n+ 1 n n n 우연히알게된암호문 / 평문쌍 암호화될평문을해독공격자가선택할수있으면키에대해보다많은정보를줄수있는평문을선택할수있다. P 34/39
암호해독공격의분류 계속 적응적선택평문공격 (adaptive chosen-plaintext attack) 선택평문공격은공격자가 ( 평문, 암호문 ) 쌍들을얻기전에해독에사용할모든평문을선택하는경우를말한다. 적응적선택평문공격은얻은암호문을바탕으로공격하는동안새로운평문에대한암호문을얻을수있다. 선택암호문공격 (chosen-ciphertext attack) ( P, C ),( P, C ), K,( P, C ) 알고있는것공격자가 C1, C2, K, Cn 를선택함 ( 공격하기전 ) 목표 1) 1 1 2 2 K 2) 알고리즘 : n+ 1 n+ 1 주로공개키알고리즘을공격할때사용 C P n n 35/39
알고리즘에대한공격결과 완전성공 (total break): 암호키를발견 광역성공 (global deduction): 암호키를발견하지못하였지만복호화할수있는알고리즘을발견 인스턴스성공 (instance deduction): 어떤한암호문으로부터그것의평문을얻어냄 정보추출 (information deduction): 암호문으로부터평문의일부나암호키와관련된정보를얻어냄 36/39
공격의복잡성척도 데이터복잡성 (data complexity): 공격이성공하기위해필요한데이터의양처리복잡성 (processing complexity): 공격이성공하기위해필요한시간 (work factor) 저장공간요구사항 (storage requirement): 공격하기위해필요한메모리공간 37/39
암호알고리즘의안전성 암호알고리즘을해독하기위해요구되는노력에의해측정 계산적안전성 (computationally secure): 암호알고리즘을해독하기위한지금까지알려진가장우수한공격방법을사용하더라도불합리하게많은컴퓨터시간을요구할경우공격방법이기준증명가능안전성 (provably secure): 어렵다고알려진문제와등가일경우 예 1.3) 인수분해문제 안전성에대한절대적증명은아님 무조건적 ( 절대적 ) 안전성 (unconditionally secure): 무한한컴퓨터자원을가져도암호알고리즘을해독할수없는경우 38/39
암호알고리즘의안전성 계속 의미론적안전성 (semantic security): 암호문이주어졌을때효율적으로계산할수있는모든것을암호문이없어도계산할수있어야한다. 구별불가안전성 (indistinguishability): 두개의메시지중하나를암호화한암호문이주어졌을때, 공격자가어떤평문을암호화한것인지맞출수있는확률이 50% 보다높지않아야한다. NM 특성 (Non-Malleability): 암호문에대응되는평문을알지못하는경우이암호문을의미있는다른암호문을변경하는것이가능하지않으면암호알고리즘은 NM 특성을제공한다고한다. NM 특성은의미론적안전성보다강한특성이다. 39/39