結果・感想
WaniCTF2023に参加しました。高専時代の先輩たちのチームに混ぜてもらいました。
20位でした！個人では、cryptoのpqqp, fusion、miscのrange_xor, int_generatorを解きました。
4つとも数学とか競プロっぽくて面白かったです。
もくじ
解説
自分が解いた問題の解説をします。
Misc range-xor
この問題は完全に競プロです。i番目の整数まで見て、その時点で0~1023の各整数が作れるか、作れるなら何通りかを保管するDP。modintとboolを持てばよい。boolをわざわざ持つ理由としては、modをしたときにもしかしたら0になってしまう可能性があるため(さすがにないとは思った)。
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
#define rep(i, n) for(int i=0;i<n;i++)
#define all(i, v) for(auto& i : v)
typedef long long ll;
using namespace std;
const ll MOD7 = 1000000007, MOD998 = 998244353, INF = (1LL<<60);
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;
template<int MOD> struct Modint {
long long val;
constexpr Modint(long long v = 0) noexcept : val(v % MOD) { if (val < 0) val += MOD; }
constexpr int mod() const { return MOD; }
constexpr Modint operator - () const noexcept { return val ? MOD - val : 0; }
constexpr Modint operator + (const Modint& r) const noexcept { return Modint(*this) += r; }
constexpr Modint operator - (const Modint& r) const noexcept { return Modint(*this) -= r; }
constexpr Modint operator * (const Modint& r) const noexcept { return Modint(*this) *= r; }
constexpr Modint operator / (const Modint& r) const noexcept { return Modint(*this) /= r; }
constexpr Modint& operator += (const Modint& r) noexcept {
val += r.val;
if (val >= MOD) val -= MOD;
return *this;
}
constexpr Modint& operator -= (const Modint& r) noexcept {
val -= r.val;
if (val < 0) val += MOD;
return *this;
}
constexpr Modint& operator *= (const Modint& r) noexcept {
val = val * r.val % MOD;
return *this;
}
constexpr Modint& operator /= (const Modint& r) noexcept {
long long a = r.val, b = MOD, u = 1, v = 0;
while (b) {
long long t = a / b;
a -= t * b, swap(a, b);
u -= t * v, swap(u, v);
}
val = val * u % MOD;
if (val < 0) val += MOD;
return *this;
}
constexpr bool operator == (const Modint& r) const noexcept { return this->val == r.val; }
constexpr bool operator != (const Modint& r) const noexcept { return this->val != r.val; }
friend constexpr istream& operator >> (istream& is, Modint<MOD>& x) noexcept {
is >> x.val;
x.val %= MOD;
if (x.val < 0) x.val += MOD;
return is;
}
friend constexpr ostream& operator << (ostream& os, const Modint<MOD>& x) noexcept {
return os << x.val;
}
constexpr Modint<MOD> pow(long long n) noexcept {
if (n == 0) return 1;
if (n < 0) return this->pow(-n).inv();
Modint<MOD> ret = pow(n >> 1);
ret *= ret;
if (n & 1) ret *= *this;
return ret;
}
constexpr Modint<MOD> inv() noexcept {
long long a = this->val, b = MOD, u = 1, v = 0;
while (b) {
long long t = a / b;
a -= t * b, swap(a, b);
u -= t * v, swap(u, v);
}
return Modint<MOD>(u);
}
};
const int MOD = MOD7;
using mint = Modint<MOD>;
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int n = 1000;
vector<mint> dp1(1024, 0);
vector<int> dp2(1024, 0);
dp1[0] = 1;
dp2[0] = 1;
rep(i, n) {
int a;
cin >> a;
vector<mint> nx1(1024, 0);
vector<int> nx2(1024, 0);
int num = min(a, 1000 - a);
for(int j = 0; j < 1024; j ++) {
nx1[j ^ a] += dp1[j];
nx2[j ^ a] |= dp2[j];
if(num != a) {
swap(num, a);
nx1[j ^ a] += dp1[j];
nx2[j ^ a] |= dp2[j];
}
}
swap(nx1, dp1);
swap(nx2, dp2);
}
for(int i = 0; i < 1024; i ++) {
if(dp2[i]) {
cout << dp1[i].val << endl;
return 0;
}
}
return 0;
}
コンパイル、実行し、入力で与えられた整数を入れると461905191が出力される。
Misc int-generator
解いたときFAの次だったので興奮した。
chall.pyを以下のように改造して実行した。
つまり、flag1, 2は前から探索、flag3は後ろから探索すると見つかりやすい。
flag2は数分待たないとでてこなかった。申し訳程度に書き換えて実行したらでた。
def f(x):
if x == 0 or x == 2**36:
return -x
if x * x % (2**36) != 0:
return -x
else:
return -x * (x - (2**36)) // (2**36)
def g(x):
ret = x * 2 + x // 3 * 10 - x // 5 * 10 + x // 7 * 10
ret = ret - ret % 2 + 1
return ret, x // 100 % 100
def digit(x):
cnt = 0
while x > 0:
cnt += 1
x //= 10
return cnt
def pad(x, cnt):
minus = False
if x < 0:
minus = True
x, cnt = g(-x)
sub = 16 - digit(x)
ret = x
for i in range(sub - digit(cnt)):
ret *= 10
if minus:
ret += pow(x % 10, x % 10 * i, 10)
else:
ret += pow(i % 10 - i % 2, i % 10 - i % 2 + 1, 10)
ret += cnt * 10 ** (16 - digit(cnt))
return ret
def int_generator(x):
ret = -x
x_ = f(x)
cnt = 1
while x_ > 0:
ret = x_
x_ = f(x_)
cnt += 1
return pad(ret, cnt)
X = 1008844668800884
for i in range(100000000):
if int_generator(i) == X:
print(i)
break
X = 2264663430088446
for i in range(100000000):
if int_generator(i) == X:
print(i)
break
X = 6772814078400884
for i in range(1 << 35, 0, -1):
if int_generator(i) == X:
print(i)
break
実行結果
0
26476544
34359738368
Crypto pqqp
p, qを求めるヒントとして(pow(p, q, n) + pow(q, p, n)) % nの値が与えられている。
実は、フェルマーの小定理から、これはp+qの値に等しいことがわかる。s = p + qとn = pqの値がわかっているため、p, qの値が求められる。
import math
from Crypto.Util.number import long_to_bytes
n = 31091873146151684702346697466440613735531637654275447575291598179592628060572504006592135492973043411815280891993199034777719870850799089897168085047048378272819058803065113379019008507510986769455940142811531136852870338791250795366205893855348781371512284111378891370478371411301254489215000780458922500687478483283322613251724695102723186321742517119591901360757969517310504966575430365399690954997486594218980759733095291730584373437650522970915694757258900454543353223174171853107240771137143529755378972874283257666907453865488035224546093536708315002894545985583989999371144395769770808331516837626499129978673
e = 65537
c = 8684906481438508573968896111659984335865272165432265041057101157430256966786557751789191602935468100847192376663008622284826181320172683198164506759845864516469802014329598451852239038384416618987741292207766327548154266633297700915040296215377667970132408099403332011754465837054374292852328207923589678536677872566937644721634580238023851454550310188983635594839900790613037364784226067124711011860626624755116537552485825032787844602819348195953433376940798931002512240466327027245293290482539610349984475078766298749218537656506613924572126356742596543967759702604297374075452829941316449560673537151923549844071
s = 352657755607663100038622776859029499529417617019439696287530095700910959137402713559381875825340037254723667371717152486958935653311880986170756144651263966436545612682410692937049160751729509952242950101025748701560375826993882594934424780117827552101647884709187711590428804826054603956840883672204048820926
a = math.isqrt(s * s - n * 4)
p = (s + a) // 2
q = (s - a) // 2
d = pow(e, -1, (p - 1) * (q - 1))
print(long_to_bytes(pow(c, d, p * q)))
実行結果
b'FLAG{p_q_p_q_521d0bd0c28300f}'
Crypto fusion
与えられたshall.pyを見つめると、まずやることとして、rの奇数bit目と偶数bit目をpとqに分解することができる。
from Crypto.PublicKey import RSA
RSAkeys = RSA.generate(2048)
p = RSAkeys.p
q = RSAkeys.q
n = RSAkeys.n
e = RSAkeys.e
m = b"FAKE{<REDACTED>}"
c = pow(int.from_bytes(m, "big"), e, n)
mask = int("55" * 128, 16)
r = p & mask
mask = mask << 1
r += q & mask
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"r = {r}")
最下位bitはnが1、p, qの片方が1なのでもう片方も1となる。
そして、n[i] = (繰り上がり) + p[i] * q[0] + p[i - 1] * q[1] + ... + p[0]q[i]となり、この中で確定していないのはp[i]とq[i]の片方だけである。p[0]=q[0]=1なので、p[i], q[i]の値によって1足されるかどうかとなる。そしてこれは偶奇を見ればよく、「繰り上がりを含めた総和」と「nのi bit目」の差が奇数なら1にする、偶数なら0にすればよい。そうすることで最終的な差が偶数となり、2で割って繰り上がりにできる。
mask(len(bin(mask)) - 2) = 1023なので1023bitは確定しているっぽい。ので、そこまではp, qを確定させられるが…。
それ以降はbit全探索を使います！p, qどっちでもいいのですが、続きの15bitくらいをbit全探索しました。nで割り切れるものがあればp, qを求めることができたと言えます。
まず以下でp, qを求めます。
mask = int("55" * 128, 16)
n = 27827431791848080510562137781647062324705519074578573542080709104213290885384138112622589204213039784586739531100900121818773231746353628701496871262808779177634066307811340728596967443136248066021733132197733950698309054408992256119278475934840426097782450035074949407003770020982281271016621089217842433829236239812065860591373247969334485969558679735740571326071758317172261557282013095697983483074361658192130930535327572516432407351968014347094777815311598324897654188279810868213771660240365442631965923595072542164009330360016248531635617943805455233362064406931834698027641363345541747316319322362708173430359
e = 65537
c = 887926220667968890879323993322751057453505329282464121192166661668652988472392200833617263356802400786530829198630338132461040854817240045862231163192066406864853778440878582265466417227185832620254137042793856626244988925048088111119004607890025763414508753895225492623193311559922084796417413460281461365304057774060057555727153509262542834065135887011058656162069317322056106544821682305831737729496650051318517028889255487115139500943568231274002663378391765162497239270806776752479703679390618212766047550742574483461059727193901578391568568448774297557525118817107928003001667639915132073895805521242644001132
r = 163104269992791295067767008325597264071947458742400688173529362951284000168497975807685789656545622164680196654779928766806798485048740155505566331845589263626813345997348999250857394231703013905659296268991584448212774337704919390397516784976219511463415022562211148136000912563325229529692182027300627232945
num = r
d = 1
p = 0
q = 0
for i in range(1023):
if i & 1:
if num & 1:
q += d
else :
if num & 1:
p += d
num >>= 1
d <<= 1
q += 1
d = 1
k = 0
for i in range(1, 1023):
d <<= 1
ans = k - (n >> i & 1)
for j in range(i + 1):
ans += (p >> j & 1) * (q >> (i - j) & 1)
if ((ans % 2) + 2) % 2 == 1:
ans += 1
if i & 1:
p += d
else :
q += d
k = ans // 2
lim = 1 << 15
ans1 = []
ans2 = []
flag = False
for bit in range(lim):
pnow = p
for i in range(15):
if bit >> i & 1:
pnow += 1 << (1023 + i)
if n % pnow == 0:
ans1.append(pnow)
ans2.append(n // pnow)
for bit in range(lim):
pnow = q
for i in range(15):
if bit >> i & 1:
pnow += 1 << (1023 + i)
if n % pnow == 0:
ans1.append(n // pnow)
ans2.append(pnow)
print(ans1[0])
print(ans2[0])
出力はこうなりました。上をp、下をqとしましょう。
158982482761532936352511330658816601706429032258548834912125273034488997046490434244533210801707343036413253864390713073589522875165458597351216083121996049787719375116167821890856038886439850595034188390482176192712663134014807479657958971828756944383908361170612935098217276884087156156071510999037803600539
175034578077309701984181964268308339398388268617712324238289276804454728925416562859929986131078776699682249344599789995987665924833218204252743836262945362936105111796551388997258331666189228142473360653861656406464150833269243661900931849107877401563507303666653995787300006491378116771557849415731270875381
これらを使ってフラグを求めます。
from Crypto.Util.number import *
p = 158982482761532936352511330658816601706429032258548834912125273034488997046490434244533210801707343036413253864390713073589522875165458597351216083121996049787719375116167821890856038886439850595034188390482176192712663134014807479657958971828756944383908361170612935098217276884087156156071510999037803600539
q = 175034578077309701984181964268308339398388268617712324238289276804454728925416562859929986131078776699682249344599789995987665924833218204252743836262945362936105111796551388997258331666189228142473360653861656406464150833269243661900931849107877401563507303666653995787300006491378116771557849415731270875381
e = 65537
d = pow(e, -1, (p - 1) * (q - 1))
c = 887926220667968890879323993322751057453505329282464121192166661668652988472392200833617263356802400786530829198630338132461040854817240045862231163192066406864853778440878582265466417227185832620254137042793856626244988925048088111119004607890025763414508753895225492623193311559922084796417413460281461365304057774060057555727153509262542834065135887011058656162069317322056106544821682305831737729496650051318517028889255487115139500943568231274002663378391765162497239270806776752479703679390618212766047550742574483461059727193901578391568568448774297557525118817107928003001667639915132073895805521242644001132
m = pow(c, d, p * q)
m = long_to_bytes(m)
print(m.decode())
実行結果は以下。
FLAG{sequ4ntia1_prim4_fact0rizati0n}
Crypto fusion あとがき
さて、今気づいたのですが、print(len(bin(mask)) - 2)で1023だったので1023bit確定させられる！って言ってたんですが、maskを1bitずらしていることに注目すれば、1024bit確定させられることに気づき、そこまで確定したらpq = nになりました。bit全探索いらなかった…。
mask = int("55" * 128, 16)
n = 27827431791848080510562137781647062324705519074578573542080709104213290885384138112622589204213039784586739531100900121818773231746353628701496871262808779177634066307811340728596967443136248066021733132197733950698309054408992256119278475934840426097782450035074949407003770020982281271016621089217842433829236239812065860591373247969334485969558679735740571326071758317172261557282013095697983483074361658192130930535327572516432407351968014347094777815311598324897654188279810868213771660240365442631965923595072542164009330360016248531635617943805455233362064406931834698027641363345541747316319322362708173430359
e = 65537
c = 887926220667968890879323993322751057453505329282464121192166661668652988472392200833617263356802400786530829198630338132461040854817240045862231163192066406864853778440878582265466417227185832620254137042793856626244988925048088111119004607890025763414508753895225492623193311559922084796417413460281461365304057774060057555727153509262542834065135887011058656162069317322056106544821682305831737729496650051318517028889255487115139500943568231274002663378391765162497239270806776752479703679390618212766047550742574483461059727193901578391568568448774297557525118817107928003001667639915132073895805521242644001132
r = 163104269992791295067767008325597264071947458742400688173529362951284000168497975807685789656545622164680196654779928766806798485048740155505566331845589263626813345997348999250857394231703013905659296268991584448212774337704919390397516784976219511463415022562211148136000912563325229529692182027300627232945
num = r
d = 1
p = 0
q = 0
for i in range(1024):
if i & 1:
if num & 1:
q += d
else :
if num & 1:
p += d
num >>= 1
d <<= 1
q += 1
d = 1
k = 0
for i in range(1, 1024):
d <<= 1
ans = k - (n >> i & 1)
for j in range(i + 1):
ans += (p >> j & 1) * (q >> (i - j) & 1)
if ((ans % 2) + 2) % 2 == 1:
ans += 1
if i & 1:
p += d
else :
q += d
k = ans // 2
print(p)
print(q)
print(p * q == n)
実行結果
158982482761532936352511330658816601706429032258548834912125273034488997046490434244533210801707343036413253864390713073589522875165458597351216083121996049787719375116167821890856038886439850595034188390482176192712663134014807479657958971828756944383908361170612935098217276884087156156071510999037803600539
175034578077309701984181964268308339398388268617712324238289276804454728925416562859929986131078776699682249344599789995987665924833218204252743836262945362936105111796551388997258331666189228142473360653861656406464150833269243661900931849107877401563507303666653995787300006491378116771557849415731270875381
True
余談
CTFは実質未経験で、普段は競プロerをやっています。
AtCoder黄色で、その知識で殴った感じです。
これまでのCTFの経験と言えば、高専時代に学内のCTF会に参加したのと、CpawCTFを埋めたくらいしかないです。阪大だと2年くらいでCTFの授業があるらしいですが編入生なので知らない子です…。
さて、このGWはといえば、4/30は阪大のいちょう祭に行き、その後は実家でサークル活動という名の競プロをやっておりました。WaniCTFのあった3日間に重なって3日間のHUPCがありました。また、競技プログラミング部RAINBOUでは部内ライブラリを作成をしております。日々、「ここはこうしたい、えーグラフテンプレートなんて使わないよ～」という宗教戦争が勃発中でございます。
