CTF密码学之RSA攻击算法

 

上一篇：CTF现代密码之RSA之数论

  前言：

学习完基本数论后，我们开始学习 RSA 的各种攻击算法及其数学原理。希望大家在学习的过程中更多的去关注攻击算法实现的原理，而不仅仅只在于 copy 攻击代码。

本文涉及靶场知识点——RSA之小公钥指数攻击 ：通过该实操练习了解CTF中常见和以前奇葩题型，有助于我们学习更多的内容。本次实验我们将学习RSA中小公钥指数的情况，例如在e特别小的情况下如何去生成私钥。

 

工具准备：

工具和第三方库的安装教程请自行百度

• python3.8环境：https://www.python.org/downloads/windows/

• 大素数分解工具:

  • factordb在线分解：http://factordb.com/

  • win10 yafu-x64：https://sourceforge.net/projects/yafu/

• python第三方库：

  • gmpy2

  • pycryptodome

  • libnum

  • sympy

  • rsa

  RSA加密类型：

1. 公钥解析，签名加密

•  

1. 利用公约数求解

•  

1. 分解 N 得到多个相同的 P

•  

1. dp、dq 泄露

•  

1. dp 泄露

•  

1. Roll 按行加密

•  

1. 共模攻击

•  

1. 低加密指数攻击

•  

1. 低加密指数广播攻击

•  

1. 低解密指数攻击

1.公钥解析,签名加密

如果题目给了pem或者key后缀结尾的文件，用工具解析出n和e。或者可以用kali自带的Openssl从公钥文件中提取出n和e。

命令：openssl rsa -pubin -text -modulus -in key.pem

例题：1

BUURSA：     https://buuoj.cn/challenges#RSA

公钥文件

-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAMAzLFxkrkcYL2wch21CM2kQVFpY9+7+
/AvKr1rzQczdAgMBAAE=
-----END PUBLIC KEY-----

 

在线网站解析公钥：http://ctf.ssleye.com/

得到n和e之后，用factordb：http://factordb.com/

分解模n，得到p,q的值。

import rsa            #rsa模块
from gmpy2 import*    #gmpy2模块

e= 65537
n= 86934482296048119190666062003494800588905656017203025617216654058378322103517
p= 285960468890451637935629440372639283459
q= 304008741604601924494328155975272418463

#求私钥d
'''
phi = (p-1)*(q-1)
d = invert(e,phi)     #gmpy2.invert(),用来求模逆的方法
print(d)
'''
d= 81176168860169991027846870170527607562179635470395365333547868786951080991441


key = rsa.PrivateKey(n,e,d,q,p)         #在pkcs标准中,pkcs#1规定,私钥包含(n,e,d,p,q)

with open("C:\\Users\\MIKEWYW\\Desktop\\flag.txt","rb") as f:  #以二进制读模式，读取密文  
    f = f.read()
    print(rsa.decrypt(f,key))           # f:公钥加密结果  key:私钥

  例题：2020西湖论剑BrokenSystems

题目

BrokenSystems.py

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from secret import flag
import os
rsa = RSA.generate(2048)
public_key = rsa.publickey().exportKey()
f=open("public.key","w")
f.write(public_key.decode())
f.close()

rsakey=RSA.importKey(open("public.key","r").read())
rsa = PKCS1_OAEP.new(rsakey)
msg=rsa.encrypt(flag.encode())
f=open("message","wb")
f.write(msg)
f.close()

public.txt

-----BEGIN PUBLIC KEY-----
MIICITANBgkqhkiG9w0BAQEFAAOCAg4AMIICCQKCAQEAwgdFIj/1uUss2EEhZvco
iiHyGH4aQhRTkYyrA8gCU0USM+sb3CNjdEIoqoaUqMLLyDP4Dd9AgxpokBsjC4Pz
8P7Uty0LlCteld7ayNzABHoq+5DIHtctOtSbcvyL0NMWfd2qarUWfAWN82rxkLIW
CFu9nWIfm9I6CT5OPZzDh7YnTywznIjhstkIrLM/TiDmR6vuBxSjzORkbolilLeB
A9zJpNt+1oEWTG5sx/0zR24XSmxwcDeyUEkTZfnw63auq6B9svZi2IBIr5jIjHbG
cQ25ZY1J/KDK8fXNmdwH8YhDK0j4VXEWitEPyCS3toK61sql0S/28EySeGtzirGb
twKCAQAdLS8fFz+BzzaP7AbUDUf9kvhhXBLuwUFo8ohCeVK4z1pTj3C6M0G2oXOu
gDdalrDThNlyKxkUn3iUc3Xgoz315pPtq9Xk1Ez/qeUl6gFPP6SZtfeymyGdkLiN
pVquOghjczjXvtBW467Fdb5Wu95TSzVaLndX23rsqW541n8hUwt8PsJKxh+bR0qy
gyIN2VRRNdBlpyTOL49E4y5GDu9fmVgAnFivWVGT135ywl8MsBUFuZPBNTKLEbUA
3KvJVckXf4Od0ENYbiWjEzXn1UN9yebNbU6+yyk34WAmwnkuF0X0Tu1UEb6qtV7Q
kF25GYy9QxERvodGL0Y2njHRpGE/
-----END PUBLIC KEY-----

message.txt

'Ω?奟?ypG睉晜