2016 국가암호공모전 (Ⅱ-A) 분야 문제 01 문제

2016 국가암호공모전 (Ⅱ-A) 분야 문제 01 문제.pdf

이 문제를 풀기 전에 RSA와 중국인의 나머지 정리에 대해 공부하였다.

이 문제를 풀고 이해하기에 필요한 정도로 설명하면 다음과 같다. 

RSA -  공개키 암호 시스템으로 공개키와 개인키를 사용 -  공개키는 모두에게 알려져 있으며 암호화할 때 사용하고 개인키를 가진 자만이 암호화된 것을 복호화할 수 있음  -  키 생성 과정 n = pq (p와 q는 서로 다른 두 소수) Φ(n) = (p-1)(q-1) gcd(e, Φ(n))= 1인 e선택하여 ed mod Φ(n)=1인 d 생성      이 때 확장된 유클리드 호제법을 사용하여 d를 구한다   - 암호화 : c = m^e mod n  - 복호화 : m = c^d mod n

중국인의 나머지정리 (CRT : Chinese Remainder Theorem) - 서로소인 자연수들에 대한 연립합동식의 유일한 해를 찾는 정리  - 정의 및 계산 방법은 다음과 같다.    k개의 서로소들  와 임의의 정수 a1, a2, ... , ak가 있을 때, 임의의 i (1 ≤ i ≤ k)에 대해  x ≡ ai  (mod ni)        로 표현되는 변수 x의 연립합동방정식에 대해 성립하는 해는 유일하게 존재한다.   그 해를 어떻게 구할까?? 서로소인 음이 아닌 정수  에 대해서  라 하자.  각 에 대해서  와 는 서로소 이므로, 인 정수 가 항상 존재한다.  ∵ 확장 유클리드호제법  라고 하면 다음이 성립한다.  ei ≡ 0  (mod ni)  ei ≡ 1  (mod nj)    (i ≠ j) 여기서  라 하면   a ≡ ai  (mod ni)  ∀ i = 1, 2, ... ,k  이 성립하고 여기서 a 가 해가 된다.

문제 설명 (...) 

OAEP(Optimal asymmetric encryption padding)와 같은 별도의 패딩 방법을 이용하지 않는 textbook RSA 공개키 암호 시스템의 키 생성, 암호화, 복호화 과정은 각각 다음과 같다.

[ 키 쌍 생성 ]
    (1) 두 소수(prime number) p, q를 임의로 선택 (단, p  ≠  q)
    (2) n = p × q 및 Φ(n) = (p - 1) × (q - 1) 계산
    (3) gcd(Φ(n), e) = 1이고 1 < e < Φ(n)인 e를 임의로 선택
    (4) (e × d) mod Φ(n) = 1을 만족하는 d를 계산
    (5) (d, n)을 개인키로 저장하고, (e, n)을 공개키로 공개

[ 암호화 ]
    (1) 암호화할 텍스트 메시지를 적절한 규칙에 의해 정수 m으로 변환 (단, 0 ≤ m < n)
    (2) 공개키 (e, n) 및 m을 이용하여 암호문 c = m^e mod n 계산

[ 복호화 ]
    (1) 암호문 c 및 개인키 (d, n)을 이용하여 평문 m = c^d mod n 계산
    (2) 정수 m을 적절한 규칙에 의해 텍스트 메시지로 변환

위의 암호화 및 복호화 과정에서는 공통적으로 모듈러 지수승 연산이 이용된다. 모듈로 지수승 연산의 소요 시간은 지수 크기(자릿수)에 비례하므로, 일반적으로 키 쌍 생성 과정에서 공개키 e를 작은 수로 선택함으로써 암호화 연산의 모듈러 지수승을 빠르게 할 수 있다. (단, 개인키 d를 작게 선택하면 안전성에 문제가 생기므로 개인키는 작게 선택하지 않음) 그러나, 지나치게 작은 e를 사용하면, 경우에 따라서는 개인키 없이 평문이 복원될 수 있어 안전성 문제가 생기게 된다.

문제.

세 명의 사용자가 e = 3으로 고정하고 공개키를 각각 (3, n₁), (3, n₂), (3, n₃)으로 설정한 후, 동일한 메시지 m에 대해 암호화(즉, c₁ = m³ mod n₁, c₂ = m³ mod n₂, c₃ = m³ mod n₃)를 수행한 결과가 각각 c₁, c₂, c₃와 같을 때, m을 복원하시오.

n₁ = 2310299443493285728875630082549132881822025540257530965759514012060264869125167678507394069856345219
n₂ = 1640254853984465233890458607584621854508380697315386098130522602681990087093753900898805886346512517
n₃ =3418519173916888863589816004190034375879476446746811141598913103396792921968768128979083353071236733
c₁ = 852463884908235555765408734486025119365910986910875208826208737582871671723341488120300441323003770
c₂ = 313555711879294064521282442285653226645699338301908834904362312223705316351738030120328187018289910
c₃ = 3404239695295196799353493775777325699675748893697977348429335254042115834104851844221409452136061008

풀이.

문제 설명에 보면 '지나치게 작은 e를 사용하면 경우에 따라서 개인키 없이 평문이 복화화 될 수 있음'라는 힌트를 주어졌다. 그러므로 개인키를 직접 구하지 않고 복호화하는 방법에 대해 생각해보면 된다. 

주어진 식들을 나열해보면 다음과 같다.  여기서 구하고자 하는 것이 m의 값임을 기억하자. 

c1 = m^3 mod n1

c2 = m^3 mod n2

c3 = m^3 mod n3

( n1, n2, n3 : 두 소수의 곱, 세 수는 서로소)

중국인의 나머지 정리를 공부하고나서 문제를 봐서 그런지 바로 중국인의 나머지정리를 사용하여 m^3의 값을 구할 수 있음을 알 수 있었다.

위 연립합동식의 해에 대하여 중국인의 나머지 정리에 의해 식을 다음과 같이 세울 수 있다. (파란색은 주어진 값이며 빨간색은 주어지지 않은 값이다. )

m^3 ≡ c1*(n2n3*s1) + c2*(n1n3*s2) + c3*(n1n2*s3)     (mod n1n2n3)

계산을 하고자 생각해보니 숫자가 너무 커서 불편하고 복잡하다.   

간단한 식을 만들기 위해 가능한 나머지를 줄이자.

 

c2 < c1 < c3 이므로 제일 작은 c2값을 빼도 식의 성립에 아무런 지장이 없다. 

 

(m^3 -c2) mod n1 = c1 - c2 = r1

(m^3 -c2) mod n2 = 0

(m^3 -c2) mod n3 = c3 - c2 = r2

다시 연립합동식의 해에 대하여 중국인의 나머지 정리에 의해 식을 세우면 다음과 같다. 

m^3 ≡ r1*(n2n3*s1) + 0*(n1n3*s2) + r2*(n1n2*s3) + c2      (mod n1n2n3)

       ≡ r1*(n2n3*s1) + r2*(n1n2*s3) + c2       (mod n1n2n3) ---- ★

 

여기서 s1과 s3은 다음과 같다. 

s1(n2n3) ≡ 1 (mod n1)  를 만족하는 s1  →  s1은 mod n1에 대한 n2n3의 역원 

s3(n1n2) ≡ 1 (mod n3)  를 만족하는 s3  →  s3은 mod n3에 대한 n1n2의 역원 

 

s1과 s3은 모듈러 연산의 곱에 대한 역원이고 확장 유클리드 알고리즘으로 모듈러에서의 곱셈의 역원을 구할 수 있다.

이 부분에서 많이 헤메었다. ㅠㅠ 

복잡하게 생각하였지만 그런거 없이, 확장 유클리드 알고리즘을 사용하여  s1과 s3를 구하면 되는 것이었다!

구한 s1과 s3을 가지고 식(★)을 계산하면 m^3값을 구할 수 있다. 

계산에 사용한 코드는 다음과 같다. 

n1 = 2310299443493285728875630082549132881822025540257530965759514012060264869125167678507394069856345219
n2 = 1640254853984465233890458607584621854508380697315386098130522602681990087093753900898805886346512517
n3 = 3418519173916888863589816004190034375879476446746811141598913103396792921968768128979083353071236733
c1 = 852463884908235555765408734486025119365910986910875208826208737582871671723341488120300441323003770
c2 = 313555711879294064521282442285653226645699338301908834904362312223705316351738030120328187018289910
c3 = 3404239695295196799353493775777325699675748893697977348429335254042115834104851844221409452136061008
r1 = c1 - c2
r2 = c3 - c2
 
 
def auth(e1, e2): # mod e2 에 대한 e1의 역원(승산 역원)
        a = [1,0]
        b = [0,1]
        x = e1
        y = e2
 
        i=2
        if e1 > e2 :
                while x%y != 0:
                        q ,tmp = divmod(x,y)
                        x = y
                        y = tmp
                        a.append(a[i-2] - q*a[i-1])
                        b.append(b[i-2] - q*b[i-1])
                        i = i + 1
 
                if a[i-1]*e1 + b[i-1]*e2 == 1:
                        print "ok"
                if a[i-1] < 0:
                        return a[i-1]+e2
                return a[i-1]
 
        else:
                while y%x != 0:
                        q ,tmp = divmod(x,y)
                        y = x
                        x = tmp
                        a.append(a[i-2] - q*a[i-1])
                        b.append(b[i-2] - q*b[i-1])
                        i = i + 1
 
                if a[i-1]*e2 + b[i-1]*e1 == 1:
                        print "ok"
                if b[i-1] < 0:
                        return b[i-1]+e2
                return b[i-1]
 
 
s1 = auth(n2*n3, n1)
s3 = auth(n1*n2, n3)
 
mm = (r1*(n2*n3*s1) + r2*(n1*n2*s3) + c2) % (n1*n2*n3)  # m^3 
print mm
 
## 출처 : https://m.blog.naver.com/PostView.nhn?blogId=sorx1234&logNo=220613536845&proxyReferer=https%3A%2F%2Fwww.google.co.kr%2F

중국인의 나머지정리를 공부하는 데에 참고한 사이트 : http://blog.myungwoo.kr/55 , 

ps. 문제푸는데 시간이 오래 걸렸던 이유 

1. 위 풀이를 A라고 하면 뭔가 너무 단순하고 코드를 짜서 계산하기에 숫자크기가 너무 커서 직접 확장 유클리드 알고리즘을 만들어 푸는 문제가 아닐거라 생각하고 다른 방법을 찾을라고 삽질하였다.ㅠㅠ

2. 확장 유클리드 알고리즘을 직접 코드 짜서 돌리는데 계속 오류가 났다 ㅠㅠ 바보였다 ㅠㅠ 그냥 남들이 올린 코드 바로 사용할 걸 그랬다.