扩展中国剩余定理脚本（恢复密文c）

1.题目

from Crypto.Util.number import *
import random
# from secret import flag
flag=''
table='abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
pad=100-len(flag)
for i in range(pad):flag+=random.choice(table).encode()
e=343284449
m=bytes_to_long(flag)
assert m>(1<<512)
assert m<(1<<1024)
p=getPrime(512)
q=getPrime(512)
r=getPrime(512)
print('p=',p)
print('q=',q)
print('r=',r)
n1=p*q
n2=q*r
c1=pow(m,e,n1)
c2=pow(m,e,n2)
print('c1=',c1)
print('c2=',c2)p= 11820891196647569262137841192985418014377132106496147254821784946481523526822939129065042819464351666077658751406165276121125571355594004514547517855730743
q= 10450390015864176713581330969519712299844487112687677452105216477861582967322473997670559995588440097951786576039009337782247912476227937589298529580432797
r= 9484954066160968219229920429258150817546418633451929876581842443665029377287119340232501682142185708534413073877473741393278935479791561681402673403009771c1= 69574855207460025252857869494766338442370688922127811393280455950372371842144946699073877876005649281006116543528211809466226185922844601714337317797534664683681334132261584497953105754257846471069875622054326463757746293958069752489458646460121725019594141157667480846709081917530190233900184428943585065316
c2= 66183492015178047844987766781469734325646160179923242098082430373061510938987908656007752256556018402101435698352339429316390909525615464024332856855411414576031970267795270882896721069952171988506477519737923165566896609181813523905810373359029413963666924039857159685161563252396502381297700252749204993228# e是q-1的因子

2.解题思路

前面大致看一下，就随机从 table中选择的字母把flag填充到100字节长度然后转换成长整数m.

重要信息是：

n1=p*q
n2=q*r
c1=pow(m,e,n1)
c2=pow(m,e,n2)

我们可以通过解这个同余方程组来恢复c:（转扩展中国剩余定理（ExCRT）-CSDN博客）

gcd(n1,n2)=q

由CRT合并后得到x=m^e mod (lcm(n1,n2))即x=m^e mod(p*q*r)不就是c吗

直接套扩展中国剩余定理脚本求出c,再进行正常的rsa求解（在这个过程中q没有直接用于解密，n=pr）

3.脚本

先求出c:

p= 11820891196647569262137841192985418014377132106496147254821784946481523526822939129065042819464351666077658751406165276121125571355594004514547517855730743
q= 10450390015864176713581330969519712299844487112687677452105216477861582967322473997670559995588440097951786576039009337782247912476227937589298529580432797
r= 9484954066160968219229920429258150817546418633451929876581842443665029377287119340232501682142185708534413073877473741393278935479791561681402673403009771
n1=p*q
n2=q*r
#print(n1)
#print(n2)
#123532923340062498196987596321158778953792410828984481020115457263717668204473703015542790129153489530621245935519745815888671340181570426743315007214814995259450485202769218431488347959428261030109200094413998290111042600270343912239267830450410094909181939564200869305441814656652376159995048386284638378171
#99121469273938908094337559030886762245366008335524496490212577254038642294316299795376895228431188701683790748101815366283781320808991079605856804571942415812705959110308025365792393315242314372015543762383660712225873022827021182760217750969535414533002246962138257379447348529580050968085829513328599859487
import gmpy2
from Crypto.Util.number import *
"""扩展欧几里得"""
def exgcd(a, b):if 0 == b:return 1, 0, ax, y, q = exgcd(b, a % b)x, y = y, (x - a // b * y)return x, y, q"""扩展中国剩余定理"""def CRT(n, a, m):if n == 1:return a[0], m[0]for i in range(1, n):x, y, d = exgcd(m[0], m[i])if (a[i] - a[0]) % d != 0:return -1, -1t = m[i] // dx = (a[i] - a[0]) // d * x % ta[0] = x * m[0] + a[0]m[0] = m[0] * m[i] // da[0] = (a[0] % m[0] + m[0]) % m[0]return a[0], m[0]
c1= 69574855207460025252857869494766338442370688922127811393280455950372371842144946699073877876005649281006116543528211809466226185922844601714337317797534664683681334132261584497953105754257846471069875622054326463757746293958069752489458646460121725019594141157667480846709081917530190233900184428943585065316
c2= 66183492015178047844987766781469734325646160179923242098082430373061510938987908656007752256556018402101435698352339429316390909525615464024332856855411414576031970267795270882896721069952171988506477519737923165566896609181813523905810373359029413963666924039857159685161563252396502381297700252749204993228# 假设的题目数据（具体根据题目来改变）
n = 2# 同余方程个数
m = [123532923340062498196987596321158778953792410828984481020115457263717668204473703015542790129153489530621245935519745815888671340181570426743315007214814995259450485202769218431488347959428261030109200094413998290111042600270343912239267830450410094909181939564200869305441814656652376159995048386284638378171,99121469273938908094337559030886762245366008335524496490212577254038642294316299795376895228431188701683790748101815366283781320808991079605856804571942415812705959110308025365792393315242314372015543762383660712225873022827021182760217750969535414533002246962138257379447348529580050968085829513328599859487]# 模数
a = [69574855207460025252857869494766338442370688922127811393280455950372371842144946699073877876005649281006116543528211809466226185922844601714337317797534664683681334132261584497953105754257846471069875622054326463757746293958069752489458646460121725019594141157667480846709081917530190233900184428943585065316,66183492015178047844987766781469734325646160179923242098082430373061510938987908656007752256556018402101435698352339429316390909525615464024332856855411414576031970267795270882896721069952171988506477519737923165566896609181813523905810373359029413963666924039857159685161563252396502381297700252749204993228]# 余数# 使用CRT求解基础解和模数
x0, mod = CRT(n, a, m)
print(x0)

再求m:

import libnum
c=1051311603595400257980451542641726560928968569258042231276292652088507209347204465348483100080899623360705698249443255030368048979130482813052608650445300611553758759647722097778171873596181791974080589234136090632966294575063306439633769753905530026312180583106024810580642209905594594119077985110929675466498207370604560182924468112540068499274911327513697378581931822685826876372554425845071592347470781982215295908151280216722253883169708944885906780090210923
p= 11820891196647569262137841192985418014377132106496147254821784946481523526822939129065042819464351666077658751406165276121125571355594004514547517855730743
q= 10450390015864176713581330969519712299844487112687677452105216477861582967322473997670559995588440097951786576039009337782247912476227937589298529580432797
r= 9484954066160968219229920429258150817546418633451929876581842443665029377287119340232501682142185708534413073877473741393278935479791561681402673403009771
e=343284449
n=p*r
phi=(p-1)*(r-1)
d=libnum.invmod(e,phi)
m=pow(c,d,n)
print(libnum.n2s(m))
#b'moectf{Th1s_iS_Chinese_rEm41nDeR_The0rEm_CRT!}YWMZSTyfRvhjTCJuQCwALQBcWHFCgTDIZWJaxRUzBPCmFOnbDTRBau'