[RSA1]P1

发现源码直接给我了p,q,e,c,那就很简单了，我们求出phi,N就可以通过inverse函数拿到phi的逆元d，这样就可以直接解出来明文了，代码如下

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *

p = 10554915510546378513140074459658086644656654144905337809416976066414771647836950941616441505897207397834928781511863699153349798682451297889979721668885951
q = 8246403321715011123191410826902524505032643184038566851264109473851746507405534573077909160292816825514872584170252311902322051822644609979417178306809223
e = 65537
c = 40005881669517895877352756665523238535105922590962714344556374248977905431683140065629966778249773228248201807844489945346731806741025157651474530811920115794270396320935022110691338083709019538562205165553541077855422953438117902279834449006455379382431883650004540282758907332683496655914597029545677184720
n = p*q

phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

[RSA1]P2

这次没有直接给我p和q，但是我们可以通过分解n得到
于是我们去yafu(真不如factordb)
最终代码如下

1
2
3
4
5
6
7
8
9
10
n = 7382582015733895208810490097582153009797420348201515356767397357174775587237553842395468027650317457503579404097373070312978350435795210286224491315941881
e = 65537
c = 6511001389892474870028836129813814173158254564777610289284056550272120510686249909340499673868720839756059423749304765055919251717618117507007046973023557
p = 70538125404512947763739093348083497980212021962975762144416432920656660487657
q = 104660876276442216612517835199819767034152013287345576481899196023866133215633

phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

[RSA1]P3

也是简单的一个分解

1
2
3
4
5
6
7
8
9
10
n = 53690629441472827148854210396580805205350972614395425306316047967905824330731
e = 65537
c = 22130296334673852790451396673112575082637108306697684532954477845025885087040
p = 193584665240506752994134779660255197091
q = 277349599849597463956171076348973750041

phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

[RSA1]P4

发现就是p-q过小问题，这里yafu集成了这种分解方法，所以我直接yafu一把嗦

1
2
3
4
5
6
7
8
9
10
11
p = 10753464577529272766954987635204502694646829328992120268238206697158857879611091921112122276180123366757978627222693360361364149654146518796988494299998729
q = 10753464577529272766954987635204502694646829328992120268238206697158857879611091921112122276180123366757978627222693360361364149654146518796988494299998033

e = 65537
c = 98161406745910866780822530171878255235776133393411573803496865047700715941955255328757920065032397556905095591171977170479344602512244671081108703687450560269408412671849929423399172588599903975793985819498354819305128607934552101433664794909855378636055525016664559476808490723554481335856183927702549281730

n = p*q
phi = (p-1)*(q-1)

d = inverse(e,phi)
print(long_to_bytes(pow(c,d,n)))

[RSA1]P5

还是yafu一把嗦

1
2
3
4
5
6
7
8
9
n = 148841588941490812589697505975986386226158446072049530534135525236572105309550985274214825612079495930267744452266230141871521931612761645600600201983605957650711248808703757693378777706453580124982526368706977258199152469200838211055230241296139605912607613807871432800586045262879581100319519318390454452117
e = 65537
c = 69038543593219231496623016705860610154255535760819426453485115089535439537440188692852514795648297200067103841434646958466720891016026061658602312900242658759575613625726750416539176437174502082858413122020981274672260498423684555063381678387696096811975800995242962853092582362805345713900308205654744774932
p = 12200065120379104459630695224710181907653841921369674962900093531339421658815375891425102591939094029941691738405035324548070063226677838530633694428729829
q = 12200065120379104459630695224710181907653841921369674962900093531339421658815305905822146210878434959851438079877557401145694064756239882458467901042367473

phi = (p-1)*(q-1)
d = inverse(e,phi)
print(long_to_bytes(pow(c,d,n)))

[RSA1]P6

共享素数攻击，这里的加密算法是

1
2
3
4
5
6
7
8
9
10
11
12
13
p1 = getPrime(512)
q = getPrime(512)
p2 = getPrime(512)

n1 = p1*q
n2 = p2*q

e = 65537

m = bytes_to_long(flag)
c1 = pow(m, e, n1)
c2 = pow(m, e, n2)

也就是我们可以通过gcd来算出我们的p1，因为n1和n2有相同的公因数p，而且加密了两次，所以我们只需要随便取一个解密即可，脚本如下

1
2
3
4
5
6
7
8
9
10
11
12
# 6 
n1 = 143348646254804947818644803938588739009782265465565896704788366218178523508874903492905378927641178487821742289009401873633609987818871281146199303052141439575438691652893995423962176259643151111739185844059243400387734688275416379337335777994990138009973618431459431410429980866760075387393812720247541406893
n2 = 138110854441015362783564250048191029327770295545362614687087481715680856350219966472039006526758450117969049316234863489558254565946242898336924686721846675826468588471046162610143748100096038583426519355288325214365299329095841907207926280081868726568947436076663762493891291276498567791697978693639037765169
e = 65537
c1 = 54957154834913405861345262613986460384513988240935244315981524013378872930144117440787175357956479768211180412158274730449811947349624843965933828130932856052315165316154486515277625404352272475136003785605985702495858150662789554694910771308456687676791434476722168247882078861234982509648037033827107552029
c2 = 122221335585005390437769701090707585780333874638519916373585594040154234166935881089609641995190534396533473702495240511296379249872039728112248708182969185010334637138777948970821974238214641235158623707766980447918480715835847907220219601467702961667091318910582445444058108454023108157805147341928089334736

p = gmpy2.gcd(n1,n2)
q1 = n1 // p
phi = (p-1)*(q1-1)
d = inverse(e,phi)
print(long_to_bytes(pow(c1,d,n1)))

[RSA1]P7

这里涉及到了多因子，我记得没错的话应该都是差不多的算法
好吧，看来我的记忆没问题

1
2
3
4
5
6
7
8
9
10
p = 10666139331774428325755287635566473140804481321882464031499529816800186578792308674238646794969384836340484775213796013129603472328582005363876462361316357
q = 8419311673449738061914489023962717718536471719688567807316495262754711350004888752049108347226115000749280146228195893953964759818878155006622123533942989
r = 12875078327453384158245832541544758526474680184252540739652077682353277702054275525591573258723948221345537075374635382175740236093131628077747126356403959
e = 65537
c = 424552463648937499189041230155623101311087334789253159440707211761796081289342164253743235182597460622581134089949035117444838205449163269030784233435435681797627188717450074808905561404960693227573181548281296514743775615606388692910356320667720308219275107443303501165027740512539959960217657836317351146520079753390346207659007421416917274795119021374032194294225350901136669304225010974617136606299060486198480556729770211945777266366417547752798441211059402

phi = (p-1)*(q-1)*(r-1)
n = p*q*r
d = inverse(e,phi)
print(long_to_bytes(pow(c,d,n)))

[RSA1]P8

加密脚本如下

1
2
3
4
5
6
7
8
9
p = getPrime(256)
q = getPrime(256)
n = (p**3) * q
e = 65537
phi = (p-1)*(q-1)

m = bytes_to_long(flag)

c = pow(m, e, n)

这里虽然是p的三次方，但是我们可以把它理解为多因子试试
但是

ϕ(n)=ϕ(p3)ϕ(q)\phi(n) = \phi(p^{3})\phi(q)

正确但是

ϕ(p3)=p2(p−1)\phi(p^{3}) = p^{2}(p-1)

这也就是我第一次没有做对的原因
所以直接进行一个公式的利用

[RSA1]P9

  • 又是一道多因子的题目，不同的是此处的𝑟=2𝑟𝑛⋅𝑒+1r=2rn​⋅e+1，这有什么特殊之处吗？
你可以尝试直接按照P7的exp来进行求解，会发现解出来的明文是乱码，或者你可以将代码中`inverse`函数替换为`gmpy2`中的`invert`函数（二者功能一样），你会发现得到了一个错误

`ZeroDivisionError: invert() no inverse exists`

提示逆元不存在，这是为什么，我们来看一下此时的𝑝ℎ𝑖phi是多少

𝑝ℎ𝑖=(𝑝−1)(𝑞−1)(𝑟−1)=(𝑝−1)(𝑞−1)⋅2𝑟𝑛⋅𝑒phi=(p−1)(q−1)(r−1)=(p−1)(q−1)⋅2rn​⋅e

然后我们可以发现𝑒e整除𝑝ℎ𝑖phi，所以他们二者是不互素的，不互素则逆元不存在，那为什么`inverse`函数还是能求解呢（虽然答案是错误的），其实我们可以打印一下使用`inverse`函数输出的𝑑d，会发现𝑑=1d=1，他并没有进行数据校验，而是会`1`。

  • 那么此时我们该如何解决这个RSA问题，逆元不存在这说明对应的私钥不存在，难道是不可解了吗？

    答案是否定的，我们可以考虑flag比较短，则flag转为数字后的数𝑚m足够小，则有

    𝑚  𝑝𝑞≡𝑚  𝑛mmodpq≡mmodn

    什么意思呢，也就是说𝑚m不仅比𝑛n（这里的𝑛=𝑝𝑞𝑟n=pqr）还小也比𝑝𝑞pq还小，所以取模得到的结果也相同，那么此时有，设

    𝑐1=𝑐  𝑝𝑞=(𝑚𝑒  𝑛)  𝑝𝑞=𝑚𝑒  𝑝𝑞𝑒𝑑1≡1(mod𝜑(𝑝𝑞))𝑐1𝑑1≡𝑚(mod𝑝𝑞)c1​=cmodpq=(memodn)modpq=memodpqed1​≡1(modφ(pq))c1d1​​≡m(modpq)

    即𝑐1c1​为𝑐c再模𝑝𝑞pq的结果，根据模的性质有𝑐1c1​便是消息使用公钥(𝑝𝑞,𝑒)(pq,e)加密的结果，那么此时我们可以求出该公钥对应的私钥进行解密，得到𝑚  𝑝𝑞mmodpq的结果，又因为𝑚m比较小，所以该结果直接就是𝑚m。

    在实际计算中，我们其实并不需要额外写一句c1 = c % (p*q)，因为根据模的性质，只要最后进行了模运算即可。

  • 其实通俗一点的理解就是当𝑚m比较小时，此时就算公钥对应的私钥不存在（逆元不存在），我们可以考虑将公钥转化为其他公钥（用原公钥因子进行重组）再尝试求解私钥进行解密，依然可以得到正确结果。

    这里其实也就解释了为什么P7，P8需要加上大量字符串的填充，就是为了防止使用该方法直接解出，在现实世界的RSA算法应用标准中，明文其实都会用特定算法进行填充来防止这种情况出现。
    脚本如下

1
2
3
4
5
6
7
8
9
10
11
12
13
# 9 
p = 7478755670255767435237487693415479182290330775502792675052667363676831056436638619069277770540533350723045234676443621124912287506103439704868369839725279
q = 9232828888049557325429111621080998490274442347556398052322580869768941301413255711626092627273543579067597113958627672298942570149816938335701615759283713
r = 102909133680612532601801231903654039
e = 65537
c = 142893174944324070830219394465469685943669308818639857030565389839224452373848570577201378981080333784852764502832587008270072323948511579823852437852643609820245476634896477031076952735298279618952398460203032125853063235638358942643559551563899381032067185778629120272032518475352761100115057449043142848203976076694124978394099839339406197

n = p*q*r
phi = (p-1)*(q-1)
d = inverse(e, phi)
m = pow(c, d, p*q)

print(long_to_bytes(m))

[RSA1]P10

一个典型的e和phi不互素的问题
脚本如下

1
2
3
4
5
6
7
8
9
10
11
12
13
# 9
p = 9927950299160071928293508814174740578824022211226572614475267385787727188317224760986347883270504573953862618573051241506246884352854313099453586586022059
q = 9606476151905841036013578452822151891782938033700390347379468858357928877640534612459734825681004415976431665670102068256547092636766287603818164456689343
e = 131074
c = 68145285629092005589126591120307889109483909395989426479108244531402455690717006058397784318664114589567149811644664654952286387794458474073250495807456996723468838094551501146672038892183058042546944692051403972876692350946611736455784779361761930869993818138259781995078436790236277196516800834433299672560
n = p*q
phi = (p-1)*(q-1)
_gcd = gmpy2.gcd(e, phi)
d = gmpy2.invert(e//_gcd, phi)
m_gcd = gmpy2.powmod(c, d, n)
m = gmpy2.iroot(m_gcd, _gcd)    # 得到元组 (mpz(1920535408007397829480400151650246901210634018403879187581), True)
flag = libnum.n2s(int(m[0]))
print(flag)