RSA加密算法解析

　　几个月前参加了一次CTF比赛，其中遇到了RSA加密解密题，当时也是一头雾水，赛后便查找资料整理了一番，在此总结分享。

算法介绍

　　RSA加密算法属于公钥加密算法，是一种非对称密码算法，所谓非对称，就是一个密码用来加密，另一个密码用来解密，一般来说，用公钥加密，私钥解密，当然也有其他情况。

算法原理

　　RSA算法基于一个事实：将两个大素数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。RSA算法三个参数：n、e1、e2

n=pq （p、q为2个大质数） n的二进制所占用的位数即秘钥的长度。
e1与e2是一对相关的值，e1可以任意取，但要求e1与(p-1)(q-1)互质；要求(e2e1)mod((p-1)(q-1))=1。
(n,e1),(n,e2)就是密钥对，其中(n,e1)为公钥，(n,e2)为私钥。

算法公式

假设：
A:明文
B:密文

——用公钥加密公式——
A=B^e2 mod n
B=A^e1 mod n

——用私钥加密公式——
A=B^e1 mod n
B=A^e2 mod n

实战演示

题目概要

这是一个公钥加密，公钥解密的RSA题目
给出公钥密码为：{920139713,19}，其中920139713为n，19为e1。
待解密的密文B为：
704796792
752211152
274704164
18414022
368270835
483295235
263072905
459788476
483295235
459788476
……
最终求解私钥A的值？

解题思路

列出公式：公钥加密
假设：
A:明文
B:密文
A=B^e2 mod n
B=A^e1 mod n

此题给出了B,n,e1,求A的值，带入公式2即可求解。

编写代码

import string
strs=string.digits+string.lowercase    #列举a-z数字

f=open("data.txt")   #把密文B的内容写进data.txt，方便程序读取
data=f.readlines()
f.close()

plaintext=""

for b in data:    #取出所有密文(b)
	for a in strs:   #取出所有可能的明文(a)
		if ord(a)**19 % 920139713==int(b.strip()):         #ord   将字符串转换为ascii码
			plaintext+=a

print plaintext

运行结果

flag13212je2ue28fy71w8u87y31r78eu1e2