• def RSA(p,q,m): print(f"1: p: {p} q: {q} M: {m}") n = p*q print(f"2: n = p*q {p} *{q} = {n}") temp = (p-1)*(q-1) print(f"3: (p-1)*(q-1) = {p-1} *{q-1} = {temp}") e = 1 print(f"4:e should be less than ...
def RSA(p,q,m):

print(f"1: p: {p} q: {q} M: {m}")
n = p*q
print(f"2: n = p*q {p} *{q} = {n}")
temp = (p-1)*(q-1)
print(f"3: (p-1)*(q-1) = {p-1} *{q-1} = {temp}")
e = 1
print(f"4:e should be less than n and relatively prime to (p-1)*(q-1) = {p-1} *{q-1} = {temp}")
for _ in range(1,n):
if temp%_ is not 0:
e = _
break
print(f"Hence, e is {e}")
print("5: Here, we should find an integer d such that e*d mod((p-1)*(q-1)) = 1")
d = 1
for _ in range(1,temp):
if e*_ % temp == 1:
d = _
print(f"Here d = {_}")
print(f"we have e*d mod((p-1)*(q-1)) = {e*d} mod {temp} = 1")
print(f"6: Public key = (e,n) = ({e},{n})")
print(f"7: Private key = (d,n) = ({d},{n})")
encrypted = m**e%n
print(f"Encrypted message: c = m^e mod n = {m}^{e} mod {n} = {encrypted}")
decrypted = encrypted**d%n
print(f"Decrypted message: m = c^d mod n = {encrypted}^{d} mod {n} = {decrypted}")

RSA(p = 17,q = 31,m = 5)

# print(160%2)

运行结果：

1: p: 17 q: 31 M: 5
2: n = p*q 17 *31 = 527
3: (p-1)*(q-1) = 16 *30 = 480
4:e should be less than n and relatively prime to (p-1)*(q-1) = 16 *30 = 480
Hence, e is 7
5: Here, we should find an interger d such that e*d mod((p-1)*(q-1)) = 1
Here d = 343
we have e*d mod((p-1)*(q-1)) = 2401 mod 480 = 1
6: Public key = (e,n) = (7,527)
7: Private key = (d,n) = (343,527)
Encrypted message: c = m^e mod n = 5^7 mod 527 = 129
Decrypted message: m = c^d mod n = 129^343 mod 527 = 5
[Finished in 0.6s]

展开全文
• 使用python2.7写的RSA加密解密，支持超过10^10的大素数，可以加解密大于64位的明文，注释详尽。
• ## RSA算法Python实现

千次阅读 2016-04-26 09:18:19
RSA算法是一种非对称加密算法，是现在广泛使用的公钥加密算法，主要应用是加密信息和数字签名。详情请看维基：http://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95算法基本思路：1.公钥...
RSA算法是一种非对称加密算法，是现在广泛使用的公钥加密算法，主要应用是加密信息和数字签名。详情请看维基：http://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95

算法基本思路：

1.公钥与私钥的生成：

(1)随机挑选两个大质数 p 和 q，构造N = p*q；

(2)计算欧拉函数φ(N) = (p-1) * (q-1)；

(3)随机挑选e，使得gcd(e, φ(N)) = 1，即 e 与 φ(N) 互素；

(4)计算d，使得 e*d ≡ 1 (mod φ(N))，即d 是e 的乘法逆元。

此时，公钥为（e, N），私钥为（d, N），公钥公开，私钥自己保管。

2.加密信息：

(1)待加密信息（明文）为 M，M < N；（因为要做模运算，若M大于N，则后面的运算不会成立，因此当信息比N要大时，应该分块加密）

(2)密文C = Me mod N

(3)解密Cd mod N = (Me)d mod N = Md*e mod N ；

要理解为什么能解密？要用到欧拉定理（其实是费马小定理的推广）aφ(n) ≡ 1 (mod n)，再推广：aφ(n)*k ≡ 1 (mod n)，得：aφ(n)*k+1 ≡ a (mod n)

注意到 e*d ≡ 1 mod φ(N)，即：e*d = 1 + k*φ(N)。

因此，Md*e mod N = M1 + k*φ(N) mod N = M

简单来说，别人用我的公钥加密信息发给我，然后我用私钥解密。

3.数字签名：

(1)密文C = Md mod N

(2)解密M = Ce mod N = (Md)e mod N = Md*e mod N  = M ；（原理同上）

简单来说，我用自己的密钥加密签名，别人用我的公钥解密可以看到这是我的签名。注意，这个不具有隐私性，即任何人都可以解密此签名。

算法的安全性：基于大整数N难以分解出p和q，构造φ(N)；或由N直接构造φ(N)同样难。

算法的实现：

1.快速幂取模：http://www.cnblogs.com/7hat/p/3398394.html

2.素性测试：http://www.cnblogs.com/7hat/p/3400831.html

3.扩展欧几里得求乘法逆元和最大公约数：http://www.cnblogs.com/7hat/p/3406494.html

实现代码：

import random

def fastExpMod(b, e, m):
"""
e = e0*(2^0) + e1*(2^1) + e2*(2^2) + ... + en * (2^n)

b^e = b^(e0*(2^0) + e1*(2^1) + e2*(2^2) + ... + en * (2^n))
= b^(e0*(2^0)) * b^(e1*(2^1)) * b^(e2*(2^2)) * ... * b^(en*(2^n))

b^e mod m = ((b^(e0*(2^0)) mod m) * (b^(e1*(2^1)) mod m) * (b^(e2*(2^2)) mod m) * ... * (b^(en*(2^n)) mod m) mod m
"""
result = 1
while e != 0:
if (e&1) == 1:
# ei = 1, then mul
result = (result * b) % m
e >>= 1
# b, b^2, b^4, b^8, ... , b^(2^n)
b = (b*b) % m
return result

def primeTest(n):
q = n - 1
k = 0
#Find k, q, satisfied 2^k * q = n - 1
while q % 2 == 0:
k += 1;
q /= 2
a = random.randint(2, n-2);
#If a^q mod n= 1, n maybe is a prime number
if fastExpMod(a, q, n) == 1:
return "inconclusive"
#If there exists j satisfy a ^ ((2 ^ j) * q) mod n == n-1, n maybe is a prime number
for j in range(0, k):
if fastExpMod(a, (2**j)*q, n) == n - 1:
return "inconclusive"
#a is not a prime number
return "composite"

def findPrime(halfkeyLength):
while True:
#Select a random number n
n = random.randint(0, 1<<halfkeyLength)
if n % 2 != 0:
found = True
#If n satisfy primeTest 10 times, then n should be a prime number
for i in range(0, 10):
if primeTest(n) == "composite":
found = False
break
if found:
return n

def extendedGCD(a, b):
#a*xi + b*yi = ri
if b == 0:
return (1, 0, a)
#a*x1 + b*y1 = a
x1 = 1
y1 = 0
#a*x2 + b*y2 = b
x2 = 0
y2 = 1
while b != 0:
q = a / b
#ri = r(i-2) % r(i-1)
r = a % b
a = b
b = r
#xi = x(i-2) - q*x(i-1)
x = x1 - q*x2
x1 = x2
x2 = x
#yi = y(i-2) - q*y(i-1)
y = y1 - q*y2
y1 = y2
y2 = y
return(x1, y1, a)

def selectE(fn, halfkeyLength):
while True:
#e and fn are relatively prime
e = random.randint(0, 1<<halfkeyLength)
(x, y, r) = extendedGCD(e, fn)
if r == 1:
return e

def computeD(fn, e):
(x, y, r) = extendedGCD(fn, e)
#y maybe < 0, so convert it
if y < 0:
return fn + y
return y

def keyGeneration(keyLength):
#generate public key and private key
p = findPrime(keyLength/2)
q = findPrime(keyLength/2)
n = p * q
fn = (p-1) * (q-1)
e = selectE(fn, keyLength/2)
d = computeD(fn, e)
return (n, e, d)

def encryption(M, e, n):
#RSA C = M^e mod n
return fastExpMod(M, e, n)

def decryption(C, d, n):
#RSA M = C^d mod n
return fastExpMod(C, d, n)

#Unit Testing
(n, e, d) = keyGeneration(1024)
#AES keyLength = 256
X = random.randint(0, 1<<256)
C = encryption(X, e, n)
M = decryption(C, d, n)
print "PlainText:", X
print "Encryption of plainText:", C
print "Decryption of cipherText:", M
print "The algorithm is correct:", X == M


转载自：http://www.cnblogs.com/7hat/p/3407897.html
展开全文
• PythonRSA Python 3 RSA算法实现 用法 生成ssh公钥和私钥在./keys/key.pub和./keys/key文件中生成2048位密钥的./keys/key.pub python3 rsa.py generate-key -l 2048 -o ./keys/key
• RSA加密算法Python实现 RSA加密算法是目前使用最广泛的加密方式，具体流程见RSA加密算法 之前想过用C语言实现，但是由于C语言对整型的位宽有要求，RSA加密算法中需要使用的数字大小远远超出C语言中long long int 的...
RSA加密算法Python实现
RSA加密算法是目前使用最广泛的加密方式，具体流程见RSA加密算法
之前想过用C语言实现，但是由于C语言对整型的位宽有要求，RSA加密算法中需要使用的数字大小远远超出C语言中long long int 的最大值，最近学习了Python之后，发现Python没有这一要求，可以较容易的实现。

from random import randint
from datetime import datetime

"""判断是否是素数"""
def is_sushu(sushu):
for i in range(2,sushu):
if sushu % i == 0:
return False
return True

"""随机生成指定范围的大素数"""
def Create_Sushu():
while True:
sushu = randint(100,1000 )#下限越大，加密越安全，此处考虑计算时间，取值较小
if is_sushu(sushu):
return sushu

"""计算欧拉函数"""
def Oula(sushu1 , sushu2):
return (sushu1-1)*(sushu2-1)

"""判断是否互质"""
def Is_Huzhi(int_min,int_max):
for i in range(2,int_min+1):
if int_min % i == 0 and int_max % i == 0:
return False
return True

"""计算公钥，直接计算编程较简单，此处考虑了计算效率的优化"""
def Creat_E(oula):
top = oula
while True:
i = randint(2,top)
for e in range(i,top):
if Is_Huzhi(e,oula):
return e
top = i

"""计算私钥"""
def Compute_D(oula,e):
k = 1
while ( k*oula+1 )% e != 0:
k+=1
return int((k*oula+1)/e)

"""
将字符串转成ASCII
"""
def Transfer_To_Ascii(messages):
result = []
for message in messages:
result.append(  ord(message) )
return result

"""
将列表转化成字符串
"""
def Transfer_To_String(string_list):
string = ''.join(string_list)
return string

if __name__ == "__main__":
"""
p、q为大素数
n=p*q
oula = （p-1）* （q-1）
e 为公钥
d 为私钥
"""

print("通信开始，正在计算公钥与私钥...")
time_start = datetime.now()
p = Create_Sushu()
q = p
while p ==q :
q = Create_Sushu()
n = p * q
oula = Oula(p, q)
e = Creat_E(oula)
d = Compute_D(oula,e)
time_end = datetime.now()
print(f"计算完成，用时{str(time_end -time_start)}秒 ")
print(f"公钥：n = {str(n)} , e = {str(e)}")
print(f"私钥：n = {str(n)} , d = {str(d)}")
#print('p='+str(p)+'\n'+'q='+str(q)+'\n'+'n='+str(n)+'\n'+'oula='+str(oula)+'\n'+'d='+str(d)+'\n')

m = input('待加密信息：')
m_list = Transfer_To_Ascii(m)

print("正在加密...")
c_list = []
for m in m_list:
c = m**e%n
c_list.append(c)
print(f"密文：{c_list}")

print("正在解密...")
decode_messages=[]
for c in c_list:
decode_message = c**d%n
decode_messages.append(chr(decode_message))
print(f"解密信息：{Transfer_To_String(decode_messages)}")



展开全文
• RSA 加解密的 Python 实现 环境 使用的 Python 版本是：Python 3.6.3。 无使用其他第三方库，根据密码学实验要求纯手工实现。 使用 进行加密 在得到的项目文件夹下使用如下命令即可启动 GUI 界面，先点击生成按钮...
• ## RSA算法与Python实现

千次阅读 2018-08-08 21:59:55
RSA算法Python实现 yangtf 功能 RSA加密是最常见的非对称加密算法，基于大数分解难题。 两个很大的素数相乘很容易，但想根据成绩解出因子则很难。 如果数不够大，还是很容易分解的。 素数 素数是这样的...
RSA算法与Python实现

yangtf

功能

RSA加密是最常见的非对称加密算法，基于大数分解难题。 两个很大的素数相乘很容易，但想根据成绩解出因子则很难。

如果数不够大，还是很容易分解的。

素数

素数是这样的整数，它除了能表示为它自己和1的乘积以外，不能表示为任何其它两个整数的乘积。例如，15＝3＊5，所以15不是素数；又如，12＝6＊2＝4＊3，所以12也不是素数。另一方面，13除了等于13＊1以外，不能表示为其它任何两个整数的乘积，所以13是一个素数。素数也称为“质数”。

互质数（或互素数）

公约数只有1的两个数，叫做互质数

模指数运算

取模就是 做一个整除，取余数作为结果，如 13 % 3 = 1 ，因为13除以3，余1
模指数运算就是先做指数运算，取其结果再做模运算。

RSA算法

（1）先随机选择两个足够大的素数

（2）计算乘积 n = pq ，这个n就是那个很难分解的大数，如果pq太小就尴尬了，很容易被爆破。

（3）计算f(n) = (p-1)*(q-1) ，p和q 不能让任何人知道。n是公开的。

（4）找到一个与f(n)互质的数e，使其1

import math
p=9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q=11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e=65537
c=83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034
n=p*q





fn=long((p-1)*(q-1))

# 计算d，使得 de≡1 mod f(n)
# 意思是  d*e % fn == 1 。 d和e的乘积取模等于1
# 也就是说 d*e = 1 + fn*i  (i为整数，就是 d*e / fn 的商)
# 下面的算法是  ( fn*i+i ) % e  如果结果为零，得到结果就是d

i = 1
while(True):
x=(i*fn)+1
if(x%e==0):
d=x/e
break
i=i+1

print "d=", d
print "i=",i

# 另外一个等价公式是  d ≡e-1 mod f(n)   ， 意思为 d % f(n) == (e-1)%f(n) , 也就是说 （e-1）+ j*fn = d + f(n)*i
# 这个比较难算了。


d= 56632047571190660567520341028861194862411428416862507034762587229995138605649836960220619903456392752115943299335385163216233744624623848874235303309636393446736347238627793022725260986466957974753004129210680401432377444984195145009801967391196615524488853620232925992387563270746297909112117451398527453977
i= 32394


KU = (e,n) # 公钥
PU = (d,n) # 私钥

M = 5577446633554466577768879988 # 明文
C = pow(M,e,n ) # M的e次方 模上n
print "C = " , C

C =  83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034


MC = pow(C,d,n)
print "MC = ",MC

MC =  5577446633554466577768879988


M == MC

True


可以看到解密后的MC和原文M相等

Cite :

https://www.cnblogs.com/jiftle/p/7903762.html

http://www.shiyanbar.com/ctf/1979

https://blog.csdn.net/sinat_33769106/article/details/79999090

还有另外一个计算D的方法，试一下。

def computeD(fn, e):
(x, y, r) = extendedGCD(fn, e)
if y < 0:
return fn + y
return y

def extendedGCD(a, b):
if b == 0:
return (1, 0, a)
x1 = 1
y1 = 0
x2 = 0
y2 = 1
while b != 0:
q = a / b
r = a % b
a = b
b = r
x = x1 - q*x2
x1 = x2
x2 = x
y = y1 - q*y2
y1 = y2
y2 = y
return(x1, y1, a)

D = computeD(fn,e)
print D

56632047571190660567520341028861194862411428416862507034762587229995138605649836960220619903456392752115943299335385163216233744624623848874235303309636393446736347238627793022725260986466957974753004129210680401432377444984195145009801967391196615524488853620232925992387563270746297909112117451398527453977


D == d

True


简单的证明

C=Me%n$C={M}^{e}\mathrm{%}n$$C = M^e \% n$
M=Cd%n=Med%n=M1%n=M$M={C}^{d}\mathrm{%}n={M}^{ed}\mathrm{%}n={M}^{1}\mathrm{%}n=M$$M = C^d \% n = M^{ed} \% n = M^{1} \% n = M$
为什么ed = 1 ,在整个公式里，都是做的模运算 ，生成过程决定了 ed % n = 1
上述公式用latex表述。
展开全文
• 基于Python实现RSA算法，包括的函数有：判断一个数是否为素数、判断两个数是否互为素数、欧几里得算法求最大公约数、产生公私钥、扩展欧几里得算法求模逆、加密明文、解密密文以及代码测试。
• RSA算法是当今使用最广泛，安全度最高的加密算法。 • RSA算法的安全性理论基础 [引]根据百科介绍，对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。假如...
• 25行代码实现完整的RSA算法Python3.X版本）   python2.7版本的请点击这里25行代码实现完整的RSA算法   网络上很多关于RSA算法的原理介绍，但是翻来翻去就是没有一个靠谱、让人信服的算法代码实现，即使有代码...
• RSA算法的纯Python实现，压缩包内共4个文件，分别是 1、大整数的运算库（当然不是算加减乘除的，这个python本身就有）。这个库是计算乘模运算，幂模运算（蒙哥马利算法），最大公约数算法及扩展最大公约数算法（扩展...
• RSA算法原理 Python实现RSA加密算法 设p、q为质数 n = p*q fn = (p-1)*(q-1) 要满足: 1 < e < fn ， 且 e 与 fn 互质 满足: e*d%fn = 1 (d>1) e 为公钥 ， d 为私钥 把e 和 n 发给 客户端 m 为明文 c = m...
• RSA算法是一种非对称加密算法，是现在广泛使用的公钥加密算法，主要应用是加密信息和数字签名。本文给大家介绍python实现rsa算法代码，感兴趣的朋友一起学习吧

...

python 订阅