[정보보안] 공개키 암호 시스템과 정수론

1. 비대칭 암호화 방식

• Diffie-Hellman Key Exchange Protocol
  • 비대칭키의 개념 소개

 

2. Group의 조건

(S, ⊕)

(1) Closure : ∀a , b , we have a⊕b∈S

(2) Identity :∃ an e∈S s.t e⊕a=a⊕e=a,  ∀a∈S

     주어진 연산에 대한 항등원이 존재 해야 한다.

(3) Associativity : ∀a , b , c ∈S , (a⊕b)⊕ c = a⊕ (b⊕ c)

     결합법칙

(4) Inverse : For each a∈S , ∃ unique element b∈S s.t. a⊕b = b ⊕ a =e

     역원이 존재 

     a에 대하여 항등원이 되도록 하는 b가 존재해야

 

3. Abelian Group

group 조건에 교환법칙 성립

If a group (S,⊕) satisfies the commutative law a⊕b=b⊕a ∀a, b∈S ,

then it is an abelian group

 

4. Zn: finite abelian group

(1) additive group modulo n : (Zn,+n) 

+에 대해서는 finite abelian group이 정의됨.

(2) (Zn, *) 에 대해서는 finite abelian group이 정의 되지 않음.

역원에 대해 0*x mod n ≡ 1 mod n 을 만족하는 x가 없기 때문.

(3) multiplicative group modulo n :

(Zn*,*n), where Zn* = {[a]n ∈ Zn| gcd(a,n)=1}

 

5. 정수론 |Z*n|= ϕ(n) : Euler's phi function

오일러 파이 함수

p는 n의 약수이며 소수인 것p가 소수라면Z*p={1,2, ... , p-1} and ϕ(n) = p-1

 

6. Subgroups

• <a> : the subgroup generated by a
  • <a>= {a^(k)| k>=1}, a is a generator of <a>
• ord(a) : the order of a (in the group S):
  • the least t>0 s.t a^(t) =e (항등원) 

 

7. generator

•  ord_(n)(g)=|Z^*_n| , then every element in Z*n is a power of g modulo n
  • g: a primitive root or a generator of Z*n
• 예) Z*7={1,2,3,4,5,6}

       |Z*7|=6

3	1	2	3	4	5	6
	3	2	6	4	5	1

        ord(3)=6  

       따라서 3은 Z*7의 generator이다.

       또한 Z*7은 cyclic이다. (아래 8번 참조)

 

8. cyclic 

    

9. Euler's Theorem and Fermat's Little Theorem

8번의 ex1)과 ex2)의 표에서 모든 a에 대하여 a ^|Z*n|=1 이 성립함을 확인할 수 있다.

• [Theorem] Euler's Theorem
  • For any integer n>1 , a ^ϕ(n)  ≡ 1 (mod n) for all a∈Z*n
• [Theorem] Fermat's Little Theorem
  • If p is prime, a ^p-1 ≡ 1 (mod p) for all a∈Z*n