공개키 암호
공개키 암호의 설계에는 수학적으로 어려운 문제가 포함되어있다.
-
정수
소인수 분해 문제(Integer factorization problem) -
순환군
이산 대수 문제(Discrete Logarithm Problem) -
정수 래티스
최소 크기 벡터 문제(Shortest vector problem)
안전성
공격자가 해당 보안기능을 깨기 위해 필요한 계산의 어려움 정도
Kerckhoffs의 원칙
암호의 구현방법은 비밀이어서는 안되고 적군은 전혀 불편함없이 암호를 구현할 수 있어야한다
공격자
- 수동적 공격자 (Passive Adversary) : 비밀 암호키를 소유한 객체와 상호작용이 불가능한 상태에서 공격한다. (ex 도청)
- 능동적 공격자 (Active Adversary) : 비밀 암호키를 소유한 객체와 상호작용이 가능한 상태에서 공격한다.
=> 안전성 = (보안목표, 공격자모델)쌍으로 정의된다.
쉬운 문제, 어려운 문제
계산량 = 비트 연산량, 최대 메모리 크기를 입력의 비트크기 함수로 나타낸다
쉬운 함수 : 상수, 로그, 다항
어려운계산은 big-Ω 기호를 이용하여 알려진 계산 방법들의 계산량함수의 하한이 준지수함수 또는 지수함수 밖에 없는 경우를 말한다.
Definition 1.4.2. 입력값의 비트크기가 n이라고 할때, 알고리즘의 계산복잡 도가 O(poly(n))인 경우, 이 알고리즘을 효율적인 알고리즘이라고 한다. 어떤 문제P에 대해 이 문제를 풀 수 있는 효율적인 알고리즘이 존재하면 이 문제 P 는 쉬운문제(feasible problem)라고한다. 만일 효율적인 알고리즘이 존재하지 않으면 이 문제 P는 어려운문제(infeasible problem)라고 한다.
안전도 변수(Security parameter)
암호기술의 안전성과 효율성을 논하기 위해서는 계산량 함수에서 공통적으로 사용할 계산량 함수의 변수 설정이 필요하다.
그것을 안전도 변수(λ)라고 한다
Definition 1.4.3. 암호기술이 λ bit 안전도를 가진다는 것은 해당 암호기술을 깨는데 필요한 알려진 계산량은 Ω(2λ) 이라는 것을 의미한다.
=> 2^λ번의 비트 연산의 수행은 해당 암호기술의 보안기능이 유지되어야하는 기간안에는 불가능하다는 것을 의미한다.
공개키 암호의 효율성
KeyGen : 암호키쌍을 생성하는 알고리즘
여기에 안전도 변수 λ에 대응되는 키의 크기와 키를 생성하는 환경 설정.(모든 사용자가 같이 사용하는 값이기 때문에 시스템 파라미터, 직접적인 변수로 볼 수 있다)
개인별 키 쌍을 생성하는 과정도 포함
- 효율성 분석은 어떻게?
setup 알고리즘 : λ에 대응되는 키의 크기 혹은 키를 생성하는 환경 변수 pp를 생성하는 알고리즘. 환경변수 pp의 비트크기는 poly(λ)로 나타나야함.
이외 알고리즘 : pp에서 크기가 가장 큰 변수의 함수로 나타낸다.=> 각 구성 알고리즘의 계산량이 λ의 다항함수로 나타낼 수 있으면 됨 => 각 알고리즘이 입력값의 크기에 대해 다항함수로 나타낼 수 있으면 된다
공개키 암호의 안전성 증명(PKC)
키에 대한 안전성은 보통 수학적으로 어려운문제와 동치이거나 새로운 어려운 계산문제를 제시하게된다
기법에 대한 안전성은 proof by reduction 증명방법을 이용한다.
- P: 해당 공개키암호기법의 안전성을 깨는 문제
- P′:이미 어렵다고 검증되거나 어려운 새 계산문제,
예를들어 키의 안전성의 근거가 되는 문제 또는 어려운 새로운 문제 - 문제 P′로 부터 문제 P으로의 reduction이 존재: 즉, 문제 P′의 임의의 instance P′(x)를 문제 P의 하나의 instance P(x)로 쉽게 변환(polynomial reduce)시킬 수 있고, 문제 P (x)의 해로부터 원래문제 P ′ (x)의 해를 쉽게 구하는 방법을 제시
