密码学题解两则

Posted on 2026-05-10 In WriteUp

自己当初死活解不出来的题现在AI能秒解

令人感慨

虎符杯 2021 Crypto – Cubic

#!/usr/bin/env python3
from math import gcd
from functools import reduce
from fractions import Fraction as Frac


N = 6

def read_num(prompt):
    try:
        num = int(input(prompt))
    except:
        return 0
    return num if num > 0 else 0


print(f"Please give me {N} pairs of positive integers (x,y,z) "
      f"satisfying the equation `x/(y+z) + y/(z+x) + z/(x+y) = {N}`\n")

anss = []
mark = 0
for i in range(N):
    x = read_num("[>] x: ")
    y = read_num("[>] y: ")
    z = read_num("[>] z: ")
    if x * y * z == 0: # positive integer
        mark = 1
        print("This is not what i want!\n")
        break
    if reduce(gcd, [x, y, z]) != 1: # (kx, ky, kz)
        mark = 1
        print("This is not what i want!\n")
        break
    if Frac(x, y+z) + Frac(y, z+x) + Frac(z, x+y) != N:
        mark = 1
        print("This is not what i want!\n")
        break
    ans = tuple(sorted([x, y, z])) # (y, x, z)
    if ans in anss:
        mark = 1
        print("This is not what i want!\n")
        break
    else:
        print("You are right!\n")
        anss.append(ans)
if mark == 0:
    flag = open('/flag', 'r').read()
    print("flag is: " + flag + "\n")
else:
    print("Something wrong!\n")

丢番图方程

简单翻译下就是下面这个图的意思

只不过是4改成了6

# 导入构建椭圆曲线所需的模块
from sage.schemes.elliptic_curves.constructor import EllipticCurve_from_cubic
from sage.arith.all import lcm, gcd

# 1. 定义多项式环和目标值 n
R.<x,y,z> = QQ[]
n = 6

# 2. 将原分式方程去分母，构造齐次三次方程
f = x*(x+y)*(x+z) + y*(y+x)*(y+z) + z*(z+x)*(z+y) - n*(x+y)*(y+z)*(z+x)

# 3. 定义需要遍历的三个平凡点
P0_list = [
    [1, -1, 0],
    [1, 0, -1],
    [0, 1, -1]
]

print(f"目标方程: x/(y+z) + y/(x+z) + z/(x+y) = {n}")
print("=" * 60)

# 外层循环：遍历不同的基准点 P0
for idx, P0 in enumerate(P0_list):
    print(f"\n>>> 正在测试第 {idx+1} 个基准点 P0 = {P0} <<<")

    # 4. 将三次曲线映射为 Weierstrass 标准型的椭圆曲线 E
    try:
        phi = EllipticCurve_from_cubic(f, P0, morphism=True)
        E = phi.codomain()
        phi_inv = phi.inverse()
        print(f"[*] 成功映射到椭圆曲线: {E}")
    except Exception as e:
        print(f"[-] 映射失败，跳过: {e}")
        continue

    # 5. 使用 Simon 2-descent 算法快速抓取独立点
    print("[*] 正在使用 Simon 2-descent 快速搜索无限阶点...")
    descent_pts = E.simon_two_descent()[2]

    if len(descent_pts) == 0:
        print("[-] 快速下降法未能找到无限阶点，跳过。")
        continue
    
    G = descent_pts[0]
    print(f"[*] 成功抓取非扭点 G: {G}")

    # 6. 遍历生成元的倍数 k*G，寻找 x, y, z 同号的解
    found = False
    print("[*] 开始在 k <= 100 范围内搜索正整数解...")

    for k in range(1, 101):  # 包含 100
        # 计算椭圆曲线上的 k 倍点
        P_E = k * G
        
        # 将点逆映射回原三次曲线的齐次坐标 (x:y:z)
        try:
            P_cubic = phi_inv(P_E)
        except ValueError:
            continue
            
        x_val, y_val, z_val = P_cubic[0], P_cubic[1], P_cubic[2]

        if x_val == 0 or y_val == 0 or z_val == 0:
            continue

        # 检查是否同号
        if (x_val > 0 and y_val > 0 and z_val > 0) or (x_val < 0 and y_val < 0 and z_val < 0):
            print(f"\n[+] 成功找到同号特解！发生在倍数 k = {k}")

            x_val, y_val, z_val = abs(x_val), abs(y_val), abs(z_val)

            # 通分化简
            d1 = x_val.denominator()
            d2 = y_val.denominator()
            d3 = z_val.denominator()
            lcm_den = lcm(d1, lcm(d2, d3))

            n1 = (x_val * lcm_den).numerator()
            n2 = (y_val * lcm_den).numerator()
            n3 = (z_val * lcm_den).numerator()
            gcd_num = gcd(n1, gcd(n2, n3))

            x_final = n1 // gcd_num
            y_final = n2 // gcd_num
            z_final = n3 // gcd_num

            print(f"    解的数字长度约为: {len(str(x_final))} 位")
            print(f"    x = {x_final}")
            print(f"    y = {y_final}")
            print(f"    z = {z_final}")
            
            found = True
            break  # 找到解后跳出当前的 k 循环，继续测试下一个 P0

    if not found:
        print(f"[-] 在 k<=100 范围内，基准点 {P0} 未能找到全正解。")

print("\n" + "=" * 60)
print("所有基准点搜索完毕。")

目标方程: x/(y+z) + y/(x+z) + z/(x+y) = 6
============================================================

>>> 正在测试第 1 个基准点 P0 = [1, -1, 0] <<<
[*] 成功映射到椭圆曲线: Elliptic Curve defined by y^2 + 8*x*y - 9792*y = x^3 + 3176*x^2 - 362304*x - 11985408 over Rational Field
[*] 正在使用 Simon 2-descent 快速搜索无限阶点...
[*] 成功抓取非扭点 G: (-1224 : 68544 : 1)
[*] 开始在 k <= 100 范围内搜索正整数解...

[+] 成功找到同号特解！发生在倍数 k = 27
    解的数字长度约为: 800 位
    x = 91799790641290895978892693045989377201208936340103016031364426490498736597677568287986160691579377724785392328266339231530225121046175630599728096521939605350739358168216330513241983978233993998988991326492874516049720675702286872816333914372511669802712219058719713832528597339293054368816739355907136102655521941992018553301928493452434474447723992660186680549103802498214282230740469986200770650120969911569599029786866103349814407040007149745644301920170584323025348517461308692357116926947251792699428368596979150563731309323515129474727817938633113832298119162778959620065753052386380251973187273607723986357950763286173562416762837143991547957533832926711542607034850457520418701875848727202883029106928219366050792422975016449024940528092641753838563742427509959090708910325398150439211810947
    y = 2370844050733763168653056912182275089135481091989469895123144001232602797883560999259129655883146226759407799774039653583687248933666821013837626069498685816554714705323847460507235277382794614936098961850448835901703891332533224965178208112684042141294337624561114056386810429548483148842597664557193452726536721058295707545479924443144714770275921157720051829171825732745857876583623371634787429544606363093272415125412836762819303421993587964400942215536942030583066797232871335393211395326041484926097986775013694902283133471846514714506451260645208477576233622738192899871671383782415144282058906877965816336875417759881658992236986398952428086504437441217917041059825839022060700048544901256390446316992733932612136873399094430223469630954259137165426566293784012450269989381719756996048058089023
    z = 314292671062173921111292961964938688436708560003041812060682883475601482731858816422240383882944462620623567286587503750889103725755740006155575297673642764299712726683321335389717791541964719934510825511641995918205107276454661741769794334108514203164641911236712095598112837257748637990075283636106682003276751427529201991787105193934697041232800134525851852447109810170418723631301828242625191639180887760900486283796646822636577982415485834912490056678350793904299469556675190381984269650656661389359603438215672023664789997298532577361391479552727060752508401019647303083662666278442587228978720394609332929193655411546120631186405265728554188782640067849098497720941130508081137596382759145482661677081314713162009647103220488302296025402048431671351592354184472261402188368030157633491138250760

>>> 正在测试第 2 个基准点 P0 = [1, 0, -1] <<<
[*] 成功映射到椭圆曲线: Elliptic Curve defined by y^2 - x*y = x^3 + 107*x^2 + 2907*x + 23409 over Rational Field
[*] 正在使用 Simon 2-descent 快速搜索无限阶点...
[*] 成功抓取非扭点 G: (-20 : 3 : 1)
[*] 开始在 k <= 100 范围内搜索正整数解...

[+] 成功找到同号特解！发生在倍数 k = 11
    解的数字长度约为: 133 位
    x = 1218343242702905855792264237868803223073090298310121297526752830558323845503910071851999217959704024280699759290559009162035102974023
    y = 2250324022012683866886426461942494811141200084921223218461967377588564477616220767789632257358521952443049813799712386367623925971447
    z = 20260869859883222379931520298326390700152988332214525711323500132179943287700005601210288797153868533207131302477269470450828233936557

>>> 正在测试第 3 个基准点 P0 = [0, 1, -1] <<<
[*] 成功映射到椭圆曲线: Elliptic Curve defined by y^2 + x*y = x^3 + 107*x^2 + 2907*x + 23409 over Rational Field
[*] 正在使用 Simon 2-descent 快速搜索无限阶点...
[*] 成功抓取非扭点 G: (-20 : 23 : 1)
[*] 开始在 k <= 100 范围内搜索正整数解...

[+] 成功找到同号特解！发生在倍数 k = 11
    解的数字长度约为: 133 位
    x = 2250324022012683866886426461942494811141200084921223218461967377588564477616220767789632257358521952443049813799712386367623925971447
    y = 20260869859883222379931520298326390700152988332214525711323500132179943287700005601210288797153868533207131302477269470450828233936557
    z = 1218343242702905855792264237868803223073090298310121297526752830558323845503910071851999217959704024280699759290559009162035102974023

============================================================
所有基准点搜索完毕。

TechWorld 2019 Crypto – Cipher

from Crypto.Util.number import *
flag = "flag{xxxxxxxxxxxxxxxxxxx}"
m = bytes_to_long(flag)

p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537

c = pow(m, e, n)

print(n)

print(c)

print(pow(p+q, 2019, n))

print(pow(p+2019, q, n))

96780461394033337689567108259893748486002236738582736851233917468787524740624888972342563373512353586255114495079107335758288612338495963159612655318462375582406898270689435326368556558777898332573467628654624176029376998056045209679733660069957700185941370295208768680659384859188808356284395145787167822039
40902682922928025118571286152821100197674619815758133392785930170320910852655524737284528223471081642113214606615949067348943884072834222360537528813694188078856744138052033683982573167279077201980728210288846946841629237854328330529467598310598928680582754313029091620726738078049238979066396109902383779474
1085028795352905556943262835596573622075429386738984173331064472484066570876869315098105988053006079365050850500671807631253369854693004975237940840141074816205938760953784453832187957129220977719685389206024588149832914477308077438518601216192362909946961689725801155118156088666938733672414905904034952121
58990774595434377063777726247309387841479057068955206198202064573296964307379687905049181435740384194830759666167579369083224550401718886673825411413076522799129655186877044125596908766674290986472905901356969650876446443052520830234766043256136817920934130392728788803076056174028811029278351458894807475631

$a \equiv (p + q)^{2019} \pmod n$

$a \equiv p^{2019} + c_{1}p^{2018}q + c_{2}p^{2017}q^{2} + \dots + c_{2018}pq^{2018} + q^{2019} \pmod n$

$a \equiv p^{2019} + k_{1}n + \dots + k_{2018}n + q^{2019} \pmod n$

$a \equiv p^{2019} + q^{2019} \pmod n$

$a \equiv p^{2019} \pmod q$

$b \equiv (p + 2019)^{q} \pmod n$

$b \equiv (p + 2019)^{q} \pmod q$

$b \equiv p + 2019 \pmod q$

$(b - 2019)^{2019} \equiv a \pmod q$

$(b - 2019)^{2019} - a \equiv 0 \pmod q$

$(b - 2019)^{2019} - a = kq$

$q = \gcd(kq, n)$

import gmpy2
from Crypto.Util.number import *


n = 96780461394033337689567108259893748486002236738582736851233917468787524740624888972342563373512353586255114495079107335758288612338495963159612655318462375582406898270689435326368556558777898332573467628654624176029376998056045209679733660069957700185941370295208768680659384859188808356284395145787167822039
c = 40902682922928025118571286152821100197674619815758133392785930170320910852655524737284528223471081642113214606615949067348943884072834222360537528813694188078856744138052033683982573167279077201980728210288846946841629237854328330529467598310598928680582754313029091620726738078049238979066396109902383779474
a = 1085028795352905556943262835596573622075429386738984173331064472484066570876869315098105988053006079365050850500671807631253369854693004975237940840141074816205938760953784453832187957129220977719685389206024588149832914477308077438518601216192362909946961689725801155118156088666938733672414905904034952121
b = 58990774595434377063777726247309387841479057068955206198202064573296964307379687905049181435740384194830759666167579369083224550401718886673825411413076522799129655186877044125596908766674290986472905901356969650876446443052520830234766043256136817920934130392728788803076056174028811029278351458894807475631
e = 65537

x = pow(b - 2019, 2019, n)
q = gmpy2.gcd(a - x, n)
p = n // q
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
flag = long_to_bytes(m)
print(flag)

flag{binomial_exp4ns1on}

Post author: xXxYOLOxXx
Post link: https://yoloyolo.top/2026/05/10/Diophantine-Equation/
Copyright Notice: All articles in this blog are licensed under BY-NC-SA unless stating additionally.