没 e 也能玩

题目如下：

python

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

p = getPrime(1024)
q = getPrime(1024)
d = inverse(65537,(p-1)*(q-1))
dp = d % (p-1)
dq = d % (q-1)
print(f'c={pow(bytes_to_long(flag),e,p*q)}')
print(f'p={p}')
print(f'q={q}')
print(f'dp={dp}')
print(f'dq={dq}')

''''
c=312026920216195772014255984174463085443866592575942633449581804171108045852080517840578408476885673600123673447592477875543106559822653280458539889975125069364584140981069913341705738633426978886491359036285144974311751490792757751756044409664421663980721578870582548395096887840688928684149014816557276765747135567714257184475027270111822159712532338590457693333403200971556224662094381891648467959054115723744963414673861964744567056823925630723343002325605154661959863849738333074326769879861280895388423162444746726568892877802824353858845944856881876742211956986853244518521508714633279380808950337611574412909
p=108043725609186781791705090463399988837848128384507136697546885182257613493145758848215714322999196482303958182639388180063206708575175264502030010971971799850889123915580518613554382722069874295016841596099030496486069157061211091761273568631799006187376088457421848367280401857536410610375012371577177832001
q=121590551121540247114817509966135120751936084528211093275386628666641298457070126234836053337681325952068673362753408092990553364818851439157868686131416391201519794244659155411228907897025948436021990520853498462677797392855335364006924106615008646396883330251028071418465977013680888333091554558623089051503
dp=11282958604593959665264348980446305500804623200078838572989469798546944577064705030092746827389207634235443944672230537015008113180165395276742807804632116181385860873677969229460704569172318227491268503039531329141563655811632035522134920788501646372986281785901019732756566066694831838769040155501078857473
dq=46575357360806054039250786123714177813397065260787208532360436486982363496441528434309234218672688812437737096579970959403617066243685956461527617935564293219447837324227893212131933165188205281564552085623483305721400518031651417947568896538797580895484369480168587284879837144688420597737619751280559493857
'''

从题目中已知条件有 $c$ 、 $p$ 、 $q$ 、 $d_{p}$ 、 $d_{q}$ ，其中 $d_{p}$ 和 $d_{q}$ 由以下公式计算：

\begin{matrix} d_{p} = d \mod (p - 1) \\ d_{q} = d \mod (q - 1) \end{matrix}

我们知道RSA解密的时候 $m \equiv c^{d} (\mod n)$ ，即 $m = c^{d} + k \times n$ ，又 $n = p \times q$

所以 $m = c^{d} + k \times p \times q$ ，两边对 $p$ 和 $q$ 同时取余，得

\begin{matrix} m_{1} \equiv c^{d} (\mod p) (1) \\ m_{2} \equiv c^{d} (\mod q) (2) \end{matrix}

由最开始计算 $d_{p}$ 和 $d_{q}$ 的的式子可以假设存在 $k_{1}$ 和 $k_{2}$ 使得

\begin{matrix} d = d_{p} + k_{1} \times (p - 1) \\ d = d_{q} + k_{2} \times (q - 1) \end{matrix}

由费马小定理（对于任意素数 $p$ 和整数 $a \in Z_{p}$ ，都有 $a^{p} \equiv a (\mod p)$ ），和 $(1)$ 式，可得

m_{1} \equiv c^{d_{p} + k_{1} \times (p - 1)} \equiv c^{d_{p}} \times (c^{k_{1}})^{p - 1} \equiv c^{d_{p}} (\mod p)

$m_{2}$ 同理，所以

\begin{matrix} m_{1} \equiv c^{d_{p}} (\mod p) (3) \\ m_{2} \equiv c^{d_{q}} (\mod q) (4) \end{matrix}

由 $(1)$ 可得 $m_{1} + x \times p = c^{d}$ ，将其代入 $(2)$ 式可得

x \times p \equiv (m_{2} - m_{1}) (\mod q) (5)

因为 $\gcd (p, q) = 1$ ，所以存在 $p^{'}$ 使得

p \times p^{'} \equiv 1 (\mod q)

给 $(5)$ 式两边同乘 $p^{'}$ ，有

x \equiv p^{'} (m_{2} - m_{1}) (\mod q) (6)

将 $(6)$ 式代入 $m_{1} + x \times p = c^{d}$ ，可得

m_{1} + p \times [p^{'} (m_{2} - m_{1}) \mod q] = c^{d}

即

c^{d} = m_{1} + p \times [p^{'} (m_{2} - m_{1}) \mod q]

$m_{1}$ 和 $m_{2}$ 可以通过 $(3)$ 式和 $(4)$ 式得到，这样代进上述式子就可以解出 $m$ .

题解如下：

python

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

c = 312026920216195772014255984174463085443866592575942633449581804171108045852080517840578408476885673600123673447592477875543106559822653280458539889975125069364584140981069913341705738633426978886491359036285144974311751490792757751756044409664421663980721578870582548395096887840688928684149014816557276765747135567714257184475027270111822159712532338590457693333403200971556224662094381891648467959054115723744963414673861964744567056823925630723343002325605154661959863849738333074326769879861280895388423162444746726568892877802824353858845944856881876742211956986853244518521508714633279380808950337611574412909
p = 108043725609186781791705090463399988837848128384507136697546885182257613493145758848215714322999196482303958182639388180063206708575175264502030010971971799850889123915580518613554382722069874295016841596099030496486069157061211091761273568631799006187376088457421848367280401857536410610375012371577177832001
q = 121590551121540247114817509966135120751936084528211093275386628666641298457070126234836053337681325952068673362753408092990553364818851439157868686131416391201519794244659155411228907897025948436021990520853498462677797392855335364006924106615008646396883330251028071418465977013680888333091554558623089051503
dp = 11282958604593959665264348980446305500804623200078838572989469798546944577064705030092746827389207634235443944672230537015008113180165395276742807804632116181385860873677969229460704569172318227491268503039531329141563655811632035522134920788501646372986281785901019732756566066694831838769040155501078857473
dq = 46575357360806054039250786123714177813397065260787208532360436486982363496441528434309234218672688812437737096579970959403617066243685956461527617935564293219447837324227893212131933165188205281564552085623483305721400518031651417947568896538797580895484369480168587284879837144688420597737619751280559493857


def rsa(dp, dq, p, q, c):
    m1 = pow(c, dp, p)
    m2 = pow(c, dq, q)
    p_q = invert(p, q)
    m = m1 + p_q * ((m2-m1) % q) * p
    print(long_to_bytes(m))


rsa(dp, dq, p, q, c)
# flag{No_course_e_can_play}

没 e 也能玩 ​

没 e 也能玩