본문 바로가기
728x90

해킹34

Chinese Remainder Theorem 중국인 나머지 정리 오늘의 마지막 포스팅은 '중국인의 나머지 정리' 입니다. RSA 에 중요한 정리임으로 꼭 알아두셔야합니다! 중국인의 나머지 정리란? -> 어떤 정수 값은 서로소 관계에 있는 moduler의 나머지 값으로 표현될 수 있다. 예를 들어 Z10 공간엔 10개의 정수 0~9가 존재합니다. 그럼 이 수 들은 modulo 2 와 5로 표현이 가능 합니다. r2 = 0 고 r5 = 3 이면 8입니다. (2와 5는 서로소 관계입니다.) 이렇게 2와 5처럼 modulo 연산을 시행하는 수를 mi 라고 표현합니다. 그리고 mod M = m1m2m3 ...mk로 구성이 됩니다. 중국인의 나머지 정리(CRT)의 핵심은 큰 연산을 작은 연산으로 쪼개줌에 있습니다. CRT m1,m2,m3,m4..mn 은 pairwise rela.. 2020. 5. 26.
Carmichael Number&Miller-Rabin Test 안녕하세요. 부산 공수니 입니다. 오늘은 제목과 같이 Carmichael Number 와 Miller-Rabin Test 에 대해 알아보겠습니다. 일단 Fermat's 소정리가 활용되는데요. 모르시는 분은 아래의 포스팅을 확인해주세요! https://com24everyday.tistory.com/44 Fermat's Theorem/페르마의 정리 안녕하세요. 오늘은 Fermat's Theorem 에 대해 알아보도록 하겠습니다. 만약 p가 Prime Number 일 때 (소수) , gcd(a,p)=1->서로소 일 때 a^(p-1) = 1 ( mod p ) a^p = a( mod p ) Fermat's Theorem 은 public key.. com24everyday.tistory.com 페르마 소정리에 의하.. 2020. 5. 25.
Group,Rings, and Fields https://www.youtube.com/watch?v=Lq8b9yw8uPk 유튜브 설명영상을 찍었습니다! 굉장히 허접한데 발전해 가는 모습 모여드리겠습니다ㅠㅠ Number Theory 중에서도 보안에서 꼭 알아야하는 'Group'에 대해 알아보겠습니다. 전체적인 집합의 그림은 아래와 같습니다. 저희는 오늘 Group,Field,Ring에 대해 집중적으로 공부해보도록 하겠습니다. 이러한 집합들은 '어떠한 연산을 만족시키는' 기준으로 집합이 형성됩니다. 여기서 '어떠한 연산'이 존재하는지 알아보겠습니다. Properties of Operator ⊕ : k X k -> k (하나의 연산자라고 생각을 해주시면 됩니다.) (1) Closure : 닫혀있다 라는 의미. 집합 {1,2,3} 있을때 연산을 아무리 .. 2020. 5. 21.
Fermat's Theorem/페르마의 정리 안녕하세요. 오늘은 Fermat's Theorem 에 대해 알아보도록 하겠습니다. 만약 p가 Prime Number 일 때 (소수) , gcd(a,p)=1->서로소 일 때 a^(p-1) = 1 ( mod p ) a^p = a( mod p ) Fermat's Theorem 은 public key 와 primality testing 에 유용하다 . 테이블을 잘 보면 a 의 숫자에 따라 반복되는 숫자들이 있다. 2,6,7,8 등은 2부터 10 까지 3,4,5,9 는 4개의 숫자가 반복된다. 10은 10,1 에서 반복되는 것을 볼 수 있다. 이렇게 전체를 Generator 하는 수는 (여기선 2,6,7,8) 의 수와 동일하다. Fermat's Theorem 증명 Proof of a^(p-1) ( mod p ),.. 2020. 5. 12.
728x90