[암호학] 2장 정리(2). 모듈로 연산과 일변수 선형 방정식

잉여집합(set of residues)

: 모듈로 연산 즉, a mod n의 결과값은 항상 0과 n-1사이의 정수이다.

--> 정수에서의 연산을 항상 닫혀있는 연산으로 할 수 있다.

 

잉여류(Residue Classes)

: 모듈로 n에 함동인 정수들의 집합

---

키 공간

덧셈암호의 키 공간

Zn=0~n-1의 연속된 정수

Z5={0, 1, 2, 3, 4}

곱셈암호의 키 공간

Zn*: n의 약수를 약수로 가지고 있지 않은 수들

ex) Z26*를 구해보자. 

1. 26의 약수는 2와 13

2. 1~n-1까지의 수 중 2와 13을 약수로 가지는 수를 뺀다.

3.  Z26*={1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25}

 

일반적으로 암호는 모듈러가 소수인 Zp와 Zp*를 사용한다. p는 prime number(소수)

---

덧셈에 대한 역원

모듈러 연산에서, 모든 정수는 덧셈에 대한 역원을 갖는다.

Z10에서 모든 덧셈에 대한 역원 쌍은?

(0, 0), (1, 9), (2, 8), (3, 7), (4, 6), (5, 5)

곱셈에 대한 역원

모듈러 연산에서, 곱셈에 대한 역원이 있을 수도 있고 없을 수도 있다.

Z10에서 8의 곱셈에 대한 역원은?

gcd(10, 8)=2(1이 아님)므로 8의 곱셈에 대한 역원은 존재하지 않는다.

 

만약 gcd(n, b)=1로 역원이 존재한다면,

 

1. 직접 찾아볼 수 있다.

Q. Z_11에서 3에 대한 곱셈의 역원을 찾아라.

 A. Z_11에서는 1=12=23=34=45=... 이 중에 12는 3의 배수이다. 따라서 12/3=4로 4가 3의 곱셈에 대한 역원이다.

 

2. 유클리드 확장 알고리즘으로 Zn에서 b의 곱셈에 대한 역원을 찾을 수 있다.

Z100에서 23의 역원을 찾아보았다. 

t의 마지막 값인 -13(=(-13)+100=87)이 23의 역원이라는 것을 구할 수 있다.

실제로 계산을 해보면, 23*87=2001로 2001mod100=1를 확인할 수 있다.

 

Zn*는 모든 수가 곱셈의 역원을 가지고 있다.

왜냐하면 애초에 원소들과 n의 최대공약수가 1이기 때문이다.

---

일변수 성형 방정식 

1. gcd(a, n)=d라고 할 때, d가 b로 나누면 x라는 해가 존재한다.

ex)

gcd(10, 15)=5이고, 5가 2로 나누어 떨어지지 않기 때문에 해가 존재하지 않는다.

 

2. 해가 존재할 때의 계산 방법

이 떄 7^(-1)mod 9 는 mod 9에서의 7의 역원을 나타낸다.

4*7=28, 28mod9=1이므로 7^(-1)mod 9 는 4mod 9이다.