RSA 예습 : 군 환 체, 오일러 피함수

정수론

 

최대공약수

(4, 6) = 2

두 수의 공통 약수 중 최대

 

최소공배수

(4, 6) = 12

두 수의 공통 배수 중 최소

 

소인수분해

 320 = $ 2^{6}*5 $ 

 

오일러피함수

 

 

n과 서로소인 수의 개수

 

 

서로소란?

 

예1) 8과 15

8의 약수 : {1,2,4,8}

15의 약수 : {1,3,5,15}

공통 1만 있음. → 서로소

 

예2) 14와 25

공통 소인수 없음 → 서로소

 

예3) 12와 18

공통 약수 : {1,2,3,6} → 서로소 X

 

예4) 9와 21

공통 소인수 : 3 → 서로소 X

 

소인수분해 관점에서 보면 다음과 같다.

$ x = p_{1}^{a}p_{2}^{b} $  $ y= q_{1}^{c}q_{2}^{d} $ 

$ p_{i} \cap q_{i} = \phi  $  → 서로소

즉 공통 소인수가 하나도 없음.

 

 

군환체

군 Group

(Z, +, 0)

집합 Z가 연산 +에 abelian group이 성립하기 위한 족

1. Z 정수군에서 닫힘
2. 연산+에 대해 결합, 교환법칙이 성립
3. 항등원, 역원이 모두 존재.

일 때 이를 abelian group이라고 한다.

환 Ring

(Z, +, x, 0, 1)

1. Z 정수군에서
2. 연산 + 는 군 성립
3. 연산 x 는 결합법칙 성립. 군은 성립하지 않음.
4. 연산 +의 항등원
5. 연산 x의 항등원

체 Field

(R, +, x, 0, 1)

1. R 실수군에서
2. 군을 성립하는 연산1
3. 군을 성립하는 연산2
4. 연산1의 항등원
5. 연산2의 항등원

 

 

$ Z_{n} = n$ 으로 나눈 나머지. n은 소수.

(소수가 아닌 경우에는 x. $ \because $0인 케이스가 많아져서 데이터를 잃게 됨)

예1) $ Z_{5} $  = {0,1,2,3,4}

 2+ 4  $ \equiv 1 $  (mod 5)

3 x 2 $  \equiv 1 $ (mod 5)

예2) $ Z_{6}$ 

2 x 3  $ \equiv 0 $ (mod 6)

→ 이러면 x

3 x 0 $ \equiv 0 $ (mod6) 처럼 x 0일때만 0이어야 함.

 

 

 

RSA는 “체가 아닌 환 위에서 정의된 곱셈 군”에서,
소인수분해의 어려움을 이용해
오일러 피함수 기반의 역원 계산을 숨기는 암호 시스템이다.

 

---

https://tinyarchive.tistory.com/5

군 (Group), 환 (Ring), 체 (Field)

 

https://m.blog.naver.com/yyhjin12/222864062441

오일러 피 함수(Euler's phi function)