오늘 끝나면
공개키 (RSA)
- ✓공개키와 개인키의 역할 차이를 설명한다
- ✓RSA가 키 교환 문제를 어떻게 완화하는지 이해한다
- ✓소인수분해가 안전성의 바탕이라는 감을 잡는다
실습 미션
미니 RSA에서 공개키로 잠그고 개인키로 풀어 원문이 돌아오는지 확인한다.
성공 조건
- □서로 다른 p, q를 골라 키쌍 생성
- □개인키로 복호해 원문이 돌아오는 것 확인
- □공개키로 풀면 실패하는 케이스 눌러보기
암호 & 보안 · 07
공개키
RSA
잠그는 열쇠는 공개, 푸는 열쇠는 나만 가짐. 1977년에 나온 발상임.
열쇠를 둘로 쪼갬
지금까지는 열쇠 하나로 잠그고 같은 열쇠로 풀었음. RSA는 그 열쇠를 둘로 쪼갬.
공개키는 잠그기만 되는 열쇠임. 개인키는 풀기만 되는 열쇠임. 둘은 짝 한 쌍임.
공개키로 잠근 건 공개키로 못 풂. 짝인 개인키로만 풀림. 잠그는 손과 푸는 손이 다른 거임.
공개키는 길에 뿌려도 됨
공개키는 이름 그대로 공개해도 됨. 게시판에 붙이든 명함에 박든 상관없음.
우체통으로 비유함. 투입구(공개키)는 길가에 열려 있어 누구나 편지를 넣음. 안의 편지를 꺼내는 문 열쇠(개인키)는 주인만 가짐.
누가 내 공개키로 잠가 보내면, 그 편지는 내 개인키로만 열림. 도청자가 공개키를 들고 있어도 못 엶. 잠금만 되는 열쇠라서임.
6강의 숙제를 풂
6강 문제 기억하셈. 비밀 열쇠를 미리 나눠야 하는데, 나누는 순간 도청당하면 끝이었음.
공개키는 이걸 한 방에 풂. 비밀 열쇠를 나눌 필요가 없음. 받는 사람이 공개키를 뿌려두면, 보내는 사람은 그걸 주워다 잠그면 됨.
잠그는 공개키는 누가 봐도 됨. 푸는 개인키는 받는 사람 손을 안 떠남. 그래서 처음 보는 사람과도 사전 약속 없이 비밀 통신이 됨.
비밀 열쇠를 먼저 나눠야 함
나누는 순간 도청 위험
공개키만 뿌리면 끝
나눌 비밀이 없음
직접 잠그고 풀어 보기
말로만 들으면 안 믿김. 오른쪽에서 진짜 RSA를 작은 숫자로 돌려 보셈.
소수 p, q를 고르면 공개키 (e, n)과 개인키 (d, n)이 자동으로 나옴. 숫자 메시지를 넣으면 공개키로 잠겨 c = m^e mod n 암호문이 됨.
이제 풀 차례임. 개인키로 풀면 원문이 그대로 돌아옴. 공개키로 풀어보기를 누르면 엉뚱한 값이 나옴. 잠그는 열쇠로는 못 푼다는 걸 눈으로 확인하셈.
n = p×q = 55 · φ = (p−1)(q−1) = 40
둘 다 눌러 보셈. 하나는 열리고, 하나는 안 열림.
안전성은 소인수분해에 기댐
공개키 n은 두 소수를 곱한 값임. 곱하는 건 1초임. 되돌려서 어떤 두 소수였는지 찾는 건 거의 불가능함.
5 × 11 = 55는 암산임. 근데 큰 숫자 던지고 “이거 어떤 두 소수의 곱이게?” 하면 막힘. 수백 자리면 슈퍼컴도 수십억 년 걸림.
개인키 d를 구하려면 그 소인수분해가 필요함. 공개키를 다 까놨는데도 안전한 이유가 이거임. 한쪽은 쉽고 반대쪽은 지옥인 수학에 안전성을 통째로 기댐.
Q. 내 공개키로 잠근 메시지는 누가 풀 수 있나?
개인키를 가진 나만 풀 수 있음. 공개키로는 잠그기만 되고 풀지는 못함. 그래서 공개키를 온 세상에 뿌려도 안전함 — 잠그는 권한과 푸는 권한이 처음부터 분리돼 있음.작은 수는 금방 풀림. 근데 수백 자리면 슈퍼컴도 수십억 년 — 그게 안전성의 뿌리임.