Curve25519

标签：mathbb right sqrt Curve25519 mbox left

1 Curve25519
对于128bit的安全级别，对于大多数的体系而言都推荐使用$2^{255}-19$这个素数来实现较为良好的性能。在$2^{250}$到$2^{521}$范围之间，同时满足$2^c-s$这个形式且$s$很小的素数很少，而且对于其他满足条件的素数，在性能上的表现却不尽如人意。这个素数满足$p≡1 (\mbox{mod }4)$，蒙哥马利曲线(Montgomery curve)$v^2=u^3+Au^2+u$由如下过程产生，称这个曲线为“Curve25519”。

1.1 系数$A$
对于满足$p≡1 (\mbox{mod }4)$的素数，曲线最小的辅因子(Cofactor)及其对应的扭曲辅因子(Twist cofactor)为$\{4,8\}$或是$\{8,4\}$。此处选取后一个辅因子对应的曲线，这样任何考虑该辅因子的算法都不必担心检查扭曲上的点，因为扭曲辅因子将是两者中较小的一个。
为了生成蒙哥马利曲线，需要找到满足$A>2$且$4|A-2$最小的正整数A，并且辅因子是必需的。如下代码中的find1Mod4函数在给定$p$的情况下返回$A$的值：

点击查看代码

<CODE BEGINS>
def findCurve(prime, curveCofactor, twistCofactor):
F = GF(prime)

for A in xrange(3, int(1e9)):
if (A-2) % 4 != 0:
continue
try:
E = EllipticCurve(F, [0, A, 0, 1, 0])
except:
continue

groupOrder = E.order()
twistOrder = 2*(prime+1)-groupOrder

if (groupOrder % curveCofactor == 0 and
is_prime(groupOrder // curveCofactor) and
twistOrder % twistCofactor == 0 and
is_prime(twistOrder // twistCofactor)):
return A

def find1Mod4(prime):
assert((prime % 4) == 1)
return findCurve(prime, 8, 4)
<CODE ENDS>

注：此处find1Mod4函数目的是寻找Curve25519曲线，对应于Curve448曲线的函数为find3Mod4，具体参阅RFC 7748中的A.2节。

1.2 基点$G$
曲线的基点是正确子群(Correct subgroup)中最小正整数$u$所对应的点。如下代码中的findBasepoint函数在给定p和A的情况下返回G的值：

点击查看代码

<CODE BEGINS>
def findBasepoint(prime, A):
F = GF(prime)
E = EllipticCurve(F, [0, A, 0, 1, 0])

for uInt in range(1, 1e3):
u = F(uInt)
v2 = u^3 + A*u^2 + u
if not v2.is_square():
continue
v = v2.sqrt()

point = E(u, v)
pointOrder = point.order()
if pointOrder > 8 and pointOrder.is_prime():
return point
<CODE ENDS>

注：其中，EllipticCurve函数表示威尔斯特拉斯方程(Weierstrass Form)，为$y^2+a_1 xy+a_3 y=x^3+a_2 x^2+a_4 x+a_6$。

如上过程生成的“Curve25519“曲线的参数如下：
$p=2^255-19$
$A=486662$
$\mbox{order}=2^{252}+0x14def9dea2f79cd65812631a5cf5d3ed$
$\mbox{cofactor}=8$
$U⁡(P)=9$
$V⁡(P)=14781619447589544791020593568409986887264606134616475288964881837755586237401$
$G=(9,14781619447589544791020593568409986887264606134616475288964881837755586237401)$
注：其中，$\mbox{order}$表示素数阶子群(prime-order subgroup)的阶，可通过协因子(cofactor)计算获得，相关阅读可参阅辅因子（cofactor）解释：揭开椭圆曲线不为人知的秘密。
关于“Curve25519“更详细介绍以及”Curve448“的详情可以参阅RFC 7748。

1.3 X25519函数
X25519函数的实现必须接受非规范值(Non-Canonical Values)，并且进行素域取模这样的处理。对于X25519，非规范值为$2^{255}-19$到$2^{255}-1$。
实现X25519函数的时候，必须屏蔽最后一个字节的最高有效位。这样做是为了保留符号位来保持与其他协议使用点格式的兼容性，并增加对实现指纹识别的抵抗力。

点击查看代码

def decodeLittleEndian(b, bits):
return sum([b[i] << 8*i for i in range((bits+7)/8)])

def decodeUCoordinate(u, bits):
u_list = [ord(b) for b in u]
# Ignore any unused bits.
if bits % 8:
u_list[-1] &= (1<<(bits%8))-1
return decodeLittleEndian(u_list, bits)

def encodeUCoordinate(u, bits):
u = u % p
return ’’.join([chr((u >> 8*i) & 0xff) for i in range((bits+7)/8)])

假定标量(Scalars)是随机生成的字节。对于X25519，为了将32个随机字节解码为整数标量，需要将第一个字节的最低三个有效位(the three least significant bits)和最后一个字节的最高有效位(the most significant bit)置为$0$，并将最后一个字节的第二个最高有效位置为$1$，最后以小端字节序(little-endian)解码。如此，生成的整数始终为$2^{254}$加上八倍的$0$到$2^{251}-1$之间任意值。

点击查看代码

def decodeScalar25519(k):
k_list = [ord(b) for b in k]
k_list[0] &= 248
k_list[31] &= 127
k_list[31] |= 64
return decodeLittleEndian(k_list, 255)

x_1 = u
x_2 = 1
z_2 = 0
x_3 = u
z_3 = 1
swap = 0

For t = bits-1 down to 0:
k_t = (k >> t) & 1
swap ^= k_t
// Conditional swap; see text below.
(x_2, x_3) = cswap(swap, x_2, x_3)
(z_2, z_3) = cswap(swap, z_2, z_3)
swap = k_t

A = x_2 + z_2
AA = A^2
B = x_2 - z_2
BB = B^2
E = AA - BB
C = x_3 + z_3
D = x_3 - z_3
DA = D * A
CB = C * B
x_3 = (DA + CB)^2
z_3 = x_1 * (DA - CB)^2
x_2 = AA * BB
z_2 = E * (AA + a24 * E)

// Conditional swap; see text below.
(x_2, x_3) = cswap(swap, x_2, x_3)
(z_2, z_3) = cswap(swap, z_2, z_3)
Return x_2 * (z_2^(p - 2))

cswap(swap, x_2, x_3):
dummy = mask(swap) AND (x_2 XOR x_3)
x_2 = x_2 XOR dummy
x_3 = x_3 XOR dummy
Return (x_2, x_3)

注：关于此节的涉及数学性质可以参阅本文自第3至9节。其中第3、4节内容主要来自Bernstein的Curve25519: new Diffie-Hellman speed records，第5节内容主要来自Montgomery的Speeding the Pollard and Elliptic Curve Methods of Factorization，第6节内容根据Bernstein的基础上给出了一个简单的实例解释Curve25519在进行标量运算时的具体计算方式，第7、8、9节给出了一些本文涉及的重要数学定理。由于来源不同，Curve25519涉及的符号较多，因此在阅读不同段落时需要注意符号表示的含义可能存在变化。

2 基于Curve25519的Diffie-Hellman(ECDH)
X25519函数可以被用于实现如下的椭圆曲线Diffie-Hellman(ECDH)协议：

1.Alice生成32个随机字节记为$a⁡[0]$至$a⁡[31]$，并计算$K_a=\mbox{X25519}⁡(a,9)$传送给Bob，其中$9$为基点的u坐标。
2.Bob同样生成32个随机字节记为$b⁡[0]$至$b⁡[31]$，并计算$K_b=\mbox{X25519}(b,9)$传送给Alice。
3.他们都使用接受到的值作为输入，并且Alice计算$\mbox{X25519}⁡(a,K_b )$、Bob计算$\mbox{X25519}⁡(b,K_a )$。

现在，他们都确定了共享密钥$K=\mbox{X25519}⁡⁡(a,K_b )=\mbox{X25519}⁡(b,K_a )$。现在，他们都可以检查K是否为全零值，以防止泄露任何K值的信息，若是的话则弃置(详细可以参阅RFC 7748的第7节)。之后，Alice和Bob可以使用包含$K$、$K_a$和$K_b$的密钥派生函数(KDF)来生成对称密钥。

事实上ECDH实现的原理非常简单，首先Alice选择了私钥$a$并计算了对应的公钥$K_a$。此时，$K_a$即对应了$aG$的$u$坐标，其中$G$为基点。类似地，Bob计算了$bG$对应的$u$坐标$K_b$。最后，Alice计算$\mbox{X25519}(a,K_b )$事实上计算的为$abG$的$u$坐标，而Bob计算$\mbox{X25519}(b,K_a )$则为baG的u坐标。又因定义在$E⁡(\mathbb{F}_{p^2 })$上的Cuvre25519满足乘法交换律，故有$abG=baG$，因此双方经过计算后获得的同样的共享密钥$K=\mbox{X25519}⁡(a,K_b )=\mbox{X25519}⁡(b,K_a )$。

RFC 7748给出的测试向量：
Alice的私钥$a$：
77076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c2a
Alice的公钥$\mbox{X25519}⁡(a,9)$：
8520f0098930a754748b7ddcb43ef75a0dbf3a0d26381af4eba4a98eaa9b4e6a
Bob的私钥$b$：
5dab087e624a8a4b79e17f8b83800ee66f3bb1292618b6fd1c2f8b27ff88e0eb
Bob的公钥$\mbox{X25519}(b,9)$：
de9edb7d7b7dc1b4d35b61c2ece435373f8343c85b78674dadfc7e146f882b4f
共享密钥$K$：
4a5d9d5ba4ce2de1728e3bf480350f25e07e21c947d19e3376f09b3c1e161742

3 Curve25519
本节与下方的第4节内容来自Bernstein的Curve25519: new Diffie-Hellman speed records，在论文中Bernstein给出了Curve25519函数运行最重要的基础定理——定理2.1。本节与下节截取了其中较为重要的部分进行介绍和证明。为了方便阅读故进行了翻译，但是无法保证翻译后的表达准确性，因此提供了英文原文进行对照阅读。若是希望对如Curve25519的安全性分析等关于Curve25519的相关知识进行进一步阅读，建议直接阅读Bernstein的原文并补充阅读Montgomery的原文。

3.1 定理2.1
令$p$为素数且$p≥5$，$A$为整数且$A^2-4$为模$p$运算下的二次非剩余。定义$E$为$\mathbb{F}_p$域下的椭圆曲线$y^2=x^3+Ax^2+x$。定义$X_0:E⁡(\mathbb{F}_{p^2})→\mathbb{F}_{p^2}$，形如：$X_0⁡(∞)=0$，$X_0⁡(x,y)=x$。令$n$为整数，$q$为$\mathbb{F}_p$域的一个元素。即对于$∀Q∈E⁡(\mathbb{F}_{p^2})$存在唯一的$s∈\mathbb{F}_p$使$X_0⁡(nQ)=s$成立，其中$X_0⁡(Q)=q$。

Theorem 2.1. Let $p$ be a prime number with $p≥5$. Let $A$ be an integer such that $A^2-4$ is not a square modulo $p$. Define $E$ as the elliptic curve $y^2=x^3+Ax^2+x$ over the field $\mathbb{F}_p$. Define $X_0:E⁡(\mathbb{F}_{p^2})→\mathbb{F}_{p^2}$ as follows: $X_0⁡(∞)=0$; $X_0⁡(x,y)=x$. Let $n$ be an integer. Let $q$ be an element of $\mathbb{F}_p$. Then there exists a unique $s∈\mathbb{F}_p$ such that $X_0⁡(nQ)=s$ for all $Q∈E⁡(\mathbb{F}_{p^2})$ such that $X_0⁡(Q)=q$.

实际上，定义p为素数$2^{255}-19$，$\mathbb{F}_p$为素域$\mathbb{Z}/p=\mathbb{Z}/(2^{255}-19)$。注意到$2$为$\mathbb{F}_p$域下的二次非剩余。定义$\mathbb{F}_{p^2}$为域$(\mathbb{Z}/(2^{255}-19))⁡[\sqrt{2}]$，$A=486662$。注意到$486662^2-4$为$\mathbb{F}_p$域下的二次非剩余。定义$E$为$\mathbb{F}_p$域下的椭圆曲线$y^2=x^3+Ax^2+x$，函数$X_0:E⁡(\mathbb{F}_{p^2})→\mathbb{F}_{p^2}$，形如：$X_0⁡(∞)=0$，$X_0⁡(x,y)=x$，函数$X:E⁡(\mathbb{F}_{p^2})→{∞}∪\mathbb{F}_{p^2}$，形如：$X⁡(∞)=∞$，$X⁡(x,y)=x$。
注：设$F$是一个域，$\mbox{Char}⁡(F)≠2$，那么任意的域的二次扩张$K$(即$[K:F]=2)$可以通过连接一个平方根得到，其中$\mbox{Char}⁡(F)$表示域$F$的特征。也就是说$K=F⁡(δ)$，且$δ^2=d∈F$。反过来，如果$δ$是在$F$的域的扩张里的一个元素，同时满足$δ^2∈F$，$δ∉F$，那么$F⁡(δ)$就是$F$的一个二次扩域。

In particular, define $p$ as the prime $2^{255}-19$. Define $\mathbb{F}_p$ as the prime field $\mathbb{Z}/p=\mathbb{Z}/(2^{255}-19)$. Note the $2$ is not a square in $\mathbb{F}_p$; define $\mathbb{F}_{p^2}$ as the field $(\mathbb{Z}/(2^{255}-19))⁡[\sqrt{2}]$. Define $A=486662$. Note that $486662^2-4$ is not a square in $\mathbb{F}_p$. Define $E$ as the elliptic curve $y^2=x^3+Ax^2+x$ over $\mathbb{F}_p$. Define a function $X_0:E⁡(\mathbb{F}_{p^2})→\mathbb{F}_{p^2}$ as follows: $X_0⁡(∞)=0$; $X_0⁡(x,y)=x$. Define a function $X:E⁡(\mathbb{F}_{p^2})→{∞}∪\mathbb{F}_{p^2}$ as follows: $X⁡(∞)=∞$; $X⁡(x,y)=x$.

此处根据定理2.1，$\mbox{Curve25519}$函数对于给定的$n∈2^{254}+8\{0,1,…,2^{251}-1\}$和$q∈\mathbb{F}_p$生成$s$。但是，为了符合密码学设计的实现并参考Menezes提出的设计错误类型，此处将$\mbox{Curve25519}$的输入和输出定义为字节序列。
字节集合定义为$\{0,1,…,255\}$，将字节编码为比特序列与此处无关。记$s↦\underline{s}$为由$\{0,1,…,2^{256}-1\}$到32字节字符串$\{0,1,…,255\}^{32}$的标准小端序双射，也即对于任意整数$s∈\{0,1,…,2^{256}-1\}$，定义$\underline{s}=(s\pmod{256},⌊s⁄256⌋\pmod{256},…,⌊s⁄256^{31}⌋\pmod{256})$。
Curve25519的公钥集合定义为$\{0,1,…,255\}^{32}，$也即$\{\underline{q}:q∈\{0,1,…,2^{256}-1\}\}$。Curve的私钥集合定义为$\{0,8,16,24,…,248\}×\{0,1,…,255\}^{30}×\{64,65,66,…,127\}$，也即$\{\underline{n}:n∈2^{254}+8\{0,1,…,2^{251}-1\}\}$。
现在，映射Curve25519可以定义为：$\mbox{Curve25519}:\{\mbox{Curve25519 secret keys}\}×\{\mbox{Curve25519 public keys}\}→\{\mbox{Curve25519 public key}\}$，有$q∈\{0,1,…,2^{256}-1\}$且$n∈2^{254}+8\{0,1,…,2^{251}-1\}$。由定理2.1可知，存在唯一整数$s∈\{0,1,…,2^{256}-1\}$满足对于任意的$Q∈E⁡(\mathbb{F}_{p^2})$有$s=X_0⁡(nQ)$，其中$X_0⁡(Q)≡q\pmod{2^{255}-19}$。最后，$\mbox{Curve25519}⁡(\underline{n},\underline{q})$定义为$\underline{s}$。注意到，$\mbox{Curve25519}$不是满射的。特别地，其输出的最后一个比特总为$0$，因此不需要传输。

At this point I could say that, given $n∈2^{254}+8\{0,1,…,2^{251}-1\}$ and $q∈\mathbb{F}_p$, the $\mbox{Curve25519}$ function produces $s$ in Theorem 2.1. However, to match cryptographic reality and to catch the types of design error explained by Menezes in [Another look at HMQV], I will instead define the inputs and outputs of $\mbox{Curve25519}$ as sequences of bytes.
The set of bytes is, by definition, $\{0,1,…,255\}$. The encoding of a byte as a sequence of bits not relevant to this document. Write $s↦\underline{s}$ for the standard little-endian bijection from $\{0,1,…,2^{256}-1\}$ to the set $\{0,1,…,255\}^{32}$ of 32-byte strings: in other words, for each integer $s∈\{0,1,…,2^{256}-1\}$, define $\underline{s}=(s \pmod{256},⌊s⁄256⌋ \pmod{256},…,⌊s⁄256^31⌋ \pmod{256})$.
The set of Curve25519 public keys is, $\{0,1,…,255\}^{32}$; in other words, $\{\underline{q}:q∈\{0,1,…,2^{256}-1\}\}$. The set of Curve25519 secret keys is, by definition, $\{0,8,16,24,…,248\}×\{0,1,…,255\}^{30}×\{64,65,66,…,127\}$; in other words, $\{\underline{n}:n∈2^{254}+8\{0,1,…,2^{251}-1\}\}$.
Now $\mbox{Curve25519}:\{\mbox{Curve25519 secret keys}\}×\{\mbox{Curve25519 public keys}\}→\{\mbox{Curve25519 public keys}\}$ is defined as follows. Fix $q∈\{0,1,…,2^{256}-1\}$ and $n∈2^{254}+8\{0,1,…,2^{251}-1\}$. By Theorem 2.1, there is a unique integer $s∈\{0,1,…,2^{256}-1\}$ with the following property: $s=X_0⁡(nQ)$ for all $Q∈E⁡(\mathbb{F}_{p^2})$ such that $X_0⁡(Q)=q\pmod{2^{255}-19}$. Finally, $\mbox{Curve25519}⁡(\underline{n},\underline{q})$ is defined as $\underline{s}$. Note that $\mbox{Curve25519}$ is not surjective: in particular, its output bit is always $0$ and need not be transmitted.

3.2 为什么是这个域？选择素数$2^{255}-19$是出于以下考量：素数尽可能地接近$2$的幂可以节约域运算的事件且不对(推测的)安全等级产生影响；素数略低于$32k$比特可以允许公钥轻松以$32$比特的字节传输，无需担心空间浪费；$k=8$可以提供一个合适的安全等级。候选的素数有$2^{255}+95$、$2^{255}-19$、$2^{255}-31$、$2^{254}+79$、$2^{253}+51$和$2^{253}+39$，最终选择$2^{255}-19$是因为$19$相比$31$、$39$、$51$、$79$、$95$更小。
注：此段讨论第1节至第1.1节之间的内容，即素域的确定。

Why this field? I chose my prime $2^{255}-19$ according to the following criteria: primes as close as possible to power of $2$ save time in field operations, with no effect on (conjectured) security level; primes slightly below $32k$ bits, for some $k$, allow public keys to be easily transmitted in 32-bit words, with no serious concerns regarding wasted space; $k=8$ provides a comfortable security level. I considered the primes $2^{255}+39$, $2^{255}-19$, $2^{255}-19$, $2^{255}-31$, $2^{254}-31$, $2^{254}+79$, $2^{253}+51$, and $2^{253}+39$, and selected $2^{255}-19$ because $19$ is smaller than $31$, $39$, $51$, $79$, $95$.

3.3 为什么是这个曲线？根据Montgomery的研究，选择形如$y^2=x^3+Ax^2+x$的曲线可以很快地计算点的$x$坐标。这种形状曲线的阶可以被$4$整除，因此需要一个略微大一些的素数才能达到相应的推测安全等级，但同时也会对曲线运算的速度造成负担。对于Curve25519按照Montgomery的建议选定了满足$(A-2)⁄4$的小整数，来加快$(A-2)⁄4$的倍乘运算，如此并不会对推测安全等级造成影响。
为了防止受到各种攻击，Curve25519选择了曲线和扭曲阶非$\{4⋅\mbox{prime},8⋅\mbox{prime}\}$的$A$，此处由于$p∈1+4\mathbb{Z}$，故$4$，$8$是最小的。由此，$A$最小的选择有$358990$，$464586$和$486662$。Curve25519没有选择$A=358990$的原因是它的其中一个素数略小于$2^{252}$，由此产生了如何才能在标准和实现中处理理论中用户可能的私钥与素数匹配的问题。显然，讨论这个问题的难度要高于换其他的$A$。至于没有选择$A=464586$也是处于同样的原因，因此最终Curve25519选择了$A=486662$。
注：此段讨论1.1节的内容，即$A$值的确定。

Why this curve? I chose the curve shape $y^2=x^3+Ax^2+x$, as suggested by Montgomery, to allow extremely fast $x$-coordinate point operations. Curves of this shape have order divisible by $4$, requiring a marginally larger prime for the same conjectured security level, but this is outweighed by the extra speed of curve operations. I selected $(A-2)⁄4$ as a small integer, as suggested by Montgomery, to speed up the multiplication by $(A-2)⁄4$; this has no effect on the conjectured security level.
To protect against various attacks discussed in Section 3, I rejected choices of $A$ whose curve and twist orders were not $\{4⋅\mbox{prime},8⋅\mbox{prime}\}$; here $4$,$8$ are minimal since $p∈1+4\mathbb{Z}$. The smallest positive choices for $A$ are $358990$, $464586$, and $486662$. I rejected $A=358990$ because one of its primes is slightly smaller than $2^{252}$, raising the question of how standards and implementations should handle the theoretical possibility of a user’s secret key matching the prime; discussing this question is more difficult than switching to another $A$. I rejected $464586$ for the same reason. So I ended up with $A=486662$.

4 定理2.1的相关知识与证明

4.1 基域 令$p$为任意素数且$p≥5$，定义$\mathbb{F}_p$为集合$\{0,1,…,p-1\}$，二元运算符$+$为$\mathbb{F}_p$上模$p$的加法运算，二元运算符$⋅$为模$p$的乘法运算，一元运算符$-$为$p$的非运算。
$\mathbb{F}_p$是$0$、$1$、$-$、$+$、$⋅$下的交换环，这意味着其符合$\mathbb{Z}$中每个$0$、$1$、$-$、$+$、$⋅$满足的特性，例如$a(b+c+1)=ab+ac+a$这一特性。进一步，因$p$为一个素数，所以$\mathbb{F}_p$是一个域，从而$\mathbb{F}_p$中每个非零元素均有倒数。

The base field. Let $p$ be a prime number with $p≥5$. Define $\mathbb{F}_p$ as the set $\{0,1,…,p-1\}$. Define a binary operation $+$ on $\mathbb{F}_p$ as addition mod $p$. Define a binary operation $⋅$ on $\mathbb{F}_p$ as multiplication mod $p$. Define a unary operation $–$ on $\mathbb{F}_p$ as negation mod $p$.
$\mathbb{F}_p$ is a commutative ring under $0$, $1$, $-$, $+$, $⋅$. This means that it satisfies every $0$, $1$, $-$, $+$, $⋅$ identity satisfied by $\mathbb{Z}$; e.g., the identity $a(b+c+1)=ab+ac+a$. Furthermore, because $p$ is prime, $\mathbb{F}_p$ is a field: every nonzero element of $\mathbb{F}_p$ has a reciprocal in $\mathbb{F}_p$.

4.2 基域中的二次剩余 对于$\mathbb{F}_p$中的非零元素，平方是一个二对一的映射，所以$\mathbb{F}_p$中存在了$(p-1)⁄2$个二次非剩余。记$δ$为$\mathbb{F}_p$中最小的二次非剩余。
费马小定理隐含了若$α$是$\mathbb{F}_p$中的非零二次剩余，则$α^{(p-1)⁄2}=1$；若$α$是$\mathbb{F}_p$中的二次非剩余，则$α^{(p-1)⁄2}=-1$；若$α=0$，则$α^{(p-1)⁄2}=0$。因此，若$α$是$\mathbb{F}_p$中的二次非剩余，那么$α⁄δ$为$\mathbb{F}_p$中的非零二次剩余。

Squares in the base field. Squaring is 2-to-1 map on the nonzero elements of $\mathbb{F}_p$, so there are exactly $(p-1)⁄2$ non-squares in $\mathbb{F}_p$. Find the smallest $δ∈\{0,1,…,p-1\}$ such that $δ$ is not a square in $\mathbb{F}_p$.
Fermat's little theorem implies that $α^{(p-1)⁄2}=1$ if $α$ is a nonzero square in $\mathbb{F}_p$; $α^{(p-1)⁄2}=-1$ if $α$ is a non-square in $\mathbb{F}_p$; and $α^{(p-1)⁄2}=0$ if $α=0$. Consequently, if $α$ is a non-square in $\mathbb{F}_p$, then $α⁄δ$ is a nonzero square in $\mathbb{F}_p$.

4.3 扩域 定义$\mathbb{F}_{p^2}$为集合$\mathbb{F}_p×\mathbb{F}_p$，$\mathbb{F}_{p^2}$上的一元运算符$-$为$-(c,d)=(-c,-d)$，$\mathbb{F}_{p^2}$上的二元运算符$+$为$(a,b)+(c,d)=(a+c,b+d)$，$\mathbb{F}_{p^2}$上的二元运算符$⋅$为$(a,b)⋅(c,d)=(ac+δbd,ad+bc)$。
$\mathbb{F}_{p^2}$是$0$、$1$、$-$、$+$、$⋅$下的交换环。进而，每个非零的$(a,b)∈\mathbb{F}_{p^2}$均有倒数$(a⁄(a^2-δb^2),-b⁄(a^2-δb^2))∈\mathbb{F}_{p^2}$。
从$\mathbb{F}_p$到$\mathbb{F}_{p^2}$的单射$a↦(a,0)$是一个环形态射，其保留了$0$、$1$、$-$、$+$、$⋅$。因此，将$(a,0)$缩写为$a$不会有混淆的风险。$\mathbb{F}_{p^2}$中的元素$(0,1)$为$\sqrt{δ}$，其满足$\sqrt{δ}^2=(δ,0)=δ$。

The extension field. Define $\mathbb{F}_{p^2}$ as the set $\mathbb{F}_p×\mathbb{F}_p$. Define a unary operation $–$ on $\mathbb{F}_{p^2}$ by $-(c,d)=(-c,-d)$. Define a binary operation $+$ on $\mathbb{F}_{p^2}$ by $(a,b)+(c,d)=(a+c,b+d)$. Define a binary operation $⋅$ on $\mathbb{F}_{p^2}$ by $(a,b)⋅(c,d)=(ac+δbd,ad+bc)$.
$\mathbb{F}_{p^2}$ is a commutative ring under $0$, $1$, $-$, $+$, $⋅$. Furthermore, each nonzero $(a,b)∈\mathbb{F}_{p^2}$ has a reciprocal $(a⁄(a^2-δb^2),-b⁄(a^2-δb^2))∈\mathbb{F}_{p^2}$.
The injection $a↦(a,0)$ is abbreviated a without risk of confusion. The element $(0,1)$ of $\mathbb{F}_{p^2}$ is abbreviated $\sqrt{δ}$; it satisfies $\sqrt{δ}^2=(δ,0)=δ$.

4.4 椭圆曲线 令$A$为$\mathbb{F}_p$上满足$A^2-4$模$p$为二次非剩余的整数，定义$E⁡(\mathbb{F}_{p^2})$为$\{∞\}∪\{(x,y)∈\mathbb{F}_{p^2}:y^2=x^3+Ax^2+x\}$。
定义$E⁡(\mathbb{F}_{p^2})$上的一元运算符$-$如：$-∞=∞$、$-(x,y)=(x,-y)$，$E⁡(\mathbb{F}_{p^2})$上的二元运算符$+$如：

$∞+∞=∞$
$∞+(x,y)=(x,y)$
$(x,y)+∞=(x,y)$
$(x,y)+(x,-y)=∞$
若$y≠0$，则$(x,y)+(x,y)=(x'',y'')$，其中$λ=(3x^2+2Ax+1)⁄2y$，$x''=λ^2-A-2x=(x^2-1)^2⁄4y^2$，$y''=λ(x-x'')-y$。此处$/$表示$\mathbb{F}_{p^2}$上的除法。
若$x'≠x$，则$(x,y)+(x',y')=(x'',y'')$，其中$λ=(y'-y)⁄(x'-x)$，$x''=λ^2-A-x-x'$，$y''=λ(x-x'')-y$。

The elliptic curve. Let $A$ be an integer such that $A^2-4$ mod $p$ is not a square in $\mathbb{F}_p$. Define $E⁡(\mathbb{F}_{p^2})$ as ${∞}∪{(x,y)∈\mathbb{F}_{p^2}:y^2=x^3+Ax^2+x}$.
Define a unary operation $–$ on $E⁡(\mathbb{F}_{p^2})$ as follows: $-∞=∞$; $-(x,y)=(x,-y)$. Define a binary operation $+$ on $E⁡(\mathbb{F}_{p^2})$ as follows:

$∞+∞=∞$
$∞+(x,y)=(x,y)$
$(x,y)+∞=(x,y)$
$(x,y)+(x,-y)=∞$
If $y≠0$ then $(x,y)+(x,y)=(x'',y'')$ where $λ=(3x^2+2Ax+1)⁄2y$, $x''=λ^2-A-2x=(x^2-1)^2⁄4y^2$, and $y''=λ(x-x'')-y$. Here $/$ refers to division in $\mathbb{F}_{p^2}$.
If $x'≠x$ then $(x,y)+(x',y')=(x'',y'')$ where $λ=(y'-y)⁄(x'-x)$, $x''=λ^2-A-x-x'$, and $y''=λ(x-x'')-y$.

标准(尽管冗长)计算证明了$E⁡(\mathbb{F}_{p^2})$是$∞$、$-$、$+$下的交换群，这意味着$\mathbb{Z}$中$0$、$-$、$+$满足的每个特性$E⁡(\mathbb{F}_{p^2})$同样满足，其中$0$需要用$∞$代替。
注意到下面三个集合为$E⁡(\mathbb{F}_{p^2})$的子群：

$\{∞,(0,0)\}$。事实上，$∞+∞=∞$、$(0,0)+(0,0)=∞$并且$(0,0)+∞=(0,0)$。
$\{∞\}∪\{E⁡(\mathbb{F}_{p^2})∩(\mathbb{F}_p×\mathbb{F}_p)\}$。事实上，若$x,y,x',y'∈\mathbb{F}_p$，则$λ$,$x''$,$y''$定义在$\mathbb{F}_p$上。
$\{∞\}∪\{E⁡(\mathbb{F}_{p^2})∩(\mathbb{F}_p×\sqrt{δ}\mathbb{F}_p)\}$。此处，倍数$λ$为$\mathbb{F}_p$中元素与$\sqrt{δ}\mathbb{F}_p$中元素的比值，因此其为$\sqrt{δ}\mathbb{F}_p$中元素，从而$x''∈\mathbb{F}_p$且$y''∈\sqrt{δ}\mathbb{F}_p$。
注意到，若$\mathbb{F}_p$中有$x^3+Ax^2+x=0$，则$x=0$。(否则$\mathbb{F}_p$中有$A^2-4=(x-1⁄x)^2$，从而$A^2-4$模$p$为$\mathbb{F}_p$中的二次剩余，故矛盾。)也即，若$x≠0$有$(x,0)∉E⁡(\mathbb{F}_{p^2})$。

Standard (although lengthy) calculations show that $E⁡(\mathbb{F}_{p^2})$ is a commutative group under $∞$, $-$, $+$. This means that every $0$, $-$, $+$ identity satisfied by $\mathbb{Z}$ is also satisfied by $E⁡(\mathbb{F}_{p^2})$ when $0$ is replaced by $∞$.
Note that the following three set are subgroups of $E⁡(\mathbb{F}_{p^2})$:

$\{∞,(0,0)\}$. Indeed, $∞+∞=∞$; $(0,0)+(0,0)=∞$; and $(0,0)+∞=(0,0)$.
$\{∞\}∪\{E⁡(\mathbb{F}_{p^2})∩(\mathbb{F}_p×\mathbb{F}_p)\}$. Indeed, if $x,y,x',y'∈\mathbb{F}_p$ then the quantities $λ,x'',y''$ defined above are in $\mathbb{F}_p$.
$\{∞\}∪\{E⁡(\mathbb{F}_{p^2})∩(\mathbb{F}_p×\sqrt{δ}\mathbb{F}_p)\}$. This time $λ$ is a ratio of an element of $\mathbb{F}_p$ and an element of $\sqrt{δ}\mathbb{F}_p)$, and is therefore an element of $\sqrt{δ}\mathbb{F}_p)$, producing $x''∈\mathbb{F}_p$ and $y''∈\sqrt{δ}\mathbb{F}_p)$.
Note also that if $x^3+Ax^2+x=0$ in $\mathbb{F}_p$ then $x=0$. (Otherwise $A^2-4=(x-1⁄x)^2$ in $\mathbb{F}_p$, so $A^2-4$ mod $p$ is a square in $\mathbb{F}_p$, contradiction.) In other words, $(x,0)∉E⁡(\mathbb{F}_{p^2}))$ if $x≠0$.

4.5 定理2.1的证明 令$n$为整数，$q$为$\mathbb{F}_p$中元素，定义$α=q^3+Aq^2+q$，$X_0:E⁡(\mathbb{F}_{p^2})→\mathbb{F}_{p^2}$，形如：$X_0⁡(∞)=0$，$X_0⁡(x,y)=x$。

$α=0$。从而有$q=0$。$\mathbb{F}_{p^2}$中仅有$0$为$0$的平方根，因此$\{Q∈E⁡(\mathbb{F}_{p^2}):X_0⁡(Q)=0\}$可以确定为群$\{∞,(0,0)\}$。进而每个$X_0⁡(Q)=q$的$Q∈E⁡(\mathbb{F}_{p^2})$有$nQ∈\{∞,(0,0)\}$，即$X_0⁡(nQ)=0$。
$α$为$\mathbb{F}_p$中的非零二次剩余。选定平方根$r$，此时有$q≠0$且仅有$±r$为$q^3+Aq^2+q$在$\mathbb{F}_{p^2}$的平方根，因此$\{Q∈E⁡(\mathbb{F}_{p^2}):X_0⁡(Q)=q\}=\{(q,r),(q,-r)\}$。定义$s=X_0⁡(n(q,r))$，群$\{∞\}∪\{E⁡(\mathbb{F}_{p^2})∩(\mathbb{F}_p×\mathbb{F}_p)\}$包含$(q,r)$，因此其包含$n(q,r)$，进而有$s∈\{0,1,2,3,…,p-1\}$。此外，$n(q,-r)=n(-(q,r))=-n(q,r)$，从而$X_0⁡(n(q,-r))=X_0⁡(n(q,r))=s$。因此，对于任意满足$X_0⁡(Q)=q$的$Q∈E⁡(\mathbb{F}_{p^2})$有$X_0⁡(nQ)=s$。
$α$为$\mathbb{F}_p$中的二次非剩余。从而有$α⁄δ$为$\mathbb{F}_p$中的非零二次剩余。选定平方根$r$，此时有$q≠0$且仅有$±r\sqrt{δ}$为$q^3+Aq^2+q$在$\mathbb{F}_{p^2}$的平方根，因此$\{Q∈E⁡(\mathbb{F}_{p^2}):X_0⁡(Q)=q\}=\{(q,r\sqrt{δ}),(q,-r\sqrt{δ})\}$。定义$s=X_0⁡(n(q,r\sqrt{δ}))$，群$\{∞\}∪\{E⁡(\mathbb{F}_{p^2})∩(\mathbb{F}_p×\sqrt{δ}\mathbb{F}_p)\}$包含$(q,r\sqrt{δ})$，因此其包含$n(q,r\sqrt{δ})$，进而有$s∈\{0,1,2,3,…,p-1\}$。此外，$n(q,-r\sqrt{δ})=n(-(q,r\sqrt{δ}))=-n(q,r\sqrt{δ})$，从而$X_0⁡(n(q,-r\sqrt{δ}))=X_0⁡(n(q,r\sqrt{δ}))=s$。因此，对于任意满足$X_0⁡(Q)=q$的$Q∈E⁡(\mathbb{F}_{p^2})$有$X_0⁡(nQ)=s$。

Proof of Theorem 2.1. Let $n$ be an integer. Let $q$ be element of $\mathbb{F}_p$. Define $α=q^3+Aq^2+q$. Define $X_0:E⁡(\mathbb{F}_{p^2})→\mathbb{F}_{p^2}$ as follows: $X_0⁡(∞)=0$, $X_0⁡(x,y)=x$.

$α=0$. Then $q=0$. The only square root of $0$ in $\mathbb{F}_{p^2}$ is $0$, so $\{Q∈E⁡(\mathbb{F}_{p^2}):X_0⁡(Q)=0\}$ is exactly the group $\{∞,(0,0)\}$. Thus each $Q∈E⁡(\mathbb{F}_{p^2})$ with $X_0⁡(Q)=q$ has $nQ∈\{∞,(0,0)\}$; i.e., $X_0⁡(nQ)=0$.
$α$ is nonzero square in $\mathbb{F}_p$. Select a square root $r$. Now $q≠0$, and the only square roots of $q^3+Aq^2+q$ in $\mathbb{F}_{p^2}$ are $±r$, so $\{Q∈E⁡(\mathbb{F}_{p^2}):X_0⁡(Q)=q\}=\{(q,r),(q,-r)\}$. Define $s=X_0⁡(n(q,r))$. The group $\{∞\}∪\{E⁡(\mathbb{F}_{p^2})∩(\mathbb{F}_p×\mathbb{F}_p)\}$ contains $(q,r)$, so it contains $n(q,r)$, so $s∈\{0,1,2,3,…,p-1\}$. Furthermore $n(q,-r)=n(-(q,r))=-n(q,r)$, so $X_0⁡(n(q,-r))=X_0⁡(n(q,r))=s$. Thus $X_0⁡(nQ)=s$ for all $Q∈E⁡(\mathbb{F}_{p^2})$ such that $X_0⁡(Q)=q$.
$α$ is a non-square in $\mathbb{F}_p$. Then $α⁄δ$ is a nonzero square in $\mathbb{F}_p$. Select a square root $r$. Now $q≠0$, and the only square roots of $q^3+Aq^2+q$ in $\mathbb{F}_{p^2}$ are $±r\sqrt{δ}$, so $\{Q∈E⁡(\mathbb{F}_{p^2}):X_0⁡(Q)=q\}=\{(q,r\sqrt{δ}),(q,-r\sqrt{δ})\}$. Define $s=X_0⁡(n(q,r\sqrt{δ}))$. The group $\{∞\}∪\{E⁡(\mathbb{F}_{p^2})∩(\mathbb{F}_p×\sqrt{δ}\mathbb{F}_p)\}$ contains $(q,r\sqrt{δ})$, so it contains $n(q,r\sqrt{δ})$, so $s∈\{0,1,2,3,…,p-1\}$. Furthermore $n(q,-r\sqrt{δ})=n(-(q,r\sqrt{δ}))=-n(q,r\sqrt{δ})$, so $X_0⁡(n(q,-r\sqrt{δ}))=X_0⁡(n(q,r\sqrt{δ}))=s$. Thus $X_0⁡(nQ)=s$ for all $Q∈E⁡(\mathbb{F}_{p^2})$ such that $X_0⁡(Q)=q$.

5 曲线上的快速差分运算
伪运算(Pseudo-operations)
考虑如下形式的四元组：

$\{X_0⁡(P),X_0⁡(Q),X_0⁡(P+Q),X_0⁡(P-Q)\}$ 如上的集合中，若已知其中的任意三个元素的值，即可获得剩余第四个元素的值。

伪加法运算——$X_ADD:(X_0⁡(P),X_0⁡(Q),X_0⁡(P-Q))→X_0⁡(P+Q)$
伪平方运算——$X_DBL:X_0⁡(P)→X_0⁡(2P)$

以上的伪加法和伪倍数运算即为快速乘法运算的基础。

令$P=(x_1,y_1)$，$Q=(x_2,y_2)$，其中$x_1≠x_2≠0$。

令$P+Q=(x_+,y_+)$，$P-Q=(x_-,y_-)$。根据Montgomery的发现，$P$、$Q$、$P+Q$和$P-Q$四个点的坐标存在如下关系：$x_+x_-(x_1-x_2)^2=(x_1x_2-1)^2$
令$2P=(x_+,y_+)$，则有：$4x_+(x_1^3+Ax_1^2+x_1)=(x_1^2-1)^2$

证明：
对于待解的第四点，不妨认为其坐标有$(x_c,y_c)$，必位于已知三点中的两个点沿$x$轴翻转连线之上，如$(x_c,y_c)=-(P+Q)=(x_+,-y_+)$，不妨令已知两点坐标为$(x_a,y_a)$，$(x_b,y_b)$。也即对于这样三个点，其在x轴的坐标必为连线与椭圆曲线联立而获得的三次方程的三个解。令k为已知两点连线的斜率，即有

$y-y'=k(x-x')⇒y=y'+k(x-x')$ 其中，$(x',y')∈\{(x_a,y_a),(x_b,y_b),(x_c,y_c)\}$。将上式代入椭圆曲线$By^2=x^3+Ax^2+x$得 $\begin{matrix} 0 & = & {x^{3} + Ax^{2} + x - By^{2}} \\ & = & {x^{3} + Ax^{2} + x - B\left( {y^{'} + k\left( {x - x^{'}} \right)} \right)^{2}} \\ & = & {x^{3} + \left( {A - Bk^{2}} \right)x^{2} + {\omega\left( x^{2} \right)}} \end{matrix}$ 其中，$ω⁡(x^2)$表示多项式中次数小于$2$的项。此外对于任意一元三次方程$ax^3+bx^2+cx+d=0$的三个解，其满足 $x_{1} + x_{2} + x_{3} = - \frac{b}{a}$ 进而，对于上述联立获得的三次方程有 $x_a+x_b+x_c=Bk^2-A⇒x_c=Bk^2-A-x_a-x_b$ 首先，对于1的情况。记$k_+$和$k_-$分别为$(P,Q)$和$(P,-Q)$的斜率，有 $\left. \left\{ \begin{matrix} {k_{+}^{2} = \frac{\left( {y_{2} - y_{1}} \right)^{2}}{\left( {x_{2} - x_{1}} \right)^{2}}} \\ {k_{-}^{2} = \frac{\left( {y_{2} + y_{1}} \right)^{2}}{\left( {x_{2} - x_{1}} \right)^{2}}} \end{matrix} \right.\Rightarrow\left\{ \begin{matrix} {x_{+} = \frac{B\left( {y_{2} - y_{1}} \right)^{2}}{\left( {x_{2} - x_{1}} \right)^{2}} - x_{1} - x_{2} - A} \\ {x_{-} = \frac{B\left( {y_{2} + y_{1}} \right)^{2}}{\left( {x_{2} - x_{1}} \right)^{2}} - x_{1} - x_{2} - A} \end{matrix} \right.\Rightarrow\left\{ \begin{array}{l} {x_{+}\left( {x_{2} - x_{1}} \right)^{2} = B\left( {y_{2} - y_{1}} \right)^{2} - \left( {x_{1} + x_{2} + A} \right)\left( {x_{2} - x_{1}} \right)^{2} = \frac{B\left( {x_{2}y_{1} - x_{1}y_{2}} \right)^{2}}{x_{1}x_{2}}} \\ {x_{-}\left( {x_{2} - x_{1}} \right)^{2} = B\left( {y_{2} + y_{1}} \right)^{2} - \left( {x_{1} + x_{2} + A} \right)\left( {x_{2} - x_{1}} \right)^{2} = \frac{B\left( {x_{2}y_{1} + x_{1}y_{2}} \right)^{2}}{x_{1}x_{2}}} \end{array} \right. \right.$ 进而有 $\begin{matrix} {x_{+}x_{-}\left( {x_{1} - x_{2}} \right)^{2}} & = & \frac{B^{2}\left( {x_{2}y_{1} - x_{1}y_{2}} \right)^{2}\left( {x_{2}y_{1} + x_{1}y_{2}} \right)^{2}}{x_{1}^{2}x_{2}^{2}\left( {x_{1} - x_{2}} \right)^{2}} \\ & = & \frac{B^{2}\left( {x_{2}^{2}y_{1}^{2} - x_{1}^{2}y_{2}^{2}} \right)^{2}}{x_{1}^{2}x_{2}^{2}\left( {x_{1} - x_{2}} \right)^{2}} \\ & = & \frac{\left( {x_{2}^{2}\left( {x_{1}^{3} + Ax_{1}^{2} + x_{1}} \right) - x_{1}^{2}\left( {x_{2}^{3} + Ax_{2}^{2} + x_{2}} \right)} \right)^{2}}{x_{1}^{2}x_{2}^{2}\left( {x_{1} - x_{2}} \right)^{2}} \\ & = & \frac{\left( {x_{2}\left( {x_{1}^{2} + Ax_{1} + 1} \right) - x_{1}\left( {x_{2}^{2} + Ax_{2} + 1} \right)} \right)^{2}}{\left( {x_{1} - x_{2}} \right)^{2}} \\ & = & \frac{\left( {x_{2}x_{1}^{2} - x_{1}x_{2}^{2} + x_{2} - x_{1}} \right)^{2}}{\left( {x_{1} - x_{2}} \right)^{2}} \\ & = & \frac{\left( {x_{1} - x_{2}} \right)^{2}\left( {x_{1}x_{2} - 1} \right)^{2}}{\left( {x_{1} - x_{2}} \right)^{2}} \\ & = & \left( {x_{1}x_{2} - 1} \right)^{2} \end{matrix}$ 即计算验证情况1成立。其次，对于2的情况。记$k_+$为点$P$处椭圆曲线的斜率，有 $k_+=(3x_1^2+2Ax_1+1)/(2By_1)⇒k_+^2=(3x_1^2+2Ax_1+1)^2/(4B^2 y_1^2)=(3x_1^2+2Ax_1+1)^2/4B(x_1^3+Ax_1^2+x_1)$ 进而，有 $\begin{matrix} & {x_{+} = Bk_{+}^{2} - 2x_{1} - A} \\ \Rightarrow & \begin{matrix} {4x_{+}\left( {x_{1}^{3} + Ax_{1}^{2} + x_{1}} \right)} & = & {\left( {3x_{1}^{2} + 2Ax_{1} + 1} \right)^{2} - 4\left( {2x_{1} + A} \right)\left( {x_{1}^{3} + Ax_{1}^{2} + x_{1}} \right)} \\ & = & {9x_{1}^{4} + 12Ax_{1}^{3} + \left( {6 + 4A^{2}} \right)x_{1}^{2} + 4Ax_{1} + 1 -} \\ & & {8x_{1}^{4} - 12Ax_{1}^{3} - \left( {8 + 4A^{2}} \right)x_{1}^{2} - 4Ax_{1}} \\ & = & {x_{1}^{4} - 2x_{1}^{2} + 1} \\ & = & \left( {x_{1}^{2} - 1} \right)^{2} \end{matrix} \end{matrix}$ 即计算验证情况2成立。证毕。

6 Montgomery‘s double-and-add formulas
对Curve25519的迭代运算(忽略cswap部分)可以表示为如下的两幅图。其中，其中第一幅图表示了迭代运算中的运算规则，第二幅图表示了每部运算所得到值的对应表达式。由图可知，每次迭代运算包含了10次乘法运算与8次加法运算，迭代次数为$\mbox{MAX}⁡(⌈log_2⁡k⌉)=255$，即去除固定比特的密钥长度。
注：在Montgomery的87年文中，给出的乘法运算为11次，但在计算过程以及复杂度上并无区别，仅为计数差异。

此处计算基础即为上节给出的关于Montgomery Curve伪运算的两个等式，但出于计算的考虑需要将其表达为有理数的形式，即对于$nP$的$x$坐标有$X_n⁄Z_n$。类似地，有$X_(m-n)⁄Z_(m-n)$、$X_m⁄Z_m$，进而$(X_{m+n}:Z_{m+n})$可由如下公式计算获得：

当mP≠nP时$X_{m+n}←Z_{m-n}(X_mX_n-Z_mZ_n)^2，Z_{m+n}←X_{m-n}(X_mZ_n-X_mZ_n)^2$
当m=n时$X_{2n}←(X_n^2-Z_n^2)^2，Z_2n←4X_nZ_n(X_n^2+AX_nZ_n+Z_n^2)^2$
注：此处对于Curve25519而言，有$Z_{m-n}=1$，$A=486662$，$(A-2)⁄4=121665$，此外有$X_1=9$，$Z_1=1$(基点G)，$X_0=1$，$Z_0=0$(无穷远点∞)，$X_{m-n}=9$(计算常量)。

记$P=nG=(x_2,z_2)$，$Q=mG=(x_3,z_3)$，有$|m-n|=1$。对于每次迭代计算，若$\mbox{swap}=0$即不发生交换时，有$P'=2nG=(\mbox{x_2}',\mbox{z_2}')$，$Q'=(m+n)G=(\mbox{x_3}',\mbox{z_3}')$；若$\mbox{swap}=1$即发生交换时，有$P'=2mG=(\mbox{x_2}',\mbox{z_2}')$，$Q'=(m+n)G=(\mbox{x_3}',\mbox{z_3}')$。最终，若$\mbox{swap}=1$则进行最后交换，并取$\mbox{x_2}⋅\mbox{z_2}^{p-2}$。
注：考虑Curve25519函数最后给出的为$kG$的$x$坐标，其中$k$为标量即私钥，那么坐标对应的比值形式即为$\mbox{x_2}⁄\mbox{z_2}=\mbox{x_2}⋅\mbox{z_2}^{-1}$。考虑费马小定理，有$\mbox{z_2}^{p-1}≡1 \pmod{p}$，因此$\mbox{x_2}⁄\mbox{z_2}≡\mbox{x_2}⋅\mbox{z_2}^{p-2}\pmod{p}$。

例：计算202G。
记$u_k$为$kG$的$x$轴坐标，其中$k∈\{1,…,202\}$，特别地，无穷远点记为$0G$，记$u_l^i$和$u_r^i$分别为第$i$轮迭代输出$(\mbox{x_2}',\mbox{z_2}')$和$(\mbox{x_3}',\mbox{z_3}')$对应的$x$轴坐标，即第$i$轮输出可记为$(u_l^i,u_r^i)$，其中$i∈\{1,…,8\}$。特别地，对于第一轮的输入有$(u_l^0,u_r^0)=(0G,1G)$。记$S_0$为计算$\mbox{swap ^= k_t}$获得的值，$(c_l^i,c_r^i)$为计算$\mbox{cswap}$后获得的值，$S_1$为计算$\mbox{swap = k_t}$获得的值。(计算代码请参阅本文1.3节，此外注意有$202=\mbox{0B}11001010$。)
第1轮：
首先取$\mbox{k}$的左端第一个bit为1，得$S_0=1$。所以$\mbox{cswap}$函数发生交换，得$(c_l^1,c_r^1)=(1G,0G)$，$S_1=1$。然后进行迭代的主体运算，得$(u_l^1,u_r^1)=(2G,1G)$。
第2轮：
首先取$\mbox{k}$的左端第二个bit为1，得$S_0=0$。所以$\mbox{cswap}$函数不做交换，得$(c_l^2,c_r^2)=(2G,1G)$，$S_1=1$。然后进行迭代的主体运算，得$(u_l^2,u_r^2)=(4G,3G)$。
第3轮：
首先取$\mbox{k}$的左端第三个bit为0，得$S_0=1$。所以$\mbox{cswap}$函数进行交换，得$(c_l^3,c_r^3 )=(3G,4G)$，$S_1=0$。然后进行迭代的主体运算，得$(u_l^3,u_r^3)=(6G,7G)$。
第4轮：
首先取$\mbox{k}$的左端第四个bit为0，得$S_0=0$。所以$\mbox{cswap}$函数不做交换，得$(c_l^4,c_r^4 )=(6G,7G)$，$S_1=0$。然后进行迭代的主体运算，得$(u_l^4,u_r^4)=(12G,13G)$。
第5轮：
首先取$\mbox{k}$的左端第五个bit为1，得$S_0=1$。所以$\mbox{cswap}$函数进行交换，得$(c_l^5,c_r^5 )=(13G,12G)$，$S_1=1$。然后进行迭代的主体运算，得$(u_l^5,u_r^5 )=(26G,25G)$。
第6轮：
首先取$\mbox{k}$的左端第六个bit为0，得$S_0=1$。所以$\mbox{cswap}$函数进行交换，得$(c_l^6,c_r^6 )=(25G,26G)$，$S_1=0$。然后进行迭代的主体运算，得$(u_l^6,u_r^6 )=(50G,51G)$。
第7轮：
首先取$\mbox{k}$的左端第七个bit为1，得$S_0=1$。所以$\mbox{cswap}$函数进行交换，得$(c_l^7,c_r^7 )=(51G,50G)$，$S_1=1$。然后进行迭代的主体运算，得$(u_l^7,u_r^7 )=(102G,101G)$。
第8轮：
首先取$\mbox{k}$的左端第八个bit为0，得$S_0=1$。所以$\mbox{cswap}$函数进行交换，得$(c_l^8,c_r^8 )=(101G,102G)$，$S_1=0$。然后进行迭代的主体运算，得$(u_l^8,u_r^8 )=(202G,203G)$。
输出：
此时有$S_1=0$，所以输出阶段$\mbox{cswap}$函数不做交换，输出$u_l^8=202G$。

7 威尔逊定理(Wilson’s Theorem)
对于任意素数$p$，有$(p-1)!≡-1 \pmod{p}$。
证明：
当$p=2$时，显然成立。
当$p≥3$时，对于任意$a∈\mathbb{F}_p\backslash\{1,p-1\}$存在$a^{-1}∈\mathbb{F}_p\backslash\{1,p-1\}$且$a≠a^{-1}$。故

$(p-1)!=(p-2)!⋅(p-1)≡1⋅-1 \pmod{p}≡-1 \pmod{p}$
证毕。

8 欧拉准则(Euler’s Criterion)
对奇素数$p$和满足$\mbox{gcd}⁡(a,p)=1$的整数a，

$a^{\frac{p - 1}{2}} \equiv \left\{ \begin{array}{rr} {1~\left( {\text{mod}~p} \right)} & {\left( {\exists x \in \mathbb{F}_{p}} \right),~a \equiv x^{2}~\left( {\text{mod}~p} \right)} \\ {- 1~\left( {\text{mod}~p} \right)} & {\left( {\forall x \in \mathbb{F}_{p}} \right),~a ≢ x^{2}~\left( {\text{mod}~p} \right)} \end{array} \right.$
即对上述的$p$和$a$，

$a$是$p$的二次剩余当且仅当$a^{\frac{p-1}{2}}≡1 \pmod{p}$。
$a$是$p$的二次非剩余当且仅当$a^{\frac{p-1}{2}}≡-1 \pmod{p}$。

证明：
对于上述结论1：

充分性：由于$a$是$p$的二次剩余，则存在$x$使$a≡x^2 \pmod{p}$成立，进而$a^{\frac{p-1}{2}}=x^{p-1}$。又因欧拉定理，有$a^{\frac{p-1}{2}}=x^{p-1}≡1 \pmod{p}$。
必要性：由原根存在定理，设$g$为模$p$的一个原根且$a≡g^k \pmod{p}$，从而有$a^{\frac{p-1}{2}}=g^{\frac{k}{2}(p-1)}≡1 \pmod{p}$。又因欧拉定理，有$g^{p-1}≡1 \pmod{p}$，进而有$(p-1)│\frac{k}{2}(p-1)$，即$k$为偶数。令$x≡g^{\frac{k}{2}} \pmod{p}$，有$x^2≡g^k≡a \pmod{p}$。

对于上述结论2：
由费马小定理可知$a^{p-1}≡1 \pmod{p}$，从而$(a^{\frac{p-1}{2}}-1)(a^{\frac{p-1}{2}}+1)≡0 \pmod{p}$，故$a^{\frac{p-1}{2}}≡±1 \pmod{p}$，即$a^{\frac{p-1}{2}}$在模$p$下有且仅有$1$和$-1$两个结果。又由上述过程得知“$a$是$p$的二次剩余当且仅当$a^{\frac{p-1}{2}}≡1 \pmod{p}$”，故有“$a$是$p$的二次非剩余当且仅当$a^{\frac{p-1}{2}}≡-1 \pmod{p}$”。
证毕。

9 二次剩余的个数
设$p$为奇素数，则模$p$运算下的二次剩余与二次非剩余均有$\frac{p-1}{2}$个。
证明：
设$a,b∈\mathbb{N}^+$且$a+b≡0 \pmod{p}$，则有$a^2≡b^2 \pmod{p}$，因此二次剩余的个数不超过$\frac{p-1}{2}$个。设$1≤i,j≤\frac{p-1}{2}$且$i≠j$，若有$i^2≡j^2 \pmod{p}$成立，则

$i^2-j^2≡(i+j)(i-j)≡0 \pmod{p}$ 即存在$p│(i+j)(i-j)$。又因$1≤i,j≤\frac{p-1}{2}$且$i≠j$，显然$p│(i+j)$与$p│(i-j)$均不成立，进而对于任意$1≤i,j≤\frac{p-1}{2}$且$i≠j$均有$i^2≢j^2 \pmod{p}$。

综上，模$p$运算的二次剩余与二次非剩余均有$\frac{p-2}{2}$个。
证毕。

参考
RFC 7748
Bernstein, D., "Curve25519: new Diffie-Hellman speed records", 2006, http://www.iacr.org/cryptodb/archive/2006/PKC/3351/3351.pdf.
Montgomery, P., "Speeding the Pollard and Elliptic Curve Methods of Factorization", January 1987, http://www.ams.org/journals/mcom/1987-48-177/S0025-5718-1987-0866113-7/S0025-5718-1987-0866113-7.pdf.
Ed25519与Curve25519：概念与相互转换 - 知乎 (zhihu.com)
辅因子（cofactor）解释：揭开椭圆曲线不为人知的秘密 - 知乎 (zhihu.com)
模平方剩余(二次剩余)与欧拉判别法_模5的平方剩余-CSDN博客
 威尔逊定理 - OI Wiki (oi-wiki.org)
抽象代数|笔记整理（A）——二次扩域，有限域，分裂域 - 知乎 (zhihu.com)
「学习笔记」二次剩余 - Aestas16's Blog (cnblogs.com)
初等数论(八): 二次剩余 - 知乎 (zhihu.com)

标签：mathbb,right,sqrt,Curve25519,mbox,left
From： https://www.cnblogs.com/miro-cnblogs/p/18467812

相关文章

赞助商

阅读排行