[鹤城杯 2021]BabyRSA 题面 # [鹤城杯 2021]BabyRSA from Crypto.Util.number import getPrime, bytes_to_long # from secret import flag flag = b'flag{test}' p = getPrime(1024) q = getPrime(1024) n = p * q e = 65537 hint1 = p >> 724 # msb 1024 - 724 hint2 = q % (2 ** 265) # lsb 265 ct = pow(bytes_to_long(flag), e, n) print(hint1) print(hint2) print(n) print(ct) # Data hint1 = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479 hint2 = 40812438243894343296354573724131194431453023461572200856406939246297219541329623 n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969 ct = 19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188 Idea Reference: 鹤城杯2021 Crypto Writes up / 我的推导 [公式]

题目附件 from Crypto.Util.number import * from secret import flag def genKey(nbits): p = getPrime(nbits) q = getPrime(nbits) N = p*p*q d = inverse(N, (p-1)*(q-1)//GCD(p-1, q-1)) return N,d def encrypt(message,N): m = bytes_to_long(flag) c = pow(m, N, N) return c nbits = 1024 m = bytes_to_long(flag) N,d = genKey(nbits) c = encrypt(m,N) print('c =', c) print('N =', N) print('d =', d) """ c = 29897791365314067508830838449733707533227957127276785142837008063510003132596050393885548439564070678838696563164574990811756434599732001622138564176327233154381380717648392357672642893142367607369679906940371540867456654151408884171467638060523066406441697453971996011548195499549200103123841556085936672833238264876038160712793697159776332101536779874757463509294968879216810485825310481778472384531442206034564488532399171243463881900578407746982324779260941957792455217641883334131366614310644607114128868153897806362954456585661855569432513785225453501792356175649676419772626548071916379318631677869452985829916084336045071072493567871623113923140668031380684940109024609167449291380675124701557542736834722898328082888430566229322840781411336263268594978558564310744076581639469210462567543585251718744340216155557606004995449505782302864725856877289388008819135023371948017425832082773421030256964953984562211638060 N = 3231913372897424708803097969843687520868057190788284975066875241636436021279559026753076528399891936983240045179193386905918743759145596242896507856007669217275515235051689758768735530529408948098860529277921046146065473333357110158008648799207873976745048714516868561754202543130629713461365314627535982379718931633528922076268531363809414255082933615667770491818402126891370106045838695484124212397783571579791558324350069782623908757815983802849109451590357380624488436968737140312471089662428308113246310588336044438265822574558816510054763215983649467009345458480077882624118620789015758507736272402998721366662352794082495441303895025585316667229865533166614969641012195668280586477033200418153345241668242651407009849656745509386158276185301334443855737552801531617549980843398648751032649895403939319648954908487619711555700124294191702406981128355348449748466449951568451135718146828444185238617155432417897711198169 d = 220908195398117048628110042133057032501548264225985823161565460390793825899523662424732910718579350524590368287207857059670558852106434615134645183432670023784725430385048028248108677670095524205518013647694485975996499747580966911259433184798952372110628624294686853944766950244209186984164963987120416687012811346656498861438432610431705868541829977481875385468143747334359481673214618931159403123892213161430602430294790913847722073762999311674428134241956293914716183107414340330449465142849402354034926378025006749405210014879947411570380433942279355488861684317611066949685697268714760755591128598654573304969 """ 思路 定义模数 $N$ 和 解密指数 $d$ 之间的关系 [公式] 解密指数 $d$ 的计算公式

Reference 基础 What is modular arithmetic? (article) | Khan Academy 中国剩余定理 - OI Wiki 视频/会议 论文 1111.4877.pdf 题目 hackergame2019-writeups/official/十次方根 at master · ustclug/hackergame2019-writeups · GitHub Intended Solution to Crypto Problems in NCTF 2019 | Soreat_u’s Blog 进阶 Using the CRT with RSA 代码 Python2 RSA/rth-root extraction at master · mad-jcbx/RSA · GitHub 拓展 Elements of Z/nZ - Finite Rings AMM 算法详解与应用 AMM算法简要理解（Adleman-Mander-Miller Method） 工具 factordb 讨论 Improved nth root for finite fields and integer_mods · Issue #7931 · sagemath/sage · GitHub sage/src/sage/rings/finite_rings/integer_mod.pyx at 3dd953c3aa6b5143071b6c39208199cf128c8080 · sagemath/sage · GitHub 导言 在一般情况的RSA中，求出 $\phi(N)$ 就已经接近解出明文了。这个时候我们往往只需要通过 $ed\equiv1 \pmod {\phi (N)}$ 即可求出私钥 $d$，从而求出明文。但是要直接求逆元 $d$，需要满足 $gcd(e,\phi(N))=1$，也就是 $e$ 和 $\phi(N)$ 互质的情况。如果不满足，则会大大提高难度。

Reference 怎么样用c语言求1000的阶乘？ - 知乎 SpeedUp 题意: 提交 'flag' + {{ $\text{SHA256}\left(\sum_{{i=0}}^{{\lfloor \log_{10} (2^{27}!) \rfloor}} \left( \left\lfloor \frac{{2^{27}!}}{{10^i}} \right\rfloor \mod 10 \right)\right)$ }} + '}' / 上面这个式子让 GPT 写的 (图一乐，而且这么求 number length 慢的要死(慢过 str(number).__len__()，而实际上是可以 log 巴拉巴拉求的，忘了复杂度了，总之是可以更快，而且实际上也不用求长度，见最后的代码))

MIFARE Classic EV1 代表了 MIFARE Classic 产品系列的最高演进阶段，继承了所有以往版本的优良特性。它提供 1K 和 4K 内存版本，分别满足不同应用需求 / 👆🏻来自 MIFARE官网 / 介绍中的 1k 和 4k 为内存容量，比较常见的为 1k 版本

SageMath 版本信息 / > sage ┌────────────────────────────────────────────────────────────────────┐ │ SageMath version 10.1.beta3, Release Date: 2023-06-11 │ │ Using Python 3.11.1. Type "help()" for help. │ └────────────────────────────────────────────────────────────────────┘ ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ ┃ Warning: this is a prerelease version, and it may be unstable. ┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ sage: 此前对 $x$ 开 $n$ 次方, 常用 pow(x, 1/n), 但对于结果不是整数时就得用 gmpy2.iroot(x, n), 而我又不喜欢使用第三方库, 现在对此问题有了以下解决方案 Sage

2023年四川网信人才技能大赛（网络安全管理员赛项）决赛 / 题目附件 from Crypto.Util.number import * from secret import flag from sympy import nextprime flag=b'' r = getRandomNBitInteger(64) p = r**5 + r**4 - r**3 + r**2 - r + 2023 q = r**5 - r**4 + r**3 - r**2 + r + 2023 p =nextprime(p) q =nextprime(q) n = p*q def enc(flag, n): m = bytes_to_long(flag) return pow(m, 65537, n) c = enc(flag, n) print(n) print(c) # 25066797992811602609904442429968244207814135173233823574561146780193277243588729282392464721760638040595480284865294238118778099149754637586361909432730412493061503054820202744474632665791457 # 18808483076270941157829928736000549389727451019027515249724024369421942132354537978233676261769285858813983730966871222263698559152437016666829640339912308636169767041243411900882395764607422 Exploit Sage / P.<r> = PolynomialRing(QQ) fp = r**5 + r**4 - r**3 + r**2 - r + 2023 fq = r**5 - r**4 + r**3 - r**2 + r + 2023 print(f'{latex((fp * fq))}') # n的最大项只有r^8，所以对n开十次过后基本就等于r r_max = (1 << 64) - 1 # 接着还可以减一个小值来模拟随机, 或者用题目的r生成方式, 会发现对最后的结果没有影响 p = fp(r = r_max) q = fq(r = r_max) P = Primes() p = P.next(Integer(p)) q = P.next(Integer(q)) n = p * q Diff = int(real_nth_root(n, 10)) - r_max print(f'{Diff = }') # 于是 换上题目数据 n = 25066797992811602609904442429968244207814135173233823574561146780193277243588729282392464721760638040595480284865294238118778099149754637586361909432730412493061503054820202744474632665791457 r = int(real_nth_root(n, 10)) - Diff p = fp(r = r) q = fq(r = r) p = P.next(Integer(p)) q = P.next(Integer(q)) assert p * q == n phi = (p - 1) * (q - 1) e = 0x10001 c = 18808483076270941157829928736000549389727451019027515249724024369421942132354537978233676261769285858813983730966871222263698559152437016666829640339912308636169767041243411900882395764607422 d = inverse_mod(e, phi) m = power_mod(c, d, n) from Crypto.Util.number import long_to_bytes print(long_to_bytes(m)) Output

同时发布于 https://hello-ctf.com/HC_envSet/Crypto/ / 前言 善于百度, 哪里不懂先去百度, 其实搜索引擎上更推荐 Bing 或是 谷歌, 百度只是要求搜索解决的统一说辞, 还有疑惑则去读 <提问的智慧>, 如果依旧不理解, 可以用从 <提问的智慧> 中学到的提问方式来请教别人.

一年一度的密码盛宴, 看春哥队和 yeye5队乱杀了, 今年 r3k 也进入前十了, 还有南邮以及中科大的队都好猛, 还有不说话只做题的队友 www, 你们 tql / 复现进度 … 先收集一下来自discord 的 wp 如下

PPT(图片)地址 / 视频地址(38 分 40 秒) / 数据生成代码(题目/Sage) from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime flag = b'flag{xxxLOV3xxx}' m = bytes_to_long(flag) p = getPrime(1024) q = getPrime(1024) n = p * q phi = (p - 1) * (q - 1) e1 = getPrime(30) e2 = getPrime(20) print(f'{e1 = }') print(f'{e2 = }') print(f'{n = }') d1 = inverse_mod(e1, phi) d2 = inverse_mod(e2, phi) c1 = pow(m, e1, n) c2 = pow(m, e2, n) print(f'{c1 = }') print(f'{c2 = }') 推导 如果 e1 与 e2 互素(不互素就先直接算 r, s, 最后开gcd(e1, e2)次根), 则用拓展欧几里得解r, s 如果 r 是负数, (r 和 s 中有一个必定是负数) 那么再用欧几里得算法计算 $c_1^{-1}$, (为什么要求逆) 有: [公式] 证明 [公式] 得出 $e_1, e_2$，接着我们计算 $m$