2011. 4. 17. 04:35ㆍ카테고리 없음
* M:평문, C:암호문, E:암호화 알고리즘, D:복호화 알고리즘, KE:암호화키, KD:복호화키
@ 암호학 - 수학적 배경 (정수론) 요약 (ctrl+F로 찾기)
* R:실수 집합, Z:정수 집합, N:자연수 집합, Z₅={0,1,2,3,4}
* 집합 Z위에서 덧셈이 정의되고, 덧셈에 대하여 교환법칙, 결합법칙이 성립한다. Z에 속하는 모든 a에 대하여 항등원(자기 자신을 만드는 수, 정수 0), 역원(0으로 만드는 수)이 존재 한다.
* 집합 Z위에서 곱셈이 정의되고, 곱셈에 대하여 교환법칙, 결합법칙, 분배법칙이 성립한다. 정수 1을 곱셈에 대한 항등원이라 한다. Z위에서 덧셈은 모든 원소가 역원을 갖고 있으나 곱셈에 대해서는 1과 -1만 역원(1로 만드는 수)을 갖는다. 따라서 Z위에는 나눗셈이 정의되지 않는다.
* b=aq+r
* a | b , a는 b를 나눈다, b는 a로 나누어 떨어진다. d | a, d | b, d는 a와 b의 공약수
* 최대공약수 : g=(a, b), g=gcd(a, b)
* 서로소 : 두 정수 a와 b의 최대 공약수가 1일 때, 즉 gcd(a, b)=1일 때 a와 b는 서로소라 한다.
* 공배수 : a | c, b | c인 정수 c를 a와 b의 공배수라고 함
* 최소 공배수 : l=[a, b], l=lcm(a, b)
* 유클리드 호제법 : 두 정수의 최대 공약수를 계산할 때 사용, gcd(a, b)=au+bv인 정수 u와 v를 구할 수 있다.
ex) 510과 62의 최대 공약수를 구하고 u와 v를 구하라
510 = 62x8+14 2=14-6x2=14-(62-14x4)x2=14x9+62x(-2)=(510-62x8)x9+62x(-2)
62=14x4+6 =510x9+62x(-74)
14=6x2+2
6=2x3 최대 공약수는 2 , 참고: 최소공배수 = a*b/최대공약수
* 소수 :１과 자신 이외의 약수가 존재하지 않는 양의 정수 (합성수: 소수가 아닌 정수)
* 표준분해 : 소인수 분해 표현법
* AKS 알고리즘 : 결정적 소수 판정 알고리즘
* 모듈라 연산 : 법(modulus)값에 다다르면 다시 초기 값을 갖는 연산, clock arithmetic 이라고도 함
40%12=4, 40≡4(mod12) 40과 4는 법(modulus 12)에 관하여 합동이다.
a≡b(mod m) a와 b의 차가 m의 배수일 때 합동(a-b=mk), a와 b는 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이 성립
* 합동은 반사적(a≡a mod m), 대칭적(a≡b mod m이면 b≡a mod m), 추이적(a≡b mod m, b≡c mod m이면 a≡c mod m의 세 가지 성질을 갖는다. 그러므로 합동관계는 정수 전체의 집합 Z위에서 동치관계
* 따라서 a≡b(mod m)에 대한 정수 집합 Z위의 동치류를 법 m에 대한 잉여류라고 한다. ex) 법 4에 대한 잉여류 : 3,7,11,15,19,23...
* 이때 법 m에 대한 잉여류를
* 법 m에 대한 완전 잉여계 ex) Z₉={0,1,2,3,4,5,6,7,8} 법9에 대한 완전 잉여계다, 각 원소를 잉여류의 대표원이라 함
* 법 m에 대한 기약 잉여계 : 기약영여계 Zm*은 완전 잉여계 원소 중에서 m과 서로소인 원소 전체의 집합
* Euler(오일러)의 φ(phi)함수 : 법 m에 대한 기약 잉여계의 개수 즉, φ(m)=개수
* 특히 m이 소수일 때 φ(m)=(p-1)이다. ex) 7의 경우, 1,2,3,4,5,6 6개, 0은 서로소의 관계에서 빠진다.
* 만일 m=pxq이고 p와 q가 소수인 경우, φ(m)=φ(p)xφ(q)=(p-1)x(q-1)
* 기약 잉여계 내의 각 원소에 gcd(a, m)=1을 만족하는 양의 정수 a를 곱한 집합도 기약 잉여계가 된다.
ex) 9의 기약잉여계 {1,2,4,5,7,8}에 gcd(2, 9)=1을 만족하는 양의 정수 2를 곱한 {2,4,8,10,14,16}도 기약 잉여계다
* 오일러의 정리, 페르마의 소정리 : 공개키 암호 방식에 가장 널리 사용되는 수학적인 정리
* 오일러의 정리 : 양의 정수 m과 (a, m)=1인 정수 a에 대하여 aφ(m) ≡ 1(mod m)이 성립한다.
* 페르마의 소정리 : p가 소수이면 φ(p)=p-1이므로, a p-1 ≡ 1(mod m)이 성립한다.
* 따라서 p가 소수일 때 정수 a에 대하여(양쪽에 a를 곱하면) a p ≡ a(mod p)가 성립한다.
* 일차 합동식 ax≡b(mod m)에서 정수 a와 m이 서로소이면 x는 단 하나의 해를 갖는다.
* a와 m이 서로소 -> gcd(a, m)=1 -> au+mv=1인 정수 u와 v가 존재(유클리드 호제법이용)
* 일차합동식 해 구하기2 : ax≡b(mod m)의 해는 a의 승산역원을 구해 양변에 곱해주면 쉽게 구할 수 있다.
* 승산역원을 가지려면 a와 m이 서로소이어야 한다. 승산역원은 유클리드 호제법을 이용하여 구한다.
* 원시근 : 공개키 암호 방식의 기반문제인 이산대수 문제 구성에 널리 이용되는 수학적 개념
* 위수 : b의 r승 ≡ 1(mod m)을 만족시키는 양의 정수 r이 존재하게 된다. 이 때 가장 작은 r을 법 m에 대한 b의 위소(order)라고 한다,
* 법 m에 관한 a의 위수는 오일러 함수보다 작으며 실제로 위수 r은 오일러 함수와 약수 관계이다.
* 법 m에 관한 g의 위수가 오일러함수m일 때 g를 법 m에 대한 원시근 또는 원시원소라고 한다. 오일러함수=위수
* 원시근의 1부터 오일러함수까지의 누승은 법m에 관한 기약잉여계 ///////
* 법 p의 p가 소수이면 반드시 원시근이 존재하며 원시근의 수는 φ(p-1)이 된다.
ex) mod 5에서 5가 소수이므로 반드시 원시근이 존재한다. p=5 φ(5)=4, 원시근의 수는 φ(p-1)=φ(4)=2
* 또, 법 p의 p가 소수일 때의 원시근을 g라고 하면 항상 다음 식이 성립한다.
* 이산대수 : 앞에서 언급한 바와 같이 양의 정수 m을 법으로 갖는 법 m의 원시근을 g라 하면 다음은 법 m에 관한한 기약 잉여계가 된다. {g의1승,g의2승......g의 오일러함수승}, 따라서 gcd(a, m)=1인 정수 a에 대하여 다음의 식을 만족하는 정수 i가 단 하나만 존재하게 된다.
* 원시근으로 만들어지는 이산대수 문제는 암호학 이론 분야에서 중요한 역할, 암호키 분배 방식과 전자 서명에 많이 이용
* 중국인의 잉여정리 : 연립 1차 합동식의 해를 구할 때 널리 사용, 양의 정수 m1,m2,m3...mn이 쌍마다 서로소일 때
연립 1차 합동식
m=Mi(자신을 뺀 정수들의 곱) x mi(자신), gcd(mi,Mi)=1이므로 Mi x Ni =1mod mi를 성립하는 Ni가 존재한다.
풀이법 : 각 식의 Mi값을 구하고, Ni값들을 구해서 각 Mi,Ni와 bi(mod 앞값)들을 곱한 다음 더한다. 이때 법은 m
* 오일러의 φ함수 : p가 소수이면 φ(p)=p-1, φ(p의e승)=p의e승-p의e-1승
* x제곱 ≡ a mod m 이 해를 가질 때 a를 m에 대한 이차 잉여라 하고, 해를 가지지 않을 때 a를 법 m에 대한 이차 비잉여라 한다.
* 이차잉여 : 기약잉여계에서 나머지로 나오는 값들, 이차비잉여 : 나머지로 나오지 않는 값들
* 군 : 1.집합위에서 이항연산이 정의 된다 a*b∈G, 2.이항연산에 대해 결합법칙이 성립한다. 3.항등원이 존재한다, 4. 역원이 단 하나 존재한다. 가산 +일 때 가산군이라 하고, 승산 X일 때 승산군이라 한다.
* 군에 다라 교환 법칙이 성립하는 경우, 가환군 혹은 아벨리안 군이라 한다.
* 환 : 집합 R이 두가지 연산이 정의되고 1.가산에 대하여 가환군이다. 2.두 원소에 대해 axb는 집합 R에 속한다. 3. 세 개의 원소에 대하여 결합법칙이 성립한다. 4. 3개의 원소에 대하여 분배 법칙이 성립한다. 앞 4가지의 성질을 만족하면 환이라 하며, 특히 두 개의 원소에 대하여 교환 법칙이 성립되면 가환환이라 한다.
* 승산에 대한 단위원이 존재하고, 영이 아닌 원소가 승산에 대하여 역원을 갖는 가환환을 체(field)라고 하며, 특히 그 원소의 수가 유한한 체를 유한체라 한다.
*
* GF(p의m승) 역시 유한체를 이룬다, 확대 갈로아체 라 한다.
* 풀 수 있는 문제 : 쉬운문제-다항식 문제(P 문제), 어려운 문제-지수식 문제(NP 문제)
* NP 문제 : 소인수 분해, 이산대수, Knapsack