You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

112 lines
2.5 KiB

  1. // Copyright 2019 The Go Authors. All rights reserved.
  2. // Copyright 2019 George Tankersley. All rights reserved.
  3. // Use of this source code is governed by a BSD-style
  4. // license that can be found in the LICENSE file.
  5. package ristretto255
  6. import (
  7. "math/big"
  8. "github.com/gtank/ristretto255/internal/radix51"
  9. )
  10. // fePow22523 sets out to z^((p-5)/8). (p-5)/8 is 2^252-3.
  11. func fePow22523(out, z *radix51.FieldElement) *radix51.FieldElement {
  12. // Refactored from golang.org/x/crypto/ed25519/internal/edwards25519.
  13. var t0, t1, t2 radix51.FieldElement
  14. t0.Square(z)
  15. for i := 1; i < 1; i++ {
  16. t0.Square(&t0)
  17. }
  18. t1.Square(&t0)
  19. for i := 1; i < 2; i++ {
  20. t1.Square(&t1)
  21. }
  22. t1.Mul(z, &t1)
  23. t0.Mul(&t0, &t1)
  24. t0.Square(&t0)
  25. for i := 1; i < 1; i++ {
  26. t0.Square(&t0)
  27. }
  28. t0.Mul(&t1, &t0)
  29. t1.Square(&t0)
  30. for i := 1; i < 5; i++ {
  31. t1.Square(&t1)
  32. }
  33. t0.Mul(&t1, &t0)
  34. t1.Square(&t0)
  35. for i := 1; i < 10; i++ {
  36. t1.Square(&t1)
  37. }
  38. t1.Mul(&t1, &t0)
  39. t2.Square(&t1)
  40. for i := 1; i < 20; i++ {
  41. t2.Square(&t2)
  42. }
  43. t1.Mul(&t2, &t1)
  44. t1.Square(&t1)
  45. for i := 1; i < 10; i++ {
  46. t1.Square(&t1)
  47. }
  48. t0.Mul(&t1, &t0)
  49. t1.Square(&t0)
  50. for i := 1; i < 50; i++ {
  51. t1.Square(&t1)
  52. }
  53. t1.Mul(&t1, &t0)
  54. t2.Square(&t1)
  55. for i := 1; i < 100; i++ {
  56. t2.Square(&t2)
  57. }
  58. t1.Mul(&t2, &t1)
  59. t1.Square(&t1)
  60. for i := 1; i < 50; i++ {
  61. t1.Square(&t1)
  62. }
  63. t0.Mul(&t1, &t0)
  64. t0.Square(&t0)
  65. for i := 1; i < 2; i++ {
  66. t0.Square(&t0)
  67. }
  68. return out.Mul(&t0, z)
  69. }
  70. // feSqrtRatio sets r to the square root of the ratio of u and v, according to
  71. // Section 3.1.3 of draft-hdevalence-cfrg-ristretto-00.
  72. func feSqrtRatio(r, u, v *radix51.FieldElement) (wasSquare int) {
  73. var a, b radix51.FieldElement
  74. v3 := a.Mul(a.Square(v), v) // v^3 = v^2 * v
  75. v7 := b.Mul(b.Square(v3), v) // v^7 = (v^3)^2 * v
  76. // r = (u * v3) * (u * v7)^((p-5)/8)
  77. uv3 := a.Mul(u, v3) // (u * v3)
  78. uv7 := b.Mul(u, v7) // (u * v7)
  79. r.Mul(uv3, fePow22523(r, uv7))
  80. check := a.Mul(v, a.Square(r)) // check = v * r^2
  81. uNeg := b.Neg(u)
  82. correctSignSqrt := check.Equal(u)
  83. flippedSignSqrt := check.Equal(uNeg)
  84. flippedSignSqrtI := check.Equal(uNeg.Mul(uNeg, sqrtM1))
  85. rPrime := b.Mul(r, sqrtM1) // r_prime = SQRT_M1 * r
  86. // r = CT_SELECT(r_prime IF flipped_sign_sqrt | flipped_sign_sqrt_i ELSE r)
  87. r.Select(rPrime, r, flippedSignSqrt|flippedSignSqrtI)
  88. r.Abs(r) // Choose the nonnegative square root.
  89. return correctSignSqrt | flippedSignSqrt
  90. }
  91. func fieldElementFromDecimal(s string) *radix51.FieldElement {
  92. n, ok := new(big.Int).SetString(s, 10)
  93. if !ok {
  94. panic("ristretto255: not a valid decimal: " + s)
  95. }
  96. return new(radix51.FieldElement).FromBig(n)
  97. }