RSA加密算法

wang 发表于 算法模板 分类,标签:

RSA的安全性依赖于大数分解,但是否等同于大数分解一直未能得到理论上的证明,因为没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法,那它肯定可以修改成为大数分解算法。 RSA 的一些变种算法已被证明等价于大数分解。不管怎样,分解n是最显然的攻击方法。人们已能分解多个十进制位的大素数。因此,模数n必须选大一些,因具体适用情况而定。



python代码实现:

# -*- coding: utf-8 -*-

__author__ = "hql"

'''
	python实现RSA加密算法:
	1,随意选择两个大的质数p和q,p不等于q,计算N=pq。
	2,根据欧拉函数,不大于N且与N互质的整数个数为(p-1)(q-1)
	3,选择一个整数e与(p-1)(q-1)互质,并且e小于(p-1)(q-1)
	4,用以下这个公式计算d:d × e ≡ 1 (mod (p-1)(q-1))
	5,将p和q的记录销毁。
	(N,e)是公钥,(N,d)是私钥。

	使用公钥进行加密,可以用秘钥进行解密


'''
import random

class RSA():

	def gcd(self, a, b):
		'''
		Stein算法求最大公约数的算法,欧几里德算法在计算大数(64位以上)时很慢

		'''

		if a == b:
			return a
		if a == 0:
			return b
		if b == 0:
			return a

		k = 0
		while (a & 1) == 0 and (b & 1) == 0:
			a = a >> 1
			b = b >> 1
			k += 1

		while (a & 1) == 0 and (b & 1):
			a = a >> 1
		while (a & 1) and (b & 1) == 0:
			b = b >> 1
		return self.gcd(abs(a-b) >> 1, min(a, b)) << k


	_x = 0
	_y = 0
	_gcd = 0
	def extend_gcd(self, a, b):
		'''
		当a与b互质时,可以使用扩展欧几里得算法
		解特殊的不定方程	a*x + b*y = gcd(a,b) = 1
		求一组解
		'''

		if b == 0:
			self._x = 1
			self._y = 0
			self._gcd = a
		else:
			self.extend_gcd(b, a%b)
			temp = self._x
			self._x = self._y
			self._y = temp - a // b * self._y



	def generate_keys(self, p,q):
		'''
		传入两个质数
		'''

		# numbers = (11,13,17,19,23,29,31,37,41,43,47,53)

		N = p*q
		C = (p-1) * (q-1)

		# 选取与C互质的整数e
		e = random.randint(2,C)
		while self.gcd(C,e) != 1:
			e -= 1

		# 根据公式d × e ≡ 1 (mod C) 计算出d
		# d × e ≡ 1 (mod C) 转化成已知(e,C)求不定方程 d*e + C*t = 1 的一组解
		self.extend_gcd(e,C)

		if self._gcd != 1:
			raise StandardError('e 与 C 没有互质')	

		d = (self._x + C) % C 	# 防止出现负数

		return ((N, e), (N, d))


	def pow_mod(self, a, b, mod):
		'''
		快速幂取模,(a^b)%mod
		'''

		ans = 1
		while b:
			if b&1:
				ans = (ans * a)%mod
			b = b >> 1
			a = (a * a) % mod

		return ans


	# 加密
	def encrypt(self, sequence, key):
		C, e = key
		return map(lambda x: self.pow_mod(x, e, C), sequence)


	# 解密
	decrypt = encrypt


# test code ------------------------------------------

rsa = RSA()

pub, pri = rsa.generate_keys(159097, 159113)
L = list(range(20,30))
C = list(rsa.encrypt(L,pub))
D = list(rsa.decrypt(C, pri))

print("keys:", pub, pri)
print("message:", L)
print("encrypt:", C)
print("decrypt:", D)


print(rsa.gcd(159097, 159113))


0 篇评论

发表我的评论