PRNG MT Notes

huangx607087关于PRNG MT 的学习笔记

0x00 博客背景

9月25日做出的0xCTF上的PRNG2,不过那道题源码不小心被我删掉了Orz,一个月后会回顾一下之前的笔记,记录自己当时的学习过程

0x01 MT简介

梅森旋转(Mersenne Twister)是一个PRNG伪随机数发生算法,基于有限二进制字段上的矩阵递归(反正我也不懂),周期高达$2^{17399}-1$

步骤:
1.获得基础的梅森旋转链
2.对于旋转链进行旋转算法
3.对于旋转算法所得结果进行处理
注:该算法的实现过程中参数的选取主要取决于梅森素数

涉及变量:
$w$ :加密长度,以bit为单位,$w$位整数。
$n$ :递归长度
$m$:周期参数,用于第三阶段的偏移量
$a$:旋转矩阵的参数
$r$:低位掩码,即低位要提取的位数
$f$:初始化旋转链所需参数
$b,c$:TGFSR的掩码
$s,t$:TGFSR的位移量
$u,d,l$ 额外的梅森旋转所需要的掩码和位移量

0x02 加密方法

1.初始化,将传入的seed值赋值给$MT0$作为初值,并递推得到旋转链
递推式:$MT_i=f×(MT
{i-1})$ xor $((MT_{i-1})>>(w-2))+i$

2.执行旋转算法
连接$MT{i}$的高$w-r$位和$MT{i+1}$的低$r$位,若这个组合后的二进制数末位为$0$,将其除以$2$.。否则将这个数除以$2$后再与$a$进行异或。假设我们最终得到的数字为$P$
所以我们的递推式为$MTi=MT{i+m}$ xor $P$

3.对于旋转算法所得结果进行处理:
设$x$为该序列下一个值,$y$是一个临时的中间变量,$z$是算法返回值
以下为处理过程:

1
2
3
4
y=x xor((x>>u)&d)
y=y xor((y<<s)&b)
y=y xor((y<<t)&c)
z=y xor(y>>l)

0x03 解密方法

解密关键:求出一个周期内的全部内容,然后就可以顺推得出前面所有的情况了

逆向处理。加密一共$4$步,都是异或运算,所以我们可以写出逆算法

我们先来看看加密的最后一步:z=y xor (y>>l),很显然,这一操作时不影响$y$的最高$l$位的,所以$z$的最高$l$位就是$y$的最高$l$位,我们可以通过$y>>l$的高$2l$位(最高$l$位全是$0$),从而我们可以得到$y$的$2l$位,进而得到$y>>l$的高$3l$位…….

上面的可能有点抽象,在此举个例子:

$y=10110110_b,t=10011011_b,l=2,y/4=00101011_b$(已知量只有$t,l$)

根据$t$的高$2$位,我们知道$y$的高$2$位为$10_b$,我们可以得到$y/4$的高$4$位为$0010_b$,由于$y$的高$4$位异或$y/4$的高$4$位可以得到$t$的高$4$位,所以$y$的高$4$位可以算出来,进而我们就可以算法出$y$的高$6$位了……

这样,我们就可以把第4步逆出来了。

关于逆出第3步,$y_1=y$ xor$((y<<t)$&$c)$,我们可以发现:$y_1$的低$t$位就是$y$的低$t$位异或$c$的低$t$位求出来的结果,所以$y_1$的低$t$位与$c$的低$t$位异或以下即为$y$的低$t$位,进而我们可以得到$(y<<t)$的低$2t$位,模仿上面的方法得到$y$的所有位

第2步和第1步分别于第3步和第4步同理,我们可以直接放上解密脚本(这么好的代码当然不是我这个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
# right shift inverse
def inverse_right(res, shift, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ tmp >> shift
return tmp
# right shift with mask inverse
def inverse_right_mask(res, shift, mask, 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, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ tmp << shift
return tmp
# left shift with mask inverse
def inverse_left_mask(res, shift, mask, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ tmp << shift & mask
return tmp
def extract_number(y):
y = y ^ y >> 11
y = y ^ y << 7 & 2636928640
y = y ^ y << 15 & 4022730752
y = y ^ y >> 18
return y&0xffffffff
def recover(y):
y = inverse_right(y,18)
y = inverse_left_mask(y,15,4022730752)
y = inverse_left_mask(y,7,2636928640)
y = inverse_right(y,11)
return y&0xffffffff
print(recover(0xf1c680f8))
'''
for i in s:
print(recover(i))

y = extract_number(o)
print('y=',y,'o=',o)
print(recover(y) == o)
'''

MT32的一些基本属性:
$(w,n,m,r)=(32,624,397,31)$
$(a,f)=(9908B0DF_h,1812433253)$
$(u,d,s,b,t,c)=(11,FFFFFFFF_h,7,9D2C5680_h,15,EFC60000_h)$
$l=18$

0x04 具体题目中分析

0xCTF PRNG2详解

首先我们看一下源代码

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
from Crypto.Util.number import*
from secret import flag
assert flag[:6] == "0xCTF{"
class MT():
def __init__(self, seed):
self.state = [seed]+[0]*23
self.flag = 0
self.srand()
self.generateNumbers()

def srand(self):
for i in range(23):
self.state[i+1] = 1812433253 * (self.state[i] ^ (self.state[i] >> 27)) - i
self.state[i+1] &= 0xffffffff

def generateNumbers(self):
for i in range(24):
y = (self.state[i] & 0x80000000) | (
self.state[(i+1) % 24] & 0x7fffffff)
temp = y >> 1
temp ^= self.state[(i + 12) % 24]
if y & 1:
temp ^= 0x9908b0df
self.state[i] = temp

def getRandomBits(self):
if self.flag == 24:
self.generateNumbers()
self.flag = 0
bits = self.Next(self.state[self.flag])
self.flag += 1
return long_to_bytes(bits)

def Next(self, tmp):
tmp ^= (tmp >> 11)
tmp ^= (tmp << 7) & 0x9d2c5680
tmp ^= (tmp << 15) & 0xefc60000
tmp ^= (tmp >> 18)
return tmp
def Encrypt(key, char):
key = bytes_to_long(key)
temp = hex(pow(ord(char), 65537, 2**8-1) ^ key)[2:]
return '0'*(32-len(temp))+temp
if __name__ == "__main__":
mt = MT(getRandomNBitInteger(32))
c = ''
for i in range(len(flag)):
c += Encrypt(b''.join([mt.getRandomBits() for _ in range(4)]), flag[i])
print(c)

这道题对标准的MT进行一下分析:与标准算法相比,只有$n$的值从$624$变成了$24$。

然而一个很显然的事实是:我这个密码学fw根本看不懂这么长的代码,怎么办?答案当然是靠输出来调试调试程序究竟是如何运行的。通过加运行可以看到:对于每一位字符,这个处理器会处理$4$次,然而每一次。

题目给出了一个很长的$c$字符$16$进制字符串,所以我们可以用C++等工具,把字符串$c$分为$8$位一小组(每组刚好是$32$位二进制数),$4$小组以大组。根据代码调试分析一下,每一大组的最后一个数字与明文对应的字符进行了异或操作,所以对于这$6$个数字来说,我们可以通过Win10自带的计算机(或者手搓),可以得到异或前的数字,也就是程序最后输出的bytes

例如:第一行最后一个数为$617d7a88_h$我们可以根据第一个字符为'0',推断出第一次异或的内容为$30_h$,进而得到异或前的bytes值为$617d7aB8_h$

根据题目assert内容,我们知道了字符串前$6$位,因此我们可以上脚本考虑恢复原来的寄存器内部的$24$位。

在这里有一个小细节:$x^{65537} \equiv x\mod 255$.因为$\phi(255)=128$,所以根据费马小定理有$x^{65536}\equiv 1\mod 255$,这个结论我们就推出来了。

把我们分割出来的前$24$个并进行简单处理过的十六进制数代入上面的求逆脚本,我们就可以得到第一组寄存器内的内容了。

简单地改一下代码初始化部分,删去__init__中的srand和generateNumbers。把初始化的seed参数和主函数中的getRandomNBitInteger(32)删去。然后每次输出mt.getRandomBits(),就可以得到一个个解(推荐$4$个一行,以$16$进制输出)

如果你是按照推荐的做法做的,我们可以一个一个比对一下(左边为程序输出结果,右边为给出来的数值),此处为程序输出与给出数值第$7$到第$9$行的比较。

1
2
3
a46e5465 533477c6 3f7f5649 cc96ec79 | a46e5465 533477c6 3f7f5649 cc96ec49
8bebeb18 c6f90a3c 38ff0c8a 0837182e | 8bebeb18 c6f90a3c 38ff0c8a 0837181b
31ba3fa7 efaee340 f9b70a82 a6fafa6f | 31ba3fa7 efaee340 f9b70a82 a6fafa57

很显然,正如我们预期:最后的一个数字不一样,并且刚好有点略微的差别,这就说明这是个跟某个数异或过的结果,而那个数,恰好就是那一位字符的ASCII码值。我们只需要用C++的freopen提取出两处的第$4$位,然后异或一下就得出结果了(如果你用的C++务必把数值类型设置成unsigned而不是int,不然十六进制中大于等于$80000000_h$会被标记为负数,导致异或结果出错)

最后异或完成的结果就是flag。

0xGameDiv3

0xGame Div 3 题解

About

第三周,密码学难度还可以,前2题难度不大,第3题难度有点大,不过还是能够用一天的时间切出来了。不过第三周结束还没有到达到7000分,第一周就有很多全栈大佬7000了,我还没他们1/3的效率高。看来奖励拿不到了。。

Crypto

1. signinRSA

这道题看到时签到题,读了一下代码,这跟上一周的parityOracle竟然有$99$%的相似。

不多说,直接复制上周写好的脚本 ,改一下nc地址,把上周脚本的倒数第$8$行的recnum=int(recnum[-1])改为recnum=int(recnum[-1],16),然后把倒数第$7$行和倒数第$5$行的对recnum的判断加上%$4$操作(如下),直接运行,几分钟就出结果了。

1
2
3
4
if recnum%4==1 or recnum%4==3:
L=M+1
if recnum%4==0 or recnum%4==2:
R=M-1

2.easyRSA

先看一下题目的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
from secret import flag

m = bytes_to_long(flag.encode())
e = 65537
p, q = getPrime(1024), getPrime(1024)
d = inverse(e, (p-1)*(q-1))
x = 11*d+7*(p-1)*(q-1)
c = pow(m, e, p*q)

print("n =", p*q)
print("c =", c)
print("x =", x)
## 给出部分略

题目给出了$n,c,x$的值(当然也有$e=65537$),其中$x=11d+7\phi$ ,所以这道题不同寻常之处就是给出了$x$,故突破口在x处。

通过之前RSA中相关知识可知:$d$ 是$e$在模$\phi$意义下的乘法逆元,也就是$ed \equiv 1 \mod \phi$ 。而由于$p,q$均为质数,所以$\phi=(p-1)(q-1)$

既然题目给出$x=11d+7phi$ ,而$d,phi$均为未知量。所以根据方程校园思想,我们可以两边同乘$d$,得到$ex=11de+7e \phi$ 。这个式子对$\phi$取模之后,我们可以得到$ex \equiv 11 \mod \phi$,这时候这个式子仅剩下一个未知数,所以我们可以提出$\phi$ ,得到$k\phi=ex-11$

在$\phi=(p-1)(q-1)=pq-p-q+1=n-p-q+1$,由于$p,q$均为$1024$位,$n$为$2047$位,远远大于$p+q$。故$\phi$的二进制位数跟$n$应该基本是一样的,计算可知,$phi$是$2068$位,所以$k$应当是$21$位或者$22$位,也就是$k∈[2^{21},2^{22})$。

我们用以下脚本枚举$k$,然后直接进行long_to_bytes 的操作,虽然有大概$50$多组解,然而最像flag的只有一组,故我们就得到了flag。

1
2
3
4
5
6
7
8
9
10
11
12
from given import n,x,e,c
from Crypto.Util.number import *
def solve(T):
tot=0
for i in range(2**20,2**22):
if T%i==0 and T//i%2^1 :
P=T//i
d=inverse(e,P)
print(long_to_bytes(pow(c,d,n)))
T=e*x-11
solve(T)

3. paddingOracle

又是一道Oracle,想到上一条Oracle我搞了好久= =。果然,上题12小时,还没人做出来。上题18小时后,才有人拿一血。我就比较逊了。上题35小时才把2血拿到。感觉后面密码学题目会越来越难的样子,awsl

简单地看了一下相关资料,然而本人太菜,连书都看不懂,最后摸索了12小时才搞懂题目意思,就让我用简洁的语言讲一下这道题的意思吧

首先,服务器会给你一个长度为$32$位的$16$进制数为初始向量,然后再给你$32k$个$16$进制数为密文(本题中$k=3$,也就是一共$96$位)。有些题目它直接给你一个$32(k+1)$位的$16$进制数,这个时候就默认最前面$32$位为初始向量,后面的$32k$位作为密文。

得到初始向量后,将密文分为$k$组,每组$32$位。记初始向量为$I_0$,后面的密文组为$I_1,I_2,I_3,…,I_k$

这个时候,我们还需要$3$个$16$位数组:$Clc$、$Tlc$和$Alc$,分别用于存储每一次解密的枚举值、中间值和破解出来的明文

第一轮枚举,我们枚举$Clc$最后一个数字也就是$Clc_{15}$,当服务器返回success时,计算$Tlc_{15}=Clc_{15}$xor$1$的值,然后轮数进入第二轮,用$Tlc_{15}$更新$Clc_{15}$,也就是$Clc_{15}=Tlc_{15}$ xor $2$。

需要注意的是:第$p$轮枚举,我们枚举的值是$Clc_{16-p}$,用$Clc_{16-p}$更新$Tlc_{16-p}$为$Clc_{16-p}$ xor $p$,然后轮数进入$p+1$,这时我们需要用$Tlc_{16-p}$及其以后所有解出来的$Tlc$去改变所有已知的$Clc$值,也就是把后面所有的$Clc$改为 $Tlc$ xor $p+1$**。换句话讲就是说$Tlc$解出来之后永远不能变,$Clc$每一次解出来以后会被不断更新。$Clc$更新$Tlc$,只更新最新解出来的一位,$Tlc$更新$Clc$,需要更新解出来的所有$Clc$内容**

上面的解释可能比较抽象,那我就用下面的例子来解释一下吧(数字下标$h$表示$16$进制,也就是$14_h$的真实值为十进制的$20$:

Round 0

初始状态:

$Clc=[00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00]_h$

$Tlc=[00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00]_h$

Round 1(枚举 $Clc_{15}$ )

第$1$轮,我们枚举$Clc_{15}$的值,假设我们枚举到$Clc_{15}=78_h$的时候服务器发回Success

那么此时:$Clc=[00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,$$78$]$_h$

用$Clc_{15}$更新$Tlc_{15}$,$Tlc_{15}=Clc_{15}$ xor $1$(轮数)$=79_h$

$Tlc=[00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,$$79$]$_h$

Round 2(枚举$Clc_{14}$ )

然后进入第$2$轮,我们首先得更新一下$Clc_{15}$的值为$Tlc_{15}$ xor $2=7B_h$

此时$Clc$发生了变化:$Clc=[00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,$$7B$]$_h$

然后我们枚举$Clc_{14}$的值,假如我们枚举到$Clc_{14}=52_h$时服务器返回Success

那么此时:$Clc=[00,00,00,00,00,00,00,00,00,00,00,00,00,00,$$52$$,7B]_h$

用$Clc_{14}$更新$Tlc_{14}$,$Tlc_{14}=Clc_{14}$ xor $2$(轮数)$=50_h$

此时的$Tlc$:$Tlc=[00,00,00,00,00,00,00,00,00,00,00,00,00,00,$$50$$,79]_h$

Round 3(枚举$Clc_{13}$)

进入第$3$轮,此时一个易错点(敲黑板)出现了:由于此时已经出来了$Clc_{14}$和$Clc_{15}$,第$3$轮异或值为$3$,所以我们要对$Clc_{14}$和$Clc_{15}$都进行异或$3$的操作

此时:$Clc=[00,00,00,00,00,00,00,00,00,00,00,00,00,00,$$53,78$$]_h$,两位都进行了更新

所以以上操作就是我们所讲的:$Clc$更新$Tlc$ 只更新这次解出来的一位,而$Tlc$更新$Clc$,需要更新$Clc$中已经解出来的所有$Clc$值

$16$个$Tlc$解出来后,本轮$Alc$就等于$Tlc$ xor $I_{m-1}$($m$为第$m$解密)。然后重新初始化,进行下一大轮的解密。$k$轮解密结束,我们就得到了所有的明文了(注意过滤掉里面的无关字符)

这个该死的脚本写了我98行,7个子函数。还是比较烦人的。因为一开始没规划好导致一会用$16$位数组(每个正数不超过$255$),一会用$32$位数组(每个正数不超过$15$)。虽然写起来简单,但还是减少了代码的可读性,究其原因,只有一个:作为密码学废物的我太菜了

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
98
99
100
101
from pwn import *
from Crypto.Util.number import *
from hashlib import sha256
def getyanzhengma(s16len,s64len):
LTSNMS="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
assert len(s16len)==16 and len(s64len)==64
for i1 in LTSNMS:
for i2 in LTSNMS:
for i3 in LTSNMS:
for i4 in LTSNMS:
if sha256((i1+i2+i3+i4+s16len).encode()).hexdigest()==s64len:
return i1+i2+i3+i4
def Transnbs(s):
T=[0 for _ in range(16)]
for i in range(16):
T[i]=int(s[2*i:2*i+2],16)
return T
def Transstr(x32):
Cmb=b""
Qld=b"0123456789abcdef"
for i in range(32):
Cmb+=Qld[x32[i]]
return Cmb
def x32tox16(x32):
X16=[0 for _ in range(16)]
for i in range(16):
X16[i]=x32[2*i]*16+x32[2*i+1]
return X16
def x16tox32(x16):
X32=[0 for _ in range(32)]
for i in range(16):
X32[2*i]=x16[i]//16
X32[2*i+1]=x16[i]%16
return X32
def findtwonum(x32,loc,sender,Strcchp):
print("You are entered")
S32=x32
for i in range(256):
S32[2*loc]=i//16
S32[2*loc+1]=i%16
Te=Transstr(x32)
for j in range(3):
Info1=sender.recvline(keepends=False)
Info1=sender.recv(numb=44,timeout=20000)
sender.send(b"1")
Info1=sender.recv(numb=44,timeout=20000)
sender.send(Te)
Info1=sender.recv(numb=44,timeout=20000)
sender.send(Strcchp)
assert len(Te)==32 and len(Strcchp)==32
R=sender.recvline(keepends=False)
if(R[:4]=="succ"):
return S32
def Decrypt1(iiv,cchp,Strcchp,sender):
Cel=[0 for _ in range(32)]
Tlc=[0 for _ in range(16)]
Alc=[0 for _ in range(16)]
cnt,Rnd=15,1
while(cnt+1):
Cel=findtwonum(Cel,cnt,sender,Strcchp)
Clc=x32tox16(Cel)
Tlc[16-Rnd]=Rnd^Clc[16-Rnd]
print('Tlc=',Tlc)
Rnd+=1
cnt-=1
for i in range(Rnd-1):
Clc[15-i]=Tlc[15-i]^Rnd
print('Tlc xor',Rnd,'=', Clc)
Cel=x16tox32(Clc)
print(Transstr(Cel))
for i in range(16):
Alc[i]=iiv[i]^Tlc[i]
return Alc
#--------MAIN BELOW---------#
sh=remote("49.235.239.97",10003)
while True:
str1=sh.recvline(keepends=False)
print(str1)
if(str1[0:6]=="sha256"):
break
yanzhengma=(getyanzhengma(str1[12:28],str1[33:97]))
sh.send(yanzhengma)
print("[NOTE]SENT YANZHENGMA")
str1=sh.recvline(keepends=False)
iv=str1[19:]
str1=sh.recvline(keepends=False)
print(str1)
y=str1[12:]
BA,BB,BC=y[0:32],y[32:64],y[64:96]
I,A,B,C=Transnbs(iv),Transnbs(BA),Transnbs(BB),Transnbs(BC)
Ans=Decrypt1(I,A,BA,sh)
print ('Ans=',Ans)
Bns=Decrypt1(A,B,BB,sh)
print ('Bns=',Bns)
Cns=Decrypt1(B,C,BC,sh)
print ('Cns=',Cns)
print(Ans,Bns,Cns)
#[48, 120, 71, 97, 109, 101, 123, 55, 48, 54, 52, 97, 98, 52, 56, 45]
#[51, 99, 53, 102, 45, 52, 50, 99, 49, 45, 97, 100, 51, 51, 45, 54]
#[99, 101, 98, 101, 98, 98, 102, 101, 101, 57, 101, 125, 4, 4, 4, 4]

RSA Notes

huangx607087学习RSA的笔记

O-About

一个密码学废物的学习笔记,很菜,别看

I-What is RSA

体制:
1.选择两个大质数$p$,$q$,计算$n=p×q$

2.计算$\phi=(p-1)(q-1)$,也就是$n$的欧拉函数(也就是小于$n$的正整数中与$n$互质数量的个数)

3.取一个数字$e$,使$e,\phi$互质

4.计算$d$,使$ed\equiv 1 \mod \phi$

5.加密函数:$c=E(m)=m^e \mod n $

6.解密函数:$m=D(c)=c^d \mod n $

II-9种RSA题型的总结

0x01 直接给出$p,q,c,e$或者$n=p^k$的题目

直接根据加密体制计算即可,有crypto这个python库的可以直接用inverse(e, (p-1)*(q-1))求出$d$

$n=p^k$时,$\phi=p^k-p^{k-1}$

0x02 只给出了$n,c,e$

这种情况一般$n$是可以暴力分解的,上yafu即可

0x03 只给出了$n,c,e$并且$e=3$的情况

根据$c=E(m)=m^3 \mod n $,也就是$m^3=c+kn,k∈${$0,1,2,3,…$},这个时候可以枚举$k$的值,通过二分$m$确定$m$的值,一般$k$不会太大的

0x04 只给出了$n,c,e$并且$\ln e≈\ln n$(也就是$e$非常大的时候)

由于$ed \equiv 1 \mod n$ 所以这时$d$可能会很小,直接枚举爆破$d$即可

0x05 给出了$n,c,e$并且给出$f(d,\phi)$的一个一次式

直接求出$ef(d,\phi)$的值,然后确定模数

0x06 已知$n,c,e$,$e=3$,并且得知$m-(m \mod 2^k)$的值

这种情况下根本不可能用0x03的方法,因为$k$值也很大

在Sagemath中的Notebook上打开网页,创建一个Sagemath网页文件,把以下代码补完整后运行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n = #你已知的n值
e = 3
m = randrange(n)#不要改
c = pow(m, e, n)#不要改
beta = 1
epsilon = beta^2/7#不要改
nbits = n.nbits()#不要改
kbits=#m被掩盖的字位数
print(nbits,kbits)
mbar = #你得到的不完整的m值
c = #你得到的c值
print ("upper %d bits (of %d bits) is given" % (nbits-kbits, nbits))
PR.<x> = PolynomialRing(Zmod(n))
f = (mbar + x)^e - c
print (m)
x0 = f.small_roots(X=2^kbits, beta=1)[0] # find root < 2^kbits with factor = n1
print( mbar + x0)

0x07 Parity Oracle

直接看0xGame Div 2的相关内容

0x08已知$n,c,e$,$e=3$和$p-(p \mod 2^k)$的值

在Sagemath中的Notebook上打开网页,创建一个Sagemath网页文件,把以下代码补完整后运行

1
2
3
4
5
6
7
8
9
10
11
n = #你得到的n值
p_fake = #你得到的不完整的p值
pbits = p_fake.nbits()
kbits = #p失去的低位
pbar = p_fake & (2^pbits-2^kbits)
print "upper %d bits (of %d bits) is given" % (pbits-kbits, pbits)
PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar
x0 = f.small_roots(X=2^kbits, beta=0.4)[0] # find root < 2^kbits with factor >= n^0.3
p= x0 + pbar
print p

有$p$就可以得到$q$,进而就很简单了

0x09 已知$n,c,e$,$e=3$和$d \mod 2^k$值

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
def partial_p(p0, kbits, n):
PR.<x> = PolynomialRing(Zmod(n))
nbits = n.nbits()
f = 2^kbits*x + p0
f = f.monic()
roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.3) # find root < 2^(nbits//2-kbits) with factor >= n^0.3
if roots:
x0 = roots[0]
p = gcd(2^kbits*x0 + p0, n)
return ZZ(p)
def find_p(d0, kbits, e, n):
X = var('X')
for k in xrange(1, e+1):
results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)
for x in results:
p0 = ZZ(x[0])
p = partial_p(p0, kbits, n)
if p:
return p
if __name__ == '__main__':
n = #你得到的n值
e = 3
d = #你得到的d的低位
beta = 0.5
epsilon = beta^2/7
nbits = n.nbits()
print "nbits:%d:"%(nbits)
#kbits = floor(nbits*(beta^2+epsilon))
kbits = nbits - d.nbits()-1
print "kbits:%d"%(kbits)
d0 = d & (2^kbits-1)
print "lower %d bits (of %d bits) is given" % (kbits, nbits)
p = find_p(d0, kbits, e, n)
print "found p: %d" % p
q = n//p
print d
print inverse_mod(e, (p-1)*(q-1))

0x0A 模不互素

这种题目一般给出$2$组$n,e,c$的值,我们可以求一下$\gcd (n_1,n_2)$ 如果不等于$1$的话,我们就得到了$n$的一个因数$p$,一除就得到了$q_1,q_2$,分别求解即可得到明文。

0xGameDiv2

0xGame Div 2 题解

About

第二周,难度比第一周大好多,只切了两道密码题,到极限了,然后只有3800多分,Top1,2两个全栈大佬都有9000+分,我果然好菜啊

Crypto

1.SmallModulus

提示:做这道题的时候!手速!一定要快!一定要快!一定要快!!!!!,无论是输4位验证码还是输入提示中的1!!!我TM因为手速太慢导致远程连接超时,整个下午都耗费在上面了,忍不住吐槽两句,太草了!

虽然我不知道sha256是个什么东西,原理是什么,不过我还是用一个python脚本,四重循环枚举出了每次需要输入的验证码内容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from hashlib import sha256
s="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
t="5d755ec7addaff634907855979bc02d0c279ab60ce736754faa895a81938b3c9"
R="EsHH8BQQsfIMp7gC"
assert len(R)==16
assert len(t)==64
for i1 in s:
for i2 in s:
for i3 in s:
for i4 in s:
XXXX=i1+i2+i3+i4
if sha256((XXXX+R).encode()).hexdigest()==t:
print (XXXX)

最终我还是手速加快,迅速地得到了许许多多组数据… …,其中一组输出提示:flag mod 9c7f17669e90b219 (in hex) : 3316d33a70b0a941

加上程序的核心代码可知,输出提示mod后买你的那个数字是质数

1
2
3
4
5
if choice == b"1":
module = getPrime(64)
self.send(("flag mod {} (in hex) : {}".format(
hex(module)[2:], hex(m % module)[2:])).encode())
continue

显然,这道题想告诉你的消息无非是许多组类似:$x \equiv a_i \mod m_i$ ,(其中$m$为质数)。根据我这个密码学废物和oi废物的理解,这道题应该是考中国剩余定理(CRT)。

查了一下,百度百科上是这样讲解CRT的:

设$M=\prod_{i=1}^n m_i$,$M_i=M/m_i$,$t_i$为$M_i$模$m_i$的逆元,也就是$M_it_i \equiv 1 \mod m_i$。则$x \equiv \sum_{i=1}^{n} a_it_iM_i \mod M$。也就是$x = \sum_{i=1}^{n}a_it_iM_i +k M$

所以,我们只需要处理一下得到的数据,然后将其放入数组$a$和$m$中。还要用到求逆元的代码(直接从上一个脚本直接移植过来的)。

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
from Crypto.Util.number import *
from MsandAs import m,a
def EX_GCD(a,b,arr): #扩展欧几里得
if b == 0:
arr[0] = 1
arr[1] = 0
return a
g = EX_GCD(b, a % b, arr)
t = arr[0]
arr[0] = arr[1]
arr[1] = t - (a // b) * arr[1]
return g
def ModReverse(a,n): #ax=1(mod n) 求a模n的乘法逆x
arr = [0,1,]
gcd = EX_GCD(a,n,arr)
if gcd == 1:
return (arr[0] % n + n) % n
else:
return -1
arr = [0,1,]

# FUNCTION MAIN#
piM=1
for i in range(40):
piM*=m[i]
print(piM)
t =[0 for _ in range(40)]
M =[0 for _ in range(40)]
for i in range(40):
M[i]=piM//m[i]
for i in range(40):
t[i]=ModReverse(M[i],m[i])
B=0 #B为所有atM之积的和
for i in range(40):
B+=a[i]*t[i]*M[i]
B%=piM
print(B)
print(long_to_bytes(B))

最后的long_to_bytes(B)算出来的就是答案了。

2.parityOracle

这道题需要用到Pwntools,也就意味着需要安装虚拟机。本fw安装一个虚拟机安装了三天,太废了

我们先了解以下Pwntools在密码学题目里面抓包时需要用到的几个指令:

1
2
3
4
5
6
7
8
9
10
11
本地 :sh = porcess("./level0")
远程:sh = remote("127.0.0.1",10001)
关闭连接:sh.close()
sh.send(data) #发送数据
sh.sendline(data) #发送一行数据,相当于在数据后面加\n
sh.recv(numb = 2048, timeout = dufault) # 接受数据,numb指定接收的字节,timeout指定超时
sh.recvline(keepends=True) #接受一行数据,keepends为是否保留行尾的\n
sh.recvuntil("Hello,World\n",drop=fasle)# 接受数据直到我们设置的标志出现
sh.recvall() # 一直接收直到EOF
sh.recvrepeat(timeout = default) # 持续接受直到EOF或timeout
sh.interactive() # 直接进行交互,相当于回到shell的模式,在取得shell之后使用

然后再看一下题目程序中的给出的最核心的代码

1
2
3
4
5
6
if choice == b"1":
cip = self.recvhex(prompt=b"Your cipher (in hex): ")
if not cip:
break
result = pow(cip, self.d, self.n) % 4
self.send(hex(result)[2:].encode())

查阅CTFWIKI上的资料可以知道,我们第$k$次发送只需要向服务器发送数值$C×2^{pk} \mod N$即可。不过需要注意的是要把$10$进制数字转化为$16$进制的字符串发送(不含前缀0x),并且每次向服务器发送的所有内容要转换成bytes类型(包括指令1)。

每次截取字符串的时候可以通过输入看看截取到字符串的是什么东西,然后根据字符串的下标关系(这个要在调试的时候自己数)选择自己需要的部分并保存。某些地方也可以自己加一点输出提示看看程序是否在运行。当然,为了确保自己抓到的内容正确,也可以加几个assert语句试试看看是否出现了报错。

初始化工作做好之后,我们就可以开始进行二分过程了。根据CTFWIKI上的提示:设$L,R$为二分的两端(初始值为$L=0,R=N$)。.然后每次取$M$=$(L+R)/2$。如果得到的数字是奇数。那么我们我们下一次截取$(M,R)$区间继续二分。如果得到的数字是偶数,那么我们截取$(L,M)$区间进行二分。由于CTFWIKI上对这一块的原理进行了详细讲述,故此处不多赘述。

最后,我们可以用下面的脚本来进行二分操作。(前面抓取验证码的程序与上一题的验证码程序一模一样)

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
from pwn import *
from hashlib import sha256
from Crypto.Util.number import *
def getyanzhengma(s16len,s64len):
LTSNMS="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
assert len(s16len)==16 and len(s64len)==64
for i1 in LTSNMS:
for i2 in LTSNMS:
for i3 in LTSNMS:
for i4 in LTSNMS:
if sha256((i1+i2+i3+i4+s16len).encode()).hexdigest()==s64len:
return i1+i2+i3+i4
sh=remote("49.235.239.97",10001)
while(True):
str1=sh.recvline(keepends=False)
if(str1[0:6]=="sha256"):
break
yanzhengma=(getyanzhengma(str1[12:28],str1[33:97]))
sh.send(yanzhengma)
print("[NOTE]SENT YANZHENGMA")
e,n,c=1,1,1
str2=sh.recvline(keepends=False)
e=str2[18:]
str2=sh.recvline(keepends=False)
n=str2[4:]
str2=sh.recvline(keepends=False)
c=str2[4:]
e,n,c=int(e),int(n),int(c)
print("[NOTE]F=GOT enc")
L,R,Clk=0,n,1
while L<=R:
if(Clk%50==0):
print(L,R,Clk)
M=(L+R)//2
for i in range(3):
str3=sh.recvline(keepends=False)
sh.send(b"1")
a=(c*pow(2,e*Clk,n))%n
sh.send(str(hex(a))[2:].encode())
recnum=sh.recvline(keepends=False)
recnum=int(recnum[-1])
if recnum==1 or recnum==3:
L=M+1
if recnum==0 or recnum==2:
R=M-1
Clk+=1
print(L)
print(long_to_bytes(L))

注意:每次程序跑的时候会存在一定误差,不过一般不超过$100$,这就意味着解出来的字符串的最后$1$到$2$位可能会不对。不过我们可以根据最后一个字符是否成词,或者根据题目中的提示,也可以解出来最后的flag

Nfsr

关于NFSR学习的一些笔记

0x01解题背景

10月6日刚把0xCTF上的所有密码学题目AK,这道题卡了我一周,得到了学长的帮助,查了CTFWIKI和学长的博客才勉强做出来,我果然是个密码学废物

0x02简介

NFSR,又称非线性移位寄存器,在模$2$的意义下,异或可以视作加法,按位与可以视作乘法。所以LFSR一般都是只有异或,而NFSR有与运算。并且与运算的性质可以知道,这是一个不可逆的运算 。

一般情况下,NFSR是多个LFSR通过一个函数$F(r_1,r_2,…,r_n)$,其中$F$函数中与运算和异或运算均存在,根据与运算的不可逆性,可知$F$函数的不可逆性,所以显然,我们写不出$F$函数的逆函数$F^{-1}$。

0x03 解题方法

我们可以一开始枚举每一个lfsr及其输出结果,看看$F(r_1,r_2,…,r_n)=r_i,i∈${$1,2,3,…,n$}的概率$P_i$。找出所有不为概率不为$0.5$的$P_i$,然后用以下的C++脚本暴力枚举$r_i$的初始值。

一般先定义$N=30$,区间筛选邻域$U(P,0.05)$判断存在性,然后不断调大$N$为$100,200,400,600,900,1200,2700$,直到最后运行只剩下一个结果即可,逐步调大主要是为了判断结果的存在性和检验参数的正确性。

如果$N$超过$600$算出来的数值仍然比较多的话,我们可以把区间筛选邻域由$U(P,0.05)$为$U(P,0.03)$或者$U(P,0.02)$增大筛选要求。

本代码以$18$位,概率$0.625$为例,实际应用应当调参

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
#include<bits/stdc++.h>
#define N 900
using namespace std;
int a[N+12];
double G=0;
int culc(int x)
{
int k=x,s=0;
while(k)
{
s+=k%2;
k/=2;
}
return s;
}
int lfsr(int r,int m)
{
int t=(r<<1)&0xffffff;
int s=culc(r&m)&1;
return (t^s);
}
void solve(int B,int msk,double pos1,double pos2)
{
int r1,i,s1;
for (r1=(1<<(B-1));r1<(1<<(B));r1++)
{
s1=r1;
G=0;
for(i=1;i<=N;i++)
{
s1=lfsr(s1,msk);
if(a[i]==(s1&1)) ++G;
}
if((G/N>pos1)&&(G/N<pos2))
{
printf("%d:pos=%.4lf%\n",r1,G/N);
}
}
}
int main()
{
freopen("data.txt","r",stdin);
int i,j;
for(i=1;i<=N;i++)
{
char c;
scanf("%c",&c);
a[i]=(c=='1');
}
solve(18,0x3da61,0.595,0.655);
return 0;
}

最后剩下的$0.5$的概率数量如果只有$1$个或者$2$个,可以开暴力枚举($2$个的话请保证能够两重循环可行)

如果最后仍然剩下很难暴力枚举的$0.5$的概率,可以把未知的量跟已知的构造异或函数,使概率较大地偏离$0.5$(取$<0.4$或者$>0.6$的值为宜)。将已知的和未知的同步起来,也可以解出最后的答案。

所有的lfsr都解出来的时候,我们的题目也就解出来了,就可以得到flag了。

0xGameDiv1

0xGame Div 1 题解

About

第一周题目还算比较简单,把密码切了两题,Misc简单看了看。搞了2000多分,很多大佬7000多分,wtcl

Crypto

1.Calendar

根据给的日历图片,THU1表示第一行的星期四对应的日期,同理,TUE2表示第二行的星期二对应的日期,不是这个月第二个星期二对应的日期。纠错方法:有个码是TUE4,如果按照后者进行理解,那么得到的值是$27$。同时题目给了提示为:“明文字母全为小写,请将明文包含在0xGame{}内提交”,说明每个数字不会超过$26$。(因为我一开始就是错误的理解,然后发现了问题)

这个可以直接手打出所有的数字,保存在一个txt文件中,然后用下面的脚本就可以得出flag了

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
int main()
{
int x;
freopen("1.txt","r",stdin);
while(~scanf("%d",&x))
{
printf("%c",x+96);
}
return 0;
}

2.easyXor

必备常识:已知$a$ xor $ b = c$ ,可以得到$c$ xor $b = a$

下面是题目的Python代码:

1
2
3
4
5
6
7
8
9
10
from random import randint
from secret import flag

flag+="^"
cipher=[]
for i in range(len(flag)-1):
cipher.append(ord(flag[i])^ord(flag[i+1]))
print(cipher)
#[72, 63, 38, 12, 8, 30, 30, 6, 82, 4, 84, 88, 92, 7, 79, 29, 8, 90, 85, 26, 25, 87, 80, 10, 20, 20, 9, 4, 80, 73, 31, 5, 82, 0, 1, 92, 0, 0, 94, 81, 4, 85, 27, 35]

很显然,题目给出了最终的输出,也知道最后增加的一位内容。从最后一位出发,我们可以一个一个回推以前的步骤。

将最后的输出结果复制到一个txt文件中,用替换功能把所有的逗号换成空格,删除无关符号,用以下的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;
stack<int>s,r;
int main()
{
freopen("1.txt","r",stdin);
int x;
while(~scanf("%d",&x))
{
s.push(x);
}
int t='^';
while(!s.empty())
{
t=t^s.top();
r.push(t);
s.pop();
}
while(!r.empty())
{
printf("%c",r.top());
r.pop();
}
return 0;
}

3.Superaffine

我们先来看一下程序代码

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
from Crypto.Util.number import *
from string import ascii_letters, digits
from random import randint
from secret import flag

assert flag.startswith("0xGame{") and flag.endswith("}")
table = ascii_letters+digits# 先小写,再大写,再数字
MOD = len(table)#mod = 62

def affine(x, a, b): return a*x+b

def genKey():
a = [randint(1, 64) for _ in range(3)]
b = [randint(1, 64) for _ in range(3)]
while GCD(MOD, a[0]*a[1]*a[2]) != 1:
a = [randint(1, 64) for _ in range(3)]
return a, b


cipher = ""
A, B = genKey()
for i in flag:
if i not in table:
cipher += i
else:
cipher += table[affine(affine(affine(table.find(i),A[0], B[0]), A[1], B[1]), A[2], B[2]) % MOD]

print("cipher =", cipher)
# cipher = t6b7Tn{2GByBZBB-aan2-JRWn-GnZB-Jyf7a722ffnZ}

很显然,这是一个仿射密码,单层加密过程为一个一次函数$y=e(x)\equiv ax+b \mod m$

Python中,ascii_letters对应一个字符串为“abc……xyzABC….XYZ”,digits对应一个字符串为”0123456789”,所以此处有$MOD=62$。

根据defgenkey可知:此处的$a_0,a_1,a_2,b_0,b_1,b_2$均为随机生成的$[1,63]$内的整数,如果暴力枚举,复杂度为$O(63^6)≈625.2亿$。所以暴力是不可以的。

化简加密公式,我们可以得到解密公式$x= d(y)\equiv a^{-1}(y-b)$。所以这里涉及到求逆元。又由于$62$为合数,$phi(62)=30$,也就是只有$30$个字符可以正确地加密并解密,说明本替换密码的密钥空间为$30×62=1860$,并不是很大。

下面我们探讨一下两重仿射密码 $e_1(x)\equiv a_1x+b_1 \mod m$ 和$e_2(x)\equiv a_2x+b_2 \mod m$,所以$e_2(e_1(x))=a_2a_1x+a_2b_1+b_2 \equiv m$,仍然是一个一次函数,还是能够写成$E=Ax+B$的形式,密钥空间不变,仍然是$30×62=1860$。所以得到一个很重要的结论:无论仿射加密有几层,密钥空间总是不变!因为可正常转换的字符数量本来就是有限的。

所以,我们根据推出的公式:$E(x)=a_2a_1a_0x+a_2a_1b_0+a_2b_1+b_2 \mod m$,写成$E(x)\equiv Ax+B \mod m$的形式,并且由于密钥空间不变,$A,B$仍然是$[1,63]$中的整数。所以我们根据代码assert的内容,写出如下的C++脚本

注:C++中不等于a!=b可以写成a-b(很毒瘤的一种写法)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
int check(int a,int b)
{
if((a*52+b+62*8)%62-19) return 0;
if((a*23+b+62*8)%62-58) return 0;
if((a*32+b+62*8)%62-1) return 0;
if((a*0+b+62*8)%62-59) return 0;
if((a*12+b+62*8)%62-45) return 0;
if((a*4+b+62*8)%62-13) return 0;
return 1;
}
int main()
{
int i,j;
for(i=1;i<=63;i++)
for(j=1;j<=63;j++)
{
if(check(i,j)) printf("A=%d B=%d\n",i,j);
}
return 0;
}
//运行结果:A=35,B=59

$y=E(x)\equiv 35x+59 \mod 62$

然后我们可以用Python的脚本,求出$35$在模$62$的意义下乘法逆元为$39$,脚本如下(下一题用到的也是这个脚本,这个脚本可以求最大公约数和逆元)

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
def EX_GCD(a,b,arr): #扩展欧几里得
if b == 0:
arr[0] = 1
arr[1] = 0
return a
g = EX_GCD(b, a % b, arr)
t = arr[0]
arr[0] = arr[1]
arr[1] = t - (a // b) * arr[1]
return g
def ModReverse(a,n): #ax=1(mod n) 求a模n的乘法逆x
arr = [0,1,]
gcd = EX_GCD(a,n,arr)
if gcd == 1:
return (arr[0] % n + n) % n
else:
return -1
arr = [0,1,]


a=35,b=62

print("niyuan",ModReverse(a,b))
print('zuidagonyueshu',EX_GCD(a,b,arr))

由于$62-59=3$,所以$59$在模$62$的意义下加法逆元为$3$,所以解密函数为$x=D(y)\equiv 39y+3 \mod 62$

同样,将密文放入一个txt文件,用C++写一个脚本,即可求出明文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
const string s="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
int f(int x)
{
return ((x+3)*39)%62;
}
int main()
{
int i,j;
char c;
freopen("tst2002.txt","r",stdin);
while(cin>>c)
{
if((int)(s.find(c))==-1) cout<<c;
else
{
cout<<s[f(s.find(c))] ;
}
}
}

4.equationSet

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
from secret import flag

e = 65537
m = bytes_to_long(flag.encode())
p, q, r = getPrime(512), getPrime(512), getPrime(512)

n = p*q*r
c = pow(m, e, n)
print(c)
print(n)
print(p+q+r)
print(p*q+p*r)
# 给出部分略

这是一个简单的RSA变式,三个质数相乘,根据我们得到的线索:有以下3个数据可用:$S=p+q+r$,$n=p×q×r$,$T=p×(q+r)$。

由于$p,q,r$均为质数,我们只需要求$T$和$n$的最大公约数即为$p$的值,然后我们很快就得到以下两个数字:$M_2=q×r$和$T_2=q+r$。

怎么解$q,r$? 换元解二次方程?显然很麻烦!

实际上我们不需要解出来这2个值,因为RSA加密为$c=m^e \mod n$,解密为$m=c^d \mod n$,其中$d$是$e$在模$phi(n)$的逆元,所以我们只需要求$phi(n)$,又因为$p,q,r$均为质数,所以$phi(n)=phi(p)×phi(q)×phi(r)=(p-1)(q-1)(r-1)=(p-1)(M_2-T_2+1)$

然后我们再用上一题的那个脚本解出$d$,进而得到$m$

得到$m$后,来一波long_to_bytes操作就得到了flag。

注:未配置相关环境的话,可以使用进制分解的手段,将$m$分解为$256$进制,然后一位一位逐一转成字符

5.Fibonacci

先放一下题目中最核心的代码,并且题目给出了 $r,n,c,N$ 这 $4$ 个数的值

1
2
3
4
5
6
7
8
9
10
n = reduce(lambda a, b: a*b, [getPrime(4) for _ in range(4)])
r = getRandomNBitInteger(67)
S = sum([F(i) % n for i in range(r)])
p = next_prime(S**16)
q = getPrime(p.bit_length())
m = bytes_to_long(flag)
c = pow(m, 65537, p*q)
N=p*q
#n=34969
#r,c,N数字过大,此处略去

这仍然是个RSA的变式题。首先我们可以看到 $p$ 跟$S$的值是密切相关的。所以我们应当先求出$S = \sum_{i=1}^r (F_i \mod 34969) $的值

根据斐波那契数列的递推公式$F_i=F_{i-1}+F_{i-2}$,其中$F_1=F_2=1$,我们可以知道:如果所有的$F_i$对同一个数取模,这个数列应当是有周期性的,所以我们应当求这个数列的周期。而模数为$34969$,并不是一个很大的数字,所以我们可以估计周期不超过$500万$,用以下的C++脚本确定周期

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
int n,f[9607087];
int main()
{
int i,j;
f[1]=f[2]=1;
for(i=3;i<=5000000;i++)
{
f[i]=(f[i-1]+f[i-2])%34969;
if(f[i]==f[i-1]&&f[i]==1) printf("%d\n",i-1);
}
return 0;
}

由于输出的第一个数字为$33661$,说明$f_{33661}=f_{33662}=1$,确定周期为$33660$,这样我们可以求出一个周期内的数字之和$S_T = \sum_{i=1}^{33660} (F_i \mod 34969)$。

然后,我们在python中计算r//33660r%33660的值,然后就可以确定数据的组数和多出来的组数了。

最终,我们得到$S=\lfloor r/33660 \rfloor × S_T +$ $ \sum_{i=1}^{r \mod 33660} (F_i \mod 34969)$。然后我们可以计算出$p$的值,进而求出$q$的值。

有了$p,q$两个数字,我们就可以求出$N$的欧拉函数 然后用跟上一题一样的脚本(Superaffine中提到的求最大公约数和逆元的脚本),用RSA解密方法迅速得出$d$和$m$,来一波long_to_bytes,得出flag。

Misc

1.签到题

这个就不写题解了吧~Rules能找到

2.easeBase

随便在百度上找个Base64加密解密网页,可以得到以下内容:307847616D657B68407070794D4953435F4D4953435F4D4953437D

观察可知这是一个$16$进制的数字,应该是ASCII码。存入一个文本文档中,然后两位一组按一个回车。最后用以下C++脚本即可得到flag

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
int main()
{
int x;
freopen("1.txt","r",stdin);
while(~scanf("%x",&x))
{
printf("%c",x);
}
return 0;
}

3.lowerBase64

根据0xgame的开头Base64加密可知:这边应该是把正确的密文全部小写后得到给出的字符串

使用以下的python脚本,每次在$k$后面加$2$位字符,可以确定后面$1$到$2$个$f$的内容,就这样手动地一步一步地扩充字符串$k$和$f$的内容,当$f$内容完整时,我们就得到了flag

1
2
3
4
5
6
7
8
9
from base64 import b64encode
from string import *
f='0xgame{'
k='mhhnyw1le'
s="abcdefghijklmnopqrstuvwxyz0123456789-{}"
for i in s:
for j in s:
if((b64encode((f+i+j).encode()).decode().lower()).startswith(k)):
print (i+j)

Web

由于本人没选择web方向,所以web简单切了2题,这两题对于主修web的是非常非常$H_2O$但我还是用了很久才做出来

1.View Source

F12就出来Flag了,Pass

2.robots协议

网址后面加/robots.txt得到一个界面,看到了Disallow内容,最后把/robots.txt改为/flaaaggg.php就得到flag了

About Me

0x01 About Me

huangx607087,2001年12月出生,高中打过OI(不过是个2=蒟蒻)。大学正在打CTF密码学方向(刚入门),现在在南京邮电大学信息安全专业20级学生(综合评价进的,因为我高考成绩不够)。

初次写博客,博客肯定很简陋。不过后期会不定时对博客进行更新。欢迎各位的关注。

自认为在博文下留言效率极低,所以本博客中并没有添加评论功能,其实是因为懒

如果各位xdm对我的博客感兴趣,可以发送邮箱至1435756429@qq.com,如果不是一个学校的话,QQ就不方便加了,470个好友,有将近200个都不知道是谁。

欢迎各位兄弟们跟我在QQ上聊天,也可以email发送邮件聊天。如果你们是密码学大佬或者只是对密码学感兴趣,当然可以找我闲聊,顺便教教我密码学,我可菜了

0x02 几个友情链接

大学的几个同学:PiCpo lakphy