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を求める方法
begin{align}
e*dp = 1+i*(p-1)
end{align}
数論的に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(間違わなかった方)が通信相手である公開鍵を使う側で計算できてしまいます。)
コメント