Introduction to number theory and cryptographic algo.
수론은 이러한 작업을 수행하는 데 있어 가장 유용한 주요 도구입니다. 많은 현대 암호 기법이 수론에 기반해 설계되어 있습니다.
위와 같은 서비스의 보안은 종종 (NP 클래스에 속하는) 풀기 어려운 문제들의 난이도에 의존합니다. 예를 들어, 큰 합성수의 인수분해 문제나 이산 로그 문제 등이 있습니다.
“수론과 암호 알고리즘”은 알고리즘 설계 및 분석의 틀 안에서 수론과 암호학의 계산적 측면을 연구하는 학문 분야입니다.
Number theory basics
임의의 집합 S와 이항 연산 ⊕에 대해, (S,⊕)가 군이 되려면 다음 네 조건을 만족해야 한다:
closed 폐쇄성: ∀a,b∈S, a⊕b∈S
identity element 항등원 존재: ∃e∈S s.t. e⊕a = a⊕e = a
inverse element 역원 존재: ∀a∈S, ∃b∈S s.t. a⊕b = b⊕a = e
associative law 결합법칙: ∀a,b,c∈S, (a⊕b)⊕c = a⊕(b⊕c)
예시
(ℤ,+): + (addition) operator for integers
(ℝ∖{0},×): x (multiplication) operator for real numbers except 0
Finite group: S is fininte for (S,⊕)
Commutative group or Abelian group: For ∀a,b∈S, a⊕b = b⊕a
Modulo congruence"합동" 또는 "동치"
Let a, b be integers and n be positive integer. If (a-b) is divisible by n, (i.e., n|(a-b)), a≡b (mod n) (congruency)
합동: a≡b (mod n) ⇔ n|(a−b).
Example
Since 3|(25 - 13), 25 ≡ 13 (mod 3)
25 ≡13 (mod 3) ↔ 25 mod 3 = 13 mod 3
Equivalence relation for (mod n)
Equivalence relation holds reflexity, symmetry, and transitivity
Reflexity: For all integers a, a ≡ a (mod n)
Symmetry: If a ≡ b (mod n), b ≡ a (mod n)
Transitivity: If a ≡ b (mod n) and b ≡ c (mod n), a ≡ c (mod n)
Equivalence class
The set of integers which is congruent witha mod n
[a]ₙ은 n 합동 관계에서 a 와 “동치”인 모든 정수의 모임을 의미
As congruence is in equivalence relation, find the equivalence class as follows
[a]ₙ = {a+kn | k∈Z}
[3]7={ ..., -11, -4, 3, 10, 17, ... }
ℤₙ : The set of equivalence classes for (mod n)
ℤₙ = { [0]ₙ, [1]ₙ, …, [n−1]ₙ } = {0,1, ... , n-1}
[a] ₙ + [b] ₙ = [a+b] ₙ
eg) [3]_5+[4]_5=[7]_5=[2]_5
[a] ₙ × [b] ₙ = [ab] ₙ
eg) [2]_5 x [4]_5 = [8]_5 = [3]_5
1. 집합 [Z]_5 연산 ‘+’ Z_5={0,1,2,3,4} 연산은 “모듈로 5 덧셈” 즉, a+b를 계산한 뒤 5로 나눈 나머지를 결과로 삼습니다.
2. 항등원(identity element) 항등원이란, 아무 원소 a에 더해도 a 그대로 나오는 요소를 말합니다. Z_5에서 어떤 a∈{0,1,2,3,4}에 대해 a+0 ≡ 0+a ≡ a(mod5) 가 항상 성립하므로, 항등원은 0입니다.
3. 역원(inverse element) 역원이란, 원소 a에 더했을 때 항등원(여기선 0)이 되는 요소 −a를 말합니다. 즉, a+(−a) ≡ 0(mod5). 모듈로 5 덧셈에서 −a는 일반적으로 5−a와 동치이므로, a + (5 - a) ≡ 0 (mod5).
(Z3,+)가 군(group)의 네 가지 공리(닫힘, 결합법칙, 항등원, 역원)를 모두 만족함을 보여준다.
1. It should be closed Any two arbitrary attributes in Ζ_3 and the result of + should be in Ζ_3
2. It follows associative law + operator clearly follows associative law (a + b) + c ≡ a + b + c ≡ a + (b + c) (mod 3)
3. There exists identity element For arbitrary a in Z_3, a + 0 ≡ a ≡ 0 + a (mod 3) There exists identity element 0.
4. There exists inverse element For arbitrary a in Z_3, a + (-a) ≡ 0 (mod 3) There exists inverse element of a, which is -a.
Theorem. For all positive integers, (Ζ𝑛, +) is finite and commutative group
[proof] (Ζ𝑛, +) follows associative and communtative laws. Identity element is [0]𝑛 and inverse element of [𝑎]𝑛 is [−𝑎]𝑛 𝑎𝑠 [𝑎]𝑛 + [−𝑎]𝑛 = [𝑎 + (−𝑎)]𝑛 = [0]𝑛
(Ζ𝑛,×) is not a group
Some attributes in Ζ𝑛 do not have inverse elements
ℤₙ*
The set of attributes in ℤₙ* which is coprime of n
If n is prime, ℤₙ* = ℤₙ - {0}
gcd(a,n)=1인 1≤a<n인 원소들의 집합 → 곱셈에 대한 군
Example
ℤ₉*={1,2,4,5,7,8}, ℤ₇*={1,2,3,4,5,6}
항등원: [1], 각 원소는 역원을 가짐
Find identity element and inverse element of all attributes for (ℤ₇*,x)
ℤ₇* = {1,2,3,4,5,6} ax1=1xa=a (mod 7)
Thus, 1 is identity element
Inverse elements
a
1
2
3
4
5
6
a의 역원
1
4
5
2
3
6
x operator table for ℤ₉*={1,2,4,5,7,8}. Based on the table, we can get the result of x and inverse element of each attribute
이 표에 의해 곱셈의 결과와 각 원소에 대한 역원을 쉽게 알 수 있다.
Identity element: 1 ( ∵ a x 1 ≡ 1 x a ≡ a (mod 9) )
Inverse element: a x ? ≡ 1 (mod 9)
Inverse element for (ℤ₉*,x) are {1,5,7,2,4,8}
표에서 “어떤 행 a에서 1이 나타나는 열”을 보면 그 열의 헤더가 a의 역원임을 알 수 있다.
Theorem. Leg gcd(a,b) be the greatest common divisor of a and b. If d|a,b and d=ax+by for some integers x,y, hen d=gcd(a,b).
정수 a,b에 대해 d가 a와 b의 공약수(d|a,b)이고, 정수 x,y가 존재하여 d=ax+by를 만족한다면, 그 d는 gcd(a,b)이다.
[proof] Since d|a and d|b, d ≤ gcd(a,b). Also, Since gcd(a,b)|a and gcd(a,b)|b, gcd(a,b)|ax+by (=d). gcd(a,b) ≤ d Therefore, d = gcd(a,b)
Example. For a=13,b=4, 1=13x1+4x(-3) so gcd(13,4) = 1 (13,4 are coprime)
2. It follows associative law (axb)xc ≡ axbxc ≡ ax(bxc) (mod 10)
3. There exists identity element ax1 ≡ a ≡ 1xa (mod 10). So, identity element is 1.
4. There exists inverse element As Z10* is the set of coprimes of 10 (i.e., gcd(a,10)=1), therefore, the inverse element of each attribute in Z10* should exist.
Z10*는 10과 서로소인 원소들의 집합(즉, gcd(a,10)=1)이므로, Z10∗의 각 원소는 곱셈 역원이 존재해야 합니다.
The number of attributes in ℤₙ* is called Euler phi function φ(n)
The product will be applied to all primes which can divide n
