RSA 키의 '반팔' 약점: 다항식으로 비밀키가 뚫린다

RSA의 안전성은 두 큰 소수의 곱 N을 인수분해하기 어렵다는 가정에 기댄다. 하지만 키 생성 과정에서 한쪽 소수의 일부 비트가 예측 가능하거나 노출되면(이른바 '반팔(short-sleeve)' 키) 이야기가 달라진다. Trail of Bits는 Coppersmith의 다항식 기법과 LLL 격자 축소를 이용해 이런 키를 효율적으로 깨는 원리를 정리했다. 핵심은 소수 p의 상위 절반가량 비트만 알면, 나머지를 '작은 근(root)을 찾는 다항식 문제'로 환산해 N을 다항 시간 안에 완전히 인수분해할 수 있다는 점이다. 무차별 대입이 아니라 키에 숨은 수학적 구조를 파고드는 공격이다. 실무 시사점은 분명하다. 약한 난수, 결함 있는 키 생성 라이브러리, 하드코딩된 패턴은 키 길이가 2048비트여도 보안을 무의미하게 만든다. 직접 구현 대신 검증된 라이브러리를 쓰고, 엔트로피 소스와 키 생성 과정을 반드시 점검하라.