Rsa 学习成果分享

如何理解呢？

这边先介绍一下欧拉函数 令欧拉函数为 def Euler(n)
这个函数是求|比n小 且于n互素 的所有数 的个数|
比如 5 有{1，2，3，4} 则 得4
9有{1，2，4，5，7，8} 则 得6
而n=qp 有{p,2p,3p,4p,……,qp,1q,2q,3q,……,(qp.这个重复了)}
则Euler(n) 得(p-1)(q-1)

再介绍一下 费马-欧拉定理

比如 2^10 = 1024 ,1024%9=7
和 10%6 = 4 , 2^4 = 16 ，16%9 = 7
的结果一样

现在我先来说一下核心点：加密解密后得到原明文的原理
即：m == ((m^e)%nd)%n
可以发现 等号右边可以简化 得*(1)： (m^(ed))%n
运用 欧拉定理 得*(2)*
再根据我们的第4点设定：得*(3)* (e*d)%nub == 1

因此得以验证。

那抱着疑惑来试试去验证引理 欧拉定理

# 如 当x和5互素时: x%5 不论x为何值 答案只会在{1,2,3,4}中出现
# 而 {1,2,3,4}被称作5的剩余类(有4个)
#
# (此行为下一行的上标行)         _ _ _ _    ___
# 而 对于任意素数p有p-1个剩余类：1,2,3,4,……,p-1
#
#                 __ __ __    _____
# 不妨把它们标记为 a1,a2,a3,……,a(p-1) 【0】
#
#         __    __      __      __
# 显然 当 a1 != a2 时: x*a1 != x*a2 【1】;
#
#                 __ __ __   ______
# 则有 (x**(p-1))*a1*a2*a3……*a(p-1)  【2】
#
#         __     __     __        ______
# 等于 (x*a1)*(x*a2)*(x*a3)*……*(x*a(p-1)) 【3】
#                               ____      ___
# 而根据 【1】 可知 【3】中任意两两(x*a[i]),(x*a[j])不等。
#
# 所以!!! 【3】是一个新的和【0】顺序不同的一组剩余类;
# 可知： 【3】 == 【0】（所有的相乘）
# 有因为 【2】 == 【3】 所以 【2】 == 【0】（所有的相乘）
#
#               __ __ __   ______     __ __ __   ______
# 即 (x**(p-1))*a1*a2*a3……*a(p-1)  == a1*a2*a3……*a(p-1)
# 约掉共同部分可得 x**(p-1) == 1;
# 也写作 x**(p-1) == T(T代表一个循环);
# 便可得 配图
#
# 代入实际参数一下便于理解：
# (9的等于类有{1，2，4，5，7，8})
# 对于 (2**10)%9
# 有     (2**10)%9 == x%9
# 等价于  ((2**4)*(2*1)*(2*2)*(2*4)*(2*5)*(2*7)*(2*8))%9 == (1*2*4*5*7*8)%9
# 算一下得 ((2**4)*2*4*8*7*5*1)%9 == (1*2*4*5*7*8)%9
# 左边调整一下顺序得 ((2**4)*1*2*4*5*7*8)%9 == (1*2*4*5*7*8)%9
# 左右两边同时消掉 1*2*4*5*7*8 得到 (2**10)%9 == (2**4)%9 == 16%9 == 7

既然我们已经了解了加密解密的原理，那么我们开始生成密钥吧

今年是2021年，重所周知(doge)2021是个合数 == 43 * 47
那我就不妨用43 * 49做p和q,n为2021;
而 nub == 42 * 47 == 1932
不妨取得 13 与 1932 互素。
现在又开始要算 d 了。
由 (13 * d)%1932 == 1 得:13 * d == 1 + 1932 * x
只要求得一个满足该方程的根
也就是说 1 怎么用 13 和 1932 来表示
这个可以运用辗转相除法
令a=1932,b=13;
1932/13 == 148……8 【1】
13/8 == 1……5 【2】
8/5 == 1……3 【3】
5/3 == 1……2 【4】
3/2 == 1……1 【5】

【1】 8 == 1932 - 148 * 13 == a - 148b
【2】 5 == 13 - 8 == b - (a - 148b) == 149b - a
【3】 3 == 8 - 5 == (a - 148b) - (149b - a) == 2a - 297b
【4】 2 == 446b - 3a
【5】 1 == 5a - 743b
得 1 == 5 * 1932 - 743 * 13
____ ____
所以 d == -743 == 1189 (1932-743)
不妨验证一下

a = 13*1189
b = a%1932
print(a,b)

密钥便求出来了
测试一下加密解密功能吧

功能测试

#  注意 e 和 d 不能想这样放在同一个函数里
class Rsa_2021:e = 13d = 1189def ecn(self,i):return i**self.e%2021def dec(self,i):return i**self.d%2021if __name__ == '__main__':# 输入明文m = int(input("输入一个数字："))# 进行加密c = Rsa_2021.ecn(Rsa_2021(),m)# 经行解密m = Rsa_2021.dec(Rsa_2021(),c)print("得到密文为：",c)print("得到明文为：",m)

这边是我编写的加密解密算法

这个加密很粗糙，可以根据词频来破解。

class Rsa_2021:e = 13def ecn(self,i):return i**self.e%2021class Mail:m = strc = []r = []def __init__(self):self.m = input("输入想要发送的消息(不能含中文)：")for x in self.m :# 把字符转数字y = ord(x)# 进行加密self.c.append(Rsa_2021.ecn(Rsa_2021(),y))# pop()为补零输出使4位为一位self.pop()def pop(self):for x in self.c:if(x<1000):print("0",end='')if(x<100):print("0",end='')if(x<10):print("0",end='')print(x,end='')print("")if __name__ == '__main__':Mail()

class Rsa_2021:d = 1189def dec(self,i):print("请自己编辑一下rsa_dec吧")return 0class ReadMail:c = strm = ""r = []def __init__(self):self.c = input("输入想要翻译的密文：")temp = ""i = 0for y in self.c:temp += yi += 1# 读取4个数字为一位if i%4==0:# 对每一位进行解密x = (Rsa_2021.dec(Rsa_2021(), int(temp)))# 把数字翻译成对应的字符self.m += chr(x)# 清空 temptemp = ""# 输出翻译好的明文print(self.m)if __name__ == '__main__':ReadMail()

这边是我加密后得到的密文，算一下原文是什么吧

10501858030303031734042603921734175403031444

自动生成公私钥代码

def isPrime(i):x = int(i**0.5)while(x-1):if i%x == 0:return Falsex -= 1return Truedef ToNub(p,q):return (p-1)*(q-1)def isCoprime(e,nub):temp = nubif e < nub:N1 = 1E1 = 0N2 = 0E2 = 1else:N1 = 0E1 = 1N2 = 1E2 = 0while (e != nub and e != 0 and nub != 0):if e < nub:tempn = N2tempe = E2x = int(nub/e)N2 = N1 - x*N2E2 = E1 - x*E2N1 = tempnE1 = tempenub = nub % eelse:tempn = N2tempe = E2x = int(e / nub)N2 = N1 - x * N2E2 = E1 - x * E2N1 = tempnE1 = tempee = e % nubif (e == 1 or nub == 1):if E1 < 0:E1 +=  tempprint("d的值为:",E1)return Trueelse:return Falseif __name__ == '__main__':p = int(input("输入素数p:"))while not isPrime(p):p = int(input("p不是质数请重新输入:"))q = int(input("输入素数q:"))while not isPrime(q):q = int(input("q不是质数请重新输入:"))nub = ToNub(p,q)print(nub)e = int(input("请输入和nub互素的e:"))while not isCoprime(e,nub):e = int(input("e不满足条件,请重新输入:"))

好啦，没啦。

这些虽然都是我刚从各个地方学的，但所有整合都是我一键盘一鼠标慢慢敲出来的自己的理解。
如果我说的不好，建议去看BV1W5411H7Hy和BV1xE411W7e5。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！