공개키 암호

 

공개키 암호 개념 (Public Key Cryptography)

1. 두 개의 키 사용
   • 공개키(Public Key): 누구나 사용 가능, 암호화에 사용.
   • 개인키(Private Key): 본인만 소유, 복호화에 사용.
2. 원리
   • 누구나 공개키로 데이터를 암호화할 수 있지만,개인키 없이는 해독 불가능.
   • 안전한 키 분배, 인증, 서명, 암호화에 활용.

• 목적: 안전한 키 분배, 전자 서명, 데이터 암호화 등.
• 수학적 기반: 일방향 함수(One-way Function) 이용.

---

기반 문제 (수학적으로 어려운 일방향 함수 기반)

→ 일방향 함수:
앞으로 계산은 쉽지만, 역으로 해독은 어렵다.

1. 소인수분해 문제
   • 큰 수를 두 소수의 곱으로 만들기는 쉽다.
   • 역으로 소인수분해는 매우 어렵다.
     → RSA
2. 이산대수 문제
   • a^x mod n은 쉽다.
   • 역으로 x를 찾기는 어렵다.
     → ElGamal, DSA, DHKE
3. 타원곡선 이산대수 문제
   • kP는 쉽다.
   • k를 찾기는 어렵다.
     → ECC (ECDSA, EC-DH 등)

문제 | 정의 기반 | 알고리즘 | 권장 키 길이 (보안 레벨)

소인수분해 문제 (Factorization)	큰 수를 소인수로 나누는 것은 어렵다.	RSA	2048 bits 이상
이산대수 문제 (Discrete Log)	g^x mod p 계산은 쉽지만, x 찾기는 어렵다.	ElGamal, DSA, DHKE	2048 bits 이상
타원곡선 이산대수 문제 (ECDLP)	kP 계산은 쉽지만, k 구하기는 어렵다.	ECC(ECDSA, EC-DH 등)	224 bits 이상

---

주요 알고리즘 흐름 개념

1. RSA (소인수분해 기반)

• 키 생성:
  큰 소수 두 개(p, q) → n 생성 → e, d 계산
• 암호화:
  C = M^e mod n
• 복호화:
  M = C^d mod n

2. ElGamal (이산대수 기반)

• 키 생성:
  소수 p, 생성자 g → y = g^x mod p
• 암호화:
  C1 = g^k mod p
  C2 = M * y^k mod p
• 복호화:
  M = C2 / C1^x mod p

3. ECC (타원곡선 이산대수 기반)

• 키 생성:
  타원곡선 E, 생성점 G → Q = d·G
• 암호화:
  C1 = k·G
  C2 = P + k·Q
• 복호화:
  P = C2 - d·C1

- 알고리즘 | 기반 문제 | 특징 | 키 크기 | 사용 예시

RSA	소인수분해 문제	가장 널리 사용, 느림	2048b	키 교환, 서명, 암호화
ElGamal	이산대수 문제	임의성 높은 암호화 지원	2048b	암호화, 키 교환
ECC	타원곡선 이산대수	짧은 키, 빠름, 모바일 친화적	224b	서명, 키 교환, TLS 등

---

비유를 통한 이해

• RSA → 잠긴 상자 비유
  누구나 잠글 수 있지만, 키 소유자만 열 수 있음.
• ElGamal → 비밀번호 계산기
  일방향 계산은 쉽지만, 비밀번호 찾기는 어려움.
• ECC → 타원 곡선 위의 숨바꼭질
  특정 점까지 빠르게 이동 가능하지만, 역으로 찾기는 어려움.

---

RSA 암호화/복호화 흐름도

키 생성:
1. 큰 소수 p, q 선택 → n = p * q
2. ϕ(n) = (p-1)(q-1) // 오일러 함수 계산 
3. e 선택 (GCD(e, ϕ(n)) = 1) // GCD 최대 공약수
4. d 계산 (e·d ≡ 1 mod ϕ(n))

암호화:
C = M^e mod n

복호화:
M = C^d mod n

---

ElGamal 암호화 흐름도 (유한체 이산대수 기반)

키 생성:
1. 공개 소수 p, 생성자 g 선택
2. 개인키 x 선택 → 공개키 y = g^x mod p

암호화:
1. 임시값 k 선택
2. C1 = g^k mod p
3. C2 = M * y^k mod p

복호화:
M = C2 / C1^x mod p

---

ECC 암호화 흐름도 (타원곡선 이산대수 기반)

키 생성:
1. 타원곡선 E 선택 (y^2 = x^3 + ax + b mod p)
2. 생성점 G, 개인키 d → 공개키 Q = d·G

암호화:
1. 임시값 k 선택
2. C1 = k·G
3. C2 = P + k·Q

복호화:
P = C2 - d·C1

---

타원곡선 상 덧셈/곱셈 연산 예시

P + Q:
1. 두 점을 잇는 직선 → 타원과 만나는 점 R
2. R을 x축 대칭 이동 → P + Q

2P (점 두 배):
1. 접선 → 타원과 만나는 점 R
2. R을 x축 대칭 이동 → 2P