signed

QiShunwang

“诚信为本、客户至上”

Rsa 学习成果分享

2021/3/21 11:52:41   来源:

Rsa 学习成果分享

这是本人刚学到的内容,很怕自己理解有误,形成误导。朋友们见谅。

首先对于介绍一下RSA算法

1.先去两个质数p,q 得到 n = pq
2.求得 <n 且和n互素 的所有数 的个数 nub = (p-1)
(q-1)
3.用整数e (e和nub互素) 做加密密钥
4.取满足 (e*d)%nub == 1 条件的 d 做解密密钥
5.加密算法为c = (me)%n
6.解密算法为m = (c
d)%n

如何理解呢?

这边先介绍一下欧拉函数 令欧拉函数为 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)

再介绍一下 费马-欧拉定理
在这里插入图片描述

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

现在我先来说一下核心点:加密解密后得到原明文的原理
即:m == ((me)%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是个合数 == 4347
那我就不妨用43
49做p和q,n为2021;
而 nub == 4247 == 1932
不妨取得 13 与 1932 互素。
现在又开始要算 d 了。
由 (13
d)%1932 == 1 得:
13d == 1 + 1932x
只要求得一个满足该方程的根
也就是说 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 = 13
    d = 1189
    def ecn(self,i):
        return i**self.e%2021

    def dec(self,i):
        return i**self.d%2021

if __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 = 13
    def ecn(self,i):
        return i**self.e%2021

class Mail:

    m = str
    c = []
    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 = 1189
    def dec(self,i):
        print("请自己编辑一下rsa_dec吧")
        return 0


class ReadMail:

    c = str
    m = ""
    r = []

    def __init__(self):
        self.c = input("输入想要翻译的密文:")
        temp = ""
        i = 0
        for y in self.c:
            temp += y
            i += 1
            # 读取4个数字为一位
            if i%4==0:
                # 对每一位进行解密
                x = (Rsa_2021.dec(Rsa_2021(), int(temp)))
                # 把数字翻译成对应的字符
                self.m += chr(x)
                # 清空 temp
                temp = ""
        # 输出翻译好的明文
        print(self.m)

if __name__ == '__main__':
    ReadMail()

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

10501858030303031734042603921734175403031444

自动生成公私钥代码

def isPrime(i):
x = int(i**0.5)
while(x-1):
if i%x == 0:
return False
x -= 1
return True

def ToNub(p,q):
return (p-1)*(q-1)

def isCoprime(e,nub):
temp = nub
if e < nub:
N1 = 1
E1 = 0
N2 = 0
E2 = 1
else:
N1 = 0
E1 = 1
N2 = 1
E2 = 0
while (e != nub and e != 0 and nub != 0):
if e < nub:
tempn = N2
tempe = E2
x = int(nub/e)
N2 = N1 - xN2
E2 = E1 - x
E2
N1 = tempn
E1 = tempe
nub = nub % e
else:
tempn = N2
tempe = E2
x = int(e / nub)
N2 = N1 - x * N2
E2 = E1 - x * E2
N1 = tempn
E1 = tempe
e = e % nub
if (e == 1 or nub == 1):
if E1 < 0:
E1 += temp
print(“d的值为:”,E1)
return True
else:
return False

if name == ‘main’:
p = int(input(“输入素数p:”))
while not isPrime§:
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。