공개키암호 박영호 암호학은정보보호서비스를안전하게제공하기위한기술로연구되고있다. 암호학에서연구되는암호학적도구는크게공개키암호와비밀키암호로나눌수있다. 비밀키암호는두사용자가동일한비밀키를공유하고있는상태에서전송하고자하는데이터를공유한키로암호화하여수신자에게전송하면수신자는동일한키로복호화하여데이터를복원한다. 네트워크를통해전송되는정보는암호화된정보이므로외부에서데이터를확인할수없게되어안전한통신이가능하게된다. 따라서비밀키암호의경우암호화키와복호화키는동일하고두키는모두비밀정보이다. n명의사용자가있는네트워크의경우를가정하면모든네트워크참여자는나머지 n-1명과비밀정보를공유하고있어야한다. 따라서 n명의사용자로구성된네트워크에서안전한통신이수행되기위해서는시스템전체적으로 n(n-1)/2개의키가요구된다. 각사용자가보유해야하는키의개수도 n-1개이다. 암호알고리즘은공개키에비해매우효율적이라는장점을가진다. 그리고통신을수행하는두주체는상호인증이가능하다. 하지만이때사용된키정보는다른사용자에게알려지지않은값이기때문에통신내용의제삼자에대한인증은제공되지않는다. 공개키암호는비밀키암호와달리송신자와수신자가다른키를사용하여비밀통신을수행한다. 송신자는수신자의공개키에해당하는정보를사용하여데이터를암호화하여네트워크를통해전송한다. 수신자는자신의공개키에해당하는비밀키로암호화된데이터를복호화하여평문을복원한다. 공개키암호는다른유저와키를공유하지않더라도암호를통한안전한통신을한다는장점을갖는다. 각사용자는자신에게전송하기위해사용될키를공개하고, 공개된키정보로암호화된정보를복호화할수있는키를비밀로보유하고있음으로써 저자약력박영호교수는고려대학교수학과박사로서프랑스 CAEN 대학교박사후연구원 (97-99), 고려대학교정보보호기술센터 (CIST) 연구교수를거쳐현재세종사이버대학교정보보호시스템공학과부교수로재직중이다. (youngho@sjcu.ac.kr) 그림 1. 비밀키암호와공개키암호의모식도. 누구나암호화할수있지만공개키에대응되는비밀키를가 진당사자만복호화할수있는특징을가진다. n명의사용 자로구성된네트워크를고려하면각사용자는공개키와비 밀키두개를보유하고있으므로네트워크전체적으로 2n개 의키가요구된다. 그리고각유저는 2개의키만보유하고 있으면된다. 공개키암호는수학적인난제를기반으로설계 되어있고, 암호화나복호화를수행하기위한연산이복잡한 수학연산을기반으로구성되기때문에효율성은비밀키암 호에비해높지않다. 공개키암호의경우에는모두가확인 표 1. 공개키암호와비밀키암호의비교. 공개키암호 비밀키암호 키의관계 암호화키 복호화키 암호화키 = 복호화키 암호화키 공개 비공개 복호화키 비공개 비공개 알고리즘 공개 공개 키의개수 2n n(n-1)/2 1인당키 1개 n-1 속도 비효율적 효율적 인증 누구나인증 키공유자 물리학과첨단기술 March 2007 7
표 2. 암호시스템의장단점비교. 장점 단점 공개키암호시스템 - 키의분배가용이함 - 사용자의증가에따라관리할키의개수가상대적으로적음 - 키변화의빈도가적음 - 여러가지분야에서응용이가능함 - 암호화 / 복호화속도가느림 - 키의길이가김 - 암호화 / 복호화속도가빠름 - 키의길이가짧음 대칭키암호시스템 - 사용자의증가에따라관리해야할키의수가상대적으로많음 - 키변화의빈도가많음 할수있는공개키에대응되는비밀키가각사용자만알고있는정보이기때문에광범위한인증기능이제공된다. 공개키암호와비밀키암호는제공되는서비스의특성에의해정보보안서비스를제공함에있어상호보완적인기능을수행한다. 비밀키암호는암호연산의효율성으로인해저장또는전송하기위한데이터를암호화하는목적으로널리사용된다. 공개키암호는비밀키암호에비해효율성이높지는않으나비밀키암호에서제공되지않는인증기능이제공되기때문에사용자또는데이터를인증하기위한목적으로사용된다. 따라서공개키암호와비밀키암호의중요성에대한절대적인비교는어렵고각기정보보안서비스를안전하게제공하기위한도구로써의중요성을지닌다. 공개키암호의소개공개키기반의암호시스템은대칭키기반의암호시스템에비하여상대적으로속도가느리다는단점을가지고있다. 하지만공개된키를이용하여인증, 서명등의서비스와더불어상호간의공개된키를이용하여비밀값을쉽게유도할수있다는장점을가지고있다. 암호알고리즘은키의특성에따 라크게암 / 복호화키가같은대칭키암호알고리즘과암 / 복호화키가서로다른공개키암호알고리즘으로나누어볼수있다. 그러나암호사용자가늘어나고, 또한다양한암호서비스에대한요구가제기되면서대칭키암호알고리즘에서발생된키관리문제와인증문제를해결하기위한알고리즘의필요성이대두되었다. 1976년 W. Diffie와 M. E. Hellman이위의두문제를해결한 New Directions in Cryptography 에서공개키암호의개념을처음소개하였다. [1] 그후많은공개키암호알고리즘이제안되어, 안전도또는실용적측면에서문제점이야기되었으나, 1978년소인수분해의어려움에기반을둔 RSA [2] 가소개되어지금까지넓게사용되고있다. RSA 외에인수분해의어려움을기반으로설계된암호로는 Rabin 암호 [3] 가있다. RSA(Rivest, Shamir, and Adleman) 는공개키암호시스템으로암호화와인증에사용된다. RSA는일반정수론적인면에서정의되었다. 이시스템은큰수의인수분해의어려움에안전성을두고있다. 전자서명의길이는 RSA 시스템에서의키길이와같다. RSA 시스템을깨는문제가인수분해문제로귀결된다는완전한수학적증명의부족과인수분해문제가 NP-hard임에도불구하고, RSA는수많은국제기구의표준뿐만아니라산업표준으로권장되고있다. 반면에, RSA 에근거한소프트웨어의분배는 RSA 알고리즘이미국에서저작권보호를받기때문에제한되고있다. RFC에따르면, 디지털서명및디지털 Envelopes를아래와같은방법으로사용하도록구조화되었다 : 디지털서명은 그림 2. 공개키암호알고리즘구성도. 참고문헌 [1] W. Diffie and M. E. Hellman, IEEE Trans. on Info. Theory IT-22, 644 (Invited Paper) (1976). [2] Ronald L. Rivest, Adi Shamir, Leonard M. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Commun. ACM 21(2), 120 (1978). [3] Rabin, Michael. Digitalized Signatures and Public-Key Functions as Intractable as Factorization. MIT Laboratory for Computer Science, January (1979). 8 물리학과첨단기술 March 2007
message-digest 알고리즘 ( 예를들면, MD5) 을첫째로설명될것이다. 서명된데이터를 message digest한후개인키에의하여암호화되며 PKCS#7에의하여원문과암호문이다루어진다. 이것은 PEM( 비밀보장이향상된전자우편 ) 과호환된다. RSA의속도는모듈러 n에의존한다. 공개키의연산은 O (k 2 ), 개인키의연산은 O (k 3 ), 키의생성은 O (k 4 ) 의연산이소요되고이때의 k는모듈러의비트크기이다. RSA 키의크기는모듈러의크기를말하며이는사용자에의하여결정된다. 따라서 RSA의안전성은모듈러의비트의크기에의존하며소수 p, q의형태에도의존한다. 만약 RSA와 DES의속도를비교하면소프트웨어에서는 DES가 RSA보다 100배정도빠르고하드웨어에서는 1,000에서 10,000 정도더빠르다. 타원곡선 (Elliptic Curves) 은약 150년전부터수학적으로광범위한연구가있어왔고, 최근 Andrew Wiles의 Fermat s Last Theorem 증명에서중요하게사용되기도하였다. 타원곡선암호시스템은 10여년전비트당안전도가타공개키시스템보다효율적이라는것이알려졌고, 최근높은속도의구현이가능하게되었다. 타원곡선을이용한공개키암호시스템즉, 유한체 (finite fields) 위에서정의된타원곡선군에서의이산대수문제에기초한타원곡선암호시스템 (ECC, [4] Elliptic Curve Cryptosystem) 은 1985년 N. Koblitz와 V. Miller에의해처음제안된이후활발히연구되고있다. 더욱이, 타원곡선방법 [5] (ECM, Elliptic Curve Method) 은최근 RSA 암호시스템의근간이되는인수분해문제와소수성테스트를위한효율적알고리즘을제공하기도하였다. 타원곡선암호시스템에서 1990년에괄목할만한성과중의하나가 Menezes, Okamoto와 Vanstone에의해연구되었다. 그들은이연구에서초특이타원곡선 (Super singular Elliptic Curve) 의이산대수문제가유한체위에서의이산대수문제로바뀔수있음을보였다. [6] 즉, Subexponential time algorithms이존재한다는것을보였다. 그러므로만약완전지수복잡도 (fully exponential complexity) 로타원곡선암호시스템이깨지기를원한다면, 초특이타원곡선을피해야함을의미한다. 그러나효율성면에서고려하면초특이타원곡선을사용한암호시스템이몇가지의이점을가지고있으므로무조건적인배제는옳지않다. 참고로지금까지가장널리사용되고있는 RSA 시스템은 subexponential time algorithm이존재한다. 키의크기가작다는것은데이터를암호화, 복호화하는데있어서적은연산과에너지가필요하다는것을의미한다. 최근에집중적으로논의되고있는전자서명의경우공개키암 호가필수적이며현재가장널리사용되고있는 RSA의경우키의크기가 1024비트는되어야안전한것으로평가되는데이는서명의길이가너무길다는단점을지닌다. 이에반해 ECC는 160비트정도의키크기로같은수준의안전성을보장하기때문에전자상거래에필요한스마트카드 (smart card) 나전자화폐등에사용될수있다. 실제로전자서명표준화는 ECDSA [7] 를중심으로진행중이고거의확정단계이다 (IEEE P1363, ANSI X9.62, ISO/IEC, WAP forum 등 ). 또한 DSA [8] 를전자서명표준으로정했던 NIST도 1999년연합정부권고알고리즘으로타원곡선을제안하고있다. 이런장점을지닌타원곡선암호시스템은전원의양이한정된이동통신기기의암호화에적용될수있다. 같은이유로타원곡선암호시스템은차세대공개키암호법으로주목받고있으며 IMT-2000에적용될수있는가장효과적인공개키암호시스템이다. XTR [9] (Efficient and Compact Subgroup Trace Representation) 공개키시스템은 Crypto 2000에서 A.K. Lenstra 에의해서처음소개되었다. 1024비트 RSA의안전성과동일한 XTR은임의의소체 (Z p ) 위에서의 ECC에기반을둔암호시스템과속도와안전성면에서비슷하지만, 파라미터를초기화하는데에 RSA와 ECC의파라미터초기화시간보다훨씬적은시간이소요된다. 참고문헌 공개키암호와전자서명 전자서명은 DSA(Digital Signature Algorithm), RSA Signature, ECDSA(Elliptic Curve Digital Signature Algorithm) 이주로사용된다. DSA는미국연방표준 FIPS 186에명시되어있으며 1,024 15,360 사이의키사이즈를가지며 message digest 함수인 SHA-256, 384, 512 등을이용하여구성된다. RSA 서명은 ANSI X9.31 또는 PKCS [4] N. Koblitz, Math. Comp. 48, 203 (1987). [5] Factoring Integers with Elliptic Curves, Annals of Mathematics, 126, 649-673. [6] Alfred Menezes, Scott A. Vanstone, Tatsuaki Okamoto, Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field STOC 80-89 (1991). [7] S. Vanstone, Communications of the ACM Archive 35(7), 41 (1992). [8] National Institute of Standards and Technology, Digital Signature Standard, FIPS Publication 186, 1994, Available at http://csrc.nist. gov.fips [9] Arjen K. Lenstra, Eric R. Verheul, The XTR Public Key System. CRYPTO 2000, 1-19. 물리학과첨단기술 March 2007 9
그림 3. 공개키암호화. 법을간단하게보여주고있다. 일반적으로, 어떤사람에게암호화된데이터를보내기위해서는그사람의공개키로데이터를암호화해야한다. 대칭키암호화와비교해서공개키암호화는더많은계산을요구하기때문에많은양의자료를암호화하는데는적합하지않다. 그러므로통신의초기에공개키를사용해서대칭키를초기화하고, 그다음에대칭키를사용하면안전하면서도빠른속도를얻을수있다. 이접근방법은 SSL이나 IPSec 등보안프로토콜등에서일반적으로사용되어진다. 이방법은전자서명에사용된다. 전자서명은우리가일상생활에서신원을확인하거나거래를하려고할때주민등록증이나인감날인또는서명등이필요하듯이, 인터넷상에서도이를확실히보장해주는수단이바로전자서명 (Digital Signature) 이다. 즉, 전자서명은인증서형태로발급되는자신만의디지털인감이며서명인것이다. 결국, 전자서명은어떤사람이그문서를작성했다는것을증명하는방법이므로전자서명을하기위해서는어떤문서에그문서를자신의개인키로암호화해서첨부하는것이다. 이렇게암호화된것은공개키에의해서복호화되서원문과비교될수있다. 그러므로이방법을사용하면어떠한사람이서명했다는것을증명할수있다. [ 그림 4] [10] 는공개키암호화와전자서명에대한그림이다. 그림 4. 공개키암호화와전자서명. 공개키암호의안전성과효율성 #1 v1.5 이상의문서에명시되어있으며키사이즈는 1,024 비트부터 256비트씩증가하고, 두개의표준은다른포맷을가진다. ECDSA는미국연방표준 FIPS 186인 DSA를타원곡선에적용한것으로 ANSI X9.62로표준화되어있으며국제적으로가장널리사용되고있다. 국내에서도기존의전자서명표준인 KCDSA의타원곡선변형을 EC-KCDSA라는이름으로작년말 TTA 표준으로제정한바있다. 또한미연방정부표준인 FIPS 186-2에서는 X9.62 표준을그대로따르되, 다만연방정부용으로사용하기위한권장곡선을추가로제공하고있으며최소 160비트이상의키사이즈를가진다. 공개키암호화는공개키 (Public key) 와개인키 (private key) 를사용해서인증, 서명, 암호화등을수행한다. 공개키와대칭키는동시에만들어지면하나의쌍으로구성된다. 특정사용자의공개키로암호화된데이터는오직그사용자의개인키로암호를해독할수있다. [ 그림 3] [10] 은공개키암호화방 두개의알고리즘이주어진키사이즈에대하여같은안전성을가졌다는것은알고리즘이깨어지거나키가노출되는데걸리는시간이같은정도를의미하며, 주어진키사이즈에대한알고리즘의안전성은일반적으로대칭키의키전수조사를통하여시도될수있는시간을의미한다. 그러므로키의사이즈는안전성에서큰부분을차지한다. 따라서요구되는안전성을고려한적당한키사이즈의선택이필요하다. 현재 80비트정도이면안전하다고알려져있으며향후 2015년을고려하면 112비트정도이면안전하다고한다. DES의키사이즈는 1997년에깨어졌다. 따라서 24비트가더많은 80비트는 Moore s 법칙에의하여 24비트를깨는데 36년이걸리므로 80비트를깨는데는 2033 (1997 + 36) 년이걸린다는결론이나온다. 또한, Lenstra는참고문헌 [10] 한국정보사회진흥원정보인증센터 http://sign.nia.or.kr/. 10 물리학과첨단기술 March 2007
표 3. 암호시스템의안전성비교. Bits of security Symmetric key algs. Hash algs. DSA, D-H, MQV RSA Elliptic Curves 80 SHA-1 112 TDES 128 AES-128 SHA-256 192 AES-192 SHA-384 256 AES-256 SHA-512 L =1024 N =160 L =2048 N =224 L =3072 N =256 L =7680 N =384 L =15360 N =512 k =1024 f =160 k =2048 f =224 k =3072 f =256 k =7680 f =384 k =15360 f =512 DES가 1982년에깨졌다가정하면 80비트는 2018년안에깨진다고한다. 따라서키사이즈의선택은신중하여야한다. 다른안전도와키사이즈를가지는알고리즘이함께사용된다면이용가능성과운용가능성의이유에의하여충분한안전성이고려되어야한다. 따라서자료의안전한보존기한을고려하여알고리즘과키사이즈를선택해야한다. [ 표 4] 는추천하는알고리즘과최소키사이즈에대하여나타나있다. 실제소인수문제에기반을둔공개키암호시스템 (RSA), 이산대수문제에기반을둔공개키암호시스템 (DSA) 및타원곡선이산대수문제에기반을둔타원곡선암호시스템모두수년간정밀한분석이있어왔고, 그러한시스템공격방법은그기반이되는수학적문제를푸는것이라고알려져있다. 그러므로이제 기반을두는어려운문제 가무엇인지를분석하여야한다. 타원곡선이산대수문제는타원곡선의작은클래스인초특이타원곡선 (Supersingular elliptic curve) 일때상대적으로쉽다는것이알려져있다. 그러나이러한취약점은쉽게확인될수있으며, 그러므로쉽게피할 수도있다. 모듈러 p에서의소인수분해문제와이산대수문제는일반적으로 subexponential time 알고리즘이알려져있다. 타원곡선암호시스템과 RSA 및 DSA를깨는알려진최상의알고리즘으로그수행시간을비교하여보면 [ 그림 5] 와같다. ( 현재허용되는보안수준은 10 12 MIPS year이다.) RSA와 DSA가 1024비트의모듈러를사용하는반면, ECC 는 160비트모듈러로도충분함을보여준다. 더욱이키크기가증가할수록그비율은더욱증가한다. 예를들어, 300비트 ECC는 2000비트 RSA 또는 DSA보다더안전하다. 공개키암호시스템의효율성을이야기하기위해서는다음요소들을고려하여야한다. 첫번째는계산량이다. 공개키와비공개키를계산하는데에드는계산량을말한다. RSA의경우, 서명검증과암호화의속도를빠르게하기위해짧은공개키를사용한다 ( 비록이것이안전에영향을준다할지라도 ). DSA와 ECC는서명생성과암호화에서사전계산이많은부분을차지할수있다. 또한 ECC 연산에포함된모듈러연산을더빠르게수행하기위하 표 4. 암호시스템과최소키크기. Year Present 2015 2016 and beyond Symmetric key algs. (Encryption & MAC) TDES AES-128 AES-192 AES-256 TDES AES-128 AES-192 AES-256 Hash Alg. SHA-1 SHA-256 SHA-384 SHA-512 SHA-256 SHA-384 SHA-512 HMAC SHA-1( 80 bit key) SHA-256( 128 bit key) SHA-384( 192 bit key) SHA-512( 256 bit key) SHA-256( 128 bit key) SHA-384( 192 bit key) SHA-256( 256 bit key) DSA, D-H, MQV L=1024 N=160 L=2048 N=224 RSA k=1024 k=2048 Elliptic Curves f =160 f =224 물리학과첨단기술 March 2007 11
1.2 COMPARISON OF SECURITY LEVELS ECC and RSA & DSA 1 0.8 6000 5000 4000 표 5. 시스템매개변수와키크기. 시스템매개변수 ( 비트 ) 공개키 ( 비트 ) 비공개키 ( 비트 ) RSA n/a 1088 2048 DSA 2208 1024 160 Key Size (Bits) 0.6 3000 ECC RSA &DSA ECC 481 161 160 0.4 2000 표 6. 긴길이메시지에서의서명크기. 0.2 1000 서명크기 ( 비트 ) 0 0 10000 1E+08 1E+12 1E+20 1E+36 Time to Break Key (MIPS Years) RSA 1024 DSA 320 그림 5. 안전성의비교. ECC 320 여 F 2m 을사용할수도있다. ECC의경우 RSA 또는 DSA보다약 10배정도의빠른수행속도를보여준다. 그러나 RSA 의경우짧은공개키를사용한다면 ECC와비교할만하다. 두번째는키쌍과시스템매개변수저장에드는비트크기이며이는 [ 표 5] 와같다. 세번째는대역폭으로암호화된메시지또는서명을전송하기위한비트크기를말한다. 긴메시지를암호화하고서명하는데에는위의시스템모두비슷한대역폭을갖는다. 그러나공개키시스템의경우짧은메시지를전송하는데에자주사용된다 ( 예를들면, 대칭키암호시스템의세션키를전송하는데에사용됨 ). 완전한비교를위해본고에서는 2000비트의메시지에서명하는것과 100비트의메시지를암호화하는것으로가정한다. 위에서살펴본바와같이, ECC는계산량, 키크기및대역폭의관점에서타공개키암호시스템보다더효율적이다. 구현에있어이러한점은높은속도, 적은전력및코드크기를줄일수있음을의미한다. Blaze는안전한대칭키암호화스킴을위해요구되는최소키길이를연구하였다. 오늘날가장심각한위협요인에대처하기위해서는적어도 75비트이상이어야하고, 향후 20년간안전도를유지하기위해서는 90비트이상의키길이를가져 야한다. 현재 ECC가기본적인안전도를제공하기위해서는 n이적어도 160비트이어야하고, 중간정도의안전도를위해서는적어도 180비트이어야한다. 결론공개키암호는안전한정보보안서비스를제공하기위한기본적인도구로써오랫동안연구되어왔고현재는정보화사회의기본기술로서널리사용되고있고, 이에대한연구는앞으로도계속수행될것이다. 최근에는타원곡선에서정의되는페어링 (pairing) 연산의겹선형성 (Bilinearity) 을기반으로 ID 기반암화기법 [11] 에대한연구가활발하게진행되고있다. 이는전통적인인증서기반의공개키암호시스템의단점을보완 / 개선할수있는시스템으로써각광을받고있으며, 세계적으로널리연구되고있다. 따라서페어링을기반으로설계되는공개키암호에대한연구는앞으로도활발하게이루어질것이다. 전통적인공개키암호나새롭게각광받는공개키암호기술에대한연구는암호학의학문적발전을위해필요할뿐아니라, 정보화사회에서사회의안정을유지하기위해중요한도구로써반드시연구되어야한다. 참고문헌 [11] Dan Boneh, Matthew K. Franklin, Identity-Based Encryption from the Weil Pairing, CRYPTO 2001 (Springer-Verlag, 2001), pp. 213-229. 12 물리학과첨단기술 March 2007