Basic Cryptography 공개된암호화폐가안전한이유 Seokhwan Moon
Modular Arithmetic! 값을 " 로나눌경우아래와같은식이성립함! = " % + ' 이를아래와같이표현할수있음! ()* % = ' 여기서 % 은 modulus( 법, 모듈로 ) 라고불리우며 ' 는 residue( 나머지 ) 라고불리움 프로그래밍에서 % 기호와같은역할 >>> 10 % 7 3 모듈로 % 의세계에서가능한모든나머지값은아래와같음 Z - = {0, 1, 2,, (% 1)} 1
Modular Arithmetic 모듈로! 의세계에서두개의값이같은나머지를갖고있다면두수는 congruent ( 합동 ) 이라고하며아래와같이표현함 " $ (&'(!) 예 : 4 8 0 &'( 2 17 10 3 (&'( 7) Modular 연산은아래와같은성질을갖고있음 " + $ &'(! = " &'(! + $ &'(! &'(! " $ &'(! = " &'(! $ &'(! &'(! " $ &'(! = " &'(! $ &'(! &'(! 2
Modular Arithmetic Modular 연산에서도일반덧셈과곱셈연산처럼역수가있음 Additive Inverse ( 덧셈역원 ) a 와 b 가아래와같은성질을갖고있으면 a 와 b 는덧셈에서 ( 서로의 ) inverse 임 # + % 0 ()*+,) 일반덧셈에서 # + % = 0 이면 % = # 이며 b 는 a 의 additive inverse 라고함 Multiplicative Inverse ( 곱셈역원 ) a 와 b 가아래와같은성질을갖고있으면 a 와 b 는곱셈에서 ( 서로의 ) inverse 임 # % 1 )*+, 일반곱셈에서 # % = 1 이면 % = 2 3 = #42 이며 b 는 a 의 multiplicative inverse 이라고함 3
Caesar Cipher 각문자열을특정숫자만큼이동시켜서암호화 / 복호화 평문 : THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG 암호문 : QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD Plain text A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Value 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 이미지출처 4
Caesar Cipher Caesar 암호는 transition ( 치환 ) 암호의한종류로 modular 연산으로표현하면 +/- 연산으로표현할수있음 Plain-Text Plain-Text $ = & + ' ()* 26 k k $ = & ' ()* 26 Encryption Cipher-Text Decryption 5
One Time Pad 비슷하지만 더욱 안전한 암호화로 One Time Pad의 방식도 존재 이미지 출처 6
Symmetric Key Chipher Symmetric key( 대칭키 ) 암호를사용한암호방식에서는아래와같은특징을갖고있음 사전에키를나눔 암호및복호에사용하는키가같음 Secured channel 7
Modern Symmetric Key Cipher DES (Data Encryption Standard) IBM 에서개발되었으며 1977 년에미국에서공식적인보안표준으로지정 1999 년에 22 시간 15 분만에공개적으로암호를해독하는하드웨어를공개함 AES (Advanced Encryption Standard) DES 를보완하기위해개발되었으며 2001 년에미국에서공식적인보안표준으로지정 이미지출처 8
Asymmetric Key Cipher Asymmetric key( 비대칭키 ) 암호방식은공개키, 비밀키두개의키가존재함 Public key( 공개키 ) 암호방식이라고도불리움 공개키로암호화, 비밀키로복호화 Communication channel Public Key Private Key 9
Asymmetric Key Cipher 공개키는공개적으로배포 공개키배포자와통신을하고싶은자가이를이용해통신내용을암호화한뒤공개키배포자에게전송 공개키배포자는암호화된문서를비밀키를이용해복호화할수있음 10
Prime Number 양수 (positive integer) 는 1, 소수 (prime number), 그리고합성수 (composite number) 로이루어져있음 소수는 1 과자기자신만으로나누어떨어지는양수 예 : 2, 3, 5, 7, 11,... 두숫자 a 와 b 의최대공약수가 1 인경우서로소 (relative prime) 라고함 두숫자를모두나눌수있는양수는 1 밖에존재하지않음 특정양수가 (P 복잡도로 ) 소수인지를판단할수있는알고리즘 (AKS primality test) 이 2002 년에최초로발표됨 11
Fermat s Little Theorem 1640 년에수학자페르마가언급했음 1749 년에오일러에의해처음으로증명됨 정수론 (Number theory) 의기초에큰영향을줌 만약 p 가소수이고 a 와 p 가서로소이면 # $%& 1 )*+, # $ # )*+, 12
Euler s Theorem! " n 보다작으면서 n 과서로소인양수들의총개수 예 :! 12 = 4 1, 5, 7, 11 만약 m 과 n 이서로소이면! ) " =! )! " 만약 p 가소수면!, =, 1 Euler s Theorem 만약 a 와 n 이서로소일경우 / 0(2) 1 )56 " / 7 0 2 89 / )56 ", 오일러의정리는페르마의소정리를일반화함 13
RSA 비대칭키암호를쓴최초의암호중하나 속도가느린알고리즘이라많이쓰이기보다대칭키를서로주고받기위해많이쓰임 이미지출처 14
RSA 두개의서로다른큰소수 p 와 q 를지정한후 # = % ' 로정함 따라서 ( # = ( % ( ' = % 1 ' 1 RSA 에서는 p 와 q 는적어도 512bit, n 은적어도 1024bit 여야함 1 과 ( # 사이의자연수중 ( # 와서로소인 e 를지정 -. 1 01. ( # 를만족시키는 d 를지정 (e 의 multiplicative inverse) e 와 ( # 은서로소이기때문에 e 는 modulo ( # 의세계에서 multiplicative inverse 가무조건존재함 공개키 (public key) 를 (e, n) 으로지정하고비밀키 (private key) 를 d 로지정 비밀키는본인만갖고있고, 공개키는본인과통신하고싶은사람들이쓸수있도록공개함 15
RSA 보낼문자를 P, 암호화된문자를 C 라고하면, 암호화 # = % & '() * 복호화 % = # + '() * 16
Proof of RSA Decryption 복호화 :! "! " #$% & = ( ) #$% & " #$% & = ( ) " #$% & = ( )" #$% & 암호화정의 : C = ( ) #$% & Modular 연산특성 9 : #$% & = { 9 #$% & : #$% & } #$% & * % =, - & + 1 가성립하는자연수 k 가존재함 ( )" #$% & = 1 2 3 4 5 6 #$% & 1 2 3 4 5 6 #$% & ( #$% & 키의정의 : * % 1 #$% -(&) 오일러의정리 9 2 3 4 56 9 #$% & : ( =! " #$% & 17
Cracking RSA 컴퓨터로지수계산은빠르게처리할수있지만, 그의반대인로그계산 (log $ % &'( )) 은매우어려움 로그계산은자연수를인수분해하는방법만큼어려움 현재자연수를쉽게인수분해하는방법 (n 을가지고 p 와 q 를찾는것 ) 은존재하지않음 ( 복잡도 NP 에속함 ) 따라서공개된 (e, n) 으로문자를암호화시킬수는있으나비밀키없이이문자를복호화시키는것은매우어려움 RSA Factoring Challenge 에서상금을걸고 n 에서 p 와 q 를인수분해하는경연을 1991 ~ 2007 년까지진행 663 bit 으로된 n 을 2005 년 5 월에인수분해에성공했음 이를처리하는데사용한파워를싱글코어 2.2GHz 옵테론프로세서 (2003 년출시된서버용 CPU) 로환산했을시약 75 년이걸리는시간이필요 18
Semantic Security Perfect security 암호화된문자만가지고원래의문자에대한정보를전혀얻을수없는경우 Shannon 에의해 perfect security 를이루는것은불가능하다고증명됨 Perfect security 를이루기위해서는적어도암호키의숫자가만들어낼수있는모든문자열의길이보다많아야함 Semantic security (practically perfect security) 이론적으로완벽한암호알고리즘이아니라도컴퓨팅파워의한계에의해서공격자가실질적으로암호문을복호화시키는게어려울수있음 따라서 ( 특정암호알고리즘의취약점이암호키의크기뿐일때 ) 암호키의크기를늘림으로써알고리즘의복잡도를매우높일수있으면그알고리즘은현실적으로안전하다고정의함 19
Hash Function Hash function 은임의의크기를갖고있는데이터를일정한크기의데이터로변환시켜주는함수 특정데이터를 hash function 을이용해계산한값을 hash 또는 hash value 라고함 단암호학에서의 hash function은아래와같은특성을만족해야함 : h"#h $ = h라고했을때 h만가지고 m을알아내기어려워야함 $ ( 을가지고 h"#h $ ( = h"#h $ ) 를만족하는 $ ) 를알아내기어려워야함 h"#h $ ( = h"#h $ ) 를만족하는 $ ( 과 $ ) 를찾기어려워야함 이미지출처 이러한특성때문에 hash function 에값을넣으면랜덤한값이나오는것처럼보임 20
Wallet in Cryptocurrency 암호화폐의지갑주소는특이한글자로되어있음 예 : bc1qar0srrr7xfkvy5l643lydnw9re59gtzz wf5mdq 이는비대칭암호의공개키가포함된값 이공개키를이용하여 block 에기록되어있는화폐의주인임을증명 이공개키와페어를이루는비밀키가존재하며, 이비밀키를이용하여인증서를생성 공개키를이용하면인증서를증명할수는있지만비밀키를알아낼수는없음 이미지출처 21
Hash Function in Cryptocurrency Block chain 이라는말처럼각거래원장 (block) 은각각연결되어있음 Bitcoin 의경우는 Proof of Work 라는방식을통해새로생성할 block 을결정함 Bitcoin 에는지정된 target 이있음 새로운 block 을생성하려는사람은현재 block chain 에존재하는가장마지막 block 의 header 를이용해서 target 보다작은 hash 값을만들수있는값 (nounce) 를찾아내야함 이미지출처 22
Hash Function in Cryptocurrency 지정된값 ( 이전원장의헤더 ) 에 nounce 를추가해서특정값보다작은값을찾는일은간단하지않음 ( 랜덤값을만들어내는듯한 ) hash fucntion 의특성상집어넣은값과결과값에아무런관계가없어보임 하지만 nounce( 와이전원장의헤더 ) 를알고있으면이게맞는 nounce 인지확인하는작업은간단함 이렇게각 block 은그전 block 들의 header 를모두포함하고있기때문에, block chain 중간에있는 block 을수정하려면매우어려움 중간의 block 을수정하려면그이후에있는모든 block 들을수정해줘야함 하나의 nounce 를찾는것도어려운만큼, ( 수정할 block 이후에존재하는 ) 여러개의 block 들을수정하기전에원래의 block chain 은이미새로운 block( 들 ) 을추가함 23
Question 이미지출처 24