re: author’sB0x
exp:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 cry = [0xc3 ,0xf5 ,0xe5 ,0xe2 ,0xEC ,0x17 ,0xE5 ,0x2A ,0xCA ,0x3 ,0xB6 ,0xFD ,0xC1 ,0xBC ,0x70 ,0x44 ,0x10 ,0xCD ,0xA6 ,0x13 ,0x0B ,0x9A ,0x73 ,0x6 ,0x0E ,0x4D ,0xDE ,0x95 ,0x12 ,0x9C ,0xD9 ,0x46 ] key = "thisiskey" len1 = len (cry) s = [0 for i in range (256 )] t = [0 for i in range (256 )] keystream = [0 for i in range (256 )] for i in range (256 ): s[i] = i t[i] = key[i%9 ] v3 = 0 v1 = 0 for i in range (256 ): v3 = (s[i] + v3 + ord (t[i]))%256 v1 = s[i] s[i] = s[v3] s[v3] = v1 v4 = 0 v5 = 0 v6 = 0 result = 0 i = 0 v2 = 0 while 1 : v2 = len1 len1 -= 1 if v2==0 : break i = (i+1 )%256 v6 = (v6+s[i])%256 v4 = s[i] s[i] = s[v6] s[v6] = v4 keystream[4 *v5] = s[(s[v6]+s[i])%256 ] v5 += 1 len1 = len (cry) flag = [0 for i in range (len1)] for i in range (len1): flag[i] = cry[i] ^ keystream[4 *i] print (chr (flag[i]),end='' )
手搓一遍就出来了。
密码:ezrsa
原题代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 from Crypto.Util.number import *from secret import flagflag = b'xxx' e = 114 m = bytes_to_long(flag) p = getPrime(1024 ) q = getPrime(1024 ) t = getPrime(1024 ) n = p * q * t p_=pow (p,2 ,n) q_=pow (q,2 ,n) c = pow (m,e,n) print ('p_=' ,p_)print ('q_=' ,q_)print ('c=' ,c)print ('n=' ,n)
第一个问题是p_ = p^2 % n
。乍一看很难解,甚至好像和二次剩余有关,实际仔细分析一番得出p并不难。n由3个1024位质数相乘,为3072位。p^2则只有2048位,小于n,相当于没模。易通过p = gmpy2.iroot(p_ , 2)[0]
得出p。q同理。
第二个问题是n = p * q * t
,三元质数加密,没学过呀。搜索一下 可知三元的欧拉函数和二元的格式相同,遂放心使用phi = (p-1)*(q-1)*(t-1)
。
第三个问题是gcd(e, phi) != 1
,所以没法直接逆元。这里可以先将e整除GCD = gcd(e, phi)
得到新的e1后通过构造d1 = gmpy2.invert(e1,phi)
后得出密钥,最后的密文要开GCD次根。
原理如下:
g = g c d ( e , ϕ ( n ) ) e 1 = e g ∵ m e ≡ c ( m o d n ) ∴ m e ≡ ( m g ) e g ≡ ( m g ) e 1 ≡ c ( m o d n ) ∴ m g = c d 1 m o d n 其中 d 1 = i n v e r s e ( e 1 , ϕ ( n ) ) g = gcd(e,\phi(n)) \\
e_1 = \frac e {g} \\
\because m^e \equiv c\space(mod\space n) \\
\therefore m^e \equiv (m^g)^{\tfrac e g} \equiv (m^g)^{e_{_ 1}} \equiv c\space(mod\space n) \\
\therefore m^g = c^{d_{_ 1}}\space mod\space n \\
\text{其中} d_1 = inverse(e_1,\phi(n))
g = g c d ( e , ϕ ( n )) e 1 = g e ∵ m e ≡ c ( m o d n ) ∴ m e ≡ ( m g ) g e ≡ ( m g ) e 1 ≡ c ( m o d n ) ∴ m g = c d 1 m o d n 其中 d 1 = in v erse ( e 1 , ϕ ( n ))
exp:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 import gmpy2from Crypto.Util.number import *p_= 10660749010264526666955869622200514149424664070021154725214604278423033834800955315638637946982741577976025615843487738805576629855459529381681679497064453109727962183277768658053394103348827822686515016677449953958986089293779870089604784750116267441026319440135025236091029928565442799040007751858012409498271852333017388486644053877238274838173771344350870565886676055860728949042361028753924290647753862707042472944714140635484722345522648010064713004854479094986010632316750770118044301903260988074471243247031854872785324506292730778884664223412372663828159205320038546293395502275887356885181013870536857351801 q_= 24900409366873586425973971191854411152048453357438215578406168704445779543895031579176888535442469919297663892450230816720758414920791049333275007446412352293152157437672026001378469357187698312455020558413101033543700131403373834030395855212901673914686297701313223697181049265286011127188695284002470629178098454764536315245968458622929902214839704674718996340182311301099900271312644919770585429288043854743210617868761990329037081770477261306489047429460937057125193231432195877922731165870197358946683698077175950756482605399815830687563398277515452842563143685190688865084064679712177247354049377034394880941369 c= 946358882688806235743551077996671406469185038565566907261383734984318844703303437873183869084536703835433988817350857866089668970925835657856975155167500190428922521871327955274363186305180350899397478897928581580727458938934640786146518171503388507311655160765881370401217708135845031083189007308497775864484758699096082815479602777639307812516934937183952478316508418895341680335172973583094238147073379957772209947376051520041093030641369536800448737539973770258342422560893630082723217759837690008955748444973711508371077927468399703456466637348191192859278206925769696645636969358967735037470196395844215361527039288120664704552775460536654859848091685928057224735031528303041212702445718384890182474053295656578327780048497422707815820736647212902522526653039676698263673166412650104420869762547385554961873764933774143297622712766521201037469301912471740996998228799841957283759679784569638149555093498363791420486340 n= 1677924010415009671349677258549532467848510897335579570922114838282842960143799964694977371357046837674443739542407516581076865550606801686170400793463690366665534118961173768008603133641864003317727610676872685077700753537755254540591236871020140458419596610210236431401477173114522177145982007059709616618279936170223104755776796458682957656555154039384483954754660803554302451221585280396378564648495919069459351016010016636012245082009946238467068412198769348889950331295680906811430325690102055808865038151762131291269197341984605959088829226733422023970618165958725486675321766767430347929319621215891165857544847088373700410007500868721335483070938971597851859953792409442485301373327127595552457801719192824050415833073999094005750868115932130442747899994421453654008731830580286370350900523295205445599466666709544075950517531382971246869745425091317996973135364990272852701046046315136273893166361180330563013617843 e=114 p,f = gmpy2.iroot(p_,2 ) q,f = gmpy2.iroot(q_,2 ) t = n//(p*q) phi = (p-1 )*(q-1 )*(t-1 ) GCD=gmpy2.gcd(e,phi) d1 = gmpy2.invert(e//GCD,phi) m1 = pow (c,d1,n) m,f = gmpy2.iroot(m1,GCD) print (long_to_bytes(m))