{"id":442,"date":"2026-07-01T21:18:47","date_gmt":"2026-07-01T13:18:47","guid":{"rendered":"https:\/\/blog.lmoon.cn\/?p=442"},"modified":"2026-07-04T10:27:00","modified_gmt":"2026-07-04T02:27:00","slug":"rsa%e4%ba%8c%e7%bb%83%e4%b9%a0","status":"publish","type":"post","link":"https:\/\/blog.lmoon.cn\/index.php\/2026\/07\/01\/rsa%e4%ba%8c%e7%bb%83%e4%b9%a0\/","title":{"rendered":"RSA(\u4e8c)\u7ec3\u4e60"},"content":{"rendered":"\n

e\u5f88\u5927\u7684dp\u6cc4\u9732\u653b\u51fb<\/strong><\/h2>\n\n\n\n

\u9644\u4ef6\u5982\u4e0b<\/p>\n\n\n\n

from Crypto.Util.number import *\n\nflag = b'NSSCTF{******}' + b'1'*80\n\np = getPrime\u200b\u200b(512)\nq = getPrime\u200b\u200b(512)\n\nn = p*q\ne = getPrime\u200b\u200b(128)\nd = inverse\u200b\u200b(e, \u200b\u200b(p-1)*\u200b\u200b(q-1))\n\ndp = d % \u200b\u200b(p-1)\n\nm = bytes_to_long\u200b\u200b(flag)\n\nc = pow\u200b\u200b(m, e, n)\n\nprint\u200b\u200b(f'n = {n}')\nprint\u200b\u200b(f'e = {e}')\nprint\u200b\u200b(f'c = {c}')\nprint\u200b\u200b(f'dp = {dp}')\n\n'''\nn = 108280026722298796068968170303156759745471686664814404724171434502249429011870583595808692893118419248225924869164875379709992190884930717654004006466664403479467573176438601715156464950045121937338569942817256182277141174728470067308962244296992229214749863655518517510026063088263849891990324547823192559069\ne = 305691242207901867366357529364270390903\nc = 26537258289122728220745496185201994733321402056894636636642710319261241111675937946139938310952968353253866895253865273981912174303818938005932883052177988834834575591342856235464380238486868448329727891268391728758132913642966389278296932186703733187105516710825918064228397602264185334108934765627411913661\ndp = 2656631506624565349527023729530989647164022271235521672257622068579788839123502046687139927161669209201953909023994372208117081512139181611949631467292513\n'''<\/code><\/pre>\n\n\n\n
\u6211\u4eec\u77e5\u9053dp*e =  1mod\u200b\u200b(p-1) => dp * e =k\u200b\u200b(p-1) +1<\/p>\n\n\n\n
\u4e5f\u5c31\u662f\u8bf4\u5982\u679c\u6211\u4eec\u53ef\u4ee5\u6784\u9020\u51fa\u4e00\u4e2a\u5f0f\u5b50\u4f7f\u5176\u6c42\u51fa\u6765\u7684\u89e3\u4e3akp\u6216\u8005k,\u90a3\u4e48\u6211\u4eec\u5c31\u53ef\u4ee5\u5229\u7528gcd\u6765\u6c42\u51fap.\u6211\u4eec\u53d1\u73b0\u5982\u679c\u5c06\u5176\u8fdb\u884c\u6a21p\u8fd0\u7b97\u4f1a\u53d1\u73b0\u5176\u7ed3\u679c\u4e3aa\uff0c\u540c\u65f6\u4e5f\u6784\u6210\u4e86kp<\/p>\n\n\n\n
\u8fd9\u4e2a\u662f\u65f6\u5019\u8fdb\u884c\u6784\u9020\\\\\n\u4ee4gcd(a,p)=1,\u5219\n\u4e00\u4e2a\u5f0f\u5b50a^{dp*e}mod(p) \\  ==>\\\\\na^{k(p-1)+1} mod(p)==>a^{kp-1}+a mod(p) ==> a  \\ mod(p)\\\\\n\\\\\u6709\u8d39\u9a6c\u5c0f\u5b9a\u7406\u5f97\u5230a^{p-1} \\equiv \\ 1 \\ mod(p) == >  \\ \\   a^{dp*e} =  a^{k(p-1)+1}  \\equiv \\ 1^{k}*a\\ mod(p) \\\\\nkp=a^{dp}-a<\/pre><\/div>\n\n\n\n
\u4ee3\u7801\u5982\u4e0b<\/p>\n\n\n\n
from Crypto.Util.number import long_to_bytes\nfrom gmpy2 import *\nn = 108280026722298796068968170303156759745471686664814404724171434502249429011870583595808692893118419248225924869164875379709992190884930717654004006466664403479467573176438601715156464950045121937338569942817256182277141174728470067308962244296992229214749863655518517510026063088263849891990324547823192559069\ne = 305691242207901867366357529364270390903\nc = 26537258289122728220745496185201994733321402056894636636642710319261241111675937946139938310952968353253866895253865273981912174303818938005932883052177988834834575591342856235464380238486868448329727891268391728758132913642966389278296932186703733187105516710825918064228397602264185334108934765627411913661\ndp = 2656631506624565349527023729530989647164022271235521672257622068579788839123502046687139927161669209201953909023994372208117081512139181611949631467292513\nk=1\na=2\np=gcd\u200b\u200b(powmod\u200b\u200b(a,dp*e,n)-a,n)\nq=n\/\/p\nprint\u200b\u200b(p*q==n)\nphi=\u200b\u200b(p-1)*\u200b\u200b(q-1)\nprint\u200b\u200b(gcd\u200b\u200b(e,phi))\nd=invert\u200b\u200b(e,phi)\nm=powmod\u200b\u200b(c,d,n)\nprint\u200b\u200b(long_to_bytes\u200b\u200b(m))<\/code><\/pre>\n\n\n\n
\"image-20260629111316885\"\/<\/div><\/figure>\n\n\n\n
NSSCTF{p_leak_but_with_huge_e}<\/code><\/pre>\n\n\n\n
d\u6cc4\u9732\u653b\u51fb<\/h2>\n\n\n\n
\u9898\u76ee\u5982\u4e0b<\/p>\n\n\n\n
from Crypto.Util.number import *\nfrom gmpy2 import *\n\np = getPrime\u200b\u200b(512)\nq = getPrime\u200b\u200b(512)\n\nass\u200b\u200bert p < q\n\nn = p*q\ne = 65537\nphi = \u200b\u200b(p-1)*\u200b\u200b(q-1)\nd = invert\u200b\u200b(e, phi)\n\nprint\u200b\u200b(f'n = {n}')\nprint\u200b\u200b(f'd = {d}')\nprint\u200b\u200b('flag is NSSCTF{md5\u200b\u200b(p)}')\n\n'''\nn = 113917408220469425995764932761465306974540330325378601642830241920567032775895088098706711486764203845425248022960733155994427766750033219106642310531864450654102562104771892268897793145789045570107312401570269581223945259704851104645493075550316424129401227653740942495625720165869565257394427181127734628103\nd = 15762135247924329080208071933121250646888501386858311483546464344350547831176536290630826247188272280853810047335214127264865205744683174860903496832368687060941437002920094364116706593296591581117381565805322046922482804679245558495134876677733584718947309975077159564300049936769192724856722338627154192353\nflag is NSSCTF{md5\u200b\u200b(p)}\n'''<\/code><\/pre>\n\n\n\n
\u9898\u76ee\u4e2d\u5f97\u77e5\u6211\u4eec\u9700\u8981\u6c42\u89e3\u7684\u662fp\uff0c\u5e76\u4e14\u6211\u4eec\u4ee5\u77e5dne\u6c42\u89e3q<\/p>\n\n\n\n
d=\nn=\ne=<\/code><\/pre>\n\n\n\n
\u6839\u636e\u4e4b\u524d\u7684\u7ec3\u4e60\u53ef\u4ee5\u63a8\u65ad\u51fa d *e  = 1 mod\u200b\u200b(phi)\uff0c\u65e2\u7136n=p * q.\u7136\u540e\u8fd9\u4e2a\u5f0f\u5b50\u80fd\u4e0d\u80fd\u627e\u5230\u4e0en\u7684\u5173\u7cfb\u5982\u4e0b<\/p>\n\n\n\n
phi=(p-1)*(q-1)\\\\\nd * e = 1\\ \\ mod(phi)\n\\\\\u4ee4 r=de-1\\\\\nr=k*(p-1)*(q-1)\n\\\\\u53d6\u4e00\u4e2a\u6570a,\u6761\u4ef6\u5f0fgcd(a,p,q)=1\\\\\na^{r}mod(p)=\\ a^{k(p-1)(q-1)}\\\\\n\u7531\u8d39\u9a6c\u5c0f\u5b9a\u7406\u5f97\u5230 a^{p-1} \\equiv 1 \\mod(p) \u548ca^{q-1} \\equiv 1\\ mod(q)\n\\\\\u6240\u4ee5\u53ef\u4ee5\u5f97\u5230\na^{r} \\equiv 1  \\ mod(p) \\ \\ \\ a^{r} \\equiv 1 \\ mod(q) \\\\\n\u5229\u7528CRT\u6216\u8005\u5f0f\u540c\u4e8e\u53ef\u4ee5\u5f97\u5230a^{r} \\equiv 1 \\ mod(n)<\/pre><\/div>\n\n\n\n
\u7136\u540e\u5f97\u5230\u8fd9\u4e2a\u4e4b\u540e\u3002\u6211\u4eec\u4ee4\u5176r=2^s*t.<\/p>\n\n\n\n
\u7136\u540e\u8ba1\u7b97\u51fas,t\u7684\u503c\u3002\u8fd9\u4e2a\u65f6\u5019\u6211\u4eec\u5c31\u53ef\u4ee5\u5229\u7528\u8fd9\u4e2as,t\u6765\u8fdb\u884c\u8fd8\u539fr\u7684\u503c\u4e86\u3002\u56e0\u4e3a\u6211\u4eec\u9009\u53d6\u7684\u662f2^s+t\u7684\u503c\uff0c\u90a3\u4e48\u5176\u8fd8\u539f\u7684\u8fc7\u7a0b\u5982\u4e0b<\/p>\n\n\n\n
x=a^{t}\\ \\ mod(n)\\\\\nx_1=x^{2}=a^{2^1*b}\\ \\ mod(n)\\\\\nx_2=x1^{2}=a^{2^2*b}\\ \\ mod(n)\\\\\nx_{i+1}=x_i^{2}\\ \\ mod(n)\\\\\n\\\\\\\n\\\\\\\nx_{s-1} =a^{2^{s-1}*t}\\ \\ mod(n)\\\\\n\u6700\u540e\u5f97\u5230\n\\\\x_s=a^{2^s*t}=a^{ed-1} \\ \\ mod(n) \\equiv 1<\/pre><\/div>\n\n\n\n
\u6709\u6700\u540e\u4e00\u6b65\u6211\u4eec\u53ef\u4ee5\u77e5\u9053 X_s-1^2 = 1 mod\u200b\u200b(n)<\/strong>,\u90a3\u4e48\u6211\u4eec\u5c31\u53ef\u4ee5\u5229\u7528\u5176\u975e\u5e73\u51e1\u6839\u6765\u8fdb\u884c\u6c42\u89e3p,\u6216\u8005q.<\/p>\n\n\n\n
p=gcd\u200b\u200b(X-1,n)\u6216\u8005\u662fq=gcd\u200b\u200b(x+1,n)<\/code><\/pre>\n\n\n\n
\u4e3a\u4ec0\u4e48X_s-1^2 = 1 mod\u200b\u200b(n)\u53ef\u4ee5\u5f97\u5230p,q\u7684\u500d\u6570\u7136\u540e\u4e0en\u8fdb\u884c\u6c42\u89e3<\/p>\n\n\n\n
\u4e0b\u9762\u4e3a\u4e86\u65b9\u4fbf\u6211\u7528x\u6765\u8fdb\u884c\u4ee3\u66ff\\\\\nx^{2} \\equiv \\ 1 \\ mod(n) \\\\\n(x-1)*(x+1) \\equiv \\ 0 \\ mod(n)\\\\\n\u56e0\u4e3a\u6c42\u89e3\u7684\u662fp,q\uff0c\u6240\u4ee5\u6211\u4eec\u8981\u5bf9n\u8fdb\u884c\u62c6\u5206\u6210 p,q\\\\\n(x-1)*(x+1) \\equiv \\ 0 \\mod(p) \\\\\n\u5f97\u5230\u4e24\u4e2a\u63a5 x=1 , x=-1\\\\\n\u540c\u7406\u5728\u6a21q\u4e0b\u4e5f\u4f1a\u6709\u4e24\u4e2a\u89e3x=1,x=-1\\\\\n\u7ec4\u5408\u4e00\u8d77\u5c31\u662f\n(1 mod(q),1 mod(p))\\\\\n(-1 mod(q),-1 mod(p))\\\\\n(1 mod(q),-1 mod(p))\\\\\n(-1 mod(q),1 mod(p))\\\\<\/pre><\/div>\n\n\n\n
\u7136\u540e\u56e0\u4e3a\u6211\u4eec\u8981\u627e\u7684\u662f\u975e\u5e73\u51e1\u56e0\u5b50\uff0c\u524d\u4e24\u4e2a\u662f\u5e73\u51e1\u56e0\u5b50\u3002\u6240\u4ee5\u6211\u4eec\u4f7f\u7528\u540e\u9762\u4e24\u4e2a\u8fdb\u884c\u8fd0\u7b97\u6240\u4ee5<\/p>\n\n\n\n
x \\ = 1 \\mod(q),\\ \\ \\ x\\equiv-1\\mod(p) ==>\\\\\nx-1 \\ = 0 \\mod(q),\\ \\ \\ x+1 \\equiv \\ 0 \\mod(p)\n\\\\\n\u5269\u4e0b\u7684\u4e00\u4e2a\u540c\u7406\uff0c\u7136\u540e\u4f60\u4f1a\u53d1\u73b0\u5f97\u5230\u7684x-1\u5bf9\u5e94\u7684\u503c\u6709\u4e24\u4e2a\u53ef\u80fd\u662fq\uff0c\u4e5f\u80af\u80fd\u662fp.<\/pre><\/div>\n\n\n\n
import math\nimport hashlib\nfrom gmpy2 import gmpy2\nn = 113917408220469425995764932761465306974540330325378601642830241920567032775895088098706711486764203845425248022960733155994427766750033219106642310531864450654102562104771892268897793145789045570107312401570269581223945259704851104645493075550316424129401227653740942495625720165869565257394427181127734628103\nd = 15762135247924329080208071933121250646888501386858311483546464344350547831176536290630826247188272280853810047335214127264865205744683174860903496832368687060941437002920094364116706593296591581117381565805322046922482804679245558495134876677733584718947309975077159564300049936769192724856722338627154192353\ne = 65537\na=e*d-1\ns=0\nb=0\nwhile a%2==0:\n    s+=1\n    a=a\/\/2\n    b = a % 2\nr=a\na=2\nx=pow\u200b\u200b(a,r,n)\ni=0\nfor _ in range\u200b\u200b(s):\n    i+=1\n    y=pow\u200b\u200b(x,2,n)\n    if y==1 and x!=1 and x!=n-1:\n        p=math.gcd\u200b\u200b(x+1,n)\n        q=n\/\/p\n        p=min\u200b\u200b(p,q)\n        print\u200b\u200b('NSSCTF{%s}' % hashlib.md5\u200b\u200b(str\u200b\u200b(p).encode\u200b\u200b()).hexdigest\u200b\u200b())\n        print\u200b\u200b(i)\n        break\n    x = y<\/code><\/pre>\n\n\n\n
wiener<\/h2>\n\n\n\n
\u9898\u76ee\u7c7b\u578b\u4e00\u822c\u4e3ad\u5f88\u5927\u7136\u540e\u53ef\u4ee5\u5229\u7528\u6e10\u5206\u6570\u6765\u83b7\u5f97\u5176\u4e2d\u6240\u6709\u8fd1\u4f3c\u7684\u503c\uff0c\u7136\u540e\u8fdb\u884c\u5bfb\u627e\u5176\u4e2d\u7684\u5bf9\u5e94\u7684d\u7684\u503c<\/p>\n\n\n\n
\u9898\u76ee\u5982\u4e0b<\/p>\n\n\n\n
from Crypto.Util.number import *\nfrom gmpy2 import *\n\nflag = b'NSSCTF{******}'\n\np = getPrime\u200b\u200b(256)\nq = getPrime\u200b\u200b(256)\n\nn = p*q\nd = getPrime\u200b\u200b(128)\ne = inverse\u200b\u200b(d, \u200b\u200b(p-1)*\u200b\u200b(q-1))\nm = bytes_to_long\u200b\u200b(flag)\n\nc = powmod\u200b\u200b(m, e, n)\n\nprint\u200b\u200b(f'n = {n}')\nprint\u200b\u200b(f'e = {e}')\nprint\u200b\u200b(f'c = {c}')\n\n'''\nn = 6969872410035233098344189258766624225446081814953480897731644163180991292913719910322241873463164232700368119465476508174863062276659958418657253738005689\ne = 3331016607237504021038095412236348385663413736904453330557803644384818257225138777641344877202234881627514102078530507171735156112302207979925588113589669\nc = 1754994938947260364311041300467524420957926989584983693004487724099773647229373820465164193428679197813476633649362998772470084452129370353136199193923837\n'''<\/code><\/pre>\n\n\n\n
\u6839\u636e\u6b27\u62c9\u6cd5\u5219\u6211\u4eec\u53ef\u4ee5\u5f97\u5230<\/p>\n\n\n\n
e*d \\equiv \\ 1  \\ mod(n) \\\\\ne*d-1 = k*n \\ => \\ \u8fd1\u4f3c\u4e8e \\ ed=k*n \\ =>\u5f97\u5230\n\\\\ \\frac{e}{n} \\  = \\ \\frac{k}{d}<\/pre><\/div>\n\n\n\n
\u7136\u540e\u5728\u6211\u4eec\u5f97\u5230d\u7684\u5019\u9009\u8005\u7684\u60c5\u51b5\u4e0b\u6211\u4eec\u53ef\u4ee5\u5229\u7528<\/p>\n\n\n\n
phi=(p-1)*(q-1)=n-q-p+1\\\\\np+q=n+1-phi\\\\\ns=p+q \\ \\ \\ \\ n=p*q\\\\\u5219\u6211\u4eec\u53ef\u4ee5\u6784\u9020\\\\\nx^2 - s*x + n = 0\\\\\n\u7136\u540e\u5229\u7528\u6839\u7684\u5224\u522b\u5f0f\u8fdb\u884c\u6765\u8fdb\u884c\u7b5b\u9009,\u4ee4s=p+q\\\\\ndelta =s^2 - 4n\\\\\ndelta=delta = (p + q)^2 - 4pq=\u300bdelta = p^2 + 2pq + q^2 - 4pq=>delta = p^2 - 2pq + q^2==>\\\\\ndelta = (p - q)^2<\/pre><\/div>\n\n\n\n
\u90a3\u4e48\u7740\u8868\u660edata\u7684\u503c\u4e00\u5b9a\u4e3a\u5b8c\u5168\u5e73\u65b9\u6570\u3002\u5230\u8fd9\u91cc\u6574\u4f53\u7684\u89e3\u9898\u601d\u8def\u5c31\u6ca1\u6709\u4e86\u63a5\u4e0b\u6765\u5c31\u662f\u6765\u8fdb\u884c\u8bb2\u89e3\u5982\u4f55\u83b7\u53d6\u5019\u9009d\u4e86<\/p>\n\n\n\n
\u5728\u5f62\u5f0f\u4e0a\u6e10\u5206\u6570\u5c31\u662f\u5c06\u4e00\u4e2a\u5206\u6570\u62c6\u89e3\u6210\u5e26\u5206\u6570\u7684\u5f62\u5f0f\uff0c\u6700\u540e\u8ba9\u5176\u4ee5\u6574\u6570\u7ed3\u5c3e\u65b9\u4fbf\u8fdb\u884c\u8fd0\u7b97\u5176\u903b\u8f91\u5982\u4e0b<\/p>\n\n\n\n
\u73b0\u5728\u5bf9\u5176\\frac{415}{93}\u8fdb\u884c\u6e10\u5206\u6570\u62c6\u89e3\\\\\n\u5176\u601d\u8def\u5c31\u662f\u5148\u5bf9\u5176\u8fdb\u884c\u5206\u5b50\u5206\u6bcd\u53cd\u8f6c\uff0c\u7136\u540e\u8fdb\u884c\u5316\u7b80\u8ba9\u5176\u5206\u6bcd<1\uff0c\u7136\u540e\u7ee7\u7eed\u5316\u7b80\u76f4\u5230\u53cd\u8f6c\u4e4b\u540e\u4e3a\u6574\u6570\\\\\n\\frac{415}{93}=4+\\frac{1}{2+\\frac{1}{6+\\frac{1}{7}}}<\/pre><\/div>\n\n\n\n
\u5176\u4e2d\u6211\u4eec\u8fdb\u884c\u6bcf\u4e00\u4e2a\u8f6e\u7684\u503c\u90fd\u662f\u6211\u4eec\u7684\u5019\u9009d\uff0c\u7531\u4e8e\u5728\u4ee3\u7801\u4e2d\u4e3a\u4e86\u65b9\u4fbf\u8fdb\u884c\u7f16\u5199\u6211\u4eec\u91c7\u7528\u5206\u5e03\u8ba1\u7b97\u7684\u5f62\u5f0f\u3002\u5148\u5bf9\u5176\u8fdb\u884c\u63d0\u53d6\u8fd0\u7b97\u4e4b\u540e\u7684\u6574\u6570\u4e5f\u5c31\u662f[4,2,6,7].\u7136\u540e\u6211\u4eec\u5c06\u5176\u8fdb\u884c\u8fd8\u539f\u6bcf\u4e00\u6b65\u7684\u503c\uff0c\u8fd9\u91cc\u5728\u8fd0\u7b97\u7684\u65f6\u5019\u6709\u4e00\u4e2a\u5730\u63a8\u516c\u5f0f\u5176\u8bc1\u660e\u5982\u4e0b\uff1a<\/p>\n\n\n\n
\u73b0\u5728\u6211\u4eec\u77e5\u9053\u524d\u4e24\u7ec4\u7684\u503c\u4e3a[4,2,x]\\\\\n\u6211\u4eec\u53ef\u4ee5\u8fd0\u7b97\u5f97\u5230\u62a2\u4e24\u4e2a\u503c\u4e3a4\u548c\\frac{9}{2}\\\\\n\u5bf9\u4e8e\u7b2c\u4e09\u4e2ax\u5bf9\u5e94\u7684\u503c\u4e3a\\\\\n4 + \\frac1 {(2 + \\frac1{x})}\\\\\n4+\\frac{1}{\\frac{2x+1}{x}}=>4+\\frac{x}{2x+1}\\\\\n\\frac{9x+4}{2x+1}\\\\\n\u5bf9\u4e8e\u5206\u5b50\u4e3ax*\u4e0a\u4e00\u4e2a\u7684\u5206\u5b50+\u4e0a\u4e0a\u4e2a\u7684\u5206\u5b50\\ \\ \u5206\u6bcd\u540c\u7406\\\\\nx_i=\\frac{h_{i-1}x+h_{i-2}}{k_{i-1}x+k_{i-2}}<\/pre><\/div>\n\n\n\n
\u73b0\u5728\u5bf9\u4e8e\u4ece\u7b2c\u4e09\u4e2a\u5f00\u59cb\u5c31\u6bd4\u8f83\u597d\u7b97\u4e86\u4e4b\u524d\u5957\u516c\u5f0f\u5c31\u662f\u4e86\uff0c\u5e94\u4e3a\u4ed6\u4eec\u7684\u524d\u9762\u90fd\u6709\u4e24\u9879\uff0c\u4f46\u662f\u5bf9\u4e8e\u524d\u4fe9\u9879\u6211\u4eec\u53bb\u5374\u6ca1\u6709\uff0c\u90a3\u4e48\u6211\u4eec\u5c31\u9700\u8981\u5bf9\u5176\u8fdb\u884c\u6784\u5efa\u524d\u4e24\u9879\u7684\u503c\u4e86\u8fd8\u662f\u6839\u636e\u4f8b\u5b50\u8fdb\u884c\u89c2\u5bdf\u524d\u4e24\u9879<\/p>\n\n\n\n
\u7b2c\u4e00\u9879\u5c31\u662f \\frac{4}{1}\\\\\n\u7b2c\u4e8c\u9879\u5c31\u662f 4+\\frac{1}{2}=\\frac{9}{2}\\\\\n\u5bf9\u4e8e\u7b2c\u4e00\u4e2a\u6765\u8bf4\u5e26\u5165\u9012\u63a8\u516c\u5f0f\n\\\\x_i=\\frac{4}{1}=\\frac{h_{i-1}4+h_{i-2}}{k_{i-1}4+k_{i-2}}\\\\\n\u90a3\u4e48\u4ee4 \\\\\nh_{i-1}=1,h_{i-2}=0\\\\\nk_{i-1}=0,k_{i-2}=1\\\\\n\u5e26\u5165\u800c\u4e2d\\\\\nx_2=\\frac{4*2+1}{1*2+0}\\\\\n\u6210\u7acb\u7b26\u5408\uff0c\u5373\u6784\u9020<\/pre><\/div>\n\n\n\n
import owiener\nfrom Crypto.Util.number import long_to_bytes\nfrom gmpy2 import iroot, gmpy2, powmod\n\nn = 6969872410035233098344189258766624225446081814953480897731644163180991292913719910322241873463164232700368119465476508174863062276659958418657253738005689\ne = 3331016607237504021038095412236348385663413736904453330557803644384818257225138777641344877202234881627514102078530507171735156112302207979925588113589669\nc = 1754994938947260364311041300467524420957926989584983693004487724099773647229373820465164193428679197813476633649362998772470084452129370353136199193923837\ndef a\u200b\u200b(n,e):\n    while e:\n        p=n\/\/e\n\n        yield p\n        n,e=e,n-p*e\n\ndef  jianfenshu\u200b\u200b(arr):\n    hi1=1;hi2=0#hil1\n    ki1=0;ki2=1\n    for x in arr:\n        h=x*hi1+hi2\n        k=x*ki1+ki2\n        yield h,k\n        hi1,hi2=h,hi1\n        ki1,ki2=k,ki1\ndef attack\u200b\u200b(e,n):\n    for k,d in jianfenshu\u200b\u200b(a\u200b\u200b(e,n)):\n        if k==0:\n            continue\n        if \u200b\u200b(e*d-1)%k!=0:\n            continue\n        phi=\u200b\u200b(e*d-1)\/\/k\n        s=n+1-phi\n        data=s*s-4*n\n        if iroot\u200b\u200b(data,2)[1]==True:\n            print\u200b\u200b('\u5206\u89e3\u6210\u529f')\n            t=iroot\u200b\u200b(data,2)[0]#p-q.s=p+q\n            p=\u200b\u200b(t+s)\/\/2\n            q=\u200b\u200b(s-t)\/\/2\n            if p*q==n:\n                m=powmod\u200b\u200b(c,d,n)\n                print\u200b\u200b(long_to_bytes\u200b\u200b(m))\n            return d\n\n    print\u200b\u200b('\u5931\u8d25')\n    return None\nattack\u200b\u200b(e, n)\n\n\n<\/code><\/pre>\n\n\n\n
\"image-20260701211616949\"\/<\/div><\/figure>\n\n\n\n
b'NSSCTF{e_is_so_huge}'\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
e\u5f88\u5927\u7684dp\u6cc4\u9732\u653b\u51fb \u9644\u4ef6\u5982\u4e0b \u6211\u4eec\u77e5\u9053dp*e = 1mod\u200b\u200b(p-1) => dp * e =k\u200b […]<\/p>\n","protected":false},"author":1,"featured_media":383,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-442","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-learn"],"_links":{"self":[{"href":"https:\/\/blog.lmoon.cn\/index.php\/wp-json\/wp\/v2\/posts\/442","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.lmoon.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.lmoon.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.lmoon.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.lmoon.cn\/index.php\/wp-json\/wp\/v2\/comments?post=442"}],"version-history":[{"count":4,"href":"https:\/\/blog.lmoon.cn\/index.php\/wp-json\/wp\/v2\/posts\/442\/revisions"}],"predecessor-version":[{"id":461,"href":"https:\/\/blog.lmoon.cn\/index.php\/wp-json\/wp\/v2\/posts\/442\/revisions\/461"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blog.lmoon.cn\/index.php\/wp-json\/wp\/v2\/media\/383"}],"wp:attachment":[{"href":"https:\/\/blog.lmoon.cn\/index.php\/wp-json\/wp\/v2\/media?parent=442"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.lmoon.cn\/index.php\/wp-json\/wp\/v2\/categories?post=442"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.lmoon.cn\/index.php\/wp-json\/wp\/v2\/tags?post=442"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}