나름 개발자의 IT블로그

배경 돈을 금고에 담아 자물쇠로 잠근 후 다른 사람에게 보낸다고 가정하자. 그렇다면 받는 사람은 금고를 열기 위한 열쇠가 필요하다. 이 과정에서 어떤 방법으로든 열쇠에 대한 정보가 필요하다. "열쇠를 직접 전달한다.", "열쇠를 만드는 법을 전달한다."같은 방법이 있는데 이런 방법은 금고 외에 추가적인 정보 전달이 필요하다. 최악의 경우 열쇠를 직접 전달하는 과정에서 도난을 당할 수 있다. Massey-Omura (Three-pass Protocol)은 이런 문제를 해결한다. Process 정보를 암호화한 상태로 추가적인 정보전달 없이 송수신이 가능할까? 0. A가 B에게 금고에 넣은 돈을 전달하는 경우를 생각하자. (자물쇠 적용 X) 1. A가 금고에 돈을 넣은 후 자물쇠로 잠근 후 B에게 전달한다. ..

지난시간 RSA를 위해 두 가지 문제점이 남아있었는데 빠른 거듭제곱은 해결했고 큰 소수 생성 문제가 남아있었다. 이를 해결해보자. 기본적인 소수 판정 $N$이 소수인지 판정한다고 하자. $1$~$\sqrt{N}$까지만 판별했을 때 나누어떨어지는 수 $d \le \sqrt{N}$가 있다면 $\frac{N}{d} \ge \sqrt{N}$ 역시 나누어 떨어지므로 $\sqrt{N}$까지 확인해보면 충분하다. $\sqrt{N}$은 이분탐색 등으로 $P$ 시간에 구할 수 있지만 위 로직은 시간복잡도가 $O(\sqrt{N})$이 나오므로 $\log N$의 입장으로 보면 $EXP$이다. 다항시간 판정법이 있어야 그나마 쓸만하니 그런 방법이 있는지 알아보자. 페르마의 소정리 $p$가 소수라면 $a^{p-1} \equiv..

사전지식 (정수론) 유클리드 호제법 합동 페르마 소정리 중국인의 나머지 정리 오일러 피 함수 분할정복을 이용한 거듭제곱 대칭키 시스템 Key $p$ : 큰 소수 $e$ : 암호화 키 (홀수) $d$ : 복호화 키 (홀수) $ed \equiv 1 \mod p-1$ $\gcd(e, p-1) = 1$ 이렇게 3개의 키를 사용한 암호화 알고리즘을 사용한다. $p$는 큰 소수이기 때문에 홀수임이 자명하다. $C \equiv m^e \mod p$으로 암호화된 $C$를 구할 수 있다. ($m$은 원본 데이터) 반대로 $m \equiv C^d \mod p$로 복호화할 수 있다. $m = C^d = (m^e)^d = m^{ed} = m$임을 사용한 심플한 알고리즘이다. 문제점은 메시지를 보내는 sender와 그 메시지를..

지난시간에 의하면 $P = NP$인지 모르기 때문에 암호가 불완전할 수 있다고 했다. 그래서 차라리 $NP$문제를 선택하고 Bob에게 힌트를 줘서 $P$로 만드는게 나을 수 있다. 그렇다면 $NP$문제중에 어려운걸 선택하면 될 것이다. 그런 문제셋을 $NP$-Complete라고 소개를 했었다. $NP$-Complete Class를 시간제한으로 봤을 때 위와 같이 나온다. ($D$, $E$와 유사하다. co-$NP$는 생각하지 말자) $NP$-Complete의 예시로 SAT가 있는데 이 문제가 핵심 역할을 할 것이다. Reduction Problem $A$의 입력 $a$를 $b$로 변환할 수 있다면 Problem $B$로 reduce할 수 있다. 우리가 알고리즘이나 수학문제를 풀 때 해당 문제를 변형해서 ..

P=NP는 수십년동안 해결되지 않은 난제로 남아있다. 위 문제가 암호에 관련이 있다고 하는데 어떤 연관이 있는지 알아보자. NP Class 전 시간에 $NP$는 NTM이 다항시간에 해결하는 Problem 집합이라고 했다. 이와 다르게 $NP$를 정의할 수 있다. $NP$는 DTM에게 적절한 힌트를 주면 YES를 검증할 수 있거나 다항시간에 해결할 수 있는 Problem 집합이다. NP-Complete라고 했던 Longest Path 문제를 보자. 단순히 그래프를 주고 A -> B로 가는 가장 긴 경로를 출력하라고 하면 힘들것이다. 하지만 문제를 그래프를 주고 A -> B로 가는 k이상의 경로가 있는가?로 바꾼다면 검증할 수 있다. 그러한 경로를 보여주면 된다! Longest Path문제도 그런 경로를 보..

지난시간 Problem의 시간을 제한하자는 아이디어가 나왔다. 하지만 시간을 몇초, 몇분 이렇게 제한할 수 없으니 일반적으로 제한한 개념이 있다. (big-O표기법과 비슷하다.) Time-Limited Complexity Classes $P$ : DTM이 다항시간에 해결하는 Problem 집합 $NP$ : NTM이 다항시간에 해결하는 Problem 집합 $EXP$ : DTM이 지수시간에 해결하는 Problem 집합 $NEXP$ : NTM이 지수시간에 해결하는 Problem 집합 $DEXP$ : DTM이 지수의 지수시간에 해결하는 Problem 집합 ($2^{2^n}$) ... (뒤에 $P$-class처럼 class가 붙어야하지만 생략합니다.) 예를들어 보면 우리가 사용하는 컴퓨터인 DTM은 정렬문제를 $..

자 이쯤되면 필요한 배경지식은 모두 쌓은것 같네요. 이제 암호학을 배우러 가보도록 하죠 첫 시간에 봤던 그림이다. M -> C로 암호화하는 Problem X1가 있을 것이고 C -> M으로 복호화하는 Problem X2가 있을 것이다. 즉 위 그림에서 1번에 X1이 들어가고, 2와 3번에 X2가 들어간다. 그럼 가장 베스트인 경우는 2는 해결할 수 없고 3은 해결할 수 있으면 좋을 것이다. (1은 언제나 해결 가능해야 함..) 그것이 가능할까? Solvable vs Unsolvable Solvable은 말 그대로 해결할 수 있는 Problem, Unsolvable은 해결할 수 없는 Problem이다. Class D에 포함되는 Problem들은 Solvable하다. (Yes, No가 출력으로 나오니까..)..

Dove-Tailing Technique Classes E 는 Enumerable 한 Problem들의 집합이라고 정의했다. 왜 그런지 알아보자. Classes E는 문제를 해결할 때 String 단위가 아니라 String안에 있는 Symbol단위로 진행한다. 예를들어 $S_1 = a_{11}a_{12}a_{13}..., ..., S_i = a_{i1}a_{i2}a_{i3}$이 있으면 $a_{11} \rightarrow a_{12} \rightarrow a_{21} \rightarrow a_{13} \rightarrow a_{22} \rightarrow a_{31} \rightarrow \dots$이런식으로 진행하며 해결한다. 이런 방법을 Dove-Tailing Technique이라고 하고 이 때문에 E..

Classes Complexity Theory에서 Classes란 Problem들의 집합을 의미한다. 우리는 앞에서 Problem이 무엇인지 알고 왔기 때문에 Classes도 큰 어려움없이 이해할 수 있다. Problem의 크기가 $|2^{|\Sigma^*|}|$였으므로 Classes의 크기는 $|2^{|2^{|\Sigma^*|}|}|$가 되고 이는 어마어마하게 많다는 것을 의미한다. 그리고 앞서 말했듯이 쉬운 문제 -> 빨리 풀린다, 어러운 문제 -> 푸는데 오래 걸린다, 굉장히 어려운 문제 -> 푸는데 언제 끝날지 모른다. 를 의미한다. 그럼 이제 Classes에는 어떤 것들이 있는지 알아보자. Classes D Classes D는 Decidable한 문제로 입력 $x$가 Language $L$에 포..

Turing Machine 이제 우리의 컴퓨터와 가장 가까운 튜링 머신이다. 튜링 머신이 가장 강력한 머신임은 모르지만 모든 문제를 풀 수 있는 General Machine이라고 한다. 다른 말로 튜링 머신으로 풀 수 없는 문제는 어떤 머신을 가지고 와도 해결할 수 없다. 우선 튜링머신의 구조는 아래와 같다. 가장 위쪽부터 작은 네모들의 집합이 Tape이다. Tape에 symbol을 남길 수 있다. 그리고 Tape에 들어있는 각 네모 칸이 Cell이고 이 곳 하나당 symbol하나를 기록할 수 있다. 현재 Cell위치를 가리키는 화살표가 R/W head이다. head를 이용하여 현재 Cell에 적힌 symbol을 읽거나 새로 쓸 수 있다. 밑에 있는 P, Q, R, S는 각각 state를 의미하고 현재 ..