확장 유클리드 알고리즘
m, n이 gcd(m,n) = 1인 경우 유용한데, 그럼 위의 식은 am + bn = 1이 되고, 여기서 a는 모듈로 연산의 곱의 역원(modular multiplicative inverse)이 되기 때문이다.
출처 : 위키백과
확장 유클리드 알고리즘은 RSA를 만들기 위한 과정 중 복호키(또는 비밀키 라고도 부른다)를 구하기 위해 필요한 알고리즘이다.
일단 지금은 이 정도만 알고 넘어가도록 하자.
확장 유클리드 알고리즘은 정말 단순히 유클리드 알고리즘(gcd)연산을 거꾸로 한 것이다.
수식으로 설명을 들어보자,
a , b = 서로소인 두 정수(알기 쉽게 설명하기 위해서 서로소로 정했다\\ 원래는 어떤 수 라도 상관 없다.)
r(1),r(2),r(3)… = 나머지
q(1),q(2),q(3)… = 몫
라고 하면, 유클리드 알고리즘은
gcd(a,b)
=> a = b*q(1) + r(1) >> gcd(b,r(1))
=> b = r(1)*q(2) + r(2) >> gcd(r(1),r(2))
=> r(1) = r(2)*q(3) + r(3) >> gcd(r(2),r(3))
……
=> r(n-1) = r(n)*q(n+1) + r(n+1) >> gcd(r(n),r(n+1))
=> r(n) = r(n+1)*q(n+2) + 1 >> gcd(r(n+1),r(n+2))
=> r(n+1) = 1*r(n+1) + 0 >> gcd(1,0)
∴ gcd(a,b) = 1
이렇게 진행 된다.
=====================================================
이제 확장된 유클리드 알고리즘 이용해 보자.
방법은 단순히 위에 연산을 거꾸로하고 대입하여 한 식으로 계산하면 된다, 아래를 참고하자.
[원래는 1 부터지만 거꾸로 계산했다는 것을 보여주기 위해 0부터 시작하겠다.]
0 = r(n+1) – 1*r(n+1) <=> r(n+1) = 1*r(n+1) + 0
1 = r(n) – r(n+1)*q(n+2) <=> r(n) = r(n+1)*q(n+2) + 1
r(n+1) = r(n-1) – r(n)*q(n+1) <=> r(n-1) = r(n)*q(n+1) + r(n+1)
……
r(3) = r(1) – r(2)*q(3) <=> r(1) = r(2)*q(3) + r(3)
r(2) = b – r(1)*q(2) <=> b = r(1)*q(2) + r(2)
r(1) = a – b*q(1) <=> a = b*q(1) + r(1)
이제 거꾸로 구한 식을 한 식에 모두 대입하자. (복잡하니 n = 2 라고 두자) (a, b, q(),r() 은 모두 상수 이다. )
[“0 = ~”은 양변이 모두 0 이므로 사용 할 수 없으니 “1 = ~”를 사용했다]
1 = r(2) – [r(1) – [b – [a – b*q(1)]*q(2)]*q(3)]*q(4)
이렇게 식을 만들고 정리 하면 1 = ☆×a + ★×b 이런 모양이 된다.
∴ 1 ≡ ☆×a + ★×b (mod a) 라면, ★값이 역원(우리가 찾는 값) 이고
1 ≡ ☆×a + ★×b (mod b) 라면, ☆ 값이 역원 이다.
즉, mod a 라면 b에 곱해진 수가 역원 mod b라면 그 반대 라는 것이다.
(∵ A≡R (mod P) 이면. A = A*X + R 양변에 P를 더해 준다면 => A + P = P* (X + 1) + R이다.
따라서 나머지(다른)값은 변화가 없음으로, 위에서 mod a 일때, ☆×a 값을 무시 할 수 있다.)
자 이렇게 확장 유클리드 알고리즘에 대한 기본 설명은 끝났다.
이해가 잘 가지 않을 수도 있으니 간단한 예를 들어보자.
a = 576, b = 31
유클리드 알고리즘
576 = 31 × 18 + 18
31 = 18 × 1 + 13
18 = 13 × 1 + 5
13 = 5 × 2 + 3
5 = 3 × 1 + 2
3 = 2 × 1 + 1 ∴ gcd(576,31) = 1, 서로소 이다.
확장 유클리드 알고리즘(빠르게 계산 하기 위해 바로 “1 = ~”으로 시작하겠다.)
1 = 3 – 2 × 1
= 3 – [5 – 3 × 1] × 1
= 3 – [5 – [13 – 5 × 2] × 1] × 1
= 3 – [5 – [13 – [18 – 13 × 1] × 2] × 1] × 1
= 3 – [5 – [13 – [18 – [31 – 18 × 1] × 1] × 2] × 1] × 1
= 3 – [5 – [13 – [18 – [31 – [576 – 31 × 18] × 1] × 1] × 2] × 1] × 1
──────────이해를 위한 순서──────────┘
= 1 = 3 – 2
= 3 – (5 – 3)
=> 2 * 3 – 5 << 정리를 해야 나중에 원하는 모양이 나옴
= 2 * ( 13 – 5 * 2 ) – 5
=> 2 * ( 13 ) – 5 * 5
= 2 * 13 – 5 * ( 18 – 13 )
=> -5 * ( 18 ) + 7 * 13
= -5 * 18 + 7 * ( 31 – 18 )
=> 7 * 31 – 12 * ( 18 )
= 7 * 31 – 12 * ( 576 – (31 * 18) )
=> -12 * 576 + 223 * 31
──────────실제 계산 순서──────────┘
=> -12 × 576 + 223 × 31 ≡ 1 (mod 576)
∴ 역원(우리가 찾는 값)은 223 이다.
위 알고리즘을 이용해 C언어로 코딩 하기전에 잠깐 생각해야 되는 부분이 있다.
우리가 필요한 값은 결과로 나오는 1 = ☆×a + ★×b 중에서 ☆or★이라는 점을 기억 해야 한다.
이제 한번 코딩해 보자.
#include <stdio.h> #include <stdlib.h> #define INT unsigned int INT inverse(INT a, INT b) { long r1, r2, q, r, t, t1, t2; r1 = a; r2 = b; t1 = 0; t2 = 1; while (r1 != 1) { q = r2 / r1; r = r2 - r1*q; t = t1 - t2*q; r2 = r1; r1 = r; t1 = t2; t2 = t; } if (t2 < 0) t2 = t2 + b; return t2; }
1 = ☆×a + ★×b 일때,
☆ | t1 << 우리가 찾는 값 |
★ | t2 |
a | r1 |
b | r2 |
t, q, r | 임시 저장 공간(단, q는 몫을 임시 저장한다) |
이렇게 정리 할 수 있다. 이번 글은 이해하기 어려웠다. 하지만 차근차근 하다 보면 이해 할 수 있을 것이다.
다음 글에선 이것 보다 간단한 고속 누승 알고리즘에 대해 알아보도록 하자.
부록 _ RSA에선 어떻게 쓸까?
e × d ≡ 1 (mod (N))에 이미 알고 있는
N [= p×q, 임의의 두 소수p, q] \\ (N)[= (p-1)(q-1)] \\ e (= gcd(e,
(N)) = 1이 되는 e)의 값을 대입하여 확장 유클리드 알고리즘을 이용해 비밀키 d 값을 구한다.
잘봄
n=55 p=5 q=11 e=7 로 하면 안되던데 왜그런거죠 ㅠㅠ