ひとこと
どんな演算にもきれいな関係性がある
問題
情報
問題リンク: https://alpacahack.com/daily/challenges/flag-is-a-plus-b
ジャンル: Crypto
難易度: Easy 2.5
問題文
A+B を計算すればフラグがわかるよ! あれ、A と B っていくつだっけ…?
もとめるものと与えられているもの
条件$A+B=M$,$0\leq A<M,B$を満たす整数$A,B$から$M$ (FLAG)を復元する問題です。
与えられている値は$A$,$B$のORとXORです。
場合分け
XOR演算とOR演算から、$A$,$B$を割り出せないでしょうか。
以降、A OR Bを$O$、A XOR Bを$X$と書きます。
Oの$i$ビット目を$O_i$、Xの$i$ビット目を$X_i$と書きます。
(i) $O_i$が0のとき
これは明らかに$A_i$、$B_i$、どちらも0です。
(ii) $O_i$が1のとき
この場合XOR演算からさらなる情報を引き出せます
(ii-i) $X_i$が0のとき
$A_i=B_i$がいえます。そして$O_i\neq 1$だから$A_i=B_i=0$しかありえません。
(ii-ii) $X_i=1$のとき
この場合$A_i,B_i$どちらかが0で、もう一方が1です。
さて...
(ii-ii)において、1なのはどっちかは確定しません。
>>> len(bin(1653224853895272618878301831150773792186632776885840473347068872416893))
232
$O_i=X_i=1$となるとき、$A,B$どちらが1かを全探索した場合$O(2^{\log_2 N})=O(N)$
($N=\max(A|B,A\oplus B)$)くらいはあるので、まあ死にます。
しかし求めたいのは$A$でも$B$でもなく、$A+B$です。この場合$i$ビット目が$A+B$に及ぼす影響、まあ寄与みたいなものを考えます。
(i)のときは$+0$、(ii-i)のとき$+2^i$、(ii-ii)のとき$+2\times 2^i=+2^{i+1}$の寄与が発生します。
ということは、こういう感じで$A+B=M$、すなわちフラグを出せるわけです。
from Crypto.Util.number import long_to_bytes
O = 1708520672692343497693425015709016883325158039728511260268583494549501
X = 1653224853895272618878301831150773792186632776885840473347068872416893
M = 0
for i in range(250): # 二進数でO,Xの桁数より大きい数
if O & (1 << i): # (ii)
if X & (1 << i): # (ii-ii)
M += 2 ** i
else: # (ii-i)
M += 2 ** (i + 1)
else: # (i)
pass
print(long_to_bytes(M))
そうするとフラグが出ます。やったね！
フラグ
フラグ
Alpaca{m4thema7ics_i5_fun!!!}
追記
この問題、こんなことしなくても、
$A+B=2O-X$で出せるらしいです。いやそんな式知らねぇよ！？
ということで証明します。
$O=O_02^0+O_12^1+...$なので、$2O=O_02^1+O_12^2+...$です。
$O_i=0$の時の寄与は$0$なのでこの式でこの場合における寄与を正しく表現できていますが、$O_i=1$かつ$X_i=1$のときの処理ができていません。この時の寄与は$2^i$で、$2^{i+1}$ではないので、どうにかして引いてあげる必要があります。
$X=X_02^0...$であることを踏まえてあげます。$O_i=0\Rightarrow X_i=0$なので、$O_i=0$のときXの$i$の寄与は無視できます。
よって、$2O$から$X$を引けば、$2^{i+1}$の無駄な寄与を間引くことができます。よって$A+B=2O-X$を証明できました。試しにやってみると
from Crypto.Util.number import long_to_bytes
O = 1708520672692343497693425015709016883325158039728511260268583494549501
X = 1653224853895272618878301831150773792186632776885840473347068872416893
M = 0
for i in range(250): # 二進数でO,Xの桁数より大きい数
if O & (1 << i): # (ii)
if X & (1 << i): # (ii-ii)
M += 2 ** i
else: # (ii-i)
M += 2 ** (i + 1)
else: # (i)
pass
print(long_to_bytes(M))
+ print(long_to_bytes(2*O-X))
なんと同じ結果が出ます 先人、よく見つけたなこの式...