题目来源CryptoHack - Public-Key Cryptography 公钥密码学模块 难度25 分 · 11728 次解题 知识标签RSA、数字签名、SHA256、bytes_to_long附件private.key含 N 和 d一、题目背景题目讲了一个「嫉妒的恋人」的故事你想约对方出去发出一条「是」的消息但被中间人篡改成了「不」。如何让接收方确信消息确实是你本人发出的答案是数字签名Digital Signature。RSA 签名的核心流程签名方你对消息 m 计算哈希 H(m)再用自己的私钥(N1,d1) 「加密」哈希值得到签名 SH(m)d1modN1。验证方朋友收到 (m,S) 后用你的公钥(N1,e1) 「解密」签名 sSe1modN1再独立计算 H(m)若 H(m)s 则验证通过。题目的具体要求用给定的私钥和SHA256哈希函数签名消息crypto{Immut4ble_m3ssag1ng}哈希输出需通过Crypto.Util.number.bytes_to_long()转为整数后参与 RSA 运算提交签名 S 作为 flag二、私钥文件分析附件private.key并非标准 PEM 格式而是直接以文本形式给出 N 和 dN 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803 d 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689N 是一个约 2048 位的大整数d 是对应的私钥指数。题目未直接给出公钥指数 e但 RSA 实践中 e 几乎总是 65537我们将在验证环节确认这一点。三、解题思路签名的本质是「用私钥对哈希值做一次模幂」。步骤如下消息mbcrypto{Immut4ble_m3ssag1ng}注意是字节串哈希H(m)SHA256(m)得到 32 字节的摘要转整数bytes_to_long(H(m))让哈希值能参与 RSA 数学运算签名SH(m)dmodN验证可选sSemodN检查 s?H(m)为什么要把哈希转成整数RSA 的模幂运算 xdmodN 要求 x 是一个整数。SHA256 输出的是 32 字节的字节串如\x99\xb4\xc7\x...不能直接做底数。bytes_to_long把字节串按大端序解释为一个整数例如b\x01\x02→ 0x0102258。这是密码学库里标准的转换方式。为什么先哈希再签名直接对原始消息做 mdmodN 也能「签名」但有问题消息可能很长超过 N 的字节长度无法直接作为 RSA 底数直接签明文没有「抗碰撞」保障且效率低。对消息先哈希再签名是把任意长度消息压缩为固定长度摘要的标准做法。哈希的单向性和抗碰撞性保证了签名不可伪造。四、代码实现python import hashlib from Crypto.Util.number import bytes_to_long # 从 private.key 读取 N 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803 d 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689 # 待签名消息字节串 m bcrypto{Immut4ble_m3ssag1ng} # 1. SHA256 哈希 h_bytes hashlib.sha256(m).digest() # 32 字节摘要 Hm bytes_to_long(h_bytes) # 转整数 # 2. 签名S H(m)^d mod N S pow(Hm, d, N) print(消息 :, m.decode()) print(SHA256(hex):, h_bytes.hex()) print(H(m) 整数 :, Hm) print(签名 S :, S)运行结果text 消息 : crypto{Immut4ble_m3ssag1ng} SHA256(hex): 99b4c7bb814cc630c4199e4814ffed85a835f64ffc82aadaa6388d9df9aeb2cb H(m) 整数 : 69523276807549773371481917516452638375664281433555793080445569568100703974091 签名 S : 13480738404590090803339831649238454376183189744970683129909766078877706583282422686710545217275797376709672358894231550335007974983458408620258478729775647818876610072903021235573923300070103666940534047644900475773318682585772698155617451477448441198150710420818995347235921111812068656782998168064960965451719491072569057636701190429760047193261886092862024118487826452766513533860734724124228305158914225250488399673645732882077575252662461860972889771112594906884441454355959482925283992539925713424132009768721389828848907099772040836383856524605008942907083490383109757406940540866978237471686296661685839083475五、结果验证为确认签名正确我用公钥指数 e65537 反向验证计算 sSemodN检查是否等于 H(m)。python e 65537 s pow(S, e, N) # 验证用公钥还原 assert s Hm, 验证失败 print(验证通过: s H(m))运行结果text 验证通过: s H(m)这说明签名 S 确实能用 (N,e65537) 还原回 H(m)反推得知本题的公钥指数 e65537题目未直接给出但通过验证可确认整个签名-验证流程闭环成立。签名与哈希的关系如下项目值消息 mcrypto{Immut4ble_m3ssag1ng}哈希算法SHA256H(m) (hex)99b4c7bb814cc630c4199e4814ffed85a835f64ffc82aadaa6388d9df9aeb2cbH(m) (整数)69523276807549773371481917516452638375664281433555793080445569568100703974091私钥 d见private.key2048 位模数 N见private.key2048 位公钥指数 e65537通过验证确认签名 S见下方 Flag六、Flag13480738404590090803339831649238454376183189744970683129909766078877706583282422686710545217275797376709672358894231550335007974983458408620258478729775647818876610072903021235573923300070103666940534047644900475773318682585772698155617451477448441198150710420818995347235921111812068656782998168064960965451719491072569057636701190429760047193261886092862024118487826452766513533860734724124228305158914225250488399673645732882077575252662461860972889771112594906884441454355959482925283992539925713424132009768721389828848907099772040836383856524605008942907083490383109757406940540866978237471686296661685839083475七、一点拓展1. 为什么「加密」和「签名」用的是同一套数学却方向相反RSA 的数学对称性是它最巧妙的地方操作用的密钥数学加密保密对方公钥 (N,e)cmemodN解密保密自己私钥 (N,d)mcdmodN签名认证自己私钥(N,d)SH(m)dmodN验签认证对方公钥(N,e)sSemodN?H(m)「加密用公钥签名用私钥」——两者共用同一对 (N,e,d)但角色对调。这正是题目里「用私钥加密哈希值」说法的由来。2. 为什么题目强调「加密和签名用不同密钥」题目原文In real cryptosystems, the best practice is to use different keys for encryption and signing.这是因为如果同一对密钥既用于加密又用于签名会引入一些安全隐患例如攻击者可能把你当作「解密预言机」来伪造签名。所以实际系统如 PGP、SSH都会为加密和签名分别生成独立的密钥对。3. 实际签名还要做 padding本题直接对原始 SHA256 值做 H(m)dmodN这种「 textbook RSA 签名」在现实中是不安全的。例如存在**存在性伪造existential forgery**攻击攻击者可以随机选 S计算 hSemodN若能找到消息 m′ 使 H(m′)h就伪造了一对有效签名 (m′,S)。实际标准如 PKCS#1 v1.5 或 PSS会在哈希值前后加特定的填充结构如0x00 0x01 0xFF...0xFF 0x00 || DigestInfo || H再对填充后的值做模幂从而抵御这类攻击。本题作为教学题省略了这一层。4.bytes_to_long与long_to_bytes是一对python from Crypto.Util.number import bytes_to_long, long_to_bytes bytes_to_long(b\x01\x02) # 258 long_to_bytes(258) # b\x01\x02它们是大端序互逆转换是 pycryptodome 里最常用的两个工具函数后续题目会反复出现。八、小结这道题串起了 RSA 签名的完整流程关键收获签名的本质用私钥对消息哈希做模幂 SH(m)dmodN验签则用公钥还原 sSemodN 并比对 H(m)。哈希的作用把任意长度消息压缩为定长摘要保证签名可行且抗碰撞。bytes_to_long哈希字节串转整数是衔接「哈希世界」和「RSA 整数世界」的桥梁。安全提醒textbook RSA 签名不安全实际系统必须配合 PKCS#1 v1.5 / PSS 填充。