암호 기초 스터디 2주차 내용 요약

2.1 정수 집합 : 우리가 초, 중딩때 배운 정수들의 집합이다.

2.1.1 연산의 기본 성질

Z1 집합 Z 위에서 덧셈이 정의된다.

Z2 덧셈에 대해서 교환 법칙이 성립한다.

Z3 덧셈에 대해서 결합 법칙이 성립한다. 

Z4 특정한 정수 0는 덧셈에 대한 항등원이다.

Z5 모든 Z내 원소 a에 대하여, a + (-a) = 0인 -a가 존재하며, -a 또한 Z 내에 포함된다. 이 때 -a를 a에 대한 역원이라고 한다.

Z6 집합 Z 위에서 곱셈이 정의된다.

Z7 곱섬에 대해 교환, 결합 법칙이 성립한다.

Z8 특정한 정수 1은 곱셈에 관한 항등원이다.

Z9 집합 Z 위에서 덧셈과 곱셈은 분배 법칙이 성립한다.

--> 나눗셈은 없는 이유 : 4/3은 정수가 아니잖어~

2.2 약수와 배수

a|b는 b가 a로 나누어 떨어진다는 의미이다. 이 때 a를 b의 약수라고 한다.

만약 d|a, d|b 라면, d는 a와 b의 공약수라고 한다. 공약수중 최대가 되는 수를 최대 공약수라고 한다.

2.2.1 유클리드 호제법

두 정수의 최대 공약수를 계산할 때는 유클리드 호제법을 이용한다. 

유클리드 호제법... 참 쉽다.

28과 12를 유클리드 호제법으로 돌려보자. 먼저 큰수를 작은수로 나눈다.

28 = 12 * 2 + 4가 된다. 유클리드 호제법은 나머지만 열심히 쳐다보면 된다. 나머지인 4를 가지고 작은 수를 나눈다.

12 = 4 * 3 + 0 .... 한번에 됐네 이렇게 되면 종료고, 4가 최대공약수이다. 

그럼 510과 62로 해보자. 위와 같이 510을 62로 나눈다.

510 = 62 * 8 + 14 나머지 14로 다시 62를 나눈다.

62 = 14 * 4 + 6 나머지 6으로 다시 14를 나눈다.

14 = 6 * 2 + 2 나머지 2로 다시 6을 나눈다.

6 = 2 * 3 + 0 이 되어 종료. 최대 공약수는 2이다. 

자 여기서, 위의 식을 위에서 아래로 차례대로, 1, 2, 3, 4번이라고 하자.

그러면 3번을 2(최대 공약수) = 14 - 6 * 2로 나타내자. 여기서 2번에 의해

2 = 14 - (62 - 14 * 4) * 2가 된다. 이를 정리하면, 

2 = 14 * 9 + 62 * (-2)가 된다. 다시, 1번에 의해

2 = (510 - 62 * 8) * 9 + 62 * (-2) 가 되는데, 다시 이를 정리하면,

2 = 510 * 9 + 62 * (-74) 와 같이 510와 62의 곱, 합으로 예쁘게 나타낼 수 있다.

그리고 배수와 공배수는 다 알거라고 믿는다.

2.3 소수

소수는 초등학교때 배워서 이미 잘 알거라고 생각한다. 그리고 책에는 표준분해라고 적혀있지만, 그냥 소인수분해이다. 넘어간다.

2.3.1 소수의 분포

소수의 개수는 무한히 많다. 쉽게 증명할 수 있지만, 본문에서는 생략한다.

양정수 x를 임의로 선택할 때, 2~x 사이의 소수의 개수를 π(x)라고 하면, π(x)와 x/(ln x)의 값이 상당히 유사하다. 

(1) Mersenne 소수

2^p - 1 모양으로 표현될 수 있는 소수를 Mersenne 소수라고 한다. ex> 3 = 2^2 - 1

일반적으로 p가 소수가 되어야만 2^p - 1이 소수이지만, p가 소수라고 무조건 2^p - 1이 소수인건 아니다.

(2) Fermat의 소수 (페르마라고 읽는다)

페르마의 수는 2^(2^n) + 1의 모양으로 표시되는 수를 말한다. (책에는 오타임)
그 중에서 소수를 페르마의 소수라고 한다. 뒤에서 자세히 배울 '페르마의 소정리'에 의하면 p가 소수일때, gcd(a, p) = 1인 모든 a에 대하여, a^(p - 1) ≡ 1 mod p이다.
그러나, 서로소인 모든 a에 대해, a^(n - 1) ≡ 1 mod n 라고해서, n이 소수인건 아니다. 그러나 n은 소수의 성질을 비슷하게 띈다고 하여, 유사 소수이다.(Carmichael 수)
(2) 소수 판정법
확실하고 오래걸리는 방법(결정적 판정법)과 빠르고 확실하지 않은 방법(확률적 판정법)이 있는데,

확오는 Eratosthenes 방법, Euclid 호제법, 페르마의 방법, 윌슨 방법이 있다.
빠확않은 Solovay - Strassen 방법, Lehmann - Peralta 방법, Miller - Rabin 방법 등이 있다.

2.4 합동식

두 정수 a와 b가 m으로 나눠서, 나머지가 같으면 a ≡ b mod m이라고 표기한다. 이는 a - b = mk와 같은 의미이다. 

2.4.1 법 m에 관한 잉여계

법 m에 대한 잉여류는 정수 집합 Z의 임의의 원소 x를 나누어, 나머지가 a가 나오는 x들의 집합이다.

m으로 나누는 경우, 나머지는 1부터 m - 1까지 총 m개가 나올 수 있기 때문에, 법 m에 대해서 정수 집합 Z를 m개의 잉여류들로 분할할 수 있다. 이 때 Z_m= {0, 1, 2, 3, ..., m - 1}을 법 m에 대한 완전 잉여계라 부르는데, 이는 각 잉여류들을 만드는 대표원들의 집합이다.

그리고 이 완전 잉여계가 아니라, m과 서로소인 친구들만 모아놓은 집합을 기약 잉여계라고 한다.

지금까지의 내용을 예로 들면, 법 4에 대해서, Z를 나눈다고 할 때, 법 4에 대한 완전 잉여계는 {0, 1, 2, 3} 이 되고, Z를 총 4개로 분할 할 수 있다.

0이 대표원인 법 4에 대한 잉여류는 {0, 4, 8, 12, ...} 이다.

1이 대표원인 법 4에 대한 잉여류는 {1, 5, 9, 13, ...} 이고,

2가 대표원인 법 4에 대한 잉여류는 {2, 6, 10, 14, ...} 이며,

3이 대표원인 법 4에 대한 잉여류는 {3, 7, 11, 15, ...} 이고,

법 4에 대한 기약잉여계는 {1, 3}이 된다.

기약잉여계의 원소수를 Φ(m)로 나타낸다. 위 예에서 Φ(4)는 2이다. 기약잉여계는 Z_m^*로 나타낸다.

특히 p가 소수이면, Φ(p) = p - 1이 된다. (0을 제외한 모두와 서로소이므로)

2.4.2 Euler의 정리

법 m에 대한 기약잉여계에, m과 서로소인 a를 곱했다고 할 때, 이 또한 기약잉여계가된다. (각 원소가 잉여류의 대표원은 아니겠지만)

식을 좀 쓰기 귀찮은데, 35 page에 적힌 식에 따라서, a^Φ(m) ≡ 1 mod m 이다. 이를 Euler 정리라고 한다.

이때 만약 m이 소수였다면, Φ(m)이 m - 1이므로, a^{m - 1} ≡ 1 mod m 가 된다. 이를 페르마의 소정리라고 한다. 

이후 일차 합동식 어쩌고가 나오는데, 필자는 일차 합동식을 잘 몰라서, 다음에 내용을 보충하도록 하겠다.

2.5 원시근

2.5.1 위수

Euler 정리로부터, 정수 a가 법 m과 서로소이면, a^Φ(m) ≡ 1 mod m이다.

그러나 a의 지수가 Φ(m)인 경우에는 꼭 법 m에 대해 1과 합동한 것은 맞으나, Φ(m)가 그를 만족하는 최소의 지수는 아니다. 그런 상황의 최소의 지수를 위수라고 부른다.

예제) 법 11에서 4와 3의 위수를 구하라.

Φ(11)은 11이 소수이므로, 10일 것이고, 페르마 소정리에 따라,

4^11 = 1,048,576 ≡ 1 mod 11

3^11 = 59,049 ≡ 1 mod 11 임은 분명하다. 

그러나 위에 설명한 대로, 10이 3과 4의 위수라는 보장은 없다. 실제로, 책 39 페이지와 같이 노가다를 뛰어보면, 3^5와 4^5가 처음으로 11로 나누었을 때 나머지가 1이 나온다. 그러므로, 법 11에 대한 3과 4의 위수는 5이다. 

그리고 위수 r과 Φ(m)는 약수관계이다. (즉, r | Φ(m))

2.5.2 원시근

법 m에 관한 정수 g의 위수가 Φ(m)일 때, g를 법 m에 대한 원시근 또는 원시원소 라고 한다. 

예시는 책 40~41 페이지 보시고

만약 g가 원시근일 때, {g^0, g^1, ..., g^Φ(m)}는 법 m에 대한 기약잉여계가 된다. 

여기서 만약 p가 소수일 때, 반드시 원시근이 존재하며, 원시근의 수는 Φ(p - 1)이 된다. 

그리고 법 p의 p가 소수 일때, 원시근을 g라고 하면, 항상 다음 식이 성립한다.

g^(p - 1/2) ≡ -1 mod p

2.5.3 이산 대수

법 m에 대한 원시근 g가 있다고 할 때, 기약 잉여계는 {g^0, g^1, ..., g^Φ(m)}로 표현된다고 했다.

그렇기 때문에, m과 서로소인 a에 대해서, a ≡ g^i mod m인 i가 단 한 개만 존재한다.

이 때 i를 이산대수라고 한다.

이산 대수는 log의 성질을 갖고 있어서, 다음 성질을 갖는다.

log g a = log g b --> a ≡ b mod m

log  g ab ≡ log g a + log g b mod Φ(m)

log g a^n ≡ n * log a mod Φ(m)

그리고 원시근과 이산 대수 문제는 암호학에서 매우 중요하다고 한다.