moectfwp

Crypto

跟风一下：入门指北写得很好推荐看

moeSign1n

阅读代码，题目逻辑其实很简单：

设m = b'MoeCTF 2026'吧

菜单1：加密除了m的任意内容并返回密文

菜单2：提交一个密文，解密后是m给你flag

所以题目就是要在不直接加密m的原文的情况下加密m

这里利用rsa的乘法同态性就能做到

我们把m 拆成m1*m2,分别加密m1，m2，再$E(m_1) \cdot E(m_2) $

就在不直接加密m的情况下得到m的密文

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

m = b'MoeCTF 2026'

io = remote('127.0.0.1', 57842)
m1 = bytes_to_long(m) // 2
m1 = long_to_bytes(m1).hex()
m2 = long_to_bytes(2).hex()
io.recv()
io.sendline(str(1))
io.recv()
io.sendline(str(m1).encode())
c1 = int(io.recvline().strip().decode())
print(c1)
io.recv()
io.sendline(str(1))
io.recv()
io.sendline(str(m2).encode())
c2 = int(io.recvline().strip().decode())
print(c2)
c = c1 * c2
io.recv()
io.sendline(str(2))
io.recv()
io.sendline(str(c).encode())
flag = io.recv()

print(flag)

wsl_Sign1n

sage是个好东西，大家可以多多研究一下，密码手必备神器

justXOR

读题发现是xor加密，题目给了密钥key的生成逻辑，我们尝试还原key就能解密

key生成逻辑

因为初始状态和生成方法都已知，所有看完代码的第一反应就是再把gen_key()函数再跑一次就能拿到key

但是马上就会发现问题：n数字过大，跑完n轮循环几乎不可能，所以另寻他法求解key

我们仔细分析代码：发现这个生成key的式子就是一个数列的递推式，我们求出这个数列的通项公式就能不要跑完range（n-1）就能拿到key

from Crypto.Util.number import long_to_bytes

# just a normal big prime
M = 2039129633208009090414901212304234091626233923923301042398416489123719065081065776033127561876033127924471

n = 10**25
key = 2*pow(3,n-1,M) - 1

enc =  b'it\x0bM\xfa-\xe3T{\xaa\x0f@\xa2\xf1@\xbd\x86e\x85\x9e\xfcp_o\x8f\xccd\x13\xceW\x13\x14\x11\x055b\xcbk\xa0'
flag = bytes([x ^ y for x, y in zip(enc, long_to_bytes(key))])
print(flag)

ez_f3mr4t

这个题出发点肯定在q = next_prime(p ^ ((1<<512)-1))

设 m = 1<<512,t = p^m 不难发现t其实就是p的按位取反，进一步我们可以发现：p + t = M

由此我们可以分析出p，q大致范围

题目中：

q=next_prime(M−p)q

所以存在一个很小的 gap，使得：

q=M−p+gapq

于是：

p+q=M+gap

令：

S=M+gap

那么 p,q 是方程：

x2−Sx+n=0

的两个根，判别式为：

Δ=S2−4n

当 gap 正确时，\Delta 是完全平方数。

枚举很小的奇数 gap 即可分解 n，然后解 RSA。

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

e = 65537
n = 0x308244e7a7de386723c92ba62e35bc22c3ec1b93023e1551408344a4ba31c6203da849aedee0cadf26a3442f9fd652f7d97c053a3f2c298eab6c0f0c2d0b4642a81765ddb00b690425eb212d5520327ac2d53a22922448399fecb54fbc04dbb68fa33fee7666cb9e05278b5f5f1330b3918d3a7def580fcc00f6f596f16eba3b
c = 0x13a77e34f09b8a2291cdb397ea0e5cb9e86f691c6565b35c76e6bb6248b67db24315e22fe1dc5321a8820320cdd9b51e3d431459aac2213948f4fbf01c4ce974428d1ed745b2c06f8aa92b22dfede3b7ceb59aa4eb22467129f55b60037a1a2de9b37f25fda3fe40323fccc7c8bbdd4446096b37cef4138337ee9a04c2e3d5fd
M = (1 << 512) - 1
# p = getStrongPrime(512)
# q = nextprime(M - p)
for k in range(1,100000):
    delt = pow(M + k,2) - 4*n
    if iroot(delt,2)[1]:
        p = (M + k + iroot(delt,2)[0]) // 2
        q = n // p
        phi = (p-1)*(q-1)
        d = inverse(e,phi)
        m = pow(c,d,n)
        print(long_to_bytes(m))

ez_fermat

给了一个hint，从hint入手

因为 a*p + b ≡ b (mod p)，所以：

plain

Text

hint ≡ (a*p + b)^q ≡ b^q (mod p)

第二步：关键变形 —— 把未知的 q 换成已知的 n

由费马小定理，模 p 时指数可以对 p-1 取模。注意 n = pq，而 p ≡ 1 (mod p-1)，所以：

Text

n = p*q ≡ 1*q = q (mod p-1)

于是：

Text

b^n ≡ b^q ≡ hint (mod p)

也就是说 p 整除 (b^n − hint)，而 b、n、hint 全是已知量

第三步：gcd 出 p，由此分解n

p = gcd(n, pow(b, n, n) - hint)

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

n = 15962603324053600624662899467930954606237037554051572101066176482327650464579501876010780067612122315010349894395035821617153081982429716234378979239633769779503395609504372912298014522344609346937078959678893005192469085672940628091531228571447786013091492389216237976408692434723698967667324605921896928717731731591488800520224411239128106892402734198486634978989319563704879076976307439748456769245703782902660583833942684475506024284563786886608632662629581206716450648212025254862836883526055933841863348546872473877054469843468332542834452213365868510001991952142536759384940216228753729399187149594010090304067
c = 4281919068424886012214413435957379635517466043647380176350221253614623990599452495938689758001256045320061491376355750164051326734927905972267385611552894838140009898450267453653097466286838460889968896032216593811984942511165228143089457988630435810304672454147149556110542203084341901598519587611096893432307236558970264536719689039318023572680185246871600989317992399536729717958072642243834689061928667913495884682029212015071613730401843271641197254089900489231738518876415262001687002012972665662364940457678043829768126263211295258465202419686281997749861180041439407866197636369525192971926660559217573713931
hint = 8894364790280693556124457666776501614023509475927164016497858629229215409128965020674642063592770935057209719989294548263833927477972267267951214184209046168773196349537926982123382473522039515862138755400978350128128233701795758152143272668945626119949376162344749760499165210224412751964322150037199401111258869439672762883792051818112500032192131948644557686621759867629440824691768395882797936616839572906841251000681054283164497419314938363871139253289134458466501698235039234455154975165111296198209091586550990873209534256929400689017034618807232508747449076486852786199340704419120538526208691066898035362296

a, b = 0x2025, 0x2026
e = 65537
p = gcd(pow(b,n,n) - hint,n)
q = n // p
phi = (p-1)*(q-1)
d = inverse(e,phi)
print(long_to_bytes(pow(c,d,n)))
```s