百度一下 藏锋者 就能快速找到本站! 每日资讯归档 下载藏锋者到桌面一键访问

当前位置:主页 > 网络安全 > Python实现网络安全RSA加密与解密

Python实现网络安全RSA加密与解密

所在栏目:网络安全 时间:04-13 10:22 分享:

网络安全技术中RSA的出现,解决了DES中密钥分发的问题,它采用了公钥和私钥制度,让人们不再为密钥的分发而苦恼。网络安全RSA的实现过程,完全基于数学运算,但我会以尽量简单易懂的方式,用Python来讲解如何实现RSA加密与解密,而不是去研究它的数学算法。
下面,我会分三个部分来讲述:RSA加密与解密演示程序(数非常小,理解RSA这个算法流程和熟悉Python语法);RSA加密与解密算法核心(数非常大,这主要是RSA数学算法的实现过程);对要加密的消息的数字化分组处理,及解密后还原为消息。
首先说一下RSA算法的流程。公钥与私钥的产生过程为:产生两个素数p和q;计算n=p*q,z=(p-1)*(q-1);选择一个随机数e(0<e<z),要求满足gcd(e,z)=1(两个数互素);通过公式d=e^(-1) mod z 计算出d;得出公钥{e,n}和私钥{d,n}。
加密过程:选择明文数字M(0<M<n),通过公式C=M^(e) mod n算出加密后的密文。
解密过程:通过公式P=C^(d) mod n计算出明文。
了解了大致的算法流程过程后,你会觉得其实RSA非常简单。确实,RSA算法本身的描述就这么简单,你也可以很快的根据它的流程来写程序实现。
为了照顾对RSA算法不太了解的朋友,我写了个Python版本的演示程序,源码只有93行,可以看出Python代码的简洁与优美。
说明:这仅仅是个演示程序,千万不要认为它能运用于实践,原因后面会说。该网络安全程序涉及到的Python语法非常简单,即使你完全不会Python,只要会C语言,也能猜出大部分语法的功能。有朋友非常讨厌数学算法,而本程序中涉及到的数学知识也非常简单,几乎在我们平时的练习程序中都会用到。要测试该程序,可以在Linux命令行下,进入文件所在目录,输入“$python rsa_demo.py”。如果是Windows,系统默认没有安装Python解释器,需要自己手动安装。请安装2.x系列(现在最新的是2.6.1),安装好过后,把python.exe所在目录添加到环境变量path里去,然后把文件中第二行的utf-8改为gb2312,否则程序执行时输出的中文为乱码。最后,在DOS下进入文件所在目录,输入“python rsa_demo.py”即可。本程序的目的是熟悉Python的语法,熟悉RSA算法流程。程序代码如下:

#!/usr/bin/env python
#-*- coding:utf-8 -*-
import math
def prime_test(prime):
"""素性测试:判断一个数是否是素数"""
end = int(math.sqrt(prime) + 1)
for i in xrange(2, end):
if prime % i == 0:  #不是素数
return False
else:
return True #是
def multip_inverse(e, z):
"""返回d = e^(-1) mod z,即返回e 的模z的乘法逆元,公式:d * e % z = 1"""
for i in xrange(1, z):
if i * e % z == 1:
return i
# a should be greater than b
def gcd (a, b):
"""Compute GCD(greatest common divisor) of two numbers
用辗转相除法,求两个数的最大公约数"""
#print 'a =%d b= %d' % (a, b)
if a < b:
(a, b) = (b, a) # 交换a和b
if b == 0:
return a# 返回
else:
return gcd(b, a % b)# 递归调用程序本身
def input_prime():
"""输入素数p"""
while True :
p = int(raw_input("请输入一个小素数p ( 2 < p < 1000) : "))
if prime_test(p) == True:
return p
else:
print "数字%d不是素数! " % p
p = input_prime()
q = input_prime()
n = p * q   # 计算n的值
z = (p-1) * (q-1)   # 计算z的值
print "p = ", p
print "q = ", q
print "n = p * q =", n
print "z = (p-1) * (q-1) =", z
while True:
e = int(raw_input('请输入一个数字e:(1 < e < z) 且e,z互为质数:'))
if e <= 1 or e >= z :
print "输入e的范围无效: (1<e< %d) 请重新输入!", z
continue
if gcd(e, z) != 1:
print '%d 与 %d不是互为质数.' % (e, z)
continue
d = multip_inverse(e, z)
break
print "公钥(e, n)为: (%d , %d)" % (e, n)
print "私钥(d, n)为: (%d , %d)" % (d, n)
while True:
message = int(raw_input('请输入你要加密的数字明文message (1 <= message < n):'))
if  message < 1 or message >= n :
print "message必须小于n,请重新输入"
continue
break
print "message = ", message
print "正在对message进行加密..."
print "\t 加密公式为: cipher = (message ** e) % n"
cipher = ( message ** e) % n# 加密得出密文cipher
print "加密后的密文cipher为:", cipher
print "正在对cipher进行解密..."
print "\t 解密公式为:plain_text = (cipher ** d) % n"
plain_text = (cipher ** d) % n  # 解密得出明文plain_text
print "解密后的明文plain_text为:", plain_text
if message == plain_text:   # 加密解密是否成功
print '\t', '*' * 50
print "RSA 加密-解密 测试成功!"
else:
print '程序测试失败!'

Linux下的运行演示程序界面如图1所示。从测试画面上可以知道,用公钥 (9,51)加密数23得到密文为数11,而用私钥(25,51)解密数11得到了明文23,即完成了加密与解密过程。
 
图1
前面我们说这个程序只适合演示算法本身,并不适用于实际,下面来看看为什么。
首先说明一下,在加密和解密过程中,公钥(9,51)是任何人都知道的。那么,如果在用上面的RSA算法加密的通信过程中,第三方得到了如下信息(这个很容易):公钥(9,51)与密文11,则现在的问题是第三方能通过某种算法得到加密前的信息吗?对于这个加密过程,答案是肯定的。
通过公式我们知道,11=M^(9) mod 51,要得到M好办,用一个循环进行穷举非常容易。

for m in xrange(1, 51):
if m ** 9 % 51 == 11:
print m

运行这个程序,瞬间就能得到答案23!还有一种方法,我们知道51=p*q (p,q都是素数),用下面的程序能求出p、q:

prime = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47)
for p in prime:
for q in prime:
if p * q == 51:
print p, q

求出的p和q为3 和17(顺序无关)。那么,我们再计算 m=(p-1)*(q-1)=16*2=32。另外,我们还知道e, 那么就可以运用公式:d*e%z=1来求出d:

for i in xrange(1, 32):
if i * 9 % 32 == 1:
print i

这样,我们就求出了d=21,相当于我们已经得到了密钥(21,51),密钥都得到了,解密就能得到明文23。
现在你是不是觉得RSA原来这么简单,这么脆弱!如果你这样想就错了,因为实际运用过程中,n是一个非常大的数,现在用的n至少应该要求是155位(512位二进制)的数。也就是说,q和p也至少应该是一个78位的数。
RSA加密算法的强度在于当今数论界对大数的素因数分解的难度上,即把一个200位(或者更多)的数分解成两个素数相乘有多难,那RSA就有多强!关于这点,可以上网查看相关的报道。暂时来说,RSA是很安全的,除非有一天,对大数的素因数分解已经很容易。
不过现在问题来了,这么大的数,用上面的程序还能进行加密解密吗?肯定不行。下面请出这次的主角,能应用于实践中的程序。
因为数很大的原因,于是这个程序要处理下面的内容:快速法求指数模;素性测试:测试一个大数(100~300位)是否是素数;大数的模p的乘法逆元;产生按要求位数的素数。
说明:这个程序涉及到的Python语言要稍微复杂些,但因为Python语言的特点,相信对你来说,应该不难。因为要对大数进行处理,所以涉及到的数学算法有点复杂,要专门花时间才能明白其中的道理。或者,建议去找专门的密码学书籍来理解这些数学算法本身。当然,网上也有这些算法的其它语言实现。

1)快速法求大数的指数模
首先说明一下Python对大数的处理问题。Python支持两种整型数据,分别为普通整数int(范围-2,147,483,648到-2,147,483,647);长整型long,long的范围很大,几乎可以说任意大的整数均可以存储。为了区分普通整数和长整数,需要在整数后加L或小写l。
这儿所说的任意大的数,是不是无限制呢?确实有限制,而这个限制本身是因为你的硬件内存的限制。也就是说,只要你内存够大,Python就能支持无限大的数,这个特性非常强。Python天生支持对大数的直接操作,这在其它语言看来,似乎有点不可思议吧!?在我们下面的运算中,很多地方运用了它这个特性,即你不用考虑数的溢出,只需要考虑得出这个结果所需的时间。例如我们计算n的时候,就是直接用公式n=p*q, 而这个n通常都是300位左右的数。Python的这个特性,让我们可以更加注重精力来解决实际的问题,而不用关注语言本身的细节。
模块名:fast_powmod.py,之所以把这个模块放在前面,是因为后面的几个模块会用到它。代码如下:

#!/usr/bin/env python
#-*- coding:utf-8 -*-
def fast_powmod(a, p, n):
"""采用快速指数模方法,计算 result = a^p mod n"""
result = a % n
remainders = []
while p != 1:
remainders.append(p & 1)
p = p >> 1
while remainders:
rem = remainders.pop()
result = ((a ** rem) * result ** 2) % n
return result

对计算result的算法,在此不做描述,有兴趣的可以查阅相关资料。再说明一下python本身的东西,def 为定义一个函数;“if __name__ == '__main__'”的意思是,如果执行这个模块本身,则其下面的代码将被执行,而如果这个模块被其它模块调用,则不执行“__main__”下面的语句。这是Python的一个非常好的特性,用于对模块本身的测试。

2)大数的素性测试

import fast_powmod

DEBUG = False   # is debug mode?
def get_d_r(prime_minus_1):
"""prime_minus_1 = odd_multiplier * 2 ^ r
返回:(odd_multiplier, r)"""
r = 0
bits = prime_minus_1
while not (bits & 1):
r += 1 # increase the r
bits >>= 1 # right shift

odd_multiplier = (prime_minus_1) / (2 ** r)
if DEBUG:
print 'r = %d, odd_multiplier = %d' % (r,odd_multiplier)
return (odd_multiplier, r)

def fast_prime_test(prime):
"""用整除的方法先快速判断一个数是否是素数"""
for test in xrange(3, 5000, 2):
if prime % test == 0:
return False# 一定不是素数
else:
return True # 可能是素数

def miller_rabin(prime):
"""用miller-rabin算法进行素性测试,返回:False表示一定是非素数,True则表示可能是素数"""
witness = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47)
#witness = (2, 3, 5, 7, 11)
prime_minus_1 = prime -1
(odd_multiplier, r) = get_d_r(prime_minus_1)

for rand_witness in witness:
y = fast_powmod.fast_powmod(rand_witness, odd_multiplier, prime)
if DEBUG:
print 'y = %d'% y
if y == 1 or y == prime-1:
continue
else:
for j in range(1, r+1):
y = fast_powmod.fast_powmod(y, 2, prime)
if y == prime_minus_1:
break
else:
return False# It is an absolutly composite

return True # It maybe a prime

if __name__ == '__main__':
 prime= 40094690950920881030683735292761468389214899724061 # This is a prime number
 print '%d is Prime?\t%s' % (prime, miller_rabin(prime))
 print miller_rabin(105)# This is a composite
 print miller_rabin(2047)   # 第一个能欺骗2的数
 print miller_rabin(2047)   # 不能欺骗2、3
 print miller_rabin(1373653)# 第一个能欺骗2、3的数

最前面的import fast_powmod表示本模块要用到前面的模块fast_powmod.py。在使用miller-rabin进行素数测试之前,先进行一次简单的测试(fast_prime_test),就是进行简单的整除测试。如果测试不通过,则表明一定不是素数;如果通过,则可能是素数。也许你会想,为什么只测试到5000呢?书上不是说可以直接测试到它的平方根吗?这样不就能准确地知道它到底是不是素数了吗?理论上是可行的,可是实际中由于数太大,执行这个测试的时间太长了。现今还没有很有效的方法来测试一个数是否是素数。在此,素性测试算法用的是miller-rabin算法(这是Fermat小定理的加强形式)。对这个算法本身不做描述,只是说一下其测试素数的效率。
如果一个数没有经过a (a为witness中的一个元素)的测试,那么它一定不是素数。但是,如果经过了测试,那么这个数是素数的概率为3/4。如果它经过了两个不同的a的测试,则它是素数的概率为1-(1/4)^2,而程序中我用了15个a来测试它,则它是素数的概率为1-(1/4)^15,这个数已经非常接近100%了,所以可以肯定的是,经过了miller_rabin算法测试的数是素数。

3)求模p的乘法逆元

# a should be greater than b
def gcd (a, b):
"""Compute GCD(greatest common divisor) of two numbers
求两个数的最大公约数"""
#print 'a =%d b= %d' % (a, b)
if a < b:
(a, b) = (b, a) #交换a和b
if b == 0:
return a  #返回
else:
return gcd(b, a % b) #递归调用程序本身
def extended_Euclid(e, z):
"""利用扩展的欧几里德(extended Euclid)算法来求密钥e的模Z乘法逆元
公式:d*e = 1 mod Z
已知:e, Z,求e的mod Z的乘法逆元
返回: d = e^(-1) mod Z"""
(x1, x2, x3) = (1, 0, z)
(y1, y2, y3) = (0, 1, e)
while True:
if y3 == 0:
return False
if y3 == 1:
return y2
div = x3 / y3
(t1, t2, t3) = (x1 -div*y1, x2 - div*y2, x3 - div*y3)
(x1, x2, x3) = (y1, y2, y3)
(y1, y2, y3) = (t1, t2, t3)

if __name__ == '__main__':
print gcd(7,261)
print extended_Euclid(7, 216)

求大数的模n的乘法逆元,用的方法是扩展的欧几里得算法。

4)产生指定位数的素数
十进制位数:这个数的十进制形式(即本身)有多少位。
二进制位数:这个数表示成二进制后,有多少位。
转换公式:十进制位数=二进制位数*log10(2),log10(2)=0.3010299956639812。
155位十进制数相当于512位二进制数。
309位十进制数相当于1024位二进制数。
619位十进制数相当于2048位二进制数。
这里说的位数,是指对大数n而言,相应的p和q则取其一半的位数。
在1998年,阿姆斯特丹的国学数学与计算机科学研究所下的一个国际密码研究小组,使用了一台超级计算机和300台个人计算机,花了7个多月的时间,成功分解了512位的大数,于是现在认为512位的n已经不安全了,一般我们可以选择1024位,或者更多的2048位。
到此,RSA算法里的难点已经全部解决了。接下来是主程序的实现,这里主要就是把前面的东西结合起来,然后实现加密解密即可。代码如下:

#!/usr/bin/env python
#-*- coding:utf-8 -*-

__author__ = "renewjoy(rlj_linux@126.com)"
__version__ = "Release: 1.0"
__date__ = "$Date: 2009/03/23 19:11:21 $"
__copyright__ = "Copyright (c) 2009"
__license__ = "Python"

#系统模块
import math #数学模块
import random   #随机数模块
from time import clock as now   #记时模块

#自定义模块
import Euclid
import fast_powmod
import prime_test
import encode

DEBUG = False   #调试模式
begin = now()   #记时开始

def produce_primes(decimal_bits):
"""产生指定位数的随机素数"""
begin = 10 ** (decimal_bits -1) + 1 # like: 1000000000000000001
end = 10 ** (decimal_bits + 1) - 1  # like: 99999999999999999999

while True:
random.seed()
odd = random.randrange(begin, end, 2) #产生一个指定范围的随机奇数(伪随机数)
#先用快速法判断一下,如果不是素数,则重新产生一个奇数
if prime_test.fast_prime_test(odd) == False:
continue
is_prime = prime_test.miller_rabin(odd) #对奇数的素性测试
if is_prime == True:
return odd
elif is_prime == False:
continue

binary_bits = 1024  #设置n 的二进制位数
decimal_bits = int(math.ceil(binary_bits * math.log10(2))) #n的十进制位数
decimal_bits >>= 1  # decimal_bits / 2
if DEBUG:
print 'n的十进制位数为:', decimal_bits

def produce_p_q():
"""产生p和q"""
# produce p
p = produce_primes(decimal_bits)
# produce q, q should not equal to p
while True:
q = produce_primes(decimal_bits)
if q != p:
return (p, q)
(p, q) = produce_p_q()
n = p * q
def bits_of_n(n):
"""计算最后产生的n的二进制位数"""
bits = 0
while n > 1:
n >>= 1
bits += 1
return bits
bits = bits_of_n(n)
print 'The bits of n is:',bits
m = (p-1) * (q-1)
def produce_e_d():
"""产生(e, d)"""
# Generate a number e so that gcd(e, m) = 1, start with e = 3
e = 3
while True:
d = Euclid.extended_Euclid(e, m)
if Euclid.gcd(m, e) == 1 and d > 0:
break
else:
e += 2
return (e, d)
(e, d) = produce_e_d()
if DEBUG:
print 'q is:', q
print 'p is:', p
print 'm is:', m
print 'e is:', e
print 'd is:', d
print 'The private key is:', (d, n) #公钥
print 'The public key is:', (e, n)  #私钥

def encrypt(groups):
"""对数字化后的消息分组进行加密"""
encrypted = [] #密文
for message in groups:
encrypted.append(fast_powmod.fast_powmod(message, e, n)) #加密
return encrypted #返回加密后的密文分组

def decrypt(cipher):
"""对加密后的密文分组进行解密"""
plain_text = []
for decrypted in cipher:
plain_text.append(fast_powmod.fast_powmod(decrypted, d, n)) # 解密
return plain_text

#要加密的消息
message = 'I love you more than I can Say!---This message is encrypted by RSA.I love you more than I can Say!---This message is encrypted by RSA.I love you more than I can Say!---This message is encrypted by RSA.I love you more than I can Say!---This message is encrypted by RSA.'

groups = encode.str2num(decimal_bits*2, message) #将消息转化为数字化的分组

print '消息共分为%d组进行加密。' % len(groups)
cipher = encrypt(groups)# 加密
plain_text = decrypt(cipher)# 解密
#cipher = ''.join(cipher)
print 'The Cipher is:', cipher
plain_text = encode.num2str(plain_text) #将数字化分组转换成消息
#解密后的明文(应该与消息相同)
print 'The Plain_text is:', plain_text
end = now() # 记时结束
print '加密-解密过程共用时间:%f 秒!' % (end-begin)

5)对消息的数字化分组处理。
我们平时使用的信息并不完全是数字,而RSA加密的是数字,所以一个解决办法就是对平时使用的信息采取数字化处理。这个问题有很多解决办法,而我使用的是先对消息进行base64编码,然后将结果字符串的每个字母用一个两位数来代替,然后转换成数字类型就可以了。 因为base64所使用的字符集为a-z、A-Z、0-9、/、+、=,而它们的ASCII码在43~122之间,我们可以采取相应的减去30,则其中的所有字符都能用一个两位数来表示。
转换后,会出现的一个问题就是,如果数字过大,那么将不能用一个分组来进行加密,因为在加密的时候,必须满足message<n这个条件,所以当数字过大时,可以采取分组处理,其中每个分组的数字位数为n-1位,这样就一定能满足要求。用python来处理这个任务很轻松,下面是代码:

#!/usr/bin/env python
#-*- coding:utf-8 -*-

import base64   # base64编码

def str2num(nbits, message):
"""对明文进行数字化分组
返回:[first_group, second_group, third_group...]
"""
#确保分组后的每组包含偶数位数,且分组后的数字比n小
if nbits %2 == 0:
nbits -= 2
else:
nbits -= 1

#将明文进行base64编码
message_b64 = base64.b64encode(message)

message_num = []
for char in message_b64:
message_num.append(str(ord(char)-30)) #-30:这样保证ord(char)-30的结果为两位数字
message_str = ''.join(message_num)

result = []
while True:
if len(message_str) > nbits:
result.append(long(message_str[:nbits]))
message_str = message_str[nbits:]
else:
result.append(long(message_str))
return result

def num2str(groups):
"""将数字转换成字符串,然后进行base64解码"""
result = []
for string in groups:
string = str(string)
#print len(string)
message = []
for i in xrange(0, len(string), 2):
base = string[i:i+2]# 每次取两位
message.append(chr(int(base) + 30))
#print len(message)
result.append(''.join(message))
result = base64.b64decode(''.join(result)) # base64解码
return result

最后说说本程序的测试效率吧。由于进行的都是网络安全大数计算,使得RSA最快的情况也比DES慢上100倍,无论是软件还是硬件实现。速度一直是RSA的缺陷,一般来说只用于加密少量数据。所以,本程序中加入了记时功能,可以让你知道一次加密解密所花时间。在我的机器测试,当n=1024位时,包括产生素数、加密解密三个分组的时间平均为1.5秒。

Python实现网络安全RSA加密与解密 免费邮件订阅: 邮件订阅

图片推荐

热点排行榜

CopyRight? 2013 www.cangfengzhe.com All rights reserved