오늘 끝나면
양자 위협
- ✓양자 위협의 핵심 문제를 한 문장으로 설명한다
- ✓오른쪽 실습에서 양자이 어떻게 움직이는지 관찰한다
- ✓다음 강의와 이어지는 한계를 말할 수 있다
실습 미션
쇼어 알고리즘 — 양자컴퓨터가 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)는 것이다. 오늘 가로챈 암호문을 쌓아뒀다가, 양자컴퓨터가 나오면 그때 푼다. 그래서 미래가 아니라 지금 대비해야 한다.
Q. 양자컴퓨터가 위협하는 암호는 주로?
RSA나 디피-헬만 같은 공개키 암호다. 이들의 안전성은 소인수분해와 이산로그가 어렵다는 데 기대는데, 쇼어 알고리즘이 그 문제를 양자컴퓨터로 빠르게(다항시간) 풀어버리기 때문이다. 키를 키워도 고전과 달리 양자 앞에선 시간이 거의 안 늘어나, 결국 무너진다.공개키는 어려운 수학 문제에 기댄다
양자가 그 문제를 빠르게 푼다
큰 양자컴퓨터가 RSA·DH를 무너뜨린다, 지금부터 대비한다