<333620BCDBC1A6C8A32DBDBAB8B6C6AE20C4ABB5E5BFEB20B3BBC0E5C7FC20C5B020BDBAC4C9C1ECB7AF20BAEDB7CF20BCB3B0E82E687770>

Size: px

Start display at page:

Download "<333620BCDBC1A6C8A32DBDBAB8B6C6AE20C4ABB5E5BFEB20B3BBC0E5C7FC20C5B020BDBAC4C9C1ECB7AF20BAEDB7CF20BCB3B0E82E687770>"

정원 복
4 years ago
Views:

1 한국산학기술학회논문지 Vol 11, No 12 pp , 2010 송제호 1* 1 전북대학교 IT 응용시스템공학과 Design of Inner Key scheduler block for Smart Card Je-Ho Song 1* 1 Dept of IT Applied System Eng Chonbuk National University 요약스마트카드는암호알고리즘의개발과더불어전자상거래환경이구축되면서가치이전의수단및활용분야가다양하기때문에정보통신망환경에서중요한보안장치로수요나활용면에서급격한증가율을보이고있다 따라서본논문에서제안한스마트카드용키스케쥴러블록은다양한멀티미디어및실시간통신의암호시스템에적용할경우기존시스템과호환성이용이하여하드웨어설계와비도및처리속도를향상시킬수있다고사료된다 Abstract Security of the electronic commercial transaction especially through the information communication network is gaining its significance due to rapid development of information and communication related fields For that, some kind of cryptographic algorithm is already in use for the smart card However, the growing needs of handling multimedia and real time communication bring the smart card into more stringent use of its resources Therefore, we proposed a key scheduler block of the smart card to facilitate multimedia communication and real time communication Key Words : Smart card, Key scheduler block, Symmetric cryptography, Asymmetric cryptography, Security level 1 서론 1990년대까지사용된대부분의스트림암호알고리즘은 LFSR(Linear Feed-back Shift Register) 을기본으로하여여러가지비선형적결합을통해주기가긴키스트림을발생하는형태가일반적이었다 이런형태는하드웨어구현에용이하고안전도를수식적으로표현할수있는장점이있지만소프트웨어의구현성이문제가되어최근에는 RC4, SEAL30, ISAAC, TWOPRIME 등의알고리즘과부분별혼합형알고리즘이제안되고있다 [1,2] 제안된암호알고리즘은스마트카드에대한구조, 특성, 안전성, 관련표준, 기술및다양한응용부분을고려하여국가간스마트카드표준화기구인 ISO /IEC JTC1 SC17의기준을적용하였다 본논문에서는스마트카드의암호시스템에적합하도록블록및스트림암호알고리즘에기반을둔암호알고리즘을제안하였다 [3,4] 대칭형암호방식에 (symmetric cryptography) 비대칭형암호방식 (asymmetric cryptography) 개념을적용한새로운암호알고리즘은데이터재배열, 치환, 데이터암호블록, 키스케쥴러로구성되어있고, 데이터암호화과정은 비트평문블록을 64 비트씩 2개의블록으로분할하고확장을거친후 80 비트크기를가지는혼합형키를사용하여암호화하였다 [5,6] 또한, 단일라운드 (round) 만을사용하고도기존 라운드에해당하는비도 (security level) 를얻도록혼합형키 (hybrid key) 와블록암호시스템의비선형부분인 F 암호함수부분을더욱더비선형화시켰다 입력신호를평문및키데이터로사용할수있고암호문은비인가자에게인증용으로적용되며기존시스템과호환성이용이하도록하였다 [7] 제안된키스케쥴러알고리즘을이용하여 Synopsys ver 으로설계하였고 40MHz의시스템속도환경에서확인하였다 * 교신저자 : 송제호 (songjh@jbnuackr) 접수일 10 년 10 월 29 일수정일 10 년 12 월 일게재확정일 10 년 12 월 17 일 4962

2 2 기존암호알고리즘구조 블록암호의동작모드는크게 4가지로분류된다 ECB 모드 (Electronic Code Book) 는각각의평문을블록단위로독립적인암 복호화과정을수행한다 CBC 모드 (Cipher Block Chaining) 는일반적인암호변환방식으로서가장많이사용하는방식으로서 IV(Initialization Vector) 값을사용한다 CFB 모드 (Cipher Feedback) 는블록암호를스트림암호로변환하여암호화를수행하는방식으로서블록암호화는의사난수데이터 (pseudo random data) 를생성하기위해사용되며암호문을생성 하기위하여평문 ( M i ) 과 XOR 연산하고출력된암호문은다음블록에대한의사난수데이터를만들기위하여블록암호화로귀환된다 OFB 모드 (Output Feedback) 는독립적인수열데이터블록 (sequence data block) S를자체동기 (self synchronizing) 스트림암호문으로변환하는과정을거쳐수행된다 블록암호알고리즘은 DES와같은형태인 Feistel 구조와치환 (substitution) 과재배열 (permutation) 을반복하여사용하는 S-P 네트웍구조등으로구성된다 Feistel 방식은한라운드에평문의일부만처리하여병렬처리효율이낮은반면라운드함수설계의융통성과암 복호화과정이동일하다는장점을가진다 S-P 네트웍방식은한라운드에서전체평문을암호화하므로병렬처리가가능하여속도가빠르지만복호화를고려하여암호화과정을설계하므로설계의폭이좁은단점을가진다 Feistel 방식의암호화는반복되는블록암호화의특별한형태로서 S-P 네트워크또는변환과라운드함수를이용하며구조는식 1과같다 암호화과정은먼저, 평문을 우측과좌측반씩두개 ( L 0, R 0 ) 로나누고라운드함 수 F 는서브키 ( K i ) 를우측에만적용하고, F 출력은 좌측의반과 XOR 연산을한후우측으로위치가교환된다 L i = R i -1 R i = L i -1 F ( R i -1, K i ) C = R i L i = L i -1 F ( R i -1, K i ) R i -1 (1) 스트림암호방식은데이터를비트단위로처리하는암호방식으로서주로유럽을중심으로발전되었으며블록암호에비하여암호화의속도는빠르고암호문을해독하기힘든장점이있다 스트림암호는주로하드웨어로구현되며군용통신과같이데이터통신내용이매우민감 한부분에적용된다 스트림암호는보통긴주기를가지는수열을발생하여문자열과비트별논리합을하여암호문을발생하는방법을사용하기때문에암호의안전성은전적으로키수열의안전성에기인한다 블록암호에비하여긴역사를가지고있는스트림암호는키스트림생성기로사용되는 LFSR, 키생성방법에따라 OTP(one time pad), 키생성이평문과암호문에종속되지않는동기스트림암호화 (synchronous stream cipher) 혹은 KAK(key auto key), 키생성이평문과암호문에종속되는자체동기스트림암호화 (self synchronous stream cipher, asynchronous stream cipher) 혹은 CTAK(cipher-text auto key) 을근간으로하지만최근에는소프트웨어구현에적합한여러가지방식이제안되고있다 LFSR은스트림암호에서의사난수발생기 (PRG : pseudo random generator) 를이용하여수학적으로분석이가능한이진수열을효율적으로발생할수있는장치로유한체위에정의된선형점화식수열로모델링할수있으며수열의특성은점화식에의해유도되는특성다항식에의하여결정된다 LFSR은암호뿐아니라대역확산통신등에도많이활용되고구현복잡도가작아빠른속도가요구되는곳에적용된다 [3] 유한체 GF(2)={0,1} 위에다음과같이정의된수열을식 (2) 로나타낸다 S j + n =(C 0 S j + n -1 + C 1 S j + n C n -1 S j ) mod 2, j 0 (2) 여기서, 은초기치로정의된다 이때식 (2) 의특성다항식 (characteristic polynomial) 는식 (3) 과같다 f( x )= s n + C 0 x n -1 + C 1 x n C n -2 x + C n -1 (3) 이때 은반드시 1이어야하며초기값이모두 0 인경우는배제한다 LFSR에서는초기값으로부터나머지수열을모두생성할수있기때문에특성다항식 의특성이중요하다 따라서, n개단을갖는 LFSR에의하여생성되는수열의특성은 n차특성다항식에의하여결정된다 유한체위에정의된다항식의특성은그다항식의차수 (degree) 와위수 (order) 에의하여결정되며특히위수가정확히 인다항식을원시다항식 (primitive 4963

3 한국산학기술학회논문지제 11 권제 12 호, 2010 polynomial) 이라부르며이러한다항식에의하여결정되는 LFSR을최대주기수열이라한다 수열의비선형성의정도를나타내는척도로서가장중요한개념은선형복잡도 (LC : Linear Complexity) 이다 어느수열의선형복잡도는그수열을생성하는최소다항식 (minimal polynomial) 의차수를의미하는데여기서최소다항식은수열의특성다항식중가장작은다항식을의미한다 [8] LFSR을이용한스트림암호구성에있어서선형적인특성은암호시스템에서해결해야하는과제이다 해결방안으로 LFSR 단의내용을비선형결합시켜병렬처리로수열을발생하는경우선형복잡도를증가시킬수있게두개이상의 LFSR을선형혹은비선형으로결합하는것이다 다른방법은시각제어논리를이용하는것으로보통 2개이상의 LFSR로구성되며 1개의 LFSR의출력으로부터다른 LFSR의출력을제어하여출력을발생하는기법으로 Stop & Go generator, alternating step generator, binary rated multiplier 등많은수열발생기가제안되었다 마지막으로메모리를이용하는방법으로 Summation Generator 등이대표적인경우이며최근에는 FCSR(Feedback with Carry Shift Register) 등많은이론이발전되고있는단계로이때발생되는수열도특정한조건하에서주기및선형복잡도를매우크게할수있다 3 제안된키스케쥴러알고리즘 암호알고리즘의구현론에서소프트웨어방식은융통성이크며업데이트가용이하지만크랙및해킹에취약성을보인다 그러므로본논문에서는정보누출및변조를막고정보보호차원에서하드웨어에의한구현을선택하여플랫폼의유 출입부분에서동작하도록암호알고리즘을제안하였으며설계된암호시스템은대칭형암호시스템을기본으로비대칭형암호시스템특징을가질수있도록설계하였다 그림 1은제안된혼합형암호시스템의데이터암호블록으로서기존 Feistel 구조와동일한형태를가진다 한방정식만존재한다 입력 비트는 IP를거친후좌우 64비트씩분리된다 좌우로분리된 64 비트는그림 4 와같이오른쪽 64 비트는왼쪽으로이동하며왼쪽 64 비트는혼합형키와 F 암호함수의연산과정후 XOR 연산을수행한후오른쪽으로이동하게된다 이러한연산을수행한후역초기치환 (IIP : Inverse Initial Permutation) 을수행하여암호화된데이터를출력하게된다 IP Left 64 Right 64 F Left 64 Right 64 IIP [ 그림 1] Feistel 구조와 SPN 구조블록암호시스템은반복을최소 회정도반복수행하지만본논문에서사용한 Feistel 구조는그림 2와같이단지 1회의라운드에대해서만수행하도록한다 이러한기능은 F 암호함수에있다 F 암호함수는일반적으로사용되는키스케쥴에의해발생된키를사용하는것이아니고단순키기능과인증및비대칭형개념을가진혼합된키값을사용하여비도를더높일수있다 L 0 R 0 = L 1 HK O F F I = I I' L 1 = L 0 L 0 ' R 1 = L 0 O HK L 1 = R 0 R 1 = L 0 f ( R 0, HK) 식 (4) 는기본 Feistel 구조와유사하지만키생성및생성된키정보의형태는다른형태를취하게된다 또한반복에관한 i 파라미터가없는대신이전과이후에관 (4) [ 그림 2] 단일라운드에대한 Feistel 구조특성키스케쥴러는스트림암호시스템으로구성되어있다 그림 3은스트림암호방식을적용한키스케쥴러블록이다 키스케쥴러입력으로는그림 3과같이키데이터가별도로존재하는것이아니고암호화대상데이터가키 4964

4 스케쥴러의입력이되므로그림 4와같이 Mixer의입력은 비트의입력데이터와 LFSR로부터생성된키수열이된다 식 (6) 에서 M 역시 비트 8 블록이므로식 (7) 과같은수열을가진다 M = { m 0, m 1,m 2,m 3, m 4,m 5,m 6,m 7 } (7) Seed Data input Key output Buffer Key_out &Auth Mixer Merging & Expansion LFSR- Key Sequence Replacement LFSR-MSB LFSR-LSB [ 그림 3] 스트림암호알고리즘의키스케쥴러블록도 식 (7) 에식 (5) 를대입하고연산수행을행렬로표현하여정리하면식 (8) 과같다 ik 00 ik 01 ik 02 ik 03 ik 04 ik 05 ik 06 ik 07 ik 10 ik 11 ik 12 ik 13 ik 14 ik 15 ik ik 17 ik 20 ik 21 ik 22 ik 23 ik 24 ik 25 ik 26 ik 27 M = ik 30 ik 40 ik 31 ik 32 ik 33 ik 41 ik 42 ik 43 ik 34 ik 35 ik 44 ik 45 ik 36 ik 37 ik 46 ik 47 ik 50 ik 51 ik 52 ik 53 ik 54 ik 55 ik 56 ik 57 ik 60 ik 61 ik 62 ik 63 ik 64 ik 65 ik 66 ik 67 ik 70 ik 71 ik 72 ik 73 ik 74 ik 75 ik 76 ik 77 (8) Matrix Permutation Key Sequence Key sequence Key sequence [ 그림 4] Mixer 블록 이두가지의데이터는 비트씩 8개의블록으로분리되며각각 XOR 연산을수행하게된다 비트의데이터 8 블록들은 XOR 연산수행후메트릭스치환을 Merging & Expansion 블록의입력으로동시에사용된다 메트릭스치환은 비트씩 8 블록이독립적으로 XOR 연산을수행하게되며행데이터들에대한연산결과는열데이터의형태로출력되어진다 입력데이터의집합을 I, 키수열의집합을 K라하면 I, K에대한표현은식 (5) 와같다 식 (5) 에서 i 와 k는각각 비트씩으로구성된스트림데이터들이다 I = { i 0, i 1, i 2, i 3, i 4, i 5, i 6, i 7 } K = { k 0, k 1, k 2, k 3, k 4, k 5, k 6, k 7 } XOR 연산을수행한결과를 M이라하였을경우 XOR 연산을수행한입력데이터들은식 (6) 과같이표현된다 (5) M = I K (6) 여기에서 는 의연산결과임을나타낸다 식 (8) 에대한매트릭스치환은식 (9) 와같이전치행렬로표시되고연산을통하여생성된 64 비트는 Merging & Expansion 모듈의입력으로사용된다 LFSR-은 8단으로구성된 LFSR이 개포함된의사난수발생기로그림 8과같다 LFSR의탭계수는 으로설정하고키부호기의초기내용은 로되어있다 이므로입력키수열은 이며부호화된출력키수열 다 모듈러-2 연산에서 가 와같이교환법칙이성립되므로 8단스트림키부호생성기를해석하기위하여초기상태조건을적용하여정리하면식 (10) 과같이된다 = = (9) (10) G ( x ) = x 7 + x 3 +1 (11) 4965

5 한국산학기술학회논문지제 11 권제 12 호, 2010 input S 1 S 2 S 7 S 8 g1 g 7 g 8 생성뿐만이아니라송신자에대한인증용데이터까지출력한다 output keyschedule [ 그림 5] 8 단 LFSR 의사난수발생기 buffer preformat mexp weightgen mixer 이때그림 5와식 (10) 을식 (11) LFSR 생성다항식에적용하여정리하면식 (12) 가된다 lfsr keyseq replator timegen z 0 + k 0 = g 1 s 1 + g 4 s 6 + g 8 s 8 z 1 + k 1 = g 1 k 0 + g 4 s 5 + g 8 s 7 z 2 + k 2 = g 1 k 1 + g 4 s 4 + g 8 s 6 z 3 + k 3 = g 1 k 2 + g 4 s 3 + g 8 s 5 lfsr8 [ 그림 7] 키스케쥴러블록도 z 4 + z 4 = g 1 k 3 + g 4 s 2 + g 8 s 4 z 5 + k 5 = g 1 k 4 + g 4 s 1 + g 8 s 3 z 6 + k 6 = g 1 k 5 + g 4 k 0 + g 8 s 2 z 7 + k 7 = g 1 k 6 + g 4 k 1 + g 8 s 1 (12) z 8 + z 8 = g 1 k 7 + g 4 k 2 + g 8 k 0 z 9 + k 9 = g 1 k 8 + g 4 k 3 + g 8 k 1 z 10 + k 10 = g 1 k 9 + g 4 k 4 + g 8 k 2 z 11 + k 11 = g 1 k 10 + g 4 k 5 + g 8 k 3 z 12 + z 12 = g 1 k 11 + g 4 k 6 + g 8 k 4 z 13 + k 13 = g 1 k 12 + g 4 k 7 + g 8 k 5 z 14 + k 14 = g 1 k 13 + g 4 k 8 + g 8 k 6 z 15 + k 15 = g 1 k 14 + g 4 k 9 + g 8 k 7 그림 6은식 (12) 를바탕으로키수열을생성시키기위한키수열생성블록이다 키스케쥴러블록은데이터를암호화하기위한키생성블록으로 Synopsys ver 으로설계하였다 암호화에필요한키값을생성하는데사용되는하부블록은그림 7과같이 9개의기능블록으로구성하였다 Mixer LFSR x 00 x 01 x 0n x 10 x m0 x mn Auth Matrix format Replace [ 그림 6] 키수열생성기 데이터암호를위한키스케쥴러블록은스트림암호시스템을기본으로하여 LFSR의의사난수발생및 SPN 을동시에사용하고있으며암호화를수행하기위한키 buffer 블록은입출력포트가구성되어있어서암호화및정보누출방지에대한게이트역할을수행하는기능블록이다 buffer 기능블록은첫번째관문으로써암호화를수행중이거나수행한후에유입데이터가비인가자에의한신호임이밝혀지면 system_en 단자에의하여 buffer은암호화에관련된모든동작은정지되며비인가신호를차단한다 preformat 기능블록은키데이터를처리하기전에미리데이터에대한포맷을정리하는기능블록으로써 mixer의입력으로사용할데이터 비트씩 8개의블록으로구별하는동작을수행하도록설계하였다 lfsr 블록으로내부에는 8단으로구성된 lfsr8 블록이존재한다 lfsr8에대한생성다항식을이용하여구현한 lfsr8은주기가 의길이를가지지만본논문에서는 8T만을사용하므로 LFSR의주기는크게비도를좌우하지않는다 lfsr8 개의모듈은각각 8T 동안동일하게출력된값들은 weight & time generator, 키수열의입력으로사용된다 keyseq 기능블록은키수열블록으로써키생성수열을수행하는기능블록이다 8 비트 개의블록데이터를입력으로내부의 key matrix 연산을수행한후 mixer와 replacement 블록으로데이터를전송한다 이때인증용데이터 비트를생성하여키스케쥴러블록의최종출력값에더해져인증용으로사용된다 weightgen 블록은 lfsr로부터출력되는데이터를재포맷하고 MSB와 LSB 데이터를분리및변화시키는기능을수행하도록설계하였다 timegen 블록은 lfsr로부터출력되는데이터재포맷기능으로키수열출력에서비밀키와공개키로분리하기위하여 time slot을생성한다 replator 기능블록은키수열, weight & time generator의데이터를받아서새로운데이터포맷을결정함으로써 time slot에의한암호용키 4966

수열생성을수행하도록한다 mexp 기능블록으로써데이터에대한 merging과 expansion 기능을수행한다 interleaving된 mixer 블록의데이터와 replator 블록에서생성된 weight &time slot을이용하여 64 비트크기를가지는새로운블록데이터를생성하도록설계하였다 4 모의실험및검증 그림

6 수열생성을수행하도록한다 mexp 기능블록으로써데이터에대한 merging과 expansion 기능을수행한다 interleaving된 mixer 블록의데이터와 replator 블록에서생성된 weight &time slot을이용하여 64 비트크기를가지는새로운블록데이터를생성하도록설계하였다 4 모의실험및검증 그림 8의키스케쥴러기능블록은평문을입력으로받아평문과의상관성을배제하고평문을암호화할수있는키수열을생성하는부분과 비트의인증용데이터를생성하는부분으로써대칭형과비대칭형암호시스템의기능을모두수행할수있도록설계하였다 키스케쥴러블록의입력은암호화하려는데이터를이용하였으며제어신호에의하여인증용과키데이터를생성하였다 그림 9는키스케쥴러블록을 Altera MAX+PlusⅡ툴로모의실험결과이다 [ 그림 8] 키스케쥴러의기능블록도 화기구인 ISO/IEC JTC1 SC17의기준을적용하였다 대칭형암호방식에비대칭형암호개념을적용한키스케쥴러로를설계하여입력신호를평문및키데이터로사용할수있고암호문은비인가자에게인증용으로적용된다 제안된키스케쥴러알고리즘을이용하여스마트카드의암호시스템을 Synopsys ver 으로설계하였고 40MHz의시스템속도환경에서확인하였다 제안된알고리즘을스마트카드의암호시스템에적용할경우기존시스템과호환성이용이하여하드웨어설계와비도및처리속도를향상시킬수있다고사료된다 참고문헌 [1] W Stallings, Cryptography and Network Security, Prentice Hall, 1998 [2] B Schneier, Applied Cryptography : Protocols, Algorithms, and Source Code in C, John Wiley & Sons, Inc, New York, USA, 1994 [3] D R Stinson, Cryptography Theory and Practice, Chapman & Hall/CRC, 2002 [4] H Miyano, AMethod to Estimate the Number of Ciphertext Pairs for Differential Cryptanalysis, Abstracts of ASIACRYPT91, 1991 [5] 서광석, 김창한, 암호학과대수학, 북스힐, 1999 [6] T Siegenthaler, "Decrypting a Class of Stream Ciphers Using Ciphertext Only," IEEE Trans on Computer, Vol C-34, No 1, pp 81-85, Jan 1985 [7] R Rueppel, "Stream Ciphers," Contemporary Cryptology: The science of Infor Integrity, New York, IEEE Pres, pp , 1991 [8] 이병관, 전자상거래보안, 남두도서, 2002 송제호 (Je-Ho Song) [ 정회원 ] [ 그림 9] 키스케쥴러의모의실험결과 5 결론 본논문에서는이동성및네트워크환경이강조되는스마트카드의암호시스템에적합한스트림암호알고리즘에대하여고찰하였다 그리고제안한암호알고리즘을스마트카드에대한구조, 특성, 안전성, 관련표준, 기술및다양한응용부분을고려하여국가간스마트카드표준 1991 년 2 월 : 원광대학교전자공학과 ( 공학사 ) 1993 년 2 월 : 원광대학교전자공학과 ( 공학석사 ) 2003 년 2 월 : 원광대학교전자공학과 ( 공학박사 ) 1996 년 3 월 ~ 현재 : 전북대학교 IT 응용시스템공학과교수 < 관심분야 > VLSI, 정보통신, 통신망네트워크시스템설계 4967

본 강의에 들어가기 전

본 강의에 들어가기 전 1 2.1 대칭암호원리 제 2 장. 대칭암호와메시지기밀성 2 3 기본용어 평문 (Plaintext) - original message 암호문 (Ciphertext) - coded message 암호화 (Cipher) - algorithm for transforming plaintext to ciphertext 키 (Key) - info used in cipher