나름 개발자의 IT블로그

사전지식 (정수론) 유클리드 호제법 합동 페르마 소정리 중국인의 나머지 정리 오일러 피 함수 분할정복을 이용한 거듭제곱 대칭키 시스템 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를 의미하고 현재 ..

암호학을 위한 Computation Theory가 끝나가고 있다. 지금은 배경지식을 알아가는 단계이니 가벼운 마음으로 알아가보자. Some Problems 여러가지 문제를 보자. $L8 = \{x|x=y2y^R2y^R, y \in \{0, 1\}^*\}$ $L9 = \{x|x=y2y^R2y^R2y^R, y \in \{0, 1\}^*\}$ $L10 = \{x|x=yy^Ry^R, y \in \{0, 1\}^*\}$ $L11 = \{x|x=yy^Ry^Ry^R, y \in \{0, 1\}^*\}$ $L12 = \{x|x=yy, y \in \{0,1\}^*\}$ 위 문제들은 DPDA로 해결할 수 없다. 특히 $L12$는 NPDA로도 해결할 수 없다. (ㄷㄷ..) 하지만 stack을 2개 사용하여 해결할 수 있다...

계속해서 배경지식에 대한 설명이 나오고 있다. 지금 내용들을 알아야 뒤에 나오는 개념들이 이해되니 천천히 알아보도록 하자.. Problem X5를 AC하는 머신이 있는가? 우리는 Problem X5가 DFA로 AC를 받을 수 없다는 것을 Pumping Lemma로 보였다 NFA로도 나타내기 힘들어 보이는데 여기에 stack를 하나 추가하는 것 만으로도 해결할 수 있다. DFA에 stack을 추가한 머신을 Deterministic Push Down Automata라고 한다. 여담으로 머신 $\in$ 튜링머신(컴퓨터)이다. Deterministic Push Down Automata (DPDA) 위에서 설명했듯이 DFA에 stack을 추가한 머신이다. 상태를 stack으로 관리하고 입력에 따라 스택에 넣을지 ..