Curve25519FieldElement.cs 7.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237
  1. #if !BESTHTTP_DISABLE_ALTERNATE_SSL && (!UNITY_WEBGL || UNITY_EDITOR)
  2. using System;
  3. using Org.BouncyCastle.Math.Raw;
  4. using Org.BouncyCastle.Utilities;
  5. namespace Org.BouncyCastle.Math.EC.Custom.Djb
  6. {
  7. internal class Curve25519FieldElement
  8. : ECFieldElement
  9. {
  10. public static readonly BigInteger Q = Curve25519.q;
  11. // Calculated as ECConstants.TWO.modPow(Q.shiftRight(2), Q)
  12. private static readonly uint[] PRECOMP_POW2 = new uint[]{ 0x4a0ea0b0, 0xc4ee1b27, 0xad2fe478, 0x2f431806,
  13. 0x3dfbd7a7, 0x2b4d0099, 0x4fc1df0b, 0x2b832480 };
  14. protected internal readonly uint[] x;
  15. public Curve25519FieldElement(BigInteger x)
  16. {
  17. if (x == null || x.SignValue < 0 || x.CompareTo(Q) >= 0)
  18. throw new ArgumentException("value invalid for Curve25519FieldElement", "x");
  19. this.x = Curve25519Field.FromBigInteger(x);
  20. }
  21. public Curve25519FieldElement()
  22. {
  23. this.x = Nat256.Create();
  24. }
  25. protected internal Curve25519FieldElement(uint[] x)
  26. {
  27. this.x = x;
  28. }
  29. public override bool IsZero
  30. {
  31. get { return Nat256.IsZero(x); }
  32. }
  33. public override bool IsOne
  34. {
  35. get { return Nat256.IsOne(x); }
  36. }
  37. public override bool TestBitZero()
  38. {
  39. return Nat256.GetBit(x, 0) == 1;
  40. }
  41. public override BigInteger ToBigInteger()
  42. {
  43. return Nat256.ToBigInteger(x);
  44. }
  45. public override string FieldName
  46. {
  47. get { return "Curve25519Field"; }
  48. }
  49. public override int FieldSize
  50. {
  51. get { return Q.BitLength; }
  52. }
  53. public override ECFieldElement Add(ECFieldElement b)
  54. {
  55. uint[] z = Nat256.Create();
  56. Curve25519Field.Add(x, ((Curve25519FieldElement)b).x, z);
  57. return new Curve25519FieldElement(z);
  58. }
  59. public override ECFieldElement AddOne()
  60. {
  61. uint[] z = Nat256.Create();
  62. Curve25519Field.AddOne(x, z);
  63. return new Curve25519FieldElement(z);
  64. }
  65. public override ECFieldElement Subtract(ECFieldElement b)
  66. {
  67. uint[] z = Nat256.Create();
  68. Curve25519Field.Subtract(x, ((Curve25519FieldElement)b).x, z);
  69. return new Curve25519FieldElement(z);
  70. }
  71. public override ECFieldElement Multiply(ECFieldElement b)
  72. {
  73. uint[] z = Nat256.Create();
  74. Curve25519Field.Multiply(x, ((Curve25519FieldElement)b).x, z);
  75. return new Curve25519FieldElement(z);
  76. }
  77. public override ECFieldElement Divide(ECFieldElement b)
  78. {
  79. //return Multiply(b.Invert());
  80. uint[] z = Nat256.Create();
  81. Mod.Invert(Curve25519Field.P, ((Curve25519FieldElement)b).x, z);
  82. Curve25519Field.Multiply(z, x, z);
  83. return new Curve25519FieldElement(z);
  84. }
  85. public override ECFieldElement Negate()
  86. {
  87. uint[] z = Nat256.Create();
  88. Curve25519Field.Negate(x, z);
  89. return new Curve25519FieldElement(z);
  90. }
  91. public override ECFieldElement Square()
  92. {
  93. uint[] z = Nat256.Create();
  94. Curve25519Field.Square(x, z);
  95. return new Curve25519FieldElement(z);
  96. }
  97. public override ECFieldElement Invert()
  98. {
  99. //return new Curve25519FieldElement(ToBigInteger().ModInverse(Q));
  100. uint[] z = Nat256.Create();
  101. Mod.Invert(Curve25519Field.P, x, z);
  102. return new Curve25519FieldElement(z);
  103. }
  104. /**
  105. * return a sqrt root - the routine verifies that the calculation returns the right value - if
  106. * none exists it returns null.
  107. */
  108. public override ECFieldElement Sqrt()
  109. {
  110. /*
  111. * Q == 8m + 5, so we use Pocklington's method for this case.
  112. *
  113. * First, raise this element to the exponent 2^252 - 2^1 (i.e. m + 1)
  114. *
  115. * Breaking up the exponent's binary representation into "repunits", we get:
  116. * { 251 1s } { 1 0s }
  117. *
  118. * Therefore we need an addition chain containing 251 (the lengths of the repunits)
  119. * We use: 1, 2, 3, 4, 7, 11, 15, 30, 60, 120, 131, [251]
  120. */
  121. uint[] x1 = this.x;
  122. if (Nat256.IsZero(x1) || Nat256.IsOne(x1))
  123. return this;
  124. uint[] x2 = Nat256.Create();
  125. Curve25519Field.Square(x1, x2);
  126. Curve25519Field.Multiply(x2, x1, x2);
  127. uint[] x3 = x2;
  128. Curve25519Field.Square(x2, x3);
  129. Curve25519Field.Multiply(x3, x1, x3);
  130. uint[] x4 = Nat256.Create();
  131. Curve25519Field.Square(x3, x4);
  132. Curve25519Field.Multiply(x4, x1, x4);
  133. uint[] x7 = Nat256.Create();
  134. Curve25519Field.SquareN(x4, 3, x7);
  135. Curve25519Field.Multiply(x7, x3, x7);
  136. uint[] x11 = x3;
  137. Curve25519Field.SquareN(x7, 4, x11);
  138. Curve25519Field.Multiply(x11, x4, x11);
  139. uint[] x15 = x7;
  140. Curve25519Field.SquareN(x11, 4, x15);
  141. Curve25519Field.Multiply(x15, x4, x15);
  142. uint[] x30 = x4;
  143. Curve25519Field.SquareN(x15, 15, x30);
  144. Curve25519Field.Multiply(x30, x15, x30);
  145. uint[] x60 = x15;
  146. Curve25519Field.SquareN(x30, 30, x60);
  147. Curve25519Field.Multiply(x60, x30, x60);
  148. uint[] x120 = x30;
  149. Curve25519Field.SquareN(x60, 60, x120);
  150. Curve25519Field.Multiply(x120, x60, x120);
  151. uint[] x131 = x60;
  152. Curve25519Field.SquareN(x120, 11, x131);
  153. Curve25519Field.Multiply(x131, x11, x131);
  154. uint[] x251 = x11;
  155. Curve25519Field.SquareN(x131, 120, x251);
  156. Curve25519Field.Multiply(x251, x120, x251);
  157. uint[] t1 = x251;
  158. Curve25519Field.Square(t1, t1);
  159. uint[] t2 = x120;
  160. Curve25519Field.Square(t1, t2);
  161. if (Nat256.Eq(x1, t2))
  162. {
  163. return new Curve25519FieldElement(t1);
  164. }
  165. /*
  166. * If the first guess is incorrect, we multiply by a precomputed power of 2 to get the second guess,
  167. * which is ((4x)^(m + 1))/2 mod Q
  168. */
  169. Curve25519Field.Multiply(t1, PRECOMP_POW2, t1);
  170. Curve25519Field.Square(t1, t2);
  171. if (Nat256.Eq(x1, t2))
  172. {
  173. return new Curve25519FieldElement(t1);
  174. }
  175. return null;
  176. }
  177. public override bool Equals(object obj)
  178. {
  179. return Equals(obj as Curve25519FieldElement);
  180. }
  181. public override bool Equals(ECFieldElement other)
  182. {
  183. return Equals(other as Curve25519FieldElement);
  184. }
  185. public virtual bool Equals(Curve25519FieldElement other)
  186. {
  187. if (this == other)
  188. return true;
  189. if (null == other)
  190. return false;
  191. return Nat256.Eq(x, other.x);
  192. }
  193. public override int GetHashCode()
  194. {
  195. return Q.GetHashCode() ^ Arrays.GetHashCode(x, 0, 8);
  196. }
  197. }
  198. }
  199. #endif