[SWPUCTF 2024 秋季新生赛]Aftermath WP
原创[SWPUCTF 2024 秋季新生赛]Aftermath WP
原创
题目：
from Crypto.Util.number import getPrime, inverse, long_to_bytes, bytes_to_long
from sympy import gcd
key_size = 1024
p = getPrime(key_size // 2)
q = getPrime(key_size // 2)
N = p * q
phi = (p - 1) * (q - 1)
e1 = 3
e2 = 7
message = b"NSSCTF{...............................................}"
m = bytes_to_long(message)
assert gcd(m, N) == 1
c1 = pow(m, e1, N)
c2 = pow(m, e2, N)
print(f"N = {N}")
print(f"e1 = {e1}")
print(f"c1 = {c1}")
print(f"e2 = {e2}")
print(f"c2 = {c2}")
#N = 80722936701364382749961243326484006977187702986017980842794443374132452156776306032868217795522046975068822236770836452911408536092460646410756678157902792329645719935468879960944028782788489463895870961967670931567205550383999951787250211085264314795753745003815839218062934564501884684565508432346164094171
#e1 = 3
#c1 = 77027474990431732719325428265107176934045610651944725251406683442684093440239073195437770144166442593914418380343458827052860752131667771506129334676070396374008929588455988149871039697387983766750148969695215583137356681988572655848921827794639096404716760310059622671470680330144220097050812716421370445797
#e2 = 7
#c2 = 13491956530007991248882899018888359080930858500993821006822695375714947537976202424265808646466853291165511243721829370428583392329886743499827454177786585477285598196204906977043127274613692623229137936467994670727274820568522666762615055848367486507714640497446688083840123758417442971555904294548595887600签到题，就是很简单的RSA：
简单讲一下rsa原理：
RSA 加密算法，一种非对称加密算法
对称加密和非对称加密的区别：
对称加密：加密和解密使用的是相同的密钥。发送方和接收方必须都拥有这个共享的密钥。
- 密钥共享问题：由于双方使用相同的密钥，加密前必须安全地传输密钥给对方，这可能存在安全隐患。
非对称加密：使用一对密钥：公钥和私钥。
- 公钥：用于加密，公开给所有人。
- 私钥：用于解密，仅拥有者保密。
- 密钥分发简单：发送者只需知道接收方的公钥即可加密，而私钥无需传递，提高了安全性。
对称加密：速度快，适合处理大量数据。常用于数据传输中加密大块文件。
- 常见的对称加密算法：AES（高级加密标准）、DES、3DES。
非对称加密：计算量大，速度较慢，通常用于加密小数据块（如对称加密密钥的加密）。
- 常见的非对称加密算法：RSA、ECC、DSA。
RSA具体操作：
- 1. RSA 的数学基础
RSA 的核心依赖于以下几个数学概念：
- 质数：只能被 1 和自身整除的数，如 2, 3, 5, 7。
- 模运算：给定两个整数 a 和 n，模运算表示的是 a 除以 n 后的余数，记作 a mod n
- 欧拉函数 ϕ(n)：表示小于 n 且与 n 互质的整数个数。如果 n 是两个质数 p 和 q 的乘积，那么 ϕ(n)=(p−1)(q−1)
2. RSA 密钥生成 RSA 密钥生成是一个基于质数的过程，包含以下步骤： 步骤 1：选择两个大质数 选择两个足够大的质数 p 和 q。 步骤 2：计算模数 n 模数 n 是这两个质数的乘积，即： n=p×q 模数 n 会用作加密和解密过程中使用的“公钥”一部分。 步骤 3：计算欧拉函数 ϕ(n) 根据质数 p 和 q，计算 ϕ(n)：ϕ(n)=(p−1)×(q−1) 步骤 4：选择公钥指数 e 选择一个整数 e，要求 1<e<ϕ(n)，并且 e 与 ϕ(n) 互质。通常，常用的 e 值为 65537。 步骤 5：计算私钥指数 d 利用 e 计算私钥指数 d。这个 d 是 e 的模 ϕ(n) 的乘法逆元，满足以下条件： d×e≡1modϕ(n) 即 d×e 除以 ϕ(n) 的余数是 1。可以使用扩展欧几里得算法来计算 d。 最终密钥对：
- 公钥：包括 (n,e)，用于加密，公钥可以公开。
- 私钥：包括 (n,d)，用于解密，保密。
3. 加密过程 加密时，发送者使用接收者的公钥 (n,e) 来加密消息。假设消息 m 是一个整数（如果消息较长，可以先分块处理），加密过程如下： c = m的e次方再mod n 。其中 c 是加密后的密文，m 是原始消息，e 是公钥指数，n 是模数。 4. 解密过程 解密时，接收者使用自己的私钥 (n,d) 来解密密文 c。解密过程如下： m=c的d次方再mod n 其中 m 是解密后的原始消息，c 是加密后的密文，d 是私钥指数，n 是模数。 由于 d 和 e 满足特定的数学关系，这样的解密过程可以正确还原原始消息。 5. RSA 工作原理示例 假设我们手动执行 RSA 加密解密流程： 密钥生成：
- 选择两个质数 p=61 和 q=53。
- 计算模数 n=p×q=61×53=3233
- 计算欧拉函数 ϕ(n)=(p−1)×(q−1)=60×52=3120。
- 选择公钥指数 e=17（要求 1 < 17 < 3120 并且 17 与 3120 互质）。
- 计算私钥指数 d，使得 d×e≡1mod3120。通过扩展欧几里得算法可以得出 d=2753
因此，公钥是 (n=3233,e=17)，私钥是 (n=3233,d=2753) 加密：
- 假设消息 m=123
- 加密过程为： c=123的17次方mod 3233=855
- 加密后的密文是 c=855
解密：
- 接收者用私钥 (n=3233,d=2753) 解密： m=855的2753次方mod 3233=123
- 解密后，恢复原始消息 m=123
但这道题多了个共模攻击，通过扩展欧几里得算法找到整数系数，使得两个加密公式的指数相加等于 1，从而可以反向计算出明文就可以。
exp：
from Crypto.Util.number import inverse, long_to_bytes
from sympy import gcd
N = 80722936701364382749961243326484006977187702986017980842794443374132452156776306032868217795522046975068822236770836452911408536092460646410756678157902792329645719935468879960944028782788489463895870961967670931567205550383999951787250211085264314795753745003815839218062934564501884684565508432346164094171
e1 = 3
c1 = 77027474990431732719325428265107176934045610651944725251406683442684093440239073195437770144166442593914418380343458827052860752131667771506129334676070396374008929588455988149871039697387983766750148969695215583137356681988572655848921827794639096404716760310059622671470680330144220097050812716421370445797
e2 = 7
c2 = 13491956530007991248882899018888359080930858500993821006822695375714947537976202424265808646466853291165511243721829370428583392329886743499827454177786585477285598196204906977043127274613692623229137936467994670727274820568522666762615055848367486507714640497446688083840123758417442971555904294548595887600
def extended_gcd(a, b):
if b == 0:
return a, 1, 0
else:
g, x, y = extended_gcd(b, a % b)
return g, y, x - (a // b) * y
gcd_val, s1, s2 = extended_gcd(e1, e2)
assert gcd_val == 1
if s1 < 0:
c1 = inverse(c1, N)
s1 = -s1
if s2 < 0:
c2 = inverse(c2, N)
s2 = -s2
m = (pow(c1, s1, N) * pow(c2, s2, N)) % N
plaintext = long_to_bytes(m)
print("Recovered plaintext:", plaintext.decode())
flag:NSSCTF{It all played out with my life on pause}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
