RSA Python 问题

Question

我在让 python 程序解密带有 RSA 问题的消息时遇到问题。出于某种原因，我的 Python 程序停滞了，实际上只是没有输出任何东西。有人知道为什么吗？

n = 23952937352643527451379227516428377705004894508566304313177880191662177061878993798938496818120987817049538365206671401938265663712351239785237507341311858383628932183083145614696585411921662992078376103990806989257289472590902167457302888198293135333083734504191910953238278860923153746261500759411620299864395158783509535039259714359526738924736952759753503357614939203434092075676169179112452620687731670534906069845965633455748606649062394293289967059348143206600765820021392608270528856238306849191113241355842396325210132358046616312901337987464473799040762271876389031455051640937681745409057246190498795697239
p = 153143042272527868798412612417204434156935146874282990942386694020462861918068684561281763577034706600608387699148071015194725533394126069826857182428660427818277378724977554365910231524827258160904493774748749088477328204812171935987088715261127321911849092207070653272176072509933245978935455542420691737433
c = 18031488536864379496089550017272599246134435121343229164236671388038630752847645738968455413067773166115234039247540029174331743781203512108626594601293283737392240326020888417252388602914051828980913478927759934805755030493894728974208520271926698905550119698686762813722190657005740866343113838228101687566611695952746931293926696289378849403873881699852860519784750763227733530168282209363348322874740823803639617797763626570478847423136936562441423318948695084910283653593619962163665200322516949205854709192890808315604698217238383629613355109164122397545332736734824591444665706810731112586202816816647839648399
e = 65537
q = 156408916769576372285319235535320446340733908943564048157238512311891352879208957302116527435165097143521156600690562005797819820759620198602417583539668686152735534648541252847927334505648478214810780526425005943955838623325525300844493280040860604499838598837599791480284496210333200247148213274376422459183
phi = (q-1)*(p-1)
d = pow(e,-1,phi)
m = pow(c,d)%n
print(m)

对于奇怪的代码格式，我深表歉意。提前致谢。

Answer 1

假设数学是正确的（我没有检查），你肯定想改变这个：

m = pow(c,d)%n

对此：

m = pow(c, d, n)

第一个拼写在除以 n 以求余数之前计算 c**d 至完全精度。那可能会非常昂贵。第二种方法一直在减少中间结果，在幕后，mod n 一直，并且永远不需要对大于 n**2.

的整数进行算术运算

因此，替换代码的最后一行并继续：

>>> m = pow(c, d, n) # less than an eyeblink
>>> m
14311663942709674867122208214901970650496788151239520971623411712977120586163535880168563325
>>> pow(m, e, n) == c
True

因此，通过依次对 d 和 e 的幂进行 mod 平方幂来恢复原始“消息”(c)。

Answer 2

@TimPeters 已经提出的主要问题是 pow(c,d)%n，应将其替换为 pow(c, d, n) 以获得巨大的性能改进。

既然你的问题已经得到解答，我决定再深入一点。受您问题的启发，我决定根据 WikiPedia article 从头开始实施大部分 RSA 数学。也许这有点离题（不是你问的），但我相信下一个代码对于想在普通 Python 中尝试 RSA 的人来说是有用的演示，并且可能对你也有帮助。

下一段代码的所有变量都与维基百科中的名称相同，公式也取自那里。 重要！，我的代码中缺少一件事，为了简单起见，我没有实现填充（只是为了展示经典的 RSA 数学），正确（例如 OAEP) 在你的系统中填充，没有它就会存在对 RSA 的攻击。此外，我仅使用 512 位作为模数的主要部分，实际系统应该有数千位才能保证安全。此外，我不对消息进行任何拆分，应将长消息拆分为子消息并进行填充以适应模数位大小。

Try it online!

import random

def fermat_prp(n):
    # https://en.wikipedia.org/wiki/Fermat_primality_test
    assert n >= 4, n
    for i in range(24):
        a = (3, 5, 7)[i] if n >= 9 and i < 3 else random.randint(2, n - 2)
        if pow(a, n - 1, n) != 1:
            return False
    return True

def gen_prime(bits):
    assert bits >= 3, bits
    while True:
        n = random.randrange(1 << (bits - 1), 1 << bits)
        if fermat_prp(n):
            return n
            
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
    
def lcm(a, b):
    return a * b // gcd(a, b)
            
def egcd(a, b):
    # https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
    ro, r, so, s, to, t = a, b, 1, 0, 0, 1
    while r != 0:
        q = ro // r
        ro, r = r, ro - q * r
        so, s = s, so - q * s
        to, t = t, to - q * t
    return ro, so, to

def demo():
    # https://en.wikipedia.org/wiki/RSA_(cryptosystem)
    bits = 512
    p, q = gen_prime(bits), gen_prime(bits)
    n = p * q
    ln = lcm(p - 1, q - 1)
    e = 65537
    print('PublicKey: e =', e, 'n =', n)
    d = egcd(e, ln)[1] % ln
    mtext = 'Hello, World!'
    print('Plain:', mtext)
    m = int.from_bytes(mtext.encode('utf-8'), 'little')
    c = pow(m, e, n)
    print('Encrypted:', c)
    md = pow(c, d, n)
    mdtext = md.to_bytes((md.bit_length() + 7) // 8, 'little').decode('utf-8')
    print('Decrypted:', mdtext)

if __name__ == '__main__':
    demo()

输出：

PublicKey: e = 65537 n = 110799663895649286762656294752173883884148615506062673584673343016070245791505883867301519267702723384430131035038547340921850290913097297607190494504060280758901448419479350528305305851775098631904614278162314251019568026506239421634950337278112960925116975344093575400871044570868887447462560168862887909233
Plain: Hello, World!
Encrypted: 51626387443589883457155394323971044262931599278626885275220384098221412582734630381413609428210758734789774315702921245355044370166117558802434906927834933002999816979504781510321118769252529439999715937013823223670924340787833496790181098038607416880371509879507193070745708801500713956266209367343820073123
Decrypted: Hello, World!

RSA Python 问题

RSA Python Issue

python

rsa