从小白变RSA大神，附常用工具使用方法及CTF中RSA典型例题

前言

RSA加解密类题型是ctf题中常见题型，考点比较广泛，涉及各种攻击手法，以前在这栽了不少跟头，这里好好总结一下。包括RSA加密原理，RSA常用工具使用方法及下载地址，RSA典型例题。

RSA加密基本原理

加密过程

选择两个大素数p和q，计算出模数N = p * q

计算φ = (p−1) * (q−1) 即N的欧拉函数，然后选择一个e (1<e<φ)，且e和φ互质

取e的模反数为d，计算方法: e * d ≡ 1 (mod φ)

对明文A进行加密：B≡A^e (mod n) 或 B = pow(A,e,n)，得到的B即为密文

对密文B进行解密，A≡B^d( mod n) 或 A = pow(B,d,n)，得到的A即为明文

p 和 q ：大整数N的两个因子（factor） N：大整数N，我们称之为模数（modulus） e 和 d：互为模反数的两个指数（exponent） c 和 m：分别是密文和明文，这里一般指的是一个十进制的数

一般有如下称呼：

（N，e）：公钥（N，d）：私钥

加密分析

RSA算法是一种非对称密码算法，所谓非对称，就是指该算法需要一对密钥，使用其中一个加密，则需要用另一个才能解密。

RSA的算法涉及三个参数，n、e、d。

其中，n是两个大质数p、q的积，n以二进制表示时所占用的位数，就是所谓的密钥长度。

e和d是一对相关的值，e可以任意取，但要求e与(p-1)(q-1)互质；再选择d，要求(ed) ≡ 1(mod(p-1)×(q-1))。

令φ = (p-1)(q-1) 上式即 d*e = 1 mod φ 即：(d*e - 1)% φ = 0

（n，e),(n，d)就是密钥对。其中(n，e)为公钥，(n，d)为私钥。RSA加解密的算法完全相同，设A为明文，B为密文，则：A≡B^d( mod n)；B≡A^e (mod n)；（公钥加密体制中，一般用公钥加密，私钥解密）

e和d可以互换使用，即：

A≡B^e (mod n)；B≡A^d( mod n);

附加解释

同余符号 “ ≡ ”

数论中的重要概念。给定一个正整数m，如果两个整数a和b满足（a-b）能够被m整除，即（a-b）/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系

比如26≡14(mod 12)

互质

公约数只有1的两个数，称为互质

python pow() 函数

RSA工具

RSA-Tool 2使用方法

软件参数

P= 第一个大素数Q= 第二个大素数 (P和Q的长度不能相差太大！) E= 公钥 (一个随机数，必须满足：GCD(E,(P-1)*(Q-1))==1)(译者注：即E和(p-1)(Q-1)互素) N= 公用模数，由P和Q生成：N=P*Q D= 私钥：D=E^(-1) mod ((P-1)*(Q-1))

参数N和E是公开的但是D是私有的并且绝不能公开！P和Q在生成密钥后便不再需要了，但是必须销毁。

为了从公钥(N,E)得到D,需要试图分解N为它的两个素数因子。对于一个很大的模数N（512位或更大）要想分解出它的P和Q是件非常困难的事。

生成一组RSA密钥对

按下’Start’按钮，通过移动你的鼠标指针来收集一些随机数据.这必须一次完成，因为收集的数据会被保存在你的RSA-Tool文件夹里面的一个文件中。选择要创建的密钥的长度(等于N的长度)。最大为4096位. 选择你的公钥(E)并把它输入到相应的编辑框作为十进制数。常用的E有（考虑到计算速度的原因):3,17,257和65537(十进制). 按下’Generate’，等到密钥生成完成。

注意，生成很大的数需要一些时间，取决于你的CPU的计算能力。

特别说明：你可以常按’Generate’.做为密钥生成过程的一个组成部分的内置随机数生成系统会在运行的时候重新进行初始化。这是故意这么做的，这样可使那些滥用这个工具做其它事情变得更困难…　　注意两次或两次以上生成相同的密钥对是不可能的。

分解一个数

选择正确的进制在Modules(N)编辑框中输入或复制这个数。这会激活’Factor’按钮。然后按Factor按钮.注意分解大于240位的数会花很大的内存和时间！

甚至很小的数也会需要几个小时。

如果用Multiple Polynomial Quadratic Sieve(MPQS)算法来分解整数,需要大量的内存.原因是这个算法的设计,而不是编码风格。

例如：分解一个给定大小的N的内存使用情况(使用MPQS算法)…

256位~89MB, 280 位~140MB, 296位~185MB等等.

由素数因子P和Q计算私钥D

选择参数P和Q的正确进制，在相应的文本区域中输入或粘贴P和Q 按下’Calc.D’，得到整数的精确位长度

为你要进行检查的数选择正确的进制在Modules(N)文本框中输入或粘贴整数按小的’Exact size’按钮.会显示出这个数使用的精确的位数

msieve使用方法

msieve是一个大数分解工具下载地址

msieve.exe —help 查看帮助 l filename 保存日志到filename文件中，默认为msieve.log i filename 从filename文件中读取数字，默认worktodo.ini one_number: 待分解数字，0开头代表8进制，0x开头代表16进制，否则为10进制。如不填，则从worktodo.ini中读取数字。 -v 意思打印具体分解的情况 -q 仅仅打印能找到的因子

各自运行结果如下：

注：prp39 即是分解出来的p,q

注意前面加上相应进制。八进制0 十六进制0x 十进制什么也不加。

openssl

生成私钥，并导出公钥生成2048 bit的PEM格式的RSA Key：Key.pem

从私钥导出公钥：Key_public.pem

准备测试数据

为了简便起见，这里将字符串”hello rsa”存放到文件msg.txt作为测试数据：

公钥加密

使用公钥key_public.pem对测试数据msg.txt进行加密生成msg.txt.enc，并查看加密后的数据：

这里使用：

-in 选项指定原始数据文件msg.bin -out 选项指定加密后的输出文件msg.bin.enc -inkey 选项指定用于加密的公钥Key_pub.pem，由于输入是公钥，所以需要使用选项-pubin来指出 -encrypt 选项表明这里是进行加密操作 -pkcs 选项指定加密处理过程中数据的填充方式，对于填充，可选项有：-pkcs, -oaep, -ssl, -raw，默认是-pkcs，即按照PKCS#1 v1.5规范进行填充

私钥解密

使用私钥key.pem对加密后的数据msg.txt.enc进行解密，并将结果存放到msg.txt.dec文件中：

这里使用：

-in 选项指定待解密的数据文件msg.bin.enc -out 选项指定解密后的输出文件msg.bin.dec -inkey 选项指定用于解密的私钥Key.pem，由于输入是私钥，所以不再需要使用选项-pubin -decrypt 选项表明这里是进行解密操作 -pkcs 选项指定解密处理过程中数据的填充方式，对于填充，可选项有：-pkcs, -oaep, -ssl, -raw，默认是-pkcs，即按照PKCS#1 v1.5规范进行填充