ezrsa

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

def pad_flag(flag, bits=1024):
    pad = os.urandom(bits//8 - len(flag))
    return int.from_bytes(flag + pad, "big")

p,q = [getPrime(1024) for _ in "RSA"[1:]] 
a,b = [randint(0, 2**1024) for _ in "RSA"[:-1]] 

n = p * q
e = 0x10001
m = pad_flag(flag)

assert m < n

c = pow(m, e, n)

print(c)
print(n)
print(p + b * q)
print(a * p + q)

# 11850797596095451670524864488046085367812828367468720385501401042627802035427938560866042101544712923470757782908521283827297125349504897418356898752774318846698532487439368216818306352553082800908866174488983776084101115047054799618258909847935672497139557595959270012943240666681053544905262111921321629682394432293381001209674417203517322559283298774214341100975920287314509947562597521988516473281739331823626676843441511662000240327706777269733836703945274332346982187104319993337626265180132608256601473051048047584429295402047392826197446200263357260338332947498385907066370674323324146485465822881995994908925
# 21318014445451076173373282785176305352774631352746325570797607376133429388430074045541507180590869533728841479322829078527002230672051057531691634445544608584952008820389785877589775003311007782211153558201413379523215950193011250189319461422835303446888969202767656215090179505169679429932715040614611462819788222032915253996376941436179412296039698843901058781175173984980266474602529294294210502556931214075073722598225683528873417278644194278806584861250188304944748756498325965302770207316134309941501186831407953950259399116931502886169434888276069750811498361059787371599929532460624327554481179566565183721777
# 4780454330598494796755521994676122817049316484524449315904838558624282970709853419493322324981097593808974378840031638879097938241801612033487018497098140216369858849215655128326752931937595077084912993941304190099338282258345677248403566469008681644014648936628917169410836177868780315684341713654307395687505633335014603359767330561537038768638735748918661640474253502491969012573691915259958624247097465484616897537609020908205710563729989781151998857899164730749018285034659826333237729626543828084565456402192248651439973664388584573568717209037035304656129544659938260424175198672402598017357232325892636389317
# 9819969459625593669601382899520076842920503183309309803192703938113310555315820609668682700395783456748733586303741807720797250273398269491111457242928322099763695038354042594669354762377904219084248848357721789542296806917415858628166620939519882488036571575584114090978113723733730014540463867922496336721404035184980539976055043268531950537390688608145163366927155216880223837210005451630289274909202545128326823263729300705064272989684160839861214962848466991460734691634724996390718260697593087126527364129385260181297994656537605275019190025309958225118922301122440260517901900886521746387796688737094737637604

题目分析

和强网杯的题重合了，p，q和a，b数量级都相同，需要想办法把相乘消去即可，可以构造如下式子

然后构造格去打即可

WP

from Crypto.Util.number import *

#stage3
c=11850797596095451670524864488046085367812828367468720385501401042627802035427938560866042101544712923470757782908521283827297125349504897418356898752774318846698532487439368216818306352553082800908866174488983776084101115047054799618258909847935672497139557595959270012943240666681053544905262111921321629682394432293381001209674417203517322559283298774214341100975920287314509947562597521988516473281739331823626676843441511662000240327706777269733836703945274332346982187104319993337626265180132608256601473051048047584429295402047392826197446200263357260338332947498385907066370674323324146485465822881995994908925
n=21318014445451076173373282785176305352774631352746325570797607376133429388430074045541507180590869533728841479322829078527002230672051057531691634445544608584952008820389785877589775003311007782211153558201413379523215950193011250189319461422835303446888969202767656215090179505169679429932715040614611462819788222032915253996376941436179412296039698843901058781175173984980266474602529294294210502556931214075073722598225683528873417278644194278806584861250188304944748756498325965302770207316134309941501186831407953950259399116931502886169434888276069750811498361059787371599929532460624327554481179566565183721777
t1=4780454330598494796755521994676122817049316484524449315904838558624282970709853419493322324981097593808974378840031638879097938241801612033487018497098140216369858849215655128326752931937595077084912993941304190099338282258345677248403566469008681644014648936628917169410836177868780315684341713654307395687505633335014603359767330561537038768638735748918661640474253502491969012573691915259958624247097465484616897537609020908205710563729989781151998857899164730749018285034659826333237729626543828084565456402192248651439973664388584573568717209037035304656129544659938260424175198672402598017357232325892636389317
t2=9819969459625593669601382899520076842920503183309309803192703938113310555315820609668682700395783456748733586303741807720797250273398269491111457242928322099763695038354042594669354762377904219084248848357721789542296806917415858628166620939519882488036571575584114090978113723733730014540463867922496336721404035184980539976055043268531950537390688608145163366927155216880223837210005451630289274909202545128326823263729300705064272989684160839861214962848466991460734691634724996390718260697593087126527364129385260181297994656537605275019190025309958225118922301122440260517901900886521746387796688737094737637604

brute = 2
for i in range(2^brute):
    for j in range(2^brute):
        L = Matrix(ZZ, [
            [1,0,0,2^brute*t1],
            [0,1,0,2^brute*t2],
            [0,0,2^(1024-brute),t1*i+t2*j-t1*t2],
            [0,0,0,n]
        ])
        L[:,-1:] *= n
        res = L.LLL()[0]

        p = 2^brute*abs(res[0])+i
        if(n % p == 0):
            q=n//p
            phi=(p-1)*(q-1)
            d=inverse(65537,phi)
            print(long_to_bytes(pow(c,d,n)))
            #flag{3z_r5a_15_r34lly_345y_w1sh_u_c0uld_g3t_f14g}

babyenc

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


assert len(flag) == 42
flag1 = flag[:len(flag)//2]
flag2 = flag[len(flag)//2:]
print(flag1.encode())
print(flag2.encode())
m1 = bytes_to_long(flag1.encode())
m2 = bytes_to_long(flag2.encode())

def e_gen(bits):
    e = []
    for _ in range(5):
        e.append(getPrime(bits))
    return e

def enc1(m, e, shift):
    n = next_prime(m << shift)
    tmp = getPrime(256)
    cc = []
    for i in range(len(e)):
        cc.append(int(pow(tmp, e[i], n)))
    return cc

def key_gen(nbits):
    p = getPrime(nbits)
    q = getPrime(nbits)
    return p, q

def enc2(m, p, q, n):
    c = [pow(m, p, n),pow(m, q, n)]
    return c

bits = 6
nbits = 1024
e = e_gen(bits)
shift = 310
c1 = enc1(m1,e,shift)
print("e =",e)
print("c1 =",c1)
p, q = key_gen(nbits)
n = p * q

c2 = enc2(m2, p, q, n)
print("n =",n)
print("c2 =",c2)

'''
e = [43, 37, 53, 61, 59]
c1 = [304054249108643319766233669970696347228113825299195899223597844657873869914715629219753150469421333712176994329969288126081851180518874300706117, 300569071066351295347178153438463983525013294497692191767264949606466706307039662858235919677939911290402362961043621463108147721176372907055224, 294806502799305839692215402958402593834563343055375943948669528217549597192296955202812118864208602813754722206211899285974414703769561292993531, 255660645085871679396238463457546909716172735210300668843127008526613931533718130479441396195102817055073131304413673178641069323813780056896835, 194084621856364235027333699558487834531380222896709707444060960982448111129722327145131992393643001072221754440877491070115199839112376948773978]
n = 16175064088648626038689748434699435826247716579187475966092822028609536761351820951820375552440329596553448265674841223230257463367834546091974959931391707199002842774795702094681528411058318007858638798643010942408552063479863545047616823056802010158288409527763686086960916160949496083789920012040215745627854092010308869223489833074860062054019221397227691063339148923860987250696934050122115972982286012688955816234717242567815830341836031567275888691320640526306946586793028267588302696611724356566003447616419092371914903382944112125852939011729294400479171568234647164730191643282793224422368321464125847020067
c2 = [12053085469218650692076937068797478047679005585690696222988148891925249697123080938461512785257424651119325211991331622346111396522606463631848519999574540677285771456451798811902760319940781754940936484802949729402283626052963389539032949160905330315285409948932070460455535716223838438994608837585387741418172014634472651248450564788332400265295308803291229281839428962457585593065595521459963501453576128172245723315811398209056633738967993602668795794847967331946516181453804430961308142497659799416125763566765485760600358126127595222197324155943818136202233758771243043559460620477085689770403810190118485243364, 13878717704635179949812987989626985689079485417345626168168664941124566737996226347895779823781042724620099437593856913505609774929187720381745418166924229828643565384137488017127800518133460531729559408120123922005898834268035918798610962941606864727966963354615441094676621013036726097763695675723672289505864372820096404707522755617527884121630784469379311199256277022770033036782130954108210409787680433301426480762532000133464370267551845990395683108170721952672388388178378604502610341465223041534665133155077544973384500983410220955683686526835733853985930134970899200234404716865462481142496209914197674463932]
'''

题目分析

part1

已知

pow(temp,e,n)

交叉消元一下就能得到

所以可以得到几组kn然后求公因数即可

e = [43, 37, 53, 61, 59]
c = [304054249108643319766233669970696347228113825299195899223597844657873869914715629219753150469421333712176994329969288126081851180518874300706117, 300569071066351295347178153438463983525013294497692191767264949606466706307039662858235919677939911290402362961043621463108147721176372907055224, 294806502799305839692215402958402593834563343055375943948669528217549597192296955202812118864208602813754722206211899285974414703769561292993531, 255660645085871679396238463457546909716172735210300668843127008526613931533718130479441396195102817055073131304413673178641069323813780056896835, 194084621856364235027333699558487834531380222896709707444060960982448111129722327145131992393643001072221754440877491070115199839112376948773978]
knlist = []
for i in range(4):
    knlist.append(c[i]**e[i+1] - c[i+1]**e[i])

for i in range(3):
    kn = gcd(knlist[i],knlist[i+1])

n = kn

print(long_to_bytes(n>>310))

part2

构造一个copper来求较小的m即可

n = 16175064088648626038689748434699435826247716579187475966092822028609536761351820951820375552440329596553448265674841223230257463367834546091974959931391707199002842774795702094681528411058318007858638798643010942408552063479863545047616823056802010158288409527763686086960916160949496083789920012040215745627854092010308869223489833074860062054019221397227691063339148923860987250696934050122115972982286012688955816234717242567815830341836031567275888691320640526306946586793028267588302696611724356566003447616419092371914903382944112125852939011729294400479171568234647164730191643282793224422368321464125847020067
c2 = [12053085469218650692076937068797478047679005585690696222988148891925249697123080938461512785257424651119325211991331622346111396522606463631848519999574540677285771456451798811902760319940781754940936484802949729402283626052963389539032949160905330315285409948932070460455535716223838438994608837585387741418172014634472651248450564788332400265295308803291229281839428962457585593065595521459963501453576128172245723315811398209056633738967993602668795794847967331946516181453804430961308142497659799416125763566765485760600358126127595222197324155943818136202233758771243043559460620477085689770403810190118485243364, 13878717704635179949812987989626985689079485417345626168168664941124566737996226347895779823781042724620099437593856913505609774929187720381745418166924229828643565384137488017127800518133460531729559408120123922005898834268035918798610962941606864727966963354615441094676621013036726097763695675723672289505864372820096404707522755617527884121630784469379311199256277022770033036782130954108210409787680433301426480762532000133464370267551845990395683108170721952672388388178378604502610341465223041534665133155077544973384500983410220955683686526835733853985930134970899200234404716865462481142496209914197674463932]

PR.<m> = PolynomialRing(Zmod(n))
f = m^2 - (c2[0]+c2[1])*m + c2[0]*c2[1]
x0 = f.small_roots()

print(long_to_bytes(int(x0[0])))

WP

from Crypto.Util.number import *

e = [43, 37, 53, 61, 59]
c = [304054249108643319766233669970696347228113825299195899223597844657873869914715629219753150469421333712176994329969288126081851180518874300706117, 300569071066351295347178153438463983525013294497692191767264949606466706307039662858235919677939911290402362961043621463108147721176372907055224, 294806502799305839692215402958402593834563343055375943948669528217549597192296955202812118864208602813754722206211899285974414703769561292993531, 255660645085871679396238463457546909716172735210300668843127008526613931533718130479441396195102817055073131304413673178641069323813780056896835, 194084621856364235027333699558487834531380222896709707444060960982448111129722327145131992393643001072221754440877491070115199839112376948773978]
knlist = []
for i in range(4):
    knlist.append(c[i]**e[i+1] - c[i+1]**e[i])

for i in range(3):
    kn = gcd(knlist[i],knlist[i+1])

n = kn

print(long_to_bytes(n>>310))
#flag{3e99c26b-efdd-4c

n = 16175064088648626038689748434699435826247716579187475966092822028609536761351820951820375552440329596553448265674841223230257463367834546091974959931391707199002842774795702094681528411058318007858638798643010942408552063479863545047616823056802010158288409527763686086960916160949496083789920012040215745627854092010308869223489833074860062054019221397227691063339148923860987250696934050122115972982286012688955816234717242567815830341836031567275888691320640526306946586793028267588302696611724356566003447616419092371914903382944112125852939011729294400479171568234647164730191643282793224422368321464125847020067
c2 = [12053085469218650692076937068797478047679005585690696222988148891925249697123080938461512785257424651119325211991331622346111396522606463631848519999574540677285771456451798811902760319940781754940936484802949729402283626052963389539032949160905330315285409948932070460455535716223838438994608837585387741418172014634472651248450564788332400265295308803291229281839428962457585593065595521459963501453576128172245723315811398209056633738967993602668795794847967331946516181453804430961308142497659799416125763566765485760600358126127595222197324155943818136202233758771243043559460620477085689770403810190118485243364, 13878717704635179949812987989626985689079485417345626168168664941124566737996226347895779823781042724620099437593856913505609774929187720381745418166924229828643565384137488017127800518133460531729559408120123922005898834268035918798610962941606864727966963354615441094676621013036726097763695675723672289505864372820096404707522755617527884121630784469379311199256277022770033036782130954108210409787680433301426480762532000133464370267551845990395683108170721952672388388178378604502610341465223041534665133155077544973384500983410220955683686526835733853985930134970899200234404716865462481142496209914197674463932]

PR.<m> = PolynomialRing(Zmod(n))
f = m^2 - (c2[0]+c2[1])*m + c2[0]*c2[1]
x0 = f.small_roots()

print(long_to_bytes(int(x0[0])))
#d2-bbe5-1420eaaa3b30}


#flag{3e99c26b-efdd-4cd2-bbe5-1420eaaa3b30}

PolyPrime

from Crypto.Util.number import getPrime, isPrime, bytes_to_long
#from secret import flag
import random
flag=b"1"

k = getPrime(333 * 5)
e = 65537
m = bytes_to_long(flag)

def temp_calc(x): 
    return (x * random.randint(2, 5)) ^ random.randint(100, 500)

def some_calc(size, depth):
    def sums_calc(base, degree): 
        result = 0
        for i in range(degree): 
            temp = temp_calc(base ** i)
            result += base ** i + temp // temp_calc(base**(i + 1))
            print(base**i)
        return result

    while True:
        prime_number = getPrime(size)

        temp_number = temp_calc(prime_number)
        poly_primes = sums_calc(prime_number, depth)  
        if temp_number % 3 == 0: 
            temp_number = temp_calc(poly_primes)
            continue

        if isPrime(poly_primes):
            return prime_number, poly_primes


p, q = some_calc(333, 5)

n = p * q * k
c = pow(m, e, n)

print(f"{n = }")
print(f"{e = }")
print(f"{c = }")

# n = 659401821142664131364043958430747314465977448744532421905138184036743766362324320051729418680079590835903781525157600055608268591994754328563246418114269690475272262915661210669701969695314157602927462228079044905276064391615467601628466982949165371933147600418057089432876120807721483665788557812323607370950442342057254926375842684430119320789097029996211564275310819486004520088130146630452262340185192110066151930586956190499953220051855668474863659201165952231016814569364299000130323859609047687714260776467149437031397019411599103716200258382231589757031469168245396061619327867355414287059363691024984066070128364157490336808211223714816668548049472199794493895870662970541167490686648385211854469386812214775829776376273299648505880034651930322294605482489225723014758138525637864689594748771025870209444029669477294995691067669374491852721622469656239730320092112222948718027850386898461208936333788173263904607181823233002355650353116486156927403178510412091666951574340730799316032588099237
# c = 455042981325030540026829365098432813829591020497037525707600104817313008442900331256387443469027825344761381076471749826547710666806180999603254398722965179851898391700090501419875562919365894255855734276825027850795202733875071307773598881254863911398285400038957998385685292965812925607278232164067624548120378758414574370042945538632864154772437639053907149514588502689277630450575630168099810584842881257614115970132960679023265157277718654731105815060916800751033956715430930381384344469220951638102432198422350425390757155267143393385221465041749156153517556389417033187856017198907366720281408810250981776112815100319814215140919133440637395953567624057248002125277569474190364142291136361144552953540727462623677375371327473687508344483184466522697912317252462246054471196345909304668083637177166153036111122244170846815657389873986264187766636830907458940128844256504176917204131708083105093700023335939233711693409336968008112511482237441198116493965744903995545941700742865846469036763734618
# e = 0x10001

题目分析

参考-sus

思路是一样的，这里最高阶是5，需要生成一个度为5的随机多项式，g^n在环N上的一次项或二次项系数就为kp,与n求公因数就能得到p，从而再推出r,最后就是求phi然后解密了。

WP

from Crypto.Util.number import *

n = 659401821142664131364043958430747314465977448744532421905138184036743766362324320051729418680079590835903781525157600055608268591994754328563246418114269690475272262915661210669701969695314157602927462228079044905276064391615467601628466982949165371933147600418057089432876120807721483665788557812323607370950442342057254926375842684430119320789097029996211564275310819486004520088130146630452262340185192110066151930586956190499953220051855668474863659201165952231016814569364299000130323859609047687714260776467149437031397019411599103716200258382231589757031469168245396061619327867355414287059363691024984066070128364157490336808211223714816668548049472199794493895870662970541167490686648385211854469386812214775829776376273299648505880034651930322294605482489225723014758138525637864689594748771025870209444029669477294995691067669374491852721622469656239730320092112222948718027850386898461208936333788173263904607181823233002355650353116486156927403178510412091666951574340730799316032588099237
c = 455042981325030540026829365098432813829591020497037525707600104817313008442900331256387443469027825344761381076471749826547710666806180999603254398722965179851898391700090501419875562919365894255855734276825027850795202733875071307773598881254863911398285400038957998385685292965812925607278232164067624548120378758414574370042945538632864154772437639053907149514588502689277630450575630168099810584842881257614115970132960679023265157277718654731105815060916800751033956715430930381384344469220951638102432198422350425390757155267143393385221465041749156153517556389417033187856017198907366720281408810250981776112815100319814215140919133440637395953567624057248002125277569474190364142291136361144552953540727462623677375371327473687508344483184466522697912317252462246054471196345909304668083637177166153036111122244170846815657389873986264187766636830907458940128844256504176917204131708083105093700023335939233711693409336968008112511482237441198116493965744903995545941700742865846469036763734618
e = 0x10001
k = 5

R = Zmod(n)["x"]
while True:
    Q = R.quo(R.random_element(k))
    pp = gcd(ZZ(list(Q.random_element() ^ n)[1]), n)
    if pp != 1:
        qq = sum([pp**i for i in range(k)])
        rr = n // (pp * qq)
        assert n == pp * qq * rr
        break
phi = (pp - 1) * (qq - 1) * (rr - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(int(m))

rickroll

from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from pwn import xor
import os
from hashlib import *
from random import *


HINT = b"123"
FLAG = "flag{xxxxxxxx}"
EFFECTIVE_ROW = 6


def rickroll_loader():
    with open("rickroll", "r") as file:
        lines = [line.strip().encode() for line in file if line.strip()]
    return lines


def find_ezprime(size):
    while True:
        prime = getPrime(size)
        if isPrime(prime // 2):
            return prime


def secure_encrypt(message_parts, hint_value):
    modulus = find_ezprime(260)

    key_material = os.urandom(32)
    multipliers = [getrandbits(256) for _ in range(EFFECTIVE_ROW)]

    encrypted_parts = [
        int((multiplier * hint_value + bytes_to_long(xor(pad(chunk, 32)
            [::-1], key_material))) % (modulus - 1))
        for multiplier, chunk in zip(multipliers, message_parts)
    ]

    return encrypted_parts, multipliers, modulus


if __name__ == "__main__":
    rickroll = rickroll_loader()
    print(rickroll)
    m = bytes_to_long(HINT)

    encrypted_lyrics, multipliers, modulus = secure_encrypt(
        rickroll[:EFFECTIVE_ROW], m)

    print("S =", encrypted_lyrics)
    print("V =", multipliers)
    print("n =", modulus)


'''
S = [624073892368439332713131144655355187273652775732037030273908973687487472640419, 1129513550732743550887354593625951854836036688324123410864182971141396110133306, 1117643028354341949186759218964558582164677605237787761003042032239935547551873, 151619055620013230556169740951169935393567570823439146992800622058967940011364, 596106506159944398847755500086869373163910176213091804211992440336880292610397, 685472210701608040945173323626153641749419080165879222271110177606156013942182]
V = [100024809269721744282017864103544473542698741247649693420201028956644193231147, 85493218764912449360009112267171851264674952927507787108286827385372626006804, 75451455656190167222034904545925816909383290106210237096763781707294423744719, 1864420400658866895837249178680154965580281261003086054650703872439476331244, 111069754111223622246512532174936637994215526100226395068812327641951277359169, 88031405587803201423744918486788030404029698214504194443110805396831023823738]
n = 1497114501625523578039715607844306226528709444454126120151416887663514076507099
'''

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you

Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

--A mysterious singer who does not want to be named.

题目分析

encrypted_parts = [
        int((multiplier * hint_value + bytes_to_long(xor(pad(chunk, 32)
            [::-1], key_material))) % (modulus - 1))
        for multiplier, chunk in zip(multipliers, message_parts)
    ]


S=V*hint+chunk^key

这里S,V,key都是已知的，但是因为异或操作，要处理chunk有点棘手，我一开始的思路就是先将异或展开写成

2^i*chunk[i]*key[i]

这样的形式，然后构造一个格来尝试求解，但是有点复杂，并没有成功求解出来。

接下来我注意到了

def rickroll_loader():
    with open("rickroll", "r") as file:
        lines = [line.strip().encode() for line in file if line.strip()]
    return lines
rickroll = rickroll_loader()
print(rickroll)

for i in range(6):
    rickroll[i]=bytes_to_long(pad(rickroll[i], 32)[::-1])
print(rickroll)

在逆向后的rickroll中存在几组开头相近的数据即r[0]和r[4],r[1]和r[3]，同时因为逆向处理，低位也是存在大量重复的，那么我们将这样的数据做差

显然异或只差是一个小量，在低位上还有许多重复的0，可以用2^k消去，这样我们就能构造相应的格来求解

WP

from Crypto.Util.number import *


S = [624073892368439332713131144655355187273652775732037030273908973687487472640419, 1129513550732743550887354593625951854836036688324123410864182971141396110133306, 1117643028354341949186759218964558582164677605237787761003042032239935547551873, 151619055620013230556169740951169935393567570823439146992800622058967940011364, 596106506159944398847755500086869373163910176213091804211992440336880292610397, 685472210701608040945173323626153641749419080165879222271110177606156013942182]
V = [100024809269721744282017864103544473542698741247649693420201028956644193231147, 85493218764912449360009112267171851264674952927507787108286827385372626006804, 75451455656190167222034904545925816909383290106210237096763781707294423744719, 1864420400658866895837249178680154965580281261003086054650703872439476331244, 111069754111223622246512532174936637994215526100226395068812327641951277359169, 88031405587803201423744918486788030404029698214504194443110805396831023823738]
n = 1497114501625523578039715607844306226528709444454126120151416887663514076507099

p = n // 2

a=(S[0]-S[4]) * inverse(2^96, p) % p
b=(S[1]-S[3]) * inverse(2^96, p) % p
c=(V[0]-V[4]) * inverse(2^96, p) % p
d=(V[1]-V[3]) * inverse(2^96, p) % p

M = matrix(ZZ, [[p, 0, 0, 0],
                [0, p, 0, 0],
                [a, b,1,0],
                [c, d,0,1]])

bits = [84, 84, 0, 256]
weights = [2^(256-i) for i in bits]
M = M * diagonal_matrix(weights)
M = M.LLL()
M = M /diagonal_matrix(weights)

print(long_to_bytes(int(abs(M[1, 3]))))

tarsrc

# task.sage
from Crypto.Util.number import *
from secret import flag
import random

nbit  = 1024
beta  = 0.30
delta = 0.10

p = getPrime(int(beta * nbit))
q = getPrime(nbit - int(beta * nbit))

N = p * q
phi = (p-1) * (q-1)
while 1:
    dq = random.randrange(1,int(N ** delta))
    if dq > q-1:
        continue
    dp = random.randrange(1,p-1)
    try:
        d = Integer(crt([dp%(p-1),dq%(q-1)],[p-1,q-1]))
    except:
        continue
    if GCD(d,phi) == 1:
        e = int(inverse(d,phi))
        break

seckey, pubkey = (p,q,d,dp,dq), (N,e)
print(f"N = {N}")
print(f"e = {e}")

c = pow(bytes_to_long(flag), e, N)
print(f"c = {c}")
"""
N = 61857467041120006957454494977971762866359211220721592255304580940306873708357617802596067329984189345493420858543581027612648626678588277060222860337783377316655375278359169520243355170247177279595812282793212550819124960549824278287538977769728573023023364686725321548391592858202718446127851076431000427033
e = 22696852369762746127523066296087974245933137295782964284054040654103039210164173227291367914580709029582944005335464668969366909190396194570924426653294883884186299265660358589254391341147028477295482787041170991166896788171334992065199814524969470117229229967188623636764051681654720429531708441920158042161
c = 41862679760722981662840433621129671566139143933210627878095169470855743742734397276638345217059912784871301273620533442249011607182329472311453700434692358352210197988000738272869600692181834281813995048665466937302183039555350612260646428575598237960405962714063137455677605629008760761743568236135324015278
"""

题目分析

找到春哥的板子就能梭了

WP

from copy import deepcopy
# https://www.iacr.org/archive/pkc2006/39580001/39580001.pdf
# Author: ZM__________J, To1in
# N = 61857467041120006957454494977971762866359211220721592255304580940306873708357617802596067329984189345493420858543581027612648626678588277060222860337783377316655375278359169520243355170247177279595812282793212550819124960549824278287538977769728573023023364686725321548391592858202718446127851076431000427033
# e = 22696852369762746127523066296087974245933137295782964284054040654103039210164173227291367914580709029582944005335464668969366909190396194570924426653294883884186299265660358589254391341147028477295482787041170991166896788171334992065199814524969470117229229967188623636764051681654720429531708441920158042161
# alpha = log(e, N)
# beta = 0.3
# delta = 0.1
# P.<x,y,z>=PolynomialRing(ZZ)

# X = ceil(2 * N^(alpha + beta + delta - 1))
# Y = ceil(2 * N^beta)
# Z = ceil(2 * N^(1 - beta))

# def f(x,y):
#     return x*(N-y)+N
# def trans(f):
#     my_tuples = f.exponents(as_ETuples=False)
#     g = 0
#     for my_tuple in my_tuples:
#         exponent = list(my_tuple)
#         mon = x ^ exponent[0] * y ^ exponent[1] * z ^ exponent[2]
#         tmp = f.monomial_coefficient(mon)

#         my_minus = min(exponent[1], exponent[2])
#         exponent[1] -= my_minus
#         exponent[2] -= my_minus
#         tmp *= N^my_minus
#         tmp *= x ^ exponent[0] * y ^ exponent[1] * z ^ exponent[2]

#         g += tmp
#     return g

# m = 5 # need to be adjusted according to different situations
# tau = ((1 - beta)^2 - delta) / (2 * beta * (1 - beta))
# sigma = (1 - beta - delta) / (2 * (1 - beta))

# print(sigma * m)
# print(tau * m)

# s = ceil(sigma * m)
# t = ceil(tau * m)
# my_polynomials = []
# for i in range(m+1):
#     for j in range(m-i+1):
#         g_ij = trans(e^(m-i) * x^j * z^s * f(x, y)^i)
#         my_polynomials.append(g_ij)

# for i in range(m+1):
#     for j in range(1, t+1):
#         h_ij = trans(e^(m-i) * y^j * z^s * f(x, y)^i)
#         my_polynomials.append(h_ij)

# known_set = set()
# new_polynomials = []
# my_monomials = []

# # construct partial order
# while len(my_polynomials) > 0:
#     for i in range(len(my_polynomials)):
#         f = my_polynomials[i]
#         current_monomial_set = set(x^tx * y^ty * z^tz for tx, ty, tz in f.exponents(as_ETuples=False))
#         delta_set = current_monomial_set - known_set
#         if len(delta_set) == 1:
#             new_monomial = list(delta_set)[0]
#             my_monomials.append(new_monomial)
#             known_set |= current_monomial_set
#             new_polynomials.append(f)            
#             my_polynomials.pop(i)
#             break
#     else:
#         raise Exception('GG')

# my_polynomials = deepcopy(new_polynomials)

# nrows = len(my_polynomials)
# ncols = len(my_monomials)
# L = [[0 for j in range(ncols)] for i in range(nrows)]

# for i in range(nrows):
#     g_scale = my_polynomials[i](X * x, Y * y, Z * z)
#     for j in range(ncols):
#         L[i][j] = g_scale.monomial_coefficient(my_monomials[j])

# # remove N^j
# for i in range(nrows):
#     Lii = L[i][i]
#     N_Power = 1
#     while (Lii % N == 0):
#         N_Power *= N
#         Lii //= N
#     L[i][i] = Lii
#     for j in range(ncols):
#         if (j != i):
#             L[i][j] = (L[i][j] * inverse_mod(N_Power, e^m))

# L = Matrix(ZZ, L)
# nrows = L.nrows()

# L = L.LLL()
# # Recover poly
# reduced_polynomials = []
# for i in range(nrows):
#     g_l = 0
#     for j in range(ncols):
#         g_l += L[i][j] // my_monomials[j](X, Y, Z) * my_monomials[j]
#     reduced_polynomials.append(g_l)

# # eliminate z
# my_ideal_list = [y * z - N] + reduced_polynomials

# # Variety
# my_ideal_list = [Hi.change_ring(QQ) for Hi in my_ideal_list]
# for i in range(len(my_ideal_list),3,-1):
#     print(i)
#     V = Ideal(my_ideal_list[:i]).variety(ring=ZZ)
#     print(V)
#[{z: 426614979768518060635433317149972303610396098751783498586225631589479798053751568080185868568717967344782297587209012869059719479952019313461850777653567018452929932659204669967695196434044149034271037885062392902287, y: 144996003362760405215910388196517232449311004246441924325936847006315296003811348342536838359, x: 66838488369949543369599279980954380920457752396291961341704448955532596917094831390389571041281062121515985150418852560085}]

from Crypto.Util.number import *


N = 61857467041120006957454494977971762866359211220721592255304580940306873708357617802596067329984189345493420858543581027612648626678588277060222860337783377316655375278359169520243355170247177279595812282793212550819124960549824278287538977769728573023023364686725321548391592858202718446127851076431000427033
e = 22696852369762746127523066296087974245933137295782964284054040654103039210164173227291367914580709029582944005335464668969366909190396194570924426653294883884186299265660358589254391341147028477295482787041170991166896788171334992065199814524969470117229229967188623636764051681654720429531708441920158042161
c = 41862679760722981662840433621129671566139143933210627878095169470855743742734397276638345217059912784871301273620533442249011607182329472311453700434692358352210197988000738272869600692181834281813995048665466937302183039555350612260646428575598237960405962714063137455677605629008760761743568236135324015278

p=144996003362760405215910388196517232449311004246441924325936847006315296003811348342536838359
q=N//p
assert p*q==N
phi=(p-1)*(q-1)
d=inverse(e,phi)
print(long_to_bytes(pow(c,d,N)))

cry

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import *
import random
import gmpy2
from secrets import iv, KEY


# I think you will definitely be interested in the content in PNG!
def banner():
    print(
        """
=======================================================================================
     _      _   _                 _           ____                                _   
    / \    | | (_)   ___    ___  ( )  ___    / ___|    ___    ___   _ __    ___  | |_ 
   / _ \   | | | |  / __|  / _ \ |/  / __|   \___ \   / _ \  / __| | '__|  / _ \ | __|
  / ___ \  | | | | | (__  |  __/     \__ \    ___) | |  __/ | (__  | |    |  __/ | |_ 
 /_/   \_\ |_| |_|  \___|  \___|     |___/   |____/   \___|  \___| |_|     \___|  \__|

=======================================================================================
"""
    )


def pad(m):
    return m + (16 - (len(m) % 16)) * b"\x00"


def get_pngdata():
    with open("picture.png", "rb") as f:
        png_data = f.read()
    return pad(png_data)


def get_Key(bits):
    p = getPrime(bits)
    g = getPrime(bits // 2)
    d = random.randint(1, p - 2)
    y = pow(g, d, p)
    public, private = (p, g, y), d
    return public, private


def Signature(m, public, private):
    m = bytes_to_long(m)
    p, g, _ = public
    d = private
    while True:
        k = random.randint(1, p - 1)
        if gmpy2.gcd(k, p - 1) == 1:
            break
    r = pow(g, k, p)
    s = ((m - d * r) * inverse(k, p - 1)) % (p - 1)
    return (r, s)


def Verity(m, sign, public):
    m = bytes_to_long(m)
    p, g, y = public
    r, s = sign
    if pow(g, m, p) == (pow(y, r, p) * pow(r, s, p)) % p:
        return True
    else:
        return False


def chall():
    banner()

    pub, pri = get_Key(512)
    png_data = get_pngdata()
    print(
        "Hello! I'm Alice. To ensure that you are truly Bob, I need to verify your identity first!"
    )
    print("Can I help you sign once? Is there anything you need to sign?")
    print(f"Here are your public key:{pub}")
    message = long_to_bytes(int(input("Give me what you need to sign:")))
    if message == b"Bob":
        print("No, it's not possible!!!")
        exit(1)
    print("Here are your sign:")
    r, s = Signature(message, pub, pri)
    print(f"r = {r}")
    print(f"s = {s}")

    print("Tell me your signature so that I know you are truly Bob.")
    r = int(input("r = "))
    s = int(input("s = "))

    if Verity(b"Bob", (r, s), pub):
        print(
            "I have a great photo that I would like to share with you. Let's send it to you in our old way! Hope you still keep our IV!"
        )
        aes = AES.new(KEY, AES.MODE_CBC, iv)
        enc_data = hex(bytes_to_long(aes.encrypt(png_data)))[2:]
        print(f"Here is my encoded data:{enc_data}")
        print(f"Here is my key:{KEY.decode()}")
        print("In summary, I wish you a wonderful day!")
    else:
        print("Alright, you're not Bob, I don't have anything to chat with anymore.")
        exit(1)


if __name__ == "__main__":
    try:
        chall()
    except:
        exit(1)

题目分析

遇到这种签名认证题一般就是找和原来的条件有什么区别，这里虽然不能用Bob来签名，但是会发现签名过程中没有做哈希操作，所以构造一个p被的"Bob"字符串传过去就能实现认证绕过。

接下来他会将flag图片做一层aes加密，用的是cbc模式