RSA 字符串映射变形加密题 Writeup

一、题目源码分析pythonfrom Crypto.Util.number import *from secret import flagdef encrypt1(n):n1 hex(n200).encode()n2 str(hex(n))[20:].encode()return n1,n2def encrypt2(m , n_1):c_1 pow(m,e_1,n_1)def encrypt3(m , n_2):c_2 pow( m , e_2 , n_2)def encrypt4(m):k getPrime(512)m m % kc_3 pow(m, e_2, n_3)return m, km1_raw,m2_raw encrypt1(flag)m1 bytes_to_long(m1_raw)m2 bytes_to_long(m2_raw)encrypt2(m1,n_1)encrypt3(n1,n_2)encrypt4(m2)输出给出参数n_2 675835056431522362944898323336128967810604111341771166424819153316861123229670037225545557183176982348673180364605892282514726016094247816130047391894056647452480835163557236407780499396076328619177440772116626645008922639448957963358124728566763693427918065300085120761329192988171031357513082056395909829128090723062007098901860182562022216900707805868351802418466423256484825705463385883821440134121804142293850861580896363541236019018383788880726735506046551222407821054687699056275935434957490772401552531501n_3 91294511667572917673898699346231897684542006136956966126836916292947639514392684487940336406038086150289315439796780158189004157494824987037667065310517044311794725172075653186677331434123198117797575528982908532086038107428540586044471407073066169603930082133459486076777574046803264038780927350142555712567e_1 65537e_2 3c_1 47029848959680138397125259006172340325269302342762903311733700258745280761154948381409328053449580957972265859283407071931484707002138926840483316880087281153554181290481533c_2 332431c_3 11951299411967534922967467740790967733301092706094553308467975774492025797106594440070380723007894861454249455013202734019215071856834943490096156048504952328784989777263664832098681831398770963056616417301705739505187754236801407014715780468333977293887519001724078504320344074325196167699818117367329779609m 9530454742891231590945778054072843874837824815724564463369259282490619049557772650832818763768769359762168560563265763313176741847581931364k 8139616873420730499092246564709331937498029453340099806219977060224838957080870950877930756958455278369862703151353509623205172658012437573652818022676431二、解题前置推导1. 关于$m_2$encrypt4内执行$m_2 \% k$输出的$m$是取模结果出题构造保证$m_2 k$因此$m_2 m$。2. 关于$m_1$$n_1$存在小素因子$p12001163$可分解模数利用RSA私钥解密$c_1$得到$m_1$。3. 核心映射关系- $m_1 \mathrm{bytes\_to\_long}(\mathrm{hex}(flag\_num 200).encode())$- $m_2 \mathrm{bytes\_to\_long}(\mathrm{hex}(flag\_num)[20:].encode())$其中$flag\_num$为flag明文对应的十进制整数$\mathrm{bytes\_to\_long}$是将ASCII字节序列直接按大端转为整数该变换单向无法通过long_to_bytes直接还原原始字符串。4. 位与十六进制换算1个十六进制字符占4bit- 200bit 50个十六进制字符$flag\_num 200$等价于截断完整十六进制串末尾50字符- hex(flag_num)[20:]等价于截断完整十六进制串前20字符三、分步解题代码1.RSA解密获取m1pythonfrom Crypto.Util.number import inversep 12001163q 44855690771929550739782329707223288927131821419455028352237125128361403243141521969624573650335136882039947325488862394629147693110596682682340652476268895560578656848803506494143984161874672364601450773738897358948372140220823428809201635588714501538552394072148267693833438724911163306215662770049528518955045500428750705152647304478909437102113170687570179858274270856623214408925483795513938118674148842265857972396583261434015688231080920147549594610626199412707570179214106087574673840773389276722727n1 p * qe1 65537c1 47029848959680138397125259006172340325269302342762903311733700258745280761154948381409328053449580957972265859283407071931484707002138926840483316880087281153554181290481533phi (p - 1) * (q - 1)d inverse(e1, phi)m1 pow(c1, d, n1)m2 95304547428912315909457780540728438748378248157245644633692592824906190495577726508328187637687693597621685605632657633131767418475819313642.SageMath BFS逆向还原原始十六进制字符串sagefrom Crypto.Util.number import bytes_to_longfrom collections import dequedef str2num(s):return bytes_to_long(s.encode(ascii))def find_str(target):char_set 0123456789abcdefxqueue deque(char_set)while queue:cur queue.popleft()val str2num(cur)if val target:return curif val target:for c in char_set:queue.append(cur c)return None3.还原两段原始hex文本s_upper_raw find_str(m1)s_lower_raw find_str(m2)s_upper s_upper_raw.removeprefix(0x)len_lower len(s_lower_raw)full_total_len 20 len_lowercut_tail 50prefix_required_len full_total_len - cut_tail补齐前导零prefix_full s_upper.zfill(prefix_required_len)head_20 prefix_full[:20]full_hex head_20 s_lower_raw4.转换明文flag_num int(full_hex, 16)flag_bytes long_to_bytes(flag_num)print(flag{ flag_bytes.decode(ascii) })四、干扰项说明$n_2、c_2、n_3、c_3$仅用于生成$m$无其他作用encrypt3为无关干扰加密全程无需参与计算。五、运行说明代码必须在SageMath环境执行依靠广度优先搜索完成单向映射的逆向匹配匹配完成后拼接完整十六进制串直接输出标准flag格式字符串。