[Daily AlpacaHack]CTF初心者の勉強記録:Floating Equality

問題ページ:https://alpacahack.com/daily/challenges/floating-equality
これは初心者による初心者のためのwriteup兼勉強記録です！もっと簡潔で分かりやすい解説が読みたい人は他の方のを読みましょう！

メインのコード

import os
import re

EPS = 1e-10
FLAG = os.environ.get("FLAG", "Alpaca{dummy}")


def validated_input(prompt: str) -> str:
    res = input(prompt)
    assert len(res) <= 16
    assert re.fullmatch(r"(?:0|[1-9][0-9]*)\.[0-9]{1,9}", res)
    return res


x_str = validated_input("value> ")
x = float(x_str)

xe9 = float(f"{x_str}e9")
x_1e9 = x * 1e9
err = abs(xe9 - x_1e9)

print(f"{xe9 = :.100g}")
print(f"{x_1e9 = :.100g}")
print(f"{err = :.100g}")

try:
    assert err < EPS
except AssertionError:
    print(f"FLAG: {FLAG}")

やってること(ざっくり)

1. 16文字以内 & 小数部分が1~9桁以内の小数xを入力
2. xe9にfloat(x*10^9)、x_1e9にfloat(x)*10^9を代入
3. xe9とx_1e9の誤差が10^-10以上ならフラグゲット

ne9=n*10^9
※xe9は正確にはxにe9という文字列を結合したものをfloatに変換している

解き方

• 丸め誤差を起こしてerr>=EPSにすることがフラグがもらえる
• xe9はxを10^9倍して整数にしてからfloat型にしているので誤差が出ない(小数部分は9桁以内なので10^9倍すれば必ず整数になる)
• x_1e9はxをそのままfloat型に変換してしまっているので誤差が生じてしまう、それに10^9を掛けた結果も丸めるのでさらに誤差が出る
• 適当に数で誤差が出るか試してもよいしこのようなプログラムを動かして探してもよい

EPS = 1e-10
for a in range(0, 100000000):
    for b in range(1, 1000000000):
        x_str = f"{a}.{b:09d}"
        if len(x_str) > 16:
            break
        x = float(x_str)
        xe9 = float(f"{x_str}e9")
        x_1e9 = x * 1e9
        if abs(xe9 - x_1e9) >= EPS:
            print(f"found: {x_str}")
            break

• すると0.000976564,1.000000001,2.000000002などが見つかるのでそれを入力すればフラグが手に入る

なぜ誤差が出るのか

• 10進数の小数を2進数で表そうとすると循環小数になってしまうことがある(例:0.1を2進数で表そうとすると0.0001100110011...となってしまう)
• 循環小数や桁の長い小数をfloat型に収めるためには桁を削る必要があり、その際に誤差が生じてしまう、これを丸め誤差という

例:1.000000001の場合

• xe9:1.000000001e9=1000000001ときれいな整数になるのでfloat型にしても誤差は出ない
• x_1e9:小数を2進数で表すことになるので誤差が発生(1回目)(float(1.000000001)=1.000000001000000082740370999090...)
  10^9を掛けた結果もまた小数なのでここでも誤差が発生(2回目)
  (float(1.000000001*1e9)=1000000001.00000011920928955078125...)