picoCTF2017のweirderRSAの解説

https://www.gulshansingh.com/posts/pico-ctf-2017-weirderrsa-writeup/
https://ctftime.org/writeup/6347
こちらのwriteupに書いてあるのでもう言うことはないです
そんなに飛躍なく説明されていてわかりやすいです。
この記事はその粗悪な日本語版のようなものです。

まずRSAについての知識と、それの秘密鍵を持ってる側での高速化の手段であるRSA-CRTについて知っている必要があります。
CRTとは中国人余剰定理というやつです。今回の問題では、それ自体よくは知らなくてもすみますがRSA-CRTのことは少し知ってる必要があります。

まず、ベーシックなRSAでは、秘密鍵である素数p,qと$d = 1/e \ \pmod{(p-1)*(q-1)}$、公開鍵n=p*q、 e(正整数、計算の高速化のため65537が多く使われる)、を用います。
それに加え、RSA-CRTでは$dp \equiv d \ \bmod(p-1)$, $dq \equiv d \ \bmod(q-1)$, その他いろいろを用います。
今回は詳しく触れなくてもOKです。

今回与えられたのは公開鍵であるeとn、暗号文c、それに加え秘密にしておくべきはずのdpです。
いま知っている情報から、秘密鍵である素数p, qを求めることができれば、あとは通常通りのRSAの手順に従い暗号文cを複合できます。

具体的には...。
まず、dpの定義式から、ある整数$k$で$d = dp + k*(p-1)$が成り立ちます。
dの定義式をの両辺にeを掛け、$e*d \equiv 1 \ \pmod{(p-1)*(q-1)}$にします。左辺の$d$に先ほどの式を代入し、$e*(dp + k*(p-1)) \equiv 1 \ \pmod{(p-1)*(q-1)}$とします。同じように、ある整数$j$で$e*dp + e*k*(p-1) = 1+j*(p-1)*(q-1)$が成り立ちます。
整理すると$e*dp  = 1+ (p-1)\{-e*k+j*(q-1)\}$、modをとると$e*dp  \equiv 1\  \bmod (p-1)$となります。

総当たりでpを求める方法

$e*dp  \equiv 1\  \bmod (p-1)$は、ある整数$i$を使うと

\begin{align} e*dp = 1+i*(p-1) \end{align}

と表せます。

dpの定義式から、dpは(p-1)でmodをとったものなので、dpは絶対に$0 \leq dp < (p-1)$を満たします。よって、$ e \geq i$だと考えられ(←直感的にはわかると思います、a*b = c*dでa$\leq$cならb>dになるっぽいことは想像できるかと)、整数$i$を0から65537(今回も与えられているし、一般的でもあるeの値。)まで総当たりすることで、さっきの式(1)を変形し、$i$でmodをとった$e*dp -1 \equiv 0 \ \bmod i$を満たす整数$i$を求めれば良いです。

$i$が求められたら、式(1)を変形した$p=(e*dp -1)/i +1$でpが求められます。

数論的にpを求める方法

pとqと互いに素で、1より大きい自然数aがあれば最大公約数,$\gcd (a * p, p * q) $、つまり$\gcd (a * p, n)$を計算することでpがわかります。$a * p$と$n (=p*q)$の最大公約数はpしかないからです。

つまり、何でもいいからpの倍数であることがわかっているものとnとの最大公約数を取ればpがわかると言うことです。

フェルマーの小定理を用います。aがpと互いに素な任意の自然数のとき、$a^\left(p-1\right) \equiv 1 \bmod p$が成り立つ、と言うものです。

このフェルマーの小定理と式(1)を用いますと、$a ^ \left( e*dp \right) \equiv a ^\left(1+i*(p-1)\right) \equiv a *( a^i )^\left(p-1\right) \equiv a \ \bmod(p)$
となります。よって、$a ^ \left( e*dp \right) - a \equiv 0 \bmod (p)$であり、めでたく
pの倍数が得られました。

aには適当に2を入れて計算すると、コンピュータでは$2 ^ \left( e*dp \right)$が大きすぎて計算ができません。nでmodをとっても$a ^ \left( e*dp \right) - a $が$p$の倍数であることは変わらないので、modを取ります。

結局、$p = \gcd(\{2 ^ \left( e*dp \right)  - 2 \}\% n, n)$でpが求められます。

(https://www.cryptologie.net/article/371/fault-attacks-on-rsas-signatures/にフツーにわかりやすく載ってますが、だいたいこんな感じで、RSA-CRT fault attackという攻撃というのがあり、秘密鍵で暗号化するときの計算でfaultがあると、その「間違って計算された暗号文から平文を引いたもの」はpかq(間違わなかった方)の倍数となっているので、nとの最大公約数をとることでpかq(間違わなかった方)が通信相手である公開鍵を使う側で計算できてしまいます。)

求めたpから復号

$ q = n/p$でqを求めます。

dを計算し、$m \equiv c^d \bmod n$を計算すると平文mが求められます。

これをASCIIとしてデコードするとflagになるらしいです。