从各种签名方案的签名值中恢复公钥的具体方法与难易程度，包括ECDSA、RSA、Schnorr、Dilithium、SPHINCS+和UOV等。
通常来说，对一个签名方案，我们可以使用公钥来判断给定的签名是否有效。但如果我们只有一个消息和一个签名，并确保该签名是有效的，如何知晓它对应的公钥呢？这里就存在一个有意思的点：攻击大众所认知的“每个人都使用密码学签名来完成一切”的思维，这篇博客就考虑了如何从各种签名方案的签名值去恢复公钥。
ECDSA 签名由两个整数 $(r, s) $组成，满足方程 $sR = zG + rP_A，z\equiv ms^{-1}\ mod\ n $，其中$ R $是椭圆曲线上 $x $坐标等于 $r $的点，能用$r$恢复完整的坐标；而$G$和$n$都是已知量。通过简单的推导，我们能得到$ P_A = r^{-1}sR - r^{-1}zG$，公钥就恢复了。
针对RSA签名的情形，我们需要两对消息/签名 $s_1 $和 $s_2$，$ m_1 $和$ m_2$，满足$ s^e \equiv m\ mod\ n$，公私钥还满足关系式： $ d \cdot e \equiv1\ mod\ \varphi(n)$。在使用中，e 通常等于65537，那么只需要计算 $ n’ = \gcd(s_1^e - m_1, s_2^e - m_2) $ 即可得到$n$。由于欧几里得算法非常高效，我们能够在短时间内算出$n$为2048位的结果。不过$n’$并不完全等于$n$，GCD出来的结果很可能是$n$和某些小素数的倍数，还需要进一步确定它是否包含小因子。
Schnorr签名是一种椭圆曲线签名，和ECDSA类似，它的公钥从阶为$n$的椭圆曲线点$G$中得到$P_A = x_A G$，$r$为$P_A$的$x$坐标，签名时计算$c = H(r || m)$和$s \equiv k - c \cdot x_A\ mod\ n$。
如果假设该算法的签名值为$(r, s)$，此时可以通过计算$P_A = c^{-1}R - c^{-1}sG$恢复公钥。
但是在原本的Schnorr签名中，签名值为$(c, s)$，则无法恢复公钥，因为$c$是公钥经过哈希后得到的值，它具有足够的熵，很难恢复原像。
现在让我们进入后量子算法Dilithium，先回忆一下，在LWE问题中，公钥是模素数$q$的一个向量$t$和一个矩阵$A$满足$t \equiv As+e\ mod\ q$，$s$和$e$是较短的密钥向量，Dilithium算法还无情的将$t$的低位给抛弃，只将其部分高位作为公钥给出。Dilithium的签名为$z = y + cs$，其中$c = H(m||w_1)$，而$w_1$是$Ay$的高比特，验证者检查$Az - ct = Ay+ c As - cAs - ce$是否有相同的高位$w_1$来验签。
在Dilithium中，由于$w_1$明显大于$c$，为了降低带宽，所以签名固定为$(c, z)$，这种情况下与Schnorr签名类似，公钥无法恢复。当然，如果$w_1$也是签名的一部分，再已知$A$的话，就可以恢复出$t$的高位。如果$A$不知道，则不能恢复高位。
SPHINCS+是一种基于哈希的签名方案，它的签名比较复杂：SPHINCS+使用一个多层次的Merkle树结构，每一层的根节点哈希值都依赖于下层节点的哈希值。最底层的叶节点通过一系列的哈希函数生成，签名包含特定叶节点的哈希值以及证明该叶节点属于Merkle树的认证路径。但是，SPHINCS+和Dilithium一样，都对公钥做了哈希处理使其无法恢复。不过如果还给出额外的信息，还是存在恢复公钥的可能性。
还记得高中时学的一元二次方程吗？给定一个$y$，计算出满足$ax^2+bx+c = y$的$x$，它存在通解即$x_{1, 2} = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$，因此，我们必须提高维度来稍微增加难度。
UOV算法的公钥是$o$个含有$o+v$个变量的二次方程（即$f_i(x_1, x_2, \dots, x_{o+v})_{i=1, \dots, o}$）。它们都是齐次方程，因此可以用矩阵表示：$f_i(x)=x^TA_ix(x$是向量)。在签名时，签名者通过门陷函数计算出一些满足$(f_i(x))_i=1,\dots,o=H(m)$的$x$作为公钥。可以看出，UOV的签名比公钥短的多，单个签名显然无法恢复公钥。但如果我们收集了多个签名，就可以通过插值的方法恢复公钥多项式。
通过理论推导，我们需要$\frac{(o+v)(o+v+1)}{2}$个消息/签名对即可恢复公钥。考虑到\((b_i)^{\frac{(o+v)(o+v+1)}{2}}_{i=1}=(X_i \cdot X_j)^{u+v, u+v}_{i=1, j=i}\)，
对于每个消息/签名对$(x_i, y_i)$，我们能计算出$b_k(x_j)$。由于还知道$f_i(x_j)=y$，还能确定每个$f_i$都是$b_k$的线性组合，这就组成了一个线性方程组，那么只要收集到$\frac{(o+v)(o+v+1)}{2}$个签名，它就会有唯一解。
从上面可以看出，各个签名方案在公钥恢复的难易程度方面差异非常大。但是验签逻辑通常不是为了抗侧信道而设置的，因此即使使用了不会从代数上泄露公钥的方案，第三方仍然可能恢复公钥，这也成了算法设计需要考虑的一个重要方面。
https://keymaterial.net/2024/06/15/reconstructing-public-keys-from-signatures/