RSA 키가 뚫리는 순간 — 다항식으로 약한 키를 인수분해하기

RSA는 왜 안전하고, 언제 안전하지 않나

인터넷 보안의 큰 축인 RSA 암호는 아주 단순한 사실 하나에 기대고 있어요. 두 개의 큰 소수를 곱하긴 쉬워도, 그 곱(n)만 보고 원래 두 소수를 다시 찾아내긴(인수분해) 엄청나게 어렵다는 거예요. 2048비트 RSA 키라면 정상적으로는 슈퍼컴퓨터를 동원해도 우주의 나이만큼 걸려요. 그래서 안전하죠.

그런데 '정상적으로 만들어졌을 때만' 안전해요. 키를 만들 때 게으름을 부리거나, 난수 생성에 문제가 있거나, 특정한 구조적 약점이 생기면 이야기가 완전히 달라져요. 이번 트레일 오브 비츠(Trail of Bits)의 글은 그렇게 '약점이 있는 RSA 키'를 다항식을 이용해 인수분해하는 방법을 다뤄요.

다항식으로 비밀을 복원한다고?

핵심 도구는 암호학에서 유명한 코퍼스미스(Coppersmith) 기법이에요. 이게 뭐냐면, '어떤 다항식 방정식의 해(근)가 충분히 작다면, 그 작은 해를 효율적으로 찾아낼 수 있다'는 수학적 마법이에요.

좀 더 풀어볼게요. RSA에서 우리가 모르는 건 소수 p예요. 만약 우리가 p의 일부 정보, 예를 들어 'p의 앞쪽 절반 비트'를 어떻게든 알아냈다고 해봐요. 그러면 모르는 부분(나머지 절반)은 상대적으로 '작은 미지수'가 돼요. 이 미지수를 변수로 둔 다항식을 세우고, 코퍼스미스 기법으로 그 작은 해를 찾으면 p 전체가 복원되고, 결국 키가 통째로 뚫려요.

이걸 가능하게 하는 내부 엔진이 격자 축소(lattice reduction), 특히 LLL 알고리즘이에요. 복잡한 다항식 문제를 '격자'라는 기하학적 구조로 바꾼 다음, 그 안에서 아주 짧은 벡터를 찾아 작은 해에 대응시키는 방식이에요. 이름은 어렵지만, 핵심은 '약간의 정보만 새어 나가도 그걸 지렛대 삼아 나머지를 전부 복원한다'는 거예요.

어떤 키가 위험한가

이런 공격이 통하는 건 키에 '예측 가능한 구조'가 있을 때예요. 대표적으로 두 소수 p와 q가 서로 너무 가깝게 생성된 경우(이때는 페르마 인수분해가 거의 즉시 통해요), 난수 생성기가 약해서 비트의 일부가 고정되거나 유추 가능한 경우, 혹은 임베디드 기기나 IoT처럼 엔트로피(무작위성)가 부족한 환경에서 만들어진 키들이에요. 실제로 과거에 라우터·스마트카드에서 대량으로 수집한 공개키들을 분석했더니 상당수가 같은 소수를 공유하고 있어서 줄줄이 인수분해된 사건(공유 소인수 사건, ROCA 취약점 등)도 있었어요.

한국 개발자에게

무서운 이야기처럼 들리지만 결론은 의외로 단순해요. 직접 키 생성 로직을 짜지 마세요. OpenSSL이나 검증된 표준 라이브러리가 시키는 대로 충분한 길이(최소 2048비트, 가능하면 RSA보다 타원곡선 ECC 사용)와 좋은 난수원으로 키를 만들면 이런 공격은 남의 일이에요. 정작 위험한 건 임베디드 펌웨어처럼 난수가 부족한 환경에서 부팅 직후 키를 생성하거나, 오래된 라이브러리를 그대로 쓰는 경우예요. IoT 제품을 다루는 분이라면 하드웨어 난수 생성기(TRNG)와 엔트로피 확보에 특히 신경 써야 해요.

암호는 '알고리즘이 강한가'보다 '구현과 키 생성이 빈틈없는가'에서 뚫리는 경우가 훨씬 많아요. 여러분이 다루는 시스템의 키는 어디서, 어떤 난수로 만들어지고 있나요? 한번 확인해볼 만하지 않을까요?