RSA概念详解及工具推荐大全 – lmn
0x01 RSA算法概述
RSA（Rivest-Shamir-Adleman）
RSA是公钥密码系统，所谓公钥加密系统就是不通过相同的密钥进行加密和解密。RSA适用于签名和加密，RSA 广泛用于电子商务协议中，足够长的密钥大大的提高了安全性。
RSA历史
为英国情报机构GCHQ工作的英国数学家Clifford Cocks在 1973 年的一份内部文件中描述了一个等效系统，但考虑到当时实施它所需的计算机相对昂贵，它主要被认为是一种好奇心，并且就是众所周知的，从未部署过。然而，由于其绝密分类，他的发现直到 1998 年才被披露，而 Rivest、Shamir 和 Adleman 独立于 Cocks 的工作设计了 RSA。
RSA 算法于 1978 年由MIT的Ron Rivest、Adi Shamir和Leonard Adleman公开描述；字母RSA是他们姓氏的首字母，按与纸上相同的顺序列出。
0x02 密钥生成
RSA包含公钥和私钥，公钥用于加密，私钥用于解密，但不是绝对的，在下面的链接中介绍了原因。
http://wiki.tidesec.com/docs/Crypto/82851f8c62417fdbfb8168ec4011f532
-
使用公钥加密的消息只能使用私钥解密，RSA 算法的密钥通过以下方式生成：
首先生成两个素数：p 和 q（整数p和q应随机均匀选择） -
计算n，n = p * q
n用作公钥和私钥的模数 -
ø(n) = (p – 1) * (q – 1)
-
选择一个整数e，使得1 < e < ø(n)
并且gcd(e,ø(n)) = 1 -
ed ≡ 1 mod ø(n)
（“≡”是数论中表示同余的符号）
如果两个整数 ed 和 1 满足 ed-1 能被 ø(n) 整除，称为整数 ed 与 1 对模 ø(n) 同余，并且（1 < d < ø(n)）
公钥由模数n和公共（或加密）指数组成e。私钥d由必须保密的私有（或解密）指数组成。
此时，密钥生成
公钥（n，e）
私钥（n，d）
0x03 加密过程
- Alice生成公钥和私钥，将公钥发送给Bob
- Bob通过公钥加密自己需要传输的信息
- Bob将加密后的信息发送回Alice
因为公钥为（n，e），加密方获得了n和e。
加密函数为：
c(m) = m^e mod n
加密方通过加密函数生成密文，并将密文发送给对方。
0x04 解密过程
- Alice收到Bob发送的密文
- Alice通过生成的私钥对密文进行解密
因为私钥为（n，d），解密方拥有n和d。
加密函数为：
m(c) = c^d mod n
解密方通过解密函数解密出明文。
0x05 分析.pem文件
写这篇文章的今天，正在参加CTF，遇到一道非常规解法的rsa密码学题目促使我想把解题过程中学到的都整理下来，作为一个note，欢迎补充👏。
通过.pem获得n，e
RsaCtfTool
python RsaCtfTool.py --dumpkey --key 公钥文件代码方式
from Crypto.PublicKey import RSA
public = RSA.importKey(open('public.pem').read())
n = int(public.n)
e = int(public.e)
print(n)
print(e)
openssl
openssl rsa -pubin -in .pem公钥文件 -text -modulus
其中可以看到Exponent就是分解得到的e，modulus是分解到的n。
0x06 分解大质数
http://factordb.com/
这是一个比较好用的网站，对于比较小的n比较好分解。
RsaCtfTool
RsaCtfTool是一个RSA多重攻击工具
从弱公钥中解密数据并尝试恢复私钥自动选择给定公钥的最佳攻击。
下载地址
https://github.com/Ganapati/RsaCtfTool
官方给出的使用方法
usage: RsaCtfTool.py [-h] [--publickey PUBLICKEY] [--timeout TIMEOUT]
[--createpub] [--dumpkey] [--ext] [--sendtofdb]
[--uncipherfile UNCIPHERFILE] [--uncipher UNCIPHER]
[--verbosity {CRITICAL,ERROR,WARNING,DEBUG,INFO}]
[--private] [--ecmdigits ECMDIGITS] [-n N] [-p P] [-q Q]
[-e E] [--key KEY] [--isconspicuous] [--convert_idrsa_pub] [--isroca] [--check_publickey]
[--attack {brent,fermat_numbers_gcd,comfact_cn,wiener,factordb,smallq,pollard_rho,euler,z3_solver,neca,cm_factor,mersenne_pm1_gcd,SQUFOF,small_crt_exp,fibonacci_gcd,smallfraction,boneh_durfee,roca,fermat,londahl,mersenne_primes,partial_q,siqs,noveltyprimes,binary_polinomial_factoring,primorial_pm1_gcd,pollard_p_1,ecm2,cube_root,system_primes_gcd,dixon,ecm,pastctfprimes,qicheng,wolframalpha,hastads,same_n_huge_e,commonfactors,pisano_period,nsif,all}]已知公钥求密文
python RsaCtfTool.py --publickey 公钥文件 --uncipherfile 加密的文件已知公钥求私钥
RsaCtfTool.py --publickey 公钥文件 --privateyafu
https://github.com/bbuhrow/yafu
进入yafu的文件夹，输入：yafu-x64
之后输入：factor(需分解的数)
如果内容比较长，可以先写入一个文件中，例如“1.txt”
之后运行：
yafu-x64 "factor(@)" -batchfile 1.txt或者输入下面的命令，找到帮助。
yafu-x64.exe help
factordb
factordb也是一个很好用的工具，输入下面的命令：
factordb 需分解的数直接命令行输入：
References:
https://blog.csdn.net/ITgougou_/article/details/109124650
https://brilliant.org/wiki/rsa-encryption/
请登录后查看回复内容