|
'''
이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' |
|||||
|
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" |
<colbgcolor=#a36> 이론 | ||||
| 기본 대상 | 수학기초론{ 수리논리학( 논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학( 그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신( 폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^ 고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임( 그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축( 무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어( 함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^ 벡터^ · 리스트^ 연결 리스트^ · 셋(set)^ 레드-블랙 트리, B-트리^ · 우선순위 큐^ 힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시( MD5 · 암호화폐 · 사전 공격( 레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘( AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘( 타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^ BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제 대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
[[컴퓨터공학|컴퓨터 과학 & 공학
Computer Science & Engineering
]]- [ 펼치기 · 접기 ]
- ||<tablebgcolor=#fff,#1c1d1f><tablecolor=#373a3c,#ddd><colbgcolor=#0066DC><colcolor=white> 기반 학문 || 수학( 해석학 · 이산수학 · 수리논리학 · 선형대수학 · 미적분학 · 미분방정식 · 대수학( 환론 · 범주론) · 정수론) · 이론 컴퓨터 과학 · 암호학 · 전자공학 · 언어학( 형태론 · 통사론 · 의미론 · 화용론 · 음운론) · 인지과학 ||
하드웨어 구성 SoC · CPU · GPU( 그래픽 카드 · GPGPU) · ROM · RAM · SSD · HDD · 참조: 틀:컴퓨터 부품 기술 기계어 · 어셈블리어 · C/ C++ · C# · Java · Python · BIOS · 절차적 프로그래밍 · 객체 지향 프로그래밍 · 해킹 · ROT13 · 일회용 비밀번호 · 사물인터넷 · 와이파이 · GPS · 임베디드 · 인공신경망 · OpenGL · EXIF · 마이크로아키텍처 · ACPI · UEFI · NERF · gRPC · 리버스 엔지니어링 · HCI · UI · UX · 대역폭 · DBMS · NoSQL · 해시( SHA · 브루트 포스 · 레인보우 테이블 · salt · 암호화폐) · RSA 암호화 · 하드웨어 가속 연구
및
기타논리 회로( 보수기 · 가산기 · 논리 연산 · 불 대수 · 플립플롭) · 정보이론 · 임베디드 시스템 · 운영 체제 · 데이터베이스 · 프로그래밍 언어{ 컴파일러( 어셈블러 · JIT) · 인터프리터 · 유형 이론 · 파싱 · 링커 · 난해한 프로그래밍 언어} · 메타데이터 · 기계학습 · 빅데이터 · 폰노이만 구조 · 양자컴퓨터 · 행위자 모델 · 인코딩( 유니코드 · MBCS) · 네트워크 · 컴퓨터 보안 · OCR · 슈퍼컴퓨터 · 튜링 머신 · FPGA · 딥러닝 · 컴퓨터 구조론 · 컴퓨터 비전 · 컴퓨터 그래픽스 · 인공지능 · 시간 복잡도( 최적화) · 소프트웨어 개발 방법론 · 디자인 패턴 · 정보처리이론 · 재귀 이론 · 자연어 처리( 기계 번역 · 음성인식) · 버전 ( 버전 관리 시스템 · Git · GitHub)
1. 개요
RSA key cryptosystem공개키 암호화 알고리즘 중 하나. RSA는 특정 단어의 약자가 아니며, 1977년[1] 이 암호 체계를 개발한 Ron Rivest, Adi Shamir, Leonard Adleman 세 사람의 성을 따서 RSA 라고 이름이 붙었다. 현재 SSL/TLS에 가장 많이 사용되는 암호화 알고리즘이며, 전세계 대부분의 인터넷 뱅킹(대한민국 포함)이 이 RSA-2048 암호화를 사용한다.
보안도가 매우 높은데다 후술할 계산 간략화 알고리즘 덕분에 (고전적인 방법으로는) 해독이 불가능한 암호문을 주판 같은 원시적인 도구로도 매우 간단하게 다룰 수 있기에 매우 실용적이다.
다만 미국 국가 표준 암호화 알고리즘인 AES보다 RSA 방식이 계산 집약적이고 훨씬 느리다. AES 256비트가 RSA 15,360비트와 같은 수준이다. 그러나, AES 는 대칭키 알고리즘인데 반해, RSA 는 비대칭키(공개키) 방식이라는 전혀 다른 암호화 방식이라 같은 선상에 비교할 수 없다. 이 때문에 RSA는 사용자 데이터를 직접 암호화하기 보다는, RSA로 쌍방간 '키(key)'만을 공유하고 실제 데이터 암호화는 공유한 키를 바탕으로 대칭키 알고리즘을 사용하는 게 일반적이다.
2. 과정
RSA는 '암호화할 때에는 마음대로였겠지만 해독할 때에는 아니다'를 기본 모토로 삼고 있다. 컴퓨터가 엄청 큰 숫자끼리 곱하거나 나누는 것은 매우 쉽지만, 반대로 그 숫자를 소인수분해하기는 매우 힘들다는 점을 원리로 삼고 있다. 해쉬를 포함한 단방향 암호화와 유사하지만, RSA는 양방향 암호이므로 복호화할 수단을 남겨놓는다는 것이 차이점이다.공개키와 개인키가 한 쌍을 이루며, 공개키로 암호화한 내용은 개인키로만, 개인키로 암호화한 내용은 공개키로만 해독할 수 있다. 개인키로 암호화하면 공개키로 누구나 그 내용을 해독할 수 있으니 무슨 의미가 있냐는 생각을 할 수 있을 것이다. 그런데 개인키는 자기만 알고 있으니 개인키로 암호화한 메시지는 본인인증의 효과를 낸다. 개인키가 없다면, 대응되는 공개키로 해독할 수 있는 암호문을 못 만들기 때문이다. 이 특성은 전자서명에 매우 유용하게 활용된다. 공인인증서의 인증 원리도 이거다.
또한 이 특징 때문에 RSA를 사용할 때는, 내가 받은 공개키가 신뢰할 수 있는 공개키가 맞는지 확인하는 절차가 반드시 필요하다. 이 과정이 생략되면 중간자 공격이 가능해진다. OS와 웹 브라우저에는 신뢰할 수 있는 공개키 목록이 이미 탑재되어 있으며, 모르는 공개키 인증서로 서명된 웹 사이트는 웹 브라우저에서 접속을 거부한다. 실제 동작 방식은 TLS 문서 참조.
RSA 방식으로 암복호화를 하기 위해선 먼저 키를 만들어야 한다. 그 과정은 다음과 같다.
2.1. 키 만들기
- 두 소수 [math( p , q )] 를 준비한다.[2]
- [math( p - 1,\ q - 1 )]과 각각 서로소인 정수 [math(e)][3]를 준비한다.
- [math(ed)]를 [math((p - 1)(q - 1))][4]으로 나눈 나머지가 1이 되도록 하는 [math(d)][5]를 찾는다.[6]
- [math(N = pq)]를 계산한 후, [math(N)]과 [math(e)]를 공개한다. 이들이 바로 공개키이며, 상대방이 평서문[7]을 암호문으로 바꿀때 쓴다. 한편 [math(d)]는 숨겨두는데, 이 수가 바로 개인키이며, 공개키로 상대방이 만든 암호문을 해독할 때 쓴다.
- 이제 [math(p, q, (p-1)(q-1))]는 필요 없거니와 있어 봐야 보안에 오히려 문제를 일으킬 수 있으니, 파기한다.[8]
[math(N)]을 계수라 부르고 [math(e)]를 지수라고 부르는데 [math(e)]는 주로 페르마 소수 중에서 고르며 보통 65537을 사용한다. RSA의 키 사이즈를 말할 때 주로 [math(N)]의 사이즈를 의미하며 사이즈가 2048일 경우라면 정수 [math(N)]의 크기가 [math(2^{2047})]과 [math(2^{2048})]의 사이라는 의미이다.
한편 소수 [math(p)]와 [math(q)]를 구하는 과정은 여전히 완전한 방법이 없다고 봐야 한다. 일단 에라토스테네스의 체를 이용한 방식을 생각해 볼 수 있는데, [math(\sqrt{p})]보다 작은 소수들 모두로 나눠 봐야 알 수 있다는 점에서 이 방법은 현실적으로 불가능한 방법이다. 그래서 대신에 확률적으로 소수인지 아닌지를 판별하는 방법을 쓴다. 기본적으로 쓰는 방식이 아래에 소개할 페르마의 소정리를 근거로 한 것인데, 이 정리의 대우명제인 '임의의 정수 [math(a)]에 대해 [math(a^{p - 1})]를 [math(p)]로 나눈 나머지가 1이 아니면 [math(p)]는 소수가 아니다'라는 사실을 이용한 것이다. 이 방법을 쓰면 상당 확률로 소수를 걸러낼 수 있다고 한다. 하지만 물론 완전하진 않으며[9] 이 때문에 다른 소수 판정법을 같이 쓰기도 한다. 여기서 리만 가설을 참이라고 가정하고 만들어진 여러 소수 판별법들을 사용한다. 현대 암호 체계가 리만 가설과 연관이 있다고 하는 이유는 이것이다.
2.2. 암호화 및 해독
공개키를 이용해 RSA 방식으로 암호화를 하는 과정은 다음과 같다.예를 들어 앨리스가 공개키를 만들어 뿌렸고, 밥이 앨리스한테 메세지를 비밀리에 주고 싶다고 하자.[12] 밥은 앨리스의 공개키를 통해 암호화된 내용([math(x)])를 앨리스한테 준다. 그러면 앨리스는 자신이 가지고 있는 개인키를 이용해 원래 평서문을 얻을 수 있다. RSA 방식으로 해독을 하는 과정은 다음과 같다.받은 암호문 [math(x)]를 [math(a' ≡ x^d\ \pmod N )]으로 복호화한다.
그러면 [math(a' = a)]가 되어 앨리스는 밥의 메세지를 무사히 받을 수 있게 된다.프로그래밍을 어느 정도 해 본 사람이라면 [math(a^e\bmod N)]나 [math(x^d \bmod N)] 같은 걸 어떻게 계산하나 싶을 것이다. [math(a^e)] 같은 걸 계산하는 걸 곱셈을 [math(e)] 번 하는 식의 터무니없이 막대한 연산을 수행할 수는 없는 노릇이고 그렇다고 pow 같은 걸 쓰자니 자릿수가 턱없이 모자랄 것이기 때문이다.[13]
이렇게 보면 RSA 방식이 필요로 하는 연산이 불가능해 보이지만 의외로 간단한데다 연산량도 그리 크지가 않아 오히려 매우 실용적이다. 어느 수의 제곱을 구할때 밑의 수를 계속 곱하면 오래걸리지만, 기존의(우리가 구해놓은) 제곱한 수를 제곱하면 되기 때문이다.
이 방식을 설명하는 것은 간단한 예를 하나 드는 것이 빠를 것 같다. 예를 들어 [math(x)]의 23제곱을 [math(N)]으로 나눈 나머지를 계산하고 싶다고 하자. 그러면 [math(ab\bmod N = (a\bmod N)(b\bmod N)\bmod N)], [math(a^b\bmod N = (a\bmod N)^b\bmod N)]로부터 다음을 얻는다.
[math(x^{23}\bmod N = x^{2^0 + 2^1 + 2^2 + 2^4}\ mod\ N = (x \cdot x^2 \cdot (x^2)^2 \cdot (((x^2)^2)^2)^2)\ mod\ N)]
[math(= ((x\ mod\ N) ((x\ mod\ N)^2\ mod\ N) (((x\ mod\ N)^2\ mod\ N)^2\ mod\ N) (((((x\ mod\ N)^2\ mod\ N)^2\ mod\ N)^2\ mod\ N)^2\ mod\ N)\ mod\ N.)]
뭔가 복잡해 보인다. 여기서 [math(x_0 = x\ mod \ N)], [math(x_{i + 1} = x_i^2\ mod\ N)]이라 표기하면 사실 위 식은 이렇게 깔끔하게 정리된다.
[math(x^{23}\ mod\ N = (x_0 x_1 x_2 x_4)\ mod\ N.)]
즉 [math(x_i)]들을 계산해 놓고 이들을 활용하면 엄청난 계산량이라든가 저장 공간 같은 것 없이 저렴하게 [math(x^d\ mod\ N)] 등을 계산할 수 있다. 이걸 다음과 같은 알고리즘으로 정리할 수 있다.
- [math(y ≡ x\ mod\ N)]을 계산한다.
- [math(m = 1, r = 1)]로 둔다.
- 만약 [math(d)]의 (2진법에서) [math(m)]번째 자릿수가 1이라면 [math(ry\ mod\ N)]을 계산한 다음 [math(r)]에 저장한다.
- [math(y)]에 [math(y^2\ mod\ N)]을 저장한다.
- [math(m)]에 [math(m + 1)]를 저장한다.
- 만약 [math(m)]가 [math(d)]의 자릿수보다 크지 않으면 3으로 돌아가고 그렇지 않으면 종료한다.
대학에서 이산수학을 수강할시 기말고사로 풀라고 문제가 나오는 경우도 있다.
3. 원리
이 방식에는 오일러 정리가 중추적인 역할을 한다. 간단하게 써 보자.[math(\gcd(a,N)=1)]인 임의의 정수 [math(a)]와 [math(N)]에 대해 항상 [math(\displaystyle a^{\varphi(N)} \equiv 1 \pmod N)][14] 이 성립한다.
여기서 [math(\varphi(N))]은 오일러-phi 함수로, 1부터 [math(N)]까지의 수들 중에서 [math(N)]과 서로소인 수들의 개수이다.
여기서 [math(\varphi(N))]의 일반적인 꼴을 다루진 않을 것이다. 다만, 이때 두 소수 [math(p, q)]가 있어 [math(N = pq)]라면, [math(\varphi(N))]의 값은 [math((p - 1)(q - 1))]로 주어진다는 것 정도는 알아야 한다.여기서 [math(\varphi(N))]은 오일러-phi 함수로, 1부터 [math(N)]까지의 수들 중에서 [math(N)]과 서로소인 수들의 개수이다.
이 정리를 이용하면 RSA 암호화 방식이 작동하는 이유가 놀랄 만큼 간단하다는 것을 알 수 있다. 일단 다른 건 몰라도 [math(a)]와 [math(a')]가 같아야 한다는 것만 있으면 된다는 걸 염두에 두자. 이제, [math(ed = b(p - 1)(q - 1) + 1 = b \varphi(N) + 1)] ([math(b)]는 어떤 정수)이라는 것과 [math(ab\ mod\ N = (a\ mod\ N)(b\ mod\ N)\ mod\ N)], [math(a^b\ mod\ N = (a\ mod\ N)^b\ mod\ N)]이라는 사실로부터, 다음을 얻을 수 있다.
[math(a' = x^d\ mod\ N = (a^e\ mod\ N)^d\ mod\ N)]
[math( = (a^e)^d\ mod\ N = a^{ed}\ mod\ N)]
[math( = a^{b \varphi(N) + 1}\ mod\ N = (a^{\varphi(N)}\ mod\ N)^b \cdot a\ mod\ N)]
[math( = 1^b \cdot a\ mod\ N = a.)]
이는 암호문을 복호화한 내용이 원래 평서문과 일치함을 말해 준다.
RSA 암호 체계의 작동 원리는 이 동영상을 보면 이해할 수 있다.[15]
4. 한계
AES와는 달리 블록화를 지원하지 않으므로 암호화 비트수를 넘어가는 데이터에 대해서는 처리가 불가능하다. 그래서 TLS/ DTLS에서는 데이터 암호화는 AES와 같은 대칭키 암호화로 처리하고 대칭키 자체에 대해서 RSA로 암호화하여 상대방에게 이를 전달한다.5. 기타
정수론에 대해 많은 기본적인 지식만 갖고 있어도 쉽게 이해할 수 있고 보안성이 뛰어나 많이 사용되고 있다. 하지만 만약 소인수분해를 다항식 시간 내에 수행할 수 있는 알고리즘이 개발되어 쉽게 소인수분해가 가능하다면 당연히 RSA 암호체계는 위기를 맞을 것이다. 양자컴퓨터를 사용하면 소인수분해를 [math(O(\log^3 n))]으로 풀 수 있는 쇼어 알고리즘이란게 있는데 문제는 이게 성공률이 100%가 아니다.[16] 이런 실패확률은 어떤 N에 대해서도 5/8을 넘지 않는다는 것이 증명되었기에 그냥 여러번 하면 풀리긴 풀린다. 다만, 컴퓨터의 성능이 높아지면 높아질수록 현재 사용되는 RSA 2048bit는 깨질 수 있다. 일단 RSA 768bit는 2009년도에 깨졌기 때문에, 더이상 사용되지 않는다. 다만 미래에 RSA 2048bit가 깨질 정도로 컴퓨터의 성능이 상승했다면 그 미래에는 이미 RSA 8192bit따위를 쓰고 있을 것이다.[17]RSA 알고리즘은 구현방법에 따라 부채널 공격의 일종인 Timing Attack에 취약할 수 있다. 정확히는 [math(e)]를 left-to-right 또는 right-to-left 알고리즘으로 계산할 때 부채널 분석에 대해 어떤 키 길이에 대해서도 취약하다.
코나미의 BEMANI 시리즈의 게임 데이터가 이 암호화 방식을 채용하고 있다. 기존의 자신들의 작품이 PC기반으로 나온 뒤 매번 크래킹의 대상이 되어 채용했지만, 기존의 암호화가 뚫린 데이터를 크래커들이 가지고 있는 이상 무용지물에 가깝게 되었다. 이외에도 닌텐도 DS의 전용 OS, 모토로라의 안드로이드 스마트폰용 부트로더가 RSA를 채용했다.
6. 예시
두 소수 p와 q를 11과 37이라 하자. 그리고, 10과도 36과도 서로소인 정수 e을 7로 정하자. 우리가 공개하는 것은 N = 11×37 = 407과 e = 7이다.다음으로 7×103 - 360×2 = 1 임을 이용해서 103 을 d 로 보관한다.
이제, 어떤 평서문 240을 암호화 해 보자. 240의 7제곱을 407로 나눈 나머지는 235이다.[18] 235를 407의 소인수를 아는 상대방에게 보낸다. 참고로 여기서 N은 407이니, 평서문은 406 이하의 숫자만 가능하다.
이제, 이걸 받은 사람은 암호를 푼다.
받은 사람은 N과 d의 값이 각각 407 과 103 임을 알고 있으므로, 전달받은 235의 103제곱을 407로 나누면 나머지가 평서문이 된다. [math(240 = 235^{103}\pmod{407})]
암호가 풀리는 과정을 더 상세히 설명하자면, 먼저 암호를 풀기 위해서는 407의 오일러 피 함수 값을 알아야 한다. 오일러 피 함수값은 어떤 수 x에 대해서 x와 같거나 작은 수들 중에서 x와 서로소인 수의 개수이다. 소인수들을 안다면 쉽게 알 수 있지만, 모른다면 구하기 힘들다. 407의 오일러 피 함수값은 360이다. 407은 11, 37 두 소수를 곱한 수이므로, 407보다 작은 수들 중에 407과 서로소가 아닌 수는 각 소수의 배수들밖에 없다. 즉 [math(407 - (11 - 1) - (37 - 1) - 1 = 360)].[19][20]
다음으로 7×103 - 360×2 = 1 임을 이용해서 235의 103제곱을 407로 나누면 나머지가 평서문이 된다. [math(240 = 235^{103} \pmod{407})][21]
언뜻 보면 위의 예시의 경우엔 시행착오 사백번 정도만 해도 풀리니 간단해 보인다. 하지만 실제로는 작은 수가 아닌 적기도 힘든 큰 수를 쓴다. 숫자의 목록은 여기를 참조하자. (한국어)[22]
여담으로 연산량이 많기 때문에 암호화 통신의 경우[23] 처음의, 그리고 일정 주기[24]마다의 암호키 교환(key exchange)에 쓰이고, 키를 교환한 뒤부터는 AES등의 블록 사이퍼를 사용한다. 암호 알고리즘 문서 참고.
정말로 간단하게 비유를 하자면, 위의 밥과 앨리스의 경우 앨리스가 자물쇠(공개키)와 그것을 열 수 있는 유일한 열쇠(개인키)를 가지고 있을 때 자물쇠만 남들에게 공개한다. 그걸 본 밥이 비밀 메시지를 쓰고 그걸 상자에 담아 해당 자물쇠로 잠그고(암호화) 전달하면, 누가 그걸 도중에 손에 넣더라도 열쇠가 없으니 열어보지를 못하고, 오직 앨리스만 열쇠로 열 수 있는 것이다. 저 자물쇠로 잠그는 행위는 앨리스가 뿌린 자물쇠가 있으니 누구나 할 수 있는데도 말이다. 이러면 '자물쇠 모양에서 열쇠 모양을 유추해낼 수 있지않냐'고 하겠지만, RSA 방식에서는 적어도 현대 수학으로는 자물쇠에서 열쇠 모양을 알아내는데 너무 많은 시간과 자원이 필요하다. 그렇기에 보안이 가능한 것.
7. 여담
RSA-896, RSA-1024, RSA-1536, RSA-2048 같은 수에는 소인수분해에 현상금이 걸려 있었다. 가장 자리수가 많은 RSA-2048은 소인수분해를 성공할 경우 20만 달러(대략 2억원)의 상금이 걸려 있었으나, 현재는 상금이 폐지되었다. 이 현상금은 소인수분해가 현실적으로 얼마나 어려운지를 보여주기 위한 것으로, 실제로는 모든 사람이 서로 다른 소수쌍을 무작위로 생성해 사용하기에 가령 어떤 사람이 수백년 이상 컴퓨터를 돌려 소인수분해에 성공하더라도 RSA 자체가 뚫린 것은 아니다.참고로 RSA-2048 은 617자리 수이다.
| RSA-2048 |
|
2519590847565789349402718324004839857142928212620403202777713783604366202070759555626401852588078440 6918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014 9718246911650776133798590957000973304597488084284017974291006424586918171951187461215151726546322822 1686998754918242243363725908514186546204357679842338718477444792073993423658482382428119816381501067 4810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350 7787077498171257724679629263863563732899121548314381678998850404453640235273819513786365643912120103 97122822120720357 |
중요도가 높은 인증서인 경우 RSA-4096 이나 RSA-8192 를 쓰기도 한다.
컴퓨터로 처리하기 위해서는 큰 수를 다루는 별도의 라이브러리나, 전용 프로그래밍 언어가 필요하다. 일반적인 프로그래밍 언어로는 64비트 정수형 (약 20자리) 보다 큰 수를 직접 제어하는 기능을 제공하지 않는다.
RSA 암호화를 골자로 하는 언어 모의고사가 출제 된 적이 있다. 위 내용을 그대로 적지는 않았고 아주 쉽게 간략화해서 출제하였다.
8. 양자 컴퓨터의 위협
RSA 암호화는 양자 컴퓨터가 등장하면 깨진다는 보안 위협에 직면해 있다. 1994년 피터 쇼어가 제안한 양자 알고리즘( 쇼어 알고리즘)은 소인수 분해를 다항 시간안에 할 수 있는 양자 알고리즘이다. 따라서 RSA 암호화에 사용된 비트 수를 계산할 수 있을 정도의 충분한 큐비트 수를 가진 양자 컴퓨터가 개발되면 RSA 암호화 체계는 붕괴될 수 있다.
[1]
사실 이것보다 4년 정도 더 빨리
GCHQ의 모 수학자가 개발했으나, GCHQ에선 이를 1998년까지 기밀처리하게 된다.
[2]
이들은 보통 굉장히 큰 홀수를 일단 랜덤하게 만든 다음, 소수를 얻을 때까지 2씩 더해 가며 찾는다. 소수의 분포가 그리 희박하진 않기에 가능한 방식이다. 참고로 해당 수가 소수인지 아닌지 판별하는 방법(primality test)이 다소 골때리는데, 이에 대해선 아래 내용 참고.
[3]
e는 지수를 의미하는 exponent에서 딴 것이다. encryption에서 딴 게 아니다. 왜냐하면 암호화할 때 평문에 e제곱을 하기 때문이다. 공개키는 어차피 모두에게 공개되므로 비교적 선택이 자유롭다. 보통 계산의 편의성을 위해 1의 비트가 2개인, 3(112)이나 65537(100000000000000012) 같은
페르마 소수를 쓴다.
[4]
[math(phi(pq))]이다.
[5]
d는 decryption에서 딴 것이다.
[6]
확장된 유클리드 호제법을 이용하면 금방 구할 수 있다. 다만 e가 (p - 1)(q - 1)와 서로소가 아니라면 이를 만족하는 d는 존재하지 않기 때문에 2번 과정이 필요하다.
[7]
물론 A = 01, B = 02, ... , Z = 26 등의 방법으로 문장을 숫자 형태로 바꿔야 한다.
[8]
실제로는 공개키 암호화 표준에선 개인키가 {d,N} 혹은 {p, q, dP, dQ, qInv, (r_i, d_i, t_i)}로 표현된다. 후자의 값들은 연산 최적화를 위한 값들로 p,q도 포함된다.
[9]
카마이클 수라고 해서, 페르마의 소정리로는 소수임을 판정할 수 없는 유사 소수가 있다. 심지어 카마이클 수는 그 수가 무한하기 때문에 해당 수가 정말로 소수인지 판별하기 위해서는 소수와 유사 소수들을 모아놓은 집합에 대하여 여러가지 다른 소수 판정법으로 체로 걸러내야만 한다.
[10]
만약 보내려는 평서문의 길이가 N보다 길면, 모종의 복잡한 변환법을 통해 분할하여 N보다 짧게 만든다. 당연하지만 해당 변환법은 보내는 측과 받는 측 모두 알고 있어야 한다.
[11]
[math( x ≡ a^e\ \pmod N )] 는 [math(x)]와 [math(a^e)]를 각각 [math(N)]으로 나눴을 때 나머지가 같다는 뜻이다. "[math(x)]와 [math(a^e)]는 법[math(N)]에 대하여
합동이다" 라고 읽는다.
[12]
대부분의 암호학 문서에서 메세지를 주고 받는 사람의 이름으로 '앨리스'와 '밥'을 쓴다.
[13]
[math(e = 3)] 같은 경우라면 모를까 일반적으로 [math(d)]는 몇 백에 달하는 자릿수를 가진 어마어마한 수일 것이고 [math(x^d)] 같은 걸 정확하게 계산하려면 전 세계에 있는 메모리를 다 모아도 부족할 정도로 어마어마한 저장 공간이 필요할 것이다.
[14]
[math(a)]의 [math(\varphi(N))] 제곱을 [math(N)]으로 나눈 나머지가 항상 1이라는 뜻이다.
[15]
RSA 암호화 뽀개기: 말할 수 있는 비밀
[16]
N과 서로소인 a로부터 [math( a^b -1 = (a^{b/2}+1)(a^{b/2}-1) = mN )]인 b를 찾아서 [math( gcd(N,a^{b/2} +1),gcd(N,a^{b/2} -1) )]를 찾는데 b가 홀수라거나 공약수가 N이라거나 하는 경우가 있다.
[17]
다만 양자컴퓨터의 경우처럼 계산 복잡도에서 암/복호화의 차이를 줄여버린다면 뚫기 어려울 정도로 복잡한 암호를 만들었다간 암호화하는 데도 너무 오래걸려서 무쓸모가 될 가능성이 높다.
[18]
[math(235 = 240^7 \pmod{407})]
[19]
(11-1)은 407을 제외한 37의 배수, (37-1)은 407을 제외한 11의 배수, 마지막 -1은 407 자신.
[20]
예로 든 백단위의 작은 수는 손으로도 쉽게 찾을 수 있지만, 실제 암호화에 사용하는 200자리가 넘어가는 수라면, 소인수를 알면 쉽게 풀 수 있지만 모를 경우
답이 없다는 것을 알 수 있다.
[21]
즉 103을 d 값으로 보관한다는 것은 오일러함수값을 찾아야하는 중간계산 절차를 넘기게 된다는 의미와 같다.
[22]
보통 100자리 이상의
소수의 곱을 사용한다. 200자리 이상의 합성수를 소인수 분해하는 것은 현대의 기술로는 거의(!) 불가능하다고 생각되어 왔지만 2013년엔 210자리 수가 개인 사용자에게 뚫리는 등 이제
CPU의 발달과 함께 소인수분해 가능한 수도 점점 커지고 있다.
[23]
다른 경우로는 전자서명을 들 수 있다.
[24]
SSH의 경우 1시간, 또는 1GB의 데이터가 오갈 때 마다 키를 갱신한다.