1.RSA密钥生成算法
密钥生成算法为用户生成加解密算法中使用的公私密钥对，分为以下几个步骤：
（1）选取两个安全大素数p和q（“大”指其长度要足够，目前推荐长度至少1024比特长）；
（2）计算乘积n=p*q，(n)=(p-1)(q-1),其中(n)为n的欧拉函数；
（3）随机选取整数e(1<e<(n))作为公钥，要求满足gcd(e,(n))=1,即e与(n)互素；
（4）用Euclid扩展算法计算私钥d，以满足d*e≡1(mod(n))，即d≡ (mod(n)),则e和n是公钥，d是私钥；
注意，加解密算法中两个素数p和q不再需要，可销毁但绝不能泄露。
例如：假设p=13，q=17；
计算 n=pq=1317=221，则(n)=(p-1)(q-1)=(13-1)*(17-1)=192.
选取公钥e=11（一般为素数），满足1<e<(n),且满足gcd(e,(n))=1.通过Euclid扩展算法求得满足公式d*e≡1(mod192)的d=35.
所以，得到公钥(e,n)为(11,221),私钥d为35.
2.RSA加密算法
1）加密过程
加密时首先将明文比特串分组，使得每一个分组对应的十进制数小于n，即分组长度小于，然后对每个明文分组
做加密运算，具体过程分为如下步骤：
（1）获得接收方公钥(e,n)；
（2）把消息M分组为长度为L(L<)的消息分组M=
；
（3）使用加密算法计算出密文
;
（4）将密文C发送给接收方；
2）解密过程
（1）接收方收到密文C,;
（2）使用私钥d逐一恢复明文分组,
；
（3）得明文消息 M=；
利用所学的生成素数的算法，生成两个尽可能的素数，进一步实现RSA的加密算法。
import random
def alpha(cipher): # 预处理,去掉空格以及回车
c = ''
for i in range(len(cipher)):
if (cipher[i].isalpha()):
c += cipher[i]
print("c:"+c)
return c
def fastExpMod(b, n, m):
'''
return : b^n mod m
'''
result = 1
while n != 0:
if (n & 1) == 1: # 按位与操作
result = (result * b) % m
b = (b * b) % m
n = n >> 1 # 位数右移操作
return result
def Euclid(a, b):
'''
欧几里得算法 ax + by = gcd(a,b)
Return : [x , y , gcd(a,b)]
'''
X = [1, 0, a]
Y = [0, 1, b]
while Y[2] != 0:
Q = X[2] // Y[2]
NEW_Y = [i * Q for i in Y]
T = list(map(lambda x: x[0] - x[1], zip(X, NEW_Y)))
X = Y.copy()
Y = T.copy()
return X
def fermatPrimeTest(m, k):
'''
费马素性检验算法
m : 给定整数
k : 安全参数，重复K次
'''
if m % 2 == 0:
return False
for i in range(k):
a = random.randint(2, m - 2)
g = Euclid(a, m)
if g[2] == 1:
r = fastExpMod(a, m - 1, m)
if r == 1:
continue
else:
return False
else:
return False
return True
def findPrime(lower, upper):
'''
return : 一个位于upper和lower之间的素数
'''
while True:
n = random.randint(lower, upper)
if fermatPrimeTest(n, 6) == True:
return n
def selectE(fn):
'''
fn : euler function
Return : e
'''
while True:
e = random.randint(1, fn)
temp = Euclid(e, fn)
if temp[2] == 1:
return e
def keyGenerate(lower, upper):
'''
给定两个素数p和q生成的区间
return : e,n,d
'''
p = findPrime(lower, upper)
q = findPrime(lower, upper)
print("p:" + str(p) + " q:" + str(q))
# print("q:"+str(q))
n = p * q
fn = (p - 1) * (q - 1)
e = selectE(fn)
temp = Euclid(e, fn) # 欧几里得算法求逆元
d = temp[0]
if d < 0: # 由于e和fn互素故一定存在逆元
d = d + fn # 保证d为正数
return e, n, d
def transfer(plaintext,n):
length=len(plaintext)
arrayNum=[0 for i in range(length)]
count=[0 for i in range(length)]
j=0
for i in range(len(plaintext)):
if(plaintext[i].isupper()):
arrayNum[i]=ord(plaintext[i])-ord('A')+1
elif(plaintext[i].islower()):
arrayNum[i]=ord(plaintext[i])-ord('a')+1
elif(plaintext[i].isdigit()):
arrayNum[i]=ord(plaintext[i])-ord('0')+1
if(count[j]*100+arrayNum[i]<n):
count[j]=count[j]*100+arrayNum[i]
else:
j=j+1
count[j]=arrayNum[i]
return count,j+1
letter_list = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
def sout(miwen,mingwen,length,m):
miwen1=[0 for i in range(len(m))]
mingwen1=[0 for i in range(len(m))]
miwen2=[0 for i in range(len(m))]
mingwen2=[0 for i in range(len(m))]
str_miwen = ''
str_mingwen = ''
j=0
j_last=0
for i in range(length):
while(miwen[i]/100!=0):
miwen1[j]=miwen[i]%100%26
j=j+1
if(j==len(m)):
break
miwen[i]=int(miwen[i]/100)
miwen2= [0 for i in range(len(m))]
j_last_for_miwen2 = j_last
for k in range(j - j_last):
miwen2[k] = miwen1[j_last_for_miwen2]
j_last_for_miwen2 = j_last_for_miwen2 + 1
miwen2[0:j - j_last] = miwen2[j - j_last - 1::-1]
for i in range(j - j_last):
str_miwen += letter_list[miwen2[i]%26 - 1]
j_last = j
j=0
j_last=0
for i in range(length):
while(mingwen[i]/100!=0):
mingwen1[j]=mingwen[i]%100
j=j+1
if (j == len(m)):
break
mingwen[i]=int(mingwen[i]/100)
mingwen2 = [0 for i in range(len(m))]
j_last_for_mingwen2=j_last
for k in range(j-j_last):
mingwen2[k]=mingwen1[j_last_for_mingwen2]
j_last_for_mingwen2=j_last_for_mingwen2+1
mingwen2[0:j-j_last]=mingwen2[j-j_last-1::-1]
for i in range(j-j_last):
str_mingwen += letter_list[mingwen2[i]%26-1]
j_last=j
print("\nEncryption of PlainText: ")
print(str_miwen)
print("\nDecryption of CipherText: ")
print(str_mingwen)
def start():
e, n, d = keyGenerate(2**512,2**513) # 密钥生成
# 更改keyGenerate函数的两个参数，可以改变生成素数的位数大小。
print("public key (e,n):", end="")
print("(" + str(e) + " , " + str(n) + ")\n")
print("private key d: " + str(d) + "\n")
m=input("please input m:")
m=alpha(m)
numArray,length=transfer(m,n)
miwen=[0 for i in range(len(m))]
mingwen=[0 for i in range(len(m))]
for i in range(length):
c = fastExpMod(numArray[i], e, n) # 加密 c为密文 m^e mod n
miwen[i]=c
x = fastExpMod(c, d, n) # 解密 c^d mod n
mingwen[i]=x
sout(miwen,mingwen,length,m)
if __name__ == "__main__":
start()
本文转载自: https://blog.csdn.net/Yuuaaa/article/details/127078210
版权归原作者 Yuaaa. 所有， 如有侵权，请联系我们删除。
版权归原作者 Yuaaa. 所有， 如有侵权，请联系我们删除。