목록암호학 (1)

donchanee

RSA - 확장 유클리드 호제법 (Extended GCD)

정수 m, n 의 GCD(Greatest Common Divisor)를 gcd(m,n)와 나타낼 때, 확장된 유클리드 호제법을 이용하여, ax + by = gcd(a,b)의 해가 되는 정수 x, y 짝을 찾아낼 수 있다. 특히, x, y이 서로소(gcd(x,y) = 1)인 경우 유용한데, 그럼 위의 식은 ax + by = 1이 되고, 여기서 a는 모듈로 연산의 곱의 역원 (modular multiplicative inverse) 이 되기 때문이다. extended gcd 와 뒤에 포스팅할 CRT (중국인의 나머지 정리) 둘 다 RSA를 위한 기반이 되므로 잘 알아두자. 우선 extended gcd 를 설명하고, python 코드로 구현하는 시연을 하겠다. 확장 유클리드 호제법 위의 소리가 이해가 가지 않..
암호학 2019. 9. 19. 10:07
이전 Prev 1 Next 다음