2023 祥云杯决赛

admin 2024年5月14日23:57:33评论3 views字数 15446阅读51分29秒阅读模式

2023 祥云杯决赛

虽然本人没有参加第三届祥云杯决赛,但赛后还是摸到了赛题看。

学生组

有一个师傅在学生组,第一天学生组比完CTF后找到我说,在比赛的时候解题卡在了最后一步,让我瞅瞅,想知道怎么做。
2023 祥云杯决赛

赛题一

from secret import flag
from Crypto.Util.number import *
total_bit = 512
def make_para(bit_size):
    P = getStrongPrime(bit_size)
    Q = getStrongPrime(bit_size)
    N = P * Q
    magic = (N + 1) * (N + P + Q + 1) + (P - Q) ** 2 + N
    d = int(0.394 * bit_size)
    e = inverse(d, magic)
    k = d * e // magic
    return (N, e), (P, Q, k)
pubkey, sec_key = make_para(2 * total_bit)
flag = bytes_to_long(flag) * sec_key[2]
p = getStrongPrime(total_bit)
q = getStrongPrime(total_bit)
n = p * q
e = 65537
c = pow(flag, e, n)
t = ((p - getRandomNBitInteger(16)) * sec_key[0] + q) % sec_key[1]
with open('output.txt''w'as f:
    f.write(str(pubkey) + 'n')
    f.write(str((t, c)))
题目大致的瞅一眼,首先生成了一些参数  其中 已知。然后把 flag 乘了 k,接着又生成了一份 RSA 的公钥,并加密了 ,然后给出了关于 的额外信息
那么问题很显然啊,需要先分解 ,把 整出来先。而关于 ,在 make_para 函数中我们注意到关于 的生成方式。乍一看,还以为生成了一个大小是 的私钥,然后用来生成 的模数是 magic,合并一下其实是 ,还以为是论文题,要用一下连分数啥的。但是转念一想,不对啊,离线比赛出论文题,那不是缺了大德么。最后定睛一看,好家伙 d = int(0.394 * bit_size),原来 是一个已知整数。
于是我们有 ,展开一下
因此 ,假设 ,那么 ,于是 ,实际测出来是
然后解个方程我们就能获取 了。
from gmpy2 import *

N,e = (21136120517038375343657055317361461947217610380415290931285704769845405139443342030139838613845989765254932385503454684656325859309861269837188207923942223163348944160792729101485975484543693998035828762630825174735962679103457025646672449491007685400869138263581883506767852264244013623583813540066115060793144049256890248337903932112449333735324371400873419104520104079223733159263094092843185909770131443506433825708789563521497940390674504488024226655482568491358458107989880756229607524452273305978138461190013290440068226454238375505010225133919526068226837545142734502100757510899741312502285931571783851666429291542085122413541028076006933740091355832744332602513957292369860771664833892358795585946753279254101863581542678927529330607906769804928526978686071141386341893467977451552634615917127445748737712286687041822255325772392569586666055711202824870471562051621883329559663555059967665101455578668904247279540014709971958403913939101728330638301270881265277488332145439522278871554725936095617940701105161078332467466405454007283937177070102098256744642045839067405705972784471374421818844770106228499198315920181837950503279178647052157269318876892192700670366858062171759498850112906238502375693099462427930964555274451795362167393410749436026095037695100430810204847979914959732383773952788768239221142673268839750770222737928397507645337714199166919835667638401309062163501094032890215821366318775462220119081175885338966308921205861717088926659072208866126879068213582499260316364548817213314952246293713853884872460934174624844462586276340207505217646013915381902979372875919823493439285174120160656952728493383464761519634974414670811896809158801804891938928244053980210687334268664219571818927285279999791212932795196689285015367417706597781418431735001428656415752334850685705212368666855124013583549768407830008606258798409140)
d = int(0.394 * 1024)

k = (e*d-1)//N**2
p_a_q = (e*d-1)//(k*N) - N - 3
p_s_q = iroot(p_a_q**2-4*N,2)[0]
p = (p_a_q+p_s_q)//2
q = p_a_q - p
assert p*q == N

print(p)
print(q)
print(k)

# 143078039642881652792725771784213914569207427179221450527831176525315265565238257928580110111049486656241446498753952813958174255162082586211603455849496271101246800300949146175660103176787576526962695816071099455794179935847192303931252206979980383408582225496150194196048569906497422686531669037370362490591
# 147724420671358625656073728988251990709657136203479220456044242791542317692661747967991832853881462444146194371982730793349362452137634455888399765514368115413509137529033492152562833458082422584778299506218002962422410654802940055372919228164309566932084727942623228573408370823021433452034727423294317997219
# 263
显然我们是需要根据 解出 来解密密文获得 flag
这里由于 是 1024 比特的, 是 512 比特。考虑格基规约,类似 ICTF 的 tan,构造如下格
from Crypto.Util.number import *
p = getPrime(510)
q = getPrime(510)
n = p * q
t = ((p - getRandomNBitInteger(16)) * P + q) % Q
shift = 2^1024
m = matrix(ZZ,[[shift*P,1,0,0,0],
    [shift*1,0,1,0,0],
    [shift*Q,0,0,1,0],
    [shift*t,0,0,0,2^512]])
m = m.LLL()

assert abs(m[1][2])==q
本地测试发现当 长度为 的时候能跑出来,但是使用原来数据时, 多 2 个比特就怎么也出不来。
于是想到爆破 的高位,首先最高位肯定都是 1,对于第二个比特 ,猜一下,总共也就四种可能。(另外 也有可能会反,需要对调一下,总共就是 8 种可能)
t,c = (1887215198419920005163300575914029522478825245132641014102248320385589479095883740847034891596621206346799529246106106927353923493932064753390291408394344474374878997574551423951840682973828690017797297403314389693286389855359988859716505483751369866768627711058765918817227162997337116455735347314683127597247672712219012743425382676880904671136942826695249149129159924785186563239747047304204962529935078111450524236186612259355850306867579998685662967391936502046679744616903469002187225791339629835786750259999982506494377133775859573660632942293353420327987860136624649402598383416748766985203781387716072244402)
k = 263
P = 143078039642881652792725771784213914569207427179221450527831176525315265565238257928580110111049486656241446498753952813958174255162082586211603455849496271101246800300949146175660103176787576526962695816071099455794179935847192303931252206979980383408582225496150194196048569906497422686531669037370362490591
Q = 147724420671358625656073728988251990709657136203479220456044242791542317692661747967991832853881462444146194371982730793349362452137634455888399765514368115413509137529033492152562833458082422584778299506218002962422410654802940055372919228164309566932084727942623228573408370823021433452034727423294317997219
# 猜测 p,q 高位
ph = 0b11<<510
qh = 0b11<<510

# 根据 p,q 高位, t 做相应处理
tbar = (t-qh-ph*P)%Q

shift = 2^1024
m = matrix(ZZ,[[shift*P,1,0,0,0],
    [shift*1,0,1,0,0],
    [shift*Q,0,0,1,0],
    [shift*tbar,0,0,0,2^512]])
m = m.LLL()

if isPrime(int(abs(m[1][2])+qh)):
 q = abs(m[1][2])+qh
 e = 65537
 d = inverse(e,q-1)
 mm = pow(c,d,q)
 print(long_to_bytes(int(mm//k)))

b'flag{6db64079-711c-4d80-86c6-baec1023d44d}'

赛题二

然后我把第二题给问过来了,

from Crypto.Util.number import *
from Crypto.Util.strxor import strxor
from random import randint
from gmpy2 import invert
import os

flag = b'xxx'

def mypad(m):
    l = len(m)
    r = 190 - l
    padded_m = m + os.urandom(r)
    return padded_m

def myfunction(num):
    output = 0
    j = 0
    for i in range(num):
        output += (i+j)*6 + 1
        j += i
    return output

def mix(a,b):
    return a | b , a * b


class MySeries():
    def __init__(self, num):
        self.num = num

    def Coe(self, n):
        i = 0
        c = 1
        while i < n:
            i += 1
            c = (c * (1 / 2 - i + 1)) / i
        return c

    def Point(self, center):
        sum = 0
        center -= 1
        i = 0
        while i < self.num:
            sum += (center ** (1 / 2 - i) * self.Coe(i))
            i += 1
        return sum


def All(bound):
    num = randint(11112222)
    T = MySeries(num)
    output = 0

    i = 3
    while i < bound:
        b1 = T.Point(i)
        b2 = T.Point(i + 1)
        output += (b1 + b2) / 2
        i += 1
    return output

if __name__ == '__main__':
    flag_len = len(flag)
    p,q = getPrime(512),getPrime(512)
    
    while True:
        r = getPrime(512)
        R = bytes_to_long(str(r).encode())
        if isPrime(R):
            break
            
    n = p * q * r 
    hint1 = R * r
    mod = myfunction(n)
    hint2 = pow(3*n+1,p % (2 ** 400),mod)
    k = int(All(n))
    xor_flag = strxor(long_to_bytes(k >> (k.bit_length() - 8 * flag_len)),flag)
    pad_flag = mypad(xor_flag)
    m = bytes_to_long(pad_flag)
    c = pow(m,65537,n)
    
    print('All data:')
    print(f'flag_len = {flag_len}')
    print(f'n = {n}')
    print(f'c = {c}')
    print(f'hint1 = {hint1}')
    print(f'hint2 = {hint2}')

'''
All data:
flag_len = 42
n = 1885106209951408608833065466098355578239648885277085979696889428331716535742564778501798478665957825315340421821880653818505857049636611632357321104069926874970489073929053910350131880591544986024406953378391135673202854750625745159391997973535848495128365477217006260495413869532372418221652962946340513593002422433536479789576519469228846773250447077165756739529520975715667675188738514871033908115371290569902086064227476952606366538782284487477820835988316471
c = 696238728213276154324787695659767792043458798396732235983493075871691401810545168845655490352789752222363100922123671319198981013421632076090146254867823593523050502577701155837063376958530879006719716789887624440134559774538443909463537086796915613123528679984244371544503657821859556837415229166015914540860398289216765611441964228176020361651359395184571105468667815326494558761738459063914192172836518999575866452752941368767971539919141604299843463853501960
hint1 = 47533994701669017942592643580845693193316601935087923279407365999451221242084261195588230994183718077379066856479267476895986608547324057765879168010176037349172136581929046771540241367625486215731295814611283581608613208990206581757576978017732022062210538697720930605552259306749633658032304554578427461842934055558865521604512892691323385156889995854702621568441768712619224249280792783364635307739215957762771386413831279443875185633720270001928747743847856394847878232194076679733830705297410959656270945532930199517880949
hint2 = 1345739841248959791137389026125065605121513428784838684290299665636596562317989590469829195181078904857051392378877013458099983407103737518119999468489762053545474516182879516762580472262640794849609626308003164739287189671066241628052826558582865342176036139097546843281565147798609965645514151827840249686650855385385323417455247722134760335695053787221300451942370377598800841980049138341564555801417479362085565640973199260631136149016266661293883650801813550118778433333591258278147003619871962070136454674193198696690506092831171400435490432196636796719177624389194619648086397178720207413652618636521150924913978530986709499047969775311955879302418093270101476537853298615347062384026172441455857088955847766335746521291043747795520485020303040819568036819058385444936925860671650596681910380157657689041971132993731048618045570715513584627109356139903842365556697314631573799394266292587334468008221427502353566938518574247502783245674619641519095644135976062817840893465238031354234069073928763492529419021632732679912738674105898149050223970723297059883534089683179512881491210176114419520070007595698242827625902377045860953285447617249204919971737086366
'''

赛题二就比较缝合怪了,魔改的应该是 2022 CCTF Infinity castle
第一步是用 和 做 gcd 求出 ,
然后测试(或者推一下)可得 myfuction 其实就是一个计算三次方的函数,
于是,根据二项式定理,我们可以利用 求出 ,
有了 的低 400 位,来一个 copper 就能分解 了。
最后为了解密 flag 还得求出 ,这个 All 函数其实就是一个泰勒展开在求 的积分,所以
    n = 1885106209951408608833065466098355578239648885277085979696889428331716535742564778501798478665957825315340421821880653818505857049636611632357321104069926874970489073929053910350131880591544986024406953378391135673202854750625745159391997973535848495128365477217006260495413869532372418221652962946340513593002422433536479789576519469228846773250447077165756739529520975715667675188738514871033908115371290569902086064227476952606366538782284487477820835988316471

    r = 13064264216014600984590013161094647588688097945008015283029781423081403612570218487688473281971441574006356719607329041516297420593832435695152551495621303

    # n = p * q * r 
    # mod = myfunction(3)
    # print(mod==n**3)

    # hint2 = pow(3*n+1,p % (2 ** 400),n**3)
    # hint2 = pow(3*n+1,400,n**3)
    # print((hint2%(n**2))//n)
    # pbar = (hint2%(n**2))//(3*n)
    # # pbar = 290093818088445232385211155295987419950746202522777816778903667287369882202987169000686051435796089920601608052312746065
    # R.<x> = Zmod(n)[]
    # f = (2^400) * x + pbar
    # x0 = f.monic().small_roots(X=2^112,beta=0.49)[0]
    # p = int(f(x0))
    # q = int(n)//p
    # p = 10835491201779459536146517032534966141751744767433086585469873899474443209697998673019277269625767885233333299822821960132722036029334072360300733477529681
    # q = 13316873218544878416280346742338579649540959399378233738197413050519025036683226049252858246940675299712559597339200613975360145818807371576573913305896497
    # phi = (p-1)*(q-1)*(r-1)
    # d = inverse(e,phi)
    # m = pow(c,d,p*q*r)
    # m = long_to_bytes(m)
    
    


    k = 2*(n*iroot(n,2)[0])//3
    xor_flag = strxor(long_to_bytes(k >> (k.bit_length() - 8 * flag_len)),flag[:42])
    xor_flag

b'flag{84934a62-f932-968c-fa88-22f0284c0e8e}'
   

社会组

同事在社会组,赛后也把题目给我瞅了瞅,于是在去陇剑杯的飞机上看了一下
from secret import flag, genPrime, generate_g
import random
import math
import os

sieve_base = # from Crypto.Util.number import sieve_base

def rabinMillerTest(n, rounds):
    tested = []
    if n < 3 or (n & 1) == 0:
        return n == 2, tested
        # n might be very large so it might be beneficial to precalculate n-1
    n_1 = n - 1
    # determine m and b so that 2**b * m = n - 1 and b maximal
    b = 0
    m = n_1
    while (m & 1) == 0:
        b += 1
        m >>= 1
    #a smaller number might be faster...
    upper = 2**(max(n.bit_length() >> 510))
    # we need to do at most n-2 rounds.
    for i in range(min(rounds, n - 2)):
        a = random.randint(2, upper)
        while a in tested:
            a = random.randint(2, upper)
        tested.append(a)
        # do the rabin-miller test
        z = pow(a, m, n)  # (a**m) % n
        if z == 1 or z == n_1:
            continue
        composite = 1
        for r in range(b):
            z = (z * z) % n
            if z == 1:
                return 0, tested
            elif z == n_1:
                composite = 0
                break
        if composite:
            return 0, tested
    return 1, tested

def is_prime(N, false_positive_prob=1e-6):
    tested = []
    if N < 3 or N & 1 == 0:
        return N == 2, []
    for p in sieve_base:
        if N == p:
            return 1, tested
        if N % p == 0:
            tested.append(p)
            return 0, tested

    rounds = int(math.ceil(-math.log(false_positive_prob)/math.log(4)))
    return rabinMillerTest(N, rounds)

print("Welcome to my secure key exchange systemn")
while True:
    q = int(input("q:"))
    if q.bit_length() < 256:
        print("oh! too small!!!")
        continue
    jud, tested = is_prime(q)
    if not jud:
        print(f"Bad parameters! test set {tested} not pass.")
    else:
        break

x = int.from_bytes(os.urandom(q.bit_length() // 8), byteorder='big')
p = genPrime(q)
g = generate_g(q, p)
print(f"p: {p}")
print(f"g: {g}")
A = pow(g, x, p)
print(f"Calculate the public key in this way: pow(g, secret, p)")
print(f"eg. pow(g, x, p) = {A}")
print(f"I can give you a hint:)")
r = int(input("r:"))
if r < x and ((p - 1) % r == 0):
    print(pow(g, x, r))
else:
    print("don't need hint?")

for i in range(100):
    B = int(input("give me your public key:"))
    if 1 < B < p:
        shared = pow(B, x, p)
        print(f"our shared key: {shared}")
        x_ = int(input("x?").strip())
        if x_ == x:
            print(flag)
        else:
            print("sorry~")

是一个需要交互的题,把函数 genPrime, generate_g 给偷摸隐藏了起来,估计是有点问题。看一下题目流程:
  1. 用户端输入一个大于 256 比特的素数
  2. 服务端随机生成一个秘密数 ,并根据用户的 生成一个素数 ,在根据 生成一个 ,并给出 。(由于没有源码,这里合理猜测生成的 具有因子 ,而 是一个在模 阶为 的一个元素,这是 Elgamal 参数生成的标准)
  3. 服务端允许用户输入一个 ,如果满足 ,服务端就会输出
  4. 之后服务端让用户输入一个 ,并给出 (就是一个 ECDH),然后让用户猜 ,猜对了就给 ,一共一百次交互机会。
乍一看给出了 rabinMillerTest 还以为让绕过素数检测,但根据后面的流程来看,估计预期应该是根据 hint 得到一些关于 信息,再利用一百次交互,每次搞到一点额外的信息,最后恢复完整的 叭。
但是,注意到给 hint 的部分会给出 ,因此,只要 是光滑的,就能解出 了。而 得是 的一个因子,如果我们对 genPrime 函数猜测的正确的话,那就直接设 为 ,而 是一个光滑数就行了。至于和 的大小关系,由于 的生成和 的比特有关 x = int.from_bytes(os.urandom(q.bit_length() // 8), byteorder='big')注意这里 并不是严格小于 ,所以爆!为了消去“地板除”的影响,要找比特长度刚好是 8 的倍数的 ,然后多跑几次等 比 大,我们就可以直接解 得到 ,然后根据大小关系,对结果加一个 就是 了。
生成 光滑的素数 的脚本
from Crypto.Util.number import *
import random

def genPrime(bit_len):
 while True:
  x = 2
  while x < 2**bit_len:
   x *= random.choice(sieve_base)
  if isPrime(x+1and x.bit_length() % 8 == 0:
   return x+1
print(genPrime(256))

(不过由于没有赛题源码,以上想法全是基于猜测正确的前提下)

2023 祥云杯决赛

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2024年5月14日23:57:33
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                   2023 祥云杯决赛https://cn-sec.com/archives/2070579.html

发表评论

匿名网友 填写信息