| [ POSTECH ] in KIDS 글 쓴 이(By): whbear (서병국) 날 짜 (Date): 1997년05월28일(수) 21시59분39초 KDT 제 목(Title): [Re] Rabin 방식에 대해서 묻습니다. 지금 이 필중 교수님의 수업(정보보안)을 들으신 분이라면 최근에 배웠을 텐데요. Schnier의 Applied Cryptography를 보면 19.5장에 나와있습니다. 자세한 식은 생략하구요. 평문을 M이라고 할 때, 암호화된 문서를 C라고 하면, C = M^2 mod n ( n = pq, p,q are prime ) 이런 방법으로 구하죠, 공개키 방식이니까, 어떤 사람 A의 공개키를 n(=pq), 비밀키를 p,q라고 볼 수 있습니다. A에게 비밀 문서를 보내고 싶은 사람은 A의 공개키 n이 공개되어 있으므로 위와 같은 식을 이용하여 A에 암호화된 문서 C를 보내게 됩니다. C는 단지 M의 square니까, 쉽게 square root를 구하여 M을 찾을 수 있지 않느냐! 라고 반문하실 수도 있겠지만, mod n 하에서는 그것이 일반적으로 매우 힘든일이며 그 일 보다는 n을 p,q로 factoring하는 즉 A의 비밀키를 알아내는 것이 square root 하는 것보다는 쉬운 일이라고 합니다. 하지만 factoring하여 p,q를 알아내는 것은 n의 size가 클 때는 polynomial time안에 쉽게 끝나는 일은 아니며, 이 어려움은 RSA의 암호학 적 견고성과 맥락을 같이 합니다. 그럼 A는 어떻게 C를 M으로 복호화(decrypt)하냐구요? A는 p,q를 알고 있기때문에 CRT(chinise remainder thoerem)을 이용하면 쉽게 M을 얻어낼 수 있습니다. 정리하면, A에게 암호문을 보내고 싶은 사람은 공개키(n)을 이용하여 은밀하게 보낼 수 있으며, A는 비밀키(p,q)를 이용하여 암호문을 복호화하여 내용을 볼 수 있읍니다. 공격자가 C를 가로채도 n을 소인수분해해야 하는 어려움 때문에 원문(M)을 보는 것이 암호알고리듬상 불가능 합니다. 더 자세한 사항은 책을 보시고 관련 논문을 찾아보는 것이 어떠할지... 도움 되었나요? :) 백꼼 Postech M '97 |