2011-1 학기현대암호학 제 12 장난수 박종혁 Tel: 970-6702 Email: jhpark1@seoultech.ac.kr
12.1 주요내용 난수가사용되는암호기술 난수의성질 의사난수생성기 구체적인의사난수생성기 의사난수생성기에대한공격
12.2 난수가사용되는암호기술 암호알고리즘을조정하는정보조각 평문을암호문으로전환 암호문을복호화하는역할 디지털서명구조 키를이용한해시함수 인증
12.2.1 난수의용도 암호학적으로안전한의사난수생성기 (Cryptographically Secure Pseudo-Random Number Generator:CSPRNG) 는암호학에서사용할수있을정도로충분한난수성질을갖고있는난수를생성하는의사난수생성기 (PRNG) 를말한다.
난수가필요한곳 대칭키의생성 대칭암호나메시지인증코드에서사용한다. 공개키쌍의생성 공개키암호나디지털서명에서사용한다. 초기화벡터 (IV) 의생성 블록암호모드인 CBC, CFB, OFB 에서각각사용한다. 난스 (nonce) 의생성 재전송공격방지나블록암호의 CTR 모드등에서사용한다. 솔트의생성 패스워드를기초로한암호화 (PBE) 등에서사용한다. 일회용패드 패딩에사용되는열을생성하는데사용한다.
결국난수를사용하는목적 간파당하지않도록하기위한것 예측불가능성 간파당하지않는다는것
12.3 난수의성질 난수를정확하게정의하는것은곤란하다 여기에서는암호기술에관련된성질에한정해서이야기한다.
12.3.1 난수의성질 무작위성 통계적인편중이없이엉터리수열로되어있는성질. 예측불가능성 과거의수열로부터다음수를예측할수없다는성질. 재현불가능성 같은수열을재현할수없다는성질. 재현하기위해서는수열그자체를보존해두는수밖에없다.
난수의성질
난수의분류
12.3.2 무작위성 간단히말하면 엉터리 로보이는성질 의사난수열의통계적인성질을조사해서치우침이없다면, 그의사난수열은무작위하다고여겨진다. 무작위성만을갖는의사난수는 약한의사난수 라고한다.
12.3.3 예측불가능성 과거에출력한의사난수열이공격자에게알려져도다음에출력하는의사난수를공격자는알아맞힐수없다는성질 예측불가능성을갖는의사난수를 강한의사난수 라한다.
12.3.4 재현불가능성 어느난수열과동일한수열을재현할수없다고하는성질 소프트웨어만으로는재현불가능성을갖는난수열을만들수없다 소프트웨어가생성하는수열은언젠가는반복이된다. 다양한하드웨어로부터얻어진정보를기초로생성한수열은재현불가능성을갖는난수열이된다 재현불가능성을갖는난수를 진정한난수 라고한다
12.3.5 무작위성과예측불가능성 비교 결정론의우주론적가정하에서본다면우주에는무작위성이란존재하지않으며오직예측불가능성만있다. 수학적으로정의된수열을살펴보면랜덤한수열의한덩어리가반복되는특성을가지고있게된다. 그러나우리가설명할수있는메커니즘에의해생성되기때문에이와같은난수를의사난수라고부른다. 이러한메커니즘을모르는사람들일볼때에의사난수는예측불가능한것으로보인다.
12.4 의사난수생성기 하드웨어로난수를생성할경우, 열이나음의변화등의예측이나재현이사실상불가능한자연현상을센서로감지해서그결과를기초로난수열을생성한다. 이런하드웨어를난수생성기 (random number generator; RNG) 라부른다.
의사난수생성기 (pseudo random number generator; PRNG) 난수를생성하는소프트웨어 소프트웨어만으로는진정한난수를생성할수가없기때문에, 의사 난수생성기라부른다
12.4.1 의사난수생성기의구조 의사난수생성기는 내부상태 를가지며, 외부에서주어진 종자 (Seed) 를기초로의사난수열을생성한다
의사난수생성기의구조
의사난수생성기의내부상태 의사난수생성기가관리하고있는메모리값 의사난수생성기는메모리의값 ( 내부상태 ) 을기초로해서계산을수행하고, 그계산결과를의사난수로서출력한다. 그리고다음의사난수의요구에대비해서, 자신의내부상태를변화시킨다
의사난수생성기의 종자 의사난수생성기로의사난수를생성하기위해서는의사난수의종자 (seed) 라불리는정보가필요하다. 의사난수의종자는의사난수생성기의내부상태를초기화하기위해이용된다. 의사난수의 종자 는랜덤한비트열이다. 종자 에의해자신만이사용할의사난수열을생성할수있다. 의사난수생성기는모두가공유하지만, 종자 는자신만의비밀로하지않으면안된다.
암호키와의사난수의종자
12.5 구체적인의사난수생성기 엉터리방법 선형합동법 일방향해시함수를사용하는방법 암호를사용하는방법 ANSI X9.17
12.5.1 엉터리방법 복잡하게만한알고리즘을사용해서수의열을생성시키면, 대부분의경우는짧은주기 ( 짧은수열의반복 ) 에빠지게된다. 암호기술에서사용하는난수는예측불가능성을가질필요가있으므로주기가짧아서는안된다.
12.5.2 선형합동법 가장많이사용되는의사난수생성기 무작위성을갖는의사난수열을간단히생성할수있다. 예측불가능성 은갖지못한다. 암호기술에사용할수는없다
선형합동법에의한의사난수생성기
12.5.3 일방향해시함수를사용하 는방법 일방향해시함수 ( 예를들면 SHA-1) 를사용해서예측불가능성을갖는의사난수열 ( 강한의사난수 ) 을생성하는의사난수생성기를만들수있다
의사난수생성기의절차 (1) 의사난수의종자를사용해서내부상태 ( 카운터 ) 를초기화한다. (2) 일방향해시함수를사용해서카운터의해시값을얻는다. (3) 그해시값을의사난수로서출력한다. (4) 카운터를 1 증가시킨다. (5) 필요한만큼의의사난수가얻어질때까지 (2)~(4) 를반복한다.
일방향해시함수를사용해서의사 난수생성기를만든다
12.5.4 암호를사용하는방법 암호를사용해서 강한의사난수 를생성하는의사난수생성기를만들수있다 ( 그림 12-7) AES 와같은대칭암호나 RSA 와같은공개키암호중어느것을사용해도상관없다.
의사난수생성기의절차 (1) 내부상태 ( 카운터 ) 를초기화한다. (2) 키를사용해서카운터를암호화한다. (3) 그암호문을의사난수로서출력한다. (4) 카운터를 1 증가시킨다. (5) 필요한만큼의의사난수가얻어질때까지 (2)~(4) 를반복한다.
암호를사용해서의사난수생성기를 만든다
12.5.5 ANSI X9.17
ANSI X9.17 의방법으로의사난수생성기를만든다
의사난수생성기의절차 (1) 내부상태를초기화한다. (2) 현재시각을암호화해서 뒤섞기역 을만든다. (3) 내부상태와뒤섞기역의 XOR 을취한다. (4) 절차 (3) 의결과를암호화한다. (5) 절차 (4) 의결과를의사난수로서출력한다. (6) 절차 (4) 의출력과뒤섞기역의 XOR 을취한다. (7) 절차 (6) 의결과를암호화한다. (8) 절차 (7) 의결과를새로운내부상태로한다. (9) 절차 (2)~(8) 을필요한만큼의의사난수가얻어질때까지반복한다.
12.6 난수와의사난수의차이점 의사난수란정확히말해서난수처럼보이는수이지만실제로는정확한의미로서난수가아닌수이다. 의사난수생성기를통해생성되는난수는통계적으로는무작위성을가지고있지만입력되는자료가같으면출력되는결과도항상같게되는인과관계가분명한존재한다.
의사난수의장점 생성하기쉽다 동일한난수를생성하고싶을경우에입력값만동일하게주게되면된다. 반복적으로사용할수있고소프트웨어를검사하거나수정할때매우유용하다.
12.6.1 난수의역사 1927 년영국의케임브리지대학출판사에서는 Leonard H.C Tippet 가개발한 41,600 개의숫자로이루어진난수표를발표 1947 년에는 RAND 회사에서룰렛바퀴를모사한전자식기계를이용하여난수를생성하였다. 1955 년에편차가 100,000 인정규분포를갖는 Million Random Digits 를출판하였다. John von Neumann 은컴퓨터에기초한난수생성의창시자 1951 년에 Derrick Henry Lehmer 가선형합동법
12.6.2 난수와암호학 암호학적인면에서살펴보면의사난수 ( 하드웨어적으로만들어졌건소프트웨어적으로만들어졌건간에 ) 를사용하는것이사실은안전하지못하다. 암호시스템을설계하는사람과사용자는모두다난수의무작위성을매우신중하게다루어야한다. 의사난수의패턴을찾아내는것이옛날보다훨씬쉬워졌다는것이다. 결국난수를더욱더신중하게선택해야한다는것이우리가암호학을배우면서깨우쳐야할중요한사실이다.
12.7 의사난수생성기에대한공격 암호에비하면의사난수생성기는두드러지지않는존재가아니다 하지만의사난수생성기도공격당한다 그러나의사난수생성기는 키를만든다 라고하는중요한역할을하고있기때문에, 빈번히공격의대상이된다.
12.7.1 종자에대한공격 의사난수의 종자 (Seed) 는암호의 키 에필적하는중요성을갖는다. 의사난수의종자가공격자에게알려져버리면, 그의사난수생성기가생성하는의사난수열은모두공격자에게알려지게된다 재현불가능성을갖는 진정한난수 를종자로할필요가있다.
12.7.2 랜덤풀에대한공격 난수가필요할때그자리에서진정한난수를만들어내는것이아니라, 랜덤풀 이라불리는파일에랜덤한비트열을비축해두는방법이있다. 랜덤풀에대한공격을대비해야한다