Table of Contents

rsa all in two #

leak (p^q)»nbits #

from Crypto.Util.number import *
import sys
sys.setrecursionlimit(1500)

nbits=512
leakBits = 262
leakbits = nbits - leakBits
e = 65537

n=73822410148110759760164946405270228269255384237831275745269402590230495569279769799226813942899942423718229747478982630879557319063920515141217164980012063064986634632452289290326704640527699568662492105204165609614169349755365956569362139057327962393611139347462018186440108621311077722819578905265976612923      
c=71808322808599218331233291542779486534747913572475630198802984648982830332628443972652322590637382696027943799004331488098592525306523343649935216419522329722152742610560398216737030893090641493326477786720839849938277402743820773957184083430369443325368720115515840174745825798187125454448297155036065857691      
leak=2223117424030234543005449667053988296724455736030907136592525175314696509716321

leak = leak << leakbits

a1 = "0" + str(bin(leak)[2:])
def find(p,q):
    l = len(p)
    tmp0 = p + (512-l)*"0"
    tmp1 = p + (512-l)*"1"
    tmq0 = q + (512-l)*"0"
    tmq1 = q + (512-l)*"1"
    if(int(tmp0,2) < int(tmq0,2)):
        return 
    if(int(tmp0,2)*int(tmq0,2) > n):
        return 
    elif(int(tmp1,2)*int(tmq1,2) < n):
        return

    if(l == 512 - leakbits):
        pp = int(tmp0,2)
        PR.<x> = PolynomialRing(Zmod(n))
        f = pp + x*2 + 1
        f = f.monic()
        res = f.small_roots(X=2^leakbits-1, beta=0.5, epsilon=0.01)
        if(res):
            try:
                plow = int(res[0])
                p = pp + plow * 2 + 1
                q = n // p
                d = inverse(e,(p-1)*(q-1))
                print(long_to_bytes(int(pow(c,d,n))))
            except:
                pass
                    
    else:
        if(a1[l] == "1"):
            find(p+"1",q+"0")
            find(p+"0",q+"1")
        else:
            find(p+"0",q+"0")
            find(p+"1",q+"1")

tempp = ""
tempq = ""
find(tempp,tempq)

#flag{6eb67115-38b1-4e75-b3fc-de3a9697e565}

比较 aii in one 的一集 #

import sympy
from Crypto.Util.number import *
from secret import flag
e = 65537
p1 = sympy.randprime(2 ** 1023,2 ** 1024)
q1 = sympy.randprime(2 ** 1023,2 ** 1024)
a1 = p1 ^ q1
b1 = p1 * q1
c1 = pow(bytes_to_long(flag[:19]),e,p1*q1)
p2 = sympy.randprime(2 ** 511, 2 ** 512)
q2 = sympy.randprime(2 ** 511, 2 ** 512)
a2 = (p2 * q2) ^ (p2 + q2)
b2 = (p2 * q2) ^ (p2 - q2)
c2 = pow(bytes_to_long(flag[19:]),e,p2*q2)
f= open('output.txt','w')
f.write(str(a1)+'\n')
f.write(str(b1)+'\n')
f.write(str(c1)+'\n')
f.write(str(a2)+'\n')
f.write(str(b2)+'\n')
f.write(str(c2)+'\n')

a1=67739512154277162085770157687437441198363095490607019903179640765859289435128844487312739643781929328039885340492248268381181927215444058044731882600621443249379470235583032722854561171610662253187419453432598163528304052508578209017561499836803166110456130462444164049945234353225230736363194196935115979960
b1=17185396829856546439605443867156437815015135756541052637907770783830686534153389303291740769607944691156059669175157827203495395745826694347428694508457493991041224390283763876476601200114028282946724348906485066220181559142937065978299071246507281834301352443856315199896106182934770582627129779923357891915723961923663378398066801894395956482176730300442901078199030200112352639266103862753546370851947797706641058966862813099369195689336228579744994641830699890792017097474275824545664085264972274642572927392940910981115837831275773192989084712813373293435228956787629490757407431010258942490818726318175944867633
c1=2180773316568266715369209198734610509148388893757598741330158376506447322216176787253641696053169188685408469718202047474660716095850135317790263924418449270019680259700945680062960717565507426032265137192689118286560945331123730529355709043463330231284484658907466172538703301303440062783852136344472063837313195697915205569416630439851250171277336484771753816776835527532090668694986220968152676688392975798850738947165707984817923309381811015047150056144403783079156300625762879231698942313672034730244627530962258121618021680413439757194393609777357848156392150372631861473658135778661768208071991812674187273360
a2=102834527596695950719979111423985349726489864165244791755647652205679952999516919199218636781810880771255724153293007819995198831162629014290926266777774940370836206596205967641213842702547665263659933022253549718321445029287279257463914991950587622466780705329578580061019164231870445205566240956950369224751
b2=102834527596695950719979111423985349726489864165244791755647652205679952999516919199218636781810880771255724153293007819995198831162629014290926266777774949520538413350277489291427420271328741830415622921056457371226207219443304838109001023043838810016379140438034881290332449739051404396455209891630254998985
c2=46285230821397377383998198689981002335902850753318921384068480704506522918467396194184971163720421808774010121239873784436865080818119851642074388303787396280596526597467664310187113430990219486840906481260493087443528880139543560763852844535689852804877233056126591516506599561944164619603448246607830867682

p*q、p^q 1 #

import sympy
from Crypto.Util.number import *
from secret import flag
e = 65537
p1 = sympy.randprime(2 ** 1023,2 ** 1024)
q1 = sympy.randprime(2 ** 1023,2 ** 1024)
a1 = p1 ^ q1
b1 = p1 * q1

#

from Crypto.Util.number import *
import sys
sys.setrecursionlimit(1500)

#part1,剪枝
a1=67739512154277162085770157687437441198363095490607019903179640765859289435128844487312739643781929328039885340492248268381181927215444058044731882600621443249379470235583032722854561171610662253187419453432598163528304052508578209017561499836803166110456130462444164049945234353225230736363194196935115979960
b1=17185396829856546439605443867156437815015135756541052637907770783830686534153389303291740769607944691156059669175157827203495395745826694347428694508457493991041224390283763876476601200114028282946724348906485066220181559142937065978299071246507281834301352443856315199896106182934770582627129779923357891915723961923663378398066801894395956482176730300442901078199030200112352639266103862753546370851947797706641058966862813099369195689336228579744994641830699890792017097474275824545664085264972274642572927392940910981115837831275773192989084712813373293435228956787629490757407431010258942490818726318175944867633
c1=2180773316568266715369209198734610509148388893757598741330158376506447322216176787253641696053169188685408469718202047474660716095850135317790263924418449270019680259700945680062960717565507426032265137192689118286560945331123730529355709043463330231284484658907466172538703301303440062783852136344472063837313195697915205569416630439851250171277336484771753816776835527532090668694986220968152676688392975798850738947165707984817923309381811015047150056144403783079156300625762879231698942313672034730244627530962258121618021680413439757194393609777357848156392150372631861473658135778661768208071991812674187273360
e = 65537
a1 = "0" + str(bin(a1)[2:])

def find(p,q):
    l = len(p)
    tmp0 = p + (1024-l)*"0"
    tmp1 = p + (1024-l)*"1"
    tmq0 = q + (1024-l)*"0"
    tmq1 = q + (1024-l)*"1"
    if(int(tmp0,2) < int(tmq0,2)):
        return 
    if(int(tmp0,2)*int(tmq0,2) > b1):
        return 
    elif(int(tmp1,2)*int(tmq1,2) < b1):
        return

    if(l == 1024):
        pp = int(tmp0,2)
        qq = int(tmq0,2)
        d = inverse(e,(pp-1)*(qq-1))
        m = long_to_bytes(pow(c1,d,pp*qq))
        print(str(m)[2:-1],end = "")
        
    else:
        if(a1[l] == "1"):
            find(p+"1",q+"0")
            find(p+"0",q+"1")
        else:
            find(p+"0",q+"0")
            find(p+"1",q+"1")

tempp = ""
tempq = ""
find(tempp,tempq)

N ^ (p + q)、N ^ (p - q) #

#part2 硬剪枝
a2=102834527596695950719979111423985349726489864165244791755647652205679952999516919199218636781810880771255724153293007819995198831162629014290926266777774940370836206596205967641213842702547665263659933022253549718321445029287279257463914991950587622466780705329578580061019164231870445205566240956950369224751
b2=102834527596695950719979111423985349726489864165244791755647652205679952999516919199218636781810880771255724153293007819995198831162629014290926266777774949520538413350277489291427420271328741830415622921056457371226207219443304838109001023043838810016379140438034881290332449739051404396455209891630254998985
c2=46285230821397377383998198689981002335902850753318921384068480704506522918467396194184971163720421808774010121239873784436865080818119851642074388303787396280596526597467664310187113430990219486840906481260493087443528880139543560763852844535689852804877233056126591516506599561944164619603448246607830867682
e = 65537

def find(p,q,k):
    mask = 2**k-1

    t1 = (int(p,2)*int(q,2))
    t2 = (int(p,2)+int(q,2))
    t3 = (int(p,2)-int(q,2))

    if(len(bin(int(p,2))[2:]) == 512 and len(bin(int(q,2))[2:]) == 512):
        pp = int(p,2)
        qq = int(q,2)
        d = inverse(e,(pp-1)*(qq-1))
        m = long_to_bytes(pow(c2,d,pp*qq))
        if(len(m) < 20):
            print(str(m)[2:-1])
            exit()

    if(((t1^t2)&mask) == (a2&mask) and ((t1^t3)&mask) == (b2&mask)):
        find("0"+p,"0"+q,k+1)
        find("0"+p,"1"+q,k+1)
        find("1"+p,"0"+q,k+1)
        find("1"+p,"1"+q,k+1)
    else:
        return

p = "1"
q = "1"

find(p,q,1)

p*q、p ^ inv_q #

_q = int(bin(q)[2:][::-1] , 2)
c = pow(m,e,n)

print(p ^ _q)

from Crypto.Util.number import *
import sys
sys.setrecursionlimit(1500)

pxorq = 47761879279815109356923025519387920397647575481870870315845640832106405230526
n = 10310021142875344535823132048350287610122830618624222175188882916320750885684668357543070611134424902255744858233485983896082731376191044874283981089774677
c = 999963120986258459742830847940927620860107164857685447047839375819380831715400110131705491405902374029088041611909274341590559275004502111124764419485191
e = 65537
pxorq = str(bin(pxorq)[2:]).zfill(256)
 
def find(ph,qh,pl,ql):
    l = len(ph)
    tmp0 = ph + (256-2*l)*"0" + pl
    tmp1 = ph + (256-2*l)*"1" + pl
    tmq0 = qh + (256-2*l)*"0" + ql
    tmq1 = qh + (256-2*l)*"1" + ql
    if(int(tmp0,2)*int(tmq0,2) > n):
        return 
    if(int(tmp1,2)*int(tmq1,2) < n):
        return
    if(int(pl,2)*int(ql,2) % (2**(l-1)) != n % (2**(l-1))):
        return

    if(l == 128):
        pp0 = int(tmp0,2)
        if(n % pp0 == 0):
            pf = pp0
            qf = n//pp0
            phi = (pf-1)*(qf-1)
            d = inverse(e,phi)
            m1 = pow(c,d,n)
            print(long_to_bytes(m1))
            exit()

    else:
        if(pxorq[l] == "1" and pxorq[255-l] == "1"):
            find(ph+"1",qh+"0","1"+pl,"0"+ql)
            find(ph+"0",qh+"0","1"+pl,"1"+ql)
            find(ph+"1",qh+"1","0"+pl,"0"+ql)
            find(ph+"0",qh+"1","0"+pl,"1"+ql)
        elif(pxorq[l] == "1" and pxorq[255-l] == "0"):
            find(ph+"1",qh+"0","0"+pl,"0"+ql)
            find(ph+"0",qh+"0","0"+pl,"1"+ql)
            find(ph+"1",qh+"1","1"+pl,"0"+ql)
            find(ph+"0",qh+"1","1"+pl,"1"+ql)
        elif(pxorq[l] == "0" and pxorq[255-l] == "1"):
            find(ph+"0",qh+"0","1"+pl,"0"+ql)
            find(ph+"0",qh+"1","0"+pl,"0"+ql)
            find(ph+"1",qh+"0","1"+pl,"1"+ql)
            find(ph+"1",qh+"1","0"+pl,"1"+ql)
        elif(pxorq[l] == "0" and pxorq[255-l] == "0"):
            find(ph+"0",qh+"0","0"+pl,"0"+ql)
            find(ph+"1",qh+"0","0"+pl,"1"+ql)
            find(ph+"0",qh+"1","1"+pl,"0"+ql)
            find(ph+"1",qh+"1","1"+pl,"1"+ql)

find("1","1","1","1")

other #

暑假做的一个小题 #

leak1 = (p2+q2) >> 400
leak2 = (p1 & ((1 << 350) - 1)) >> 5

题目的主要问题在于由leak1解出leak2。显然，如果我们有完整的p2+q2，我们就能够直接联立n2的方程得到精确的p2、q2的值。但是问题在于leak1的低四百位被隐藏了，因此我们没有办法直接解出精确的p2、q2。

而事实上，我们并不需要精确的p2、q2，我们只需要知道他们的高位，就可以通过p高位泄漏求出他们的精确值。因此我们可以通过下面方式解出p2、q2的近似值：
#part1 get leak2
PR.<x> = PolynomialRing(RealField(1000))
f = x*((leak1<<400)-x) - n2 
p2high = int(f.roots()[0][0])

smallroot解方程 #

def getn():
    while(1):
        p = getPrime(128)
        error = getPrime(40)
        q = 2*p + error
        r = 2*q + error
        if(isPrime(q) and isPrime(r)):
            n = p*q*r
            break
    return (p,n)

拿p解方程

#step 1
PR.<x> = PolynomialRing(Zmod(n1//p1))
f = (2*p1 + x)*(4*p1 + 3*x)
f = f.monic()
roots = f.small_roots(X=2^41,beta=0.4)
if roots:
    error = int(roots[0])

连分数 #


num1 = 3
num2 = 5
while(num1<num2):
    num1 = getPrime(512)
    num2 = getPrime(512)

num3 = ring(num1) / ring(num2)
num3 = 1.23389923415003373900567515471436168841941584796842188964423737295914869304653496800649965063081353720701415762591488370228399019899893688681309320356016722276295236528757306976510687729729934668311830828756908988350841843676900575414367123810470585198055372776278588638204471298838884740198056387082949710435502826460830711429956
c = continued_fraction(num3)
print(c)
 
alist = c.convergents()
 
for i in alist:
    a = str(i).split('/')
    if len(a)>1 and gcd(int(a[0]),int(a[1])) == 1 and is_prime(int(a[0])) and is_prime(int(a[1])) and int(a[0]).bit_length()==512 and int(a[1]).bit_length()==512:
        num1 = int(a[0])
        num2 = int(a[1])

二项式 #

myfunction(n)的结果是n^3，那这个方程就变成了hint2 = (3n+1)^p_low mod n^3，二项式定理展开，看系数能算出来p_low，然后coppersmith求出p就行了

from Crypto.Util.number import *
from Crypto.Util.strxor import strxor
from random import randint
from gmpy2 import invert
import os

flag = b'xxx'

def mypad(m):
    l = len(m)
    r = 190 - l
    padded_m = m + os.urandom(r)
    return padded_m

def myfunction(num):
    output = 0
    j = 0
    for i in range(num):
        output += (i+j)*6 + 1
        j += i
    return output

def mix(a,b):
    return a | b , a * b

class MySeries():
    def __init__(self, num):
        self.num = num

    def Coe(self, n):
        i = 0
        c = 1
        while i < n:
            i += 1
            c = (c * (1 / 2 - i + 1)) / i
        return c

    def Point(self, center):
        sum = 0
        center -= 1
        i = 0
        while i < self.num:
            sum += (center ** (1 / 2 - i) * self.Coe(i))
            i += 1
        return sum

def All(bound):
    num = randint(1111, 2222)
    T = MySeries(num)
    output = 0

    i = 3
    while i < bound:
        b1 = T.Point(i)
        b2 = T.Point(i + 1)
        output += (b1 + b2) / 2
        i += 1
    return output

if __name__ == '__main__':
    flag_len = len(flag)
    p,q = getPrime(512),getPrime(512)
    
    while True:
        r = getPrime(512)
        R = bytes_to_long(str(r).encode())
        if isPrime(R):
            break
            
    n = p * q * r 
    hint1 = R * r
    mod = myfunction(n)
    
    hint2 = pow(3*n+1,p % (2 ** 400),mod)
    
    k = int(All(n))
    xor_flag = strxor(long_to_bytes(k >> (k.bit_length() - 8 * flag_len)),flag)
    pad_flag = mypad(xor_flag)
    m = bytes_to_long(pad_flag)
    c = pow(m,65537,n)
    
    print('All data:')
    print(f'flag_len = {flag_len}')
    print(f'n = {n}')
    print(f'c = {c}')
    print(f'hint1 = {hint1}')
    print(f'hint2 = {hint2}')

'''
All data:
flag_len = 42
n = 1885106209951408608833065466098355578239648885277085979696889428331716535742564778501798478665957825315340421821880653818505857049636611632357321104069926874970489073929053910350131880591544986024406953378391135673202854750625745159391997973535848495128365477217006260495413869532372418221652962946340513593002422433536479789576519469228846773250447077165756739529520975715667675188738514871033908115371290569902086064227476952606366538782284487477820835988316471
c = 696238728213276154324787695659767792043458798396732235983493075871691401810545168845655490352789752222363100922123671319198981013421632076090146254867823593523050502577701155837063376958530879006719716789887624440134559774538443909463537086796915613123528679984244371544503657821859556837415229166015914540860398289216765611441964228176020361651359395184571105468667815326494558761738459063914192172836518999575866452752941368767971539919141604299843463853501960
hint1 = 47533994701669017942592643580845693193316601935087923279407365999451221242084261195588230994183718077379066856479267476895986608547324057765879168010176037349172136581929046771540241367625486215731295814611283581608613208990206581757576978017732022062210538697720930605552259306749633658032304554578427461842934055558865521604512892691323385156889995854702621568441768712619224249280792783364635307739215957762771386413831279443875185633720270001928747743847856394847878232194076679733830705297410959656270945532930199517880949
hint2 = 1345739841248959791137389026125065605121513428784838684290299665636596562317989590469829195181078904857051392378877013458099983407103737518119999468489762053545474516182879516762580472262640794849609626308003164739287189671066241628052826558582865342176036139097546843281565147798609965645514151827840249686650855385385323417455247722134760335695053787221300451942370377598800841980049138341564555801417479362085565640973199260631136149016266661293883650801813550118778433333591258278147003619871962070136454674193198696690506092831171400435490432196636796719177624389194619648086397178720207413652618636521150924913978530986709499047969775311955879302418093270101476537853298615347062384026172441455857088955847766335746521291043747795520485020303040819568036819058385444936925860671650596681910380157657689041971132993731048618045570715513584627109356139903842365556697314631573799394266292587334468008221427502353566938518574247502783245674619641519095644135976062817840893465238031354234069073928763492529419021632732679912738674105898149050223970723297059883534089683179512881491210176114419520070007595698242827625902377045860953285447617249204919971737086366
'''

$$ hint2 = (3n+1)^{p’} mod n^3 $$

$$ = kn^3+9(p’\frac{(p’-1)}{2})n^2 + 3p’n + 1

from Crypto.Util.number import *
from Crypto.Util.strxor import strxor

flag_len = 42
n = 1885106209951408608833065466098355578239648885277085979696889428331716535742564778501798478665957825315340421821880653818505857049636611632357321104069926874970489073929053910350131880591544986024406953378391135673202854750625745159391997973535848495128365477217006260495413869532372418221652962946340513593002422433536479789576519469228846773250447077165756739529520975715667675188738514871033908115371290569902086064227476952606366538782284487477820835988316471
c = 696238728213276154324787695659767792043458798396732235983493075871691401810545168845655490352789752222363100922123671319198981013421632076090146254867823593523050502577701155837063376958530879006719716789887624440134559774538443909463537086796915613123528679984244371544503657821859556837415229166015914540860398289216765611441964228176020361651359395184571105468667815326494558761738459063914192172836518999575866452752941368767971539919141604299843463853501960
hint1 = 47533994701669017942592643580845693193316601935087923279407365999451221242084261195588230994183718077379066856479267476895986608547324057765879168010176037349172136581929046771540241367625486215731295814611283581608613208990206581757576978017732022062210538697720930605552259306749633658032304554578427461842934055558865521604512892691323385156889995854702621568441768712619224249280792783364635307739215957762771386413831279443875185633720270001928747743847856394847878232194076679733830705297410959656270945532930199517880949
hint2 = 1345739841248959791137389026125065605121513428784838684290299665636596562317989590469829195181078904857051392378877013458099983407103737518119999468489762053545474516182879516762580472262640794849609626308003164739287189671066241628052826558582865342176036139097546843281565147798609965645514151827840249686650855385385323417455247722134760335695053787221300451942370377598800841980049138341564555801417479362085565640973199260631136149016266661293883650801813550118778433333591258278147003619871962070136454674193198696690506092831171400435490432196636796719177624389194619648086397178720207413652618636521150924913978530986709499047969775311955879302418093270101476537853298615347062384026172441455857088955847766335746521291043747795520485020303040819568036819058385444936925860671650596681910380157657689041971132993731048618045570715513584627109356139903842365556697314631573799394266292587334468008221427502353566938518574247502783245674619641519095644135976062817840893465238031354234069073928763492529419021632732679912738674105898149050223970723297059883534089683179512881491210176114419520070007595698242827625902377045860953285447617249204919971737086366

r = gcd(n, hint1)
pq = n // r
P.<x> = PolynomialRing(ZZ)
f = 9*x*(x-1)*n^2 + 6*x*n + 2 - 2*hint2
p_low = f.roots()[0][0]

P.<y> = PolynomialRing(Zmod(pq))
g = 2^400*y + p_low
g = g.monic()
res = g.small_roots(X=2^112, beta=0.4, epsilon=0.03)
p = 2^400*int(res[0]) + p_low
q = pq // p
phi = (p-1) * (q-1) * (r-1)

assert p*q*r == n
d = inverse(65537, phi)
m_pad = long_to_bytes(int(pow(c, d, n)))
m_xor = m_pad[:42]
# print(m_pad)

integral = lambda x: int(floor(2/3*(x^(3/2) - 3^(3/2))))
k = integral(n)
flag = strxor(long_to_bytes(k >> (k.bit_length() - 8 * flag_len)), m_xor)
print(flag)

数论题 #

hint2 = pow(2, 2023, Mod) #

https://tangcuxiaojikuai.xyz/post/39588.html


m = (m >> kbits) << kbits
Mod = getPrime(1024)
hint1 = (2021-2023*m) % Mod
hint2 = pow(2, 2023, Mod)
print('hint1 =',hint1)
print('hint2 =',hint2)

$$ hint2-KM=2^{2023} \ mod (M) $$

hint1 = ...
hint2 = ...
e = 3
kM = 2**2023-hint2

PR.<x> = PolynomialRing(Zmod(kM))
f = 2023*x + hint1 - 2021
f = f.monic()
roots = f.small_roots(X=2^200,beta=0.4)
if roots:
    mhigh = roots[0]

p1 = inverse(p,q) #

m

1 = bytes_to_long(flag1)
p = getPrime(512)
q = getPrime(512)
n = p*q
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)

p1 = gmpy2.invert(p,q)
q1 = gmpy2.invert(q,p)
c = pow(m1,e,n)

print("p1=",p1)
print("q1=",q1)
print("c=",c)
print("phi=",phi)

带点爆破

from Crypto.Util.number import *

#1
def gcd(a, b):
  while(b):
    a,b = b, a % b
  return a

def mysqrt(d):
  st = 1
  en = 10**1300
  while st<=en:
    mid = (st+en)//2
    if mid*mid == d: return mid
    if mid*mid < d: st=mid+1
    else: en=mid-1
  return -1

def egcd(a1, a2):
    x1, x2 = 1, 0
    y1, y2 = 0, 1
    while a2:
        q = a1 // a2
        a1, a2 = a2, a1 - q * a2
        x1, x2 = x2, x1 - q * x2
        y1, y2 = y2, y1 - q * y2
    return (x1, y1, a1)

flag = ""
ipmq= ...
iqmp= ...
phi= ...
e = 65537
enc = ...
d = inverse(e,phi)
gg = gcd(iqmp-1,ipmq-1)

c = phi // gg
a = (ipmq-1)//gg
b = (iqmp-1)//gg
# p*a + q*b = c
pmod = inverse(a, b)*c%b
for j in range(100000):
    p = pmod + j*b
    if p > (1<<1024): break
    if not isPrime(p): continue
    q = (c-p*a)//b
    assert(p*a+q*b==c)
    if (iqmp*q-1)%p == 0 and (ipmq*p-1)%q == 0:
        M = pow(enc,d,p*q)
        flag += str(long_to_bytes(M))[2:-1]
        break

hint = pow(2023*p + 114514, q, n) #

二项式

hint = pow(2023 * p + 114514, q, n)

$$ hint =2023p+k\ mod \ q\hint =114514^p\ =114514^{pq}\ mod \ q\ $$

$$ hint=114514^n\ +kp+tn \mod \ p\hint-14514^n=kp+0\ mod\ n $$

cnss 掩码剪枝收集 #

print(f'mask = {mask}')
print(p|mask)
print(p&mask)

from Crypto.Util.number import *

c = 64949799997326584007544788513993497249594769744995858720976935000014197232306799968807213667255871030075230919683627404813038995304033226711042639925325815395252041199650244620814678407788637241064396318107929964286966081900052163098825412222835465966640369222321472659135622216530966800717417560715221275591
n = 106750680418525866311589462967145265327203310954735134383588573660691518247034803380198999333962213971657327515092895034635965957228036264848532931376595751503164297061094511187060069380048933807326213369464059701069965785612620370291933800122445966488267918733547599024267999872488061941892122230382138042783
mask = 12270330408774238331968219216635392599519489634111741706590917012819298856158311310855782884352875794146685141255943386189197362902992928716839082520848927
gift1 = 13112112110892990771168306272793201342028151601627796725313855804865001339738164412798270175076178951452110894792943424133718769511979832250960465757056799
gift2 = 11731832079629748669705816329667815638461774924918417348984676937048335348013101619038697983623814812736529127108466295988845879378764866277739393693264401
e = 65537

strmask = bin(mask)[2:]
strgift1 = bin(gift1)[2:]
strgift2 = bin(gift2)[2:]

strp = []
for i in range(len(strmask)):
    if(strgift2[i] == "1"):
        strp.append("1")
    else:
        if(strgift1[i] == "1" and strmask[i] == "0"):
            strp.append("1")
        elif(strgift1[i] == "1" and strmask[i] == "1"):
            strp.append("0")
        else:
            strp.append("0")

p = int("".join(strp),2)
q= n//p
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

print(f'mask1 = {mask1}')
print(f'mask2 = {mask2}')
print(f'h1 = {p&mask1}')
print(f'h2 = {q&mask2}')

思路

&运算为1，则p该位必为1
&运算为0，mask该位为1，则p该位必为0

而当&运算为0，mask也为0时，p的该比特位就存在两种结果，无法完全确定。可是这题不仅给了p，还给了q的位运算结果，因此我们可以利用下面这一点信息，从高位向低位进行深度优先搜索，显著降低复杂度：

1、将p、q当前确定的二进制位后方全部填充0，直至填满512位，此时p、q乘积应小于n。

2、将p、q当前确定的二进制位后方全部填充1，直至填满512位，此时p、q乘积应大于n。

偷代码

h1[l] == "1") and (mask2[l] == "0" and h2[l] == "0")):
            find(p+"1",q+"0")
            find(p+"1",q+"1")
        elif((mask1[l] == "1" and h1[l] == "0") and (mask2[l] == "1" and h2[l] == "1")):
            find(p+"0",q+"1")
        elif((mask1[l] == "1" and h1[l] == "0") and (mask2[l] == "1" and h2[l] == "0")):
            find(p+"0",q+"0")
        elif((mask1[l] == "1" and h1[l] == "0") and (mask2[l] == "0" and h2[l] == "0")):
            find(p+"0",q+"1")
            find(p+"0",q+"0")

        elif((mask1[l] == "0" and h1[l] == "0") and (mask2[l] == "1" and h2[l] == "1")):
            find(p+"0",q+"1")
            find(p+"1",q+"1")
        elif((mask1[l] == "0" and h1[l] == "0") and (mask2[l] == "1" and h2[l] == "0")):
            find(p+"0",q+"0")
            find(p+"1",q+"0")
        elif((mask1[l] == "0" and h1[l] == "0") and (mask2[l] == "0" and h2[l] == "0")):
            find(p+"0",q+"0")
            find(p+"0",q+"1")
            find(p+"1",q+"0")
            find(p+"1",q+"1")

tempp = ""
tempq = ""

#find(tempp,tempq)
P = 10172774442863868719013872884099170294615753094066736187886125116462340120031133533430755779832487215255546434139069419394249074006281284289077492708469893
Q = 8580050824978592226795441601299432164577158891190171233964440597982925469924083252289609500726234367555160732119333211934059529993446003001925910065317613
phi = (P-1)*(Q-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

hint = sqrt(p) ^ sqrt(q) #

hint = sqrt(p) ^ sqrt(q)

https://tangcuxiaojikuai.xyz/post/795314c1.html

p*q、p^q 2 #

所以根据这个爆破一下p和q,n是4096位，p^q是2047位乘2是4094位显然p和q的最高位都是1异或值是0

n = 568511......
e = 65537
p_xor_q = 14888341604...
 
def getpq(p,q, i):
    if p*q > n:
        #print('A', i)
        return 
    tail = (1<<i)-1   #后i位置1
    if (p|tail)*(q|tail) < n:
        #print('B:', i, hex(p|tail), hex(q|tail))
        return 
    if p*q == n:
        print('p=',p)
        print('q=',q)
        return 
    i -= 1
    if p_xor_q & (1<<i) == 0:
        getpq(p^(1<<i), q^(1<<i), i)
        getpq(p,q,i)
    else:
        getpq(p^(1<<i), q, i)
        getpq(p,q^(1<<i),i)
        
print(n.bit_length(), p_xor_q.bit_length())  #4096 2047
import sys
sys.setrecursionlimit(3000)
  
getpq(3<<2046,1<<2047, 2046)