V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
faketemp
V2EX  ›  问与答

RSA 已知 pde 计算 d 值的疑难杂症

  •  
  •   faketemp · 2020-07-02 07:00:38 +08:00 · 1292 次点击
    这是一个创建于 1588 天前的主题,其中的信息可能已经有所发展或是发生改变。

    常用 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 友指点迷津……

    faketemp
        1
    faketemp  
    OP
       2020-07-02 08:22:58 +08:00
    网上第四种方法:
    ```python
    import libnum

    #...

    phi = (p - 1) * (q - 1)
    d = libnum.modular.invmod(e, phi)
    print(d)
    ```

    结果与主贴三种方法返回一致,但经测错误……
    Corua
        2
    Corua  
       2020-07-02 09:42:33 +08:00   ❤️ 1
    不是 python 的错,pq 也是对的。
    直接看的时候都以为给出来的 e 是十进制,但实际上这题给的 e 是 0x65537 。
    0x65537 的逆元就是第二个 d 了,所以才能解密对。
    至于 rsatool,默认输入的是 16 进制,可能是你后输入的 e 是 65537,阴差阳错得出来了第二个 d 。
    Citrus
        3
    Citrus  
       2020-07-02 10:15:07 +08:00   ❤️ 1
    楼主贴的代码,只要吧 e = 65537 改成 e = 0x65537,均跟所谓准确 D 值相同。。。
    ThirdFlame
        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))

    ```
    faketemp
        5
    faketemp  
    OP
       2020-07-02 11:42:45 +08:00   ❤️ 1
    欲哭无泪 一脸懵逼.gif

    这个问题困扰了两天,查找了大量资料,原来坑在 e 值,65537 竟然不是十进制??!!!这出题人真是……

    还了解到 RSA Tool 工具的一个坑点:
    右上角改变默认进制,竟然不会影响 e 值的进制!!!——也就是说不论你修改成默认显示什么进制,e 值永远都是十六进制!!!

    谢谢楼上解惑,学到很多
    Citrus
        6
    Citrus  
       2020-07-02 17:45:30 +08:00 via iPhone
    @faketemp e 那旁边一个不会消失的 [HEX] 没看到么ˊ_>ˋ
    faketemp
        7
    faketemp  
    OP
       2020-07-03 06:37:59 +08:00 via iPhone
    @Citrus 看到了 只是想不明白为什么这样设置 既然允许自定义进制显示 那就整个界面统一处理省得出错嘛 有的会处理有的不处理 这个……
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3149 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 13:39 · PVG 21:39 · LAX 05:39 · JFK 08:39
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.