前言
其实一个月前就设计了这个游戏，今天正式整理发布。
算法采用
通过利用argon2id算法的内存硬度来对抗GPU运算，实现基于内存的PoW，拉低硬件差距。
通过利用shamir算法门限方案，增加游戏乐趣。
游戏整体流程图
flowchart TD
Enumerate(Enumerate Nonce) --> |枚举 Nonce| Target[Target Nonce]
M[Memory Cost] --> Parameters[Parameters]
T[Time Cost] --> Parameters[Parameters]
Parallelism[Parallelism] --> Parameters[Parameters]
Length[Output Length] --> Parameters[Parameters]
Salt[Salt] --> Parameters[Parameters]
Parameters[Parameters] --> |参与计算| Argon2id[Argon2id PoW]
Target[Target Nonce] --> |参与计算| Argon2id[Argon2id PoW]
Argon2id[Argon2id PoW] --> |派生内容| Secret[Secret]
Secret[Secret] --> |转换| AES1Key[AES Key]
AES1Key[AES Key] --> |参与计算| AES1[AES Algorithm]
EncryptedShamirContent[Encrypted Shamir Key] --> |参与计算| AES1[AES Algorithm]
AES1[AES Algorithm] --> |解密内容| TagShamirKey[Tag + Shamir Key]
TagShamirKey[Tag + Shamir Key] --> |匹配 Tag| CorrectTag{Correct Tag}
CorrectTag{Correct Tag} --> |No| Enumerate(Enumerate Nonce)
CorrectTag{Correct Tag} --> |Yes| ShamirKey[Shamir Key]
ShamirKey[Shamir Key 1] --> |参与计算| Shamir[Shamir Algorithm]
ShamirKey2[Shamir Key 2] --> |参与计算| Shamir[Shamir Algorithm]
ShamirKey3[Shamir Key 3] --> |参与计算| Shamir[Shamir Algorithm]
MoreShamirKey[...] --> |参与计算| Shamir[Shamir Algorithm]
Shamir[Shamir Algorithm] --> |合成 AES Master Key| MasterAESKey[AES Master Key]
MasterAESKey[Master AES Key] --> |参与计算| AES2[AES Algorithm]
EncryptedContent[Encrypted Content] --> |参与计算| AES2[AES Algorithm]
AES2[AES Algorithm] --> |得到解密密文| DecryptedContent(Decrypted Content)玩法讲解
公开参数
首先，出题者会给出本次游戏难度（Argon2id算法）参数：
- Memory Cost(m) - 内存开销：指定算法在计算过程中需要使用的内存总量
- Time Cost / Iterations (t) - 时间开销 / 迭代次数：指定算法的执行轮数。
- Parallelism / Lanes (p) - 并发度 / 线程数：指定计算时可以同时使用的独立计算通道（lanes）或线程数量。
- Salt (S) - 盐值：随机数据。
- Output Length / Hash Length (l) - 输出长度：最终哈希结果的字节长度，一般为32用于匹配AES256密钥长度
下方为可选的公开数据：
- Range - Nonce范围：Nonce的范围，可用于降低游戏难度。
然后，出题者会公开本次游戏奖池数与最少碎片数（Shamir算法）：
- Total shares(n) - 总份额数 / 碎片总数：指定总奖池数量。
- Threshold(k) - 阈值 / 门限值：拼凑出最终Key所需的最少碎片数。
公开密文
接着，出题者会公开本次游戏所有的被加密的密文以及标识：
- 所有被加密的Shamir Key（奖池）的密文
- 最终需要解密的密文
- 正确解密的内容所包含的Tag
开始计算
首先，解题者需要从挑选一个奖池，确定奖池的密文。
然后找出一个Nonce（随机数），将公开的游戏难度参数与Nonce通过argon2id算法进行计算，计算时间由出题者设置的难度决定。
如果出题者公开了Nonce范围，则在范围内寻找。
计算完成后会得到一个派生内容。
接着解题者需要将派生内容转换为 AES Key（具体转换规则由出题者公布），通过AES算法将奖池密文解密出来。
解密出内容后，可以通过Tag进行匹配（其实也可以不用匹配，AES-CGM模式下自带MAC校验），如果能成功匹配，则说明是正确的Nonce，成功得到一枚碎片；如果不能匹配成功，则说明是错误的Nonce，需要重新寻找。
当集齐出题者所设置的最少数量的碎片时，即可通过Shamir算法将碎片合成一个AES Master Key。
最后，通过这个AES Master Key，解密得到最终的奖品。
计算优化
寻找Nonce
如果出题者给出Nonce范围，则可以尝试采用随机+HashMap去重的方式，将一部分期望压在你的lucky上。
你可能计算一次就中，也可能计算完整个奖池才中😄。
当然，你也可以一个一个算。
并行计算
虽然出题者可以限制argon2id算法的并行数，但解题者可以并行的寻找Nonce并计算，只要解题者愿意付出额外的资源与成本😄。
算法讲解
argon2算法
argon2有些复杂，不讲（
Shamir算法
以下内容参考于Gemini
Shamir算法全名叫Shamir 秘密共享算法 (Shamir's Secret Sharing)。
Shamir算法的数学基础是多项式插值。
首先构造一个多项式
假设要隐藏的密钥是数值 SS。随机生成一个 m−1m-1 次的多项式：
f(x)=a0+a1x+a2x2+⋯+am−1xm−1f(x) = a_0 + a_1x + a_2x^2 + \dots + a_{m-1}x^{m-1}
在这个多项式中，常数项 a0a_0 为要隐藏的密钥 SS（即 f(0)=Sf(0) = S），而其他的系数 a1,a2,…,am−1a_1, a_2, \dots, a_{m-1} 为随机生成。
然后，在这个多项式的曲线上取 nn 个不同的点 (x1,y1),(x2,y2),…,(xn,yn)(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n) 。
在数学上，要唯一确定一个 m−1m-1 次的多项式，刚好需要 mm 个点。
只要任意 mm 个点，就可以通过拉格朗日插值法计算出完整的原多项式，从而求出 a0a_0，也就是还原出了真正的密钥 SS。
如果凑齐点数少于 mm 个，即使拥有 m−1m-1 个点，也无法推导出常数项 a0a_0 。
示例
例如典型的 (3, 5) 门限方案
门限 m=3m=3，因此需要一个 3−1=23-1=2 次的多项式。
二次多项式也就是一元二次方程，它的图像是一条抛物线 (Parabola)。
方程的形式为：
f(x)=a2x2+a1x+Sf(x) = a_2x^2 + a_1x + S
在这条抛物线上，随机切下 5 个不同的点（比如 x=1,2,3,4,5x=1, 2, 3, 4, 5 对应的坐标）。
5 个坐标点 (x1,y1)(x_1, y_1) 到 (x5,y5)(x_5, y_5)。
在几何学中，任意三个不在一条直线上的点，可以唯一确定一条抛物线。只要有 3 个坐标点，通过方程计算，就能还原出这条抛物线，找到它与 Y 轴的交点（即 x=0x=0 时的值），即可把 SS 算出来。
如果只有 2 个点，两点只能确定一条直线。经过这两个点的抛物线有无数条，无法知道哪一条是真正的抛物线，SS 的可能性为无限大。
下面为具体数值演示
隐藏的密钥：S=42S = 42 （也就是抛物线与 Y 轴交点的值，即 x=0x=0 时的 yy 值）。
方程：f(x)=−2x2+5x+42f(x) = -2x^2 + 5x + 42 （对还原者隐藏）。
生成的 5 个坐标点：
- (1,45)(1, 45)
- (2,44)(2, 44)
- (3,39)(3, 39)
- (4,30)(4, 30)
- (5,17)(5, 17)
假设已知的坐标分别是 (1,45)(1, 45)、(3,39)(3, 39) 和 (4,30)(4, 30)
拉格朗日插值法 (Lagrange Interpolation)
拉格朗日插值法的核心思想是“加权”。对于每一个点的 yy 值，乘以一个特定的“权重系数”（通常用 ll 表示），然后相加即可得到 x=0x=0 时的密钥 SS。
公式如下：
S=y1⋅l1+y2⋅l2+y3⋅l3S = y_1 \cdot l_1 + y_2 \cdot l_2 + y_3 \cdot l_3
权重 ll 它只和的 xx 坐标 有关。
计算规则是：用其他的 xx 坐标除以“其他的 xx 坐标减去自己的 xx 坐标”，然后相乘。
把选出的三个点的 xx 坐标分别记为：x1=1x_1=1，x2=3x_2=3，x3=4x_3=4。
计算 (1,45)(1, 45) 的权重 l1l_1： 提取另外两个的 xx 坐标（33 和 44），与 xx 坐标（11）进行计算：
l1=x2x2−x1⋅x3x3−x1l_1 = \frac{x_2}{x_2 - x_1} \cdot \frac{x_3}{x_3 - x_1}
l1=33−1⋅44−1=32⋅43=126=2l_1 = \frac{3}{3 - 1} \cdot \frac{4}{4 - 1} = \frac{3}{2} \cdot \frac{4}{3} = \frac{12}{6} = 2
计算 (3,39)(3, 39) 的权重 l2l_2： 提取另外两个的 xx 坐标（11 和 44），与 xx 坐标（33）进行计算：
l2=x1x1−x2⋅x3x3−x2l_2 = \frac{x_1}{x_1 - x_2} \cdot \frac{x_3}{x_3 - x_2}
l2=11−3⋅44−3=1−2⋅41=−2l_2 = \frac{1}{1 - 3} \cdot \frac{4}{4 - 3} = \frac{1}{-2} \cdot \frac{4}{1} = -2
计算 (4,30)(4, 30) 的权重 l3l_3： 提取另外两个的 xx 坐标（11 和 33），与 xx 坐标（44）进行计算：
l3=x1x1−x3⋅x2x2−x3l_3 = \frac{x_1}{x_1 - x_3} \cdot \frac{x_2}{x_2 - x_3}
l3=11−4⋅33−4=1−3⋅3−1=33=1l_3 = \frac{1}{1 - 4} \cdot \frac{3}{3 - 4} = \frac{1}{-3} \cdot \frac{3}{-1} = \frac{3}{3} = 1
现在，将三个点的 yy 值与各自算出的权重相乘，然后相加：
S=(y1⋅l1)+(y2⋅l2)+(y3⋅l3)S = (y_1 \cdot l_1) + (y_2 \cdot l_2) + (y_3 \cdot l_3)
S=(45⋅2)+(39⋅−2)+(30⋅1)S = (45 \cdot 2) + (39 \cdot -2) + (30 \cdot 1)
S=90−78+30S = 90 - 78 + 30
S=42S = 42
最后还原出了最初设定的密钥 42。
原始的解方程
依然使用上文 3 个坐标点：(1,45)(1, 45)、(3,39)(3, 39) 和 (4,30)(4, 30)。
3 个点确定的抛物线，它的标准方程形式则为：
y=ax2+bx+cy = ax^2 + bx + c
目标是求出未知的系数 aa、bb 和 cc。
注意： 当 x=0x = 0 时，y=cy = c。因此，因此需要寻找的 SS 其实就是常数项 cc。
将 3 个 (x,y)(x, y) 坐标分别代入标准方程中：
- 代入点 (1,45)(1, 45)：
a(1)2+b(1)+c=45a(1)^2 + b(1) + c = 45
化简得：a+b+c=45a + b + c = 45 (方程 ①)
- 代入点 (3,39)(3, 39)：
a(3)2+b(3)+c=39a(3)^2 + b(3) + c = 39
化简得：9a+3b+c=399a + 3b + c = 39 (方程 ②)
- 代入点 (4,30)(4, 30)：
a(4)2+b(4)+c=30a(4)^2 + b(4) + c = 30
化简得：16a+4b+c=3016a + 4b + c = 30 (方程 ③)
现在，得到了一个包含三个未知数 (a,b,ca, b, c) 的三元一次方程组。
为了解开它，可以通过两个方程相减，先消去常数项 cc：
1. 用方程 ② 减去方程 ①：
(9a+3b+c)−(a+b+c)=39−45(9a + 3b + c) - (a + b + c) = 39 - 45
8a+2b=−68a + 2b = -6
两边同除以 2，化简得：4a+b=−34a + b = -3 (方程 ④)
2. 用方程 ③ 减去方程 ②：
(16a+4b+c)−(9a+3b+c)=30−39(16a + 4b + c) - (9a + 3b + c) = 30 - 39
7a+b=−97a + b = -9 (方程 ⑤)
3. 用方程 ⑤ 减去方程 ④，消去 bb：
(7a+b)−(4a+b)=−9−(−3)(7a + b) - (4a + b) = -9 - (-3)
3a=−63a = -6
解得：a=−2a = -2
4. 把 a=−2a = -2 代回方程 ④，求 bb：
4(−2)+b=−34(-2) + b = -3
−8+b=−3-8 + b = -3
解得：b=5b = 5
现在已知 a=−2a = -2 和 b=5b = 5。将其代入方程 ① 中：
a+b+c=45a + b + c = 45
−2+5+c=45-2 + 5 + c = 45
3+c=453 + c = 45
解得：c=42c = 42
后记
其实这个游戏不仅可以用argon2id算法，也可以用RSW时间锁谜题这类算法。