# just a normal big prime M = 2039129633208009090414901212304234091626233923923301042398416489123719065081065776033127561876033127924471
n = 10**25 key = 2*pow(3,n-1,M) - 1
enc = b'it\x0bM\xfa-\xe3T{\xaa\x0f@\xa2\xf1@\xbd\x86e\x85\x9e\xfcp_o\x8f\xccd\x13\xceW\x13\x14\x11\x055b\xcbk\xa0' flag = bytes([x ^ y for x, y inzip(enc, long_to_bytes(key))]) print(flag)
ez_f3mr4t
这个题出发点肯定在q = next_prime(p ^ ((1<<512)-1))
设 m = 1<<512,t = p^m 不难发现t其实就是p的按位取反,进一步我们可以发现:p + t = M
由此我们可以分析出p,q大致范围
题目中:
q=next_prime(M−p)q
所以存在一个很小的 gap,使得:
q=M−p+gap
于是:
p+q=M+gap
令:
S=M+gap
那么 p,q 是方程:
x2−Sx+n=0
的两个根,判别式为:
Δ=S2−4n
当 gap 正确时,\Delta 是完全平方数。
枚举很小的奇数 gap 即可分解 n,然后解 RSA。
from Crypto.Util.number import * from gmpy2 import *
e = 65537 n = 0x308244e7a7de386723c92ba62e35bc22c3ec1b93023e1551408344a4ba31c6203da849aedee0cadf26a3442f9fd652f7d97c053a3f2c298eab6c0f0c2d0b4642a81765ddb00b690425eb212d5520327ac2d53a22922448399fecb54fbc04dbb68fa33fee7666cb9e05278b5f5f1330b3918d3a7def580fcc00f6f596f16eba3b c = 0x13a77e34f09b8a2291cdb397ea0e5cb9e86f691c6565b35c76e6bb6248b67db24315e22fe1dc5321a8820320cdd9b51e3d431459aac2213948f4fbf01c4ce974428d1ed745b2c06f8aa92b22dfede3b7ceb59aa4eb22467129f55b60037a1a2de9b37f25fda3fe40323fccc7c8bbdd4446096b37cef4138337ee9a04c2e3d5fd M = (1 << 512) - 1 # p = getStrongPrime(512) # q = nextprime(M - p) for k inrange(1,100000): delt = pow(M + k,2) - 4*n if iroot(delt,2)[1]: p = (M + k + iroot(delt,2)[0]) // 2 q = n // p phi = (p-1)*(q-1) d = inverse(e,phi) m = pow(c,d,n) print(long_to_bytes(m))
ez_fermat
给了一个hint,从hint入手
因为 a*p + b ≡ b (mod p),所以:
plain
Text
hint ≡ (a*p + b)^q ≡ b^q (mod p)
第二步:关键变形 —— 把未知的 q 换成已知的 n
由费马小定理,模 p 时指数可以对 p-1 取模。注意 n = pq,而 p ≡ 1 (mod p-1),所以:
Text
n = p*q ≡ 1*q = q (mod p-1)
于是:
Text
b^n ≡ b^q ≡ hint (mod p)
也就是说 p 整除 (b^n − hint),而 b、n、hint 全是已知量
第三步:gcd 出 p,由此分解n
p = gcd(n, pow(b, n, n) - hint)
from Crypto.Util.number import * from gmpy2 import *
n = 15962603324053600624662899467930954606237037554051572101066176482327650464579501876010780067612122315010349894395035821617153081982429716234378979239633769779503395609504372912298014522344609346937078959678893005192469085672940628091531228571447786013091492389216237976408692434723698967667324605921896928717731731591488800520224411239128106892402734198486634978989319563704879076976307439748456769245703782902660583833942684475506024284563786886608632662629581206716450648212025254862836883526055933841863348546872473877054469843468332542834452213365868510001991952142536759384940216228753729399187149594010090304067 c = 4281919068424886012214413435957379635517466043647380176350221253614623990599452495938689758001256045320061491376355750164051326734927905972267385611552894838140009898450267453653097466286838460889968896032216593811984942511165228143089457988630435810304672454147149556110542203084341901598519587611096893432307236558970264536719689039318023572680185246871600989317992399536729717958072642243834689061928667913495884682029212015071613730401843271641197254089900489231738518876415262001687002012972665662364940457678043829768126263211295258465202419686281997749861180041439407866197636369525192971926660559217573713931 hint = 8894364790280693556124457666776501614023509475927164016497858629229215409128965020674642063592770935057209719989294548263833927477972267267951214184209046168773196349537926982123382473522039515862138755400978350128128233701795758152143272668945626119949376162344749760499165210224412751964322150037199401111258869439672762883792051818112500032192131948644557686621759867629440824691768395882797936616839572906841251000681054283164497419314938363871139253289134458466501698235039234455154975165111296198209091586550990873209534256929400689017034618807232508747449076486852786199340704419120538526208691066898035362296
a, b = 0x2025, 0x2026 e = 65537 p = gcd(pow(b,n,n) - hint,n) q = n // p phi = (p-1)*(q-1) d = inverse(e,phi) print(long_to_bytes(pow(c,d,n)))
from Crypto.Util.number import * import uuid from pwn import * from gmpy2 import *
io = remote("127.0.0.1", 55450) io.recvuntil(b'p = ') p = io.recvline() p = int(p.strip().decode()) print(p) points = []
inv = inverse(2**248,p)
for i inrange(1,45): io.recvuntil(b'choice: ') io.sendline(b'1') io.recvuntil(b'input x: ') io.sendline(str(i).encode()) data = int(io.recvline().strip()) * inv point = (i, data) points.append(point)
R.<x> = PolynomialRing(GF(p)) f = R.lagrange_polynomial(points) print(f) cs = f.list() flag = ''.join(chr(x) for x in cs)