RSA-240, 250이 깨졌다는 소식

Hhan댓글 5개

다들 아시는 RSA암호의 안전성 기반의 가장 기초인 소인수분해를 빨리 하는 챌린지인 RSA Factoring Challenge가 있다. 이 챌린지는 1991년에 시작되어 2007년에 이제 우리가 소인수분해를 잘 이해하는것 같다는 이유로 -_- 중단되었는데, 당연히 그 이후에도 계속 연구되었다. 기존 최고 기록은 2009년 Kleinjung et al.의 768bit의 자연수를 소인수분해하는 RSA-768. 이 문제는 2000 core-년 (즉 single core로 2000년정도) 정도의 연산시간에 해결했었음.

이번에 발표된 결과는 Boudot et al.의 결과로 RSA-240, 250, 즉 10진법으로 240, 250자리를 갖는 수들을 소인수분해한 것이다. 즉 각각 795, 829비트를 갖는 자연수를 1000, 2500 core-년씩 써서 소인수분해했다고 한다. 쓴 라이브러리는 Cado-NFS라고 하는데, 이들의 메일링리스트에서는 이 결과가 이미 작년 12월, 올해 2월에 각각 발표되었었나보다. 또 DLP-240도 3000 core-년에 해결한 모양. 이 결과는 2016년 발표된 DLP-768의 5300 core-년 해결보다 훨씬 빠르다. 이런것들은 완전 새로운 알고리즘인건 아니고, 오래전부터 써오던 NFS 알고리즘을 이리저리 변형하고 파라미터를 훨씬 잘 잡은것에서 나온것인가봄.

이 분야도 계속 어찌저찌 발전은 계속 하고있나보다. 여튼 현재 한국의 많은 암호시스템은 RSA-2048에 해당하는 파라미터를 쓰니 아주 안전하다 ㅎㅎ. 개인적인 생각으로는 고전컴퓨터가 이걸 깨는거보다 양자컴퓨터가 나와서 깨는게 더 빠를것같음.

arXiv의 #strike4blacklives

Hhan댓글 남기기

과학 논문들이 모이는 아카이브 arXiv.org에서 조지 플로이드 사건에 따른 최근의#BlackLivesMatter 을 응원하는 #ShutDownAcademia, #ShutDownSTEM 운동의 일환으로 어제 (6월 10일) 이프린트들을 올리지 않았다고 한다. 나는 CS/quantum 계열에서 주로 쓰는 scirate를 많이 보는데, 어제 논문들이 안올라와서 미국이 그냥 공휴일이겠거니 했는데 -_-.. 한국에 살다보니 아카데미아의 BLM에 동참하는 운동이 있는것도 처음 알았네. 그나마 연락하는 사람들이라고 해봤자 거의 아시안이니.. 뭐 어제 딱히 별 공부를 하진 않아서 어쩌다보니 동참한셈인가…….

아래는 arXiv.org에 올라온 공지.

#STRIKE4BLACKLIVES

arXiv staff is pausing business-as-usual to join scientists participating in the #strike4blacklives and #shutdownSTEM. There will be no announcement on the evening of Tuesday, June 9, 2020. Article submissions received at or after 14:00 ET Monday, June 8 and before 14:00 ET Wednesday, June 10 will be announced at 20:00 ET Wednesday, June 10. We encourage arXiv readers to use the time they would normally spend reading the daily announcement or submitting an article to instead read about racism and discuss how they will work in their own local and professional communities to address it. For more information, read our staff statement here.

arxiv.org, retrieved at June 11, 2020.

BLM의 의의에는 동의하고 지지하지만, 언제나 아시안들에 대한 차별은 외면받는것 같아 참 아쉽다. (많은 인터넷 커뮤니티는 이런 스탠스를 넘어서 왜 BLM을 지지해야하는가에 대한 의문을 품는것같다.) 유럽의 학회에서도 “너희 아시안들은 다들 똑같이 생겨서 구별이 안되네 ㅎㅎ”같은 말을 들어본적도 있고… 웃고 넘어가긴 했지만 참.. 그나마 다행인 것은 이론적 컴퓨터과학 (TCS, theoretical computer science) 학계에는 마이너리티에 대한 편견을 없애려는 노력이 되게 강한것 같다. 예를 들어 TCS for women이나 QueerCrypt같은 소모임이 큰 학회의 위성학회 등으로 열린다던가. 반대로 보면 그런 학회에마저도 앞서 말한것같이 차별적인 발언을 하는 사람이 있는거지만 -_-…

색약/색맹인들을 위한 기술들의 발전

Hhan댓글 남기기

The wall street journal에 따르면 많은 회사들과 앱들이 색약모드 등을 점점 지원하는듯 하다. 구체적인 예시로는 Zoom의 Leave meeting 버튼이 빨강/검정으로 되어있었는데 이를 구별하지 못하는 사람이 해당 버튼을 찾는데 한참 애를 먹었고, 이제는 빨간바탕에 흰 글씨로 바뀌었다고 한다. 검정-빨강을 구별못하는 경우가 있는지 처음 들어서 검색해보니 Colour Blind Awareness라는 사이트에서 색약/생맹이 종류가 굉장히 많고, 특히 Protanopia (1종색맹?)의 경우 검정-빨강을 구별하기 힘들어한다고 한다. 애플 등의 회사에서는 색약모드 등을 지원하는듯 한데, 긍정적인 변화인듯.

신호등도 구별이 안되는 경우가 있어서 위치로 구별한다는데, 멍때리거나 급한 상황에서는 착각할 수 있찌 않나 생각이 든다 -_-.. 돈이 좀 들더라도 천천히 바꿔야할것 같은데, 어떻게 진행되고 있는지 잘 모르겠네.

근처에서 색약인 사람을 본건 두 명 뿐이지만, 사실 이유가 없으면 말을 하고다닐 이유도 없는 것이니.. 통계를 찾아보니 위에 말한 Colour Blind Awareness에서 남자의 8%, 여자의 0.5%가 색약이라고 하네. 생각보다 엄청 많다. 아래는 같은 사이트에서 나온 색연필의 사진으로, 순서대로 Normal / Deuteranopia / Protanopia / Tritanopia의 시점.

에코백의 역설

Hhan댓글 남기기

비닐봉지보다 적은 환경파괴를 하기 위해서는 에코백을 131번정도는 써야한다는 중앙일보발 기사. 요점은 목화로 에코백을 만드는 과정이 석유로 비닐을 만드는 과정보다 훨씬 어렵고 환경 비용이 많이 들기 때문이라는 것. 예를 들어 목화 재배를 위한 토지, 비료, 살충제나 제품화과정에서의 물의 오염, 온실가스 등등. 찾아보니 2019년 중앙일보 영어기사에서는 텀블러에 대해서도 다룬적이 있는데, 이 경우 종이컵보다 적은 영향을 주려면 재질에 따라 15~39번정도는 사용해야한다고 한다. 같은 기사에 따르면 덴마크 환경보호국에서는 에코백이 7000~2만번정도는 사용되어야 비닐봉지보다 더 효율적이라고.

갑자기 2018년쯤 뉴욕에 학회 갔을 때 스타벅스에서 옆에앉은 아저씨가 플라스틱컵 쓰지말라고 환경 신경써야한다고 이런저런 얘기를 해준 기억이 나네 -_-ㅋㅋ 아저씨.. 뭘 써야할지 생각보다 어려운 문제인가봐요..

나는 사실 에코백을 환경을 위해서라기보단 학교에 갈 때 편해서 들고 다니긴 하는데, 이렇게 비효율적인지는 몰랐네.. 생전에 지구를 뜰 것 같지는 않으니 어떻게든 신경은 써야할 문제인듯.

3DSEN:닌텐도 패미컴 게임을 3D로 바꿔주는 에뮬레이터

Hhan댓글 남기기

3DSEN이라는 NES(Nintendo Entertainment System) 혹은 패미컴게임, 즉 엄청 오래된 옛날 2D게임들을 3D로 바꿔서 실행할 수 있는 에뮬레이터가 나온다고 한다.

긴 말로 설명하는것보다 다음 영상을 보는걸 추천.

3D SEN 영상

와 이게 어떻게 되는거지 -_-… 서커스의 불고리를 뛰어넘는걸 정면에서 보여주는게 압권인듯.

머신러닝으로 한건가? 에뮬레이터니까 아마 코드를 뜯어서 알아서 고쳐주는거지 싶다. 단순한 형체들은 그냥 두께만 주는것같고, 일부 형체들은 되게 세밀하게 나타나는걸로 봐서 이것저것 직접 손댄 오브젝트 + 자동적으로 3D로 바꾸는것이 합쳐진게 아닐까 싶다.

곧 스팀에서 구매가능하다고 한다.

Knuth Prize Winner: Cynthia Dwork

Hhan댓글 한 개

2020년 Knuth Prize의 수상자로 Cynthia Dwork이 선정되었다는 소식. 현재 하버드와 Microsoft Research에 소속된 Cynthia Dwork은 Differential Privacy, Non-malleability, Lattice-based cryptography, concurrent composition, proofs of work등을 제안하고 연구했다고 한다. 2017년 Gödel Prize도 Differential privacy를 소개한 공로로 받으셨던데 연구를 참 많이도 하셨네 -_-… ACM SIGACT 페이지에 설명이 잘 되어 있지만, 여기서는 위에 언급된 것들중 몇개에 대해 간단히 소개해보고자 한다.

계속 읽기 →

인터넷 소식들: 싸이월드 폐업, 스팀게임 규제

Hhan댓글 남기기
  1. 싸이월드가 폐업했다고 한다. [출처]

과거의 부끄러운 모습들과 꽤 근처까지도 흑역사나 감정의 쓰레기통으로 사용하던 곳인데, 앱 로그인이 잘 안되던건 한참 된것같은데 결국은 폐업했나보다. 그 흑역사들을 모아놓을정도로 정이 있진 않았지만, 한때 삶의 일부같은거였는데 안타깝네. 좀만 잘했으면 한국에서는 페이스북 위치정도는 유지하지 않았을까 싶은데..

2. 등급분류를 받지 않은 스팀게임들에 대해 게임물관리위원회가 규제를 하겠다고 한다 [출처]

옛날 만화가 한참 규제받던거랑 비슷한것같다. 찾아보진 않았지만, 지금은 만화류는 기껏해야 사후 규제인것같은데.. 어떻게보면 (대부분의 경우) 상품을 파는거니까 그럴수도 있다 싶지만..
한국은 대부분의 법이 사전에 허용된 것 이외에는 안되도록 만들어져있다고 들은적이 있는데 (전혀 정확하지 않음) 지금같은 변화의 시대에 그런 스탠스를 취하는게 맞는가 싶다. 당장은 스팀 게임 사놓고 못한것들을 한참 못하게될까 걱정이 더 와닿지만 -_-..

큰 숫자들 by Scott Aaronson

Hhan댓글 2개

이 글은 스콧 아론손(Scott Aaronson)이 블로그에 쓴 글 Big Numbers를 번역한 것이다. 아론손은 Festivaletteratura이라는 이탈리아에서 매년 열리는 축제에서 큰 수에 관한 이야기를 했고, 이를 다시 글로 정리했다고 한다. 이 글은 1999년 아론손이 스스로 쓴 글과도 많이 겹치는데, 집합론이나 논리학등 새로운 몇 부분을 추가했다고 한다. 가장 번역이 어려웠던 부분이다 -_-.. 하루를 꼬박 다 썼네. 혹시 이런쪽에 익숙한 분들중 자연스럽지 않은 부분을 발견하신 분은 말해주세요.

Festivaletteratura는 굉장히 특이한 문학축제인데, 문학 뿐만아니라 다양한 다른 분야의 사람들을 불러서 소규모 강연회를 개최하나보다. 신기하군..

계속 읽기 →

삼성의 Galaxy A Quantum, QRNG, and more

Hhan댓글 남기기

삼성에서 Galaxy A Quantum이라는 폰이 나온다는 소식. 사실 한국에서 이런 소식이 돈건 한참됐고, 이제 외신까지 뜨고있나보다.

앞선 글에서 말했듯 구글에서 조그마한 양자컴퓨터 만드는데 골골대는데 삼성이 외계인을 고문해서 양자컴퓨터를 폰에 넣었다! 이런건 아니고, 그냥 Galaxy A의 난수생성하는 부분을 QRNG (Quantum random number generator)로 대체했다는 말이다.

이 글에서는 1. 왜 QRNG가 유용한 기술인지, 그리고 더 나아가 2. 양자컴퓨터가 난수에 대한 어떤일을 할 수 있는지 살짝 언급해보고자 한다. 얼마전에 DC 수잘갤에 쓴 글을 다듬어서 씀.

계속 읽기 →

양자 스도쿠, 라틴 방진

Hhan댓글 남기기

다들 알다시피 스도쿠는 9*9 격자에서 1,2,…,9를 각 행,렬 그리고 작은 3*3 격자 9개에 모두 한번씩만 등장하게 적는 퍼즐이다. 심심할때 아래 처럼 굉장히 이상한… 스도쿠를 풀어보는데 정말 만든사람도 변태다 싶다 -_-

Buy 3D Sudoku logic puzzles from Any Puzzle Media
며칠 걸려 겨우 풀었던 스도쿠…

그리고 라틴 방진 (Latin square)는 스도쿠에서 3*3에 대한 조건을 뺀 훨씬 간단한 형태. 근데 얘네의 양자버젼이 존재한다고 한다! 양자 라틴방진은 2015년에 제안되었는데, 신기하게도 몇가지 응용도 있다 -_-!! 하지만 무슨말인지 잘 모르겠으니 패스. 그냥 세팅은 간단하다. 9*9격자의 각 점에 1,…,9의 숫자대신 \mathbb C^9 벡터들을 두되, 각 행/열 (스도쿠라면 3*3 사각형에도)의 벡터들이 orthonormal basis가 되도록 하는것.

그러니까 격자들에 벡터를 두고, 아래 묶인집합들이 항상 ONB가 되도록 하는것.

SudoQ — a quantum variant of the popular game 에서 발췌

이번에 올라온 논문은 스도쿠의 양자버젼은 SudoQ인데, 이런저런 재밌는 관찰이나 추측들이 제시된다. 스도쿠가 non-trivial SAT의 한 예시인데 NP-complete라서 흥미롭다네.. 몰랐던 사실 -_- 이전에 Sinkhorn이라는 방식의 iterative 알고리즘을 통해 스도쿠를 풀수있다고도 한다. 이것도 전혀 몰랐군.. 이런 방식의 알고리즘의 양자버젼을 만들고, 얘의 수렴성도 확인한것같다. (증명이 자명한건지 딱히 안적혀있다..)

이런저런 추측은 다음과 같다.

  1. 고전적으로 해가 없는 스도쿠는 SudoQ에서도 해가 없다.
  2. 고전적으로 해가 유일한 스도쿠는 SudoQ에서도 해가 그거뿐이다.

하지만 아쉽게도 정말 게임으로 즐길수는 없을거같다. 대신 sudoku code라는 error correction code의 양자버젼으로 쓸수 있을거라는 대안만 제시하고 끝.