오늘 끝나면
공개키 (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. 내 공개키로 잠근 메시지는 누가 풀 수 있나?
개인키를 가진 나만 풀 수 있다. 공개키로는 잠그기만 되고 풀지는 못한다. 그래서 공개키를 온 세상에 뿌려도 안전하다. 잠그는 권한과 푸는 권한이 처음부터 분리돼 있기 때문이다.작은 수는 금방 풀린다. 그런데 수백 자리면 슈퍼컴퓨터도 수십억 년이 걸린다. 그게 안전성의 뿌리다.