如何避免对Ed25519标量乘法的侧信道攻击？

Question

我是一个使用爱德华兹曲线的初学者，我正在尝试实现一个签25519签名。我有个课文上的问题。请参阅下图(在Python中)。

在标量乘法的部分，它只使用了双加法：

def point_mul(s, P):
    Q = (0, 1, 1, 0)  # Neutral element
    while s > 0:
        if s & 1:
            Q = point_add(Q, P)
        P = point_add(P, P)
        s >>= 1
    return Q

够安全吗？

为什么它不使用像x25519这样的恒定时间方法来交换DH密钥呢？X25519的标量乘法采用Montgomery阶梯进行DH密钥交换，以防止侧信道攻击。Ed25519怎么样？

在使用标量乘法时，如何防止侧信道攻击？如何修改函数？

在完成python实现之后，我将使用硬件设计来实现。有什么方法可以防止攻击吗？

Answer 1

正如RFC第8.1节所指出的，“本文档中的示例实现并不试图保持侧通道沉默”。

你不能按原样写算法。基本上，您需要始终计算点相加：

T = point_add(Q, P)
Q = select(Q, T, s & 1)
P = point_add(P, P)
s >>= 1

select函数(也称为“条件复制”)根据第三个操作数的值(更准确地说是“侧通道沉默”)选择两个操作数中的一个。这意味着您不能使用分支，而只能使用算术操作。其基本思想是计算q ^= (q ^ t) & -b，其中q和t是输入，b是select位。如果为0，q将保持不变；如果为1，则-b将等于0xFFFF...，q将设置为t。您必须小心使用正确的数据类型才能工作--尽管您将在易于处理的硬件中实现它。当然，对于涉及到的椭圆曲线点中的每一个数字的每个字，您都需要这样做。有许多例子，这是其中之一。