(2021.07.18)
2주차 암호 스터디
제 2장은 정수론에 대해 다루고 있다.
42p 까지만 정리해보았다.
2.1 정수집합
✔ 2.1.1 연산의 기본 성질
정수들의 집합=Z
Z1. 집합 Z위에서 덧셈이 정의된다.
Z2. 덧셈에 대하여 교환법칙이 성립한다.
Z3. 덧셈에 대하여 결합법칙이 성립한다.
Z4. 특정한 정수 0∈Z은 모든 a∈Z에 대하여 a+0=0+a 를 만족한다.
+) 정수 0을 덧셈에 대한 항등원(identity)이라고 함
Z5. 모든 a∈Z 에 대하여 a+(-a)=(-a)+a=0 인 -a∈Z 가 존재한다.
+) 정수 -a를 덧셈에 관한 a의 역원(inverse)이라고 함
Z6. 집합 Z위에서 곱셈이 정의된다.
Z7. 곱셈에 대하여 교환 법칙이 성립한다.
Z8. 곱셈에 대하여 결합 법칙이 성립한다.
Z9. 특정한 정수 1∈Z , 1∈0 은 모든 a∈Z 에 대하여 a·1=1·a=a 를 만족시킨다.
+) 정수 1을 곱셈에 대한 항등원(identity)이라고 함
Z10. 집합 Z위에서 덧셈과 곱셈은 분배 법칙이 성립한다.
정수 집합 Z위에서 덧셈은 모든 원소가 역원을 가지지만, 곱셈에 대해서는 1과 -1만 역원을 가진다.
--> 정수 집합 Z위에서는 나눗셈이 정의되지 않는다.
두 정수 a,b ∈ Z 가 a≠0 일 때,
b=a·q+r , 0≤r<|a| 인 q,r ∈ Z 가 유일하게 존재한다.
--> 두 정수 q,r 를 각각 b를 a로 나누었을 때의 몫(quotient), 나머지(remainder)라고 한다.
2.2 약수와 배수
두 정수 a,b ∈ Z 에 대해서 b = c · a 를 만족하는 정수 c가 존재할 때,
a: b의 약수(divisor)
b: a의 배수
a | b 라고 표시함. --> a는 b를 나눈다 or b는 a로 나누어 떨어진다
세 정수 a,b,c ∈ Z 에 대해서 d | a , d | b 인
정수 d 에 대해서 a 와 b 의 공약수(common divisor) 라고 한다.
두 정수 a, b 에 대해 가장 큰 공약수 g 를 a 와 b 의 최대 공약수(gcd: greatest common multiple) 라고 함
g = (a,b) or g = gcd(a,b)
두 정수 a,b의 최대공약수가 1일 때, 즉 gcd(a,b)=1 일 때,
a와 b는 서로소(relatively prime)이라고 한다.
세 정수 a,b,c ∈ Z 에 대해서 a | c , b | c 인 정수 c를 a 와 b 의 공배수(common multiple) 라고 한다.
두 정수 a, b 에 대해 가장 작은 공배수 l 을 a 와 b 의 최소 공배수(lcm: least common multiple) 라고 함
l = [a,b] or l = lcm(a,b)
✔2.2.1 유클리드 호제법 ( Euclidean algorithm)
호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다.
2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
(위키백과)
예를 들어, 510과 62의 최대 공약수를 유클리드 호제법으로 구해본다면,
510을 62로 나눈 나머지는 14이다. 510=62·8+14
62를 14로 나눈 나머지는 6이다. 62=14·4+6
14를 6으로 나눈 나머지는 2이다. 14=6·2+2
6을 2로 나눈 나머지는 0이다. 6=2·3
--> 즉 나머지가 0이 되었을 때 나누는 수인 2가 510과 62의 최대공약수인 것이다.
2.3 소수
양의 정수 p가 1과 자기자신 이외의 약수가 존재하지 않을 때, p를 소수(prime number)라고 한다.
정수 a가 소수가 아닐 때, a를 합성수(composite number)라고 한다.
+) 정수가 합성수일 조건: a = b · c 인 정수 a,b 가 존재하는 것
✔ 2.3.1 소수의 분포
양의 정수 중에 소수의 개수는 무한히 많다.
증명)
소수가 유한개라고 가정하고, 모든 소수를 p1, p2, ... , pk라고 가정한다.
p1 x p2 x ... x pk + 1 = Nk 라고 놓는다.
Nk 는 p1, p2, ..., pk 의 배수가 아니므로 새로운 소수가 된다.
따라서, 소수가 유한개라는 가정에 모순되기 때문에 소수는 무한개 임을 알 수 있다.
그러나 여기서 p1 x p2 x ... x pk + 1 = Nk 가 항상 소수가 되는 것은 아니다.
( 2 x 3 x 5 x 7 x 11 x 13 + 1 = 30031 = 59 x 209 )
양의 정수 x 를 임의로 선택했을 때, x 안에 분포하는 소수의 개수를 π(x) 라고 표시할 때,
π(x)=x/lnx 이다.
| x | π(x) | x/lnx |
| 10 | 4 | 4 |
| 10^2 | 25 | 22 |
| 10^3 | 168 | 145 |
| 10^4 | 1229 | 1086 |
| 10^5 | 9592 | 8686 |
| 10^6 | 78498 | 72382 |
| 10^7 | 664579 | 620421 |
Mersenne 소수
Mersenne 소수
양의 정수 중에서 2^p-1 의 모양으로 표시되는 수를 Mersenne 수 라고 한다.
Mersenne 수 중에서 소수를 Mersenne 소수 라고 한다.
양정수 2^p-1 이 Mersenne 소수가 되려면 p 가 소수이어야 한다.
+) 역은 성립하지 않는다.
2^2-1, 2^3-1, 2^5-1 은 Mersenne 소수이지만, 2^11=23x89 로 Mersenne 소수가 아니다.
Fermat 소수
양의 정수 중에서 2^(2^n)-1 의 모양으로 표시되는 수를 Fermat 의 수 라고 한다.
Fermat 수 중에서 소수를 Fermat 소수 라고 한다.
그러나 2^(2^5)+1=641x6700417은 Fermet의 소수가 아니다.
지금까지 알려진 가장 큰 Fermat의 소수는 65537이다.
Carmichael 수(유사소수)
소수와 유사한 성질을 가지지만 소수가 아닌 수를 Carmichael 수 라고 한다.
Fermat의 소정리에 의하면 p가 소수이면, gcd(a,p)=1인 모든 a에 대해 a^(p-1)≡1 mod p 가 성립한다.
+) 역은 성립하지 않는다.
p=561=3x7x11 은 합성수이지만, gcd(a,561)=1인 모든 a에 대해서 a^560≡1 mod 561이다.
561과 같은 수를 Carmichael 수라고 한다. (유사소수)
소수 판정법
- 안전한 공개키 암호방식 구성에 사용되는 소수는 수 100자리 이상의 소수여야한다.
① 결정적 판정방법
- 소수임을 정확하게 판정할 수 있으나 오래걸림
- Eratosthenes 방법, Euclid 호제법, Fermat 방법, Wilson 방법 등
② 확률적 판정방법
- 정확성은 떨어지나 시간이 짧게 걸림
- Solovay - Strassen 방법, Lehmann - Peralta 방법, Miller - Rabin 방법 등
2.4 합동식
- 현대 암호학에서 가장 널리 사용되는 수학적인 개념
- 두 정수 a,b 에 대해 a-b 가 m의 배수일 때, a 와 b 는 법(modulus) m 에 관해 합동이라고 하고,
a ≡ b mod m 이라고 표시함 --> a-b=mk
- 상등, 상이, 대등 등의 관계를 가지고 있음
- 세가지 성질을 가짐
① a ≡ a mod m (반사적)
② a ≡ b mod m 이면 b ≡ a mod m (대칭적)
③ a ≡ b mod m, b ≡ c mod m 이면 a ≡ c mod m (추이적)
임의의 정수 c에 대해서 a+c≡b+c mod m이면 ac≡bc mod m 이 성립함
ab≡ac mod m 이고, a≠0 mod m 이면, b≡c mod m 이 성립하지않음
ab≡ac mod m 이고, gcd(a,m)=1 이면 b≡c mod m 이 성립함
✔ 2.4.1 법(modulus) m에 관한 잉여계
반사적, 대칭적, 추이적 성질에 의해 합동 관계 a≡b mod m은 정수 전체의 집합 Z위에서 동치관계이다.
a≡b mod m에 대한 정수 집합 Z 위의 동치류를 법 m 에 대한 잉여류(residue)라고 한다.
a∈Z 에 의해 만들어지는 잉여류를 A라고 하면,
A ≡ { x∈Z | x ≡ a mod m } 으로 표시된다.
--> 합동관계 a≡b mod m에 의해 정수집합 Z가 m개의 잉여류들로 분할(partition)된다.
정수 m에 대하여 집합 zm, Zm을 다음과 같이 정의하면,
zm = { 0,1,2, ... , m-1 }
Zm = { A | a ∈ Z }
Zm은 법 m에 대한 모든 잉여류 전체의 집합이 된다.
zm 을 법 m에 관한 완전 잉여계(complete residue system)라고 하고, 각 원소를 잉여류의 대표원(representive)라고 한다.
집합 zm의 원소중에서 m과 서로소인 원소 전체의 집합을 zm*로 표시하고, 이를 법 m에 대한 기약 잉여계(reduced residue system)라고 함 zm* 의 원소의 개수는 φ(m)으로 나타낸다.
zm*= { a ∈ zm | gcd(a,m)=1 }
φ(m)=|zm*|
(φ(m)을 Euler의 φ함수라고 함)
p가 소수일 때, zp* = { 1,2,...,p-1 }, φ(p)=p-1
zm* = { r1, r2, ..., rφ(m) } 로 표시가능
gcd(a,m)=1을 만족하는 양의 정수 a를 곱한 R={ ar1, ar2, ..., arφ(m) } 도 기약잉여계가 된다.
✔ 2.4.1 Euler의 정리
공개키 암호 방식에 가장 널리 사용되는 수학적인 정리가 Euler의 정리와 Fermat의 소정리이다.
집합 zm = { 0,1,2, ... , m-1 } 위의 원소 가운데 m과 서로소인 원소수를 φ(m)로 표시하고, 이를 Euler의 함수라고 한다.
ar1 x ar2 x ar3 x ... x arφ(m) ≡ r1 x r2 x r3 ... x rφ(m) mod m
a^(φ(m)) x r1 x r2 x r3 ... x rφ(m) ≡ r1 x r2 x r3 x ... x rφ(m) mod m
따라서, a^(φ(m)) = 1 mod m 이다.
이를 Euler의 정리 라고 한다.
Euler의 정리에서 zm의 m이 소수 p인 경우 gcd(a,p)=1 에 대해서 φ(p)=p-1 이므로
a^(p-1)≡1 mod p 가 성립한다.
이를 Fermat의 소정리 라고한다.
일차 합동식 ax ≡ b mod m 이 정수 a와 m이 서로소이면, x는 단 하나의 해를 갖는다.
p가 소수일 때, 일차 합동식 ax ≡ b mod p 는 단 한개의 해를 갖는다.
a와 m이 서로소이므로 au+mv=1인 정수 u,v가 존재한다.
a(ub)+m(vb)=b 이므로 a(ub) ≡ b mod m이 성립하고, x ≡ ub mod m 은 주어진 합동식의 해가 된다.
실제 일차 합동식 ax ≡ b mod m 의 해는 a의 승산역원 a^(-1)를 구해 일차 합동식 ax ≡ b mod m의 양변해 곱하면 된다.
정수 a ∈ zm 가 법 m에 대해 승산 역원 a^(-1) ∈ zm을 가지기 위해서는 a와 m이 서로소여야한다.
a x a^(-1) ≡ 1 mod m, gcd(a,m)=1
승산 역원 a^(-1)은 유클리드 호제법으로 간단히 구할 수 있다.
a의 승산역원이 a^(-1)이므로 a^(-1)의 승산역원도 a가 된다.
2.5 원시근
✔ 2.5.1 위수
Euler의 정리로부터 정수 a ∈ Z가 법 m과 서로소이면, a^(φ(m)) ≡ 1 mod m이다.
정수 b ∈ Z 와 m이 서로소이면, b^r ≡ 1 mod m 을 만족시키는 양의 정수 r이 존재한다.
이때, 가장 작은 r을 법 m 에 대한 b의 위수(oreder)라고 한다.
법 m에 관한 a의 위수는 Euler 함수 φ(m)보다 작고, 위수 r은 φ(m)과 약수 관계이다.
✔ 2.5.2 원시근
법 m에 관한 정수 g의 위수가 φ(m)일 때, g를 법 m 에 대한 원시근(primitive root) or 원시원소(primitive element)라고 한다.
p가 소수일 때, 법 p의 원시근을 g라고 하면, g^{(p-1)/2} ≡ -1 mod p 가 성립한다.
✔ 2.5.3 이산 대수
양의 정수 m을 법으로 갖는 법 m의 원시근을 g라고 한다.
{ g^1, g^2, g^3, ..., g^(φ(m)) } 은 법 m에 관한 기약 잉여계가 된다.
gcd(a,m)=1 인 정수 a에 대해서 a ≡ g^i mod m 인 정수 i가 단 하나 존재한다.
즉, 정수 m을 법으로 구성되는 집합 zm 이 원시근 g를 가질 때, gcd(a,m)=1인 a 에 대해 a ≡ g^i mod m 인 i를 법 m에 관한 g를 밑으로 갖는 a의 이산 대수(discrete logarithm) 라고 한다.
i = log g a--> a ≡ g^i mod m
참고도서: 현대 암호학
'Security > 현대 암호학' 카테고리의 다른 글
| [현대암호학] 제 2장 암호수학(3) (1) | 2021.10.04 |
|---|---|
| [현대암호학] 제 2장 암호수학 (2) (0) | 2021.09.29 |
| [현대암호학] 제 2장 암호수학 (1) (0) | 2021.09.21 |
| [현대암호학] 제 2장 수학적 배경 (2) (0) | 2021.07.25 |
| [현대암호학] 제 1장 암호학 (0) | 2021.07.13 |
