UNCTFwp

huangx607087对于UNCTF密码学的笔记

About

在队伍里dxgdl的同意下，又水了一篇题解，然而有两道最难的题目我不会写，Hermes大佬却已经把7条密码学AK了，我果然是个fw

Write Ups

1.RSA1

首先先看一下题目代码：（最后给出部分略）

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

p = number.getPrime(1024)
q = number.getPrime(1024)
if p > q:
    a = p + q
    b = p - q
    print(a,b)

n = p * q
e = 65537
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = bytes_to_long(b'msg')
c = pow(m,e,n)
print(c)

题目给出了$a,b$的值，还有加密后密文$c$的值，很容易地我们可以求出来$p=(a+b)/2,q=(a-b)/2$.然后直接用RSA的最基本的方法解决即可，很水的一道题。

2.(大法官之失去的营养怎么补)

这道题一开始给出了一个长为$100$的字符串如下：ottttootoootooooottoootooottotootttootooottotttooootttototoottooootoooottotoottottooooooooottotootto。然后我们可以看到，这个字符串里面只有o和t两个字符，盲猜o是one，t是two。

然后观察到密文长度刚好是$100$，符合条件长度是$5$的倍数，可以考虑培根密码。把o替换成A，t替换成B。然后随便找个网站就可以解出题目了。

3. EZRSA

又是一道RSA的题目，题目给出了$e,n,c$数值，我们可以看到$\ln e ≈ \ln n $。自然会想到winnerattack的方法。（之前Am473ur师傅出的那道题是直接爆破$d$，可能是因为$d$的值太小了导致我一重$for$循环直接枚举出来，没有对其进行深刻研究233333）。

不多说，直接上解题代码，也就是winnerattack的脚本。到时候我会更新一下自己的RSA笔记。

这个脚本是在网上找到的，不是自己打的= =所以可以证明我的fw属性成立

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
from __future__ import print_function
import libnum

def continued_fractions_expansion(numerator,denominator):#(e,N)
	result=[]
 
	divident = numerator % denominator
	quotient = numerator // denominator
	result.append(quotient)
 
	while divident != 0:
		numerator = numerator - quotient * denominator
 
		tmp = denominator
		denominator = numerator
		numerator = tmp
 
		divident = numerator % denominator
		quotient = numerator // denominator
		result.append(quotient)
 
	return result
 
def convergents(expansion):
	convergents=[(expansion[0], 1)]
	for i in range(1, len(expansion)):
		numerator = 1
		denominator = expansion[i]
		for j in range(i - 1, -1, -1):
			numerator += expansion[j] * denominator
			if j==0:
				break
			tmp = denominator
			denominator = numerator
			numerator = tmp
		convergents.append((numerator, denominator)) #(k,d)
	return convergents
 
def newtonSqrt(n):
	approx = n // 2
	better = (approx + n // approx) // 2
	while better != approx:
	    approx = better
	    better = (approx + n // approx) // 2
	return approx
 
def wiener_attack(cons, e, N):
	for cs in cons:
		k,d = cs
		if k == 0:
			continue
		phi_N = (e * d - 1) // k
		#x**2 - ((N - phi_N) + 1) * x + N = 0
		a = 1
		b = -((N - phi_N) + 1)
		c = N
		delta = b * b - 4 * a * c
		if delta <= 0:
			continue
		x1 = (newtonSqrt(delta) - b)//(2 * a)
		x2 = -(newtonSqrt(delta) + b)//(2 * a)
		if x1 * x2 == N:
			return [x1, x2, k, d]

if __name__ == "__main__":
    n = 147282573611984580384965727976839351356009465616053475428039851794553880833177877211323318130843267847303264730088424552657129314295117614222630326581943132950689147833674506592824134135054877394753008169629583742916853056999371985307138775298080986801742942833212727949277517691311315098722536282119888605701
    e = 18437613570247445737704630776150775735509244525633303532921813122997549954741828855898842356900537746647414676272022397989161180996467240795661928117273837666615415153571959258847829528131519423486261757569454011940318849589730152031528323576997801788206457548531802663834418381061551227544937412734776581781
    
    c = 140896698267670480175739817539898638657099087197096836734243016824204113452987617610944986742919793506024892638851339015015706164412994514598564989374037762836439262224649359411190187875207060663509777017529293145434535056275850555331099130633232844054767057175076598741233988533181035871238444008366306956934
   
    expansion = continued_fractions_expansion(e, n)
    cons = convergents(expansion)
    p, q, k, d = wiener_attack(cons, e, n)
    m = pow(c, d, n)
    print(libnum.n2s(m))

4

一道没有任何技术含量的题目，只需要打开Word文档，把字体调成Wingdings 2。然后看着图片一个一个对照就可以了（最后转成正常的字体（比如宋体）

5 SignIn

先看一下题目代码：

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
import random
from Crypto.Cipher import AES
from os import urandom
from string import printable
from binascii import hexlify
from secret import flag

random.seed(urandom(32))

key1 = '0'*13 + ''.join([random.choice(printable) for _ in range(3)])
key2 = ''.join([random.choice(printable) for _ in range(3)]) + '0'*13

cipher1 = AES.new(key=key1.encode(), mode=AES.MODE_ECB)
cipher2 = AES.new(key=key2.encode(), mode=AES.MODE_ECB)

pt = input("You have a chance to get something: ")
pt = pt.encode()

val = len(pt) % 16
if not val == 0:
    pt += b'\x00'*(16 - val)

c1 = cipher1.encrypt(pt)
c2 = cipher2.encrypt(c1)
print('Your cipher:{}'.format(hexlify(c2)))

assert(len(flag) % 16 == 0)
c3 = cipher1.encrypt(flag)
c4 = cipher2.encrypt(c3)
print('Your flag:{}'.format(hexlify(c4)))
'''
You have a chance to get something: UNCTF2020_Enjoy_Crypto~
Your cipher:b'01a4e429e76db218fa0eb18f03ec69c9200a2362d8b4d7ea46170ce698389bbd'
Your flag:b'196cc94c2d685beb54beeaa14c1dc0a6f3794d65fca0d1a1274515166e4255ab367383092e42d774992f74bc138faaad'
'''

题目给出了一次加密的结果。从代码中我们可以看到：$key1$的前$13$位密钥全是$0$，后$3$位是未知的。而$key2$的前$3$位是未知的,后面$13$位全是$0$。

第一次对给出的内容加密，我们可以看到第一次加密的结果是$c1$，第二次加密的结果是$c2$。并且$c2$是已知的。考虑到字符库是有限的(只有$100$个可用字符）。所以我们可以暴力枚举所有$100^3=1000000$种$pt$的加密可能，然后暴力枚举$1000000$种对$p2$解密的可能性,换句话说，我们就通过两面夹击的方式，枚举到了两种不同途径$c1$的可能结果。然后我们就可以寻找到相同的部分，就能得到$c1$字符串了。

暴力枚举代码如下：

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 string import *
from gmpy2 import *
from Crypto.Util.number import *
from Crypto.Cipher import AES
pt=b"UNCTF2020_Enjoy_Crypto~"
val = len(pt) % 16
if not val == 0:
    pt += b'\x00'*(16 - val)
print(pt)
s=printable
GivenChiper='01a4e429e76db218fa0eb18f03ec69c9200a2362d8b4d7ea46170ce698389bbd'
GivenChiper=long_to_bytes(int(GivenChiper,16))
Key1='0'*13
boxi=[]
for i1 in s:
    for i2 in s:
        for i3 in s:
            Keyi=Key1+i1+i2+i3
            cipher1 = AES.new(key=Keyi.encode(), mode=AES.MODE_ECB)
            f=cipher1.encrypt(pt)
            boxi+=[f]
with open('data1.out', 'w') as f:
    #for i in range(10):
    for i in range(len(s)**3):
        if(i%25000==0):
            print(i)
        f.write(hex(bytes_to_long(boxi[i]))[2:]+'\n')
Key2='0'*13
boxi=[]
for i1 in s:
    for i2 in s:
        for i3 in s:
            Keyii=i1+i2+i3+Key2
            cipher2 = AES.new(key=Keyii.encode(), mode=AES.MODE_ECB)
            f=cipher2.decrypt(GivenChiper)
            boxi+=[f]
with open('data2.out', 'w') as f:
    for i in range(len(s)**3):
        if(i%25000==0):
            print(i)
        f.write(hex(bytes_to_long(boxi[i]))[2:]+'\n')

然后我们就出来了data1和data2两个文件，然后我们用以下的C++脚本，可以找到唯一的共同输出（这样我们可以用$O(2n)$的复杂度，而不是魔鬼般的$O(n^2)$）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
map<string,bool>p;
string s;
int main()
{
	int i,j;
	freopen("data2.out","r",stdin);
	for(i=1;i<=1000000;i++)
	{
		cin>>s;
		p[s]=1;
	}
	freopen("data1.out","r",stdin);
	for(i=1;i<=1000000;i++)
	{
		cin>>s;
		if(p[s]==1)
			cout<<s<<endl;
	}
	return 0;
}

然后我们再一次暴力枚举，找出共同点时的密钥$k1$和$k2$被省略的$3$位数。

找到之后，我们就可以用以下脚本，解出flag了（

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Cipher import AES
from os import urandom
from string import printable
from binascii import hexlify
from Crypto.Util.number import *
key1 = '0'*13 +'W<&'
key2 = '0/i' + '0'*13
C=b'196cc94c2d685beb54beeaa14c1dc0a6f3794d65fca0d1a1274515166e4255ab367383092e42d774992f74bc138faaad'
C=long_to_bytes(int(C,16))
print(C)
cipher1 = AES.new(key=key1.encode(), mode=AES.MODE_ECB)
cipher2 = AES.new(key=key2.encode(), mode=AES.MODE_ECB)
D=cipher2.decrypt(C)
D=cipher1.decrypt(D)
print(D)
CTFSeason1
#WriteUp
UNCTFwp
http://example.com/2020/11/13/UNCTFwp/
作者
huangx607087
发布于
2020年11月13日
许可协议