Elliptic Curve Cryptography (ECC)

前面我们已经展示过几个椭圆曲线的图像，但点与点之间好像没有什么联系。我们能不能建立一个类似于在实数轴上加法的运算法则呢？数学家们定义了一个这样的运算法则。

椭圆曲线上两个点“加法”算法的定义： 任意取椭圆曲线上两点 \(P\) 和 \(Q\) （若 \(P\) 和 \(Q\) 两点重合，则做 \(P\) 点的切线）做直线交于椭圆曲线的另一点 \(R'\) ，过 \(R'\) 做 \(y\) 轴的平行线交于 \(R\) 。我们定义点 \(R\) 就是点 \(P\) 和 \(Q\) 相加的结果，记为： \(P+Q=R\) 。

椭圆曲线上两个点加法运算的例子如图 2 和 3 所示。

注 1：我们称 \(y\) 轴的平行线与椭圆曲线的两个交点互为“负元”，图 2 和 3 的例子中 \(-R=R'\) 。
注 2： \(k\) 个相同的点 \(P\) 相加，我们记作 \(kP\) ，如图 3 例子中有 \(R=2P\) ，再如图 4 例子中有 \(P+P+P=2P+P=3P\) 。

前面介绍了椭圆曲线上加法运算的定义，这节介绍它的计算公式。需要注意的是椭圆曲线上的加法不是实数中普通的加法，而是从普通加法中抽象出来的加法，他具备普通加法的一些性质，但其运算规则显然与普通加法不同。

设有椭圆曲线 \(y^2 = x^3 + ax + b\) ，点 \(P=(x_P,y_P)\) 和 \(Q=(x_Q,y_Q)\) 是椭圆曲线上的两点，求 \(P+Q\) 。

把点 \(P+Q\) 记为 \(R=(x_R,y_R)\) ，当点 \(P\) 和点 \(Q\) 是不同点时（不考虑 \(x_P = x_Q\) 的特殊情况），记斜率 \(m=\frac{y_P - y_Q}{x_P - x_Q}\) ，过这两点直线为：
\[y=m (x - x_Q) + y_Q\]
由椭圆曲线上加法运算的定义知， \(P=(x_P,y_P),Q=(x_Q,y_Q),-R=R'=(x_R, -y_R)\) 三点共线，从而这三点的坐标满足下面方程组：
\[\begin{cases} y^2 = x^3 + ax + b \\ y=m (x - x_Q) + y_Q \\ \end{cases}\]
求解方程组可得 \(R\) 的坐标为：
\[\begin{cases} x_R & = m^2 - x_P - x_Q \\ y_R & = - m (x_R - x_P) - y_P \\ \end{cases}\]
当点 \(P\) 和点 \(Q\) 是同一点时，按照定义，我们需要先求过 \(P\) 点的切线，再求切线与椭圆曲线联立方程组求得交点 \(-R=R'=(x_R, -y_R)\) ，详细过程省略，这里直接给出结论：很巧的是，它也可以化为上面的形式（即和点 \(P,Q\) 是不同点的形式相同），不过此时式中的 \(m = \frac{3 x^2_P + a}{2y_P}\) 。

总结，椭圆曲线 \(y^2 = x^3 + ax + b\) 上加法运算 \((x_R,y_R) = (x_P,y_P) + (x_Q,y_Q)\) 的计算公式：
\[\begin{cases} x_R & = m^2 - x_P - x_Q \\ y_R & = - m (x_R - x_P) - y_P \\ \end{cases}\]
上式中，当点 \(P\) 和点 \(Q\) 是不同点时 \(m=\frac{y_P - y_Q}{x_P - x_Q}\) ，当点 \(P\) 和点 \(Q\) 是同一点时 \(m = \frac{3 x^2_P + a}{2y_P}\) 。

在近世代数中，“群”是集合再加上集合上一个二元运算（比如加法）满足下面条件后组成的代数结构：

1. 封闭性： \(\forall a_1, a_2 \in A, \; a_1 + a_2 \in A\)
   
2. 结合律： \(\forall a_1, a_2, a_3 \in A, \; (a_1 + a_2) + a_3 = a_1 + ( a_2 + a_3)\)
   
3. 具有单位元： \(\exists e \in A, \; s.t. \; \forall a \in A, \; e + a = a + e = a\)
   
4. 都有逆元素： \(\forall a \in A, \; \exists a^{-1} \in A, \; s.t. \; a + a^{-1} = e\)
   

把上一节中椭圆曲线所对应的离散点作为群的集合，仿照实数域椭圆曲线加法运算的定义（参见节 1.1 ），我们把群上的二元运算记为 \(+\) ，设 \(P=(x_P, y_P), Q=(x_Q, y_Q)\) ，把 \(R = P + Q\) 定义为：
\[\begin{aligned} x_R &= m^2 - x_P - x_Q \pmod p \\ y_R &= -m (x_R - x_P ) - y_P \pmod p \\ \end{aligned}\]
当 \(P \neq Q\) 时， \(m = \frac{y_P - y_Q}{x_P - x_Q} \pmod p\) ；当 \(P=Q\) 时， \(m = \frac{3 x_P^2 + a}{2 x_P} \pmod p\) 。

设 \(P,Q\) 在椭圆曲线上，按上面定义计算的点 \(P+Q\) 一定也在椭圆曲线上（即“封闭性”） ，为什么会这样呢？这里不证明，有兴趣的话可参考 An Elementary Proof Of The Group Law For Elliptic Curves（文章中也有关于“结合律”的证明）。我们通过一个具体的例子来验证一下“封闭性”。设椭圆曲线 \(y^2 \equiv x^3 − x \pmod {61}\) （参考图 7 ），易知点 \(P=(4,11), Q=(8,4)\) 都在椭圆曲线，通过上面的加法定义公式可求得 \(P+Q=(33, 55)\) ，容易验证点 \((33, 55)\) 确实也在椭圆曲线上。不仅如此，椭圆曲线上任意两点相加的结果都会在椭圆曲线上。

现在考察椭圆曲线上是否具有“单位元”，即是否存在点 \(\mathcal{O}\) （单位元）使所有点都满足：
\[P + \mathcal{O} = P\]
事实上， 椭圆曲线满足上面条件的点 \(\mathcal{O}\) 是不存在的。为了满足群定义，我们将一个抽象的无穷点 \((x, \infty)\) 定义为单位元 \(\mathcal{O}\) ，这个无穷点可以看作是位于 \(y\) 轴正半轴的无穷远处，或 \(y\) 轴负半轴的无穷远处。

现在考察椭圆曲线上每个点是否都有“逆元素”，即对每一个点 \(P\) ，是否可以找到 \(-P\) 满足：
\[P + (-P) = \mathcal{O}\]
答案是肯定的， \(-P\) 可以这样定义（可以证明它一定存在于椭圆曲线上）：
\[-P = (x_P, - y_P \bmod p)\]
比如，按上面公式可求椭圆曲线 \(y^2 \equiv x^3 − x \pmod {61}\) 上的点 \((4, 11)\) 的逆元素为 \((4, 50)\) ，容易验证它确实也在椭圆曲线上。

有限素域 \(\mathbb{F}_{p}\) 上的椭圆曲线记为 \(E(\mathbb{F}_{p})\) ，它由下面这些点组成： \[E(\mathbb{F}_{p}) = \{(x, y): x,y \in \mathbb{F}_{p} \;\text{satisfy}\; y^2 = x^3 + ax + b \} \cup \{ \mathcal{O} \}\]

本文中，还采用类似 \(y^2 \equiv x^3 − x \pmod {61}\) 的记号表示有限素域 \(\mathbb{F}_{61}\) 上的椭圆曲线 \(y^2 = x^3 − x\) 。

椭圆曲线，如 \(y^2 \equiv x^3 − x \pmod {61}\) 上（包含 \(\mathcal{O}\) ）有多少个点呢（注：群中元素个数又称为群的阶）？这里素数 \(p\) 比较小，我们把 \(x\) 从 \(0\) 到 \(p-1\) 遍历一次，每个 \(x\) 看是否可以求出合法的 \(y\) 也满足 \(y \in \{0, 1, \cdots, p-1\}\) ，即可统计出所有满足要求的点。当 \(x\) 固定时最多有 2 个 \(y\) ，再加上一个额外的 \(\mathcal{O}\) ，所以我们知道 \(\mathbb{F}_{p}\) 上的椭圆曲线的点的数量肯定不会超过 \(2p+1\) 。这种方法当素数 \(p\) 很大时效率很慢，可以用 Schoof's algorithm 快速计算椭圆曲线上点的个数。

对于有限素域 \(\mathbb{F}_{p}\) 上的椭圆曲线，其点的个数记为 \(\#E(\mathbb{F}_{p})\) 。

我们定义下面记号：
\[nP = \underbrace{P + P + \cdots + P}_{n \text{ times}}\]
定义 \(0P = \mathcal{O}\) 。以 \(y^2 \equiv x^3 + 2x + 3 \pmod {97}\) 为例，取 \(P=(3,6)\) ，我们计算一下 \(P, 2P, 3P, 4P, 5P, 6P \cdots\) ，由群的“封闭性”可知，它们都属于椭圆曲线所在“群”。
\[\begin{aligned} 0P &= \mathcal{O} \\ 1P &= (3, 6) \\ 2P &= (80, 10) \\ 3P &= (80, 87) \\ 4P &= (3, 91) \\ 5P &= \mathcal{O} \\ 6P &= (3, 6) \\ 7P &= (80, 10) \\ 8P &= (80, 87) \\ 8P &= (3, 91) \\ 10P &= \mathcal{O} \\ \cdots \\ \end{aligned}\]
我们可以发现， \(P\) 的倍数只有 5 个点，而椭圆曲线上其他的点没有出现在 \(P\) 的倍数中。

可以证明 \(\mathcal{O}, (3, 6), (80, 10), (80, 87), (3, 91)\) 在椭圆曲线群所定义的加法运算下也构成群，它称为椭圆曲线群的“子群”，由于这个子群的每个元素可通过对 \(P=(3, 6)\) 重复进行群运算而生成，所以这个子群又称为“循环子群”，其中 \(P\) 称为循环子群的 Base Point（或者 Generator）。

在椭圆曲线的循环子群中（设循环子群的阶为 \(n\) ），考虑式子 \(Q=kP\) ，对于给定的 \(k\) 和 \(P\) 计算 \(Q\) 相对容易（可以使用 Double-and-add 算法）；而如果已知点 \(P\) 和 \(Q\) ，求 \(k\) 则比较困难（当然我们并不能证明它很“难”，只是说目前没有找到有效的算法来计算上式中的 \(k\) ），这个问题称为椭圆曲线离散对数问题（Elliptic-Curve Discrete-Logarithm Problem, ECDLP）。

如果要暴力求解 \(k\) 的话，你需要设 \(k=1,2,\cdots,n\) ，对于每一个 \(k\) 直接使用加法计算公式验证其是否满足 \(Q = \underbrace{P + P + \cdots + P}_{k \text{ times}}\) ，当 \(n\) 非常大时，暴力求解没有应用价值。

注：在 Digital Signature Algorithm（DSA）或者 Diffie-Hellman Key Exchange 算法中，我们也会说到“离散对数问题”，它指的是另一个问题： \(k\) 和 \(y\) 满足 \(y \equiv g^k \pmod p\) ，其中 \(g,p\) 是参数，已知 \(y\) 时请问 \(k\) 是多少？这个问题也很“难”（目前没有找到有效算法），这里不介绍。

使用基于椭圆曲线的密码学算法时，各个参与方首先需要约定好椭圆曲线的各个参数，它们被称为 Domain Parameters。

下面是 ECC 的 Domain Parameters：

• The prime \(p\) that specifies the size of the finite field.（注： \(p\) 一般取很大的素数）
  
• The coefficients \(a\) and \(b\) of the elliptic curve equation. 到此，我们可以确定椭圆曲线群 \(E(\mathbb{F}_{p})\) 了，参见节 2.2
  
• The base point (generator) \(G=(x_G, y_G)\) that generates our subgroup. 有了 Generator 后，我们可以确定 \(E(\mathbb{F}_{p})\) 上的一个循环子群了，参见节 2.4
  
• The order \(n\) of the subgroup. \(n\) 就是上一步得到的循环子群的元素个数
  
• The cofactor \(h=N/n\) of the subgroup. 这里 \(N=\#E(\mathbb{F}_{p})\) ，即 \(N\) 是椭圆曲线群 \(E(\mathbb{F}_{p})\) 所包含的所有点的个数，由拉格朗日定理（参见节 2.4.2）可知， \(h\) 一定是一个整数。显然，当 \(h=1\) 时，由 \(G\) 确定的椭圆曲线的所有点就是椭圆曲线群 \(E(\mathbb{F}_{p})\) 本身，比如曲线 Secp256k1 的 \(h\) 就是 1。曲线 Curve25519 的 cofactor \(h=8\) ，所以它的 Generator 得到的循环子群的元素个数是椭圆曲线群 \(E(\mathbb{F}_{p})\) 元素个数的 \(1/8\) 。需要说明的是，当 \(h>1\) 时，有一些安全问题需要注意：比如可能遭受 Small-Subgroup Attack，还可能存在 Non-injective behavior/Covert channels/Implementation-defined behavior/Nontrivial modifications 等问题，具体可参考：Decaf: Eliminating cofactors through point compression, 1.1 Pitfalls of a cofactor。区块链 Monero 上出现过由于 \(Cofactor>1\) 而引起的安全漏洞，参考：Disclosure of a Major Bug in CryptoNote Based Currencies
  

一般使用 \((p, a, b, G, n, h)\) 表示 ECC 的 Domain Parameters。需要说明的是： 当 \(p,a,b,G\) 确定后， \(n\) 和 \(h\) 也就确定了，也就是说 \(n,h\) 是由 \(p,a,b,G\) 计算出来的参数。

下面介绍使用椭圆曲线进行密钥交换（Key Exchange）的过程，它是 Diffie-Hellman algorithm 算法的变种，一般称为 Elliptic curve Diffie-Hellman (ECDH)。

Alice 和 Bob 想进行通信，为了加密（基于效率考虑往往会采用对称密钥算法，如 AES 等）通信的数据，他们需要约定同一个密钥（称为“Shared Secret”）。

使用 ECDH 算法约定“Shared Secret”的过程（和 Diffie-Hellman 密钥交换算法基本类似）如下。

第一步，选择一个椭圆曲线（即确定 Domain parameters），你可以从 Standards for Efficient Cryptography, SEC 2: Recommended Elliptic Curve Domain Parameters 中选择一个推荐的参数。

第二步，为 Alice 和 Bob 分别生成 private key/public key。比如，Alice 生成 private key/public key 的过程如下：
1、从 \(\{1, 2, \cdots, n - 1\}\) （ \(n\) 在 Domain parameters 中指定的循环子群的阶）中随机选择一个数 \(d_A\) 作为 private key。
2、计算 \(Q_A=d_A G\) （ \(G\) 是 Domain parameters 中的 Base Point）， \(Q_A\) 就是 public key。（注：这就是由私钥生成公钥的过程，直接按多次加法求解比较慢，可采用 Double-and-add 算法进行优化。这里有一个使用 Double-and-add 算法计算公钥的例子：https://bitcoin.stackexchange.com/questions/25024/how-do-you-get-a-bitcoin-public-key-from-a-private-key）
类似的过程，Bob 生成一个 private key/public key，分别记为 \(d_B, Q_B\) ，有 \(Q_B=d_B G\) 。

第三步，Alice 和 Bob 分别把自己的公钥传送给对方，传递过程被别人偷看也没关系，由公钥无法容易地计算出私钥。

第四步， Alice 用自己的私钥和 Bob 的公钥计算 \(Secret_1=d_A Q_B\) ，同样地，Bob 用自己的私钥和 Alice 的公钥计算 \(Secret_2=d_B Q_A\) ，由于 \(Secret_1 = Secret_2\) （因为 \(d_A Q_B = d_A (d_B G) = d_B (d_A G) = d_B Q_A\) ），所以它可作为“Shared Secret”。

在椭圆曲线中，私钥 \(d \in \{1, 2, \cdots, n - 1\}\) 是整数；而公钥 \(Q =d G\) 则是椭圆曲线上的一个“点”，它有 \(x_Q, y_Q\) 两个坐标，每个坐标都是整数。下面是 secp256k1 曲线上公钥的一个例子：
\[\begin{aligned} x_Q &= \texttt{0x50863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B2352} \\ y_Q &= \texttt{0x2CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6} \\ \end{aligned}\]

我们容易验证这个公钥确实是 secp256k1 曲线上的一个点：

Python 3.6.8 (default, Oct  7 2019, 12:59:55)
[GCC 8.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
>>> x = 0x50863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B2352
>>> y = 0x2CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6
>>> y**2 % p - (x**3 + 7) % p
0

一般地，我们往往用“一个数”来表达椭圆曲线中的公钥，如何用一个数来表达两个坐标呢？有两种方案：“Uncompressed format”和“Compressed format”（Compressed format 有 ansiX962_compressed_prime 和 ansiX962_compressed_char2 标准，这里不介绍它们）。

下面介绍一下“Uncompressed format”，它的规则很简单，把 \(x_Q\) 和 \(y_Q\) 直接连接在一起，再在前面加个 0x04 前缀即可。例如有：
\[\begin{aligned} x_Q &= \texttt{0x50863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B2352} \\ y_Q &= \texttt{0x2CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6} \\ \end{aligned}\]
则公钥（十六进制）可表示为：

Q = 0450863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B23522CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6

参考：https://stackoverflow.com/questions/6665353/is-there-a-standardized-fixed-length-encoding-for-ec-public-keys

前面介绍了使用椭圆曲线进行密钥交换（Key Exchange）的过程，这里将介绍如何使用椭圆曲线进行数字签名，简称 ECDSA。ECDSA 是椭圆曲线应用于 DSA 的成果，其基本思路和 DSA 很相似。

数字签名的场景为：Alice 用他的私钥 \(d_A\) 对消息进行签名，而其它人（如 Bob）可以使用 Alice 的公钥 \(Q_A\) 来验证这个消息确实是 Alice 发送的。

下面是 ECDSA 的 Python 实现（注：pip 上已有现成的库 ecdsa）：

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# 代码摘自：https://github.com/andreacorbellini/ecc/blob/master/scripts/ecdsa.py

import collections
import hashlib
import random

EllipticCurve = collections.namedtuple('EllipticCurve', 'name p a b g n h')

curve = EllipticCurve(
    'secp256k1',
    # Field characteristic.
    p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f,
    # Curve coefficients.
    a=0,
    b=7,
    # Base point.
    g=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
       0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8),
    # Subgroup order.
    n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141,
    # Subgroup cofactor.
    h=1,
)


# Modular arithmetic ##########################################################

def inverse_mod(k, p):
    """Returns the inverse of k modulo p.
    This function returns the only integer x such that (x * k) % p == 1.
    k must be non-zero and p must be a prime.
    """
    if k == 0:
        raise ZeroDivisionError('division by zero')

    if k < 0:
        # k ** -1 = p - (-k) ** -1  (mod p)
        return p - inverse_mod(-k, p)

    # Extended Euclidean algorithm.
    s, old_s = 0, 1
    t, old_t = 1, 0
    r, old_r = p, k

    while r != 0:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
        old_t, t = t, old_t - quotient * t

    gcd, x, y = old_r, old_s, old_t

    assert gcd == 1
    assert (k * x) % p == 1

    return x % p


# Functions that work on curve points #########################################

def is_on_curve(point):
    """Returns True if the given point lies on the elliptic curve."""
    if point is None:
        # None represents the point at infinity.
        return True

    x, y = point

    return (y * y - x * x * x - curve.a * x - curve.b) % curve.p == 0


def point_neg(point):
    """Returns -point."""
    assert is_on_curve(point)

    if point is None:
        # -0 = 0
        return None

    x, y = point
    result = (x, -y % curve.p)

    assert is_on_curve(result)

    return result


def point_add(point1, point2):
    """Returns the result of point1 + point2 according to the group law."""
    assert is_on_curve(point1)
    assert is_on_curve(point2)

    if point1 is None:
        # 0 + point2 = point2
        return point2
    if point2 is None:
        # point1 + 0 = point1
        return point1

    x1, y1 = point1
    x2, y2 = point2

    if x1 == x2 and y1 != y2:
        # point1 + (-point1) = 0
        return None

    if x1 == x2:
        # This is the case point1 == point2.
        m = (3 * x1 * x1 + curve.a) * inverse_mod(2 * y1, curve.p)
    else:
        # This is the case point1 != point2.
        m = (y1 - y2) * inverse_mod(x1 - x2, curve.p)

    x3 = m * m - x1 - x2
    y3 = y1 + m * (x3 - x1)
    result = (x3 % curve.p,
              -y3 % curve.p)

    assert is_on_curve(result)

    return result


def scalar_mult(k, point):
    """Returns k * point computed using the double and point_add algorithm."""
    assert is_on_curve(point)

    if k % curve.n == 0 or point is None:
        return None

    if k < 0:
        # k * point = -k * (-point)
        return scalar_mult(-k, point_neg(point))

    result = None
    addend = point

    while k:
        if k & 1:
            # Add.
            result = point_add(result, addend)

        # Double.
        addend = point_add(addend, addend)

        k >>= 1

    assert is_on_curve(result)

    return result


# Keypair generation and ECDSA ################################################

def make_keypair():
    """Generates a random private-public key pair."""
    private_key = random.randrange(1, curve.n)
    public_key = scalar_mult(private_key, curve.g)

    return private_key, public_key


def hash_message(message):
    """Returns the truncated SHA512 hash of the message."""
    message_hash = hashlib.sha512(message).digest()
    e = int.from_bytes(message_hash, 'big')

    # FIPS 180 says that when a hash needs to be truncated, the rightmost bits
    # should be discarded.
    z = e >> (e.bit_length() - curve.n.bit_length())

    assert z.bit_length() <= curve.n.bit_length()

    return z


def sign_message(private_key, message):
    z = hash_message(message)

    r = 0
    s = 0

    while not r or not s:
        k = random.randrange(1, curve.n)
        x, y = scalar_mult(k, curve.g)

        r = x % curve.n
        s = ((z + r * private_key) * inverse_mod(k, curve.n)) % curve.n

    return (r, s)


def verify_signature(public_key, message, signature):
    z = hash_message(message)

    r, s = signature

    w = inverse_mod(s, curve.n)
    u1 = (z * w) % curve.n
    u2 = (r * w) % curve.n

    x, y = point_add(scalar_mult(u1, curve.g),
                     scalar_mult(u2, public_key))

    if (r % curve.n) == (x % curve.n):
        return 'signature matches'
    else:
        return 'invalid signature'


print('Curve:', curve.name)

private, public = make_keypair()
print("Private key:", hex(private))
print("Public key: (0x{:x}, 0x{:x})".format(*public))

msg = b'Hello!'
signature = sign_message(private, msg)

print()
print('Message:', msg)
print('Signature: (0x{:x}, 0x{:x})'.format(*signature))
print('Verification:', verify_signature(public, msg, signature)) # 验证通过

msg = b'Hi there!'                # 使用不同的消息，会验证失败
print()
print('Message:', msg)
print('Verification:', verify_signature(public, msg, signature))

private, public = make_keypair()  # 使用不同的公钥，会验证失败

msg = b'Hello!'
print()
print('Message:', msg)
print("Public key: (0x{:x}, 0x{:x})".format(*public))
print('Verification:', verify_signature(public, msg, signature))