일단 1/2^128은 절대 일어나지 않는 확률이다.


꼬우면 1/2^256으로 낮춰도 된다. 1/2^256 확률의 사건은 절대 일어나지 않는다.


슈퍼컴퓨터가 1초에 100억번이 넘는 수를 조사해도 다 조사하려면 10^21년 걸린다. 2^256을 다 조사하려면 10^59년이 걸린다.


우주 나이가 100억년 따리인데, 1/2^256의 확률의 사건은 우주가 멸망할때까지 일어나지 않는다는것만 알아둬라.


본론으로 들어가서, 현대암호는 소수를 기반으로 하고있는데, 소수가 크면 클수록 안전성이 올라간다는건 옆집 누렁이도 아는 사실이다.


그래서 안전한 암호를 만들려면, 큰 소수를 찾아야 하는데, 2^128보다 큰 소수를 찾는 알고리즘이 뭘까? 한번10초 정도 고민해보고 밑 줄을 읽어 보길 바란다.








혹시 2부터 시작해서 소수인지 아닌지 체크하면서, 2^128까지 다 조사를 했다고 생각했는가?


만약 그렇다면 지금 마우스를 잡고 있는 오른손으로 자신의 뺨을 때려라. 두번 더 때려라.


위에서 슈퍼컴퓨터로도 10^21년이 걸린다고 이야기했다. 하나씩 조사하는것만큼 최악의 알고리즘은 없다.


2^128보다 큰 수를 아무거나 찍은 다음에 소수인지 체크하는 방법을 여러번 반복한다고 생각했다면 대충 맞았다.


그런데 소수의 정의를 생각해보면 그 숫자보다 작은 소수를 모두 구한다음에, 각각의 소수가 그 숫자를 나누는지 확인해봐야 할 것만 같다.


사실 맞는 말이다. 어떤수가 소수인지 '정확하게' 판별하는 방법중에 저 방식보다 유의미하게 효율적인 알고리즘은 없다.


하지만 이 방법을 하려면 아까 말했듯이 2부터 하나하나 다 조사해야한다. 그러면 우주가 멸망해도 큰 소수를 찾을수 없다.


대신, '정확하지 않게' 소수인지 판별하는 방법은 꽤 빠르게 할 수 있다.


여기서부터 수학이야기가 나올 것이다. 똥꼬에 힘 꽉주도록.





일단 5^128을 어떻게 계산할까?


단순하게 생각하면 5를 128번 곱하면 된다. 그렇다면 5^(2^128)은 어떻게 구할까?


5를 2^128번 곱한다고 생각했다면 자신의 뺨을 신나게 때려라.


정답은 5를 128번 제곱하는 것이다. 그러면 5, 5^2, 5^4, 5^8 ..... 이런 식으로 제곱하면 128번만에 구할 수 있다.


이 방법처럼, 5^100을 구하는 방법은 5^64 , 5^32, 5^4 만 알면 된다. 세 수를 곱하면 5^100이니까.


이 방법을 Fast exponentiation이라고 하고, 대략 x^m 을 log(m)만의 계산으로 구할 수 있다.


물론 현재는 이것보다 더 빠른방법이 있다. 이제 우리는 어떤수에 지수연산을 존나 빠르게 구할수 있다는걸 알았다. 다음은 소수에 관한 정리이다.





페르마 소정리에 따르면, 임의의 수 a와 소수 p에 대해서, a^(p-1) 을 p로 나눈 나머지는 1이다.


즉, 3^18을 19로 나눈 나머지는 1이라고 계산하지 않고 알수있다.


또한 83^122을 123로 나눈 나머지는 1이다. 이는 즉 123이 소수임을 의미한다.







미안한데 123은 소수가 아니다. 123은 3의 배수다. 윗 줄에서 고개를 끄덕끄덕거리면서 내려온 사람은 마우스 휠을 내리던 오른손으로 자기 뺨을 때려라.


지식은 누가 떠먹여주는게 아니라 스스로 의심하면서 챙기는것이다.


페르마의 소정리는 어떤수 a와 p에 대해서, a^(p-1)을 p로 나눈 나머지가 1이라고 해서 p가 소수인건 아니다.


그럼 소수인지도 모르면서 왜 페르마 소정리를 꺼냈냐고? 좀 기다려봐라.


해법은 a를 계속 바꾸는 것이다. 만약 p가 찐 소수라면, a를 아무리 바꿔도 1이 나오겠지.


p가 찐소수가 아니라면, a를 바꾸면 1이 아닌 다른 수가 나올 수 있다는 것이다.


83^122는 123으로 나누면 1이 나오지만, 2^122나 3^122는 123으로 나누면 1이 안나온다.


p보다 작은 숫자 a를 아무거나 갖고와서 a^(p-1)을 p로 나눈 나머지가 1인지 확인하고, 다시 아무숫자를 갖고와서 또 확인하고... 이걸 반복하면 된다.


이런식으로 p가 소수가 아닐 확률을 계속 낮출 수 있다. 


보통 p가 찐 소수가 아닌데, a^(p-1)을 p로 나눈 나머지가 1이 나올 확률이 1/2보다 작으니, 128번 반복해서 전부 1이 나오면 p가 소수가 아닐 확률은 1/2^128보다 작아진다.


불안하면 256번 반복해도 된다. 지수연산은 존나 빠르니까, 빠른시간안에 p가 소수가 아닐 확률은 1/2^256보다 작아질수 있다.


사실 그 확률이 1/2보다 작지 않은 숫자가 존재하긴 한다. 이런 수를 유사소수라고 부른다. 하지만 유사소수는 개수가 훨씬 적다.


결론적으로 보통의 소수를 찾을때, 여러번 반복하면 우리가 원하는 만큼 소수가 아닐 확률을 낮출수 있다는 것이다.


이 판정법을 Fermat primality test라고 부른다. 물론 현재는 유사소수 문제도 해결한 소수판정법이 있다. 더 알고 싶다면 miller-rabin test를 검색하도록.





아참, 그리고 알만한 사람은 알겠지만, 소수는 숫자가 커질수록 개수가 적어진다.


따라서 합리적인 의심으로 원하는 만큼 큰 소수를 찾으려면 엄청난 삽질을 해야되지 않을까라고 생각할수 있다.


가우스의 소수정리에 따르면, x이하의 소수의 개수는 대략 x/log(x)이다.


즉 2^128과 2^129사이에서 아무숫자나 뽑았을때, 그 숫자가 소수일 확률은 1/128이라는 것이다. 1/2^128에 비하면 선녀 같은 확률이다.


대충 2^128보다 큰 수를 아무렇게나 128개정도 뽑고 전부 소수판정을 해보면 소수가 있을 수 있다는 이야기다.






마무리를 어떻게 해야될지 모르겠는데, 요즘쓰는 타원곡선암호(ECC)에 대해서, 미국국가안보국(NSA)은 384-bit key로 최고기밀암호를 보호하고 있다.


물론 타원곡선암호가 RSA에 비해서 훨씬 안전해서 작은 소수를 써도 되는것이다. RSA가 384-bit key ECC와 비슷한 안전성을 가질려면 7680-bit key를 써야한다.


즉 ECC는 2^384 크기의 소수만 뽑으면 되는데, RSA는 두 소수의 곱으로 이루어진 암호이다보니 2^3840 크기의 소수를 두개 뽑아야한다.


음... 대신 RSA는 저지랄을 해도 ECC보다 훨씬 빠르다. 소수만 잘 찾으면, 속도면에서 RSA를 이길 방법은 없다.


그래도 3000bit넘어가면 소수찾는것도 빡세고, 저장용량도 많이 차지하니, 저장 용량 적은 ECC도 RSA보다 나은게 많다.


아직도 암호학자들은 RSA가 낫네 ECC가 낫네로 피터지게 갑론을박중이다.


마무리를 어떻게 해야할지 모르겠네 작성자는 작년에 전국암호공모전에 논문을 냈는데 이딴것도 논문이라면서 파쇄기에 넣어지고 참가상으로 칫솔살균기를 받았다.