随缘刷题(一)

​ 学如逆水行舟，不进则退。开一个刷题专栏，持之以恒地练习。PS：难度大约是中等。

hgame2023 week4

ECRSA

p=115192265954802311941399019598810724669437369433680905425676691661793518967453
q=109900879774346908739236130854229171067533592200824652124389936543716603840487
n = 12659731371633323406361071735480743870942884407511647144758055911931321534333057725377899993936046070028289182446615763391740446071787318153462098556669611
a = 34573016245861396068378040882622992245754693028152290874131112955018884485688
b = 103282137133820948206682036569671566996381438254897510344289164039717355513886
e = 11415307674045871669

from Crypto.Util.number import *
ciphertext = b'f\xb1\xae\x08`\xe8\xeb\x14\x8a\x87\xd6\x18\x82\xaf1q\xe4\x84\xf0\x87\xde\xedF\x99\xe0\xf7\xdcH\x9ai\x04[\x8b\xbbHR\xd6\xa0\xa2B\x0e\xd4\xdbr\xcc\xad\x1e\xa6\xba\xad\xe9L\xde\x94\xa4\xffKP\xcc\x00\x907\xf3\xea'
c = Integer(bytes_to_long(ciphertext))

Ep = EllipticCurve(Zmod(p), [a, b])
Eq = EllipticCurve(Zmod(q), [a, b])
py = Ep.lift_x(c)
qy = Eq.lift_x(c)

cc = crt([ZZ(py[1]),ZZ(qy[1])],[p,q])
ct = (c,cc)
E = EllipticCurve(Zmod(n), [a, b])
C = E(ct)

ordp = Ep.order()
ordq = Eq.order()
phi = ordp*ordq
print(phi)
d = inverse_mod(e,phi)

m = (C*d)[0]
print(long_to_bytes(int(m)))

LLLCG

相较于普通的lcg，其增量为随机值，即$seed\cdot a + (random\;mod\;n)$，注意是先模再加，所以增量可以看作一个小的噪音，问题转化为LWE。格子造两行就行了：

$$\left[ \begin{matrix} s_1 & s_3 &\cdots &s_{n-1} \\ s_2 & s_4 &\cdots &s_n\\ \end{matrix} \right]$$

这样的话规约时的系数分别为a和1，a即是flag。

n = next_prime(2**360)
c = 
c1 = [c[i] for i in range(0,len(c),2)]
c2 = [c[j] for j in range(1,len(c),2)]
print(len(c))
A = [c1,c2]
M = matrix(ZZ,A)
L = M.LLL()[0]
print(L)
X = M.solve_left(L)
print(X)

LLLCG-Revenge

在LLLCG的基础上改的，增加了括号，即$(seed\cdot a + random)\;mod\;n$，这样整个问题不再是一个LWE，已知信息为$as_1+e_1=k_1n+s_2,as_2+e_2=k_2n+s_3\cdots$，可以构造如下的格：

$$\left[ \begin{matrix} n & 0 & \cdots & 0 &0&0\\ 0 & n & \cdots & 0 &0&0\\ \vdots & \vdots & \ddots & \vdots &\vdots&\vdots\\ 0 &0 &0 &n &0 &0 \\ s_1 & s_2 & \cdots & s_{n-1} & \small1 &0 \\ s_2 &s_3 &\cdots &s_n &0 &\small2^{340} \end{matrix} \right]$$

那么$(e1,e_2\cdots e{n-1},a,2^{340})$是该格上的短向量，a (flag)就可以规约得到。刚开始我没意识到这是个HNP，造的格少了两列，结果规约失败，与tsuppari师傅交流后发现加上两列构成方阵就很容易出了，感谢师傅。

n = next_prime(2^360)
s = 
num = len(s)
mat = [[0 for _ in range(num + 1)] for _ in range(num + 1)]
for i in range(len(s) - 1):
    mat[i][i] = n
    mat[-2][i] = s[i]
    mat[-1][i] = s[i + 1]
mat[-2][-2] = 1
mat[-1][-1] = 2 ^ 340
mat = matrix(ZZ,mat)
solv = mat.LLL()[0]
print(solv)
flag = solv[-2]
from Crypto.Util.number import *
print(long_to_bytes(int(flag)))

长城杯2022

xor

利用异或的性质恢复即可。

start = 'flag{'
res = [[150, 194, 49, 195, 23, 79, 66], [194, 136, 63, 147, 3, 2, 81], [132, 221, 57, 144, 83, 83, 93], [208, 223, 37, 193, 28, 0, 70], [154, 203, 108, 156, 28, 78, 68], [159, 221, 62, 146, 86, 82, 88], [197, 141, 117, 192, 31, 90, 85]]
start_c = res[0]
pad0 = start_c[0] ^ ord(start[0]) ^ ord(start[1]) ^ ord(start[2])
pad1 = start_c[5] ^ ord(start[2]) ^ ord(start[4]) ^ pad0
pad4 = start_c[6] ^ ord(start[0]) ^ ord(start[2]) ^ ord(start[4])
pad2 = start_c[1] ^ ord(start[3]) ^ ord(start[4]) ^ pad1
pad3 = start_c[3] ^ ord(start[3]) ^ pad1 ^ pad4
i5 = start_c[4] ^  ord(start[4]) ^ pad0 ^ pad1
print(chr(i5))
pad5 = start_c[2] ^ i5 ^ pad1 ^ pad3
pad = [pad0,pad1,pad2,pad3,pad4,pad5]


def check(out):
    i = b'flag{9'
    tmp = []
    tmp.append(i[0] ^ i[1] ^ i[2] ^ pad[0])
    tmp.append(i[3] ^ i[4] ^ pad[1] ^ pad[2])
    tmp.append(pad[5] ^ i[5] ^ pad[1] ^ pad[3])
    tmp.append(i[3] ^ pad[3] ^ pad[4] ^ pad[1])
    tmp.append(i[5] ^ pad[0] ^ i[4] ^ pad[1])
    tmp.append(i[2] ^ i[4] ^ pad[0] ^ pad[1])
    tmp.append(i[2] ^ i[0] ^ i[4] ^ pad[4])
    if out == tmp:
        print('验证通过')

def decrypt(c):
    i3 = c[3] ^ pad1 ^ pad3 ^ pad4
    i4 = c[1] ^ i3 ^ pad1 ^ pad2
    i2 = c[5] ^ i4  ^ pad0 ^ pad1
    i0 = c[6] ^ i2 ^ i4 ^ pad4
    i1 = c[0] ^ i0 ^ i2 ^ pad0
    i5 = c[2] ^ pad1 ^ pad3 ^ pad5
    return chr(i0) + chr(i1) + chr(i2) + chr(i3) + chr(i4) + chr(i5)

if __name__ == '__main__':

    check(res[0])
    flag = ''
    for i in res:
        flag = flag + decrypt(i)
    print(flag)

known_phi

已知phi和e，分解n是容易的，后边就是DSA的共用k攻击。

from Crypto.Util.number import *
import random
import gmpy2
from hashlib import sha256

n = 104228256293611313959676852310116852553951496121352860038971098657350022997841589403091722735802150153734050783858816709247647536393314564077002364012463220999962114186339228164032217361145009468516448617173972835797623658266515762201804936729547278758839604969469770650218191574897316410254695420895895051693
phi = 104228256293611313959676852310116852553951496121352860038971098657350022997837434645707418205268240995284026522165519145773852565112344453740579163420312890001524537570675468046604347184376661743552799809753709321949095844960227307733389258381950812717245522599433727311919405966404418872873961877021696812800
q = 24513014442114004234202354110477737650785387286781126308169912007819
s1 = 764450933738974696530033347966845551587903750431946039815672438603
r1 = 8881880595434882344509893789458546908449907797285477983407324325035
r2 = 8881880595434882344509893789458546908449907797285477983407324325035
s2 = 22099482232399385060035569388467035727015978742301259782677969649659
e = 65537
d = inverse(e,phi)

def getpq(n):
    while True:
        k = phi
        g = random.randint(0, n)
        while k%2==0:
            k=k//2
            temp=gmpy2.powmod(g,k,n)-1
            if gmpy2.gcd(temp,n)>1 and temp!=0:
                return gmpy2.gcd(temp,n)

# tmp = getpq(n)
# print(tmp)
factors = [92128261871628241975522014503893089775204276818952562864868068434189077323911,114034877389817517986186253205403596431234414440955842208884285396147740113161,87835491118288540715995802690214012778910595141140880257454164067662889225787,]
factors.append(n//(factors[0]*factors[1]*factors[2]))
factors.sort()

m1 = long_to_bytes(factors[0] + factors[3])
m2 = long_to_bytes(factors[1] + factors[2])
hm1 = bytes_to_long(sha256(m1).digest())
hm2 = bytes_to_long(sha256(m2).digest())

k = (hm1 - hm2) * inverse(s1-s2,q) % q
x = inverse(r1,q)*(s1 * k - hm1) % q
print(long_to_bytes(x))

baby_rsa(2021)

enc1只给了c和e，没给n但给了不少p q的限制条件，p 的比特位数仅1000多，因此v1和m1应该都不大，那么进行遍历即可，当满足条件的时候进行解密，用flag头判断解密是否成功。

from Crypto.Util.number import long_to_bytes
from gmpy2 import invert, is_prime
from tqdm import tqdm

c1 = 15808773921165746378224649554032774095198531782455904169552223303513940968292896814159288417499220739875833754573943607047855256739976161598599903932981169979509871591999964856806929597805904134099901826858367778386342376768508031554802249075072366710038889306268806744179086648684738023073458982906066972340414398928411147970593935244077925448732772473619783079328351522269170879807064111318871074291073581343039389561175391039766936376267875184581643335916049461784753341115227515163545709454746272514827000601853735356551495685229995637483506735448900656885365353434308639412035003119516693303377081576975540948311
c2, n, fac = (40625981017250262945230548450738951725566520252163410124565622126754739693681271649127104109038164852787767296403697462475459670540845822150397639923013223102912674748402427501588018866490878394678482061561521253365550029075565507988232729032055298992792712574569704846075514624824654127691743944112075703814043622599530496100713378696761879982542679917631570451072107893348792817321652593471794974227183476732980623835483991067080345184978482191342430627490398516912714451984152960348899589532751919272583098764118161056078536781341750142553197082925070730178092561314400518151019955104989790911460357848366016263083, 43001726046955078981344016981790445980199072066019323382068244142888931539602812318023095256474939697257802646150348546779647545152288158607555239302887689137645748628421247685225463346118081238718049701320726295435376733215681415774255258419418661466010403928591242961434178730846537471236142683517399109466429776377360118355173431016107543977241358064093102741819626163467139833352454094472229349598479358367203452452606833796483111892076343745958394932132199442718048720633556310467019222434693785423996656306612262714609076119634814783438111843773649519101169326072793596027594057988365133037041133566146897868269, 39796272592331896400626784951713239526857273168732133046667572399622660330587881579319314094557011554851873068389016629085963086136116425352535902598378739)

P = []
for v1 in tqdm(range(400)):
    for m1 in range(400):
        p = pow(v1, (m1+1))-pow((v1+1), m1)
        if int(p).bit_length() > 2048:
            break
        if is_prime(p):
            P.append(p)

for p in P:
    for q in P:
        n1 = p*q
        if int(n1).bit_length() == 2048:
            try:
                d = invert(0x10001, (p-1)*(q-1))
                dec = long_to_bytes(pow(c1, d, n1))
                if b'flag' in dec:
                    print(dec)
                    break
            except ValueError:
                pass

# flag{8102c552-3d78-4a

第二部分更简单，因为flag是uuid格式，所以flag2小于512比特，用fac[0]+fac[1]+fac[2]) << 1) - 1解密即可。

RSA

只要注意给了$d_1-d_2$的值就很容易构造出kphi，那么求d解密即可。

from Crypto.Util.number import *

N = 0x62c048bc886075bffb9ad01255786dd8ef2480ba510f13689c1e84ffaaf21dfb5695a4d83f4ba22093bdd75bfc8f5979185d29724ecccf045e1857b1b2a4757dd82dc44318c054c9fce9bc451e6beecb97bbda6562420fc8c295521c5455443413f90403cf1af6271fb6d2d54378b86ced18ae6844a877890ea853a215880a09c68c517a75c1183c067b706ce630f3f0913591f7354cfa60c8f6b7ab2f15e466a1ea6e8034417a5fc3c11b8ba746596c22c734b09257e9a6fb18358738d416eda0ba0e7b028dd2d550b1e018b180916ac25f47910657a5db2410946c0593b7e23ed1659a811083f363ad4eb65642091a040befbd643089bbee376634d2394d11
e1 = 0x124241a12ea2be53f9b9b1fd92e10d089cfa32aa07e6c2cace848aaa6c73ff06d4c6c92b7d1f29160b2eef95a5f580915d3f15c0ea23975cbadfe8347a10daab2bd0827d7e909b329ec53c5eb306f0a5125b3817e7ea0c15b2317a46c36c4f34fc626dadc6c769bcc7be18ddf7954fae8dde3fd4ce3c5146c019bdb0d9552af1dc9ef7186e06b1d59e763fb05c7cd21fbb3f509fee52d4e24921ebfa76bb8302ea6760e92606e440907cc1c110946af53900904e84dbc309fcef15ea060c667070e5e0310891606df151609ff609bcc6125c6043c35119b25df78b4d5ca61ab6492753cc5e5b32e044fce0aeb0442464f36298add254e9fb6505fa4cddae1cf7
e2 = 0x17b3937cec3ca5fdddad8db29c6dc4efae1408bf5b4aa2ff602112c50f302e9698c79c7ab79fef0210c621dcc218d91d358b7f93a978c4e3f2b982794697c4797cef89189d1464ed1c767bf72433092922352885f8e355952c558ad2c9ade58a19375ddc5dcf3f9fa28c68a5cff158734d94224b85f77bd939133f39ab7884ece61d9fb3496373008827c2ae694dfe7da08eee348ef99c3a6737a4b088b62978cf209ef3d1140a30d42872615b94378108266e3d344caf51b497a585a4b5ef8619cc46959bad9b89f59f36175fbf9b64363443f3f7743896c72a198decedf89c518fa07b1d401d0359578a4926b7d67de86232ee24751f17dafbc749c0783b33
e3 = 0x5647c4490bda9e7e497651551600572c5ef4e2d889b9b1ba0e9a493660497e10877e975c01da9aebae5e3ba9aad976a1a783b39191e8fd799689dfa26b069264d60543602d514ac412ac75d827d67c78ad544bda633f0fa69fb5bbc37e0f6b95714576ff53bae3f7f991d143a4b1e841730d5d580d4effeb8fb02e8b3c3c9a1f1899d2eb411ce37f16d30cfa1f7af7322be4f42f5d012f484a1181fa4aa0b5f420a472030a5c08c80bff76ab82ef5768bfd495abcdc5f22aae1891561322dfb28ff63c4e467411c8b73c11d64b05f411e2a1de0c7754c6a62d1f72cded9e2592ccc21be3fce4ea6f083a617a246fd3fe464ef2487adbfabfb628c882ea991675
c = 0x45f2ee650d622d1e0f0e2e2e861001e9866c541f9f1dd2ec1dec18194f8b7224914916ecd68bbc74b28a000d2664e671586aed63b54c0928a939caf28d39eeba03c0ce3afcf2cdc5805e8e2792d76e88545aa4dee11078ba1e2e5b56ee23d58e443d7aff180d4e7463ae66ea8e96e0c8d4e1443e7664b99599af14e591e28cf2f833bd30b44b89c396b5fc1ee81ea3f7bc08dab426b1871eb66829c81d57e2ebf5c7a3e9c593ce496f0b0c4237906b019ae75ca551d6b0b1adfe64958c2ead6c39e517eb75eaf4b4d72402bea40f043cf0a80317aa2f1a996c727e195e15f903c0cac618f668af1015ee479d1c7b1c1b370fd4a5a76f5bf295e6bd7d0f4ae56f
l0 = 0x3dbabf6ea5b801221c283bd234f04264d292c8f3048c8b59c21e003cda983a3a41e4392c6ea77a706631de60d261f2b367027e037d37fda5a13a8e01b2c6c0f48a3112315cffe7420a50a3ebada09aba61f8e6da793654a467b9f780c20c5085012e064ab9205c076073b4fb4895e01d0d568fd5c30159879180093855d39d5548a1389a94f57c680c

kphi = e1 - e2 + l0 * e1 * e2
d3 = inverse(e3,kphi)
print(long_to_bytes(pow(c,d3,N)))

VNCTF2021

whitegive

前一部分可以通过数论推导得到两个关于p的式子，求公因子分解以后解出e，发现e很大，于是尝试boneh_durfee求解即可。

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

n = 1246903000089073759886267722667196003041462505274526737638837808213476294697746018085346623497511017543801377442390781101585650581984057653018703031659844145960721073451379508212905335383758157379301019575213158532070229897587088955814288202279949391608732448294591675986989254272257059551622461096394217684402667140362275595245430242117193793913872208576714597860532581116390903216389172132085635891741189355461016795362341416848534340615825023292174042406128959
c = 952508462840095293368043281511747192551431448088755251878915582522463097721381421883702408853564036431155676272901680250701398946525803160765527940151587567521509500006089852079864042238196362897144754722623523621230744820970423076092319608853809407595863195726851921082224085255808985329769890887863865121647796115540376158135632760785321953364738008064130705467326745546629505023549047992509562623348749056757848144371814157305011884825502144329268299851210747
h = 788785744509676701442642497798353940704045062680685297430840370664093043099033424646382070232242765761123110381200239132310785932203252095093993313010883982078216697297202940152563278231011836966627537170460186597134847633828107444548759805274516431300662852153808962421740187067058018192457264083227110866080267684557127718769967184710395811547902947248700889674967381917907905535103547918375731341071557144999864774198881339085314424766509424492349867615604684
e = 65537

p = gcd(pow(e,e) * h - 1,n)
q = n//p//p
phi = (p-1) * (q-1) * p
d = invert(e,phi)
e0 = pow(c,d,n)
print(e0.bit_length())
print(e0)

n0 =  97814568264814384858194701955408461509880555772006698372422205341758322175891474378211599333051180365254844248340812534463000531890490435018379585036704801177155418066770861143206836558793774360498040810255823235715535487716966004194143204900564413879660115112965484824906920141847149888933004740523449213441
c0 = 86143311788363675684674113699193046781796638913243016152555572150858159500527674063754694514501999791875561142925154991000532628799185608465062814546108160434468098898040769021072007374156546314975240583347468026001633652940408779155579339470960571067652924814623371177901052302005289155305089588204204313261
d0 = 103079922798932082066165266087442072203677117380612800709240732626110126828541
print(long_to_bytes(pow(c0,d0,n0)))

factor

考查的是[Lattice Based Attack on Common Private Exponent RSA]，但给的是$e_id\equiv1\;mod\;(p+1)(q+1)$，参考论文可知这题$\phi(N_i)=N_i - s_i=N_i-(-p_i-q_i-1)$，所以有$e_id-1=k_i(N_i-s_i)$，变形一下就是$e_id-k_iN_i=1-k_is_i$，利用这个关系就能规约，规约的结果为向量$(dM,1-k_1s_1,…,1-k_is_i)$，由于$1-k_is_i$的比特大约是$k_ip$，所以我们在构造格的时候才需要取$M=N_r^{1/2}$。本题求出的d并不能用于解密，因为$e_id\equiv1\;mod\;(p+1)(q+1)$，需要取规约的系数得到$k_i$，利用$k_i$求出p+q分解n，最后利用正确的phi来求私钥d。

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

(n2,e2),(n1,e1) = [(115483338707853323510117244601663937653032657454816581880428779391136584508645415322441921678179684904267659942318581245589538093236558206867210468172871004098796706517288570963560499418427771831765342801956281881820593084352360716457591198748797415842971188690055630073433785996545367137242661591939632740177, 57942961120648999071495995119939754708884253716257622598699627649519120883383654560602196191747110519111036450217116739928381611061803307053632035548944075112790103258912149703053932492832060534126356062378027983000713091223894604748395826345780826674822582205573649323340945351657354960324397873669889767611), (53622548101803784449246949981043962044702821559359430270342163843702543781580388956841660273746825211912789196955019345268896290156568895362182295889379787233440464948232717888315385094207004043907898658611926470834448875571292174245716821120409044389816082878077188546182422805778560826667364235348059795229, 37629174280947918845570975617525141920002123382327456934545962737176558640617579710289304146119507880547361939594011152968663070025066085778798378563965349218834887746411017240322083056673687330052590220772859205859051875687741541958997904176801239206348298021023694604932588913541173039972303193792987583003)]
c2,c1 = (51861394323132582263685584977796608641129485967610029542263453128833142621927008505594685713111162217651119546991411861320042282788909858323941435593508384080858965324662410947546608051702238057613339996124961723578887443100478753831786550701578678090466528863014222331341645240511640398819027209200809466160, 53200507591144017820710284362261363695745231005527161900426580605551005076410241969689161754211964469126847594337121140420040532547631617290907291418063708630323838133357597795892690304405706577096504918510233628396424543417886828387510407109281423448827267022542075484645277275676556239547911837897827866040)

assert n1 < n2
M=iroot(int(n2),int(2))[0]
a=[0]*3
a[0]=[M,e1,e2]
a[1]=[0,-n1,0]
a[2]=[0,0,-n2]

Mat = matrix(ZZ,a)
Mat_LLL=Mat.LLL()[0]
t1 = Mat_LLL[1]
# 求系数k1，k2
v = Mat.solve_left(Mat_LLL)
k1 = v[1]
s1 = (1 - t1)//k1
p1plusq1 = -s1 - 1
print(p1plusq1)

p, q = var('p, q')
solve([p + q == p1plusq1,p * q == n1], p, q)
p = 7606901304062429604110489427249254587884248344627948326915848665305366245856616424368965543016839050022061751753055060333176198894726784386359964040610943
q = 7049197295772316208399586675406918999457038516909904725192476462818207744618559093720204540536950043797933449511950112596210193686547390820360414974856803
phi = (p-1)*(q-1)
d = inverse_mod(e1,phi)
print(long_to_bytes(ZZ(pow(c1,d,n1))))

湖湘杯2021

signin

考查的是维纳攻击的变式，即利用维纳攻击的思想(连分数)去求解参数。本题根据gen的算法可知p1和p2的比特差距并不是很大，那么近似有$q_1/q_2=n_1/n_2$，而$n_1$和$n_2$是已知的，可以考虑展开$n_1/n_2$的连分数来求解q1和q2。exp：

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

n1,n2 = pk = (1150398070565459492080597718626032792435556703413923483458704675295997646493249759818468321328556510074044954676615760446708253531839417036997811506222349194302791943489195718713797322878586379546657275419261647635859989280700191441312691274285176619391539387875252135478424580680264554294179123254566796890998243909286508189826458854346825493157697201495100628216832191035903848391447704849808577310612723700318670466035077202673373956324725108350230357879374234418393233, 1242678737076048096780023147702514112272319497423818488193557934695583793070332178723043194823444815153743889740338870676093799728875725651036060313223096288606947708155579060628807516053981975820338028456770109640111153719903207363617099371353910243497871090334898522942934052035102902892149792570965804205461900841595290667647854346905445201396273291648968142608158533514391348407631818144116768794595226974831093526512117505486679153727123796834305088741279455621586989)
c1, c2 = (361624030197288323178211941746074961985876772079713896964822566468795093475887773853629454653096485450671233584616088768705417987527877166166213574572987732852155320225332020636386698169212072312758052524652761304795529199864805108000796457423822443871436659548626629448170698048984709740274043050729249408577243328282313593461300703078854044587993248807613713896590402657788194264718603549894361488507629356532718775278399264279359256975688280723740017979438505001819438, 33322989148902718763644384246610630825314206644879155585369541624158380990667828419255828083639294898100922608833810585530801931417726134558845725168047585271855248605561256531342703212030641555260907310067120102069499927711242804407691706542428236208695153618955781372741765233319988193384708525251620506966304554054884590718068210659709406626033891748214407992041364462525367373648910810036622684929049996166651416565651803952838857960054689875755131784246099270581394)
c = continued_fraction(n1/n2)
alist=c.convergents()
for i in alist[1:]:
    if gcd(i.numerator(),n1) > 1:
        q1 = i.numerator()
        q2 = i.denominator()
        print(q1)
        print(q2)
        break
e = 65537
p1 = iroot(int(n1/q1),4)[0]
p2 = iroot(int(n2/q2),4)[0]
phi1 = p1^3 * (p1-1) * (q1-1)
phi2 = p2^3 * (p2-1) * (q2-1)
d1 = inverse_mod(65537,phi1)
d2 = inverse_mod(65537,phi2)
print(long_to_bytes(ZZ(pow(c1,d1,n1))) + long_to_bytes(ZZ(pow(c2,d2,n2))))

CISCN2022 东北赛区

gcrd2

gcrd是矩阵分析的内容，参考链接，根据定义，这里的矩阵T是aT和bT的一个最大右公因子，因此可以用gcrd的构造定理求解，即将aT和bT堆叠，进行初等行变换，最后划归的非零部分就是两个多项式矩阵的最大右公因子，在matlab里 用rref()函数即可化简，拿到T之后求一下res就能计算flag了。

import numpy as np
from hashlib import md5

np.set_printoptions(threshold=np.inf)
f = open('out','r')
bT = []
aT = []
for i in range(32):
    line = [int(i) for i in f.readline().strip().split()]
    aT.append(line)
for i in range(32):
    line = [int(i) for i in f.readline().strip().split()]
    bT.append(line)

aT = np.array(aT)
bT = np.array(bT)
T = np.eye(32,dtype='int')
res = np.dot(bT, np.dot(T, aT))

flag = 0
for i in str(res[:, 0])[1:-1].replace('\n', '').split(' '):
    if not i == '':
        flag = flag + int(i)
print(flag)
result = md5(str(flag).encode()).hexdigest()
print(result)

math1

没做出来，参考博客进行复现。首先根据密钥生成算法可知$n_1=a_1b_1+1,n_2=a_2b_2+1,n_3=a_1b_2+1,v_2=kb_1+1,N_1=n_1n_2,N_2=n_3v_2$，那么近似有$N_1/N_2=a_2/k$，展开连分数就可以求到a2和k，又$ed-1=k\phi$，所以$\phi_1\equiv(-1)k^{-1}\;mod\;e$，并且$\phi_1 \equiv a_1a_2b_1b_2\;mod\;a_2$，用crt可将$\phi_1$上升到模$a_2e$下。这仍然不足以求出$\phi_1$，需要爆破，因为$N_1-\phi_1$大约是512比特级别，和$a_2e$是同一个量级，所以考虑用$\phi_1=\phi_1low+N_1//(a_2e)*(a_2e)+te_2e$来爆破，t应该比较小。需要注意用N1是不行的，它不是$a_2e$的倍数。exp：

import gmpy2
import libnum
from tqdm import tqdm


N1 = 112187114035595515717020336420063560192608507634951355884730277020103272516595827630685773552014888608894587055283796519554267693654102295681730016199369580577243573496236556117934113361938190726830349853086562389955289707685145472794173966128519654167325961312446648312096211985486925702789773780669802574893
N2 = 95727255683184071257205119413595957528984743590073248708202176413951084648626277198841459757379712896901385049813671642628441940941434989886894512089336243796745883128585743868974053010151180059532129088434348142499209024860189145032192068409977856355513219728891104598071910465809354419035148873624856313067
e = 86905291018330218127760596324522274547253465551209634052618098249596388694529
enc1 = 71281698683006229705169274763783817580572445422844810406739630520060179171191882439102256990860101502686218994669784245358102850927955191225903171777969259480990566718683951421349181856119965365618782630111357309280954558872160237158905739584091706635219142133906953305905313538806862536551652537126291478865

# c = continued_fraction(int(N2) / int(N1)) 
# sage里int不太对
c = continued_fraction(N2 /N1)
end = 0
for i in tqdm(range(1, 211)):
    if end == 1:
        break
    a2 = c.denominator(i)
    k = c.numerator(i)
    if gmpy2.gcd(k, e) != 1:
        continue
    tmp = gmpy2.invert(k, e)
    res = (-1*tmp) % e
    phi_ = crt(res, 0, e, a2)
    bound = lcm(e,a2)  # lcm
    phi1 = phi_ + (N1 // bound) * bound  # 必须加bound的倍数
             
    for j in range(1000):
        if gmpy2.gcd(e, phi1) == 1:
            d1 = gmpy2.invert(e, phi1)
            flag = libnum.n2s(int(pow(enc1, d1, N1)))
            if b"flag" in flag:
                print(flag)
                end = 1
                break
        phi1 -= bound

巅峰极客2022

point-power

根据倍点公式和椭圆曲线公式建立方程组求解，用代入法比较好解: $y_1^2=x_1^3+ax_1+b$ $\lambda=\frac{3x_1^2+a}{2y_1}$ $\lambda^2-2x_1=x_2$

p = 3660057339895840489386133099442699911046732928957592389841707990239494988668972633881890332850396642253648817739844121432749159024098337289268574006090698602263783482687565322890623
b = 1515231655397326550194746635613443276271228200149130229724363232017068662367771757907474495021697632810542820366098372870766155947779533427141016826904160784021630942035315049381147
x1 = 2157670468952062330453195482606118809236127827872293893648601570707609637499023981195730090033076249237356704253400517059411180554022652893726903447990650895219926989469443306189740
x2 = 1991876990606943816638852425122739062927245775025232944491452039354255349384430261036766896859410449488871048192397922549895939187691682643754284061389348874990018070631239671589727

P.<a>=GF(p)[]
y12 = x1^3+a*x1+b
f = y12 * 4 * (x1*2+x2)-(3*x1^2+a)^2
solve=f.roots()
for a,_ in solve:
    print(bytes.fromhex(hex(a)[2:]))

strange curve

gcd

推导一下，做gcd求p*q 。本题实际上是基于公钥加密体制Schmidt-Samoa。

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

n = 1715097516831775561161353747739509313962850384763754284193603064705990003183954750857689649540587082555847904377918426763475079170697690469267290454724999354302036981034615698694153403754870938739225201770934147845874793740053505575413463153429315475539039712818850905666950096326806695688446947957198050957270336443016980023115464136303403780696015358461369838964806435293267645492940773964907954737849962270208167145137818071024789445448292917016422004351584109968952746852305729861258178402122017513103311904147173869605944992973485253275501741635308107788593258463591060922145241960065862813218690280146883588390356662245698217956617720339878472430817614915509896516775918109916920083183701011823993137753987826242193055167215287839864164955881557719443664876504155709359476375455266912247205663953373944852046907623883953483708248467223346798885142046228485310724692353541792975390854356153906879056788972704718688261213
x = 13693034247131001247611357013365838905472128629161269384100755984286945944986882779020879733934334461215591081830359749241927901759168319107452036275703768755532293338513836146556306490425526394420440685291299327486258632666082657664827474947846307949205548526817689180357262646108048851554962291154624349603853599623877095789135051759890435127891210971940795915429197420232561510826760487552089621705187244655827668509013761027910519038664267576214742561936826964572261315984043602119812357324667105678247267841445497640859880436819217418374184256023378843611198818733281625017307272013394628328908242726204785568269
c = 1207106262178445359018459948589897274651891185968586806427714234447059397099330669443037189913958678506147447588787686432870791586266645067569198511010947847769438531195366288233395081813524859121328300315116211130908169351354477893647936383056584771268247471788727296968981371535384241445434057942795625350351461517179136190258136244456887118978348223420158887403238429201791427682781494296473806409015961385580794909106746874670027369932286414096790928966277930586468864071103687837936910843559150279603968747213779555572156135983177121194768041838538456267670795923361920648635769732101772513407467158904982779342496410211785417729464008786654808126619152228029357660596380038858050797654917902576424059433048290426186067840363899227577713800670585547473870112798624948349947633855963137174688403113603549470708467306886181387445601800049442519922530086418265660642841544022198981442640591637598035257382429976435264690303
pq = gcd(pow(2,n*x-1,n)-1,n)
p = n//pq
q = n//(p**2)
phi = (p-1)*(q-1)*p
d = inverse(65537,phi)
print(long_to_bytes(pow(c,d,n)))

Learning with fault

vikeCTF2023

Ramparts, Shields & Armour

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

e=65537
n= 2715497625635217146051376883956221648457865424622390574119932619240972515957205301547292163268724150187299302534465552773073139476525066742321406599243867465883849966396559680643698047414084301014507492106282319588119157974394187603403699632895945629213903894587666324702695802895745447206685995668163896335087720970956472989601397590054003266898289768493161392030105302457157363021403799771182388703628329605850194393268686044923475312870917582827968692465970401385092167983959555898172994224835950025711275910795477467161659125090139213700951006615227142761425199562930474622208063719519967552546075441680528564381619671244482483370324691479133982575782792761354401433225302382110766631654057892534939319680412593946754663446176047443171302181260711497921957223797559705657563059146379524464376911709110980976711662094151747135752785623430700378782619219767151302618362874360951701711850602414797407445920937513222982463
c= 2412481553363067093994916106363138049676984068236717223446550136171994383803478397500582933716465596790399547785030492395365201877716652700143844505307501652470883697533651197665986331703230104426840112747699995620811385491528574446175126510676387450802481586396253826465171957105380668709916951820668574228024071014457042504788367209816822997439069546208655373188430319424281112336866266338808391138368420494075883526920594370234349115371071576557496658595306274879005581064161369194441884021024926550233457727353645678589032674268525692578834142222591657655876528245907018527470023673383681518369733877208435542662260811658693623152145931671636562104853620717919813146153890630297430942453932072766596242967505064809743305645874530813033758653920440104744594118679043088872558752784045628474230603822071828647953195345218722932560770485975541412563771196519749202050483658465939572153802085946092772315833898486765474763

f = iroot(n,3)[0]
# 枚举求一个因子再费马分解
for i in range(-10 ** 5,10 ** 5):
    t = f + i
    if gcd(t,n) > 1:
        print(t)
        break

p = 13951357765155709449830622397661638963070683976472071585199504608625810928008612997548809635837631164950341825594429159537546547719716808479935035640532723431507957846055033278541122998184597009740171807903306417775729507986843778070860411124830445265478641966781186918221084904469724098608590367319371499057
qr = n//p
q = fermat(qr)
r = qr//q
phi = (p-1)*(q-1)*(r-1)
d = invert(e,phi)
print(long_to_bytes(pow(c,d,n))[::-1])