Gae Ko's Blog

R u Ronald Rivest 재승이 블로그에 있는 라이트업을 보고 풀이 흐름을 깨닫고 모르는 부분에 대해 찾아서 알아가는 식으로 공부하였습니다. 문제 풀이에 앞서서 RSA에 관한 기본적인 설명---------------------------------------------------------------------------------------RSA- 공개키 암호 시스템으로 공개키와 개인키를 사용- 공개키는 모두에게 알려져 있으며 암호화할 때 사용하고 개인키를 가진 자만이 암호화된 것을 복호화할 수 있음 - 키 생성 과정n = pq (p와 q는 서로 다른 두 소수)Φ(n) = (p-1)(q-1)gcd(e, Φ(n))= 1인 e선택하여 ed mod Φ(n)=1인 d 생성 이 때 확장된 유클리드 호제법..

http://sage.skku.edu/

이 문제를 풀기 전에 RSA와 중국인의 나머지 정리에 대해 공부하였다.이 문제를 풀고 이해하기에 필요한 정도로 설명하면 다음과 같다. RSA- 공개키 암호 시스템으로 공개키와 개인키를 사용- 공개키는 모두에게 알려져 있으며 암호화할 때 사용하고 개인키를 가진 자만이 암호화된 것을 복호화할 수 있음 - 키 생성 과정n = pq (p와 q는 서로 다른 두 소수)Φ(n) = (p-1)(q-1)gcd(e, Φ(n))= 1인 e선택하여 ed mod Φ(n)=1인 d 생성 이 때 확장된 유클리드 호제법을 사용하여 d를 구한다 - 암호화 : c = m^e mod n - 복호화 : m = c^d mod n 중국인의 나머지정리 (CRT : Chinese Remainder Theorem)- 서로소인 자연수들에 대한 연립합..