정수론 수업을 듣고 흥미로운 문제를 들었다.n차 합동방정식은 n개의 서로 다른 해를 가지는데 왜 RSA는 복호화가 잘 되는가?이거에 대해 알아본 결과.A를 특정 값으로 제한해서 복호화가 망가지는 걸 억제하는 것이였다. A값의 제한으로 여러 해 나오지 않게 하기m = pq (p, q는 소수)gcd(ϕ(m), k) = 1 에서 암호화는 c ≡ a^k (mod m) 이다.당연히 c는 양수(암호문은 항상 양수만 생각)이고 m에 대해 유일하다. 그럼 문제의 복호화는?x ≡ c^u ≡ a (mod m) 이다.이때 gcd(ϕ(m), k) = 1 이므로 선형방정식의 정리에 의해ku-ϕ(m)v = 1에서 해 ui, vi를 구할 수 있고 식을 변형하면 ku ≡ 1 mod(ϕ(m))이다.gcd(ϕ(m), k) = 1이므로 ..

이전 글: https://verybigsilver.tistory.com/106 [암호학](-)[RSA 구현 1]이론 암호학 중심 이론 정리https://verybigsilver.tistory.com/55 [암호학 둘러보기](8)[RSA]RSA: 비대칭키 암호화 방식디피-헬만과는 다르게 서명까지 지원해 안전함. (상대방의 공개키를 이용해 암호화하기verybigsilver.tistory.com GMP 라이브러리를 이용한 RSA 구현예전에 짰던 RSA 프로그램은 파이썬이나 C로 짰었는데,파이썬은 시간이 너무 오래 걸리고C는 visual studio 기준으로 long long 64비트밖에 지원을 하지 않아서 오버플로우가 났었다.따라서 C에서 큰 수의 연산을 가능하게 하는 GMP 라는 라이브러리로 다시 구현해 보..

이론 암호학 중심 이론 정리https://verybigsilver.tistory.com/55 [암호학 둘러보기](8)[RSA]RSA: 비대칭키 암호화 방식디피-헬만과는 다르게 서명까지 지원해 안전함. (상대방의 공개키를 이용해 암호화하기 때문)과정메세지 보내는 A, 메세지 받는 B이고 공개된 파라미터 e가 있다.B의 공verybigsilver.tistory.com 수론 중심 이론 정리https://verybigsilver.tistory.com/100 참고 구현 일단 코드를 대충 짜면 이렇게 된다.def extended_gcd(a, b): if b == 0: return 1, 0 # 해는 (1, 0) x1, y1 = extended_gcd(b, a % b) # 재귀 호출 ..