PolarD&N 2024冬季个人挑战赛 Crypto题解教学文档

题目1：博福特与埃特巴什的秘密

题目描述：
根据题目名称和提示，需使用博福特密码解码，再用埃特巴什码解密，最后通过幂数加密得到flag。

解题步骤：

1. 原始密文处理

   • 给定数字串：4442 122 88421 8881 14 1 8442
   • 去除所有0，将剩余数字作为分隔符。

2. 幂数加密解码

   • 幂数加密规则：数字代表2的幂次方之和，对应字母表位置（A=1, B=2,..., Z=26）。
     • 4442 → 2² + 2² + 2² + 2¹ = 4+4+4+2 = 14 → N
     • 122 → 2¹ + 2² + 2² = 2+4+4 = 10 → E
     • 同理解码其他数字：
       88421→23(W), 8881→25(Y), 14→5(E), 1→1(A), 8442→18(R)
   • Flag：flag{NEWYEAR}

关键点：

• 幂数加密需将数字拆分为2的幂次求和，再映射到字母表。

题目2：bllbl的密码锁

题目描述：
密文以U2Fsd开头，提示密钥为bllbl，需解密后与服务器交互。

解题步骤：

1. 初始判断

   • U2Fsd开头表明可能是AES或Rabbit加密，结合提示使用密钥bllbl解密。

2. 自定义编码逆向

   • 给定密文：nInuILUauBilLUaLBgnnNBluG-bNaIlinaA+...
   • 编码规则：字符映射到自定义字符集BALUINGbaluing+-，每字符对应4位二进制，转16进制。
   • 解码脚本：

     class Bllbl_crypto1:
         def __init__(self):
             self.char_map = "BALUINGbaluing+-"
             self.index_map = {char: index for index, char in enumerate(self.char_map)}
     
         def decode(self, cipher):
             binary_str = ''.join(format(self.index_map[char], '04b') for char in cipher)
             hex_str = ''.join(hex(int(binary_str[i:i+4], 2))[2:] for i in range(0, len(binary_str), 4))
             return hex_str
     
     ciphertext = "nInuILUauBilLUaLBgnnNBluG-bNaIlinaA+..."
     plaintext = Bllbl_crypto1().decode(ciphertext)
     print(plaintext)  # 输出16进制明文
     

   • 明文：c4ca4238a0b923820dcc509a6f75849b...（SHA-1哈希格式）

3. 服务器交互

   • 将明文提交至题目指定的nc服务，获取下一步提示或flag。

关键点：

• 自定义字符集映射需转换为二进制再转16进制。
• 注意密文中的分隔符（+-）需保留。

题目3：RSA共模攻击

题目描述：
给定两组(n, e, c)，其中n1=n2，使用共模攻击解密。

解题步骤：

1. 共模攻击原理

   • 若n相同，且e1与e2互素，可通过扩展欧几里得算法找到x,y满足e1*x + e2*y = 1，则明文m = (c1^x * c2^y) mod n。

2. 解密脚本：

   import gmpy2
   from Crypto.Util.number import long_to_bytes
   
   n = 20367004933619640329031799226776514837061685981664854285308115632909435670724596920128402172098160576548639864098528644817516365660648152982472184401323785790562533467196556834124275893853534815001482876360398354954695792370636033673202145070244264275187457752956505832556854269231285319773348399301741813934834487846223229051935634443669493220012667872355681808618502449585839172939977649524262173256707695568263984472286856069995773192355643301872930251256460438128472182620887659172465881490174220827917135702261368000920219514539361766564775919476617752618166100973206718108473026971567131239107358379641923763013
   e1, e2 = 2333, 23333
   c1 = 10264744066430466481593872630149143558573077174416980857009118692134660819073913212595308263898462327337283768644911383152506209840559778285757586705322364622425329621425100366723498923698716160356383331699930898455469318543849123623408889653265452565954257437198570129871082756267930336123137826093005304199337852991417533302939219968193861864872868938531890911844179764341487167273826185141101537209604030231278035081281820795150900579415774349854010257952836794529900536730723453110219127519437954530016383921843131179651083796172790701851004000889426375776340135273928938349542525459256006377475939436412482003970
   c2 = 5419945808600875685324905255766599302044490914532517430566320331248051121989090272712976205411073231922350575383585807837699039790705965844972602000549867253273355997765191642673804824094384527196797854210696722264604208353972695860473231983654542614752370002709975410103077627528638449599044074982480645065659196532121501525242050349677315892712735554820817806905097442560421171589689581990204756724213720035752010249253635380639611831099379821172339940499162281183608981563319912252895890992937277744761454652788338855099270346501953960046919430422924656133558212488023532963289949329182442150206387260469485512737
   
   _, x, y = gmpy2.gcdext(e1, e2)
   m = pow(c1, x, n) * pow(c2, y, n) % n
   print(long_to_bytes(m))
   

   • 输出：明文m对应的ASCII字符串。

关键点：

• 确保e1和e2互素（gcd(e1,e2)=1）。
• 结果可能需要进一步处理（如去除填充）。

题目4：Variation-RSA

题目描述：
多组(n, e, c)，其中n1与n2、n3与n4、n5与n6有公因子，需分解n后逐层解密。

解题步骤：

1. 公因子分解

   • 计算p1 = gcd(n1, n2)，p2 = gcd(n3, n4)，p3 = gcd(n5, n6)。
   • 分解得到q1 = n1//p1，q2 = n2//p1，依此类推。

2. 逐层解密

   • 对每组(n, e, c)计算私钥d = invert(e, phi)，其中phi = (p-1)*(q-1)。
   • 解密顺序：先解密外层（第二次加密），再解密内层（第一次加密）。

3. 解密脚本：

   p1 = gmpy2.gcd(n1, n2)
   p2 = gmpy2.gcd(n3, n4)
   p3 = gmpy2.gcd(n5, n6)
   # 计算phi和d...
   m1 = pow(pow(c1, d2, n2), d1, n1)  # 注意解密顺序
   print(long_to_bytes(m1).decode())
   

   • Flag：flag{c2c4c982b574fb735487899f11faed80}（需修正为flag{cc4c98b5574fb7355487899f11faed80}）

关键点：

• 每组n需独立分解，确保p和q正确。
• 解密后需处理编码（如.decode()），避免乱码。

总结

1. 幂数加密：数字转2的幂次和，映射字母表。
2. 自定义编码：分析字符集映射规则，逆向为二进制或16进制。
3. RSA共模攻击：n相同时利用扩展欧几里得算法组合密文。
4. 多组RSA：优先检查公因子分解，逐层解密并注意编码转换。