2022 DSCTF

picproblem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
from PIL import Image
from Crypto.Util.number import *
from numpy import array, zeros, uint8
import gmpy2 as gp
import cv2
from key import x,y,kn,hint
image = cv2.imread("flag.jpg")
img_gray = cv2.cvtColor(image,cv2.COLOR_RGB2GRAY)
imagearray = array(img_gray)
h = len(imagearray)
w = len(imagearray[0])

assert 1301149798051259562945444365741194129602596348352064372203373*pow(x, 2) == 1175915431138623881271508290982969935822476052419526528443170552123*pow(y, 2) + 1301149798051259562945444365741194129602596348352064372203373
x1 = round(x/y*0.001, 16)
u1 = y*3650/x
x2 = round(x/y*0.00101, 16)
u2 = y*3675/x
x3 = round(x/y*0.00102, 16)
u3 = y*3680/x
kt = [x1, x2, x3]

temp_image = zeros(shape=[h, w, 3], dtype=uint8)
print(len(temp_image))
print(len(temp_image[0]))
print(len(temp_image[0][1]))
for k in range(0, kn):
    for i in range(0, h):
        for j in range(0, w):
            x1 = u1 * x1 * (1 - x1)
            x2 = u2 * x2 * (1 - x2)
            x3 = u3 * x3 * (1 - x3)
            r1 = int(x1*255)
            r2 = int(x2*255)
            r3 = int(x3*255)
            for t in range(0, 3):
                temp_image[i][j][t] = (((r1+r2) ^ r3)+imagearray[i][j][t]) % 256
    x1 = kt[0]
    x2 = kt[1]
    x3 = kt[2]

encflagarray = Image.fromarray(temp_image)
encflagarray.show()
encflagarray.save("encflag.jpg")
#************************************hint**************************************
m = hint
p = getPrime(512)
q = getPrime(512)
n = p * q
e = 65537
phi = (p-1)*(q-1)
dp = gp.invert(e, p-1)
c = pow(m, e, n)
#n =  85413323752199019806030766630760449394238054889872415531186815348349883843039718091361611175963675771467536496812507338620957273406076058263122453235926619595761737396698699834116678598534261542535530241537247151318756003375573850725841254167462648747492270335084402716816450008370008491069875351593380154253
#dp =  1576424214336939000475035870826282526256046059505538052583882122452307602095912733650442447289122473348318614749578285418144935611098423641334952097553125
#c =  53653254613997095145108444611576166902006080900281661447007750088487109015427510365774527924664116641019490904245926171500894236952984157500461367769566121581870986304353174732328118576440353500038670030097108081972287049673200783198844842527470746431369314585103203118824985764754487936404004696485346196488

hint部分求解简单，代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import libnum
e = 65537
n =  85413323752199019806030766630760449394238054889872415531186815348349883843039718091361611175963675771467536496812507338620957273406076058263122453235926619595761737396698699834116678598534261542535530241537247151318756003375573850725841254167462648747492270335084402716816450008370008491069875351593380154253
dp =  1576424214336939000475035870826282526256046059505538052583882122452307602095912733650442447289122473348318614749578285418144935611098423641334952097553125
c =  53653254613997095145108444611576166902006080900281661447007750088487109015427510365774527924664116641019490904245926171500894236952984157500461367769566121581870986304353174732328118576440353500038670030097108081972287049673200783198844842527470746431369314585103203118824985764754487936404004696485346196488
pd = e*dp-1

def ext_euclid(a, b):
    if b == 0:
        return 1, 0, a
    else:
        x, y, q = ext_euclid(b, a % b)
        x, y = y, (x - (a // b) * y)
        return x, y, q

def mod_inv(a, b):
    return ext_euclid(a, b)[0] % b   #函数返回的第一个数%b

for i in range(1,e):
    if pd % i == 0:
        if n % (pd//i+1) == 0:
            p = pd//i+1
            q = n//p
            fn = (p-1)*(q-1)
            d = mod_inv(e,fn)
            m = pow(c,d,n)
            print(libnum.n2s(m))
#b'*********** kn = 8 **************'

找到相关文章：Logistic映射在图像加密中的应用-爱代码爱编程 (icode.best)

但差解x,y的方程。x，y的方程化简如下：
$$
x^2 = 903751*y^2 + 1
$$
查阅发现是Pell 方程 (oi-wiki.org)，利用连分数对其求解：

1
2
3
4
5
6
7
8
9
10
11
12
def Pell(D):
    temp = continued_fraction(sqrt(D))
    i=0
    while True:
        i+=1
        denom = temp.denominator(i)
        num = temp.numerator(i)
        if num^2 - D*denom^2 == 1:
            return num,denom

Pell(903751)
#(1524993807674193841904821512553946379967374698278296055158206699585083472817489721493862711615915407326315660670541801753616900039772802728925226091475860689682871555641241500183892397513037971186709123629077584204226084524811673794984687840178772052545441242927492902583547355565525538664836516589721942980577095421561886873928634330640979800040574060218872787212426630202508118484269553983399179155489583316400107655564222453437462724749097265122300644936717434151331633092585140183510349369422527440264746843972834927860065578557836150798690530172694679514231722613822246810010130005324032492360889531553803832398604563088256410481865243771216990603166993198935358471831328395618477974126824762560872337594997394218234427050399655270848385995088586420526886397320949350980406936200217112040971433660322179072288438842964957568719036794320203116263329623589339367497303140938070334557345834226085189140858264388063745189833584962825509843279678826240558480527560, 1604145232044543633656616254647708451166351104281510395737885491696385806407267633308545985473789119651681711082023113933085624628557168423578747544761597312012713558891523798820667618256495398479378172124019360339427592449217208805888502769358288779859969965560832505104388955091637704481336716722418336373334467787371085728212260231330510705797124224353810509272250940285165605853594811893804251478850270703294638335268305881655491870226553141286503109543313414279220480589704210363277523457948607498351377843904335637032510420141505975997452077477296326035048463179997347136990808017374750824810458605412236391952910679246288287664717533857743462935708681309073915761377477454479206054016260422865457862565353002789887917196437750618212918420129464330488021272187952177063175896447842395209693304502304253471733746765257510395226972224876277717457205220726240042035259947453816668460757995771018155703600926745905595162857982860955545877343914746294034180707)

最后解密

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
from PIL import Image
import cv2
from numpy import array, zeros, uint8

image = cv2.imread("encflag.jpg")
imagearray = array(image)
print(imagearray.shape)
h = len(imagearray)#35
w = len(imagearray[0])#261

def decrypt(img,key):
    # 混沌系统初始条件
    x1 = key[0]
    x2 = key[1]
    x3 = key[2]
    # 分岔参数u
    u1 = key[3]
    u2 = key[4]
    u3 = key[5]
    # 加密次数
    n = key[6]
    # 一个临时数组用于返回加密后的图像，可以不影响传入的加密图像
    img_tmp = zeros(shape=[h, w, 3], dtype=uint8)
    for k in range(0, n):
        for i in range(0, h):
            for j in range(0, w):
                x1 = u1 * x1 * (1 - x1)
                x2 = u2 * x2 * (1 - x2)
                x3 = u3 * x3 * (1 - x3)
                r1 = int(x1 * 255)
                r2 = int(x2 * 255)
                r3 = int(x3 * 255)
                for t in range(0, 3):
                    img_tmp[i][j][t] = (img[i][j][t] - ((r1 + r2) ^ r3)) % 256
        x1 = key[0]
        x2 = key[1]
        x3 = key[2]
    return img_tmp


x, y = (1524993807674193841904821512553946379967374698278296055158206699585083472817489721493862711615915407326315660670541801753616900039772802728925226091475860689682871555641241500183892397513037971186709123629077584204226084524811673794984687840178772052545441242927492902583547355565525538664836516589721942980577095421561886873928634330640979800040574060218872787212426630202508118484269553983399179155489583316400107655564222453437462724749097265122300644936717434151331633092585140183510349369422527440264746843972834927860065578557836150798690530172694679514231722613822246810010130005324032492360889531553803832398604563088256410481865243771216990603166993198935358471831328395618477974126824762560872337594997394218234427050399655270848385995088586420526886397320949350980406936200217112040971433660322179072288438842964957568719036794320203116263329623589339367497303140938070334557345834226085189140858264388063745189833584962825509843279678826240558480527560, 1604145232044543633656616254647708451166351104281510395737885491696385806407267633308545985473789119651681711082023113933085624628557168423578747544761597312012713558891523798820667618256495398479378172124019360339427592449217208805888502769358288779859969965560832505104388955091637704481336716722418336373334467787371085728212260231330510705797124224353810509272250940285165605853594811893804251478850270703294638335268305881655491870226553141286503109543313414279220480589704210363277523457948607498351377843904335637032510420141505975997452077477296326035048463179997347136990808017374750824810458605412236391952910679246288287664717533857743462935708681309073915761377477454479206054016260422865457862565353002789887917196437750618212918420129464330488021272187952177063175896447842395209693304502304253471733746765257510395226972224876277717457205220726240042035259947453816668460757995771018155703600926745905595162857982860955545877343914746294034180707)
assert 1301149798051259562945444365741194129602596348352064372203373*pow(x, 2) == 1175915431138623881271508290982969935822476052419526528443170552123*pow(y, 2) + 1301149798051259562945444365741194129602596348352064372203373
x1 = round(x/y*0.001, 16)
u1 = y*3650/x
x2 = round(x/y*0.00101, 16)
u2 = y*3675/x
x3 = round(x/y*0.00102, 16)
u3 = y*3680/x
kn = 8
kt = [x1, x2, x3, u1, u2, u3, kn]
print(kt)
temp_image = decrypt(imagearray, kt)
flagarray = Image.fromarray(temp_image)
flagarray.show()
flagarray.save("flag.jpg")

RSA330

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
alarm(10)
PoWp = random_prime(2^100)
PoWq = random_prime(2^100)
PoW = int(input(f"Factor {PoWp*PoWq}:\n"))
assert PoW == PoWp + PoWq

alarm(60)
se = int(input("plz select the size of e: "))
assert se > 16 and se < 1024

while True:
    p = random_prime(2^512)
    q = random_prime(2^512)
    e = ZZ.random_element(2^(se-1),2^se)
    if gcd(e, (p-1)*(q-1)) == 1:
        break
        
print(e, e.inverse_mod(p-1)>>330, e.inverse_mod(q-1)>>330)
pq = int(input(f"RSA330 - {p*q}:\n"))
assert pq == p + q

print(open("flag.txt").read())

sage中有大数分解的函数，牛哇！

1
2
3
qsieve(184378666276085226424026508072440771590659834511908100578309)#
factor(184378666276085226424026508072440771590659834511908100578309)#所有素数
divisors(184378666276085226424026508072440771590659834511908100578309)#所有因数

参考论文：[Approximate Divisor Multiples](271.pdf (iacr.org))

根据论文，选取$e>N^{\dfrac{1}{12}}$，即$e.bit_length()>85.333$。

构造上述A可以得到k*l，然后对等式(5)对e取余得到：
$$
k+l = 1-kl(N-1)\quad mod\ e
$$
得到k+l，解方程 $(x-k)(x-l)=0$ 可以求出k,l。

利用Howgrave-Graham定理，构建如下格：

其中每行为 $g_i(x) := f^i(x)k^{m-i}N^{max(0,t-i)}$ ，$f(x):=x+a$，$f(x)$的构造过程如下

也就是将 域为kp上的待解方程$f = e(dp^{(M)}*2^{330}+x)+k-1$ （其中 $x = dp^{(L)}$ ）的未知数的系数化为1（f.monic()）就得到了。

用待求得范围($2^{330}$)先代替$x$进行LLL()，再替换回来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
def C(a,b):
    ret = 1
    for i in range(b):
        ret*=(a-i)
        ret/=(b-i)
    return ret

def dec(e,dp,k,n):
    m,t=20,10
    P = Zmod(k*n)['x']
    x = P.gen()
    f = e*(dp+x) - 1 + k
    f = f.monic()
    f = f.change_ring(ZZ)
    a = list(f)[0]#常数a
    L=matrix(ZZ,m+1,m+1)
    for i in range(m+1):
        for j in range(i+1):
            L[i,j] = k^(m-i)*n^max(0,t-i)*C(i,j)*pow(a,i-j)*pow((1<<330),j)
    L = L.LLL()
    P = ZZ['y']
    y = P.gen()
    for i in range(m+1):
        for j in range(m+1):
            L[i,j]=L[i,j]//pow(1<<330,j)#矩阵并不能直接乘pow(y,j)，但取其行，对其中每一列可以操作
    
    L = L*vector([y^i for i in range(m+1)])#对应多个多项式方程
    for i in L:
        r = i.roots()
        if len(r) > 0:
            #print(r)
            return int(r[0][0]+dp)

e = 715817461603291345056500257 
dpm = 443241367152182375089742080168879750401826010196673998 
dqm = 976237271910199872999512149615932692866377555493664771
n = 27691523316352200817507757939445581338449495137376447632107748594499386764483747774332325018477605530261133431823935050480971625479504155045304870831284969481372795315373409317596161046086158910790777312868535076795758303488626394277433645375132000508031171867198231228726163618498261234493051930360826747417
kbits = 330
A = (2^(2*kbits)*e^2*dpm*dqm)//n + 1
b = (1 - A*(n-1))%e
delta = b^2 - 4*A
if delta > 0:
    assert sqrt(delta)^2 == delta
    k = (b+sqrt(delta))//2
    l = (b-sqrt(delta))//2
    print(f'k = {k}')
    print(f'l = {l}')

result = [dec(e,dpm<<kbits,k,n),dec(e,dqm<<kbits,l,n),dec(e,dpm<<kbits,l,n),dec(e,dqm<<kbits,k,n)]
print(result)
dp = result[2]
dq = result[3]
p = (e*dp-1)//l+1
q = (e*dq-1)//k+1
assert n == p*q
print(f'p = {p}')
print(f'q = {q}')

参考：

Logistic映射在图像加密中的应用-爱代码爱编程 (icode.best)

Pell 方程 (oi-wiki.org)

[Approximate Divisor Multiples](271.pdf (iacr.org))

2022DSCTF-wp (qq.com)

Crypto
#Pell #RSA #LLL #Logistic
2022 DSCTF
http://example.com/2022/07/19/CTF/2022-dsctf/
作者
gla2xy
发布于
2022年7月19日
许可协议