RSA(Rivest-Shamir-Adleman)
RSA是公钥密码系统,所谓公钥加密系统就是不通过相同的密钥进行加密和解密。RSA适用于签名和加密,RSA 广泛用于电子商务协议中,足够长的密钥大大的提高了安全性。
为英国情报机构GCHQ工作的英国数学家Clifford Cocks在 1973 年的一份内部文件中描述了一个等效系统,但考虑到当时实施它所需的计算机相对昂贵,它主要被认为是一种好奇心,并且就是众所周知的,从未部署过。然而,由于其绝密分类,他的发现直到 1998 年才被披露,而 Rivest、Shamir 和 Adleman 独立于 Cocks 的工作设计了 RSA。
RSA 算法于 1978 年由MIT的Ron Rivest、Adi Shamir和Leonard Adleman公开描述;字母RSA是他们姓氏的首字母,按与纸上相同的顺序列出。
RSA包含公钥和私钥,公钥用于加密,私钥用于解密,但不是绝对的,在下面的链接中介绍了原因。
Tide安全文库 http://wiki.tidesec.com/docs/Crypto/82851f8c62417fdbfb8168ec4011f532
公钥由模数n和公共(或加密)指数组成e。私钥d由必须保密的私有(或解密)指数组成。
此时,密钥生成
公钥(n,e)
私钥(n,d)
因为公钥为(n,e),加密方获得了n和e。
加密函数为:
c(m) = m^e mod n
加密方通过加密函数生成密文,并将密文发送给对方。
因为私钥为(n,d),解密方拥有n和d。
加密函数为:
m(c) = c^d mod n
解密方通过解密函数解密出明文。
写这篇文章的今天,正在参加CTF,遇到一道非常规解法的rsa密码学题目促使我想把解题过程中学到的都整理下来,作为一个note,欢迎补充👏。
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 rsa -pubin -in .pem公钥文件 -text -modulus
其中可以看到Exponent就是分解得到的e,modulus是分解到的n。
网址:
http://factordb.com/
这是一个比较好用的网站,对于比较小的n比较好分解。
RsaCtfTool是一个RSA多重攻击工具
从弱公钥中解密数据并尝试恢复私钥自动选择给定公钥的最佳攻击。
官方给出的使用方法
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 公钥文件 --private
https://github.com/bbuhrow/yafu
进入yafu的文件夹,输入:yafu-x64
之后输入:factor(需分解的数)
如果内容比较长,可以先写入一个文件中,例如“1.txt”
之后运行:
yafu-x64 "factor(@)" -batchfile 1.txt
或者输入下面的命令,找到帮助。
yafu-x64.exe help
factordb也是一个很好用的工具,输入下面的命令:
factordb 需分解的数
直接命令行输入:
References:
RSA解密工具--RsaCtfTool使用_Three ooo的博客-CSDN博客_rsactftool
RSA Encryption | Brilliant Math & Science Wiki