학습하기

공개키 암호

정의

일반적인 활용 방식

공개키 암호의 기반문제

개요

• 공개키 암호는 수학적으로 어려운 문제들에 기반하고 있다.
• 수학적으로 쉬운 문제는 계산시간이 짧은 문제, 어려운 문제는 계산시간이 현실적으로 풀지 못할 정도로 긴 문제를 의미
• 일방향 함수란 함수의 결괏값으로 입력값을 찾기 어려운 함수를 의미한다
• 암호학에서는 다음과 같은 일방향 함수를 활용한다
  • 소인수분해 문제 - RSA
  • 이산대수 문제
  • 타원곡선 이산대수 문제 - ECC

소인수분해 문제

정의

• 두 정수의 곱은 쉽게 구할 수 있지만, 임의의 양의정수를 소인수분해하는 것은 어렵다
• 256bit * 256bit는 쉽게 계산가능하지만
• 512bit를 소인수 분해하는 것은 8000 MIPS Year 걸린다.
• MIPS : Million Instruction Per Second

RSA

• 소인수분해 기반 대표 알고리즘
• 안전한 암호로 사용하기 위해 2048bit 키가 필요함

(정수) 이산대수 문제

정의

• 양의 정수 n, a, x에 대해서 a^x(mod n)은 빠른 시간에 구할 수 있다. 지수연산과 나머지 연산만하는 쉬운 계산이다.
• n, a, y에 대해 y = a^x(mod n)인 지수 x 값을 구하는 것은 매우 어렵다.

이산대수 기반 알고리즘

• ElGamal 알고리즘
• DSA
• Diffie-Hellman 키 교환 프로토콜
• 안전한 암호로 사용하기 위해 2048bit 키가 필요함

타원곡선 이산대수 문제

타원곡선

• 타원곡선상의 점과 타원곡선에서 정의되는 덧셈 연산을 이용하여 정의되는 이산대수 문제

타원곡산 이산대수 기반 알고리즘

• EC-DSA
• 224bit의 키로도 안전한 암호화 가능

공개키 암호의 알고리즘들

RSA

개요

• 1978년 Rivest, Shamir, Adleman이 개발
• 가장 널리 사용되는 공개키 암호
• 자리수가 비슷하지만 차가 큰 두 소수 p, q 활용

키 생성(수신자)

1. n = pq
2. ϕ(n) = (p - 1)(q - 1)과 서로소인 수 e를 임의로 선택
3. 유클리드 알고리즘을 이용하여 ed = 1(mod ϕ(n))이 되는 d를 구함
4. 공개키 = (e, n), 개인키 = (d, p, q)

암호화

• 평문 P, 공개키 e, n을 이용해서 암호문 C 생성
• C = P^e(mod n)

복호화

• 암호문 C, 개인키 d, p, q를 이용해 평문 P 계산
• P = C^d(mod n)

ECC(Elliptic Curve Cryptosystem)

• 밀러와 코블리츠가 각각 1985년에 발표

정의

• 유한체상에서 정의된 타원곡선 군에서의 이산대수 문제에 기반
• RSA, ElGamal 등과 동일한 수준의 보안성을 제공하면서 키의 길이는 224bit로 짧음
• 컴퓨터 성능과 무관하게 높은 보안성 제공
• ElGamal을 변환하여 타원곡선 암호 알고리즘 적용 가능

타원곡선

• y^2 = x^3 + ax + b로 정의되는 타원곡선상에서 덧셈 연산

• 타원곡선 위에 있는 점들만을 대상으로 연산을 고려

• 타원곡선상의 덧셈 연산은 아래와 같이 정의된다.

1. 타원곡선 군에서 임의의 두점을 정한다.
2. 두점을 잇는 선분을 연장하여 곡선과 만나는 점을 찾는다.
3. 만난 점을 x축에 대칭시켜 최종 결과를 찾는다.
4. 덧셈 연산을 반복적용할수 있다.

• 타원곡선상의 한 점을 R = kP와 같의 정의했을 때 k를 구하는 것은 수학적으로 매우 어려운 문제