21Jan3

huangx607087寒假的切题3

0.简介

一个密码学废物的寒假切题笔记，别看，贼菜

近期BUU已经上了1500分，但作为一个yydfw，仍然是会被别人吊着打的那种，而szx在yydsfmyy的指导下，进步非常快，已经成为了pwn神。而jiangjiang作为一个G1DALAO也在RE有了很多进展，哎，自己进步太慢的根本原因就是太菜了

1.[NCTF2020] RDH

一道题目，别人做2天，我做了2个月，wtcl，wsfw

首先来看一下题目脚本代码，查了一下，这貌似是个Paillier加密算法，加密的部分方法与RSA类似：

加密方法很简单，首先与RSA一样，选择两个大素数$p,q$，计算$n=pq$，其中$\gcd(n,(p-1)(q-1))=1$。然后计算$\lambda=\text{lcm}(p-1,q-1)$。

然后选择随机整数$g$。计算密文$E(m,r)c\equiv g^mr^n\pmod {n^2}$，其中$r$是随机整数

解密方法为$D(c,\lambda)=m\equiv \dfrac{L(c^\lambda \mod n^2)}{L(g^\lambda \mod n^2)}\pmod n$，其中$L(x)=\dfrac{x-1}{n}$

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
from PIL import Image
import numpy as np
from Crypto.Util.number import *
import random
from gmpy2 import lcm
from secret import flag
def getMyPrime(nbits):
    def genProduct(nbits):
        p = 1
        while p.bit_length() < nbits:
            p *= random.choice(sieve_base)
        return p
    P = genProduct(nbits)
    while not isPrime(P-1):
        P = genProduct(nbits)
    return (P-1)
class Homo:
    def __init__(self):
        p, q = getMyPrime(512), getMyPrime(512)
        n = p*q
        g = random.randint(1, n*n)
        while GCD(self.L(pow(g, lcm(p-1, q-1), n*n), n), n) != 1:
            g = random.randint(1, n*n)
        self.g, self.n = g, n
        print("n =", n)
        print("g =", g)
    def enc(self, m):
        n = self.n
        return (pow(self.g, int(m), n*n)*pow(random.randint(1, n), n, n*n)) % (n*n)
    def L(self, u, n): return (u-1)//n
def encrypt_img(homo, img_array):
    cip_list = []
    for i in range(len(img_array)):
        for j in range(len(img_array[i])):
            cip_list.append(homo.enc(img_array[i][j]))
    return cip_list
def encrypt_flag(homo, flag):
    flag_bin = bin(flag)[2:]
    cip_list = [homo.enc(int(i) << 8) for i in flag_bin]
    return cip_list
if __name__ == "__main__":
    homo = Homo()
    img = Image.open("./img.png").convert("L") # 56x56
    img_array = np.array(img)
    img_enc = encrypt_img(homo, img_array)
    flag = bytes_to_long(flag.encode())
    flag_enc = encrypt_flag(homo, flag)
    
    assert len(img_enc) > len(flag_enc)
    with open("data", "w") as f:
        for i in range(len(img_enc)):
            if i < len(flag_enc):
                enc = (flag_enc[i]*img_enc[i]) % (homo.n**2)
                f.write(hex(enc)[2:]+"\n")
            else:
                f.write(hex(img_enc[i])[2:]+"\n")
# n = 18434491463536053807355381425234564739214857081161321309756933006496704225386021314592003940717664842835425875706674652882353813796736161102105318696602774157554627232038142092845118667433422811370679163251506433284182749390704212211677891535882993540750379419384629735499044085104591893176847835387567644762636961
# g = 99894228586367782940715460732971967417359410558715186789679488951080212107512884192976002563404881263875114900183845944243751294600634946131559701908524899495387780188074842981190381617301097312646907480816373003121403029154865843313001145153263200356271270964096284006748227606839491672635131818273934109984977288621523498782962389115299664149676881349445940131040928322172748228670542470966453917916224551852329336572423059849239115479150176538160893340622774682474615303826972971312087884483400100816655408278649954266707268236152380355955111697822333005733513834283677509165970313043388621472231706074701389916165894223877

从加密代码中可以看出：这个生成的素数$p,q$满足$p+1,q+1$为光滑的数字，因此可以利用PrimeFac插件在linux环境下分解因数，在自己的电脑Lenovo Legion Y7000(512G,16G)上跑大概$9$分钟左右

1

分解因数后，我们就可以用下面的脚本进行解密：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
from given import n,p,q,g
def L(x):
    return (x-1)//(n)
#-----MAIN BELOW-----#
f=open("data.txt","r")
b=f.read()
f.close()
C,M=[],[]
s=""
for i in range(len(b)):
    if b[i]=='\n':
        C.append(int(s,16))
        s=""
    else:
        s=s+b[i]
lm=(p-1)*(q-1)//GCD(p-1,q-1)
for i in range(len(C)):
    if(i%100==0):
        print(i)
    m=L(pow(C[i],lm,n*n))*inverse(L(pow(g,lm,n*n)),n)%n
    M.append(m)
    print(M)

然后我们可以得到很多的数据，在记事本用$16$进制打开时这样的

2

很显然，有些数字大于等于$100_h$，一张图片正常的灰度值应该是在$[00_h,\text{FF}_h]$之间，根据这个加密算法的加法同态性与加密代码，我们可以认为那些大于$\text{FF}_h$的数字应该对应的是flag字节中的$1$

发现最后flag比特数除以$8$的余数是$1$，所以我们应该在最前面补一个$0$，得到flag为NCTF{R3v3r5ibLe_D4t4_H1d1ng_1N_P4illi3r_Crypt0sy5t3m}

2.[b01lers2020]safety_in_numbers

PublicKey读取后，我们可以看到$n$有一千多万位，$e=65537$，$c$有$900$多万位，$\ln n-\ln c > 400000$，此时直接用gmpy2中的iroot函数对$c$进行开根即可。

不过注意到这里有个byteorder='little'，也就意味着写在最后的那个字节代表着最高位，这样才能得到正确答案

1
2
3
4
5
6
7
8
9
10
from Crypto.Util.number import *
from gmpy2 import *
from E import e
import libnum
with open('flag.enc','rb') as f:
    cipher = f.read()
c = int.from_bytes(cipher, byteorder='little')
print(iroot(c,e)[0])
for i in range(4):
    input()

3.[INSHack2019]Yet Another RSA Challenge - Part 1

1
2
3
4
5
6
7
8
import subprocess
p = subprocess.check_output('openssl prime -generate -bits 2048 -hex')
q = subprocess.check_output('openssl prime -generate -bits 2048 -hex')
flag = int('INSA{REDACTED}'.encode('hex'), 16)
N = int(p,16) * int(q,16)
print N
print '0x'+p.replace('9F','FC')
print pow(flag,65537,N)

题目难度较为简单，给出了一个将$p$中所有$\text{9F}_h$字节替换成了$\text{FC}_h$字节，查了一下给出的数字中一共有$4$个$\text{FC}_h$字节，因此一共有$16$个可能的的数字，直接枚举一下看看哪个整除$n$就可以把$n$分解了，难度很低。

4.[AFCTF2018]一道有趣的题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#加密代码
def encrypt(plainText):
    space = 10
    cipherText = ""
    for i in range(len(plainText)):
        if i + space < len(plainText) - 1:
            cipherText += chr(ord(plainText[i]) ^ ord(plainText[i + space]))
        else:
            cipherText += chr(ord(plainText[i]) ^ ord(plainText[space]))
        if ord(plainText[i]) % 2 == 0:
            space += 1
        else:
            space -= 1
    return cipherText
# 密码
#00| 15 12 0d 1a 0a
#05| 08 10 01 0a 03
#10| 1d 3e 31 00 0d
#15| 1d 17 0d 17 3b
#20| 0d 17 3b 0c 07
#25| 06 02 06

我们根据最后输出的内容得到flag长度是$28$位，并且我们可以盲猜flag[:6]='afctf{',flag[-1]='}'

然后我们光afctf{这个字段跑一边，得到了这样的内容：afctf{cr??t?n?l?sis_isih??_}（问号处表示未知字符）。

然后我们用下面的C++程序把这个字符带进去，考虑到最后一个下划线可能是错的，因此我们可以把最后一个下划线也改成问号

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
#include<bits/stdc++.h>
using namespace std;
char c[35]={0x15,0x12,0x0d,0x1a,0x0a,0x08,0x10,0x01,0x0a,0x03,0x1d,0x3e,0x31,0x00,0x0d,0x1d,0x17,0x0d,0x17,0x3b,0x0d,0x17,0x3b,0xc ,07 ,06 ,02,06};
char m[35]="afctf{cr??t?n?l?sis_isih???}";
int main()
{
	int i,s=10;
	for(i=0;i<=27;i++)
	{
		if(m[i+s]=='?'&&m[i]!='?')
			m[i+s]=m[i]^c[i];
		if(m[i+s]!='?'&&m[i]=='?')
			m[i]=m[i+s]^c[i];
		if(m[i]!='?')
		{
			if(m[i]%2==0)
				++s;
			else 
				--s;
		}
	}
	for(i=0;i<=27;i++)
		cout<<m[i];
	return 0;
}

然后跑出来了这个玩意：afctf{cryptWn?l`sis_isiha}

盲猜最后一个单词是hard，带进去，得afctf{cryptWnalysis_isihard}。

调整一下，得afctf{cryptanalysis_is_hard}即可得出答案

5.[V&N2020 公开赛]Backtrace

题目给出的代码非常简单。

1
2
3
4
5
6
import random
flag = "flag{" + ''.join(str(random.getrandbits(32)) for _ in range(4)) + "}"
with open('output.txt', 'w') as f:
    for i in range(1000):
        f.write(str(random.getrandbits(32)) + "\n")
print(flag)

一开始我也不知道这道题应该怎么解，直到看到了这个：

3

才知道这是一个梅森旋转算法，给出了$1000$个状态，但前$4$个状态被做成了flag，也就是说，我们无法得知一个完整的$624$个状态

不过我们既然知道了编号为$624,625,626,627$的四个状态，就很容易会推到$0,1,2,3$这四个状态，也就是我们想要的flag，脚本代码如下：

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
from random import Random
# right shift inverse
def inverse_right(res,shift,mask=0xffffffff,bits=32):
    tmp = res
    for i in range(bits//shift):
        tmp = res ^ tmp>>shift & mask
    return tmp
# left shift inverse
def inverse_left(res,shift,mask=0xffffffff,bits=32):
    tmp = res
    for i in range(bits//shift):
        tmp = res ^ tmp << shift & mask
    return tmp
def backtrace(cur):
    high = 0x80000000
    low = 0x7fffffff
    mask = 0x9908b0df
    state = cur
    for i in range(3,-1,-1):
        tmp = state[i+624]^state[i+397]
        # recover Y,tmp = Y
        if tmp & high == high:
            tmp ^= mask
            tmp <<= 1
            tmp |= 1
        else:
            tmp <<=1
        # recover highest bit
        res = tmp&high
        # recover other 31 bits,when i =0,it just use the method again it so beautiful!!!!
        tmp = state[i-1+624]^state[i+396]
        # recover Y,tmp = Y
        if tmp & high == high:
            tmp ^= mask
            tmp <<= 1
            tmp |= 1
        else:
            tmp <<=1
        res |= (tmp)&low
        state[i] = res
    return state
def recover_state(out):
    state = []
    for i in out:
        i = inverse_right(i,18)
        i = inverse_left(i,15,0xefc60000)
        i = inverse_left(i,7,0x9d2c5680)
        i = inverse_right(i,11)
        state.append(i)
    return state
f = open("output.txt","r").readlines()
c = []
for i in range(1000):
    c.append(int(f[i].strip()))
partS = recover_state(c)
state = backtrace([0]*4+partS)[:624]
# print(state)
prng = Random()
prng.setstate((3,tuple(state+[0]),None))
flag = "flag{" + ''.join(str(prng.getrandbits(32)) for _ in range(4)) + "}"
print(flag)

6.总结

寒假第三波题目，后面还要继续加油（

CTFSeason2
#ExpLog
21Jan3
http://example.com/2021/01/26/21Jan3/
作者
huangx607087
发布于
2021年1月26日
许可协议