2021-09-06-현대암호학-2주차.md

2. Mathmatics of Cryptography

Greatest Common Divisor

• Definition. 정수 $𝑎$와 $𝑏(\neq0)$에 대하여 아래 조건을 만족하는 정수인 몫(quotient) $𝑞$와 나머지(remainder) $𝑟$이 존재한다.

  $𝑎=𝑏𝑞+𝑟 (0≤𝑟<𝑏)$

  • 나머지 $𝑟$이 $0$일 때 𝑏가 𝑎를 나눈다라고 하며 $𝑏$는 $𝑎$의 약수(divisor)라고 한다
  • 정수 $𝑎$와 $𝑏$를 모두 나누는 정수를 $𝑎$와 $𝑏$의 공약수(common divisor)라고 한다
  • 공약수 중 가장 큰 정수를 최대공약수(greatest common divisor)라고 한다
  • $𝑎$와 $𝑏$의 최대공약수를 $\gcd(a,b)$로 표기하고, 최대공약수가 $1$일 때 $𝑎$와 $𝑏$는 서로소(relatively prime)라고 한다.

The Euclidean Algorithm

• Definition. $\gcd(a,0) = a$.
• Theorem. 정수 $𝑎$와 $𝑏(<𝑎)$가 $𝑎=𝑞𝑏+𝑟$를 만족하면

  $\gcd (𝑎,𝑏) =\gcd (𝑏,𝑟)$

  • 유클리드 알고리즘을 활용한 효율적 $\gcd(a,b)$ 계산
    

The Extended Euclidean Algorithm

• Theorem. 양의 정수 $𝑎$와 $𝑏$에 대하여 다음 식을 만족하는 정수 $𝑥$와 $𝑦$가 존재한다.

  $\gcd(a, b) = ax + by$

  • 확장 유클리드 알고리즘을 이용하여 최대공약수를 두 정수의 선형 결합(Linear Combination)으로 나타낼 수 있음.
    

Modular Arithmetic

• Definition. 정수 $𝑎$를 양의 정수 $𝑛$으로 나누어서 나머지 $𝑟(0≤𝑟<𝑛)$을 얻었을 때, 다음과 같은 연산으로 표현할 수 있다.

  $𝑎\mod𝑛 ≡ 𝑟$

  • 연산자 mod를 모듈라 연산자(modular operator)라고 한다.
  • 양의 정수 $𝑛$을 모듈러스(modulus) 또는 법(法)이라고 한다.
• Definition. 양의 정수 $𝑛$과 두 정수 $𝑎$, $𝑏$에 대하여 $𝑎\mod𝑛≡ 𝑏\mod𝑛$을 만족하면 모듈라 n에 대하여 a와 b는 합동(congruence)이다라고 하고 다음과 같이 표현한다.

  $𝑎 ≡ 𝑏 \pmod 𝑛$

  • $𝑎$와 $𝑏$가 합동이면 두 정수는 $𝑛$으로 나누었을 때 나머지가 같다고 할 수 있다.
  • 다시말해 $𝑎−𝑏$가 $𝑛$으로 나누어진다.
• Theorem. 모듈라 연산은 다음과 같은 특성을 갖는다.
  1. $(𝑎+𝑏) \mod𝑛 = [(𝑎\mod𝑛) + (𝑏\mod𝑛)] \mod𝑛$
  2. $(𝑎-𝑏) \mod𝑛 = [(𝑎\mod𝑛) - (𝑏\mod𝑛)] \mod𝑛$
  3. $(𝑎\times𝑏) \mod𝑛 = [(𝑎\mod𝑛) \times (𝑏\mod𝑛)] \mod𝑛$
• Remark. 모듈러 연산 $\mod 2$를 이용하면 암호학에서 가장 많이 사용되는
  $XOR(\oplus)$ 논리 연산을 표현할 수 있다.
  - $XOR(⊕)$연산: 2개의 입력 비트가 같으면 $0$, 다르면 $1$을 출력
  
  

Residue Systems

• Definition. $𝑛(≥ 1)$개의 원소를 가지는 어떤 정수 집합의 원소들을 $𝑛$으로 나눴을 때 모든 나머지들을 얻을 수 있다면, 이 집합을 모듈러스 $𝑛$에 대한 완전 잉여계(complete residue system)라고 한다.
• 정수 집합을 $\mathbb Z = \{...,−2,−1,0,1,2,... \}$라고 표기할 때,
  모듈라 연산은 완전 잉여계 $\mathbb Z_𝑛 = \{0,1,2,...,𝑛−1\}$ 을 만든다.
• Definition. 완전 잉여계 $\mathbb Z_𝑛$의 원소 중에 $𝑛$과 서로소인 원소들의 집합을 기약잉여계(reduced residue system) $\mathbb Z^∗_n$이라고 한다.

Identities & Inverses

• Definition. 완전 잉여계 $\mathbb Z_𝑛$에서 항등원(identity) $𝑒 ∈ \mathbb Z_𝑛$은 모든 원소 $𝑎 ∈ \mathbb Z_𝑛$에 대하여 다음과 같은 성질을 만족한다.
  • $(\mathbb Z_𝑛,+): 𝑎+𝑒≡𝑒+𝑎≡𝑎\pmod𝑛$ 덧셈 대한 항등원
  • $(\mathbb Z_𝑛,×): 𝑎×𝑒≡𝑒×𝑎≡𝑎\pmod𝑛$ 곱셈에 대한 항등원
  • $\mathbb Z_𝑛$에서 덧셈에 대한 항등원은 $0$, 곱셈에 대한 항등원은 $1$이다.
• Definition. 완전 잉여계 $\mathbb Z_𝑛$에서 원소 $𝑎 ∈ \mathbb Z_𝑛$ 에 대한 역원(inverse) $𝒃 ∈ \mathbb Z_𝒏$은 다음과 같은 성질을 만족한다.
  • $(\mathbb Z_𝑛,+): 𝑎+𝑏≡𝑏+𝑎≡𝑒 \pmod𝑛$ 덧셈에 대한 역원
  • $(\mathbb Z_𝑛,×): 𝑎×𝑏≡𝑏×𝑎≡𝑒\pmod 𝑛$ 곱셈에 대한 역원
  • 일반적으로 덧셈에 대한 역원은 $−𝑎$, 곱셈에 대한 역원은 $𝑎^{−1}$으로 표기한다.
• Theorem. $(\mathbb Z_𝑛,×)$상에서 원소 $𝑎 ∈ \mathbb Z_𝑛$의 곱셈에 대한 역원이 존재하기 위한 필요충분조건은 $\gcd(𝑎, 𝑛)= 1$이다.
  • $\gcd(𝑛,𝑎) =1$이라면 $𝑎^{−1}$을 다음과 같이 찾을 수 있다.
    • 확장 유클리드 알고리즘을 사용하여 $𝑛𝑥+𝑎𝑦=1$인 정수 $𝑥$, $y$를 구할 수 있다.
    • $(𝑛𝑥+𝑎𝑦) \mod𝑛≡1\mod𝑛$
    • $𝑎𝑦 ≡ 1 \pmod𝑛$
  • $∴𝑎^{−1} ≡𝑦\pmod𝑛$