- Published on
About Mathematics in Cryptography
- Authors
- Name
- 이민기
- Github
- @mingi3442
- Trapdoor
- One-Way Function
- Euler's theorem
- φ⒩
- Euclidean algorithm
- Euclidean algorithm (유클리드 알고리즘)
- 𖤐 Extended Euclidean algorithm (확장 유클리드 알고리즘)
- 암호화와 복호화
- Fast_Exponentiation
Trapdoor
Trapdoor 함수는 쉽게 계산되지만, 특정한 비밀 정보(Trapdoor) 없이는 역산하기 어려운 함수입니다. 비대칭키 암호화에서 공개키로 데이터를 암호화할 수 있지만, 개인키 없이는 복호화할 수 없는 구조를 제공합니다. 이는 공개키 암호화 시스템의 기본적인 구조로, 데이터 보안과 키 관리에 핵심적인 역할을 합니다.
Trapdoor가 주어지면
f⁻¹(y)
를 이용해x
를 구할 수 있습니다.
k * k' = 1 mod n 이고, k 를 알 수 있다면 x = yᵏ mod n 을 이용해 x 를 구할 수 있습니다.
⤷ k : 공개 키
⤷ k' : 비공개 키
One-Way Function
One-way function은 계산은 쉽지만 역산이 극도로 어려운 함수이며, 대표적인 예시로 해시함수가 있습니다.
비대칭키 암호화에서 이러한 함수들은 공개키로 암호화가 가능하게 하며, 오직 해당 개인키를 가진 사용자만이 데이터를 복호화할 수 있도록 합니다. 이는 보안성이 높은 통신과 데이터 전송에 필수적인 역할을 합니다.
x가 주어질 경우 f(x) 의 계산은 쉽지만, y 가 주어지더라도 f⁻¹(y) 를 통해 x를 계산하는건 어렵습니다.
y = xᵏ mod n
만약 n > x 이고 x 와 k 가 주어진다면 계산이 쉽지만,y, n, k 를 이용하여 x 를 계산하는 것은 어렵습니다.
Euler's theorem
RSA 암호화 과정에서 중요한 역할을 하며 공개키와 개인키의 생성 및 복호화 과정에서 오일러의 정리를 사용하여 암호화 및 복호화 연산이 수행됩니다.
φ⒩
Zn 에 속하고 n
보다 작으면서 n
과 서로소인 정수의 개수
φ⒩ 특징
φ(1)
=0
p
가 소수일 경우 ⮕φ(p)
=p-1
p
가 소수일 경우 ⮕φ(pᵉ)
=pᵉ
-pᵉ⁻¹
m
과n
이 서로수일 경우 ⮕φ(m * n)
=φ(m)
*φ(n)
φ⒩ 오일러의 정리
a
과n
이 서로수일 경우 ⮕a < n
이고k
가 정수일 경우 ⮕
Euclidean algorithm
두 양의 정수, 혹은 두 다항식의 최대 공약수(GCD)를 구하는 알고리즘으로 비 대칭키 암호화에서는 키 생성 과정에 중요한 역할을 합니다. 특히 RSA 암호화에서는 두 큰 소수를 선택하고, 그 곱으로 구성된 모듈러스에서 공개키와 개인키를 생성할 때 이 알고리즘이 사용됩니다.
Euclidean algorithm (유클리드 알고리즘)
두 수를 받아 나머지연산을 하여 최대 공약수를 구하는 알고리즘으로 golang
을 이용하여 구현하면 다음과 같습니다.
func main() {
var a, b int
reader := bufio.NewReader(os.Stdin)
fmt.Fscanf(reader, "%d %d", &a, &b) // a,b를 입력 받는다
if a < b {
a, b = b, a // 나머지 연산을 하기 위해 b가 a보다 클 경우 자리를 바꿔준다
}
gcd := 0 // 최대공약수 선언
for {
r := a % b
if r == 0 {
//나머지 연산 값이 0일 경우 최대 공약수 값은 0이 되며 반복문은 종료
gcd = b
break
}
// 나머지 연산 값이 0이 아닐 경우 a에는 b를, b에는 나머지 연산 값을 선언해서 반복
a = b
b = r
}
fmt.Println(gcd)
}
𖤐 Extended Euclidean algorithm (확장 유클리드 알고리즘)
RSA에서 Private Key를 구하기 위해 사용하며 golang
을 이용하여 구현하면 다음과 같습니다.
func main() {
var a, b int
reader := bufio.NewReader(os.Stdin)
fmt.Fscanf(reader, "%d %d", &a, &b)
r1 := a
r2 := b
t1 := 0
t2 := 1
for r2 > 0 {
q := r1 / r2
r := r1 - q*r2
r1, r2 = r2, r
t := t1 - q*t2
t1, t2 = t2, t
r = a % b
if r1 != 1 {
// if r1 != 1일 경우 a, b가 최대공약수가 1이 아니므로, b의 inverse는 존재하지 않는다
fmt.Println(0)
}
if t1 < 0 {
// 만약 t1이 음수가 되면 "t1 % n" 또는 t1을 더해주어서 해결한다
t1 = a + t1
}
}
fmt.Println(t1)
}
암호화와 복호화
- Encryption (암호화) : PlainText(P)와 공개키 e, n을이용해 을 계산
RSA_Encryption (P, e, n) {
C = Fast_Exponentiation(P, e, n)
retrun C
}
- Decryption (복호화) : CipherText(C)와 비공개키 d, n을이용해 을 계산
RSA_Decryption (C, d, n) {
P = Fast_Exponentiation(C, d, n)
retrun P
}
Fast_Exponentiation
을 계산하는 계산 시간을 단축하기 위해 Square and Multiply 개념을 이용해서 계산하는 방법입니다.
위와 같은 식을 golang
의 rsa
패키지를 이용하여 구현할 수 있고, 패키지 안의 코드는 아래와 같습니다.
func SquareAndMultiply(base int, exp int, modulo int) int {
res := base
// converst the number to a string of 0 and 1 in binary
bin := strconv.FormatInt(int64(exp), 2)
for e := 1; e < len(bin); e++ {
res *= res
res %= modulo
if bin[e] == '1' {
res *= base
res %= modulo
}
}
return res
}