2020年 3/14(土)9:00 - 3/19(木)9:00 JST で開催された、ångstromCTFのCrypto分野の復習です。CTF Timesはこちら。
他の分野のwriteup, 戦績はこちら。
Crypto問最後の Lo-Kee はなんかヤバそうな匂いがしたのと、それまでのやつで力尽きたので手つかずです。
[Crypto] Keysar
Hey! My friend sent me a message... He said encrypted it with the key ANGSTROMCTF.
He mumbled what cipher he used, but I think I have a clue.
Gotta go though, I have history homework!!
agqr{yue_stdcgciup_padas}
これ、競技中に力技で解いたのですが、他の方のwriteup見ると "Keyed Caesar Cipher" というやつだったみたいです。
文字マップがアルファベット順ではなく、与えられたキーの文字列から始まる文字列+キーに含まれないアルファベットはその後に続く。例えば、keyがTESTKEY
だとすると、マップはTESTKEYABCDFGHIJLMNOPQRUVWXZ
となる。
下記のページで復号可能。
[Crypto] one time bad
My super secure service is available now!
Heck, even with the source, I bet you won't figure it out.
nc misc.2020.chall.actf.co 20301
server.py
が配布されます。
import random, time import string import base64 import os def otp(a, b): r = "" for i, j in zip(a, b): r += chr(ord(i) ^ ord(j)) return r def genSample(): p = ''.join([string.ascii_letters[random.randint(0, len(string.ascii_letters)-1)] for _ in range(random.randint(1, 30))]) k = ''.join([string.ascii_letters[random.randint(0, len(string.ascii_letters)-1)] for _ in range(len(p))]) x = otp(p, k) return x, p, k random.seed(int(time.time())) print("Welcome to my one time pad service!\nIt's so unbreakable that *if* you do manage to decrypt my text, I'll give you a flag!") print("You will be given the ciphertext and key for samples, and the ciphertext for when you try to decrypt. All will be given in base 64, but when you enter your answer, give it in ASCII.") print("Enter:") print("\t1) Request sample") print("\t2) Try your luck at decrypting something!") while True: choice = int(input("> ")) if choice == 1: x, p, k = genSample() print(base64.b64encode(x.encode()).decode(), "with key", base64.b64encode(k.encode()).decode()) elif choice == 2: x, p, k = genSample() print(base64.b64encode(x.encode()).decode()) a = input("Your answer: ").strip() if a == p: print(os.environ.get("FLAG")) break else: print("Wrong! The correct answer was", p, "with key", k)
指定されたホストにつなぐと、こんな感じ。
$ nc misc.2020.chall.actf.co 20301 Welcome to my one time pad service! It's so unbreakable that *if* you do manage to decrypt my text, I'll give you a flag! You will be given the ciphertext and key for samples, and the ciphertext for when you try to decrypt. All will be given in base 64, but when you enter your answer, give it in ASCII. Enter: 1) Request sample 2) Try your luck at decrypting something! > 1 LRoJBQcOIQs5CyUPEBEDGCMjLiEeCjcDMRMkLTo= with key eXF4S3NLWERRTVRGWUJQc2VKbHFNZEZUQXBDeGo= > 1 OhIkHgocAAoDAw4VEjgeMAw/Ngo4JA== with key anBtd2ZxbWFZaktndHlRanptR011cQ== > 1 LyoU with key anJx > 2 Fg== Your answer: test Wrong! The correct answer was G with key Q
問題のタイトルとソースコードから、random.seed()
が接続後に一度しか呼ばれていないことに起因する、random配列が予測できるところが脆弱っぽい…?
choice = 1
を選択したときは、genSample()
関数内でrandom.randint
を3回呼んでいる。ここで生成したx,p,k
は、x,k
が出力として返され、p
はx xor k
で求めることができる。
choice = 2
を選択したときは、与えられたx
に対してp
を予測し、答えを入れるとflagが表示されるみたい。間違えてもp
とk
を教えてくれる。
- まずは
random.randit()
の配列を抽出する randit()
配列を予想する
これで行けないかなー?pythonのrandom()
関数の予測は
Mersenne Twisterの出力を推測してみる - ももいろテクノロジー
こちらの記事を以前読んだことがありました。
これを参考に、624回rand
関数が呼ばれたら、その後のrand
関数で生成される関数は予測できそう…。
と思ったんだけど、getrandbits(32)
以外の関数・引数だと一致しない。うーむ。
ここで競技終了。
ここから復習
いくつかwriteupを読んでみたところ、2つの解法を見つけました。難しく考えすぎていたか。
random
のseed
がtime
ベースなので、ほぼ同時接続して通信させるk
が特定の一文字になる確率が高いことを利用したbrute-force- 比較的レンジが絞られているseedを、Sampleで得られた
x,p,k
から予測する
せっかくなので全部やってみることにしました。
1.randomのseedがtimeベースなので、ほぼ同時接続して通信させる
random関数のシードがrandom.seed(int(time.time()))
と、int
で丸めることによって秒単位になった時刻を使っているので、ほぼ同時に接続した通信では同じseedが使用されます。結果、random関数で生成される値も同じになるはずなので、失敗して送られてきた正解をそのまま投げつければ良さそう。
これは思いつきたかったなー!!!!!!
#!/usr/bin/env python3 # -*- coding:utf-8 -*- from pwn import * host = "misc.2020.chall.actf.co" port = 20301 r1 = remote(host, port) r2 = remote(host, port) r1.recvuntil(b'> ') r1.sendline(b'2') cipher1 = r1.recvuntil(b': ').split(b'\n')[0] r1.sendline(b'dummy') res = r1.recv() ans = res.split(b' ')[5] key = res.split(b' ')[8] r2.recvuntil(b'> ') r2.sendline(b'2') cipher2 = r2.recvuntil(b': ').split(b'\n')[0] if cipher1 == cipher2: r2.sendline(ans) print(r2.recvall()) else: print('wrong cipher! c1: ' + cipher1 + ', c2: ' + cipher2)
実行結果
$ python solve.py [+] Opening connection to misc.2020.chall.actf.co on port 20301: Done [+] Opening connection to misc.2020.chall.actf.co on port 20301: Done [+] Recieving all data: Done (56B) [*] Closed connection to misc.2020.chall.actf.co port 20301 b'actf{one_time_pad_more_like_i_dont_like_crypto-1982309}\n' [*] Closed connection to misc.2020.chall.actf.co port 20301
2.k
が特定の一文字になる確率が高いことを利用したbrute-force
一つは、genSample()
関数内でランダムに生成しているp
,k
の長さが1~30
であり、候補の文字列もlen(string.ascii_letters) = 52
程度であることから、1/30 * 1/52 = 1/1560
の確率でk
が特定の一文字になります。なので一文字でbrute-forceをすれば試行回数が少なく結果が得られそう、というもの。
#!/usr/bin/env python3 # -*- coding:utf-8 -*- import string from pwn import * host = "misc.2020.chall.actf.co" port = 20301 print(len(string.ascii_letters)) r = remote(host, port) cnt = 0 while True: print('cnt: ' + str(cnt)) r.recvuntil(b'> ') r.sendline(b'2') r.recvuntil(b': ').split(b'\n')[0] r.sendline(b'a') res = r.recvline() if b'actf{' in res: print(res) break else: cnt += 1 continue
実行結果
$ python solve2.py 52 [+] Opening connection to misc.2020.chall.actf.co on port 20301: Done cnt: 0 ~(中略)~ cnt: 109 cnt: 110 b'actf{one_time_pad_more_like_i_dont_like_crypto-1982309}\n' [*] Closed connection to misc.2020.chall.actf.co port 20301
わーお!期待値を大幅に下回る110回目の思考でflagが手に入りました。ラッキー!
3.比較的レンジが絞られているseedを、Sampleで得られたx,p,k
から予測する
x,p,k
の生成アルゴリズムが公開されていること、randomとは言え時刻ベースのseedを使っているので、seedのレンジがある程度予測できることから(サーバーの時刻が大きくずれていなければ)、seedをlocalのbrute-forceで予測し、次のx,p,k
を生成する解法。
#!/usr/bin/env python3 # -*- coding:utf-8 -*- import string import base64 from pwn import * def otp(a, b): r = "" for i, j in zip(a, b): r += chr(ord(i) ^ ord(j)) return r def genSample(): p = ''.join([string.ascii_letters[random.randint(0, len(string.ascii_letters)-1)] for _ in range(random.randint(1, 30))]) k = ''.join([string.ascii_letters[random.randint(0, len(string.ascii_letters)-1)] for _ in range(len(p))]) x = otp(p, k) return x, p, k host = "misc.2020.chall.actf.co" port = 20301 print(len(string.ascii_letters)) r = remote(host, port) cnt = 0 r.recvuntil(b'> ') r.sendline(b'1') res = r.recvuntil(b'> ') x = base64.b64decode(res.split(b' ')[0]).decode() k = base64.b64decode(res.split(b' ')[3]).decode() p = otp(x, k) for t in range(int(time.time())-20, int(time.time())+20): random.seed(t) my_x, my_p, my_k = genSample() if my_k == k: print('seed: ' + str(t)) break next_x, next_p, next_k = genSample() r.sendline(b'2') r.recvuntil(b': ') r.sendline(next_p) print(r.recvline())
実行結果
$ python solve3.py 52 [+] Opening connection to misc.2020.chall.actf.co on port 20301: Done seed: 1586233716 b'actf{one_time_pad_more_like_i_dont_like_crypto-1982309}\n' [*] Closed connection to misc.2020.chall.actf.co port 20301
わー!こんなに色んな解法があるのに一つも思いつかなかったとは!面白いなー。
[Crypto] Discrete Superlog
You've heard of discrete log...now get ready for the discrete superlog.
Server 1:
nc crypto.2020.chall.actf.co 20603
Server 2:
nc 3.234.224.95 20603
Server 3:
nc 3.228.7.55 20603
Hint
just do it lmao
それぞれのサーバーに接続してみます。全部同じような文言が出てきました。Serverがたくさんあるのは予備かな?
$ nc crypto.2020.chall.actf.co 20603 We define a^^b to be such that a^^0 = 1 and a^^b = a^(a^^(b-1)), where x^y represents x to the power of y. Given this, find a positive integer x such that a^^x = b mod p. Generating challenge 1 of 10... p = 723016406727943930447 a = 564447721002380463960 b = 642755755056058439913 Enter x:
これも競技中に、当てずっぽうと力ずくで解いたのですが、writeupを見ておさらい。
この問題、自分のwriteupにも書いたとおり
a^(a^^(x-1))....
と展開していって、x-1 -> 0
になるまで繰り返し、その結果がb mod p
になるようなx
を求める。
となります。この計算のことを"テトレーション"と呼ぶらしい。
テトレーション(英: tetration)とは、冪乗の次の 4 番目のハイパー演算である。つまり、自らの冪乗を指定された回数反復する二項演算である。超冪(ちょうべき)ともいうが、この語は n ≥ 4 番目の一般のハイパー演算を総称するために用いられることもある。
ほえー!知らなかった。
数学はちゃんと勉強したこと無いので、数式の中に とか出てきたら「アゲアゲ?」ってなっちゃうな…。
べき乗(冪乗)は
それに対して、テトレーションは
と展開できます。なので、今回の問題を数式にして表現すると、
となるx
を求めよ、という問題らしい。
普通にtetrationの値を求めようとすると、再帰を用いて
def tetration(a, x): if x == 0: return 1 else: return pow(a, tetration(a, (x-1)))
のように実装できます。しかしこれでは計算量が爆発してしまい、x=2
までくらいしか計算できない。
そこで、
フェルマーの小定理を拡張した、オイラーの定理を使うことで、計算量を抑えることを試みます。
フェルマーの小定理自体は、
を素数とし、 を の倍数でない整数( と は互いに素)とする時に、
すなわち、 の 乗を で割った余りが1になる。
このフェルマーの小定理を拡張したオイラーの定理は、フェルマーがp
は素数という条件だったのに対し、これを合成数に拡張したもの。
を正の整数とし、 を と互いに素な整数としたとき、
すなわち、 の 乗を で割った余りが1になる。
ここで、はオイラー関数(totient関数)と言い、正の整数 n
に対して、 n
と互いに素である 1
以上 n
以下の自然数の個数 を与える数論的関数のこと。
例えば、1, 2, 3, 4, 5, 6
のうち 6
と互いに素なのは 1, 5
の 2
個であるから、定義によれば である。また例えば 1, 2, 3, 4, 5, 6, 7
のうち 7
以外は全て 7
と互いに素だから、。
totient
については、pythonだと下記のライブラリで高速に求めることができます。
Number Theory — SymPy 1.5.1 documentation
フェルマーの小定理とオイラーの定理については、下記の記事がとてもわかり易かった。
更に、オイラーの定理より a^φ(n) % n == 1
と、周期的に1になり、その周期がφ(n)
なので
が成り立ちます。
今回の問題に当てはめてみると、求めたい a↑↑x % p
は
※
と表すことが出来ます。※ を%
で表記しています。
さらに、オイラーの定理より
なので、
と表すことができ、再帰で表現できそうです。
先程のテトレーションを純粋に求めるプログラムをちょっと変更して
from sympy.ntheory import totient def tetoration_mod(a, x, p): if p == 1 or x == 0: return 1 return pow(a, tetoration_mod(a, x-1, totient(p)), p)
これで計算できそう。
あとは、問題文から各値を読み込んで10回x
を求めてみます。
#!/usr/bin/env python3 # -*- coding:utf-8 -*- from pwn import * from sympy.ntheory import totient def tetoration_mod(a, x, p): if p == 1 or x == 0: return 1 return pow(a, tetoration_mod(a, x-1, totient(p)), p) host = "crypto.2020.chall.actf.co" port = 20603 r = remote(host, port) for i in range(10): r.recvuntil(b'of 10...\n') p = int(r.recvline().split(b' ')[2].strip()) a = int(r.recvline().split(b' ')[2].strip()) b = int(r.recvline().split(b' ')[2].strip()) r.recvuntil(b'Enter x: ') x = 0 while True: if tetoration_mod(a, x, p) == b: break x += 1 print(str(i) + 'th x: ' + str(x)) r.sendline(str(x).encode()) ans = r.recvline() if ans == b'Correct!\n': continue else: print(ans) print(r.recvall())
実行結果
$ python solve.py [+] Opening connection to crypto.2020.chall.actf.co on port 20603: Done 0th x: 6 1th x: 7 2th x: 8 3th x: 4 4th x: 4 5th x: 3 6th x: 7 7th x: 2 8th x: 13 9th x: 3 [+] Recieving all data: Done (50B) [*] Closed connection to crypto.2020.chall.actf.co port 20603 b'flag: actf{lets_stick_to_discrete_log_for_now...}\n'
(๑•̀ㅂ•́)و✧
ところで、なぜ力ずく解法が通ったのかは不明。大きな値を入れることで、サーバー側に付加をかけ、timeout = 正解!を狙った感じになっちゃったのかな?申し訳ない…。 参考にさせてもらったwriteup
[Crypto] Confused Streaming
I made a stream cipher!
nc crypto.2020.chall.actf.co 20601
chall.py
が配布されます。
from __future__ import print_function import random,os,sys,binascii from decimal import * try: input = raw_input except: pass getcontext().prec = 1000 def keystream(key): random.seed(int(os.environ["seed"])) e = random.randint(100,1000) while 1: d = random.randint(1,100) ret = Decimal('0.'+str(key ** e).split('.')[-1]) for i in range(d): ret*=2 yield int((ret//1)%2) e+=1 try: a = int(input("a: ")) b = int(input("b: ")) c = int(input("c: ")) # remove those pesky imaginary numbers, rationals, zeroes, integers, big numbers, etc if b*b < 4*a*c or a==0 or b==0 or c==0 or Decimal(b*b-4*a*c).sqrt().to_integral_value()**2==b*b-4*a*c or abs(a)>1000 or abs(b)>1000 or abs(c)>1000: raise Exception() key = (Decimal(b*b-4*a*c).sqrt() - Decimal(b))/Decimal(a*2) except: print("bad key") else: flag = binascii.hexlify(os.environ["flag"].encode()) flag = bin(int(flag,16))[2:].zfill(len(flag)*4) ret = "" k = keystream(key) for i in flag: ret += str(next(k)^int(i)) print(ret)
b*b - 4*a*c
おや、この公式どこかで見たことがあるぞ…。なんだっけ…。2次方程式の解の公式だ!
コメントの部分に、"これらの厄介な虚数、有理数、ゼロ、整数、大きな数などを削除します"とあるので、それ以外のa,b,c
の組み合わせを探す。
abs(a)>1000 or abs(b)>1000 or abs(c)>1000
だと落ちるので、a,b,c
の絶対値は 1000
以下。
Decimal(b*b-4*a*c).sqrt().to_integral_value()**2!=b*b-4*a*c
の条件に合うa,b,c
を入力すると、flagをkeystream(key)
関数で生成したk
とxorを取ったflagが出力される。条件をまとめるとこんな感じ。
b*b > 4*a*c
a != 0, b != 0, c != 0
Decimal(b*b-4*a*c).sqrt().to_integral_value()**2 != b*b-4*a*c
a,b,c
の絶対値は1000
以下上記の条件に合うa,b,cを考える
keystream(key)
関数からk
を推測する(ただしrandom
関数が使われている…!)- 出力と
k
をxorする
条件似合いそうなa,b,c
を与えてみます。
$ nc crypto.2020.chall.actf.co 20601 a: -1 b: 2 c: 1 01100001011000110111010001100110011110110110010001101111011101110110111001011111011101000110111101011111011101000110100001100101010111110110010001100101011000110110100101101101011000010110110001111101
おお、なんか一個もらえた。んー、でもk
を推測するのが難しそう。なんとかk=0
にならんかな?
ここから復習
ここで競技時間は終了してしまいましたが、なんとこれflagだった…orz。
from Crypto.Util.number import * stream = '01100001011000110111010001100110011110110110010001101111011101110110111001011111011101000110111101011111011101000110100001100101010111110110010001100101011000110110100101101101011000010110110001111101' print(long_to_bytes(int(stream,2)))
実行結果
$ python solve.py b'actf{down_to_the_decimal}'
ただ、原理を理解して得られたわけではないのでちゃんと復習する。
ここから復習
これ、keystream()
関数で生成されるk
は常に0
にできる条件を使っていたのでした。
key
に0.5以下の値が渡されると、
ret = Decimal('0.'+str(key ** e).split('.')[-1])
において、key ** e
が非常に小さくなり、Decimal('0.'+str(key ** e).split('.')[-1])
自体も、とても小さい値になります。(2.3E-340
など)
for i in range(d): ret*=2
がret
に対して施されますが、d
がe
に比べて小さすぎるために
yield int((ret//1)%2)
は常に int(({1以下の値}//1)%2)
となり、0
が返ります。結果、flag xor 0
の結果が表示されているので、これをint to byte decodeすればflagそのものだったというわけ。
なんとか
k=0
にならんかな?
なっとった!
原理がわからなくても、chall.py
をlocalで動かして挙動を確認し、key
,k
にどんな値が入ってくるかを観察すれば解けたかもしれない。(localで用意したflagのbinと出力が同じである、常にk=0
になっている、などが確認できたため。)e
とd
の出力まではlocalで挙動を確認していたが、その結果k
やret
がどうなっているかは確認していなかった。残念。
さらに、下の Dream Stream で別解、というか想定解を見たので記録。
[Crypto] Dream Stream
I made my stream cipher better.
nc crypto.2020.chall.actf.co 20602
chall.py
が配布されます。
from __future__ import print_function import random,os,sys,binascii from Crypto.Util.number import isPrime from decimal import * try: input = raw_input except: pass getcontext().prec = 3000 def keystream(key): random.seed(int(os.environ["seed"])) p = random.randint(3,30) while not isPrime(p): p = random.randint(3,30) e = random.randint(50,600) while 1: d = random.randint(10,100) ret = Decimal('0.'+str(key ** e).split('.')[-1]) for i in range(d): ret*=2 yield int((ret//1)%2) e+=p try: a = int(input("a: ")) b = int(input("b: ")) c = int(input("c: ")) # added some more weak key protections if b*b < 4*a*c or [a,b,c].count(0) or Decimal(b*b-4*a*c).sqrt().to_integral_value()**2==b*b-4*a*c or abs(a)>400 or abs(b)>500 or abs(c)>500: raise Exception() key = (Decimal(b*b-4*a*c).sqrt() - Decimal(b))/Decimal(a*2) if 4*key*key<5 or abs(key-key.to_integral_value())<0.05: raise Exception() except: print("bad key") else: flag = binascii.hexlify(os.environ["flag"].encode()) flag = bin(int(flag,16))[2:].zfill(len(flag)*4) ret = "" k = keystream(key) for i in flag: ret += str(next(k)^int(i)) print(ret)
Confused Streamingの続きっぽい。接続してみると
$ nc crypto.2020.chall.actf.co 20602 a: 1 b: 2 c: 3 bad key
出てくる文言も同じ様子。競技期間中は、「まずはConfused Streamingだな…」というメモを最後に終わっている…。
ここから復習
Confused Streamingからの変更点をソースから追ってみます。
まずは、a,b,c
の入力値の評価について、Confusedの方では
remove those pesky imaginary numbers, rationals, zeroes, integers, big numbers, etc
との注意書きがありました。Dreamのほうは
added some more weak key protections
とあります。変更されている評価は、Exception発生の条件として
abs(a)>1000 or abs(b)>1000 or abs(c)>1000
から
abs(a)>400 or abs(b)>500 or abs(c)>500
に。その後、key
を生成してから
if 4*key*key<5 or abs(key-key.to_integral_value())<0.05: raise Exception()
の評価が追加になっています。
この
の条件が加わったので、key
はより大きい必要があり、先程 Confused Stream で使った手が使えません。
ここでwriteupを探してみましたが、CTF Timeにも載っていません…。問題自体Tasksにもなかったので、無かったことになっている??
唯一、Discordに公式writeupがあがっていました。
Confused Streaming/Dream Stream: Note that
a
,b
, andc
are being used as coefficients that are plugged into the quadratic formula to get the key. The bits of the keystream are taken from random bits in the fractional part ofkey^n
, wheren
increases by an odd number. Plugging ina = 1, b = -2, c = -2
gives the keyk = 1+sqrt(3)
. This has the nice property thatk^n
gets closer and closer to an integer as n increases. In fact, it flip-flops between being just over an integer and just under an integer (proof below). So, the bits of the keystream alternate between1
and0
. Thus, we XOR the output with01010101...
or10101010...
to get the flag.Proof of the nice property: Consider
(1+sqrt(3))^n + (1-sqrt(3))^n
. If we expand both of the binomials, the terms withsqrt(3)
all cancel out. So, this expression approaches an integer. However, note that-1 < 1-sqrt(3) < 0
, so(1-sqrt(3))^n
approaches 0, alternating between just greater than 0 and just less than 0. Therefore,(1+sqrt(3))^n
alternates between being just greater than an integer and just less than an integer.edit: it has come to my attention that 1,-2,-2 may produce an error. In that case, any other key with the property described above works; you just need to find one that does (there are a lot that work).
Unintended solution for Confused Streaming: make the key between 0 and 1 so that it approaches 0
ぱっとこれを読んだだけではわからなかったので、読み解いていきました。
更に、この解法ではない組み合わせでもflagが取れたので、そちらも。多分こっちでflagが取れたチームのほうが多かったのでは。
- 想定解法
k=010101...
ork=101010...
になる組み合わせを使う k=1
になる組み合わせを使う
想定解法k=010101...
ork=101010...
今回の制約を数式に表すと
- を整数に丸めたものの2乗
となっています。keystream
関数で返却される値は0,1
のどちらかとなっており、
e
は範囲 50~600 のランダムな整数d
は範囲 10~100 のランダムな整数p
は 3~30 の範囲のランダムな素数
の時に
を計算し、ret
を小数点以下で切り捨てて整数にした値(k
)が
- 奇数なら
1
- 偶数なら
0
が返却されます。
Confused Streamingでは、を小さくすることで、を0に収束させ、d
の値が比較的小さいことから の影響を小さくし、常にret
が正の0に限りなく近い状態、k
を0に固定することで解けました。
今回は先程も述べたとおり、の条件が加わったので、key
はより大きい必要があり、0に収束させることが出来ません。
ここで先程の公式解法より。唐突ですが、[1, -2, -2]
を[a, b, c]
の入力として与えることを考えます。このとき、
となります。無理数の平方根と有理数の加算になっていますが、このような数において以下のような性質があります。
平方根の部分がキャンセルされるので、常に整数になります。
更に、、すなわち , であるため、
と n
が増えるにつれて0に収束していきます。更に、後者の条件より
で負の数 を に掛けることになるので、±が逆転します。
以上の条件をまとめると
- の符号は の反対になる
以上のことより、
であり、さらに 整数I
の上下を行き来しながら収束する性質があることがわかります。(I + 0.000000...
, I - 0.000000....
)
よって、key
がの場合、
は、e
が十分大きく、1ずつ増える時、0.0000000...
(0に限りなく近い正の値)と0.9999999....
(1に限りなく近い1以下の値)を交互に取りながら0
と1
に収束していくことがわかります。
今回、e
は1ずつ増えるのではなくp
、すなわちランダムな3~30の間の素数ずつ増えますが、p
は奇数なため、e
は奇数と偶数を交互に繰り返します。このため、やはり と を交互に繰り返すことになります。
更にこのあと、 が待っています。
0に収束する場合は、e
よりd
が十分小さい場合はこの 2d は無視できますが、1に収束する方はこの影響を大きく受けるはずです。ぱっと見、d
がランダムなため、値が不定になってしまうように見えます。
ここで1に収束する値を、 と置いてみます。
ここで、 で、0に限りなく近い正の値になるため、上記の式の値は 奇数.99999....
となります。
これをint()
で少数以下切り捨ての整数にするため、ret
は必ず奇数になり、1
が返ることがわかります。
以上のことより、key
が有理数+平方根で表現され、有理数 - 平方根 (key'
) が の範囲に設定できれば、k
が01010...
もしくは10101...
の形になり、これと出力をxorすることでflagが求まります。
※残念ながら、2020/4/15現在、サーバーが正常に動いていないようなのでローカルでやることに。環境変数を設定するとlocalでも実行可。
$ export flag="kswd{this_is_local_flag!}" $ export seed="10" $ python chall.py a: 1 b: -2 c: -2 001111100010011000100010001100010010111000100001001111010011110000100110000010100011110000100110000010100011100100111010001101100011010000111001000010100011001100111001001101000011001000101000
from Crypto.Util.number import * stream = '001111100010011000100010001100010010111000100001001111010011110000100110000010100011110000100110000010100011100100111010001101100011010000111001000010100011001100111001001101000011001000101000' xor1 = '' xor2 = '' i = 0 for b in stream: xor1 += str(int(b) ^ (i%2)) xor2 += str(int(b) ^ ((i+1)%2)) i += 1 print(long_to_bytes(int(xor1,2))) print(long_to_bytes(int(xor2,2)))
実行結果
$ python solve.py b'kswd{this_is_local_flag}' b'\x94\x8c\x88\x9b\x84\x8b\x97\x96\x8c\xa0\x96\x8c\xa0\x93\x90\x9c\x9e\x93\xa0\x99\x93\x9e\x98\x82'
\(*ˊᗜˋ*)/
これをサーバーに対して実行できれば、flagが得られたはず。
k=1
になる組み合わせを使う解法
今度は入力値[1, -3, 1]
としてみます。このとき、
上記と同様、おもむろに を考えてみます。
のため、今度は です。
前項の想定解のとき見た性質より、
- の符号は と同じ
以上より、
と、整数Iよりわずかに小さい値に収束します。
ここからは先程の想定解法のときと同じく、 して小数部分を切り捨てて整数にすると、この結果は必ず奇数になるため、k
は必ず1が返ります。
よって、key
が有理数+平方根で表現され、有理数 - 平方根 (key'
) が の範囲のに設定できれば、k
が1
に固定され、これと出力をxorすることでflagが求まります。
$ export flag="kswd{this_is_local_flag!}" $ export seed="10" $ python chall.py a: 1 b: -3 c: 1 100101001000110010001000100110111000010010001011100101111001011010001100101000001001011010001100101000001001001110010000100111001001111010010011101000001001100110010011100111101001100010000010
from Crypto.Util.number import * stream = '100101001000110010001000100110111000010010001011100101111001011010001100101000001001011010001100101000001001001110010000100111001001111010010011101000001001100110010011100111101001100010000010' xor = '' for b in stream: xor += str(int(b) ^ 1) print(xor) print(long_to_bytes(int(xor,2)))
実行結果
$ python solve.py 011010110111001101110111011001000111101101110100011010000110100101110011010111110110100101110011010111110110110001101111011000110110000101101100010111110110011001101100011000010110011101111101 b'kswd{this_is_local_flag}'
\(*ˊᗜˋ*)/
想定解法じゃないけど、こっちで解けたチームのほうが多そう。
競プロ勢は、日々こういう問題に取り組んでるのかな。この手の問題は常識レベル??
今回の問題は、別解に使える入力を弾きそびれたのかな?何れにせよ、普段数式見たり考えたりすることないので、とても面白かったです。
実際競技中に解こうと思うと、chall.py
がせっかく配布されているので、ローカルで動かしながら挙動を観察、k
がどのような値をとっているかを確認すればよかったかなぁと思います。
[Crypto] RSA-OTP
RSA is kinda bad but I strengthened it with the unbreakable one time pad!
nc crypto.2020.chall.actf.co 20600
Hint
What information does the server tell you?
今回も chall.py
が配布されます。
from Crypto.Util.number import bytes_to_long from Crypto.Random.random import getrandbits # cryptographically secure random get pranked from Crypto.PublicKey import RSA from secret import d, flag # 1024-bit rsa is unbreakable good luck n = 136018504103450744973226909842302068548152091075992057924542109508619184755376768234431340139221594830546350990111376831021784447802637892581966979028826938086172778174904402131356050027973054268478615792292786398076726225353285978936466029682788745325588134172850614459269636474769858467022326624710771957129 e = 0x10001 key = RSA.construct((n,e,d)) f = bytes_to_long(bytes(flag,'utf-8')) print("Encrypted flag:") print(key.encrypt(f,0)[0]) def otp(m): # perfect secrecy ahahahaha out = "" for i in bin(m)[2:]: out+=str(int(i)^getrandbits(1)) return out while 1: try: i = int(input("Enter message to sign: ")) assert(0 < i < n) print("signed message (encrypted with unbreakable otp):") print(otp(key.decrypt(i))) except: print("bad input, exiting") break
とりあえず n
を素因数分解しようとしてみたが、msieveでは桁が大きすぎて扱えないエラーが。factordb.comでも全く分解できませんでした。
指定のホストに接続してみると、flagをencryptしたものを表示してくれます。
$ nc crypto.2020.chall.actf.co 20600 Encrypted flag: 17482644844951175640843255713372869422739097498066773957636359990466096121278949693816080016671592558403643716793132479255285512907247513385850323834210899918531077167485767118313722022095603863840851451191536627814100144146010392752308431038754246815068245448456643024387011488032896209253644172833489422733
そのあと、Enter message to sign:
で整数を入力すると、これを key.decrypt() -> otp()
の順で処理した値を表示してくれます。
perfect securityらしいotp(m)
はただのxorなので、getrandbits(1)
が何かわかれば再度xorしてあげるだけで逆算できるはず…なのですが、getrandbits(1)
が文字通りランダムなのでわかりません。
とりあえず、教えてもらったEncrypted flagをそのまま突っ込んでみます。
$ nc crypto.2020.chall.actf.co 20600 Encrypted flag: 17482644844951175640843255713372869422739097498066773957636359990466096121278949693816080016671592558403643716793132479255285512907247513385850323834210899918531077167485767118313722022095603863840851451191536627814100144146010392752308431038754246815068245448456643024387011488032896209253644172833489422733 Enter message to sign: 17482644844951175640843255713372869422739097498066773957636359990466096121278949693816080016671592558403643716793132479255285512907247513385850323834210899918531077167485767118313722022095603863840851451191536627814100144146010392752308431038754246815068245448456643024387011488032896209253644172833489422733 signed message (encrypted with unbreakable otp): 0001000100011111100101000110111000011101010000001011000011110111100101111011110001000011111000011010101011010010001110100101010111110111110000100110101110010001001100100001010111111101110001010101011111101011011110001111100101110000011010011000110010110011001000111101011110101001100101000000110011010100100100111100010001110011010111111111100111010110010011101000111001101011001101000111000011100100010100001101110000011010011111000110111000110101101101111011011111000011000010100001010000000111010101110101010101111000010111100010101111011011001011101001001
flagをdecryptした結果…をランダムなbitsでxorした結果が得られました。でもやっぱりgetrandbits(1)
がわからないので、これを復元できる気がしません…。もちろん、突っ込むたびに返ってくるbit列が変わってしまいます。
このあと、getrandbits(1)
の出目予想が出来ないかなど色々試してみましたが、どれもうまく刺さりませんでした。
与えられている情報は、ソースよりn
とe
、そして暗号化されたflagc
。n
とe
があれば公開鍵を構築できるので、公開鍵も与えられていることになります。あとは、好きな暗号文を与えると、復号して更にランダムなbit列でxorしたものも得られます。
一体これらの情報で、どうやったら平文が得られるんだろう🤔
ここから復習
他のwriteupを読んだところ、今回の問題ではOracle攻撃
というのが使える様子。Oracle攻撃といえばPadding Oracle
が有名です。Oracle攻撃の概要はこちらがわかりやすかったです。
writeupは、下記の4つが見つかりました。
- 公式解法のソルバ
- スクリプトのみ。そのままでは動かないが、ちょっと手を入れると動きました。
- RSA-OTP - face0xff's writeups
- ソルバが載っている解法その2
- 2分探索で
m
のレンジを絞っていくのですが、step1までで最後までflagが得られなかったそう - flagの最後のほうはゲスパーしたとのこと
- ångstromCTF 2020 - RSA-OTP Writeup | pwnthem0le
- ソルバなし。下記の方法と似ている気がするが、読み解けず。
- Angstrom CTF 2020 ※ベトナム語
- ソルバなし。
- LSB Oracle attack 的な手法とのこと。この用語を手がかりに解くことが出来ました
実際のところ全部の解法を読んで理解を試みましたが、ソルバがあるけど解説がないもの、解説があるけどソルバがないもの、解説とソルバはあるけどflagが最後まで取得できなかったもの、という感じで結構厳しい。
最終的には、4つ目の解法がなんとか理解できそうだったので、この解法でやってみます。また、動くソルバを書いた&途中まで理解したので、公式解法についても中途半端ですが残しておきます。
- LSB Oracle Attack っぽい解き方
- 公式解法っぽい解き方(未完成)
LSB Oracle Attack っぽい解き方
ヒントの What information does the server tell you?
というやつ。そりゃ当たり前だわ、サーバーが返す値を見ないことには始まらないわ、と思って無視してたんですけど、さすがヒント、これが大事だったようです。
結局、otp
の処理を施して返却される値は、otp
処理でランダムなビット配列とxorされてしまっており、元に戻すことは不可能です。他に得られる情報で、xorの結果、変わらない情報が「長さ」。突っ込んだmessageをdecryptした結果の長さがわかります。
先程試してみた、encryptoされたflagを突っ込んでdecrypt,otp処理をした結果の出力では、559bitsが返ってきています。otp処理では長さは変わらないはずなので、flagの平文m
のbit長は559ビットということになります。
以下、まずは一般的な LSB Oracle Attack について考えてみます。
ほかの方のwriteup読んでも何故そうなるかさっぱりわからなかったのですが、こちらのサイトの解説のおかげで、まずは LSB Oracle Attack について理解することが出来ました。とても丁寧でわかりやすくてありがたい。
LSB Decryption Oracle Attack - ごちうさ民の覚え書き
以下、上記のブログの内容ほぼそのままなので、元の記事を見ていただくのが良いかと。途中から今回の問題に当てはめるために、こちらにも写経させていただきます。
RSA暗号の公式をおさらいすると、c
が暗号文、m
が平文の場合、
(c = pow(m, e, n)
),
(m = pow(c, d, n)
) (※dはinverse, eの逆元)
また、decryptした結果について得られる情報があることから、このEnter message to sign:
に値を突っ込んで返してもらう機能をOracle
と呼ぶことにします。
LSB Oracle Attack では、Oracleを関数f(x)
とすると、
と、復号した結果が偶数か奇数か、すなわち最終ビットが0か1かがわかる場合に有効です。ここで、
とすると、
と展開できます。また、RSA暗号の性質より
- は奇数 (大きい素数(≠2)、, の積であるため)
最後の条件は、よりが成り立つため、 から説明できる。
ここで、i=1
の時を考えてみます。
すなわち、2m % n
が偶数か奇数か。ここで、先程のm
のレンジの制約より、の商は0
か1
になります。また、2m
は偶数、n
は奇数のため、2m % n
が
- 偶数の場合:
- 商は0
- 奇数の場合:
- 商は1
であることがわかります。
次に、i=2
の時を考えてみます。
i=1
のときの結果を利用して、下記のように展開できます。
かつ のとき
このように、他のケースについても展開して考えると
- f(ac)=1, f(a2c)=1の場合:
- f(ac)=1, f(a2c)=0の場合:
- f(ac)=0, f(a2c)=1の場合:
- f(ac)=0, f(a2c)=0の場合:
i=3
以降も上記を繰り返すことにより、平文m
の範囲を2文探索の要領で狭めていき、最終的に上限と下限の差分が1以下になったらm
が求まります。
今回の問題では、Oraclef(x)
が f(x) = dec(x) % 2
ではなく f(x) = dec(x).bit_length
です。このとき、
であり、m
のレンジに関する性質は変わりません。
ここで、i=1
の時を考えてみます。
今回もm
のレンジの制約より、の商は0
か1
になります。また、2m
は偶数、n
は奇数のため、2m % n
のbit長u
が
- mのbit長より大きい(+1)場合:
- 商は0
- それ以外の場合:
- 商は1
であることがわかります。i=2
以降は、先程の LSB Oracle Attack 同様の流れになるので、同じようにm
のレンジを狭めていって特定することが出来ます。
from Crypto.Util.number import long_to_bytes from pwn import * n = 136018504103450744973226909842302068548152091075992057924542109508619184755376768234431340139221594830546350990111376831021784447802637892581966979028826938086172778174904402131356050027973054268478615792292786398076726225353285978936466029682788745325588134172850614459269636474769858467022326624710771957129 e = 0x10001 host = "crypto.2020.chall.actf.co" port = 20600 def get_plain_bit_length(c): r.sendline(str(c).encode()) res = r.recv().split(b'\n')[1] return len(res) r = remote(host, port) c = int(r.recv().split(b'\n')[1]) m_bit_len = get_plain_bit_length(c) lower_m = 0 upper_m = n u_prev = m_bit_len while upper_m - lower_m >= 1: cK = (c * pow(2, e, n)) % n u = get_plain_bit_length(cK) if u == u_prev + 1: upper_m = (upper_m + lower_m) // 2 else: lower_m = (upper_m + lower_m) // 2 u_prev = u c = cK print('----------') print(long_to_bytes(lower_m)) print(long_to_bytes(upper_m))
実行結果
$ python solve.py [x] Opening connection to crypto.2020.chall.actf.co on port 20600 [x] Opening connection to crypto.2020.chall.actf.co on port 20600: Trying 52.207.14.64 [+] Opening connection to crypto.2020.chall.actf.co on port 20600: Done ---------- b'\x00' b'`\xd90\x10\xef%5_\x9a\x1d $\x93d\x95\xd4\xe8F\x15(\\%nMn\xd1R\xb8\xc1\xd7b\xab\x9f\xc4\xeb\xd6\x1b\x82\x15\r\xc3s\x07\xcb\xfb\xc5\x85EA!0>\xeb\xf5\xb5\x98\xb7\xc9\xfdP\xa3\xafK+\x15$\xea\xb78\x059\xc8\xcbyNo\xc7\x0c\xc3\\\x11\xaa\x94\x91p!7\xbdk:vD\xdc\x19\x1b\x97\xafyZ\x90\xa39\x7fV\xb4\x11S\xf5+XM\x92\xd3\x17\xf4F.?\x1f\xe6\xeco\x95\x0e\x13r\xae\xc4' ---------- b'\x00' b'0l\x98\x08w\x92\x9a\xaf\xcd\x0e\x90\x12I\xb2J\xeat#\n\x94.\x12\xb7&\xb7h\xa9\\`\xeb\xb1U\xcf\xe2u\xeb\r\xc1\n\x86\xe1\xb9\x83\xe5\xfd\xe2\xc2\xa2\xa0\x90\x98\x1fu\xfa\xda\xcc[\xe4\xfe\xa8Q\xd7\xa5\x95\x8a\x92u[\x9c\x02\x9c\xe4e\xbc\xa77\xe3\x86a\xae\x08\xd5JH\xb8\x10\x9b\xde\xb5\x9d;"n\x0c\x8d\xcb\xd7\xbc\xadHQ\x9c\xbf\xabZ\x08\xa9\xfa\x95\xac&\xc9i\x8b\xfa#\x17\x1f\x8f\xf3v7\xca\x87\t\xb9Wb' ...(中略)... ---------- b'actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_with_padding9' b'actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_with_padding:' ---------- b'actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_with_padding9' b'actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_with_padding9' [*] Closed connection to crypto.2020.chall.actf.co port 20600
3~4分回すと、flagが出てきました٩(๑❛ᴗ❛๑)尸
最後閉じてないけど!実際は最後の9
->}
ですが、コレくらいの推測なら解けたと言っても良いはず…。
下記公式解法などの解き方より収束が遅く、ソルバがうまく動作しているのか不安になって諦めかけたりしましたが、自分で納得しながら書いたソルバでflagがゲットできて良かった!
公式解法っぽい解き方(未完成)
あるk
を
とします。このとき、K
はk
の暗号文になります。このK
とflagの暗号文c
をかけると、
となり、mk
の暗号文が得られることになります。
このとき、mk
のbit長がn
のbit長以下の場合、cK
を突っ込んで得られる応答から、mk
のbit長がわかることになります。
ここで、mk
のbit長をu
と置くと、
とmk
のレンジを表すことが出来ます。
先程の試行より、m
のbit長は559
とわかっているので、
ということがわかります。
したがって、m
は
の範囲であることがわかります。
これを、
と仮定し、i
を 559からn
のbit長まで増やしていき、m
の範囲を絞っていきます。
…が、この方法でm
のレンジを絞っていくと、flagが途中まで判明します。が、まだ最後の数バイトが不明のまま残ってしまいます…。
公式ソルバでは、この後"step2"として、更にm
の下位の方のバイトを求めています。
下記は、公式のソルバを上記の説明に合わせて書き換え、動くようにしたもの。残念ながら、step2についてはまだ理解が出来ていないです。多分巨大な数shift
を挟むことでm
が収束するレンジを広げ、小さいbitまで絞り込めるようにしていると思うのだけど…。
from Crypto.Util.number import long_to_bytes from Crypto.PublicKey import RSA from pwn import * # refer to https://pastebin.com/P8L7RTDu n = 136018504103450744973226909842302068548152091075992057924542109508619184755376768234431340139221594830546350990111376831021784447802637892581966979028826938086172778174904402131356050027973054268478615792292786398076726225353285978936466029682788745325588134172850614459269636474769858467022326624710771957129 e = 0x10001 pubkey = RSA.construct((n,e)) host = "crypto.2020.chall.actf.co" port = 20600 def get_plain_bit_length(c): r.sendline(str(c).encode()) res = r.recv().split(b'\n')[1] return len(res) r = remote(host, port) c = int(r.recv().split(b'\n')[1]) c_bit_len = get_plain_bit_length(c) u = c_bit_len lower_m = 2**(u-1) upper_m = 2**u - 1 dd = upper_m - lower_m mid_m = (upper_m + lower_m) // 2 for num in range(u+1, n.bit_length()): k = (2**num - 1) // mid_m cK = (c * pow(k, e, n)) % n u = get_plain_bit_length(cK) upper_m = min(upper_m, (2**u-1)//k) lower_m = max(lower_m, (2**(u-1)//k)) if upper_m - lower_m < dd: dd = upper_m - lower_m mid_m = (upper_m + lower_m) // 2 print('----------') print(long_to_bytes(lower_m)) print(long_to_bytes(upper_m)) print('----------') print('u: ' + str(u)) print('k: ' + str(k)) print('m: ' + str(mid_m)) print(long_to_bytes(lower_m)) print(long_to_bytes(upper_m)) # ここから更に正確な値を求めていく i = 4*pow(10,40) # 適当な大きな数 shift = n*i for num in range(n.bit_length()): k = (2**num - 1 + shift) // mid_m cK = (c * pow(k, e, n)) % n u = get_plain_bit_length(cK) if u == n.bit_length(): # we didn't wrap around upper_m = min(upper_m, (shift-1)//k) lower_m = max(lower_m, (2**(u-1) + shift - n)//k) else: upper_m = min(upper_m, (shift + 2**u - 1)//k) lower_m = max(lower_m, (2**(u-1)+shift)//k) if upper_m - lower_m < dd: dd = upper_m - lower_m mid_m = (upper_m + lower_m) // 2 if dd <= 1: break print('----------') print(long_to_bytes(lower_m)) print(long_to_bytes(upper_m)) print('----------') print('u: ' + str(u)) print('k: ' + str(k)) print('m: ' + str(mid_m)) print(long_to_bytes(lower_m)) print(long_to_bytes(upper_m))
実行結果
$ python solve.py [+] Opening connection to crypto.2020.chall.actf.co on port 20600: Done ---------- b'@\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00' b'\x7f\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff' ---------- b'@\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00' b'ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff' ---------- ...{中略1}... ---------- u: 1024 k: 62606626634666857169962576496954328573681192124427072668906299463448781600005761352512899051732400786172667561506921142654444651242031108630 m: 1435705157341034722972040166343948017765222376167759753619834511904754169570506546261909734839045859564975508867904779044318503483547332182165204288687845169555358931060 b'actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_q\x1ab7\xb2\x08gO\x0fu\xcd#\xe1' b'actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_x\xa0\xed3\xc0\xb3%\x82w\xa94\x8d\x08' ...{中略2}... ---------- b'actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_v\xe7\xc7\xcbx\xd8\x82y!\xd4\xa7\x8e\x99' b'actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_x\xa0\xed3\xc0\xb3%\x82w\xa94\x8d\x08' ---------- b'actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_v\xe7\xc7\xcbx\xd8\x82y!\xd4\xa7\x8e\x99' b'actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_w\xc4Z\x7f\x9c\xc5\xd3\xfd\xcc\xbe\xee\r\xd0' ---------- ...{中略3}... ---------- u: 567 k: 473699294761052263257453976608854380286151134994879613791162315212316412696124816295601503453088411612127948258634000745395634796195218589954600739259717757111055678091542 m: 1435705157341034722972040166343948017765222376167759753619834511904754169570506546261909734839045859564975508867904779044318503483547332182366926494593476321186830772092 b'actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_with_padding|' b'actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_with_padding}' [*] Closed connection to crypto.2020.chall.actf.co port 20600
中略1のあと、actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_
までm
の範囲が絞れましたが、まだその先数byte残っています。
そこでstep2の処理に移行し、m
を最終bitまで特定しているようです。
この解法の、私にもわかりそうな解説ありましたらぜひ教えて下さいませー!