[현대 암호학] 06-3. 정수론

3. 정수론

 

약수/공약수/최대공약수/소수/서로소

 

약수(Divisors) - https://namu.wiki/w/약수(수학)

 

24의 양의 약수 = 1, 2, 3, 4, 6, 8, 12, 24

 

• 어떤 수를 나누었을 때 나머지가 0이 되는 수
• 즉, 나누어 떨어지는 수(단, 약수는 정수이다.)
• 모든 자연수는 1과 자기 자신을 약수로 갖는다.
• 1 보다 큰 자연수 중 1과 자기 자신밖에 약수가 존재하지 않는 자연수를 소수라 한다.
• 'a는 b의 약수이다'를 a|b라고 표현하기도 한다.
• 예를 들어 4|20은 참이지만 5|21은 거짓이다.

 

 

 

최대 공약수(GCD) - https://ko.wikipedia.org/wiki/최대공약수

 

8, 12의 공약수는 1, 2, 4 이다.

* 8의 약수 = 1, 2, 4, 8

* 12의 약수 = 1, 2, 3, 4, 6, 12

따라서, 최대 공약수는 4이다.

 

• GCD(Greatest Common Divisor, GCD)
• 두 수의 공통된 약수
• 두 수의 최대 공약수는 공약수 중 가장 큰 값

 

 

 

소수(Prime Numbers) - https://ko.wikipedia.org/wiki/소수_(수론)

 

5는 소수이다.(1 x 5, 5 x 1)

 

• 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.
• 즉, 소수는 1과 자신의 수만을 약수로 갖는다.

 

 

 

서로소(Relatively Prime Number) - https://ko.wikipedia.org/wiki/서로소_아이디얼

 

8과 15는 서로소이다.

* 8의 약수 : 1, 2, 4, 8

* 15의 약수: 1, 3, 5, 15

 

• 어떤 두 수가 공통적인 소인수를 갖지 못할 때 두수를 서로소라고 한다.

 

 

 

모듈러 연산

- https://johngrib.github.io/wiki/discrete-math-modular/

 

• 어떤 양의 정수 n과 어떤 정수 a가 주어지고
• 만약 a를 n으로 나눈다면 다음과 같은 관계를 가지고 몫(Quotient) q와 나머지r(Remainder)을 얻는다.

 

a = q / n

a = qn + r (0 <= r < n)     a ≡ r mod n

 

q = a div n

r = a mod n

 

[python]

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

(예)  7 = 2 x 3 + 1

       2 = 7 div 3          7 // 3 = 2 (몫)

       1 = 7 mod 2        7 % 2 = 1 (나머지)

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

 

 

모듈러 산술연산

• [(a mod n) + (b mod n)] mod n = (a + b) mod n    (예): [(5 mod 3)+(4 mod 3)] mod 3 = (5 + 4) mod 3
• [(a mod n) - (b mod n)] mod n = (a - b) mod n      (예): [(5 mod 3)-(4 mod 3)] mod 3 = (5 - 4) mod 3
• [(a mod n) * (b mod n)] mod n = (a * b) mod n      (예): [(5 mod 3)*(4 mod 3)] mod 3 = (5 * 4) mod 3

 

 

 

페르마와 오일러의 정리

 

페르마 정리(Fermat Theorem)

만약 p가 소수라면, a는 p에 의해 나누어지지 않는 양의 정수이다.

그때,

a^p-1 ≡ 1 mod p 성립한다.

 

(예) a=3, p=5

a^p-1 = 1 mod p

3^4 = 1 mod 5

 

페르마의 다른 유용한 형태

만약 p가 소수이고 a가 양의 정수라면

a^p ≡ a mod p 성립한다.

 

(예) a=3, p=5

a^p = a mod p

3^5 = 3 mod 5

 

 

 

오일러의 정리

 

오일러의 totient 함수

• 정수론에서 오일러의 totient 함수는 φ(n)라고 표기한다.

 

φ(n) : n보다 작고 n과 서로 소인 양의 정수의 개수

 

n        1 2 3 4 5 6 7 8 9 10 11 12

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

φ(n)    1 1 2 2 4 2 6 4 6 4 10 4

 

n=1    1

n=2    1

n=3    1,2

n=4    1,3

n=5    1,2,3,4

n=6    1,5

n=7    1,2,3,4,5,6

n=8    1,3,5,7

n=9    1,2,4,5,7,8

n=10   1,3,7,9

n=11   1,2,3,4,5,6,7,8,9,10

n=12   1,5,7,10

 

 

오일러 정리

• 서로소인 모든 a와 n에 대한 관계를 나타낸다.

 

a^φ(n) ≡ 1 mod n

 

a = 3,   n = 10,   φ(n) = 4

3^4 = 81 ≡ 1 mod 10

 

a = 2,   n = 11,   φ(n) = 10

3^10 = 1024 ≡ 1 mod 11

 

 

오일러 정리의 추가적인 특성

 

a^φ(n)+1 ≡ a mod n

 

 

이산 대수

 

다음과 같은 등식을 고려해 보자.

 

y = g^x mod p

 

g, x, p 주어지면, y를 계산하는 것은 쉬운 문제이다. 최악의 경우, 반복적인 곱셈과정을 x번 수행해야만 하며, 효율적인 계산을 위한 알고리즘이 존재한다.

 

그러나, y, g, p가 주어진다고 하더라도 x를 계산하는 것은 매우 어려운 문제이다.그 어려움은 RSA 알고리즘을 풀기 위해 요구되는 인수분해의 어려움과 같은 어려움을 가진다.

 

 

 

 

 

Diffine Hellman 알고리즘 예

[원문] https://rsec.kr/?p=242 (여기 사이트의 내용을 정리하였다. 반드시 읽기)

특히, SSL Report: jroh.kr(Qualys SSL Labs)의 Diffine Hellman 알고리즘에 대한 경고 부분을 확인하기.

 

 

노씨가 소수 P, 그리고 정수 G를 선택해 이씨에게 보낸다. 김씨도 훔쳐보고 알 수 있다. 노씨는 정수 a를 선택한다. 현재상태에서 노씨만 알고 이씨와 김씨도 모른다. 이씨도 정수 b를 선택한다. 현재상태에서 이씨만 알고 노씨와 김씨도 모른다. 노씨는 일정한 값 A를 계산한다. (G의 a승을 P로 나눈 나머지: G^a mod P) 이씨는 일정한 값 B를 계산한다. (G의 b승을 P로 나눈 나머지: G^b mod P) 노씨는 계산된 값 A를 이씨에게 전송한다. 김씨도 훔쳐보고 알 수 있다. 이씨는 계산된 값 B를 노씨에게 전송한다. 김씨도 훔쳐보고 알 수 있다. 노씨는 수신받은 B값을 이용하여 일정한 값을 만든다 (B의 a승을 P로 나눈 나머지: B^a mod P) 이씨는 수신받은 A값을 이용하여 일정한 값을 만든다 (A의 b승을 P로 나눈 나머지: A^b mod P) 노씨와 이씨는 계산후의 공통의 키값을 얻게 된다. 이게 암호키고 김씨가 중간에 본 혼합값으로는 키를 알 수 없다.

 

 

RSA 알고리즘의 예 - 암호화와 복호화

 

평문 메시지 M = 19 일 경우

• 암호문 : 195 = 66 mod 119 => 66
• 복호문 : 6677 = 19 mod 119 => 19

 

① pri=(77,119), pub=(5,119)                         ② pub=(5,119) <----                         ③ 19^5 mod 119 -----> 66                                                      ④ 66^77 mod 119 ---> 19