文章总结： 本文详细记录了PotensicAtom2无人机固件逆向工程中BCH纠错码的完整分析过程。作者通过拆解SPINAND芯片并用ESP32读取镜像，暴力枚举出BCH参数（prim_poly=17475，t=16），成功纠正24.7万个位错误并解出UBIFS。文章提供了可直接复用的Python还原脚本和ECC爆破脚本，展示了从硬件提取到软件破解的完整技术路径，对IoT安全研究具有较高参考价值。 综合评分： 85 文章分类： IoT安全,逆向分析,二进制安全
BCH 纠错逆向全脚本：Potensic Atom 2 无人机固件还原与本原多项式推导（下）
原创
黑卷 黑卷
黑卷的IoT攻防日记
2026年10月4日 07:03 上海
在小说阅读器读本章
去阅读
在公众号小说中沉浸阅读
BCH 纠错逆向全脚本：Potensic Atom 2 无人机固件还原与本原多项式推导（下）
上篇里，Neodyme 在一台没有 UART/JTAG、固件包又加密的 Potensic Atom 2 无人机上热风枪拆下 SPI NAND，用 ESP32 读出 544 MiB 镜像，靠多数表决和熵分析摸清 OOB/ECC 布局。随后暴力枚举 14 次本原多项式和取反/位序变换，22 秒爆出 BCH 参数（prim_poly = 17475，t = 16），纠正 24.7 万个位错误并解出 UBIFS。下篇是作者附录：三份可直接复用的完整脚本，以及 BCH 背后的多项式代数推导。
附录
最终还原脚本
import os.path
import sys
import bchlib
ECC_POLYNOMIAL = 17475
CORRECTION_CAPACITY = 16
USER_DATA_SIZE = 4096
PAGE_SIZE = USER_DATA_SIZE + 256
SLICE_DATA_0 = slice(0, 1028)
SLICE_ECC_0 = slice(1028, 1056)
SLICE_DATA_1 = slice(1056, 2084)
SLICE_ECC_1 = slice(2084, 2112)
SLICE_DATA_2 = slice(2112, 3140)
SLICE_ECC_2 = slice(3140, 3168)
SLICE_DATA_3 = slice(3168, 4096)
SLICE_BB = slice(4096, 4098)
SLICE_DATA_4 = slice(4098, 4182)
SLICE_ECC_3 = slice(4182, 4210)
SLICE_CTRL = slice(4210, 4224)
def parse_flash_page(flash_page: bytes) -> list[tuple[bytearray, bytearray]]:
"""
Transforms a flash-layout page into a userdata-layout page according to SoC datasheet,
chunked according to ECC coverage.
Flash layout:
data + ecc + data + ecc + data + ecc + data + bb + data + ecc + ctrl
Userdata layout:
data + bb + ctrl
ECC coverage:
data0 <- ECC0
data1 <- ECC1
data2 <- ECC2
data3+data4+bb+ctrl <- ECC3
:param flash_page: The 4224 or 4352 byte flash-layout page
"""
chunks = []
# three simple chunks of full-sized data + ecc
chunks.append((flash_page[SLICE_DATA_0], flash_page[SLICE_ECC_0]))
chunks.append((flash_page[SLICE_DATA_1], flash_page[SLICE_ECC_1]))
chunks.append((flash_page[SLICE_DATA_2], flash_page[SLICE_ECC_2]))
# last chunk is fragmented a bit
userdata_chunk = bytearray()
userdata_chunk.extend(flash_page[SLICE_DATA_3])
userdata_chunk.extend(flash_page[SLICE_DATA_4])
userdata_chunk.extend(flash_page[SLICE_BB])
userdata_chunk.extend(flash_page[SLICE_CTRL])
chunks.append((userdata_chunk, flash_page[SLICE_ECC_3]))
return chunks
def invert(b: bytearray) -> bytearray:
return bytearray(x ^ 0xFF for x in b)
def fix_chunk_inplace(data: bytearray, ecc: bytearray) -> tuple[int, bytearray]:
data_transformed = invert(data)
ecc_transformed = invert(ecc)
bch = bchlib.BCH(t=CORRECTION_CAPACITY, prim_poly=ECC_POLYNOMIAL, swap_bits=True)
err_count = bch.decode(data_transformed, ecc_transformed)
bch.correct(data_transformed, ecc_transformed)
return err_count, invert(data_transformed)
def main():
if len(sys.argv) != 2:
print(
f"Usage: {sys.argv[0]} full_flash_dump.bin "
f"(with {PAGE_SIZE} byte pages)",
file=sys.stderr,
)
sys.exit(1)
total_page_count = os.path.getsize(sys.argv[1]) // PAGE_SIZE
f_in = open(sys.argv[1], "rb")
f_out = open("firmware-corrected.bin", "wb")
page_index = 0
total_errors = 0
pages_with_errors = 0
highest_chunk_error_count = 0
while (page := f_in.read(PAGE_SIZE)) != b"":
page_index += 1
chunks = parse_flash_page(page)
errors_in_page = 0
page_corrected = bytearray()
for i, (data, ecc) in enumerate(chunks):
err_count, data = fix_chunk_inplace(data, ecc)
page_corrected.extend(data)
errors_in_page += err_count
highest_chunk_error_count = max(highest_chunk_error_count, err_count)
# cut off BB and CTRL
f_out.write(page_corrected[:USER_DATA_SIZE])
print(
f"[{page_index/total_page_count*100: 4.0f} % ] Extracted page {page_index: 8d} / {total_page_count: 8d} "
+ (
f"(errors in page: {errors_in_page})"
if errors_in_page > 0
else f"(no errors)"
)
)
total_errors += errors_in_page
if errors_in_page > 0:
pages_with_errors += 1
print()
print(f"======== DONE EXTRACTING")
print(f"- Total pages: {total_page_count}")
print(
f"- Pages with errors: {pages_with_errors} ({pages_with_errors/total_page_count*100:.02f} %)"
)
print(
f"- Total bit errors: {total_errors} ({total_errors / (total_page_count*PAGE_SIZE*8)*100:.04f} %)"
)
print(f"- ECC polynomial: {ECC_POLYNOMIAL}")
print(f"- Correction capacity per chunk: {CORRECTION_CAPACITY}")
print(
f"- Highest error count in a single chunk: {highest_chunk_error_count} "
f"({highest_chunk_error_count/CORRECTION_CAPACITY*100:.02f} %)"
)
if __name__ == "__main__":
main()
ECC 爆破脚本
import datetime
import itertools
import sys
import bchlib
PAGE_SIZE = 4096 + 256
SLICE_DATA_0 = slice(0, 1028)
SLICE_ECC_0 = slice(1028, 1056)
def reverse_bit_order(b: bytes) -> bytes:
# credit to this hack at
# https://graphics.stanford.edu/~seander/bithacks.html#ReverseByteWith64BitsDiv
return bytes((x * 0x0202020202 & 0x010884422010) % 1023 for x in b)
def reverse_byte_order(b: bytes) -> bytes:
return b[::-1]
def swap_nibbles(b: bytes) -> bytes:
return bytes((x >> 4 | x << 4) & 0xFF for x in b)
def invert(b: bytes) -> bytes:
return bytes(x ^ 0xFF for x in b)
TRANSFORMATIONS = [reverse_bit_order, reverse_byte_order, swap_nibbles, invert]
def all_transformation_sequences():
"""
:return: Iterator over all possible subsets and
orderings of transformations
(without duplicate transformations).
"""
for transformation_count in range(0, len(TRANSFORMATIONS)):
for subset in itertools.combinations(TRANSFORMATIONS, transformation_count):
for permutation in itertools.permutations(subset):
yield permutation
def main():
if len(sys.argv) != 2:
print(
f"Usage: {sys.argv[0]} full_flash_dump.bin "
f"(with {PAGE_SIZE} byte pages)",
file=sys.stderr,
)
sys.exit(1)
f = open(sys.argv[1], "rb")
# Both of these work about equally fast
# primitive_polynomials = list(primitive_binary_polynomials(14))
primitive_polynomials = list(range(2**14 + 1, 2**15, 2))
# try all pages
t0 = datetime.datetime.now()
page_index = 0
while (page := f.read(PAGE_SIZE)) != b"":
print(f"Trying page {page_index}, userdata segment 0")
page_index += 1
user_data = page[SLICE_DATA_0]
known_ecc = page[SLICE_ECC_0]
# try all primitive polynomials of the correct degree
for prim_poly in primitive_polynomials:
try:
bch = bchlib.BCH(t=16, prim_poly=prim_poly)
except RuntimeError:
continue
# try all combinations of pre-transformations
for pre_transform_seq in all_transformation_sequences():
user_data_transformed = user_data
for pre_transform in pre_transform_seq:
user_data_transformed = pre_transform(user_data_transformed)
ecc = bch.encode(user_data_transformed)
# try all combinations of post-transformations
for post_transform_seq in all_transformation_sequences():
ecc_transformed = ecc
for post_transform in post_transform_seq:
ecc_transformed = post_transform(ecc_transformed)
if ecc_transformed == known_ecc:
print(f"========== ECC parameters found!")
print(f"- prim_poly = {prim_poly}")
print(f"- pre_transform_seq = {pre_transform_seq}")
print(f"- post_transform_seq = {post_transform_seq}")
t1 = datetime.datetime.now()
print(f"- time to brute force: {t1 - t0}")
return
if __name__ == "__main__":
main()
本原二元多项式生成器
def prime_factorization(n):
fac = []
p = 2
while p * p <= n:
if n % p == 0:
fac.append(p)
while n % p == 0:
n //= p
p += 1
if n > 1:
fac.append(n)
return fac
def poly_mod(a, mod):
d_a = a.bit_length() - 1
d_m = mod.bit_length() - 1
while a and d_a >= d_m:
a ^= mod << (d_a - d_m)
d_a = a.bit_length() - 1
return a
def poly_mul(a, b):
result = 0
while b:
if b & 1:
result ^= a
b >>= 1
a <<= 1
return result
def poly_gcd(a, b):
while b:
a, b = b, poly_mod(a, b)
return a
def poly_pow_mod(x, e, mod):
res = 1
while e:
if e & 1:
res = poly_mod(poly_mul(res, x), mod)
x = poly_mod(poly_mul(x, x), mod)
e >>= 1
return res
def is_reducible(fx):
degree = fx.bit_length() - 1
x = 2
y = x
for _ in range(degree // 2 + 1):
y = poly_mod(poly_mul(y, y), fx)
y_minus_x = y ^ x
if poly_gcd(y_minus_x, fx) != 1:
return False
for _ in range(degree // 2 + 1, degree):
y = poly_mod(poly_mul(y, y), fx)
return y == x
def primitive_binary_polynomials(degree):
n = 2**degree - 1
prime_factors = set(prime_factorization(n))
x = 2
for fx in range(2**degree + 1, 2 ** (degree + 1), 2):
# check irreducible
if not is_reducible(fx):
continue
# check primitive
for q in prime_factors:
if poly_pow_mod(x, n // q, fx) == 1:
break
else:
yield fx
if __name__ == "__main__":
m = 14
print(f"All primitive polynomials of degree {m}:")
i = 0
for px in primitive_binary_polynomials(m):
i += 1
print(f"{px} = {bin(px)}")
print(f"Total primitive polynomials of degree {m}: {i}")
翻车花絮
忘了订电池，只好拿实验室电源供电……
多项式代数小绕路
如果你和我一样不太熟悉多项式代数，比较好的方式是先聊整数世界里的相关概念，再过渡到多项式世界里的对应物，这样更容易建立直觉。
这里假设你大致了解模运算和素数。
整数与模环
先在整数集 {…, −2, −1, 0, 1, 2, …} 上工作，数学上记作 ℤ。
引入一个模数后，就得到 ℤ/nℤ。记号解释：
- n 是某个模数，此时不一定是素数，就是一个整数——ℤ 的一个元素。
- nℤ 是 n 的所有倍数，即 {…, −2n, −n, 0, n, 2n, …}。如果 n = 7，就是 {…, −14, −7, 0, 7, 14, …}。
ℤ/nℤ 的意思是：在 ℤ 上，凡是相差 n 的倍数的元素都视为等价——也就是它们的差落在 nℤ 里。如果 n = 7，那么 2 和 16 等价，因为差是 14，是 7 的倍数，属于 7ℤ。
这其实就是“mod 7”：16 ≡ 2 (mod 7)。
所以 ℤ/nℤ 就是“ℤ mod n”的全部。
注意，这把无穷多的整数 ℤ 压缩成了有限个等价类。在 ℤ/7ℤ 里，所有数要么属于 {0, 1, 2, 3, 4, 5, 6}，要么与其中某个等价。所以实际上 ℤ/7ℤ 只有 7 种取值。
那素数是用来干嘛的？ℤ/nℤ 有个实际问题：有时两个非零元素相乘会得到 0。以 ℤ/8ℤ 为例：
4 * 2 = 0 mod 8
8 * 2 = 0 mod 8
12 * 2 = 0 mod 8
如果要在模环里做大量乘法，这就很糟糕。一旦不小心碰到 8 的倍数，就会得到 0，之后再乘什么都还是 0。于是很多不同的值，乘上某些数后都会塌缩成同一个 0。
在全体整数 ℤ 里没有这个问题：只要不乘 0 本身，乘积永远不会是 0。好在有个解决办法：用素数模数。
素数、有限域与循环
素数 p 有个好性质：它诱导的模环 ℤ/pℤ 是域而不只是环，加法和乘法和在 ℤ 里一样好用。在 ℤ/pℤ 中，乘一个非 0 的数永远不会得到 p 的倍数——因为 p 是素数，无法由其他数相乘得到。（乘 p 本身不算，因为 p ≡ 0 (mod p)。）
因为 ℤ/pℤ 是域，且元素有限 {0, 1, 2, …, p−1}，所以叫“有限域”或“伽罗瓦域”，有时记作 GF(p)。严格来说，GF(p) 是个泛化概念，指“任何有 p 个元素的有限域”，ℤ/pℤ 恰好是其中之一，也是最常用的那个。
再往前一步，看一个叫原根（primitive root）的概念。解释它之前，先看一个用例。
假设你想要 {0, 1, 2, 3, 4, 5, 6} 的一个伪随机排列：不要 0, 1, 2, 3, 4, 5, 6 这种顺序，而是一个看起来更随机、但仍然覆盖所有数的序列。不需要密码学级别的随机或不可预测，只要看起来有点乱就行——比如把内存写入打散，做更好的磨损均衡。原根就能很优雅地实现这一点。
在 ℤ/pℤ 中，除非乘 0，否则乘法永远不会得到 0。也就是说，你可以不停地把一个数翻倍，永远不会意外碰到 0：
1 = 1 mod 7
1 * 2 = 2 mod 7
1 * 2^2 = 4 mod 7
1 * 2^3 = 1 mod 7
1 * 2^4 = 2 mod 7
1 * 2^5 = 4 mod 7
1 * 2^6 = 1 mod 7
...
看，出现了一个循环！在有限域里总会这样：一直乘同一个数，最终会回到起点，之后就进入循环。
不过 2 mod 7 不太好用，它诱导的循环只会经过 {1, 2, 4}，永远碰不到 {3, 5, 6}。注意任何循环都不会经过 0，所以模 7 时能得到的最大循环长度是 6。
原根与素因子
确实有能生成完整循环的数！
# 3
1 * 3^0 = 1 mod 7
1 * 3^1 = 3 mod 7
1 * 3^2 = 2 mod 7
1 * 3^3 = 6 mod 7
1 * 3^4 = 4 mod 7
1 * 3^5 = 5 mod 7
1 * 3^6 = 1 mod 7
1 * 3^7 = 3 mod 7
...
# 5
1 * 5^0 = 1 mod 7
1 * 5^1 = 5 mod 7
1 * 5^2 = 4 mod 7
1 * 5^3 = 6 mod 7
1 * 5^4 = 2 mod 7
1 * 5^5 = 3 mod 7
1 * 5^6 = 1 mod 7
1 * 5^7 = 5 mod 7
...
这类能在有限域里诱导出完整循环的数，叫作原根。3 和 5 都是模 7 的原根。它们诱导的循环长度都是 6，所以 3 和 5 的阶（order）是 6。
更一般地，模素数 p 的原根 g，是阶为 p−1 的数，也就是它诱导的循环长度为 p−1，此时 g^(p−1) ≡ 1 (mod p)。更形式化地说：g 是模 p 的原根，当且仅当使 g^k ≡ 1 (mod p) 成立的最小正整数 k 等于 p−1。
那么怎样检查一个数 g 是不是模 p 的原根最好？显而易见的办法是让 k 从 1 数到 p−2，每次检查 g^k ≡ 1 (mod p)。这能用，但数字大了会很慢。其实不需要把 1 到 p−2 的每个 k 都查一遍。为了理解这一点，回头看前面的 g = 2：
1 = 1 mod 7
1 * 2 = 2 mod 7
1 * 2^2 = 4 mod 7
...repeat
循环长度为 3，包含 {1, 2, 4}，看不到 {3, 5, 6}。那如果还是用 g = 2，但从 3 开始呢？
3 = 3 mod 7
3 * 2^1 = 6 mod 7
3 * 2^2 = 5 mod 7
...repeat
又是一个长度为 3 的循环！这次覆盖了剩下的 {3, 5, 6}。从 5 或 6 开始也会得到同一个 {3, 5, 6} 循环。所以 g = 2 把除 0 以外的整个有限域分成了两个子集：{1, 2, 4} 和 {3, 5, 6}。
再看一个例子：g = 6，找出所有循环。
# 从 1 开始
1 * 6^0 = 1 mod 7
1 * 6^1 = 6 mod 7
...循环
# 从 2 开始
2 * 6^0 = 2 mod 7
2 * 6^1 = 5 mod 7
...循环
# 从 3 开始
3 * 6^0 = 3 mod 7
3 * 6^1 = 4 mod 7
...循环
所以 g = 6 把非零元素划分为 {1, 6}、{2, 5}、{3, 4}。
注意到没有：同一个数诱导的所有循环长度都一样。仔细想想这完全合理：g = 6 时“从 3 开始”，本质上就是把常规的 {1, 6} 循环里每个元素都乘 3，所以得到的循环长度也必然是 2。
这不是巧合。同一个数诱导的所有循环总是等长的，而且这个数总会把去掉 0 的整个有限域划分成若干个大小相同、互不相交的集合。
这有什么用？对 p = 7 来说，循环长度 4 和 5 是不可能的！因为没法把 6 个非零元素 {1, 2, 3, 4, 5, 6} 分成大小为 4 或 5 的若干组。更一般地，循环长度（也就是阶）必须是 p−1（全部非零元素的个数）的约数。
这就是拉格朗日定理：子群的阶整除整个群的阶。
所以检查 g 是否为原根，不用把 1 到 p−2 的 k 全查一遍，只要查 p−1 的所有约数！另外 k = 1 显然不用查：只有 1 本身满足 g^1 ≡ 1 (mod p)，而 1 总是诱导长度为 1 的循环，所以当 p > 2 时它永远不是原根。
于是只剩下检查 p−1 大于 1 的约数，这已经排除了大部分候选。
但还能更进一步！
快速原根判定
其实只要查一部分约数。这就轮到素因数分解出场了。假设我们有 p−1 的素因子，记为 {q₁, q₂, …}。注意 p 本身没有（非平凡）素因子——毕竟它是素数。但 p−1 有素因子，而且 2 一定是其中之一：p > 2 的素数必为奇数，p−1 必为偶数。
如果我告诉你，只需要检查用 p−1 除以某个素因子得到的那些约数呢？具体就是：
(p-1) / q_1
(p-1) / q_2
...
例子：
p = 37
p-1 = 36
= 2 * 2 * 3 * 3
非平凡约数集合 = {2, 3, 4, 6, 9, 12, 18}
素因子集合 = {2, 3}
只需要检查
36 / 2 = 18
和
36 / 3 = 12
不需要检查其他约数
{2, 3, 4, 6, 9}
为什么？首先注意，“其他约数” {2, 3, 4, 6, 9} 本身都是 12 或 18 的约数：
12 = 2 * 6
= 3 * 4
= 4 * 3
= 6 * 2
18 = 2 * 9
= 3 * 6
= 6 * 3
= 9 * 2
而如果 g^12 ≢ 1 (mod 37)，就能推出：
g^2 != 1 mod 37
g^3 != 1 mod 37
g^4 != 1 mod 37
g^6 != 1 mod 37
以此类推。
为什么？因为假如 g^6 mod 37 等于 1，那么
g^6 = 1 mod 37
(g^6)^2 = 1^2 mod 37
g^12 = 1 mod 37
这就矛盾了！对一般的 p 也能同样证明，思路和这个例子完全一样。
好，所以只需要对 p−1 的每个素因子 q，检查 g^((p−1)/q) ≡ 1 (mod p) 是否成立。
下面这个生成器函数会返回给定素数模数 p 的所有原根：
def primitive_roots(p):
N = p - 1
prime_factors = set(prime_factorization(N))
for g in range(2, N + 1):
for q in prime_factors:
if pow(g, N // q, p) == 1:
break
else:
yield g
知道吗？有了这个，我们不仅能找原根，还能找本原多项式！只需要把这个概念平移到多项式上！
……这一步有点绕。
二元多项式、不可约性与本原元
先说正事：多项式。它们长这样：
f(x) = 14x⁴ + 2x³ + 0x² + 53x + 42
借助数学的黑魔法，我们可以把多项式当作多维的数：
Polynomial: f(x) = 14x^4 + 2x^3 + 0x^2 + 53x + 42
Coefficients: [14, 2, 0, 53, 42]
在它们上面，可以做和整数一样的运算：加、乘、减、除——因此也有取模。一个多项式除以另一个多项式听起来很怪？确实怪。细节这里就跳过了，已经跑题够远了。只要知道整数运算的直觉可以平移到多项式上就行。
记住，我们处理的是二元多项式，也就是系数只有 0 或 1 的多项式，可以用整数来表示。例如 51 表示的多项式是：
Polynomial: f(x) = 1x^5 + 1x^4 + 0x^3 + 0x^2 + 1x + 1
Binary coefficients: 1 1 0 0 1 1
Decimal representation: 51
之所以用二元多项式，是因为它们有很多 BCH 纠错码依赖的好性质。比如，所有长度为 K 的二进制串都可以表示成一个系数为二元的 K 次多项式。如果用整数，这些串就是 0 到 2^K 的整数；但这样做模运算会有麻烦，因为 2^K 不一定是素数，ℤ/2^Kℤ 就不是域。而对多项式，有很好且高效的方法在 K 次二元多项式上构造一个域。
这一节始终要记住：整数表示（上例中的 51）只是多项式在内存中的表示。多项式不是整数，不能直接拿 Python 的加号、乘号运算符做普通的整数加乘。多项式有自己的运算规则，和整数不一样。
既然是二元多项式，系数都是 0 或 1。更形式化地说，系数是 GF(2) 的元素，基本等同于 ℤ/2ℤ，也就是“mod 2”。
所有二元多项式的集合记作 GF(2)[x]。用计算机的话说，就是所有可能的位数组。
既然我们从整数切换到了二元多项式，GF(2)[x] 就是 ℤ 在二元多项式世界里的对应物：ℤ 是全体整数，GF(2)[x] 是全体二元多项式。
之前用 n 表示 ℤ 里的一个整数，现在用 f(x) 表示 GF(2)[x] 里的一个多项式。
类似 nℤ 是 n 的所有倍数，(f(x)) 是 f(x) 的所有倍数——注意是双括号。
类似 ℤ/nℤ 是“把相差 n 的倍数的两个整数视为等价”的 ℤ，GF(2)[x]/(f(x)) 就是“把相差 f(x) 的倍数的两个多项式视为等价”的 GF(2)[x]。本质上就是多项式世界里的“mod f(x)”。
一个整数 p 如果不能被其他整数整除，p 就是素数。类似地，一个多项式 p(x) 如果不能被其他多项式约简，p(x) 就是不可约的。
如果 p 是素数，ℤ/pℤ 里至少有一个原根 g，使得 {g⁰, g¹, g², g³, …} 覆盖整个 ℤ/pℤ。如果 p(x) 不可约，GF(2)[x]/(p(x)) 里至少有一个本原元 g(x)，使得 {g⁰, g¹, g², g³, …} 覆盖整个 GF(2)[x]/(p(x))。
（旁注：“原根”是只用于 ℤ/pℤ 的旧称，“本原元”是通用说法，两者是一回事。）
另外，ℤ/pℤ 的（乘法群）阶就是 p−1，而 GF(2)[x]/(p(x)) 的阶是 2^deg(p(x)) − 1，也就是所有 deg(p(x)) 位位数组（去掉全零）的数量。
快到了！我们已经能看出：不可约多项式 p(x) 对应的就是素数 p。
那么，本原多项式又是什么？
本原多项式
很简单！本原多项式就是满足一个额外条件的不可约多项式：
最简单的那个多项式 x mod p(x) 必须是本原元，也就是 {x⁰, x¹, x², x³, …} 必须覆盖整个 GF(2)[x]/(p(x))。
这有什么用？这意味着 GF(2)[x]/(p(x)) 里每个非零多项式都可以表示成 x^t，t 是某个整数。于是每个非零多项式都能用一个整数表示，而且我们得到了所有非零二元多项式的一个看起来随机的排列。
这就是 BCH 码要用的东西，也是为什么它需要本原多项式。
那怎么算出所有本原多项式？算不完，有无穷多个。但可以算出某个特定次数 m 的所有本原多项式！怎么算？用前面为整数找原根的那套方法：
- 遍历所有 m 次多项式，对每个候选 p(x)：（第 1 步）
- 检查 p(x) 是否不可约，不是就丢掉。（第 2 步）
- 检查 x（整数表示为 2 的那个最简单多项式）在 p(x) 诱导的有限域中是否为本原元：期望的循环长度 N 是所有 m 次多项式（非零）的数量 N = 2^m − 1；求出 N 的所有素因子 q；对每个素因子 q 检查 x^(N/q) ≡ 1 (mod p(x)) 是否都不成立。（第 3 步）
第 1 步：我们要的是 m 次本原多项式，所以只考虑第 m 位系数为 1、更高位系数都为 0 的多项式，它们的整数表示落在 range(2^m, 2^(m+1))。
再提速一倍：常数项（最低位系数）为 0 的多项式都不可能。例如：
x⁵ + x³ + x（注意末尾没有 +1）
因为常数项为 0 的多项式都能被多项式 x 整除，所以不是不可约的，自然也不是本原的。因此只遍历常数项为 1 的多项式，整数表示就是奇数：
range(2^m + 1, 2^(m+1), 2)（译注：作者此处写作 2^(m-1)，应为笔误）
第 2 步：检查多项式是否不可约，对应的是检查整数是否为素数。
第 1 步排除了偶数表示，跳过了一半候选，因为它们全是可约的。可惜剩下的里面依然有大量可约多项式——就像奇数里也有很多合数一样。
完整的不可约性测试用的是 Rabin 测试，它的实现结构和整数的 Miller-Rabin 素性测试类似。两者这里都不展开，这一节已经够长了。（译注：函数名叫 is_reducible，但返回 True 表示“不可约”，沿用作者的命名。）
def is_reducible(fx):
# check irreducible with rabin's irreducibility test
# for all k <= n//2, check that
# x^(2^k) - x does not divide fx
degree = fx.bit_length() - 1
x = 2
y = x
for _ in range(degree // 2 + 1):
# y = y^2 mod fx
y = poly_mod(poly_mul(y, y), fx)
y_minus_x = y ^ x
if poly_gcd(y_minus_x, fx) != 1:
return False
# check that fx divides
# x^(2^n) - x
for _ in range(degree // 2 + 1, degree):
y = poly_mod(poly_mul(y, y), fx)
return y == x
第 3 步：和整数世界找原根的做法一样，只是换成支持多项式的 pow 函数：
def primitive_binary_polynomials(degree):
n = 2**degree - 1
prime_factors = set(prime_factorization(n))
x = 2
for fx in range(2**degree + 1, 2 ** (degree + 1), 2):
# check irreducible
if not is_reducible(fx):
continue
# check primitive
for q in prime_factors:
if poly_pow_mod(x, n // q, fx) == 1:
break
else:
yield fx
求出所有本原多项式
现在终于可以算出所有 14 次本原多项式了。完整脚本见上面的附录。在我的笔记本上单线程大约 1 秒，就能列出全部 756 个 14 次本原多项式。没错——只有 756 个！
All primitive polynomials of degree 14:
16427 = 0b100000000101011
16441 = 0b100000000111001
16467 = 0b100000001010011
16479 = 0b100000001011111
16507 = 0b100000001111011
16553 = 0b100000010101001
...
32653 = 0b111111110001101
32671 = 0b111111110011111
32709 = 0b111111111000101
32721 = 0b111111111010001
32743 = 0b111111111100111
Total primitive polynomials of degree 14: 756
那这比朴素的 range(2**14 + 1, 2**15, 2)（列出一半的 14 次二元多项式）快多少？
在我的笔记本上单线程跑……大约 1 秒。
结果就是：把一堆大多不是本原的多项式直接扔给 bchlib、再接住异常，和规规矩矩算本原多项式一样快……
哦对了，你知道吗？其实也可以直接从网上拉一份 14 次本原多项式的列表。毕竟我们又不是第一个生成这份列表的人。
不过嘿，至少学了点数学。
往期推荐
- 从调试口抽到改固件：Sonoff ZigBee 网关的芯片到云端两条 CVE
- EOL 路由照样打穿：Netgear WGR614v9 UART + Bitdefender Box SPI 降级 RCE
- 拍桌子才出 root：FiberGateway GR241AG 从 UART 故障注入打到 MEO 公网 WiFi RCE
- 拆机焊 UART 还不够：Nokia Beacon 1 从受限串口到 CGI 注入 + Qiling 算口令
- 从 UART 焊到未认证后门：ANJIA PTZ 摄像头（CVE-2026-31077）
免责声明：
本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。
任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。
本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。
本文转载自：黑卷的IoT攻防日记 黑卷 黑卷《BCH 纠错逆向全脚本：Potensic Atom 2 无人机固件还原与本原多项式推导（下）》
版权声明
本站仅做备份收录，仅供研究与教学参考之用。
读者将信息用于其他用途的，全部法律及连带责任由读者自行承担，本站不承担任何责任。
评论