Crypto Lab 3: ECC & Paillier¶

本节 lab 题目为 CryptoHack 上的题目，总数较多，但是不要求全部完成。

题目所需的思路多为上课讲过的内容。

题目内容：

所做题目要求提供思路与源码，除 BACKGROUND 和 STARTER 的部分会进行查重（这不意味这前两部分可以抄袭，亦会考虑对明显雷同者做处罚）QAQ

另外请遵守 CryptoHack 的规则，即对于 Starter 分区与小于等于 10pts 的题目以外的任何题目，请不要在公网上公开分享直接的思路、脚本等内容。

所得分数按在 CryptoHack 所设定的 points 和给出，会根据大家提交的作业的 points 采用合适的方式换算（当然，保证换算函数做到 pts 越高则得分越高）出最终得分。

为了避免在这种设定下大家相互卷或者都跑去做 Lab 2，做出以下设定：

达到 300pts 一定是本专题 100 分（Basic Task）
达到 800pts 一定是 +100 分（Bonus/Extend Task，与 Lab 2 的 Bonus 形成互相溢出的关系，Lab 2 做到 200 分或本专题做到 800pts 则 Crypto 专题满分，但继续多做不再加分；如果以前对 Crypto 专题的分数有其他模糊的设定，以此处设定为准）

虽然不加分了但是还是鼓励完成更多的题目，比如 AK CryptoHack 啥的。

课上讲的又快又迷糊 QAQ，可以慢慢康康 CryptoHack 上的介绍题或下面的讲稿来学习相关知识：

什么是椭圆曲线？¶

就是满足

\[ y^2=x^3+ax^2+bx+c \]

的点 \((x,y)\) 组成的集合，注意 \(x^3+ax^2+bx+c=0\) 需有 3 个不同解。（当然，椭圆曲线还有其他形式，这里是 Weierstrass 形式，相互间通过对坐标的线性变化得到同态映射）

这里的加法定义在一个有加法交换群定义和乘法交换群定义的域上，常见的域有全体有理数集合组成的域，通过模一个素数意义下的运算定义出加减乘除的素数域（模数非素数时，逆元不一定找得到，其乘法也就不再是一个封闭的群）。

Sage 上定义这样的曲线（\(GF(p)\) 等价于模素数 \(p\) 意义下定义出来的素数域；\(GF(p^e)\) 可以看作每个系数均为模 \(p\) 意义下的，且整个多项式处于模一个最高次项是 \(x^e\) 的多项式的域）：

 sage: E = EllipticCurve(GF(10007), [0,2,0,4,5])
 Elliptic Curve defined by y^2 = x^3 + 2*x^2 + 4*x + 5 over Finite Field of size 10007

怎样运算椭圆曲线？¶

取负 ¶

点 \(A=(x,y)\) 则 \(-A=(x,-y)\)。

加法 ¶

两个椭圆曲线上的点 A,B 可以定义其加法，结果为 \(C=A+B\)。

当\(A\neq B\) ( 除\(B=-A\)以外 ) 时：

易解出两点处在一直线 \(y=kx+b\) 上，该直线与椭圆曲线的交点（联立方程得）有 3 个，其中两个是 \(A,B\)，易用韦达定理算出另一个点 \(-C=(x_{-C},y_{-C})\)。则 \(C=(x_{-C},-y_{-C})\)。

当 \(A= B\) 时：

曲线的点 \(A\) 的切线的斜率 \(k_A\)（你可以用原曲线求导得到）为

\[ k=\frac{3{x_A}^2+2bx_A+d}{2y_A} \]

易解出 \(A\) 的切线，该切线与椭圆曲线的交点（联立方程得）有 3 个，其中两个是 \(A,A\) 易用韦达定理算出另一个点 \(-C=(x_{-C},y_{-C})\)。则 \(C=(x_{-C},-y_{-C})\)。

当 \(B=-A\) 时：

根据前面取负的定义，此时直线 \(AB\) 在曲线上只找到两个解。

但是没有关系，我们可以抛弃欧氏几何对于两条平行线不相交的假设，采纳非欧几何的观点，认为他们相交于无穷远点 \(\infin\)（通常，也记为 \(O\)）。（想象一下，从任何一个方向远离原点走无限远的距离，都将到达 \(\infin\)）

因此 \(\infin=A+(-A)\)。

当 \(A,B\) 中有一个是无穷远点时：

将 \(\infin=A+(-A)\) 移项，有 \(A+\infin=A\)。

可见，椭圆曲线上的加法构成一个群（原来的曲线的 \(x\) 有 3 次保证有第 3 个解，而非欧几何的 \(\infin\) 保证有单位元，\(y^2\) 保证有逆元（\(-A\)））。

我们需要的是一个大素数阶的循环群，因此选取一点作为生成元（被叫做基点 \(G\)），接下来讨论的都将是这个生成子群上的元素。（事实上，椭圆曲线群必然与循环群或者两个循环群的直和同构，且一般用于密码学的椭圆曲线是第一种情况）

乘法 ¶

我们将 \(k\) 个点 \(A\) 相加的和记作 \(kA\)，可见，如果我们把椭圆曲线的加法叫“乘法”，那么所谓的 \(kA\) 就是 \(A^k\)。

可以用反复平方法（快速幂）来算乘法。

除法 ¶

存在计算椭圆曲线上解的个数 \(|E|\) 的算法，而曲线上的点生成的循环群的阶 \(n\) 必然是其因子（记余因子为 \(h=\frac{|E|}{n}\)），因此如果能将 \(|E|\) 因式分解，那么曲线的阶自然也就知晓了。(Sage 上直接执行 E.order() 即可求得曲线上点的数量 )

当阶是一个大素数 \(n\) 时，由于 \((kn+x)G=k\infin+xG=xG,\forall k,x\in \mathbb{Z}\)，所以如果这个乘数在模 \(n\) 意义下是相同值，则乘法的结果就相同，因此，可以认为乘数在 \(GF(n)\) 上，进而定义除法 \(\frac{G}{x} = (x^{-1})G\)，其中 \(x^{-1}\) 为 \(x\) 在 \(GF(n)\) 上的乘法逆元。

离散对数问题 ¶

即已知 \(A,kA\) 求 \(k\)。

当阶为 \(n\) 的群是一个循环群时，它与模 \(n\) 意义下的整数加法群同构。而求这个加法群的离散对数是非常容易的，当 \(ka\equiv w\pmod n\) 时，显然有其”离散对数“ \(k\equiv wa^{-1}\pmod n\) 。因此，椭圆曲线加法群上的点本质上对应着模意义下整数加法群上的一个数字，而两者本身的加法都是易求的，困难的是求得这个对应关系（也就是同构映射）。

PS：因此，当对椭圆曲线的理解有困难时，完全可以类比模 n 意义下的整数加法群（只是你不知道每个点具体代表的哪个数字）。

hash-to-point¶

输入一串内容，可以返回一个椭圆曲线上的点的哈希函数。（这个密码学原语的关键在于返回的点对于基点或者其他它所返回的点的离散对数是难以计算的，因此不能用一个 hash-to-scalar 的算法算出一个 k，然后返回 \(kG\) 了事）

参考例题：”hash-to-point" 原语误用 PlaidCTF2022 - pressure

双线性配对 ¶

当曲线定义在 \(GF(p)\) 上、曲线群的阶为 n 时，我们定义曲线的嵌入度数为满足 \(p^k\equiv 1\pmod n\) 的最小正整数 k。（如果模 n 意义下的整数乘法是个群，那么 k 就是由 p 生成的子群大小）

可见，这玩意一般是很大的，当其非常小时，如下一个双线性配对是容易计算的：

e(A,B)=C 其中 A 是 GF(p) 上定义的椭圆曲线上的点，B 是 \(GF(p^k)\) 上定义的椭圆曲线上的点，C 是 \(GF(p^k)\) 上的值。

它满足双线性，即 \(e(xA,yB)=e(A,B)^{xy},e(A+B,C)=e(A,C)e(B,C),e(A,B+C)=e(A,B)e(A,C)\)。

PS：BLS 短签名算法，SM9 标识密码算法等算法依赖它，此外，它也使得在一些情况下的椭圆曲线易受攻击。

具体的双线性映射实现可以参考 https://crypto.stanford.edu/pbc/notes/elliptic/weil.html。

总结 ¶

上面的内容的具体细节并不重要，重要的是我们得到了一个循环群，这个群上的运算是容易的，但是离散对数问题是困难的。

此外，我们还有有趣的双线性配对可以做 :)

椭圆曲线上的公钥密码体制的应用简介 ¶

由于离散对数是困难的，我们定义私钥 x，公钥 xG。

密钥交换 ¶

Diffle-Hellman 很容易从 GF(p) 的乘法群上移到曲线群上，即 Alice 随机选择 \(x_A\)，发送 \(x_AG\)，Bob 选择 \(x_B\)，发送 \(x_BG\)。

而 \(s=x_A(x_BG)=x_B(x_AG)=s'\) 作为交换到的秘密。

公钥加密 ¶

通过密钥交换，容易定义此节。

可以注意到，双方密钥交换能够实现公钥加密算法，即加密者首先随机生成一个私钥 p' 并算出公钥 P'，算出 s=KeyExchange(P,p') 作为对称密钥来加密 m 得到 c'，令 c=(c',P')；私钥持有者算出 s=KeyExchange(P',p) 并以此来解密 c' 得到 m。椭圆曲线上的公钥加密算法就是这样实现的。

数字签名 ¶

以下介绍最简单的 Schnorr 签名（相比依赖的假设更多、更复杂的 ECDSA, SM2 等算法而言）：

数字签名的本质是：

签名者要向验证者展示一项自己拥有 p （“超能力”）才能做到的事情，同时，这个“展示”和 m 强相关。

而签名者拥有的所谓“超能力”自然是能求解 \(xG\) 的离散对数了，但是，毫无疑问，这会向验证者暴露 \(x\)，接下来验证者就可以变成私钥持有者了。

这时我们注意到，如果对 \(xG\) 做线性变换，那么它的离散对数签名者仍然能知道。例如：给出 \(c,r\)，那么 \(cxG+rG\) 的离散对数就是 \(cx+r\)。注意到 \(cxG,xG+rG,cxG+rG\) 中如果 \(c,r\) 随机，那么三者等概率的取到椭圆曲线群上的任意一点。那么对于任意一点的离散对数，自然没有问题？

但是如果验证者知道 \(r,c\)，那么它照样可以求出 \(x\)，为此我们需要确保验证者只知道 \(rG\)，而不知道 \(r\)。

由于签名者必须知道 \(r\)，那么过程可以是签名者随机选取 \(r\)，发送 \(rG\) 给对方。

那么 \(c\) 呢？如果是签名者提供的，显然它可以随机选取 \(k\)，然后令所谓的 \(rG=kG-cxG\)，虽然签名者并不知道 \(x,r\) ，但显然签名者能回答 \(cxG+rG\) 的离散对数 \(k\)。因此 \(c\) 必须在给出 \(rG\) 后由验证者生成。

整理一下：

签名者告知本次签名的相关对象为 \(m\)；
签名者随机生成 \(r\) 发送 \(rG\)；
验证者随机生成 \(c\)；
签名者计算 \(s=r+cx\) 发送 \(s\)；（有些地方最后两步是减法，不影响正确性）
验证者验证 \(sG=rG+cxG\)。

除了第 5 步以外，前面的步骤也要验证者参与，这意味着签名者必须在每次签名时都在线能够回答问题？

因此，需要将交互式的证明过程变换成非交互的，这个过程被称作 Fiat-shamir 变换：

即，将验证者随机生成的内容，替换为此前验证者收到的内容输入密码学安全哈希函数（比如 SHA256，下文简记做 \(H\)）后的输出。

也就是说，签名改为：

签名者随机生成 \(r\)；
签名者计算 \(c=H(rG,m,xG)\)；
签名者计算 \(s=r+cx\) 发送 \((rG,s)\)；（有些地方发送的是 \((s,c)\)，不影响正确性）
验证者验证 \(sG=rG+H(rG,m,xG)xG\)。

这样前 3 步就是标准的签名步骤，最后一步就是标准的验证步骤了。

高级 Schnorr 签名简介 ¶

多签 (MuSig) ¶

多签，即多个人（一个组）共同对一个消息表示认可。

最朴素的多签方法是，每个人各自签一个名，这样签名的大小就会变得较大。

一种想法是，签名时实际上对聚合公钥 \(X=\sum x_iG\)，作签名。但是，如果其中第 j 个人随机生成 k 并声称它的公钥是 \(x_jG=kG-\sum_{i\neq j} x_iG\)。他就可以自己拿着 k 对替代整个组来签名（这称作密钥取消攻击）。

一种解决方法是 \(X=\sum H(x_1G,\ldots,x_nG,x_iG)x_iG\) 采用类似 Fiat-shamir 变换的思想，想要密钥取消攻击，必须先得知由 \(H(\ldots)\) 确定的系数，而想要算出这些系数，必须先得出 \(x_jG\)。

同时，多签的过程中要求任何人串通都不能得到余下人的密钥，因此，计算 s 不能是共享一个 \(r\)，大家给出自己的 \(cx_i\)。而是每人生成 \(r_iG\) 并共享，然后大家算出 \(rG=\sum r_iG\)，据此求出 c，然后每个人求出 \(s_i=r_i+cx_i\)，求出签名中的 \(s=\sum s_i\)。

同理，大家对 \(r_iG\) 也有可能采取密钥取消攻击，为此，大家首先分享 \(H(r_iG)\)，全数摘要收到后再分享 \(r_iG\) 的同时验证摘要是否正确。

离散对数相等证明 ¶

考虑对于群上两个基点 \(G,H\) 要证明 \(C=xG,D=xH\) 的同时不泄露 \(x\)，也可用 Schnorr 签名进行。

其步骤如下：

签名者随机生成 \(r\)；
签名者计算 \(c=H(rG,rH,G,H,C,D)\)；
签名者计算 \(s=r+cx\) 发送 \((rG,rH,s)\)；
验证者验证 \(c=H(rG,rH,G,H,C,D),sG=rG+cC,sH=rH+cD\)。

这里，签名者同样被要求解答线性变换后的离散对数问题，且要求变换后离散对数相等。

这里 \(s,c\) 均共用，因此唯一的作弊机会来到了伪造 \(r'H(r'\neq r)\) 并声称 \(r'H\) 是 \(rH\) 上；但是伪造正确的 \(r'H\) 需要事先得知 \(c\)，Fiat-shamir 变换保证了这是难以做到的。

离散对数相等证明可用于为环签名提供可链接性，实现可验证随机函数（VRF）等。

环签名 ¶

这里介绍一种被叫做自发匿名组（SAG）签名的环签名，可见，环签名是你自行选择和任意 n-1 个其他公钥组成一个组，进行签名，而验证者只能确认你是组中的一员而不知道你具体是用哪个公钥对应的私钥签名。

这通常用于用户需要证明自己满足某个性质时，找到其他若干个同样满足性质的身份的公钥进行环签名，从而使得用户证明自己拥有某个性质的同时不泄露自己的具体身份。

发送的是 \((s,c)\) 版本的 Schnorr 签名的验证可表述为计算 \(c'=H(sG-cxG,m,xG)\) 验证 \(c'=c\)。

这里有一个先得知的 \(c\) 和基于此算出来的 \(c'\) 他们“神奇”地相等了，又或者说，\(c\) 是个大小为 \(1\) 的“环”。

我们记第 \(i\) 个组员（环成员）的公钥为 \(x_iG\)。

让我们扩充这个环，使得验证过程变为 \(\forall i,c_{i+1}=H(s_{i}G-c_ix_iG,m,x_iG);c_{n+1}=c_1\)。

那么如何进行签名呢？

首先我们要选择自己混入的是第 \(\pi\) 个组员（不然也就没有匿名性了）。

然后随机生成 r，计算 \(c_{\pi+1}=H(rG,m,x_{\pi}G)\)。

然后依次计算 \(c_{\pi+1},\ldots,c_{n+1}=c_{1},\ldots,c_{\pi}\) 为 \(c_{i+1}=H(s_{i}G-c_ix_iG,m,x_iG)\)，其中 \(s_i\) 为任选随机数。

令 \(s_{\pi}=r+cx_{\pi}\)，然后发送签名 \(c_1,s_1,\ldots,s_n\)。

由此，在验证者看来，\(c_1,s_i\) 均为随机值，没法分辨你是谁（或者说，得出签名时的变量 \(\pi\)）了。

事实上，这样的环签名具有完全匿名性，也就是即使离散对数难题被攻破了，验证者造出量子计算机了，乃至非确定图灵机了，验证者仍然不知道是谁签的名。

任意群上离散对数求解简介 ¶

本节不限于椭圆曲线群，而可以扩展到任意群。

本节和下节默认的问题是已知 \(A,kA\) 求 \(k\)。

先来复习两个基础课的算法：

BSGS algorithm¶

Baby-Step Giant-Step 是每个 OIer 都耳熟能详的算法，对于阶为 n 的群，它可确定地在 \(O(\sqrt{n})\) 的时间内求出任一离散对数问题，同时消耗 \(O(\sqrt{n})\) 的空间。（与之相比，暴力枚举对数 k 耗时 O(n)）

下面记 \(d=\lfloor \sqrt{n}\rfloor\)。

首先，\(\forall x\in[0,d]\) 计算 xA 并存入哈希表 T 中。（Baby-Step）

枚举 \(i\in [0,\lfloor\frac{n}{d}\rfloor]\)，计算 \(kA-idA\) 并在 T 中查找，如找到离散对数 x，则 \(k=id+x\)。（Giant-Step）

Pohlig-hellman algorithm（光滑曲线上的攻击）¶

我们一直在强调，群的阶必须要有大素数，如果没有，会发生什么（这样的曲线被称作光滑曲线）？

令曲线的阶的唯一质因数分解如下 \(n=\prod p_i^{e_i}\)。

那么，如果我们可以求得 \(\{x_i\}\) 使得 \(x_i\equiv n\pmod {p_i^{e_i}}\) 那么，我们总是可以通过中国剩余定理恢复 n。

接下来，我们先来考虑求得 \(x\equiv n\pmod {p_i}\)：

令 \(A'=\frac{n}{p_i}A,(kA)'={\frac{n}{p_i}(kA)}\)，显然有 \(k A'=(kA)'\)，但是，由 \(A'\) 生成的子群的大小至多只有 \(p_i\)（如果 A 生成子群的大小为 n，即 \(nA=\infin\)，那么 \(p_iA'=\infin\) ）。

那么套用前面的算法，我们只需要 \(O(\sqrt{p_i})\) 的时间求解离散对数。

进一步地，令 \(x'\equiv n\pmod{p_i^2}\)，那么 \(x'=k’p_i+x\)，我们只需要求得 \(k'\in[0,p_i)\) 即可。

类似的，我们求 \({\frac{n}{p_i^2}(kA-xA)}\) 相对 \(A'\) 的离散对数即可，也只需要 \(O(\sqrt{p_i})\) 的时间。

同理，我们可以求出 \(x_i\equiv n\pmod{p_i^{e_i}}\)。

也就是说，我们只花费了 \(O(\sum e_i\sqrt{p_i})\) 的时间求出了离散对数，当 n 中没有大质因子时，这将是致命的。

Pollard’s \(\rho\) algorithm¶

Pollard’s \(\rho\)algorithm 算法能在 \(O(\sqrt{n})\) 内消耗 O(1) 的空间算出离散对数 k。

其大概原理为生成伪随机序列 \(a_iA+b_ikA\)，当存在两个元素相等时（根据生日攻击，此时元素个数约为 \(\sqrt{n}\)），有：

\[ a_iA+b_ikA=a_jA+b_jkA\\ a_i+b_ik=a_j+b_jk\\ k=\frac{a_i-a_j}{b_j-b_i} \]

同时，这也意味着伪随机序列存在着大小为 j-i 的循环节。

如果令伪随机序列的下个元素由上个元素确定 ( 即\(x_{i+1}=f(x_i)\) )，那么由 Floyd 的找循环节算法可以在 O(1) 的空间内找到循环节：

维护两个值 c,d，每一步令 \(c\leftarrow f(c),d\leftarrow f(f(d))\)，则第 i 步时 \(c=x_i,d=x_{2i}\)，当 c=d 时，有循环节大小为 i。

Pollard’s Kangaroo(Lambda) algorithm¶

推广上面的算法，我们可以得到 Pollard’s Kangaroo(lambda) 算法，它能在 \(O(\sqrt{r-l})\) 内消耗 O(1) 的空间算出已知 \(k\in [l,r)\) 的离散对数 k。

直接在 Sage 调用 discrete_log_lambda(kA, A, (lbound, rbound),operation='+') 即可求解（由于椭圆曲线群在 Sage 中是加法群，因此需要最后一个参数，否则默认尝试乘法群）

具体原理参考：https://en.wikipedia.org/wiki/Pollard%27s_kangaroo_algorithm

椭圆曲线上离散对数求解简介 ¶

奇异曲线及其攻击 ¶

我们在本章开头强调，\(x^3+ax^2+bx+c=0\) 需有 3 个不同解，但如果它有解相同，会发生什么？

曲线 \(y^2 = (x-\alpha)^3\) 被称作 cusp，而曲线 \(y^2 = (x-\alpha)^2(x-\beta)\) 被称作 node，他们的点 \((\alpha, 0)\) 被称作奇异点。（两种曲线均为奇异曲线）

对于 node，存在如下同构映射，将一个椭圆曲线上的点映射到 GF(p) 的乘法群中。

\[ \begin{array}{rrcl} \varphi : & E(GF(p)) & \longrightarrow & GF(p)^{\times}, \\ & (x,y) & \longmapsto & \frac{y + \sqrt{\alpha-\beta}(x-\alpha)}{y - \sqrt{\alpha-\beta}(x-\alpha)}. \end{array} \]

接下来，问题等价于在 GF(p) 的乘法群上的离散对数。

对于 cusp，有将一个椭圆曲线上的点映射到 GF(p) 的加法群中的同构映射：

\[ \begin{array}{rrcl} \varphi : & E(GF(p)) & \longrightarrow & GF(p)^{+}, \\ & (x,y) & \longmapsto & \frac{y}{x-\alpha}. \end{array} \]

这显然没有任何安全性可言。

异常曲线攻击（SMART attack）¶

当 n=p 时，我们可以构造如下的同构映射，使得曲线加法被映射到 GF(p) 上的加法：

首先我们扩展点的加法，点和 GF(p) 上的数字 \(\alpha\) 关联起来，记作 \([P,\alpha]\)，此时点的加法定义为

\[ [P, \alpha] \oplus [Q, \beta] = [ P + Q, \alpha + \beta + slope(P,Q)] \]

\(slope(P,Q)\) 返回两点所在直线的斜率（P=Q 时是点在椭圆曲线上切线的斜率）。

接下来计算 \(n[P,0]=[\infin,\beta]\)，令 \(\varphi(P) = \beta\) 作为这个同构映射。

无效曲线攻击 ¶

当曲线上的点由其他人提供时，我们必须要判断点是否在曲线上，而如果点并不在曲线上，当我们就当无事发生地进行点的数乘运算，我们实际上在算什么东西？

事实上，Weierstrass 形式曲线的加法，并没有任何运算有 \(c\) 的参与。将你的点 \((x',y')\) 带入曲线方程解出 \(c'\)，你实际上就在以 \((a,b,c')\)为参数的曲线上运算，而这样的曲线不是被精心设计的，因此很容易是光滑曲线。

降级曲线攻击 ¶

而对于另一种实现中常见的曲线形式——Edwards 曲线，如果不校验点，那么其他人可以输入 \((0,y)\)，此时点的乘法满足：

\(n(0,y)=(0,y^n)\)，换言之，离散对数问题来到了 GF(p) 上。

实数域曲线离散对数的计算 ¶

我们通常在 GF(p) 上实现椭圆曲线，但是，在实数域上实现椭圆曲线的问题是什么？

对于实数域乘法群的“离散“对数，大家都知道可以通过放缩和泰勒展开来计算，但实数域上的椭圆曲线的问题则没有这么广为人知，甚至在网上能够找到声称通过把椭圆曲线的运算扩展到实数域的三流论文。而事实上对于曲线 \(y^2=x^3+ax+b\)，我们有：

\[ \begin{array}{rrcl} \varphi : & E(R) & \longrightarrow & R/Z^{+}, \\ & (x,y) & \longmapsto & \left\{ \begin{array}{rrcl}\frac{\int_{x}^{+\infin}\frac{dx}{\sqrt{x^3+ax+b}}}{2\int_{\gamma}^{+\infin}\frac{dx}{\sqrt{x^3+ax+b}}} \pmod 1, &y>0\\ 1-\frac{\int_{x}^{+\infin}\frac{dx}{\sqrt{x^3+ax+b}}}{2\int_{\gamma}^{+\infin}\frac{dx}{\sqrt{x^3+ax+b}}} \pmod 1, &y<0 \end{array} \right. \end{array} \]

这里 \(\gamma\) 为方程 \(x^3+ax+b=0\) 的最大实数解；\(R/Z\)( 圆群 ) 上的运算可以视为 \([0,1)\) 上的整数进行加法运算（运算结果只取小数部分，即\(\pmod 1\)）。

几何解释：

椭圆曲线的两翼趋向的无穷远点是同一个点，因此将两翼连接就近似于一个圆。

一种基于 double 的同态构造方法是：（把圆内角是 0~360° 看作 0~1，而 y>0 则在前 0.5，否则在后 0.5，然后 double 后看 y 的符号即可确认下一位是在那个 0.5 里的哪一半，以此类推）。

而积分方法在几何上是把 \(y\) 坐标取反后统计面积占比。

圆群上的离散对数可以通过格基规约求解，例如小数精度为 50 位时，问题 nA=B 的离散对数 n 即格基 \([(10^{50},0),(\lfloor 10^{50}A\rfloor,1)]\) 与向量 \((\lfloor 10^{50}B\rfloor,0)\) 的 CVP 的第二个值的绝对值。

低嵌入度数的曲线（MOV 攻击）¶

但嵌入度数 k 较小时，任取定义在 \(GF(p^k)\) 上的椭圆曲线上的一点 Q，计算 \(e(A,Q),e(kA,Q)\)。

而 \(e(A,Q)^k=e(kA,Q)\) 因此问题转移（同构映射）到 \(GF(p^k)\) 上，后者可以采用数域筛法（NFS）在相比在椭圆曲线上更容易地求出离散对数。（可下载 cado-nfs 计算离散对数）

由此也可以看到，椭圆曲线上的离散对数的困难性和同构映射计算的困难性有着莫大的关系。

双线性配对带来的其他威胁 ¶

本文并不详细介绍关于椭圆曲线困难性相关的命题，除了椭圆曲线上的离散对数问题（ECDLP）外，还有 One more discrete logarithm problem（OMDLP）等问题的困难性论证这些密码学的安全性，ECDLP 如果可解，他们也一样可解，但反之并不亦然。

例如，前述 Diffle-Hellman 密钥交换相关存在两个命题：

ECCDHP，椭圆曲线上的 Diffle-Hellman 可计算性问题：即给定 xG,yG 求 xyG。

ECDDHP，椭圆曲线上的 Diffle-Hellman 可判定性问题：即给定 xG,yG 和 A，请判断 A=xyG 是否成立。

后者在嵌入度数为 1 的曲线上显然是易受威胁的，因为此时存在 GF(p) 的椭圆曲线上两个点映射到 GF(p) 上的双线性映射，而 \(e(xG,yG)=e(G,G)^{xy}=e(xyG,G)\)，因此只要判断 e(A,G)=e(xG,yG) 是否成立就足以回答问题。

此外，Weil 配对满足 e(X,Y)=1 当且仅当存在 \(aX=bY,a,b\in \mathbb{Z}\)，进而可以判断点是否在任一循环群上。

数字签名中与 r 相关的攻击简介 ¶

本节不限于椭圆曲线群和 Schnorr 签名，例如 DSA、ECDSA 算法也易受类似的攻击

r 重用 ¶

考虑签名中关键的线性式子 \(s=r+cx\)。

两次签名中使用了相同的 r，意味着 \(s_1=r+c_1x,s_2=r+c_2x\pmod n\) 而未知数只有 r,x 因此可以联立方程求解。

r 线性相关 ¶

考虑采用线性同余随机数生成器 LCG （假设 d 已知）来产生随机数 r，那么 l 次签名的 r 满足

\(r_{i+1}=ar_{i}+b\pmod d\)

同时 \(s_i=r_i+c_ix\pmod n\)。

对于 l 次签名，我们可以列 2l-1 个等式，含有 3+l 个未知量，显然当 l 足够大时，我们就有机会解出所有方程。

当然，需注意到这些模意义下的线性方程的模数不同。

这时，我们可以祭出格基规约大法，对于第 i 个方程为 \(\sum_{j=1}^{m}a_{i,j}x_j=b_i\pmod {p_i}\) 的 n 个方程的方程组，构造格基：

\[ \begin{bmatrix} a_{1,1} & \cdots & a_{1,m} & p_1 & & & b_1 \\ \vdots & \ddots & \vdots & & \ddots & & \vdots \\ a_{n,1} & \cdots & a_{n,m} & & & p_n & b_n \\ 1 & & & & & & \\ & \ddots & & \\ & & 1 & \\ \end{bmatrix} \]

根据 \(x_i\) 可能的取值范围适当缩放此格基的每一列向量，其 CVP 即为前 n 格元素为 0，后 m 个元素为 \(x_i\)（乘上缩放系数）的向量。

（其实建议直接调用求解不同模意义下的线性方程组的板子 solvelinmod.py，见附件，为 github 公开内容）

r 部分已知 ¶

如果每次我都泄露 r 的一些比特呢（比如 r 虽然随机，但是随机的范围是 [0,x]，而 \(x<<n\) 导致前几位都是 0）。

那么，我们的 \(r=r_c+r_ss_c\) 其中 \(r_c,s_c\) 为常数，而 \(r_s\) 非常小。

考虑 \(s=r+cx\)，我们的问题将会转换为如下的问题（Hidden number problem，HNP）：

即求解第 i 个方程为 \(x_i-t_iy+a_i\equiv 0\pmod p\) 的 m 个方程的方程组，其中 \(p,a_i,t_i\) 已知，且 \(x_i\) 非常小 ( 小于 B)。

”非常小“要素察觉，快去西天请格基规约：

\[ \begin{bmatrix} p \\ & p \\ & & \ddots \\ & & & p \\ t_1 & t_2 & \cdots & t_m & B/p \\ a_1 & a_2 & \cdots & a_m & & B \end{bmatrix} \]

这里每行为一向量，其 CVP 为 \((-x_1,-x_2,..,-x_m,-By/p, B)\)。

可见，格基规约是求线性、解非常小的方程组的利器。

Paillier 同态加密 ¶

基础 ¶

加法同态 ¶

对数的加法即幂次结果的乘法。令对数为密文，则有 \(g^{m_1}g^{m_2}=g^{m_1+m_2}\)。（原文 m，密文 \(g^{m}\)）

现在的问题是，解密需要有人会做离散对数，而且要求恰好是私钥拥有者会做，其他人不会做。

比如说，对于光滑合数阶群的离散对数问题，可以用 Pollard rho、Pollard lambda、BSGS、Pohlig Hellmen 解决，但是，毫无疑问地，问题变成了所有人都可以解决。

解决特定情形的离散对数问题 ¶

一个将在模平方乘法群上的离散对数转为乘法的神奇技巧（仔细考虑\(\pmod{p^2}\) 意味着什么即可得到）：

p 是素数。根据欧拉定理，\(\phi(p^2)=p(p-1),\phi(p)=p-1\)

对于任意数 g，\(g^{p-1}=1\pmod p\)，换言之 \(g^{p-1}=kp+1\)。

对于所有整数成立的式子对于模任意数也成立，因此 \(g^{p-1}\equiv kp+1\pmod{p^2}\)

而 \((kp+1)^m\equiv mkp+1\pmod{p^2}\) 注意二项式定理，且更大的项都被\(p^2\)模掉了。

定义 \(L_p(x)=\frac{x-1}{p}\)。请注意，\(L_p\) 的输入是在\(\pmod{p^2}\) 下的，而输出是在\(\pmod p\) 下的。

那么 \(L_p((kp+1)^m)=L_p(mkp+1)=mk\pmod p\)。将式子左侧成 k 在模 p 下的逆元即可求出 \(m\pmod p\)。

扩展到合数情景 ¶

“二”解决了离散对数问题，但是没法做到“只有私钥拥有者会做”，为此，我们将其扩展为合数情景，从而引入私钥 ( 大整数的分解 )。

根据 RSA，我们知道知道 (p-1)(q-1) 和知道素数分解等价，前者可以作为秘密。

n=pq，而 p,q 是素数。

根据欧拉定理，\(\phi(n^2)=pq(p-1)(q-1),\phi(n)=(p-1)(q-1)\)。

现在我们求 \(\mathbb{Z}_{n^2}\) 与 \(\mathbb{Z}_{n}\) 群的最大生成子群的阶，根据 Carmichael 函数， \(\lambda(n)=lcm(p-1,q-1),\lambda(n^2)|pqlcm(p-1,q-1)=n\lambda(n)\)（伏笔）。（显然，知道 \lambda(n) 或知道 \phi(n) 可以转换，前者可以作为秘密）

对于任意数 g，\(g^{\lambda(n)}=1\pmod n\)，换言之 \(g^{\lambda(n)}=kn+1\)。

同上面的理 \(g^{\lambda(n)}\equiv kn+1\pmod{n^2}\)

而同样根据二项式定理，有 \((kn+1)^m\equiv mkn+1\pmod{n^2}\) 。

\(L_n((kn+1)^m)=L_n(mkn+1)=mk\pmod n\)。将式子左侧乘 k 在模 n 下的逆元 \(\mu\) 即可求出 \(m\pmod n\)。

交换运算次序 ¶

上面的过程是首先有 g，第一步得到 \(g^{\lambda(n)}\)，第二步得到 \(g^{\lambda(n)m}\) ，第三步反解得到 m。

毫无疑问，加密操作是引入 m 的时候发生的，但问题是第三步不需要用到秘密，而第一步却用到了秘密。

为了解决这个问题，我们根据幂运算的性质来交换运算次序：

首先有 g，第一步得到 \(g^{m}\)，第二步得到 \(g^{\lambda(n)m}\) ，第三步反解得到 m。

这样就够成了密码协议（协议中的计算 \(d=f(a,b,c)=\ldots=g(a,b,c)\) ，表示算法中的步骤为 \(d\coloneqq f(a,b,c)\)，而 \(\ldots\) 是对 f(a,b,c) 的数学推导，其结果等于 g(a,b,c)）：

密钥生成 ¶

Miller-Rabin 得到大素数 p,q，计算 \(n=pq,\lambda(n)=lcm(p-1,q-1)\)。

随机生成 g，算出 \(k=L_n(g^{\lambda(n)})=L_n(kn+1)\)，求 k 在模 n 下的逆元 \(\mu\)，如果逆元不存在，重新生成 g。（可见，不存在的概率极小）

公钥 g,n （加密所需）。私钥 \(\lambda(n),\mu\) （解密所需，其中 \(\lambda(n)\) 是难以求出的秘密本身）

加密 ¶

消息为 \(m\pmod n\)，密文 \(c\equiv g^m\pmod{n^2}\)。

解密 ¶

首先，计算 \(h=L_n(c^{\lambda(n)})=L_n({(g^{\lambda(n)})^{m}})=L_n((kn+1)^m)=L_n(mkn+1)=mk\)。

解密得到 \(m=h\mu=hk^{-1}\pmod n\)。

简言之，\(m=L_n(c^{\lambda(n)}\pmod{n^2})\mu\pmod n\)。

同态加法 ¶

消息的加法 \(m_1+m_2 => c_1c_2=g^{m_1+m_2}\pmod{n^2}\)。

随机扰动 ¶

现在的问题是，有意义的值很可能很小，比如 1,2,3。攻击者只要依次加密他们并把结果与某个有意义的值的密文比较，就可以得到这个值是多少。换言之，离散对数极小时，离散对数问题的困难性不存在。

一个想法是，密文引入“完美的”随机扰动 t，使得 \(c'\equiv g^mt\pmod{n^2}\)。

随机扰动足够的多，导致没法爆破。

但是同时又不影响解密，即 \(m=L_n({c'}^{\lambda(n)}\pmod{n^2})\mu\pmod n\) 仍然成立。

即，要使得 \(c^{\lambda(n)}=g^{m\lambda(n)}\pmod{n^2}\) 与 \({c’}^{\lambda(n)}=g^{m\lambda(n)}t^{\lambda(n)}\pmod{n^2}\) 相等。

即，要使得 \(t^{\lambda(n)}=1\pmod{n^2}\)。

而我们有，对于任意群元素 x，\(x^{\lambda(n^2)}\equiv 1\pmod{n^2}\)。

伏笔回收，\(x^{n\lambda(n)}\equiv 1\pmod{n^2}\)。也就是说 \({(x^n)}^{\lambda(n)}\equiv 1\pmod{n^2}\)。

换言之取随机数 r，\(r^n\) 就是一个“完美的”随机扰动，而且得到这样的一个扰动不需要私钥信息。

回顾一遍整个协议：

密钥生成（不变）¶