这是一个创建于 1386 天前的主题，其中的信息可能已经有所发展或是发生改变。
常用 RSA 计算工具主要是 RSA Tool 和 Python，这两天刷题突然发现网上找到的 N 段 python rsa 代码，在 p/q 值较大时计算 d 值是错误的，尝试过网上五六种不同 python 解法，脚本得出的 d 值都一样————但是和 RSA Tool 工具算出的 d 值完全不同，并且经测试只有 RSA tool 计算的 d 值是准确的，可以成功解密密文
下面时网上被争相转载的 rsa 计算代码(Python3.8)：
第一段：
import gmpy2
p = 31093551302922880999883020803665536616272147022877428745314830867519351013248914244880101094365815998050115415308439610066700139164376274980650005150267949853671653233491784289493988946869396093730966325659249796545878080119206283512342980854475734097108975670778836003822789405498941374798016753689377992355122774401780930185598458240894362246194248623911382284169677595864501475308194644140602272961699230282993020507668939980205079239221924230430230318076991507619960330144745307022538024878444458717587446601559546292026245318907293584609320115374632235270795633933755350928537598242214216674496409625928797450473
q = 31093551302922880999883020803665536616272147022877428745314830867519351013248914244880101094365815998050115415308439610066700139164376274980650005150267949853671653233491784289493988946869396093730966325659249796545878080119206283512342980854475734097108975670778836003822789405498941374798016753689377992355122774401780930185598458240894362246194248623911382284169677595864501475308194644140602272961699230282993020507668939980205079239221924230430230318076991507619960330144745307022538024878444458717587446601559546292026245318907293584609320115374632235270795633933755350928537598242214216674496409625928997877221
#n = p*q
e = 65537
c=796983434801285801035506456613751041412401221081761619465143633772980578681222354794754171546842175764487330047090774468385458721093498582002999612123895344764488252258147003570107801369001334193415851313831374317827540572818487986253070916416104835732745971482686780094934080128761370661855576907775754816727828762662702236564791292407400598314729354234532327557902733202127244721321959431344807847346639760369323575843100726776777824056532473464985656427151381519922438032837706107233407696417731985441371468645554838701879231168972862629531841598533326107350331062656995416201205990466017352260613810137553934997580514437560240053911539740611611514163969126867425115465120400600839806398118818388165299519541809605181029854404908904714340846179559628907364656790109047432815875123192058602315639867791175382388022938086581287310055706237892608574797123074505345689982088564245685070361569039051098499125148468123005807373154464939780438855550107384849025949901892360318177449749013442403801832501489591788931293671223350377572643036064247915241957850760432970341442475119543463729083682266541376435473532457753072904778602689434884246708203978713295989854090340919428601642635316925469219747095123748509234725022563666422440299394
p =gmpy2.mpz(p)
q =gmpy2.mpz(q)
e =gmpy2.mpz(e)
phi_n= (p - 1) * (q - 1)
d = gmpy2.invert(e, phi_n)
print (d)
第二段：
def getD(p,q,e):
n = p * q
Qn = (p-1) * (q-1)
i = 1
while (True):
x = (Qn * i ) + 1
if (x % e == 0):
d = x // e
return d
i += 1
print(getD(p,q,e))
第三段：
def inverse(x, m):
a, b, u = 0, m, 1
while x > 0:
q = b // x # integer division
x, a, b, u = b % x, u, x, a - q * u
if b == 1:return a % m
PHI=(p-1)*(q-1)
print(inverse(e, PHI))
以上代码输出的 D 值都是错误的：
815629325053659645285350585199852033833716278229778374775605178972130793264780626063336436552061004322705478471331699298380571376265400785164446160811325376518083069202248349694382360212003286538549698169675217701555407820448705487134842623311153348873078972266337620575049219128548622996485652139430623323296749627127194400794264876387066943209562587671890155318583123028910830056232264092324341621808383802425831323592075184641724514268242803399912425294171839366324802014353453034292175782721428175302334967525749763938242096446316263656232624025571844604756738926874639192130259931923171925133000671998436282142562355007940095701859316556110717606346196070191968434346861120831905626790949532156806635940962056505940952605814321522185460103113580472287498815298415316487221112917914100499110384412687991174125327319406687671778223291430460896965590287997039197779685333477261520025203549187179000910387018738623782349520386576780077684604215779819328743771694816385581762867875599260269250558182287321739011970846918851240906016602359025001538830149199165878011937774676386818625978355614002304831057999424232018119083942615699068234906203794357615394524220426355429218555158219385826410337792552531250336334042537460195331137953
RSA Tool 算出的准确 D 值：
597373407487622321143865741339644585399805175534602906048500398004027514355319548259963205813148967692533604807742580525038291597114252114760288937144130962915733209463683391073618320650448112777094945558343016623495522195633019983208422213116889890166875402919856918439815840163856193284106064946583758789957409055401878119228445741986266276789002125788275255262782598199986816757217520199306469333091385671558141042443828519720840844612205546741521507602208210504968769251096691977629504372476185893091951913537857655204273504925512099798554530315421252429845763467955947091137583054897189820614376937575605844505871052114274124854717992255668456007963714086857868347087842354569892647988859877487659335398714163134185910521044146328455091690870687942171857316032772278065597643687000141010304239525841657476251864349002822068472655037074714679993245585095030366918739563213861142317262579490261932012081768607119956469355527345091498827500194564826969669009099736158738107529846150458897817694434778805241118731521520152876372202732403509612433298996631919358971943723863045396682604920877257205424148836689566659734417149096949677551590469591777390334811888051248345255115012247709439974036721418802103333570398040235670603310471
想了很多种办法测试，当 p/q/n 值很小的时候以上代码运算结果都准确，但是处理类似上面这种大数 python 返回结果全部错误，怀疑 python 大数运算时数据精度问题导致？
求 V 友指点迷津……
 |
1
faketemp OP 网上第四种方法：
```python import libnum #... phi = (p - 1) * (q - 1) d = libnum.modular.invmod(e, phi) print(d) ``` 结果与主贴三种方法返回一致，但经测错误…… |
 |
2
Corua 2020-07-02 09:42:33 +08:00  1
不是 python 的错，pq 也是对的。
直接看的时候都以为给出来的 e 是十进制，但实际上这题给的 e 是 0x65537 。 0x65537 的逆元就是第二个 d 了，所以才能解密对。 至于 rsatool，默认输入的是 16 进制，可能是你后输入的 e 是 65537，阴差阳错得出来了第二个 d 。 |
 |
3
Citrus 2020-07-02 10:15:07 +08:00 1
楼主贴的代码，只要吧 e = 65537 改成 e = 0x65537，均跟所谓准确 D 值相同。。。
|
 |
4
ThirdFlame 2020-07-02 10:20:28 +08:00 1
```
import gmpy2 import libnum flag = "flag{test1_test2_test3_test4}" p = 31093551302922880999883020803665536616272147022877428745314830867519351013248914244880101094365815998050115415308439610066700139164376274980650005150267949853671653233491784289493988946869396093730966325659249796545878080119206283512342980854475734097108975670778836003822789405498941374798016753689377992355122774401780930185598458240894362246194248623911382284169677595864501475308194644140602272961699230282993020507668939980205079239221924230430230318076991507619960330144745307022538024878444458717587446601559546292026245318907293584609320115374632235270795633933755350928537598242214216674496409625928797450473 q = 31093551302922880999883020803665536616272147022877428745314830867519351013248914244880101094365815998050115415308439610066700139164376274980650005150267949853671653233491784289493988946869396093730966325659249796545878080119206283512342980854475734097108975670778836003822789405498941374798016753689377992355122774401780930185598458240894362246194248623911382284169677595864501475308194644140602272961699230282993020507668939980205079239221924230430230318076991507619960330144745307022538024878444458717587446601559546292026245318907293584609320115374632235270795633933755350928537598242214216674496409625928997877221 n = p * q e = 65537 phi_n = (p - 1) * (q - 1) d = gmpy2.invert(e, phi_n) c = pow(libnum.s2n(flag), e, n) m = pow(c, d, n) print(libnum.n2s(m)) ``` |
|
5
faketemp OP 1
欲哭无泪 一脸懵逼.gif
这个问题困扰了两天，查找了大量资料，原来坑在 e 值，65537 竟然不是十进制？？！！！这出题人真是…… 还了解到 RSA Tool 工具的一个坑点： 右上角改变默认进制，竟然不会影响 e 值的进制！！！——也就是说不论你修改成默认显示什么进制，e 值永远都是十六进制！！！ 谢谢楼上解惑，学到很多 |
Select Language