\u5149\u6ed1\u653b\u51fb<\/h3>\n\n\n\n
\u5f53\u4e00\u4e2a\u6570\u7684\u6700\u5927\u7d20\u56e0\u5b50\u7ec4\u4e0d\u5927\u4e8e \u8fd9\u4fdd\u8bc1\u4e86\u6784\u9020\u51fa\u6765\u7684M=mk\u5982<\/p>\n\n\n\n \u56e0\u4e3a\u5f97\u5230\u7684M\u5927\u4e8ep\u7684\u6700\u5927\u7d20\u56e0\u5b50\u7136\u540e\u6211\u4eec\u5c31\u53ef\u4ee5\u5f97\u5230<\/p>\n\n\n\n \u9898\u76ee\u5982\u4e0b<\/p>\n\n\n\n \u9996\u5148\u8981\u5148\u770b\u61c2\u90e8\u5206\u4ee3\u7801\uff0c\u8fd9\u4e2a\u9898\u76ee\u7684\u52a0\u5bc6\u903b\u8f91\u4e3a\u968f\u673a\u9009\u53d6\u7d20\u6570\u200b\u200b(sieve_base\u751f\u6210\u4e00\u4e32\u7d20\u6570)\u4e0ep\u76f8\u4e58\uff0c\u5f53p+1\u4e3a\u7d20\u6570\u662f\u5c31\u505c\u6b62\u5faa\u73af\u3002<\/p>\n\n\n\n \u90a3\u4e48\u6211\u4eec\u53ef\u4ee5\u77e5\u9053p\u662f\u6709\u591a\u4e2a\u7d20\u6570\u76f8\u4e58\u5f97\u5230\u7684 \uff081\uff09<\/p>\n\n\n\n \u66f4\u5177\u524d\u9762\u7684\u77e5\u8bc6\u6211\u4eec\u5e94\u8be5\u6784\u9020\u4e00\u4e2aM\u7136\u540e\u5bf9\u5176\u8fdb\u884c\u89e3\u9898\uff0c\u4f46\u662fM\u6211\u4eec\u5229\u7528\u4ee3\u7801\u8868\u793a\u4e0d\u597d\u8868\u793a\uff0c\u6240\u4ee5\u6211\u4eec\u5bf9\u5176\u8fdb\u884c\u6269\u5927\u627e\u5176k!<\/p>\n\n\n\n \u7136\u540e\u5bf9\u4e8e\u6c42\u89e3a^k!<\/p>\n\n\n\n \u6c42\u51fa\u4e4b\u540e\u5229\u7528gcd\u200b\u200b(a^{k!}-1,n)=p\u8fdb\u884c\u5224\u65ad\u5982\u4f55p\u4e0d\u662f1\u548cn\u90a3\u4e48\u5c31\u8868\u793a\u5206\u89e3\u6210\u529f<\/p>\n\n\n\n \u9996\u5148\u5bf9\u4e8edp\u548cdq\u7684\u542b\u4e49\u4e3ad\u5728\u6a21p\u4e0b\u7684\u8fd0\u7b97\uff0c\u6216\u8005\u662fd\u5728\u6a21q\u4e0b\u7684\u8fd0\u7b97<\/p>\n\n\n\n \u6211\u4eec\u77e5\u9053\u5728\u5bf9\u4e8e\u4e00\u822c\u60c5\u51b5\u6765\u8bf4\u6211\u4eec\u7684\u52a0\u5bc6\u662fc=pow\u200b\u200b(m,e,n),\u800c\u89e3\u5bc6\u662fm=pow\u200b\u200b(c,d,n).\u4f46\u662f\u5e94\u4e3an=p*q\uff0c\u6240\u4ee5\u6b64\u65f6\u6839\u636e\u4e2d\u56fd\u5269\u4f59\u5b9a\u7406\u6211\u4eec\u53ef\u4ee5\u5f97\u5230 m1=pow\u200b\u200b(c,d,p),m2=pow\u200b\u200b(c,d,q)\u3002<\/p>\n\n\n\n \u6211\u4eec\u8ba9\u5176d%\u200b\u200b(p-1) \u4e5f\u5c31\u7b49\u4ef7\u4e8e d=k\u200b\u200b(p-1)+r<\/p>\n\n\n\n \u800c\u6211\u4eec\u8fd9\u91cc\u7684\u9898\u76ee\u7ed9\u51fa\u7684dp\u5c31\u7b49\u4ef7\u4e8e\u8fd9\u91cc\u7684r,\u5e94\u4e3a\u6211\u4eec\u5c06n\u8fdb\u884c\u62c6\u5206\u4e86\u6240\u4ee5\u6211\u4eec\u5c06\u5176\u5728\u8ba1\u7b97m\u7684\u65f6\u5019\u4e5f\u9700\u8981\u8fdb\u884c\u5408\u5e76\u3002<\/p>\n\n\n\n \u4f46\u662f\u5982\u679cm<p,m<q\u3002\u8bdd\u5c31\u4e0d\u9700\u8981\u5e94\u4e3a\u4ed6\u7684\u6c42\u6a21\u8fd8\u662f\u4ed6\u81ea\u5df1\uff0c\u6240\u4ee5\u6211\u4eec\u5f97\u5230\u7684m\u5c31\u662f\u771f\u6b63\u7684flag\uff0c\u4f46\u662f\u5982\u679c\u5f53<\/p>\n\n\n\n m>q.m>p\u7684\u65f6\u5019\u6211\u4eec\u5c31\u9700\u8981\u5c06\u5176\u8fdb\u884cCRT\u548c\u5e76\u4e86<\/p>\n\n\n\n \u5e94\u4e3a\u6211\u4eec\u5f97\u5230mp,mq\u76f8\u5f53\u4e8e\u662fm\u5728\u6a21p.q\u4e0b\u7684\u53d6\u503c\u3002\u6240\u4ee5<\/p>\n\n\n\n \u6216\u8005\u5e94\u4e3am<p,q\uff0cmq\u548cmp\u5c31\u662fm<\/p>\n\n\n\n \u9898\u76ee\u7ed9\u51fadp\u548ce,\u6839\u636edp\u548cd\u7684\u5173\u7cfb\u6211\u4eec\u77e5\u9053<\/p>\n\n\n\n \u6240\u4ee5ed-1 = k*\u200b\u200b(p-1),\u7136\u540e\u53cd\u63a5p<\/p>\n\n\n\n RSA\uff08\u4e8c\uff09 1.p-1\u5149\u6ed1\u653b\u51fb \u7ec3\u4e60\u5e73\u53f0NSSCTF \u5149\u6ed1\u653b\u51fb \u5f53\u4e00\u4e2a\u6570\u7684\u6700\u5927\u7d20\u56e0\u5b50\u7ec4\u4e0d\u5927\u4e8eB\u65f6\uff0c\u6211\u4eec\u53ef\u4ee5\u79f0 […]<\/p>\n","protected":false},"author":1,"featured_media":384,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-439","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\/439","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=439"}],"version-history":[{"count":2,"href":"https:\/\/blog.lmoon.cn\/index.php\/wp-json\/wp\/v2\/posts\/439\/revisions"}],"predecessor-version":[{"id":441,"href":"https:\/\/blog.lmoon.cn\/index.php\/wp-json\/wp\/v2\/posts\/439\/revisions\/441"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blog.lmoon.cn\/index.php\/wp-json\/wp\/v2\/media\/384"}],"wp:attachment":[{"href":"https:\/\/blog.lmoon.cn\/index.php\/wp-json\/wp\/v2\/media?parent=439"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.lmoon.cn\/index.php\/wp-json\/wp\/v2\/categories?post=439"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.lmoon.cn\/index.php\/wp-json\/wp\/v2\/tags?post=439"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}B<\/code>\u65f6\uff0c\u6211\u4eec\u53ef\u4ee5\u79f0\u5176\u4e3aB-\u5149\u6ed1\u6570\uff0c\u4f8b\u59826=2*3<\/code>\u53ef\u4ee5\u79f0\u5176\u4e3a3-\u5149\u6ed1\u6570\uff0c12=2^2*3<\/code>\u53ef\u4ee5\u79f0\u5176\u4e3a4-\u5149\u6ed1\uff08\u56e0\u4e3a2^2\u662f\u6700\u5927\u7684\u7d20\u56e0\u5b50\u7ec4\uff09\u6570\uff08\u6ce8\u610f\u6211\u4eec\u4e5f\u53ef\u4ee5\u53eb\u5b835-\u5149\u6ed1\u30016-\u5149\u6ed1\u3001n-\u5149\u6ed1\u200b\u200b(n>3)\uff09\u3002\u90a3\u4e48\u5bf9\u4e8e*p*\u6765\u8bf4\u5b83\u662fp-\u5149\u6ed1\u6570\uff08\u56e0\u4e3a\u5b83\u662f\u7d20\u6570\uff09\uff0c\u4f46*p*\u22121\u5305\u542b\u5f88\u591a\u5c0f\u7d20\u6570\u56e0\u5b50\uff0c\u6211\u4eec\u5047\u8bbe*p*\u22121\u4e3ak-\u5149\u6ed1\u6570\uff0c\u5b58\u5728\u8fd9\u6837\u7684\u4e00\u4e2a\u6570*M*<\/p>\n\n\n\nM = \\prod_i{p_i}^{\\log_{p_i}{k}}<\/pre><\/div>\n\n\n\np=10\u7684\u7d20\u56e0\u5b50\u4e3a 2 3 7 5\n\u90a3\u4e48M1=2^log2 10=2^3 \/\/\u5411\u4e0b\u53d6\u6574\nM2=3^3\nM=2^3*3^3*7*5<\/code><\/pre>\n\n\n\n\u200b\u200b(p-1)|M\ngcd\u200b\u200b(M,N)=p<\/code><\/pre>\n\n\n\nfrom Crypto.Util.number import *\nfrom random import choice\n\nflag = b'NSSCTF{******}'\n\ndef getMyPrime\u200b\u200b(nbits):\n while True:\n p = 1\n while p.bit_length\u200b\u200b() <= nbits:\n p *= choice\u200b\u200b(sieve_base)\n \n if isPrime\u200b\u200b(p+1):\n return p+1\n\np = getMyPrime\u200b\u200b(256)\nq = getMyPrime\u200b\u200b(256)\n\nn = p*q\ne = 65537\nm = bytes_to_long\u200b\u200b(flag)\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}')\n\n'''\nn = 53763529836257082401813045869248978487210852880716446938539970599235060144454914000042178896730979463959004404421520555831136502171902051936080825853063287829\ne = 65537\nc = 50368170865606429432907125510556310647510431461588875539696416879298699197677994843344925466156992948241894107250131926237473102312181031875514294014181272618\n'''<\/code><\/pre>\n\n\n\na^{M}=a^{t*(p-1)}\\equiv \\ 1^{t} mod(p) =>\n\\\\gcd(a^M-1,n)=p\n\\\\\u5e94\u4e3aM|k! =>\n\\\\gcd(a^{k!}-1,n)=p =>\n\\\\a^{k!}\\equiv \\ 1\\ \\ \\ mod(p)<\/pre><\/div>\n\n\n\n\\\\\n\u6211\u4eec\u53ef\u4ee5\u5c061\u8fdb\u884c\u4ee3\u6362\u6389\uff0c\u5f0f\u5b50\u7b49\u4ef7\u4e8e\n\\\\ a^{(k+1)!} \\equiv (a^{k!} \\ mod(p)\\ )^{(k+1)} \\ \\ mod(p)<\/pre><\/div>\n\n\n\nfrom Crypto.Util.number import *\nfrom math import *\n\nfrom gmpy2 import powmod_exp_list, gmpy2, invert, powmod\n\nn = 53763529836257082401813045869248978487210852880716446938539970599235060144454914000042178896730979463959004404421520555831136502171902051936080825853063287829\ne = 65537\nc = 50368170865606429432907125510556310647510431461588875539696416879298699197677994843344925466156992948241894107250131926237473102312181031875514294014181272618\na=2\nm=2\nass\u200b\u200bert gcd\u200b\u200b(a,n)==1\nwhile 1:\n a=gmpy2.powmod\u200b\u200b(a, m,n)\n p=gcd\u200b\u200b(a-1,n)\n if p!=1 and p!=n:\n break\n m+=1\nq=n\/\/p\nphi=\u200b\u200b(p-1)*\u200b\u200b(q-1)\nd=invert\u200b\u200b(e,phi)\nm=powmod\u200b\u200b(c,d,n)\nprint\u200b\u200b(long_to_bytes\u200b\u200b(m))\n\n<\/code><\/pre>\n\n\n\n![\"image-20260627153835183\"\/](\"https:\/\/blog.lmoon.cn\/wp-doc-assets\/RSA-\u4e8c\/image-20260628144358845.png\")
<\/div><\/figure>\n\n\n\nb'NSSCTF{p-1_smooth_with_factor}'<\/code><\/pre>\n\n\n\n2.dp&dq\u6cc4\u9732<\/h2>\n\n\n\n
m1 \\equiv \\ pow(c,d,n) => \\ \\ m1= c^d \\ mod(p) \\\\\n\\\\m1 = c^{k(p-1)+r}\\ \\ mod(p)\n\\\\\u5e94\u4e3a\u8d39\u9a6cgcd(c,p)=1 => \\ c^{p-1} \\equiv \\ 1 \\ mod(p)\\\\\nm1=c^{r} \\ \\ mod(p)<\/pre><\/div>\n\n\n\nm_p\\ \\equiv \\ m\\mod(p)\\\\\nm_q\\ \\equiv \\ m\\mod(q)\\\\\nm_p+k_2p\\ =m \\\\\nm_q+k_1q\\ =m \\\\\nm_q\\ =k_2p+m_p \\ \\ mod(q) \\\\\nk_2p= m_q \\ -m_p \\ mod(q)\\\\\nk_2=(m_q-m_p)*invert(p,q) mod(q)\n\\\\\n\\\\m=m_p+k2*p<\/pre><\/div>\n\n\n\n
\nfrom Crypto.Util.number import long_to_bytes\n\nfrom gmpy2 import gmpy2, invert\n\np = 13070310882303377463944295715444821218324151935347454554272870042925400761984585838979931730897626589859098834802923539617244712852188293321626061072925723\nq = 10411551818233737389114520103233235272671271111546186997024935593000298916988792710521511848414549553426943998093077337023514210631662189798921671306236009\nc = 62492280219693914005334023569480350249964827909276875032578276064973191654731196407886841145547165693859745313398152742796887457192397932684370631253099255490064673499746314452067588181106154875239985334051909867580794242253066085627399488604907196244465911471895118443199543361883148941963668551684228132814\ndp = 11568639544706374912496682299967972464196129347160700749666263275305083977187758414725188926013198988871173614336707804756059951725809300386252339177953017\ndq = 3455040841431633020487528316853620383411361966784138992524801280785753201070735373348570840039176552952269927122259706586236960440300255065994052962742469\nmp=pow\u200b\u200b(c,dp,p)\nmq=pow\u200b\u200b(c,dq,q)\ninvp = invert\u200b\u200b(p, q)\nk=\u200b\u200b(mq-mp)*invert\u200b\u200b(p,q)%q\nm=mp+k*p\nprint\u200b\u200b(long_to_bytes\u200b\u200b(m))<\/code><\/pre>\n\n\n\nfrom Crypto.Util.number import long_to_bytes\n\nfrom gmpy2 import gmpy2, invert\n\np = 13070310882303377463944295715444821218324151935347454554272870042925400761984585838979931730897626589859098834802923539617244712852188293321626061072925723\nq = 10411551818233737389114520103233235272671271111546186997024935593000298916988792710521511848414549553426943998093077337023514210631662189798921671306236009\nc = 62492280219693914005334023569480350249964827909276875032578276064973191654731196407886841145547165693859745313398152742796887457192397932684370631253099255490064673499746314452067588181106154875239985334051909867580794242253066085627399488604907196244465911471895118443199543361883148941963668551684228132814\ndp = 11568639544706374912496682299967972464196129347160700749666263275305083977187758414725188926013198988871173614336707804756059951725809300386252339177953017\ndq = 3455040841431633020487528316853620383411361966784138992524801280785753201070735373348570840039176552952269927122259706586236960440300255065994052962742469\nmp=pow\u200b\u200b(c,dp,p)\nmq=pow\u200b\u200b(c,dq,q)\nprint\u200b\u200b(long_to_bytes\u200b\u200b(mq))<\/code><\/pre>\n\n\n\n![\"image-20260628101351222\"\/](\"https:\/\/blog.lmoon.cn\/wp-doc-assets\/RSA-\u4e8c\/image-20260628144359537.png\")
<\/div><\/figure>\n\n\n\n3.dp\u6cc4\u9732\u653b\u51fb<\/h2>\n\n\n\n
from Crypto.Util.number import *\n\nflag = b'NSSCTF{******}' + b'1'*100\n\np = getPrime\u200b\u200b(512)\nq = getPrime\u200b\u200b(512)\n\nn = p*q\ne = 65537\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'c = {c}')\nprint\u200b\u200b(f'dp = {dp}')\n\n'''\nn = 79201858340517902370077926747686673001645933420450220163567700296597652438275339093680329918615445030212417351430952656177171126427547284822789947152085534939195866096891005587613262293569611913019639653984932469691636338705418303482885987114085769045348074530172292982433373154900841135911548332400167290083\nc = 70109332985937768446301118795636999352761371683181615470371772202170324747707233792154935611826981798791499937601162039878070094663516868746240133223110650205575807753345252087103328657073552992431511929172241702073381723302143955977662087561904058172777520360991685289300855900793806183473523998422682944404\ndp = 3098334089252415941833934532457314870210700261428241562420857845879512952043729097866485406309479489101668423603305497982177150304625615059119312238777275\n'''<\/code><\/pre>\n\n\n\ndp \\equiv \\ d \\ mod(p-1) \\\\ \\\ndp*e \\ \\equiv \\ d*e \\ mod(p-1) \\\\\ne*d \\ \\equiv \\ 1 \\ mod(phi) => phi=(p-1)*(q-1) => e*d \\equiv 1 \\ mod(p-1)<\/pre><\/div>\n\n\n\n
from Crypto.Util.number import long_to_bytes\nfrom gmpy2 import gmpy2\nd=1\nn = 79201858340517902370077926747686673001645933420450220163567700296597652438275339093680329918615445030212417351430952656177171126427547284822789947152085534939195866096891005587613262293569611913019639653984932469691636338705418303482885987114085769045348074530172292982433373154900841135911548332400167290083\nc = 70109332985937768446301118795636999352761371683181615470371772202170324747707233792154935611826981798791499937601162039878070094663516868746240133223110650205575807753345252087103328657073552992431511929172241702073381723302143955977662087561904058172777520360991685289300855900793806183473523998422682944404\ndp = 3098334089252415941833934532457314870210700261428241562420857845879512952043729097866485406309479489101668423603305497982177150304625615059119312238777275\ne=65537\nfor k in range\u200b\u200b(1,e):\n if \u200b\u200b(dp*e-1)%k!=0:\n continue\n p=\u200b\u200b(dp*e-1)\/\/k+1\n print\u200b\u200b(k)\n\n if n%p==0:\n phi = \u200b\u200b(p - 1) * \u200b\u200b(n\/\/p-1)\n d=gmpy2.invert\u200b\u200b(e,phi)\n m=pow\u200b\u200b(c,d,n)\n print\u200b\u200b(long_to_bytes\u200b\u200b(m))\n break\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"