做网站如何挂支付系统,wordpress模板代码分析,上海协策网站制作,做设计有必要买素材网站会员1.rsa256
下载文件#xff0c;解压得到4个文件#xff0c;打开message后缀文件里面都是乱码。打开public.key#xff0c;观察其格式明显是openssl的公钥文件#xff0c;再根据题目提示可知#xff0c;我们拿到的message后缀文件是由该公钥rsa加密得到的#xff0c;用ope…1.rsa256
下载文件解压得到4个文件打开message后缀文件里面都是乱码。打开public.key观察其格式明显是openssl的公钥文件再根据题目提示可知我们拿到的message后缀文件是由该公钥rsa加密得到的用openssl命令获取public.key中的n和e发现n并不是很大可以用msieve分解得到pq。这样我们就可已得到d用n,d对密文解密将得到的16进制通过ascii转为字符输出注意里面存在不可输出字符直接输出有可能截断字符串导致输出不完整
import sys
import os
import gmpy2
def shuchu(mingwenstr):if mingwenstr[len(mingwenstr)-1]L:mingwenstrmingwenstr[2:len(mingwenstr)-1]else:mingwenstrmingwenstr[2:len(mingwenstr)]if not len(mingwenstr)%20:mingwenstr0mingwenstrilen(mingwenstr)mingwenwhile i1:str1mingwenstr[i-2:i]if int(str1,16)33 and int(str1,16)126:mingwenchr(int(str1,16))mingwenelse :mingwen mingwenii-2print mingwen
p302825536744096741518546212761194311477
q325045504186436346209877301320131277983
e65537
np*q
dint(gmpy2.invert(e,(p-1)*(q-1)))
with open(encrypted.message1 , rb) as f:sf.read()miwenlong(s.encode(hex),16)mingwenintpow(miwen,d,n)mingwenstrhex(mingwenint)shuchu(mingwenstr)
with open(encrypted.message2 , rb) as f:sf.read()miwenlong(s.encode(hex),16)mingwenintpow(miwen,d,n)mingwenstrhex(mingwenint)shuchu(mingwenstr)
with open(encrypted.message3 , rb) as f:sf.read()miwenlong(s.encode(hex),16)mingwenintpow(miwen,d,n)mingwenstrhex(mingwenint)shuchu(mingwenstr)
对结果观察即可获取明文
2.RSA
打开文件即可看到necn比较长可放入yafu进行分解得到pq。即可得到d对c解密输出即可
import gmpy2
def shuchu(mingwenstr):if mingwenstr[len(mingwenstr)-1]L:mingwenstrmingwenstr[2:len(mingwenstr)-1]else:mingwenstrmingwenstr[2:len(mingwenstr)]if not len(mingwenstr)%20:mingwenstr0mingwenstrilen(mingwenstr)mingwenwhile i1:str1mingwenstr[i-2:i]if int(str1,16)33 and int(str1,16)126:mingwenchr(int(str1,16))mingwenelse :mingwen mingwenii-2print mingwen
p31093551302922880999883020803665536616272147022877428745314830867519351013248914244880101094365815998050115415308439610066700139164376274980650005150267949853671653233491784289493988946869396093730966325659249796545878080119206283512342980854475734097108975670778836003822789405498941374798016753689377992355122774401780930185598458240894362246194248623911382284169677595864501475308194644140602272961699230282993020507668939980205079239221924230430230318076991507619960330144745307022538024878444458717587446601559546292026245318907293584609320115374632235270795633933755350928537598242214216674496409625928997877221
q31093551302922880999883020803665536616272147022877428745314830867519351013248914244880101094365815998050115415308439610066700139164376274980650005150267949853671653233491784289493988946869396093730966325659249796545878080119206283512342980854475734097108975670778836003822789405498941374798016753689377992355122774401780930185598458240894362246194248623911382284169677595864501475308194644140602272961699230282993020507668939980205079239221924230430230318076991507619960330144745307022538024878444458717587446601559546292026245318907293584609320115374632235270795633933755350928537598242214216674496409625928797450473
e65537
np*q
dint(gmpy2.invert(e,(p-1)*(q-1)))
c168502910088858295634315070244377409556567637139736308082186369003227771936407321783557795624279162162305200436446903976385948677897665466290852769877562167487142385308027341639816401055081820497002018908896202860342391029082581621987305533097386652183849657065952062433988387640990383623264405525144003500286531262674315900537001845043225363148359766771033899680111076181672797077410584747509581932045540801777738548872747597899965366950827505529432483779821158152928899947837196391555666165486441878183288008753561108995715961920472927844877569855940505148843530998878113722830427807926679324241141182238903567682042410145345551889442158895157875798990903715105782682083886461661307063583447696168828687126956147955886493383805513557604179029050981678755054945607866353195793654108403939242723861651919152369923904002966873994811826391080318146260416978499377182540684409790357257490816203138499369634490897553227763563553981246891677613446390134477832143175248992161641698011195968792105201847976082322786623390242470226740685822218140263182024226228692159380557661591633072091945077334191987860262448385123599459647228562137369178069072804498049463136233856337817385977990145571042231795332995523988174895432819872832170029690848
mingwenintpow(c,d,n)
mingwenstrhex(mingwenint)
shuchu(mingwenstr)
3.RSA?
打开文件发现e1有rsa加密原理可知这里大概率mc直接将c转为字符获得答案
4.RSA
打开文件发现已知d那么直接使用密钥解密即可
5.RSA2
和RSA基本一样打开文件即可看到necn比较长可放入yafu进行分解得到pq。即可得到d对c解密输出即可
import gmpy2
def shuchu(mingwenstr):if mingwenstr[len(mingwenstr)-1]L:mingwenstrmingwenstr[2:len(mingwenstr)-1]else:mingwenstrmingwenstr[2:len(mingwenstr)]if not len(mingwenstr)%20:mingwenstr0mingwenstrilen(mingwenstr)mingwenwhile i1:str1mingwenstr[i-2:i]if int(str1,16)33 and int(str1,16)126:mingwenchr(int(str1,16))mingwenelse :mingwen mingwenii-2print mingwen
p57970027
q518629368090170828331048663550229634444384299751272939077168648935075604180676006392464524953128293842996441022771890719731811852948684950388211907532651941639114462313594608747413310447500790775078081191686616804987790818396104388332734677935684723647108960882771460341293023764117182393730838418468480006985768382115446225422781116531906323045161803441960506496275763429558238732127362521949515590606221409745127192859630468854653290302491063292735496286233738504010613373838035073995140744724948933839238851600638652315655508861728439180988253324943039367876070687033249730660337593825389358874152757864093
e65537
np*q
dint(gmpy2.invert(e,(p-1)*(q-1)))
c0x3dbf00a02f924a70f44bdd69e73c46241e9f036bfa49a0c92659d8eb0fe47e42068eaf156a9b3ee81651bc0576a91ffed48610c158dc8d2fb1719c7242704f0d965f8798304925a322c121904b91e5fc5eb3dc960b03eb8635be53b995217d4c317126e0ec6e9a9acfd5d915265634a22a612de962cfaa2e0443b78bdf841ff901423ef765e3d98b38bcce114fede1f13e223b9bd8155e913c8670d8b85b1f3bcb99353053cdb4aef1bf16fa74fd81e42325209c0953a694636c0ce0a19949f343dc229b2b7d80c3c43ebe80e89cbe3a3f7c867fd7cee06943886b0718a4a3584c9d9f9a66c9de29fda7cfee30ad3db061981855555eeac01940b1924eb4c301
miwenint(c,16)
mingwenintpow(miwen,d,n)
mingwenstrhex(mingwenint)
shuchu(mingwenstr)
6.medium RSA
下载文件解压得到一个enc文件一个pem文件而enc文件并不是数据包文件用文本文件打开发现乱码而pem文件时openssl的公钥文件根据题目可知enc文件时用RSA公钥文件pem加密得到的密钥文件用openssl获取pem文件中的ne发现n不太大可放入msieve进行分解得到pq。即可得到d对enc文件解密输出即可
import sys
import os
import gmpy2
def shuchu(mingwenstr):if mingwenstr[len(mingwenstr)-1]L:mingwenstrmingwenstr[2:len(mingwenstr)-1]else:mingwenstrmingwenstr[2:len(mingwenstr)]if not len(mingwenstr)%20:mingwenstr0mingwenstrilen(mingwenstr)mingwenwhile i1:str1mingwenstr[i-2:i]if int(str1,16)33 and int(str1,16)126:mingwenchr(int(str1,16))mingwenelse :mingwen mingwenii-2print mingwen
p275127860351348928173285174381581152299
q319576316814478949870590164193048041239
e65537
np*q
dint(gmpy2.invert(e,(p-1)*(q-1)))
with open(flag.enc , rb) as f:sf.read()miwenlong(s.encode(hex),16)mingwenintpow(miwen,d,n)mingwenstrhex(mingwenint)shuchu(mingwenstr)
7.hard RSA
与medium RSA相似下载文件解压又得到一个enc文件一个pem文件且enc文件并不是数据包文件而pem文件时openssl的公钥文件根据题目可知enc文件时用RSA公钥文件pem加密得到的密钥文件用openssl获取pem文件中的nen与medium RSA的n相同却发现这里的e2。当e为2时与n的欧拉函数不再互质无法求出d无法再用正常的RSA解密方式来解密。但这里n依旧可以分解为两个素数pq且p%43q%43这里我们有Toelli-shanks算法的直接结论使用对于给定c和p当p%43当(m^2)cmodp的解有m(c^((p1)/4))modp或m-(c^((p1)/4))modp即m((c^(1/2))modp)的解在根据中国剩余定理将模p的解mp和模q的解mq组合为模n的解这种加解密成为rabin加解密这里会出现四个解根据欧几里得扩展原理获得yp*mpyq*mq1
r(yp*p*mqyq*q*mp)modn
-rn-r
s(yp*p*mq-yq*q*mp)modn
-sn-s
即可得到结果 import gmpy2
import libnum
def shuchu(mingwenstr):mingwenstrmingwenstr[2:len(mingwenstr)-1]if not len(mingwenstr)%20:mingwenstr0mingwenstrilen(mingwenstr)mingwenwhile i1:str1mingwenstr[i-2:i]if int(str1,16)33 and int(str1,16)126:mingwenchr(int(str1,16))mingwenelse :mingwen mingwenii-2print mingwenp275127860351348928173285174381581152299
q319576316814478949870590164193048041239
np*q
fopen(flag.enc,r)
sf.read()
f.close()
clong(s.encode(hex),16)
#获得c^(1/2)modp,q的解
rpow(c,(p1)/4,p)
spow(c,(q1)/4,q)
#使用中国定理组合解
pniint(gmpy2.invert(p,q))
qniint(gmpy2.invert(q,p))
a(s*p*pnir*q*qni)%n
a1n-a
b(s*p*pni-r*q*qni)%n
b1n-b
shuchu(hex(a))
shuchu(hex(a1))
shuchu(hex(b))
shuchu(hex(b1))
8.very hard RSA
下载文件解压又得到两个enc文件一个py文件首先打开py文件阅读加密算法可知这一次是分别使用RSA公钥Ne1和Ne2对相同密文加密可以使用RSA共模攻击破解密文
import gmpy2
#在a,b较小时可用这种欧几里得扩展
def egcd(a, b):if a 0:return (b, 0, 1)else:g, y, x egcd(b % a, a)return (g, x - (b // a) * y, y)
def shuchu(mingwenstr):if mingwenstr[len(mingwenstr)-1]L:mingwenstrmingwenstr[2:len(mingwenstr)-1]else:mingwenstrmingwenstr[2:len(mingwenstr)]if not len(mingwenstr)%20:mingwenstr0mingwenstrilen(mingwenstr)mingwenwhile i1:str1mingwenstr[i-2:i]if int(str1,16)33 and int(str1,16)126:mingwenchr(int(str1,16))mingwenelse :mingwen mingwenii-2print mingwenn0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929
e117
e265537
g,s1,s2egcd(e1, e2)
fo1 open(flag.enc1,rb)
fo2 open(flag.enc2,rb)
data1 fo1.read()
data2 fo2.read()
fo1.close()
fo2.close()
c1 int(data1.encode(hex),16)
c2 int(data2.encode(hex),16)
if s10:c1int(gmpy2.invert(c1,n))s1-s1
if s20:c2int(gmpy2.invert(c2,n))s2-s2
miwenint(pow(c1,s1,n)*pow(c2,s2,n))%n
shuchu(hex(miwenint))
9.Round Rabins!
已知此题是rabin解密在hard RSA已经提到如何解密发现n较长放在yafu中分解结果发现n是一个平方数这样正常的rabin解密无法解密此题中国剩余定理要求分解得到的因子互素此时问题变成了如何求解m(c^(1/2))%(p^2)(其中np^2)。我们可以根据Toelli-shanks算法在hard RSA已经提到求出m(c^(1/2))mod(p)此时问题变为如何通过m(c^(1/2))mod(p)得到x(c^(1/2))mod(p^2)我们假定mps(c^(1/2))mod(p^2)那么(mps)^2cmod(p^2)即m^22*m*p*s(p^2)*(s^2)cmod(p^2)所以m^22*m*p*scmod(p^2)2*m*p*s(c-m^2)mod(p^2)。我们已知m^2cmod(p)即c-m^2可整除p所以s((c-m^2)/(2*m*p))modp(简单说明当mpnpmod(p^2)则((m-n)*p)%(p^2)0要是等式成立一定有m-nkp即mnmodp)那么mps(mp*((c-m^2)/(2*m*p)))即mps(m((c-m^2)/(2*m)))即(c^(1/2))mod(p^2)的解为x(m(c-m^2/(2*m)))mod(p^2)这里只是简单的完成了Hensels lemma 的事想知到详情可查看原定理,根据此原理可解出密文
import gmpy2
import libnum
def legendre_symbol(a, p):ls pow(a, (p - 1)/2, p)if ls p - 1:return -1return ls
def prime_mod_sqrt(a, p):a % pif a 0:return [0]if p 2:return [a]if legendre_symbol(a, p) ! 1:return []if p % 4 3:x pow(a, (p 1)/4, p)return [x, p-x]q, s p - 1, 0while q % 2 0:s 1q // 2z 1while legendre_symbol(z, p) ! -1:z 1c pow(z, q, p)x pow(a, (q 1)/2, p)t pow(a, q, p)m swhile t ! 1:i, e 0, 2for i in xrange(1, m):if pow(t, e, p) 1:breake * 2b pow(c, 2**(m - i - 1), p)x (x * b) % pt (t * b * b) % pc (b * b) % pm ireturn [x, p-x]
def egcd(a, b):if a 0:return (b, 0, 1)else:g, y, x egcd(b % a, a)return (g, x - (b // a) * y, y)
def modinv(a, m):g, x, y egcd(a, m)if g ! 1:raise Exception(modular inverse does not exist)else:return x % m
# This finds a solution for c x^2 (mod p^2)
def find_solution(c, p):n p ** 2r prime_mod_sqrt(c,p)[0]inverse_2_mod_n modinv(2, n)inverse_r_mod_n modinv(r, n)new_r r - inverse_2_mod_n * (r - c * inverse_r_mod_n)return new_r % nif __name__ __main__:n 0x6b612825bd7972986b4c0ccb8ccb2fbcd25fffbadd57350d713f73b1e51ba9fc4a6ae862475efa3c9fe7dfb4c89b4f92e925ce8e8eb8af1c40c15d2d99ca61fcb018ad92656a738c8ecf95413aa63d1262325ae70530b964437a9f9b03efd90fb1effc5bfd60153abc5c5852f437d748d91935d20626e18cbffa24459d786601Lp 0xa5cc6d4e9f6a893c148c6993e1956968c93d9609ed70d8366e3bdf300b78d712e79c5425ffd8d480afcefc71b50d85e0914609af240c981c438acd1dcb27b301Lc 0xd9d6345f4f961790abb7830d367bede431f91112d11aabe1ed311c7710f43b9b0d5331f71a1fccbfca71f739ee5be42c16c6b4de2a9cbee1d827878083acc04247c6e678d075520ec727ef047ed55457ba794cf1d650cbed5b12508a65d36e6bf729b2b13feb5ce3409d6116a97abcd3c44f136a5befcb434e934da16808b0bLsolution find_solution(c, p)print hex(solution)[2:-1].decode(hex)10.RSA-5
n0x78e2e04bdc50ea0b297fe9228f825543f2ee0ed4c0ad94b6198b672c3b005408fd8330c36f55d36fb129d308c23e5cb8f4d61aa7b058c23607cef83d63c4ed0f066fc0b3c0062a2ac68c75ca8035b3bd7a320bdf29cfcf6cc30377743d2a8cc29f7c588b8043412366ab69ec824309cb1ef3851d4fb14a1f0a58e4a1193f5518fa1d0c159621e1f832b474182593db2352ef05101bf367865ad26efe14fce977e9e48d3310a18b67991958d1a01bd0f3276a669866f4deaef2a68bfaefd35fe2ba5023a22c32ae8b2979c26923ee3f855363f18d8d58bb1bc3b7f585c9d9f6618c727f0f7b9e6f32af2864a77402803011874ed2c65545ced72b183f5c55d4d1 e0x10001 nextprime(p)*nextprime(q)0x78e2e04bdc50ea0b297fe9228f825543f2ee0ed4c0ad94b6198b672c3b005408fd8330c36f55d36fb129d308c23e5cb8f4d61aa7b058c23607cef83d63c4ed0f066fc0b3c0062a2ac68c75ca8035b3bd7a320bdf29cfcf6cc30377743d2a8cc29f7c588b8043412366ab69ec824309cb1ef3851d4fb14a1f0a58e4a1193f5a58ee70a59ac06b64dbe04b876ff69436b78cf03371f2062707897bf4e580870e42b5e62709b69f6d4939ac5641ea0f29de44aaee8f2fcd0f66aaa720b584f7c801e52ce7cd41db45ceb99ebd7b51bef8d0cd2deb5c50b59f168276c9c98d46a1c37bd3d6ef81f2c6e89028680a172e00d92dd8b392135112dd16efab57d00b26b9 c0x1c3588ac81ec3d1b439cfd2d5e6e8a5a95c8f95aaeff1b0ba49276ade80435323f307a17006ae2ffb4ca321e54387d9b33ed7ccda3117f7bc8d247ffd2ccdd67b7e2aad3d908d0a5187a73d13d532c1cf41758e2743bd4359bf72a99bbf0d716bb171cf636bd56acee9551cbb8af25f32583facbd25aed232659d24580c5a30a080e2860790a65422f7c442559c3042d37fdd7e8c1dd604252a2cbff8c74e5a0b6a0dfb9dcfed9eed515705ab9214dcf2dabce7b354040940613d065918079b3197da948b6d1d7daccc417069f7102fd2525e879fe69b6d5fb39e1dd6c0a9a9087dcc809294d7774efb42829f6124dff4af44f308977d1f91422c63073176026 在这里我们假设nextprime(p)*nextprime(q)(px)*(qy)并设nextprime(p)*nextprime(q)n1p*qn2将q替换掉即可得到y*(p^2)(x*yn2-n1)pn2*x0这是一个一元二次方程所以直接对xy进行爆破直接用公式求解即可得到p代码如下
import gmpy2
n20x78e2e04bdc50ea0b297fe9228f825543f2ee0ed4c0ad94b6198b672c3b005408fd8330c36f55d36fb129d308c23e5cb8f4d61aa7b058c23607cef83d63c4ed0f066fc0b3c0062a2ac68c75ca8035b3bd7a320bdf29cfcf6cc30377743d2a8cc29f7c588b8043412366ab69ec824309cb1ef3851d4fb14a1f0a58e4a1193f5518fa1d0c159621e1f832b474182593db2352ef05101bf367865ad26efe14fce977e9e48d3310a18b67991958d1a01bd0f3276a669866f4deaef2a68bfaefd35fe2ba5023a22c32ae8b2979c26923ee3f855363f18d8d58bb1bc3b7f585c9d9f6618c727f0f7b9e6f32af2864a77402803011874ed2c65545ced72b183f5c55d4d1
e0x10001
n10x78e2e04bdc50ea0b297fe9228f825543f2ee0ed4c0ad94b6198b672c3b005408fd8330c36f55d36fb129d308c23e5cb8f4d61aa7b058c23607cef83d63c4ed0f066fc0b3c0062a2ac68c75ca8035b3bd7a320bdf29cfcf6cc30377743d2a8cc29f7c588b8043412366ab69ec824309cb1ef3851d4fb14a1f0a58e4a1193f5a58ee70a59ac06b64dbe04b876ff69436b78cf03371f2062707897bf4e580870e42b5e62709b69f6d4939ac5641ea0f29de44aaee8f2fcd0f66aaa720b584f7c801e52ce7cd41db45ceb99ebd7b51bef8d0cd2deb5c50b59f168276c9c98d46a1c37bd3d6ef81f2c6e89028680a172e00d92dd8b392135112dd16efab57d00b26b9
c0x1c3588ac81ec3d1b439cfd2d5e6e8a5a95c8f95aaeff1b0ba49276ade80435323f307a17006ae2ffb4ca321e54387d9b33ed7ccda3117f7bc8d247ffd2ccdd67b7e2aad3d908d0a5187a73d13d532c1cf41758e2743bd4359bf72a99bbf0d716bb171cf636bd56acee9551cbb8af25f32583facbd25aed232659d24580c5a30a080e2860790a65422f7c442559c3042d37fdd7e8c1dd604252a2cbff8c74e5a0b6a0dfb9dcfed9eed515705ab9214dcf2dabce7b354040940613d065918079b3197da948b6d1d7daccc417069f7102fd2525e879fe69b6d5fb39e1dd6c0a9a9087dcc809294d7774efb42829f6124dff4af44f308977d1f91422c63073176026
p114791494681514143990268371423282183138226784645868909558224024738011633713833580549522009721245299751435183564384247261418984397745114977301564583085777881485180217075670585703780063072373569054286277474670485124459902688373648390826470893613150198411843162021692225644621249349903453125961550887837378298881
q132940802289018336261987415312533953042764596984032548157327529495089307889127354914528507277209940457450746338751400025568015673025956762534143027257695791611900765053802453566263676389771478041671317414828940200119172760057249923066534954345956113954028278683477795444749575874548525999126508093286460575953
def qiugen(a,b,c):gagmpy2.mpz(a)gbgmpy2.mpz(b)gcgmpy2.mpz(c)delatgb**2-4*ga*gcif delat0 or ga0:return 0degmpy2.iroot(delat,2)if de[1]:x1(de[0]-gb)/(2*ga)x2(-de[0]-gb)/(2*ga)if x10 and n2%x10:return x1if x20 and n2%x20:return x2return 0
for x in xrange(0,1500):for y in xrange(1,1500):aybx*yn2-n1cn2*xif not qiugen(a,b,c)0:pqiugen(a,b,c)qn2/pprint p,qdef shuchu(mingwenstr):if mingwenstr[len(mingwenstr)-1]L:mingwenstrmingwenstr[2:len(mingwenstr)-1]else:mingwenstrmingwenstr[2:len(mingwenstr)]if not len(mingwenstr)%20:mingwenstr0mingwenstrilen(mingwenstr)mingwenwhile i1:str1mingwenstr[i-2:i]if int(str1,16)33 and int(str1,16)126:mingwenchr(int(str1,16))mingwenelse :mingwen mingwenii-2print mingwen
dgmpy2.invert(e,(p-1)*(q-1))
mingwenpow(c,d,n1)
mingwenhexhex(mingwen)
print mingwenhex
shuchu(mingwenhex)11.HCTF2016-Crypto so interesting
题目不难观察代码发现这里随机生成RSA的pq然后随机生成一个比较小的u求u对phi_n求逆得到t再求t对bt求逆获得e最后求e对phi_n求逆得到d用e对明文加密解这道题并不难已知en先用e对bt求逆获得t由于u比较小这里可以使用wiener攻击获得uphi_n以及pq直接可以求解d对密文进行解密这里的重点是里面使用wiener攻击的代码有利于我们理解对rsa的wiener攻击
import libnum
import gmpy2
def pi_b(x):bt 536380958350616057242691418634880594502192106332317228051967064327642091297687630174183636288378234177476435270519631690543765125295554448698898712393467267006465045949611180821007306678935181142803069337672948471202242891010188677287454504933695082327796243976863378333980923047411230913909715527759877351702062345876337256220760223926254773346698839492268265110546383782370744599490250832085044856878026833181982756791595730336514399767134613980006467147592898197961789187070786602534602178082726728869941829230655559180178594489856595304902790182697751195581218334712892008282605180395912026326384913562290014629187579128041030500771670510157597682826798117937852656884106597180126028398398087318119586692935386069677459788971114075941533740462978961436933215446347246886948166247617422293043364968298176007659058279518552847235689217185712791081965260495815179909242072310545078116020998113413517429654328367707069941427368374644442366092232916196726067387582032505389946398237261580350780769275427857010543262176468343294217258086275244086292475394366278211528621216522312552812343261375050388129743012932727654986046774759567950981007877856194574274373776538888953502272879816420369255752871177234736347325263320696917012616273Lreturn libnum.invmod(x, bt)
def isqrt(n):x ny (x 1) // 2while y x:x yy (x n // x) // 2if pow(x, 2) n:return xelse:return False
def con_fra(a, b):r []while True:if a 1:breaktmp a/bif tmp ! 0:r.append(tmp)a, b b, (a-tmp*b)return rdef wiener_attack(e, n):cf con_fra(e, n)for x in xrange(len(cf)):k, d 0, 1while x 0:k, d d, d*cf[x] kx - 1# print k: %s\nd: %s\n %(k, d)phi_n (e*d - 1)/kB n - phi_n 1C ndt pow(B, 2) - 4*C # b^2 - 4*a*cif dt 0 and isqrt(dt) and (Bisqrt(dt)) % 2 0:print phi_n: , hex(phi_n)print p,hex((Bisqrt(dt)) / 2)print q,hex((B-isqrt(dt)) / 2)return phi_nprint wiener attack fail!n0x763b60d8a9bc44d609847cf9ccb2642d519e9699f13d0242767b30ec151552a4daaf02929a606cb9ad6e974ff38ea33a54ec0f12b898087b47219957f44899470069068ba7fddf82698d95a54ca577d8b19069dc1e5578cef2e7b1883601305e649abce142106099d104d218ef2300be53addee9d0ed3dafbc9e00d16a1f7cd0c30b0f26829433d4429cda5f7c68ab3ac01991b91b8b4553e514b43058474ac60f88376b903dfce3c826c3a9bac4c39e357bf71e2afa0e3766c4794ac22e3816fa3549854a0aef329352b6bcb5d5a65eb10aa0d8d0734351e4d992b55c6bf40ad618057fc836baabc822133faa305f9abc48119c7f18703d07f4f1568fc5a270368bee9315bc3aa092665be4c0d23a722911f384c16b990275ed299e4e13156368285319945adc2d42a132d2a38b64c64e007a79d1428c827f828b57fad542b0c49774ebd68f3a2bd14fa0cb1ab521320120ba596760e6f6a64296f1d3b140686a8ce536c088609e885d3e57f82f6e50b0eb68e30f7cad77a060863b6fe8c981fa049d785bddc1170aa58001a835ff73105cab477ebe820d52929bcb1971a7502bdfc75f3b94a90a66fbf22d79dd613b0262240b9e3f5fbe50e1e508b3fcebeb8a04eedab6d28f926756e4b2e4eb8896bd272b65d362661b3bf012f85df72820cf281e6151aa3bd178fa4c3bb9a619c3a82c3b70570247ed7bf620387df077f3
e0x38df4b9719a20d237ea83a24394cd54b0470a22ed2705b4b8b74adc67a8302fdf89296d7daa2b02163bac22384bdf0d396406a90259c3b15c1ceeb0a86266f686e3800bd43b42effb7b127b296bed09882bfd9c95a76d2ca02a4f551b323bd3929a813250e0682545ecfb8a21ef0dfbf7996942948194c3101fba32f0ffb6bef4172efd5563b13a13ed0a367cd6c1cefb278cfee225f285ed646ccb4b87ef5812d11669468ed71fd67a19b5a66b35ef4fce5399515b2b221367b35f5e4966e32696bf5debdb7d4df8a93ec47b6958ac0a193484eb40712a4c19216c67c9cb5585b64eb7d460f00585863b765584d382d716ae2e2269787d831bbd5e6d76ba48b51bb8fa8f4e9fb22e944a744958fd5429b3c647ceef521625f958d7ae631c149bed37f4c4a78e2c1e7ccd187b21f2edc5f1a3a93eb8625b9cc0b879c6a371d0c4c41667db838fe64e3ed2e41d0eb34e59b7c456619d4690a20584dc68f0d0b90827829389eabc6429f7a513cef2ee66c475fd3466204b75424cb6016c2211befc3535e2c8f42e11d3ba5e0be083974d9ed6ba4ac6deab7f9eaa4b9202112b2643ffe77da82dc6d0990fac9e92fa53999053fe7aa008a692e8cbbb6b33b9608dcc84fc7b80fe4109b8b74b3d29f79544ae782baa9f44115f2ae28e382e057b126313a14032b71bba3d58e646e6628bd9ac2984215573263b84926b21f64555ae7
flag0x2df4647e8a965e64defe9a4746827d467ab439330641bb98ccd6300ad2c7566763fb19f40eb012aa216b6868216f8e8ec36284c4438679a17a1a9cdb21b35a1198a0b8c277deea0c0a173975e98e267da34fe04ba75601aa54a1bc4086ae5b939a26088f72872c309c254ac7113e0d6770456a6ee8057d3adf9054a5ba4997a95bf63f03e9a8032630b26165c7730cb7cce800a811ce841cf81b7c97607e43267a1ff1a168f6142c93db14ff6c7b53c260c0807b710cf5de457ec890d1e417670a47ade2f19ae2b72bc5dd18617dcd42e84cbcb59b7a5a5598eb5911658a8fcdda680993081bc86146c2405179acaf28534e644e62930aa5b77048cabeae4e6e8b436b94e356ec5bcbd2388948d8e3c050016a8a3385ccf1614155ebbd67a3878b34c4bc16242de85a52309f6c15f1d2e443fac9e492bb0aaa4da18c7eaa56888711c5c8cdb484eb5e098b7975bfa991043cf21a8c8eb756331b3a46fecb9e3a055cd589dd1bd0686465b96e03327f41d7bd6cc132b9b3e329a435cea81b4759f055ed0c8070013a1e65c1c7601e25b0f3f2407f861a968e8b78bd191ce9f03fc98a12ca5e6be0e9eda2ccabf18fba8cac402252b01b8bc22f50b5554231bd9c0346c270a4148e9af29256b5755d668e77128e6fd35e77a2e822565dd484c1382f9ebe29e88e88550902f6438f46c178ee1ad924bffc1ac9b9f0a8a624d2a3b2
tpi_b(e)
wiener_attack(t,n)
12.HCTF2016-Crypto so cool
题目随机生成了p和q_t相乘获得n_t取n_t的左边1024/16部分和右边(5*1024)/8部分作为n的左边1024/16部分和右边(5*1024)/16部分再选择p的左边(5*1024)/16部分做des加密放入n的中间qn/p如q为偶数则q1若q不是素数将异或一个长为1024/16的随机数做异或直至q变为素数np*q随机生成e2对明文加密。我们获得nee2c。我们可以先将n中有关p的部分取出再使用Coppersmith partial information attack算法还原p根据nep即可对c进行解密
from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long, isPrime, size
from Crypto.Cipher import DES
from libnum import gcd, invmod
from hashlib import sha512
import signal
import random
import gmpy2
key abcdefg1
k 2048
def get_bit(number, n_bit, dire):dire:1: left0: rightif dire:sn size(number)if sn % 8 ! 0:sn (8 - sn % 8)return number (sn-n_bit)else:return number (pow(2, n_bit) - 1)def pi_b(x, m):m:1: encrypt0: decrypt enc DES.new(key,DES.MODE_ECB)if m:method enc.encryptelse:method enc.decrypts long_to_bytes(x)sp [s[a:a8] for a in xrange(0, len(s), 8)]r for a in sp:r method(a)return bytes_to_long(r)
k 2048
n0x78861bb9529cd40d3e29f8ebed4b697d2132a3ecb25904cac59f379828a2638f8e507d28c02c2eaadbd723c44733e36e0c522b3367fe98cca9cac1f5001cc676da983721d9ff6f4c39647206eb57edcaa589f99770efc918bddec6cdcbaf27a235f2a26ee9df26b4be1b0256de1fd4bc45f296c43a4059bb58e5fdb7c0d9e792dcdb75611ccb2323031aa053bd8b6dd4439136de0876c9cfdde31d1802e10417a82886054755b400d1a8d1c72a207114c8ad7d4d1d80cb126e094da961e976161b81ef2d4922fe5a19644412159c831c8d0b426890006e6eb02b64a9fed314a446d21271646dd627fa3d03d9b110386bf7af93d373abee935451165374a0356f
e0x10001
e20x999d
flag0x73907b2828a84e6af79d748464ec23471db575bd101e203f63bd6c28bea060bc48bb1a4f4b72e8b234557232e75ade97006ea61ae6c68ef429b109499cf982154b8f42466bc6cf2a41f6fa61b9d5d6e83b373a61f22d80760cdae08846f80c33d9c02a5f530819f41c2324494750b4de1c9b76e7497b8a38c870fadbf7cc341c8c5ee2164412b11b4af86a00b4f4f83cb7a98cad627dfdc4ec194dd452ae01b36c0590f3ee2442ffc466e4785a228ebcc32ac094a3e09ce9668105b8e49d855543342d56a5c6489eb4e42f11b96a9eed67f1644101cbc3cecfb8b366db8f3a24052c769cbdd80118d9b6c0ed7abf98bde199e2719d9f57bd24efc097380d7739
c121342536467
m1 0x2e72c47a71ce9186aa3474e243457364491504260e2712ba9340325f62e1fcb0731bb7a9e35c42d03730b8c1884d1ac4fccdaadf90ab9b74fadf915d6aed58b7aaf631f5e393e431297f895cad7b1cd0df0a4f3c969065b003fda4296ab2580ba9459ec0fcb0dd6f752666f8038565d4df0600c1d9ea8def140a3347a9c6576661429cbadbde6444ec1333e19b5900e8740ed7f77ecb4be642fa7709007c10754974292b923894bf5870338c45b51e990f7dfb716cc6ee1f5717c41bebb8c68b6aa14222f40f00080694d82a18cfb937ba77965d201a822744018aff375c78596e67b4b17eed904a676e87f4f342c2efca0daffce7d9bdb9714a699b48176fdeuget_bit(get_bit(n,3*k/8,1),5*k/16,0)
p4pi_b(u,0)
print hex(p4)
#p,q可由后面的脚本求出
p0xdfdf6ba55b2e1de773a3b5c2f041380bd3ac13974ce4ebd8f726d7a771acc73097f9670ceb47be920a3a556ac27cf82286a8c0b55113dd52f3273d596622015e4bbbbb47df5d54f864c3dd7a726e5449ca593af6b465918cb9ae25da52e79b8f40c40966a1f9994b531ae594a7c2adc0273f0f4388d80ffc1573b7bd3af56bb9
q0x89d1e21689e49a7d6388ea7438ea9563b7b6a37467d8a419e0f7fae1420628f63dd6fd238f7ecd537fa147c04530d943f7b12cb8f36cf740b3fb57fb061d08de6e29312c022aab6704ea3df1c5a8771d5ad2b3354fc0d1757570a3d2bbb2c55ad24a36d77dc450cbea39dc462782078c7c0f768bec26d562613675d6304bce67
dgmpy2.invert(e2,(p-1)*(q-1))
flagpow(flag,d,n)
print flag
print long_to_bytes(flag)
sega脚本
p40xdfdf6ba55b2e1de773a3b5c2f041380bd3ac13974ce4ebd8f726d7a771acc73097f9670ceb47be920a3a556ac27cf82286a8c0b55113dd52f3273d596622015e4bbbbb47df5d54f864c3dd7a726e5449
n0x78861bb9529cd40d3e29f8ebed4b697d2132a3ecb25904cac59f379828a2638f8e507d28c02c2eaadbd723c44733e36e0c522b3367fe98cca9cac1f5001cc676da983721d9ff6f4c39647206eb57edcaa589f99770efc918bddec6cdcbaf27a235f2a26ee9df26b4be1b0256de1fd4bc45f296c43a4059bb58e5fdb7c0d9e792dcdb75611ccb2323031aa053bd8b6dd4439136de0876c9cfdde31d1802e10417a82886054755b400d1a8d1c72a207114c8ad7d4d1d80cb126e094da961e976161b81ef2d4922fe5a19644412159c831c8d0b426890006e6eb02b64a9fed314a446d21271646dd627fa3d03d9b110386bf7af93d373abee935451165374a0356fpbits 1024
kbits pbits - p4.nbits()
print p4.nbits()
p4 p4 kbitsPR.x PolynomialRing(Zmod(n))
f x p4
x0 f.small_roots(X2^kbits, beta0.4)[0]
print x: %s %hex(int(x0))p p4x0
print p: , hex(int(p))
assert n % p 0
q n/int(p)print q: , hex(int(q))
12.HCTF2016-Crypto so amazing
和上一题类似只是这里的密钥p的一部分是通过D-H函数生成的所以我们首先拿到通过反向拿到p的一部分再使用Coppersmith partial information attack算法还原p根据nep即可对c进行解密其中pi_sit_x函数虽然使用了hash函数但其中结构可逆(由于yu F_hash(H_hash(xu) ^ xl) ^ xuyl H_hash(xu) ^ xl那么存在 H_hash(xu)yl^xl即yu F_hash(H_hash(xu) ^ xl) ^ xu可转变为yu F_hash(yl) ^ xuxuyu^F_hash(yl)xlyl^H_hash(yu^F_hash(yl))答案中的xu推到结果不正确但由于最后取的是后256位再xl中所以对结果不影响
from Crypto.Util.number import size, long_to_bytes, bytes_to_long, getRandomNBitInteger
from hashlib import sha512
import itertools
import random
import time
k 2048
e 0x10001
o 1024
m 256
def get_bit(number, n_bit, dire):dire:1: left0: rightif dire:sn size(number)if sn % 8 ! 0:sn (8 - sn % 8)return number (sn-n_bit)else:return number (pow(2, n_bit) - 1)def int_add(x1, x2):bit plusreturn bytes_to_long(long_to_bytes(x1) long_to_bytes(x2))def H_hash(x):h sha512(long_to_bytes(x)).hexdigest()return int(h, 16)def F_hash(x):h sha512(long_to_bytes(x/4)).hexdigest()return int(h, 16)def pi_sit_x2(sit, z):inverse operationzu get_bit(z, sit/2, 1)zl get_bit(z, sit/2, 0)xu zu ^ F_hash(zl)xl zl ^ H_hash(zu ^ F_hash(zl))return int_add(xu, xl)
def sha512_proof(fuzz, prefix, verify):y len(verify)while True:try:padd .join(fuzz.next())except StopIteration:breakr sha512(prefix padd).hexdigest()if verify in r:return padddef verify(r):r.readuntil(Prefix: ) prefix r.readline()prefix prefix.decode(base64)t1 time.time()proof sha512_proof(fuzz, prefix, fffffff)print time.time() - t1r.send(proof.encode(base64))def main():P0xe49614ad3a11e66bfbe847e477e1b283630790dd5975d478b8e75c56c89571d9b9223372036854775808n0x8b4abe0fc81d1ac4e027eda051960f6681a0921698ff310e60ffa754fa1b730dbb19ba0cc916b338a80ad1d8536c132d922022f7ae942e21dcfa1574149583b2bf3c81b5c76920acf99690e27888959e12f9e179819b5d273a94eea371c51265a85e61f0080f2dbad3bcf5c907cee497930cd281f393a3d45634c451e96835ef0f5b4657cbbb6f2d76b1559c444b4ddf948234166b5552fd4428b5618ad40b851f9e1eb3efcfa63985d5df16ffa5a23ca9ed3c0b6746ffd170ecd75cef2656bf3890a53a1d69b260652342769f1e7fd4447109d0a3fa220ebc88eb537c59a4fac597ac3ee2c9d2a1fb5a34680bed35fae67423c6bfcaf7e82ed1a59f34fc4889e0x10001e20x840dflag0x80dc303e2ed66eaa76c5b0e1edafd68641df4a6e27401e2d5699e6df3974335e15239640f625df590a8bf325da96c719d6cbb80bacc51ab3bf6530c799a22dcde6b9ad4332e1c28d6fb83ecc0b769de1d0f4658f40856418a30aca1028abb4dd2c14574d9be3d54a7ac71270ce5f6a20f61f47645a9a75355d930d796b994b368405a6d864986bdd013a7e2c2cc3035d16d9fc3f23ced422253c1e2ff6d9e74ddf63cce56c8972423f414fc97d3374c5a1398d0fd2d59e4c5fbdbc6cf10b5dcbb8764339d5a9ddde6981f17bed47b25be977cb5deaff66ae3ffe7d8fe38029d903cd6f3e10fcd5ecb33efdabdb95e702f1b3b0266ef82d25c72d21c73513cba5cipher1234567890Plaintext0x4356b108d0a28cd1ce4aa23c147da6c2d3ddcdbc3824446421f75fd624e34f053a691b96a58fd4e9d16cf45546d625121e9760b64be319f94a171cabd297a1a84c3a705ade71d50f1cbb431ba044b6140dcc0f7cb428cbcb9a38f4fc2ee3ed8a9b379abe6221174aea2c678baddea54b7360e67a04acaa2e215d505c27bdfe4ad32f5bceda1736fc5daec4eff930d87fa77b73b901679917d750e9251a8634749ab4b9bf629fd6916bd8a0d9164a8251b8c12e34186f8f25af2e5cae74f6d01e8a463487920ba6188314f02a58f37f1e787002794626896eb9fb61f5e034a781d4e7b1fce6571897619f7d25abad61de245c99ac8c7ecaeaaa662b13189a7fc7print n:,nprint e:,eprint e2:,e2print flag:,flagtget_bit(n,1024,1)print t:,hex(t)spi_sit_x2(o,t)print s:,hex(s)attack_spubget_bit(s,m,0)attack_sprivpow(attack_spub,b,P)print spub:,hex(attack_spub)print spriv:,hex(attack_spriv)if __name__ __main__:main()sage3.py
import randomspriv 0xbc100f24304ac73a357877ce1e57500521d1b0429591d75d931bca82f94f2fea
T 512 64PRF random.Random()
PRF.seed(spriv)def get_p4():while True:u PRF.randint(2**(T-1), 2**T)yield ufget_p4()
print get_p4().next() sage脚本
from sage3 import get_p4n0x8b4abe0fc81d1ac4e027eda051960f6681a0921698ff310e60ffa754fa1b730dbb19ba0cc916b338a80ad1d8536c132d922022f7ae942e21dcfa1574149583b2bf3c81b5c76920acf99690e27888959e12f9e179819b5d273a94eea371c51265a85e61f0080f2dbad3bcf5c907cee497930cd281f393a3d45634c451e96835ef0f5b4657cbbb6f2d76b1559c444b4ddf948234166b5552fd4428b5618ad40b851f9e1eb3efcfa63985d5df16ffa5a23ca9ed3c0b6746ffd170ecd75cef2656bf3890a53a1d69b260652342769f1e7fd4447109d0a3fa220ebc88eb537c59a4fac597ac3ee2c9d2a1fb5a34680bed35fae67423c6bfcaf7e82ed1a59f34fc4889
pbits 1024g_p get_p4()
while True:p4 g_p.next()# p4 0x81a722c9fc2b2ed061fdab737e3893506eae71ca6415fce14c0f9a45f8e2300711119fa0a5135a053e654fead010b96e987841e47db586a55e3d4494613aa0cc4e4ab59fc6a958b5kbits pbits - 576p4 p4 kbitsPR.x PolynomialRing(Zmod(n))f x p4x0 f.small_roots(X2^kbits, beta0.4)if len(x0) 0:continueprint x: %s %hex(int(x0[0]))p p4x0[0]print p: , hex(int(p))assert n % p 0q n/int(p)print q: , hex(int(q))print p4: , hex(p4)break结果
from Crypto.Util.number import size, getPrime, long_to_bytes, bytes_to_long, isPrime, getRandomNBitInteger
from libnum import invmod, gcd
from hashlib import sha512
import random
p0x851f7cd8fe49730a7a481e19e6afe52b9191261735854e310d75622199d7bad447a92cf257583fb34342e78a5e32dec0a34cae1e19afa355fe49f1584e1f7998a8f8971ad4370c99ec6ed717c791009ff2bc55115dbfc28f33c82b8d0bac89ba2b56fbe9a74bb6c1d0e265da303aca0400f46201f8a2b85eea710a92a33fc90f
q0x10bdcf5be7479deafce95c7eef5cdd721a585fdc9a3b524afa20eaf35666267bd6228f6e5ef46029d1d67b6b83badcf8b3e327a65a8a1a5242b5872d7e055ffaa6b0e350e3875cb58940c19164c90eb52daf1283d2c4a4d17f10675425e36cbd300158940c7a55ccccbb26a88fabc11a39cfe5ccf81ab08f8fdde6af69ddc64e7
n0x8b4abe0fc81d1ac4e027eda051960f6681a0921698ff310e60ffa754fa1b730dbb19ba0cc916b338a80ad1d8536c132d922022f7ae942e21dcfa1574149583b2bf3c81b5c76920acf99690e27888959e12f9e179819b5d273a94eea371c51265a85e61f0080f2dbad3bcf5c907cee497930cd281f393a3d45634c451e96835ef0f5b4657cbbb6f2d76b1559c444b4ddf948234166b5552fd4428b5618ad40b851f9e1eb3efcfa63985d5df16ffa5a23ca9ed3c0b6746ffd170ecd75cef2656bf3890a53a1d69b260652342769f1e7fd4447109d0a3fa220ebc88eb537c59a4fac597ac3ee2c9d2a1fb5a34680bed35fae67423c6bfcaf7e82ed1a59f34fc4889
e20x840d
flag0x80dc303e2ed66eaa76c5b0e1edafd68641df4a6e27401e2d5699e6df3974335e15239640f625df590a8bf325da96c719d6cbb80bacc51ab3bf6530c799a22dcde6b9ad4332e1c28d6fb83ecc0b769de1d0f4658f40856418a30aca1028abb4dd2c14574d9be3d54a7ac71270ce5f6a20f61f47645a9a75355d930d796b994b368405a6d864986bdd013a7e2c2cc3035d16d9fc3f23ced422253c1e2ff6d9e74ddf63cce56c8972423f414fc97d3374c5a1398d0fd2d59e4c5fbdbc6cf10b5dcbb8764339d5a9ddde6981f17bed47b25be977cb5deaff66ae3ffe7d8fe38029d903cd6f3e10fcd5ecb33efdabdb95e702f1b3b0266ef82d25c72d21c73513cba5
phi_n(p-1)*(q-1)
d invmod(e2,phi_n)
enc_flag pow(flag, d, n)
flag long_to_bytes(enc_flag)
print enc_flag
print flag
