专栏首页湛卢工作室RSA常见解题思路及技巧

RSA常见解题思路及技巧

RSA算法介绍

1977年,麻省理工学院的 Ron Rivest、Adi Shamir 和 Leonard Adleman 共同提出了一种非对称加密算法,用他们三人的姓氏缩写命名为 RSA。RSA 既不是惟一,也不是最早的非对称加密算法。但它是使用最广泛,因而也是最重要的非对称加密算法。

RSA算法的可靠性由极大整数因数分解的难度决定。也就是说,对一个极大整数做因数分解越困难,RSA算法越可靠。如果有人找到一种快速因数分解的算法的话,那么用RSA加密的信息的可靠性就肯定会极大降低。然而找到这样的算法的可能性是非常低的,如今只有短的RSA密钥才可能被强力方式破解,到2018年为止,还未有任何可靠的攻击RSA算法的方式。

RSA加密算法原理

在开始前可以根据这篇文章复习一下数论基础:

https://blog.sengxian.com/algorithms/mod-world

1、RSA加密解密涉及元素

· N:大整数N,我们称之为模数(modulus)

· p 和 q :大整数N的两个因子(factor)

· e 和 d:互为模反数的两个指数(exponent)

· c 和 m:分别是密文和明文

· phi:N的欧拉函数值,在求解d的时候常用

2、RSA算法密钥的产生

· 选取两个较大的互不相等的质数p和q,计算n = p * q

· 计算phi = (p-1) * (q-1)

· 选取任意e,使得e满足 1<e<phigcd(e , phi) = 1

· 计算e关于phi的模逆元d, 即d满足

· 加解密:

。其中m为明文,c为密文,{n,e}为公钥对,d为私钥,要求 0 <= m < n 。

3、RSA加密解密原理图

模拟场景:

假设A是秘密消息的发送者,B是秘密消息的接收者,则只有B知道私钥{d,n},所有人都可以知道公钥{e,n}。

加密操作:

如果A要发送需要保密的明文m给B,首先,要用B的公钥{e,n}计算,得到密文c,然后把c发送给B。

解密操作:

B收到密文c之后,根据自己的私钥{d,n}计算,得到的结果就是明文m。

常见解题思路

CTF中的RSA题目一般是将flag进行加密,给出密文c以及其他一些解题需要的信息,需要克服重重难关解密密文c,得到flag(即明文m),一般有下列题型:

1已知p、q、e,求d

求d脚本:get-d.py//rsatool.py(需gmpy模块)

例:

在一次RSA密钥对生成中,假设p=473398607161,q=4511911,e=17,求解d。

代码:

import gmpy2

p = gmpy2.mpz(473398607161)

q = gmpy2.mpz(4511491)

e = gmpy2.mpz(17)

phi = (p - 1) * (q - 1)

d = gmpy2.invert(e, phi)

print d

2已知p、q、e、密文c,求明文m

(1)求d脚本

(2)m=pow(c,d,n)

3已知n、e、密文c,求明文m

(1)分解n

a)yafu.com(https://sourceforge.net/projects/yafu/)

命令行运行 ./yafu-x64.exe,输入:factor(920139713) ,回车即可:

b) http://factordb.com

c) http://www.atool.org/quality_factor.php

(2)求d脚本

(3)m=pow(c,d,n)

例:http://ctf5.shiyanbar.com/crypto/RSAROLL.txt

题目给出了RSA加密之后的密文c、以及加密所用到的e、n的值,求解明文m。

分解n,得到p,q分别为18443,49891,后续脚本如下:

4已知public key,密文c,求明文m

(1)分解public key:

a) public.pem/public.pub文件

i. getn-e.py(RSA模块)

from Crypto.PublicKey import RSA

public = RSA.importKey(open('normal.pub').read())

n = long(public.n)

e = long(public.e)

print n

print e

ii. openssl:

pem/pub文件可以直接使用openssl提取,主要方法如

openssl rsautl -encrypt -in FLAG -inkey public.pem -pubin -out flag.enc openssl rsa -pubin -text -modulus -in warmup -in public.pem

或:

openssl rsa -inform PEM -in normal.pub -noout -modulus -text -pubin

n可以通过factorDB 或者yafu.exe分解得到p

b)public.pcap/public.ppc文件

i. pcap文件:

需要用wireshark等工具分析,根据流量包的通信信息,提取出所有解题需要用到的参数,然后进行解密;

ii. PPC文件:

这种模式是上述pcap文件的交互版,通常会给一个端口进行一些crypto的交互,参数会在交互中给出。

(2)github

a) https://github.com/pablocelayes/rsa-wiener-attack

b) https://github.com/D001UM3/CTF-RSA-tool

本文分享自微信公众号 - 湛卢工作室(xuehao_studio),作者:刘翔

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-12-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 除夕 | ATT&CK红队评估实战靶场vulnstack

    开源靶场VulnStack是由国内红日安全团队打造一个靶场知识平台。靶场设计思路来源ATT&CK红队评估模式,从漏洞利用、内网搜集、横向移动、构建通道、...

    tinyfisher
  • CTF杂谈之PHP魔法与CBC加密

    PHP语言的开发者在几乎所有内置函数以及基本结构中使用了很多松散的比较和转换,防止程序中的变量因为程序员的不规范而频繁的报错,然而这却带来了安全问题。也正是因为...

    tinyfisher
  • 杂项及密码基础

    Base58是用于Bitcoin中使用的一种独特的编码方式,主要用于产生Bitcoin的钱包地址。 相比Base64,Base58不使用数字"0",字母大写...

    tinyfisher
  • byteTCC框架--关于接口返回问题的讨论

    在普通的web项目中,调用接口返回数据,如下,不出错返回一种,出错了,返回另外一种。前端是直接可以拿到返回的信息的。

    IT云清
  • Shield Healthcare:为穷人服务(Technology)

    有时候,当你纠结于一个小小的客户服务失误时,你就解开了一大堆棘手的问题。这是因为Shield Healthcare没有按时给“耐莉阿姨”送去她的医疗用品。

    吴亚芳
  • 如何使用腾讯云云硬盘API

    腾讯云控制台允许您以类似于使用硬盘驱动器的方式管理腾讯云CVM的额外存储。只需点击腾讯云简化的GUI或图形用户界面,即可为我们的CVM添加云硬盘。但是,这不是一...

    好烟
  • 干货 | 怎样用数据分析找对象?

    写在前面 在工作中,经常利用多个数据指标对整体进行综合评价,需要把多个数据压缩成一个综合指标,这就是多指标综合评价方法。 耐心学完本期内容,足够装X一整年。 专...

    CDA数据分析师
  • 美国翻脸后,我们还能去哪里读AI?

    教育部月初发布留学预警1号文件,提醒赴美留学学生注意签证被拒签问题,并积极做好相应准备。

    大数据文摘
  • 懒人推动社会进步,这样的全自动早餐机器谁不想拥有?

    早上想多睡一会儿,而且还不用饿肚子,下面这个神器简直太贴心了。英国苏塞克斯郡一名69岁的老人耗时约1000小时,制作了一台全自动早餐神器,你只需一个按钮,机器就...

    机器人网
  • MIT推出新一代机器人猎豹3,可用于灾害救援

    镁客网

扫码关注云+社区

领取腾讯云代金券