RSA-240 역대 최대 암호키 해독… 3500만 코어시간 소요, 양자컴퓨터 위협 예고

795비트·240자리 RSA 키 인수분해 성공

암호화는 디지털 기기로 수신, 저장, 전송하는 데이터 보호에 사용됩니다. 정부는 기밀 정보, 기업은 영업 비밀, 개인은 사생활 보호에 씁니다.

거의 모든 암호 기술이 긴 문자열로 온라인 데이터 안전 지킵니다. 가장 대중적 암호 형태는 RSA 암호학입니다. 큰 정수 인수분해 어렵다는 사실 기반입니다.

RSA는 공개키와 개인키 포함하는 비대칭 암호 알고리즘입니다. 공개키엔 두 큰 소수 곱인 숫자 포함. 개인키는 같은 두 소수에서 유도. 키 크기 2배·3배 되면 암호 강도 기하급수적 증가.

현대 하드웨어 대비 암호 보안성 보여주기 위해 RSA 연구소가 반소수(두 소인수만 가진 수) 목록 공개하고 원래 소인수 찾기 도전 과제 냈습니다. 지금까지 54개 목록 RSA 숫자 중 20개 해독됐습니다.

최근 프랑스 컴퓨터과학 자동화 연구소(INRIA) 연구팀이 240자리 십진수, 795비트 크기 RSA-240 인수분해 성공했습니다. 지금까지 해독된 최대 암호키입니다.

이전 기록 2009년 RSA-768(768비트, 232자리)였습니다. RSA-240이 RSA-768보다 크지만 연구자들은 이전 기록보다 더 빠르게 소인수 얻었습니다.

참고: 795-bit factoring | Wikipedia

계산 시간

소인수 분해 외에도 RSA-240 이산로그(discrete logarithm)도 계산했습니다. 정수 인수분해와 이산로그 두 기록이 같은 소프트웨어·하드웨어로 함께 깨진 최초 사례입니다.

두 계산 모두 수체 체 알고리즘(Number Field Sieve)으로 수행, 오픈소스 소프트웨어 CADO-NFS 사용.

RSA-240과 소인수들

정수 인수분해 약 800만 코어시간, 이산로그 계산 2,700만 코어시간 걸렸습니다. 총 계산 시간은 단일 컴퓨터 코어(2.1GHz 인텔 제온 골드 6130) 3,500만 시간, 즉 4,000년 실행과 동등합니다.

계산량 기준 RSA-240 해독은 RSA-768보다 2.25배 어렵습니다. 동일한 하드웨어 쓰고 예상 3배 빠르게 결과 얻었으므로, 가속은 지난 10년간 다양한 알고리즘 개선 덕분입니다. CADO-NFS 구현 크게 개선됐습니다.

이 계산들은 현대 컴퓨터 보안 위협 안 됩니다. 오늘 컴퓨터 쓰는 RSA 키는 1024~4096비트 더 크기 때문. 하지만 양자 컴퓨터 출현이 상황 근본적으로 바꿀 수 있습니다.