首页 比赛

# sigin

# 题目

from Crypto.Util.number import *
from gmpy2 import *
from FLAG import flag
def gen_key():
    (p,q,n,e,d) = (0 for _ in range(5))
    p = getStrongPrime(1024)
    q = next_prime(p)
#     q = p + 1
#     while(True):
#         q += 2 if q & 1 else 1
#         if is_prime(q, 30):
#             break
    n = p*q
    e = 0x10001
    d = invert(e, (p-1)*(q-1))
    par = (p,q,n,e,d)
    return par
def leak(par, c):
    assert len(par) == 5
    (p,q,n,e,d) = par
    print("Here's something for you.")
    print("n =",n)
    print("e =",e)
    print("c_mod_p =",c % p)
    print("c_mod_q =",c % q)
def enc(message, par):
    assert len(par) == 5
    (p,q,n,e,d) = par
    m = bytes_to_long(message)
    c = powmod(m,e,n)
    return c
if __name__ == '__main__':
    par = gen_key()
    c = enc(flag, par)
    leak(par, c)
"""
Here's something for you.
n = 19955580242010925349026385826277356862322608500430230515928936214328341334162349408990409245298441768036250429913772953915537485025323789254947881868366911379717813713406996010824562645958646441589124825897348626601466594149743648589703323284919806371555688798726766034226044561171215392728880842964598154362131942585577722616354074267803330013886538511795383890371097812191816934883393255463554256887559394146851379087386846398690114807642170885445050850978579391063585254346364297374019309370189128443081285875218288166996242359495992824824109894071316525623741755423467173894812627595135675814789191820979950786791
e = 65537
c_mod_p = 32087476819370469840242617415402189007173583393431940289526096277088796498999849060235750455260897143027010566292541554247738211165214410052782944239055659645055068913404216441100218886028415095562520911677409842046139862877354601487378542714918065194110094824176055917454013488494374453496445104680546085816
c_mod_q = 59525076096565721328350936302014853798695106815890830036017737946936659488345231377005951566231961079087016626410792549096788255680730275579842963019533111895111371299157077454009624496993522735647049730706272867590368692485377454608513865895352910757518148630781337674813729235453169946609851250274688614922
"""
# exp
q = 141264221379693044160345378758459195879285464451894666001807667429134348549398732060237738374405784248735752195059908618618110595213605790125890251970818437656069617772772793421437649079362238861287098916200835889507111259332056471215428085418047179545017193159169629731673653136069647622114441162534727202901
p = 141264221379693044160345378758459195879285464451894666001807667429134348549398732060237738374405784248735752195059908618618110595213605790125890251970818437656069617772772793421437649079362238861287098916200835889507111259332056471215428085418047179545017193159169629731673653136069647622114441162534727202891
n = 19955580242010925349026385826277356862322608500430230515928936214328341334162349408990409245298441768036250429913772953915537485025323789254947881868366911379717813713406996010824562645958646441589124825897348626601466594149743648589703323284919806371555688798726766034226044561171215392728880842964598154362131942585577722616354074267803330013886538511795383890371097812191816934883393255463554256887559394146851379087386846398690114807642170885445050850978579391063585254346364297374019309370189128443081285875218288166996242359495992824824109894071316525623741755423467173894812627595135675814789191820979950786791
e = 0x10001
c_mod_p = 32087476819370469840242617415402189007173583393431940289526096277088796498999849060235750455260897143027010566292541554247738211165214410052782944239055659645055068913404216441100218886028415095562520911677409842046139862877354601487378542714918065194110094824176055917454013488494374453496445104680546085816
c_mod_q = 59525076096565721328350936302014853798695106815890830036017737946936659488345231377005951566231961079087016626410792549096788255680730275579842963019533111895111371299157077454009624496993522735647049730706272867590368692485377454608513865895352910757518148630781337674813729235453169946609851250274688614922
d=invert(e,(p-1))
print(p>q)
print(long_to_bytes(pow(c_mod_p,d,p)))
# COA_RSA（复现）
# 题目
from Crypto.Util.number import getStrongPrime, inverse, bytes_to_long
from secret import get_e, message, flag
def gen_parameter():
    p = getStrongPrime(1024)
    q = getStrongPrime(1024)
    N = p*q
    phi_N = (p-1) * (q-1)
    e = get_e(N, phi_N)
    d = inverse(e, phi_N)
    print(f"N:{N}\n")
    print(f"e:{e}\n")
    return N, e
def enc(m, e, N):
    return pow(m, e, N)
if __name__ == '__main__':
    assert(len(message) == 18)
    assert(flag == b"NepCTF{" + message + b"}")
    N, e = gen_parameter()
    m = bytes_to_long(message)
    c = enc(m, e, N)
    print(f"c:{c}")
"""
N:21584562909016222405243274981318074723609424537864138818516166296882870952596923388616896100179452902343709246295468740335682613555154383977025156631083258377497353559709636001246215851357586251697339782140616762844466658464225538929007012548727508420837702781524936615164070353418037478517089569783507555024418411710631778073941565485748505472232785028182423960096719453903248061164351629862893495202801853287312265865916733075532360012981688805080299664971109817752216823608878051817158172160419426189481753020154076548471877219325637944601624370884640014467928928695819398270014246851395540617763179525187009648347
e:3083508987002317486463324997331153531944203505409162688359452328126124421799560484088128014311350414620529892327924105762240373365022054853860736661583322625356764794244233714463745121622512321671048540305802394692066665494889362704143858935532501202976814683074990945023438621916862496931012795683358222146303422749958603642494190335211644060403826011553655733835479351434022282429633638548092493767861402690047591624267078125799219896130381280612151738318061042109602694447606410766564110264194828211637692086652912524063147129310052531789754620749834783108524619617738417203269142329494376062347356009094704271801
c:4350922598266339224026193891975078418170168801819772034264767820713898265684630717877568988722980203827973605369872324389093738872638952249759042892387749292013137399168284781320083750172563798340746904451459359268152189983004829803065811628192447436195347501480101582498240174872791092809557067538800318476384792579696811714128502969704568997167132768453189707964546102168532460995624338582249438596921314744866700025932162716723912105789085167524526913197129852605391260182535842364550510703599942313178440055016324692710162447783500265413604087721982116926701740447032328198647967485123967003172122184982695286738
"""
根据提示用格
memodn=cm^e mod n=c
me−x∗mxmodn=cm^{e-x}*m^{x}\quad mod\quad n=c
令 x=1
m1−x∗c=mmodnm^{1-x}*c=m\quad mod\quad n
m1−x∗c−k∗n=mm^{1-x}*c-k*n=m
c,n 已知
$\begin {bmatrix} 1,c\0,n \end {bmatrix} $ 的最短向量
n=21584562909016222405243274981318074723609424537864138818516166296882870952596923388616896100179452902343709246295468740335682613555154383977025156631083258377497353559709636001246215851357586251697339782140616762844466658464225538929007012548727508420837702781524936615164070353418037478517089569783507555024418411710631778073941565485748505472232785028182423960096719453903248061164351629862893495202801853287312265865916733075532360012981688805080299664971109817752216823608878051817158172160419426189481753020154076548471877219325637944601624370884640014467928928695819398270014246851395540617763179525187009648347
e=3083508987002317486463324997331153531944203505409162688359452328126124421799560484088128014311350414620529892327924105762240373365022054853860736661583322625356764794244233714463745121622512321671048540305802394692066665494889362704143858935532501202976814683074990945023438621916862496931012795683358222146303422749958603642494190335211644060403826011553655733835479351434022282429633638548092493767861402690047591624267078125799219896130381280612151738318061042109602694447606410766564110264194828211637692086652912524063147129310052531789754620749834783108524619617738417203269142329494376062347356009094704271801
c=4350922598266339224026193891975078418170168801819772034264767820713898265684630717877568988722980203827973605369872324389093738872638952249759042892387749292013137399168284781320083750172563798340746904451459359268152189983004829803065811628192447436195347501480101582498240174872791092809557067538800318476384792579696811714128502969704568997167132768453189707964546102168532460995624338582249438596921314744866700025932162716723912105789085167524526913197129852605391260182535842364550510703599942313178440055016324692710162447783500265413604087721982116926701740447032328198647967485123967003172122184982695286738
v1 = vector(ZZ, [1, c])
v2 = vector(ZZ, [0, n])
m = matrix([v1,v2])
f,g= m.LLL()[0]
print(f, g)
出的是负数
x=1 就是最短向量的时候？？
不太懂
想着 x 可能未知？
还是 x=1 时
这。。。。
看完 wp
这个 hint 给的。。。。
  1. 根据分析，$\begin {bmatrix} A\m \end {bmatrix} $ 满足 Minkowski's bound. 于是有
A2+m2=(m1−emodn)2+m2<=2A^2+m^2=(m^{1-e}mod n)^2+m^2<=2
可见
m1−emodnm^{1-e}mod n
的量级为n\sqrt n
  1. 可以猜测出 1-e 很接近于 m 的阶，进而有e=ϕ(n)/a−be=\phi(n)/a-b，其中a∣ϕ(n)a|\phi(n) 并且 a，b 很小
  2. n//e 算出 a，对 b 进行穷举。 已知 $ \phi (n) = (p-1)(q-1) $ 分解 n=pq 是容易的（中学数学），用 $n \pmod {p} = 0 $ 来判断当前分解是否正确即可。之后再做常规 RSA 解密就好了。
from Crypto.Util.number import *
from gmpy2 import *
n=21584562909016222405243274981318074723609424537864138818516166296882870952596923388616896100179452902343709246295468740335682613555154383977025156631083258377497353559709636001246215851357586251697339782140616762844466658464225538929007012548727508420837702781524936615164070353418037478517089569783507555024418411710631778073941565485748505472232785028182423960096719453903248061164351629862893495202801853287312265865916733075532360012981688805080299664971109817752216823608878051817158172160419426189481753020154076548471877219325637944601624370884640014467928928695819398270014246851395540617763179525187009648347
e=3083508987002317486463324997331153531944203505409162688359452328126124421799560484088128014311350414620529892327924105762240373365022054853860736661583322625356764794244233714463745121622512321671048540305802394692066665494889362704143858935532501202976814683074990945023438621916862496931012795683358222146303422749958603642494190335211644060403826011553655733835479351434022282429633638548092493767861402690047591624267078125799219896130381280612151738318061042109602694447606410766564110264194828211637692086652912524063147129310052531789754620749834783108524619617738417203269142329494376062347356009094704271801
c=4350922598266339224026193891975078418170168801819772034264767820713898265684630717877568988722980203827973605369872324389093738872638952249759042892387749292013137399168284781320083750172563798340746904451459359268152189983004829803065811628192447436195347501480101582498240174872791092809557067538800318476384792579696811714128502969704568997167132768453189707964546102168532460995624338582249438596921314744866700025932162716723912105789085167524526913197129852605391260182535842364550510703599942313178440055016324692710162447783500265413604087721982116926701740447032328198647967485123967003172122184982695286738
a=n//e
for b in range(20):
    phi=(e+b)*a
    p_plus_q=n-phi+1
    p_p=iroot(p_plus_q**2-4*n,2)[0]
    p=(p_plus_q+p_p)//2
    if(n%p==0):
        q=n//p
        phi=(p-1)*(q-1)
        print(long_to_bytes(pow(c,inverse(e,phi),n)))
# 中学数学
# 题目
p=getPrime(1024)
q=next_Prime(p+p>>500)
n=13776679754786305830793674359562910178503525293501875259698297791987196248336062506951151345232816992904634767521007443634017633687862289928715870204388479258679577315915061740028494078672493226329115247979108035669870651598111762906959057540508657823948600824548819666985698501483261504641066030188603032714383272686110228221709062681957025702835354151145335986966796484545336983392388743498515384930244837403932600464428196236533563039992819408281355416477094656741439388971695931526610641826910750926961557362454734732247864647404836037293509009829775634926600458845832805085222154851310850740227722601054242115507
c=6253975396639688013947622483271226838902346034187241970785550830715516801386404802832796746428068354515287579293520381463797045055114065533348514688044281004266071342722261719304097175009672596062130939189624163728328429608123325223000160428261082507446604698345173189268359115612698883860396660563679801383563588818099088505120717238037463747828729693649297904035253985982099474025883550074375828799938384533606092448272306356003096283602697757642323962299153853559914553690456801745940925602411053578841756504799815771173679267389055390097241148454899265156705442028845650177138185876173539754631720573266723359186
e=0x10001
本来想着解方程的，一直解不出来。。
那就换一个思路，之前遇到过费马分解，q-p 大概是 500 + 位算很小？
费马分解直接出了，之前存的代码有问题。。没输出。。。还以为跑不出
# exp
from tqdm import tqdm
from gmpy2 import *
n=13776679754786305830793674359562910178503525293501875259698297791987196248336062506951151345232816992904634767521007443634017633687862289928715870204388479258679577315915061740028494078672493226329115247979108035669870651598111762906959057540508657823948600824548819666985698501483261504641066030188603032714383272686110228221709062681957025702835354151145335986966796484545336983392388743498515384930244837403932600464428196236533563039992819408281355416477094656741439388971695931526610641826910750926961557362454734732247864647404836037293509009829775634926600458845832805085222154851310850740227722601054242115507
c=6253975396639688013947622483271226838902346034187241970785550830715516801386404802832796746428068354515287579293520381463797045055114065533348514688044281004266071342722261719304097175009672596062130939189624163728328429608123325223000160428261082507446604698345173189268359115612698883860396660563679801383563588818099088505120717238037463747828729693649297904035253985982099474025883550074375828799938384533606092448272306356003096283602697757642323962299153853559914553690456801745940925602411053578841756504799815771173679267389055390097241148454899265156705442028845650177138185876173539754631720573266723359186
e=0x10001
def fermat_factorization(n):
    factor_list = []
    get_context().precision = 2048
    x = int(sqrt(n))
    print(x)
    while True:
        x += 1
        y2 = x ** 2 - n
        if is_square(y2):
            print('x = ', x)
            y2 = mpz(y2)
            get_context().precision = 2048
            y = int(sqrt(y2))
            factor_list.append([x + y, x - y])
            print(factor_list)
        if len(factor_list) == 2:
            break
    return factor_list
print(fermat_factorization(n))
p=117374101720892014802773132009595684550070475491812959407700503409964134408139790074777009067182443277766119990724185784535299405313567262727445965171110284932237912222026220958706260216927350725324469350893507592837055161338352274913301924684983498346654165295930055956026431077232360603315231271970883987911
q=117374101720892014802773132009595684550070475491812959407700503409964134408139790074777009067182443277766119990724185784535299405313567262727445965171074427891089886767667348073044876487630536209840494632852807000951512126317010773423294553929289375585831391437922887752426888245829185481732564145862194694837
print(long_to_bytes(pow(c,inverse(e,(p-1)*(q-1)),N)))
# bd_key
# 题目
太长不想放了
提示后门 la 佬博客直接找到了
Dual EC DRBG
# exp
p=115792089210356248762697446949407573530086143415290314195533631308867097853951
b=0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
E=EllipticCurve(GF(p), [-3, b])
P =E(72696788778535848020209987825324097844942627382508830211685965810687985426258,49180397040468497821240854375656422791216946832858522054245540263375986110762)
d = 66604141534275704476445937214374130642068729921454877238730830814793201802544
Q = E(48439561293906451759052585252797914202762949526041747995844080717082404635286,36134250956749795798585127919587881956611106672985015071877198253568414405109)
r1 = 59100197418944667413449341413044666843726352095054393072750502893110293231642
def do_next(s):
    sP = s * P
    r = Integer(sP[0])
    s_new = Integer((r * P)[0])
    rQ = r * Q
    return Integer(rQ[0]), s_new
def do_guess(r1):
    try:
        rQ1 = E.lift_x(r1)
    except ValueError:
        return None
    sP2 = d * rQ1
    s2 = Integer(sP2[0])
    r2, s3 = do_next(s2)
    return r2, s3
r2,s3=do_guess(r1)
print(r2)
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
key=127452153710767463567686578700133367453
from Crypto.Util.number import *
key=long_to_bytes(key)
cipher = AES.new(key, AES.MODE_ECB)
ct = 25645992443585671366815910836517434170297823176311632150463962979581372384075859802765045877741181123347569267185176
ct=long_to_bytes(ct)
print(cipher.decrypt(ct))
# p or s（复现）
# 题目
from secret import keys
from Crypto.Util.number import *
assert (len(keys) == 6)
Pbox = [
    [0, 3, 6, 9, 10, 11, 13, 16, 18, 19, 20, 24, 25, 27, 28, 29, 30, 31],
    [0, 1, 3, 8, 9, 11, 12, 14, 16, 18, 19, 23, 24, 25, 26, 28, 29],
    [0, 1, 2, 3, 9, 10, 11, 13, 19, 20, 22, 25, 27, 28, 29, 31],
    [0, 2, 3, 5, 6, 7, 8, 13, 16, 19, 21, 25, 26, 27, 28],
    [2, 4, 6, 7, 9, 11, 12, 13, 16, 17, 20, 21, 22, 23, 24, 25, 27, 31],
    [2, 10, 13, 15, 16, 17, 21, 22, 23, 24, 29, 31],
    [1, 2, 8, 11, 12, 13, 16, 17, 19, 21, 22, 24, 25, 26, 27, 28, 30, 31],
    [0, 3, 6, 13, 14, 17, 19, 21, 22, 23, 26, 27, 28],
    [1, 5, 7, 8, 11, 12, 14, 15, 19, 23, 25, 27, 31],
    [0, 2, 3, 6, 7, 8, 9, 10, 11, 12, 16, 18, 19, 22, 23, 24, 25, 26, 27, 28],
    [0, 1, 6, 7, 10, 15, 16, 21, 24, 25, 29, 30],
    [1, 4, 5, 6, 7, 12, 13, 15, 18, 19, 20, 22, 26, 27, 29, 31],
    [0, 3, 5, 8, 9, 17, 21, 22, 24, 25, 26, 27, 30],
    [0, 2, 3, 4, 5, 6, 7, 8, 11, 17, 19, 20, 24, 25, 26, 27, 30],
    [2, 6, 7, 8, 11, 12, 14, 16, 20, 21, 22, 24, 29, 30, 31],
    [0, 2, 5, 6, 7, 8, 9, 10, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 29, 31],
    [0, 1, 2, 3, 4, 5, 8, 10, 11, 12, 13, 16, 17, 18, 20, 21, 22, 23, 25, 26, 28, 29, 30],
    [3, 5, 6, 8, 10, 13, 14, 17, 19, 20, 21, 22, 24, 26, 27, 29, 30],
    [1, 3, 6, 12, 14, 15, 16, 17, 18, 21, 24, 25, 26, 27, 28],
    [0, 1, 2, 3, 5, 6, 7, 8, 9, 12, 13, 19, 20, 23, 26, 29, 30],
    [3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 20, 21, 22, 25, 26, 27, 28, 29, 30],
    [0, 1, 2, 4, 6, 7, 9, 10, 11, 13, 15, 16, 18, 19, 20, 21, 25, 31],
    [0, 2, 7, 10, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 29, 31],
    [1, 2, 3, 5, 7, 8, 18, 19, 21, 22, 23, 25, 31],
    [3, 4, 7, 8, 10, 11, 13, 14, 17, 18, 19, 21, 22, 23, 24, 28, 29],
    [0, 2, 6, 7, 8, 10, 11, 12, 13, 16, 18, 19, 21, 23, 31],
    [0, 1, 3, 4, 8, 13, 14, 16, 18, 19, 21, 26, 27, 30, 31],
    [5, 6, 7, 9, 13, 14, 15, 18, 19, 20, 21, 24, 25, 28],
    [1, 3, 4, 5, 6, 7, 11, 14, 16, 17, 19, 20, 21, 22, 23, 25, 30, 31],
    [2, 3, 4, 6, 7, 11, 13, 17, 18, 19, 20, 23, 24, 25, 26, 28, 29, 30, 31],
    [0, 1, 2, 3, 4, 7, 9, 10, 13, 15, 16, 19, 22, 23, 24, 25, 27],
    [0, 1, 3, 4, 12, 16, 18, 19, 26, 30]]
def enc(v):
    t = v
    for i in keys:
        q = []
        for j in Pbox:
            q.append(sum([t[k] for k in j]) % 2)
        t = [int(q[j]) ^ int(i[j]) for j in range(32)]
    return t
assert (len(flag) == 32)
fb = bin(bytes_to_long(flag))[2:].zfill(32 * 8)
ciphertext = ""
for i in range(0, len(fb), 32):
    t = enc([int(j) for j in fb[i:i + 32]])
    ciphertext += "".join([str(j) for j in t])
print(ciphertext)
"""
0111110000100101000001101011110111101100000010110011101111000101111110111111100100100010001011000101000110110011111101000001001000000101111000001110001111001001100100111000011011101111111101001011100000100100110011111101100111001100111111110001111011101100
"""
已知 flag='flag {***}'
刚好前 32 位是固定的
想着把 key 跑出来，但好像不行
然后就没然后了
看了 La 佬博客（tql）
代码逻辑：将 flag 二进制 32*8 位 01 串分为 8 组，每一组都先经过 P 盒按位选择求和运算，再与未知的 32 位 key 进行按位异或运算，因为有 6 组 key，上述两步运算循环进行 6 次操作，得到最终 32 位密文。
将加密过程转为 GF (2) 下的矩阵运算，MiM_i 为 1x32 明文矩阵 (0≤i<8)，P 为 32x32 P 盒矩阵，KiK_i 为 1x32 key 矩阵 (0≤i<6)，TiT_i 为中间矩阵 (0≤i<6)，C 为密文矩阵，即：
T0=MiT_0=M_i
T1=T0∗P−1+K0T_1=T_0*P^{−1}+K_0
T2=T1∗P−1+K1T_2=T_1*P^{−1}+K_1
T3=T2∗P−1+K2T_3=T_2*P^{−1}+K_2
T4=T3∗P−1+K3T_4=T_3*P^{−1}+K_3
T5=T4∗P−1+K4T_5=T_4*P^{−1}+K_4
T6=T5∗P−1+K5T_6=T_5*P^{−1}+K_5
可得：
C=T6=Mi(P−1)6+K0(P−1)5+K1(P−1)4+K2(P−1)3+K3(P−1)2+K4P−1+K5C=T_6=M_i(P^{-1})^6+K_0(P^{-1})^5+K_1(P^{-1})^4+K_2(P^{-1})^3+K_3(P^{-1})^2+K_4P^{-1}+K_5
由于 KiK_i 和 P 都固定，
令 A=(P−1)6(P^{-1})^6,B=K0(P−1)5+K1(P−1)4+K2(P−1)3+K3(P−1)2+K4P−1+K5K_0(P^{-1})^5+K_1(P^{-1})^4+K_2(P^{-1})^3+K_3(P^{-1})^2+K_4P^{-1}+K_5
有 C=A∗Mi+BC=A*M_i+B，其中 A,B 都为固定值，A 可求，B 未知。
M0M_0，C0C_0 已知可以求出 B
# exp
# from gmpy2 import *
# n =  85413323752199019806030766630760449394238054889872415531186815348349883843039718091361611175963675771467536496812507338620957273406076058263122453235926619595761737396698699834116678598534261542535530241537247151318756003375573850725841254167462648747492270335084402716816450008370008491069875351593380154253
# dp =  1576424214336939000475035870826282526256046059505538052583882122452307602095912733650442447289122473348318614749578285418144935611098423641334952097553125
# c =  53653254613997095145108444611576166902006080900281661447007750088487109015427510365774527924664116641019490904245926171500894236952984157500461367769566121581870986304353174732328118576440353500038670030097108081972287049673200783198844842527470746431369314585103203118824985764754487936404004696485346196488
# e=65537
# for x in range(1, e):
#     if(e*dp%x==1):
#         p=(e*dp-1)//x+1
#         if(n%p!=0):
#             continue
#         q=n//p
#         phin=(p-1)*(q-1)
#         d=invert(e, phin)
#         m=powmod(c, d, n)
#         if(len(hex(m)[2:])%2==1):
#             continue
#
#         print("m:",m)
#         #print(hex(m)[2:])
#         print("flag:",bytes.fromhex(hex(m)[2:]))
# Sage
P = [
[0, 3, 6, 9, 10, 11, 13, 16, 18, 19, 20, 24, 25, 27, 28, 29, 30, 31],
[0, 1, 3, 8, 9, 11, 12, 14, 16, 18, 19, 23, 24, 25, 26, 28, 29],
[0, 1, 2, 3, 9, 10, 11, 13, 19, 20, 22, 25, 27, 28, 29, 31],
[0, 2, 3, 5, 6, 7, 8, 13, 16, 19, 21, 25, 26, 27, 28],
[2, 4, 6, 7, 9, 11, 12, 13, 16, 17, 20, 21, 22, 23, 24, 25, 27, 31],
[2, 10, 13, 15, 16, 17, 21, 22, 23, 24, 29, 31],
[1, 2, 8, 11, 12, 13, 16, 17, 19, 21, 22, 24, 25, 26, 27, 28, 30, 31],
[0, 3, 6, 13, 14, 17, 19, 21, 22, 23, 26, 27, 28],
[1, 5, 7, 8, 11, 12, 14, 15, 19, 23, 25, 27, 31],
[0, 2, 3, 6, 7, 8, 9, 10, 11, 12, 16, 18, 19, 22, 23, 24, 25, 26, 27, 28],
[0, 1, 6, 7, 10, 15, 16, 21, 24, 25, 29, 30],
[1, 4, 5, 6, 7, 12, 13, 15, 18, 19, 20, 22, 26, 27, 29, 31],
[0, 3, 5, 8, 9, 17, 21, 22, 24, 25, 26, 27, 30],
[0, 2, 3, 4, 5, 6, 7, 8, 11, 17, 19, 20, 24, 25, 26, 27, 30],
[2, 6, 7, 8, 11, 12, 14, 16, 20, 21, 22, 24, 29, 30, 31],
[0, 2, 5, 6, 7, 8, 9, 10, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 29, 31],
[0, 1, 2, 3, 4, 5, 8, 10, 11, 12, 13, 16, 17, 18, 20, 21, 22, 23, 25, 26, 28, 29, 30],
[3, 5, 6, 8, 10, 13, 14, 17, 19, 20, 21, 22, 24, 26, 27, 29, 30],
[1, 3, 6, 12, 14, 15, 16, 17, 18, 21, 24, 25, 26, 27, 28],
[0, 1, 2, 3, 5, 6, 7, 8, 9, 12, 13, 19, 20, 23, 26, 29, 30],
[3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 20, 21, 22, 25, 26, 27, 28, 29, 30],
[0, 1, 2, 4, 6, 7, 9, 10, 11, 13, 15, 16, 18, 19, 20, 21, 25, 31],
[0, 2, 7, 10, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 29, 31],
[1, 2, 3, 5, 7, 8, 18, 19, 21, 22, 23, 25, 31],
[3, 4, 7, 8, 10, 11, 13, 14, 17, 18, 19, 21, 22, 23, 24, 28, 29],
[0, 2, 6, 7, 8, 10, 11, 12, 13, 16, 18, 19, 21, 23, 31],
[0, 1, 3, 4, 8, 13, 14, 16, 18, 19, 21, 26, 27, 30, 31],
[5, 6, 7, 9, 13, 14, 15, 18, 19, 20, 21, 24, 25, 28],
[1, 3, 4, 5, 6, 7, 11, 14, 16, 17, 19, 20, 21, 22, 23, 25, 30, 31],
[2, 3, 4, 6, 7, 11, 13, 17, 18, 19, 20, 23, 24, 25, 26, 28, 29, 30, 31],
[0, 1, 2, 3, 4, 7, 9, 10, 13, 15, 16, 19, 22, 23, 24, 25, 27],
[0, 1, 3, 4, 12, 16, 18, 19, 26, 30]]
PP = zero_matrix(GF(2),32)
for k in range(32):
    PP[k] = [1 if x in P[k] else 0 for x in range(32)]
PPt = PP.transpose()
c = '0111110000100101000001101011110111101100000010110011101111000101111110111111100100100010001011000101000110110011111101000001001000000101111000001110001111001001100100111000011011101111111101001011100000100100110011111101100111001100111111110001111011101100'
C = zero_matrix(GF(2),8,32)
for k in range(0,len(c),32):
    C[k//32] = [1 if x == '1' else 0 for x in c[k:k+32]]
print(C)
M0= vector(GF(2),list(bin(int(b'flag'.hex(),16))[2:].zfill(4*8)))
flag = b'flag'
B = C[0] - (M0*(PPt^6))
A=PPt^(-6)
for k in range(1,8):
    l = list((C[k]-B)*A)
    flag += bytes.fromhex(hex(int(''.join([str(i) for i in l]),2))[2:])
    
print(flag)
# b'flag{P_has_no_Semantic_Security}'
不会用矩阵哇
# timing（复现）
# 题目
#!/usr/bin/python3 
from time import perf_counter_ns as clock1
from time import *
ecc_table = {
    'n': 'FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123',
    'p': 'FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF',
    'g': '32c4ae2c1f1981195f9904466a39c9948fe30bbff2660be1715a4589334c74c7'
         'bc3736a2f4f6779c59bdcee36b692153d0a9877cc62a474002df32e52139f0a0',
    'a': 'FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC',
    'b': '28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93',
    'O': '0000000000000000000000000000000000000000000000000000000000000000'
         '0000000000000000000000000000000000000000000000000000000000000000',
}
class TSM2(object):
    def __init__(self, sk):
        self.ecc_table = ecc_table
        self.n = int(ecc_table['n'], 16)
        self.para_len = len(ecc_table['n'])
        self.ecc_a3 = (int(ecc_table['a'], base=16) +
                       3) % int(ecc_table['p'], base=16)
        self.sk = sk
        self.pk = self.kg(self.sk, ecc_table['g'])
    def sign(self, data, K):
        e = data
        d = self.sk
        k = K
        P1 = self.kg(k, self.ecc_table['g'])
        x = int(P1[0:self.para_len], 16)
        R = ((e + x) % int(self.ecc_table['n'], base=16))
        if R == 0 or R + k == int(self.ecc_table['n'], base=16):
            return None
        d_1 = pow(
            d+1, int(self.ecc_table['n'], base=16) - 2, int(self.ecc_table['n'], base=16))
        S = (d_1*(k + R) - R) % int(self.ecc_table['n'], base=16)
        if S == 0:
            return None
        else:
            return '%064x%064x' % (R, S)
    def verify(self, Sign, data):
        r = int(Sign[0:self.para_len], 16)
        s = int(Sign[self.para_len:2 * self.para_len], 16)
        e = int(data.hex(), 16)
        t = (r + s) % self.n
        if t == 0:
            return 0
        P1 = self.kg(s, self.ecc_table['g'])
        P2 = self.kg(t, self.pk)
        if P1 == P2:
            P1 = '%s%s' % (P1, 1)
            P1 = self._double_point(P1)
        else:
            P1 = '%s%s' % (P1, 1)
            P1 = self._add_point(P1, P2)
            P1 = self._convert_jacb_to_nor(P1)
        x = int(P1[0:self.para_len], 16)
        return r == ((e + x) % self.n)
    
    def kg(self, k, Point):
        k=k%self.n
        if k == 0:
            return '0' * 128
        Point = '%s%s' % (Point, '1')
        mask_str = '8'
        for i in range(self.para_len - 1):
            mask_str += '0'
        mask = int(mask_str, 16)
        Temp = Point
        flag = False
        for n in range(self.para_len * 4):
            if flag:
                Temp = self._double_point(Temp)
            if (k & mask) != 0:
                if flag:
                    Temp = self._add_point(Temp, Point)
                else:
                    flag = True
                    Temp = Point
            k = k << 1
        return self._convert_jacb_to_nor(Temp)
    
    def _double_point(self, Point):
        t1=clock1()
        l = len(Point)
        len_2 = 2 * self.para_len
        if l < self.para_len * 2:
            return None
        else:
            x1 = int(Point[0:self.para_len], 16)
            y1 = int(Point[self.para_len:len_2], 16)
            if l == len_2:
                z1 = 1
            else:
                z1 = int(Point[len_2:], 16)
            T6 = (z1 * z1) % int(self.ecc_table['p'], base=16)
            T2 = (y1 * y1) % int(self.ecc_table['p'], base=16)
            T3 = (x1 + T6) % int(self.ecc_table['p'], base=16)
            T4 = (x1 - T6) % int(self.ecc_table['p'], base=16)
            T1 = (T3 * T4) % int(self.ecc_table['p'], base=16)
            T3 = (y1 * z1) % int(self.ecc_table['p'], base=16)
            T4 = (T2 * 8) % int(self.ecc_table['p'], base=16)
            T5 = (x1 * T4) % int(self.ecc_table['p'], base=16)
            T1 = (T1 * 3) % int(self.ecc_table['p'], base=16)
            T6 = (T6 * T6) % int(self.ecc_table['p'], base=16)
            T6 = (self.ecc_a3 * T6) % int(self.ecc_table['p'], base=16)
            T1 = (T1 + T6) % int(self.ecc_table['p'], base=16)
            z3 = (T3 + T3) % int(self.ecc_table['p'], base=16)
            T3 = (T1 * T1) % int(self.ecc_table['p'], base=16)
            T2 = (T2 * T4) % int(self.ecc_table['p'], base=16)
            x3 = (T3 - T5) % int(self.ecc_table['p'], base=16)
            if (T5 % 2) == 1:
                T4 = (T5 + ((T5 + int(self.ecc_table['p'], base=16)) >> 1) - T3) % int(
                    self.ecc_table['p'], base=16)
            else:
                T4 = (T5 + (T5 >> 1) - T3) % int(self.ecc_table['p'], base=16)
            T1 = (T1 * T4) % int(self.ecc_table['p'], base=16)
            y3 = (T1 - T2) % int(self.ecc_table['p'], base=16)
            form = '%%0%dx' % self.para_len
            form = form * 3
            t2=clock1()
            if(t2-t1<1e7):
                sleep(0.01-(((t2-t1))/1000000000.0))
            return form % (x3, y3, z3)
        
    def _add_point(self, P1, P2):
        t1=clock1()
        if P1 == '0' * 128:
            return '%s%s' % (P2, '1')
        if P2 == '0' * 128:
            return '%s%s' % (P1, '1')
        len_2 = 2 * self.para_len
        l1 = len(P1)
        l2 = len(P2)
        if (l1 < len_2) or (l2 < len_2):
            return None
        else:
            X1 = int(P1[0:self.para_len], 16)
            Y1 = int(P1[self.para_len:len_2], 16)
            if l1 == len_2:
                Z1 = 1
            else:
                Z1 = int(P1[len_2:], 16)
            x2 = int(P2[0:self.para_len], 16)
            y2 = int(P2[self.para_len:len_2], 16)
            T1 = (Z1 * Z1) % int(self.ecc_table['p'], base=16)
            T2 = (y2 * Z1) % int(self.ecc_table['p'], base=16)
            T3 = (x2 * T1) % int(self.ecc_table['p'], base=16)
            T1 = (T1 * T2) % int(self.ecc_table['p'], base=16)
            T2 = (T3 - X1) % int(self.ecc_table['p'], base=16)
            T3 = (T3 + X1) % int(self.ecc_table['p'], base=16)
            T4 = (T2 * T2) % int(self.ecc_table['p'], base=16)
            T1 = (T1 - Y1) % int(self.ecc_table['p'], base=16)
            Z3 = (Z1 * T2) % int(self.ecc_table['p'], base=16)
            T2 = (T2 * T4) % int(self.ecc_table['p'], base=16)
            T3 = (T3 * T4) % int(self.ecc_table['p'], base=16)
            T5 = (T1 * T1) % int(self.ecc_table['p'], base=16)
            T4 = (X1 * T4) % int(self.ecc_table['p'], base=16)
            X3 = (T5 - T3) % int(self.ecc_table['p'], base=16)
            T2 = (Y1 * T2) % int(self.ecc_table['p'], base=16)
            T3 = (T4 - X3) % int(self.ecc_table['p'], base=16)
            T1 = (T1 * T3) % int(self.ecc_table['p'], base=16)
            Y3 = (T1 - T2) % int(self.ecc_table['p'], base=16)
            form = '%%0%dx' % self.para_len
            form = form * 3
            t2=clock1()
            if(t2-t1<1e8):
                sleep(0.1-(((t2-t1))/1000000000.0))
            return form % (X3, Y3, Z3)
    
    def _convert_jacb_to_nor(self, Point):
        len_2 = 2 * self.para_len
        x = int(Point[0:self.para_len], 16)
        y = int(Point[self.para_len:len_2], 16)
        z = int(Point[len_2:], 16)
        z_inv = pow(
            z, int(self.ecc_table['p'], base=16) - 2, int(self.ecc_table['p'], base=16))
        z_invSquar = (z_inv * z_inv) % int(self.ecc_table['p'], base=16)
        z_invQube = (z_invSquar * z_inv) % int(self.ecc_table['p'], base=16)
        x_new = (x * z_invSquar) % int(self.ecc_table['p'], base=16)
        y_new = (y * z_invQube) % int(self.ecc_table['p'], base=16)
        z_new = (z * z_inv) % int(self.ecc_table['p'], base=16)
        if z_new == 1:
            form = '%%0%dx' % self.para_len
            form = form * 2
            return form % (x_new, y_new)
        else:
            return None
    def add_point(self,P1,P2):
        if P1==P2:
            return self._double_point(P1)
        else :
            return self._convert_jacb_to_nor(self._add_point(P1,P2))
import sys,os
from random import *
import socketserver
import signal
import string
class Task(socketserver.BaseRequestHandler):
    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()
    def send(self, msg, newline=True):
        msg=msg.encode()
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass
    def recv(self, prompt=b'[-] '):
        self.send(prompt, newline=False)
        return self._recvall()
    def handle(self):
        signal.alarm(3600)
        g=ecc_table["g"]
        O=ecc_table["O"]
        t=[randint(1,254) for i in range(8)]
        sk=sum([1<<i for i in t])
        
        self.send("system reseting...")
        sm2 = TSM2(sk)
        self.send("done")
        self.send("the system is "+str(sm2.pk))
        
        for i in range(100):
            try:
                user=int(self.recv("plz give me your number:"))
            except:
                self.send("wrong, plz try again")
                continue
            t1=clock1()
            kG=sm2.kg(sk-user,g)
            t2=clock1()
            self.send("used "+str((t2-t1)/1e9)+" s")
            if kG==O:
                f=open("/flag")
                flag=f.read()
                self.send(flag)
                exit()
            
class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass
class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass
if __name__ == "__main__":
    HOST, PORT = '0.0.0.0',8000
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    print(HOST, PORT)
    server.serve_forever()
没怎么看懂，，，完全没思路
出题师傅说是侧信道 ，，没怎么做过这类题目
我们要输入 u 使(sk−u)G=O(sk-u)G=O 可以拿到 flag
可以输入 100 次
要满足(sk−u)G=O(sk-u)G=O，只有sk−u=0sk-u=0 或者sk−u=nsk-u=n
而我们知道的只有 pk 和运算时的时间
只能猜测sk−u=0sk-u=0
t=[randint(1,254) for i in range(8)]
sk=sum([1<<i for i in t])
sk 只有 8 位是 1
利用运算总时间，可作为侧信道信息来测试 sk 各位为 1 时的消耗时间，测试发现当接近正确的 “1” 位时，运算总时间相较相邻的两位小，那么可使用时间侧信道攻击来求解私钥 sk。
因尝试的总次数最多为 100 次，采用区间遍历法缩小尝试次数，令 x 为每个区间长度，总次数 c=254x+8x<=100c=\frac{254}{x}+8x<=100，x 可取值 4~8。
采用 x=4 实现：
# exp
from pwn import *
from tqdm import tqdm
r = remote('nep.lemonprefect.cn', 21270)
r.recvuntil(b'is ')
pk = r.recvline().strip()
print(pk)
nowt = 100000.0
start = []
startt = []
def send(x):
    r.recvuntil(b'number:')
    r.sendline(str(x).encode())
    r.recvuntil(b'used ')
    time = float(r.recvuntil(b' s').decode()[:-2])
    r.recvline()
    return time
for i in tqdm(range(1, 255, 4)):
    t = send(1 << i)
    #print(i, t)
    if t > nowt:
        start.append(i - 4)
        #print(start)
    nowt = t
print(start)
ans = []
for k in tqdm(start):
    nowt = send(1 << k)
    for j in range(4):
        t = send(1 << (k + 1 + j))
        if t > nowt and k + 1 + j - 1 <= 254:
            ans.append(k + 1 + j - 1)
            #print(ans)
        nowt = t
print(ans)
sk = sum([1 << i for i in ans])
print(sk)
send(sk)
print(r.recvall())
#NepCTF{856faad5-7b60-42cd-ade2-0a738d3fe478}
 更新于   阅读次数  次