【攻防世界】Crypto系列之baigeiRSA

题目代码如下

import libnum
from Crypto.Util import number
from secret import flag

size = 128
e = 65537
p = number.getPrime(size) #产生二进制数
q = number.getPrime(size)
n = p*q

m = libnum.s2n(flag) #将数字转换为字符串
c = pow(m, e, n)

print('n = %d' % n)
print('c = %d' % c)

#n = 88503001447845031603457048661635807319447136634748350130947825183012205093541
#c = 40876621398366534035989065383910105526025410999058860023908252093679681817257

分析可得算法为RSA算法，已知数据为n,c,e。

具体来说，加密过程如下所示：

选择两个大质数p和q，计算出n=pq，并计算出φ(n)=(p-1)(q-1)。

选择一个大于1小于φ(n)的整数e，计算出d，使得ed=1 mod φ(n)。

根据明文M，计算出密文C=M^e mod n。
解密过程则可以使用私钥(n, d)来计算出原文M，具体来说：

输入密文C，以及私钥(n, d)。

计算出原文M=C^d mod n。

请注意，由于RSA算法依赖于大质数的分解难度，所以它的安全性并不是十分稳定。目前，对于小规模的RSA密钥，已经有多种针对性的分解方法可以破解RSA密钥，但是对于大规模的RSA密钥，还没有有效的分解方法。所以，如果要使用RSA算法，需要选择更大的密钥来保证安全性。另外，由于RSA算法的计算复杂度较高，它不太适合用于加密大量数据。通常情况下，RSA算法更多的用于数字签名的场景。

这里使用yafu工具对n进行自动因式分解，快速将yafu分解出p,q值，工具运行如下

得到p和q

P39 = 274539690398523616505159415195049044439
P39 = 322368694010594584041053487661458382819

接下来计算欧拉函数

p = 274539690398523616505159415195049044439
q = 322368694010594584041053487661458382819

oula = (p-1)*(q-1)
print(oula)

88503001447845031603457048661635807318850228250339231930401612280155697666284

然后计算e的逆元

from Crypto.Util.number import *
print(inverse(65537,88503001447845031603457048661635807318850228250339231930401612280155697666284))

7662328611548784798175310040223409230315031128864989272824492242208270573241

注意这里c=pow(m,e,n),由RSA解密算法得m=pow(c,d,n)可求出m的数字，然后使用libnum.n2s()将数字转换为字符串

n = 88503001447845031603457048661635807319447136634748350130947825183012205093541
c = 40876621398366534035989065383910105526025410999058860023908252093679681817257
d = 7662328611548784798175310040223409230315031128864989272824492242208270573241
m = pow(c,d,n)
print(libnum.n2s(m))

得到字符串

b'HSCTF{@Zh3n_Ba1_G3i!@}'

打赏