73은 유일한 쉘든 소수다

해커 뉴스[1]에서 일전에 이야기한[2] 페르마 도서관에 올라온 쉘든 소수에 관한 글[3]이 나와 있어서 좀 읽어봤다. 근데 와 은근 빡시네-_-

일단 빅뱅 이론이라는 시트콤이 뭔지 알아야 되는데, 뭐 여기 방문하시는 분들은 대부분 본 적이 있을 듯. 73번째 에피소드에 이런 내용이 있다. 재생시간 1분 50초

쉘든은 73이 21번째 소수이고 37은 12번째 소수이고, 7×3=21 등등의 성질을 이야기하는데, 이에 영감을 받아서 Byrnes 등은 이런 성질의 소수가 또 있는지에 대한 언급[4]을 하는 내용이다. 좀 더 뽀대나게 설명해보면,

n번째 소수를 p(n)이라 쓰고, 십진법으로 자리를 뒤집는 operator를 m(n)이라 쓰자. m(p(n))=p(m(n))을 만족하는 소수 p(n)은 거울성질(mirror property)을 가지고 있다고 정의하고, 십진법으로 자리수의 곱을 Π(n)이라 표기하면 Π(p(n))=n이 되는 소수 p(n)은 곱성질(product property)을 가지고 있다고 정의하자. 거울성질과 곱성질을 모두 가진 소수를 쉘든 소수라 하자. 쉘든 소수는 73이외에 더 있는가?

2015년에 제시되었으니 몇 년 된 추측인데, 딱 보자마자 직관적으로 성질을 만족하는 수가 별로 없을 듯해 보인다. 일전에 뒤집어 처음의 배수가 되는 이야기[5]도 했지만, 이런 교묘한 성질은 자리수가 늘어나면 늘어날수록, 조건을 만족하는 가능한 경우의 수가 급속히 줄어들 것이다.

근데 내 생각대로 얼마전에 그 증명[6]이 제시된 것 같다. 근데 위키피디아의 73 항목monthly에 있다고 나와 있는데, 실제로 monthly의 출판 목록[9]을 확인해보면, 앞뒤로 찾아봐도 이 기사[6]가 없다. 아놔… 이유는 모르겠음. 여하간 대충 그 내용을 봤는데, 뜬금없이 다음과 같은 부등식으로 시작한다.

17보다 큰 모든 x에 대하여 \displaystyle \pi(x) > \frac{x}{\log x}이 성립한다.

음?? 충분히 큰 수에 대해서는 성립하는줄 아는데, 17부터 부등식이 성립하는지 어떻게 알았지??? 물론 여기서 π는 prime counting function이다. 원문[6]에는 Rosser & Schoenfeld[7]를 보라고 돼 있던데, 직접보니, 큰 수들은 bound를 이용하고 작은 수들은 컴퓨터를 이용하여 직접 확인한 것 같다. 참고로 Rosser & Schoenfeld[7]의 앞부분에는 integration by part를 이용하여 오차항을 줄이는 재미있는 테크닉이 소개되어 있는데, 일전에 이야기한 내용[8]과 유사하다. ㅎㅎㅎ 어쨌든 이 부등식을 이용하여, 자리수에 9자가 많다고 가정해도 거울성질을 가진 소수는 1045를 넘을 수 없다는 것을 보인다.

일단 컴퓨터로 10억정도까지는 쉽게 커버가 가능하지만, 컴퓨터로도 1045은 좀 빡센 범위다. 이 정도 자리수의 모든 소수를 쉽게 슥슥 다루기는 쉽지 않다. PNT 등으로, 알려진 큰 소수들의 bound를 이용하여 n번째 소수의 범위를 좁히면 앞쪽의 열몇 자리 정도의 숫자가 결정된다. 10억 이상의 쉘든 소수가 존재한다면 만족해야 하는 여러가지 조건들을 이용하여 후보를 좁히는 것 같다. 그 뒤로 열라 재미없는-_- 계산노가다 이후 컴퓨터로 커버하여 확인한 것 같다.

여하간 그래서 쉘든 소수는 73밖에 없다는 거. 근데 개인적으로는 5318008이 최고라는 Raj의 의견에 동의함-_- ㅋㅋㅋㅋㅋ

.


[1] The Sheldon Conjecture (hacker news)
[2] 내 백과사전 새로 생긴 수학 사이트 두 개 2015년 9월 16일
[3] the Sheldon Conjecture (fermatslibrary.com)
[4] Byrnes, J., Spicer, C., Turnquist, A. (2015). The Sheldon conjecture. Math Horizons. 23(2): 12–15. doi:10.4169/mathhorizons.23.2.12
[5] 내 백과사전 거꾸로 뒤집어 처음의 배수가 되는 수 2011년 10월 30일
[6] Pomerance, Carl; Spicer, Chris (April 2019). “Proof of the Sheldon conjecture”. Amer. Math. Monthly.
[7] Rosser, J. B., Schoenfeld, L. (1962). Approximate formulas for some functions of prime numbers. Illinois J. Math. 6: 64–94.
[8] 내 백과사전 Euler–Maclaurin formula를 이용한 오차항 줄이기 2011년 1월 9일
[9] The American Mathematical Monthly (tandfonline.com)

8866128975287528³+(-8778405442862239)³+(-2736111468807040)³

오 마이 갓 대박뉴스다.

일전에 세 개의 세제곱수 이야기[1]를 했지만, 평범하게 잘 나가다가 갑자기 난이도가 확 어려워지는 케이스가 있다. 근데 방금 Gil Kalai 선생의 블로그[2]를 보니 33인 케이스가 풀린 모양이다. 그 해답은 바로

88661289752875283+(-8778405442862239)3+(-2736111468807040)3 = 33

헐…. Timothy Browning이라는 사람이 푼 모양인데, 나는 처음 듣는 이름이다. 위키피디아에 이름이 있는 걸 보면, 모르긴 해도 나름 유명한 듯??

당연히 맨땅에 헤딩해서 찾지는 않았을 터이고, 엘키스 선생의 경우[3]처럼 뭔가 트릭을 썼을 듯 한데, 방법이 궁금하구만. ㅋㅋ reddit 페이지[4]도 참고 바람.

.


2019.3.10
몰랐는데 74가 비교적 최근인 2016년에 풀렸었네-_-[5] 헐… 몰랐었음. 이로 인해 100이하의 값들 중에 풀리지 않은 값은 42 하나 남았다.

.


2019.3.11
오늘 블로그[2]를 다시보니 Andrew Booker라는 사람이 푼 것이라 한다. 그의 논문이 공개[6]되어 있다.

.


2019.3.27
quanta magazine Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33 March 26, 2019

.


2019.4.4
Andrew R. Booker, “Cracking the problem with 33”, arXiv:1903.04284 [math.NT]

.


[1] 내 백과사전 세 개의 세제곱수 2012년 6월 22일
[2] 8866128975287528³+(-8778405442862239)³+(-2736111468807040)³ (gilkalai.wordpress.com)
[3] Elkies, N. D. (2000) “Rational points near curves and small nonzero |x3 − y2| via lattice reduction”, arXiv:math/0005139 [math.NT]
[4] 33=8866128975287528^3+(-8778405442862239)^3+(-2736111468807040)^3 (reddit.com)
[5] Sander G. Huisman, “Newer sums of three cubes”, arXiv:1604.07746 [math.NT]
[6] CRACKING THE PROBLEM WITH 33 pdf 269KB

원심분리기 문제 The Centrifuge Problem

며칠전에 Mad Scientist 선생께서 ‘센돌이’의 역사에 대한 글[1]을 쓰셨던데, 재미있으니 일독을 권한다. ㅎㅎ 본인은 써 본적이 없지만, 아마 원심분리기가 현대 실험실 필수장비인 듯 싶다.

때 마침 유튜브의 Numberphile 채널[2]을 보니, 원심분리기 문제를 소개[3]하고 있었다. 음?? 이게 수학이랑 무슨 상관이지???? 재생시간 9분 17초.

검색해보니 조지아 공대 수학과 소속[5]인 Matt Baker 선생이 블로그[4]에 이 문제를 소개하고 있다. Iswar Hariharan이라는 암 연구자와 바베큐를 먹다가 들은 이야기라고 한다.

Mad Scientist 선생의 설명[1]에 자세히 나와 있지만, 원심분리기는 고속으로 회전시켜서 물질을 분리하는 장비인데, 배치한 시험관의 질량중심이 정중앙에 오도록 배치하지 않으면, 회전시 쏠리기 때문에 장비의 수명이 짧아진다고 한다. 질량중심이 중앙에 오도록 하는 배치가 가능할 때도 있고, 불가능할 때도 있는데, 예를 들어 원심분리기의 슬롯의 개수가 6이고 시험관의 개수가 4면 가능하지만, 시험관의 개수가 5면 불가능하다.

나는 처음에 Numberphile 영상[3]을 봤을 때, 당연히 원심분리기 슬롯의 개수가 n 이면, n과 서로소가 아닌 것만 가능한게 아닌가??? 라고 생각했다. 근데 슬롯이 12개일 때 7개의 시험관의 배치가 가능하다!!!! 헐-_-

Matt Baker 선생은 슬롯이 n개이고 시험관이 k개면, k와 n-k가 모두 n의 소인수의 합으로 표현가능할 때 가능하다는 conjecture를 제시하고 있던데, 아직 해결은 되지 않은 듯????

이 문제를 푼다면 원심분리기 제작업체는 가능한 많은 숫자를 커버할 슬롯의 개수를 찾아야 할 것 같다. ㅎㅎㅎ

뭐 여하간 원심분리기 돌리다보면 한번쯤 생각날 법도 한 문제 같은데, 별로 유명하지는 않은 듯???? ㅎㅎ

.


[1] ‘센돌이’의 은밀한 역사 (madscientist.wordpress.com)
[2] Numberphile (youtube.com)
[3] The Centrifuge Problem – Numberphile (youtube 9분 17초)
[4] The Balanced Centrifuge Problem (mattbaker.blog)
[5] Matt Baker’s Home Page (people.math.gatech.edu)

prime gap과 Jumping champion

정수론에서 prime gap과 관련된 썰-_-들이 많은데, 개략적인 정보는 일전에 올려둔 타오 선생의 강연 영상[1]을 참고하기 바란다.

여하간 주어진 n이하의 prime들 사이의 prime gap 중에서 출현 빈도수가 가장 높은 값을 jumping champion[2]이라고 부르는 모양인데, 나는 처음 듣는 용어다. 유래를 보아하니 역시나 잡기에 능한(?) 콘웨이 선생의 작품인 듯.[2] ㅋㅋㅋ

John Baez 선생의 구글 플러스[3]를 보니 jumping champion에 대한 이야기가 나오길래, 나도 블로그 포스팅 함 해봄. ㅎㅎㅎ 참고로 Mind the gap이라는 표현은 런던 지하철의 승강장과 지하철 사이의 틈을 조심하라는 표현인데, 일전에 이야기한 적[4]이 있다. ㅋ

극초반의 예외를 제외하면 jumping champion의 값은 6으로 고정되는데, 6의 특성상 충분히 이해가 되는 부분이다. 물론 점진적으로 prime density가 낮아지므로 평균적으로 prime gap이 넓어지고, 따라서 jumping champion의 값이 변해야 마땅한데, 언제 어떤 값으로 변할 건지가 관건이다. 여러가지 수치적 정보를 토대로 이를 추정하는 글[5]이 있는 모양인데, jumping champion이 6에서 30으로 변경되는 위치는 대략 다음 값으로 추정된다고 한다.

174270000000000000000000000000000000 = 1.7427 ⋅ 1035

헐… 또 천하에 쓸데없이-_- 큰 수가 나오는 게, 일전의 메르텐스 추측[6]이 생각나는구만. ㅎ prime density가 생각보다는 빠르게 떨어지지 않는 모양이다.

원래 연구[5]에서는 maple의 isprime 함수를 사용했다고 하는데, 사실 이 함수는 Miller-Rabin Test를 이용하므로 이론적으로 완벽하게 소수를 판정하는 함수는 아니다. 다만 10100이내에서 반례를 찾을 수 없다는 연구를 소개하는 사이트를 봤었는데[7], 도통 찾을 수가 없네…-_- 여하간 이 연구[5]에 영향을 줄 정도는 아닐 것이 확실하다.

최초 prime들의 곱을 Primorial이라 하는데, 왠지 느낌상 앞으로 jumping champion은 Primorial이 될 것 같은 느낌이 든다. 이걸 Hardy-Littlewood prime k-tuple conjecture를 가정해서 증명한 연구[8]도 있긴 하던데, 무슨 말인지는 하나도 모르겠음-_-

.


[1] 내 백과사전 타오의 prime gap 강의 2015년 4월 25일
[2] Jumping Champion (mathworld.wolfram.com)
[3] https://plus.google.com/+johncbaez999/posts/LpbzuUQaEsF
[4] 내 백과사전 새로운 런던 지하철 노선도 2011년 7월 6일
[5] Andrew Odlyzko, Michael Rubinstein & Marek Wolf (1999) Jumping Champions, Experimental Mathematics, 8:2, 107-118, DOI: 10.1080/10586458.1999.10504393
[6] 내 백과사전 메르텐스 추측과 리만 가설 2010년 3월 8일
[7] http://zariski.egloos.com/2382504
[8] D. A. Goldston, A. H. Ledoan, “The jumping champion conjecture”, arXiv:1102.4879 [math.NT]

Atiyah 선생의 리만 가설 증명?

트위터발 소문[1]에 따르면 Michael Atiyah 선생이 리만 가설의 증명을 발표할 거라는 이야기가 나오는데, 아무래도 이름값이 있으니 헛소리는 아닐 가능성이 높다. 한편 얼마전에 숄체 선생이 모치즈키 선생의 주장[2]에 반론을 제기[3]했던데, 이거이거 관전할만한 거인들의 진검승부들이 자꾸 나오니 쓸데없이 흥미진진하구만. ㅋㅋㅋ

.


2018.9.21
몰랐는데 Atiyah 선생의 나이가 생각보다 많구만. ㅎㅎㅎ 올해 89세라서 치매 안 걸리는 것만으로도 다행인 나이 같은데-_- 이렇게 눈에 띄는 업적을 남기는게 가능할까 싶은 생각도 든다. 디씨 인사이드발 소문[4]에 누가 mental trouble이 있다는 이야기를 하는데, 설마 싶어서 얼마전에 리우 데 자네이루에서 개최된 ICM 2018의 연설 영상[5]을 보니, 멀쩡해 보이면서도 내용이 횡설수설한게 정상이 아닌 듯해 보이기도 하다-_- 아무래도 이번 소문은 헤프닝으로 끝날 듯… ㅋ

.


2018.9.27
science Skepticism surrounds renowned mathematician’s attempted proof of 160-year-old hypothesis Sep. 24, 2018 , 5:15 PM

.


2018.9.29
Is there a way to discuss the correctness of the proof of the RH by Atiyah in MO? (meta.mathoverflow.net)

.


20191.1.12
대학신문 리만가설과 마이클 아티야 2018.11.04 04:49

.


[1] https://twitter.com/HLForum/status/1042670700652318720
[2] 내 백과사전 모치즈키의 abc 추측 증명에 대한 논란 2017년 12월 22일
[3] Quanta magazine Titans of Mathematics Clash Over Epic Proof of ABC Conjecture September 20, 2018
[4] 아티야의 HLF 강연에 대해 (gall.dcinside.com)
[5] Abel Lecture ICM 2018 — The future of mathematical physics: new ideas in old bottles, Michael Atiyah (youtube 1시간 25초)

중국판 ‘굿 윌 헌팅’

영화 ‘굿 윌 헌팅‘에는 정규 교육을 받지 않은 청소부 노동자가 현대수학의 난제를 풀어내는 장면이 나온다. 물론 영화의 핵심주제는 이게 아닌데, 수학전공자들은 영화가 전달하려는 메세지보다 영화 도중에 지나가는 칠판의 수식에 더 관심이 가게 된다-_-

YTN 기사[1]에 정규 고등수학교육을 받지 않은 택배 노동자 Yu Jianchun이 취미로 수학문제의 새로운 증명을 내 놓았다는 이야기를 봤는데, 제작년 기사인데 여태 몰랐네. ㅎ 기사 만으로는 증명의 구체적인 내용은 알 길이 없는데, mathoverflow에 약간의 정보[2]가 있다.

카마이클 수는 서로 소인 모든 base에 대해 Fermat’s little theorem의 역이 성립하는 합성수를 말하는데, 이 수가 무한히 많음이 증명되어 있다[3]고 한다. 몰랐는데 1994년에 풀렸다고 하니, 나름 비교적 최근에 해결됐구만.

이 무한성을 Yu Jianchun은 기존과 다른 방법으로 증명한 듯 하다. 증명을 쓴 종이의 일부가 CNN기사[4]에 나와 있는데, 중국어라서 본인은 모르겠지만 mathoverflow 댓글[2]에 이 부분을 누가 번역해 놓았다. 증명 전체를 영어로 번역하여 볼 수 있으면 좋겠는데 아쉽구만.

이번 결과는 (증명이 참이라는 가정하에) 수학계에서 이미 증명된 것을 다시 한 것이므로 매우 임팩트 있는 결과는 아니다. 게다가 Alford et al.[3]의 결과는 카마이클 수의 density까지 제시하고 있는데, 아마 Yu Jianchun의 증명은 모르지만 이보다 강력한 결과는 아닐 듯 하다. 그러나 그는 이번 증명을 인정받아서 crank[5]가 아니라는 걸 보였으니, 진짜 난제를 풀어 인정받기 위한 발판이 될 수 있을 듯 하다.

예전에 어느 환갑 넘으신 할아버지가 취미로 리만가설을 공부해서 뚫어보려고 나름 진지하게 연구하던게 생각나는데[6], 내용이 맞는지는 모르겠지만 결국 이 분도 지쳐서 포기하셨다. 리만가설은 좀 너무했고, 약간 덜 어려운 문제부터 풀고 인정을 받아서 도전했으면 지치지 않고 좀 나은 결과를 냈을지도 모를 일이다. ㅎ

재야에 숨은 현자 이야기는 언제나 흥미롭다. 일전에 Cleo의 이야기[7]도 했지만, 라마누전의 전례 때문에 이런 관련 이야기는 잊을만 하면 한 번씩 나오는 듯-_-

아마추어가 난제를 해결할 가능성에 관해서 Gowers 선생의 저서[8]에 나름 합리적으로 잘 설명하고 있다. 논리적으로는 아주 불가능하지는 않은 이야기지만, 현대수학의 대부분 영역은 기본적으로 난제의 이해까지 도달하는 데만 상당한 노력이 필요하므로, 실질적으로는 불가능하다. 그나마 필요한 배경지식이 상대적으로 적은 일부 정수론 문제에서 가능성이 있긴 한데, 이 조차도 선대에 해놓은 작업량이 나름 상당하므로 쉽지는 않을 것 같다. ㅎ

.


[1] YTN 취미로 풀었는데…어려운 수학문제 새로운 증명 제시 2016-07-18 21:51
[2] What did Yu Jianchun discover about Carmichael numbers? (mathoverflow.net)
[3] W. R. Alford; Andrew Granville; Carl Pomerance (1994). “There are Infinitely Many Carmichael Numbers”. Annals of Mathematics. 139: 703–722. doi:10.2307/2118576
[4] CNN China’s ‘Good Will Hunting?’ Migrant worker solves complex math problem 0328 GMT (1128 HKT) July 18, 2016
[5] 내 백과사전 공급중시론자와 크랭크 2011년 12월 6일
[6] 리만가설 증명/ 김정건 ( Proof of Riemann Hypothesis by JG Kim, 2007 ) (blog.daum.net)
[7] 내 백과사전 Cleo : 인터넷 수학 현자 2017년 6월 28일
[8] 내 백과사전 [서평] 아주 짧게 소개하는 수학 2013년 2월 26일

세 번째로 비이성적인 수

수학에서는 rational이 유리수라는 의미지만, 원래 ‘이성적인’이라는 의미도 있어서, 이런 말장난하는 짤방도 있다. ㅋ

i : 이성적이 돼!
pi : 현실을 보라구!

어느 블로거의 What is the 3rd most irrational number? The answer will surprise you! 라는 글[1]을 봤는데, 처음에 이 제목이 무슨 말인가 한참 생각했다. ㅎㅎㅎ Diophantine approximation에 관한 글인데 무척 재미있으니 일독을 권함. 일전에 이야기한 Liouville number[2]와도 아주아주 조금 관련이 있다. ㅋ

.


2019.9.17

.


[1] What is the 3rd most irrational number? The answer will surprise you! (extremelearning.com.au)
[2] 내 백과사전 리우빌 근사 정리 Liouville’s Approximation Theorem 2010년 3월 7일

[서평] 소수와 리만 가설 – 질서와 패턴을 찾고자 하는 이들의 궁극적 도전 대상

소수와 리만 가설 – 질서와 패턴을 찾고자 하는 이들의 궁극적 도전 대상
배리 메이저(저자) | 윌리엄 스타인(저자) | 권혜승(역자) | 승산 | 2017-06-27 | 원제 Prime Numbers and the Riemann Hypothesis

 


일전에 본 블로그에서 언급[1]한 스테인 선생과 메이저 선생의 그 책[2]이 번역서로 출간될 줄은 꿈에도 몰랐다. 웬 떡이냐. ㅋㅋㅋ 작년에 출간된 듯 한데, 인제사 발견해서 후닥닥 읽어봤다. ㅋ

국내에 John Derbyshire의 책인 Prime Obsession의 번역서[3]가 출간되어 있어, 관심있는 사람은 이미 대부분 읽어봤을 것이라 생각한다. 본인이 알기로 국내 대중서 가운데 리만 가설이 중심 주제인 책은 이 한 권 뿐이었던 걸로 알고 있는데, 번역되지 않은 책들 중에서는 리만 가설에 대한 대중서가 꽤 있는 듯 하다.

그러나 그런 책들은 대부분 비교적 역사적 관점에서 리만 가설을 설명하는 책인데 비해, 이 책은 수학적 배경이 적은 사람에게 리만 가설이 왜 중요한지에 대해 실제로 수학적 설명을 시도하는 책으로, 다른 대중서들과는 조금 방향성이 다르다. 근데 내가 보기에는 독자들이 가진 수학실력의 폭을 너무 크게 잡은 바람에 앞부분은 너무 쉽고, 갈수록 어려워져서 뒷부분은 너무 어려운-_- 요상한 책이 돼 버렸다. ㅋㅋㅋ

텍스트의 분량 자체는 그리 많지 않지만, 이리저리 찾아가면서 읽으면 나름 시간이 걸릴 듯한 책이다. 뭐 나는 수학에 별로 관심이 없어서-_- 초 대충 읽었다. ㅋㅋㅋ

뭐 여하간 책안에 적분, 로그, 시그마 등등의 수식이 등장하니 최소한 고교수학 정도의 실력은 있어야 볼만할 듯 하다. 수학에 좀 관심이 있는 고교생들은 좋아할 듯. ㅋ

 


[1] 내 백과사전 Barry Mazur와 William Stein의 새 책 2015년 11월 25일
[2] Prime Numbers and the Riemann Hypothesis (amazon.com)
[3] 존 더비셔 저/박병철 역, “리만 가설“, 승산, 2006

교과서적인 RSA와 심각하게 허술한 보안 상태인 QQ 브라우저

얼마전에 텐센트가 중국 기업 최초로 시총 5천억달러를 돌파했다는 뉴스[1]를 봤는데, 바이두, 알리바바와 함께 천하삼분지계를 노리는 세 회사 중에서 텐센트가 제일 잘 나가는 모양이다.

해커뉴스[2]에서 텐센트의 QQ 브라우저가 얼마나 보안에 취약한지에 대해 설명하는 arxiv의 글[3]을 봤는데, 와 진짜 대단하네-_- 텐센트가 중국 정부의 검열에 엄청난 기여를 하고 있는 것 같다. ㅎㅎ 시총 5천억달러의 위업이 무색해지는 순간이다.

내용[3]을 보니 QQ브라우저는 텐센트 서비스로 로그인 하는 순간에 IMEI, IMSI, 와이파이 맥주소, 와이파이 SSID, 안드로이드 ID, 방문한 모든 페이지의 URL 등등의 개인정보를 전송한다고 한다-_-

QQ 브라우저는 PRNG 알고리즘으로 AES를 쓴다고 하는데, 그냥 쓰는게 아니라 89999999이하의 난수를 생성하는 nextInt(89999999) 함수 앞에 문자열 10000000을 붙여 사용하여 엔트로피를 줄여 쓴다(즉, 원래 경우의 수인 2128보다 작게 줄여 쓴다)고 한다. 경우의 수가 작으면 그만큼 뚫기도 쉬워진다.

이 뿐만 아니라, QQ 브라우저가 쓰는 RSA 알고리즘은 겨우 128비트(!) 밖에 안 되는데, 합성수 245406417573740884710047745869965023463 을 쓰고 있다고 한다. 내가 가지고 있는 maple의 ifactor 함수[4]로 시험삼아 돌려보니 1초만에

245406417573740884710047745869965023463 = 14119218591450688427 * 17381019776996486069

이라고 바로 인수분해 된다-_- 1024비트 합성수도 불안하다고 난리치는 세상에 128비트라니… ㅋ

게다가 QQ 브라우저의 RSA 알고리즘은 완전히 교과서 그대로인 RSA (즉, textbook RSA)라서 padding이나 일체의 보완책이 없기 때문에 매우 뚫기 쉽다고 한다. RSA를 교과서 내용 그대로만 쓰는 경우에는 매우 취약하다는 건 처음 알았네-_-

비대칭 암호의 경우, 공격자가 암호장비와 복호장비가 별도로 확보되는 상황이 있는데, 암호장비에 적절한 평문을 넣어 공격하는 방법이 Chosen-plaintext attack이고, 복호장비에 적절한 암호문을 넣어 공격하는 방법이 Chosen-ciphertext attack(CCA)이다. 이 때, 적절한 암호문을 융통성있게 잘 넣어 보는 공격법이 Adaptive chosen-ciphertext attack이라고 하는데, 업계에서는 CCA2라는 약자로 부르는 것 같다. 이런 건 처음 알았음. ㅎㅎ

저자는 글[3]에서 CCA2를 이용하면 교과서적인 RSA가 얼마나 뚫기 쉬운지 이야기하고 있는데, 그 밖에도 알려진 다양한 공격법으로 뚫리는지에 대한 이야기를 하고 있다. 음… ㅋ

 


[1] 연합뉴스 텐센트, 中 IT기업 최초로 시가총액 5천억弗 돌파 2017/11/21 09:51
[2] Breaking Textbook RSA Used to Protect the Privacy of Millions of Users (hacker news)
[3] Jeffrey Knockel, Thomas Ristenpart, Jedidiah Crandall, “When Textbook RSA is Used to Protect the Privacy of Hundreds of Millions of Users”, arXiv:1802.03367 [cs.CR]
[4] ifactors (maplesoft.com)