RSA加密算法
前言
最近遇到了很多rsa算法的题目,于是写了本文来简述一下什么是RSA算法以及它的原理是什么。
简介
RSA算法是一种非对称的加密算法,而非对称加密算法是一种密钥的保密方法。生成一对RSA密钥,其中之一是保密密钥(私钥),由用户保存;另一个为公开密钥(公钥),可对外公开;要加密传输内容时,比如A要给B传输信息,此时A先用B的公钥将内容加密后传输,B收到A传输过来的信息后用自己的私钥解密.
安全性
RSA的难度与大数分解难度等价。因为没有证明破解RSA就一定需要做大数分解。其保密强度随其密钥的长度增加而增强。但是随着我们的密钥越长,其加解密所耗用的时间也越长。因此要慎重考虑应用场景。
涉及参数
在RSA算法中用到了许多的参数,具体可以分为以下参数:
N:整数N,模数
p 和 q :N的两个因子(素数)
e 和 d:互为模反数的两个指数
c 和 m:密文和明文,求解d时用到函数(d=gmpy2.invert(e,n的欧拉函数))
加密算法
上面式子展示的就是将明文m(m<n是一个整数)加密成密文c,具体分析一下公式也就是密文等于m的e次方对N求余,可能涉及参数比较多有点混乱,我们重新整理一下,公式中C为密文,M为明文,而n,e组成公钥。
解密算法
可以发现与上面式子是类似的,只不过将E改成了D,RSA的明文是对代表密文的数字 c 的 d 次方对 N 求余的结果。仿照上面公钥的组成方式,我们便可以推断出私钥的组成方式。
具体图解
参数生成
根据上文内容可知,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用于自动整数因式分解) 。
分解出来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
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
photoshop蒙版画笔没反应怎么办
PHP中文网 06-24