基于 RSA 的盲签名原理以及其数学证明

准备资料

• 盲签名源码
• 取模运算规则
• 欧拉定理)
• RSA 算法原理

资料提炼

1. 通过阅读 盲签名源码 可以知道，当一个明文 m 经过盲化、签名，最后再去盲的操作后的最终结果为：

$$((((m(r^{e} \bmod n)) \bmod n)^{d} \bmod n)r^{-1}) \bmod n$$

其中：

• m为明文
• r为随机数
• n 和 e 组成公钥，n 和 d 组成私钥，根据 RSA 加密算法定义可知：e 和 d 满足：$ed \equiv 1 \pmod {\phi(n)}$
• $r^{-1}$ 为 r 对于 n 的模反元素，满足：$r^{-1} \cdot r \equiv 1 \pmod {n}$

1. 从 欧拉定理) 得到公式（a 与 n 互质）: $a^{\phi(n)} \equiv 1 \pmod {n}$
2. 从 取模运算规则 中列出以下对于本次证明有用的公式：

说明	公式	编号
结合律	$((a \cdot b) \% n \cdot c) \% n = (a \cdot (b \cdot c) \% n) \% n$	1
模结合律	$a^{b} \% n = ((a \% n)^{b}) \% n$	2
乘法分配律	$(a \cdot b) \% n = (a \% n \cdot b \% n) \% n$	3

证明过程

由盲签名的原理可知，我们需要证明：

$$((((m(r^{e} \% n)) \% n)^{d} \%n)r^{-1}) \% n = m^{d} \% n$$

下面是证明过程：

$$\begin{aligned} left=&((\color{blue}{((m(r^{e} \% n)) \% n)^{d} \%n})r^{-1}) \% n \ \ \ \text{ => 符合公式 2 的逆向}\\ =&(((m(r^{e} \% n))^{d} \% n)r^{-1}) \% n\\ =&((\color{blue}{(m^{d} \cdot (r^{e} \% n)^{d}) \%n})r^{-1}) \% n \ \ \ \text{ => 符合公式 3}\\ =&(((m^{d}\%n \cdot \color{blue}{(r^{e} \% n)^{d} \%n}) \%n)r^{-1}) \%n \ \ \ \text{ => 符合公式 2}\\ =&((\color{blue}{((m^{d} \%n) \cdot (r^{ed} \%n)) \%n})r^{-1}) \%n \ \ \ \text{ => 符合公式 3 的逆向}\\ =&\color{blue}{(((m^{d} \cdot r{ed}) \%n) \cdot r^{-1}) \% n} \ \ \ \text{ => 符合公式1}\\ =&(m^{d} \cdot (r^{ed} r^{-1}) \%n) \% n \end{aligned}$$

即需要证明 $(r^{ed} r^{-1}) %n = 1$ ，根据 RSA 加密算法的定义，得出已知条件 $ed = k \cdot \phi(n) + 1$， 代入后有：

$$\begin{aligned} &(r^{ed} r^{-1}) \%n\\ =&(r^{k\cdot\phi(n)+1} r^{-1}) \%n\\ =&\color{blue}{(r^{k\cdot\phi(n)} \cdot rr^{-1}) \%n} \ \ \ \text{ => 符合公式 3}\\ =&(r^{k\cdot\phi(n)}\%n \cdot \color{blue}{(rr^{-1})\%n}) \%n \ \ \ \text{ => 符合模反元素的定义}\\ =&(r^{k\cdot\phi(n)}\%n \cdot 1) \%n\\ =&((r^{\phi(n)} \cdot \cdot \cdot r^{\phi(n)}) \%n ) \%n \end{aligned}$$

令 $r^{\phi(n)}=p,\ p \bmod n=q$，则有：

$$\begin{aligned} &((r^{\phi(n)} \cdot \cdot \cdot r^{\phi(n)}) \%n ) \%n\\ =&(\color{blue}{(p \cdot \cdot \cdot p) \%n} ) \%n \ \ \ \text{ => 符合公式 3}\\ =&((p\%n \cdot \color{blue}{(p \cdot \cdot \cdot p) \%n} )\%n) \%n \ \ \ \text{ => 符合公式 3}\\ =&((q(q(q(\cdot \cdot \cdot (q\cdot q) \%n\cdot \cdot \cdot ) \%n) \%n) \%n) \end{aligned}$$

根据 盲签名源码 可知，r 与 n 被特意取值满足了互质条件，符合欧拉定理。那就有了 $r^{\phi(n)}\bmod n=1$，即 $q=1$，原式得证。

盲签原理

为什么我们要证明

$$((((m(r^{e} \% n)) \% n)^{d} \%n)r^{-1}) \% n = m^{d} \% n$$

因为根据 RSA 加解密过程，再结合业务场景，我们能总结出加密过程为：

$$c = m^{d} \% n$$

解密过程为：

$$m = c^{e} \% n$$

我们传给服务器的是盲化后的内容，即：

$$(m(r^{e} \% n)) \% n$$

服务器用私钥将这个内容做加密操作后，然后我们再其做去盲处理就拿到了服务器对原文的加密结果。即：

$$((((m(r^{e} \% n)) \% n)^{d} %n)r^{-1}) \% n = m^{d} \% n = c$$

其他人就可以用公钥来校验这个结果是否满足等式 $m = c^{e} \% n$

安全性

我们来看看交给服务器的盲化后的字串：

$$(m(r^{e} \% n)) \% n$$

式子里总共有四个未知量：m、r、e、n，服务器只知道 e 和 n，没有 r 求不出 m。

再来考虑一下 r 被穷举的难度有多大呢？

根据源码的 这段代码 可知，r 的选取需满足以下条件：

$$(1 < r) \land (r < min(n, 2^{80})) \land (r⊥n) \land (r ∈ N)$$

现在的 RSA 算法中的 n 一般都是 1024 位，那么 r 就是小于 $2^{80}$ 且与 n 互质的正整数。

那这样的数有多少个呢？

根据 资料 我们知道小于 n 且与 n 互质的正整数的个数叫做 欧拉函数，写作 $\phi(n)$ 。在 RSA 算法里，设 p、q 是任意两个质数，$\phi(n)$ 满足下面的条件：

$$n = p \cdot q\ \\ \phi(n) = (p-1) \cdot (q-1)$$

当 n 足够大时，并假设 p、q 亦足够大（事实上 p、q 也确实足够大），那么 $\phi(n)$ 取其二次方项：

$$\phi(n) = (p-1) \cdot (q-1)= pq - p - q + 1≈ pq = n$$

所以可知小于 n 且与 n 互质的数大致是成均匀分布，那么满足条件的 r 的个数大约是 $2^{80}$

所以 r 被穷举的难度取决于 r 的随机范围。

我看 最新代码 是把 $2^{80}$ 扩大到 $2^{512}$ 了