Document inversion ladder in curve25519
[openssl.git] / crypto / ec / curve25519.c
index 3dbf4ac..a7be5b8 100644 (file)
@@ -670,60 +670,91 @@ static void fe_invert(fe out, const fe z) {
   fe t3;
   int i;
 
+  /*
+   * Compute z ** -1 = z ** (2 ** 255 - 19 - 2) with the exponent as
+   * 2 ** 255 - 21 = (2 ** 5) * (2 ** 250 - 1) + 11.
+   */
+
+  /* t0 = z ** 2 */
   fe_sq(t0, z);
-  for (i = 1; i < 1; ++i) {
-    fe_sq(t0, t0);
-  }
+
+  /* t1 = t0 ** (2 ** 2) = z ** 8 */
   fe_sq(t1, t0);
-  for (i = 1; i < 2; ++i) {
-    fe_sq(t1, t1);
-  }
+  fe_sq(t1, t1);
+
+  /* t1 = z * t1 = z ** 9 */
   fe_mul(t1, z, t1);
+  /* t0 = t0 * t1 = z ** 11 -- stash t0 away for the end. */
   fe_mul(t0, t0, t1);
+
+  /* t2 = t0 ** 2 = z ** 22 */
   fe_sq(t2, t0);
-  for (i = 1; i < 1; ++i) {
-    fe_sq(t2, t2);
-  }
+
+  /* t1 = t1 * t2 = z ** (2 ** 5 - 1) */
   fe_mul(t1, t1, t2);
+
+  /* t2 = t1 ** (2 ** 5) = z ** ((2 ** 5) * (2 ** 5 - 1)) */
   fe_sq(t2, t1);
   for (i = 1; i < 5; ++i) {
     fe_sq(t2, t2);
   }
+
+  /* t1 = t1 * t2 = z ** ((2 ** 5 + 1) * (2 ** 5 - 1)) = z ** (2 ** 10 - 1) */
   fe_mul(t1, t2, t1);
+
+  /* Continuing similarly... */
+
+  /* t2 = z ** (2 ** 20 - 1) */
   fe_sq(t2, t1);
   for (i = 1; i < 10; ++i) {
     fe_sq(t2, t2);
   }
   fe_mul(t2, t2, t1);
+
+  /* t2 = z ** (2 ** 40 - 1) */
   fe_sq(t3, t2);
   for (i = 1; i < 20; ++i) {
     fe_sq(t3, t3);
   }
   fe_mul(t2, t3, t2);
-  fe_sq(t2, t2);
-  for (i = 1; i < 10; ++i) {
+
+  /* t2 = z ** (2 ** 10) * (2 ** 40 - 1) */
+  for (i = 0; i < 10; ++i) {
     fe_sq(t2, t2);
   }
+  /* t1 = z ** (2 ** 50 - 1) */
   fe_mul(t1, t2, t1);
+
+  /* t2 = z ** (2 ** 100 - 1) */
   fe_sq(t2, t1);
   for (i = 1; i < 50; ++i) {
     fe_sq(t2, t2);
   }
   fe_mul(t2, t2, t1);
+
+  /* t2 = z ** (2 ** 200 - 1) */
   fe_sq(t3, t2);
   for (i = 1; i < 100; ++i) {
     fe_sq(t3, t3);
   }
   fe_mul(t2, t3, t2);
+
+  /* t2 = z ** ((2 ** 50) * (2 ** 200 - 1) */
   fe_sq(t2, t2);
   for (i = 1; i < 50; ++i) {
     fe_sq(t2, t2);
   }
+
+  /* t1 = z ** (2 ** 250 - 1) */
   fe_mul(t1, t2, t1);
+
+  /* t1 = z ** ((2 ** 5) * (2 ** 250 - 1)) */
   fe_sq(t1, t1);
   for (i = 1; i < 5; ++i) {
     fe_sq(t1, t1);
   }
+
+  /* Recall t0 = z ** 11; out = z ** (2 ** 255 - 21) */
   fe_mul(out, t1, t0);
 }