picoCTF 2019 rsa-pop-quiz - Points: 200

#問題

https://2019game.picoctf.com/problems

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/dbcc7711-ac00-625e-466c-2a65ddc51846.png)

#解いてみた

とりあえずアクセスしてみます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/86f7f86c-9e3d-ad4b-ef4e-99d73dc5f806.png)

あんまり意味が分かりませんが、YESをこたえないといけない気がしますが、一度noをこたえてみます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/e9324802-ee23-1e90-6ec6-8c33408c4283.png)

ダメっぽい感じになりました。
yesで答えてみます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/e9df1029-df05-866c-a002-a431b131371e.png)

なんかよくわかりませんが、nをこたえる問題のようなので、適当に答えてみます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/e6217f3f-5973-b7c4-902f-73926e7fc152.png)

ダメだったみたいです。
ヒント見てみます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/47f2149e-d43c-33ad-3b32-a75e4d473555.png)

RSAの問題でしたか。確かに問題の題名もRSAになってましたね。
ヒントのリンクに移動してみます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/2adde593-db17-7c03-9225-2c7336f97d0c.png)

なるほどn=qpらしいので、そのまま計算してみます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/201bf4da-bc0d-8109-2fac-d2d3482de8cd.png)

突破した！
次はpnからqを求める問題のようです。
割り算すればよいですよね？

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/40474bbc-642b-5754-54fc-44097f092bff.png)

正解しましたが、次の問題は桁数半端ない。
暗号によくあるやつ。

nとeからqとpを求める問題か。
eは初めて出てきたので、さっきのヒントページを見てみます。
RSA暗号なら日本語ページ見ればいいですね。
eは適当な正整数ということでqとpには関係ないようです。
qとpとnの関係はさっきの問題でわかっているとおりn=q*pなのでnからqとpを生成するのは不可能です。
ということでこの問題はnoが答えだと思います。

次の問題。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/b0b97a07-2d13-c970-e2da-db81464a9757.png)

totientってなんでしょうか？
日本語サイトじゃわからなかったので英語サイトに戻ります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/69a3c408-eaf5-22ca-2ba2-2dd129782552.png)

だそうです。
その通りに計算すると正解でした。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/94bca480-8e89-b493-23f8-c9090fb9adc4.png)

平文とeとnから暗号文が生成できるか？という問題。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/e1f4d7b4-81f6-185e-c6a5-e160793c70f8.png)

できそうですが、桁数がかなり大きいのでpythonで計算します。
pow()使えば一発でできそうです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/168ba6b0-08ee-0805-a348-a10de0dc9c44.png)

こんな感じで。

次の問題。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/47798743-6b02-9b81-d4e0-7fb51a950e49.png)

復号できるかという問題。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/a49ee659-8692-69f1-b34d-62c8c4e1aca2.png)

dがないのでできません。

次の問題。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/c73d6225-db47-74b2-3c64-e97c7008c840.png)

dを求める問題です。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/bcdd8827-c517-dbe0-93b2-f628fc040b65.png)

これをpythonで作ると

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/0ff9cb6a-9b6c-081b-8cbb-06ed02b31b12.png)

という感じでしょうか。
これを実行すると

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/bb50d72b-2b15-ae3f-889a-af1f70da0ca6.png)

エラーになりました。
3番目の引数つけると負の累乗はできないんですって。
まぁ確かに小数になるから余りなんてないか。
ん？そしたら答えがないことに。

そもそも式の読み方がちょっと違って

dを(p-1)(q-1)で割ったときのあまりがe^-1ですよという式か。
と思ったらそれだとしたらeは正の整数なのでe^-1は小数になってやはりありえないことに？

ほかのサイトを調べてみると

```
ed≡1(mod(p-1)(q-1))
```

と書いてるところが多かった。
これはedをかけた数を(p-1)(q-1)で割ったら余りは1ですよという意味で、これならありえそう。
だけど計算式はちょっと難しそうなので検索する。

Python で RSA 公開鍵暗号をなぞってみる - CAMPHOR- Tech ...
https://tech.camph.net/rsa-public-key-encryption/

ここを参考にしてdを求めました。

次の問題です。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/f8eb4c81-dda1-9f9a-2206-82a8c71f2591.png)

まだあるのか。
ほかの200点と比べて費用対効果が。。。

p,e,nを与えられた状態で暗号文を復号することができるかという問題です。
復号するにはdとnが必要です。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/123f65b5-2f28-7072-394f-81c95b916685.png)

nはすでに与えられているのでdが生成できるかどうか。

dはひとつ前の問題で生成する方法を学びました。
nとpがあればqは算出できるので、eも使ってdは出せそうです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/5709d243-9e4e-1f49-f0d0-d10e869a0a09.png)

こういうことをすればよさそうです。
これを実行すると相当長い数字は出てくるんですが、答えではありませんでした。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/f4bdc991-94b7-dd6c-f7c9-4e969824c7d0.png)

プログラムがたぶん間違ってるので見直してみます。
とりあえずqを表示してみる。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/8f2d661b-1c0a-3110-2816-30fe7423300f.png)

長すぎたときになるやつ。
q*pをしてnと一致するか見てみます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/48ba051f-1e89-5bc3-5b80-a1cb74e975f9.png)

q*pがinfになってしまった。
n/pがうまくいってないってことですよね。


Python3の整数int型に最大値はない（上限なし） | note.nkmk.me
https://note.nkmk.me/python-int-max-value/

ここを参考にすると

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/10ccea23-854c-dcff-4756-fe900064d8c3.png)

だそうです。
n/pして算出したqの型を見てみます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/8d3436ef-83f5-33a8-408c-442c79e81013.png)

まさかのfloat。割り算だから勝手にfloatになるのか。
intにキャストすれば良いのか。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/d3261e26-f9b9-b17c-07bf-b1773f5b7a2b.png)

これで実行すると上が問題の値で下が算出した結果です。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/53979bef-4aa6-47b0-6177-d325030acf53.png)

途中から変わってますね。
もともとfloatで算出されたqをintにキャストしてもfloatの時点ですでに何かしら丸め込まれているということでしょうか。

python2でやってみますか。
Ubuntuで。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/bca0a568-6e78-eef1-4433-74492ddf0e69.png)

long型でかつnも合ってました。
このままpython2でやったほうがよさそう。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/40b598ea-2d1d-b44e-df79-1ac87f1782fd.png)

それっぽい答えが出ました。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/25b30487-f361-96f6-6cea-927e12657d6c.png)

あってたっぽいです。
python3怖いな。
python2を使い続けたほうが良いんでしょうか。

さっきの答えを16進数に変換してasciiに変換します。
CyberChef使います。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17681/8aa945f4-0546-1a12-2cbc-5d33678cd7da.png)

答えです。