암호 수학

<정수 연산(Integer Arithmetic)>
- 암호는 정수론, 선형 대수, 대수 구조를 포함한 수학의 몇몇 특정 분야에 기반을 두고 있다
- 정수 연산에서는 집합(Set)과 몇 개의 연산을 사용
- 정수 집합 Z는 음의 무한대에서 양의 무한대까지의(분수가 아닌)모든 정수
- 암호에서는 정수 집합에 적용되는 세 가지 이진 연산을 주로 사용한다
- 이진 연산(Binary operation)은 입력값 2개에 대해서 하나의 결과값을 산출한다
- 정수에 대한 세 가지 일반적인 2인 연산은 덧셈(Add), 뺄셈(Subtract), 곱셈(Multiply)
- 정수연산에서, a를 n으로 나누면, q와 r을 얻는다
  이 네 정수 사이의 관계(나눗셈 관계식, Division relation)은 다음과 같다
  -> a = q*n+r



<암호에서의 나눗셈의 두 가지 제약 사항>
- 제수(Divisor)는 양의 정수(n>0)
  *제수(Divisor) : 나누는 수
- 나머지는 음이 아닌 정수(r>=0)
- a = q*n+r
  - n : positive(양의 정수)
  - r : nonnegative(음이 아닌 정수)



<나머지 연산의 두 가지 형태>
1. Remainder operation(%) : 0 또는 피제수(Dividend)의 부호와 동일
-> a%n = (a-n*int(a/n))
ex) -9%7 = -2

2. Modulo operation(mod) : 0 또는 피제수(divisor)의 부호와 동일
-> a mod n = (a-n*floor(a/n))
ex) -9 mod 7 = 5


<가분성>
- 나눗셈 관계식에서 a가 0이 아니고, r = 0이라고 하면, 다음의 식을 얻는다
-> a = q*n
1) 만약 나머지가 0이라면 n | a
2) 만약 나머지가 0이 아니라면 n not| a

ex) 32=8*4이기 때문에 4는 32를 나누고, 다음과 같이 표현 -> 4|32
ex) 42=5*8+2이기 때문에 8은 42를 나누지 않는다 나머지 2가 존재하기 때문에 -> 8 not | 42


특성
Property 1 : 만약 a|1이라면 a= +-1
Property 2 : 만약 a|b이고 b|a 라면 a=+-b
Property 3 : 만약 a|b이고 b|c라면 a|c
Property 4 : 만약 a|b이고 a|c라면 a|(m*b+n*c)가 된다. 여기서 m과 n은 임의의 양수

 

<최대 공약수(Greatest common divisor, GCD)>
- 두 양의 정수의 최대공약수는 두 정수를 나누는 가장 큰 정수


<유클리드 알고리즘(Euclidean algorithm), 유클리드 호제법>
- Fact 1 : gcd(a,0) = a
- Fact 2 : gcd(a,b) = gcd(b,r) 여기서 r은 a를 b로 나눈 나머지 

- a = q*b+r
- 집합 E : a와 b의 공약수의 집합 r = a-q+b, 집합 F : b와 r의 공약수의 집합 a = q*b+r
- E의 모든 원소는 r을 나눈다(r의 약수),  F의 모든 원소는 a를 나눔(a의 약수)
- E는 a,b,r의 모든 공약수의 집합,  F는 a,b,r의 모든 공약수의 집합
- E = F
- gcd(a,b) = gcd(b,r)


- gcd(a,b) = 1일경우, a와 b는 서로소(Relatively prime, Coprime)




<확장 유클리드 알고리즘(Extended Euclidean Algorithm)
- 두 정수 a와 b가 주어졌을 때, 
  아래의 식을 만족하는 다른 두 정수 계산해야 할 필요가 있다
  s*a+t*b = gcd(a,b)
  확장 유클리드 알고리즘은 gcd(a,b)를 계산할 수 있을 뿐만 아니라, 동시에 s와 t값을 계산할 수 있다



<일차 디오판투스 방정식(Linear Diophantine Equation)>
- 2변수 일차 디오판투스 방정식은 ax + by = c
  s*a + t*b = gcd(a,b)
  gcd(a,b) = d라 하자
  s/d * a+t/dBb = 1
  s/d*c*a+t/d*c*b = c
-> x = c/d*s, y=c/d*t
  특수해(Particular solution) : x0 = (c/d)s와 y0=(c/d)t

  임의의 정수 k 포함 Z에 대하여
  ax + by = c
  a*{x0+k(b/d)}+b*{y0-k(a/d)} = ax0 + akb/d + by0 - bka/d
  
  일반해(General soulation) : x = x0 + k(b/d) 와 y=y0 - k(a/d) (k는 정수)