나름 개발자의 IT블로그

우리는 암호를 왜 사용할까? 어떠한 정보에 도달하기 위해 내가 그 정보에 도달할 수 있는 유효한 사람임을 증명하기 위해 사용할 것이다. 예를 들어 웹사이트에서 나의 정보를 얻기 위해 나라는 것을 증명하기 위해 로그인을 하는 행위가 있을 것이다. 굉장히 심플한 방법이지만 보통 로그인을 할 때 패스워드를 서버에 보내서 서버에 있는 패스워드와 일치하는지 확인하는 방법을 사용하기 때문에 서버에 패스워드를 보내는 행위 자체가 찝찝할 수 있다. Zero Knowledge Proof어떤 문제를 해결하려는 사람 $P$(Prover)와 $P$가 제출한 데이터가 유효한지 검증하는 $V$(Verifier)가 있다고 하자. $P$는 $V$에게 어떤 데이터 $X$를 알고있다는 사실을 알려주고 싶다. 여기에서 $X$에 대한 정보..

UUIDuuid란 엔트로피가 굉장히 높은 무작위성을 가진 36자리의 문자열이다. 중복될 확률이 굉장히 낮기 때문에 키 값으로 많이 사용된다.1f298256-e337-46d7-b985-f365d395c8fa실제로 파이썬을 사용하여 생성한 uuid이다. 그럼 키 값으로 해당 uuid를 사용하고 전송할 데이터에 키와 신청 여부를 포함하려면 어떻게 할까? 방법 1가장 생각하기 쉬운 방법으로 json을 생각할 수 있다.{ "key": "1f298256-e337-46d7-b985-f365d395c8fa", "value": True }이 방법은 GET일 땐 사용하기 힘들고 용량도 상당히 크다. 방법 2jwt토큰으로 만들어서 토큰을 전송한다.이제 하나의 문자열이 됐으니 GET메소드에서 path variable이나 qu..

배경 돈을 금고에 담아 자물쇠로 잠근 후 다른 사람에게 보낸다고 가정하자. 그렇다면 받는 사람은 금고를 열기 위한 열쇠가 필요하다. 이 과정에서 어떤 방법으로든 열쇠에 대한 정보가 필요하다. "열쇠를 직접 전달한다.", "열쇠를 만드는 법을 전달한다."같은 방법이 있는데 이런 방법은 금고 외에 추가적인 정보 전달이 필요하다. 최악의 경우 열쇠를 직접 전달하는 과정에서 도난을 당할 수 있다. 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..