(방송통신대 이산수학 기말시험)1. 2019학년도 이산수학의 기말시험 기출문제 중 6개 문제(55번~60번)에 대해 교재 제10장의 연구과제 14번 15번 RSA 암호화와 복호화 과정에 대해

소개글

(방송통신대 이산수학 기말시험)1. 2019학년도 이산수학의 기말시험 기출문제 중 6개 문제(55번~60번)에 대해 교재 제10장의 연구과제 14번 15번 RSA 암호화와 복호화 과정에 대해에 대한 보고서 자료입니다.

목차

1. 2019학년도 『이산수학』의 기말시험 기출문제 중 6개 문제(55번~60번)에 대해 풀이를 해설하시오. 단, 문제에서 다루는 주요 용어에 대해 설명하고, 정답은 왜 정답인지, 오답은 왜 오답인지를 상세히 설명할 것. (참고: 이산수학 워크북의 해설) [30점]
1)55번 문제 2)56번 문제 3)57번 문제 4)58번 문제 5)59번 문제 6)60번 문제

2. 교재 제10장의 연구과제 14번(교재 p.268)을 푸시오. [10점]

3. 교재 제12장의 연구과제 15번(교재 p.325)을 푸시오. [10점]
(교재에 문제를 푸는 힌트로, 파스칼 삼각형의 대각선 방향의 수들의 합이 해당 위치의 피보나치 수라는 것이 제시되어 있고, 이를 이용해 문제를 풀라는 것입니다.)

4. RSA 암호화와 복호화 과정에 대해 다음 순서에 따라 설명하시오. [20점]
(1) 암호화를 위한 공개키를 임의로 정하고 왜 적합한지 밝히시오.
(2) 학생의 영문 성과 학번의 끝 3자리를 암호문으로 만드는 과정을 설명하시오. (예를 들어 학생 홍길동의 학번이 ******-***123이면 HONG123이 평서문임. 필요한 경우 space를 26번으로 정함).
(3) 복호화를 위한 비밀키를 임의로 정하고 왜 적합한지 밝히시오.
(4) 단계(2)번에서 구한 암호문을 평서문으로 복호화하는 과정을 설명하시오.

본문내용

cd(17, 2668) = 1이 성립한다. (오일러 파일 함수의 특별한 경우로, 양의 정수 n이 두 개의 소수 p와 q의 곱이라면 φ(n) = (p-1) * (q-1)이다. 즉, φ(n) = (47-1)*(59-1) = 2668와 같이 계산된다).
따라서 φ(n)의 값 2668과 e의 값 17의 최대공약수가 1이고, 17(e) < 2668(φ(n))이므로, 임의로 선정한 (2773, 17)은 공개키로서 적합하다고 할 수 있는 것이다.
다만, 계산 편의를 위해 300자리 이상의 큰 소수를 선택한 것이 아니므로 2773처럼 작은 수는 컴퓨터로 소인수분해가 빠르게 가능해 암호화의 안정성 측면에서는 문제가 있다.
(2) 학생의 영문 성과 학번의 끝 3자리를 암호문으로 만드는 과정을 설명하시오. (예를 들어 학생 홍길동의 학번이 ******-***123이면 HONG123이 평서문임. 필요한 경우 space를 26번으로 정함).
①암호화할 할 평문으로 HONG123을 선택한다.
②HONG123을 주어진 표를 이용해 숫자로 바꾸면 07 14 13 06 01 02 03이 된다.
이때 한 자리 숫자에는 앞에는 ‘0’을 덧붙인다. 그리고 이 숫자들을 숫자 4개의 블록으로 나누어 0714 1306 0102 0323와 같이 나열한다. 이때 마지막 숫자 23은 4개의 블록으로 나누기 위해 문자X(23)를 편의상 덧붙인 것이다. 블록의 크기는 2525...25가 n을 초과하지 않는 가장 큰 수의 자릿수를 선택하면 된다. 2525 < 2773 < 252525 이므로 2525의 자릿수인 4를 선택한 것이다. 만약 n을 다른 수, 예를 들면 1271을 선택했다면 25 < 1271 < 2525 이므로 25의 자릿수인 2를 선택하고 07 14 13 06 01 02 03과 같이 나눈다.
③c = me mod n의 공식을 이용해 0714 1306 0102 0323의 각 블록을 암호화한다. 이때 이진법을 이용한 나머지 거듭제곱 알고리즘(교재 p347)을 사용하여 계산한다.
먼저 0714를 암호화하기 위해 071417 mod 2773은 계산과정은 다음과 같다.
지수 17 = (10001)2와 같이 이진수로 바꾼다.
i
ai
x
power
1
714 mod 2773 = 714
0
1
(1 * 714) mod 2773 = 714
7142 mod 2773 = 2337
1
0
714
23372 mod 2773 = 1532
2
0
714
15322 mod 2773 = 1066
3
0
714
10662 mod 2773 = 2199
4
1
(714 * 2199) mod 2773 = 568
071417 mod 2773 = 568
같은 방법으로 나머지 문자의 암호화 값도 계산하면 다음과 같다.
130617 mod 2773 = 183
010217 mod 2773 = 1395
032317 mod 2773 = 1714
따라서 0714 1306 0102 0323을 암호화하면 다음과 같다.
0568 0183 1395 1714
(3) 복호화를 위한 비밀키를 임의로 정하고 왜 적합한지 밝히시오.
비밀키(n, d)로 (2773, 157)을 임의로 정해 적합성 여부를 확인해본다. gcd(e, (p-1)(q-1)) = 1이기 때문에 e 모듈로 (p-1)(q-1)의 역이 존재한다. RSA암호방식에서는 비밀키(d)로 이 역을 사용한다. 따라서 임의로 비밀키로 정한 d가 17 모듈로 2668의 역이 되는지 확인하면 된다.
17 모듈로 2668의 역을 구하는 과정은 다음과 같다.
de ≡ 1(mod (p-1)(q-1))을 만족하는 d를 구한다.(단, 0 < d < (p-1)(q-1)인 정수)
이를 위해 유클리드 알고리즘(교재 p333)을 이용한다.
2668 = 156*17 + 16
17 = 1*16 + 1
16 = 16*1
이제 거꾸로 거슬러 올라가면 역이 구해진다.
1 = 17 - 1*16 = 17 - 1*(2668-156*17) = -1*2668 + 157*17
위 식에서 -1과 157이 베주 계수이며, 157이 17 모듈로 2668의 역이 된다.
따라서 임의로 정한 값 157이 17 모듈로 2668의 역이 되므로 비밀키로 적합하다고 할 것이다.
(4) 단계(2)번에서 구한 암호문을 평서문으로 복호화하는 과정을 설명하시오.
복호화는 m = cd mod n을 통해 이루어진다.
먼저 0568을 위식에 대입해 계산하면 다음과 같다. 이때 이진법을 이용한 나머지 거듭제곱 알고리즘(교재 p347)을 사용하여 아래 표와 같이 계산한다.
지수 157 = (10011101)2
m = 568157 mod 2773 = 714
같은 방법으로 나머지 암호문도 복호화하면 다음의 결과를 얻게 된다.
m = 183157 mod 2773 = 1306
m = 1395157 mod 2773 = 102
m = 1714157 mod 2773 = 323
따라서 0568 0183 1395 1714를 복호화한 결과는 0714 1306 0102 0323 이다.
이를 문제에 주어진 표를 이용해 문자로 변환하면 HONG123X가 되고 마지막 X를 제외하면 원문인 HONG123이 된다.
i
ai
x
power
1
568 mod 2773 = 568
0
1
(1 * 568) mod 2773 = 568
5682 mod 2773 = 956
1
0
568
9562 mod 2773 = 1619
2
1
(568 * 1619) mod 2773 = 1729
16192 mod 2773 = 676
3
1
(1729 * 676) mod 2773 = 1371
6762 mod 2773 = 2204
4
1
(1371 * 2204) mod 2773 = 1887
22042 mod 2773 = 2093
5
0
1887
20932 mod 2773 = 2082
6
0
1887
20822 mod 2773 = 525
7
1
(1887 * 525) mod 2773 = 714
5. 참고문헌
손진곤(2021). 이산수학. 한국방송통신대학교출판문화원.
Kenneth H. Rosen(2019). 이산수학 8판. McGraw-Hill Education.
박주미(2017). 컴퓨팅 사고력을 키우는 이산수학 . 한빛아카데미.

키워드

방송통신대이산수학,   방송대이산수학,   방통대이산수학,   이산수학기말시험기출문제,   RSA암호화,   RSA복호화