2025년, 코딩은 선택이 아닌 필수!

2025년 모든 학교에서 코딩이 시작 됩니다. 먼저 준비하는 사람만이 기술을 선도해 갑니다~

강의자료/이산수학문제풀이

[정보올림피아드 대비]22. 암호화 관련 문제

원당컴1 2023. 3. 22. 09:38

1. 다음의 암호화된 문장을 해독하세요.

KS VCDS HC USH CIF OGGSHG QFCGG HC RSGQSBROBHG.

 

생각해 보기)

 

- 분수는 왜 유한소수 혹은 순환소수가 될까?

예)

3/10 = 0.3

7/20 = 0.35

2/125 = 0.016

1/7 = 0.142857.....

1/12 = 0.0833333...

 

- 여기서 우리는 10진수 체계이므로 분모가 2와 5로 이루어진 경우는 유한소수이다.

증명)

7/20 = (7*5)/(20*5) = 35/100 과 같이 분모를 10의 거듭제곱으로 나타낼 수 있다.

 

- 2와 5외의 수가 포함되면 순환소수이다.

증명)

1/7 = 10/70 = (10/7) / 10 = (1 + 3/7) / 10 = 1/10 + 3/70

3/70 = 30/700 = (30/7)/100 = (4+2/7)/100 = 4/100 + 2/700

....

1/7 = 1/10 + 4/10^2 + 2/10^3 + 8/10^4 + 5/10^5 + 7/10^6 + 1/10^6 * 1/7

 

그렇다면 여기서 왜 순환소수가 되는것일까?

7로 나눈 나머지는 0부터 6까지의 수만 나올수 밖에 없다. 여기서 나머지가 0 이 나온다면 유한소수가 될것이다.

1/7 은 나머지만을 보면 3->2->6->4->5->1 과 같이 6개에서 순환이 될수 밖에 없는 구조를 가지게 된다.

 

다른문제 풀어보기)

문제1) 1/3 의 순환마디의 길이를 구하시오

문제풀이)

더보기

1/3 = 0.33333.... 이 된다.

따라서 순환마디는 1

문제2) 이집트인들은 모든 분수를 단위분수들의 합으로 표현하려고 했다. 그런 방법으로 대표적인 아이디어를 중세 이탈리아 수학자 피보나치가 제안했다. 기본적인 아이디어는 주어진 분수보다 작은 단위분수를 찾아 뺀 후 남은 수에 이 과정을 반복하는 것이다.

예) 5/11 을 표현하는 방법

1단계 ) 1/3 < 5/11 < 1/2  이고 5/11 - 1/3 = 4/33 이므로 5/11 = 1/3 + 4/33

2단계) 1/9 < 4/33 < 1/8 이고 4/33 - 1/9 = 1/99 이므로 4/33 = 1/9 + 1/99

따라서 5/11 = 1/3 + 1/9 + 1/99

 

이 방법을 이용해서 5/21을 단위분수들의 합으로 표현하시오.

문제풀이)

더보기

1단계) 1/5 < 5/21 < 1/4 이고 5/21 - 1/5 = 25/105 - 21/105 = 4/105 이므로 5/21 = 1/5 + 4/105

2단계) 1/27 < 4/105 < 1/26 이고 4/105 - 1/27 = 36/945 - 35/945 = 1/945 이므로  4/105 = 1/27 + 1/945

따라서 5/21 = 1/5 + 1/27 + 1/945

 

시저 암호란?)

 

카이사르암호(Caesar cipher) 또는 시저암호는 암호학에서 다루는 간단한 치환 암호의 일종이다. 

위와 같이 암호화 하고자 하는 내용을 알파벳별로 일정한 거리만큼 밀어서 다른 알파벳으로 치환하는 방식이다.

 

2개의 회전 디스크를 구성하여 코드를 암호화 하거나 암호 해독 할 수 있다.

 

그렇다면 맨 먼저 나온 KS VCDS HC USH CIF OGGSHG QFCGG HC RSGQSBROBHG. 을 시저암호로 해독해 보자.

이때 모든 문자를 하나씩 대입해 보려면 25번을 회전해야 한다.

그렇다면 여기서 과거에 암호문 해독하던 사람들은 25번을 모두 회전해서 찾아냈을까?

일반적으로 문장에서 가장 많이 사용하는 것은 a,e,i,o,u 와 같은 모음이다.

그렇다면 KS 에서 모음이 나올 테니까 K를 5개의 모음에 대입, S를 5개의 모음에 대입해보면 10번만에 해독이 가능하다.

위의 문장은 실제로 S->E 에 대입하여 해독할 수 있다.

 

그렇다면  S->E 로 대입한 문장은 다음과 같다.

We hope to get our assets cross to descendants.

(우리의 자산이 후손들에게 전달되기를 희망한다.)

 

이와 같이 암호화(Encoding) 된 문장을 해독하는 것을 디코딩(Decoding) 이라고 한다.

 

 

소수와 합성수)

 

- 암호학에서 소수는 굉장히 중요한 분야입니다.

소인수 분해란 합성수를 소수들의 곱으로 쪼개는 과정입니다.

이때 작은 수는 소인수 분해가 쉽지만 만약에 884339를 소인수 분해한다면?

887 * 997 이 됩니다. 이런 경우 사람이 계산하기 위해서는 2 부터 소수들을 하나 하나 찾아가면서 해당 수를 나누어 떨어지는지 확인을 해야 됩니다.

 

따라서 이러한 소수의 곱으로 이루어진 큰 소수를 이용하여 보안키로 만드는 것을 RSA 암호화 입니다.

129자리 합성수가 있는데 이것을 소인수 분해 하여 키값을 사용하는 경우 이 키값을 찾는데 1977년에 제출된 문제가 1994년에 17년 걸려서 풀렸다고 합니다.

 

이미지 EBS 캡쳐

문제를 푸는데 600명과 컴퓨터 1600대의 컴퓨터를 활용하여 1개월만에 해결을 하였다고 합니다.

 

이처럼 암호학에서 소수를 판별하는것이 중요합니다.

 

그렇다면 이제 소수와 합성수 여행을 떠나 볼까요?

 

작은 범위의 수라면 소수를 판별하는 방법으로 "에라토스테네스의 체" 가 있습니다.

이 방법은 2가 소수라면 2의 배수들은 합성수라는 것에 착안을 하여 해당 범위 중에 2의 배수는 모두 합성수라고 미리 걸러 내는 것입니다.

그 다음 남은 것중에 가장 작은 3을 꺼내서 3의 배수들을 모두 합성수로 걸러내는 것입니다.

 

이렇게 하는 것은 매우 많은 메모리가 필요합니다.

가령 메모리가 2000만개의 메모리를 할당 할 수 있다면 2000만 까지의 수중에서 소수를 판별하는 것은 어렵지 않을 수 있습니다.

 

그렇다면 2000만 보다 커지는 수 중에서 소수는 어떤 식으로 찾아 내 주어야 할까요?

 

해당 수를 기존에 찾아낸 모든 소수로 나누어 지는지 판별해 보는 방법을 사용합니다.

 

만약 13이 소수인지 아닌지 판별하기 위해서 13보다 작은 소수, 2,3,5,7 로 나누어 보고 나누어 떨어지지 않는다면 13은 소수가 되는 것과 같은 이치입니다.

 

그렇다면 소수의 갯수는 유한할까? 아니면 무한할까?

 

여기서 소수의 갯수는 무한하다는 것을 귀류법을 이용하여 정의 해 보겠습니다.

 

 

귀류법)

- 귀류법이란 어떤 주장에 대해 그 내용을 따라 가다 보면 이치에 닿지 않는 내용 또는 결론에 이르게 된다는 것을 보여서 그 주장이 잘못된 것임을 보이는 것이다. 배리법,반증법이라고 일컬어지기도 하는데 귀류법은 간접증명법으로 오류에 귀착된다는 것을 보임으로 그 주장이 거짓임을 판별하는 방법.

 

예) 오래전 사람들은 지구가 평평하다고 믿고 있었다.

지구가 평평하다면 바다의 끝까지 간다면 바다는 반드시 절벽으로 떨어져야만 한다.

따라서 절벽을 찾아서 항해 했지만 결국은 절벽을 찾지 못했다면 지구가 평평하다고 가정했는데 찾지 못했으므로 평평하다는 가정에 위배 된 것임

 

 

- 그렇다면 소수의 갯수는 유한하다는 것이 잘못됨을 보이면 소수가 무한하다는 것이므로 소수가 유한하다고 가정을 해 봅니다.

1) 우리가 알고 있는 수가 0 부터 9 까지만의 수라고 가정하면 소수는 2,3,5,7 이 있습니다.

2) 하지만 이 네개의 소수의 곱 2 * 3 * 5 * 7 에 숫자 1을 더하면 211 이 됩니다.

3) 211은 1과 자기 자신만 약수로 가지고 있는 소수 입니다.

 

이렇게 소수는 자신이 아는 범위의 밖에서 갑자기 툭 하고 튀어 나오게 됩니다.

따라서 수가 무한인만큼 소수도 무한합니다.

 

- 여기서 그렇다면 소수의 곱 + 1 은 항상 소수인가? 하는 문제가 발생합니다.

2*3*5*7*11*13+1=30031 이 됩니다.

30031 = 59 * 509 가 됩니다.

그렇다면 위의 귀류법이 잘못된 것일까요?

아닙니다. 여기서 2*3*5*7*11*13+1 이라는 값은

소수를 2,3,5,7,11,13 까지의 소수만 알고 있는 상태에서 30031이 나온 것이고 59라는 소수는 우리가 알고 있는 범위의 수 밖의 수가 되는 것입니다.(따라서 귀류법에 의한 정의로 소수의 갯수는 무한하다고 정의 할 수 있습니다.)

 

하지만 이렇게 5자리 수도 소수인지 아닌지 판별하기가 쉽지 않습니다.

 

이렇게 소인수 분해를 이용한 암화화 키를 만드는 것이 공개키 암호의 핵심입니다.

 

 

문제1)

'자연수 m과 n이 곱 mn이 홀수라면 m과 n은 모두 홀수이다.' 를 귀류법으로 증명하는 과정이다.( ) 안에 들어갈 단어는 무엇인가?

'm과 n은 홀수이다' 라는 ( 1 ) 을 부정한다. 즉 m과 n 은 적어도 하나는 짝수라고 가정한다. 가령 m을 짝수라고 가정하면 n의 짝수 혹은 홀수와 관계없이 mn은 항상 ( 2 ) 이다. 이것은 mn이 홀수라는 ( 3 ) 에 모순된다. 

 

문제풀이)

더보기

1) 결론

2) 짝수

3) 가정

 

공개키 암호의 개념)

공개키는 은행에서 사용하는 공인인증서와 같이 고객에게 암호화 열쇠를 모두 공개하여 암호화 열쇠를 이용하여 데이터를 암호화 하여 은행에 전송을 하면 은행에서 암호화 된 비밀키를 가지고 해독하는 개념.

 

- 공개키 알고리즘

1) 두개의 소수 p와 q를 선택하고 이 두 수는 비밀로 유지한다.

2) n=pq를 이용하여 n 의 값을 고객에게 공개한다.

3) GCD(e,∮(n)) = 1 을 만족하는 e(공개키) 를 고객에게 공개한다.

4) ed ≡ 1(mod ∮(n)) 을 만족하는 d(비밀키)를 비밀로 유지한다.

=> 이 두개의 공개키와 복호화 방법

1) 외부에 공개되는 공개키는 n과 e 이고 비밀키는 d 이다.

2) 평문 x를 암호화 하는 과정 x^e ≡ y(mod n) 에 의해서 y로 암호화

3) 암호문 y를 복호화 하는 과정 y^d ≡ x(mod n) 에 의해서 x로 복호화

 

여기서 GCD 란 최대공약수를 의미한다.

그렇다면 ∮(n) 은 무슨의미일까?

 

 

페르마의 소정리)

페르마의 소정리를 알아 보기 전에 다음을 먼저 살펴 봅니다.

 

합동식(≡) 이란?

- 나머지 연산의 관점에서 같은 수를 의미합니다. 예를 들어 2 mod 5 ≡ 7 mod 5 ≡ 12 mod 5 과 같은 표현식을 합동식이라고 합니다.

 

여기서 합동식은 사칙연산이 가능할까요?

7 * 4 ≡ 12 * 4 (mod 5) -> 28 ≡ 48 (mod 5)

7 + 4  ≡ 12 + 4 (mod 5) -> 11 ≡ 16 (mod 5) 

7 - 4  ≡ 12 - 4 (mod 5) -> 3 ≡ 8 (mod 5) 

2 / 2  ≡ 12 / 2 (mod 10) -> 1 6 (mod 10) (==> 성립이 안됨)

 

=> 나머지 연산의 합동식에서는 +,-,* 의 연산은 가능하다. 하지만 나눗셈(/) 연산은 불가능하다.

 

※ mod 연산에서 나눗셈연산이 가능한 경우

- mod n 의 n이 소수이면 합동식의 나눗셈은 항상 성립한다.

(주어진 수와 그 수로 나눈 나머지가 서로 소의 관계에 있을때에는 나눗셈이 성립한다.)

예) mod 9 인 경우 9와 서로 소인 2,4,5,7,8 인 경우는 성립하지만 서로소가 아닌 3,6 일때는 성립하지 않는다.

8/2 ≡ 26/2 (mod 9) -> 4 ≡4(mod 9)

6/3 ≡ 24/3(mod 9) -> 2 ≡ 4(mod 9) (==> 성립이 안됨)

- mod n의 n과 서로소의 관계에 놓인 합동식은 나눗셈이 성립한다.

 

거듭제곱의 나머지 연산

5의 거듭제곱을 7로 나눈 나머지 연산을 해 봅시다.

5^1  5 (mod 7)

5^2  4 (mod 7)

5^3  6 (mod 7)

5^4  2 (mod 7)

5^5  3 (mod 7)

5^6  1 (mod 7)

----------------------------------------

5의 거듭제곱을 7로 나눈 나머지 연산을 해 보면 나머지는 5,4,6,2,3,1 로 반복하는 것을 확인 할 수 있다.

 

문제1) 4^1000 (mod 11) 의 값은 무엇입니까?

 

문제풀이)

더보기

4^1  4 (mod 11)

4^2  5 (mod 11)

4^3  9 (mod 11)

4^4  3 (mod 11)

4^5  1 (mod 11)

5회씩 반복되는 것을 확인 할 수 있다.

1000 % 5 == 0 이 되므로 5번째 나타나는 1이 되는 것을 확인 할 수 있다.

 

여기서 a^n  1 (mod b) 이 되는 n을 알고 있으면 위와 같은 문제를 푸는데 쉽게 풀 수 있다는 것을 확인 할 수 있다.

 

문제2)  x^e ≡ 1(mod 11) 이 되는 값을 확인해 봅시다.

x 2 3 4 5 6 7 8 9 10
e 10 5 5 5 10 10 10 5 2

문제3)  x^e ≡ 1(mod 13) 이 되는 값을 확인해 봅시다.

x 2 3 4 5 6 7 8 9 10
e 12 3 6 4 12 12 4 2 6

※ 여기서 mod 11 에서는 10의 약수와 관련이 있는 수이고 mod 13 에서는 12의 약수와 관련이 있는 수라는 것을 확인 할 수 있다. 따라서 mod n 의 연산에서 n 이 소수일때 (n-1)의 거듭제곱에서는 항상 n으로 나눈 나머지가 1이 된다는 사실을 알 수 있다. 위의 예에서 mod 11 에서는 어떤 수이든 10의 거듭제곱에서는 항상 1이 된다.

예) 5^100 ≡ 1(mod 11), 5^12 ≡ 1(mod 13)

 

여기서 이러한 것을 페르마의 소정리라고 한다.

페르마의 소정리)
x^(n-1) ≡ 1(mod n) (단,n은 소수)

 

그렇다면 여기서 n이 소수가 아닌 경우를 살펴 보자.

5^2≡ 1(mod 12)

7^2≡ 1(mod 12)

11^2≡ 1(mod 12)

이 외에 2 , 3, 4 등과 같은 거듭제곱은 합동식이 1이 나오지 않는 것을 확인 할 수 있다.

여기서 잘 살펴 보면 5,7,11 은 12와 서로소 인 경우이다

따라서 x와 n 이 서로소인 경우에는 합동식이 1이 나오지만 서로소가 아닌 경우에는 합동식이 1이 되는 경우가 없는 것을 확인 할 수 있다.

그렇다면 서로소는 무엇일까?

 

서로소가 지니는 의미)

위의 예에서 x와 n 이 서로소가 아니라면 합동식이 1이 되는 경우가 없는 이유는 무엇일까?

21과 서로소가 아닌 3의 거듭제곱에서 21로 나눈 나머지가 1이 나올수 없는 이유를 살펴 보자.

3의 거듭제곱은 항상 3의 배수이다.

따라서 21로 나눈 나머지는 3의 배수일 수 밖에 없다.

3^m = 21 * 몫 + 나머지

따라서 나머지는 항상 3의 배수이다.

 

그렇다면 어떤 수에 대해 서로소의 갯수를 확인해 보자.

12와 서로소 : 1,5,7,11 (4개)

15와 서로소 : 1,2,4,7,8,11,13,14 (8개)

21과 서로소 : 1,2,4,5,8,10,11,13,16,17,19,20 (12개)

여기서 1을 제외한 서로소에서 mod n 으로 나눈 나머지가 1인 합동식을 살펴 보면 다음과 같다.

mod 12 : 5^2, 7^2, 11^2

mod 15 : 2^4, 4^2, 7^4, 8^4, 11^2, 13^4, 14^2

mod 21 : 2^6, 4^3, 5^6, 8^2, 10^6, 11^6, 13^2, 16^3, 17^6, 19^6, 20^2

 

여기서

a^4 ≡ 1(mod 12) (단 여기서 a는 12와 서로소)

 a^8 ≡ 1(mod 15) (단 여기서 a는 15와 서로소)

 a^12 ≡ 1(mod 21) (단 여기서 a는 21와 서로소)

인것을 알 수가 있다.

이것을 바탕으로 다음과 같은 내용을 확인 할 수 있다.

"n과 서로소인 수 a를 n과 서로소인 수의 갯수 m만큼 거듭제곱한 수 a^m 은 n으로 나눈 나머지가 1이다."

문제1) 8^2000 를 11로 나눈 나머지를 구하시오

문제풀이)

더보기

페르마의 소정리에 따르면 11은 소수이기 때문에 a^10 ≡ 1(mod 11) 이므로 a^2000 ≡1 (mod11)이다.

 

비대칭 암호의 대표 RSA)

암호문은 비밀번호 기반으로 암호를 한 후 해당 비밀번호를 가지고 해독하는 과정을 거치는 대칭키를 사용하는 것이 일반적이다.

하지만 이러한 대칭키이 근본적인 문제는 암호화를 하는 사람과 해독을 하는 사람이 비밀번호를 알고 있어야 한다. 비밀번호를 수시로 변경하면서 비밀번호를 서로 공유해야 하는 구조적인 한계점을 가지고 있다.

이러한 단점을 보완하기 위해 나온 알고리즘 중 대표적인 알고리즘이 RSA 알고리즘이다.

RSA 암호는 소수로 소인수 분해 하는 방식으로 개발된 알고리즘이다. 그렇다면 이러한 RSA 알고리즘은 누구나 가능한 소인수 분해 방삭을 사용하는데 과연 안전한 방법일까?

 

포함배제의 원리)

RSA암호화를 알아 보기 전에 다음의 문제를 풀어 봅시다.

 

문제1) 21의 서로소의 개수는 몇개인가?

여기서 21은 3과 7의 곱이므로 3의 배수 7개 와 7의 배수 3개를 빼면 나머지가 서로소이다.(?)

여기서 3의 배수 7개 중에는 21이 포함이 되어 있고 7의 배수 3개 중에는 21이 포함 되어 있는 것을 확인 할 수 있다.

따라서 21의 서로소의 갯수는 21 - (7+3 - 1) = 12 개 인것 을 확인 할 수 있다.

  

문제2) 12의 서로소의 개수는 몇개인가?

2의 배수가 6개, 3의 배수가 4개 이며 2와 3의 공통배수가 2개 이다. 따라서 12 - (6+4-2) = 4개(1,5,7,11) 이다.

 

이처럼 포함되어 있는 수 중에서 공통으로 세어지는 수를 배제 시켜 주어야 한다.

 

그렇다면 2 * 3 * 5 = 60 의 서로소의 개수는 어떻게 될까?

2의 배수 30,3의 배수 20,5의 배수 12 이므로 60 -(30 + 20 + 12) 에서 2와 3의 공통배수 6의 배수 10,2와 5의 공통배수 10의 배수 6, 3과 5의 공통배수 15의 배수 4개 가 공통으로 포함 되므로 60 - (30 + 20 + 12 - 10 - 6 - 4) 가 된다.

하지만 여기서 2,3,5 의 공통배수 60이 세번이 포함되면서 세번이 빠지는 경우가 되므로 60의 갯수를 하나 더 포함 시켜 주어야 한다. 따라서 60 - (30 + 20 + 12 - 10 - 6 - 4 + 1) 과 같이 계산을 할 수 가 있다.

 

 이와 같이 "공통으로 들어간 수에 대한 정보를 다시 보충해 주는 원리가 포함배제의 원리이다."

 

오일러피함수)

그렇다면 RSA암호화 중에 

3) GCD(e,∮(n)) = 1 을 만족하는 e(공개키) 를 고객에게 공개한다.

에서 ∮(n)를 보았던 적이 있다.

 

∮(n) 란 오일러피함수라고 하면서 n과 서로소인 것의 개수를 나타내는 함수이다.

서로소가 지니는 의미에서 n과 서로소인 어떤 수를 mod n 으로 할때 n과 서로소의 갯수m 의 거듭제곱이 1의 합동식임을 확인 할 수 있었다.

 

그렇다면 오일러 피함수를 계산하는 방법을 살펴 보자

 

n 을 소인수 분해 한것이 다음과 같을때
n = ∏Pi^ei (단 Pi는 서로 다른 소수이다. 가령 72 인 경우 2^3 * 3^2 으로 나타낼 수 있다.)
이때 ∮(n) 함수는 다음과 같이 계산된다.
∮(n) = n * ∏(1-1/Pi)
예) ∮(72) = 72 * (1-1/2) * (1-1/3) = 72 * 1/2 * 2/3 = 24
여기서 72의 서로소인 경우는
2^3 * 3^2 이므로 2의 배수 36개 3의 배수 24개를 뺀 후 6의 배수 12개를 더해 주어야 하므로 72 - (36 + 24 - 12) = 24

여기서 "오일러피함수는 포함배제의 원리를 식으로 깔끔하게 정리한 것"

 

공개키암호제작)

- 공개키 알고리즘

1) 두개의 소수 p와 q를 선택하고 이 두 수는 비밀로 유지한다.
2) n=pq를 이용하여 n 의 값을 고객에게 공개한다.
3) GCD(e,∮(n)) = 1 을 만족하는 e(공개키) 를 고객에게 공개한다.
4) ed ≡ 1(mod ∮(n)) 을 만족하는 d(비밀키)를 비밀로 유지한다.

 

1) 먼저 p=7,q=13 을 찾고 이 수는 우리만 아는 비밀키로 선택하자.

2) n=7*13 = 91 을 고객에게 공개한다.

3) ∮(91) = 91*(6/7)*(12/13)=72 의 오일러 피 함수를 찾는다.

GCD(e,72)=1 을 만족하는 e를 찾아 보자.

여기서 72와 서로소인 수는 1,5,7,11,13,17,...,71 과 같이 24개의 수가 있는데 여기서 임의로 7이라는 수를 선택해 보자.

4) 7d(mod 72) ≡ 1 이 되는 d를 찾아 보자.

여기서 d 값을 찾는 방법을 생각해 보자.

"n과 서로소인 수 a를 n과 서로소인 수의 갯수 m만큼 거듭제곱한 수 a^m 은 n으로 나눈 나머지가 1이다." 를 배운적이 있다.

그렇다면 72=2^3*3^2의 서로수의 갯수인 ∮(72)=72*(1/2)*(2/3) = 24 이므로 72와 서로 소인 7d = 7^24 의 d 의 값을 찾으면 되므로 d = 7^23 과 같은 임의의 수를 찾을 수 있다.

하지만 계산의 편의상 여기서 d의 값이 31 일때 역시 7*31=217 ≡ 1(mod 72) 이므로 d의 값을 31로 선택해 보자.

 

그렇다면 위에서 선택한 수를 정리하면 다음과 같다.

- 비밀키 : p=7,q=13,d=31

- 공개키 : n=91,e=7

이것을 이용하여 x=15 라는 수를 암호화 해 보자.

 

=> 공개키와 복호화 방법
1) 외부에 공개되는 공개키는 n과 e 이고 비밀키는 d 이다.
2) 평문 x를 암호화 하는 과정 x^e ≡ y(mod n) 에 의해서 y로 암호화
3) 암호문 y를 복호화 하는 과정 y^d ≡ x(mod n) 에 의해서 x로 복호화

15^7(mod 91) = 170,859,375(mod 91) = 50 (고객이 공개키에 의해 암호화 하는 과정으로 나온 값)

 

그렇다면 50을 비밀키를 가지고 복호화 하였을때 15 값이 나오는지 확인해 보자.

50^31(mod 91) = 15 

 

만약 위에서 공개키 n과 e를 가지고 비밀키를 알아 낼 수 있는 방법이 있을까?

비밀키만 알아 낸다고 하면 복호화 하는 것은 쉬울것이다.

여기서 91이 7*13 이라는 수를 가지고 역 추적하면 충분히 가능 할 것이다.

하지만 91이라는 수가 아니고 34081 이라는 수가 주어진다면?

약간의 고생끝에 173 * 197 이라는 두 수를 찾아 낼 수 있을것이다.

 

하지만 129자리의 숫자가 주어졌다고 한다면 두 소수를 찾아 내는 것은 거의 불가능에 가깝다.

 

지금까지 찾아낸 가장 큰 소수는 2^82589922 - 1 이다.

 

문제1) 오일러 피 함수를 이용하여 900과 서로소인 수가 몇개인지 구하시오

 

문제풀이)

더보기

900=2^2 * 5^2 * 3^2 이므로 서로수의 갯수는 900 * (1/2)*(4/5)*(2/3) = 240

문제2) 가로의 길이가 2607이고 세로의 길이가 948인 벽에 한변의 길이가 a(a는 자연수)인 정사각형의 타일로 빈틈없이 채우려면 최소 몇 개의 타일이 필요한가?

 

문제풀이)

더보기

최소의 갯수이므로 2607과 948의 최대공약수를 찾아서 정사각형의 갯수를 찾으면 된다.

GCD(2607,948) = GCD(948,711) = GCD(711,237) = GCD(237,0) 이므로

237 * 237 인 타일로 채우면 된다.

따라서 가로 2607/237 = 11, 세로 948/237=4 이므로 11*4= 44개

 

 

 

[역대기출문제]

2018년 고등부 43번 - blog.naver.com/icon003/221416893023

 

2018년 정보올림피아드 지역대회 고등부 43번 문제풀이

​​문제풀이)ㄱ. iloveyou 를 암호화 하면 il => "ES",ov=>"HO&quo...

blog.naver.com

 

사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 통신판매신고번호 : 호 | 사이버몰의 이용약관 바로가기