2. Math of crpytography (3)

additive inverse 덧셈 역

multiplicative inverse 곱셈 역

n : 양의 정수

Zn = {0, 1, ... , n-1}

 Zn에서의 역원

additive inverse

a, b ∈ Zn

(a+b) mod n = 0,

a, b는 서로의 덧셈 역원

(a+b) ≡ 0 mod n

b = n-a

ex) n=10

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

Z_10 = {0,1,2, ..., 9}

multiplicative inverse

ab mod n = 1

ab ≡ 1 mod n

a, b는 서로의 곱셈역

n = 10, Z10 = {0, 1, ..., 9}

ex) 3의 곱셈 역? 

-> 3b mod 10  = 1

b = 7

1의 곱셈 역? 1

0의 곱셈 역은 undefined (정의 자체가 성립되지 않음)

9의 곱셈 역? 9

8의 곱셈 역? 없음

n = 11?

{1,2,3, ..., 10}

(1, 1), (2, 1), (3, 4), (5, 9), (7, 8), (10,10)

n이 소수이기 때문에 모든 수에 대해 존재

Integer b in Zn has a multiplicative inverse

⇔iff(if and only if 필충) gcd(n, b) = 1

증명

sa + tb = gcd( a, b ) 

if, a = n

sn + tb = gcd(n,b) = 1

sn + tb = 1

( sn + tb ) mod n = 1 mod n = 1

tb mod n = 1

t= b의 곱셈역

덧셈, 곱셈이 중요함

b에 대한 곱셈 역을 구하는게 우리의 목표

이것을 위해 하는 것이 extended euclid algorithm을 사용  (sa + tb = gcd(a,b))

---

곱셈역 구하기

extended euclid algorithm

b에 대한 곱셈역을 구하는 알고리즘 euclid와의 유일한 차이점은 s에 대한 변수가 사라짐

이외 t와 r에 대한 부분은 동일하게 유지 ( s가 필요없기 때문, s를 그대로 두고 유클리드와 똑같이 써도 상관은 없음)

Algorithm

r1 ← n , r2 ←b

t1 ← 0,  t2 ←1

while(r2>0)

    q←r1/r2

    r←r1, -q*r2

    r1←r2, r2←r

    t←t1-qt2

    t1←t2, t2←t

    if(r1 = 1) b의 곱셈의 역 ← t1

        r1 = gcd(n,b)

ex) Z26, 11의 곱셈역?

시작

q	r1	r2	r	t1	t2	t
	26	11		0	1

q	r1	r2	r	t1	t2	t (=t1-qt2)
2	26	11	4	0	1	-2

q	r1	r2	r	t1	t2	t (=t1-qt2)
2	26	11	4	0	1	-2
	11	4		1	-2

q	r1	r2	r	t1	t2	t (=t1-qt2)
2	26	11	4	0	1	-2
2	11	4	3	1	-2	5

q	r1	r2	r	t1	t2	t (=t1-qt2)
2	26	11	4	0	1	-2
2	11	4	3	1	-2	5
	4	3		-2	5

q	r1	r2	r	t1	t2	t (=t1-qt2)
2	26	11	4	0	1	-2
2	11	4	3	1	-2	5
1	4	3	-2	-2	5	-7

...

q	r1	r2	r	t1	t2	t (=t1-qt2)
2	26	11	4	0	1	-2
2	11	4	3	1	-2	5
1	4	3	-2	-2	5	-7
3	3	1	0	5	-7	26
	1	0		-7	26

Z26에서 11의 곱셈역 

t = -7 = 19 (mod취하면 같으므로)

extended euclid algorithm을 사용하면, 어떤 수에 대해 곱셈역의 유무와 존재한다면 해당 값에 대해 효율적으로 판단할 수 있게 된다.

숫자가 작을땐 상관 없지만 매우 큰 수에 대해 곱셈역을 구할 때는 브루트포스방식으로 모두 대입하는 것이아니라, 유클리드 알고리즘을 사용해야한다. 

따라서, 위의 알고리즘은 매우 중요하다.

---

Addition Table, Multiplication Table

연산의 역을 판단할때 또 다른 방식

n=10

Addition table (a+b)mod 10

+	0	1	2	3	4	5	6	7	8	9
0	0	1	2	...						9
1	1	2	3	...
2
3
4
5
6
7
8
9

Multiplication Table (a*b)mod10

*	0	1	2	3	4	5	6	7	8	9
0	1	2	3	...						9
1		1
2
3								1
4
5
6
7				1
8
9										1

Z10 = {0,1,2,3, ..., 9}

Z10^* = {1,2,3,7,9} 곱셈역이 존재하는 것들 -> 곱셈표를 그려서 판단해야함.

곱셈역이 존재하는 것들에 대한 표기법 : {Z}_{10}^{*}

n mod에 대한 덧셈역이 존재하는 것들은 Zn과 같다.

숫자에 따라 곱셈역이 달라진다

Z7={0,1,2, ..., 6)

Z7^* ={1,2,3,4,5,6}

7은 소수이므로, 모든 수에 대해 곱셈역이 존재한다.

Zp => n이 소수인경우 (소수에 대해서는 강조를 위해 n이 아닌 p로 표현한다.)

Zp = {0,1,2,... ,p-1}

Zp^* = {1, 2, ..., p-1}

Zp = Zp^* ∪ {0}