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即可求解。

编写代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

本文标题:RSA加密算法解析

文章作者:nMask

发布时间:2016年09月06日 - 00:09

最后更新:2017年07月25日 - 20:07

原始链接:http://thief.one/2016/09/06/RSA加密算法解析/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

nMask wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
坚持原创技术分享,您的支持将鼓励我继续创作!