[CryptoHack] Extended GCD

양의 정수 a와 b가 있을 때,
확장된 유클리드 알고리즘은 다음과 같은 정수 u,v를 찾는 효율적인 방법이다.

a * u + b * v = gcd(a,b)

 

나중에 RSA를 해독하는 방법을 배울 때

공개 지수의 모듈러 역수를 계산하기 위해 이 알고리즘이 필요하다고 한다.

 

확장된 유클리드 알고리즘에 대한 자세한 내용은 아래 페이지를 확인하라고 한다.

https://web.archive.org/web/20230511143526/http://www-math.ucdenver.edu/~wcherowi/courses/m5410/exeucalg.html

Extended Euclidean Algorithm

 

---

gcd(81, 57)은 다음과 같은 과정으로 찾아진다.

def gcd(a, b):
    print(f'{a} = {a//b}({b}) + {a%b}')
    if a % b == 0:
        return b
    else:
        return gcd(b, a%b)

print(gcd(81,57))

81 = 1(57) + 24
57 = 2(24) + 9
24 = 2(9) + 6
9 = 1(6) + 3
6 = 2(3) + 0
3

gcd(a, b) = r 일 때, 다음을 만족하는 정수 p, s가 존재한다.

p(a) + s(b) = r

 

이 정수 p, s를 찾으려면 gcd(a, b) 연산을 역으로 계산하면 된다.

위에서 봤듯이 gcd(81, 57) = 3이며

연산 과정을 가지고 역연산을 하면 다음과 같이 식을 쓸 수 있다.

3 = 9 -1(6)

From the line before that, we see that 6 = 24 - 2(9), so:
3 = 9 - 1(24 - 2(9)) = 3(9) - 1(24)

From the line before that, we have 9 = 57 - 2(24), so:
3 = 3( 57 - 2(24)) - 1(24) = 3(57) - 7(24)

From the line before that 24 = 81 - 1(57), giving us:
3 = 3(57) - 7( 81 - 1(57)) = 10(57) -7(81)

So we have found p = -7, s = 10

 

---

 

연습 문제는 다음과 같다.

두 소수 p = 26513, q = 32321을 사용하여 다음과 같은 정수 u,v를 찾습니다.

p * u + q * v = gcd(p,q)

u와 v 중 낮은 숫자를 플래그로 입력합니다.

 

gcd를 구한 뒤 역으로 구해나가는 방식으로 u, v를 구할 수 있다.

 

파이썬 코드는 다른 구현된 코드를 참고해서 다음과 같이 짰다.

a*x + b*y = gcd(a, b) 의 형태로 보고 짠 코드이다.

(a>b 를 만족해야 함)

def egcd(a, b):
    global my_gcd
    if a%b == 0:
        my_gcd = b
        return 1, 0
    else:
        x, y = egcd(b, a%b)
        return y - (a//b)*x, x

print(egcd(32321,26513))

(10245, -8404)

 

 

---

레퍼런스

https://cryptohack.org/courses/modular/egcd/

CryptoHack – Home

 

 

---

이해를 위한 발버둥의 흔적..

'''
# gcd(81,57)

81 - 1(57) = 24
57 - 2(24) = 9
24 - 2(9) = 6
9 - 1(6) = 3
6 - 2(3) = 0
 
3 = 9 - 1(6)
  = a - (a//b)(b)
  = (1)a + (-1)b

3 = 9 - 1(24 - 2(9)) 
  = 3(9) - 1(24)
  = (3)b + (-1)a

3 = 3(57 - 2(24)) - 1(24)
  = 3(57) - 7(24)
  = (3)a + (-7)b

3 = 3(57) - 7(81 - 1(57))
  = 10(57) - 7(81)
  = (10)a + (-7)b
  
a  b       x   y     a//b
81 57     10  -7      1
57 24     -7   3      2
24  9      3  -1      2
 9  6     -1   1      1
 6  3      1   0      1
'''