七七的欧拉

Pasted image 20231130161132.png

文件改了个后缀

import gmpy2
import libnum
from crypto.Util.number import *

flag=b'ISCTF{*************}'
m=bytes_to_long(flag)

p=libnum.generate_prime(1024)
e=libnum.generate_prime(512)

c=pow(m,e,n)
output = open('output1.txt', 'w')
output.write('e=' + str(e) + '\n')
output.write('n=' + str(n) + '\n')
output.write('c=' + str(c) + '\n')
output.close()

显然就是传统的RSA

Pasted image 20231130161351.png

进行分解，得到n为p的8次方

此时

\varphi(n)=\varphi(p^8)=p^8-p^7

算出phi后代入算出d，然后解rsa。

e=8401285423075497989963572888601376313375827722858883767564499066473101615084214973041844878664837606157257039358849583049856161628241418012475432529735909
n=4321524416983780646994834778612486851863709339970595612409550086067211224407144019110798099401660010305645681548980160563216101786447875231976835115531375372678886339587480251211072894186558627897353793098608766868067029578667171419890150599640781594755080391489447462042167529203389236065727274166091741227068469987681083794139925327545810024038937132463518225611578727737940746784891867532498184642892826569777559107609493212332054559366409007685504768163376250281644004067745087899653778023414105973047620041288118404657934689253192043728590231618132716567084621670074256312939305265244486145758609971249077639085204680923108132415216543541472534580414274250979940330459551536830268428508217821060604260805109071534457808355664329902779603050878055690772430842865701249378096775899778255848773171108341331128673249899037133851535556515961699925809139476576825524135111237249709241579903807179252011010794867269715170739895392375920757559721516050680666658719990497863646989338960261844762127142439486275294670858114079687572243312184222126710967744971775585723045524467708387051034760208768956889939050498139189352842087278125173957182804116052402778416216669522309692266036094371308166663738284209615212016564171075874421472070422416318901926525719485991792111414333398004433143751908199358861514725313334333703539239414806773743941986164981642517673117412666430463318509571757766510835600758060976848374353352239044908034501477295696684294816091801944163877509558909040753907584672390823893991672246726026216973013330313971007514064831801564703364591696610900089228302936595848024616691878437618798864186634802647568239526771151323609650598156701595265876736712670677452013054393336294483452480213271032488201259990782289047132105989846972462094302132564809025802421057537091870932014884606863807260521123084423689494401900014232257381801590783735595575258160274248494498550583673688754220860142413631521279464318987425447302135444093663034598455694901199312497459228254746451233078954904159983269585883146959928222698672413648364391121696092287848931565798557217897678221379451042304811449415982434055522599829843482810025780349284547491767219221510351411192251236517341826619338084348136539121415210345488359563985046136632077665460793346345051213014836088333266911684271237227766588616771431226302155269893547077232087387411935345207081799500649921586279416751311277417949192360648342427657867424947189027886922112452681434778850977010752230391327878892161
c=1319666577538961333645698288755316431847498788803191213042970951363587036899021668814931340784440773619019635330248746606532233949080268712626456845590851812018539646705520729734738948568349756255640832936325965096602018372418260009779997764653043892043725224481361578258532294625476542003357969893609762981355267857532927948279737945466285738730414948695579002627741734690862181161919734547857550654813379550806374778412603233570494684223057004866601064851006909940259029023083838730497564657690493780040030061594915385886594845808342023634855913932575150487723897981518504381563064479784253539091893925934095008385592529031453149337783826491324308222762190756839839091742536583068791632135883271750510776330897598323339568926234205068941397524390446254057404779041850572848212437589629794980799894974937730065394307284096622814438575278571743516485062058882794531407454597341604166586040406867868323002258035737328450923576878935675998377134860357842547595516243737449809845708319003744144753130977649201725370898918939022097783844477196723482879094829249203949784703408369396219233552019108990900029123063369670129291960293576115301371071209198455299007327352602249399500334424934488528506773472420414119617828578424633182320749576697196936762283306228974126242434663703609495003656244194067493769815032134577138807799395279843708630774412341952691146906264694889245375545635688534662371202213660012977431598746482601668122679279419039288257069843297770840263002870206849857995148396439717143553611140228607531647245352254251824086797704561756363448681983654454393569932173970943157225527780067126895832370645456372127507057750232257828579628856504832975775855059816283684123444984393171125206440588627925736223222718784319209561804023835238526792966229582251575475514349566824846911411659740321154272534589694497411065971714157409318007179403833025337349924938487211920583780456897879801099476865645416182025930390267064170271613760577949655548949317295792361772032185463678410983568470647837758657058230086368185901572658482084202212103405161775243930901117532775865963215971025744893777631306256061896284125630451368067313753222195227231131526000755922331413457862253392530308284156400411897252674398583100198330007779643967156773216464341590817951828849769679134515304258819218015083183653130972243262400248230445031327719507314015062447355358100770763425336581258193908638241498461735819218673116282476452340137513156421147748432605954889277898079292196216

import gmpy2
import libnum

phi = n**8 - n**7
d= gmpy2.invert(e,phi)
m=pow(c,d,n)
print(libnum.n2s(int(m)))

夹里夹气

Pasted image 20231130164838.png

Pasted image 20231130164826.png

easy_rsa

Pasted image 20231130164935.png

Pasted image 20231130164944.png

p=
q=
e=
c=

import gmpy2
import libnum

n=p*q
phi = (p-1)*(q-1)
d=gmpy2.invert(e, phi)
m=pow(c,d,n)
print(libnum.n2s(int(m)))

rsa_d

Pasted image 20231130165110.png

Pasted image 20231130165120.png

p=
q=
e=

import gmpy2
n=p*q
phi = (p-1)*(q-1)
d=gmpy2.invert(e,phi)
print(d)

Pasted image 20231130171352.png

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

def genKey(nbits):
    p = getPrime(nbits)
    q = getPrime(nbits)
  
    N = p*p*q
    d = inverse(N, (p-1)*(q-1)//GCD(p-1, q-1))
    return N,d

def encrypt(message,N):
    m = bytes_to_long(flag)
    c = pow(m, N, N)
    return c

nbits = 1024
m = bytes_to_long(flag)
N,d = genKey(nbits)
c = encrypt(m,N)

print('c =', c)
print('N =', N)
print('d =', d)

"""
c = 29897791365314067508830838449733707533227957127276785142837008063510003132596050393885548439564070678838696563164574990811756434599732001622138564176327233154381380717648392357672642893142367607369679906940371540867456654151408884171467638060523066406441697453971996011548195499549200103123841556085936672833238264876038160712793697159776332101536779874757463509294968879216810485825310481778472384531442206034564488532399171243463881900578407746982324779260941957792455217641883334131366614310644607114128868153897806362954456585661855569432513785225453501792356175649676419772626548071916379318631677869452985829916084336045071072493567871623113923140668031380684940109024609167449291380675124701557542736834722898328082888430566229322840781411336263268594978558564310744076581639469210462567543585251718744340216155557606004995449505782302864725856877289388008819135023371948017425832082773421030256964953984562211638060
N = 3231913372897424708803097969843687520868057190788284975066875241636436021279559026753076528399891936983240045179193386905918743759145596242896507856007669217275515235051689758768735530529408948098860529277921046146065473333357110158008648799207873976745048714516868561754202543130629713461365314627535982379718931633528922076268531363809414255082933615667770491818402126891370106045838695484124212397783571579791558324350069782623908757815983802849109451590357380624488436968737140312471089662428308113246310588336044438265822574558816510054763215983649467009345458480077882624118620789015758507736272402998721366662352794082495441303895025585316667229865533166614969641012195668280586477033200418153345241668242651407009849656745509386158276185301334443855737552801531617549980843398648751032649895403939319648954908487619711555700124294191702406981128355348449748466449951568451135718146828444185238617155432417897711198169
d = 220908195398117048628110042133057032501548264225985823161565460390793825899523662424732910718579350524590368287207857059670558852106434615134645183432670023784725430385048028248108677670095524205518013647694485975996499747580966911259433184798952372110628624294686853944766950244209186984164963987120416687012811346656498861438432610431705868541829977481875385468143747334359481673214618931159403123892213161430602430294790913847722073762999311674428134241956293914716183107414340330449465142849402354034926378025006749405210014879947411570380433942279355488861684317611066949685697268714760755591128598654573304969
"""

这里我为了大部分人的阅读体验，证明可能写的有点啰嗦，各位佬们见谅。

根据逆元定义

Nd \equiv 1 \pmod {\frac{(p-1)*(q-1)}{GCD(p-1, q-1)}}

事实上，这个模的部分是两者的最小公倍数lcm，但是这题用不到，我们可以暂时忽略这个知识点，记这一大坨为L，即

L=\frac{(p-1)*(q-1)}{GCD(p-1,q-1)}

将恒等式化为等式，有

Nd=1+kL,k \in Z

注意到k是任取的，我们不妨就找一些特殊的k，即

k=k_1*GCD(p-1,q-1),k_1 \in Z

即k是L的倍数，代入上式，有

Nd=1+k_1 \varphi(n)

其中

\varphi(n)=(p-1)*(q-1)

此时注意到，两个k均属于Z且任取。那么我们注意到原式可以写成

Nd \equiv 1 \pmod {\varphi(n)}

任取一个正整数a>1，取其Nd次方，并对n取模，有

a^{Nd} \equiv a^{1+k_1*\varphi(n)} \pmod n

注意这里的

n=p*q

而

N=p*p*q

然后有

a^{Nd}\equiv a*a^{k_1\varphi(n)} \pmod n

由于欧拉定理，

a^{\varphi(n)} \equiv 1 \pmod n

而1的任意次方都等于1
所以

a^{Nd} \equiv a \pmod n

转化为等式，移项，有

a^{Nd} -a=k_2n

a自选的，N，d都已知，所以k_2n已知，与N求gcd，可得到n

N=p*p*q=p*(p*q)=p*n

因此

p=\frac{N}{n}

有p后计算q，然后正常求解RSA

N=
c=
d=

import gmpy2

a=2 #不妨取a为2
kn = pow(a,N*d,N) - a
n = gmpy2.gcd(N,kn)
p = N // n
q = n // p
assert p*q==n

print(n2s(int(pow(c,d,n))))

EasyAES

Pasted image 20231130205613.png

from secret import flag,key
from Crypto.Util.number import *
from Crypto.Cipher import AES
import os

assert(len(flag)==39)
assert(len(key)==16)

def padding(msg):
    tmp = 16 - len(msg)%16
    pad = hex(tmp)[2:].zfill(2)
    return bytes.fromhex(pad*tmp)+msg

def encrypt(message,key,iv):
    aes = AES.new(key,AES.MODE_CBC,iv=iv)
    enc = aes.encrypt(message)
    return enc

iv = os.urandom(16)
message = padding(flag)
hint = bytes_to_long(key)^bytes_to_long(message[:16])
enc = encrypt(message,key,iv)

print(enc)
print(hex(hint))

"""
b'bsF\xb6m\xcf\x94\x9fg1\xfaxG\xd4\xa3\x04\xfb\x9c\xac\xed\xbe\xc4\xc0\xb5\x899|u\xbf9e\xe0\xa6\xdb5\xa8x\x84\x95(\xc6\x18\xfe\x07\x88\x02\xe1v'
0x47405a4847405a48470000021a0f2870
"""

容易得知，padding后的结果是在前面加上9个 \t键
而明文字符串ISCTF{为6个字符，差一个字符我们可以爆破，从而得到原文的前16个，进而恢复出key

那么iv怎么恢复？

我们注意到加密方式为CBC加密

我们了解一下CBC加密和ECB加密方式，这里我们假设明文都是16的倍数长，如果非倍数应该先进行填充，这里暂且不谈。

首先是ECB加密

ECB加密将明文按照16个一组的顺序分为n组，然后对于n组分别进行加密

举个例子，比如我们以数组的形式代替分组，用函数

f(x)=x^2

代替加密函数

假设我们有一个这样的数组

[2,7,16,19,21]

如果按照ECB模式进行加密，则加密结束后的数组为

[4,49,256,361,441]

然后是CBC加密，CBC加密要求我们输入一个iv，我们通常称为偏移量

CBC的加密方式是流加密，就如同一条河流一样有先后顺序，例如要想计算出第二个值，必须计算出第一个值之后才能计算。那么对于第一个值来说，我们需要在第一个值之前找到一个值，才能计算出来，这个值就是iv。

例如还是刚才的例子，但是我们稍微更改一下这个函数，让他变成流加密的形式

f(x_i,x_{i-1})=x_i^2+x_{i-1}

同时我们设定一个iv为3
那么按照这样的加密方式，有第一个值为

2^2+3=7

第二个值为

7^2+7=56

第三个值为

16^2+56=312

以此类推，最终得到的数组为

[7,56,312,673,1114]

这就是CBC的基础思想，只不过在真正的CBC中，是将原文与iv进行异或后进行AES加密的。

很容易发现，无论是CBC还是ECB加密，两者明文和密文最终长度是相同的。

让我们回到这道题上来，那么我们根据上边的介绍，我们知道明文的第一段（前16位），明文和密文是一一对应的，第一段明文对应第一段密文，加密方式是CBC加密，CBC加密第一段是用IV和明文异或后进行加密得到的密文。那么我们反向进行，即

将密文解密后与明文进行异或，得到IV

获得IV后再将全体解密即可。

from libnum import n2s,s2n
from Crypto.Cipher import AES

c = b'bsF\xb6m\xcf\x94\x9fg1\xfaxG\xd4\xa3\x04\xfb\x9c\xac\xed\xbe\xc4\xc0\xb5\x899|u\xbf9e\xe0\xa6\xdb5\xa8x\x84\x95(\xc6\x18\xfe\x07\x88\x02\xe1v'
hint = 0x47405a4847405a48470000021a0f2870
m = b"\t\t\t\t\t\t\t\t\tISCTF{"

for i in range(256):
	raw = m + n2s(i)
	key = n2s(hint ^ s2n(raw))
	c0 = c[:16]
	iv_enc = AES.new(key,AES.MODE_ECB).decrypt(c0)
	iv = n2s(s2n(iv_enc)^s2n(raw))
	flag = AES.new(key,AES.MODE_CBC,iv=iv).decrypt(c)
	if (b"ISCTF{" in flag) and flag.endswith(b"}"):
		print(flag)
		break

#b'\t\t\t\t\t\t\t\t\tISCTF{1b106cea3fb848e7bea310c9851f15c1}'

1zRSA

Pasted image 20231130225754.png

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

e = 65537
def genKey(nbits):
    while 1:
        p1 = getPrime(3*nbits)
        p2 = gmpy2.next_prime(p1)
        q1 = getPrime(nbits)
        q2 = getPrime(nbits)
        print(abs((p1 - p2)*q1*q2 / p2) < 0.5)
        if (abs((p1 - p2)*q1*q2 / p2) < 0.5):
            n1 = p1 * q1
            n2 = p2 * q2
            return n1,n2

def encrypt(message,e,n):
    m = bytes_to_long(message)
    cipher = pow(m,e,n)
    return cipher

e = 65537
nbits = 512
N1,N2 = genKey(nbits)
c = encrypt(flag,e,N1)

print("c =",c)
print("N1 =",N1)
print("N2 =",N2)

"""
c = 10514867898770499427284608506159580569755258729683776720082395249877529851029152305989048383470182992945743997295638334301128554841767619528809377736651238576700664675871769469687466885347209033023021132575700436470105289467423655742323143373578268184141573237433927498143740155552829633601489926767185335051352605346248971754473960051955670785777007641909166041398566067524811394639822575661469340152913706417365065683835945980239268665146900957692685590242386540944646586739158427428484471978559453954674292300496568823382513505511940062159025700312492163454304120916055466108498000990408937265075788135466153131436
N1 = 29306627985861300819651846356448043523015086509329909246911330574896611830331438353458702041787309531570626136669100576501108581024502570212983369979387658041578384466200573362881060761873478590684611265249166591510948597798713864127744488747451815919677861684787135464097885906630772472111899455047125676738720391327331161464894360886214160668909531050207033060523194208723151015702926842472554933849380343375654696115359960495727909221926251630408376527033291123026893207722440649867394971680316008434251667567174806214522621693042164997381729300075394393372808917061813346794422821819494227772694592990703688149467
N2 = 18405525902524887428651801489049128242565457677879715229456940729064725933277139190670749899959483734341103740185991771024797037242681566772189045321838652668819112989587974866361063424698215713773139281840970499871668796770682692589505769008516630604297570518689639885716307469568821629424402742264467677407820449195383921766157185602677665872353099155904715047452319853202981674101731121033360393547940246101864940155160699277417096395998766928213545196492031975135121409309520198853066288180944871441224241681478164494169741263236267316380581883196836731872676312125837497320438964940186318916950049777255612191899
"""

我们简单总结一下代码给我们的
首先生成了4个数，分别是p1,q1,p2,q2
其中p2是p1的下一个质数，在质数很大的情况下，我们可以认为p2-p1很小
然后已知

\left |\frac{(p_1-p_2)*q_1*q_2}{p_2} \right | < \frac{1}{2}

显然p2大于p1，我们去掉绝对值

\frac{(p_2-p_1)*q_1*q_2}{p_2} < \frac{1}{2}

有

n_1n_2=p_1p_2q_1q_2

有

\frac{(p_2-p_1)*n_1*n_2}{p_1p_2^2} < \frac{1}{2}

这种式子看起来不太清晰，我们稍微变一下形
式子左边先去掉括号，有

\frac{n_1n_2p_2 - n_1n_2p_1}{p_1p_2^2}< \frac{1}{2}

然后再利用n1,n2的等式做一下变换

q_1q_2-\frac{n_1q_2}{p_2}< \frac{1}{2}

继续变换，并提出一个q2的平方，就有

q_2^2(\frac{q_1}{q_2} - \frac{n_1}{n_2}) < \frac{1}{2}

这样其实已经非常明显了，我们要用到连分数近似的概念
我们把公因子移到不等式右边，加上绝对值

\left | \frac{n_1}{n_2} - \frac{q_1}{q_2} \right | < \frac{1}{2q_2^2}

上述的变换只是为了更好的给大家展示推导过程，使得思路不那么跳脱，可自行简化，不一定按照上述推导。

引理：
legendre Continued fraction
若有

\left | \xi - \frac{a}{b} \right | < \frac{1}{2b^2}

那么\frac{a}{b}是\xi的连分数展开的某一项渐进分数

具体不证，可以去这儿仔细研究推导
https://math.stackexchange.com/questions/531736/legendres-proof-continued-fractions-from-hardys-book

那么下一步就是如何求某个数的连分数，事实上，通过辗转相除法，可以得到任何一个数的连分数展开形式，我们这里只讨论有理数的连分数。

计算上就是求除数和余数，然后把除数写成连分数加号位置上的数，余数取倒数后继续重复上述计算，这里不在赘述。

以一个例子作为参考，如计算下式的连分数

\frac{67}{29}=2+\frac{1}{3+\frac{1}{4+\frac{1}{2}}}

其中67除以29得除数为2，余数为\frac{9}{29}
然后取倒数，在进行计算，直到可以整除。

那么我们可以将任意的实数写成类似于连分数的形式，然后我们记加号前的数为a_i，即

\frac{n}{m} = a_1+\frac{1}{a_2+\frac{1}{a_3+ \dots}}

这样我们可以得到一个类似于数列的东西a_i
事实上我们可以证明任何无理数的这个数列都有无穷项，而任何有理数都为有穷项。

那么什么是渐进分数呢？
我们类比求数列前n项和的形式，定义渐进分数为某一个数的前n项连分数和，即

c_1=\frac{a_1}{1}=\frac{p_1}{q_1}

c_2=a_1 + \frac{1}{a_2}=\frac{p_2}{q_2}

c_3=a_1 + \frac{1}{a_2+\frac{1}{a_3}}=\frac{p_3}{q_3}

以此类推。同时我们定义其分子分母。

为了方便计算，我们引入下列定理
对于一个连分数，其第i个渐进分数的分子分母（其中i>2）为

p_i=a_i p_{i-1} + p_{i-2}

q_i=a_i q_{i-1} + q_{i-2}

然后i=1时，

p_1=a_1,q_1=1

当i=2时，

p_2=a_1 a_2+1,q_2=a_2

可以用数学归纳法证明，这里不证。

那么就可以计算题目中的q1,q2了，由上述定理可以知道q1,q2是N1,N2的连分数的某一项渐进分数。
我们应用该定理去找就ok


import gmpy2
import libnum

c = 10514867898770499427284608506159580569755258729683776720082395249877529851029152305989048383470182992945743997295638334301128554841767619528809377736651238576700664675871769469687466885347209033023021132575700436470105289467423655742323143373578268184141573237433927498143740155552829633601489926767185335051352605346248971754473960051955670785777007641909166041398566067524811394639822575661469340152913706417365065683835945980239268665146900957692685590242386540944646586739158427428484471978559453954674292300496568823382513505511940062159025700312492163454304120916055466108498000990408937265075788135466153131436
N1 = 29306627985861300819651846356448043523015086509329909246911330574896611830331438353458702041787309531570626136669100576501108581024502570212983369979387658041578384466200573362881060761873478590684611265249166591510948597798713864127744488747451815919677861684787135464097885906630772472111899455047125676738720391327331161464894360886214160668909531050207033060523194208723151015702926842472554933849380343375654696115359960495727909221926251630408376527033291123026893207722440649867394971680316008434251667567174806214522621693042164997381729300075394393372808917061813346794422821819494227772694592990703688149467
N2 = 18405525902524887428651801489049128242565457677879715229456940729064725933277139190670749899959483734341103740185991771024797037242681566772189045321838652668819112989587974866361063424698215713773139281840970499871668796770682692589505769008516630604297570518689639885716307469568821629424402742264467677407820449195383921766157185602677665872353099155904715047452319853202981674101731121033360393547940246101864940155160699277417096395998766928213545196492031975135121409309520198853066288180944871441224241681478164494169741263236267316380581883196836731872676312125837497320438964940186318916950049777255612191899
e=65537

#这里数组的第一个为0是为了下标从1开始，方便计算和对齐
def get_aList(p,q,a_list = [0]):
	a=p//q
	a_list.append(a)
	if p % q != 0:
		return get_aList(q,p%q,a_list)
	else:
		return a_list


def get_pqList(a_list):
	pqList=[(0,0)] #这里跟上述同理
	#pqList为一个数组，每个值为一个元组，表示分子和分母
	pqList.append((a_list[1],1))
	pqList.append( (a_list[1]*a_list[2] + 1, a_list[2]) )
	for i in range(3,len(a_list) ):
		pqList.append( (a_list[i]*pqList[i-1][0] + pqList[i-2][0] , a_list[i] * pqList[i-1][1] + pqList[i-2][1]) )
	return pqList


def crack(N1,N2):
	alist = get_aList(N1,N2)
	pqList = get_pqList(alist)[1:] #把前面对齐的第0项删掉，或者下边过滤一下不计算第0项
	for q1,q2 in pqList:
		#找每一项渐进分数
		if N1 % q1 == 0 and q1 != 1:
			print(q1)
			p1 = N1 // q1
			d = gmpy2.invert(e,(p1-1)*(q1-1))
			m = pow(c,d,N1)
			print(n2s(int(m)))
			break

if __name__ == "__main__":
	crack(N1,N2)

ezRSA(τ)

Pasted image 20231201014305.png

Pasted image 20231201014310.png

本题依旧是两部分
step1就是变形就能解
step2要找一个卡迈克尔数，然后有LCG和RSA组合（就硬套）

先解决第一部分
有

leak = (e^2+(ed-1)*f)*getPrime(256) + k

移项去括号化简，设p=getPrime(256)

leak - k = pe^2 + (ed-1)*f*p

其中f是k的阶乘

e大小为512位，平方为1024位，p为256位，故pe^2为1280位
而k在800到1500之间
阶乘函数单调递增，而f(600)为6568位
显然远大于pe^2
因此等式两边同除f,pe^2为余数，p*(ed-1)为倍数
显然两边有公共因子p
若k不对，两边几乎不可能恰好有共同因子且大小为256位
因此因此遍历k，当两边有共同因子且大小为256bit时找到k和p
而已经有除数和倍数，除数和倍数都除以p
可以得到e^2和ed-1
开方可以得到e，代入右边可以得到d
已知n,e,d可以求得p,q
step1解决。

解决step2，提示有3部分且大小小于一亿，并且为合数但通过素性检验
易知为卡迈克尔数
小于1亿的由三个组成的卡迈克尔数有255个，爆破即可得到56052361

卡迈克尔数子集的生成公式：
若6k+1, 12k+1, 18k+1均为质数，那么他们的乘积是卡迈克尔数。
或
6k+1 ,18k+1, 54k^2+12k+1均为质数，那么他们的乘积是卡迈克尔数。

然后此时leak1是典型的rsa题型，

p^q \equiv q\pmod n

q^p \equiv p\pmod n

因此leak1实际上为p+q
与n=p*q联立解方程，有p和q
然后有leak2解LCG，可以求出下一个随机数seed
然后将key和seed异或算出base
这里实际上是将十进制的c转化为base进制的final
已知base转化回来即可
然后算出十进制下的c
解RSA即可。

baby group

Pasted image 20231201014325.png

很明显，这道题给了一个mask*mask的值，并计算了其mask的哈希值，然后利用一个新的mul*mask得到了一个hash，用这个hash的值异或flag得到msg，加密msg

因此我们要关注的点在mask的求解和解密msg

首先看mask是由P生成的，P中生成了一个给定大小的自然数序列并打乱

P的乘法是在在右乘中找左乘中对应位置的数

如[1,4,3,2,5] * [a,b,c,d,e]

左乘列表中第一个值是1，在右乘列表中找第1个值，为a

左乘列表中第二个值为4，在右乘列表中找第4个值，为d

以此类推，得到[a,d,c,b,e]

实际上P类是sage permutation group

即构成了一个S_{256}对称群

根据群论的理论，我们将题目抽象为

给定一个对称群P^2求P

易验证下列三条性质

1、对于任意一个对称群G，总能由属于群G不同元素完全重组成多个循环，对于其中第i个循环，不妨将该循环记作R_i，即

\forall a \in G \ to a \in R_i \quad and \quad \forall i,j < n,i \neq j \to P_i \cap P_j = \varnothing

2、若P_i的长度为奇数，则对于G的任意次方所组成的循环中，P_i的元素不变

3、若P_i的长度为偶数，则对于偶数次循环中，其P_i的长度会减半，变成两个相同长度的循环

如群[7,4,1,8,9,5,6,2,3]可以分为(1, 7, 6, 5, 9, 3), (2, 4, 8)两个循环，不妨验证(2,4,8)组成了一个循环，从该循环第一个元素出发，第2个元素是4，第4个元素是8，第8个元素是2，即如果G自乘，该循环中的三个元素位置只可能是2,4,8且值也为2,4,8，只不过对于的位置和值可能不同。

再考虑该循环，显然元素有奇数个，即长度为奇数，由上述易证，只可能是2,4,8，循环不变。

而对于(1, 7, 6, 5, 9, 3)，显然对G^2来说，G^2:[6, 8, 7, 2, 3, 9, 5, 4, 1]，组成的循环为[(1, 6, 9), (2, 8, 4), (3, 7, 5)]

显然分解成了两个长度相等，大小为原来的一半的两个新循环，而奇数长度不变。

有了上述性质，大家可以试着再解一下前半部分题目。

那么我们来求解该题目，显然，mask可以分解为不同的循环组成的。

我们依旧记mask为G,对于G^2，其中的奇数次循环既可能是原来就是奇数次循环，也可能是偶数次循环分解得到的。对于其中的偶数次循环，一定是由一个大循环分解过来的。如果是分解得到的，那么两个循环长度相等。

因此我们可以得到以下思路：

对于奇数次循环，我们寻找G^2的所有循环里是否有与该奇数次循环长度一样的循环，如果没有，说明该循环就是我们找的本身。如果有，可能是巧合，也可能是由一个大循环分解过来的。

对于偶数次循环，必定能找到与其长度相同的循环。

现在，假设我们找到了G对应的循环，我们应该如何由循环恢复G呢？

引入定理：

若两个循环没有重复的元素，则它们的顺序可互换

那么对于一个自然循环群，乘上上述的各个循环即可恢复群。

现在问题是，循环中只是元素不变，如何确定循环中各元素的位置？

可自行验证，若对于G的循环，其G^2的相同循环（此处的相同指的是偶数分解后的两个循环或者奇数循环本身）总是按照隔一个取一个的形式来进行的。如对循环(1,3,4,6,9,8,7)，其G^2的该循环为(1,4,9,7,3,6,8)

读者可自行验证G=[3,5,4,6,2,9,1,7,8]时是否满足上述情况。

而对于偶数长度的循环，上述也适用，但无法确定谁在开始位，譬如(2,4)和(1,3)既可以是(1,2,3,4)也可以是(2,1,4,3)，此时需要遍历查找

由上述所有定理可以得到搜索算法，将搜索时间从256！降到可行的水平。

由于本wp默认无群论基础也可以看懂，所以讲的相对啰嗦

第二部分为一个简单的格密码学问题
简单写一下
加密给了两个值，一个h一个q
self.h = invert(self.f, self.q) * self.g % self.q

h \equiv f^{-1}g \pmod q

e是密文，解密需要f和g
我们对式子进行恒等变换，首先左右各乘上一个f

fh \equiv g \pmod q \tag{1}

同时
e = (r * self.h + m) % self.q

e = r*h + m \pmod q

代入h

e = r*f^{-1}*g + m\pmod q

一样同乘

e*f = r*g + m*f \pmod q

考虑1式，有k \in Z满足

fh = g + kq

我们不妨构造两个向量

a_1=(1,h),a_2=(0,q)

那么考虑向量(f,g)可以表示为

(f,g) = fa_1 - ka_2

我们已知h和q
若我们能求出来f和g，那么我们显然可以直接进行解密

那么上述都是数学变换，怎么进行求解呢？
我们这里不进行具体证明，有兴趣可以自行验证

二维格上的高斯启发式：

v_{min = }\sqrt{\frac{detL}{\pi e}}

其中v为二维格上的最小向量（注：上式为估计值）
那么我们不妨将a1，a2设为一个二阶格系统，
则detL为由a1,a2组成的矩阵的行列式
|a_1,a_2| = 1*p - 0*h = p
即最小向量在p附近
同时由题目可得，|(f,g)| \leq p
不加证明的猜测(f,g)为最小向量

而二阶格系统的最小向量可由高斯格基规约算法得到
参考链接：https://blog.csdn.net/qq_42667481/article/details/118332181

import numpy as np
from gmpy2 import *

def GLR(h, q):
	a = np.array([1, h], dtype=object)  
	b = np.array([0, q], dtype=object)
	if a @ a > b @ a: #@为向量点乘
		a, b = b, a
	m = (a @ b) // (a @ a)
	while m > 0:
		b = b - m * a
		if a @ a > b @ b:
			a, b = b, a
		m = (a @ b) // (a @ a)
	(f, g) = a
	return f, g

def dec(f,g, e):
	a = f * e % q
	b = invert(f, g) * a % g
	return b

e=
q, h = 
f,g = GLR(h,q)
c=dec(f,g,e)

print(c)#解密

可算写完了......
好多数学公式推导，全在这儿了，保你看的眼花缭乱：（

如果觉得文章对你有用，请随意赞赏

ISCTF writeup CTF Crypto 群论抽象代数

ISCTF2023 Crypto全wp

http://www.guoqil.top/archives/1701595420414

作者

虚空guoql

发布于

2023-12-03

更新于

2023-12-05

许可协议

CC BY 4.0