picoCTF全部解く(解きたい)

未分類

01 /08 2022

picoCTFのpicoGYM(過去に出題された問題)をポイントの少ない(基本的には難易度低)ものから解いていくチャレンジ
CTF超初心者なので、他のwriteupより冗長に丁寧に書くことを心がけます。
現在17問完了。(2022/1/8)
私の環境は一般的なWindows10 LaptopにWSL(Windows Subsystem for Linux)を入れたものです。

■Obedient Cat(G,5)
ダウンロードできるファイルは拡張子がありませんが、メモ帳で開くことができます。
開くと、平文でflagが書かれていることが分かります。

■Mod 26(C,10)
ROT13という文字の変換をするとflagを獲得できます。ググると変換できるサイトがあるので、使うと速いと思います。
https://dencode.com/ja/cipher/rot13 こことか。

■Python Wrangling(G,10)
pythonコード(ende.py)の中身をみると、コマンド-e もしくはコマンド-dで実行させることで何かしらの処理がされることが分かります。
if文の中をみると、encryptとかdecryptとか書いてあるので、それぞれ暗号化と複合化のコマンドなのではないかと予想できます。
ende.pyを実行し、flagファイルをコマンド-dを使って復号化することでflagを取得できます。
入れるべきコマンドは例えば、
python ende.py -d flag.txt.en

■Wave a flag(G,10)
warmというファイルを実行しろと言われるのでlinux上で実行します。
ただし、linuxファイルにはpermissionという概念があり、ただ単純に./warmで実行するだけではpermission deniedが返ってきます。
(考えてみればWindowsにもありますね)
permissionの概念に関しては
https://qiita.com/takuyanin/items/18590600d077df707923
が詳しいです。分かりやすく載っています。
picoCTFの方のヒントだけ読むと何がなんだかわかりませんが、とにかくchmodコマンドを使ってpermissionの権限を変えると実行できるようになります。

nyan-picoctf@webshell:~$ chmod +x warm
nyan-picoctf@webshell:~$ ls
README.txt unko warm
nyan-picoctf@webshell:~$ ./warm
Hello user! Pass me a -h to learn what I can do!
nyan-picoctf@webshell:~$ ./warm -h
Oh, help? I actually don't do much, but I do have this flag here: picoCTF{b1scu1ts_4nd_gr4vy_755f3544}
nyan-picoctf@webshell:~$

■Information(F,10)
jpgファイルにはExifという情報があります。
linux上でjheadというコマンドを使うとみることが出来る………のですが、
それを使ってみてもよく分からず、眠かったので諦めてkusuwadaさんのwriteupを読みました。後はこちらから。
https://tech.kusuwada.com/entry/2021/04/08/121205

10点問題でも、もうそういう事するのか…。はい、、、精進します。

■Nice netcat...(G,15)
与えられたコマンドをlinux上で実行すると、
3桁までの数字がたくさん出てきます。
ヒントの通り、これらはASCIIコードを表していて、それぞれの数字に対応する文字があります。
対応表に基づき、数字を文字に変換していくとflagがゲットできます。
もしくは、下記のようなコードを書けば一発で出てきます。
https://wandbox.org/permlink/jTP97qZz8G2asTtN

■Transformation(R,20)
慣れていないと分かりにくいですが、
encはencordの略、ということでエンコードされたflagの文字列を表しています。
txtファイルで開くとよく分からない文字列が出てきていますが、問題文を読むと、flag[]から何らかの変換を受けて生成されたことが分かります。

これに対応した逆変換をかけることで、flagが生成できます。(要追記)
https://wandbox.org/permlink/ENGwjdGX02HHCQc8

https://tsalvia.hatenablog.com/entry/2021/04/08/110000

■Stonks(B,20)
I decided to try something noone else has before.
I made a bot to automatically trade stonks for me using AI and machine learning.
I wouldn't believe you if you told me it's unsecure! (と共にvuln.cが添付されている)
ということで、完全な死亡フラグっぽい文章があります。その通りで、このプログラムはsecureではありません。

一応実行してみると、1と2を選べと言われて、2を選ぶと即終了、1を選ぶと
What is your API token?　と聞かれ、何かしらの入力をすると、それに応じて株が買われる仕組みに見えます。
(ここの例では"ako"と入力している)

～～～～～～～～～～～～～～
What would you like to do?
1) Buy some stonks!
2) View my portfolio
1
Using patented AI algorithms to buy stonks
Stonks chosen
What is your API token?
ako
Buying stonks with token:
ako
Portfolio as of Sat May 29 18:48:12 UTC 2021

2 shares of QFRC
3 shares of QQ
40 shares of YT
112 shares of YU
60 shares of P
120 shares of D
102 shares of O
35 shares of A
544 shares of NMT
Goodbye!
～～～～～～～～～～～～～～

一度購入するとそのまま終了するので、1を選んで購入した株はそれ以降見ることが出来ません。
(1を入力し購入して、その次の実行で2を選んでも何も出てこない)

よく分からないですが、
1か2を入力、1を入力した場合に何かを入力、の部分しか悪さを出来る部分が無いので、この2つのどちらかがキーとなる可能性がある、程度に思っておきます。

ソースコードは149行あり、すこし長い感じがします(競プロ視点)が、main関数から見ていきます。
(私が調べたことをつらつらと書いただけで、main関数に書いてあることは、問題の本質になんの関連もありません)

〇122行目 setbuf(stdout,NULL)->バッファを使用しない設定にしている =
https://bg1.hatenablog.com/entry/2019/03/04/210000
https://daeudaeu.com/fflush/

〇123行目 srand(time(NULL))->乱数生成の準備

〇124行目 Portfolio型変数(へのポインタ変数)を宣言初期化条件はinitialize_portfolio()
Portfolio型変数は、structを用いて15行目から18行目で宣言されている。
Portfolio型変数は、内部にint moneyとStonk *headを持ち、さらにこのStonkもstructを用いて9行目から13行目で宣言されている。

Stonk型変数は、内部にint shares とchar symbol[MAX_SYM_LEN + 1]、さらにstruct Stonks *nextを持つ(自己参照構造体)。
自己参照構造体:http://www9.plala.or.jp/sgwr-t/c/sec15-5.html
(この問題において1ミリも重要でないので未読)

initialize_portfolioは「Portfolio型変数へのポインタ」　型の返り値を持つ関数。
中身は、Portfolio型に必要なだけメモリ領域を確保し、moneyに1-2018の適当な値を、headはNULLとした(何も株を持っていない状態)変数pを出力するもの。

もしここで確保できなかった場合main関数の125行目から128行目でエラー出力をして終わる(基本起こらない)。

〇130行目から142行目
実際に実行した時にも表示される「1か2を選択して、それに応じた処理をする」の部分。
1を押すとbuy_stonks(p)が実行され、2を押すとview_portfolio(p)が実行されるようになっている。

(main関数おわり)

次に、buy_stonks(p)の中身を見ていきます。62行目から100行目で記述されています。
63行目から65行目はpのメモリに何も値が入ってなかった時用のエラー出力。

66行目からがキーポイントで、まずchar api_buf[FLAG_BUFFER]が宣言されています。
まさに、フラグ文字列を入れるための変数であることを意味しており、臭います

67行目でFILE変数に読み込み専用モード(r)でapiファイルを展開して、
72行目でapi_bufにその内容を書き込んでいます。

すなわち、このapi_bufの中身が分かればフラグゲットです。

74行目から85行目ではお金が無くなるまで何かしらのアルゴリズムで株を選んで買っていることが分かります。
(randって文字が見えるので多分適当です)
ただ、それだとすると、この次の入力で何をしているのかが謎です。

89行目でuser_buf変数を301バイト分確保し、90行目から93行目では、scanfでuser_bufに文字を入れ、そのままprintfで出しているだけに見えます。
ただ、ここで気づくのは、printfのフォーマット指定子が全くないことです。
違和感があるので調べてみると"Format String Bug"というものが存在することが分かります。

Format String Exploitを試してみる- CTFするぞ https://ptr-yudai.hatenablog.com/entry/2018/10/06/234120

>>printfは"%s"や"%d"のようなフォーマットを見つけると，スタックから順番にデータを読み込んで処理します．したがって，bufに"%x%x%x"のような文字列が入っていると，スタック上のデータが表示されてしまいます．これがFormat String Bugと呼ばれる脆弱性なのですが，このようにスタック上のデータを漏洩してしまうだけでなく，スタック以外でもメモリ上のデータを漏洩，改竄することが可能になります．
だそうです。

そこで、
～～～～～～～～～～～～～～～～～～～～
AAAA%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x%x
Buying stonks with token:
AAAA9b373d0804b00080489c3f7f55d80ffffffff19b35160f7f63110f7f55dc709b3618019b373b09b373d06f6369707b465443306c5f49345f74356d5f6c6c306d5f795f79336e3463646261653532ff85007df7f90af8f7f6344060aabe0010f7df2be9f7f640c0f7f555c0f7f55000ff854b78f7de358df7f555c08048ecaff854b840f7f77f09804b000f7f55000f7f55e20ff854bb8f7f7dd50f7f5689060aabe00f7f55000804b000ff854bb88048c869b35160ff854ba4ff854bb88048be9f7f553fc0ff854c6cff854c64119b3516060aabe00ff854bd000f7d98f21f7f55000f7f550000f7d98f211ff854c64ff854c6cff854bf410f7f55000f7f7870af7f900000f7f5500000118e1a9ea8047c8e000180486300f7f7dd50f7f78960804b00018048630080486628048b85
Portfolio as of Sat May 29 21:54:15 UTC 2021

1 shares of STY
1 shares of AIDB
13 shares of L
2 shares of R
4 shares of VNA
395 shares of A
816 shares of GL
Goodbye!

^C
～～～～～～～～～～～～～～～～～～～～
のように入力すると、%x指定子のおかげでスタックに入っているものが全部出てきます。
(%xは整数を16進数で出力してくれるので、整数が入っていればそのまま、char型の何かが入っていれば文字コードとして返してくれます)

フラグのフォーマットはpicoCTF{...}だったので、
p->0x70 i->0x69 c->0x63 o->0x6F
から始まる文字列がないかを探すと、、、
6f636970を含む部分があります。エンディアンの関係で順番が逆になっているのでした。

ここから始まる部分をASCIIコード変換してあげるとフラグゲットです。
変換サイトの例:https://www.rapidtables.com/convert/number/hex-to-ascii.html

リトルエンディアンで反転してるのを変換してくれるのないかな？

■Get aHEAD(W,20)
サイトを開くと、謎のBlueボタンとRedボタンが表示されています。
とりあえずソースを開くと、それぞれGETメソッドとPOSTメソッドが行われていることが分かります。

GET/POSTについてはこちらがわかりやすいです。
https://qiita.com/7968/items/4bf4d6f28284146c288f

とりあえずBurpSuiteを使えと言われているので使い方を
https://www.as-lab.net/150713/
このあたりのサイトで見てみます。
このツールはHTTPリクエストの中身を覗いたり改ざんしたり出来るようです。

ただ、パラメータを見ても怪しいところがありません。
はて…というところでヒントを見ると、「選択肢は2つじゃないよ(もっとあるよ)」的なことが書いてあります。
実際にはここでgive upしたのですが、問題のタイトルも加味して考えると、"HEAD"メソッドを試せということのようです。。。分からん。

GETやPOSTとなっているところを直接HEADに書き換えてHTTPリクエストを送ってみると、Responseとして"NAME=flag"というパラメータが返ってきていて、その中にflagがあります。

■Mind your Ps and Qs
問題文の通りRSA暗号を解く問題です。
RSA暗号の概要については https://qiita.com/YutaKase6/items/cd9e26d723809dc85928 がくわしい
ブログ記事を見ながら自習したメモ

問題で与えられるパラメータは下記の通り

Decrypt my super sick RSA:
c: 62324783949134119159408816513334912534343517300880137691662780895409992760262021
n: 1280678415822214057864524798453297819181910621573945477544758171055968245116423923
e: 65537

メモと文字の対応が出来ていないが、c->C, n->N e->Eと読み替えます。
M = C^D (mod N)よりDが求まれば解けます。
DはD = pow(E,-1,φ(N)) = pow(E,-1,(p-1)(q-1))で、
pとqはNを素因数分解した時の2つの素数であるので、問題のキモはNを素因数分解すること。

競プロでよくやる素因数分解のアルゴリズムはO(√N)かかってしまうため、80桁以上の素因数分解には向いていないです。
世の中には
https://wacchoz.hatenablog.com/entry/2019/05/14/205306
http://www.cs.t-kougei.ac.jp/nsim/lecture/2008/ws/QS.pdf
にあるように2次ふるい法というものがあり、このオーダーのNの素因数分解を解けるらしいのですが、実装できず断念しました…

CTF的にはmseiveというツールを用いたり、http://factordb.com/ に入力することで解いてしまうことが多いようです。
(どちらも今回のNの素因数分解が出来る事を確認しました)

msieveで出た結果はこんな感じ。

最後にこの結果を用いて、平文を出しますが、平文が10進数なので16進数に直しASCIIベースで文字に変換すると、答えが得られます。
https://wandbox.org/permlink/bTDAy0ik1WqTn7NP

■Static ain't always noise (General Skills, 20pts)
バイナリファイルの中を見ろと言われます。
また、「このBASH scriptが役に立つよ」と言われるので、併せて落としてみます。
Bash scriptはシェルスクリプトの一種でlinuxで叩くようなコマンド入力を自動化するものと理解しています。

スクリプトの中身を読んでみると、
まずobjdumpコマンド(オプション: -Djと.text)を第1引数のファイルに対して行ったものを (ファイル名).ltdis.x86_64.txtとして出力します。
Bash scriptのコメントアウトにも書いてある通り、objdump -Dコマンドはバイナリファイルの逆アセンブル情報を表示し、
-j .textはテキストセクションのみを表示するオプションです。
(セクションが何なのかよく分かっていない。https://karino2.github.io/c-lesson/casm_link_load.html ここに書いてありそうな予感がします。全然読んでません)
テキストセクションには定数が入っているみたいです。Cでいうmain関数とか。(よく分かっていない)

その後、(ファイル名).ltdis.x86_64.txtが存在すれば、同じファイルに対してstringsコマンドを実施してテキストデータとして出力するように書かれています。
stringsコマンドは、バイナリファイルの中にあるテキスト情報を抜き出して一覧表示してくれるもので、出力結果を見ていくとpicoCTF{から始まる文字列があるので、これでflagゲットです。

★参考になるサイト
https://linuxcommand.net/objdump/
https://qiita.com/rsooo/items/bb91071685f447ce29db

恐らくこれが想定された解法ですが、
直接staticをバイナリエディタで開き、"picoCTF"で検索するだけでも見つかります。

■Tab, Tab, Attack (General Skills, 20pts)
上の問題と大体同じ?

■keygenme-py (Reverse Engneering, 30pts)
https://twitter.com/nya______n/status/1477368424078917632?s=20

■Matryoshka doll(Forensics, 30pts)
https://twitter.com/nya______n/status/1477385736349691904?s=20

■crackme-py(Reverse Engeneering, 30pts)

■Magikarp Ground Mission(General Skills, 30pts)

■tunn3l v1s10n(Forensics, 30pts)

■Easy Peasy(Cryptography, 40pts)
ワンタイムパスワードに関する問題。
opt.pyの中身を見ると、動作は

外部から"key"と"flag"を読み込む keyの長さは50000っぽい？
flagは文字列として、keyは"rb"指定なのでバイナリ(16進数)として取得。
startup動作
- flagの長さ分だけkeyを取ってくる。例えばflagの長さが32ならkeyのうち1文字目から32文字目を取ってくる。
- 19行目にて、resultの中にlistとして『「flagを1文字ずつとったものをバイナリに変換したもの」と「keyを1文字ずつとったもの」のXORをとったもの』を入れていく
- この結果を表示。shell上で下記のように表示される。文字を数えると32文字。(1byte文字が32文字なので、バイナリにすると64文字出力されている。例えば最初の"51"は"Q")
- This is the encrypted flag!
  51466d4e5f575538195551416e4f5300413f1b5008684d5504384157046e4959
encrypt動作(1回目)
- 何か任意の文字列を入力する。= ui
- uiとkeyに対してstartup動作と同様のことを行う。
- ただし、keyは再び最初から使うわけではなく、startupで使用したkeyの次の文字から使う。
- 例えば、startup動作が上記の例だとして、len[ui] = 10なら、ここで使われるkeyは33文字目から42文字目まで。(key[32:42])
- 同様にuiとkeyでXORを取ったものを表示
encrypt動作(2回目以降)
- 同様だが、keyは直前に使ったところの次から使用する。
- (正確には1回目でも起こるが)使用したkeyが50000文字に達すると、(34行目から36行目の記述)にあることが起こる。
- (★)ずっと勘違いしていたのですが、恐らくKEY_FILEの中身は実際には50000文字より長いので、このif文の中身が実行されるとき、実際にはkey[:stop]の部分は出てこないものと思われます。(問題の不備では？？？)
- (★)もう少し具体的に言うと、key_location=49995(つまり49996文字目)のとき、ui = 10の文字列を入力すると、ソースコード上はkey[49995:50000]+key[0:5]が出てくるように見えますが、実際にはlen[key]は50000より長いので、key[49995:50005]の文字が出力されていると思われます。

以上の動作を考慮すると、50000文字分のkeyを正確に消費すれば、次に使うkeyは最初のflagの時に使ったものと同じになるはず。
そのため、encrypt動作にてkeyを50000文字分まで消費した後、既知の文字列をuiとして入力し結果を出力すると、そこから鍵が逆算できます。

ui XOR key = resultですが、
XORの性質よりA XOR B = CならばA XOR C = Bが成り立つため、
ui XOR resultを計算することでkeyを計算できます。

もしくは、
https://tsalvia.hatenablog.com/entry/2021/04/08/110000#Easy-Peasy---40-points
で紹介されているように、直接"0x00"をぶちこむことで、計算しなくても鍵を出す方法があるようです。
つまり、
0 XOR A = Aが常に成り立つので、
0 XOR key = result ならば、 result = keyになるという算段です。

なお、(★)に書いてあるような仕様があるので、
例えば、「"A"を50000文字入力しresultを出して、最後の32文字分を見る」というやり方をすると不正解になります。
最後の32文字はkey[0:32]のつもりが、実際にはkey[50000:50032]が出力されているからです。(KEY_FILEが50000文字を超えていることの弊害。やっぱり問題の不備では…)

ともあれ、keyが分かりました。
最初のstartupでは、
flag XOR key = 51466d4e5f575538195551416e4f5300413f1b5008684d5504384157046e4959
であったので、
flag = key XOR 51466d4e5f575538195551416e4f5300413f1b5008684d5504384157046e4959
です。
これを計算し、最後にASCIIコードから文字列に変換すると32文字の1byte文字が得られます。

スポンサーサイト

Comment - 0 Trackback - 0

ABC169-C問題"Multiplication 3"を通して浮動点小数の扱いを勉強する(とちゅう)

未分類

06 /24 2020

仕事の資料が作り終わらず、やる気が起きず寝ていたらABC169に参加しそびれたのですが、どうやらB問題とC問題で誤答(WA)が連発したようです。
特にC問題では、小数(浮動点小数)を型変換する際に生じる誤差についてキチンと理解していないと間違うというトリッキーな問題でした。

私は翌日起きてからこの問題を解こうとしたら全く解けず絶望したのですが、教育的な問題だと思い、この機会に「何が起きているのか？」を勉強してみることにしました。
また、私含む初心者にとって公式解説の行間はあまりにも空きすぎていると思うので、復習がてらゆっくり理解していくことを目的として、メモを書いていきます。
実は、3月ごろに開催されたコンテストのこの問題も、小数の扱いを理解しないと危ない問題だったのですが、嘘解法でたまたまACしてしまったためあんまり復習していませんでした。反省。こちらも一緒に理解を進めたので、いつか記事にしたいとは思っています。

先に言及しておくと、ABC169-C問題に関しては、結論からいえばpythonなどで有効桁数を非常に大きくした固定小数点を使えば一発で解決します。
そうなると固定小数点で全部やればいいので、浮動小数点について勉強する意味ある？となりそうですが、いろいろな事情からそういうわけにいかないようで、現実様々なところで浮動小数点型が使われているため、やっぱりちゃんと学んだほうがよさそうです。

素人が勉強のために書いているメモなので、誤りを含む可能性が大いにあります。親切に指摘して頂けると大変喜びます。
叩いたり晒し上げたりする/されるよりは、共に学べると良いなと思っています。

■0.999999... = 1?

全然別の話題からスタートしますが、
中学生が循環小数を習ったときにこんな疑問が出てくるはずです。

「1=(1/3) * 3 = 0.333333.... * 3 = 0.999999...」は正しい式なのか？

私含めて多くの人が疑問だったものだと思います。

教えてgoo!にも旧石器時代に質問された形跡があり、古くから共通の疑問だったと思われます。

結論から言うと0.999999... = 1は正しく、ε-N論法のようにして解釈することが出来ます。
(素人なので、説明に誤りがあれば教えてください)

初項a[1] = 0.9
a[n+1] = a[n] + 0.9 * (1/10)^n (n>=1)

となる数列を用意すると、これは
a[1] = 0.9, a[2] = 0.99, a[3] = 0.999, ...
となる単調増加の数列となりますが、
項数を無限に大きくしていくと、その項は0.999999...と同じとみなせます。

ここで、任意の小さい正の数εを用意することを考えます。このとき、
|1 - a[N]| < ε
となるNが絶対見つかるかどうか？を考え、見つかれば、a[N]の極限は1であると解釈できます。
この場合では、実際にどんなεを持ってきても、この不等式を満たすNを取ってくることができます。
例えば0.0000000003742という数を用意したときは、a[10]を用意すれば式を満たします。(もちろんそれ以降の項でもいいです)
もっと大胆にいえば、どんなε(<1)が用意されたとしても、N=floor(1/ε)とすれば、オーバーキルで絶対上記の不等式を満たします。
このことから、a[n]は1に収束する数列であり、項数を無限大に発散させた0.999999... は1と同じである解釈することが出来ます。

この事は直感的でなく、しばらくは納得できないかもしれませんが、これは9が無限に続くから言えることであって、
確実なことは、0.999999...と無限に続かずに、途中で切った場合は絶対に1にならないということです。
「0.999999...は1にならないでしょ」という感覚は、脳内で勝手にどこかの桁で打ち切ってしまうことから出てくる考えだと思われます。

最初の例で0.333333333 * 3と9桁で切ってしまった場合は答えは0.999999999となり、0.000000001の誤差が生じます。
このように、循環小数を人の都合で勝手な桁数で切ると、それを用いた計算結果には誤差が生じることになります。

■2進数の循環小数

さて、循環小数は10進数の世界でなく2進数の世界にもあります。
2進数の世界では、10進数で小数部分が (0or1) * 2^(-1) + (0or1) * 2^(-2) + (0or1) * 2^(-3) + ...と表せない限り循環小数になります。例えば10進数でいう0.1は2進数に直すと
0.0001 1001 1001 1001 1001 1001 1001 1001 1001...と続くようです。

しかしコンピュータサイエンスの世界では、実際のメモリに値を格納しないといけないので、有限の数のメモリに小数を保存しないといけません。そのため、格納できる小数の桁数(2進数の桁数)が決まっています。
例えばfloat型では23bitです*。つまり、循環小数が24桁以上続く場合、それ以降の情報は落とさないといけません。
循環小数を人の都合で勝手な桁数で切ると、それを用いた計算結果には誤差が生じることから、これを使った計算には誤差が発生します。
(循環小数でなかったとしても、2進数で表したときに24桁以上になるような数を扱う際には、同様のことが発生します)

*
float型をはじめ多くの浮動小数点型では、全ての小数を
1.xx * 2^(yy)
の形にしてxxの部分とyyの部分を記憶することを行います。
ここで、整数部分は絶対に1になるように変形するとルールが決められているようなので(ケチ表現というらしい)、この1をメモリに保存する必要はなく、この1を除いた23bitを保存します。そのため有効数字は24桁あるようです(2進数の24桁です)
たとえば、10進数でいう0.275は2進数で0.011と表されますが、これを(10進数では2.75*10^1と表すのと同様にすることで)1.1*2^(-2)のように表したとき、実際に整数部分の1は情報として持つ必要がないということです。この場合小数第1位の"1"と指数の肩の"2"さえ覚えておけば、1.1*2^(-2)のデータを格納することが出来ます。

環境・定義によってあらわせるbitの数は異なるようですが、今回は下記wikipediaのリンク先にある"IEEE 754 での単精度浮動小数点数の形式: binary32"の環境を前提とします。私の環境でもfloatを使うとこうなるので。他の環境のことは知りません
floatの表し方のフォーマットはwikipediaなどを参照

さて、例えば0.1(10進数)をfloatに格納することを考えます。
c++でいえば、float val = 0.1; としたときの動作です。
(実際にやった例)

前述の通り0.1(10進数)を2進数に変換すると
0.1 = 0. 0001 1001 1001 1001 1001 1001 100(1 1001 1001 ...)
ですが、動作の定義上、実際には最初の1が出たbit(青文字)の次のbitから23bitぶん(最初の1は保存しなくてよい)、floatデータへ格納されます。
この時点では

1.1001 1001 1001 1001 1001 100 * 2^(-4)

のように保存されているはずです。
次に、カッコ内の部分はfloatには格納しきれないbitです。この部分に関しては切り捨てや切り上げなどの丸め処理がなされます。
恐らく言語や環境によって違うのでしょうが、私の環境では赤文字のbit(格納できないbitのうち一番大きな桁)を見て、0なら切り捨て、1なら切り上げ(切り上げたら1個左のbitを1増やす)の処理がなされます。(いわゆる0捨1入)

1.1001 1001 1001 1001 1001 101 * 2^(-4)

これで処理は終了です。実際には2進数のこの値がメモリに格納されています。
見てきてわかるように、カッコ内を切り捨てるかわりに、その左のbitを1増やしてしまうので、トータルでみると真の数に比べて格納した数は大きくなってしまっています。

実際に0.1をfloatに格納し、それを10進数に直すと実際にやった例のようになります。ぴったり0.1ではない、0.1より少し大きな数が出力されているのが分かります。
また、ここでは無理やり小数第35位まで表示させていますが、小さな数を表すbit(さっきの説明でいうとカッコの中にあったbit)は全て丸め処理をされて0になっているので、途中の桁からは全て0が出力されるのが分かります。

さて、ここで出てきた数字0.100000001490116119384765625と、真の数0.1との差の絶対値が誤差です。
今回は切り上げの場合を考えましたが、切り捨ての場合も同様に考えることが出来、この場合は真の値より小さい値が出ることになります。

■ 丸め処理をした時の誤差はどのくらい？

いろんな数をfloatに格納した場合、相対誤差の大きさは最大どのくらいでしょうか？
1.xx * 2^(-yy) のフォーマットで表したとき、仮数部分(1.xxの部分)の2^(-24)桁(小数第24位)以降の情報が無くなりますが、
たとえば真の数の仮数部分が
1.0000 0000 0000 0000 0000 0001
と表される場合、これに切り上げ処理を行うと
1.0000 0000 0000 0000 0000 001(0)
となります。(カッコ内はfloatのbitに格納されない)

このようなとき、つまり切り上げ処理を行った仮数部から真の数の仮数部を引いて
0.0000 0000 0000 0000 0000 0001
となるときに相対誤差は最大となります。大きさは2^(-24)です。

切り捨て処理をしたときの相対誤差の最大も同じように考えることが出来、最大2^(-24)の誤差が生じえます。
普通に小数を計算するときは、それがイチイチ切り捨てられるか切り上げられるかが分からないので(普通はそう)、±2^(-24)の誤差を認めて計算をしないといけないと理解できます。

言い換えると、

任意の数Fをfloatに入れたとき、floatに入れた値は
F*(1-2^(-24)) から F*(1+2^(-24))の値のどれかを取る

といってもいいと思います。
2^(-24)は6*10^(-8)程度の値であり、
「float型では有効数字は7桁程度」というのは恐らくここからくる話でしょう。

逆に、
floatに入っている数がF'のとき、
真の数は大体
F'*(1-2^(-24))からF'*(1+2^(-24))の間くらいにある
と言ってもいいような気はします。正確ではないとは思いますが。

以上が、floatに格納した際の誤差についての理解です。

さて、ここまではずっとfloatの例をずっと続けてきましたが、
doubleでは仮数部が52bitのためケチ表現を加え、2進数で53桁の有効数字を持ちます。
同様の議論をすることで相対誤差の最大は2^(-53)≒1.1×10^(-16)。
c++かつgccの場合(AtCoderのc++はそうです)、long doubleを使うと仮数部64bitが使用可能のようです。
このlong doubleにはどうやらケチ表現は使われないようなので、有効数字は65桁ではなく64桁(これも2進数)です。
これも同様に考えることで相対誤差の最大は2^(-64)≒5.4×10^(-20)です。

■ABC169　C問題の2つのトラップ

やっと本題ですが、この問題には小数の扱いに関して2段階のトラップがあります。
1つ目はfloat,doubleを使うことによる有効桁数の不足で、
2つ目は小数を整数型へキャストする際に生じる切り捨てによって起こる誤差です。

どちらも本質的には「長く続く小数(循環小数に限らない)を勝手に有限のbitしか保存できないメモリに入れることで起こる誤差」から来るものだと(私は)理解していますが。

■ABC169 C問題トラップ1 float,doubleを使うことによる有効桁数の不足

C問題では0以上10^15以下の整数A(有効数字は最大15桁)と0以上10未満の小数B(有効数字は最大3桁)を掛け算します。
掛け算した結果、有効数字は最大18桁となります。
例えば999 9900 0000 0001*9.99を考えましょう(ちなみにこれはテストケースのhand_01と同一です)。
この結果は正確には9989 9001 0000 0009.99‬=9.9899 0010 0000 0099 9*10^15‬‬です。
(つまり、このテストケースでは9989900100000009と出力しなくてはなりません)。

仮に上記の計算が正確に出来たとしましょう。(ナイーブに実装するだけでは実際には正確に行うことが出来ません。後で言及します)
この正確な計算結果9.9899 0010 0000 0099 9*10^15をdoubleに格納することを考えます。

上述の議論から、doubleに格納した時点で1.1*10^(-16)程度の相対誤差が生じるので、
だいたい9.99*10^15*1.1*10^(-16)≒1.1の絶対誤差が発生しうることになります。
積の整数部分をこたえなくてはいけない問題なのに1程度の絶対誤差が発生するということは、
誤った答えが出る可能性が大いにあると理解できます。

ちなみに、実際に1程度の誤差が出ることが確かめられます(1行目の結果を参照。下3ケタが099ではなく100となってしまっています)。

1.1*10^(-16)の相対誤差が生じうるdoubleでさえこの結果なので、
6*10^(-8)程度の相対誤差が生じうるfloatでは論外の結果が出てくることは想像できます。
上記のリンクの出力2行目はfloatに9.9899 0010 0000 0099 9*10^15を格納した結果です。

さらに実はそれ以前の問題があって、
999 9900 0000 0001*9.99
は、9.99をdoubleに格納して計算しようとする時点で正確に計算することは出来ていません。
9.99をdoubleに格納するときも誤差が発生するからです。

よって、例えば



long a = 999990000000001;
double b = 9.99; //1つ目
cout << (long)(a*b); //2つ目

としようものなら、2段階で誤差が発生していることになります。(今まで説明していたのは2番目の誤差のこと)

もっと精度の高い浮動小数点型(long doubleなど)を使う事ができれば2つ目の誤差は回避できそうですが、
1つ目の誤差は有限精度の浮動小数点型をそのまま使うだけでは、どんな精度のものを使っても解決することができません。
(long doubleを使っただけの例)

上記のコードでWAを出しているケースの中身は
A=776013196293085, B=2.60　(after_contest_01)
です。

本来の計算結果(積)は2017 6343 1036 2021となり、整数になるはずです。
しかし、Bを浮動小数点型に格納すると、切り捨てまたは切り上げが起こり2.60より少しだけ異なる値が保存されます。
(2.6 = 2.5 + 0.1と考えれば、2.5は2進数の有限小数で表せ、かつ0.1は上記の例があるので分かりやすいでしょうか。)

切り上げで保存してくれればまだ良いのですが、切り捨てたときが最も悪さをするケースです。
正確に2.6と保存してほしいところを2.6よりちょっと小さい数を保存してしまうことになり、
正確には積は2017 6343 1036 2021となるところが、2017 6343 1036 2021よりちょっと小さい数(+誤差)が結果として出てきます。そして小数点以下を切り捨てると、下2桁が21ではなく20となってしまう、ということです。

結局のところ、浮動小数点型を使わないで計算する必要がありそうです。
出来る方法としては、安全にBを整数に変換して、整数の掛け算として処理するか、
任意精度で計算できるdecimal型(pythonなど)を使って、正確にA*Bを計算する方法がありそうです。
前者の方法をメインに考えますが、「安全にBを整数に変換する」ためにもう少し考える必要があり、ここが2番目のトラップです。
後者の方法は全く別物なので、あとから補足だけします。

((20200624 0:26 ここまで。)

■ABC169 C問題トラップ2 小数を整数型にキャストすることによる誤差

Comment - 0 Trackback - 0