10주차_현대암호학 기초 [기초 대수학]

1주차_현대암호학 기초 < 기초 정수론 > (tistory.com)

1주차_현대암호학 기초 < 기초 정수론 >

 

1주차 내용에서 살펴보면 기초정수론을 학습했는데, 10주차는 기초 대수학을 학습했다.

 

 

📌 Group (군)

 

Group (군) 정의

• 공개키 암호 알고리즘이 정의되는 수학적 구조
  •  RSA 암호, ElGamal 암호, DSA 전자서명
  • 타원곡선

 

Group의 정의 

공집합이 아닌 집합 𝐺 와 𝐺의 원소에 대해 다음을 만족하는 연산 ⊗가 정의되면 (𝐺,⊗) 를 Group이라고 부른다 

[결합법칙]
연산 ⊗ 에 대해 결합법칙이 성립한다.
𝑎 ⊗ 𝑏 ⊗ 𝑐 = 𝑎 ⊗ (𝑏 ⊗ 𝑐) 

[항등원]
𝐺의 모든 원소 𝑎에 대해 연산 ⊗ 에 대한 항등원 𝑒 ∈ 𝐺가 존재한다.
𝑎 ⊗ 𝑒 = 𝑒 ⊗ 𝑎 = 𝑎 

[역원]
𝐺의 각 원소 𝑎에 대해 연산 ⊗ 에 대한 역원 𝑎 −1가 존재한다.
𝑎 ⊗ 𝑎 −1 = 𝑎 −1 ⊗ 𝑎 = 𝑒

 

Group 예시

공집합이 아닌 집합 𝐺 와 𝐺의 원소에 대해 다음을 만족하는 연산 ⊗ 가 정의되면 (𝐺,⊗) 를 Group이라고 부른다. 

 

𝑎 ⊗ 𝑏 ⊗ 𝑐 = 𝑎 ⊗ (𝑏 ⊗ 𝑐) 

𝑎 ⊗ 𝑒 = 𝑒 ⊗ 𝑎 = 𝑎 

𝑎 ⊗ 𝑎 −1 = 𝑎 −1 ⊗ 𝑎 = 𝑒

 

Group 조건 : 결합법칙 만족, 항등원 존재, 역원 존재한다.

 

✅ 예를 들어서 아래와 같다. (+ , x , z*일때)

 

(𝑍𝑛, +) 

𝑍𝑛 = 0,1, … , 𝑛 − 1 

 

Group

[결합법칙] 𝑎 + 𝑏 + 𝑐 = 𝑎 + 𝑏 + 𝑐 𝑚𝑜𝑑 𝑛 

[항등원] 𝑎 + 0 = 0 + 𝑎 = 𝑎 (𝑚𝑜𝑑 𝑛) 

[역원] 𝑎 + −𝑎 = −𝑎 + 𝑎 = 0 (𝑚𝑜𝑑 𝑛)

 

(𝑍𝑛, ×)

Group이 아니다.

 

[결합법칙] 𝑎 ⋅ 𝑏 ⋅ 𝑐 = 𝑎 ⋅ 𝑏 ⋅ 𝑐 𝑚𝑜𝑑 𝑛 

[항등원] 𝑎 ⋅ 1 = 1 ⋅ 𝑎 = 𝑎 (𝑚𝑜𝑑 𝑛) 

[역원] 모든 원소에 대해 존재한다고 할 수 없다.

2 ∈ 𝑍6 

2 ⋅ 𝑥 = 1 𝑚𝑜𝑑 𝑛 인 𝑥 존재하지 않는다.

 

(𝑍𝑛 ∗ , ×)

𝑍𝑛의 원소 중에서 곱셈에 대한 역원이 존재하는 숫자들의 집합이다. 

즉, 0, … , 𝑛 − 1 중에서 𝑛 과 서로소인 수들의 집합이다.

Group (RSA 암호에서 사용)

 

[결합법칙] 𝑎 ⋅ 𝑏 ⋅ 𝑐 = 𝑎 ⋅ 𝑏 ⋅ 𝑐 𝑚𝑜𝑑 𝑛

[항등원] 𝑎 ⋅ 1 = 1 ⋅ 𝑎 = 𝑎 (𝑚𝑜𝑑 𝑛) 

[역원] 정의상 역원이 존재하는 원소들로만 구성되어 있다.

 

 

Group 예시

 

(𝑍15∗ , ×)

𝑍15∗ = { 1 , 2 , 4 , 7 , 8 ,11 ,13 ,14 }

연산에 대해 닫혀있음

 

[결합법칙]

𝑎 ⋅ 𝑏 ⋅ 𝑐 = 𝑎 ⋅ 𝑏 ⋅ 𝑐 𝑚𝑜𝑑 𝑛 

 

[항등원] 1 이 존재한다.  

𝑎 ⋅ 1 = 1 ⋅ 𝑎 = 𝑎 (𝑚𝑜𝑑 𝑛 ) 

 

[역원]

모든 원소가 곱셈에 대한 역원을 가진다.

 

1−1 = 1 (𝑚𝑜𝑑 15)

2−1 = 8 (𝑚𝑜𝑑 15) 

4−1 = 4 𝑚𝑜𝑑 15 

7−1 = 13 (𝑚𝑜𝑑 15) 

8−1 = 2 (𝑚𝑜𝑑 15) 

11−1 = 11 (𝑚𝑜𝑑 15)

13−1 = 7 (𝑚𝑜𝑑 15) 

14−1 = 14 (𝑚𝑜𝑑 15)

 

< 연산 테이블 >

	1	2	4	7	8	11	13	14
1	1	2	4	7	8	11	13	14
2	2	4	8	14	1	7	11	13
4	4	8	1	13	2	14	7	11
7	7	14	13	4	11	2	1	8
8	8	1	2	11	4	13	14	7
11	11	7	14	2	13	1	8	4
13	13	11	7	1	14	8	4	2
14	14	13	11	8	7	4	2	1

 

 

(𝑍𝑝 ∗ , ×) 

𝑝: 소수

𝑍𝑝 ∗ = 1, … , 𝑝 − 1 

 

Group (ElGamal 공개키 암호 & DSA 전자서명 에서 사용된다. )

 

[결합법칙] 𝑎 ⋅ 𝑏 ⋅ 𝑐 = 𝑎 ⋅ 𝑏 ⋅ 𝑐 𝑚𝑜𝑑 𝑝

[항등원] 𝑎 ⋅ 1 = 1 ⋅ 𝑎 = 𝑎 (𝑚𝑜𝑑 𝑛) 

[역원] 1, … , 𝑝 − 1 는 모두 𝑝 와 서로소 → 곱셈에 대한 역원이 존재

 

 

Group 표기법

 

Group 연산 ⊗ 는 크게 덧셈 + 또는 곱셈 × 로 정의됨 

연산에 따라 아래와 같은 표기를 사용한다.

 

	곱셈 연산 Group	덧셈 연산 Group
원소	𝑔 ∈ G	𝑎 ∈ 𝐴
항등원	1	0
역원	𝑔 −1	− 𝑎
거듭제곱 (지수)	𝑔 1 = 𝑔, 𝑔 0 = 1, 𝑔 −1	1 ⋅ 𝑎 = 𝑎, 0 ⋅ 𝑎 = 0, −1 ⋅ 𝑎 = − 𝑎
	𝑔 3 = 𝑔 ⋅ 𝑔 ⋅ 𝑔	3𝑎 = 𝑎 + 𝑎 + 𝑎
	𝑔 −3 = 𝑔 −1 ⋅ 𝑔 −1 ⋅ 𝑔 −1 = (𝑔 −1 )^3	-3𝑎 = −𝑎 − 𝑎 − 𝑎 = 3 ⋅ (−𝑎)

 

 

Abelian Group

 

• Abelian group 
• 가환군 또는 Commutative group 
• Group (𝐺,⊗) 에서 연산⊗에 대해 교환법칙이 성립하는 경우를 말함
  • 𝑎 ⊗ 𝑏 = 𝑏 ⊗ 𝑎
• 예시) (𝑍𝑛, + )
  • 𝑎 + 𝑏 = 𝑏 + 𝑎 (𝑚𝑜𝑑 𝑛) 
• 예시) (𝑍𝑛 ∗ , ×) , (𝑍𝑝 ∗ , ×) 
  • 𝑎 ⋅ 𝑏 = 𝑏 ⋅ 𝑎 (𝑚𝑜𝑑 𝑛)

2. 아벨군(Abelian Group), 유한.. : 네이버블로그 (naver.com)

2. 아벨군(Abelian Group), 유한군(finite group), 위수(order), 덧셈군(additive group), 곱셈군(multiplicative group)

 

Group 위수 (order)

 

• Group order (위수)
  • Group 𝐺의 원소의 개수 
  • |𝐺|로 표기
  • 𝑍5 ∗ = 1,2,3,4 = 4 
  • |𝑍15 ∗ | = |{1,2,4,7,8,11,13,14}|=8 
  • |𝐺|가 유한한 값 ℓ → 모든 𝑔 ∈ 𝐺 에 대해 𝑔 ℓ = 1 
  • 임의의 𝑔 ∈ 𝐺 에 대해 𝑔 𝑖 = 𝑔 𝑖 𝑚𝑜𝑑 |𝐺| 
    • 𝑖 = ℓ ⋅ 𝑘 + 𝑗 → 𝑔 𝑖 = 𝑔 ℓ⋅𝑘+𝑗 = 𝑔 𝑘 ℓ ⋅ 𝑔 𝑗 = 𝑔 𝑗
• Group 원소의 order 
  • Group 𝐺의 원소 𝑔의 위수  𝑔^n⇔ = 1이 되는 최소 자연수
  • |𝑔|로 표기
  • 2 ∈ 𝑍5 ∗ 의 위수 : 2 ^1 = 2, 2^ 2 = 4, 2^ 3 = 8 = 3, 2^ 4 = 16 = 1 → 2 = 4 
  • 5 ∈ 𝑍13 ∗ 의 위수 : 5, 5^ 2 = 12, 5^ 3 = 8, 5^ 4 = 1 → 5 = 4 
  • 2 ∈ 𝑍15 ∗ 의 위수 : 2, 2^ 2 = 4, 2^ 3 = 8, 2^ 4 = 16 = 1 (𝑚𝑜𝑑 15) → 2 = 4

 

Cyclic Group

 

• Cyclic group
  • Group (𝐺,⊗)의 모든 원소가 하나의 원소 𝑔의 거듭제곱 (지수)로 표현되는 Group 
  • 생성 원소 𝑔 를 generator라고 부른다.
  • (표기) 𝐺 = ⟨𝑔⟩ = {𝑔 0 = 1, 𝑔, 𝑔 2 , … } 
• 예시 (𝑍5 ∗ , ×) 
  • 𝑍5 ∗ = ⟨2⟩ = 1,2,3,4
    • 2^ 1 = 2, 2^ 2= 4, 2^ 3= 8 = 3, 2^ 4= 16 = 1 
• 소수 𝑝 에 대 𝑍𝑝 ∗는 항상 cyclic group 
  • 𝑍𝑝 ∗ =⟨𝑔⟩ 가 되는 generator 𝑔 가 존재

 

Subgroup (부분군)

• [정의] Group 𝐺,⊗ 의 공집합이 아닌 부분집합 𝐻 ⊂ 𝐺
  • (𝐻,⊗)도 group이 되면 subgroup이라고 정의
  • 표기 : 𝐻 ≤ 𝐺 또는 𝐻 < 𝐺
• [예시] 
  • 𝐺 = 𝑍7 ∗ = 1,2,3,4,5,6 
  • 𝐻 = 1,2,4 
    • 곱셈에 대해 결합법칙 성립
    • 항등원 1 존재
    • 모든 원소에 대해 역원이 존재
      • 1 −1 = 1 (𝑚𝑜𝑑 7), 2 −1 = 4 𝑚𝑜𝑑 7 , 4 −1 = 2 (𝑚𝑜𝑑 7)

Subgroup 성질

 

라그랑즈(Lagrange) 정리 

Group 𝐺 의 위수가 유한한 수 𝑛 이라고 하면, 모든 𝐺의 subgroup 𝐻의 위수는 𝑛 의 약수이다. 

즉, 𝐻 | |𝐺| 이다.

 

EX) 𝑍7 ∗ = 1,2,3,4,5,6 의 subgroup 𝐻 = 1,2,4 → 𝐻 = 3, 𝑍7 ∗ = 6 & 3 | 6

 

• 라그랑즈 정리의 역은 일반적으로 성립하지 않는다.
• 일반적으로, Group 𝐺 의 위수가 𝑛 이라할 때, 𝑚|𝑛 인 자연수 𝑚이 있다고 하더라도 위수가 𝑚인 𝐺의 subgroup 𝐻 가 항상 존재하지는 않는다.
• 특이한 경우에 대해서만 라그랑즈 정리의 역이 성립 (cyclic group)
• 아래에서는 유한한 위수 ℓ 을 가지는 Group Group 𝐺를 고려 
• 임의의 𝑔 ∈ 𝐺 에 대해 ⟨𝑔⟩는 𝐺의 subgroup
  • 𝑔 𝑖 ⋅ 𝑔 𝑗 = 𝑔 𝑖+𝑗 ∈ ⟨𝑔⟩ 
  • 𝑔 𝑖 ⋅ 𝑔 𝑗 ⋅ 𝑔 𝑘 = 𝑔 𝑖+𝑗+𝑘 = 𝑔 𝑖 ⋅ (𝑔 𝑗 ⋅ 𝑔 𝑘 ) 
  • 𝑔 = 𝑛 ⇔ 𝑔 𝑛 = 1 ∈ ⟨𝑔⟩ 
  • 𝑔 = 𝑛 ⇒ 𝑔 𝑖 −1 = 𝑔 𝑛−𝑖 
• 𝐻 ≤ 𝐺 이면 모든 ℎ ∈ 𝐻 에 대해 ℎ |𝐺| = 1 
  • 라그랑즈 정리에 의해 𝐺 = 𝑠|𝐻| 인 자연수 𝑠가 존재 → ℎ ^|𝐺| = ℎ^ 𝑠|𝐻| = (ℎ^ 𝑠)^ |𝐻| = 1

Cyclic Group의 Subgroup

 

• 𝐺 = ⟨𝑔⟩, 𝑔 = 𝑛 에 대해 아래가 성립한다.
• Cyclic group 𝐺의 subgroup 𝐻 도 cyclic group (𝐺가 무한 위수를 가지더라도 이 사실은 성립) 
  • 𝐺 = 𝑍7 ∗ = 1,2,3,4,5,6 = ⟨5⟩ 
  • 𝐻 = 1,2,4 = 2 ≤ 𝐺 
• Cyclic group 에서는 라그랑즈 정리의 역이 성립한다.
  • 𝑑 | 𝑛 이면 위수가 𝑑 인 𝐺의 subgroup 𝐻가 유일하게 존재한다.

𝐺 = ⟨𝑔⟩, 𝑔 = 𝑛 에 대해 아래가 성립

 

gcd 𝑛, 𝑚 = 1 → 𝐺 = ⟨𝑔⟩ = ⟨𝑔 ^𝑚 ⟩

 

𝐺 = ⟨𝑔⟩, 𝑔 = 𝑛 에서 order가 𝑑 인 subgroup 𝐻 찾기 (𝑑|𝑛)

cyclic group의 subgroup 은 cyclic group 이므로 order가 𝑑 인 ℎ ∈ 𝐺 를 구하는 것과 동일하다.

 

 

📌 Ring (환)

 

𝑍𝑛의 구조

 

• 𝑍𝑛 = {0,1, … , 𝑛 − 1} 
• 𝑚𝑜𝑑 𝑛 더하기, 곱하기가 모두 잘 정의되며 다양한 연산 법칙이 성립 
  • 덧셈에 대한 결합법칙 성립
  • 덧셈에 대한 교환법칙 성립
  • 덧셈에 대해 항등원과 역원이 존재 
  • 곱셈에 대해 결합법칙 성립
  • 분배법칙 성립 
  • 곱셈에 대한 교환법칙 성립 
  • 곱셈에 대해 항등원 존재 
• (𝑍𝑛, +) 는 Group이 된다.
• 𝑍𝑛 의 경우 덧셈 외에 곱셈 연산도 상당히 잘 됨 (즉 연산이 하나 더 있음) 
  • Group은 이러한 성질을 가지는 대수적 구조를 다루지 않는다.
  • 𝑍𝑛 을 설명하기 위해서는 Group 외에 확장된 대수적 구조를 정의하는 것이 필요하다.

 

Ring (환)

 

공집합이 아닌 집합 𝑅 와 𝑅의 원소에 대해 다음을 만족하는 두 개의 연산 +𝑅 과 ×𝑅 이 정의되면 (𝑅, +𝑅, ×𝑅) 를 Ring(환)이라고 부른다.
1. [+𝑅에 대한 결합법칙] 모든 𝑎, 𝑏, 𝑐 ∈ 𝑅 에 대해 𝑎 +𝑅 𝑏 +𝑅 𝑐 = 𝑎 +𝑅 (𝑏 +𝑅 𝑐)
2. [+𝑅에 대한 교환법칙] 모든 𝑎, 𝑏 ∈ 𝑅 에 대해 𝑎 +𝑅 𝑏 = 𝑏 +𝑅 𝑎
3. [ +𝑅 에 대한 항등원] 𝑅의 모든 원소 𝑎에 대해 𝑎 +𝑅 0𝑅 = 0𝑅 +𝑅 𝑎 = 𝑎 인 항등원 0𝑅 ∈ 𝑅 존재
4. [+𝑅에 대한 역원] 𝑅의 각 원소 𝑎에 대해 𝑎 +𝑅 (−𝑎) = 0𝑅 인 역원 −𝑎 ∈ 𝑅 존재
5. [×𝑅에 대한 결합법칙] 모든 𝑎, 𝑏, 𝑐 ∈ 𝑅 에 대해 𝑎 ×𝑅 𝑏 ×𝑅 𝑐 = 𝑎 ×𝑅 (𝑏 ×𝑅 𝑐)
6. [분배법칙] 모든 𝑎, 𝑏, 𝑐 ∈ 𝑅 에 대해 𝑎 ×𝑅 𝑏 +𝑅 𝑐 = 𝑎 ×𝑅 𝑏 +𝑅 𝑎 ×𝑅 𝑐 , 𝑏 +𝑅 𝑐 ×𝑅 𝑎 = 𝑏 ×𝑅 𝑎 +𝑅 𝑐 ×𝑅𝑎)

 

1, 2, 3, 4 에 따라 (𝑅, +𝑅) 은 Abelian group (가환군, Commutative group)

Ring은 Abelian group에서 5, 6을 만족하는 연산이 하나 더 추가된 것이다.

단, ×𝑅에 대해 교환법칙이 성립할 필요는 없음 & ×𝑅에 대해 항등원, 역원이 존재할 필요도 없다.

 

예시

정수 𝑍 & 더하기, 곱하기 연산 

𝑍𝑛 = 0,1, … , 𝑛 − 1 & 𝑚𝑜𝑑 𝑛 더하기, 곱하기 연산 

𝑍𝑛 의 경우 곱하기에 대한 항등원 1이 존재 → 이러한 ring을 ring with 1 이라고 부름

𝑍𝑛 의 경우 곱하기에 대해 교환법칙이 성립 → 이러한 ring을 commutative ring (가환환) 이라고 부름

 

행렬 

𝑛 × 𝑛 정수 행렬 집합 𝑀𝑛×𝑛(𝑍) & 행렬 덧셈, 곱셈 연산 

𝑛 × 𝑛 𝑍𝑛 행렬 집합 𝑀𝑛×𝑛(𝑍𝑛) & 행렬 𝑚𝑜𝑑 𝑛 덧셈, 𝑚𝑜𝑑 𝑛 곱셈 연산

행렬 요소 숫자 집합에 따라 곱셈에 대한 항등원, 역원이 존재하지 않을 수 있음 

즉, 행렬은 Ring이 가져야할 조건을 최소한으로 만족하는 ring이라고 할 수 있음

 

 

📌 Finite Field (유한체)

𝑍𝒑의 구조

 

• 𝑍𝑝 = {0,1, … , 𝑝 − 1} 
• 𝑚𝑜𝑑 𝑝 더하기, 곱하기가 모두 잘 정의되며 다양한 연산 법칙이 성립
  • 덧셈에 대한 결합법칙 성립
  • 덧셈에 대한 교환법칙 성립
  • 덧셈에 대해 항등원과 역원이 존재
  • 곱셈에 대해 결합법칙 성립
  • 분배법칙 성립
  • 곱셈에 대한 교환법칙 성립 
  • 곱셈에 대해 항등원 존재
  • 𝟎 아닌 원소에 대해 곱셈에 대한 역원 존재 
• 𝑍𝑝 의 경우 유리수, 실수와 같은 성질을 가지고 있음 (곱셈 교환법칙, 곱셈 항등원, 곱셈 역원) 
  • 자유로운 사칙연산 제공 (뺄셈과 나눗셈은 각각 덧셈에 대한 역연산, 곱셈에 대한 역연산으로 정의) 
  • Ring은 이러한 성질을 가지는 대수적 구조를 별도로 다루지 않음 
  • 𝑍𝑝 을 설명하기 위해서는 Ring 보다 고도화한 대수적 구조를 정의하는 것이 필요

Field (체) 정의

Field (체)
Ring (𝐹, +𝐹, ×𝐹) 가 아래를 만족하면 field라고 정의한다.
1. [×𝐹에 대한 교환법칙] 모든 𝑎, 𝑏 ∈ 𝐹 에 대해 𝑎 ×𝐹 𝑏 = 𝑏 ×𝐹 𝑎
2. [ ×𝐹 에 대한 항등원] 𝐹의 모든 원소 𝑎에 대해 𝑎 ×𝐹 1𝐹 = 1𝐹 ×𝐹 𝑎 = 𝑎 인 0𝐹 와 다른 항등원 1𝐹 ∈ 𝐹 존재
3. [×𝐹에 대한 역원] 0𝐹가 아닌 각 𝑎 ∈ 𝐹에 대해 𝑎 ×𝐹 𝑎 −1 = 1𝐹 인 역원 𝑎 −1 ∈ 𝐹 존재

 

[예시] 

• 소수 𝑝 에 대해, (𝑍𝑝, +, ×)는 field 
• 정수 𝑛 에 대해, (𝑍𝑛, +, ×)는 field가 아님 
  • 곱셈에 대한 역원 성질 불만족 
    • 곱셈에 대한 역원이 존재하지 않는 숫자 존재
    • 2 ∈ 𝑍6 에 대해, 2 ⋅ 𝑥 = 1 𝑚𝑜𝑑 6 인 𝑥 가 존재하지 않음
• 𝐹 가 field 이고, 𝐹 의 원소의 개수가 유한한 경우 
  • 소수 𝑝에 대해 𝑍𝑝 
    • 원소의 개수가 𝑝개인 유한체 
  • 유리수, 실수
    • Field 지만 유한하지는 않음 
• Field는 영인자(zero divisor)가 없다 
  • 영인자 
    • 𝑎와 𝑏 모두 0이 아니지만 𝑎 ⋅ 𝑏 = 0 이 되는 경우
    • 𝑍6은 영인자를 가짐: 2 ⋅ 3 = 6 = 0 (𝑚𝑜𝑑 6) 
• Field 의 경우 
  • 𝑎 ⋅ 𝑏 = 0 이면 𝑎 = 0 또는 𝑏 = 0