日期：2023-12-14 作者：jgk01 介绍： GL(n,fp)群阶的题目类型研究。
0x00 前言
最近比赛遇到的一道密码题，当时比赛就给了三个小时，时间不够没做出来，赛后又花了一些时间解出来了这个题目，总结一下这个题目所用到的知识点。
0x01 群的阶
rsa中求d的时候需要知道n的欧拉函数也就是(p-1)(q-1),同样对于一个线性群也存在这样的欧拉函数，及他的阶次方等于单位I，这是比较通俗易懂的解释，呢么稍微专业点的术语就是：
0x02 模p非奇异矩阵的群的阶
首先这里的p是素数，我们先说p为素数的情况后续在套路p为两素数之积也就是符合rsa加密解密的情况。
从最低的3阶矩阵到n阶矩阵，我们可以通过几个例子先来看一下：
flag=b''N = 3x=7flag += os.urandom(N^2)m = [int(x) for x in flag]m = [m[N*i : N*(i+1)] for i in range(N)]m = matrix(IntegerModRing(x), m)assert m.determinant() != 0phi=x^3-1phi2=x^2-1phi3=x*(x-1)*(x+1)*(x^2+x+1)print(pow(m,int(phi)))print(pow(m,int(phi2)))print(pow(m,int(phi3)))
......
详细的生成代码如下：
var('x')def getOrderX(n):P = [x, x-1]fori inrange(2, n+1):ifis_prime(i):P.append(sum([x^jforj inrange(i)]))else:forj inrange(2, i): # bruteifi%j==0:ifj^2==i:P.append((x^i-1)/(P[1]*P[j]))else:P.append((x^i-1)/(P[1]*P[j]*P[i//j]))breakreturnP(getOrderX(8))
0x03 题目分析
搞明白这些以后我们来看这次的题目：
import libnumimport osfrom secret import flagflag=b''# keysp = random_prime(2^256)q = random_prime(2^256)n = p*qe = 65537# paddingN = 8assert len(flag) <= N^2flag += os.urandom(N^2-len(flag))# int2matrixm = [int(x) for x in flag]m = [m[N*i : N*(i+1)] for i in range(N)]m = matrix(IntegerModRing(n), m)assert m.det() != 0# encryptc = pow(m, e)print('n = %d' % n)print(c)
这个题目可以看到是讲flag补充到64位，然后转换为为8x8的矩阵，然后将其定义在模n的群上，进行rsa加密，题目代码很清晰，关键问题是普通的rsa解密很简单只需要求出p，q然后计算出d进行解密，但是这里加密的对象是矩阵，呢么在求d的就需要用到我们上面提到的模p非奇异矩阵的群的阶。
0x04 解题思路
首先因为没有其他有关n分解的信息，所以我们猜测n可以直接被分解，所以我们直接分解n得到了p，q然后我们知道一般要通过n的欧拉函数来求d，这里原理也差不多，通过求求模p和模q的群阶，然后相乘得到模n的群阶，以此来求出d，还原出原矩阵，从而得到flag：
import numpy as npfrom scipy.linalg import sqrtmimport gmpy2n = 11796050253789357988229853226810765102072753365957721787851890262946618828865787422738071244638409487072455435274538798538891961483369615447645570851179759p=108609623209867356524133896921743474579112689065734450666844523397224166827367q=108609623209867356524133896921743474578888969988810592929455411432628814667577e = 65537m =[[10267334564092643380826384431487331067263957797542323456794589522526250849030662036976653271982555145673342053269863760936765225565196345379986725578477487, 11794707436592700463738682042951802145431132015615849927573956608006985241850374504037990427805441242328372462433159537663869079793970818495301087294448973,11360535034389254942617474128403695700497561051050976077764757419910425749577403646700009350963915152402648424802827377208954821261519729312303768719660598, 6566546736549663214564771869690874077779613561962660722774979110424766928020054493825415091372974396219353731004563241963592362833354753090566135453384537,10520547002790511688130654790316845374071426864742200784457583927334710435217058045715933341326969338506760466111581004792813848500379376407447462210655694, 1711529214527852304668758423190193000560890299472146643928541456611970067583705666087044404253966235704578339626918050426244330226667553719802169348080114, 6934401900139801778045530944996905181061132787884890057240526628539602094393259988780017242441640629069057275259534794112770938064035897280025559589766653, 8844274828157953464130900309240655613451901821857394031173534047789123110563645575721535361841458166109190212301048266382042847672415312657216071188563379],[7198719889183165261786006224205698267748474315913834105829678657135363909961895539978579819222750287218931023181431697835326833424096608080630232142242900, 9788517765328779791712456060013907621622343575696954227785817542458236550040394607210568558943846354254400357757872695077109873663932903372404910520688093, 5995197438430425209753536105484829111318072440753816042288312579287675367822708354902925467875520928283237243630467203200610620807891289788592763117706227,10116820438169022423668348883018670276832901508399942496352198345636428677182197352304073533485332196448954359651888778393622274005238818356543335786469886, 6415514974496671046155728783743632322039217129590504290551842783761606920421170642295752778374161249840022027735351812264477925188009853187315840804757864, 3048569456830155817750930998564106614828818818625058171561491049932069868747477455047042711022226750929644658515135340186535698234216952101967644285835704, 3258207872816093047083641161371121201364593033646561035446136668073150155933675157812336257417223379003295694712563835036667298301638226036710296545883383, 7271435235746061327909360916149972677686562477813484703508757352281269168691365502175783649622402072817121566888514632474020819431314350562092260732908695],[4127957848599883890335465124930999627335302076710669872738294154994172091809475284175938697191103117188624534379235395634084477269862720828490108519344230, 9671846847824209494934416785413316517268687645637238372783629647183832983473091895695100560067752989266604325499176161989859143828936829458165952828400164, 9165935848508742991123041194493068347432948316633061363176603127357564697306234665588022632617551347641185102125312266311129652796617950048157274913668679, 6912757871370794374759901997589605074226493501972635799793236946766821524908290368365912513348540457903178566606726114728171616871993006364721583312336887, 2772358871408923034204621091872889687103161284582841375111918524964785468908216158971069453667365119211725770870409337265995837333163410123525053082089580, 6531664151019280186382595159872895240102881355486532323279892668555049996916478827497573481450502154879542744087162142694981322426662903074730589843860960, 9055704922050122914443384736705521642055104764393302440373553116925338667314460578744271058293822649509688066559039295703018452427638892267180037727371742, 7791598555159613126365683288402838567793298287144986542345500368882444050010417502355424747873528002462959726445281049167575366743169599326793961618051359],[8137540905097035177186334621358919965466832408854971270841646763684663079487921641477979881153051908402004756665078795736103323586562318870290451121788907, 68549086908431586932633034238124978810462049984753844801754060656786824728574426436661735757482632126120220082795885233932017068142073939344806564617629, 232600438583031153974118817632093851886202886606773481638324970686487456565622608860387663503178419913832604285617032888718792893037809666902438443050215, 2730804246457584714798310013836867734292906688736534041023882104276874363859778262213250760084939399584836336623613743576408436477209982443905975722890270, 8968962402185864871730929722048876942660118497830342006727803375586728303489767027184361234468783912601795602241003117157944496320155983804283131270786230, 933275398962165429711839994606144540560644472545729251802642209632965366320431901574408640024862688478191960714471878570767501781995912231655805450973457, 6420396044080908523277585401016937108569865564116424330954979822643068742397432577328415490355197037733718008065429975054014971631437920529874821145416519, 8823200684251635080451723766861775681468161520224315568094289002718414900231495749307143970324900236208067801430028266026601107169079984226913420101781842],[9251446959825727715008485842347193004672519378966743136763974729435014151423724964094211437054748504091548804411509138132384691734697978090581976925005335, 2529761422168349910521788049907512201032759056986409073670965945024069516493427439109601385986881557414759186058814561452654969278983137443785218956680766, 3980251355731000356822984848017907469957058383727255521936865050660575861051949458574755497040510240623792134568440648235397156327318950638942773587324849, 7326265415789416694698318201493287125126308901526887030389775650117124347545469269908897851070788621890409390972723144498551783880294374045936609187923860, 5499588757378394548211376721120609331980894935240843357501852186662484036117296636482275139248456217062131274394657615588217101677166403780207395489439311, 9005084323225184203368271981357495667265443453212804737454792383513027202574813505785275358157826728506858751862249555897328515215811642965586057834979403,10994478046795590718182756328014543229456751211439708339544806304182045853549444441091672387131383527765701451281690984316339347435030699073374530320369898, 7862899886364559009131773043216623328658190308011694314605477767005128308783776698595916513638065233686460865363684920261577887103080021998836713849298525],[650055911007234685352784769005726834411849394064491142469930523496626024793814449643229740900196818609327693159924603708904005840541789480221954040213066, 2809661317636500610850397776121837483501232887758234469107848434335319471633847928623371181400860418199701936569876751444308713386218251733626262986492274, 9693211976843193406855410557441720940889859060150298172824743285358155086502916424335999240877094527770915057575139562568852839618781069535361965834231151, 2154538183017350102677480391641319415988248321335185132844836345176711470789459373438178668836866909037575305489811079179629882575003063809920547011673473, 9683422469808648003362511380944279760862302780715465044303860978693413808480139347587442353117050593226202476594449622823752816472358005627235312549207069, 6353355306575382008133604800656352131030399774978108071361980147620344012304509679502775219081589194614842510783979399183440815428483174609361000310009805, 9954511916173983779608341086089102264614679525033928734582532560643183013406618272373241965558341652654254516655074620743387372821595372186042865286176976, 5344443426733429315310874051973740316783157396146789626830556654028105615703627805003898129544483509422907139991285072444871842874284740446098650366452670],[2427787887177230026663625973701516878665227060964001682937225791304356156764341273255630820456923753213299228812993127900389124575172649820317133753887172, 8755094031646900202786405216763690544858903084676589007569601012325379022197813175059938821410476122548209727824903137466124229196960225456307813871635737,11534405890518352352649345966932578178829141744327349451919451846726194285931163678208720133009443549794157887115049075638937541343121404655178462831315019, 9266094507306291162088164653459352792751610294885461233454966712074455086997526359250100782905111196806581443719704908057589563104345364176955558221260626, 3938400564583162644569921638786836404385817891514382358806625756115129937487499401550971416225470555784210736545477878734228393030491576738831016310189433,11669296482390506406221654541712363653019303963396580186059433808894116792994364654998721780768342194760008037791605803639961718269378369893226393205832659, 3195767821043187203604744061334089138267639163020610884720872868940859235262889806991809597852056019604806751531158215875192416785493676738851841663652573, 1088812402716000767207889690871847575637569481816097482191510227990668178298918251780548145011592593815934971160538689647049289713583691658764954209517707],[8153096942899370412925799815589733002254656571840992296358702554727996034971737871217626501324848647964988137319614423210101223616802468188942904631259211, 4634587706147343284061898712007205232627609799585429287502593958861948023952265200969861861729303737801316359107664885077863929316425353033069966125658926, 2681575869342941217476838201386497490983933368026388400348969608697678128766987928766865591934770819728175841486632758069528267443509850525193839129892987, 5985531185826038677448813983353171114107736898140592134802453405834880712865520512087604224173013777856178588258434144466156027776072051312502416171860414, 6073422108057347544260880598847406906776086425730609238300360653916876391778075426694361432576203483309203002511578931011774427794727027881175141611482048, 9924292694539582863016820239279046740645528353350582112562701608554578883371871948040146857542955872923918754767147498316541609260806559360767459174207446, 8270807130853034520300987338813312097822630837965065031141103253854518174363354236287879919061654850239370699608336930219258013660234519258424952120735853, 2999891455984263967801041471548095508429573855139041602306462648079489777281346714061528391641076139769456927081295187666111905173951511905816846226333773]]# I = identity_matrix(IntegerModRing(p), 8)m2=matrix(IntegerModRing(q), m)phi_p=p^8-1phi_q=x*(x - 1)*(x + 1)* (x^2 + x + 1)* ((x^4 - 1)/((x + 1)*(x - 1)))* (x^4 + x^3 + x^2 + x + 1)* ((x^6 - 1)/((x^2 + x + 1)*(x + 1)*(x - 1)))* (x^6 + x^5 + x^4 + x^3 + x^2 + x + 1)* ((x^8 - 1)/(x^4 - 1))phi=phi_p*phi_qd = gmpy2.invert(e, int(phi))m=matrix(IntegerModRing(n), m)m2=pow(m,d)print(m2)#求flag：import numpym=[[68,65,83,67,84,70,123,49],[102,52,52,97,100,57,99,45],[97,51,100,50,45,52,102,54],[55,45,57,56,54,52,45,54],[55,53,52,54,98,49,51,102],[49,102,51,125,115,214,12,97],[244,240,95,234,180,230,226,9],[91,165,145,213,152,13,37,150]]m = numpy.array(m)flag=''for i in range(0,7):for j in range(0,7):flag=flag+chr(m[i,j])print(flag)
0x04 后记
更多专业知识可以访问大佬博客了解，多动手算一下也许理解会更深刻一点。
Reference
https://chenliang.org/2021/02/26/group-theory/
原文始发于微信公众号（宸极实验室）：『CTF』模 p 非奇异矩阵的群阶的计算
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论