如何在蒙哥馬利空間中乘以 Twisted Edwards 點？

EdDSA（和 ed25519）簽名需要標量乘法。目前，我直接在 Twisted Edwards 空間中執行此操作。（程式碼可以在我的加密庫中找到。）我的研究和測試表明，在蒙哥馬利空間中進行乘法運算會快得多。這將意味著 4 個步驟：

1. 將 Twisted Edwards 點轉換為 Montgomery 空間。
2. 執行蒙哥馬利階梯。
3. 恢復 Y 座標。
4. 轉換回 Twisted Edwards 空間。

步驟 1、2 和 4 看起來很簡單（甚至很簡單）。第 3 步更複雜，但在我遵循的本文中有記錄。這是我的嘗試，不幸的是給出了錯誤的結果：

typedef i32 fe[10]
typedef struct { fe X; fe Y; fe Z; fe T; } ge;

sv ge_scalarmult(ge *p, const ge *q, const u8 scalar[32])
{
   // convert q to montgomery format
   fe x1, y1, z1, x2, z2, x3, z3, t1, t2, t3, t4;
   fe_sub(z1, q->Z, q->Y);  fe_mul(z1, z1, q->X);  fe_invert(z1, z1);
   fe_add(t1, q->Z, q->Y);
   fe_mul(x1, q->X, t1  );  fe_mul(x1, x1, z1);
   fe_mul(y1, q->Z, t1  );  fe_mul(y1, y1, z1);
   fe_1(z1); // coherence

   // montgomery scalarmult
   // The same ladder is used for x25519,
   // it comes from the ref10 implementation.
   // Field elements are modified in-place
   x25519_ladder(x1, x2, z2, x3, z3, scalar);

   // recover the y1 coordinate
   fe_mul(t1, x1, z2);  // t1 = x1 * z2
   fe_add(t2, x2, t1);  // t2 = x2 + t1
   fe_sub(t3, x2, t1);  // t3 = x2 − t1
   fe_sq (t3, t3);      // t3 = t3^2
   fe_mul(t3, t3, x3);  // t3 = t3 * x3
   fe_mul973324(t1, z2);// t1 = 2a * z2
   fe_add(t2, t2, t1);  // t2 = t2 + t1
   fe_mul(t4, x1, x2);  // t4 = x1 * x2
   fe_add(t4, t4, z2);  // t4 = t4 + z2
   fe_mul(t2, t2, t4);  // t2 = t2 * t4
   fe_mul(t1, t1, z2);  // t1 = t1 * z2
   fe_sub(t2, t2, t1);  // t2 = t2 − t1
   fe_mul(t2, t2, z3);  // t2 = t2 * z3
   fe_add(t1, y1, y1);  // t1 = y1 + y1
   fe_mul(t1, t1, z2);  // t1 = t1 * z2
   fe_mul(t1, t1, z3);  // t1 = t1 * z3
   fe_mul(x1, t1, x2);  // x1 = t1 * x2
   fe_sub(y1, t2, t3);  // y1 = t2 − t3
   fe_mul(z1, t1, z2);  // z1 = t1 * z2

   // convert back to twisted edwards
   fe_sub(t1  , x1, z1);
   fe_add(t2  , x1, z1);
   fe_mul(p->X, x1, t2);
   fe_mul(p->Y, y1, t1);
   fe_mul(p->Z, y1, t2);
   fe_mul(p->T, x1, t1);
}

有人可以告訴我我做錯了什麼嗎？

我終於從Hacker News得到了答案。我的錯誤來自轉換程式碼。我使用了 Wikipedia 中的公式，它與正確的公式略有不同。簡單地說，我錯過了乘以一個常數（具體來說，-486664 的平方根，或 6853475219497561581579357271197624642482790079785650197046958215289687604742 也可以。）

轉換為蒙哥馬利格式的正確程式碼是這樣的（注意反轉，需要確保z1 == 1，它允許更快的蒙哥馬利階梯）：

// sqrt(-486664), in 26/25 bit limbs.
fe K = { 54885894, 25242303, 55597453,  9067496, 51808079,
        33312638, 25456129, 14121551, 54921728,  3972023 };

// Actual conversion
fe x1, y1, z1, x2, z2, x3, z3, t1, t2, t3, t4;
fe_sub(z1, q->Z, q->Y);  fe_mul(z1, z1, q->X);  fe_invert(z1, z1);
fe_add(t1, q->Z, q->Y);
fe_mul(x1, q->X, t1  );  fe_mul(x1, x1, z1);
fe_mul(y1, q->Z, t1  );  fe_mul(y1, y1, z1);
fe_mul(y1, K, y1);  // missing multiplication
fe_1(z1);

（即使我們使用投影座標，蒙哥馬利階梯在假設 z1 等於 1 時會更快。這補償了反演的成本。）

轉換回 Twisted Edwards 格式的正確程式碼如下：

fe_sub(t1  , x1, z1);
fe_add(t2  , x1, z1);
fe_mul(x1  , K , x1);  // missing multiplication
fe_mul(p->X, x1, t2);
fe_mul(p->Y, y1, t1);
fe_mul(p->Z, y1, t2);
fe_mul(p->T, x1, t1);

引用自：https://crypto.stackexchange.com/questions/50057