이동식 저장소

서명 서명이 있으면 암호화만 가지고는 못 하는 일들을 할 수 있다. 예를 들어 인터넷뱅킹. 내 입장에서 보면 상대가 은행인지 어떻게 아는가? 반대로 은행 측은 내가 계좌 주인인지 어떻게 아는가? 상대방을 확인할 수 있는 서명이 있다면, 서명이 누구의 것인지 확인할 수 있다면 많은 일을 할 수 있다. 이상적인 서명은 어때야 하는가? 단 한명만 만들 수 있는 서명, 누구나 그 서명의 주체를 확인할 수 있는 서명이 좋은 서명이다. 또, 내가 서명했다는 사실을 부인할 수 없어야 한다. RSA 서명 다음의 상황을 가정한다. $p,~q$: 큰 소수 (공개됨) $n=pq$ (공개됨) $e$: 암호화 키 (공개) $d$: 복호화 키 (비공개) $ed=1 \mod (p-1)(q-1)$ 메시지 $m$에 대해 서명 $s(m..

저번 시간까지 RSA에 대해 공부했다. 이제 두 번째 암호에 대해 알아보자. 이산 로그 (Discrete Log) $Z_{n}^{*}=\{ g,g^{2},\cdots,g^{\varphi (n)} (=1) \} $이면 $g$는 $Z_{n}^{*}$의 ``Generator``이다. ``Generator``가 항상 존재하지는 않는다. 예를 들어 $Z_{15}^{*}$의 ``Generator``는 존재하지 않는다. 사실 ``Generator``가 존재할 조건은 다음과 같다. $Z_{n}^{*}$의 ``Generator``가 존재한다 $\Leftrightarrow~n=2,2^{2},p^{k},2p^{k}$, $p$는 홀수 소수 $Z_{7}^{*}=\{1,2,3,4,5,6\}$의 ``Generator`` $g=3$..

소인수분해는 얼마나 어려운가? RSA를 뚫는 것은 $n$을 소인수분해(factoring)하는 문제와 동치임을 보였다. 그러면 소인수분해는 얼마나 어려운가? 지금까지 알려진 바에 의하면 소인수분해는 $NP \cap co-NP$에 속한다. 그러나 소인수분해가 $P$에 속하는지는 알려지지 않았다. 추측하기로는 $P$에는 속하지 않고, $NP \cap co-NP$에 속하지 않을까 싶다. 소인수분해와 소수 확인 (Primality) 더보기 # 소인수분해와 소수 (펼치기) 소인수분해를 하면 소수인지 확인할 수 있다. 그러나 소수인지 아닌지 안다고해서 소인수분해가 가능한 것은 아니다. 소수가 아니라면 그 수의 소인수를 찾아야 하기 때문이다. 위에서 말했듯이 소인수분해는 $P$에 있는지 알려지지 않았다. $n$이 소수..

Complete Residue System $Z_{6}=\{0,1,2,3,4,5\}$에서, $5 \times 5=1 \mod 6$이므로 $5$의 역원은 $5$이다. 그런데 $2$와 곱해서 $1$이 되는 수, 즉 $2$의 역원은 존재하지 않는다. 따라서 Complete Residue System에서는 곱셈이 잘 정의되지 않는다. 곱셈이 잘 정의되지 않는다는 말은 역원 또는 항등원이 존재하지 않는다는 말과 같다. 우리는 곱셈과 나눗셈이 잘 정의되는 Residue System을 원한다. Reduced Residue System $Z_{m}^{*}=\{a|\gcd(a,m)=1,~0 \le a < m\}$ $Z_{m}^{*}$에서 곱셈이 잘 정의된다는 것을 증명한다. $\forall a \in Z_{m}^{*},..

이번주면 정수론은 끝난다. 다음주에는 지금 배우는 내용을 바로 써먹을 수 있는 암호를 공부한다. $a|bc,~\gcd(a,~b)=1 \Rightarrow a|c$ $a$가 $bc$를 나눈다. 그런데 $a$와 $b$의 최대공약수가 $1$이라면 $a$는 $b$를 나누지 못한다. 따라서 $a$가 $c$를 나눠야만 한다. 직관적으로는 당연하지만 한번 증명해 보자. 증명 $a|bc$이므로 $bc=ka$를 만족하는 정수 $k$가 존재한다. 또한 $\gcd(a,~b)=1$이므로 $ax+by=1$을 만족하는 정수 $x,~y$가 존재한다. $ax+by=1$의 양변에 $c$를 곱하면 $acx+bcy=acx+kay=a(cx+ky)=c$이다. $c=k'a$ 꼴로 나타낼 수 있으므로 $a$가 $c$를 나누고, $a|c$이다. ..