번역은 댓글이 안 달려서 재미를 잃고 접음 ㅎㅎ 대신 다른 주제로 글을 써봄


=====


밀레니엄 난제인 리만가설에는 10억의 상금이 걸려있다. 그런데 21세기 수학에서 가장 어렵고도 중요하다고 여겨지는 난제치고는 10억이 초라하게 느껴진다. (강남에 아파트 한 채 사기도 어렵다.) 10억을 버는 가장 어려운 방법이 바로 리만가설을 푸는 것이라는 농담이 있을 정도이니… 물론 리만가설을 해결하면 아벨상은 따놓은 당상이니 플러스 10억에 (필즈상은 상금이 1000만 원 수준) 이후에 초청강연 한 번에 천만 원 넘게 받을 테니 직간접적인 이익을 모두 합치면 10억보다는 훨씬 클 테지만 그래도 100억 이하이지 아닐까 싶다.


리만 가설보다 더 큰 상금이 걸려있는 수학문제가 있을까? 상금이라고 표현하기는 애매하지만, 이산로그(DL; Discrete Logarithm)라는 문제가 있다. Finite cyclic group $G$와 그의 generator $g$에 대해 $h \in G$가 주어져 있을 때 $g^n = h$가 되는 자연수 $n$을 찾는 간단한 문제다. $(Z_p, +)$처럼 이산로그가 쉬운 group도 존재하지만, 일반적으로는 효율적인 알고리즘이 알려져 있지 않다 [1]. $(Z_p^{\times}, \times)$만 되어도 아직 알려진 다항시간 알고리즘이 없다. 그리고 소인수분해와 함께, 이산로그는 우리가 매일 사용하고 있는 암호시스템들의 초석이다. 이산로그를 효율적으로 해결할 수 있게 되면, 우리는 기존 암호시스템들을 폐기하고 인터넷보안 체계를 재정립해야 한다.


그래서 이산로그에는 얼마의 상금이 걸려있냐면… 최소 백만 비트코인, 현재 시가로 50조 원 정도이다. 사실 일반적인 인터넷 뱅킹 시스템은 핸드폰 인증이라던가 좀 다른 종류의 안전장치들이 있어서 이산로그를 푼다고 마음대로 할 수는 없다. 그런데 비트코인은 탈중앙화를 철학으로 가져가면서, 온전히 암호학에 안전성을 기반하고 있다. 비트코인도 시간이 흐름에 따라 추가적인 안전장치가 생겼지만 [2], Satoshi가 채굴한 것으로 보이는 초창기 백만 비트코인은 Satoshi가 자취를 감추면서 2009년 1월부터 10년 넘게 거래 없이 묶여있게 되었고, 이산로그만 해결할 수 있으면 내 마음대로 사용할 수 있다.


사실 일반적인 이산로그 알고리즘을 고안할 필요도 없다 [3]. 비트코인이 사용하고 있는 타원곡선인 Secp256k1 위에서의 이산로그만 풀면 된다. Secp256k1는 아래 16진법으로 표기한 (a,b,p,g1,g2)에 대해 타원곡선 y^2 = x^3 + a x + b (mod p)이 이루는 Group을 사용하고, (g1, g2)를 generator로 사용한다.


a = 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798

b= 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

g1 = 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798

g2 = 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8


심지어 더 나아가 알고리즘을 고안할 필요도 없이 하나의 instance에 대해서 풀어도 각각 50 비트코인이 주어진다 [4]. 비트코인의 첫 번째 블록의 채굴보상인 50 비트코인은 Secp256k1 위에서 아래 $h = (h1, h2)$에 대해 이산로그를 풀면 내 마음대로 쓸 수 있다.


h1= 96B538E8 53519C72 6A2C91E6 1EC11600 AE139081 3A627C66 FB8BE794 7BE63C52

h2= DA758937 9515D4E0 A604F814 1781E622 94721166 BF621E73 A82CBF23 42C858EE


50 비트코인. 그러니까 시가로 27억이다. 이 어처구니없는 산수문제 하나에 밀레니엄 난제 상금과 아벨상 상금을 합친 것 정도의 상금이 걸려있다.


=====


[1] Shor’s algorithm과 같은 양자알고리즘 제외.

[2] P2PK에서 P2PKH로 바뀌었다. P2PKH 하에서는 SHA-256이라는 해시함수(Cryptographic Hash Function)의 역상을 찾는 문제까지 해결해야 한다.

[3] 사실 일반적인 이산로그를 효율적으로 푸는 것은 불가능하다는 결과가 있다. Victor Shoup의 "Lower bounds for discrete logarithm and related problems"

[4] 당시에 채굴보상은 50 비트코인이었는데, Satoshi가 의도적으로 채굴 시에 여러 지갑주소로 받은 듯하다.