rsarsa
rsarsa
下载压缩包然后解压
这里给了p、q、e、c
1、算法基础 - 数论知识
- 互质关系：如果两个正整数，除了 1 以外，没有其他公因数，那么这两个数是互质关系。例如，15 和 8 是互质的，因为 15 的因数是 1、3、5、15，8 的因数是 1、2、4、8，它们只有公因数 1。
- 欧拉函数：对于正整数n，欧拉函数φ(n)表示小于等于n且与n互质的正整数的个数。例如，当n = 6 时，与 6 互质的数有 1 和 5，所以φ(6) = 2。如果n是质数p，那么φ(p) = p -1，因为所有小于p的正整数都与p互质。
- 模运算：模运算即求余数的运算。例如，7 mod 3 = 1，表示 7 除以 3 的余数是 1。在 RSA 算法中，模运算起到了关键作用，许多运算都是在模某个数的环境下进行的。
- 费马小定理和欧拉定理
-
- 费马小定理：假如p是质数，且a与p互质，那么a^p-1 mod p = 1。例如，当p = 5，a = 3时，3^4 mod 5 = 81 mod 5 = 1。
-
-
- 欧拉定理：若a与n互质，则a^φ(n) mod n = 1。它是费马小定理的推广，当n为质数时， φ(n) = n - 1，就退化成费马小定理。
-
步骤一：选择两个大质数p和q
步骤二：计算n = p × q和
步骤三：选择一个整数e，使得1 < e < φ (n)且e与 φ(n)互质
步骤四：计算d，使得e × d mod φ(n)，即d是e在模 φ(n)下的乘法逆元
解密过程
- 使用私钥(d，n)对密文c进行解密，解密公式为m = c^d mod n。
- 对于前面得到的c = 855，d = 2753，n = 3233，计算m = 855^2753 mod 3233，经过计算可以得到m = 123，即还原出了原始消息。
利用原理写个EXP：
p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e = 65537
c = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034
import gmpy2 #gmpy2 是一个用于高效数学运算的库。
from Crypto.Util.number import long_to_bytes #inverse 用于计算模逆。 long_to_bytes 用于将长整型转换为字节串。
n=(p*q) # n 是 RSA 模数，等于两个质数 p 和 q 的乘积。
phi_n=(q-1)*(p-1) #phi_n 是欧拉函数值，用于计算私钥。
d=gmpy2.invert(e,phi_n) #d 是 RSA 私钥，使用 inverse 函数计算 e 关于 phi_n 的模逆。
m=pow(c,d,n) #使用 RSA 解密公式 m = c^d mod n，计算出明文 m。
print(m)
flag{5577446633554466577768879988}
原文地址：https://blog.csdn.net/ming20211016/article/details/144794826
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！