CRT 검색 결과

해당 글 2건

중국인의 나머지 정리

Chinese remainder theorem (CRT) 양의 정수들 $n_1, n_2 ,\cdots , n_k$가 $1\leq i \neq j \leq k$, $gcd(n_i,n_j)=1$(서로소)를 항상 만족할때, 아래의 연립합동식이 법 $M=n_1n_2\cdots n_k$에 대해 유일한 해를 가진다. $$x≡ a_1\pmod{n_1}$$ $$x≡ a_2\pmod{n_2}$$ $$\vdots$$ $$x≡ a_k\pmod{n_k}$$ 증명 ( 존재성과 유일성) $M=n_1n_2\cdots n_k$ $M_i = M/n_i$라고 할 때, $n_j\neq n_i$인 모든 $n_j$에 대해 $M_i ≡ 0 \pmod{n_j}$ 이다. $gcd(n_i,n_j)=1$이므로 (1외에 공유하는 인수가 없으므로) $g..
수학 2022. 3. 12. 13:48

RSA

핵심 개념은 $x^{ed}≡x \pmod{pq}$이다. ($x$는 평문, $x^{e}(\mbox{mod } pq)$는 암호문, $e$: Encrytion exponent, $d$: Decryption exponent) x를 e로 암호화하고 d로 복호화 하면 다시 평문x가 나오며, 반대로 d로 암호화, e로 복호화 해도 평문 x가 나온다.(전자서명에서 사용) p와 q는 매우 큰 소수이다. 키사이즈 N비트는 pq를 말한다. $\varphi(pq) = (p-1)(q-1)$ $x^{\varphi(pq)} ≡ 1 (\mbox{mod }pq)$ 오일러 정리 $a^{\varphi(n)}\equiv 1 \pmod{n}$ if $gcd(a,n)=1$ ($a$와 $n$이 서로소) $\varphi(n)$: $n$과 서로소인..
정보보호론 2022. 2. 21. 19:13