공부 저장소

암호론 검색 결과

해당 글 3건

생일 패러독스, 생일 공격

$n$명의 사람이 있다. 이 사람들의 생일이 모두 다를 확률은 얼마나 될까? $$\prod_{i=1}^{n-1} \left( 1 - \frac{i}{365} \right)$$ 이다. 이 경우 $n = 23$만 되어도 이미 확률이 절반 이하가 된다. 생각보다 적은 수의 사람이 모여도 꽤 높은 확률로 생일이 같은 두 사람을 찾을 수 있다는 것이 생일 패러독스이다. 이를 이용하여 충돌쌍 하나를 효과적으로 구하는 암호론적 공격이 생일 공격이다. 해시함수의 충돌값을 찾거나, 블록암호를 공격할 때 사용된다. Factoring 문제를 효과적으로 푸는 Pollard's rho 랜덤 알고리즘도 똑같은 원리를 기반으로 한다. 특히 블록암호에서 어떤 함수 $G$에 대해 $G(x) = G(y)$인 서로 다른 문자열 $x,..

Mathematics 5년 전

소수 밀도 하한의 간단한 증명

베르트랑의 공준 증명에서 조그만한 아이디어를 가져왔다. 소수 밀도 하한에 대한 초등적이면서 Big-$O$ 표기법으로는 실제와 동일한 결과가 나오는 간단한 증명인 것 같다. 1부터 $n$까지 소수의 개수를 $\pi(n)$이라고 하자. Theorem. 임의의 자연수 $n$에 대하여 $$\pi(n) \geq \frac{n}{2 \log n}$$ 이다. (단 이 글에서 모든 생략된 로그 밑은 2이다.) Claim. $$\pi(2n) \geq \frac{2n}{2 \log 2n}$$ (Proof) $\binom{2n}{n} = N$이라고 하자. 수학적 귀납법에 의해 $N \geq 2^n$을 만족한다. 소수 $p$에 대하여, $p^e | N$이 성립하는 $e$의 최대값을 $f_N(p)$라고 하자. $$ \b..

Mathematics 5년 전

Even-Mansour 블록 암호 security는 2^(n/2) 증명

Even-Mansour 블록 암호란 $n$비트 스트링을 $n$비트 스트링으로 암호화하는 대칭키 암호 시스템이다. 어떤 퍼뮤테이션 $F : \{0, 1\}^n \rightarrow \{0, 1\}^n$이 고정되어 있고(이는 공개적으로 알려져 있다.), 키는 $n$비트 스트링 $K_1, K_2 \in \{0, 1\}^n$이다. 암호화 방식은 $M \in \{0, 1\}^n$ 평문을 받아서 $C = E_{K_1, K_2} (M) = K_2 \oplus F(K_1 \oplus M)$ 으로 구현한다. $F$ 퍼뮤테이션의 역도 계산 가능하므로 복호화는 $M = K_1 \oplus F^{-1} (K_2 \oplus C)$ 로 쉽게 처리할 수 있다. 암호론 교수님께서 본 암호의 security가 $2^{n/2}$ 임을..

Mathematics 5년 전