오늘 끝나면
양자 위협
- ✓양자 위협의 핵심 문제를 한 문장으로 설명한다
- ✓오른쪽 실습에서 양자이 어떻게 움직이는지 관찰한다
- ✓다음 강의와 이어지는 한계를 말할 수 있다
실습 미션
쇼어 알고리즘 — 양자컴퓨터가 RSA를 깨는 날 이 문장이 실제로 무슨 뜻인지 실습에서 한 번 손으로 확인한다.
성공 조건
- □실습의 기본값을 먼저 관찰
- □입력값이나 모드를 한 번 이상 바꿔 결과 비교
- □왜 결과가 바뀌었는지 한 문장으로 설명
암호 & 보안 · 19
양자
위협
양자컴퓨터의 쇼어 알고리즘은 RSA를 깸. 지금 안전한 게 미래엔 안 안전함.
공개키의 안전 = 어려운 수학 문제
RSA·디피-헬만 같은 공개키 암호는 딱 하나에 목숨을 걸고있음. “이 수학 문제는 풀기 너무 어렵다”는 가정임.
RSA는 큰 수 소인수분해가 어렵다는 데 기댐. 두 소수를 곱하긴 쉬운데, 그 곱을 다시 두 소수로 쪼개긴 지옥임. 디피-헬만은 이산로그가 어렵다는 데 기댐.
고전 컴퓨터로 2048비트 키를 쪼개려면 우주 나이를 써도 모자람. 그래서 안전한 거임. 근데 이 안전은 “아직 빠른 방법이 없다”는 데 얹혀 있을 뿐임.
큰 수 소인수분해
두 소수의 곱 쪼개기이 어렵다
이산로그
거듭제곱의 지수 되찾기이 어렵다
곱하긴 쉽고 · 쪼개긴 어렵다
왜 소인수분해가 그렇게 어려운지 감을 잡아보셈. 핵심은 일방통행임.
61 × 53 = 3233은 1초컷임. 근데 거꾸로 3233만 주고 “무슨 두 소수의 곱이냐”고 물으면? 하나하나 나눠봐야 함.
작은 수면 금방이지만, 수가 수백 자리로 커지면 후보가 천문학적으로 불어남. 고전 컴퓨터엔 지름길이 없어서 사실상 못 풂. 이 비대칭이 자물쇠의 본질임.
61 × 53 = 3233
1초컷
3233 = ? × ?
하나씩 나눠봐야 함 — 수가 커지면 사실상 불가능
이 일방통행이 RSA 자물쇠의 핵심임
쇼어 알고리즘이 지름길을 낸다
1994년, 피터 쇼어가 알고리즘 하나를 냄. 양자컴퓨터라면 소인수분해를 빠르게 푼다는 거임.
고전 컴퓨터는 후보를 하나씩 시도함. 양자컴퓨터는 중첩으로 수많은 후보를 동시에 굴리고, 주기(패턴)를 찾아내 답으로 점프함. 무차별 대입을 다항시간으로 줄여버림.
즉, 고전엔 우주 나이가 걸리는 문제를 양자는 현실적인 시간에 풂. 공개키를 떠받치던 “어렵다”는 가정이 무너지는 거임.
후보를 하나씩 시도
중첩으로 동시에 + 주기 찾기
쇼어 = 어려운 문제에 양자 지름길을 냄
키를 키워도 양자 앞에선 무력
오른쪽에서 직접 해보셈. RSA 키 길이를 올리면 두 막대가 어떻게 갈리는지 한눈에 보임.
고전 막대는 키를 키울수록 자릿수째로 폭증함 — 우주 나이를 우습게 추월함. 그래서 지금까진 키만 키우면 안전했음.
근데 양자(쇼어) 막대는 키를 키워도 거의 안 움직임. 다항식이라 완만함. 키를 두 배로 늘려도 양자 앞에선 별 차이 없음. “키만 키우면 된다”가 안 통하는 거임.
≈ 10^26 초 — 소인수분해를 무차별로 시도
≈ 10^4 초 — 쇼어로 다항시간에 풂
키를 키우면 고전은 자릿수째로 폭증(우주 나이도 추월), 양자는 거의 그대로 완만함. 같은 자물쇠인데 한쪽엔 만리장성, 한쪽엔 문턱임.
숫자는 직관용 근사·예시임 — 정밀 벤치마크 아님
큰 양자컴퓨터 = 지금 대비 필요
충분히 큰 양자컴퓨터가 나오면 현재 RSA·디피-헬만은 무너짐. 아직은 그 규모가 안 됐지만, 시간 문제로 봄.
진짜 무서운 건 지금 훔쳐두고 나중에 깬다(Harvest Now, Decrypt Later)임. 오늘 가로챈 암호문을 쌓아뒀다가, 양자컴퓨터 나오면 그때 푸는 거임. 그래서 미래가 아니라 지금 대비해야 함.
내일은 그 대비책 — 양자컴퓨터로도 못 깨는 양자 암호 & PQC를 봄.
Q. 양자컴퓨터가 위협하는 암호는 주로?
RSA·디피-헬만 같은 공개키 암호임. 이들의 안전성은 소인수분해·이산로그가 어렵다는 데 기대는데, 쇼어 알고리즘이 그 문제를 양자컴퓨터로 빠르게(다항시간) 풀어버려서임. 키를 키워도 고전과 달리 양자 앞에선 시간이 거의 안 늘어나, 결국 무너짐.공개키 = 어려운 수학 문제에 기댐
양자가 그 문제를 빠르게 풂
큰 양자컴퓨터 → RSA·DH 붕괴 → 지금부터