Flag is A+B — Daily AlpacaHack

コード

from Crypto.Util.number import bytes_to_long
import os
import random

FLAG = bytes_to_long(os.getenv("FLAG", "Alpaca{DUMMY}").encode())

A = random.randint(0, FLAG)
B = FLAG - A

assert A + B == FLAG

print(f"A or B = {A | B}")
print(f"A xor B = {A ^ B}")

🤔

• A or B と A xor B から、演算 A + B の結果を得よという問題

  • とりあえず真理値表を書いてみる

  入力 A	入力 B	OR	XOR	A+B
  0	0	0	0	0
  0	1	1	1	1
  1	0	1	1	1
  1	1	1	0	2

  • (OR, XOR) = (1,1) のとき (A, B) が一意に定まらないので、 A, B そのものは復元できなさそうだ
    • A + B を求めるなら区別しなくていいが、(A, B) = (1, 1) のときの繰り上がりは考えねばならない

• というわけで、全加算機を考える

  • a AND b = a OR b AND (NOT a XOR b) であるから、これを利用すればできる
  • 証明

• ここで

  • Cin を一つ小さい位からの繰り上がりとする
  • Cout を次に大きい位への繰り上がりとする

| A | B | Cin (繰り上がり) | A XOR B | A AND B | Cout (繰り上げる) | 和 | | --- | --- | --- | --- | --- | --- | --- | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 0 | 0 | 1 | 0 | 0 | 0 | 1 | | 0 | 1 | 0 | 1 | 0 | 0 | 1 | | 0 | 1 | 1 | 1 | 0 | 1 | 0 | | 1 | 0 | 0 | 1 | 0 | 0 | 1 | | 1 | 0 | 1 | 1 | 0 | 1 | 0 | | 1 | 1 | 0 | 0 | 1 | 1 | 0 | | 1 | 1 | 1 | 0 | 1 | 1 | 1 |

• この表に準じて、一番小さい位からひとつずつ大きい位へ計算していけばよい
  • e.g. a XOR b = 0, a AND b = 1, Cin = 0 のとき、和 = 0, Cout = 1 なので、 flagの位は 0 を記録し、次に大きい位の計算の時 Cin = 1 にする

solve

a_or_b = 1708520672692343497693425015709016883325158039728511260268583494549501
a_xor_b = 1653224853895272618878301831150773792186632776885840473347068872416893

# AND = a_OR_b & (NOT a_XOR_b)
# 真理値表を書けばいい
a_and_b = a_or_b & ~a_xor_b

# A + B を計算する
#   繰り上がり P_i = A_i ^ B_i
#   1の位の和  G_i = A_i & B_i
#   下の位からの繰り上がりを足して、和は P_i ^ carry_in
#   次の位への繰り上がりは             G_i | (P_i & carry_in)
bit_len = max(a_or_b.bit_length(), a_xor_b.bit_length())

# full adder を実装する
carry = 0
total = 0
for i in range(bit_len):
    p = (a_xor_b >> i) & 1
    g = (a_and_b >> i) & 1
    s = p ^ carry
    carry = g | (p & carry)
    total |= s << i
total |= carry << bit_len

flag = total.to_bytes((total.bit_length() + 7) // 8, "big")
print(flag)

Solve (shorter)

実は a XOR b は繰り上がりを無視した各位の和、a AND b は次の位への繰り上がりの有無である よって、a AND b を左に1 bitシフトしたのち a XOR b と和をとることもできる

a_or_b = 1708520672692343497693425015709016883325158039728511260268583494549501
a_xor_b = 1653224853895272618878301831150773792186632776885840473347068872416893

# もっと短い解き方もある
# a XOR b が「繰り上がりのない和」(0 + 1 = 1 になるが 1 + 1 = 0) で、
# a AND b が 繰り上がりであることから、
# 結局これの和を取ってやればいい
total = a_xor_b + (a_and_b<<1)

flag = total.to_bytes((total.bit_length() + 7) // 8, "big")
print(flag)