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-1right) equiv 1 bmod p$が成り立つ、と言うものです。

このフェルマーの小定理と式(1)を用いますと、$a ^ left( e*dp right) equiv a ^left(1+i*(p-1)right) equiv a *( a^i )^left(p-1right) 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になるらしいです。

コメント