前言
最近做的CTF题目遇到RSA加密总是不会，于是参考资料学习一番，小结自己的学习过程，怕自己某天又忘记了
RSA是属于现代密码学的范畴，现代密码学的终极目标是:发明永远无法破解的加密算法
而他们很多又是跟二进制相关，二进制加密的唯一算法 XOR
下面两个标准就很典型。。。
DES 数据加密标准
AES 高级加密标准
对于上面的东西一知半解。。什么轮子函数都没了解清楚，还有一些什么盒子之类的东西。。。emmm以后在深究吧
正文
跟标题一样，我只是简单了解RSA算法，然后把自己得理解写出来，毕竟那些什么欧拉公式，什么高斯的数论，看也看一到两天，太费时间。。。
RSA是一种非对称加密算法，它由 公钥（n/e），私钥(n/d)，明文M和密文C组成。
RSA的大致过程
选取两个大素数生成n,p和q，n=p*q,这里的n目前大都是在1024位左右，难以破解，因为它越长，分解起来就越难
随机选取加密密钥e，保证e和(p-1)(q-1)互素
计算解密私钥
e*d ≡ 1 mod (p-1)(q-1)
加密
c=m^e mod n
解密
这里的c指的是密文，m指的是明文
其中(n,e)为公钥，(n,d)为私钥
介绍一个同余运算的概念
两个整数a,b，它们除以整数M所得的余数相等：
a ≡ b(mod m)
，比如说5除3余数为2，11除3余数也为2，于是可写成
11 ≡ 5(mod 3)
然后就做了几个题目，发现嫌他们的套路就是不停的玩转这几个参数。。。。
已知p、q、e求d
已知p、q、e和密文 求明文
已知n、e和密文 求明文
已知公钥和密文 求明文
还有就是简单记录一下相关工具的用法
RSAtool
这个还是比较方便的，但还是觉得脚本顺手
Keysize(Bits)：填写你N的位数
Public Exp.(E)：填写你的e的十进制值
Number Base：填写你下面N的进制（一般采用10进制）
Modulus(N)：填写N的十进制数（和Number Base填写的要对应）
然后点击左下角的Factor N
就会自动分解出P和Q
然后点击左下角的Calc. D
就会自动计算出D
然后点击左下角的Test
（这里好像有个Bug，要先加密一次，才能用解密功能）
然后把你的密文放在result里，点击decrypto
即可得到解密后的答案
yafu
一个大数分解工具
用命令行进入打此目录下，命令如下，N是你输入的大数
yafu-x64.exe factor(N)
还有一个PARI。。。这好像也是一种语言。。一般是用来将大数16进制转10进制。。或者是判断N的位数使用
反正不理了，指令也很简单：
第一步:
输入数字
（当然，如果输入16进制，你要带上0x，他会底下自动给你显示10进制，十分方便）
第二步:
binary(x)
他就会帮你把这个大数分解成2进制
第三步:
length(x)
他可以帮你输出这个N的位数
openssl
有时候遇到下面这种格式的,就会选择用openssl
-----BEGIN PUBLIC KEY-----
MIICIjANBgkqhkiG9w0BAQEFAAOCAg8AMIICCgKCAQEDZxmNa1YU6VgTrdjyKkcX
vHK+HqvZM9G4aUT9t1uO0jC+YtfRtp0iIJXBKMhvggEuyxFhkf2dAYptAvhNsnvF
GiEwfchvS/dxxpHBQ+Wr5Um1vS1usaIf1icOfhtI/gYR+LhsLNSTm9N6LTko0Xa
RKE96CW3JgjbbHxKQLeCZubIe7/e9rSDgdScRQeli81Ht21ktFkIsVi9frxNrLCx
z9bCwZV09A6y79Dp4Q3HAFytObyvUrnqw4czaNaQMcXnJGhKRPBo79HT3Altm11k
EeWL3uQ+RrmaDQSUudsoGVr5Aa/xMNSm4gPa0I2lf6fkAmKlutsqMj7aKLRGlqsw
XQKCAQEA85Wdl44C658G3vPzNdj4r9dgmVHdrGC3FLbCKvD6kS8hCzQga9JKlgHH
jfSgJ18Qf9OrVS2VBX65NOcb3c1wRcJLGFh7jI/PWt1MXYPwx3yU3JxQy+Q44rZ7
r9MWM7aq8XgdkMOtbwPQN7MyGAGyNUbUg+Z+JgZ/eyI0fdvAwtWSzoFMv138zBQU
N/FOCzmQ+IBh5fC65fAeP6cNsOlgXnz9V16cge/uxSnDP9kDeiD9is1ROsljd2gx
PmP5g4rjURzdCporUW8hSMjUdaNgoGNZRJc57s0lGrtCsBRXPkOfL6RXNVeyVpn/
wR5jHOjul1qG5+JyvPX3apNFA0j+Pw==
-----END PUBLIC KEY-----
上面的public.key就是你所需要查看的文件名
然后使用密钥文件进行解密的话
flag.enc是加密文件 private.pem是密钥 flag.dec解密文件
配合下面的Python脚本在linux下使用，记得在同一文件夹下
import math
import sys
from Crypto.PublicKey import RSA
keypair = RSA.generate()
keypair.p =
keypair.q =
keypair.e =
keypair.n = keypair.p * keypair.q
Qn = long((keypair.p-) * (keypair.q-))
i =
while (True):
x = (Qn * i ) +
if (x % keypair.e == ):
keypair.d = x / keypair.e
break
i +=
private = open('private.pem','w')
private.write(keypair.exportKey())
private.close()
记得修改一下p q e
参考文章:
http://www.freebuf.com/column/148185.html