21Jan2

huangx607087寒假的切题2

0.简介

在同校Soreat,Am473ur,Hermes和To1in四位密码学大佬的带领下，本密码学fw终于在密码学方面稍微懂了多一些了。BUU也刷上了1000分。不过作为一个yydfw，哎，还是要继续努力。

1.[NPUCTF2020]认清形势，建立信心

常规操作，先来看一下出题的代码：

from Crypto.Util.number import *
from gmpy2 import *
from secret import flag
p = getPrime(25)
e = # Hidden
q = getPrime(25)
n = p * q
m = bytes_to_long(flag.strip(b"npuctf{").strip(b"}"))
c = pow(m, e, n)
print(c)
print(pow(2, e, n))
print(pow(4, e, n))
print(pow(8, e, n))
'''
169169912654178
128509160179202
518818742414340
358553002064450
'''

可能作为NPUCTF2020的密码学签到题，这道题难度并不是很大：题目给出了$2^e,4^e,8^e$对$n$取模的值。不过对于$n,e$题目并没有给出。

根据基本的算数原理：$2^e×2^e=4^e,2^e×4^e=8^e$。我们假设$2^e,4^e,8^e$对$n$取模的值分别是$a,b,c$，那么我们可以得到这样两个等式：
$$
a^2-b=k_1n
$$
$$
ab-c=k_2n
$$

所以我们可以很快得到$a^2-b,ab-c$的值，然后直接放Sagemath中对这两个数进行因式分解即可。

根据图片发现共同的因数是$18195301,28977097$，那么$p,q$得解。

后面直接用C++爆破$e$的值即可，得到$e=808723997$，用时不到$10$秒，然后这道题就是正常的RSA解密了。

2.[AFCTF2018]MyOwnCBC

又是一道AES解密题，不过我们可以先来了解一下CBC模式：CBC加密模式的特点就是所有的加密连接都在一起，并且每次加密的内容都依赖于上一个加密后的状态。第一个状态由初始向量iv（可以理解为第$0$个状态）决定。

继续上一下题目的出题代码：

from Crypto.Cipher import AES
from Crypto.Random import random
from Crypto.Util.number import long_to_bytes
def MyOwnCBC(key, plain):
	if len(key)!=32:
		return "error!"
	cipher_txt = b""
	cipher_arr = []
	cipher = AES.new(key, AES.MODE_ECB, "")
	plain = [plain[i:i+32] for i in range(0, len(plain), 32)]
	print plain
	cipher_arr.append(cipher.encrypt(plain[0]))
	cipher_txt += cipher_arr[0]
	for i in range(1, len(plain)):
		cipher = AES.new(cipher_arr[i-1], AES.MODE_ECB, "")
		cipher_arr.append(cipher.encrypt(plain[i]))
		cipher_txt += cipher_arr[i]
	return cipher_txt	
key = random.getrandbits(256)
key = long_to_bytes(key)
s = ""
with open("flag.txt","r") as f:
	s = f.read()
	f.close()
with open("flag_cipher","wb") as f:
	f.write(MyOwnCBC(key, s))
	f.close()

题目先把明文分成了$32$位一组然后用AES的ECB模式进行加密的，密钥就依赖于上一个明文的加密结果。所以最后的密文长度与明文长度一致。密文一共$1696$位，可以推断一共分了$53$组。

所以我们只需要逐个读取密文，然后将密文分成$53$组存在数组里，模仿他的加密代码进行解密即可。

from Crypto.Util.number import *
from Crypto.Cipher import AES
fp=open("flag_cipher.txt","rb")
b=fp.read()
print(len(b))
C=[]
M=[]
S=""
for i in range(0,len(b),32):
    C.append(b[i:i+32])
print(len(C))
for i in range(52,0,-1):
    Enc=AES.new(C[i-1],AES.MODE_ECB)
    M=[Enc.decrypt(C[i])]+M
    S+=M[0].decode()
print(S)

最后我们程序的运行结果是这样的但我最后并没有求出iv，或许这个iv也是求不出来的吧

根据我这个fw的分析，答案应该是afctf{Don't_be_fooled_by_yourself} ，最后答案也验证了这个猜想

3.[QCTF2018]Xman-RSA

打开解密脚本：很明显，这个代码被使用了替换密码加密过了。根据自己对Python那一点点的熟悉程度的分析，很快地还原了加密源码

from gmpy2 import is_prime
from os import urandom
import base64
def bytes_to_num(b):
	return int(b.encode('hex'), 16)
def num_to_bytes(n):
	b = hex(n)[2:-1]
	b = '0' + b if len(b)%2 == 1 else b
	return b.decode('hex')
def get_a_prime(l):
	random_seed = urandom(l)

	num = bytes_to_num(random_seed)
	
	while True:
		if is_prime(num):
			break
		num+=1
	return num
def encrypt(s, e, n):
	p = bytes_to_num(s)
	p = pow(p, e, n)
	return num_to_bytes(p).encode('hex')	
def separate(n):
	p = n % 4
	t = (p*p) % 4
	return t == 1
f = open('flag.txt', 'r')
flag = f.read()
msg1 = ""
msg2 = ""
for i in range(len(flag)):
	if separate(i):
		msg2 += flag[i]
	else:
		msg1 += flag[i]
p1 = get_a_prime(128)
p2 = get_a_prime(128)
p3 = get_a_prime(128)
n1 = p1*p2
n2 = p1*p3
e = 0x1001
c1 = encrypt(msg1, e, n1)
c2 = encrypt(msg2, e, n2)
print(c1)
print(c2)
e1 = 0x1001
e2 = 0x101
p4 = get_a_prime(128)
p5 = get_a_prime(128)
n3 = p4*p5
c1 = num_to_bytes(pow(n1, e1, n3)).encode('hex')
c2 = num_to_bytes(pow(n1, e2, n3)).encode('hex')
print(c1)
print(c2)
print(base64.b64encode(num_to_bytes(n2)))
print(base64.b64encode(num_to_bytes(n3)))

首先我们先对$n_2,n_3$进行Base64解码，然后转化成数字。使用我博客中的RSA Notes 1中的相关脚本，通过共模攻击求得$n_1$。求得$n_1$后，根据模不互素，直接求$\gcd(n_1,n_2)$，很快地分解了$n_1,n_2$，最后两次解密，根据他的separate函数直接拼接明文即可，难度不高。

为保险起见还是上一下最后的脚本，共模攻击见RSA Notes 1提供的脚本

from Crypto.Util.number import *
from base64 import *
def separate(n):
	p = n % 4
	t = (p*p) % 4
	return t == 1
n2='PVNHb2BfGAnmxLrbKhgsYXRwWIL9eOj6K0s3I0slKHCTXTAUtZh3T0r+RoSlhpO3+77AY8P7WETYz2Jzuv5FV/mMODoFrM5fMyQsNt90VynR6J3Jv+fnPJPsm2hJ1Fqt7EKaVRwCbt6a4BdcRoHJsYN/+eh7k/X+FL5XM7viyvQxyFawQrhSV79FIoX6xfjtGW+uAeVF7DScRcl49dlwODhFD7SeLqzoYDJPIQS+VSb3YtvrDgdV+EhuS1bfWvkkXRijlJEpLrgWYmMdfsYX8u/+Ylf5xcBGn3hv1YhQrBCg77AHuUF2w/gJ/ADHFiMcH3ux3nqOsuwnbGSr7jA6Cw=='
n3='TmNVbWUhCXR1od3gBpM+HGMKK/4ErfIKITxomQ/QmNCZlzmmsNyPXQBiMEeUB8udO7lWjQTYGjD6k21xjThHTNDG4z6C2cNNPz73VIaNTGz0hrh6CmqDowFbyrk+rv53QSkVKPa8EZnFKwGz9B3zXimm1D+01cov7V/ZDfrHrEjsDkgK4ZlrQxPpZAPl+yqGlRK8soBKhY/PF3/GjbquRYeYKbagpUmWOhLnF4/+DP33ve/EpaSAPirZXzf8hyatL4/5tAZ0uNq9W6T4GoMG+N7aS2GeyUA2sLJMHymW4cFK5l5kUvjslRdXOHTmz5eHxqIV6TmSBQRgovUijlNamQ=='
n2=bytes_to_long(b64decode(n2))
n3=bytes_to_long(b64decode(n3))
n1=2499586809914462821807624371088011200618603528498132509598946284572455726453497171635086810524607288333625665025664872216634366700044105279185519761587818169021167370991396691510275499486673922916370294043072503635630922980240462022218565365191228535222150496387990987123639567257124081274667568443678527637259644488779394704508217357758791670308548246801142468699716221789070607334747835552167450340441488756779323653879402176647890584656379628685893686585469918686253137796663587854943386347039389769790329948165162483370187914412810153613198247569427480466488647563900948387020677830797976534568626241686906738179
p=GCD(n1,n2)
q1,q2=n1//p,n2//p
phi1,phi2=(p-1)*(q1-1),(p-1)*(q2-1)
d1,d2=inverse(0x1001,phi1),inverse(0x1001,phi2)
c1=0x1240198b148089290e375b999569f0d53c32d356b2e95f5acee070f016b3bef243d0b5e46d9ad7aa7dfe2f21bda920d0ac7ce7b1e48f22b2de410c6f391ce7c4347c65ffc9704ecb3068005e9f35cbbb7b27e0f7a18f4f42ae572d77aaa3ee189418d6a07bab7d93beaa365c98349d8599eb68d21313795f380f05f5b3dfdc6272635ede1f83d308c0fdb2baf444b9ee138132d0d532c3c7e60efb25b9bf9cb62dba9833aa3706344229bd6045f0877661a073b6deef2763452d0ad7ab3404ba494b93fd6dfdf4c28e4fe83a72884a99ddf15ca030ace978f2da87b79b4f504f1d15b5b96c654f6cd5179b72ed5f84d3a16a8f0d5bf6774e7fd98d27bf3c9839
c2=0x129d5d4ab3f9e8017d4e6761702467bbeb1b884b6c4f8ff397d078a8c41186a3d52977fa2307d5b6a0ad01fedfc3ba7b70f776ba3790a43444fb954e5afd64b1a3abeb6507cf70a5eb44678a886adf81cb4848a35afb4db7cd7818f566c7e6e2911f5ababdbdd2d4ff9825827e58d48d5466e021a64599b3e867840c07e29582961f81643df07f678a61a9f9027ebd34094e272dfbdc4619fa0ac60f0189af785df77e7ec784e086cf692a7bf7113a7fb8446a65efa8b431c6f72c14bcfa49c9b491fb1d87f2570059e0f13166a85bb555b40549f45f04bc5dbd09d8b858a5382be6497d88197ffb86381085756365bd757ec3cdfa8a77ba1728ec2de596c5ab
m1,m2=pow(c1,d1,n1),pow(c2,d2,n2)
m1,m2=long_to_bytes(m1),long_to_bytes(m2)
m1,m2=m1.decode(),m2.decode()
s,n="",len(m1)+len(m2)
po1,po2=0,0
for i in range(n):
    if(separate(i)):
        s=s+m2[po2]
        po2+=1
    else:
        s=s+m1[po1]
        po1+=1
print(s)

4.[NPUCTF2020]共 模 攻 击

PART 1

做题目时，发现题目给了一个hint，我们先打开看一下

from gmpy2 import *
from Crypto.Util.number import *
from secret import hint
m = bytes_to_long(hint)
p = getPrime(256)
c = pow(m, 256, p)
print(p)
p, q = getPrime(256), getPrime(256)
n = p * q
e1, e2 = getPrime(32), getPrime(32)
c1, c2 = pow(c, e1, n), pow(c, e2, n)
print(n)
print(e1, c1)
print(e2, c2)

很显然，我们如果想解密这个hint,首先来的就是一次共模攻击，解出这个hint加密后的$c$值，然后我们就是要解同余方程$x^{256}\equiv c \pmod p$。发现$p$是素数，并且$\gcd(p-1,256)=4$，说明方程一共有$4$个根。我们可以直接利用Sagemath解$\text{GF}$域上的方程，得到$4$个解如下图，然后一个 一个通过long_to_bytes转换成字符，可以得到hint：m.bit_length()<400

PART 2

得到了hint之后，我们再进入正规的解题题目中来：

from gmpy2 import *
from Crypto.Util.number import *
from secret import flag
flag = flag.strip(b"npuctf{").strip(b"}")
m = bytes_to_long(flag)
p, q = getPrime(512), getPrime(512)
n = p * q
e1, e2 = p, q
c1, c2 = pow(m, e1, n), pow(m, e2, n)
print(n)
print(c1)
print(c2)

这道题虽然也是共模攻击，但是这两个指数很特殊，恰好就是$n$的两个素因子$p,q$。也就是说，我们知道了$m^p,m^q$的值，下面就是要考虑一下构造式子的问题。

根据之前在离散对数中探讨过的一个内容：在模$M$（$M$不一定是素数）的意义下所有的$\mathrm{ord}(x)$均为$\phi(M)$的因数，所以我们可以得到：
$$
m^p\equiv m \pmod p \Rightarrow m^p\equiv ap+m\pmod n
$$
$$
m^q\equiv m \pmod q \Rightarrow m^q\equiv bq+m\pmod n
$$

下面就是要想办法构造一下两个式子，很显然我们可以把这两个式子相乘和相加，那么就有下面两个算式
$$
F=m^p+m^q\equiv ap+bq+2m \pmod m
$$
$$
G=m^pm^q=m^{p+q}\equiv m^2+m(ap+bq)+abpq \pmod n
$$

由于$n=pq$，所以$G$式的最后一项有$abpq\equiv 0 \pmod n$，所以化简$G$式，有
$$
G \equiv m^2+m(ap+bq) \pmod n
$$
$F$式子乘上$m$，得：
$$
mF\equiv m(ap+bq)+2m^2 \pmod n
$$
再进行两步推导
$$
mF-G\equiv m^2\pmod n
$$
$$
m^2-mF+G\equiv 0 \pmod n
$$

因为$F=c_1+c_2,G=c_1c_2$，所以我们构建方程$m^2-(c_1+c_2)m+c_1c_2\equiv 0 \pmod n$，由于$n$并不是素数，所以我们需要换一种求根的方式，要用上hint中给出的内容，限定一下根的大小不超过$2^{400}$，即可得解

5[AFCTF2018]Tiny LFSR

一道lfsr题目

import sys
from binascii import unhexlify
if(len(sys.argv)<4):
	print("Usage: python Encrypt.py keyfile plaintext ciphername")
	exit(1)
def lfsr(R, mask):
	output = (R << 1) & 0xffffffffffffffff
	i=(R&mask)&0xffffffffffffffff
	lastbit=0
	while i!=0:
		lastbit^=(i&1)
		i=i>>1
	output^=lastbit
	return (output,lastbit)
R = 0
key = ""
with open(sys.argv[1],"r") as f:
	key = f.read()
	R = int(key,16)
	f.close
mask = 0xd800000000000000
a = ''.join([chr(int(b, 16)) for b in [key[i:i+2] for i in range(0, len(key), 2)]])
f=open(sys.argv[2],"r")
ff = open(sys.argv[3],"wb")
s = f.read()
f.close()
lent = len(s)
for i in range(0, len(a)):
	ff.write((ord(s[i])^ord(a[i])).to_bytes(1, byteorder='big'))
for i in range(len(a), lent):
    tmp=0
    for j in range(8):
        (R,out)=lfsr(R,mask)
        tmp=(tmp << 1)^out
    ff.write((tmp^ord(s[i])).to_bytes(1, byteorder='big'))
ff.close()

题目给出了一个明文Plain及其加密后的样子，同时也给出了flag的密文，很显然是要求flag明文。

根据出题代码可以发现：mask的值是$16$位$16$进制数，所以密钥的长度也应该是$16$位$16$进制数（也就是$8$字节），并且最后最先给出的应该是明文与密钥的加密结果，所以我们可以直接先将明文与密钥异或一下，代码如下

from Crypto.Util.number import *
fp,gp=open("[2]Plain.txt","r"),open("[3]cipher.txt","rb")
pl,cp=fp.read().encode(),gp.read()
pl,cp=bytes_to_long(pl),bytes_to_long(cp)
print(hex(pl^cp))
'''
0x123456789abcdef184bb2ec4d1ee7b86e3a6e926e3a6e8d203b2e03203b2f2c6226e22e6226fad1953215e7953374e745e7cf6d45f97467bf6adc09be5779eecc4444ccd535dba9f2aaa7fe85ad0b2aa800a81ff94ff680380e39205550c78208801067007b0cb6
'''

注意到最后的$16$进制位数的长度是奇数（一开始我没发现，耽误了好长的时间），说明了应该在前面补$0$，那么密钥就应该是$0123456789\text {ABCDEF}_h$，这么好的数字，说明我们的密钥发现是对的

拿到了密钥，也就说明我们就拿到了lfsr的种子,进而就可以获得最后的flag了

from Crypto.Util.number import *
def lfsr(R, mask):
        output = (R << 1) & 0xffffffffffffffff
        i=(R&mask)&0xffffffffffffffff
        lastbit=0
        while i!=0:
                lastbit^=(i&1)
                i=i>>1
        output^=lastbit
        return (output,lastbit)
R=0x0123456789abcdef
mask=0xd800000000000000
a=b'\x01\x23\x45\x67\x89\xab\xcd\xef'
fp=open("flag_encode.txt","rb")
c=fp.read()
ans=""
for i in range(8):
        ans+=chr(a[i]^c[i])
print(ans)
for i in range(8,1213):
        tmp=0
        for j in range(8):
                (R,out)=lfsr(R,mask)
                tmp=(tmp << 1)^out
        ans+=chr(tmp^c[i])
print(ans)