准备资料
资料提炼
- 通过阅读 盲签名源码
可以知道，当一个明文
m经过盲化、签名，最后再去盲的操作后的最终结果为： $ ((((m(r^{e} n)) n)^{d} n)r^{-1}) n $
其中：
m为明文r为随机数n和e组成公钥，n和d组成私钥，根据 RSA 加密算法定义可知：e和d满足：\(ed \equiv 1 \pmod {\phi(n)}\)- $ r^{-1} $ 为 r 对于 n 的模反元素，满足：$ r^{-1} r $
| 说明 | 公式 | 编号 |
|---|---|---|
| 结合律 | $ ((a b) \% n c) \% n = (a (b c) \% n) \% n $ | 1 |
| 模结合律 | $ a^{b} \% n = ((a \% n)^{b}) \% n $ | 2 |
| 乘法分配律 | $ (a b) \% n = (a \% n 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}\) 了