糖醋小鸡块的blog
0%

2023-浙江省赛决赛-wp-crypto

发表于 更新于 分类于 Valine：

有师傅问了几个题，就做了做。

R_r

题目：

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
from Crypto.Util.number import *
import random
from gmpy2 import *
from secret import flag1,flag2

flag = flag1 + flag2

p = getPrime(256)
q = getPrime(256)
n= p*q
hint1 = p^2*q
hint2 = p*q^2

while True:
    g1 = random.randint(1, n*n)
    if gcd((g1-1)//n, n) == 1:
        break

g2=n+1

m1 = bytes_to_long(flag1)
m2 = bytes_to_long(flag2)

while True:
    r1 = random.randint(1, n-1)
    if(gcd(r1,n) == 1):
        break

r2=random.randint(1,n)

c1 = (pow(g1, m1, n*n) * pow(r1, n, n*n))% (n*n)
c2 = (pow(g2 ,m2, n*n) * pow(r2, n, n*n))% (n*n)

print(c1)
print(c2)

"6401013954612445818165507289870580041358569258817613282142852881965884799988941535910939664068503367303343695466899335792545332690862283029809823423608093"
"22910385210568304958107161962017571071703393748261640924342214385124480716797688566364653958202687496536914575643833029904856616616361552065618233346044007555777302010059956180989299881167620123404157184856914845192870935052388587836639109148835943673531131160427033530692003589837535181715398419950146539295"
"1575524821989347564982343787894614774971961408914047143111430998332905514952763763178813184329394269351923009990561408822591722869938177600916108444223304303415189694914099273457779531528733347451404048342144363056595763890310306908442288806184110971228621297398433865511027539993213883705000977616240346813"
"17972230632127848019159546735961788940716048105141697301143941156703842346042203282817931551107307709193702947228391512160043387022559315244264272847054598619204201233617960636207483484678274743413667794843966312743641773413722257484289905138257413051485362435527999048370294082815591234891288108779292951281"
"6401013954612445818165507289870580041358569258817613282142852881965884799988781523237008972618187818067224685481215653712129336192028926158248667825733199"
"6401013954612445818165507289870580041358569258817613282142852881965884799988781523237008972618187818067224685481215653712129336192028926158248667825732455"

题目数据给的有点迷，做完过后依次解释一下从上到下每个参数是什么：

1
2
3
4
5
6
n = 6401013954612445818165507289870580041358569258817613282142852881965884799988941535910939664068503367303343695466899335792545332690862283029809823423608093
c1 = 22910385210568304958107161962017571071703393748261640924342214385124480716797688566364653958202687496536914575643833029904856616616361552065618233346044007555777302010059956180989299881167620123404157184856914845192870935052388587836639109148835943673531131160427033530692003589837535181715398419950146539295
c2 = 1575524821989347564982343787894614774971961408914047143111430998332905514952763763178813184329394269351923009990561408822591722869938177600916108444223304303415189694914099273457779531528733347451404048342144363056595763890310306908442288806184110971228621297398433865511027539993213883705000977616240346813
g1 = 17972230632127848019159546735961788940716048105141697301143941156703842346042203282817931551107307709193702947228391512160043387022559315244264272847054598619204201233617960636207483484678274743413667794843966312743641773413722257484289905138257413051485362435527999048370294082815591234891288108779292951281
hint1 = 6401013954612445818165507289870580041358569258817613282142852881965884799988781523237008972618187818067224685481215653712129336192028926158248667825733199
hint2 = 6401013954612445818165507289870580041358569258817613282142852881965884799988781523237008972618187818067224685481215653712129336192028926158248667825732455

然后回到题目，他将flag分为两部分分别加密，不过加密形式都是：

这是Paillier同态加密的特征，可以参考：

应用密码学 | Paillier同态加密算法简介 - 知乎 (zhihu.com)

那么只要我们有n的分解，就有这个加密的私钥，进而解密。然后这里其实出题人弄的数据有点问题，hint1、hint2并不是按题目代码中给的方式进行计算的，而均是先计算异或再计算乘，也就是：

所以其实将hint与n求gcd就能得到n的分解，然后代入Paillier解密就可以了。而如果是按题目代码的顺序运算得到hint1、hint2的话，预期应该是用hint1进行深搜。

exp：

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
from Crypto.Util.number import *
from gmpy2 import *

n = 6401013954612445818165507289870580041358569258817613282142852881965884799988941535910939664068503367303343695466899335792545332690862283029809823423608093
c1 = 22910385210568304958107161962017571071703393748261640924342214385124480716797688566364653958202687496536914575643833029904856616616361552065618233346044007555777302010059956180989299881167620123404157184856914845192870935052388587836639109148835943673531131160427033530692003589837535181715398419950146539295
c2 = 1575524821989347564982343787894614774971961408914047143111430998332905514952763763178813184329394269351923009990561408822591722869938177600916108444223304303415189694914099273457779531528733347451404048342144363056595763890310306908442288806184110971228621297398433865511027539993213883705000977616240346813
g1 = 17972230632127848019159546735961788940716048105141697301143941156703842346042203282817931551107307709193702947228391512160043387022559315244264272847054598619204201233617960636207483484678274743413667794843966312743641773413722257484289905138257413051485362435527999048370294082815591234891288108779292951281
hint1 = 6401013954612445818165507289870580041358569258817613282142852881965884799988781523237008972618187818067224685481215653712129336192028926158248667825733199
hint2 = 6401013954612445818165507289870580041358569258817613282142852881965884799988781523237008972618187818067224685481215653712129336192028926158248667825732455
g2 = n+1

p = GCD(n,hint2)
q = n// p


#part1
lamda = lcm(p-1,q-1)
def L(x):
	return (x-1)//n

miu = inverse(L(pow(g1,lamda,n**2)),n)
b = gmpy2.powmod(c1,lamda,n*n)
m1 = (L(b)*miu) % n
print(str(long_to_bytes(m1))[2:-1],end = "")


#part2
r2 = pow(c2,inverse(n,(p-1)*(q-1)),n)
r2n = pow(r2,n,n**2)
m2 = (((c2*inverse(r2n,n**2) % n**2) - 1) // n )% n
print(str(long_to_bytes(m2))[2:-1])

#DASCTF{a59055ff-0a22-641d-2bf2-7b0b69c2244b}



0_1_Game

题目：

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
from Crypto.Util.number import *
from secret import flag

p = getPrime(512)
q = getPrime(512)
n = p * (q**2)

s = 65537

hint1 = pow((p+q), s, n)
hint2 = pow((p-q), s, n)



while True:
    z = getRandomRange(1, n - 1)
    if pow(z, (p-1)//2, p) == p-1 and pow(z, (q-1)//2, q) == q-1:
        break


def secert_0_1_encrypt(m, n, z):
    secret = getRandomRange(1, n - 1)
    c = pow(secret, 2, n) * pow(z, m, n) % n
    return c

m = bytes_to_long(flag)
plaintext = int(bin(int(m))[2:])
ciphertext = [0] * len(str(plaintext))
for i in range(len(str(plaintext))):
    ciphertext[i] = secert_0_1_encrypt(plaintext % 10, n, z)
    plaintext = plaintext // 10


print("n=", n)
print("hint1", hint1)
print("hint2", hint2)
print("z=", z)
print("ciphertext", ciphertext)

首先给了两个hint：

那么二项式展开就有：

相加后与n求gcd即可得到n的分解。

然后进入下一部分，首先他按如下方式生成了z：

1
2
3
4
while True:
    z = getRandomRange(1, n - 1)
    if pow(z, (p-1)//2, p) == p-1 and pow(z, (q-1)//2, q) == q-1:
        break

这里其实就是用欧拉判别式保证：

也就是说，z既不是模p下的二次剩余，也不是模q下的二次剩余。

然后，他将flag转换成二进制串，并把这个二进制串视为一个十进制数，然后对每一位逐位加密。也就是说这个十进制串的每一位都是0或1，逐位加密的方式如下，每一十进制位记作mi：

然后由于我们有了n的分解，我们将这个式子转化到模p下(模q下也一样)：

那么，当mi等于0和等于1时，cipheri分别是：

而由于z不是模p下的二次剩余，所以当mi分别为0和1时，cipheri分别是\不是二次剩余。因此我们可以用欧拉判别式来判断cipheri是不是二次剩余，以此来还原每一位mi：

或：

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
from cipher import *
from gmpy2 import *

p = GCD(hint1 + hint2,n)
q = iroot(n // p , 2)[0]

flag = ""
for i in ciphertext:
    if(pow(i,(p-1)//2,p) == 1):
        flag += "0"
    else:
        flag += "1"
print(long_to_bytes(int(flag[::-1],2)))

#DASCTF{5e1eddfb-dda2-11ed-8d28-ac675d4bad}



odd_factor

题目：

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
from Crypto.Util.number import *
from flag import flag
import random

m = bytes_to_long(flag)
assert size(m)<360

while True:
    p = getPrime(512)
    q = getPrime(512)
    r = getPrime(512)
    s = getPrime(512)
    t = getPrime(512)
    real_p = p * q * r * s * t
    real_q = p + q + r + s + t
    if isPrime(real_q) == True:
        n = real_p * real_q
        break

e=65537
c=pow(m,e,n)

print('real_p=',real_p)
print('real_q=',real_q)

print('c=',c)

'''
real_p= 55062197317446999463174096263876498316593115551165463378239159905809676640454208209918217385995561457672251651152473557992138742135601815169185076218362135899344751677854110957095631491941800392408438811446405332089775007801060526398896827361974179433880944797942088556569121442758603066960469154848058525555919633585074687002653178371734389317920858433073228324119903275748010661381766238387457768079481851583182446632335485869275973875534654769410510717692168386489418039967948185844825093846853624216235947670855966394462382073931422900372413115651622846475697848013017412006570314438593706146398436291246626158990758006393615755523796444561949003170112244508437710660501492796759763772367048031312446027160494843576151592257914618405347047042441934740949960412334441
real_q= 45155472176560032394858410670734933043941707240560969397865820853107208563396632699891831616425752109128199454680206954866754585433276759685964959793491769
c= 29523353286662420447288429739820034783180593797609319451802397100630230980492429018460170953928563500202582346942199142197785013588760361998950680313834852877108490792872966526015601050884302042018430083206594510237759312983601611859463798190030017950871533501858080631812335748118077560727632343411246129300608114305005550505334558174100631528820258311294104339625598892394650057151595693208992748213949675232397315855876112627150056755058037371576593415880216272977089381300018893299243081150404742921857440064511032025713772327330252031889227225225823090259315491541462395033093742723528280894218885823268632726414223235862198062147879817814619506196476372010238569022037192794906574876350397747710442236263832960264742898816690984736558117232240584876068441918457179310704845718452829124188403042383896118962087518608022867798693371250897927956711708162621772577123078819978462483151316840145260542738057960771219011604
'''

有点幽默的题目，注意到题目中保证了：

1
size(m)<360

那么其实直接在模realq下解明文就行。

exp：

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *

real_p= 55062197317446999463174096263876498316593115551165463378239159905809676640454208209918217385995561457672251651152473557992138742135601815169185076218362135899344751677854110957095631491941800392408438811446405332089775007801060526398896827361974179433880944797942088556569121442758603066960469154848058525555919633585074687002653178371734389317920858433073228324119903275748010661381766238387457768079481851583182446632335485869275973875534654769410510717692168386489418039967948185844825093846853624216235947670855966394462382073931422900372413115651622846475697848013017412006570314438593706146398436291246626158990758006393615755523796444561949003170112244508437710660501492796759763772367048031312446027160494843576151592257914618405347047042441934740949960412334441
real_q= 45155472176560032394858410670734933043941707240560969397865820853107208563396632699891831616425752109128199454680206954866754585433276759685964959793491769
c= 29523353286662420447288429739820034783180593797609319451802397100630230980492429018460170953928563500202582346942199142197785013588760361998950680313834852877108490792872966526015601050884302042018430083206594510237759312983601611859463798190030017950871533501858080631812335748118077560727632343411246129300608114305005550505334558174100631528820258311294104339625598892394650057151595693208992748213949675232397315855876112627150056755058037371576593415880216272977089381300018893299243081150404742921857440064511032025713772327330252031889227225225823090259315491541462395033093742723528280894218885823268632726414223235862198062147879817814619506196476372010238569022037192794906574876350397747710442236263832960264742898816690984736558117232240584876068441918457179310704845718452829124188403042383896118962087518608022867798693371250897927956711708162621772577123078819978462483151316840145260542738057960771219011604
e = 65537

d = inverse(e,real_q-1)
print(long_to_bytes(pow(c,d,real_q)))

#DASCTF{b4920de4-9b76-9222-1bc4-ae05a6714ce6}