SECCON 2022 CTF writeup (pqpq)
問題
暗号化の手順を示したソースコードと、その実行結果が与えられる。特殊な RSA 暗号で暗号化されている cm を復号すればいい問題。
from Crypto.Util.number import *
from Crypto.Random import *
from flag import flag
p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
n = p * q * r
e = 2 * 65537
assert n.bit_length() // 8 - len(flag) > 0
padding = get_random_bytes(n.bit_length() // 8 - len(flag))
m = bytes_to_long(padding + flag)
assert m < n
c1p = pow(p, e, n)
c1q = pow(q, e, n)
cm = pow(m, e, n)
c1 = (c1p - c1q) % n
c2 = pow(p - q, e, n)
print(f"e = {e}")
print(f"n = {n}")
# p^e - q^e mod n
print(f"c1 = {c1}")
# (p-q)^e mod n
print(f"c2 = {c2}")
# m^e mod n
print(f"cm = {cm}")
e = 131074
n = 587926815910957928506680558951380405698765957736660571041732511939308424899531125274073420353104933723578377320050609109973567093301465914201779673281463229043539776071848986139657349676692718889679333084650490543298408820393827884588301690661795023628407437321580294262453190086595632660415087049509707898690300735866307908684649384093580089579066927072306239235691848372795522705863097316041992762430583002647242874432616919707048872023450089003861892443175057
c1 = 92883677608593259107779614675340187389627152895287502713709168556367680044547229499881430201334665342299031232736527233576918819872441595012586353493994687554993850861284698771856524058389658082754805340430113793873484033099148690745409478343585721548477862484321261504696340989152768048722100452380071775092776100545951118812510485258151625980480449364841902275382168289834835592610827304151460005023283820809211181376463308232832041617730995269229706500778999
c2 = 46236476834113109832988500718245623668321130659753618396968458085371710919173095425312826538494027621684566936459628333712619089451210986870323342712049966508077935506288610960911880157875515961210931283604254773154117519276154872411593688579702575956948337592659599321668773003355325067112181265438366718228446448254354388848428310614023369655106639341893255469632846938342940907002778575355566044700049191772800859575284398246115317686284789740336401764665472
cm = 357982930129036534232652210898740711702843117900101310390536835935714799577440705618646343456679847613022604725158389766496649223820165598357113877892553200702943562674928769780834623569501835458020870291541041964954580145140283927441757571859062193670500697241155641475887438532923910772758985332976303801843564388289302751743334888885607686066607804176327367188812325636165858751339661015759861175537925741744142766298156196248822715533235458083173713289585866
問題の詳細
普通の RSA だと 2 つの素数を使って暗号化するが、この問題では 3 つの素数
また、出力として、
方針
まず
次に
その
つまり、以下の 3 ステップで求められる。
- n を素因数分解する
- cm を復号して m^2 を得る
- m^2 の平方剰余を求める
n を素因数分解する
という式が得られる。
が言える。
が成り立つことがわかる。それぞれ足したり引いたりすることで、
が得られる。上の式の左辺は p の倍数、下の式の左辺は q の倍数でないといけないことがわかる。
cm を復号して m^2 を得る
と求めることができる。
m^2 の平方剰余を求める
後は
と分解して、それぞれの平方剰余を求める。ここで注意するのは平方根は剰余であっても(存在すれば) 2 つ出ることである。なので元に戻すのは 8 パターンある。
今回はフラグの文字列として SECCON が含まれることが保証されているので、その文字列が含まれているかで確認する。
求めるコード
import math
import random
import sympy.ntheory.modular as mod
e = 131074
n = 587926815910957928506680558951380405698765957736660571041732511939308424899531125274073420353104933723578377320050609109973567093301465914201779673281463229043539776071848986139657349676692718889679333084650490543298408820393827884588301690661795023628407437321580294262453190086595632660415087049509707898690300735866307908684649384093580089579066927072306239235691848372795522705863097316041992762430583002647242874432616919707048872023450089003861892443175057
c1 = 92883677608593259107779614675340187389627152895287502713709168556367680044547229499881430201334665342299031232736527233576918819872441595012586353493994687554993850861284698771856524058389658082754805340430113793873484033099148690745409478343585721548477862484321261504696340989152768048722100452380071775092776100545951118812510485258151625980480449364841902275382168289834835592610827304151460005023283820809211181376463308232832041617730995269229706500778999
c2 = 46236476834113109832988500718245623668321130659753618396968458085371710919173095425312826538494027621684566936459628333712619089451210986870323342712049966508077935506288610960911880157875515961210931283604254773154117519276154872411593688579702575956948337592659599321668773003355325067112181265438366718228446448254354388848428310614023369655106639341893255469632846938342940907002778575355566044700049191772800859575284398246115317686284789740336401764665472
cm = 357982930129036534232652210898740711702843117900101310390536835935714799577440705618646343456679847613022604725158389766496649223820165598357113877892553200702943562674928769780834623569501835458020870291541041964954580145140283927441757571859062193670500697241155641475887438532923910772758985332976303801843564388289302751743334888885607686066607804176327367188812325636165858751339661015759861175537925741744142766298156196248822715533235458083173713289585866
def sqrtPrime(n, p):
q = p - 1
m = 0
while q & 1 == 0:
q >>= 1
m += 1
z = 1
while pow(z, (p - 1) >> 1, p) == 1:
z = random.randint(1, p - 1)
c = pow(z, q, p)
t = pow(n, q, p)
r = pow(n, (q + 1) >> 1, p)
if t == 0:
return 0
m -= 2
while t != 1:
while pow(t, 2**m, p) == 1:
c = c * c % p
m -= 1
r = r * c % p
c = c * c % p
t = t * c % p
m -= 1
return r
p = math.gcd(c1 + c2, n)
q = math.gcd(c1 - c2, n)
r = n // (p * q)
d = pow(e // 2, -1, (p - 1) * (q - 1) * (r - 1))
m2 = pow(cm, d, n)
m2p = m2 % p
m2q = m2 % q
m2r = m2 % r
pm = sqrtPrime(m2p, p)
qm = sqrtPrime(m2q, q)
rm = sqrtPrime(m2r, r)
m = 0
for tp in [pm, p - pm]:
for tq in [qm, q - qm]:
for tr in [rm, r - rm]:
(ttt, _) = mod.crt([p, q, r], [tp, tq, tr])
t = ttt.to_bytes(256, byteorder="big")
if b"SECCON" in t:
print(t[t.find(b"SECCON") :].decode("utf-8"))
※平方剰余のアルゴリズムはこのサイトを参考にさせていただきました。
余談
めっちゃ分かった風に書いているが、実は解けなかった問題である(笑)。
Discussion