학문
헤라아레스
암호학에서 공인인증서에 사용되는 RSA
안녕하세요!
암호학에서 공인인증서에 사용되는 RSA 비대칭키 암호화가 소인수분해의 난이도를 기반으로 작동하는 원리는 무엇인가요?
3개의 답변이 있어요!
안녕하세요. 박재화 전문가입니다.
RSA는 아주 큰 두 소수를 곱해 만든 숫자를 이용하는 대표적인 공개키 암호 방식입니다.
두 소수의 곱은 계산하기 쉽지만, 그 결과만 보고 원래 두 소수를 찾아내는 소인수분해는 숫자가 충분히 크면 매우 어려운 특징이 있습니다. 이 두 소수를 이용해서 서로 수학적으로 연결된 공개키와 개인키를 만들게 됩니다. 공개키는 누구에게나 알려줄 수 있지만, 개인키는 소유자만 보관해야 합니다.
인증서에서는 보통 개인키로 전자서명을 만들고, 상대방은 공개키로 그 서명이 정말 해당 개인키에서 만들어졌는지 확인합니다. 공격자가 공개키만 가지고 개인키를 알아내려고 하면 사실상 매우 큰 수의 소인수분해와 관련된 어려운 계산들을 해결해야 합니다.
결국에는 RSA의 핵심이라고 하는 것은 곱셈은 쉽지만 거꾸로 큰 수를 소인수분해하는 것은 매우 어렵다는 계상상의 비대칭성을 이용하는 것입니다.
채택 보상으로 502베리 받았어요.
채택된 답변안녕하세요. 이수민 전문가입니다.
RSA의 바탕에는 계산의 비대칭성이 있어요. 큰 소수 두 개를 곱하는 건 초등학생도 할 수 있지만, 그 곱을 보고 원래 두 소수를 찾아내는 건 차원이 다른 문제예요. 수백 자리 숫자의 소인수분해는 슈퍼컴퓨터로도 우주의 나이만큼 걸려요. 한 방향은 쉽고 역방향은 사실상 불가능한 이 격차가 RSA의 자물쇠예요.
작동 방식은 이래요. 먼저 거대한 소수 p와 q를 비밀로 고르고, 둘을 곱한 N을 만들어요. 이 N과 암호화 지수를 묶은 게 공개키로, 누구에게나 보여줘요. 반면 복호화 지수는 p와 q를 알아야만 계산할 수 있는데, 이게 개인키예요. 누군가 나에게 비밀 메시지를 보낼 때는 공개키 N으로 정해진 거듭제곱 연산을 해서 암호문을 만들어요. 이 암호문을 풀려면 개인키가 필요하고, 개인키를 만들려면 N을 소인수분해해야 하니, 공개키가 만천하에 공개돼도 p와 q를 아는 나만 풀 수 있는 거예요. 자물쇠는 아무나 채울 수 있지만 열쇠는 나만 가진 우편함과 같아요.
공인인증서에서는 이 구조를 신원 확인에 써요. 인증 기관이 내 공개키에 전자서명을 해주면, 나는 개인키로만 만들 수 있는 서명을 문서에 붙여요. 상대방은 내 공개키로 그 서명을 검증하죠. 서명이 풀린다는 건 짝이 되는 개인키의 주인이 서명했다는 뜻이라, 소인수분해의 어려움이 곧 위조 불가능의 근거가 되는 거예요.
덧붙이면 이 안전성은 어렵다는 게 증명된 게 아니라 아직 아무도 빠른 방법을 못 찾았다는 경험적 사실에 기대요. 양자컴퓨터의 쇼어 알고리즘이 소인수분해를 빠르게 풀 수 있어서, 지금 암호학계는 양자 내성 암호로 갈아타는 준비를 하고 있어요 :)
안녕하세요. 김재훈 전문가입니다.
RSA 비대칭키 암호화는 두 개의 거대한 소수를 곱하여 만든 합성수를 다시 소인수분해하는 것이 현대의 컴퓨터 성능으로도 매우 오랜 시간이 걸린다는 수학적 난이도에 기반합니다. 암호화 과정에서는 이 합성수와 특정 정수를 이용해 공개키를 생성하여 데이터를 암호화하지만 이를 복호화하려면 원래의 두 소수로 만들어지는 비밀키가 반드시 필요합니다. 공격자가 공개키 정보만으로 비밀키를 계산해내려면 결국 거대한 합성수를 소인수분해해야만 하는데 현재의 기술력으로는 실질적인 시간 내에 이를 해결하는 것이 불가능에 가깝습니다 이러한 일방향 함수적 특성 덕분에 RSA는 공인인증서와 같은 디지털 서명 및 전자 거래 시스템에서 데이터의 비밀성과 신원 검증을 위한 안전한 핵심 기술로 활용되고 있습니다