Contents

闲题杂记

[toc]

gkctf2021 6-25 补档

XOR

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
from hashlib import md5

a = getPrime(512)
b = getPrime(512)
c = getPrime(512)
d = getPrime(512)
d1 = int(bin(d)[2:][::-1] , 2)
n1 = a*b
x1 = a^b

n2 = c*d
x2 = c^d1
flag = md5(str(a+b+c+d).encode()).hexdigest()
print("n1 =",n1)
print("x1 =",x1)
print("n2 =",n2)
print("x2 =",x2)

这个题基本是靠约束条件对多余情况进行剪枝,捡到运算量在合理范围就可以了

顺序不变时只需要考虑低位,除开异或条件外还计 算 $a*b =n;mod;2^{i}-1$ 来对已猜测数据进行低位检测

这是一种模糊的条件,该条件是最终条件的必要条件


顺序改变的情况,异或需要考虑高低位交换的情况,每次要四个bit同时运算看是否同时满足 n的高位和低位

乘法条件中,低位由于没有进位,直接判断$a*b =n;mod;2^{i}-1$

高位由于又进位,使用高位相同时的必要条件if n_highbits-temp2 >= 0 and n_highbits-temp2 <=((2<<i+1)-1):

a = 111

b = 100

a*a = 1 1000 1

b*b = 010000

当然,这依旧是一个十分粗略的必要条件。。。。

正序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
34
35
36
37
38

# 初始化第1位的已知数:0
def getab(n,x,lenth):
    a_list=[0]
    b_list=[0]
    # 这里判断512位应该就够了阿。。。。
    mask = 0
    for i in range(lenth):
        # 取第n位
        mask = 2**(i+1)-1
        xi = (x>>i) & 1
        nextA_list=[]
        nextB_list=[]
        
        for ai in range(2):
            for bi in range(2):
                for j in range(len(a_list)):
                    if (ai^bi == xi):
                        nlow = n & mask
                        axbLow = (((ai<<i)+a_list[j])*((bi<<i)+b_list[j]))&mask
                        if(nlow==axbLow):
                            nextA_list.append((ai<<i)+a_list[j])
                            nextB_list.append((bi<<i)+b_list[j])
        # 
        a_list = nextA_list
        b_list = nextB_list

    for a in a_list:
        if(n%a==0):
            return(a,n//a)

lenth = 512

n = 83876349443792695800858107026041183982320923732817788196403038436907852045968678032744364820591254653790102051548732974272946672219653204468640915315703578520430635535892870037920414827506578157530920987388471203455357776260856432484054297100045972527097719870947170053306375598308878558204734888246779716599
x = 4700741767515367755988979759237706359789790281090690245800324350837677624645184526110027943983952690246679445279368999008839183406301475579349891952257846
a,b = getab(n,x,lenth)
from icecream import *
ic(a,b)

倒序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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
def get_cd(n,x,lenth): 
	p_low = [0] 
	q_high = [0]
	q_low = [0] 
	p_high = [0] 
	# maskn = 2
	maskn  = 0
	for i in range(lenth//2): 
		maskn = 2**(i+1)-1
		xi = (x >> i )&1
		n_lowbits = (n & maskn) 
		# 高位判断从lenth-1处开始
		High_index = lenth-1 -i
		XHi = (x >> (High_index))&1 
		n_highbits = (n)>> (High_index) *2
		nextP_l = [] 
		nextQ_l = [] 
		nextP_h =[] 
		nextQ_h =[] 
		
		for j in range(len(p_low)): 
			for pl in range(2): 
				for ql in range(2): 
					for ph in range(2): 
						for qh in range(2): 
							if pl ^ qh == xi and ql ^ ph == XHi:
								PlxQl = (((pl<<i) + p_low[j]) * ((ql<<i) + q_low[j])) & maskn 
								PhxQh = (((ph << (High_index)) + p_high[j]) * ((qh << (High_index)) + q_high[j]))>>(High_index)*2 
								if PlxQl == n_lowbits : 
									# if n_highbits-PhxQh >= 0 and n_highbits-PhxQh <=((2<<i+1)-1)
									# 高n位的差在 2^(i+1)-1以内是 高位相同的必要条件
									if n_highbits-PhxQh >= 0 and n_highbits-PhxQh <=((2<<i+1)-1): 
										nextP_l.append((pl<<i) + p_low[j]) 
										nextQ_l.append((ql<<i) + q_low[j]) 
										nextP_h.append((ph<<(High_index))+p_high[j]) 
										nextQ_h.append((qh<<(High_index))+q_high[j]) 
		p_low = nextP_l 
		q_low = nextQ_l 
		p_high = nextP_h 
		q_high = nextQ_h 
	for a in p_low: 
		for b in p_high: 
			if n %(a+b) ==0: 
				p = a + b 
				q = n//p                                             
				print(p,q)
				break


n2 = 65288148454377101841888871848806704694477906587010755286451216632701868457722848139696036928561888850717442616782583309975714172626476485483361217174514747468099567870640277441004322344671717444306055398513733053054597586090074921540794347615153542286893272415931709396262118416062887003290070001173035587341
x2 =3604386688612320874143532262988384562213659798578583210892143261576908281112223356678900083870327527242238237513170367660043954376063004167228550592110478
lenth = 512
get_cd(n2,x2,lenth)

# ic(p,q)

稍微改了一下原p阴间的位运算

n1ctf2021

咕咕咕了好久

vss

  • 难点在随机数预测上面

先使用了一个二维码生成

1
2
3
4
5
6
7
8
9
    qr = qrcode.QRCode(
        version=1,
        error_correction=qrcode.constants.ERROR_CORRECT_L,
        box_size=12,
        border=4,
    )
    qr.add_data(FLAG)
    qr.make(fit=True)
    img = qr.make_image(fill_color="black", back_color="white")

RGB = 0xffffff 是白色

RGB = 0 是黑色

在填充像素时

当 pixel !=255 时填充在 2x, 2y 的 color会不一样

若能获得一大段连续的一样的pixel ,只要通过判断n个连续 color0 / color1的值就可以恢复出随机数MT9937的当前状态,不管是向前还是向后推都可以得到加密图片使用的随机数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
        if pixel:
            ...
        else:
            share1.putpixel((2*x, 2*y), color0)
            share1.putpixel((2*x, 2*y+1), color0)
            ...

            share2.putpixel((2*x, 2*y), color1)
            share2.putpixel((2*x, 2*y+1), color1)
            ...

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
34
35
from PIL import Image
from randcrack import RandCrack
import random
share = Image.open('./share2.png')
width = share.size[0]//2
res = Image.new('L', (width, width))
bits = ''

# pixel为1填充0
# pixel为0填充1
# 01分别对应的是黑色的填充和白色的背景像素 
# 官p取最后一段连续白色
for idx in range(width*width-624*32, width*width):
    i, j = idx//width, idx % width
    if share.getpixel((2*j, 2*i)) == 255:
        bits += '0'
    else:
        bits += '1'
# 判断像素后
rc = RandCrack()
for i in range(len(bits), 0, -32):
    rc.submit(int(bits[i-32:i], 2))
flipped_coins = [int(bit) for bit in bin(rc.predict_getrandbits(width*width-624*32))[2:].zfill(width*width-624*32)] + list(map(int, bits))

data = []

for idx in range(width*width):
    i, j = idx//width, idx % width
    if share.getpixel((2*j, 2*i)) == 255:
        data.append(0 if flipped_coins[idx] else 255)
    else:
        data.append(255 if flipped_coins[idx] else 0)

res.putdata(data)
res.save('ans.png')

CISCN 2021 oddaes

标准的远古时代的aes差分分析,做出来的估计互通有无得比较厉害

市面上能搜到的aes差分脚本有三种,只有一种是专门针对这个题的

能现学现找到的都是智商160+的超人😅😅😅

感谢ChaMd5让本菜鸡学习了该脚本的用法

暂且不论为什么社会安全团体会参加大学生赛事

Differential Fault Analysis(DFA)

先来简单了解一下FDA是个啥

Differential fault analysis (DFA) is a type of active side-channel attack in the field of cryptography, specifically cryptanalysis. The principle is to induce faults—unexpected environmental conditions—into cryptographic implementations, to reveal their internal states.

For example, a smartcard containing an embedded processor might be subjected to high temperature, unsupported supply voltage or current, excessively high overclocking, strong electric or magnetic fields, or even ionizing radiation to influence the operation of the processor. The processor may begin to output incorrect results due to physical data corruption, which may help a cryptanalyst deduce the instructions that the processor is running, or what its internal data state is.

For DES and Triple DES, about 200 single-flipped bits are necessary to obtain a secret key.DFA was also applied successfully to the AES cipher.

简单地说就是向密码系统内引入一定的错误,体现为加入以下细小的变化,使其与标准加密相比会有所不同。

实验情况为手动加入错误,现实情况可能是由天气温度等物理因素导致的以外情况

对des、3des而言约两百个单翻转位就足以获取到其密钥

可以理解为我们使用两套不一样的加密系统加密了同一套明文,而两套加密系统的不同是已知的且微小的,通过对密文分析,有几率得到密钥

analysis and implement

https://eprint.iacr.org/2009/575.pdf

Abstract. In this paper we present a differential fault attack that can be applied to the AES using a single fault. We demonstrate that when a single random byte fault is induced at the input of the eighth round, the AES key can be deduced using a two stage algorithm.

在这篇文章中介绍了针对第八轮的输入中引发单个随机字节错误时,可以使用两阶段算法推导出 AES 密钥的算法(其实后面正式attack👴一个字都没看)

Conclusion

these attacks can be conducted without any knowledge of the plaintext being enciphered, as an attacker would just need to know the plaintexts were the same

好了,那么我们可以发现题目给出的情况和论文中的情况是一模一样的🙄🙄🙄

 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
    def encrypt_block(self, plaintext):
        """
        Encrypts a single block of 16 byte long plaintext.
        """
        assert len(plaintext) == 16

        plain_state = bytes2matrix(plaintext)

        add_round_key(plain_state, self._key_matrices[0])

        for i in range(1, self.n_rounds):
            sub_bytes(plain_state)
            shift_rows(plain_state)
            mix_columns(plain_state)
            add_round_key(plain_state, self._key_matrices[i])

        sub_bytes(plain_state)
        shift_rows(plain_state)
        add_round_key(plain_state, self._key_matrices[-1])

        return matrix2bytes(plain_state)

    def encrypt_block_(self, plaintext,bytee):
        """
        Encrypts a single block of 16 byte long plaintext.
        """
        assert len(plaintext) == 16

        plain_state = bytes2matrix(plaintext)

        add_round_key(plain_state, self._key_matrices[0])

        for i in range(1, self.n_rounds):
            # 故意在第八轮中手动加入了差错。。。。
            if i==8:
                plain_state[0][0] ^= bytee
                
            sub_bytes(plain_state)
            shift_rows(plain_state)
            mix_columns(plain_state)
            add_round_key(plain_state, self._key_matrices[i])

        sub_bytes(plain_state)
        shift_rows(plain_state)
        add_round_key(plain_state, self._key_matrices[-1])
        keym = self._key_matrices[-1]
        return matrix2bytes(plain_state),keym[0]+keym[1]+keym[2]+keym[3]

https://github.com/Daeinar/dfa-aes

直接把这个库里面的example1的input-1.csv两段密文换成题目给出的密文就可以得到一堆matter keys,把所有matter keys拿进去遍历就得到key了

csv的文件结构和txt基本一样

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from aes import AES
import os,hashlib,random 
from tqdm import tqdm

# -----------------------------------
f = open('keys-0.csv','r') 

plain = os.urandom(16) 
m1 = '973f5ae78bc933a8fc7f7ab98d53d16f' 
m2 = '628aab012199cdab83cc1aa72204ea98'
s = random.randint(0,255)

for i in tqdm(range(4266)): 
    key = f.readline().replace('\n','') 
    cipher,k = AES(bytes.fromhex(key)).encrypt_block_(plain,s) 
    piece1 = [k[0],k[1],k[4],k[7],k[10],k[11],k[13],k[14]] 
    m11 = hashlib.md5(bytes(piece1)).hexdigest() 
    piece2 = [k[2],k[3],k[5],k[6],k[8],k[9],k[12],k[15]] 
    m22 = hashlib.md5(bytes(piece2)).hexdigest() 
    if m11 == m1 and m22 == m2: 
        print(key) 
        print("CISCN{"+hashlib.md5(bytes.fromhex(key)).hexdigest()+"}")
        break

癫疯极客2021补档 7-31

东拼西凑把wp凑齐了🙄

learnSM4

SM4采用和aes完全不同的结构

列如在第一轮中,使用原有明文生$X_0X_1X_2X_3$成新的明文$X_4$

在$n$轮后选取最后四个$X$作为密文

这里故意加入leak可以在第一轮和第二轮泄露用$X_0X_1X_2X_3$生成的$X_4$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def _crypthack(num, mk, rou,index):
    x_keys = list(_byte_unpack(num, byte_n=16))
    
    round_keys = _round_keys(mk)
    
    leak = 0 
    for i in _range(32):
        reg = _round_f(x_keys[i:i+4], round_keys[i])
        x_keys.append(reg) # use x0123 get x4
        reg =  _byte_unpack(reg)
        if i == rou:
            leak = reg[index]
    return _byte_pack(x_keys[-4:][::-1], byte_n=16),leak

生成公式如下

$X_4=repT(X_1\oplus X_2\oplus X_3\oplus roundKey)$

1
2
3
4
def _round_f(byte4_array, rk):
    x0, x1, x2, x3 = byte4_array
    print(x0, x1, x2, x3)
    return x0 ^ _rep_t(x1 ^ x2 ^ x3 ^ rk)

也就是说找到$repT$的逆算法就能求roundKey[0]了

然后就陷入了僵局。。写半天局部爆破每弄出来


事后发现有人用z3直接梭哈。。。

构造$X_4=1\oplus repT(0\oplus 0\oplus 0\oplus roundKey)$

依次输入r = 0 i=0~3 msg=0000001000000000000000000000000

 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
58
59
60
61
62
63
64
65
66
67
68
import z3
S_BOX = {
    0X00: 0XD6, 0X01: 0X90, 0X02: 0XE9, 0X03: 0XFE, 0X04: 0XCC, 0X05: 0XE1, 0X06: 0X3D, 0X07: 0XB7,
    0X08: 0X16, 0X09: 0XB6, 0X0A: 0X14, 0X0B: 0XC2, 0X0C: 0X28, 0X0D: 0XFB, 0X0E: 0X2C, 0X0F: 0X05,
    0X10: 0X2B, 0X11: 0X67, 0X12: 0X9A, 0X13: 0X76, 0X14: 0X2A, 0X15: 0XBE, 0X16: 0X04, 0X17: 0XC3,
    0X18: 0XAA, 0X19: 0X44, 0X1A: 0X13, 0X1B: 0X26, 0X1C: 0X49, 0X1D: 0X86, 0X1E: 0X06, 0X1F: 0X99,
    0X20: 0X9C, 0X21: 0X42, 0X22: 0X50, 0X23: 0XF4, 0X24: 0X91, 0X25: 0XEF, 0X26: 0X98, 0X27: 0X7A,
    0X28: 0X33, 0X29: 0X54, 0X2A: 0X0B, 0X2B: 0X43, 0X2C: 0XED, 0X2D: 0XCF, 0X2E: 0XAC, 0X2F: 0X62,
    0X30: 0XE4, 0X31: 0XB3, 0X32: 0X1C, 0X33: 0XA9, 0X34: 0XC9, 0X35: 0X08, 0X36: 0XE8, 0X37: 0X95,
    0X38: 0X80, 0X39: 0XDF, 0X3A: 0X94, 0X3B: 0XFA, 0X3C: 0X75, 0X3D: 0X8F, 0X3E: 0X3F, 0X3F: 0XA6,
    0X40: 0X47, 0X41: 0X07, 0X42: 0XA7, 0X43: 0XFC, 0X44: 0XF3, 0X45: 0X73, 0X46: 0X17, 0X47: 0XBA,
    0X48: 0X83, 0X49: 0X59, 0X4A: 0X3C, 0X4B: 0X19, 0X4C: 0XE6, 0X4D: 0X85, 0X4E: 0X4F, 0X4F: 0XA8,
    0X50: 0X68, 0X51: 0X6B, 0X52: 0X81, 0X53: 0XB2, 0X54: 0X71, 0X55: 0X64, 0X56: 0XDA, 0X57: 0X8B,
    0X58: 0XF8, 0X59: 0XEB, 0X5A: 0X0F, 0X5B: 0X4B, 0X5C: 0X70, 0X5D: 0X56, 0X5E: 0X9D, 0X5F: 0X35,
    0X60: 0X1E, 0X61: 0X24, 0X62: 0X0E, 0X63: 0X5E, 0X64: 0X63, 0X65: 0X58, 0X66: 0XD1, 0X67: 0XA2,
    0X68: 0X25, 0X69: 0X22, 0X6A: 0X7C, 0X6B: 0X3B, 0X6C: 0X01, 0X6D: 0X21, 0X6E: 0X78, 0X6F: 0X87,
    0X70: 0XD4, 0X71: 0X00, 0X72: 0X46, 0X73: 0X57, 0X74: 0X9F, 0X75: 0XD3, 0X76: 0X27, 0X77: 0X52,
    0X78: 0X4C, 0X79: 0X36, 0X7A: 0X02, 0X7B: 0XE7, 0X7C: 0XA0, 0X7D: 0XC4, 0X7E: 0XC8, 0X7F: 0X9E,
    0X80: 0XEA, 0X81: 0XBF, 0X82: 0X8A, 0X83: 0XD2, 0X84: 0X40, 0X85: 0XC7, 0X86: 0X38, 0X87: 0XB5,
    0X88: 0XA3, 0X89: 0XF7, 0X8A: 0XF2, 0X8B: 0XCE, 0X8C: 0XF9, 0X8D: 0X61, 0X8E: 0X15, 0X8F: 0XA1,
    0X90: 0XE0, 0X91: 0XAE, 0X92: 0X5D, 0X93: 0XA4, 0X94: 0X9B, 0X95: 0X34, 0X96: 0X1A, 0X97: 0X55,
    0X98: 0XAD, 0X99: 0X93, 0X9A: 0X32, 0X9B: 0X30, 0X9C: 0XF5, 0X9D: 0X8C, 0X9E: 0XB1, 0X9F: 0XE3,
    0XA0: 0X1D, 0XA1: 0XF6, 0XA2: 0XE2, 0XA3: 0X2E, 0XA4: 0X82, 0XA5: 0X66, 0XA6: 0XCA, 0XA7: 0X60,
    0XA8: 0XC0, 0XA9: 0X29, 0XAA: 0X23, 0XAB: 0XAB, 0XAC: 0X0D, 0XAD: 0X53, 0XAE: 0X4E, 0XAF: 0X6F,
    0XB0: 0XD5, 0XB1: 0XDB, 0XB2: 0X37, 0XB3: 0X45, 0XB4: 0XDE, 0XB5: 0XFD, 0XB6: 0X8E, 0XB7: 0X2F,
    0XB8: 0X03, 0XB9: 0XFF, 0XBA: 0X6A, 0XBB: 0X72, 0XBC: 0X6D, 0XBD: 0X6C, 0XBE: 0X5B, 0XBF: 0X51,
    0XC0: 0X8D, 0XC1: 0X1B, 0XC2: 0XAF, 0XC3: 0X92, 0XC4: 0XBB, 0XC5: 0XDD, 0XC6: 0XBC, 0XC7: 0X7F,
    0XC8: 0X11, 0XC9: 0XD9, 0XCA: 0X5C, 0XCB: 0X41, 0XCC: 0X1F, 0XCD: 0X10, 0XCE: 0X5A, 0XCF: 0XD8,
    0XD0: 0X0A, 0XD1: 0XC1, 0XD2: 0X31, 0XD3: 0X88, 0XD4: 0XA5, 0XD5: 0XCD, 0XD6: 0X7B, 0XD7: 0XBD,
    0XD8: 0X2D, 0XD9: 0X74, 0XDA: 0XD0, 0XDB: 0X12, 0XDC: 0XB8, 0XDD: 0XE5, 0XDE: 0XB4, 0XDF: 0XB0,
    0XE0: 0X89, 0XE1: 0X69, 0XE2: 0X97, 0XE3: 0X4A, 0XE4: 0X0C, 0XE5: 0X96, 0XE6: 0X77, 0XE7: 0X7E,
    0XE8: 0X65, 0XE9: 0XB9, 0XEA: 0XF1, 0XEB: 0X09, 0XEC: 0XC5, 0XED: 0X6E, 0XEE: 0XC6, 0XEF: 0X84,
    0XF0: 0X18, 0XF1: 0XF0, 0XF2: 0X7D, 0XF3: 0XEC, 0XF4: 0X3A, 0XF5: 0XDC, 0XF6: 0X4D, 0XF7: 0X20,
    0XF8: 0X79, 0XF9: 0XEE, 0XFA: 0X5F, 0XFB: 0X3E, 0XFC: 0XD7, 0XFD: 0XCB, 0XFE: 0X39, 0XFF: 0X48
}
def getnum(arr):
    HEX = ''
    for i in arr:
        HEX += hex(i)[2:]
    return int(HEX,16)

# 用z3逆T变换中的r(x)
def f(B):
    B1 = (((B << 2 ) & 0b1100000000000000000000000000000000) >>32) ^ (B << 2) & 0xffffffff
    B2 = (((B << 10) & 0b111111111100000000000000000000000000000000) >> 32) ^ (B<<10) & 0xffffffff
    B3 = (((B << 18) & 0b11111111111111111100000000000000000000000000000000) >> 32) ^ (B<<18) & 0xffffffff
    B4 = (((B << 24) & 0b11111111111111111111111100000000000000000000000000000000) >> 32) ^ (B<<24) & 0xffffffff
    return B ^ B1 ^ B2 ^ B3 ^ B4
    
S = z3.Solver()
x = z3.BitVec('x',64)
# 四次获取的x4
S.add((getnum([173,171,64,87])^1)- f(x)==0)
if S.check():
    print(S.model())
# [x = 2810370552]
    
    
    
print(hex(2810370552)[2:])
# 0x842586b9


key = '0'
arr = [0xa7,0x82,0xd9,0xf8]
for i in arr:
    key += hex(findS(i))[2:]
print(int(key,16))

crtrsa

没这么看这个,看完wp的爆破感觉智商收到了侮辱。。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from gmpy2 import *
from Crypto.Util.number import *
from tqdm import tqdm
from rich.progress import track
from rich.traceback import install
install()
# -----------------------------------
N = 6006128121276172470274143101473619963750725942458450119252491144009018469845917986523007748831362674341219814935241703026024431390531323127620970750816983
e = 2953544268002866703872076551930953722572317122777861299293407053391808199220655289235983088986372630141821049118015752017412642148934113723174855236142887
c=4082777468662493175049853412968913980472986215497247773911290709560282223053863513029985115855416847643274608394467813391117463817805000754191093158289399
 
a=2
A=powmod(a,e,N)
 
for dp in tqdm(range(1,2**20)):
    if gcd(powmod(A,dp,N)-a,N)!=1 and gcd(powmod(A,dp,N)-a,N)!=N:
        p=gcd(pow(A,dp,N)-a,N)
        q=N//p
        phi=(p-1)*(q-1)
        d=invert(e,phi)
        m=pow(c,d,N)
        print(long_to_bytes(m))
        break

抄,我疯狂抄

祥云ber secret_share

下午来推了一半就出去吃东西去了😘😘

看了wp发现只要几个步骤串起来其实不难的,可能是因为我只会炼丹吧。。。

基本加解密:

enc

$E = g^e\mod p,V=g^v\mod p\ s = v+e(h2(E||V))$

$c = m*pk^{e+v}\mod p$

r_enc:

$E_- = g^{e\times skI\times dd} , V_-=g^{v\times skI\times dd}$

$E = g^{e},V=g^{v}$

$c = m\times (EV)^{skI}\mod p =m\times (E_-V_-)^{inv(dd,p-1)}\mod p$

这里拿到dd就可以搞解密了,解dd的前提是吧encoder搞清楚

encoder当时没细看,其实变化写完了一看就很简单了

照着👴们的消元学习了

连续4次推得sk拿到随机出来的m可以得到

$mul={sk}^4\cdot dd_1\cdot dd_2\cdot dd_3\cdot dd_4%p$

$dd_i$是已知的,有些solve是域下开根

有些是神仙炫技直接 韦达定理 或者 费玛大定理

https://gitee.com/ljahum/images/raw/master/img/20210830211519.png

拿到单独的sk后就可以搞事情了

EV都是已知,c也已知 直接算就🆗了

solve-step1

 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
58
59
60
61
62
63
64
from Crypto.Util.number import *
from icecream import *
from hashlib import sha256
from gmpy2 import *
import libnum
from pwn import *
from libnum import *
def h2(m):
    return int(sha256(m).hexdigest(), 16)

io=remote('0.0.0.0',10001)


#1
io.recvuntil('choice>')
io.sendline('1')
io.recvuntil('Please take good care of it!\n')
pk_sk=io.recvuntil('\n')[:-1].decode()[2:-1].split('L,0x')
pk,sk=int(pk_sk[0],16),int(pk_sk[1],16)

#2
io.recvuntil('choice>')
io.sendline('2')
pp, g = 0xb5655f7c97e8007baaf31716c305cf5950a935d239891c81e671c39b7b5b2544b0198a39fd13fa83830f93afb558321680713d4f6e6d7201d27256567b8f70c3, 0x85fd9ae42b57e515b7849b232fcd9575c18131235104d451eeceb991436b646d374086ca751846fdfec1ff7d4e1b9d6812355093a8227742a30361401ccc5577
group_list = [32, 64, 128, 256]
DD=1
for group in group_list:
    io.recvuntil('The cipher shared to you\n')
    cc=int(io.recvuntil('L, ')[1:-3])
    new_cipher=[cc]
    new_cipher+=eval(io.recvuntil(')\n')[:-2].decode().replace('L',''))
    c,E_,V_,s_=new_cipher

    io.recvuntil('prefix, encoder = ')
    Enc2,prefix=pre_enc=eval(io.recvuntil('\n')[:-1].decode().replace('L',''))
    prefix=int(prefix,16)
    encoder=[1,(-pow(prefix,sk,pp)) %pp]
    prefix = long_to_bytes(prefix).rjust(64, b'\x00')

    ml=[1]
    for i in range(len(Enc2)):
        ml.append((ml[-1]*encoder[-1]+Enc2[i]*(-1)**(i+1))%pp)
    r=-ml[-1]%pp
    dd = h2(prefix + long_to_bytes(r).rjust(64, b'\x00')) | 1
    DD*=dd
    d=libnum.invmod(dd,pp-1)
    tmp=E_*V_%pp
    xx=pow(tmp,d,pp)
    m=c*libnum.invmod(xx,pp)%pp
    io.send(hex(m)[2:])
io.recvuntil('You are a clever boy! Now I can share you some other information!\n0x')
mul=int(io.recvuntil('\n')[:-2],16)


ic(DD)
ic(mul)

#3
io.recvuntil('choice>')
io.sendline('3')
cc=int(io.recvuntil('L, ')[1:-3])
cipher=[cc]
cipher+=eval(io.recvuntil(')\n')[:-2].decode().replace('L',''))
ic(cipher)

solve-step2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
from gmpy2 import *
io=0xb5655f7c97e8007baaf31716c305cf5950a935d239891c81e671c39b7b5b2544b0198a39fd13fa83830f93afb558321680713d4f6e6d7201d27256567b8f70c3
D=15987058835088036058838351739905403758810826722245822649290306549906899936826738229650730140126509371862930340608846190807298868677166971678478129606238898364288362139315516922003581996769819030117310508402522153899137933429897987557331966070437119010259514160059698255241259153692392463260794449949596746727
mul=7194716155235037744823597029059822446255314248196377746260315999958188811928743123657567494196521690514320209430663462342437059567384744437239548754416135
c=mul*libnum.invmod(D,io)%io
e=4
R.<x> = Zmod(io)[]
f = x ^ e- c
f = f.monic()
res1 = f.roots()
print(res1)

solve-step3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
from Crypto.Util.number import *
from gmpy2 import *
pp=0xb5655f7c97e8007baaf31716c305cf5950a935d239891c81e671c39b7b5b2544b0198a39fd13fa83830f93afb558321680713d4f6e6d7201d27256567b8f70c3
sk=3415391405045794570454819264678842883406589094879440924771251075986414212665514615692960890299627279215019657097231396800926908716766924569917256830117771
cipher=[1452085683981538837849557434841689674477096081702343000869186835544808468459192026693029532721465657214194362000756249662047209552808256166535501585736401, 9299317806552199012103361766715291248186887467752322286719294121971787657296205598139365760833959784768412272593061318430853065277862724140493914797711689, 9287316455075844376168558534606543590293095721271733423230961724912040658757071778242087450272981713664977773510705690081763692753388091475741636185572383, 229110517869350912236518454062717456777603700368163296438479618211042488031942897036793380693680124455343059560507824269299022538059530971380675264277197]
c,E,V,s=cipher
xx=E*V%pp
m=c*libnum.invmod(pow(xx,sk,pp),pp)%pp
print(long_to_bytes(m))
#flag{504d0411-6707-469b-be31-9868200aca95}

学到很多

蓝帽ber final

https://github.com/ljahum/crypto-challenges/tree/main/%E8%93%9D%E7%8C%AB2021/final/twoBytes

twobyte

二分法

传入$C\times padding^e$

利用高位的two bytes判断$M\times padding和2^{496}$的大小关系(512-16=496)

利用二分法查找padding的值

查找约1000+次可以恢复secret

solve

 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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
from subprocess import run
from Crypto.Util.number import long_to_bytes
from icecream import *
from pwn import *
import re

from pwnlib.util.iters import pad
def b2s(s):
    if(type(s)==str):
        return s
    else:
        return s.decode()

def CatNum(txt):
    txt = b2s(txt)
    matchObj = re.findall(r'[0-9]+', txt)
    return matchObj



def dec(n):
    print(io.recvuntil('Your choice: '))
    io.sendline('1')
    print(io.recvuntil('Your cipher: '))
    io.sendline(str(n))
    return io.recvline()[:-1]
def bigger(mid,c):
    # tmp1 = pow(mid,e,n)
    # ic(tmp1)
    tmp = (c*pow(mid,e,n))%n
    print(tmp)
    # ic(padding)
    m = dec(tmp)
    ic(m)
    if(m!=b'0000'):
        return True
    else:
        return False


io=remote('0.0.0.0',10001)
# print(io.recv(1024))
io.recvuntil('PKCS1_v1_6?(y/n)')
io.sendline('n')
e = int(CatNum(io.recvline())[0])
n = int(CatNum(io.recvline())[0])
c = int(CatNum(io.recvline())[0])
ic(e,c,n)

'''估算padding范围
padding = 1
h = 0
for i in range(512):
    tmp1 = pow(padding,e,n)
    ic(tmp1)
    tmp = (c*tmp1)%n
    print(tmp)
    ic(padding)
    m = dec(tmp)
    ic(m,i)
    if(m!=b'0000'):
        h=i
        input()
        break
    padding *= 2

'''


# pad=240~260
pl = 2**200
ph = 2**496
mid= (pl+ph)//2
input()
for i in range(512):
    # tmp = m*mid
    # ic(tmp-n)
    if(bigger(mid,c)==True):
        ph=mid-1
        mid = (mid+pl)//2
    else:
        pl=mid+1
        mid  =(mid+ph)//2
    # print(mid)
    # input()
ic(mid)
n=2**496
s =n//mid
secret = long_to_bytes(s)
ic(secret)
ic(secret.hex())
print(io.recvuntil('Your choice: '))
io.sendline('2')
io.sendline(secret.hex())
sleep(0.5)
print(io.recv(1024))

1
2
3
4
5
b'Your choice: '
b"You know my secret? (in hex): b'flag{ba1f2511fc30423bdbb183fe33f3dd0f}'\n"
[*] Closed connection to 0.0.0.0 port 10001
  /mnt/c/U/16953/Desktop/twoBytes took  11s at  11:38:42 AM
❯