• 首页 首页 icon
  • 工具库 工具库 icon
    • IP查询 IP查询 icon
  • 内容库 内容库 icon
    • 快讯库 快讯库 icon
    • 精品库 精品库 icon
    • 问答库 问答库 icon
  • 更多 更多 icon
    • 服务条款 服务条款 icon

RSA加密算法

武飞扬头像
juejin
帮助169

前言

最近遇到了很多rsa算法的题目,于是写了本文来简述一下什么是RSA算法以及它的原理是什么。

简介

RSA算法是一种非对称的加密算法,而非对称加密算法是一种密钥的保密方法。生成一对RSA密钥,其中之一是保密密钥(私钥),由用户保存;另一个为公开密钥(公钥),可对外公开;要加密传输内容时,比如A要给B传输信息,此时A先用B的公钥将内容加密后传输,B收到A传输过来的信息后用自己的私钥解密.

rsa.PNG

安全性

RSA的难度与大数分解难度等价。因为没有证明破解RSA就一定需要做大数分解。其保密强度随其密钥的长度增加而增强。但是随着我们的密钥越长,其加解密所耗用的时间也越长。因此要慎重考虑应用场景。

涉及参数

在RSA算法中用到了许多的参数,具体可以分为以下参数:

N:整数N,模数

p 和 q :N的两个因子(素数)

e 和 d:互为模反数的两个指数

c 和 m:密文和明文,求解d时用到函数(d=gmpy2.invert(e,n的欧拉函数))

rsa1.PNG

加密算法

RSA2.PNG

上面式子展示的就是将明文m(m<n是一个整数)加密成密文c,具体分析一下公式也就是密文等于m的e次方对N求余,可能涉及参数比较多有点混乱,我们重新整理一下,公式中C为密文,M为明文,而n,e组成公钥。

解密算法

rsa3.PNG

可以发现与上面式子是类似的,只不过将E改成了D,RSA的明文是对代表密文的数字 c 的 d 次方对 N 求余的结果。仿照上面公钥的组成方式,我们便可以推断出私钥的组成方式。

具体图解

rsa4.PNG

参数生成

根据上文内容可知,RSA涉及的参数还是挺多的,除去明文密文,其他参数我们要怎样生成呢?

N

在求N时我们需要找出两个很大的质数P,Q,n就等于P,Q的乘积,至于为什么PQ要尽量大的原因是上文提到过RSA算法类似于大数分解,如果我们P,Q设置的数过于小,那么N也是非常容易破解的,反之,如果我们设置的P,Q比较大,那么分解N并不是一件容易的事。

P*Q=N

φ

作用于密钥对的生成部分:

φ=(P-1)*(Q-1)

E

选择一个小于φ的整数e,且e与φ互素,φ 与 e 的最大公约数为1,即两者互质。

D

首先整数E小于φ,且e与φ互素,可以得到如下公式。

e*d mod φ=1

样例题目

了解了以上内容后,我们便可以尝试做一些题目来尝试求解一下RSA题目,下面题目皆为CTF比赛中RSA算法题目。

[HDCTF2019]basic rsa

一道非常简单的RSA题目,我们先下载附件,得到题目源码,简单分析一下:

import gmpy2
from Crypto.Util.number import *
from binascii import a2b_hex, b2a_hex


flag = "*****************"


p = 262248800182277040650192055439906580479
q = 262854994239322828547925595487519915551


e = 65533
n = p * q


c = pow(int(b2a_hex(flag), 16), e, n)


print c
# 27565231154623519221597938803435789010285480123476977081867877272451638645710

根据我们上面学过的内容,先找出来能被利用的参数,浏览题目会发现题目给出p,q,e,c。需要我们求M。因为n=p*q,就是说明已知p,q,e,c,n,要我们求M,我们只需要套入公式就能求解出密文M了:

import gmpy2
import libnum


p = 262248800182277040650192055439906580479
q = 262854994239322828547925595487519915551


e = 65533
n = p * q


c = 27565231154623519221597938803435789010285480123476977081867877272451638645710
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
M = pow(c, d, n)
print libnum.n2s(M)

运行脚本得到flag

flag{B4by_Rs4}

[ACTF新生赛2020]crypto-rsa3

也是先下载附件得到源码:

from Crypto.Util.number import *


import gmpy2


import random


e=65537


p = getPrime(512)


q = int(gmpy2.next_prime(p))


n = p*q


m = bytes_to_long(FLAG)


c = pow(m,e,n)


print(n)


print(c)


#n=177606504836499246970959030226871608885969321778211051080524634084516973331441644993898029573612290095853069264036530459253652875586267946877831055147546910227100566496658148381834683037366134553848011903251252726474047661274223137727688689535823533046778793131902143444408735610821167838717488859902242863683
#c=1457390378511382354771000540945361168984775052693073641682375071407490851289703070905749525830483035988737117653971428424612332020925926617395558868160380601912498299922825914229510166957910451841730028919883807634489834128830801407228447221775264711349928156290102782374379406719292116047581560530382210049

看完后会发现q只是对p进行了简单的调整,由此推断p,q的大小应该很接近,我们尝试用yafu分解一下 (yafu用于自动整数因式分解)

rsa7.PNG

分解出来p,q后还是按照公式去进行求解:

from Crypto.Util.number import *
import gmpy2
e=65537
n=177606504836499246970959030226871608885969321778211051080524634084516973331441644993898029573612290095853069264036530459253652875586267946877831055147546910227100566496658148381834683037366134553848011903251252726474047661274223137727688689535823533046778793131902143444408735610821167838717488859902242863683
c=1457390378511382354771000540945361168984775052693073641682375071407490851289703070905749525830483035988737117653971428424612332020925926617395558868160380601912498299922825914229510166957910451841730028919883807634489834128830801407228447221775264711349928156290102782374379406719292116047581560530382210049
q=13326909050357447643526585836833969378078147057723054701432842192988717649385731430095055622303549577233495793715580004801634268505725255565021519817179231
p=13326909050357447643526585836833969378078147057723054701432842192988717649385731430095055622303549577233495793715580004801634268505725255565021519817179293
phi=(p-1)*(q-1)
d=inverse(e,phi)
m=pow(c,d,n)
print(m)
#m=893441512863695667867454629314548913750576288726628646106246575194731343607717680126106810553506844477056381
#m=616374667b705f616e645f715f73686f756c645f6e6f745f62655f736f5f636c6f73655f696e5f76616c75657d
#m=actf{p_and_q_should_not_be_so_close_in_value}

这篇好文章是转载于:学新通技术网

  • 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
  • 本站站名: 学新通技术网
  • 本文地址: /boutique/detail/tanekbe
系列文章
更多 icon
同类精品
更多 icon
继续加载