easy RSA 解密RSA密文

howrsaworks.png

题目信息

已知一段加密的信息为:0xdc2eeeb2782c,且已知加密所用的公钥:(N=322831561921859 e = 23)

请解密出明文,提交时请将数字转化成ascii码提交,比如你解出的明文是0x6162,请提交字符串ab

提交格式:PCTF{明文字符串}

分析

算法原理

RSA加密演算法

RSA加密演算法 是一种非对称加密演算法,在公开密钥加密电子商业中被广泛使用。RSA是由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)在1977年一起提出的。当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的。^[1]^

公钥与私钥的产生

公钥与私钥的产生
假设Alice想要通过一个不可靠的媒体接收Bob的一条私人讯息。她可以用以下的方式来产生一个公钥和一个私钥:

随意选择两个大的质数 {\displaystyle p}p{\displaystyle q}q{\displaystyle p}p不等于{\displaystyle q}q,计算{\displaystyle N=pq}N=pq
根据欧拉函数,求得{\displaystyle r=\varphi (N)=\varphi (p)\times \varphi (q)=(p-1)(q-1)}{\displaystyle r=\varphi (N)=\varphi (p)\times \varphi (q)=(p-1)(q-1)}
选择一个小于{\displaystyle r}r的整数{\displaystyle e}e,使{\displaystyle e}e{\displaystyle r}r互质。并求得{\displaystyle e}e关于{\displaystyle r}r的模反元素,命名为{\displaystyle d}d(求{\displaystyle d}d{\displaystyle ed\equiv 1{\pmod {r}}}{\displaystyle ed\equiv 1{\pmod {r}}})。(模反元素存在,当且仅当{\displaystyle e}e{\displaystyle r}r互质)
{\displaystyle p}p{\displaystyle q}q的记录销毁。
{\displaystyle (N,e)}(N,e)是公钥,{\displaystyle (N,d)}(N,d)是私钥。Alice将她的公钥{\displaystyle (N,e)}(N,e)传给Bob,而将她的私钥{\displaystyle (N,d)}(N,d)藏起来。

题目分析

  • 工具

https://github.com/Ganapati/RsaCtfTool

  • 配置环境

Ubuntu 18.04 and Kali specific Instructions

git clone https://github.com/Ganapati/RsaCtfTool.git
sudo apt-get install libgmp3-dev libmpc-dev
cd RsaCtfTool
pip3 install -r "requirements.txt"
python3 RsaCtfTool.py

Generate a public key

将数据存置 test.pub

┌──(kali㉿kali)-[~/Desktop/RsaCtfTool]
└─$ ./RsaCtfTool.py --createpub -n 322831561921859 -e 23 --private                                                                                                                             130 ⨯
-----BEGIN PUBLIC KEY-----
MCAwDQYJKoZIhvcNAQEBBQADDwAwDAIHASWdFJIVQwIBFw==
-----END PUBLIC KEY-----

求私钥

┌──(kali㉿kali)-[~/Desktop/RsaCtfTool]
└─$ ./RsaCtfTool.py --publickey ./*.pub --private           

[*] Testing key ./test.pub.
[*] Performing mersenne_primes attack on ./test.pub.
 16%|████████████████████████▋                                                                                                                                    | 8/51 [00:00<00:00, 114130.72it/s]
[*] Performing smallq attack on ./test.pub.
[*] Performing system_primes_gcd attack on ./test.pub.
100%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 7007/7007 [00:00<00:00, 139558.52it/s]
[*] Performing fibonacci_gcd attack on ./test.pub.
100%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 9999/9999 [00:24<00:00, 401.92it/s]
[*] Performing pastctfprimes attack on ./test.pub.
100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 113/113 [00:00<00:00, 492678.12it/s]
[*] Performing noveltyprimes attack on ./test.pub.
100%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 21/21 [00:00<00:00, 303725.46it/s]
[*] Performing comfact_cn attack on ./test.pub.
[*] Performing fermat_numbers_gcd attack on ./test.pub.
  0%|| 31/9999 [00:32<3:45:22,  1.36s/it][!] Timeout.                                                                                                                                                                                   
  0%|| 31/9999 [01:00<5:22:46,  1.94s/it]
[*] Performing fermat attack on ./test.pub.
[*] Attack success with fermat method !

Results for ./test.pub:

Private key :
-----BEGIN RSA PRIVATE KEY-----
MDQCAQACBwElnRSSFUMCARcCBiZMI8i0ZwIEAWrgowIEAM8i4QIEAL1TzwIEAJkZ
xwIDOEUW
-----END RSA PRIVATE KEY-----

解密密文

┌──(kali㉿kali)-[~/Desktop/RsaCtfTool]
└─$ ./RsaCtfTool.py --publickey ./*.pub --uncipher 0xdc2eeeb2782c
private argument is not set, the private key will not be displayed, even if recovered.

[*] Testing key ./test.pub.
[*] Performing mersenne_primes attack on ./test.pub.
 16%|████████████████████████▋                                                                                                                                    | 8/51 [00:00<00:00, 101680.10it/s]
[*] Performing smallq attack on ./test.pub.
[*] Performing system_primes_gcd attack on ./test.pub.
100%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 7007/7007 [00:00<00:00, 139110.64it/s]
[*] Performing fibonacci_gcd attack on ./test.pub.
100%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 9999/9999 [00:24<00:00, 406.13it/s]
[*] Performing pastctfprimes attack on ./test.pub.
100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 113/113 [00:00<00:00, 447550.85it/s]
[*] Performing noveltyprimes attack on ./test.pub.
100%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 21/21 [00:00<00:00, 332378.81it/s]
[*] Performing comfact_cn attack on ./test.pub.
[*] Performing fermat_numbers_gcd attack on ./test.pub.
  0%|| 31/9999 [00:31<3:39:22,  1.32s/it][!] Timeout.                                                                                                                                                                                   
  0%|| 31/9999 [01:00<5:22:50,  1.94s/it]
[*] Performing fermat attack on ./test.pub.
[*] Attack success with fermat method !

Results for ./test.pub:

Unciphered data :
HEX : 0x00000033613559
INT (big endian) : 862008665
INT (little endian) : 25109964510986240
utf-8 : 3a5Y
STR : b'\x00\x00\x003a5Y'

题目答案

3a5Y


标题:easy RSA 解密RSA密文
作者:糖醋鱼
地址:https://expoli.tech/articles/2021/07/15/1626312938763.html

    评论
    0 评论
avatar

取消