HECTF 一些re和密码

re: author’sB0x

exp:

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

原题代码如下：

from Crypto.Util.number import *
from secret import flag
flag = 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_= 10660749010264526666955869622200514149424664070021154725214604278423033834800955315638637946982741577976025615843487738805576629855459529381681679497064453109727962183277768658053394103348827822686515016677449953958986089293779870089604784750116267441026319440135025236091029928565442799040007751858012409498271852333017388486644053877238274838173771344350870565886676055860728949042361028753924290647753862707042472944714140635484722345522648010064713004854479094986010632316750770118044301903260988074471243247031854872785324506292730778884664223412372663828159205320038546293395502275887356885181013870536857351801
#q_= 24900409366873586425973971191854411152048453357438215578406168704445779543895031579176888535442469919297663892450230816720758414920791049333275007446412352293152157437672026001378469357187698312455020558413101033543700131403373834030395855212901673914686297701313223697181049265286011127188695284002470629178098454764536315245968458622929902214839704674718996340182311301099900271312644919770585429288043854743210617868761990329037081770477261306489047429460937057125193231432195877922731165870197358946683698077175950756482605399815830687563398277515452842563143685190688865084064679712177247354049377034394880941369
#c= 946358882688806235743551077996671406469185038565566907261383734984318844703303437873183869084536703835433988817350857866089668970925835657856975155167500190428922521871327955274363186305180350899397478897928581580727458938934640786146518171503388507311655160765881370401217708135845031083189007308497775864484758699096082815479602777639307812516934937183952478316508418895341680335172973583094238147073379957772209947376051520041093030641369536800448737539973770258342422560893630082723217759837690008955748444973711508371077927468399703456466637348191192859278206925769696645636969358967735037470196395844215361527039288120664704552775460536654859848091685928057224735031528303041212702445718384890182474053295656578327780048497422707815820736647212902522526653039676698263673166412650104420869762547385554961873764933774143297622712766521201037469301912471740996998228799841957283759679784569638149555093498363791420486340
#n= 1677924010415009671349677258549532467848510897335579570922114838282842960143799964694977371357046837674443739542407516581076865550606801686170400793463690366665534118961173768008603133641864003317727610676872685077700753537755254540591236871020140458419596610210236431401477173114522177145982007059709616618279936170223104755776796458682957656555154039384483954754660803554302451221585280396378564648495919069459351016010016636012245082009946238467068412198769348889950331295680906811430325690102055808865038151762131291269197341984605959088829226733422023970618165958725486675321766767430347929319621215891165857544847088373700410007500868721335483070938971597851859953792409442485301373327127595552457801719192824050415833073999094005750868115932130442747899994421453654008731830580286370350900523295205445599466666709544075950517531382971246869745425091317996973135364990272852701046046315136273893166361180330563013617843

第一个问题是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 = 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))$$

exp:

import gmpy2
from 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))