CTF初心者がpicoCTFのpicoGymをやってみた【初めてにおすすめのCTF入門】[picoCTF2021]
picoGymとは
CTFとは問題を解くことでフラグという文字列を得るゲームのことです。しかし私のような超ウルトラプログラミング初心者には難しいものばっかりです。
そこでいろいろ探してみると、picoCTFやcpawCTFがおすすめだとわかりました。
そして実際に自分でやってみると、、、難しい。
多分cpawCTFが初心者におすすめって記事に書いている人は、初心者の意味が私にとっての中級者に対応しているんだと思います。
やっぱりCTFは難しいものしかないのか。。
そう思っていましたが、ついに簡単そうなものを見つけました！
それがpicogymです！
これはpicoCTFの練習場らしいです。
これは自分のレベルに合っているだろうと思いやってみました。
どんな感じか
今6問解いたところでこの部分を書いているのですが、結構初心者の中の初心者の私でも解けて楽しいです。
なによりヒントがあるのがいいです。
そしてLinux環境を用意しなくて済み、pythonすらインストールしなくてもできます。
一部自分でプログラムを書いて解くものもありますが、入出力ができればどんな言語でも自分の好きな言語ででき、ネットで必要な変換サイトとかみつければプログラムすら書かなくて済みます。
やはりpicoGymはcpawCTF等の有名なCTFより簡単で一番最初に解くのにふさわしい難易度だと思いました。
まあまだ6問しか解いてないんですけどね。
12問解きました。むずすぎです。いやwriteupを見れば超短いコードで華麗に解いているため簡単に見えますが、いざ実際自分で解くとなるとやはりその過程にどうしてたどり着くのか疑問がわき出てきます。
あとpython使えないとむりむりのむり。あとは最低限の数学の知識も必要。
なにがpicoだ！もっとごつくGACHICTFとか強そうな名前にして欲しい。
ポイントが小さい順からやっているのですが、ポイントが高い問題でもめっちゃ簡単な問題があるので解ける問題から解くのがいいかもしれません。
やってみた
以下解説というか自分のやった記録を書きますが、FLAGは書いていません。
数字は自分がやった順番です。
１．Obedient Cat (正解率66%/いいね率89%)
チュートリアルの一番最初にふさわしい問題でした。
ファイルをダウンロードして、その中身を見るだけ。
まあcpawとかはフラグがそのまま表示してあるんですけどね。
でもそのあとの難易度の上がり方がついていけないんですよねー。
2.Mod 26 (68%/93%)
rot13の問題です。アルファベットを13文字ずらすだけです。
rot13.comに打ち込めばすぐ出ますが、せっかくなので自分で書きました。
VisualCを使うのはめんどかったので、paiza.IOを利用しました。
c言語くらいしか普通に使えないため、長ったらしく書いてみました。
#include <stdio.h>
int main(void){
char a[100];
scanf("%s",a);
for(int i=0;i<100;i++){
int koeru;
//小文字
if(a[i]>='a' && a[i]<='z'){
koeru=a[i]+13-'a'-('z'-'a'+1);
if(koeru>=0){
a[i]='a'+koeru;
}else{
a[i]+=13;
}
}
//大文字
if(a[i]>='A' && a[i]<='Z'){
koeru=a[i]+13-'A'-('Z'-'A'+1);
if(koeru>=0){
a[i]='A'+koeru;
}else{
a[i]+=13;
}
}
printf("%c",a[i]);
}
}
rot13.comのコードを見てみたらめちゃ短くてすごいなと思いました。
3.Python Wrangling (71%/63%)
pythonを使う問題です。
なるべく自分のパソコンじゃなくてブラウザ上で完結させたいと思いpaiza.ioを使おうとしたのですが、なぜかエラーが出て引数をうまく渡せませんでした。
そのため自分のパソコンにanacondaを入れていたので、anaconda promptから実行しました。
実行すると文法が表示され、適当に引数を渡すと使い方の例を表示してくれます。
-dでデコードすればOKです。
なんと！
次の問題を解くときわかったのですが、picogymのサイトに付属しているwebshellという機能を使うとpythonをそこで実行できることがわかりました！
しらなかったー。
4. Wave a Flag (81%/91%)
Linuxの実行ファイルであるELFの問題です。
私はWindowsを使っているので、cpawとかでELF問題が出るの本当に嫌でした。
私は圧倒的exe派で、exeを解析するツールであるx96dbgやollydbg、うさみみハリケーンでELFが解析できるならいいんですけど。
cpawのときはわざわざ仮想環境をインストールしたんですけどノートパソコンじゃ重いので本当に嫌だったんですよねー。
だがしかし！今回はwebshellがあります。
Linuxなんかほとんど全く使わないので使い方がわかりません。
でもヒントが今回は5つもあります。
使い方も丁寧に書いており、wgetでURLからファイルをダウンロードし、chmodで実行可能にし、あとは実行して指示に従うだけです。
wget URL
chmod 777 ファイル
ELFの実行コマンドは直下のディレクトリに移動して ./ELFファイル
5.information (24%/44%)
むずすぎる。自力で解けなかった。
あとなんで正解率が24％なのにいいね率が44％と正解率より高いんだ？
まあ前まで大体正解率90％だったのが一気に半分になった理由はわかります。
それはヒントが急に優しくなくなったからです。
何すればいいかわからないですもん。
まあこれが普通のCTF、いや簡単な方なのはわかるんですけど私にはむずすぎます。
とりあえずバイナリエディタで開いて中身を見てみました。
結構長かったので何か他のファイルが埋め込まれているんじゃないかと思い、exeの目印であるMZがないか、xpacket end='w'とか書いてあったためググるとPDFが一番上に出てきたためPDFが埋め込まれているんじゃないかとか、ファイルが長いので後半は画像データじゃないんじゃないかと思いいろいろいじると猫がホラー画像のような色になったりとか、画像のパソコンの画面が荒かったので色彩を変えれば文字が浮かび上がるのではとかいろいろしたんですけどわかりませんでした。
結局picogym informationでググることに。すると同じようにwriteupを書いている人がいました。
それを見るとメタデータのところにbase64でエンコードされたフラグがあるとわかりました。
なんかメタデータに怪しい文字列があったからとりあえずbase64でデコードしたそうです。
もうまずその発想がありません。
ていうか全部怪しく見えます。
あとなぜbase64が思いつくのか。文字列を隠すのなんてそれこそ前の問題に出たrot13もあり得るのに。
てかせめて文字数変えて末尾に=があったらまだわかるのになんでぴったりにしちゃうの？picogymでしょ？
とりあえず画像の情報が書かれている最初の部分に確かに怪しいと思えば怪しい文字列があったのでデコードするとフラグが得られました。
あとなるべくwebshellを使いたかったのでwebshellでbase64のデコードをしようとしたらやり方がわからなく、ぐぐると使い方が書かれているサイトがあり、
echo 'エンコードされた文字列' | base64 -d
でできるそうですが、base64 --helpで調べてもファイルをデコードする方法しか出なかったのでどうやってそれがわかったのかなとかいろいろ疑問がわいて疲れました。
前に自力でbase64を実装したことはありますが、ビットシフトさせたりとか作るのにめちゃくちゃ時間がかかったのでさすがに今回は作る気は起きませんでした。
しかし復習として前に作ったものを一応載せておきます。
base64とは、どんなバイナリでも変換してアルファベットと数字と記号を合わせた64種類で表すというものです。
その変換は、base64に変換するエンコードでは26=64で64種類を表せる6ビットずつ取り出して対応する文字に置き換えます。
余ったビットは0で埋めて対応する文字に変換します。
このときもともと8ビットのものから6ビットずつ変換するため、キリがいい最小公倍数である24ビット、すなわち4文字ずつ変換します。
そのため4文字ずつ変換できるようにエンコード後に文字数が4の倍数になるよう足りない分'='を付け足します。
base64を元に戻すデコードでは、エンコードの逆の操作をします。
まず'='を除く。
そしてbase64の対応するアルファベットを数字に戻して、そこから8ビットずつ取り出せば元に戻せます。
一応私の冗長なコードも載せました。
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
int b64table(int b64)
{
int ascii=-1;
//0~9 48~57 -> 52~61
if (b64 >= 48 && b64 <= 57) {
ascii = b64 + 4;
}
//A~Z 65~90 -> 0~25
if (b64 >= 65 && b64 <= 90) {
ascii = b64 - 65;
}
//a~z 97~122 -> 26~51
if (b64 >= 97 && b64 <= 122) {
ascii = b64 - 71;
}
//'+' 43 -> 62
if (b64 == 43) {
ascii = b64 + 19;
}
//'/' 47 -> 63
if (b64 == 47) {
ascii = b64 + 16;
}
//'=' 61 -> 0
if (b64 == 61) {
ascii = 0;
}
//error
if (b64 == -1) {
printf("ascii=%d\n",b64);
}
return ascii;
}
char* b64decode(char *data)
{
int b64size=strlen(data);
for(int i=0;i<strlen(data);i++){
if(data[i]=='='){
b64size=i;
break;
}
}
//デコード後のサイズ
int dsize=(b64size*6)/8;
char* decode = (char*)calloc(dsize+1,1);
for (int i = 0; i < b64size; i += 3) {
int comp = i / 3;
if (i + comp >= b64size)break;
decode[i] += b64table(data[i + comp]) << 2;
if (i + 1 + comp >= b64size)break;
decode[i] += b64table(data[i + 1 + comp]) >> 4;
decode[i + 1] += b64table(data[i + 1 + comp]) << 4;
if (i + 2 + comp >= b64size)break;
decode[i + 1] += b64table(data[i + 2 + comp]) >> 2;
decode[i + 2] += b64table(data[i + 2 + comp]) << 6;
if (i + 3 + comp >= b64size)break;
decode[i + 2] += b64table(data[i + 3 + comp]);
}
return decode;
}
char* b64encode(char* moji)
{
int size=strlen(moji);
char base64[65] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
//'='を含まないエンコード後のサイズ
int esize=(size*8)/6;
if((size*8)%6>0)esize++;
int surplus = (size * 8)/24;
if((size * 8)%24>0)surplus++;
surplus=surplus*4-esize;
char* encode = (char*)calloc(esize+1,1);
for (int i = 0; i < esize; i += 3) {
int comp = i / 3;
if (i >= esize)break;
encode[i + comp] += moji[i]>> 2;
encode[i + 1 + comp] += (moji[i] & 0b00000011) << 4;
if (i + 1 >=esize)break;
encode[i + 1 + comp] += moji[i + 1] >> 4;
encode[i + 2 + comp] += (moji[i + 1] & 0b00001111) << 2;
if (i + 2 >= esize)break;
encode[i + 2 + comp] += moji[i + 2]>> 6;
encode[i + 3 + comp] += (moji[i + 2] & 0b00111111);
}
char* encodeStr = (char*)calloc(esize+surplus+1,1);
for (int i = 0; i < esize; i++) {
encodeStr[i]=base64[encode[i] % 64];
}
for (int i = 0; i < surplus; i++) {
encodeStr[i+esize]='=';
}
return encodeStr;
}
int main()
{
char *b64url= "YmFzZTY0aXNkaWZmaWN1bHR0b3VuZGVyc3RhbmQ=";
b64url=b64decode(b64url);
puts(b64url);
b64url=b64encode(b64url);
puts(b64url);
b64url=b64decode(b64url);
puts(b64url);
return 0;
}
話を戻し、今回の問題を整理すると、問題名がinformationであること、ヒント1がdetailを見ろとのことから画像の情報の部分、すなわちメタデータ(データに関するデータ)の部分を見ろということ。
ヒント2からフラグの形式がpicoCTFであることを再確認せよとのことから、picoCTFという文字列を何らかの方法で変換して埋め込まれているということ。
ここからbase64が一般的に用いられる変換法であることから試してみるというのがこの問題の解き方でしょうか。
私はdetailの意味を詳しくだと思い、バイナリデータを詳しく探せって意味にとらえてました。
一気に難易度上がりすぎというか、ヒントが少ないというか不親切というか。
picogymならもっとヒントがあってもいいと思いました。疲れた。
6.Nice netcat... (63%/91%)
数字が羅列されます。
問題文の英語ではない何かをしゃべっているということからこの数字は文字である、文字に変換可能であるだろうと予測できます。
そもそも文字は文字コードという数字で扱われるので、アルファベットによく使われるアスキーコードに変換するとクリアです。
c言語で書いてみました。
#include <stdio.h>
int main(void){
char a[100];
for(int i=0;i<100;i++){
scanf("%d",&a[i]);
if(a[i]==-1)break;
}
puts(a);
}
任意の数の整数を受け付ける方法が分からなかったので、最後に自分で-1を入力しときました。
この問題でもアスキーコードが思いつかなかったら解けないじゃんと思われますが、ちゃんとヒントに書いてあります。というか、アスキーコードを使えというよりはアスキーコードを使う他の問題が紹介されてますね。
そもそもnetcatってなんなんですかね。アスキーコードをしゃべるネット上の猫ってことでしょうか？
ここまで問題を左から右に順番に解いてきたのですが、せっかく他の問題をお勧めされたのでそれをやってみます。
7.what's a net cat? (75%/85%)
関係ないですけどLinuxでコピペはctrl+shift+(C or V)でできるんですね。
キーボードでできないのかと思っていちいちマウスでやってました。
この問題はnetcatの使い方を学ぶ問題です。
もう最高です。
私のようなnetcatって何？ネット上の猫？とか思っている人にもnetcatとはlinuxのパケットを扱うツールなんだよ、使い方のサイトはここだよって知るきっかけをくれます。
やっぱこういう問題いいですよね。
段階的に学べて行く感じが楽しいです。
しかもただ順番に学ぶんじゃなくてこういうCTFというゲームを通じて学べる。
最高ですよ。
この問題は6のヒント1で紹介されていた問題なので、次はヒント2でおすすめされていた問題を解きます。
8.Lets Warm Up (44%/77%)
アスキーコードを知る問題です。
6でつかったコードを16進数用に直して16進数をアスキーコードに変換しました。
これで6の問題はnetcatとアスキーコードを知ってから臨めるということですね。
実に丁寧でいいです。
こういうの求めてました。
9.Transformation (42%/56%)
あと本当に関係ないんですけど、書式なしのペーストってctrl+shift+vでできるんですね。
このブログに問題名をコピペするとき、いちいち検索バーに一回ペーストして書式消してました。けれどwebshellからコピーするときchromeだとデベロッパーツールが開いちゃうのがなぁ。
てかまたむずいのが来た。
自力で解けませんでした。
しかし今回は解く手がかりはちゃんと用意されていました。
そのためただの実力不足です。
解けなかった理由としては
・問題文にあったコードが何を意味しているのか理解できなかった
・pythonの理解不足
が挙げられます。
とりあえずencをダウンロードしてバイナリを見てみましたが、ただのバイナリでした。
問題文にはコードがあったため、このコードを使えばフラグが得られるんだと思いました。
しかしそもそもこのコードが何の言語かわからず、writeupがひっからない位で、「''.join([chr((ord(」でググるとどうやらpythonらしいことがわかりました。
しかしどう使えばいいか分からなかったため、''のなかにencの中身を入れればいいのかな、flagにencの中身を入れればいいのかとかいろいろ試してみました。
しかし何も表示されなかったりエラーが出たりしました。
ヒントを見てもオンラインのデコーダ探せば、としか書いておらず、意味が分かりません。
ここで万策尽きたのでこのコード全体をググりました。
するとwriteupが見つかり、それでも最初は理解できなかったんですけど、3つくらいwriteupを見てやっと理解しました。
''.join([chr((ord(flag[i]) << 8) + ord(flag[i + 1])) for i in range(0, len(flag), 2)])
これはこのコードを使ってフラグを変換したよということを意味していました。
そのため、このコードの逆の手順によってencの中身をフラグに戻せばいいということです。
私はpythonの関数なんてprintしか知らないので、pythonの勉強を合わせて解いていこうと思います。
.join()
文字列のリストを連結する関数。'間に挿入する文字列'.join([連結したい文字列のリスト])
ずっと''に何か入れるんだとおもっていましたが全然違いましたね。
chr()
ユニコードの文字コードを文字に変換する関数。
ord()
文字をユニコードの文字コードに変換する関数。
<<はc言語でもあるビットシフトですね。
あとpythonはfor文が独特ですよね。今回はリスト内包表記というリストの処理を簡便に書く方法が取られています。
range()
順番にリストを取得する関数。range(start,stop,step)
これらを知ったうえでこのコードを読んでみると、変数iは0からリストflagの要素数まで2個飛ばしで値を取る。
そしてflag[i]をユニコードに変換し、それを8ビット左にずらしたものとflag[i+1]の和を取り、それをユニコードに変換したものをすべて連結して文字列にしている。
すなわち、フラグの文字列を、2文字ずつ1文字に圧縮していることがわかります。
今度はこれを逆に実行してみましょう。
まずはファイルencをopen(ファイル名)で開き、ファイルオブジェクト.read()で中身を得ます。
次に、コードの最後で文字列に変換されたので、list(リストにしたい文字列)で文字列をリストに変換します。
そして、一文字にはフラグが2文字分含まれているので、上位8ビットと下位8ビットをビット演算で分ければフラグを取り出せます。
f=open("encへのパス",encoding="utf-8")
flag_en=list(f.read())
flag=""
for i in range(len(flag_en)):
moji1=chr(ord(flag_en[i])>>8)
moji2=chr(ord(flag_en[i])&0b11111111)
flag+=moji1+moji2
print(flag)
webshellでやろうとすると、一行ずつ打たなければならず、またfor文が始まった後、どうfor文を終わらせればいいかわからなかったので自分のPC内でやりました。
あとwindowsで実行すると、文字コードがCP932というマイクロソフト版になるっぽく、文字化けしたのでutf-8にエンコードしておきました。
pythonの勉強になったので良かったです。
10.Stonks (29%/60%)
自力で解けませんでした。
これもヒントが優しくないです。
しかし、しかしですよ！
c言語をやっていたり、脆弱性の本を読んだことがあったのでprintfの脆弱性については知っていたんです。
でもなんか%nを使ってほにゃほにゃするやつとかいう記憶で全然ちゃんとは理解できていなかったのです。はい。
最初はテキトーに1と2の選択肢を選んでどんな感じに動くのか確かめてました。
そのあとコードを読んで、3回くらい読み直して少しずつどんなコードかわかってきました。
するとコメントアウトが3つあり、後ろの2つで囲まれた部分に唯一ユーザーが自由に打てるscanfのコードがありました。
最初の1か2を入力するものはただ1か2をif文で判断しているだけですが、2つ目の入力はわざわざユーザーの入力をprintf(user_buf)で表示しています。
このとき、あ、なんか見たことあるやつだと思い出しました。
そうです。
%xとか入力するとprintf("%x")となって、バッファの中身が表示されるとかのやつです。
またヒントによればAPI keyを入手しろとありました。
APIに関係しそうなものは
char api_buf[FLAG_BUFFER];
FILE *f = fopen("api","r");
if (!f) {
printf("Flag file not found. Contact an admin.\n");
exit(1);
}
fgets(api_buf, FLAG_BUFFER, f);
ここの部分ですよね。
すなわちapi_bufという変数にapiというファイルから何か読み込んでいることがわかります。
よってprintfの脆弱性を使ってapi_bufを表示させればいいということです。
だからいろいろ入力してみました。
%s
%c
"%s",api_buf
%s".api_buf);//
とか。それっぽいものをいろいろ入力していました。
しかしprintfの仕組みとメモリについてちゃんと理解していませんでした。
そこで改めてprintfとメモリについて学びなおそうと思いました。
c言語でこんなコードを書いてみます。
#include <stdio.h>
int main(void)
{
char moji1[]="ABC";
char moji2[]="DEF";
printf("%s %s %s\n");
printf("%c %c %c\n");
printf("%x %x %x\n");
return 0;
}
なんと苦CのEasyIDECという簡単で軽いc言語の開発環境が10年ぶりに更新されていたのでそれを使ってみました。VC++はいちいちプロジェクトを作る必要があり面倒くさいので。
実行結果は
€
D A p
464544 434241 19ff70
こうなりました。ときどき何も表示されませんでした。
もっと詳しく見てみましょう。デバッガでprintf関数のもっと深く、WriteFile関数を呼び出す手前です。
WriteFile関数によってコンソール画面に文字が書き出される直前では、WriteFile関数に書きだす文字とかが渡されます。
その文字は[ebp-1AB8]のアドレスにあり、pushされることで[esp+4]に入ったようで
19E3A8に渡されたデータがあることがわかります。
これはprintf("%s %s %s\n")を呼び出すときのものです。
さらにこの中身を見てみると
よくわからない値のため文字化けしていたのですね。
同様にしてprintf("%c %c %c\n")を呼び出すときのWriteFileに渡されるアドレスの中身を見てみると
printf("%x %x %x\n")のときも
でもどうしてこんな風に表示されるのでしょうか。
moji1とmoji2のメモリの周りを見てみましょう。
printf("%c %c %c\n")のときはABCDEFの周りが 44454600 41424300 70FF1900であり、その先頭1バイトだけ取り出して44 41 70、アスキーに直してA D pとなったということがわかります。
printf("%x %x %x\n")はそのまま出力されてますね。
printf("%x %x %x\n")はそのまま出力されてますね。
まとめると、%xを用いると勝手にprintfの前にあるメモリを表示してしまうということがわかりました。そして%sや%cではちゃんとは表示できないということもわかりました。
しかし疑問なのは、%xと%pって変数のアドレスを表示するはずで、
#include <stdio.h>
int main(void)
{
char moji1[]="ABC";
printf("%p\n",moji1);
printf("%x\n",moji1);
return 0;
}
の結果は
0019FF34
19ff34
のようにmoji1の中身ではなくmoji1のアドレスを示しますよね。だから%xじゃ中身を表示できないでしょと思っていたので%sや%cしか試していなかったのでした。すなわち、メモリが変数代わりになってメモリのアドレスが表示されるのではないかと思っていました。
しかし今回確かめたように、printfは変数を文字列の後に書かないとメモリの中身を直接出力してしまうことがわかりました。
長くなりましたが話を戻します。
%sを試してもできなかったので諦めてググってwriteupを読み、%xで試すことにしました。
%x%x%x%xのように羅列して入力します。
するとプログラムのメモリがばーって16進数で羅列されるので、それを文字列に直します。
やり方はてきーとに思いついた方法ですが、まず文字列として受け取り、2文字ずつ取り出して、strtolという文字列を数値に変換するウルトラ便利な関数があったのでそれを使った感じです。
#include <stdio.h>
#include <stdlib.h>
int main(void){
char a[10000];
scanf("%s",a);
for(int i=0;i<3000;i+=2){
char moji[]={a[i],a[i+1],'\0'};
int suuji= strtol(moji, NULL, 16);
printf("%c",suuji);
}
}
するとフラグらしき文字列がリトルエンディアン、すなわち8バイトずつ順番が逆になった状態で得られました。
そのため上記のコードを改良し、
#include <stdio.h>
#include <stdlib.h>
int main(void){
char a[10000];
scanf("%s",a);
for(int i=4;i<3000;i+=8){
for(int j=i+6;j>=i;j-=2){
char moji[]={a[j],a[j+1],'\0'};
int suuji= strtol(moji, NULL, 16);
printf("%c",suuji);
}
}
}
ちょっと位相というかフラグのところからちょうど8バイトずつ逆にするためにiの初期値を調整して無事クリアできました！
確か%nは昔あったやつで今は使えなかったりとかなんとかだった気がします。
あとwriteupを見てみるとpythonを使って%pを
$ python3 -c 'print("1\n" + "%p." * 50)' | nc mercury.picoctf.net 53437
のように華麗に書いている例があったのですが、ちょっとよく分からなかったのでコピペ大作戦を決行しました。
てかそもそもpicogymは初心者向けというより、picoCTFのアーカイブとして主に使われているようで、このような超初心者の私にはこの問題も重かったです。
もうpicogymを完全に初心者向けにしてヒントを追加したりして、アーカイブは他のところでやってほしいです。
てかcpawCTFは現時点で公開されているLevel3まで全部クリアしてましたね。びっくり。
なんか結局picoCTFをやっているわけで、cpawCTFと難易度はそんな変わらなくなってしまった感じがします。
もっと、もっと親切な問題が欲しい。。
11.GET aHEAD (60%/80%)
もう、もう無理です。。。
3連続解けないとかむずすぎて意味わかんないです。。。
今まではnetcatとか使い方から教えてくれたのに、もう新しい要素が出てきても自分で考えろばかと言われているようで全然優しくないです。
もうpicogymとか全然練習じゃないです。
writeupでもググりますか。。
writeupを見てみると一応ヒントはあったようですね。
この問題のタイトルであるGET aHEADは、問題文中ではフラグを勝ち取れ的な意味で使われていましたが、あえてaheadのHEADが大文字になっていることがヒントだったそうです。
私がこの問題を解けなかった理由は明らかで、POSTとかGET、HEADなどの基礎知識をそもそも知らなかったことです。
パケット関係について一応軽く本を読んだつもりでしたが、全然理解が甘かったので、ここで復習しておきます。
えー、まずネットではデータをパケットという単位でやり取りしていると。
そのデータというのは電気信号で電磁波や光、電子として電線とか通って遠くのコンピュータにデータが届くと。
そのパケットにはいろんな情報が詰め込んであり、そのパケットの中身はOSI参照モデルという段階的にデータのやり取りの仕方を決めたものに基づいて分類されると。
まずパケットの中身以前に、遠くのコンピュータにどんな電気信号として渡し受け取るかを決める物理層。
次からパケットの中身として、どのコンピュータに送るかを決めるデータリンク層。
どのネットワークに送るかを決めるネットワーク層。
どのアプリケーションにどんなふうに渡すかを決めるトランスポート層。
最後に、アプリケーションに渡す中身であるアプリケーション層。
このように、データリンク層からアプリケーション層の4種類のデータが含まれたパケットというデータをやり取りすることでネットワークが成り立っていると。
それで今回は、赤とか青に変わるサイトでフラグを探せということでした。
このサイトのコードを見てみると、ボタンを押すことでGETやPOSTといったデータを送っていました。
GETやPOSTというデータは、サイトのデータを送ってくるサーバーにあるプログラムやブラウザといったアプリケーションに関係します。
そのためこの問題を解くためには、アプリケーション層について知っていればいいということになります。
ブラウザやサーバープログラムが送り合うデータの形式は
メッセージフォーマット：
・スタートライン
メッセージの種類を表す。
・メッセージヘッダー
ブラウザとかの設定が書かれている。
・空行
ヘッダーとボディの境界。
・メッセージボディ
データの中身。
このようになっていると。
さらにこれはデータを最初に送るリクエストメッセージとと、それに返信するレスポンスメッセージの場合で中身が変わってくると。
リクエストメッセージでは
・スタートライン
+リクエストライン
メッセージの種類を表す。
・メッセージヘッダー
+リクエストヘッダー
+一般ヘッダー
+エンティティヘッダー
+その他のヘッダー
・空行
ヘッダーとボディの境界。
・メッセージボディ
データの中身。
ここでGETやPOSTといったものはリクエストラインに含まれ、GETはサーバーからデータを取得する、POSTはサーバーへデータを転送するというメッセージの種類を表しています。
メッセージヘッダーではブラウザが扱える画像や文字、言語を指定したり、メッセージボディのサイズやクッキーやキャッシュの取り扱いについてとかいろいろ書かれています。
メッセージボディには送りたいデータが書かれます。
次にその返信としてレスポンスメッセージでは
・スタートライン
+ステータスライン
処理結果。
・メッセージヘッダー
+レスポンスヘッダー
+一般ヘッダー
+エンティティヘッダー
+その他のヘッダー
・空行
・メッセージボディ
リクエストメッセージと大体似た感じでまたいろいろ情報が載ってます。
ではGET aHEADのサイトが送ってきたパケットを見てみましょう。
・Frame
パケットの情報？
・Ethernet II
データリンク層
・Internet Protocol
ネットワーク層
・Transmisson Control Protocol
トランスポート層
・[2 Reassembled …
TCPの情報？
・Hypertext Transfer Protocol
アプリケーション層。スタートライン、メッセージヘッダがある。
・Line-based text data
メッセージボディの部分？なんでHypertext Transfer Protocolの中にないんだろ？
とりあえずこんな感じのパケットが送られていることがわかりました。
でも結局はこのパケットの情報を手掛かりとして少しずつ解いていく問題ではなく、今回の問題は発想力が必要となります。
・問題名のGET aHEAD
・ヒント1の2つ以上選択肢があるよ
・ヒント2のBurpsuiteというソフトで自分のリクエストメッセージを弄り、そのレスポンスメッセージを確認して
とりあえずGETとPOST以外にメソッドがあるか調べると、データの更新に使うPUT、削除するDELETEしかでてきませんでした。
しかしちゃんと調べれば、もしくは知っていれば他にももっと
OPTIONS, HEAD, TRACE, CONNECTなどがあることがわかります。
この全部を試すか、問題名に含まれるヘッダを求めるHEADを試せればクリアです。
全部試せば発想力要りませんね。けれど、私はPUTとDELETEを試してだめだったので解くには他の方法でないといけないのかもと思い諦めてしまいました。
HEADを送ると
ヘッダのところにフラグが書かれて送られてきます。
これはパケットをキャプチャするwiresharkを使わなくても、ヒントでおすすめされている自分のリクエストメッセージを編集できるburpsuiteを使わなくても解けます。
コマンドラインから様々なプロトコルのデータを送受信できるcurlというものを使えば解けます。
あとずっと勘違いしていたのは、GETでデータ全体を、HEADでヘッダ部分だけ得られるならGETで得たデータのヘッダ部分にフラグが書かれているんじゃないかと思っていましたが、ふつうにHEADだとGETの時とは異なるヘッダが送られてくるというだけでした。
あとchromeのデベロッパーツールでいじれないかと思ったのですが、phpはいじれないっぽいです。
12.Mind your Ps and Qs (47%/70%)
この問題は一番時間がかかりました。もう疲れました。。
これも解けなかったので4連敗中です。むずすぎ。picoCTFむずすぎ。
RSA暗号に関する問題です。
RSA暗号とは大きな2つの素数p,qを決め、n=pqとして1<e<nでnと互いに素なeを決め、{e,n}を平文の暗号化に使用する鍵(公開鍵)とする。
暗号の復号に使用する鍵(秘密鍵)をdとし、dは0<d<(p-1)(q-1)かつed≡1 mod (p-1)(q-1)を満たすものにする。
平文をm、暗号文をcとすると
暗号化は
c=me mod n
復号は
m=cd mod n
文字式では理解しにくいので小さい数を当てはめてみると
p=11,q=13,n=143,e=17とすると
(p-1)(q-1)=120
17d≡1 mod 120
ここで17d=120k+1 (kは整数)と表せる。
変形すると17d-120k=1
方程式のように表すとd=x, y=-kとして
17x+120y=1
17x+120y=1の方程式を解く、すなわち120k+1が17の倍数となるkを求められればdの値も決まる。
そこでユークリッド互除法という、2つの整数において商と余りを求め、割った数と余りにおいて同様に商と余りを求めるという操作を余りが出なくなるまで繰り返すことで、最初の2つの整数の最大公約数を求められるという方法を用いる。
拡張ユークリッドの互除法の説明が長いので、知っている人や読まなくていいやという人は先に飛んでください。
まず一般に
ax+by=cという式があるとし、
a=bq+rと商qと余りrで表せば
(bq+r)x+by=c
bでまとめて
b(qx+y)+rx=c
となる。
ここでs=qx+y, t=xとおくと
bs+rt=c
となる。
この操作を実際の数値を当てはめて繰り返していく。
すなわち次はb=a', s=x', r=b', t=y'となる。
まず最初は
17x+120y=1
これはax+by=cと比べると、1回目の操作のため_1をつけて
a_1=17, b_1=120
となる。
ここで17と120において
a=bq+rを表すと
17=120*0+17
すなわち
q_1=0, r_1=17
となる。
最初の式に代入して
(120*0+17)x+120y=1
120でくくって
①120y+17x=1
これはbs+rt=cと比べると
s_1=y, t_1=xとなるため
b_1*s_1+r_1*t_1=1
と表せる。
まとめると
a_1=17
b_1=120
q_1=0 (=a_1/b_1)
r_1=17 (=a_1%b_1)
s_1=y (=q_1*x+y=q_1*s_0+t_0)
t_1=x (=s_0)
(x=s_0, y=t_0と、x, yとs, tの繋がりが個人的にわかりやすいようにしてみました。
最初の式ax+by=cをbs+rt=cに見立てたということです。)
①のb_1をa_2に、r_1をb_2に置き換えて同様にa=bq+rを求めると
120=17*7+1
式①に代入して
(17*7+1)y+17x=1
17でくくって
②17(7y+x)+1*y=1
これはbs+rt=cの形であり、b_2*s_2+r_2*t_2=1と表せる。
2回目の変数をまとめると
a_2=120 (=b_1)
b_2=17 (=r_1)
q_2=7 (=b_1/b_2)
r_2=1 (=a_2%b_2)
s_2=7y+x (=q_2*s_1+t_1)
t_2=y (=s_1)
②のb_2, r_2をそれぞれa_3, b_3として
17=1*17+0
これを式②に代入して
(1*17+0)(7y+x)+1*y=1
1でくくって
1(119y+17x+y)+0*(7y+x)=1
③1(120y+17x)+0*(7y+x)=1これはb_3*s_3+r_3*t_3=1に対応する。
よって
a_3=17 (=b_2)
b_3=1 (=r_2)
q_3=17 (=a_3/b_3)
r_3=0 (=a_3%b_3)
s_3=120y+17x (=q_3*s_2+t_2)
t_3=7y+x (=s_2)
ユークリッド互除法より余りr_3=0となったため、b_3が120と17の最大公約数であり、1だとわかります。
しかし今回はこの値は使いません。
③を満たすには120y+17x=1となる必要があり、
s_3=1, t_3は任意の値をとることがわかります。
ここから式を逆にたどっていくことで答えを求めます。
s_3=q_3*s_2+t_2
t_3=s_2
に対応することから②のs,tを求めると
s_2=t_3=任意の値
t_2=s_3-q_3*s_2=s_3-q_3*t_3=1-17*任意の値
また
s_2=q_2*s_1+t_1
t_2=s_1
に対応することから①に戻ると
s_1=t_2=1-17*任意の値
t_1=s_2-q_2*s_1=任意の値-7(1-17*任意の値)=-7+120*任意の値
そして
s_1=y
t_1=x
に対応することから最初の式に戻ると
x=t_1=-7+120*任意の値 (=-7+(yの係数=(p-1)(q-1))*任意の値)
y=s_1=1-17*任意の値 (=1-(xの係数=e)*任意の値)
となり、最初の不定方程式の解が求められました！やったぁ！
任意の値は解を一般解として表すときのパラメータです。
簡単にするために0を入れることが多いです。
まとめると、
ax+by=cの解x,yはこの式を
A_nX_n+B_nY_n=C (n=0) とおくと、
Q_(n+1)=A_n/B_n を商、
R_(n+1)=A_n%B_n を余りとして、
(B_nQ_(n+1)+R_(n+1))X_n+B_nY_n=C と表せ、
B_n(Q_(n+1)X_n+Y_n)+R_(n+1)X_n=C とまとめられ、
A_(n+1)=B_n
X_(n+1)=Q_(n+1)X_n+Y_n
B_(n+1)=R_(n+1)
Y_(n+1)=X_n とおくと
A_(n+1)X_(n+1)+B_(n+1)Y_(n+1)=C となり、
X_n=Y_(n+1)
Y_n=X_(n+1)-Q_(n+1)X_n=X_(n+1)-Q_(n+1)Y_(n+1)
R_k=0となったときX_k=1, Y_k=0(任意の値)となることからnをたどって
X_0=Y_1=X_2-Q_2Y_2=Y_3-(A_1/B_1)*(X_3-Q_3Y_3)=...=function(X_k,Y_k)
Y_0=X_1-Q_1Y_1=Y_2-(A_0/B_0)*(X_2-Q_2Y_2)=...=function(X_k,Y_k)
のように漸化式を用いて不定方程式が解けるということでした。
これを拡張ユークリッド互除法というらしいです。
数学を忘れていたのかもともと理解できていなかったのか理解するのに死ぬほど時間がかかりました。
今まできっとなんとなくで解いていたんですかね。。どおりで整数問題が苦手なわけだ。。
死ぬほど長くなりましたが、話を戻すと任意の数=0とするとd=-7となります。
正の整数で扱いため、
d=x=-7+(p-1)(q-1)*任意の値=-7+120*任意の値
より(p-1)(q-1)=120を足して(任意の値を1増やした)d=113と求められました。
平文m=65とすれば、暗号文cは
c=me mod n
=6517 mod 143
=65
='a' (ASCIIコード)
あれ？暗号化できてないですね。
じゃあm=66だと、、、同じになった。。
じゃあm=67では
c=6717 mod 143
=45
='-'
やっと違う数字になった。
復号は
m=cd mod n
=45113 mod 143
=67
='a'
ちゃんと元の平文に戻りました。
pやqなどの数字が小さいので暗号化しても同じになってしまうことがあるっぽいですね。
あと平文はn=pq以下の数字でないといけません。nの余りで表しているからですね。
参考として、RSAの計算をしてくれるサイト、RSAのわかりやすい説明のサイトを貼っておきます。
ここではオイラーの定理や中国の剰余定理などのRSA暗号の仕組みの部分はさっぱりイミフなので取り扱いません。。
長くなりましたが、ついに、やっと、この問題を解いていきます！！
まず問題では、暗号文c、n,eが与えられます。
cとnは死ぬほど桁が多いです。
復号は
m=cd mod n
であり、dが分かれば解けます。
dは0<d<(p-1)(q-1)かつed≡1 mod (p-1)(q-1)を満たすものでした。
うーんと、pとqがわからないと解けないな。
でもnは死ぬほどでかい値だし無理だな。
ここでもう諦めました。
最初は勘違いして(p-1)(q-1)のところをnにしてed≡1 mod nになるdを求めればいいんだとか思っていましたが、まず巨大な数値をc言語では扱えずできませんでした。
結局諦めてwriteupをググりました。
するとこの問題のnは小さいのだそうです。
wikiにもnの桁は300-1000桁程度が推奨と書いてありました。
人によって与えられた数字は異なるようですが、私のは82桁でした。
確かに推奨されている値よりは大幅に小さいですが、普段扱う値と比べるとめちゃくちゃでかく感じました。
そしてCTF初心者なので知らなかったのですが、factordb.comというサイトで素因数分解を数字を入力することで検索できるらしいです。
今回の肝はこれですよね。
これ知らないと絶対と言っていいほど解けないですよね。
そのためこのサイトでnを素因数分解し、pとqを得ます。
確かに問題タイトルがMind your Ps and QsでPとQに注意って言ってますもんね。
このタイトルからこんなに大きいnでもPとQが求められるのだろうから、その方法を検索して探してみようって感じで知らなくてもfactordb.com等のデータベースにたどり着くのが理想的な道筋ですかね。
これでp,qを求め、次にed≡1 mod (p-1)(q-1)でdを求めます。
さっき長々と説明した拡張ユークリッド互除法をプログラムで実装します。
再帰関数できれいに実装できますが、私は再帰関数が死ぬほど苦手なのでめちゃくちゃコメントアウトで手順を書いておきました。
#include <stdio.h>
int GCD(int a,int b)
{
if(b==0)return a;
else return GCD(b,a%b);
}
/*
//さっき紹介したサイトに載っていたきれいなプログラム。理解できなかったので自分なりに冗長化したものが_がついたやつ
int extGCD(int a,int b,int *x,int *y)
{
if(b==0){
*x=1;
*y=0;
return a;
}
int d=extGCD(b,a%b,y,x);
*y-=a/b*(*x);
return d;
}
*/
//ax+by=dをユークリッド互除法を用いて解く
//dはaとbを足しているため、aとbの最大公約数の定数倍となるはず
//そのためdは答えの一つであるaとbの最大公約数として求める
void _extGCD(int a,int b,int *x,int *y)
{
//dが求められた時の処理
if(b==0){
//ユークリッドの互除法の最後
//yは任意の数ですが、分かりやすくするため0で
//printf("a=%d, b=%d\n",a,b,*x,*y);
*x=1;
*y=0;
return;
}
//a=qb+r
int q=a/b;
int r=a%b;
//a=qb+rをax+by=dに代入して
//(qb+r)x+by=d
//b(qx+y)+rx=d
//bs+rt=d
//s=qx+y x=t
int s,t;
//dはaとbの最大公約数だからaをbに、bをrに変えてdを求めていく。
//sとtはまだ求められないから次の関数にまかせる
_extGCD(b,r,&s,&t);
//dが求められてsとtも求められた後
//x=t y=s-qx=s-qt
*x=t;
*y=s-q*t;
printf("x=t=%d, y=%d, s=%d\n",*x,*y,s);
return;
}
int main(void)
{
int a=17,b=120;
int x,y;
_extGCD(a,b,&x,&y);
printf("extGCD(%d,%d):x=%d,y=%d\n",a,b,x,y);
//printf("GCD(%d,%d)=%d\n",a,b,GCD(a,b));
return 0;
}
これが普通の整数に対応している関数です。
しかし今回は普通ではなく巨大な整数です。
そのため扱い方を工夫しなければいけません。
そこで登場する考えが多倍長整数演算です。
これは数字を1文字ずつ配列として扱うことでメモリのある限り巨大な桁の計算ができるというものです。
このサイトを読んで実装しました。
筆算をプログラム上で再現する感じです。
そのサイトの後半には高速で計算する方法が書かれていますが、割り算の筆算を実装するだけで超疲れたので無理です。
これでc言語のintやlong型で扱える桁の上限を突破できました。
ちなみに後でコードを載せるのですが、数値の配列ではなく文字列として計算するよう実装したため構造体等で数字を渡さずに文字列だけを関数に渡せばよくなったのですが、その分内部がぐちゃぐちゃになりました。
あとmallocで確保したメモリを解放してないので真似しないでください。
どうせ長時間起動するプログラムではないので個人的には問題ないです。
この多倍長整数演算を実装して拡張ユークリッド互除法を計算することで得られたdを用いて
m=cd mod n
より平文mを求めていきます。
もう後は簡単ですよね。
cをd乗してnの余りを求めるだけですから。
しかしまた躓きました。
普通にcのd乗を計算しようとしたからです。
やってみるとわかりますが無理です。
膨大過ぎて時間がかかりすぎます。
これは合同式の重要な性質を忘れていたからです。
それは
a≡A mod m, b≡B mod m のとき ab≡AB mod m が成り立つ
です。
証明は、k,lを整数としてa=A+mk, b=B+mlとなるため
ab-AB=(A+mk)(B+ml)-AB
=m(Al+Bk+mkl)
よりabとABの差がmの倍数になるため証明できた。
abもABもmで割った時の余りが同じため、差を求めると余りが消えてmの倍数が残ったということです。
すなわち、cdをいきなり求めるのではなく、cをnで割って余りを出し、さらにcをかけたものをnで割った余りを出し、とcを掛けるたびにnで割っちゃっていいんです。
そしてさらに、d回cを掛けるのもまあ時間がかかるのでこのサイトを参考にべき乗の計算を再帰関数を用いる方法を実装しました。
例えばcを101乗するならcの50乗同士を掛け合わせた後cをかけることにしてまた自身の関数を呼び、50乗は25乗どうしをかけることにしてまた呼び出し、12*2+1, 6*2, 3*2, 1*2+1までいき、実際にかけ合わせながら戻ってくることで最後にc101=(c50)2×cで求めることで大幅に計算回数を減らせるということです。
それでついにmを求められました。
次にこの得られた巨大な整数である平文を文字に変換します。
この変換にもまた躓きましたが、要するに文字コードが16進数としてつなげられて1つの整数として表されているということです。
例を挙げるとASCIIでは'a'=97=0x61, 'b'=0x62です。
よって"ab"をこの平文と同じように整数で表すと
"ab"='a','b',(0)=0x61,0x62→0x6162=24930
という具合です。
この逆の操作をプログラムで実装すればOKです。
そして遂に、やっと、めちゃくちゃ時間がかかりましたが、このプログラムを解くことができました。
この膨大な数をfactordb.com以外に外部のライブラリ等に頼らずにc標準ライブラリだけで解くことができました！
疲れました。
500行弱のくそコードなのでこれを表示するのに10秒弱かかりましたが、pythonでやれば10行程度のコードで1秒にも満たない時間で解けます。
CTFやるやつはpython使えよっていうメッセージがひしひしと伝わってきました。
CTFやるやつはpython使えよっていうメッセージがひしひしと伝わってきました。
一応参考にはならないと思いますが自分のコードを載せておきます。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* convmin(char* a,int flag);
char* chartonum(char *suuji)
{
int keta=strlen(suuji);
char *p=(char*)malloc(keta+1);
for(int i=0;i<keta;i++){
p[keta-i-1]=suuji[i]-'0';
}
p[keta]='\0';
return p;
}
char* inttochar(int *a,int keta)
{
char *p=(char*)malloc(keta+1);
for(int i=0;i<keta;i++){
p[i]=(char)a[i];
}
p[keta]=0;
return p;
}
char* rev(char *suuji)
{
int keta=strlen(suuji);
char *p=(char*)malloc(keta+1);
for(int i=0;i<keta;i++){
p[keta-i-1]=suuji[i];
}
p[keta]='\0';
return p;
}
//a>b:1, a<b:-1, a=b:0
//左が大きいときに1
int comp(char *a,char *b)
{
//マイナスのフラグ
int minA=0,minB=0;
if(a[0]=='-')minA=1;
if(b[0]=='-')minB=1;
//マイナスの符号を取る
if(minA==1)a=convmin(a,1);
if(minB==1)b=convmin(b,1);
char *n1=chartonum(a);
char *n2=chartonum(b);
int keta1,keta2;
keta1=strlen(a);
keta2=strlen(b);
if(keta1>keta2){
if(minA==1)return -1;
return 1;
}else if(keta1<keta2){
if(minB==1)return 1;
return -1;
}
int j=keta1;
while(j>=0){
if(n1[j]>n2[j]){
if(minA==1)return -1;
return 1;
}else if(n1[j]<n2[j]){
if(minB==1)return 1;
return -1;
}
j--;
}
return 0;
}
//マイナスを取り外しする関数
//0:つける, 1:はずす
char* convmin(char* a,int flag)
{
char *p=(char*)calloc(strlen(a)+1+1,1);
if(flag){
for(int i=0;i<strlen(a);i++)p[i]=a[i+1];
}else{
for(int i=0;i<strlen(a);i++)p[i+1]=a[i];
p[0]='-';
}
return p;
}
//0:add, 1:min
//a±b
char* addmin(char *a,char *b,int flag)
{
//マイナスのフラグ
int minA=0,minB=0;
if(a[0]=='-')minA=1;
if(b[0]=='-')minB=1;
if(flag==0){
//足し算で0を対応
if(comp(a,"0")==0||comp(b,"0")==0)return (comp(a,"0")==0)?b:a;
//足し算でマイナスがあり引き算になるときに対応
if(minA+minB==1){
if(minA==1)a=convmin(a,1);
if(minB==1)b=convmin(b,1);
return (minA==1)?addmin(b,a,1):addmin(a,b,1);
}
}
if(flag==1){
//引き算で0を対応
if(comp(a,b)==0)return "0";
//引き算でマイナスがあり足し算になるときに対応
if(minA+minB==1){
if(minA==1)b=convmin(b,0);
if(minB==1)b=convmin(b,1);
return addmin(a,b,0);
}
}
//マイナスの符号を取る
if(minA==1)a=convmin(a,1);
if(minB==1)b=convmin(b,1);
char *n1=chartonum(a);
char *n2=chartonum(b);
int ketas,ketab,keta1,keta2;
keta1=strlen(a);
keta2=strlen(b);
if(keta1>keta2){
ketab=keta1;
ketas=keta2;
}else{
ketab=keta2;
ketas=keta1;
}
//足し算で取り得る最大桁は与えられた最大桁+1にヌル文字分
char *N=(char*)calloc(ketab+1+1,1);
for(int i=0;i<ketab;i++){
if(i<ketas){
if(flag){
//引き算
//ここでは絶対値を出す
N[i]+=(comp(a,b)==1)?n1[i]-n2[i]:n2[i]-n1[i];
}else{
//足し算
N[i]+=n1[i]+n2[i];
}
}else{
N[i]+=(keta1>keta2)?n1[i]:n2[i];
}
//繰り上げ
if(flag){
if(N[i]<0){
N[i+1]--;
N[i]+=10;
}
}else{
if(N[i]>=10){
N[i+1]++;
N[i]-=10;
}
}
}
int keta;
for(int i=ketab+1;i>=0;i--){
if(N[i]!=0){
keta=i+1;
break;
}
}
for(int i=0;i<keta;i++)N[i]+='0';
//最初に'-'を入れる
//足し算でマイナスに対応する
if(flag==0&&((comp(a,b)==1&&minA==1)||(comp(a,b)==-1&&minB==1)))N[keta]='-';
//引き算でマイナスに対応する
if(flag==1&&((comp(a,b)==1&&minA==1)||(comp(a,b)==-1&&minB==0)))N[keta]='-';
return rev(N);
}
//0:tim, 1:div a/b
//0の割り算は対応してない
//割り算はマイナスに対応してない
char* timdiv(char *a,char *b,int flag)
{
//マイナスのフラグ
int minA=0,minB=0;
if(a[0]=='-')minA=1;
if(b[0]=='-')minB=1;
//マイナスの符号を取る
if(minA==1)a=convmin(a,1);
if(minB==1)b=convmin(b,1);
//a<b
if(flag==1&&(comp(a,b)==-1))return "0";
//0の掛け算
if(flag==0&&(comp(a,"0")==0||comp(b,"0")==0))return "0";
char *n1=chartonum(a);
char *n2=chartonum(b);
int keta1,keta2;
keta1=strlen(a);
keta2=strlen(b);
//掛け算の最大桁は桁1+桁2にヌル文字分
int *N=(int*)calloc(keta1+keta2+1,sizeof(int));
if(flag){
//割り算
//temp1は商が一桁になるaから切り取った数
//temp2はbと商をかけてtemp1に一番近くなる値
//temp3はtemp1-temp2であり、次の桁を下ろしてbで割る値
char *temp1,*temp2,*temp3;
int revise;
//商の桁数を出す
int KETA;
for(int i=0;;i++){
char *Z="1";
for(int j=0;j<i;j++){
Z=timdiv("10",Z,0);
}
if(comp(a,timdiv(b,Z,0))==-1){
KETA=i;
break;
}
}
//次に引いた分に割られる数の隣のけたを降ろす。
//割る数で割れるようになるまで降ろす(取り出す)
for(int i=0;i<keta1;i++){
if(i==0){
//まずはbが1桁で割れる分だけaから取り出す。
//最初はbと同じ桁だけ、bより小さいならなら+1桁。
temp1=(char*)calloc(keta2+1,1);
for(int j=0;j<keta2;j++){
temp1[j]=a[j];
}
i=keta2-1;
revise=i;
if(comp(temp1,b)==-1){
temp1[keta2]=a[keta2];
i++;
revise=i;
}
}else{
//後は一桁ずつ降ろしていく
temp3=timdiv(temp3,"10",0);
char Z[2]={};
Z[0]=a[i];
temp1=addmin(Z,temp3,0);
}
//次にbと1~9をかけてギリギリで割れる数を探す。
//そして引く。
for(int k=1;k<10;k++){
char Z[2]={};
Z[0]=k+'0';
temp2=timdiv(b,Z,0);
int COMP=comp(temp1,temp2);
//printf("t1:%s t2:%s t3:%s comp:%d i:%d k:%d\n",temp1,temp2,temp3,COMP,i,k);
if(COMP==-1){
Z[0]=k+'0'-1;
temp3=addmin(temp1,timdiv(b,Z,0),1);
N[KETA-i-1+revise]=k-1;
break;
}else{
if(COMP==0){
temp3=addmin(temp1,timdiv(b,Z,0),1);
N[KETA-i-1+revise]=k;
break;
}
if(k==9){
temp2=timdiv("10",b,0);
if(comp(temp1,temp2)==-1){
N[KETA-i-1+revise]=9;
temp3=addmin(temp1,timdiv(b,"9",0),1);
}
//N[KETA-i-1+revise]=0;
break;
}
}
}
}
//printf("%d,%d,%d,%d\n",N[0],N[1],N[2],N[3]);
}else{
//掛け算
for(int i=0;i<keta1;i++){
for(int j=0;j<keta2;j++){
//ここはNがcharだと127を超えてしまう
N[i+j]+=n1[i]*n2[j];
}
}
//繰り上げ
if(flag){
}else{
for(int i=0;i<keta1+keta2;i++){
if(N[i]>=10){
N[i+1]+=N[i]/10;
N[i]%=10;
}
}
}
}
char *p=inttochar(N,keta1+keta2);
int keta;
for(int i=keta1+keta2;i>=0;i--){
if(p[i]!=0){
keta=i+1;
break;
}
}
for(int i=0;i<keta;i++){
p[i]+='0';
}
//掛け算でマイナスに対応する
if(flag==0&&minA+minB==1)p[keta]='-';
return rev(p);
}
char* ADD(char *p,char *q){return addmin(p,q,0);}
char* SUB(char *p,char *q){return addmin(p,q,1);}
char* MUL(char *p,char *q){return timdiv(p,q,0);}
char* DIV(char *p,char *q){return timdiv(p,q,1);}
//余り
//a%b
char* AMARI(char *a,char *b)
{
char *sho=DIV(a,b);
char *seki=MUL(sho,b);
char *amari=SUB(a,seki);
return amari;
}
//べき乗
//a^b
char* POW(char *a,char *b)
{
char *p="1";
while(1){
p=MUL(p,a);
b=SUB(b,"1");
if(comp(b,"0")==0)break;
}
return p;
}
//べき乗。高速ver, 余りあり
char* POW2(char *a,char *b, char *c)
{
if(b[0]=='0')return "1";
char *p="1";
char *q=DIV(b,"2");
char *r=AMARI(b,"2");
p=POW2(a,q,c);
p=MUL(p,p);
if(r[0]=='1')p=MUL(p,a);
if(c[0]!='n')p=AMARI(p,c);
return p;
}
//素数判定(文字列受取)
//2桁だけ素因数分解も表示
//最初はこれでnからp,qを求めようと思っていたが、無事メモリを使い果たしてなぜか別プロセスのchromeまで落ちた。
int judgeprime(char *p)
{
if(comp(p,"1")==0)return 0;
char *I="2";
while(1){
if(I[0]=='1')puts(I);
char *sho=DIV(p,I);
char *seki=MUL(sho,I);
char *amari=SUB(p,seki);
//printf("i:%s 商:%s 積:%s 余り:%s\n",I,sho,seki,amari);
if(comp(amari,"0")==0){
//printf("p:%s, q:%s\n",I,sho);
return 0;
}
if(strcmp(I,"2")==0){
I=ADD(I,"1");
}else{
I=ADD(I,"2");
}
if(comp(I,DIV(p,"2"))>=0){
break;
}
}
return 1;
}
//ax+by=dをユークリッド互除法を用いて解く
//dはaとbを足しているため、aとbの最大公約数の定数倍となるはず
//そのためdは答えの一つであるaとbの最大公約数として求める
char* extGCD(char *a,char *b,char *x,char *y)
{
//dが求められた時の処理
if(comp(b,"0")==0){
//ユークリッドの互除法の最後
//yは任意の数ですが、分かりやすくするため0で
x[0]='1';
y[0]='0';
return x;
}
//a=qb+r
char *q=DIV(a,b);
char *r=AMARI(a,b);
//a=qb+rをax+by=dに代入して
//(qb+r)x+by=d
//b(qx+y)+rx=d
//bs+rt=d
//s=qx+y x=t
int keta=(strlen(a)>strlen(b))?strlen(b):strlen(a);
char *s=(char*)calloc(keta,1);
char *t=(char*)calloc(keta,1);
//printf("x=%s, y=%s, s=%s, a=%s, b=%s, t=%s, r=%s, q=%s\n",x,y,s,a,b,t,r,q);
//sとtはまだ求められないから次の関数にまかせる
extGCD(b,r,s,t);
//sとtが求められた後
//x=t y=s-qx=s-qt
if(x[0]=='n'){
x=t;
y=SUB(s,MUL(q,t));
}else{
strcpy(x,t);
strcpy(y,SUB(s,MUL(q,t)));
}
//printf("_______________x=%s, y=%s, s=%s, a=%s, b=%s, t=%s, r=%s, q=%s\n",x,y,s,a,b,t,r,q);
return x;
}
//数字を文字へ
//例：24930=0x6162=0x61,0x62="ab"
char* inttobyte(char *p)
{
char *keta;
char *i="0";
while(1){
char *n16=POW2("16",i,"n");
if(comp(n16,p)<=0&&comp(MUL("16",n16),p)==1){
//16進数の時の桁数
keta=i;
break;
}
i=ADD(i,"1");
}
char *a=(char*)calloc(atoi(keta)+1,1);
i=SUB(keta,"1");
int j=0;
while(1){
if(comp(i,"0")<0)break;
char *n16=POW2("16",i,"n");
char *m=DIV(p,n16);
a[j]=atoi(m);
p=SUB(p,MUL(m,n16));
//printf("a[%d]:%s p:%s n16:%s\n",j,m,p,n16);
i=SUB(i,"2");
j++;
}
return a;
}
int main(void)
{
char *p="2159947535959146091116171018558446546179";
char *q="658558036833541874645521278345168572231473";
char *n="1422450808944701344261903748621562998784243662042303391362692043823716783771691667";
char *e="65537";
char *c="843044897663847841476319711639772861390329326681532977209935413827620909782846667";
char *phi=MUL(SUB(p,"1"),SUB(q,"1"));
char *d,*k;
d=extGCD(e,phi,"n","n");
while(1){
if(comp(d,"0")==1)break;
d=ADD(d,phi);
}
printf("d=%s\n",d);
char *m=POW2(c,d,n);
printf("m=%s\n",m);
m=inttobyte(m);
printf("m=%s\n",m);
return 0;
}
まあいい勉強になりました。
拡張ユークリッド互除法、多倍長整数演算、再帰関数、べき乗、RSA暗号、mod、ポインタ等学べることが多かったです。
あとdは逆行列でも求められるらしいですが、行列は苦手すぎるので無理です。
続く
頑張って理解しようと自分の理解していないところもすべて含めて書いていたらこんなに長くなってしまいました。
編集するとき重くなってきたので次のページに続きを書いていこうと思います。
コメント
0 件のコメント :
コメントを投稿