简介一份基于Python实现的Shamir(t,n)密钥共享方案源码面向信息安全专业学生、密码学爱好者及需要安全分发密钥的开发者。Shamir秘密共享方案由Adi Shamir于1979年提出核心思想是把秘密拆成n个份额任意t份即可完整恢复而少于t份无法得到任何有效信息因而特别适用于分布式密钥托管、多人协同签名、灾备恢复等场景。压缩包内仅含1个.py文件大小仅1KB代码轻量易读实现覆盖从选择大素数、秘密映射、随机多项式构造到份额分配、Lagrange插值恢复秘密的完整流程并附有基础测试用例通过查看代码可以直观理解有限域运算、多项式插值等密码学基础。目前已有825人学习下载。读者可直接调整阈值t和份额数n将份额生成与恢复函数嵌入自己的密钥管理、多签名钱包或安全备份系统教学与工程实践价值兼备。1. 密钥共享不是复制粘贴Shamir(t,n) 方案用 python 程序实现后到底解决了什么Shamir(t,n) 密钥共享方案最反直觉的一点秘密拆成 n 份后丢掉 n-t 份也不怕只要凑齐任意 t 份就能完整恢复而手里只有 t-1 份时你能获得的信息和一个完全没参与的旁观者一样多。这套数学性质让它在密钥托管、多用户联合授权、冷备份场景里非常实用。很多人第一反应是“把密钥复制 n 份发下去”那既放大了泄露面又做不到“缺两个人也能开、任何一个人单独却开不了”。用 python 程序实现 Shamir 方案核心就一个份额生成函数加一个恢复函数不依赖任何第三方加密库跑通第一版的时间远比想象中短。下文我会按“原理、可运行代码、参数与文件落地、踩坑”的顺序推进。新手先按 python 安装教程装好 3.10在 vscode 里配好 python 环境再往下读直接想看代码的老手可以跳到第 3 章但第 5 章的坑位建议别跳。2. 插值恢复与有限域先把 t、n、prime 三个参数选明白再写代码2.1 拉格朗日插值如何找回被拆掉的秘密Shamir 方案用到的核心数学工具是多项式插值而且是有名字的那个拉格朗日插值。基本原理一句话——平面上 t 个点能唯一确定一条 t-1 次多项式曲线。选择秘密 s随机生成 t-1 个系数 a1, a2, ..., a(t-1)构成多项式 P(x) s a1x a2x² ... a(t-1)*x^(t-1)然后取 n 个不同的 x 代入得到 n 个点 (x_i, y_i)每个点就是一份份额。恢复时只要拿到任意 t 个点就能把这条曲线完全确定下来秘密 s 就等于 P(0)。为什么 t 个点就够因为 t-1 次多项式有 t 个未知系数t 个方程恰好能解出全部系数。至于“唯一”这件事可以用反证法如果有两条不同的 t-1 次多项式都经过同样的 t 个点它们相减得到一条次数不超过 t-1 的多项式却拥有 t 个不同的根一个非零多项式不可能做到所以差值多项式只能恒等于零。这个证明虽然简略但值得在写代码前过一遍它能帮你理解为什么份额数量少于 t 时数学上绝对无法恢复。拉格朗日插值的具体形式不用背但要理解它的计算结构对每一份 (x_i, y_i)算一个权重 L_i(0)权重等于“把所有其他 x_j 都当成零点、再把 x_i 排除在分母之外”的乘积。秘密就是 Σ y_i * L_i(0)。写成代码之前先记住一件事这套公式里的除法在实数域上没问题但在计算机里直接做几乎一定会翻车原因看下一节。2.2 为什么必须工作在素有限域而不是实数上如果直接用浮点数做拉格朗日插值典型结果是恢复出 42.0000000001 这种值demo 看着能跑一旦秘密是大整数、t 接近 n浮点误差会直接抹掉低位数字。更麻烦的是实数域上的除法没办法在整数世界里精确表达而你手上的秘密往往就是一个大整数不是浮点数。职业做法是把所有运算放进一个有限域选一个大素数 p所有加、减、乘、除都在模 p 下进行。“除”被定义成“乘上模逆元”而 p 是素数保证了 1 到 p-1 的每个整数在模 p 下都有逆元。模逆元的计算不复杂。python 3.8 之后可以直接写 pow(a, -1, p) 拿到 a 在模 p 下的逆元内部用的是扩展欧几里得算法性能足够。要注意的是在 python 3.8 之前的版本里这个写法不可用需要自己实现扩展欧几里得或者升级解释器。整个方案的安全性也依赖这个有限域所谓“t-1 份没有任何信息”严格说法是在 Z/pZ 上任意猜测一个秘密 s都能构造出唯一一条经过 s 和你手里 t-1 个点的 t-1 次多项式所以所有猜测等可能。这就是为什么 Shamir 方案被称作“完美的秘密共享”——它不是难破解而是信息论意义上无懈可击。前提就是你老老实实工作在素数有限域里。2.3 参数选型秘密长度、容错人数与丢失容忍度的取舍参数选型我一般分两件事选 (t, n)再选 p 的位长。(t, n) 决定的是权力结构和容错能力。t 越小凑齐人的门槛越低但单份份额被泄露后能造成的危害也越大t 越大越安全但一旦关键人员缺席可能凑不齐人。我常用的一组对照使用场景tn取舍说明双人复核、小型团队23任意两人可恢复丢失一份也不影响经典密钥托管35容忍两人失联防止任何一人单独动用跨地域、多人参与47容忍三人缺席降低少数人勾结的风险p 的位长决定能放多大的秘密也决定了安全冗余。秘密转换成整数后必须小于 p否则恢复出来的是 secret mod p这个错非常隐蔽。建议 p 的位长至少比秘密位长大 64 到 128 位留出冗余。常用组合秘密类型秘密位长prime 建议位长说明启动口令、轻量配置64~128192够用且速度快AES-128 密钥128256最常备份的密钥类型AES-256 密钥256384~512具体生成方法见第 4 章很多教学代码爱用梅森素数 2^127-1因为它形式漂亮、模运算快但要注意它只能容纳 16 字节的秘密直接拿去做 AES-256 密钥托管是不行的。选 p 的原则就一条宁大勿小。python 大整数加解密在几百位的量级上开销可以忽略没必要为了省那点计算时间压缩安全冗余。3. 份额生成与恢复两段核心 python 代码直接跑通3.1 生成份额随机多项式与霍纳规则求值先写份额生成函数。这里所有运算都模 prime系数用随机数生成但要注意系数不能取 0原因在第 5 章展开。x 从 1 开始取避开 x0因为 P(0) 就是秘密本身x0 的份额等于把秘密直接交出去。import random from typing import List, Tuple def generate_shares(secret: int, t: int, n: int, prime: int) - List[Tuple[int, int]]: if t n: raise ValueError(门限 t 不能大于总份额数 n) if t 2: raise ValueError(t 至少为 2否则方案没有意义) if not (0 secret prime): raise ValueError(秘密必须落在 [0, prime) 区间内) # 随机多项式系数a1 到 a(t-1)全部非零 coeffs [secret] [random.randrange(1, prime) for _ in range(t - 1)] shares [] for x in range(1, n 1): # 霍纳规则求 P(x) c0 c1*x c2*x^2 ... y 0 for c in reversed(coeffs): y (y * x c) % prime shares.append((x, y)) return shares生成份额的关键是这行coeffs [secret] [...]。列表第一项是秘密本身作为多项式的常数项后面随机生成 t-1 个系数决定了曲线形状。霍纳规则那段循环写成reversed(coeffs)是从最高次系数一路向常数项合并比直接算幂次更快也避免了大整数乘方的开销。验证多项式是否正确的办法很简单P(0) 应该等于第一个系数也就是 secret。random.randrange(1, prime) 下限是 1 而非 0这个小细节会在第 5 章重点说它直接关系到多项式真实次数是否降级。x 从 1 到 n 连续取值保证份额编号不重复如果有人手工改份额编号会造成恢复时插值点冲突后面第 5 章会讲排查方法。3.2 恢复秘密在 x0 处做拉格朗日插值恢复函数的输入可以多于 t 份代码只取前 t 份参与计算。拉格朗日权重里分子是“0 - xj”对应求 P(0)分母是“xi - xj”保证权重在自己这份点上值为 1、在别人那份点上为 0。除法用 pow(den, -1, prime) 实现模逆。def reconstruct_secret(shares: List[Tuple[int, int]], prime: int) - int: if len(shares) 2: raise ValueError(至少需要两份份额才能恢复) secret 0 for i, (xi, yi) in enumerate(shares): num 1 den 1 for j, (xj, _) in enumerate(shares): if i j: continue num (num * (0 - xj)) % prime den (den * (xi - xj)) % prime # 拉格朗日基函数在 x0 处的取值 L_i(0) weight num * pow(den, -1, prime) % prime secret (secret yi * weight) % prime return secret这段循环没有显式写出拉格朗日插值公式但逻辑完全对应num 累积所有“其他 xj”的乘积den 累积“当前 xi 减去其他 xj”的乘积二者相除就是权重。如果你之前见过教科书公式对照这段代码就能看出为什么叫“基函数法”而不是“解方程组法”。恢复时份额顺序无所谓enumerate 自带索引天然支持打乱输入。注意恢复函数没有校验“传入的份额是否真的属于同一多项式”这是 Shamir 方案本身不提供的完整性保证也是很多实现翻车的根源。第 5 章会给一个带校验的改进写法。3.3 最小可运行主流程n5, t3 一把跑完把两个函数拼起来跑一个最小闭环。这种三段式结构也是我平时给团队做最小演示的模板先定参数再生成份额最后随机抽 3 份验证恢复结果。if __name__ __main__: PRIME 2**127 - 1 # 梅森素数仅供演示 secret 20240601 t, n 3, 5 shares generate_shares(secret, t, n, PRIME) print(生成的 5 份份额) for x, y in shares: print(f 份额 {x}: {y}) # 随机抽出任意 3 份验证恢复结果 picked shares[:3] restored reconstruct_secret(picked, PRIME) print(f恢复出的秘密{restored}) assert restored secret, 恢复失败请检查参数 print(验证通过3/5 份额成功恢复原始秘密)这段代码在 python 3.8 上直接跑不需要任何第三方库。如果输出和 secret 不一致先检查是不是把 pow 的-1参数写成了普通除法这是最常见的翻车点。主流程里的 t、n、PRIME 都是变量方便你测试不同组合试着把 picked 改成两份输出会是一个看上去完全正常的随机整数而且每次运行结果都不同——这正是完美秘密共享的特性不是 bug。4. 从 demo 到能用的细节份额落盘、真实密钥换算与分发习惯4.1 份额文件格式与落盘权限份额在内存里是 (x, y) 元组落盘时至少要保存 x 编号和 y 值同时建议把 prime 一起存下来否则恢复的人无法确定 p。我用一种极简的自定义文本格式每份一行管道符分隔。这么做的好处是肉眼可读、易于跨机器传输坏处是没有内置校验所以落盘后不要手工编辑。import os def save_share(path: str, x: int, y: int, prime: int) - None: fd os.open(path, os.O_WRONLY | os.O_CREAT | os.O_TRUNC, 0o600) with os.fdopen(fd, wb) as f: f.write(f{x}|{y}|{prime}\n.encode()) def load_share(path: str): with open(path, r, encodingutf-8) as f: x_str, y_str, prime_str f.read().strip().split(|) return int(x_str), int(y_str), int(prime_str)save_share 用 os.open 而不是 open目的是创建文件时就设置 0600 权限只有当前用户能读写防止份额文件被同机其他用户读走。load_share 不做格式校验如果文件被截断或手工改过会在 int() 转换时报 ValueError这其实比静默出错好。解压一个宣称实现方案的压缩包后你往往会在里面看到类似格式的份额文件和 main 脚本这种“x|y|prime”的约定相当常见。真正要把份额拿到线下分发时建议把每份份额写到单独的 U 盘或打印成二维码并且明确“份额永远不要和 prime 放同一介质”。虽然 p 是公开参数泄露 prime 本身不泄露秘密但奇偶校验和后续调试会因此多出很多便利。我见过有人图省事把 n 份份额加 prime 一起打成一个 zip 存在网盘那就等于没拆。4.2 处理真实密钥AES-256 到整数、随机素数生成真实密钥是字节串比如 AES-256 密钥是 32 字节。要参与 Shamir 运算得先转成整数而且这个整数必须小于 prime。如果只是拿 2^127-1 当 prime一个 32 字节的秘密根本放不进去恢复出来的是 secret mod prime使用方几乎无法察觉。正确流程是先确定秘密的字节长度再生成一个位长比它大 128 的随机素数最后把字节串转成 int。import secrets def bytes_to_int(b: bytes) - int: return int.from_bytes(b, big) def int_to_bytes(value: int, length: int) - bytes: return value.to_bytes(length, big) def is_probable_prime(n: int, rounds: int 32) - bool: if n 2: return False for q in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29): if n % q 0: return n q d, r n - 1, 0 while d % 2 0: d // 2 r 1 for _ in range(rounds): a secrets.randbelow(n - 3) 2 x pow(a, d, n) if x 1 or x n - 1: continue for _ in range(r - 1): x pow(x, 2, n) if x n - 1: break else: return False return True def random_prime(bits: int) - int: while True: p secrets.randbits(bits) | (1 (bits - 1)) | 1 if is_probable_prime(p): return pis_probable_prime 是 Miller-Rabin 素性测试rounds32 时对生产级密钥长度来说误判概率已经低到可忽略。random_prime 里三个位运算分别保证比特数达到 bits、最高位为 1、最低位为 1。素数是在循环里现生成的一次循环平均几十次随机采样python 大整数模幂运算很快完全够用。与之配套的完整切分函数也很短def split_secret_bytes(secret: bytes, t: int, n: int): value int.from_bytes(secret, big) prime random_prime(len(secret) * 8 128) assert value prime, 秘密超出素数范围请增大 bits shares generate_shares(value, t, n, prime) return shares, prime我的习惯是这份 secret 是 32 字节时bits 传 384。如果你在做 python 量化交易策略代码或者数据分析项目顺手复用这套 bytes/int 映射也行本质上它就是把任意字节串安全地塞进整数域。4.3 分发节奏与演练参数和代码都定了分发环节往往是整个方案最容易泄气的地方。我的做法分四步先在本机生成完整份额并立刻删除原始密钥文件再逐份复制到独立介质然后在三台机器上分别演练恢复最后把“谁持有哪一份”的记录清单加密存放。记录清单很重要——密钥托管系统的最大风险不是算法被攻破而是时间久了没人知道哪份份额在谁手里。对 n5、t3 的经典组合我会把份额编号和持有人对应关系这样安排份额 1、2 放在两个核心负责人手里份额 3 放备份保险箱份额 4、5 分别交到跨地域的另外两位同事手上。这样任何一个人单独行动都凑不够 3 份而任意三人组合一定包含至少一个核心负责人。演练频率我建议每半年一次恢复一次的真实耗时要控制在半小时以内做不到就说明文件格式或流程有问题。5. 踩坑与排查5 个会让恢复结果“成功但错误”的高频问题5.1 没做模运算拉格朗日插值给出了带小数的结果现象恢复出的秘密是 42.0000000001 或者完全不对的大整数把结果 round 一下偶尔能对上换一组份额又乱了。原因把拉格朗日公式里的除法直接写成了/python 3 里对两个整数会得到浮点数浮点精度在几百位大整数场景下根本不够用。解决所有运算改用模 prime 的整数运算除法替换成乘模逆元。注意 python 3.8 以下没有内置的pow(a, -1, prime)需要自己写扩展欧几里得或者升级解释器。另一个被忽略的点是负数取模python 里(-3) % 7 4负数的行为是取正余数写num (num * (0 - xj)) % prime时不用担心符号问题但如果你从别的语言转过来要确认自己写的%语义一致。5.2 份额被悄悄篡改恢复出来的秘密是另一个值现象恢复流程正常跑完没有抛任何异常但输出和原秘密对不上而且换一份受污染的份额后每次错误结果都不同。原因Shamir 方案本身只做秘密共享不提供完整性校验。攻击者改掉任意一份份额拉格朗日插值依然能算出唯一的 P(0)只是这个值不再是原始秘密软件层面没有任何提示。解决在切分前给秘密加上校验信息。常见做法是对秘密做 HMAC把摘要拼在秘密后面一起切分恢复后校验摘要。代价是方案从“信息论安全”降级为“计算安全”但能直接暴露篡改行为工程上很值得。import hmac import hashlib def seal_secret(secret: bytes, mac_key: bytes) - bytes: tag hmac.new(mac_key, secret, hashlib.sha256).digest()[:16] return secret tag def open_secret(payload: bytes, mac_key: bytes) - bytes: secret, tag payload[:-16], payload[-16:] expect hmac.new(mac_key, secret, hashlib.sha256).digest()[:16] if not hmac.compare_digest(tag, expect): raise ValueError(份额被篡改或恢复出的秘密不完整) return secretmac_key 必须单独放在另一个保管链路里比如公司密码管理器。这样即使攻击者拿到全部份额没有 mac_key 也无法构造能通过校验的伪造秘密。我在生产工具里一直保留这个校验位恢复前先过 open_secret不通过直接终止流程。5.3 随机系数取到 0多项式真实的“度数”降级了现象方案配置是 t3但只用 2 份份额就能恢复出原秘密或者 CEO 和 CTO 两个人就能绕过第三个人动用密钥。原因如果随机生成的某个多项式系数恰好是 0实际多项式次数会低于 t-1。极端情况下其余的系数也全是 0所有份额都等于秘密本身。random.randrange(0, prime) 的默认写法没有排除 0。解决份额生成时把系数取值范围改成 randrange(1, prime)从源头排除零系数。更稳妥的做法是在生成后做一次度数自检用任意两份份额验证它们对应的多项式次数是否真的大于等于 t-1不过代码层面直接把取值下限定为 1 是最干净的处理。另一个关联隐患是 x 编号重复如果手工把两份份额的 x 都改成同一个值插值矩阵会退化表现为要么直接报错、要么恢复出一个并非唯一的秘密务必保证 x 唯一且大于 0。5.4 少于 t 份也能“恢复”怎么向协作方解释完美性现象拿 t-1 份调用 reconstruct_secret函数照样返回一个整数看起来像“部分恢复”有人会据此认为方案不够安全。原因这不是错误恰恰是完美秘密共享的体现。在模 p 有限域里任意 t-1 个点都能被无穷多条不同的 t-1 次多项式经过对应该点组合的 P(0) 均匀分布在 0 到 p-1 上和随机猜一个没有区别。算法只是在“硬算”一条多项式并不意味着算出来的值有意义。解决代码里加一道门槛恢复前强制校验份额数量if len(shares) t: raise ValueError(f至少需要 {t} 份份额当前只有 {len(shares)} 份)但要注意这个校验只在你显式传入 t 时才有意义。真正的“不可恢复”是数学保证的不是异常机制保证的。给协作方演示时我会故意拿 2 份跑两次把两次不同结果打印在同一行比讲任何概率论都直观。5.5 random 模块的种子问题用伪随机数生成的系数遇到安全评审现象工具功能正常但安全评审不通过理由是随机数源不合格。在某些语言实现里如果随机种子被攻击者控制多项式系数可被预测进而推导出秘密。原因python 的 random 模块是梅森旋转算法伪随机且状态可复现不是密码学安全随机数生成器。它在模拟、测试里没问题用在密钥托管场景就是缺口。解决把 radom.randrange 换成 secrets.randbelowimport secrets def secure_random_coeff(prime: int) - int: # 返回 [1, prime-1] 内的密码学安全随机数 return secrets.randbelow(prime - 1) 1secrets 模块底层依赖操作系统提供的熵源性能比 random 慢一个量级但在生成多项式系数这种一次性操作上完全无感。我的习惯是 demo 里用 random所有要跨机器传递、要长期保存的份额一律走 secure_random_coeff。这个问题属于典型的“平时测不出来、审核一看就挂”提前规避能省很多解释成本。6. 上生产前的自检函数以及怎么把 t-of-n 玩出更多价值6.1 一个断言式自检脚本任何工具提交给团队使用前我都先跑一遍组合自检不仅验证任意 t 份能恢复还要验证 t-1 份恢复结果不等于真值把数学性质变成可执行的断言。from itertools import combinations def selftest(secret: int, t: int, n: int, prime: int) - bool: shares generate_shares(secret, t, n, prime) for comb in combinations(shares, t): assert reconstruct_secret(list(comb), prime) secret, 合法组合恢复失败 # 完美性保证此断言在 prime 足够大时成立概率接近 1 bad reconstruct_secret(list(shares[: t - 1]), prime) assert bad ! secret, t-1 份不应该恢复出原秘密 print(selftest passed) return Truecombinations 会枚举所有 C(n,t) 种合法组合对 n5、t3 就是 10 种跑完不到一秒。第二个断言按数学原理几乎不会失败如果有一天它真的失败了第一件事检查随机源是否被篡改、prime 参数是否被改小。这套自检脚本放在源码仓库里以后任何人改了参数或代码都能先验证一轮再提交。6.2 把 t-of-n 用出更多价值Shamir 方案能做的事不止“托管一个静态密钥”。我最近在做的 python 数据分析项目里用它来给一组敏感性配置做“多人审批后解密”把配置拆成份额后用同一个自检函数验证完整性配置轮换时只需要重新生成份额不需要改动业务代码。另一个常见场景是加密钱包助记词备份把助记词转成字节按 t3、n5 拆成 5 份分别存进保险箱、银行保管箱和两个可信同事手里助记词原文立刻删除。真正上生产环境之前建议补上几个硬性习惯用 secrets 而不是 random 生成一切涉及秘密的随机数用 os.open 设置 0600 权限落盘恢复流程必须经过第 5.2 节的完整性校验。我自己最深刻的教训是早年用 random 写完第一版后自我感觉良好结果安全评审一句“随机源不合格”就把代码打了回来。后来我把这套工具彻底重写把 selftest 挂进 CI每次改动代码库都自动跑一遍再没在这种基础环节上翻过车。希望帮到你。本文还有配套的精品资源点击获取