지난시간에 의하면 $P = NP$인지 모르기 때문에 암호가 불완전할 수 있다고 했다.
그래서 차라리 $NP$문제를 선택하고 Bob에게 힌트를 줘서 $P$로 만드는게 나을 수 있다.
그렇다면 $NP$문제중에 어려운걸 선택하면 될 것이다.
그런 문제셋을 $NP$-Complete라고 소개를 했었다.
$NP$-Complete
Class를 시간제한으로 봤을 때 위와 같이 나온다. ($D$, $E$와 유사하다. co-$NP$는 생각하지 말자)
$NP$-Complete의 예시로 SAT가 있는데 이 문제가 핵심 역할을 할 것이다.
Reduction
Problem $A$의 입력 $a$를 $b$로 변환할 수 있다면 Problem $B$로 reduce할 수 있다.
우리가 알고리즘이나 수학문제를 풀 때 해당 문제를 변형해서 풀면 더 쉽게 풀리는 경우가 많은 것과 유사하다.
다만 transform 하는 시간이 직접 문제를 해결하는 시간보다 오래걸리면 의미가 사라질 것이다.
이 내용의 핵심은 문제를 다른 문제로 변환할 수 있다는 것이다!
SAT
SAT(Satisfiability)은 $n$개의 bool 변수가 참일 조합이 있는지 찾는 문제이다.
예를들어 $p_1 \land (p_2 \lor \lnot p_3)$라고 하면 $p_1 = T, p_2 = T, p_3 = F$가 정답중 하나가 될 것이다.
직관적으로 모든 경우를 확인하는 $O(2^n)$ 알고리즘이 있기 때문에 $EXP$에는 포함된다는 것을 알 수 있다.
https://www.acmicpc.net/problem/11281
특히 2-SAT이면 SCC로 풀 수 있지만 3-SAT만 하더라도 휴리스틱이 필요한 굉장히 어려운 문제이다.
SAT의 특징
- SAT은 $NP$에 있다.
- SAT은 $NP$-Complete임이 최초로 증명된 문제이다.
- $NP$에 있는 모든 Problem은 SAT으로 reduce할 수 있다.
핵심은 3번이다.
$NP$에 있는 모든 문제는 $NP$-Complete인 SAT으로 바뀔 수 있다는 것이다.
정말 신기한 증명이 있지만 지금은 다루지 않는다.
SAT이 $P$에 존재함을 증명한다면 이는 곧 $P = NP$임을 증명하는 것과 같아진다
SAT의 특징에 의해 $P \neq NP$라면 모든 $NP$-Complete 문제로 암호를 만들 수 있다.
요즘 암호는 그림의 위치에 있는 Problem을 사용한다. (RSA가 소인수분해를 사용한다.)
소수판정은 $P$일 수도 있다고 하는데 만약 $P$에 들어간다면 $P$-Complete가 된다고 한다.
이는 $P \neq NP$라는 것을 가정했기 때문에 아직은 믿고 사용할 수 있다.
앞으로 RSA같은 구체적인 암호화 기법을 알아볼 것이다.
'기타 > 암호학' 카테고리의 다른 글
[암호학] 20. 소수 판정 (Primality Test) (0) | 2023.02.03 |
---|---|
[암호학] 19. RSA 암호 (0) | 2023.01.31 |
[암호학] 17. P, NP (0) | 2023.01.24 |
[암호학] 16. Complexity Classes (0) | 2023.01.20 |
[암호학] 15. 암호란 무엇인가? 2 (0) | 2023.01.17 |