5. The X25519 and X448 Functions (X25519和X448函数)

"X25519" 和 "X448" 函数对上述曲线的蒙哥马利形式执行标量乘法。(这在实现Diffie-Hellman时使用。) 这些函数将标量和u坐标作为输入, 并产生u坐标作为输出。尽管函数在内部使用整数工作, 但输入和输出是32字节字符串 (对于X25519) 或56字节字符串 (对于X448), 本规范定义了它们的编码。

u坐标是底层域 GF(2^255 - 19) 或 GF(2^448 - 2^224 - 1) 的元素, 并被编码为字节数组 u, 采用小端序, 使得 u[0] + 256u[1] + 256^2u[2] + ... + 256^(n-1)*u[n-1] 与值模 p 同余, 且 u[n-1] 最小。当接收到这样的数组时, X25519 (但不是X448) 的实现必须屏蔽最后一个字节中的最高有效位。这样做是为了保持与为其他协议保留符号位的点格式的兼容性, 并增加对实现指纹识别的抵抗力。

实现必须接受非规范值, 并将它们处理为已对域素数取模的值。非规范值对于X25519是 2^255 - 19 到 2^255 - 1, 对于X448是 2^448 - 2^224 - 1 到 2^448 - 1。

以下函数用Python实现了这一点, 尽管Python代码不是为了性能或防侧信道而设计的。这里, "bits" 参数对于X25519应设置为255, 对于X448应设置为448:

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)])

标量假定为随机生成的字节。对于X25519, 为了将32个随机字节解码为整数标量, 将第一个字节的三个最低有效位和最后一个字节的最高有效位设置为零, 将最后一个字节的第二个最高有效位设置为1, 然后按小端序解码。这意味着结果整数的形式为 2^254 加上 0 到 2^251 - 1 (含) 之间的值的8倍。同样, 对于X448, 将第一个字节的两个最低有效位设置为0, 将最后一个字节的最高有效位设置为1。这意味着结果整数的形式为 2^447 加上 0 到 2^445 - 1 (含) 之间的值的4倍。

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)

def decodeScalar448(k):
    k_list = [ord(b) for b in k]
    k_list[0] &= 252
    k_list[55] |= 128
    return decodeLittleEndian(k_list, 448)

要实现 X25519(k, u) 和 X448(k, u) 函数 (其中k是标量, u是u坐标), 首先解码k和u, 然后执行以下过程, 该过程取自 [curve25519] 并基于 [montgomery] 中的公式。所有计算都在GF(p)中执行, 即它们是模p执行的。常数a24对于curve25519/X25519是 (486662 - 2) / 4 = 121665, 对于curve448/X448是 (156326 - 2) / 4 = 39081。

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))

(请注意, 这些公式与蒙哥马利的原始论文略有不同。实现可以自由使用任何正确的公式。)

最后, 将结果值编码为小端序的32或56字节。对于X25519, 未使用的最高有效位必须为零。

cswap函数应该以常数时间实现 (即独立于swap参数)。例如, 可以按如下方式完成:

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)

其中 mask(swap) 是与 x_2 和 x_3 长度相同的全1或全0字, 例如计算为 mask(swap) = 0 - swap。

5.1. Side-Channel Considerations (侧信道考虑)

X25519和X448的设计使得更容易产生快速的常数时间实现。上述过程确保对密钥的所有值执行相同的域运算序列, 从而消除了侧信道泄漏的常见来源。然而, 仅此一项并不能防止所有侧信道。重要的是, 内存访问和跳转的模式不依赖于k的任何位的值。同样重要的是, 所使用的算术不会泄露关于整数模p的信息, 例如使 bc 与 cc 区分开来。在某些架构上, 甚至原始机器指令 (如单字除法) 也可能基于其输入具有可变时序。

侧信道攻击是一个活跃的研究领域, 仍在不断产生重要的新结果。建议实现者密切关注这项研究。

5.2. Test Vectors (测试向量)

提供了两种类型的测试。第一种是每个函数的一对测试向量, 包含给定输入的预期输出。输入通常以64或112个十六进制数字给出, 需要在处理之前解码为32或56个二进制字节。

X25519:

输入标量:

a546e36bf0527c9d3b16154b82465edd62144c0ac1fc5a18506a2244ba449ac4

输入标量数值 (十进制):

31029842492115040904895560451863089656472772604678260265531221036453811406496

输入u坐标:

e6db6867583030db3594c1a424b15f7c726624ec26b3353b10a903a6d0ab1c4c

输入u坐标数值 (十进制):

34426434033919594451155107781188821651316167215306631574996226621102155684838

输出u坐标:

c3da55379de9c6908e94ea4df28d084f32eccf03491c71f754b4075577a28552

输入标量:

4b66e9d4d1b4673c5ad22691957d6af5c11b6421e0ea01d42ca4169e7918ba0d

输入标量数值 (十进制):

35156891815674817266734212754503633747128614016119564763269015315466259359304

输入u坐标:

e5210f12786811d3f4b7959d0538ae2c31dbe7106fc03c3efc4cd549c715a493

输入u坐标数值 (十进制):

8883857351183929894090759386610649319417338800022198945255395922347792736741

输出u坐标:

95cbde9476e8907d7aade45cb4b873f88b595a68799fa152e6f8f7647aac7957

X448:

输入标量:

3d262fddf9ec8e88495266fea19a34d28882acef045104d0d1aae121700a779c984c24f8cdd78fbff44943eba368f54b29259a4f1c600ad3

输入标量数值 (十进制):

599189175373896402783756016145213256157230856085026129926891459468622403380588640249457727683869421921443004045221642549886377526240828

输入u坐标:

06fce640fa3487bfda5f6cf2d5263f8aad88334cbd07437f020f08f9814dc031ddbdc38c19c6da2583fa5429db94ada18aa7a7fb4ef8a086

输入u坐标数值 (十进制):

382239910814107330116229961234899377031416365240571325148346555922438025162094455820962429142971339584360034337310079791515452463053830

输出u坐标:

ce3e4ff95a60dc6697da1db1d85e6afbdf79b50a2412d7546d5f239fe14fbaadeb445fc66a01b0779d98223961111e21766282f73dd96b6f

输入标量:

203d494428b8399352665ddca42f9de8fef600908e0d461cb021f8c538345dd77c3e4806e25f46d3315c44e0a5b4371282dd2c8d5be3095f

输入标量数值 (十进制):

633254335906970592779259481534862372382525155252028961056404001332122152890562527156973881968934311400345568203929409663925541994577184

输入u坐标:

0fbcc2f993cd56d3305b0b7d9e55d4c1a8fb5dbb52f8e9a1e9b6201b165d015894e56c4d3570bee52fe205e28a78b91cdfbde71ce8d157db

输入u坐标数值 (十进制):

622761797758325444462922068431234180649590390024811299761625153767228042600197997696167956134770744996690267634159427999832340166786063

输出u坐标:

884a02576239ff7a2f2f63b2db6a9ff37047ac13568e1e30fe63c4a7ad1b3ee3a5700df34321d62077e63633c575c1c954514e99da7c179d

第二种类型的测试向量由调用函数指定次数的结果组成。最初, 将k和u设置为以下值:

对于X25519:

0900000000000000000000000000000000000000000000000000000000000000

对于X448:

050000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

对于每次迭代, 将k设置为调用函数的结果, 将u设置为k的旧值。最终结果是保留在k中的值。

X25519:

一次迭代后:

422c8e7a6227d7bca1350b3e2bb7279f7897b87bb6854b783c60e80311ae3079

1,000次迭代后:

684cf59ba83309552800ef566f2f4d3c1c3887c49360e3875f2eb94d99532c51

1,000,000次迭代后:

7c3911e0ab2586fd864497297e575e6f3bc601c0883c30df5f4dd2d24f665424

X448:

一次迭代后:

3f482c8a9f19b01e6c46ee9711d9dc14fd4bf67af30765c2ae2b846a4d23a8cd0db897086239492caf350b51f833868b9bc2b3bca9cf4113

1,000次迭代后:

aa3b4749d55b9daf1e5b00288826c467274ce3ebbdd5c17b975e09d4af6c67cf10d087202db88286e2b79fceea3ec353ef54faa26e219f38

1,000,000次迭代后:

077f453681caca3693198420bbe515cae0002472519b3e67661a7e89cab94695c8f4bcd66e61b9b9c946da8d524de3d69bd9d9d66b997e37