出了三道密码，出的很早但是被解烂了，不过也算是没有给团队拖太多的后腿，夹带一句思路，星盟密码招新，详情请关注星盟安全团队公众号

强网杯

Crypto

EasyRSA

#encoding:utf-8
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime
import random, gmpy2

class RSAEncryptor:
    def __init__(self):
        self.g = self.a = self.b = 0
        self.e = 65537
        self.factorGen()
        self.product()

    def factorGen(self):
        while True:
            self.g = getPrime(500)
            while not gmpy2.is_prime(2*self.g*self.a+1):
                self.a = random.randint(2**523, 2**524)
            while not gmpy2.is_prime(2*self.g*self.b+1):
                self.b = random.randint(2**523, 2**524)
            self.h = 2*self.g*self.a*self.b+self.a+self.b
            if gmpy2.is_prime(self.h):
                self.N = 2*self.h*self.g+1
                print(len(bin(self.N)))
                return

    def encrypt(self, msg):
        return gmpy2.powmod(msg, self.e, self.N)


    def product(self):
        with open('/flag', 'rb') as f:
            self.flag = f.read()
        self.enc = self.encrypt(self.flag)
        self.show()
        print(f'enc={self.enc}')

    def show(self):
        print(f"N={self.N}")
        print(f"e={self.e}")
        print(f"g={self.g}")


RSAEncryptor()

看到题目些许眼熟，突然想到之前翻过的一篇文章

https://hasegawaazusa.github.io/common-prime-rsa.html#%E7%94%9F%E6%88%90%E7%AE%97%E6%B3%95

是一个玩意，然后根据这个又找了找文章发现了原题

https://f61d.github.io/crypto/RSA/huwangbei2019_Crypto1/

只能说近乎一样了，只是这个直接生成的是self.N = 2self.hself.g+1，其实这个也就是p = 2ga+1，q = 2gb+1相乘得到的结果，然后直接把py2改成py3代码直接开始跑，跑了五十二分钟出了

from Crypto.Util.number import bytes_to_long, long_to_bytes
from gmpy2 import mpz, iroot, powmod, invert, div

# 给定的 N, e, g, C
N=51657999756690967186588996215664168497370486139760099988595414828727983779546605719940804807600702982441420573278857358283956576117953922473066432017592495133706729760422222891652753765512676564676681283098394548913387209196150332971723414216557817623554405430820579740222241707060798484488162959906554151628826649645549857376389514235605383200948637393805620922357497559575721372378043647085586958646623616279499301953828119839759155713210540465295077855783065483067730429116459612106943556564234959652876183429793248281482188133483319276230212777676735792371318110006476193874307484991785161682554109354412732317203
e=65537
g=2485123610764374014270789237614946556941781726543303674175119390795018685478874519905795106078406823435536131288458566170115665041363495335269709135811
C=28202679072153296346006816417382124529937666704182542518065303275976321831906094232804772404923511250416941784829263735008621187061575092462163699748934506898476841195128781938795842168820103035149075505083142014293446685272596151227631135157118425271040826931331389205822851376453576019854472679252746859939324841698162300853121273468883875556566200571290316887270568728688434714111270070758059040093516226853074913178501938759026695823416142154992551841347420935341846204890649806890263435571918894890106600252801255493750546432442678011345166162953964688073884233888980485821317850868322223277612229644994478304841
# 计算 h, u, v
h = (N - 1) // g
u = h // g
v = h % g

def Solve_c():
    # 计算 C 的估计值
    sqrt_N = iroot(N, 2)[0]
    C = div(sqrt_N, g ** 2)
    C=int(C)

    a = 2
    b = powmod(a, g, N)

    # 在估计的范围内尝试寻找合适的 r 和 s
    for i in range(2, int(C)):
        print(iroot(C, 2)[0])
        D = (iroot(C, 2)[0] + 1) * i
        final = powmod(b, u, N)
        for r in range(D):
            for s in range(D):
                print(r * D + s)
                if powmod(b, r * D + s, N) == final:
                    print("r =", r, "s =", s, "i =", i)
                    return r * D + s

# 解密流程
c = Solve_c()
print("c:", c)  # c = 51589121
A = u - c
B = v + c * g

# 计算 delta 并解出 x 和 y
delta = iroot(B ** 2 - 4 * A, 2)[0]
x = (B + delta) // 2
y = (B - delta) // 2

# 计算 a 和 b
a = x // 2
b = y // 2

# 计算 p 和 q
p = 2 * g * a + 1
q = 2 * g * b + 1

# 计算私钥 d 并解密消息
d = invert(e, (p - 1) * (q - 1))
m = powmod(C, d, N)
print("Decrypted message:", long_to_bytes(m))

apbq

from Crypto.Util.number import *
from secrets import flag
from math import ceil
import sys

class RSA():
    def __init__(self, privatekey, publickey):
        self.p, self.q, self.d = privatekey
        self.n, self.e = publickey

    def encrypt(self, plaintext):
        if isinstance(plaintext, bytes):
            plaintext = bytes_to_long(plaintext)
        ciphertext = pow(plaintext, self.e, self.n)
        return ciphertext

    def decrypt(self, ciphertext):
        if isinstance(ciphertext, bytes):
            ciphertext = bytes_to_long(ciphertext)
        plaintext = pow(ciphertext, self.d, self.n)
        return plaintext

def get_keypair(nbits, e = 65537):
    p = getPrime(nbits//2)
    q = getPrime(nbits//2)
    n = p * q
    d = inverse(e, n - p - q + 1)
    return (p, q, d), (n, e)

if __name__ == '__main__':
    pt = './output.txt'
    fout = open(pt, 'w')
    sys.stdout = fout

    block_size = ceil(len(flag)/3)
    flag = [flag[i:i+block_size] for i in range(0, len(flag), block_size)]
    e = 65537

    print(f'[+] Welcome to my apbq game')
    # stage 1
    print(f'┃ stage 1: p + q')
    prikey1, pubkey1 = get_keypair(1024)
    RSA1 = RSA(prikey1, pubkey1)
    enc1 = RSA1.encrypt(flag[0])
    print(f'┃ hints = {prikey1[0] + prikey1[1]}')
    print(f'┃ public key = {pubkey1}')
    print(f'┃ enc1 = {enc1}')
    print(f'----------------------')

    # stage 2
    print(f'┃ stage 2: ai*p + bi*q')
    prikey2, pubkey2 = get_keypair(1024)
    RSA2 = RSA(prikey2, pubkey2)
    enc2 = RSA2.encrypt(flag[1])
    kbits = 180
    a = [getRandomNBitInteger(kbits) for i in range(100)]
    b = [getRandomNBitInteger(kbits) for i in range(100)]
    c = [a[i]*prikey2[0] + b[i]*prikey2[1] for i in range(100)]
    print(f'┃ hints = {c}')
    print(f'┃ public key = {pubkey2}')
    print(f'┃ enc2 = {enc2}')
    print(f'----------------------')

    # stage 3
    print(f'┃ stage 3: a*p + q, p + bq')
    prikey3, pubkey3 = get_keypair(1024)
    RSA3 = RSA(prikey3, pubkey3)
    enc3 = RSA2.encrypt(flag[2])
    kbits = 512
    a = getRandomNBitInteger(kbits)
    b = getRandomNBitInteger(kbits)
    c1 = a*prikey3[0] + prikey3[1]
    c2 = prikey3[0] + b*prikey3[1] 
    print(f'┃ hints = {c1, c2}')
    print(f'┃ public key = {pubkey3}')
    print(f'┃ enc3 = {enc3}')

题目分为了三步，第一步是给你p+q的值，第二步是给你ap+bq的值，第三步是给你ap+q,p+bq的值让我们逐步分析

首先第一步p+q

很简单列一个p+q和pq的方程直接接出来

from Cryptodome.Util.number import *
from sympy import *
hints = 18978581186415161964839647137704633944599150543420658500585655372831779670338724440572792208984183863860898382564328183868786589851370156024615630835636170
a=pow(hints,2)
n1=89839084450618055007900277736741312641844770591346432583302975236097465068572445589385798822593889266430563039645335037061240101688433078717811590377686465973797658355984717210228739793741484666628342039127345855467748247485016133560729063901396973783754780048949709195334690395217112330585431653872523325589
e=65537
enc1 = 23664702267463524872340419776983638860234156620934868573173546937679196743146691156369928738109129704387312263842088573122121751421709842579634121187349747424486233111885687289480494785285701709040663052248336541918235910988178207506008430080621354232140617853327942136965075461701008744432418773880574136247


p,q=symbols('p q')
s1=Eq(p+q,hints)
s2=Eq(p*q,n1)
s=solve([s1,s2],[p,q])
print(s)
p=int(s[0][0])
q=int(s[0][1])
d=inverse(e,(p-1)*(q-1))
m=long_to_bytes(pow(enc1,d,n1))
print(m)

看第二步，ap+bq

这个之前真没接触过，然后我在谷歌翻了翻找到了原题，DownUnder2023的apbq-rsa-ii,但是你会发现这道题他三个数据是不够的，所以我们使用四个数据就可以得到结果了，然后还找到了maple当时的题解

https://github.com/DownUnderCTF/Challenges_2023_Public/blob/main/crypto/apbq-rsa-ii/solve/solv.sage

https://blog.maple3142.net/2023/09/03/downunderctf-2023-writeups/#apbq-rsa-ii

import itertools
from Crypto.Util.number import long_to_bytes
n = 73566307488763122580179867626252642940955298748752818919017828624963832700766915409125057515624347299603944790342215380220728964393071261454143348878369192979087090394858108255421841966688982884778999786076287493231499536762158941790933738200959195185310223268630105090119593363464568858268074382723204344819
c = 17737974772490835017139672507261082238806983528533357501033270577311227414618940490226102450232473366793815933753927943027643033829459416623683596533955075569578787574561297243060958714055785089716571943663350360324047532058597960949979894090400134473940587235634842078030727691627400903239810993936770281755

hints = [18167664006612887319059224902765270796893002676833140278828762753019422055112981842474960489363321381703961075777458001649580900014422118323835566872616431879801196022002065870575408411392402196289546586784096, 16949724497872153018185454805056817009306460834363366674503445555601166063612534131218872220623085757598803471712484993846679917940676468400619280027766392891909311628455506176580754986432394780968152799110962, 17047826385266266053284093678595321710571075374778544212380847321745757838236659172906205102740667602435787521984776486971187349204170431714654733175622835939702945991530565925393793706654282009524471957119991, 25276634064427324410040718861523090738559926416024529567298785602258493027431468948039474136925591721164931318119534505838854361600391921633689344957912535216611716210525197658061038020595741600369400188538567]


V = hints
k = 2^800
M = Matrix.column([k * v for v in V]).augment(Matrix.identity(len(V)))
B = [b[1:] for b in M.LLL()]
M = (k * Matrix(B[:len(V)-2])).T.augment(Matrix.identity(len(V)))
B = [b[-len(V):] for b in M.LLL() if set(b[:len(V)-2]) == {0}]
print(B)

for s, t in itertools.product(range(4), repeat=2):
    T = s*B[0] + t*B[1]
    print(T)
    a1, a2, a3,a4 = T
    kq = gcd(a1 * hints[1] - a2 * hints[0], n)
    print(kq)
    if 1 < kq < n:
        print('find!', kq, s, t)
        break
for i in range(2**16, 1, -1):
    if kq % i == 0:
        kq //= i
q = int(kq)
print(q)
p = int(n // kq)
d = pow(0x10001, -1, (p - 1) * (q - 1))
m = pow(c, d, n)
flag = long_to_bytes(int(m))
print(flag)

接下来就是最nt的第三步，我也不知道是出题人写错了，还是他为了降低题目难度，你仔细审题会发现，在这里他用的是生成的RSA2这个公钥系统，而不是用的三，勾吧我没注意到直接取解关于ap+q,p+bq,然后在网上找到了一个原题，

https://github.com/defund/ctf/blob/master/angstromctf-2024/blahaj/solve.sage

from Crypto.Util.number import *
hints = (68510878638370415044742935889020774276546916983689799210290582093686515377232591362560941306242501220803210859757512468762736941602749345887425082831572206675493389611203432014126644550502117937044804472954180498370676609819898980996282130652627551615825721459553747074503843556784456297882411861526590080037, 117882651978564762717266768251008799169262849451887398128580060795377656792158234083843539818050019451797822782621312362313232759168181582387488893534974006037142066091872636582259199644094998729866484138566711846974126209431468102938252566414322631620261045488855395390985797791782549179665864885691057222752)
n=94789409892878223843496496113047481402435455468813255092840207010463661854593919772268992045955100688692872116996741724352837555794276141314552518390800907711192442516993891316013640874154318671978150702691578926912235318405120588096104222702992868492960182477857526176600665556671704106974346372234964363581

c = 17737974772490835017139672507261082238806983528533357501033270577311227414618940490226102450232473366793815933753927943027643033829459416623683596533955075569578787574561297243060958714055785089716571943663350360324047532058597960949979894090400134473940587235634842078030727691627400903239810993936770281755
x=hints[0]
y=hints[1]

e = 65537

R = Integers(n)

P.<a, b, p, q> = PolynomialRing(Integers(n))

f1 = a*p + q

f2 = p + b*q

f3 = p*q

I = Ideal([f1 - x, f2 - y, f3 - n])
B = I.groebner_basis()

print(B)

g = B[-1]

z = ZZ(g.coefficient({q: 1}))
assert g.constant_coefficient() == R(-y)

_, (z1, _), (z2, _) = list(g)
z1 = ZZ(z1)
z2 = ZZ(z2)

S = 2^512

for p_upper_bits in range(16):
    p_upper = p_upper_bits << 510
    for q_upper_bits in range(16):
        q_upper = q_upper_bits << 510
        M = matrix(ZZ, [[S, -1, 0, 0], [S*z1, 0, -1, 0], [S*(z2 + p_upper + q_upper*z1), 0, 0, S], [S*n, 0, 0, 0]])
        B = M.LLL()
        for b in B:
            if b[-1] == S:
                if b[1] < 0:
                    b *= -1
                p_guess = b[1] + p_upper
                q_guess = b[2] + q_upper
                print(p_guess)

                if p_guess * q_guess == n:
                    print(666)
                    print(p_guess)
                    print(q_guess)
                    d = pow(e, -1, (p_guess - 1)*(q_guess - 1))
                    message = int(pow(c, d, n))
                    message_bytes = message.to_bytes((message.bit_length() + 7) // 8, 'big')
                    print(message_bytes)


                    exit()
                    

然后呢你要是真用的这个我觉得算是预期解法解这个你最后虽然pq什么的都对了但是你还是错的因为你压根用的不是这个加密的

然后我突然发现用的rsa2，勾吧做出来的时候真在骂人，浪费我两个点题目从20多解到了六十多解，我懒得再写，我直接贴把3的数据放到2的exp里面的脚本

import itertools
from Crypto.Util.number import long_to_bytes
n = 73566307488763122580179867626252642940955298748752818919017828624963832700766915409125057515624347299603944790342215380220728964393071261454143348878369192979087090394858108255421841966688982884778999786076287493231499536762158941790933738200959195185310223268630105090119593363464568858268074382723204344819
c = 17737974772490835017139672507261082238806983528533357501033270577311227414618940490226102450232473366793815933753927943027643033829459416623683596533955075569578787574561297243060958714055785089716571943663350360324047532058597960949979894090400134473940587235634842078030727691627400903239810993936770281755

hints = [18167664006612887319059224902765270796893002676833140278828762753019422055112981842474960489363321381703961075777458001649580900014422118323835566872616431879801196022002065870575408411392402196289546586784096, 16949724497872153018185454805056817009306460834363366674503445555601166063612534131218872220623085757598803471712484993846679917940676468400619280027766392891909311628455506176580754986432394780968152799110962, 17047826385266266053284093678595321710571075374778544212380847321745757838236659172906205102740667602435787521984776486971187349204170431714654733175622835939702945991530565925393793706654282009524471957119991, 25276634064427324410040718861523090738559926416024529567298785602258493027431468948039474136925591721164931318119534505838854361600391921633689344957912535216611716210525197658061038020595741600369400188538567]


V = hints
k = 2^800
M = Matrix.column([k * v for v in V]).augment(Matrix.identity(len(V)))
B = [b[1:] for b in M.LLL()]
M = (k * Matrix(B[:len(V)-2])).T.augment(Matrix.identity(len(V)))
B = [b[-len(V):] for b in M.LLL() if set(b[:len(V)-2]) == {0}]
print(B)

for s, t in itertools.product(range(4), repeat=2):
    T = s*B[0] + t*B[1]
    print(T)
    a1, a2, a3,a4 = T
    kq = gcd(a1 * hints[1] - a2 * hints[0], n)
    print(kq)
    if 1 < kq < n:
        print('find!', kq, s, t)
        break
for i in range(2**16, 1, -1):
    if kq % i == 0:
        kq //= i
q = int(kq)
print(q)
p = int(n // kq)
d = pow(0x10001, -1, (p - 1) * (q - 1))
m = pow(c, d, n)
flag = long_to_bytes(int(m))
print(flag)

21_steps

import re
import random
from secrets import flag
print(f'Can you weight a 128 bits number in 21 steps')
pattern = r'([AB]|\d+)=([AB]|\d+)(\+|\-|\*|//|<<|>>|&|\^|%)([AB]|\d+)'

command = input().strip()
assert command[-1] == ';'
assert all([re.fullmatch(pattern, i) for i in command[:-1].split(';')])

step = 21
for i in command[:-1].split(';'):
    t = i.translate(str.maketrans('', '', '=AB0123456789'))
    if t in ['>>', '<<', '+', '-', '&', '^']:
        step -= 1
    elif t in ['*', '/', '%']:
        step -= 3
if step < 0:exit()

success = 0
w = lambda x: sum([int(i) for i in list(bin(x)[2:])])
for _ in range(100):
    A = random.randrange(0, 2**128)
    wa = w(A)
    B = 0
    try : exec("global A; global B;" + command)
    except : exit()
    if A == wa:
        success += 1

if success == 100:
    print(flag)

看到题目分析下步骤，他对于步的判定就是这个函数

step = 21
for i in command[:-1].split(';'):
    t = i.translate(str.maketrans('', '', '=AB0123456789'))
    if t in ['>>', '<<', '+', '-', '&', '^']:
        step -= 1
    elif t in ['*', '/', '%']:
        step -= 3
if step < 0:exit()

我们要在21步内使得我们最后得到的结果要是我们生成的128bit位随机数的权重，我先问了一下gpt

然后我根据gpt给的思路我自己测一下数据，发现gpt的是可以的不过步数超了

w = lambda x: sum([int(i) for i in list(bin(x)[2:])])
A=307841650595242525000004472218706432542
print(w(A))
# Step 1: 将相邻的 2 位累加
A = (A & 0x55555555555555555555555555555555) + ((A >> 1) & 0x55555555555555555555555555555555)
print(bin(A))
# Step 2: 将相邻的 4 位累加
A = (A & 0x33333333333333333333333333333333) + ((A >> 2) & 0x33333333333333333333333333333333)
print(bin(A))
# Step 3: 将相邻的 8 位累加
A = (A & 0x0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F) + ((A >> 4) & 0x0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F)
print(bin(A))
# Step 4: 将相邻的 16 位累加
A = (A & 0x00FF00FF00FF00FF00FF00FF00FF00FF) + ((A >> 8) & 0x00FF00FF00FF00FF00FF00FF00FF00FF)
print(bin(A))
# Step 5: 将相邻的 32 位累加
A = (A & 0x0000FFFF0000FFFF0000FFFF0000FFFF) + ((A >> 16) & 0x0000FFFF0000FFFF0000FFFF0000FFFF)
print(bin(A))
# Step 6: 将相邻的 64 位累加
A = (A & 0x00000000FFFFFFFF00000000FFFFFFFF) + ((A >> 32) & 0x00000000FFFFFFFF00000000FFFFFFFF)
print(bin(A))
# Step 7: 将所有 128 位累加
A = (A & 0x0000000000000000FFFFFFFFFFFFFFFF) + ((A >> 64) & 0x0000000000000000FFFFFFFFFFFFFFFF)
print(bin(A))
print(A)

因为我们的操作做是不断地将1向后移动，然后仔细观察下面的数据，然后因为我观察到后面其实都是按位与，越往后面的话在掩码末尾的1会越来越多，所以我尝试将后面的按位与逐步去掉发现只需要相加我们就可以在末六位的到我们的权值，修改过后发现确实没问题

那我们可以逐步的减少按位与最后得到21步可以完成操作

    w = lambda x: sum([int(i) for i in list(bin(x)[2:])])
    A=307841650595242525000004472218706432542
    print(w(A))
    # Step 1: 将相邻的 2 位累加
    A = (A & 0x55555555555555555555555555555555) + ((A >> 1) & 0x55555555555555555555555555555555)
    print(bin(A))
    # Step 2: 将相邻的 4 位累加
    print(bin((A >> 2) & 0x33333333333333333333333333333333))
    print(bin(A & 0x33333333333333333333333333333333))
    A = (A & 0x33333333333333333333333333333333) + ((A >> 2) & 0x33333333333333333333333333333333)
    print(bin(A))
    # Step 3: 将相邻的 8 位累加
    A = (A & 0x0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F) + ((A >> 4) & 0x0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F)
    print(bin(A))
    # Step 4: 将相邻的 16 位累加
    A = (A & 0x00FF00FF00FF00FF00FF00FF00FF00FF) + ((A >> 8) & 0x00FF00FF00FF00FF00FF00FF00FF00FF)
    print(bin(A))
    # Step 5: 将相邻的 32 位累加
    A = (A ) + ((A >> 16))
    print(bin(A))
    # Step 6: 将相邻的 64 位累加
    A = (A ) + ((A >> 32) )
    print(bin(A))
    # Step 7: 将所有 128 位累加
    A = (A ) + ((A >> 64))
    A=A&127
    print(bin(A))
    print(A)

然后后续的思路因为要传入AB，其实就是B=((A >> 1) & 0x55555555555555555555555555555555)，A需要自己变更然后exp如下：

B=A>>1;B=B&113427455640312821154458202477256070485;A=A&113427455640312821154458202477256070485;A=A+B;B=A>>2;B=B&68056473384187692692674921486353642291;A=A&68056473384187692692674921486353642291;A=A+B;B=A>>4;B=B&20016609818878733144904388672456953615;A=A&20016609818878733144904388672456953615;A=A+B;B=A>>8;A=A+B;B=A>>16;A=A+B;B=A>>32;A=A+B;B=A>>64;A=A+B;A=A&127;