RSA 암호는 깨질 것인가?

보안에 관심이 있다면 RSADiffie–Hellman 키 교환에 대해 들어보신 분들이 있을 것이다. RSA는 소인수분해가 어렵다는 사실을 이용하고 있고, Diffie–Hellman 키 교환은 Discrete logarithm을 찾기가 어렵다는 사실을 이용하는 것으로 알고 있다.

근래에 Antoine Joux라는 암호학자가 발표한 두 개의 논문[1,2]이 사람들 사이에서 꽤 화자되고 있는 모양인데, 본인은 내공이 모자라서-_- 직접 읽지는 못하겠다. L-notation도 여기서 처음 봤다ㅠㅠ 이와 관련해서 대중적 강연이 얼마전에 열린 컴퓨터 보안 컨퍼런스 Black Hat에 발표된 모양이다. 그런데 이 내용이 꽤나 임팩트가 있는 모양. 본인도 pdf 포맷의 프레젠테이션 자료[3]를 누가 소개[4]했길래 대충-_- 보았다.

잘은 모르겠지만 Antoine Joux라는 이 친구가 characteristic이 작은 field에서 Discrete logarithm을 빠르게 계산하는 어떤 비약적 업적을 이룬 듯 하다. 잘 모르긴 해도 알고리즘이 점점 향상되면 RSA 암호화도 꽤 위험한 수준에 이를지 모른다는 추측성 글[5]도 있다. 헐…. RSA가 무용지물이 될 것인가. 흥미롭긴 하다.

이런 위험을 진작에 간파해서인지 점점 더 많은 시스템과 프로그래밍 언어가 아직은 보다 안전한 타원곡선 암호화를 지원하는 추세인 듯 하다.

국내 인터넷 뱅킹에서는 SEED 알고리즘을 쓰는 걸로 알고있는데, 본인은 뭐 잘모르긴 해도 타원곡선 쪽으로 우리도 슬슬 준비해야 하는 거 아닌가 모르겠다. ㅋ

 


2017.10.19
해커뉴스[6]에 mathoverflow[7]의 흥미로운 질문이 올라와 있던데, 질문의 내용을 거의 이해 못했지만-_- 어쨌든 질문자는 강력한 수치적 증거가 있다고 한다. 수학적인 증명이 어렵다 할지라도 어쨌든 factoring의 트릭의 한 종류로서 해커들이 유용하게 이용할 수 있을지도 모른다.

 


[1] Antoine Joux (2014) “A New Index Calculus Algorithm with Complexity L(1/4+o(1)) in Small Characteristic”, Selected Areas in Cryptography — SAC 2013, pp 355-379, DOI:10.1007/978-3-662-43414-7_18
[2] Razvan Barbulescu, Pierrick Gaudry, Antoine Joux, Emmanuel Thomé (2013) “A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic”, arXiv:1306.4244 [cs.CR]
[3] https://www.isecpartners.com/media/105564/ritter_samuel_stamos_bh_2013_cryptopocalypse.pdf
[4] The Factoring Cryptopocalypse by Lucb1e
[5] MIT Technology Review Math Advances Raise the Prospect of an Internet Security Crisis August 2, 2013
[6] https://news.ycombinator.com/item?id=15504051
[7] Conjecturally unsafe RSA primes p=27a^2+27a+7 in mathoverflow

Advertisements

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중