)]}'
{
  "commit": "0fc57bef1821c163ac023a0aa96e4fb2a67c0d82",
  "tree": "2a9ec3484d9c94f69ae14c7f9c7d81c7795eb652",
  "parents": [
    "0f4454c07545e6f4465ad88e83fcbaa95a08d28f"
  ],
  "author": {
    "name": "James Muir",
    "email": "muir.james.a@gmail.com",
    "time": "Sun Jan 16 09:28:34 2022 -0500"
  },
  "committer": {
    "name": "Boringssl LUCI CQ",
    "email": "boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com",
    "time": "Thu Jan 27 20:02:40 2022 +0000"
  },
  "message": "Simpler square-root computation for Ed25519\n\nDescription:\nMark Wooden and Franck Rondepierre noted that the square-root-mod-p\noperations used in the EdDSA RFC (RFC 8032) can be simplified.  For\nEd25519, instead of computing u*v^3 * (u * v^7)^((p-5)/8), we can\ncompute u * (u*v)^((p-5)/8).  This saves 3 multiplications and 2\nsquarings.  For more details (including a proof), see the following\nmessage from the CFRG mailing list:\n\n  https://mailarchive.ietf.org/arch/msg/cfrg/qlKpMBqxXZYmDpXXIx6LO3Oznv4/\n\nTesting:\nBuild and run the Ed25519 tests:\n\n  mkdir build\n  cd build\n  cmake -GNinja ..\n  ninja \u0026\u0026 ./crypto/crypto_test --gtest_filter\u003d\"Ed25519Test*\"\n\nNumerical testing of the square-root computation can be done using the\nfollowing sage script:\n\n  def legendre(x,p):\n      return kronecker(x,p)\n\n  # Ed25519\n  p \u003d 2**255-19\n  # -1 is a square\n  if legendre(-1,p)\u003d\u003d1:\n      print(\"-1 is a square\")\n  # 2 is a non-square\n  if legendre(2,p)\u003d\u003d-1:\n      print(\"2 is a non-square\")\n\n  # 2 is a generator\n  # this can be checked by factoring p-1\n  # and then showing 2**((p-1)/q) !\u003d 1 (mod p)\n  # for all primes q dividing p-1.\n\n  # suppose u/v is a square.\n  # to compute one of its square roots, find x such that\n  #    x**4 \u003d\u003d (u/v)**2 .\n  # this implies\n  #    x**2 \u003d\u003d  u/v, or\n  #    x**2 \u003d\u003d -(u/v) ,\n  # which implies either x or i*x is a square-root of u/v (where i is a square root of -1).\n  # we can take x equal to u * (u*v)**((p-5)/8).\n\n  g \u003d 2\n  s \u003d p\u003e\u003e2  # s \u003d (p-1)/4\n  i \u003d power_mod(g, s, p)\n\n  t \u003d p\u003e\u003e3  # t \u003d (p-5)/8\n  COUNT \u003d 1\u003c\u003c18\n  while COUNT \u003e 0:\n      COUNT -\u003d 1\n\n      r \u003d randint(0,p-1)   # r \u003d u/v\n      v \u003d randint(1,p-1)\n      u \u003d mod(r*v,p)\n\n      # compute x \u003d u * (u*v)**((p-5)/8)\n      w \u003d mod(u*v,p)\n      x \u003d mod(u*power_mod(w, t, p), p)\n\n      # check that x**2 \u003d\u003d r, or (i*x)**2 \u003d\u003d r, or r is not a square\n      rr \u003d power_mod(x, 2, p)\n      if rr\u003d\u003dr:\n          continue\n\n      rr \u003d power_mod(mod(i*x,p), 2, p)\n      if rr\u003d\u003dr:\n          continue\n\n      if legendre(r,p) !\u003d 1:\n          continue\n\n      print(\"failure!\")\n      exit()\n\n  print(\"passed!\")\n\nChange-Id: Iaa284d3365dd8c9fa18a4584121013f05a3f4cc6\nReviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/50965\nReviewed-by: David Benjamin \u003cdavidben@google.com\u003e\nReviewed-by: Adam Langley \u003cagl@google.com\u003e\nCommit-Queue: Adam Langley \u003cagl@google.com\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "64aa1e6032f151eba58345b7ebe43711dac65c08",
      "old_mode": 33188,
      "old_path": "crypto/curve25519/curve25519.c",
      "new_id": "7cb0add474f99629ae62a5c03543ee07b01a1d42",
      "new_mode": 33188,
      "new_path": "crypto/curve25519/curve25519.c"
    }
  ]
}