本题需要计算所有满足条件e的总和，需要在e加密的情况下为加密的信息数目是最小的。所以首先我们需要编写计算最大公约数的函数gcd()这里运用欧几里得方法得到，减少时间复杂度。

1
2
3
4
5
def gcd(a,b):
    if b ==0:
        return a
    else: 
        return gcd(b,a%b)

由题目知道未加密信息满足算式：me≡mmodnm^{e}\equiv m mod n则未加密的信息数目就是该算式解的个数。又n=p∗qn = p*q可以得到解个数公式该方程解个数为(gcd⁡(e−1,p−1)+1)∗(gcd⁡(e−1,q−1)+1)(gcd⁡(e-1,p-1)+1)*(gcd⁡(e-1,q-1)+1)，由此我们能够遍历所有的e的可能，并且记录下对应未加密信息数目。最后统计出最小的未加密信息数值，累加得到所有满足条件的e。

1
2
3
4
5
6
7
8
9
10
11
12
if __name__ == "__main__":
    p=1009
    q=3643
    phi = (p-1)*(q-1)
    e_state = {}
    for e in range(2,phi):
        if gcd(e,phi)==1:
            e_state[e]=(gcd(e-1,p-1)+1)*(gcd(e-1,q-1)+1)
    min_result = min(e_state.values())
    print(f"未加密信息的数目为最小值:",min_result)
    e_sum = sum([i for i in e_state if e_state[i] == min_result])
    print(f"e的和",e_sum)

最后运行程序得到答案：

1
2
未加密信息的数目为最小值: 9
e的和 399788195976

2.实施RSA（link）

本题要我们实施RSA密码，首先需要编写一个生成大素数的函数，但是在题目中说生成大素数不是重点可以运用已经存在库函数实现。所以我使用getPrime(bits)来得到随机大素数，需要引用如下库函数。

1
from Crypto.Util.number import getPrime

首先我们需要编写一个运算逆的函数invmod(a, b)，题目中提示运用欧几里得方法来运算。首先我们得到a和b的最大公约数，在ab互素的情况下得到ax+by=1中x和y的值。进而知道x%b就是a对模b的逆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def invmod(a, b):
    def egcd(a, b):
        if a == 0:
            return b, 0, 1
        g, x1, y1 = egcd(b % a, a)
        x = y1 - (b // a) * x1
        y = x1
        return g, x, y

    g, x, y = egcd(a, b)
    if g != 1:
        raise ValueError('模逆不存在')
    else:
        return x % b

然后我们需要编写生成公钥和私钥的函数def generate_rsa_keys(bits=1024)这里假设生成的大素数长度为1024bits。需要注意是的生成的pq必须满足et和e要互素，否则需要提示‘e和et不互素，需要重新生成p和q’重新运行本程序。

1
2
3
4
5
6
7
8
9
10
def generate_rsa_keys(bits=1024):
    p = getPrime(bits)
    q = getPrime(bits)
    e = 3  
    n = p * q
    et = (p-1)*(q-1)
    if et % e == 0:
        raise ValueError("e和et不互素，需要重新生成p和q")
    d = invmod(e,et)
    return (e,n),(d,n)

然后就是RSA的加密和解密函数

1
2
3
4
def RSA_e(m,public_key):
    e,n = public_key
    c = pow(m,e,n)
    return c
1
2
3
4
def RSA_d(c,private_key):
    d,n = private_key
    m = pow(c,d,n)
    return m

最后需要验证我们的函数，首先验证题目中提供对数字‘42’的加密和解密，编写如下主函数：

1
2
3
4
5
6
7
8
9
def main():
    public_key, private_key = generate_rsa_keys(bits=1024)
    print("Public Key:", public_key)
    print("Private Key:", private_key)
    m = 42
    c = RSA_e(m,public_key)
    m = RSA_d(c,private_key)
    print("Encrypted message:",c)
    print("Decrypted message:",m)

测试结果如下：

1
2
3
4
Public Key: (3,18584674673132354443799672761999941195666000202227614111637155188539270102977177731778018459960150317179869096463577703162143774936243688426920345316552503579131340867655377725303228596377386065225388154913735169967323835455241628652156536489258197597460873974039760487200652925252344940958437709182291610007034125308781140179215153252229512228360941259630163260655799104054957802710229055844388887031905568258883483304070344807372760151934114113984889764718190341459171281490147513254095481591774318259828757818433860151920192737540296635075104425833323314600516252161361510537724590619394519884470682648995016113887)
Private Key: (12389783115421569629199781841333294130444000134818409407758103459026180068651451821185345639973433544786579397642385135441429183290829125617946896877701669052754227245103585150202152397584924043483592103275823446644882556970161085768104357659505465064973915982693173658133768616834896627305625139454861073337838844392286656582400222672086962170281752665081946086647483823131098260696325149265363477667565205536882892789035367095109247178601111866806090173693393156455850235147511096016082968414410933328693661222516965388865455131890742039547494515108404863454559206641078024375171187968771304813410281675569739684491, 18584674673132354443799672761999941195666000202227614111637155188539270102977177731778018459960150317179869096463577703162143774936243688426920345316552503579131340867655377725303228596377386065225388154913735169967323835455241628652156536489258197597460873974039760487200652925252344940958437709182291610007034125308781140179215153252229512228360941259630163260655799104054957802710229055844388887031905568258883483304070344807372760151934114113984889764718190341459171281490147513254095481591774318259828757818433860151920192737540296635075104425833323314600516252161361510537724590619394519884470682648995016113887)
Encrypted message: 74088
Decrypted message: 42

现在测试对一个字符串‘Happy Holloween!’的加解密结果，编写如下主函数：

1
2
3
4
5
6
7
8
9
10
11
def main():
    public_key, private_key = generate_rsa_keys(bits=1024)
    print("Public Key:", public_key)
    print("Private Key:", private_key)
    message = "Happy Holloween!"
    m = int.from_bytes(message.encode('utf-8'), byteorder='big')
    c = RSA_e(m,public_key)
    print("Encrypted message:",c)
    m = RSA_d(c,private_key)
    message = m.to_bytes((m.bit_length() + 7) // 8, byteorder='big').decode('utf-8')
    print("Decrypted message:",message)

测试结果如下：

1
2
3
4
Public Key: (3, 18746808571300120504075819075682594108587535388098754677870678403048294162399846334137445538730775144599084227460865632005107133341672067110771050673013583813667197683875501302973912467166141154341320814285678147761034215354099126591602306404085973955963843526566924290314499362955841196440900414874353607804365254706041430929565530836774408396058906536328668430766073670852859439307267025218730395514185697403199973733802260324197180412572479037624518165071365862506194984607606206276475436694257745689639894210738259160828771680605477570068261833446369430881080564601723636695474262854104359084128262572628557179013)
Private Key: (12497872380866747002717212717121729405725023592065836451913785602032196108266564222758297025820516763066056151640577088003404755561114711407180700448675722542444798455917000868649274978110760769560880542857118765174022810236066084394401537602723982637309229017711282860209666241970560797627266943249569071869393919769818227415018394576223101062948188806376352414567503277949919018535889622512491130511685307096516768916314421416945739691371071076417554540102038686665301000050159474220726679317018289250423738605246696532022745489211634236528769821582503745462361003025656079851791180146414307639207005583822966476907, 18746808571300120504075819075682594108587535388098754677870678403048294162399846334137445538730775144599084227460865632005107133341672067110771050673013583813667197683875501302973912467166141154341320814285678147761034215354099126591602306404085973955963843526566924290314499362955841196440900414874353607804365254706041430929565530836774408396058906536328668430766073670852859439307267025218730395514185697403199973733802260324197180412572479037624518165071365862506194984607606206276475436694257745689639894210738259160828771680605477570068261833446369430881080564601723636695474262854104359084128262572628557179013)
Encrypted message: 890564482417655822788709386116389927760915707730126623223467631024461475735568125139054708085662317206414437078625
Decrypted message: Happy Holloween!

实验总结

本次实验我充分了解了RSA算法的运行过程，并且更加熟悉了运用公钥和私钥加解密的程序编写。在第一个实验里面复习了计算解个数的公式。在第二个实验里面我起初的运行速度很慢，后来仔细读题发现模逆运算中面对大素数的运算开销很大需要运用欧几里得算法来减少时间复杂度。在实验二对字符串加解密的时候需要把字符串中的字节转换为整数再进行运算。最后解密时需要把整数转换为二进制向上取整进而算出需要多少个字节表示，再把整数转换为字节数组再将字节数组解码为 UTF-8 编码的字符串得到最终答案。

源代码连接

https://github.com/cool-chicken/cryptography-exp/tree/main/密码学实验三