Newbie Cryptography Cheatsheet (작업 중)

$$
\newcommand{\Mod}[1]{\ (\mathrm{mod}\ #1)}
$$

Intro

CTF 도중에 꺼내서 보고 싶은 내용들이 적혀있는 치트시트가 있었으면 좋겠다고 생각했는데, 크립토를 접었음에도 쓰면서 공부하면 괜찮을 것 같아서 매우 바쁜 와중에도 짬짬히 적고 있다. 내 생각엔 그냥 rkm0959 블로그를 열심히 베끼고 있는 것 같다 ㅋㅋ(본인이시라면 뒤로 가기를 눌러 주세요). 이 내용을 실제 공부용이나 CTF용으로 사용하는 것을 강력히 추천하지 않는다.

RSA

Introduction

• 크기가 비슷한 큰 소수 $p, q$가 있을 때, $N=pq$라 하자. 이때 공개된 $e$에 대해 $ed \equiv 1 \Mod{\phi(N)}$인 $d$가 존재하도록 하면 오일러 정리에 의거하여 $C \equiv M^e \Mod{N}$로 암호화 할 수 있고, $M \equiv C ^ e \Mod{N}$으로 복호화할 수 있다.
• 가장 기초적인 공격은 $N$을 실제로 소인수분해하는 것이다. 이는 $d$나 $\phi(N)$을 찾는 것과 동치이다. 소인수분해는 어려운 문제이지만, 특수한 경우에 빠르게 소인수분해할 수 있다.
  • $p-1$이나 $p+1$이 작은 소수들의 곱으로 나타나는 경우(Pollard, Williams).
  • $p$와 $q$의 차가 작은 경우. (Fermat's Factorization)
• $d$를 안다면 $N$의 인수분해 또한 쉽게 계산할 수 있다.
  • $k=ed-1$이라고 두면 이 값은 $\phi(N)$의 배수이고, $\phi(N)$이 짝수이므로 $k$도 짝수.
  • $k=2^tr$이고 $r$이 홀수라고 가정하자. 이 때 다음 과정을 수행한다.
  • $N$의 배수가 아닌 $g$를 하나 무작위로 잡고, $gcd(g, N) = 1$임을 확인한다. 아니라면 자명하게 소인수분해된다. 그 후 $0 \le i \le t$에 대해 $s_i = g^{k/2^i} \Mod{N}$ 이라 하고 $s_{i-1} \equiv s_i^2 \equiv 1 \Mod{N}$이면서 $s_i \not\equiv \pm 1 \Mod{N}$인 $i$를 찾자. 성공할 때까지 계속 반복하자. 이때 $\gcd{s_i - 1 , N}$은 $N$의 nontrivial factor이다.

Small Message

• 메세지 자체가 크기가 작으면 문제가 생길 수 있다. 이를 해결하기 위한 방법으로 패딩(Padding)이 있다.
• 가장 간단하게, $m^e$가 $N$보다 작거나 약간 큰 경우를 생각해볼 수 있다. 따라서 $C = m^e + kN$ 꼴임을 가정할 수 있는 경우 $O(\max(k))$에 공격할 수 있다.

Low Private Exponent (d)

• Wiener's Attack : $N=pq$고, $q<p<2q$일 때 $d<\frac{1}{3}N^{1/4}$면 $ed \equiv 1 \Mod{\phi(N)}$인 $N$과 $e < \phi(N)$이 주어졌을 때 $d$를 효율적으로 복원가능하다.
  • Wiener's Attack을 쓰면 안 된다! 실제로는 더 강력한 Bound를 제공해 주는 Boneh-durfee 공격을 사용해야 한다. Boneh-durfee 공격은 $d < N ^ {0.292}$까지 커버할 수 있다. 이 링크를 수정하여 사용할 수 있다.
  • Owiener 라이브러리를 활용할 수 있다. Boneh-durfee 공격을 지원하는지는 확인해보지 못했다.
• 일반적으로 $d$가 작은 상황이라면 Boneh-durfee 공격을 단순하게 사용하기만 하면 되나, $d$가 작은 경우는 자주 출제되지 않는다. 일반적으로 $e$가 비정상적으로 큰 상황이라면 $d$가 매우 작음을 의심해볼 수 있다.

Low Public Exponent (e)

• $e$만 작다고 문제를 해결할 수 있는 것은 아니다. $d$가 작은 경우와 달리, $e$가 작을 때는 추가적인 정보들이 더 필요하다.

• 통상적으로 사용되는 $e$ 값은 0x10001이며, 가장 작은 값은 $e=3$이다. 일반적으로 $e=3$이라면 아래 서술한 내용들을 한번쯤 의심해보는 것이 좋다. 그러나, $e$가 작은 것이 풀이를 보장해주지는 않는다.

• Hastad's Broadcast Attack: 완전히 같은 메세지를 서로 다른 $N$과 $e$ 쌍으로 암호화했다면, 이 공격을 통해 해결할 수 있다. $e=3$일 때 세 쌍이 필요하며, $e$가 증가하면 더 많은 쌍을 확보해야 한다. 구현체는 간단하게 구글링해서 찾을 수 있다.

• Franklin-Reiter Related Message Attack: $M_1 \equiv f(M_2) \Mod{N}$인 경우, $C_1 \equiv M_1^e \Mod{N}$과 $C_2 \equiv M_2^e \Mod{N}$을 계산했다면 $C_1$과 $C_2$를 알 때 $M_1$과 $M_2$를 복원할 수 있다.

• Coppersmith's Short Pad Attack: 메시지 $M$ 뒤에 적은 수의 random bit $R$을 추가해 $M' = M || R$으로 패딩했다고 가정해 보자. 이 때 두 개의 Ciphertext를 확보한다면 $M$을 복원할 수 있다.

• Coppersmith: $p$의 $n/4$ prefix/suffix bits를 알면 소인수분해할 수 있다.

• Boneh, Durfee, Frank's Partial Key Exposure Attack: $d$의 $n/4$ least significant bits를 알면 $d$ 전체를 $O(e \lg e)$로 복원할 수 있다.

Miscs

• Return of Coppersmith's attack: 과거에 사용되었던 primorial을 이용한 빠른 소수 생성 방식이 존재한다. ROCA를 통해 이를 빠른 속도로 공격할 수 있다.
• Ron was wrong, Whit is right: $N$을 가장 쉽게 인수분해하는 방법은 많은 $N$이 주어졌을 때 이 중 임의의 두 $N$은 같은 소인수를 사용했을 것이라고 믿는 것이다. $\gcd(N_1, N_2)$를 통해 non-trivial factor을 빠르게 찾을 수 있다.
  • 최대공약수를 구하는 것은 굉장히 강력한 공격 방식이다. 두 다항식에 공통으로 있는 항을 추출하기 위해 최대공약수를 사용할 수 있다. 예를 들어 $q^x - q^y$꼴 식 두 개가 있을 때 이 방정식을 푸는 것은 어려울 지 몰라도 최대공약수를 구해서 $q$를 알아내는 것은 어렵지 않은 일이다.
• Blinding Attack: 전자서명과 관련된 문제가 출제되면 검색해보자. (TODO)