제 5 장 암호학의 수학기초 2007. 10 Network Security Lab Mun Hyung Jin.

Presentation on theme: "제 5 장 암호학의 수학기초 2007. 10 Network Security Lab Mun Hyung Jin."— Presentation transcript:

1 제 5 장 암호학의 수학기초 Network Security Lab Mun Hyung Jin

2 Part I. 정수론 Introduction to Number Theory

3 목 차 1.1 소수 (Prime Numbers) 1.2 페르마정리와 오일러함수 (Fermat’s and Euler’s Theorems) 1.3 소수 판정 (Testing for Primality) 1.4 중국인 나머지 정리 (The Chinese Remainder Theorem) 1.5 이산대수 (Discrete Logarithms) 3

4 1.1 소수 정수론을 통한 숫자 개념의 정리 공개키 암호 알고리즘의 기초적인 요소 직관적으로 이해가 어려울 때 예제로써 이해
4

5 1.1.1 약수 b|a 이라면 b는 a의 약수(divisor) 표기
어떤 수 m에 대해 a=mb이면 b는(b≠0) a를 나눈다고 함. 나눗셈에서 나머지가 0이면 b는 a를 나눈다고 말함. 여기서 a, b, m은 정수 표기 b|a는 b가 a를 나눈다는 기호로 사용 정수 b는 정수a의 약수다 또는 정수 a는 약수 b를 갖는다 예: 24의 양의 약수는 1, 2, 3, 4, 6, 8, 12 그리고 24이다. 2|24 , 3|24, 8|24 5

6 1.1.1 약수(cont’) 약수에서의 관계 약수 관련 예 b=7; g=14; h=63; m=3, n=2
만약 a|1 이라면, a = 1 임 만약 a|b 이고 b|a라면, a = b 임. 어떠한 0이 아닌 b도 0을 나눔. (b|0) 만약 b|g 이고, b|h 라면, 그 때 임의의 정수 m과 n에 대해 b|(mg+nh) 임. 만약 b|g라면, 그때 g는 어떠한 정수 g1 에 대해 g = b × g1 을 만족, 만약 b|h라면, 그때 h는 어떠한 정수 h1 에 대해 h = b × h1 을 만족. mg + nh = mbg1 + nbh1 = b×(mg1 + nh1) 따라서 b는 mg+nh를 나눈다. 약수 관련 예 b=7; g=14; h=63; m=3, n=2 7|14 와 7|63에 대해서 7|(3×14+2×63)이 성립하는가? 6

7 1.1.2 소수 pi | pk 소수(prime Number)
정수 p >1 이 만약 단지 약수들로써 1과 p만을 가진다면 p는 소수임. 어떠한 정수 a>1은 다음과 같이 유일한 방법으로 인수분해 된다. a = p1α1 p2α2 …. Piαi ; 여기서p1 < p2 < p3 < … < pi 는 소수이고 지수 qi > 0 예 : 91 = 7 × 13 ; = 7 × 112 × 13 pk의 형태를 가지는 어떠한 정수는 단지 그것보다 작거나 같은 지수를 가지는 소수 pj에 의해 나누어질 수가 있음.(jk) pi | pk 7

8 1.1.2 소수(cont’) 양의 정수의 표현 양의 정수의 표현을 0이 아닌 소수들의 멱 지수들로 목록화 예 :
12 = 22 × 31 ⇒ {α2 = 2, α3 = 1} 18 = 21 × 32 ⇒ {α2 = 1, α3 = 2} 모든 p에 대해 a|b ⇒ ap  bp 예 : a=12; b=36 ⇒ 12|36 12 = 22 × 31; 36 = 22 × 32 ⇒ {a2 = 2, a3 = 1}, {b2 = 2, b3 = 2} ⇒ a2 = b2 이고 a3 ≤ b3 임 8

9 1.1.3 최대공약수 gcd(a, b) : 정수 a와 b의 공동약수 중에서 제일 큰 공약수 최대공약수
양의 정수 c가 다음 조건을 만족한다면, c는 a와 b의 최대 공약수 c는 a와 b의 약수임 a와 b에 대한 임의의 약수는 c의 약수임 gcd(a, b) = max { k : k는 k|a이고 k|b } gcd(a, b) = gcd(a, -b)=gcd(-a, b)=gcd(-a, -b)=gcd(|a|, |b|) 9

10 1.1.3 최대공약수(cont’) 소수로 정수를 표현하는 경우 최대공약수 구하기 쉽다 예 : 300 = 22 × 31 × 52
18 = 21 × 32 × 50 gcd(300, 18) = 21 × 31 × 50 = 6 모든 p에 대해, k = gcd(a, b) ⇒ kp = min(ap, bp) 최대공약수 찾기 gcd(a,b) = gcd(b, a mod b) gcd(55,22)=gcd(22, 55 mod 22)= gcd(22, 11)= gcd(11,0)= 11 gcd(18, 12)=gcd(12,6)=gcd(6,0)=6 gcd(11,10)=gcd(10,1)=gcd(1,0)=1 10

11 1.1.4 서로 소 서로 소 : 정수 a 와 b 가 공통적으로 소수 인수를 가지지 못하면 a와 b는 서로 소임.
공약수가 단지 1 뿐임. gcd(a, b) = 1 이라면 a와 b는 서로 소. 8은 약수로서 1, 2, 4와 8을 가지며 15는 약수로서 1, 3, 5 그리고 15를 가지기 때문에 8과 15는 서로 소이다. 또한 1은 이 두 수들이 가지는 약수들의 목록들 중에서 유일하게 같은 수이다. 11

12 1.2.1 페르마의 정리 페르마의 정리 p가 소수이고 a가 p에 의해 나누어지지 않는 양의 정수라면 ap-1 ≡ 1 mod p
(p-1) 숫자들 {a mod p, 2a mod p, ..., (p-1)a mod p}은 어떠한 순서에서의 숫자 {1, 2, p-1}들이다. 이러한 숫자들을 같이 곱하면 a ×2a ×... ×((p-1)a) = (p-1)! ap-1 ≡[(a mod p) ×(2a mod p) ×… ×((p-1)a mod p)] mod p ≡(p-1)! mod p ==> ap-1 ≡ 1 mod p 12

13 1.2.1 페르마의 정리(cont’) 페르마 정리에 의해 ap ≡ a mod p 예 :
p가 소수이고 a가 p에 의해 나누어지지 않는 양의 정수라면 예 : p = 5, a = 3, 35 = 243 ≡ 3 mod 5 p = 5, a = 10, 105 = ≡ 10 mod 5 ≡ 0 mod 5 13

14 1.2.2 오일러 함수 오일러 함수 φ(n) 소수 p에 대하여는 φ(p) = p – 1
n보다 작고 n과 서로 소인 양의 정수의 개수; φ(1) =1 로서 정의됨 표 8.2 : n이 1 부터 30까지 일 때의 φ(n) 소수 p에 대하여는 φ(p) = p – 1 서로 다른 소수 p와 q에 대하여,n = pq 일때, φ(n)=φ(pq)=φ(p)×φ(q)=(p-1)×(q-1) 8 6 12 4 10 2 1 φ(n) 15 14 13 11 9 7 5 3 n 28 18 20 22 16 30 29 27 26 25 24 23 21 19 17 φ(21) = 12 = φ(3) ×φ(7) = 2 × 6 = (3-1) ×(7-1) = 12개 ==> {1,2,3,4,5,8,10,11,13,16,17,19,20}의 정수 12개 14

15 1.2.3 오일러의 정리 오일러 정리 : 서로 소인 모든 a와 n에 대한 관계의 표현 aφ(n) ≡ 1 mod n
오일러 정리의 다른 형태 aφ(n)+1 ≡ a mod n RSA 알고리즘의 유용성을 증명하는 유용한 결과 15

16 1.2.3 오일러의 정리(cont’) 두 개의 소수 p와 q가 주어지고, 0 < m < n 인 정수 n= pq 와 m이 주어진다고 가정하면 m φ(n)+1 = m (p-1)(q-1) + 1 ≡ m (mod n) 16

17 1.3 소수판정 매우 큰 수가 소수인지 판정하는 효율적인 방법의 부재
Fermat’s Theorem 를 가지고 소수 판정에 이용 < Algorithm >: TEST (n) is: 1. Find integers k, q, k > 0, q 홀수, so that (n–1)=2kq 2. Select a random integer a, 1<a<n–1 3. if aq mod n = 1 then return (“가능"); 4. for j = 0 to k – 1 do 5. if (a2jq mod n = n-1) then return(" 가능 ") 6. return (“합성수") a 를 t번 선택을 하여 실험하여 얻은 결과가 소수 가능성은 1-4-t t=10 소수가능성은 17

18 1.3.1 소수판정에 관한 예 n=29 라면 1) n-1=28=(22) *7=(2k) *q. (k=2, q=7)
2) a=10 으로 선택 3) 10^7 mod 29=1 ? (17) No 4,5) j=0 이면 (107) mod 29 =28 ? (17) No j=1 이면 (102)*7 mod 29 =28? (28) Yes Return : 소수일수 있다.(가능성제시) 18

19 1.3.1 소수판정에 관한 예(cont’) n=29 라면 2) a=2으로 선택 3) 27 mod 29=1 ? (12) No
4,5) j=0 이면 (27) mod 29 =28 ? (12) No j=1 이면 (22)*7 mod 29 =28? (28) Yes Return : 소수일수 있다.(가능성제시) 즉 소수라고 판정할 수 있다 19

20 1.3.1 소수판정에 관한 예(cont’) n=221=13*17 라면 1) n-1=220=(22) *55 k=2,q=55
2) a=5으로 택 3) 5^55 mod 221=1 ? (112) No 4,5) j=0 이면 (555) mod 221 =220 ? (112) No j=1 이면 (52)*55 mod 221 =220? (168) No Return : 합성수이다.(composite) 만약 a=21로 선택했다면 return 값이 inconclusive(확정적이 아닌) 가 나온다. 즉 소수일수도 있다는 가능성을 제시한다. 그러나 221는 합성수이다. 20

21 1.3.2 Repeated Use of the Miller-Rabin Algorithm
Test (n) 이 “합성수” 로 리턴이 되면 n는 소수가 아니다. 그러나 Test (n) 이 “가능”으로 리턴이 된다고 n이 소수라는 보장은 못한다. a 를 택하여 반복할 때 반복횟수를 t로 놓으면 n이 소수일 가능성(확률)은 1-(1/4t)이다. 즉 10번 반복해서 “가능”이라고 나오면 n 이 소수일 확률이 (99%)이다. 21

22 1.4 중국인의 나머지 정리 정수론에서 가장 유용한 요소들 중의 하나는 중국인의 나머지 정리
(CRT: Chinese Remainder Theorem) : modulo가 서로소인 쌍 모듈로의 나머지 집합들로부터 어떠한 범위 내에 있는 정수들을 재구성하는 것이 가능. Z10(0, 1, , 9)에서 10개의 정수들은 modulo 2와 5(10의 서로 소인 소인수)의 두 나머지들로부터 재구성될 수 있다. 알려진 10진수 x 의 나머지들은 r2=0와 r5=3이라고 하자 ; 즉, x mod 2 = 0이고 x mod 5 = 3이다. 그런 까닭에 x는 Z10에서 짝수이다. 5에 의한 나눗셈에서 나머지는 3이다. 유일한 해는 x = 8이다. 22

23 1.4 중국인의 나머지 정리 CRT 기원 : '3으로 나누면 2가 남고 5로 나누면 3이 남고 7로 나누면 2가 남는 수 중에서 제일 작은 수는?' 이 문제가 바로 중국인의 나머지 정리의 기원 CRT란 연립 선형 합동식의 공통해를 찾는 문제에 대한 답. 각 선형합동식의 법(moduli)은 쌍마다 서로 소인 가정. 가우스(Gauss),오일러(Euler)가 정리를 많이 연구,이용 그 풀이의 아이디어는 3세기초 중국의 수학자인 순체(Sun-Tzu)가 쓴 책에 있는 위에 쓴 문제의 풀이에서 기원. 중국인의 나머지 정리: m1, m2, ..., mr 이 양의 정수이면서 서로 소라고 하자. 임의의 정수 a1, a1, ...,ar 에 대하여 다음 r 개의 합동식 x=ai (mod mi) (i=1,2,...,r) 은 공통해를 같고 서로 다른 두 해의 차이는 m1*m2*...*mr 로 나누어 떨어진다. 23

24 1.4 중국인의 나머지 정리 중국인의 나머지 정리 다른 예
6로 나누어 나머지가 1이고, 9로 나누어 나머지가 3인 수가 있는가? 질문의 답은 '없다'이다 위에서 알 수 있는 것은 m으로 나누어 나머지가 r , n으로 나누어 나머지가 s인 수는 r과 s를 d=gcd(m,n)로 나눈 나머지가 같지 않으면 해가 존재하지 않는다는 사실이다. 이것의 역, 즉, r,s를 d로 나눈 나머지가 같으면 해가 존재하겠는가 하는 문제를 생각할 수 있는데, 중국인의 나머지 정리는 '해가 반드시 존재'하고, lcm(m,n)의 정수배 차이를 제외하고는 유일하다는 것을 말한다. 24

25 1.5 이산대수 이산대수 Diffie-Hellman의 키 교환과 전자서명 알고리즘((DSA : Digital Signature Algorithm)을 포함하는 공개키 암호 알고리즘에서 중요한 개념 25

26 1.5.1 Modulo n상에서 정수의 멱 오일러의 정리 : aφ(n) ≡ 1 mod n
오일러 함수인 φ(n)은 n보다 작은 양의 정수이고 a 와 n 은 서로 소임. 일반적인 표현 am ≡ 1 mod n -- 식(8.11) 만약 a와 n이 서로 소이라면, m=φ(n)을 만족하는 정수 m이 적어도 하나 존재(멱 지수라 부름) 식 (8.11)을 만족하는 가장 작은 양의 멱 지수 m a (mod n)에 대한 차수 a가 (mod n)에 속한 멱 지수 a에 의해 생성된 주기의 길이 26

27 1.5.1 Modulo n상에서 정수의 멱(cont’)
예 modulo 19상에서 7에 대한 멱 지수 71 = mod 19 72 = 49= 2× = mod 19 73 = 343 = 18× = mod 19 74 = 2401 = 126× = 7 mod 19 75 = = 884 × = 11 mod 19 발견 사항들 73 = 1 (mod 19), 73+j = 737j = 7j (mod 19) 3만큼의 차이가 나는 7에 대한 어떠한 두 멱 지수는 각각 (mod 19)에 있어서 합동(주기가 존재) 주기의 길이는 7m = 1 (mod 19)를 만족하는 가장 작은 양의 멱 지수 m=3 임. 27

28 1.5.1 Modulo n상에서 정수의 멱(cont’)
발견 성질들 1. 모든 순열은 1에서 끝이 남 2. 순열의 길이는 φ(19) = 18 로 구분된다. 즉, 순열에 대한 전체 숫자는 표의 각 행에서 나타남 3. 어떠한 순열들은 길이가 18 이다. 이러한 경우에 있어서, 밑수 a는 modulo19 상에서 0이 아닌 정수들의 집합을 생성함. 그와 같은 각각의 정수를 modulus 19 의 원시 근(primitive root) 라고 부름 28

29 1.5.2 지수 정수 b와 소수 p의 원시근 a에 대해 b ≡ ai mod p,
0 ≤ i ≤ (p-1)인 i 를 지수라 하며 inda,p(b) 로 표기 inda,p(1) = 0, ∵ a0 mod p = 1 mod p = 1 inda,p(a) = 1, ∵ a1 mod p = a 29

30 1.5.3 이산대수의 계산 y = gx mod p g, x 그리고 p가 주어진다면, y를 계산하는 것은 쉬운 문제.
그러나 y, g 그리고 p가 주어진다고 하더라도 x를 계산하는 것은 매우 어려운 문제. 30

31 Part II. 유 한 체 Finite Fields

32 목 차 2.1 군, 링, 체(Groups, Rings, and Fields)
목 차 2.1 군, 링, 체(Groups, Rings, and Fields) 2.2 모듈러 계산 (Modular Arithmetic) 2.3 유클리드 알고리즘 (Euclid’s Algorithm) 2.4 GF(p) 형태의 유한체 (Finite Fields of the Form GF(p)) 2.5 다항식의 계산 (Polynomial Arithmetic) 2.6 GF(2n) 형태의 유한체 (Finite Fields of the Form GF(2n)) 32

33 2.1 Group, Ring, and Field 2.1.1 Groups 2.1.2 Rings 2.1.3 Fields 33

34 2.1.1 Group Group(군)의 정의 : 집합과 연산 덧셈연산에 대하여 닫혀있다. 덧셈연산에서 결합법칙이 성립.
덧셈 항등원이 존재. (Identity) a*e=a가 되는 e가 집합의 원소일 때 e를 항등원 덧셈 역원이 존재. (Inverse) 각 원소 a 에 대하여 a*x=e 가 되는 x를 a 의 역원 예: Sn={permutation of integers} : group 닫혀있고; 결합법칙 성립; 항등원: 항등함수;역원(Inverse element) : 역함수 유한군 (Finite Group) : 원소가 유한인 군 Order of the group : 원소의 개수 34

35 2.1.1 Group 아벨리언 그룹 (Abelian Group) Group 덧셈연산에서 교환법칙 (Commutative) 성립
a+b=b+a, 예 (Z, *) : 그룹이 아니다. Sn (n>2) : Abelian 그룹이 아니다. 합성함수는 교환법칙이 성립하지 않는다. (Z, +) : Abelian group 35

36 2.1.1 Group 순환그룹(Cyclic Group) Group
생성자(Generator)가 존재: 임의의 원소를 특정한 원소로 표현 가능할 때 그 원소를 생성자라 한다. x ∈ G 에 대하여 x= ak (k는 정수) 일 때 a는 생성자이다. 예 (Z, +) : 순환그룹이다 임의의 n에 대하여 1로 표현이 가능하다 (n=n*1) 생성자는 1이므로 (Z, +)=<1>로 표현 가능하다 (A, *) : 순환그룹이다 (A= {-1,1}) 1=(-1)*(-1) , -1=(-1) 생성자는 -1이므로 (A, *)=<-1>로 표현 가능하다. 36

37 2.1.2 Ring Ring Abelian Group 곱셈에 대하여 닫혀있다.
곱셈에 대한 결합법칙 a*(b*c)=(a*b)*c 곱셈에 대한 분배법칙 a*(b+c)=a*b+a*c 예 M2(R) : ring Abelian group; 곱셈에 대하여 닫혀 있고; A*B=2-squar matrix Z : ring Abelian group; 곱셈에 대하여 닫혀 있다. 37

38 2.1.2 Ring 교환 가능한 링(Commutative Ring) Ring 곱셈에 대하여 교환법칙이 성립 a*b=b*a 예
정수 Z : commutative ring M2(R) : 2-square matrices over R commutative ring이 아니다. A*B 와 B*A 가 같지 않다. 38

39 2.1.2 Ring Integral Domain Commutative ring 곱셈에 대한 항등원 : 1
0의 약수가 존재하지 않는다. 즉, a*b =0 이면 a=0 이거나 b=0 이다. 예 Z : Integral Domain M2(R) : Zero divisor 가 존재한다. 즉, A*B=0 이지만 A , B 어느 것도 영행렬이 아니다. 물론 commutative ring이 아니므로 Integral Domain도 아니다. 39

40 2.1.3 Field Field Integral Domain 곱셈에 대한 역원 존재 예 유리수 집합,
정수 집합 Z : field 가 아니다. 40

41 2.2 모듈러 연산 a mod n 의 의미 : a 를 n 으로 나누었을 때의 나머지
예 : 11 mod 7 = 4 , mod 7 = 3 , 10 mod 5 = 0 (a mod n) ≡ (b mod n) 를 만족하면 a 와 b 는 congruent modulo n 라고 한다. 표기 : a ≡ b (mod n) 예 : 73 ≡ 4 ( mod 23) , ≡ -9 (mod 10) b|a ⇔ a=mb 를 만족하는 정수 m 이 존재 이때 b는 a의 divisor라 한다. 41

42 2.2 모듈러 연산 합동식 a  b mod m, m | (a – b)
완전 잉여계(complete residue system) Zm = {0, 1, 2, , m – 1} 기약 잉여계(reduced reside system) Zm* = {a  Zm | gcd(a, m) = 1} Euler 함수  (m) = | Zm* | 42

43 2.2 모듈러 연산 특성 b|g 이고 b|h 이면 임의의 수 m, n에 대하여 b|(m*g+n*h)
a|1 이면 a= 1 또는 -1 a|b 이고 b|a이면 a = b 또는 a = -b a 가 0이 아니면 항상 a|0 b|g 이고 b|h 이면 임의의 수 m, n에 대하여 b|(m*g+n*h) n | (a-b) 이면 a ≡ b (mod n) a=0 (mod n) ⇔ n |a a ≡ b (mod n) 이면 b ≡ a (mod n) a ≡ b (mod n) 이고 b ≡ c (mod n)이면 a ≡ c (mod n) 43

44 2.2 모듈러 연산 Zn ={0,1,2,3, … ,(n-1)} ⇔ Z / n Z Z8 에서의 덧셈
44

45 2.2 모듈러 연산 Z8 에서의 곱셈 Z8 에서의 역원 45

46 2.2 모듈러 연산 성질 (a+b) ≡ (a+c) (mod n) 이면 b ≡ c (mod n)
a, n 서로 소이고 a*b ≡ a*c (mod n) 이면 b ≡ c (mod n) 6*3 ≡ 6*7 (mod 8) ≡ 2 (mod 8) Zn 는 곱셈에 대한 항등원을 가진 commutative ring n 이 소수일때 field가 된다. 이것을 GF(p)라 한다. 46

47 2.2 모듈러 연산 선은 0에서 출발하고 있으며 n, 2n을 통과하여 qn까지 진행 qn≤a 그리고 (q+1)n 〉a을 만족
양의 정수 n과 정수 a가 주어지고, a를 n으로 나눈다면, 다음과 같은 관계를 가지는 몫 q와 나머지 r을 얻는다. a = qn + r ≤ r〈 n; q = a/n  x 는 x보다 작거나 또는 같은 가장 큰 정수이다. 선은 0에서 출발하고 있으며 n, 2n을 통과하여 qn까지 진행 qn≤a 그리고 (q+1)n 〉a을 만족 qn부터 a까지의 거리는 r이며, q와 r의 유일한 값을 찾을 수 있다. 나머지 r은 잉여(residue)라고 한다. 47

48 2.2 모듈러 연산 a = 11; n = 7; = 1 × 7 + 4; r = 4 a = -11; n = 7; = (-2) × 7 + 3; r = 3 a가 정수이고 n이 양의 정수라면, a mod n을 n으로 a를 나누었을 때의 나머지라고 정의 정수 a에 대해, 다음과 같이 표기 a = a/n × n + a (mod n) 11 mod 7 = 4; mod 7 = 3 만약 (a mod n) = (b mod n)이라면, 두 개의 정수 a와 b는 modulo n에 대해 합동이라고 한다. a ≡ b mod n 으로 표기한다. 73 ≡ 4 mod 23; ≡ -9 mod 10 48

49 2.2 모듈러 연산 a ≡ 0 mod n 이라면, 그때 n|a이다. modulo 연산자의 속성
1) n|(a-b)라면  a ≡ b mod n 2) (a mod n) = (b mod n)은  a ≡ b mod n 3) a ≡ b mod n은  b ≡ a mod n 4) a ≡ b mod n과 b ≡ c mod n은  a ≡ c mod n a - b = = n × k ; a ≡ b mod n = = 5 × 3 ;  ≡ 8 (mod 5) = -16 = 8 ×(-2) ;  -11 ≡ 5 (mod 8) = = 27 × 3 ;  ≡ 0 (mod 27) 49

50 2.2 모듈러 연산 모듈러 산술연산(Modular Arithmetic Operation)
1) [(a mod n) + (b mod n)] mod n = (a+b) mod n 2) [(a mod n) - (b mod n)] mod n = (a-b) mod n 3) [(a mod n) × (b mod n)] mod n = (a×b) mod n 11 mod 8 = 3; 15 mod 8 = 7 1) [(11 mod 8) + (15 mod 8)] mod 8 = 10 mod 8 = 2 ( ) mod 8 = 26 mod 8 = 2 2) [(11 mod 8) - (15 mod 8)] mod 8 = -4 mod 8 = 4 ( ) mod 8 = -4 mod 8 = 4 3) [(11 mod 8) × (15 mod 8)] mod 8 = 21 mod 8 = 5 (11 × 15) mod 8 = 165 mod 8 = 5 50

51 2.2 모듈러 연산 거듭제곱승은 일반적인 연산에서와 같이 곱셈을 반복함으로써 수행이 된다
117 mod 13을 계산하기 위한 절차 112 = 121 ≡ 4 mod 13 114 ≡ 42 ≡ 3 mod 13 117 = 11 × 112 × 114 117 mod 13 = (11 × 112 × 114 ) mod 13 = [(11 mod 13) × (112 mod 13) × (114 mod 13)] mod 13 = [(11 mod 13) × (4 mod 13) × (3 mod 13)] mod 13 = [11 × 4 × 3] mod 13 = 132 mod 13 ≡ 2 mod 13 51

52 2.2 모듈러 연산 모듈러 연산의 속성 w ∈ Zn에 대한 z가 존재하면 w+z ≡ 0 mod n을 만족
덧셈에 대한 역원(- ω) (0 + w) mod n = w mod n (1 × w)mod n = w mod n 항등 [w × (x × y)] mod n = [(w × x) × (w × y)] mod n 분배 법칙 [(w + x) + y] mod n = [w + (x + y)] mod n [(w × x) × y] mod n = [w × (x × y)] mod n 결합법칙 (w+x) mod n = (x+w) mod n (w×x) mod n = (x×w) mod n 교환법칙 표현 특성 52

53 2.2 모듈러 연산 (a+b) ≡ (a+c) mod n라면 ==> b ≡ c mod n (1)
(5 + 23) ≡(5 + 7) mod 8; 23 ≡ 7 mod 8 등식 (7.1)은 덧셈에 대한 역원이 존재하여야 성립한다. a에 대한 덧셈에 대한 역원을 등식 (7.1)의 양편에 더함으로서 우리는 다음과 같은 수식을 얻는다. ((-a) + a + b) ≡ ((-a) + a + c) mod n ==> b ≡ c mod n (a×b) ≡ (a×c) mod n ==> b ≡ c mod n (2) 식 (2)는 식(1)과 다르게 추가적인 조건을 가져야만 성립 즉, 추가적 조건은 “a는 n과 서로 소” 일 때만 곱셈역원 존재 6 × 3 ≡ 18 ≡ 2 mod 8 6 × 7 ≡ 42 ≡ 2 mod 8 그러나, 3  7 mod 8 53

54 2.2 모듈러 연산 a와 n이 서로 소 일 때 곱셈 연산에서 유일한 역원 존재 a=5, n=8 일 때
마지막 행은 나머지로 Z8상에 있는 모든 수들을 가르킨다. 만약 p가 소수라면 그때 Zp의 모든 원소들은 p와 서로 소 곱셈에 대한 역수(w-1) 각각의 w∈Zp에 대해, w×z ≡ 1 mod p인 z가 존재. 즉. Zp상에 있는 어떠한 한 숫자는 w에 의해 곱해졌을 때 나머지 값으로 1을 갖게 된다. 그 숫자는 w의 곱셈에 대한 역원이며 w-1로 표시 ((a-1) × a × b) ≡ ((a-1) × a × c) mod n b ≡ c mod n Z8 1 2 3 4 5 6 7 5의 곱 10 15 20 25 30 35 나머지 54

55 2.2 모듈러 연산 + 1 2 3 4 5 6 4 3 2 1 6 5 w -w w-1 - 1 6 2 5 4 3 (a) 7진법 덧셈 + 1 2 3 4 5 6 (c) 7진법 덧셈과 곱셈의 역원 (b) 7진법 곱셈 55

56 2.3 유클리드 알고리즘 최대공약수 gcd(a,b) : a와 b의 최대 공약수 정의
양수 c 가 a와 b의 약수 (즉, c |a, c |b ) 임의의 약수 k가 c의 약수 ( 임의의 k |c 이면 k |a, k |b ) gcd(a,b) = gcd(-a,b) = gcd(a,-b) = gcd(-a,-b) gcd(a,0) = |a| gcd(a,b) = a와 b가 서로소 56

57 2.3 유클리드 알고리즘 최대공약수 찾기 Euclid (a,b) 1. A <- a; B <- b
gcd(a,b) = gcd(b, a mod b) gcd(55,22)=gcd(22, 55 mod 22)=gcd(22, 11) gcd(18, 12)=gcd(12,6)=gcd(6,0)=6 gcd(11,10)=gcd(10,1)=gcd(1,0)=1 Euclid (a,b) 1. A <- a; B <- b 2. If B=0 return A=gcd(a,b) 3. R=A mod B 4. A <- B 5. B <- R 6. Goto 2 57

58 2.4 유한체 GF(p) 4.4.1 유한체 GF(p) 4.4.2 유한체 GF(p) 곱셈 역원 찾기 58

59 2.4 유한체 GF(p) GF( pn) : Galois field
Finite Fields of Order p GF(p)={0,1,2, … ,(p-1)}=Zp Zp : commutative ring 또한 곱셈에 대한 역원이 존재한다. Zero divisor가 존재하지 않는다. 그래서 Zp 는 field이다 참고 Zn (n이 소수가 아닐 때) ; field 가 아니고, 단지 commutative ring 이다. 59

60 2.4 유한체 GF(p) Z7에 관한 덧셈 Z7에 관한 곱셈 Z7 의 역원 60

61 2.4 유한체 GF(p) 유한체 GF(p) 곱셈 역원 찾기 Extended Euclid (m,b)
gcd(m,b)=1이면 b는 곱셈에 대한 역원(mod m)를 갖는다. Extended Euclid (m,b) 1. (A1,A2,A3) <- (1,0,m); (B1,B2,B3) <- (0,1,b) 2. If B3=0 return A3=gcd(m,b) ; no inverse 3. If B3=0 return B3=gcd(m,b); B2=b^(-1) (mod m) 4. Q=[ A3 / B3 ] 5. (T1,T2,T3) <- (A1-QB1, A2-QB2, A3-QB3) 6. (A1,A2,A3) <- (B1,B2,B3) 7. (B1,B2,B3) <- (T1,T2,T3) 8. Goto 2 61

62 2.5 다항식 계산 4.5.1 Ordinary Polynomial Arithmetic
4.5.2 Polynomial Arithmetic with Coefficients in Zp Finding the Greatest Common Divisor 62

63 2.5.1 일반 다항식 연산 정의 n차 다항식 상수 다항식( constant polynomial)
Monic polynomial : 최고차항이 1인 다항식 계산 63

64 2.5.2 다항식연산과 Zp 계수 다항식연산과 Zp 계수 Polynomial ring Polynomial over GF(2)
덧셈은 논리적 AND 계산으로 구할 수 있다. Polynomial f(x) : irreducible over F(field) f(x) 이 1이 아닌 두 다항식의 곱으로 표현할 수 없을 때 참고, 정수에서 소수와 같은 개념으로 보면 쉽다. GF(2) 상에서 f(x)=x4 +1는 reducible 이다. f(x)=(x+1)(x3+x2+x+1) f(x)=x3+x+1 는 irreducible이다. 왜 irreducible 정의가 필요한가? 그 이유는 이 함수가 있어야 order가 2n 인 field를 만들 수 있다. 64

65 2.5.3 Finding the GCD gcd(a(x),b(x))=gcd(b(x), a(x) mod b(x))
다항식에서의 최대공약수 c(x)|a(x), c(x) | b(x) 임의의 약수 k(x)에 대하여, k(x ) | c (x ) gcd(a(x),b(x))=gcd(b(x), a(x) mod b(x)) Euclid (a(x), b(x)) 1. A(x) <- a(x); B(x) <- b(x) 2. if B(x)=0 return A(x)=gcd(a(x), b(x)) 3. R(x)=A(x) mod B(x) 4. A(x) <- B(x) 5. B(x) <- R(x) 6. goto 2 65

66 2.6 확대체 GF(2n) Table 4.5 Arithmetic in GF(23) (a) Addition 66

67 2.6 확대체 GF(2n) Table 4.5 Arithmetic in GF(23) (b) Multiplication 67

68 2.6 확대체 GF(2n) Table 4.5 Arithmetic in GF(23)
(c) Additive and multiplicative inverse 68

69 2.6.1 다항식의 모듈러 연산 Modular Polynomial Arithmetic P=3, n=2 일 때의 다항식의 집합은
{0, 1, 2, x, x+1, x+2, 2x, 2x+1, 2x+2} p = 2, n=3 일 때의 다항식의 집합은 {0, 1, x, x+1, x2, x2+1, x2+x, x2+x+1} 계산 69

70 2.6.1 다항식의 모듈러 연산 유한체 GF(23)를 만들기 위해서는 3차인 인수분해가 안 되는 다항식(irreducible polynomial)이 필요하다. 예 : 70

71 2.6.2 다항식 곱셈연산의 역원 71

72 2.6.2 다항식 곱셈연산의 역원 Extend Euclid [m(x),b(x)]
[A1(x),A2(x),A3(x)] <- [1,0,m(x)]; [B1(x),B2(x),B3(x)] <- [0,1,b(x)] if B3(x)=0 return A3(x)=gcd[m(x),b(x)] ; no inverse if B3(x)=1 return B3(x)=gcd[m(x),b(x)] ; B2(x)=b(x)-1 (mod m(x)) Q(x)=quotient of A3(x)/B3(x) [T1(x),T2(x),T3(x)] <- [A1(x)-Q(x)B1(x),A2(x)-Q(x)B2(x),A3(x)-Q(x)B3(x)] [A1(x),A2(x),A3(x)] <- [B1(x),B2(x),B3(x)] [B1(x),B2(x),B3(x)] <- [T1(x),T2(x),T3(x)] goto 2 72

73 2.6.3 연산적 고찰 덧셈(Addition) 곱셈(Multiplication) 다항식을 2진수로 표현한다.
각 비트 마다 XOR로 계산한다. 곱셈(Multiplication) 73

74 2.6.3 연산적 고찰 ( )х( )=( ) ( )х( )=( ) ( )=( ) ( )х( )=( ) ( )х( )=( ) ( )=( ) ( )х( )=( ) ( )х( )=( ) ( )х( )=( ) ( )( )=( )[( ) ( ) ( )] =( ) ( ) ( )=( ) 74