BUUCTF rsarsa

题目

RSA

RSA是目前最有影响力的公钥加密算法，公开密钥密码体制就是使用不同的加密密钥与解密密钥，是一种“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。

算法原理

RSA公开密钥密码体制的原理是：
根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥

算法描述

1. 任意选取两个不同的大素数p和q，这两个值越大，破解RSA越困难，而执行加密和解密所用时间也越长。
   计算乘积n = p*q、z = (p-1)(q-1)
2. 选择一个小于 n 的数e，且 e 和 z 互质(没有非1的公因数)(此时 e 和 z 互素)。使用字母 e 表示是因为这个值将被用于加密。
3. 求一个数d，使得 ed -1 可以被 z 整除。使用字母 d 表示是因为这个值将被用于解密。即给定 e ，我们选择 d ，使得
   ed mod z = 1
4. 得到公钥 \(K_B^+=(n,e)\) 和私钥 \(K_B^-=(n,d)\)

加解密过程

能够实现加解密这个恒等式(模运算性质)很有用    \((a\;mod\;n)^d\;mod\;n\;=\;a^d\;mod\;n\)

1. 加密
   假设A向B发送一个由整数m表示的比特组合，且 m < n 。为了进行编码，A利用公钥 \(K_B^+=(n,e)\) 执行指数运算 \(m^e\) ，然后计算 \(m^e\) 被 n 除的整数余数c。密文c的比特模式发送给B。
   即

\[c\;=\;m^e\;mod\;n \]

2. 解密
   要求B使用私钥 \(K_B^-=(n,d)\)计算

\[m\;=\;c^d\;mod\;n \]

工作原理

在RSA加密过程中，一个报文m(唯一地表示为整数)使用模n算术做e次幂运算，即

\[c\;=\;m^e\;mod\;n \]

解密则先对该值执行d次幂运算，再做模n运算。因此先加密再解密的结果就是

\[(m^e\;mod\;n)^d\;mod\;n=m \]

下面我们来看看关于这个量能够得到什么。正如前面提到的，模算术的一个重要性质是对于任意值 a 、n 和 d 都有\((a\;mod\;n)^d\;mod\;n\;=\;a^d\;mod\;n\) 。因此在这个性质中使用\(a=m^e\)，则有

\[(m^e\;mod\;n)^d\;mod\;n\;=\;m^{ed}\;mod\;n \]

因此剩下证明 \(m^{ed}\;mod\;n=m\)，为了证明这一点，需要用到数论中一个相当神奇的结论：如果 p 和 q 是素数，且有 n = p * q 和 z = (p-1)(q-1) ，则\(x^y\;mod\;n\)与\(x^{y\;mod\;z}\;mod\;n\)是等同的。应用这个结论，对于 x=m 和 y=ed ，可得

\[m^{ed}\;mod\;n\;=\;m^{ed\;mod\;z}\;mod\;n \]

但要记住，我们是这样选择e和d的，即ed mod z = 1。这告诉我们

\[m^{ed}\;mod\;n\;=\;m^1\;mod\;n\;=\;m \]

这正是我们希望得到的结果！先对m做e次幂运算(加密)再做d次幂运算(解密)，然后做模n的算术运算，就可得到初始明文m。甚至更为奇妙之处是，如果我们先对m做d次幂运算(加密)，再做e次幂运算，即颠倒加密和解密的次序，先执行解密操作再执行加密操作，也能得到初始明文m 这个奇妙的结果完全遵循下列模算术：

\[(m^d\;mod\;n)^e\;mod\;n=m^{de}\;mod\;n=m^{ed}\;mod\;n=(m^e\;mod\;n)^d\;mod\;n \]

解

1.利用RSA Tool2找到私钥d
(链接：https://pan.baidu.com/s/1jzUGaJFwYgIAre_-sPChmQ 提取码：p1wl )

2.利用python函数pow()求出flag

模数指数 pow() 提供带有 3 个参数，pow(a, b, c) 评估模幂运算\(a^b\;mod\;c\)

p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e =  65537
n = p*q
c = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034
d = 56632047571190660567520341028861194862411428416862507034762587229995138605649836960220619903456392752115943299335385163216233744624623848874235303309636393446736347238627793022725260986466957974753004129210680401432377444984195145009801967391196615524488853620232925992387563270746297909112117451398527453977

M = pow(c,d,n)    #快速求幂取模运算
print(M)

3.得到d=5577446633554466577768879988
即flag{5577446633554466577768879988}

参考链接：
https://blog.csdn.net/qq_42777804/article/details/99578263

https://baike.baidu.com/item/RSA算法/263310#2
参考书籍：
《计算机网络 自顶而下方法(原书第7版)》/(美)詹姆斯·F·库罗斯等；陈鸣译