s프레쏘

암호학 검색 결과

해당 글 3건

중국인의 나머지 정리

Chinese remainder theorem (CRT) 양의 정수들 $n_1,n_2,\cdots ,n_k$가 $1\le i\ne j\le k$, $gcd(n_i,n_j)=1$(서로소)를 항상 만족할때, 아래의 연립합동식이 법 $M=n_1{n}_2\cdots n_k$에 대해 유일한 해를 가진다. $$x\equiv a_1(\mathrm{mod}{n}_1)$$ $$x\equiv a_2(\mathrm{mod}{n}_2)$$ $$⋮$$ $$x\equiv a_k(\mathrm{mod}{n}_k)$$ 증명 ( 존재성과 유일성) $M=n_1{n}_2\cdots n_k$ $M_i=M/n_i$라고 할 때, $n_j\ne n_i$인 모든 $n_j$에 대해 $M_i\equiv 0(\mathrm{mod}{n}_j)$ 이다. $gcd(n_i,n_j)=1$이므로 (1외에 공유하는 인수가 없으므로) $g..

수학 3년 전

오일러 정리

$a^{\phi (n)}\equiv 1(\mathrm{mod}n)$ if $gcd(a,n)=1$ ($a$와 $n$이 서로소) $\phi (n)$: $n$과 서로소인 $n$이하의 자연수의 갯수 증명 $Z_n^{\ast }=S=\{b_1,b_2,\cdots ,b_{\phi (n)}\}$ ($Z_n^{\ast }$은 양의 정수 n이하의 n과 서로소인 자연수 집합) $aS=\{a{b}_1,a{b}_2,\cdots ,a{b}_{\phi (n)}\}$ 일 때, S의 임의의 서로 다른 두 원소 $b_i$와 $b_j$ 는 n으로 나눈 나머지가 항상 다르다...(1) ($\because b_i,b_j$두 수의 차의 범위는 $0<|b_i-b_j|\le (n-2)$이다. 이 범위에서 $n$의 배수는 없다. 즉 $|b_..

수학 3년 전

암호문 훔치기

CTS(CipherText Stealing) Padding 방식 중 하나. CBC기준 설명 Pn : 마지막 평문 블럭 B : 마지막블럭을 제외한 일반 블럭 길이 M : Pn의 길이 En-1 : E(Pn-1 XOR Cn-2, K) (여기까진 일반 CBC 과정이다.) Cn : head(En-1, M). En-1에서 앞부분 M비트만 남기고 지운다. B-M 비트가 제거된다. P : Pn

정보보호론 3년 전