To1in 的BUU刷题记录——1
1.[NCTF2019]childRSA
这道题的题面很“普通”，就是常规的RSA生成算法，给的p、q位数很大，按道理来说n很难分解，不过我们把n放到factordb.com里面分解，网站数据库里已经有了这个数的分解结果，于是就按照正常的RSA decrypt流程走一遍就完事了。
但是，如果我们去查阅一下官方的wp（Intended Solution to Crypto Problems in NCTF 2019 | Soreat_u's Blog (soreatu.com)）就会发现，出题人的思路并不是这样的。
我们仔细观察一下生成素数的算法：
def getPrime(bits):
while True:
n = 2
while n.bit_length() < bits:
n *= choice(primes)
if isPrime(n + 1):
return n + 1
#bits=2048
p、q由上面这个函数生成，其中primes是Crypto.Util.number中的sieve_base模块，在pycharm中按住ctrl点这个函数，就可以跳到其定义的地方：
# The first 10000 primes used for checking primality.
# This should be enough to eliminate most of the odd
# numbers before needing to do a Rabin-Miller test at all.
sieve_base = (
2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
......
103723, 103769, 103787, 103801, 103811, 103813, 103837, 103841, 103843, 103867,
103889, 103903, 103913, 103919, 103951, 103963, 103967, 103969, 103979, 103981,
103991, 103993, 103997, 104003, 104009, 104021, 104033, 104047, 104053, 104059,
104087, 104089, 104107, 104113, 104119, 104123, 104147, 104149, 104161, 104173,
104179, 104183, 104207, 104231, 104233, 104239, 104243, 104281, 104287, 104297,
104309, 104311, 104323, 104327, 104347, 104369, 104381, 104383, 104393, 104399,
104417, 104459, 104471, 104473, 104479, 104491, 104513, 104527, 104537, 104543,
104549, 104551, 104561, 104579, 104593, 104597, 104623, 104639, 104651, 104659,
104677, 104681, 104683, 104693, 104701, 104707, 104711, 104717, 104723, 104729,
)
我们可以看到这道题的素数生成算法其实是有些奇怪的，输出的prime是很多库中的素数相乘后+1得到的。这就使得素数p、q在-1后，可以分解成很多相对小的素数。这样的数，在数学上称作 数。
这其实就可以联想到一个大数分解算法——Pollard's p-1 method。
我们先来看它的预备知识：费马小定理
将其变形
也就是说是的倍数。
于是我们把同余式改写成等式
如果a的指数L是p-1的倍数，那么就是p的倍数。
所以我们只要找到一个指数L，使得对于一个底数a，是的倍数，但不能是的倍数，这时我们只要计算，得到的就是p，于是我们成功分解了N。
在Pollard's p-1 method这个分解算法中，由于p–1是p1, p2, ..., pk的乘积，那么pk!=1·2·…·pk一定包含p1—pk这些数，于是pk！一定是p-1的倍数。
也就是说，L>pk时，L!在很大概率上能被p-1整除（不一定的原因是，p-1中的p1—pk的幂次不一定为1）。所以对于n=2,3,4…，我们任意选择一个a（可以简单地选为2），并计算 ，如果结果在1到N中间，我们就找到了p。
这个算法有一些需要优化的地方，比如计算 时，可以先计算，于是我们自己实现一下这个算法
#2021-7-11
from Crypto.Util.number import *
def Pollard_p_1(N):
f=2
for n in range(1,80000):
f=pow(f,n,N)
for n in range(80000,104730):
f=pow(f,n,N)
if n % 20==0:
d=GCD(t-1,N)
if 1<d<N:
return d
N=32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
print(Pollard_p_1(N))
#d=178449493212694205742332078583256205058672290603652616240227340638730811945224947826121772642204629335108873832781921390308501763661154638696935732709724016546955977529088135995838497476350749621442719690722226913635772410880516639651363626821442456779009699333452616953193799328647446968707045304702547915799734431818800374360377292309248361548868909066895474518333089446581763425755389837072166970684877011663234978631869703859541876049132713490090720408351108387971577438951727337962368478059295446047962510687695047494480605473377173021467764495541590394732685140829152761532035790187269724703444386838656193674253139
大概两分钟的样子（cpu：3300x）就可以跑出来，接下来就是RSA常规流程。
下面贴一个网上的实现
# author: 随缘
# time: 2020-4-30
def pollard_p_1(n,B):
"""
Factor n = p*q (p is B-smooth)
:param n:
:param B:
:return: d = p
"""
# step 1
a = 2
# step 2
false_range = int(0.8*B)
for j in range(2,false_range):
# We assume n had a factor > 0.8B,so we can do less gcd
a = pow(a, j, n)
d = 0
for j in range(false_range,B+1):
# step 3
a = pow(a, j, n)
# step 4
d = gcd(a-1, n)
# step 5
if 1<d<n:
return d
#原文链接：https://blog.csdn.net/qq_42667481/article/details/106729900
2.[CISCN2018]oldstreamgame
题目：
flag = "flag{xxxxxxxxxxxxxxxx}"
assert flag.startswith("flag{")
assert flag.endswith("}")
assert len(flag)==14
def lfsr(R, mask):
output = (R << 1) & 0xffffffff
i = (R & mask) & 0xffffffff
lastbit = 0
while i != 0:
lastbit ^= (i & 1)
i = i >> 1
output ^= lastbit
return output, lastbit
R = int(flag[5:-1], 16)
mask = 0b10100100000010000000100010010100
f=open("key","w")
for i in range(100):
tmp=0
for j in range(8):
(R,out)=lfsr(R,mask)
tmp=(tmp << 1)^out
f.write(chr(tmp))
f.close()
题目里给我我们mask，而flag是lfsr的seed（即R），它是一个8位的16进制数，即2进制有32位。在这里不建议使用爆破初始seed的做法，而是递推逆向求出lfsr的初始seed。
def recover(R, mask):
lastbit=R&1 #获得最后的lastbit
R=R>>1 #得到outbut>>1，缺少的第0位就是要求的
i=(R&mask)&0xffffffff #得到i，由于缺少第0位，所以异或之后就能得到第0位
while i!=0:
lastbit^=(i&1)
i=i>>1
output=(lastbit<<31)|R #把恢复出来的R的原来的第0位 放到前面
return output
mask = 0b10100100000010000000100010010100
with open('key', 'rb') as f:
b = f.read()
key = 0b0
for i in range(4):
t=b[i]
key =(key<<8)+t
print(bin(key))
for i in range(32):
key = recover(key,mask)
print(hex(key))
3.[De1CTF2019]Babylfsr
又是一道lfsr的题目，task和key如下
import hashlib
from secret import KEY,FLAG,MASK
assert(FLAG=="de1ctf{"+hashlib.sha256(hex(KEY)[2:].rstrip('L')).hexdigest()+"}")
assert(FLAG[7:11]=='1224')
LENGTH = 256
assert(KEY.bit_length()==LENGTH)
assert(MASK.bit_length()==LENGTH)
def pad(m):
pad_length = 8 - len(m)
return pad_length*'0'+m
class lfsr():
def __init__(self, init, mask, length):
self.init = init
self.mask = mask
self.lengthmask = 2**(length+1)-1
def next(self):
nextdata = (self.init << 1) & self.lengthmask
i = self.init & self.mask & self.lengthmask
output = 0
while i != 0:
output ^= (i & 1)
i = i >> 1
nextdata ^= output
self.init = nextdata
return output
if __name__=="__main__":
l = lfsr(KEY,MASK,LENGTH)
r = ''
for i in range(63):
b = 0
for j in range(8):
b = (b<<1)+l.next()
r += pad(bin(b)[2:])
with open('output','w') as f:
f.write(r)
# 001010010111101000001101101111010000001111011001101111011000100001100011111000010001100101110110011000001100111010111110000000111011000110111110001110111000010100110010011111100011010111101101101001110000010111011110010110010011101101010010100101011111011001111010000000001011000011000100000101111010001100000011010011010111001010010101101000110011001110111010000011010101111011110100011110011010000001100100101000010110100100100011001000101010001100000010000100111001110110101000000101011100000001100010
发现这次只给了输出，key和mask都没有。所以我们需要根据出题人给出的504bit信息，推出mask和key共512位信息。
由于lfsr的性质，在进行256次操作后，原有的key被全部替换，而被替换后的key是我们已知的，即给出的前256位。于是我们可以据此推出mask。不过我们只有后面的504-256=248位，从方程的角度考虑，我们少8组方程，不过少的8组我们可以通过爆破次输出补上。求解出的答案，我们通过题目中给出的sha256进行校验，从而找到正确的mask。
于是问题就可以看成，在上，256位的向量R点乘mask向量，得到的数已知。所以我们可以把lfsr的状态一行行写在矩阵上，把 lsfr 每次所生成的结果也拼成一个向量，记为 ，那么掩码向量 使得：
对取逆，在两边同时乘上，就可以得到mask向量，即。
接下来求key的步骤和上面那题lfsr一样。只需要在最后进行key的校验就好了。
import itertools, hashlib, numpy as np
def int2bin(a, n):
assert 0<=n and a < 2**n
res = np.zeros(n, dtype = int)
for x in range(n):
res[n-x-1] = a % 2
a = a // 2
return res.tolist()
def bin2int(a):
return reduce(lambda x,y: x*2+y, a)
def bitAnd(a, b):
assert len(a) == len(b)
return list(map(lambda x,y: int(x)&int(y), a, b))
def test(padding):
s = [int(x) for x in '001010010111101000001101101111010000001111011001101111011000100001100011111000010001100101110110011000001100111010111110000000111011000110111110001110111000010100110010011111100011010111101101101001110000010111011110010110010011101101010010100101011111011001111010000000001011000011000100000101111010001100000011010011010111001010010101101000110011001110111010000011010101111011110100011110011010000001100100101000010110100100100011001000101010001100000010000100111001110110101000000101011100000001100010'] + padding
M = matrix(GF(2), 256, 256)
T = vector(GF(2), 256)
for i in range(len(s) - 256):
M[i] = s[i : i + 256]
T[i] = s[i+256]
try:
mask = M.inverse() * T
except:
return
suf = []
for i in range(256):
if bitAnd([0] + suf + s[0:255 - i], mask).count(1) % 2 == s[255 - i]:
suf = [0] + suf
else:
suf = [1] + suf
key = hex(bin2int(suf))[2:]
sha = hashlib.sha256(key.encode()).hexdigest()
if sha[:4] == '1224':
print('de1ctf{' + sha + '}')
for x in itertools.product([0, 1], repeat = 8):
test(list(x))
#https://www.ruanx.net/babylfsr/
Comments NOTHING