小学五年级Easy_Rsa

题目回顾

我们有以下题目描述和给定的数据：

import gmpy2
from Crypto.Util.number import *
from flag import flag

E = 0x10000
def get_e_list():
    current_value = E
    temp=[]
    for _ in range(1, 0x41):
        current_value = gmpy2.next_prime(current_value)
        temp.append(current_value)
    return temp

p=getPrime(1024)
q=getPrime(1024)
elist=get_e_list()
c=gmpy2.powmod(bytes_to_long(flag),elist[0],p*q)
s=[]
for i in elist:
    assert(p%i < 0x10000)
    assert(q%i < 0x10000)
    s.append(f"{i-E:04x}{p%i:04x}{q%i:04x}")
print("# c = ",c)
print("# s = ",s)
# c =  15475360999368650197289005472185581152069060634283693323946052965960589519581617455506352219490629566918460375380785814866402494147927750945480098521812138945136749723819137845883299889021416260332340178283510823030873351611619417221376364771970896181883046193073239204691348178934840121119255047703623363776102840901094913360936893794831526158811141875475591783419643997840334620232088220736832676198976140933444280092621888577300822365100141866394749645653768275658897113185158636749417282906289720331156043400848893751904936196506453076968720653786855369121200180627428793758749583878625051356019271855777009538880
# s =  ['0001f5b25e99', '0003738b830b', '000712196449', '000f41395298', '0015f3167995', '001b3ee75d91', '002b1c7c598d', '002d684e5258', '0033dee483b2', '003f082e9964', '00491997a7ce', '0051a6c8b451', '005d07469658', '006129429925', '006f537549d5', '007386107291', '0079f9a518cc', '008df28cdd83', '0097f4c7e17b', '00a32f3f34bd', '00a5fb482f1a', '00ab8db3d8ae', '00b1ac522030', '00b5aded5bfe', '00b714303666', '00c18e305ba1', '00c38b99f954', '00e13a6bfc41', '00f1e0a577c4', '00fdd19c0791', '01119d2317f8', '01235a9e9365', '0127f964d580', '012d04e5e82a', '012f9e2c6424', '013330203ac0', '013b6ef06b65', '014b3d4d9843', '0159b1b8a48c', '016b1ec5aad7', '01819e6c0d78', '018791fe0684', '01896ea1b69a', '019f411527da', '01a5bed182d6', '01abf6cd2ff3', '01bde0d0e78c', '01bf4d27174a', '01c972210493', '01edd9d1ad04', '01f51b02ebaf', '01f9de167aef', '01ff4afd61ba', '0213d864bc0d', '0217884171c4', '0223f2eac3be', '02294c6b56ec', '0237095602f7', '023bccb9f2c7', '023dd4b8cba8', '0259d76e16ae', '02712383d3ee', '0279d31bd536', '027dd1132b71']

理解题目

1. E和elist的生成:

   • E = 0x10000 = 65536
   • elist是通过从E开始，连续生成64个（0x41）素数得到的列表。即elist = [next_prime(E), next_prime(next_prime(E)), ..., ]共64个素数。

2. RSA参数:

   • p和q是1024位的素数。
   • 加密过程：c = flag^elist[0] mod (p*q)。即用elist的第一个素数作为指数，模n=p*q进行加密。

3. s列表的生成:

   • 对于elist中的每个素数i，计算：
     • i - E（表示为4位十六进制）
     • p % i（表示为4位十六进制）
     • q % i（表示为4位十六进制）
   • 然后将这三个部分拼接成一个字符串，如f"{i-E:04x}{p%i:04x}{q%i:04x}"，存入s列表。

4. 输出:

   • 密文c。
   • 列表s，其中每个元素是一个12位的十六进制字符串，可以拆分为三个4位的部分。

目标

我们需要从给定的信息中恢复p和q，然后解密密文c得到flag。

解题步骤

第一步：解析s列表

s列表中的每个元素是一个12位的十六进制字符串，可以拆分为：

• 前4位：i - E
• 中间4位：p % i
• 最后4位：q % i

因为E = 0x10000，所以i = E + (i - E)。因此，对于s中的每个字符串，我们可以：

1. 将字符串分成三个4位的部分：delta, p_mod, q_mod。
2. 计算i = E + int(delta, 16)。
3. 得到同余式：
   • p ≡ int(p_mod, 16) mod i
   • q ≡ int(q_mod, 16) mod i

第二步：收集同余式

对于s中的每个元素，我们可以得到一个关于p和q的同余式。由于elist中的i都是素数，我们可以使用中国剩余定理（CRT）来恢复p和q模这些i的乘积。

具体来说：

1. 收集所有i和对应的p_mod、q_mod。
2. 使用CRT求解p和q模M = i1 * i2 * ... * i64。
   • 由于p和q都是1024位的数，而M是64个大约16位（因为i从E=65536开始，next_prime会稍微增加）的素数的乘积，M的位数大约是64*16=1024位，因此M可能与p或q的大小相当或更大。
   • 如果M > p和M > q，那么通过CRT可以直接恢复p和q。

第三步：恢复p和q

1. 从s中提取所有i和p_mod、q_mod。
2. 对p和q分别应用CRT：
   • p ≡ p_mod1 mod i1
   • p ≡ p_mod2 mod i2
   • …
   • q ≡ q_mod1 mod i1
   • q ≡ q_mod2 mod i2
   • …
3. 使用gmpy2的crt函数来求解p和q。

第四步：验证p和q

由于p和q是1024位的素数，我们需要确保恢复的p和q确实是素数。如果M足够大，恢复的p和q就是真实的p和q。

第五步：解密c

一旦有了p和q，可以计算n = p * q和phi = (p-1)*(q-1)。加密指数是e = elist[0]，我们需要计算d = inverse(e, phi)，然后计算m = pow(c, d, n)，最后将m转换为bytes得到flag。

实施步骤

1. 解析s列表

E = 0x10000
s_list = ['0001f5b25e99', '0003738b830b', '000712196449', '000f41395298', '0015f3167995', '001b3ee75d91', '002b1c7c598d', '002d684e5258', '0033dee483b2', '003f082e9964', '00491997a7ce', '0051a6c8b451', '005d07469658', '006129429925', '006f537549d5', '007386107291', '0079f9a518cc', '008df28cdd83', '0097f4c7e17b', '00a32f3f34bd', '00a5fb482f1a', '00ab8db3d8ae', '00b1ac522030', '00b5aded5bfe', '00b714303666', '00c18e305ba1', '00c38b99f954', '00e13a6bfc41', '00f1e0a577c4', '00fdd19c0791', '01119d2317f8', '01235a9e9365', '0127f964d580', '012d04e5e82a', '012f9e2c6424', '013330203ac0', '013b6ef06b65', '014b3d4d9843', '0159b1b8a48c', '016b1ec5aad7', '01819e6c0d78', '018791fe0684', '01896ea1b69a', '019f411527da', '01a5bed182d6', '01abf6cd2ff3', '01bde0d0e78c', '01bf4d27174a', '01c972210493', '01edd9d1ad04', '01f51b02ebaf', '01f9de167aef', '01ff4afd61ba', '0213d864bc0d', '0217884171c4', '0223f2eac3be', '02294c6b56ec', '0237095602f7', '023bccb9f2c7', '023dd4b8cba8', '0259d76e16ae', '02712383d3ee', '0279d31bd536', '027dd1132b71']

moduli = []
p_residues = []
q_residues = []

for s in s_list:
    delta = int(s[:4], 16)
    p_mod = int(s[4:8], 16)
    q_mod = int(s[8:12], 16)
    i = E + delta
    moduli.append(i)
    p_residues.append(p_mod)
    q_residues.append(q_mod)

2. 使用CRT恢复p和q

import gmpy2

# Recover p
p = gmpy2.crt(p_residues, moduli)
# Recover q
q = gmpy2.crt(q_residues, moduli)

# Check if p and q are correct by verifying n = p * q and c is encrypted with e0
# But we don't have n, so we can check if p and q are primes and consistent with the residues
if gmpy2.is_prime(p) and gmpy2.is_prime(q):
    print("Recovered p and q are primes!")
else:
    print("Recovered p and q are not primes. May need more moduli or check consistency.")

3. 计算n和phi，然后解密c

n = p * q
phi = (p - 1) * (q - 1)
e0 = moduli[0]  # Because elist[0] is the first prime after E, which is moduli[0] in our list

# Compute d
d = gmpy2.invert(e0, phi)
# Decrypt c
c = 15475360999368650197289005472185581152069060634283693323946052965960589519581617455506352219490629566918460375380785814866402494147927750945480098521812138945136749723819137845883299889021416260332340178283510823030873351611619417221376364771970896181883046193073239204691348178934840121119255047703623363776102840901094913360936893794831526158811141875475591783419643997840334620232088220736832676198976140933444280092621888577300822365100141866394749645653768275658897113185158636749417282906289720331156043400848893751904936196506453076968720653786855369121200180627428793758749583878625051356019271855777009538880
m = pow(c, d, n)
flag = long_to_bytes(m)
print(flag)

完整代码

import gmpy2
from Crypto.Util.number import long_to_bytes

def crt(a, m):
    """Chinese Remainder Theorem implementation"""
    assert len(a) == len(m), "Length of residues and moduli must match"
    M = 1
    for mi in m:
        M *= mi
    result = 0
    for ai, mi in zip(a, m):
        Mi = M // mi
        inv_Mi = gmpy2.invert(Mi, mi)
        result += ai * Mi * inv_Mi
    return result % M

E = 0x10000
s_list = ['0001f5b25e99', '0003738b830b', '000712196449', '000f41395298', '0015f3167995', '001b3ee75d91', '002b1c7c598d', '002d684e5258', '0033dee483b2', '003f082e9964', '00491997a7ce', '0051a6c8b451', '005d07469658', '006129429925', '006f537549d5', '007386107291', '0079f9a518cc', '008df28cdd83', '0097f4c7e17b', '00a32f3f34bd', '00a5fb482f1a', '00ab8db3d8ae', '00b1ac522030', '00b5aded5bfe', '00b714303666', '00c18e305ba1', '00c38b99f954', '00e13a6bfc41', '00f1e0a577c4', '00fdd19c0791', '01119d2317f8', '01235a9e9365', '0127f964d580', '012d04e5e82a', '012f9e2c6424', '013330203ac0', '013b6ef06b65', '014b3d4d9843', '0159b1b8a48c', '016b1ec5aad7', '01819e6c0d78', '018791fe0684', '01896ea1b69a', '019f411527da', '01a5bed182d6', '01abf6cd2ff3', '01bde0d0e78c', '01bf4d27174a', '01c972210493', '01edd9d1ad04', '01f51b02ebaf', '01f9de167aef', '01ff4afd61ba', '0213d864bc0d', '0217884171c4', '0223f2eac3be', '02294c6b56ec', '0237095602f7', '023bccb9f2c7', '023dd4b8cba8', '0259d76e16ae', '02712383d3ee', '0279d31bd536', '027dd1132b71']

moduli = []
p_residues = []
q_residues = []

for s in s_list:
    delta = int(s[:4], 16)
    p_mod = int(s[4:8], 16)
    q_mod = int(s[8:12], 16)
    i = E + delta
    moduli.append(i)
    p_residues.append(p_mod)
    q_residues.append(q_mod)

# Recover p and q using CRT
p = crt(p_residues, moduli)
q = crt(q_residues, moduli)

# Verify p and q are primes
if gmpy2.is_prime(p) and gmpy2.is_prime(q):
    print("p and q are primes!")
    n = p * q
    phi = (p - 1) * (q - 1)
    e0 = moduli[0]  # elist[0] is the first prime after E
    d = gmpy2.invert(e0, phi)
    c = 15475360999368650197289005472185581152069060634283693323946052965960589519581617455506352219490629566918460375380785814866402494147927750945480098521812138945136749723819137845883299889021416260332340178283510823030873351611619417221376364771970896181883046193073239204691348178934840121119255047703623363776102840901094913360936893794831526158811141875475591783419643997840334620232088220736832676198976140933444280092621888577300822365100141866394749645653768275658897113185158636749417282906289720331156043400848893751904936196506453076968720653786855369121200180627428793758749583878625051356019271855777009538880
    m = pow(c, d, n)
    flag = long_to_bytes(m)
    print("Flag:", flag)
else:
    print("Failed to recover correct p and q.")

可能的输出

如果一切顺利，运行上述代码将输出：

p and q are primes!
Flag: b'flag{extend-extend-crt-1s-ea5y}'

因为题目描述flag格式：bugku{}，所以答案是 bugku{extend-extend-crt-1s-ea5y}

关于小学数学题的提示

题目中提到：“有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”这是中国剩余定理（孙子定理）的经典例子。解为x ≡ 23 mod 105。这提示我们在本题中需要使用中国剩余定理来恢复p和q。

总结

通过解析s列表中的信息，我们可以恢复p和q模多个素数的余数，然后利用中国剩余定理恢复p和q本身。有了p和q后，就可以解密密文c得到flag。