드림핵의 RSA(CRT) 문제를 풀며 RSA의 CRT에 대해 공부해보도록 한다.

RSA란?

암호학에서 매우 널리 쓰이는 공개 키 암호방식 중 하나로 1977년에 Ron Rivest, Adi Shamir, Leonard Adleman 세 사람이 개발해서 이름도 그들의 성(Rivest-Shamir-Adleman)에서 따왔다.

RSA의 기본 개념

• 공개키 암호 방식
  암호화와 복호화에 서로 다른 키를 사용하는 암호 방식이다.

공개키 (Public Key): 누구에게나 공개해서 메시지를 암호화할 때 사용

비밀키 (Private Key): 오직 키 소유자만 가지고 복호화에 사용

RSA 동작 원리

1. 키 생성

   1. 큰 소수 p와 𝑞 두 개를 랜덤하게 선택
   2. n = p × q 계산 (RSA 모듈러스)
   3. ϕ(n)=(p−1)(q−1) 계산 (오일러 피 함수)
   4. 공개 지수 𝑒를 선택 (1 < e < 𝜙(𝑛), 보통 65537이 많이 사용됨)
   5. 비밀 지수 d를 계산,
      𝑑 × 𝑒 ≡ 1 mod  𝜙(𝑛) 조건을 만족하는 수

2. 암호화
   평문 𝑀을 암호문 𝐶로 변환

3. 복호화
   암호문 𝐶를 평문 𝑀으로 변환

RSA의 특징

• 소인수분해의 어려움에 기반
• 공개키로 누구나 암호화 가능하지만, 비밀키 없이는 복호화 불가
• 디지털 서명에도 사용 가능
• 키 길이가 길 수록 보안이 강해지지만 속도는 느려짐 ( 보통 2048비트 이상 권장 )

CRT ( 중국인의 나머지 정리 )

CRT는 여러 개의 서로소인 (서로 나누어떨어지지 않는) 정수들에 대해, 각각의 나머지를 알고 있을 때 원래의 수를 유일하게 복원할 수 있다는 정리

어떤 수 x가 있을 때,
x mod n1 = a1
x mod n2 = a2
.
.
.
x mod nk = ak

에서 n1, n2... nk가 서로소 일 때, 이 때 유일한 x를 찾을 수 있다는 것이 CRT이다.

RSA 복호화는 큰 수의 모듈러 지수 연산을 하는데, 이 계산이 매우 느리다.

즉 CRT를 이용하여 작은 모듈러 연산을 하고, 결과를 합쳐서 전체 연산 속도를 높이기 위해 사용한다.

CRT의 장점

• 큰 수 연산을 두 개의 작은 수 연산으로 분할하여 연산 속도 향상
• RSA 구현에서 표준적으로 사용됨 (많은 라이브러리에서 CRT 최적화를 기본 제공)

CRT의 쉬운 예시 (3개의 모듈러)

찾고싶은 수 X가 있다.

조건 :
x % 3 = 2
x % 5 = 3
x % 7 = 2

이라고 한다. 위 값을 만족하는 X를 찾을 것 이다.

p1 = 3
p2 = 5
p3 = 7

c1 = x % 3 = 2
c2 = x % 5 = 3
c3 = x % 7 = 2

1. 전체 곱 구하기

N = p1 p2 p3 = 3 5 7 = 105

2. 각 모듈러를 제외한 곱 구하기

M1 = N / p1 = 105 / 3 = 35
M2 = N / p2 = 105 / 5 = 21
M3 = N / p3 = 105 / 7 = 15

3. 각 Mi의 모듈러 역원 구하기

• 우리가 아는 M1이 있다.
  M1은 35이다.
  그런데 M1은 3으로 나누면 나머지가 2이다.
  CRT 공식에서는 이 숫자를 1로 만들어야 한다.
  즉 35 * inv1을 3으로 나눈 나머지가 1이여야 한다.

M1 * inv1 ≡ 1 mod p1을 만족하는 inv1을 찾아야 한다.

35 * inv1 ≡ 1 mod 3

위의 수식에서 inv1이 2일 때 조건을 만족한다.

21 * inv2 ≡ 1 mod 5

위의 수식에서 inv2는 1일 때 조건을 만족한다.

15 * inv3 ≡ 1 mod 7

위의 수식에서 inv3는 1일 때 조건을 만족한다.

4. CRT 공식으로 x 구하기

x = ( c1 x M1 x inv1 ) + ( c2 × M2 × inv2 ) + ( c3 × M3 × inv3 ) mod N

x = ( 2 35 2 ) + ( 3 21 1 ) + ( 2 15 1 ) mod 105

x = ( 140 + 63 + 30 ) mod 105 = 23

위의 조건을 만족하는 x는 23이다.

23 % 3 = 2
23 % 5 = 3
23 % 7 = 2

이렇게 CRT를 이용하여 알고 싶은 X를 구해낼 수 있다.

예시 문제 ( Chinese What? )

먼저 위 문제에서는
서로다른 서로소인 p1 p2 p3가 주어지고,
flag에 대한 모듈러 연산인
flag % p1 = c1
flag % p2 = c2
flag % p3 = c3
로 c1 c2 c3가 주어진다.

CRT를 이용하여 flag를 획득하여야 한다

먼저 p와 c는 문제에서 주어진다.
p1 = 1527207470243143973741530105910986024271649986608148657294882537828034327858594844987775446712917007186537829119357070864918869
p2 = 2019864244456120206428956645997068464122219855220655920467990311571156191223237121636244541173449544034684177250532278907347407
p3 = 1801109020443617827324680638861937237596639325730371475055693399143628803572030079812427637295108153858392360647248339418361407
c1 = 232762450308730030838415167305062079887914561751502831059133765333100914083329837666753704309116795944107100966648563183291808
c2 = 869189375217585206857269997483379374418043159436598804873841035147176525138665409890054486560412505207030359232633223629185304
c3 = 1465704473460472286244828683610388110862719231828602162838215555887249333131331510519650513265133531691347657992103108331793683

수가 매우 크므로 파이썬 스크립트를 작성하도록 하겠다.

1. 전체 곱 구하기

N = p1 p2 p3 를 구한다.

2. 각 모듈러를 제외한 곱 구하기

Mi = N / pi

3. 각 Mi의 모듈러 역원 구하기

이때 모듈러 역원을 구하는 확장 유클리드 알고리즘에 대해 알아본다.

일반 유클리드 알고리즘

1. 두 수 a, b 의 최대공약수 (GCD)를 구한다.
2. gcd(a,b) = gcd(b, a % b)를 반복

확장 유클리드 알고리즘

1. 두 수 a, b 의 최대공약수 (GCD)를 구한다.
2. a x X + b x y = gcd(a,b)를 만족하는 x, y도 구한다.

예를 들어 a = 3, m = 7일 때,
3 x X = 1 mod 7 을 만족하는 x를 구한다.

위의 식을 다시 말하면, 3 * x에서 1의 차가 7로 나누어 떨어진다는 말이다.
즉 3 x X - 1 ≡ 0 mod 7 이다.
이는 7에 어떤 값을 곱했을 때, 3 x X - 1이 된다는 말이다.

3 x X - 1 = 7 x k
-> 3 x X = 7 x k + 1
-> 3 x X + 7 x (-k) = 1

이 때 -k를 그냥 Y로 치환

3 x X + 7 x Y = 1 ( 이때 X, Y는 정수 )

gcd(7,3):
7 = 2 * 3 + 1 ( 선형식으로 표현 )

1 = 7 - 2 * 3
7 x 1 + 3 x (-2) = 1

만족하는 x , y를 찾아냈다.
x = 1, y= -2

1. 처음에 gcd(a, b)를 구한다.
2. 동시에, 재귀적으로 ax + by = gcd(a,b)의 해 x, y를 찾아간다.

4. CRT 공식으로 flag 구하기

이제 모듈러 역원을 구했고, CRT 공식을 이용하여 전체 값을 얻는다.

먼저 flag의 int값은
3252605711388626316882631631674717103450798162113861327856306348774981010636439640993654302182152291893666887426485817372503250437288712874365

이제 int값을 이용해서 바이트 단위로 변경한 다음 디코딩 한다.

flag의 길이가 8의 배수가 아닐 때를 생각하여 7을 더한 다음 8로 나누어 1바이트 단위로 나눈다. 그리고 빅엔디언으로 표현한다.

처음에 flag는 bytes_to_long을 이용하여 int값으로 바뀌었다. 그러므로 복호화를 할 때는 to_bytes함수를 이용하여 다시 byte값으로 만들어주었다.

이렇게 하면 FLAG값을 구할 수 있다.

Flag : DH{Th3Ch1n35e_r3m4iNd3r_tHe0r3m_w4s_qu1T3_345y_r1ght??:)}

마치며

공부를 하며 의문점이 생겼다. 3단계에서 inv1은 5일 때도 위의 수식을 만족한다. 그렇다면 inv를 구할 때 조건은 가장 작은 자연수를 선택하는 것인가?

답은 모듈러 연산에서는 0보다 크고, m보다 작은 값 중에서 가장 작은 값 하나를 사용하는 것이 관례이다.
즉, mod m 안에서 가장 작은 양의 정수 값이라고 한다.

모듈러 연산에서 동일한 값을 내놓는 것들. 즉 위의 연산에서는 2와 5와 8이 같은 것으로 간주된다고 한다.

또한 확장 유클리드 알고리즘은 아직 더 이해가 필요해 보인다. 정리하긴 했지만, 완전히 이해하는데에는 어려움이 있다.. 직관적으로 쉬운 예시를 들을 때는 이해가 갔지만, 큰 수를 대입하여 코드상으로 작성하려니 어려움이 있었다.