[Cryptography] 비대칭 키 암호

Asymmetric Key (비대칭 키) 암호

비밀 키와 공개 키를 한 쌍으로 암호 키로 사용하여 암호화

활용 메커니즘

• 비밀 메시지 : A의 공개키로 암호화한 암호는 A의 비밀 키로 복호화
• 전자 서명 : A의 비밀 키로 암호화한 암호는 A가 암호화 했다고 증명 가능

𖤐 대칭 키 암호와 비대칭 키 암호의 차이

	대칭 키	비대칭 키
개념 및 키 구성 차이	같은 키를 두 사람이 공유	공개 키는 공개되어 있지만 개인의 비밀 키는 공개하지 않음
암호화 방식	C = Ek(P)	C = f(PublicKey, P)
복호화 방식	P = Dk(C)	P = g(PrivateKey, C)
알고리즘의 실행 시간	빠르다	상대적으로 느리다
활용	길이가 긴 메시지를 암호화	짧은 데이터 암호화, 전자서명, 인증 등

---

One-Way Function

단 방향 함수라고도 하며 가장 대표적인 예시로 해시함수가 있다.

• x가 주어질 경우 f(x)의 계산은 쉽지만, y가 주어지더라도 f⁻¹(y)를 통해 x를 계산하는건 어렵다

y = xᵏ mod n
만약 n>x이고 x와 k가 주어진다면 계산이 쉽다.
그러나 y, n, k을 이용하여 x를 계산하는 것은 어렵다.

---

Trapdoor

단 방향 함수이며 힌트가 주어지면 f⁻¹(y)를 이용해 x를 구할 수 있다

k * k' = 1 mod n이고, k를 알 수 있다면
x = yᵏ mod n을 이용해 x를 구할 수 있다
↪ k : 공개 키, k' : 비공개 키

---

Euler 의 φ⒩

Zn* 에 속하고 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$