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

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

 

추천글 : 【암호론】 암호론 목차

---

1. 문제 [본문]

2. 풀이 [본문]

---

 

1. 문제 [목차]

세 명의 사용자가 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

 

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

다운로드

 

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를 사용하면, 경우에 따라서는 개인키 없이 평문이 복원될 수 있어 안전성 문제가 생기게 된다.

 

 

2. 풀이 [목차]

다음과 같은 문제가 주어져 있다고 가정하자.

 

 

그러면 다음과 같이 풀어낼 수 있다.

 

 

(mod n)에 대해서 n이 소수이기 때문에 변칙적인 상황이 나오지 않을 것이다. 변칙적인 상황은 다음을 지칭한다.

 

 

이제 본 문제로 돌아가, 다음 식을 찾을 수 있다.

 

 

이때 c_i의 크기를 비교하면 c₂ < c₁ < c₃이므로 다음 순서로 푼다.

 

(01) k₂n₂ ≡ c₁ - c₂ (mod n₁)

(02) (01)을 푼 결과 k₂ ≡ a (mod n₁)인 0 < a < n₁을 찾는다. 그 결과 다음과 같다.

 

210824214449695233006980592380909113808777047569969848337716314539333057685637224866726963639360265

 

(03) k₂n₂ = (n₁t + a) n₂ = n₁n₂t + an₂ ≡ c₃ - c₂ (mod n₃)

(04) n₁n₂t ≡ c₃ - c₂ - an₂ (mod n₃)

(05) (04)를 푼 결과 t ≡ b (mod n₃)인 0 < b < n₃을 찾는다. 그 결과 다음과 같다.

 

89329647693091640013623734899873053413799691201603093490413135180340208568271437133325984870644816

 

(06) m³ = (n₁t + a) n₂ + c₂ = (n₁(n₃s + b) + a) n₂ + c₂ = n₁n₂n₃s + (c₂ + n₂a + n₁n₂b)

(07) c₂ + n₂a + n₁n₂b를 n₁n₂n₃로 나눈 나머지는 다음과 같다.

 

338512902294180026742062499790246825491289530419663739994471843709329922151035000808607134601362162647058249285652331936506525556228449559501805785815277061779222758843899987547741135718572919800738201126715596563715818914393006712626744776667230661545824969368334261918787149105268353396521516883 

 

(08) m³ < n₁n₂n₃이고 후보는 단 하나였으므로 m³은 (07)에서 구한 수가 된다.

(09) m³을 알고 있으므로 m을 알 수 있다.

(10) 관련된 C 코드는 아래에 첨부한다. 

 

코드 1.c

다운로드

 

입력: 2016.08.14 12:19