rsa

点击此处获得更好的阅读体验

---

题目考点

• RSA加密

解题过程

目是一个RSA加密，已知n,e,dp,c,求m,推理过程可以参考RSA之拒绝套路(1)

dp的意思为：dp≡d mod (p−1)

故此可以得到k2∗(p−1)∗(q−1)+1=k1∗(p−1)+dp∗ek2∗(p−1)∗(q−1)+1=k1∗(p−1)+dp∗e

变换一下(p−1)∗[k2∗(q−1)−k1]+1=dp∗e(p−1)∗[k2∗(q−1)−k1]+1=dp∗e

因为dp<p−1dp<p−1可以得到e>k2∗(q−1)−k1e>k2∗(q−1)−k1

我们假设x=k2∗(q−1)−k1x=k2∗(q−1)−k1可以得到x的范围为 (0,e)(0,e)

因此有 x∗(p−1)+1=dp∗ex∗(p−1)+1=dp∗e

那么我们可以遍历 x∈(0,e)x∈(0,e)求出p-1，求的方法也很简单，遍历65537种可能

其中肯定有一个p可以被n整除那么求出p和q

即可利用 ϕ(n)=(p−1)∗(q−1)d∗e≡1 mod ϕ(n)ϕ(n)=(p−1)∗(q−1)d∗e≡1 mod ϕ(n)

推出d≡1∗e−1 mod ϕ(n)d≡1∗e−1 mod ϕ(n)

import gmpy2
import libnum
n = 22000596569856085362623019573995240143720890380678581299411213688857584612953014122879995808816872221032805734151343458921719334360194024890377075521680399678533655114261000716106870610083356478621445541840124447459943322577740268407217950081217130055057926816065068275999620502766866379465521042298370686053823448099778572878765782711260673185703889168702746195779250373642505375725925213796848495518878490786035363094086520257020021547827073768598600151928787434153003675096254792245014217044607440890694190989162318846104385311646123343795149489946251221774030484424581846841141819601874562109228016707364220840611
e = 65537
dp = 84373069210173690047629226878686144017052129353931011112880892379361035492516066159394115482289291025932915787077633999791002846189004408043685986856359812230222233165493645074459765748901898518115384084258143483508823079115319711227124403284267559950883054402576935436305927705016459382628196407373896831725
c = 14874271064669918581178066047207495551570421575260298116038863877424499500626920855863261194264169850678206604144314318171829367575688726593323863145664241189167820996601561389159819873734368810449011761054668595565217970516125181240869998009561140277444653698278073509852288720276008438965069627886972839146199102497874818473454932012374251932864118784065064885987416408142362577322906063320726241313252172382519793691513360909796645028353257317044086708114163313328952830378067342164675055195428728335222242094290731292113709866489975077052604333805889421889967835433026770417624703011718120347415460385182429795735
for i in range(1,65538):
    if (dp*e-1)%i == 0:
        if n%(((dp*e-1)/i)+1)==0:
            p=((dp*e-1)/i)+1
            q=n/(((dp*e-1)/i)+1)
            phi = (p-1)*(q-1)
            d = gmpy2.invert(e,phi)%phi
            print libnum.n2s(pow(c,d,n))

FLAG

flag{d90a4bb43f64275794522dffdb4bd78b}