2. Math of crptography (1)

암호학에서 수학은 기본적으로 정수 혹은 이산적인 데이터만 사용한다.

왜냐하면, 기본적으로 암호화와 복호화 혹은 역의 (변환) 과정에서 정보 손실이 발생하면 안된다.

컴퓨터상에서 실수가 올바르게 표현되지 않으므로, 암호학에서 대부분의 경우에는 정수기반의 수학만을 사용한다.

---

Integer Arithmetic

정수 z = {..., -2, -1, 0, 1, 2, ...}

+, -, *, /

a/n ?

a = qn + r 

quotient : 몫

remainder : 나머지

암호학에서의 규약

암호학에서 대부분의 n은 양의 정수를 의미한다.

또한, r값은 항상 0이상의 정수로 취급한다.

a=-255 n=11

a/n?

-255=-23*11+(-2) (x)

-255 = -24 *11+9 

q = 11

r =9

---

Divisor

a=qn꼴일때 즉, r=0일때

↔ n divides a

↔ n | a

ex) 4 | 32

4가 32를 나눈다.

8 ∤ 42 (약수가 아니다 not a divisor)

약수 | 관련 성질

If, a|1, then a=±1

If, a|b and b|a, then a=±b

If, a|b and b|c, then a|c

If, a|b and a|c, then a|mb +nc for any integer m,n

(Fact) 

1. 1 has only one divisor(약수)

2. Any positive integer has at least two divisors ( 1과 자기 자신 )

---

common divisor 공약수

Greatest Common Divisor (GCD) 최대공약수

암호학에서는 소수가 중요한 역할을 많이 하다. 소수와 직간접적으로 연관이 많은 GCD 역시 매우 중요하다.

gcd(a,b)의 성질

1. gcd(a,0)=a for a>0
2. gcd(a,b)=gcd(b,a%b)=gcd(a-b,b) for a ≥ b >0

  2번에 뒤에 두 term이 비슷한 개념이다. 직관적으로 a%b는 a에서 b를 뺄 수 있을 만큼 빼서 b에 대한 공약수를 구하는것이므로, a에서 b를 빼는 과정을 반복하다보면, 결국 gcd(a-b,b)가 gcd(a%b,b)와 같은 꼴로 이어진다. 

---

2에 대한 증명

a와 b의 공약수들의 집합을 기반으로 유도한다. 

 위의 각 집합이 동치임을 보여야한다.

 왼쪽의 집합을 A 오른쪽 집합을 B라고 하면, A⊆B이고, B⊆A임을 보이면 집합의 성질상 두 집합이 동치 관계 임이 증명된다.

 이를 조금 더 구체화해서, A에 임의의(For every) 원소 d가 B에 포함됨을 보이면 된다.

1. d : a와 b의 공약수

a = dx, b = dy for integer x, y

a = qb + a%b

a%b = a - qb

        = dx - qdy

        = d(x - qy)

따라서, d가 a%b의 약수이다. (x-qy가 정수이므로)

∴ d는 b와 a%b의 공약수

2. e : b와 a%b의 공약수

b=ex, a%b=ey for integer x, y

a = qb + a%b

   = qex + ey

   = e(qx + y)

∴ e는 a와 b의 공약수

∴ a와 b의 공약수의 집합이 b와 a%b의 공약수들의 집합과 동치관계 이므로, 각각의 최대 공약수 역시 동일하다.

---

*gcd(a, b) = gcd(a-b,b)에 대한 증명

gcd(a,b)=G라고 하자.

a=Gn

b=Gm

a-b = Gn - Gm

a-b = G(n-m)

G는 a-b의 약수이다.

∴ gcd(a,b) = gcd(a-b,b)

---

Euclidean Algorithm

iteration 기반

a, b a≥b>0

r₁ <- a; r₂ <- b;

while( r₂>0)

    q <- r₁ / r₂;

    r <- r₁ - q*r₂;

    r₁ <- r₂ ;

    r₂ <- r;

gcd <- r₁;

recursive 기반

euclid(a,b)

    if(b=0) return a;

    return euclid(b,a%b);

함수콜 때문에 iteration이 실질적으로 더 빠르다

Ex) a =2740, b = 1760

iteration 방식의 도식화

q	r₁	r₂	r
1	2740	1760	980
1	1760	980	780
1	980	780	200
3	780	200	180
1	200	180	20
9	180	20	0
	20	0

r₂가 0이 될때 stop하면, r1에 gcd가 담겨있게 된다.

*a<b인 경우에 대해서는?

r₁=a

r₂=b

q=0

r=a

r₁=b

r₂=a

한 스탭만 더 돌리면 a>b가 되므로 전처리를 안해줘도 되긴 하지만, 불필요한 작업이 한번 더 수행되는것 이므로, a<b가 있으면 사전에 a>b가 되게 끔 swap 처리해주는게 바람직하다.