EZ_RSA_5

from Crypto.Util.number import *
import gmpy2
from secret import flag

m=bytes_to_long(flag)

p=getPrime(512)
q=getPrime(512)
e=65537
n=p*q

phi =(p-1)*(q-1)
p1 = gmpy2.invert(p,q)
q1 = gmpy2.invert(q,p)

c = pow(m,e,n)
P = pow(m,p,n)
Q = pow(m,q,n)
K=P*Q

phi_K=(P-1)*(Q-1)
d=inverse(e,phi_K)
dp=d%(P-1)

print("p1 =",p1)
print("q1 =",q1)
print("phi =",phi)
print('K = ',K)
print('dp = ',dp)

'''

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

'''

题目分析

题目相当于两个题目融在一起，一步步来分析

求p,q

题目给出了

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

通过这个证明

modular arithmetic - Why $\,p\, (p^{-1}!\bmod q) + q\,(q^{-1}!\bmod p) = pq + 1?$ - Mathematics Stack Exchange

可以得到

p1*q1=p*q+1

同时题目还给出了phi,这样我们就等于拥有n和phi了，我们目标并不是求私钥而是分解p,q所以可以通过韦达定理或者直接解方程的方式来求解，代码如下：

p,q = symbols("p q")
eq1 = Eq(p1 * p + q1 * q - (phi+p+q-1)- 1, 0)
eq2 = Eq(p * q, (phi+p+q-1))
sol = solve((eq1, eq2), (p, q))
print(sol)

求P

得到p,q后，我们发现P，Q是通过一个类似rsa加密得到的，同时题目给出了

K=P*Q
dp=d%(P-1)

这里就是一个典型的dp泄露了，存在

这里k和e数量级相近，我这里并未采用copper的方式，而是计算出k*(P-1)对其做一个因式分解，猜测出P

最后根据P的数量级以及与K求公因子来判断是否求出了P。

P=2*97*1607*76913*1396531*1919383*1395706600644157259974982648351255149930388215960739306052912331920433430679971552387679955894073493045723578902122326115948623883012881773788416937456910053347201243593983907897115831437365673123810949788457527954151891475615612988650185439616760227797557200145227951147074873449680289+1
print(P.bit_length())

print(GCD(P,K))

得到P我们就相当于得到明文了，这里直接对P做解密即可得到flag。

WP

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

p1 = 2636020992576559969055483957060200941734026828135579110378070592732862908176025649071069827089999996350015210043636523971348821850565913816154887832272305
q1 = 7886513101716991094728039196608717849158915101115291363845210343608904418304571443491051842715241903123031976527174063528298034452215971449949398656913945
phi = 115505961171763309547793530782914001823768056515083869218337105172209622283311582473506324170565971054492347897941697574972266679462737991988159654350224823122310342866537098903019067348499259894857405865405379172014292034138593409888061494667098647947191077373457924105640280156013690526621147715122416478264
K =  3995906172915513953882445609459153360257793100017419734812726991957587919349807133880917342081892953635338598486012480314014321088548439223094566668968735207492741920107799674089668131177188073985125603237341660194741854181484934968528811686828555591685803851909027192343245722679639249600176791158349393704697742640442010893811830528349203606514981272974154582682489532205008927740716725904614810707240205595586894383039181983075907373556864396176123489201513001026708388504250801785422323131912494763394371589512367935031912074535458595633402462463667072692589863355712935552396330534658448628449816139943205511637
dp =  53589538487289875479012684116246778147274714450209576105277816626983528993595125486641833027290704077932308918237978477501981907543847383655230156916578979044682282870153618849419762148348930652564442177633668690473147864322377146889467662769284463217004314651469157455678363085510100707437896627192687923547
e=65537
# p,q = symbols("p q")
# eq1 = Eq(p1 * p + q1 * q - (phi+p+q-1)- 1, 0)
# eq2 = Eq(p * q, (phi+p+q-1))
# sol = solve((eq1, eq2), (p, q))
# print(sol)
p=10314441767710606102937195215834089659678641178199945218290612694615948834633793866983953938981209335187624023708779675532856424652499590260914133511985373
q=11198469463791545278619772990550048972153411253872703306559384762341904625491585546901465814421769882976230432056883880344770707467660327961608441011384163
print(p.bit_length())
n=p*q

# print(e*dp-1)
#e*dp-1=k*(P-1) 网站分解一下排列组合下就能得到P-1
P=2*97*1607*76913*1396531*1919383*1395706600644157259974982648351255149930388215960739306052912331920433430679971552387679955894073493045723578902122326115948623883012881773788416937456910053347201243593983907897115831437365673123810949788457527954151891475615612988650185439616760227797557200145227951147074873449680289+1
print(P.bit_length())

print(GCD(P,K))

d=inverse(p,phi)
print(long_to_bytes(pow(P,d,n)))

# 2 * 7**2 * 17 * 47 * 97 * 1607 * 76913 * 1396531 * 1919383
# b'DASCTF{this_1s_crazy_Rsa}'

real_rsa_2

from Crypto.Util.number import getPrime, bytes_to_long
from random import randint
FLAG = b""
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 0x10001
a1=randint(0, 2**312)
a2=randint(0, 2**312)
a3=randint(0, 2**312)
b1=randint(0, 2**312)
b2=randint(0, 2**312)
b3=randint(0, 2**312)
x1=a1 * p + b1 * q
x2=a2 * p + b2 * q
x3=a3 * p + b3 * q
c = pow(bytes_to_long(FLAG), e, n)
print(n)
print(c)
print(x1,x2,x3)
# 10762816985859495139869192967586986169700585407650401758492914432007691215829829791170341055156952976765180258893167491520857418187717684546804091210840024146052291097940830614742073364552838290223328178129141450654974155663740167060363586046667418448000998787456156206763022665332848878718353207304752459866785987037244104966604168107428925002453961599326527075890562706405965932261029119740876890925151892381057306445871753182344654732310415856215026583156200205190290229513783502698870703593936084079889610093661632981253566737244298490483887491349685327054110713416608442026862452848911878315454050801737258113439
# 8447423691845267507910623881220381551666985692061130076228863364484545883136565538153853576456124232843440600389531458361591643000579120508101213567369995084232851488318213585166763995128971205060742692924173515480605390369108788114163397502997675308466114417550035850225404358223296655286051772334268473129000095354558509683438282602907669640723660576086897314122077227840018348574919569323961412521005657567879672836500813700075919902705930777791052105528663343979204155473143542923352804010273593743826083253263605472374027833649945128024719518687833938452374975314769405521418020888003402906733694105525873475248
#1037185901048299733994080148617255395054343048856247908410601987778479809878530408488320575174117338778636437390189707472850545495340030261432470823966833296599326227471363743571435638488350843501335163114522221236295887873384511904404076136719828753484908833522690485308801343692672087896916151728355339557063865979845334871596911380941183991996355328789626661832721727696996294542137065146082233136253 846732177805839592702453549495036743295384625187602625155533672143689218095451041579929817175558384214705957953439776505091441694232911111216302515231684660931114920885206001996415471667166302864276782382471749478878838743894218008585118570123564743506751263851346701898521514512630773037841739309871594639329517489797555801372814456505858967177535379362107863024397586339230559713504606369217391562005 1217849239241871953321322081958369125171815220222141431376710417230239975203684179024894356985970928925706068277775190791530588613770873433292421516394141880830700610067858856573183833274026726718793895096348188237821645080587133237246160317789656442199700812194023448514540614924352568135486220217732774487120710678057024335377334874015695483740444589213501325972313562358601186396370236713889278627191

题目分析

参考

一个RSA加密系统，题目给出的条件是关于p,q的，我们需要考虑通过给出的条件来分解p,q

这里给出的a,,b都是较小的，而p,q较大，我们目标就转向尝试求解a,b从而得到p,q。我们通过消除p,q可以得到

X的数量级大概在21024312bit 而三个a或b相乘数量级也就接近1024，有机会通过格来求解，这样我们就能得到一组结果

然后再通过等式关系即可尝试求解出a,b

WP

from Crypto.Util.number import *
from random import randint
from itertools import product, combinations


n=10762816985859495139869192967586986169700585407650401758492914432007691215829829791170341055156952976765180258893167491520857418187717684546804091210840024146052291097940830614742073364552838290223328178129141450654974155663740167060363586046667418448000998787456156206763022665332848878718353207304752459866785987037244104966604168107428925002453961599326527075890562706405965932261029119740876890925151892381057306445871753182344654732310415856215026583156200205190290229513783502698870703593936084079889610093661632981253566737244298490483887491349685327054110713416608442026862452848911878315454050801737258113439
c=8447423691845267507910623881220381551666985692061130076228863364484545883136565538153853576456124232843440600389531458361591643000579120508101213567369995084232851488318213585166763995128971205060742692924173515480605390369108788114163397502997675308466114417550035850225404358223296655286051772334268473129000095354558509683438282602907669640723660576086897314122077227840018348574919569323961412521005657567879672836500813700075919902705930777791052105528663343979204155473143542923352804010273593743826083253263605472374027833649945128024719518687833938452374975314769405521418020888003402906733694105525873475248

h1=1037185901048299733994080148617255395054343048856247908410601987778479809878530408488320575174117338778636437390189707472850545495340030261432470823966833296599326227471363743571435638488350843501335163114522221236295887873384511904404076136719828753484908833522690485308801343692672087896916151728355339557063865979845334871596911380941183991996355328789626661832721727696996294542137065146082233136253
h2=846732177805839592702453549495036743295384625187602625155533672143689218095451041579929817175558384214705957953439776505091441694232911111216302515231684660931114920885206001996415471667166302864276782382471749478878838743894218008585118570123564743506751263851346701898521514512630773037841739309871594639329517489797555801372814456505858967177535379362107863024397586339230559713504606369217391562005
h3=1217849239241871953321322081958369125171815220222141431376710417230239975203684179024894356985970928925706068277775190791530588613770873433292421516394141880830700610067858856573183833274026726718793895096348188237821645080587133237246160317789656442199700812194023448514540614924352568135486220217732774487120710678057024335377334874015695483740444589213501325972313562358601186396370236713889278627191
hints=(h1,h2,h3)
L = matrix(hints).T.augment(matrix.identity(3))
L[:, 0] *= n
L = L.LLL()
for v in L:
    print(v)
    print([int(x).bit_length() for x in v])

# the expected vector is (a1*a3*b1-a1*a2*b3, -a1*a3*b1+a1**2*b3, a1*a2*b1-a1**2*b2)
# but we can see that a1 divides all of them
# assuming gcd(gcd((a1*a3*b2-a1*a2*b3), (-a1*a3*b1+a1**2*b3)), (a1*a2*b1-a1**2*b2)) == 1 here
# the shortest vector should be (a3*b2-a2*b3, -a3*b1+a1*b3, a2*b1-a1*b2)

_, t, u, v = L[0]
# therefore this should hold
# assert abs(a3*b2 - a2*b3) == abs(t)
# assert abs(a3*b1 - a1*b3) == abs(u)
# assert abs(a2*b1 - a1*b2) == abs(v)
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}

insecure_padding

from Crypto.Util.number import *



assert flag[:7]==b'DASCTF{' and flag[-1:]==b'}'
flag = flag[7:-1]
assert len(flag) == 20


def my_rsa_padding(m):
    e = 3
    p = getPrime(1024)
    q = getPrime(512)
    n = p*q
    pad = long_to_bytes(777*p+666)
    m = bytes_to_long(m+pad)
    assert m < n
    c = pow(m, e, n)
    return c, e, n, len(pad)


print(my_rsa_padding(flag))
#(1193333119181381225632504634109476125461718042032463066180160159530821008151288619914035008577444580123023483451618973104785206841878926362053767758825420307104536873166791566346076985369125399199847240472385775854381103486198612767122009780041785220241663307760491699892303259600093817957324293717178123893664313547870460181936283477289029428950611459484805364390503487619676794166358047636359524103138509752217552291498141048509236471615548177017684230320627457, 3, 1345974903151028106176188777499919289689885052993818155551239513162986365479059645712347472719763678799888312063629534224676532524320490059299999431455806985776161385636341889882617880557005343019148419971407438285456200388681742721058826527478752200546957229924712840178042652788689761602760552457535667154424045780264689394678280189407534443469304768432295723527834457536647823320807747766083091825227699222804959851169910812454526260545186908048603618547346519, 130)

题目分析

这里rsa中明文做了pad所以使得其无法直接通过开方来得到flag。这里可以注意到e很小，同时q也反常的设置成了比p小。那么我们就可以观察给出的密文

既然p比q大那么我们就把p转成q，这样我们就得到

再消元就可以得到

我们就可以设置m为未知数数量级为160bit，就算是三次方也还是可接受范围，然后就可以copper求解出flag了

WP

c, e, n, len=(1193333119181381225632504634109476125461718042032463066180160159530821008151288619914035008577444580123023483451618973104785206841878926362053767758825420307104536873166791566346076985369125399199847240472385775854381103486198612767122009780041785220241663307760491699892303259600093817957324293717178123893664313547870460181936283477289029428950611459484805364390503487619676794166358047636359524103138509752217552291498141048509236471615548177017684230320627457, 3, 1345974903151028106176188777499919289689885052993818155551239513162986365479059645712347472719763678799888312063629534224676532524320490059299999431455806985776161385636341889882617880557005343019148419971407438285456200388681742721058826527478752200546957229924712840178042652788689761602760552457535667154424045780264689394678280189407534443469304768432295723527834457536647823320807747766083091825227699222804959851169910812454526260545186908048603618547346519, 130)
print(int(n).bit_length())
R.<x> = PolynomialRing(Zmod(n))
f=(2^(8*len)*x+666)^3-c
f=f.monic()
res=f.small_roots(X=2^160,beta=0.45)
print(res)
#P@dding_1s_important