Z2kDH - Writeup by AI

Z2kDH - Writeup by AI题目描述这是一个基于离散对数的密钥交换协议类似于 Diffie-Hellman。题目给出了以下信息模数:modulus 1 258(即 2^258)生成器: g 5Alice 的公钥:99edb8ed8892c664350acbd5d35346b9b77dedfae758190cd0544f2ea7312e81Bob 的公钥:40716941a673bbda0cc8f67fdf89cd1cfcf22a92fe509411d5fd37d4cb926afd需要求解他们之间的共享密钥并从中提取 flag。考点分析离散对数问题的特殊性: 当模数为 2 的幂次时离散对数问题变得容易求解Pohlig-Hellman 算法的应用: 在光滑阶群上离散对数可以高效求解逐比特恢复技术: 利用模数 2^n 的特殊性质从低位到高位逐位恢复私钥数学洞察力: 理解 5 ≡ 1 (mod 4) 这一关键性质在解题中的作用解题思路1. 理解协议流程defZ2kDH_init(private_exponent):returnpow(5,private_exponent,modulus)//4defZ2kDH_exchange(public_result,private_exponent):returnpow(public_result*41,private_exponent,modulus)//4Alice 和 Bob 各自生成私钥计算公钥pub 5^private mod 2^258 // 4交换公钥后计算共享密钥secret 5^(private_a * private_b) mod 2^258 // 42. 恢复实际公钥值由于Z2kDH_init返回的是除以 4 后的值而Z2kDH_exchange会乘以 4 再加 1所以实际的公钥值为actual_pub pub * 4 13. 求解离散对数对于方程5^x ≡ h (mod 2^n)使用逐比特恢复方法核心思想设已恢复的前 i 位为 x_i要确定第 i 位 b_ix x_i b_i * 2^i (更高位项)通过比较h * 5^(-x_i) mod 2^(i3)与5^(2^i) mod 2^(i3)来判断 b_i判断规则如果ratio 5^(2^i): b_i 1如果ratio 1: b_i 04. 计算共享密钥获得私钥后计算shared_secret pow(bob_pub_actual, alice_private, modulus) // 45. 转换为 Flag将共享密钥转换为字节序列解码为 ASCII 字符串。详细步骤步骤 1: 读取并处理公钥alice_pubint(99edb8ed8892c664350acbd5d35346b9b77dedfae758190cd0544f2ea7312e81,16)bob_pubint(40716941a673bbda0cc8f67fdf89cd1cfcf22a92fe509411d5fd37d4cb926afd,16)alice_pub_actualalice_pub*41bob_pub_actualbob_pub*41步骤 2: 实现逐比特恢复算法defsolve_discrete_log(g,h,bits):x0foriinrange(bits):mod_val1(i3)gxpow(g,x,mod_val)gx_invpow(gx,-1,mod_val)ratio(h%mod_val)*gx_inv%mod_val g_2ipow(g,1i,mod_val)ifratiog_2i:x|(1i)returnx步骤 3: 求解 Alice 的私钥alice_privatesolve_discrete_log(5,alice_pub_actual,256)# 结果0xc3eb8407c7a92004ee28611da0e6b213dc1eadbbe28b545083de58344a66ff381步骤 4: 验证私钥alice_check_fullpow(5,alice_private,modulus)ifalice_check_fullalice_pub_actual:print(✓ 验证成功!)步骤 5: 计算共享密钥shared_secretpow(bob_pub_actual,alice_private,modulus)//4# 结果0x776374667b5030484c31475f48334c4c4d344e5f244d344c4c5f70723114d337d步骤 6: 提取 Flagbyte_len(shared_secret.bit_length()7)//8shared_bytesshared_secret.to_bytes(byte_len,big)flagshared_bytes.decode(utf-8)# 结果wctf{XXX}运行结果$ python solve.pyZ2kDH CTF 题解[步骤1]读取并处理公钥 Alice 公钥(已处理): 0x99edb8ed8892c664350acbd5d35346b9b77dedfae758190cd0544f2ea7312e81 Bob 公钥(已处理): 0x40716941a673bbda0cc8f67fdf89cd1cfcf22a92fe509411d5fd37d4cb926afd Alice 实际公钥: 0x267b6e3b6224b1990d42b2f574d4d1ae6ddf7b7eb9d60643341513cba9cc4ba05 Bob 实际公钥: 0x101c5a50699ceef683323d9ff7e273473f3c8aa4bf942504757f4df532e49abf5[步骤2]算法正确性测试测试私钥12345 恢复的私钥12345 ✓ 算法测试成功![步骤3]求解 Alice 的私钥Alice 私钥0xc3eb8407c7a92004ee28611da0e6b213dc1eadbbe28b545083de58344a66ff381 Alice 私钥位数256 ✓ Alice 私钥验证成功![步骤4]计算共享密钥共享密钥0x776374667b5030484c31475f48334c4c4d344e5f244d344c4c5f70723114d337d[步骤5]提取 Flag共享密钥(字节): bwctf{XXX}*** Flag: wctf{XXX}***总结这道题目的关键点在于识别特殊模数: 模数 2^258 是 2 的幂次属于光滑阶不适合用于密码学应用 Pohlig-Hellman 思想: 在光滑阶群上离散对数可以在线性时间内求解逐比特恢复技巧: 利用模 2^n 运算的性质从低位到高位逐位确定私钥数学性质的重要性: 5 ≡ 1 (mod 4) 保证了 5(2k) ≡ 1 (mod 2^(k2))这是逐比特恢复的基础