海河工匠杯wp

河海工匠杯 个人wp

虽然赛题不很难，但是鉴于主包第一次参加的赛事，记录一下叭

1.crack_RSA

题目：

N : 460657813884289609896372056585544172485318117026246263899744329237492701820627219556007788200590119136173895989001382151536006853823326382892363143604314518686388786002989248800814861248595075326277099645338694977097459168530898776007293695728101976069423971696524237755227187061418202849911479124793990722597
e : 354611102441307572056572181827925899198345350228753730931089393275463916544456626894245415096107834465778409532373187125318554614722599301791528916212839368121066035541008808261534500586023652767712271625785204280964688004680328300124849680477105302519377370092578107827116821391826210972320377614967547827619
enc : 38230991316229399651823567590692301060044620412191737764632384680546256228451518238842965221394711848337832459443844446889468362154188214840736744657885858943810177675871991111466653158257191139605699916347308294995664530280816850482740530602254559123759121106338359220242637775919026933563326069449424391192

看到这中没有任何提示的rsa题目补药怕呀，往往只是吓吓你而已
rsa常规流程走一便：

n可以暴力分解！
剩下就好说咯

from Crypto.Util.number import *
from gmpy2 import *
p =15991846970993213322072626901560749932686325766403404864023341810735319249066370916090640926219079368845510444031400322229147771682961132420481897362843199
q = 28805791771260259486856902729020438686670354441296247148207862836064657849735343618207098163901787287368569768472521344635567334299356760080507454640207003
e = 354611102441307572056572181827925899198345350228753730931089393275463916544456626894245415096107834465778409532373187125318554614722599301791528916212839368121066035541008808261534500586023652767712271625785204280964688004680328300124849680477105302519377370092578107827116821391826210972320377614967547827619
enc = 38230991316229399651823567590692301060044620412191737764632384680546256228451518238842965221394711848337832459443844446889468362154188214840736744657885858943810177675871991111466653158257191139605699916347308294995664530280816850482740530602254559123759121106338359220242637775919026933563326069449424391192
N = 460657813884289609896372056585544172485318117026246263899744329237492701820627219556007788200590119136173895989001382151536006853823326382892363143604314518686388786002989248800814861248595075326277099645338694977097459168530898776007293695728101976069423971696524237755227187061418202849911479124793990722597

phi = (p-1)*(q-1)
d = inverse(e, phi)
m = pow(enc,d,N)
print(long_to_bytes(m))

什么？你说没法爆破怎么办？跳了呗，下一题（bushi）
另解：观察特点，发现e非常大，由此也可以看出d会很小，可以尝试winner攻击
RSA的密钥满足：ed - k·φ(n) = 1（k为正整数），变形得：

$ed = k·φ(n) + 1$

• 欧拉函数φ(n) = (p-1)(q-1) = n - (p+q) + 1，由于p和q是大素数，p+q远小于n，因此φ(n) ≈ n；

• 将ed = k·φ(n) + 1两边除以d·φ(n)：

  $\frac{e}{φ(n)} = \frac{k}{d} + \frac{1}{d·φ(n)}$

• 忽略极小项1/(d·φ(n))，结合φ(n)≈n，可得核心近似关系：

  $\frac{e}{n} ≈ \frac{k}{d}$

对 $\frac{e}{n}$ 连分数展开便有可能得出k与n咯

import gmpy2
import libnum

def continued_fraction(x, y):
    """计算连分数展开序列
    :param x: 分子 (e)
    :param y: 分母 (n)
    :return: 连分数列表
    """
    cf = []
    while y:
        cf.append(x // y)
        x, y = y, x % y
    return cf

def gradual_convergents(cf):
    """生成所有渐进分数 (k/d)
    :param cf: 连分数列表
    :yield: (分子k, 分母d)
    """
    numerator_prev, numerator_curr = 0, 1
    denominator_prev, denominator_curr = 1, 0
    for q in cf:
        numerator_next = q * numerator_curr + numerator_prev
        denominator_next = q * denominator_curr + denominator_prev
        numerator_prev, numerator_curr = numerator_curr, numerator_next
        denominator_prev, denominator_curr = denominator_curr, denominator_next
        yield (numerator_curr, denominator_curr)

def solve_pq(a, b, c):
    """通过二次方程分解n=p*q
    :param a: x²系数 (固定为1)
    :param b: x系数 (n - phi + 1)
    :param c: 常数项 (n)
    :return: p, q
    """
    delta = b**2 - 4*a*c
    if delta < 0: return None
    sqrt_delta = gmpy2.isqrt(delta)
    if sqrt_delta * sqrt_delta != delta:
        return None
    p = (-b + sqrt_delta) // (2 * a)
    q = (-b - sqrt_delta) // (2 * a)
    return (p, q) if p * q == c else None

def wiener_attack(e, n):
    """维纳攻击主函数
    :param e: 公钥e
    :param n: 模数n
    :return: 私钥d 或 None
    """
    cf = continued_fraction(e, n)
    for k, d in gradual_convergents(cf):
        if k == 0: continue
        if (e * d - 1) % k != 0:
            continue
        phi = (e * d - 1) // k
        pq = solve_pq(1, n - phi + 1, n)
        if pq:
            p, q = pq
            if p * q == n:
                return d
    return None

if __name__ == "__main__":
    # 测试数据（替换为实际参数）
    n = 460657813884289609896372056585544172485318117026246263899744329237492701820627219556007788200590119136173895989001382151536006853823326382892363143604314518686388786002989248800814861248595075326277099645338694977097459168530898776007293695728101976069423971696524237755227187061418202849911479124793990722597
    e = 354611102441307572056572181827925899198345350228753730931089393275463916544456626894245415096107834465778409532373187125318554614722599301791528916212839368121066035541008808261534500586023652767712271625785204280964688004680328300124849680477105302519377370092578107827116821391826210972320377614967547827619
    c = 38230991316229399651823567590692301060044620412191737764632384680546256228451518238842965221394711848337832459443844446889468362154188214840736744657885858943810177675871991111466653158257191139605699916347308294995664530280816850482740530602254559123759121106338359220242637775919026933563326069449424391192   
    d = wiener_attack(e, n)
    if d:
        print(f"[+] 私钥d = {d}")
        m = pow(c, d, n)
        print(f"[+] 明文 = {libnum.n2s(int(m)).decode()}")
    else:
        print("[-] 攻击失败，可能d不满足维纳条件")

2.command

题目

from secret import flag
from Crypto.Util.number import *

p = getPrime(1024)
q1 = getPrime(1024)
q2 = getPrime(1024)

n1 = p * q1
n2 = p * q2
e  = 0x10001

m = bytes_to_long(flag)
c1 = pow(m, e, n1)
c2 = pow(m, e, n2)

print(c1)
print(n1)
print(c2)
print(n2)


# 4941707047346667175208995859949404389322583225976420544331062614693386809791615029343678778664425048376340187366155043564992194252492261601744888865226804666848581371609771137227420031942968451977653728169798389786353613232575562480592642357804748184143027923004426192328699886075682903734608470957863437094162637828629980861061313193478602945671274941820713441068765686829372743052820131555406957764726286667754643454059540313131391568239032095090368445897408669444308899803560012425357607296170299089198157608947328661673814435023280124404645125994375763555334414315256063016251526584818376451642455251523209255802
# 23870161680183523079741569974844567326019753076392636009584986567612198552769297327520140947753967201209251923569250042808435602604746173316812218561002639890627852637259978806388826042450311742551247657942180612619269580501221658861246087292389488686348455622638650573340684120087995899502358420625262078225393838288965001923426876996521245801399902175648882304659224530399947903626889562357334105116376279410129681393098230440046021549860624097368418577529956483763264706086840482433245189236097197915840133182908767740904012654564998517212402393117912683093507460179360440863741119755955402495890705201911376608287
# 15361482578239201122825735518613560425956918915682082355755400248771835488441342237398430042762133757967330714360779296866589247720714355380496678719262004338885321961470744042111217118574883401901820510469999875432217721036106005542885036119619624821458268716392152006782899996387626674519404398439643754050298394226768471302131781460214161254895195587947346312072521081253756073686949674898685783707405534113832058397514942338528976019855060111031531673705000954520440402528450353772060433440812396824325761264326895396370502262440389779595049703594280011852963627217339075366282031362737198717406376555679069806258
# 27799578924743649991986024628153641945800733904267409387203138015966552861634251919848520890705796293509399305155356061091874177186618542710179261647491030477309736237809439680701450990170747064756974278248222130804744789442182601317629449781655995599376757972019189878891496801811940270932663639537402645346568086063480094758375696668553141406635142266030261394906382884967081494979457009425568148790959718481235323099812941999183305133433926721515800515742432246719644508578309303020326602709313629970737948300830614693840686955065188058995026232804383907013878621481775642198847855961249614692528029044092622003431

看看出题入的巧思在哪里？注意到：

n1 = p * q1
n2 = p * q2

n1n2已知，可以利用欧几里得算法求p，p既出，则题解！

from Crypto.Util.number import *
from gmpy2 import *

c1 = 4941707047346667175208995859949404389322583225976420544331062614693386809791615029343678778664425048376340187366155043564992194252492261601744888865226804666848581371609771137227420031942968451977653728169798389786353613232575562480592642357804748184143027923004426192328699886075682903734608470957863437094162637828629980861061313193478602945671274941820713441068765686829372743052820131555406957764726286667754643454059540313131391568239032095090368445897408669444308899803560012425357607296170299089198157608947328661673814435023280124404645125994375763555334414315256063016251526584818376451642455251523209255802
n1 = 23870161680183523079741569974844567326019753076392636009584986567612198552769297327520140947753967201209251923569250042808435602604746173316812218561002639890627852637259978806388826042450311742551247657942180612619269580501221658861246087292389488686348455622638650573340684120087995899502358420625262078225393838288965001923426876996521245801399902175648882304659224530399947903626889562357334105116376279410129681393098230440046021549860624097368418577529956483763264706086840482433245189236097197915840133182908767740904012654564998517212402393117912683093507460179360440863741119755955402495890705201911376608287
c2 = 15361482578239201122825735518613560425956918915682082355755400248771835488441342237398430042762133757967330714360779296866589247720714355380496678719262004338885321961470744042111217118574883401901820510469999875432217721036106005542885036119619624821458268716392152006782899996387626674519404398439643754050298394226768471302131781460214161254895195587947346312072521081253756073686949674898685783707405534113832058397514942338528976019855060111031531673705000954520440402528450353772060433440812396824325761264326895396370502262440389779595049703594280011852963627217339075366282031362737198717406376555679069806258
n2 = 27799578924743649991986024628153641945800733904267409387203138015966552861634251919848520890705796293509399305155356061091874177186618542710179261647491030477309736237809439680701450990170747064756974278248222130804744789442182601317629449781655995599376757972019189878891496801811940270932663639537402645346568086063480094758375696668553141406635142266030261394906382884967081494979457009425568148790959718481235323099812941999183305133433926721515800515742432246719644508578309303020326602709313629970737948300830614693840686955065188058995026232804383907013878621481775642198847855961249614692528029044092622003431
e = 0x10001

p = gcd(n1, n2)
q1 = n1 // p
phi = (p - 1) * (q1 - 1)
d = inverse(e, phi)
m = pow(c1, d, n1)
print(long_to_bytes(m))

3.affine

y = 11*x+7 试对密文dikhkkruz解密,答案格式：flag{********}

凯撒仿射啦，直接喂ai吧
但是有解密公式就好办了：x = 19 * (y - 7) mod

---

补充一下：

1. 凯撒密码与仿射密码

   • 凯撒密码是仿射密码在 $a=1$ 时的特例。

   • 仿射密码的密钥空间更大（ $a$ 有 12 种选择， $b$ 有 26 种选择，共 $12 \times 26 = 312$ 种密钥），而凯撒密码只有 26 种密钥。

---

密文字母	密文数字(y)	(y-7) mod26	19*(y-7) mod26	明文数字(x)	明文字母
d	3	22	22*19=418 mod26=2	2	c
i	8	1	19 mod26=19	19	t
k	10	3	57 mod26=5	5	f
h	7	0	0 mod26=0	0	a
k	10	3	57 mod26=5	5	f
k	10	3	57 mod26=5	5	f
r	17	10	190 mod26=8	8	i
u	20	13	247 mod26=13	13	n
z	25	18	342 mod26=4	4	e

拼接后明文为 ctfaffine，最终flag为 flag{ctfaffine}。

4.HASH

现在我们有一个压缩文件,但我们不知道完整的解压密码。
幸好我们知道解压密码的一部分hash值，不过这个hash值被人改动过
你能帮我们找到的密码吗?
不完整的密码：”*ha*i*_go*d” *代表可打印字符
不完整的hash值：”2aa90dc*46aa5d0*baedc4a*13e4c0a6*91bf6*2″（*代表可打印字符）
答案格式： flag{*******}

哈希。。。没啥想法，套脚本爆破结果

import hashlib

def find_correct_password():
    hash_template = "2aa90dc*46aa5d0*baedc4a*13e4c0a6*91bf6*2"
    fixed_positions = []
    for idx, char in enumerate(hash_template):
        if char != '*':
            fixed_positions.append((idx, char))
    printable_chars = [chr(c) for c in range(32, 127)]

    count = 0
    for c1 in printable_chars:
        for c4 in printable_chars:
            for c6 in printable_chars:
                for c10 in printable_chars:
                    password = f"{c1}ha{c4}i{c6}_go{c10}d"
                    sha1_hash = hashlib.sha1(password.encode('utf-8')).hexdigest()
                    match = True
                    for (pos, target_char) in fixed_positions:
                        if sha1_hash[pos] != target_char:
                            match = False
                            break
                    if match:
                        print(f"找到正确密码：{password}")
                        print(f"对应的SHA1哈希：{sha1_hash}")
                        return password
                    count += 1

    return None
correct_pwd = find_correct_password()
if correct_pwd:
    print(f"\nflag{{{correct_pwd}}}")

5.coppersmith

敬请期待
QwQsagemath
没整明白
等笔者好消息吧

from secret import flag
from Crypto.Util.number import *

m = bytes_to_long(flag)

p = getPrime(512)
q = getPrime(512)
N = p * q
e = 7

c = pow(m, e, N)
high_p = (p >> 100) << 100

print(c, N, high_p, sep='\n')

# 77910349061944763568299396394184337520861899083817490010678766043320388729842050532499742515132299125221386423487817013007167101659632771120727305169401713711755701139645391311421914142639007159020652755880068954988225402131362184667436752944331368809243280933094976267099141065017878199319211904257432652753
# 99887986204824691113457754897953425406993412586030259044004283966194202433452866024995465248688896193125819761385921365388030307691682145106269184432165936577174730773115650122496935533603059557681592007428920955897003476296682566264772005134125852663260971355535474414913501328212769545952135420770881499467
# 12672576027810761975840956553905924324108169270520824932988309977042643967090398117355253953195633095326913407044418517938976916071656473263683948565757952

很明显的p高位攻击了，连还原高位的过程都帮你做了

from gmpy2 import *
from Crypto.Util.number import *

c = 77910349061944763568299396394184337520861899083817490010678766043320388729842050532499742515132299125221386423487817013007167101659632771120727305169401713711755701139645391311421914142639007159020652755880068954988225402131362184667436752944331368809243280933094976267099141065017878199319211904257432652753
n = 99887986204824691113457754897953425406993412586030259044004283966194202433452866024995465248688896193125819761385921365388030307691682145106269184432165936577174730773115650122496935533603059557681592007428920955897003476296682566264772005134125852663260971355535474414913501328212769545952135420770881499467
p = 12672576027810761975840956553905924324108169270520824932988309977042643967090398117355253953195633095326913407044418517938976916071656473263683948565757952

PR.<x> = PolynomialRing(Zmod(n))

f = p+x
res = f.small_roots(X=2^100, beta=0.4)

p = int(res[0]) + p
q = n // p
print(q)
d = inverse_mod(7, (p-1)*(q-1))
m = power_mod(c, d, n)
print(long_to_bytes(m))

(p(x) = (p_h + x) \mod n)。

---

Coppersmith 方法的能力是：如果多项式在模 n 的某个因数下有一个 “足够小的根”，就能把这个根求出来。

---

res = f.small_roots(X=2^100, beta=0.4)
参数解释：

• x：X 是小根的上界，即告诉算法：“我们要找的根 (x_0) 满足 (|x_0| < X)”。
• 作用beta 是因数占比参数，表示 N 的素因子 p 满足 (p \geq N^{\text{beta}})。