[Cryptography] About Mathematics in Cryptography

• 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 암호화 과정에서 중요한 역할을 하며 공개키와 개인키의 생성 및 복호화 과정에서 오일러의 정리를 사용하여 암호화 및 복호화 연산이 수행됩니다.

φ⒩

Z_n 에 속하고 n 보다 작으면서 n 과 서로소인 정수의 개수

φ⒩ 특징

• φ(1) = 0
• p가 소수일 경우 ⮕  φ(p) = p-1
• p가 소수일 경우 ⮕  φ(pᵉ) = pᵉ - pᵉ⁻¹
• m과 n이 서로수일 경우   ⮕ φ(m * n) = φ(m) * φ(n)

φ⒩ 오일러의 정리

• a과 n이 서로수일 경우   ⮕ $a^{φ(n)} = 1  mod  n$
• a < n이고 k가 정수일 경우   ⮕ $a^{k × φ(n)+1} = a  mod  n$

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을이용해 $P^e mod n$을 계산

RSA_Encryption (P, e, n) {
	C = Fast_Exponentiation(P, e, n)
    retrun C
}

• Decryption (복호화) : CipherText(C)와 비공개키 d, n을이용해 $C^d mod n$을 계산

RSA_Decryption (C, d, n) {
	P = Fast_Exponentiation(C, d, n)
    retrun P
}

Fast_Exponentiation

$y= a^x mod n$을 계산하는 계산 시간을 단축하기 위해 Square and Multiply 개념을 이용해서 계산하는 방법입니다.

$y= a^9 = a^{1001_2} = a^8 × 1 × 1 × a$

위와 같은 식을 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
}