search

techiall / Blog

🍋 [My Blog] See discussions
https://github.com/techiall/Blog/discussions
MIT License
8 stars 1 forks source link

CTF | RSA #35

Open techiall opened 5 years ago

techiall commented 5 years ago

RSA 参数

求 d

已知 p，q，e

def get_d(p: int, q: int, e: int) -> int:
    r = (p - 1) * (q - 1)
    i = 0
    while True:
        if (1 + r * i) % e == 0:
            return '%d' % (1 + r * i // e) # 除 和 取整除 两者有区别
        i += 1

if __name__ == '__main__':
    p = 473398607161
    q = 4511491
    e = 17
    x = get_d(p=p, q=q, e=e)
    print(x)

用了网上别人代码，里面有一个坑，愣是坑了很久。

别人是用 python2 版本，我用的是 python3，在最后的 除 和 整除 这里有区别。

除 得到的答案是 125631357777427552。

整除 得到的答案是 125631357777427553 。

使用 整除 得到的才是正确答案。

或者使用 decimal 模块

求明文

已知 公钥 和 密文，求明文

  1. 已知 公钥，得到 n 和 e
  2. 分解 n 得到 p 和 q
  3. 得到 d
  4. 解密密文
if __name__ == '__main__':
        c =
        d =
        n =
        x = pow(c, d, n)
        print(bytes().fromhex('%x' % x))

decimal 模块

要求超过17位的精度分析

python默认的是17位小数的精度，但是这里有一个问题，就是当我们的计算需要使用更高的精度（超过17位小数）的时候该怎么做呢？

  1. 使用格式化(不推荐)

  2. 高精度使用decimal模块，配合getcontext

默认的context的精度是28位，可以设置为50位甚至更高，都可以。这样在分析复杂的浮点数的时候，可以有更高的自己可以控制的精度。其实可以留意下context里面的这rounding=ROUND_HALF_EVEN 参数。ROUND_HALF_EVEN， 当half的时候，靠近even.

谈谈关于Python里面小数点精度控制的问题

利用 decimal 模块，改良求 d 代码

from decimal import *

def get_d(p: int, q: int, e: int) -> str:
    r = Decimal((p - 1) * (q - 1))
    i = 0
    while True:
        if (1 + r * i) % e == 0:
            return '%d' % (1 + r * i / e)
        i += 1

if __name__ == '__main__':
    getcontext().prec = 100
    p = 473398607161
    q = 4511491
    e = 17
    x = get_d(p=p, q=q, e=e)
    print(x)

求明文

已知 p，q，e 和 密文 c，求明文

from decimal import *

def get_d(p: int, q: int, e: int) -> int:
    r = Decimal((p - 1) * (q - 1))
    i = 0
    while True:
        if (1 + r * i) % e == 0:
            return '%d' % (1 + r * i / e)
        i += 1

def get_n(p: int, q:int) -> int:
    return q * p

if __name__ == '__main__':
    getcontext().prec = 1000

    p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
    q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
    e = 65537
    c = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034
    d = get_d(p=p, q=q, e=e)
    n = get_n(p=p, q=q)
    print(d)
    print(pow(c, Decimal(d), n))

参考文献