| | | 1 | | using System; |
| | | 2 | | using System.Collections; |
| | | 3 | | using System.Diagnostics; |
| | | 4 | | using System.Text; |
| | | 5 | | |
| | | 6 | | using Renci.SshNet.Security.Org.BouncyCastle.Math.EC.Multiplier; |
| | | 7 | | |
| | | 8 | | namespace Renci.SshNet.Security.Org.BouncyCastle.Math.EC |
| | | 9 | | { |
| | | 10 | | /** |
| | | 11 | | * base class for points on elliptic curves. |
| | | 12 | | */ |
| | | 13 | | internal abstract class ECPoint |
| | | 14 | | { |
| | | 15 | | protected static ECFieldElement[] EMPTY_ZS = new ECFieldElement[0]; |
| | | 16 | | |
| | | 17 | | protected static ECFieldElement[] GetInitialZCoords(ECCurve curve) |
| | | 18 | | { |
| | | 19 | | // Cope with null curve, most commonly used by implicitlyCa |
| | | 20 | | int coord = null == curve ? ECCurve.COORD_AFFINE : curve.CoordinateSystem; |
| | | 21 | | |
| | | 22 | | switch (coord) |
| | | 23 | | { |
| | | 24 | | case ECCurve.COORD_AFFINE: |
| | | 25 | | case ECCurve.COORD_LAMBDA_AFFINE: |
| | | 26 | | return EMPTY_ZS; |
| | | 27 | | default: |
| | | 28 | | break; |
| | | 29 | | } |
| | | 30 | | |
| | | 31 | | ECFieldElement one = curve.FromBigInteger(BigInteger.One); |
| | | 32 | | |
| | | 33 | | switch (coord) |
| | | 34 | | { |
| | | 35 | | case ECCurve.COORD_HOMOGENEOUS: |
| | | 36 | | case ECCurve.COORD_JACOBIAN: |
| | | 37 | | case ECCurve.COORD_LAMBDA_PROJECTIVE: |
| | | 38 | | return new ECFieldElement[] { one }; |
| | | 39 | | case ECCurve.COORD_JACOBIAN_CHUDNOVSKY: |
| | | 40 | | return new ECFieldElement[] { one, one, one }; |
| | | 41 | | case ECCurve.COORD_JACOBIAN_MODIFIED: |
| | | 42 | | return new ECFieldElement[] { one, curve.A }; |
| | | 43 | | default: |
| | | 44 | | throw new ArgumentException("unknown coordinate system"); |
| | | 45 | | } |
| | | 46 | | } |
| | | 47 | | |
| | | 48 | | protected internal readonly ECCurve m_curve; |
| | | 49 | | protected internal readonly ECFieldElement m_x, m_y; |
| | | 50 | | protected internal readonly ECFieldElement[] m_zs; |
| | | 51 | | protected internal readonly bool m_withCompression; |
| | | 52 | | |
| | | 53 | | // Dictionary is (string -> PreCompInfo) |
| | | 54 | | protected internal IDictionary m_preCompTable = null; |
| | | 55 | | |
| | | 56 | | protected ECPoint(ECCurve curve, ECFieldElement x, ECFieldElement y, bool withCompression) |
| | | 57 | | : this(curve, x, y, GetInitialZCoords(curve), withCompression) |
| | | 58 | | { |
| | | 59 | | } |
| | | 60 | | |
| | | 61 | | internal ECPoint(ECCurve curve, ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, bool withCompression) |
| | | 62 | | { |
| | | 63 | | this.m_curve = curve; |
| | | 64 | | this.m_x = x; |
| | | 65 | | this.m_y = y; |
| | | 66 | | this.m_zs = zs; |
| | | 67 | | this.m_withCompression = withCompression; |
| | | 68 | | } |
| | | 69 | | |
| | | 70 | | protected abstract bool SatisfiesCurveEquation(); |
| | | 71 | | |
| | | 72 | | protected virtual bool SatisfiesOrder() |
| | | 73 | | { |
| | | 74 | | if (BigInteger.One.Equals(Curve.Cofactor)) |
| | | 75 | | return true; |
| | | 76 | | |
| | | 77 | | BigInteger n = Curve.Order; |
| | | 78 | | |
| | | 79 | | // TODO Require order to be available for all curves |
| | | 80 | | |
| | | 81 | | return n == null || ECAlgorithms.ReferenceMultiply(this, n).IsInfinity; |
| | | 82 | | } |
| | | 83 | | |
| | | 84 | | public ECPoint GetDetachedPoint() |
| | | 85 | | { |
| | | 86 | | return Normalize().Detach(); |
| | | 87 | | } |
| | | 88 | | |
| | | 89 | | public virtual ECCurve Curve |
| | | 90 | | { |
| | | 91 | | get { return m_curve; } |
| | | 92 | | } |
| | | 93 | | |
| | | 94 | | protected abstract ECPoint Detach(); |
| | | 95 | | |
| | | 96 | | protected virtual int CurveCoordinateSystem |
| | | 97 | | { |
| | | 98 | | get |
| | | 99 | | { |
| | | 100 | | // Cope with null curve, most commonly used by implicitlyCa |
| | | 101 | | return null == m_curve ? ECCurve.COORD_AFFINE : m_curve.CoordinateSystem; |
| | | 102 | | } |
| | | 103 | | } |
| | | 104 | | |
| | | 105 | | /** |
| | | 106 | | * Returns the affine x-coordinate after checking that this point is normalized. |
| | | 107 | | * |
| | | 108 | | * @return The affine x-coordinate of this point |
| | | 109 | | * @throws IllegalStateException if the point is not normalized |
| | | 110 | | */ |
| | | 111 | | public virtual ECFieldElement AffineXCoord |
| | | 112 | | { |
| | | 113 | | get |
| | | 114 | | { |
| | | 115 | | CheckNormalized(); |
| | | 116 | | return XCoord; |
| | | 117 | | } |
| | | 118 | | } |
| | | 119 | | |
| | | 120 | | /** |
| | | 121 | | * Returns the affine y-coordinate after checking that this point is normalized |
| | | 122 | | * |
| | | 123 | | * @return The affine y-coordinate of this point |
| | | 124 | | * @throws IllegalStateException if the point is not normalized |
| | | 125 | | */ |
| | | 126 | | public virtual ECFieldElement AffineYCoord |
| | | 127 | | { |
| | | 128 | | get |
| | | 129 | | { |
| | | 130 | | CheckNormalized(); |
| | | 131 | | return YCoord; |
| | | 132 | | } |
| | | 133 | | } |
| | | 134 | | |
| | | 135 | | /** |
| | | 136 | | * Returns the x-coordinate. |
| | | 137 | | * |
| | | 138 | | * Caution: depending on the curve's coordinate system, this may not be the same value as in an |
| | | 139 | | * affine coordinate system; use Normalize() to get a point where the coordinates have their |
| | | 140 | | * affine values, or use AffineXCoord if you expect the point to already have been normalized. |
| | | 141 | | * |
| | | 142 | | * @return the x-coordinate of this point |
| | | 143 | | */ |
| | | 144 | | public virtual ECFieldElement XCoord |
| | | 145 | | { |
| | | 146 | | get { return m_x; } |
| | | 147 | | } |
| | | 148 | | |
| | | 149 | | /** |
| | | 150 | | * Returns the y-coordinate. |
| | | 151 | | * |
| | | 152 | | * Caution: depending on the curve's coordinate system, this may not be the same value as in an |
| | | 153 | | * affine coordinate system; use Normalize() to get a point where the coordinates have their |
| | | 154 | | * affine values, or use AffineYCoord if you expect the point to already have been normalized. |
| | | 155 | | * |
| | | 156 | | * @return the y-coordinate of this point |
| | | 157 | | */ |
| | | 158 | | public virtual ECFieldElement YCoord |
| | | 159 | | { |
| | | 160 | | get { return m_y; } |
| | | 161 | | } |
| | | 162 | | |
| | | 163 | | public virtual ECFieldElement GetZCoord(int index) |
| | | 164 | | { |
| | | 165 | | return (index < 0 || index >= m_zs.Length) ? null : m_zs[index]; |
| | | 166 | | } |
| | | 167 | | |
| | | 168 | | public virtual ECFieldElement[] GetZCoords() |
| | | 169 | | { |
| | | 170 | | int zsLen = m_zs.Length; |
| | | 171 | | if (zsLen == 0) |
| | | 172 | | { |
| | | 173 | | return m_zs; |
| | | 174 | | } |
| | | 175 | | ECFieldElement[] copy = new ECFieldElement[zsLen]; |
| | | 176 | | Array.Copy(m_zs, 0, copy, 0, zsLen); |
| | | 177 | | return copy; |
| | | 178 | | } |
| | | 179 | | |
| | | 180 | | protected internal ECFieldElement RawXCoord |
| | | 181 | | { |
| | | 182 | | get { return m_x; } |
| | | 183 | | } |
| | | 184 | | |
| | | 185 | | protected internal ECFieldElement RawYCoord |
| | | 186 | | { |
| | | 187 | | get { return m_y; } |
| | | 188 | | } |
| | | 189 | | |
| | | 190 | | protected internal ECFieldElement[] RawZCoords |
| | | 191 | | { |
| | | 192 | | get { return m_zs; } |
| | | 193 | | } |
| | | 194 | | |
| | | 195 | | protected virtual void CheckNormalized() |
| | | 196 | | { |
| | | 197 | | if (!IsNormalized()) |
| | | 198 | | throw new InvalidOperationException("point not in normal form"); |
| | | 199 | | } |
| | | 200 | | |
| | | 201 | | public virtual bool IsNormalized() |
| | | 202 | | { |
| | | 203 | | int coord = this.CurveCoordinateSystem; |
| | | 204 | | |
| | | 205 | | return coord == ECCurve.COORD_AFFINE |
| | | 206 | | || coord == ECCurve.COORD_LAMBDA_AFFINE |
| | | 207 | | || IsInfinity |
| | | 208 | | || RawZCoords[0].IsOne; |
| | | 209 | | } |
| | | 210 | | |
| | | 211 | | /** |
| | | 212 | | * Normalization ensures that any projective coordinate is 1, and therefore that the x, y |
| | | 213 | | * coordinates reflect those of the equivalent point in an affine coordinate system. |
| | | 214 | | * |
| | | 215 | | * @return a new ECPoint instance representing the same point, but with normalized coordinates |
| | | 216 | | */ |
| | | 217 | | public virtual ECPoint Normalize() |
| | | 218 | | { |
| | | 219 | | if (this.IsInfinity) |
| | | 220 | | { |
| | | 221 | | return this; |
| | | 222 | | } |
| | | 223 | | |
| | | 224 | | switch (this.CurveCoordinateSystem) |
| | | 225 | | { |
| | | 226 | | case ECCurve.COORD_AFFINE: |
| | | 227 | | case ECCurve.COORD_LAMBDA_AFFINE: |
| | | 228 | | { |
| | | 229 | | return this; |
| | | 230 | | } |
| | | 231 | | default: |
| | | 232 | | { |
| | | 233 | | ECFieldElement Z1 = RawZCoords[0]; |
| | | 234 | | if (Z1.IsOne) |
| | | 235 | | { |
| | | 236 | | return this; |
| | | 237 | | } |
| | | 238 | | |
| | | 239 | | return Normalize(Z1.Invert()); |
| | | 240 | | } |
| | | 241 | | } |
| | | 242 | | } |
| | | 243 | | |
| | | 244 | | internal virtual ECPoint Normalize(ECFieldElement zInv) |
| | | 245 | | { |
| | | 246 | | switch (this.CurveCoordinateSystem) |
| | | 247 | | { |
| | | 248 | | case ECCurve.COORD_HOMOGENEOUS: |
| | | 249 | | case ECCurve.COORD_LAMBDA_PROJECTIVE: |
| | | 250 | | { |
| | | 251 | | return CreateScaledPoint(zInv, zInv); |
| | | 252 | | } |
| | | 253 | | case ECCurve.COORD_JACOBIAN: |
| | | 254 | | case ECCurve.COORD_JACOBIAN_CHUDNOVSKY: |
| | | 255 | | case ECCurve.COORD_JACOBIAN_MODIFIED: |
| | | 256 | | { |
| | | 257 | | ECFieldElement zInv2 = zInv.Square(), zInv3 = zInv2.Multiply(zInv); |
| | | 258 | | return CreateScaledPoint(zInv2, zInv3); |
| | | 259 | | } |
| | | 260 | | default: |
| | | 261 | | { |
| | | 262 | | throw new InvalidOperationException("not a projective coordinate system"); |
| | | 263 | | } |
| | | 264 | | } |
| | | 265 | | } |
| | | 266 | | |
| | | 267 | | protected virtual ECPoint CreateScaledPoint(ECFieldElement sx, ECFieldElement sy) |
| | | 268 | | { |
| | | 269 | | return Curve.CreateRawPoint(RawXCoord.Multiply(sx), RawYCoord.Multiply(sy), IsCompressed); |
| | | 270 | | } |
| | | 271 | | |
| | | 272 | | public bool IsInfinity |
| | | 273 | | { |
| | | 274 | | get { return m_x == null && m_y == null; } |
| | | 275 | | } |
| | | 276 | | |
| | | 277 | | public bool IsCompressed |
| | | 278 | | { |
| | | 279 | | get { return m_withCompression; } |
| | | 280 | | } |
| | | 281 | | |
| | | 282 | | public bool IsValid() |
| | | 283 | | { |
| | | 284 | | return ImplIsValid(false, true); |
| | | 285 | | } |
| | | 286 | | |
| | | 287 | | internal bool IsValidPartial() |
| | | 288 | | { |
| | | 289 | | return ImplIsValid(false, false); |
| | | 290 | | } |
| | | 291 | | |
| | | 292 | | internal bool ImplIsValid(bool decompressed, bool checkOrder) |
| | | 293 | | { |
| | | 294 | | if (IsInfinity) |
| | | 295 | | return true; |
| | | 296 | | |
| | | 297 | | ValidityCallback callback = new ValidityCallback(this, decompressed, checkOrder); |
| | | 298 | | ValidityPreCompInfo validity = (ValidityPreCompInfo)Curve.Precompute(this, ValidityPreCompInfo.PRECOMP_NAME, |
| | | 299 | | return !validity.HasFailed(); |
| | | 300 | | } |
| | | 301 | | |
| | | 302 | | public virtual ECPoint ScaleX(ECFieldElement scale) |
| | | 303 | | { |
| | | 304 | | return IsInfinity |
| | | 305 | | ? this |
| | | 306 | | : Curve.CreateRawPoint(RawXCoord.Multiply(scale), RawYCoord, RawZCoords, IsCompressed); |
| | | 307 | | } |
| | | 308 | | |
| | | 309 | | public virtual ECPoint ScaleY(ECFieldElement scale) |
| | | 310 | | { |
| | | 311 | | return IsInfinity |
| | | 312 | | ? this |
| | | 313 | | : Curve.CreateRawPoint(RawXCoord, RawYCoord.Multiply(scale), RawZCoords, IsCompressed); |
| | | 314 | | } |
| | | 315 | | |
| | | 316 | | public override bool Equals(object obj) |
| | | 317 | | { |
| | | 318 | | return Equals(obj as ECPoint); |
| | | 319 | | } |
| | | 320 | | |
| | | 321 | | public virtual bool Equals(ECPoint other) |
| | | 322 | | { |
| | | 323 | | if (this == other) |
| | | 324 | | return true; |
| | | 325 | | if (null == other) |
| | | 326 | | return false; |
| | | 327 | | |
| | | 328 | | ECCurve c1 = this.Curve, c2 = other.Curve; |
| | | 329 | | bool n1 = (null == c1), n2 = (null == c2); |
| | | 330 | | bool i1 = IsInfinity, i2 = other.IsInfinity; |
| | | 331 | | |
| | | 332 | | if (i1 || i2) |
| | | 333 | | { |
| | | 334 | | return (i1 && i2) && (n1 || n2 || c1.Equals(c2)); |
| | | 335 | | } |
| | | 336 | | |
| | | 337 | | ECPoint p1 = this, p2 = other; |
| | | 338 | | if (n1 && n2) |
| | | 339 | | { |
| | | 340 | | // Points with null curve are in affine form, so already normalized |
| | | 341 | | } |
| | | 342 | | else if (n1) |
| | | 343 | | { |
| | | 344 | | p2 = p2.Normalize(); |
| | | 345 | | } |
| | | 346 | | else if (n2) |
| | | 347 | | { |
| | | 348 | | p1 = p1.Normalize(); |
| | | 349 | | } |
| | | 350 | | else if (!c1.Equals(c2)) |
| | | 351 | | { |
| | | 352 | | return false; |
| | | 353 | | } |
| | | 354 | | else |
| | | 355 | | { |
| | | 356 | | // TODO Consider just requiring already normalized, to avoid silent performance degradation |
| | | 357 | | |
| | | 358 | | ECPoint[] points = new ECPoint[] { this, c1.ImportPoint(p2) }; |
| | | 359 | | |
| | | 360 | | // TODO This is a little strong, really only requires coZNormalizeAll to get Zs equal |
| | | 361 | | c1.NormalizeAll(points); |
| | | 362 | | |
| | | 363 | | p1 = points[0]; |
| | | 364 | | p2 = points[1]; |
| | | 365 | | } |
| | | 366 | | |
| | | 367 | | return p1.XCoord.Equals(p2.XCoord) && p1.YCoord.Equals(p2.YCoord); |
| | | 368 | | } |
| | | 369 | | |
| | | 370 | | public override int GetHashCode() |
| | | 371 | | { |
| | | 372 | | ECCurve c = this.Curve; |
| | | 373 | | int hc = (null == c) ? 0 : ~c.GetHashCode(); |
| | | 374 | | |
| | | 375 | | if (!this.IsInfinity) |
| | | 376 | | { |
| | | 377 | | // TODO Consider just requiring already normalized, to avoid silent performance degradation |
| | | 378 | | |
| | | 379 | | ECPoint p = Normalize(); |
| | | 380 | | |
| | | 381 | | hc ^= p.XCoord.GetHashCode() * 17; |
| | | 382 | | hc ^= p.YCoord.GetHashCode() * 257; |
| | | 383 | | } |
| | | 384 | | |
| | | 385 | | return hc; |
| | | 386 | | } |
| | | 387 | | |
| | | 388 | | public override string ToString() |
| | | 389 | | { |
| | | 390 | | if (this.IsInfinity) |
| | | 391 | | { |
| | | 392 | | return "INF"; |
| | | 393 | | } |
| | | 394 | | |
| | | 395 | | StringBuilder sb = new StringBuilder(); |
| | | 396 | | sb.Append('('); |
| | | 397 | | sb.Append(RawXCoord); |
| | | 398 | | sb.Append(','); |
| | | 399 | | sb.Append(RawYCoord); |
| | | 400 | | for (int i = 0; i < m_zs.Length; ++i) |
| | | 401 | | { |
| | | 402 | | sb.Append(','); |
| | | 403 | | sb.Append(m_zs[i]); |
| | | 404 | | } |
| | | 405 | | sb.Append(')'); |
| | | 406 | | return sb.ToString(); |
| | | 407 | | } |
| | | 408 | | |
| | | 409 | | public virtual byte[] GetEncoded() |
| | | 410 | | { |
| | | 411 | | return GetEncoded(m_withCompression); |
| | | 412 | | } |
| | | 413 | | |
| | | 414 | | public abstract byte[] GetEncoded(bool compressed); |
| | | 415 | | |
| | | 416 | | protected internal abstract bool CompressionYTilde { get; } |
| | | 417 | | |
| | | 418 | | public abstract ECPoint Add(ECPoint b); |
| | | 419 | | public abstract ECPoint Subtract(ECPoint b); |
| | | 420 | | public abstract ECPoint Negate(); |
| | | 421 | | |
| | | 422 | | public virtual ECPoint TimesPow2(int e) |
| | | 423 | | { |
| | | 424 | | if (e < 0) |
| | | 425 | | throw new ArgumentException("cannot be negative", "e"); |
| | | 426 | | |
| | | 427 | | ECPoint p = this; |
| | | 428 | | while (--e >= 0) |
| | | 429 | | { |
| | | 430 | | p = p.Twice(); |
| | | 431 | | } |
| | | 432 | | return p; |
| | | 433 | | } |
| | | 434 | | |
| | | 435 | | public abstract ECPoint Twice(); |
| | | 436 | | public abstract ECPoint Multiply(BigInteger b); |
| | | 437 | | |
| | | 438 | | public virtual ECPoint TwicePlus(ECPoint b) |
| | | 439 | | { |
| | | 440 | | return Twice().Add(b); |
| | | 441 | | } |
| | | 442 | | |
| | | 443 | | public virtual ECPoint ThreeTimes() |
| | | 444 | | { |
| | | 445 | | return TwicePlus(this); |
| | | 446 | | } |
| | | 447 | | |
| | | 448 | | private class ValidityCallback |
| | | 449 | | : IPreCompCallback |
| | | 450 | | { |
| | | 451 | | private readonly ECPoint m_outer; |
| | | 452 | | private readonly bool m_decompressed, m_checkOrder; |
| | | 453 | | |
| | | 454 | | internal ValidityCallback(ECPoint outer, bool decompressed, bool checkOrder) |
| | | 455 | | { |
| | | 456 | | this.m_outer = outer; |
| | | 457 | | this.m_decompressed = decompressed; |
| | | 458 | | this.m_checkOrder = checkOrder; |
| | | 459 | | } |
| | | 460 | | |
| | | 461 | | public PreCompInfo Precompute(PreCompInfo existing) |
| | | 462 | | { |
| | | 463 | | ValidityPreCompInfo info = existing as ValidityPreCompInfo; |
| | | 464 | | if (info == null) |
| | | 465 | | { |
| | | 466 | | info = new ValidityPreCompInfo(); |
| | | 467 | | } |
| | | 468 | | |
| | | 469 | | if (info.HasFailed()) |
| | | 470 | | return info; |
| | | 471 | | |
| | | 472 | | if (!info.HasCurveEquationPassed()) |
| | | 473 | | { |
| | | 474 | | if (!m_decompressed && !m_outer.SatisfiesCurveEquation()) |
| | | 475 | | { |
| | | 476 | | info.ReportFailed(); |
| | | 477 | | return info; |
| | | 478 | | } |
| | | 479 | | info.ReportCurveEquationPassed(); |
| | | 480 | | } |
| | | 481 | | if (m_checkOrder && !info.HasOrderPassed()) |
| | | 482 | | { |
| | | 483 | | if (!m_outer.SatisfiesOrder()) |
| | | 484 | | { |
| | | 485 | | info.ReportFailed(); |
| | | 486 | | return info; |
| | | 487 | | } |
| | | 488 | | info.ReportOrderPassed(); |
| | | 489 | | } |
| | | 490 | | return info; |
| | | 491 | | } |
| | | 492 | | } |
| | | 493 | | } |
| | | 494 | | |
| | | 495 | | internal abstract class ECPointBase |
| | | 496 | | : ECPoint |
| | | 497 | | { |
| | | 498 | | protected internal ECPointBase( |
| | | 499 | | ECCurve curve, |
| | | 500 | | ECFieldElement x, |
| | | 501 | | ECFieldElement y, |
| | | 502 | | bool withCompression) |
| | | 503 | | : base(curve, x, y, withCompression) |
| | | 504 | | { |
| | | 505 | | } |
| | | 506 | | |
| | | 507 | | protected internal ECPointBase(ECCurve curve, ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, bool with |
| | | 508 | | : base(curve, x, y, zs, withCompression) |
| | | 509 | | { |
| | | 510 | | } |
| | | 511 | | |
| | | 512 | | /** |
| | | 513 | | * return the field element encoded with point compression. (S 4.3.6) |
| | | 514 | | */ |
| | | 515 | | public override byte[] GetEncoded(bool compressed) |
| | | 516 | | { |
| | | 517 | | if (this.IsInfinity) |
| | | 518 | | { |
| | | 519 | | return new byte[1]; |
| | | 520 | | } |
| | | 521 | | |
| | | 522 | | ECPoint normed = Normalize(); |
| | | 523 | | |
| | | 524 | | byte[] X = normed.XCoord.GetEncoded(); |
| | | 525 | | |
| | | 526 | | if (compressed) |
| | | 527 | | { |
| | | 528 | | byte[] PO = new byte[X.Length + 1]; |
| | | 529 | | PO[0] = (byte)(normed.CompressionYTilde ? 0x03 : 0x02); |
| | | 530 | | Array.Copy(X, 0, PO, 1, X.Length); |
| | | 531 | | return PO; |
| | | 532 | | } |
| | | 533 | | |
| | | 534 | | byte[] Y = normed.YCoord.GetEncoded(); |
| | | 535 | | |
| | | 536 | | { |
| | | 537 | | byte[] PO = new byte[X.Length + Y.Length + 1]; |
| | | 538 | | PO[0] = 0x04; |
| | | 539 | | Array.Copy(X, 0, PO, 1, X.Length); |
| | | 540 | | Array.Copy(Y, 0, PO, X.Length + 1, Y.Length); |
| | | 541 | | return PO; |
| | | 542 | | } |
| | | 543 | | } |
| | | 544 | | |
| | | 545 | | /** |
| | | 546 | | * Multiplies this <code>ECPoint</code> by the given number. |
| | | 547 | | * @param k The multiplicator. |
| | | 548 | | * @return <code>k * this</code>. |
| | | 549 | | */ |
| | | 550 | | public override ECPoint Multiply(BigInteger k) |
| | | 551 | | { |
| | | 552 | | return this.Curve.GetMultiplier().Multiply(this, k); |
| | | 553 | | } |
| | | 554 | | } |
| | | 555 | | |
| | | 556 | | internal abstract class AbstractFpPoint |
| | | 557 | | : ECPointBase |
| | | 558 | | { |
| | | 559 | | protected AbstractFpPoint(ECCurve curve, ECFieldElement x, ECFieldElement y, bool withCompression) |
| | | 560 | | : base(curve, x, y, withCompression) |
| | | 561 | | { |
| | | 562 | | } |
| | | 563 | | |
| | | 564 | | protected AbstractFpPoint(ECCurve curve, ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, bool withCompr |
| | | 565 | | : base(curve, x, y, zs, withCompression) |
| | | 566 | | { |
| | | 567 | | } |
| | | 568 | | |
| | | 569 | | protected internal override bool CompressionYTilde |
| | | 570 | | { |
| | | 571 | | get { return this.AffineYCoord.TestBitZero(); } |
| | | 572 | | } |
| | | 573 | | |
| | | 574 | | protected override bool SatisfiesCurveEquation() |
| | | 575 | | { |
| | | 576 | | ECFieldElement X = this.RawXCoord, Y = this.RawYCoord, A = Curve.A, B = Curve.B; |
| | | 577 | | ECFieldElement lhs = Y.Square(); |
| | | 578 | | |
| | | 579 | | switch (CurveCoordinateSystem) |
| | | 580 | | { |
| | | 581 | | case ECCurve.COORD_AFFINE: |
| | | 582 | | break; |
| | | 583 | | case ECCurve.COORD_HOMOGENEOUS: |
| | | 584 | | { |
| | | 585 | | ECFieldElement Z = this.RawZCoords[0]; |
| | | 586 | | if (!Z.IsOne) |
| | | 587 | | { |
| | | 588 | | ECFieldElement Z2 = Z.Square(), Z3 = Z.Multiply(Z2); |
| | | 589 | | lhs = lhs.Multiply(Z); |
| | | 590 | | A = A.Multiply(Z2); |
| | | 591 | | B = B.Multiply(Z3); |
| | | 592 | | } |
| | | 593 | | break; |
| | | 594 | | } |
| | | 595 | | case ECCurve.COORD_JACOBIAN: |
| | | 596 | | case ECCurve.COORD_JACOBIAN_CHUDNOVSKY: |
| | | 597 | | case ECCurve.COORD_JACOBIAN_MODIFIED: |
| | | 598 | | { |
| | | 599 | | ECFieldElement Z = this.RawZCoords[0]; |
| | | 600 | | if (!Z.IsOne) |
| | | 601 | | { |
| | | 602 | | ECFieldElement Z2 = Z.Square(), Z4 = Z2.Square(), Z6 = Z2.Multiply(Z4); |
| | | 603 | | A = A.Multiply(Z4); |
| | | 604 | | B = B.Multiply(Z6); |
| | | 605 | | } |
| | | 606 | | break; |
| | | 607 | | } |
| | | 608 | | default: |
| | | 609 | | throw new InvalidOperationException("unsupported coordinate system"); |
| | | 610 | | } |
| | | 611 | | |
| | | 612 | | ECFieldElement rhs = X.Square().Add(A).Multiply(X).Add(B); |
| | | 613 | | return lhs.Equals(rhs); |
| | | 614 | | } |
| | | 615 | | |
| | | 616 | | public override ECPoint Subtract(ECPoint b) |
| | | 617 | | { |
| | | 618 | | if (b.IsInfinity) |
| | | 619 | | return this; |
| | | 620 | | |
| | | 621 | | // Add -b |
| | | 622 | | return Add(b.Negate()); |
| | | 623 | | } |
| | | 624 | | } |
| | | 625 | | |
| | | 626 | | /** |
| | | 627 | | * Elliptic curve points over Fp |
| | | 628 | | */ |
| | | 629 | | internal class FpPoint |
| | | 630 | | : AbstractFpPoint |
| | | 631 | | { |
| | | 632 | | /** |
| | | 633 | | * Create a point which encodes without point compression. |
| | | 634 | | * |
| | | 635 | | * @param curve the curve to use |
| | | 636 | | * @param x affine x co-ordinate |
| | | 637 | | * @param y affine y co-ordinate |
| | | 638 | | */ |
| | | 639 | | public FpPoint(ECCurve curve, ECFieldElement x, ECFieldElement y) |
| | | 640 | | : this(curve, x, y, false) |
| | | 641 | | { |
| | | 642 | | } |
| | | 643 | | |
| | | 644 | | /** |
| | | 645 | | * Create a point that encodes with or without point compression. |
| | | 646 | | * |
| | | 647 | | * @param curve the curve to use |
| | | 648 | | * @param x affine x co-ordinate |
| | | 649 | | * @param y affine y co-ordinate |
| | | 650 | | * @param withCompression if true encode with point compression |
| | | 651 | | */ |
| | | 652 | | public FpPoint(ECCurve curve, ECFieldElement x, ECFieldElement y, bool withCompression) |
| | | 653 | | : base(curve, x, y, withCompression) |
| | | 654 | | { |
| | | 655 | | if ((x == null) != (y == null)) |
| | | 656 | | throw new ArgumentException("Exactly one of the field elements is null"); |
| | | 657 | | } |
| | | 658 | | |
| | | 659 | | internal FpPoint(ECCurve curve, ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, bool withCompression) |
| | | 660 | | : base(curve, x, y, zs, withCompression) |
| | | 661 | | { |
| | | 662 | | } |
| | | 663 | | |
| | | 664 | | protected override ECPoint Detach() |
| | | 665 | | { |
| | | 666 | | return new FpPoint(null, AffineXCoord, AffineYCoord, false); |
| | | 667 | | } |
| | | 668 | | |
| | | 669 | | public override ECFieldElement GetZCoord(int index) |
| | | 670 | | { |
| | | 671 | | if (index == 1 && ECCurve.COORD_JACOBIAN_MODIFIED == this.CurveCoordinateSystem) |
| | | 672 | | { |
| | | 673 | | return GetJacobianModifiedW(); |
| | | 674 | | } |
| | | 675 | | |
| | | 676 | | return base.GetZCoord(index); |
| | | 677 | | } |
| | | 678 | | |
| | | 679 | | // B.3 pg 62 |
| | | 680 | | public override ECPoint Add(ECPoint b) |
| | | 681 | | { |
| | | 682 | | if (this.IsInfinity) |
| | | 683 | | return b; |
| | | 684 | | if (b.IsInfinity) |
| | | 685 | | return this; |
| | | 686 | | if (this == b) |
| | | 687 | | return Twice(); |
| | | 688 | | |
| | | 689 | | ECCurve curve = this.Curve; |
| | | 690 | | int coord = curve.CoordinateSystem; |
| | | 691 | | |
| | | 692 | | ECFieldElement X1 = this.RawXCoord, Y1 = this.RawYCoord; |
| | | 693 | | ECFieldElement X2 = b.RawXCoord, Y2 = b.RawYCoord; |
| | | 694 | | |
| | | 695 | | switch (coord) |
| | | 696 | | { |
| | | 697 | | case ECCurve.COORD_AFFINE: |
| | | 698 | | { |
| | | 699 | | ECFieldElement dx = X2.Subtract(X1), dy = Y2.Subtract(Y1); |
| | | 700 | | |
| | | 701 | | if (dx.IsZero) |
| | | 702 | | { |
| | | 703 | | if (dy.IsZero) |
| | | 704 | | { |
| | | 705 | | // this == b, i.e. this must be doubled |
| | | 706 | | return Twice(); |
| | | 707 | | } |
| | | 708 | | |
| | | 709 | | // this == -b, i.e. the result is the point at infinity |
| | | 710 | | return Curve.Infinity; |
| | | 711 | | } |
| | | 712 | | |
| | | 713 | | ECFieldElement gamma = dy.Divide(dx); |
| | | 714 | | ECFieldElement X3 = gamma.Square().Subtract(X1).Subtract(X2); |
| | | 715 | | ECFieldElement Y3 = gamma.Multiply(X1.Subtract(X3)).Subtract(Y1); |
| | | 716 | | |
| | | 717 | | return new FpPoint(Curve, X3, Y3, IsCompressed); |
| | | 718 | | } |
| | | 719 | | |
| | | 720 | | case ECCurve.COORD_HOMOGENEOUS: |
| | | 721 | | { |
| | | 722 | | ECFieldElement Z1 = this.RawZCoords[0]; |
| | | 723 | | ECFieldElement Z2 = b.RawZCoords[0]; |
| | | 724 | | |
| | | 725 | | bool Z1IsOne = Z1.IsOne; |
| | | 726 | | bool Z2IsOne = Z2.IsOne; |
| | | 727 | | |
| | | 728 | | ECFieldElement u1 = Z1IsOne ? Y2 : Y2.Multiply(Z1); |
| | | 729 | | ECFieldElement u2 = Z2IsOne ? Y1 : Y1.Multiply(Z2); |
| | | 730 | | ECFieldElement u = u1.Subtract(u2); |
| | | 731 | | ECFieldElement v1 = Z1IsOne ? X2 : X2.Multiply(Z1); |
| | | 732 | | ECFieldElement v2 = Z2IsOne ? X1 : X1.Multiply(Z2); |
| | | 733 | | ECFieldElement v = v1.Subtract(v2); |
| | | 734 | | |
| | | 735 | | // Check if b == this or b == -this |
| | | 736 | | if (v.IsZero) |
| | | 737 | | { |
| | | 738 | | if (u.IsZero) |
| | | 739 | | { |
| | | 740 | | // this == b, i.e. this must be doubled |
| | | 741 | | return this.Twice(); |
| | | 742 | | } |
| | | 743 | | |
| | | 744 | | // this == -b, i.e. the result is the point at infinity |
| | | 745 | | return curve.Infinity; |
| | | 746 | | } |
| | | 747 | | |
| | | 748 | | // TODO Optimize for when w == 1 |
| | | 749 | | ECFieldElement w = Z1IsOne ? Z2 : Z2IsOne ? Z1 : Z1.Multiply(Z2); |
| | | 750 | | ECFieldElement vSquared = v.Square(); |
| | | 751 | | ECFieldElement vCubed = vSquared.Multiply(v); |
| | | 752 | | ECFieldElement vSquaredV2 = vSquared.Multiply(v2); |
| | | 753 | | ECFieldElement A = u.Square().Multiply(w).Subtract(vCubed).Subtract(Two(vSquaredV2)); |
| | | 754 | | |
| | | 755 | | ECFieldElement X3 = v.Multiply(A); |
| | | 756 | | ECFieldElement Y3 = vSquaredV2.Subtract(A).MultiplyMinusProduct(u, u2, vCubed); |
| | | 757 | | ECFieldElement Z3 = vCubed.Multiply(w); |
| | | 758 | | |
| | | 759 | | return new FpPoint(curve, X3, Y3, new ECFieldElement[] { Z3 }, IsCompressed); |
| | | 760 | | } |
| | | 761 | | |
| | | 762 | | case ECCurve.COORD_JACOBIAN: |
| | | 763 | | case ECCurve.COORD_JACOBIAN_MODIFIED: |
| | | 764 | | { |
| | | 765 | | ECFieldElement Z1 = this.RawZCoords[0]; |
| | | 766 | | ECFieldElement Z2 = b.RawZCoords[0]; |
| | | 767 | | |
| | | 768 | | bool Z1IsOne = Z1.IsOne; |
| | | 769 | | |
| | | 770 | | ECFieldElement X3, Y3, Z3, Z3Squared = null; |
| | | 771 | | |
| | | 772 | | if (!Z1IsOne && Z1.Equals(Z2)) |
| | | 773 | | { |
| | | 774 | | // TODO Make this available as public method coZAdd? |
| | | 775 | | |
| | | 776 | | ECFieldElement dx = X1.Subtract(X2), dy = Y1.Subtract(Y2); |
| | | 777 | | if (dx.IsZero) |
| | | 778 | | { |
| | | 779 | | if (dy.IsZero) |
| | | 780 | | { |
| | | 781 | | return Twice(); |
| | | 782 | | } |
| | | 783 | | return curve.Infinity; |
| | | 784 | | } |
| | | 785 | | |
| | | 786 | | ECFieldElement C = dx.Square(); |
| | | 787 | | ECFieldElement W1 = X1.Multiply(C), W2 = X2.Multiply(C); |
| | | 788 | | ECFieldElement A1 = W1.Subtract(W2).Multiply(Y1); |
| | | 789 | | |
| | | 790 | | X3 = dy.Square().Subtract(W1).Subtract(W2); |
| | | 791 | | Y3 = W1.Subtract(X3).Multiply(dy).Subtract(A1); |
| | | 792 | | Z3 = dx; |
| | | 793 | | |
| | | 794 | | if (Z1IsOne) |
| | | 795 | | { |
| | | 796 | | Z3Squared = C; |
| | | 797 | | } |
| | | 798 | | else |
| | | 799 | | { |
| | | 800 | | Z3 = Z3.Multiply(Z1); |
| | | 801 | | } |
| | | 802 | | } |
| | | 803 | | else |
| | | 804 | | { |
| | | 805 | | ECFieldElement Z1Squared, U2, S2; |
| | | 806 | | if (Z1IsOne) |
| | | 807 | | { |
| | | 808 | | Z1Squared = Z1; U2 = X2; S2 = Y2; |
| | | 809 | | } |
| | | 810 | | else |
| | | 811 | | { |
| | | 812 | | Z1Squared = Z1.Square(); |
| | | 813 | | U2 = Z1Squared.Multiply(X2); |
| | | 814 | | ECFieldElement Z1Cubed = Z1Squared.Multiply(Z1); |
| | | 815 | | S2 = Z1Cubed.Multiply(Y2); |
| | | 816 | | } |
| | | 817 | | |
| | | 818 | | bool Z2IsOne = Z2.IsOne; |
| | | 819 | | ECFieldElement Z2Squared, U1, S1; |
| | | 820 | | if (Z2IsOne) |
| | | 821 | | { |
| | | 822 | | Z2Squared = Z2; U1 = X1; S1 = Y1; |
| | | 823 | | } |
| | | 824 | | else |
| | | 825 | | { |
| | | 826 | | Z2Squared = Z2.Square(); |
| | | 827 | | U1 = Z2Squared.Multiply(X1); |
| | | 828 | | ECFieldElement Z2Cubed = Z2Squared.Multiply(Z2); |
| | | 829 | | S1 = Z2Cubed.Multiply(Y1); |
| | | 830 | | } |
| | | 831 | | |
| | | 832 | | ECFieldElement H = U1.Subtract(U2); |
| | | 833 | | ECFieldElement R = S1.Subtract(S2); |
| | | 834 | | |
| | | 835 | | // Check if b == this or b == -this |
| | | 836 | | if (H.IsZero) |
| | | 837 | | { |
| | | 838 | | if (R.IsZero) |
| | | 839 | | { |
| | | 840 | | // this == b, i.e. this must be doubled |
| | | 841 | | return this.Twice(); |
| | | 842 | | } |
| | | 843 | | |
| | | 844 | | // this == -b, i.e. the result is the point at infinity |
| | | 845 | | return curve.Infinity; |
| | | 846 | | } |
| | | 847 | | |
| | | 848 | | ECFieldElement HSquared = H.Square(); |
| | | 849 | | ECFieldElement G = HSquared.Multiply(H); |
| | | 850 | | ECFieldElement V = HSquared.Multiply(U1); |
| | | 851 | | |
| | | 852 | | X3 = R.Square().Add(G).Subtract(Two(V)); |
| | | 853 | | Y3 = V.Subtract(X3).MultiplyMinusProduct(R, G, S1); |
| | | 854 | | |
| | | 855 | | Z3 = H; |
| | | 856 | | if (!Z1IsOne) |
| | | 857 | | { |
| | | 858 | | Z3 = Z3.Multiply(Z1); |
| | | 859 | | } |
| | | 860 | | if (!Z2IsOne) |
| | | 861 | | { |
| | | 862 | | Z3 = Z3.Multiply(Z2); |
| | | 863 | | } |
| | | 864 | | |
| | | 865 | | // Alternative calculation of Z3 using fast square |
| | | 866 | | //X3 = four(X3); |
| | | 867 | | //Y3 = eight(Y3); |
| | | 868 | | //Z3 = doubleProductFromSquares(Z1, Z2, Z1Squared, Z2Squared).Multiply(H); |
| | | 869 | | |
| | | 870 | | if (Z3 == H) |
| | | 871 | | { |
| | | 872 | | Z3Squared = HSquared; |
| | | 873 | | } |
| | | 874 | | } |
| | | 875 | | |
| | | 876 | | ECFieldElement[] zs; |
| | | 877 | | if (coord == ECCurve.COORD_JACOBIAN_MODIFIED) |
| | | 878 | | { |
| | | 879 | | // TODO If the result will only be used in a subsequent addition, we don't need W3 |
| | | 880 | | ECFieldElement W3 = CalculateJacobianModifiedW(Z3, Z3Squared); |
| | | 881 | | |
| | | 882 | | zs = new ECFieldElement[] { Z3, W3 }; |
| | | 883 | | } |
| | | 884 | | else |
| | | 885 | | { |
| | | 886 | | zs = new ECFieldElement[] { Z3 }; |
| | | 887 | | } |
| | | 888 | | |
| | | 889 | | return new FpPoint(curve, X3, Y3, zs, IsCompressed); |
| | | 890 | | } |
| | | 891 | | |
| | | 892 | | default: |
| | | 893 | | { |
| | | 894 | | throw new InvalidOperationException("unsupported coordinate system"); |
| | | 895 | | } |
| | | 896 | | } |
| | | 897 | | } |
| | | 898 | | |
| | | 899 | | // B.3 pg 62 |
| | | 900 | | public override ECPoint Twice() |
| | | 901 | | { |
| | | 902 | | if (this.IsInfinity) |
| | | 903 | | return this; |
| | | 904 | | |
| | | 905 | | ECCurve curve = this.Curve; |
| | | 906 | | |
| | | 907 | | ECFieldElement Y1 = this.RawYCoord; |
| | | 908 | | if (Y1.IsZero) |
| | | 909 | | return curve.Infinity; |
| | | 910 | | |
| | | 911 | | int coord = curve.CoordinateSystem; |
| | | 912 | | |
| | | 913 | | ECFieldElement X1 = this.RawXCoord; |
| | | 914 | | |
| | | 915 | | switch (coord) |
| | | 916 | | { |
| | | 917 | | case ECCurve.COORD_AFFINE: |
| | | 918 | | { |
| | | 919 | | ECFieldElement X1Squared = X1.Square(); |
| | | 920 | | ECFieldElement gamma = Three(X1Squared).Add(this.Curve.A).Divide(Two(Y1)); |
| | | 921 | | ECFieldElement X3 = gamma.Square().Subtract(Two(X1)); |
| | | 922 | | ECFieldElement Y3 = gamma.Multiply(X1.Subtract(X3)).Subtract(Y1); |
| | | 923 | | |
| | | 924 | | return new FpPoint(Curve, X3, Y3, IsCompressed); |
| | | 925 | | } |
| | | 926 | | |
| | | 927 | | case ECCurve.COORD_HOMOGENEOUS: |
| | | 928 | | { |
| | | 929 | | ECFieldElement Z1 = this.RawZCoords[0]; |
| | | 930 | | |
| | | 931 | | bool Z1IsOne = Z1.IsOne; |
| | | 932 | | |
| | | 933 | | // TODO Optimize for small negative a4 and -3 |
| | | 934 | | ECFieldElement w = curve.A; |
| | | 935 | | if (!w.IsZero && !Z1IsOne) |
| | | 936 | | { |
| | | 937 | | w = w.Multiply(Z1.Square()); |
| | | 938 | | } |
| | | 939 | | w = w.Add(Three(X1.Square())); |
| | | 940 | | |
| | | 941 | | ECFieldElement s = Z1IsOne ? Y1 : Y1.Multiply(Z1); |
| | | 942 | | ECFieldElement t = Z1IsOne ? Y1.Square() : s.Multiply(Y1); |
| | | 943 | | ECFieldElement B = X1.Multiply(t); |
| | | 944 | | ECFieldElement _4B = Four(B); |
| | | 945 | | ECFieldElement h = w.Square().Subtract(Two(_4B)); |
| | | 946 | | |
| | | 947 | | ECFieldElement _2s = Two(s); |
| | | 948 | | ECFieldElement X3 = h.Multiply(_2s); |
| | | 949 | | ECFieldElement _2t = Two(t); |
| | | 950 | | ECFieldElement Y3 = _4B.Subtract(h).Multiply(w).Subtract(Two(_2t.Square())); |
| | | 951 | | ECFieldElement _4sSquared = Z1IsOne ? Two(_2t) : _2s.Square(); |
| | | 952 | | ECFieldElement Z3 = Two(_4sSquared).Multiply(s); |
| | | 953 | | |
| | | 954 | | return new FpPoint(curve, X3, Y3, new ECFieldElement[] { Z3 }, IsCompressed); |
| | | 955 | | } |
| | | 956 | | |
| | | 957 | | case ECCurve.COORD_JACOBIAN: |
| | | 958 | | { |
| | | 959 | | ECFieldElement Z1 = this.RawZCoords[0]; |
| | | 960 | | |
| | | 961 | | bool Z1IsOne = Z1.IsOne; |
| | | 962 | | |
| | | 963 | | ECFieldElement Y1Squared = Y1.Square(); |
| | | 964 | | ECFieldElement T = Y1Squared.Square(); |
| | | 965 | | |
| | | 966 | | ECFieldElement a4 = curve.A; |
| | | 967 | | ECFieldElement a4Neg = a4.Negate(); |
| | | 968 | | |
| | | 969 | | ECFieldElement M, S; |
| | | 970 | | if (a4Neg.ToBigInteger().Equals(BigInteger.ValueOf(3))) |
| | | 971 | | { |
| | | 972 | | ECFieldElement Z1Squared = Z1IsOne ? Z1 : Z1.Square(); |
| | | 973 | | M = Three(X1.Add(Z1Squared).Multiply(X1.Subtract(Z1Squared))); |
| | | 974 | | S = Four(Y1Squared.Multiply(X1)); |
| | | 975 | | } |
| | | 976 | | else |
| | | 977 | | { |
| | | 978 | | ECFieldElement X1Squared = X1.Square(); |
| | | 979 | | M = Three(X1Squared); |
| | | 980 | | if (Z1IsOne) |
| | | 981 | | { |
| | | 982 | | M = M.Add(a4); |
| | | 983 | | } |
| | | 984 | | else if (!a4.IsZero) |
| | | 985 | | { |
| | | 986 | | ECFieldElement Z1Squared = Z1IsOne ? Z1 : Z1.Square(); |
| | | 987 | | ECFieldElement Z1Pow4 = Z1Squared.Square(); |
| | | 988 | | if (a4Neg.BitLength < a4.BitLength) |
| | | 989 | | { |
| | | 990 | | M = M.Subtract(Z1Pow4.Multiply(a4Neg)); |
| | | 991 | | } |
| | | 992 | | else |
| | | 993 | | { |
| | | 994 | | M = M.Add(Z1Pow4.Multiply(a4)); |
| | | 995 | | } |
| | | 996 | | } |
| | | 997 | | //S = two(doubleProductFromSquares(X1, Y1Squared, X1Squared, T)); |
| | | 998 | | S = Four(X1.Multiply(Y1Squared)); |
| | | 999 | | } |
| | | 1000 | | |
| | | 1001 | | ECFieldElement X3 = M.Square().Subtract(Two(S)); |
| | | 1002 | | ECFieldElement Y3 = S.Subtract(X3).Multiply(M).Subtract(Eight(T)); |
| | | 1003 | | |
| | | 1004 | | ECFieldElement Z3 = Two(Y1); |
| | | 1005 | | if (!Z1IsOne) |
| | | 1006 | | { |
| | | 1007 | | Z3 = Z3.Multiply(Z1); |
| | | 1008 | | } |
| | | 1009 | | |
| | | 1010 | | // Alternative calculation of Z3 using fast square |
| | | 1011 | | //ECFieldElement Z3 = doubleProductFromSquares(Y1, Z1, Y1Squared, Z1Squared); |
| | | 1012 | | |
| | | 1013 | | return new FpPoint(curve, X3, Y3, new ECFieldElement[] { Z3 }, IsCompressed); |
| | | 1014 | | } |
| | | 1015 | | |
| | | 1016 | | case ECCurve.COORD_JACOBIAN_MODIFIED: |
| | | 1017 | | { |
| | | 1018 | | return TwiceJacobianModified(true); |
| | | 1019 | | } |
| | | 1020 | | |
| | | 1021 | | default: |
| | | 1022 | | { |
| | | 1023 | | throw new InvalidOperationException("unsupported coordinate system"); |
| | | 1024 | | } |
| | | 1025 | | } |
| | | 1026 | | } |
| | | 1027 | | |
| | | 1028 | | public override ECPoint TwicePlus(ECPoint b) |
| | | 1029 | | { |
| | | 1030 | | if (this == b) |
| | | 1031 | | return ThreeTimes(); |
| | | 1032 | | if (this.IsInfinity) |
| | | 1033 | | return b; |
| | | 1034 | | if (b.IsInfinity) |
| | | 1035 | | return Twice(); |
| | | 1036 | | |
| | | 1037 | | ECFieldElement Y1 = this.RawYCoord; |
| | | 1038 | | if (Y1.IsZero) |
| | | 1039 | | return b; |
| | | 1040 | | |
| | | 1041 | | ECCurve curve = this.Curve; |
| | | 1042 | | int coord = curve.CoordinateSystem; |
| | | 1043 | | |
| | | 1044 | | switch (coord) |
| | | 1045 | | { |
| | | 1046 | | case ECCurve.COORD_AFFINE: |
| | | 1047 | | { |
| | | 1048 | | ECFieldElement X1 = this.RawXCoord; |
| | | 1049 | | ECFieldElement X2 = b.RawXCoord, Y2 = b.RawYCoord; |
| | | 1050 | | |
| | | 1051 | | ECFieldElement dx = X2.Subtract(X1), dy = Y2.Subtract(Y1); |
| | | 1052 | | |
| | | 1053 | | if (dx.IsZero) |
| | | 1054 | | { |
| | | 1055 | | if (dy.IsZero) |
| | | 1056 | | { |
| | | 1057 | | // this == b i.e. the result is 3P |
| | | 1058 | | return ThreeTimes(); |
| | | 1059 | | } |
| | | 1060 | | |
| | | 1061 | | // this == -b, i.e. the result is P |
| | | 1062 | | return this; |
| | | 1063 | | } |
| | | 1064 | | |
| | | 1065 | | /* |
| | | 1066 | | * Optimized calculation of 2P + Q, as described in "Trading Inversions for |
| | | 1067 | | * Multiplications in Elliptic Curve Cryptography", by Ciet, Joye, Lauter, Montgomery. |
| | | 1068 | | */ |
| | | 1069 | | |
| | | 1070 | | ECFieldElement X = dx.Square(), Y = dy.Square(); |
| | | 1071 | | ECFieldElement d = X.Multiply(Two(X1).Add(X2)).Subtract(Y); |
| | | 1072 | | if (d.IsZero) |
| | | 1073 | | { |
| | | 1074 | | return Curve.Infinity; |
| | | 1075 | | } |
| | | 1076 | | |
| | | 1077 | | ECFieldElement D = d.Multiply(dx); |
| | | 1078 | | ECFieldElement I = D.Invert(); |
| | | 1079 | | ECFieldElement L1 = d.Multiply(I).Multiply(dy); |
| | | 1080 | | ECFieldElement L2 = Two(Y1).Multiply(X).Multiply(dx).Multiply(I).Subtract(L1); |
| | | 1081 | | ECFieldElement X4 = (L2.Subtract(L1)).Multiply(L1.Add(L2)).Add(X2); |
| | | 1082 | | ECFieldElement Y4 = (X1.Subtract(X4)).Multiply(L2).Subtract(Y1); |
| | | 1083 | | |
| | | 1084 | | return new FpPoint(Curve, X4, Y4, IsCompressed); |
| | | 1085 | | } |
| | | 1086 | | case ECCurve.COORD_JACOBIAN_MODIFIED: |
| | | 1087 | | { |
| | | 1088 | | return TwiceJacobianModified(false).Add(b); |
| | | 1089 | | } |
| | | 1090 | | default: |
| | | 1091 | | { |
| | | 1092 | | return Twice().Add(b); |
| | | 1093 | | } |
| | | 1094 | | } |
| | | 1095 | | } |
| | | 1096 | | |
| | | 1097 | | public override ECPoint ThreeTimes() |
| | | 1098 | | { |
| | | 1099 | | if (this.IsInfinity) |
| | | 1100 | | return this; |
| | | 1101 | | |
| | | 1102 | | ECFieldElement Y1 = this.RawYCoord; |
| | | 1103 | | if (Y1.IsZero) |
| | | 1104 | | return this; |
| | | 1105 | | |
| | | 1106 | | ECCurve curve = this.Curve; |
| | | 1107 | | int coord = curve.CoordinateSystem; |
| | | 1108 | | |
| | | 1109 | | switch (coord) |
| | | 1110 | | { |
| | | 1111 | | case ECCurve.COORD_AFFINE: |
| | | 1112 | | { |
| | | 1113 | | ECFieldElement X1 = this.RawXCoord; |
| | | 1114 | | |
| | | 1115 | | ECFieldElement _2Y1 = Two(Y1); |
| | | 1116 | | ECFieldElement X = _2Y1.Square(); |
| | | 1117 | | ECFieldElement Z = Three(X1.Square()).Add(Curve.A); |
| | | 1118 | | ECFieldElement Y = Z.Square(); |
| | | 1119 | | |
| | | 1120 | | ECFieldElement d = Three(X1).Multiply(X).Subtract(Y); |
| | | 1121 | | if (d.IsZero) |
| | | 1122 | | { |
| | | 1123 | | return Curve.Infinity; |
| | | 1124 | | } |
| | | 1125 | | |
| | | 1126 | | ECFieldElement D = d.Multiply(_2Y1); |
| | | 1127 | | ECFieldElement I = D.Invert(); |
| | | 1128 | | ECFieldElement L1 = d.Multiply(I).Multiply(Z); |
| | | 1129 | | ECFieldElement L2 = X.Square().Multiply(I).Subtract(L1); |
| | | 1130 | | |
| | | 1131 | | ECFieldElement X4 = (L2.Subtract(L1)).Multiply(L1.Add(L2)).Add(X1); |
| | | 1132 | | ECFieldElement Y4 = (X1.Subtract(X4)).Multiply(L2).Subtract(Y1); |
| | | 1133 | | return new FpPoint(Curve, X4, Y4, IsCompressed); |
| | | 1134 | | } |
| | | 1135 | | case ECCurve.COORD_JACOBIAN_MODIFIED: |
| | | 1136 | | { |
| | | 1137 | | return TwiceJacobianModified(false).Add(this); |
| | | 1138 | | } |
| | | 1139 | | default: |
| | | 1140 | | { |
| | | 1141 | | // NOTE: Be careful about recursions between TwicePlus and ThreeTimes |
| | | 1142 | | return Twice().Add(this); |
| | | 1143 | | } |
| | | 1144 | | } |
| | | 1145 | | } |
| | | 1146 | | |
| | | 1147 | | public override ECPoint TimesPow2(int e) |
| | | 1148 | | { |
| | | 1149 | | if (e < 0) |
| | | 1150 | | throw new ArgumentException("cannot be negative", "e"); |
| | | 1151 | | if (e == 0 || this.IsInfinity) |
| | | 1152 | | return this; |
| | | 1153 | | if (e == 1) |
| | | 1154 | | return Twice(); |
| | | 1155 | | |
| | | 1156 | | ECCurve curve = this.Curve; |
| | | 1157 | | |
| | | 1158 | | ECFieldElement Y1 = this.RawYCoord; |
| | | 1159 | | if (Y1.IsZero) |
| | | 1160 | | return curve.Infinity; |
| | | 1161 | | |
| | | 1162 | | int coord = curve.CoordinateSystem; |
| | | 1163 | | |
| | | 1164 | | ECFieldElement W1 = curve.A; |
| | | 1165 | | ECFieldElement X1 = this.RawXCoord; |
| | | 1166 | | ECFieldElement Z1 = this.RawZCoords.Length < 1 ? curve.FromBigInteger(BigInteger.One) : this.RawZCoords[0]; |
| | | 1167 | | |
| | | 1168 | | if (!Z1.IsOne) |
| | | 1169 | | { |
| | | 1170 | | switch (coord) |
| | | 1171 | | { |
| | | 1172 | | case ECCurve.COORD_HOMOGENEOUS: |
| | | 1173 | | ECFieldElement Z1Sq = Z1.Square(); |
| | | 1174 | | X1 = X1.Multiply(Z1); |
| | | 1175 | | Y1 = Y1.Multiply(Z1Sq); |
| | | 1176 | | W1 = CalculateJacobianModifiedW(Z1, Z1Sq); |
| | | 1177 | | break; |
| | | 1178 | | case ECCurve.COORD_JACOBIAN: |
| | | 1179 | | W1 = CalculateJacobianModifiedW(Z1, null); |
| | | 1180 | | break; |
| | | 1181 | | case ECCurve.COORD_JACOBIAN_MODIFIED: |
| | | 1182 | | W1 = GetJacobianModifiedW(); |
| | | 1183 | | break; |
| | | 1184 | | } |
| | | 1185 | | } |
| | | 1186 | | |
| | | 1187 | | for (int i = 0; i < e; ++i) |
| | | 1188 | | { |
| | | 1189 | | if (Y1.IsZero) |
| | | 1190 | | return curve.Infinity; |
| | | 1191 | | |
| | | 1192 | | ECFieldElement X1Squared = X1.Square(); |
| | | 1193 | | ECFieldElement M = Three(X1Squared); |
| | | 1194 | | ECFieldElement _2Y1 = Two(Y1); |
| | | 1195 | | ECFieldElement _2Y1Squared = _2Y1.Multiply(Y1); |
| | | 1196 | | ECFieldElement S = Two(X1.Multiply(_2Y1Squared)); |
| | | 1197 | | ECFieldElement _4T = _2Y1Squared.Square(); |
| | | 1198 | | ECFieldElement _8T = Two(_4T); |
| | | 1199 | | |
| | | 1200 | | if (!W1.IsZero) |
| | | 1201 | | { |
| | | 1202 | | M = M.Add(W1); |
| | | 1203 | | W1 = Two(_8T.Multiply(W1)); |
| | | 1204 | | } |
| | | 1205 | | |
| | | 1206 | | X1 = M.Square().Subtract(Two(S)); |
| | | 1207 | | Y1 = M.Multiply(S.Subtract(X1)).Subtract(_8T); |
| | | 1208 | | Z1 = Z1.IsOne ? _2Y1 : _2Y1.Multiply(Z1); |
| | | 1209 | | } |
| | | 1210 | | |
| | | 1211 | | switch (coord) |
| | | 1212 | | { |
| | | 1213 | | case ECCurve.COORD_AFFINE: |
| | | 1214 | | ECFieldElement zInv = Z1.Invert(), zInv2 = zInv.Square(), zInv3 = zInv2.Multiply(zInv); |
| | | 1215 | | return new FpPoint(curve, X1.Multiply(zInv2), Y1.Multiply(zInv3), IsCompressed); |
| | | 1216 | | case ECCurve.COORD_HOMOGENEOUS: |
| | | 1217 | | X1 = X1.Multiply(Z1); |
| | | 1218 | | Z1 = Z1.Multiply(Z1.Square()); |
| | | 1219 | | return new FpPoint(curve, X1, Y1, new ECFieldElement[] { Z1 }, IsCompressed); |
| | | 1220 | | case ECCurve.COORD_JACOBIAN: |
| | | 1221 | | return new FpPoint(curve, X1, Y1, new ECFieldElement[] { Z1 }, IsCompressed); |
| | | 1222 | | case ECCurve.COORD_JACOBIAN_MODIFIED: |
| | | 1223 | | return new FpPoint(curve, X1, Y1, new ECFieldElement[] { Z1, W1 }, IsCompressed); |
| | | 1224 | | default: |
| | | 1225 | | throw new InvalidOperationException("unsupported coordinate system"); |
| | | 1226 | | } |
| | | 1227 | | } |
| | | 1228 | | |
| | | 1229 | | protected virtual ECFieldElement Two(ECFieldElement x) |
| | | 1230 | | { |
| | | 1231 | | return x.Add(x); |
| | | 1232 | | } |
| | | 1233 | | |
| | | 1234 | | protected virtual ECFieldElement Three(ECFieldElement x) |
| | | 1235 | | { |
| | | 1236 | | return Two(x).Add(x); |
| | | 1237 | | } |
| | | 1238 | | |
| | | 1239 | | protected virtual ECFieldElement Four(ECFieldElement x) |
| | | 1240 | | { |
| | | 1241 | | return Two(Two(x)); |
| | | 1242 | | } |
| | | 1243 | | |
| | | 1244 | | protected virtual ECFieldElement Eight(ECFieldElement x) |
| | | 1245 | | { |
| | | 1246 | | return Four(Two(x)); |
| | | 1247 | | } |
| | | 1248 | | |
| | | 1249 | | protected virtual ECFieldElement DoubleProductFromSquares(ECFieldElement a, ECFieldElement b, |
| | | 1250 | | ECFieldElement aSquared, ECFieldElement bSquared) |
| | | 1251 | | { |
| | | 1252 | | /* |
| | | 1253 | | * NOTE: If squaring in the field is faster than multiplication, then this is a quicker |
| | | 1254 | | * way to calculate 2.A.B, if A^2 and B^2 are already known. |
| | | 1255 | | */ |
| | | 1256 | | return a.Add(b).Square().Subtract(aSquared).Subtract(bSquared); |
| | | 1257 | | } |
| | | 1258 | | |
| | | 1259 | | public override ECPoint Negate() |
| | | 1260 | | { |
| | | 1261 | | if (IsInfinity) |
| | | 1262 | | return this; |
| | | 1263 | | |
| | | 1264 | | ECCurve curve = Curve; |
| | | 1265 | | int coord = curve.CoordinateSystem; |
| | | 1266 | | |
| | | 1267 | | if (ECCurve.COORD_AFFINE != coord) |
| | | 1268 | | { |
| | | 1269 | | return new FpPoint(curve, RawXCoord, RawYCoord.Negate(), RawZCoords, IsCompressed); |
| | | 1270 | | } |
| | | 1271 | | |
| | | 1272 | | return new FpPoint(curve, RawXCoord, RawYCoord.Negate(), IsCompressed); |
| | | 1273 | | } |
| | | 1274 | | |
| | | 1275 | | protected virtual ECFieldElement CalculateJacobianModifiedW(ECFieldElement Z, ECFieldElement ZSquared) |
| | | 1276 | | { |
| | | 1277 | | ECFieldElement a4 = this.Curve.A; |
| | | 1278 | | if (a4.IsZero || Z.IsOne) |
| | | 1279 | | return a4; |
| | | 1280 | | |
| | | 1281 | | if (ZSquared == null) |
| | | 1282 | | { |
| | | 1283 | | ZSquared = Z.Square(); |
| | | 1284 | | } |
| | | 1285 | | |
| | | 1286 | | ECFieldElement W = ZSquared.Square(); |
| | | 1287 | | ECFieldElement a4Neg = a4.Negate(); |
| | | 1288 | | if (a4Neg.BitLength < a4.BitLength) |
| | | 1289 | | { |
| | | 1290 | | W = W.Multiply(a4Neg).Negate(); |
| | | 1291 | | } |
| | | 1292 | | else |
| | | 1293 | | { |
| | | 1294 | | W = W.Multiply(a4); |
| | | 1295 | | } |
| | | 1296 | | return W; |
| | | 1297 | | } |
| | | 1298 | | |
| | | 1299 | | protected virtual ECFieldElement GetJacobianModifiedW() |
| | | 1300 | | { |
| | | 1301 | | ECFieldElement[] ZZ = this.RawZCoords; |
| | | 1302 | | ECFieldElement W = ZZ[1]; |
| | | 1303 | | if (W == null) |
| | | 1304 | | { |
| | | 1305 | | // NOTE: Rarely, TwicePlus will result in the need for a lazy W1 calculation here |
| | | 1306 | | ZZ[1] = W = CalculateJacobianModifiedW(ZZ[0], null); |
| | | 1307 | | } |
| | | 1308 | | return W; |
| | | 1309 | | } |
| | | 1310 | | |
| | | 1311 | | protected virtual FpPoint TwiceJacobianModified(bool calculateW) |
| | | 1312 | | { |
| | | 1313 | | ECFieldElement X1 = this.RawXCoord, Y1 = this.RawYCoord, Z1 = this.RawZCoords[0], W1 = GetJacobianModifiedW( |
| | | 1314 | | |
| | | 1315 | | ECFieldElement X1Squared = X1.Square(); |
| | | 1316 | | ECFieldElement M = Three(X1Squared).Add(W1); |
| | | 1317 | | ECFieldElement _2Y1 = Two(Y1); |
| | | 1318 | | ECFieldElement _2Y1Squared = _2Y1.Multiply(Y1); |
| | | 1319 | | ECFieldElement S = Two(X1.Multiply(_2Y1Squared)); |
| | | 1320 | | ECFieldElement X3 = M.Square().Subtract(Two(S)); |
| | | 1321 | | ECFieldElement _4T = _2Y1Squared.Square(); |
| | | 1322 | | ECFieldElement _8T = Two(_4T); |
| | | 1323 | | ECFieldElement Y3 = M.Multiply(S.Subtract(X3)).Subtract(_8T); |
| | | 1324 | | ECFieldElement W3 = calculateW ? Two(_8T.Multiply(W1)) : null; |
| | | 1325 | | ECFieldElement Z3 = Z1.IsOne ? _2Y1 : _2Y1.Multiply(Z1); |
| | | 1326 | | |
| | | 1327 | | return new FpPoint(this.Curve, X3, Y3, new ECFieldElement[] { Z3, W3 }, IsCompressed); |
| | | 1328 | | } |
| | | 1329 | | } |
| | | 1330 | | |
| | | 1331 | | internal abstract class AbstractF2mPoint |
| | | 1332 | | : ECPointBase |
| | | 1333 | | { |
| | | 1334 | | protected AbstractF2mPoint(ECCurve curve, ECFieldElement x, ECFieldElement y, bool withCompression) |
| | | 1335 | | : base(curve, x, y, withCompression) |
| | | 1336 | | { |
| | | 1337 | | } |
| | | 1338 | | |
| | | 1339 | | protected AbstractF2mPoint(ECCurve curve, ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, bool withComp |
| | | 1340 | | : base(curve, x, y, zs, withCompression) |
| | | 1341 | | { |
| | | 1342 | | } |
| | | 1343 | | |
| | | 1344 | | protected override bool SatisfiesCurveEquation() |
| | | 1345 | | { |
| | | 1346 | | ECCurve curve = Curve; |
| | | 1347 | | ECFieldElement X = this.RawXCoord, Y = this.RawYCoord, A = curve.A, B = curve.B; |
| | | 1348 | | ECFieldElement lhs, rhs; |
| | | 1349 | | |
| | | 1350 | | int coord = curve.CoordinateSystem; |
| | | 1351 | | if (coord == ECCurve.COORD_LAMBDA_PROJECTIVE) |
| | | 1352 | | { |
| | | 1353 | | ECFieldElement Z = this.RawZCoords[0]; |
| | | 1354 | | bool ZIsOne = Z.IsOne; |
| | | 1355 | | |
| | | 1356 | | if (X.IsZero) |
| | | 1357 | | { |
| | | 1358 | | // NOTE: For x == 0, we expect the affine-y instead of the lambda-y |
| | | 1359 | | lhs = Y.Square(); |
| | | 1360 | | rhs = B; |
| | | 1361 | | if (!ZIsOne) |
| | | 1362 | | { |
| | | 1363 | | ECFieldElement Z2 = Z.Square(); |
| | | 1364 | | rhs = rhs.Multiply(Z2); |
| | | 1365 | | } |
| | | 1366 | | } |
| | | 1367 | | else |
| | | 1368 | | { |
| | | 1369 | | ECFieldElement L = Y, X2 = X.Square(); |
| | | 1370 | | if (ZIsOne) |
| | | 1371 | | { |
| | | 1372 | | lhs = L.Square().Add(L).Add(A); |
| | | 1373 | | rhs = X2.Square().Add(B); |
| | | 1374 | | } |
| | | 1375 | | else |
| | | 1376 | | { |
| | | 1377 | | ECFieldElement Z2 = Z.Square(), Z4 = Z2.Square(); |
| | | 1378 | | lhs = L.Add(Z).MultiplyPlusProduct(L, A, Z2); |
| | | 1379 | | // TODO If sqrt(b) is precomputed this can be simplified to a single square |
| | | 1380 | | rhs = X2.SquarePlusProduct(B, Z4); |
| | | 1381 | | } |
| | | 1382 | | lhs = lhs.Multiply(X2); |
| | | 1383 | | } |
| | | 1384 | | } |
| | | 1385 | | else |
| | | 1386 | | { |
| | | 1387 | | lhs = Y.Add(X).Multiply(Y); |
| | | 1388 | | |
| | | 1389 | | switch (coord) |
| | | 1390 | | { |
| | | 1391 | | case ECCurve.COORD_AFFINE: |
| | | 1392 | | break; |
| | | 1393 | | case ECCurve.COORD_HOMOGENEOUS: |
| | | 1394 | | { |
| | | 1395 | | ECFieldElement Z = this.RawZCoords[0]; |
| | | 1396 | | if (!Z.IsOne) |
| | | 1397 | | { |
| | | 1398 | | ECFieldElement Z2 = Z.Square(), Z3 = Z.Multiply(Z2); |
| | | 1399 | | lhs = lhs.Multiply(Z); |
| | | 1400 | | A = A.Multiply(Z); |
| | | 1401 | | B = B.Multiply(Z3); |
| | | 1402 | | } |
| | | 1403 | | break; |
| | | 1404 | | } |
| | | 1405 | | default: |
| | | 1406 | | throw new InvalidOperationException("unsupported coordinate system"); |
| | | 1407 | | } |
| | | 1408 | | |
| | | 1409 | | rhs = X.Add(A).Multiply(X.Square()).Add(B); |
| | | 1410 | | } |
| | | 1411 | | |
| | | 1412 | | return lhs.Equals(rhs); |
| | | 1413 | | } |
| | | 1414 | | |
| | | 1415 | | protected override bool SatisfiesOrder() |
| | | 1416 | | { |
| | | 1417 | | ECCurve curve = Curve; |
| | | 1418 | | BigInteger cofactor = curve.Cofactor; |
| | | 1419 | | if (BigInteger.Two.Equals(cofactor)) |
| | | 1420 | | { |
| | | 1421 | | /* |
| | | 1422 | | * Check that the trace of (X + A) is 0, then there exists a solution to L^2 + L = X + A, |
| | | 1423 | | * and so a halving is possible, so this point is the double of another. |
| | | 1424 | | */ |
| | | 1425 | | ECPoint N = this.Normalize(); |
| | | 1426 | | ECFieldElement X = N.AffineXCoord; |
| | | 1427 | | ECFieldElement rhs = X.Add(curve.A); |
| | | 1428 | | return ((AbstractF2mFieldElement)rhs).Trace() == 0; |
| | | 1429 | | } |
| | | 1430 | | if (BigInteger.ValueOf(4).Equals(cofactor)) |
| | | 1431 | | { |
| | | 1432 | | /* |
| | | 1433 | | * Solve L^2 + L = X + A to find the half of this point, if it exists (fail if not). |
| | | 1434 | | * Generate both possibilities for the square of the half-point's x-coordinate (w), |
| | | 1435 | | * and check if Tr(w + A) == 0 for at least one; then a second halving is possible |
| | | 1436 | | * (see comments for cofactor 2 above), so this point is four times another. |
| | | 1437 | | * |
| | | 1438 | | * Note: Tr(x^2) == Tr(x). |
| | | 1439 | | */ |
| | | 1440 | | ECPoint N = this.Normalize(); |
| | | 1441 | | ECFieldElement X = N.AffineXCoord; |
| | | 1442 | | ECFieldElement lambda = ((AbstractF2mCurve)curve).SolveQuadraticEquation(X.Add(curve.A)); |
| | | 1443 | | if (lambda == null) |
| | | 1444 | | return false; |
| | | 1445 | | |
| | | 1446 | | ECFieldElement w = X.Multiply(lambda).Add(N.AffineYCoord); |
| | | 1447 | | ECFieldElement t = w.Add(curve.A); |
| | | 1448 | | return ((AbstractF2mFieldElement)t).Trace() == 0 |
| | | 1449 | | || ((AbstractF2mFieldElement)(t.Add(X))).Trace() == 0; |
| | | 1450 | | } |
| | | 1451 | | |
| | | 1452 | | return base.SatisfiesOrder(); |
| | | 1453 | | } |
| | | 1454 | | |
| | | 1455 | | public override ECPoint ScaleX(ECFieldElement scale) |
| | | 1456 | | { |
| | | 1457 | | if (this.IsInfinity) |
| | | 1458 | | return this; |
| | | 1459 | | |
| | | 1460 | | switch (CurveCoordinateSystem) |
| | | 1461 | | { |
| | | 1462 | | case ECCurve.COORD_LAMBDA_AFFINE: |
| | | 1463 | | { |
| | | 1464 | | // Y is actually Lambda (X + Y/X) here |
| | | 1465 | | ECFieldElement X = RawXCoord, L = RawYCoord; |
| | | 1466 | | |
| | | 1467 | | ECFieldElement X2 = X.Multiply(scale); |
| | | 1468 | | ECFieldElement L2 = L.Add(X).Divide(scale).Add(X2); |
| | | 1469 | | |
| | | 1470 | | return Curve.CreateRawPoint(X, L2, RawZCoords, IsCompressed); |
| | | 1471 | | } |
| | | 1472 | | case ECCurve.COORD_LAMBDA_PROJECTIVE: |
| | | 1473 | | { |
| | | 1474 | | // Y is actually Lambda (X + Y/X) here |
| | | 1475 | | ECFieldElement X = RawXCoord, L = RawYCoord, Z = RawZCoords[0]; |
| | | 1476 | | |
| | | 1477 | | // We scale the Z coordinate also, to avoid an inversion |
| | | 1478 | | ECFieldElement X2 = X.Multiply(scale.Square()); |
| | | 1479 | | ECFieldElement L2 = L.Add(X).Add(X2); |
| | | 1480 | | ECFieldElement Z2 = Z.Multiply(scale); |
| | | 1481 | | |
| | | 1482 | | return Curve.CreateRawPoint(X, L2, new ECFieldElement[] { Z2 }, IsCompressed); |
| | | 1483 | | } |
| | | 1484 | | default: |
| | | 1485 | | { |
| | | 1486 | | return base.ScaleX(scale); |
| | | 1487 | | } |
| | | 1488 | | } |
| | | 1489 | | } |
| | | 1490 | | |
| | | 1491 | | public override ECPoint ScaleY(ECFieldElement scale) |
| | | 1492 | | { |
| | | 1493 | | if (this.IsInfinity) |
| | | 1494 | | return this; |
| | | 1495 | | |
| | | 1496 | | switch (CurveCoordinateSystem) |
| | | 1497 | | { |
| | | 1498 | | case ECCurve.COORD_LAMBDA_AFFINE: |
| | | 1499 | | case ECCurve.COORD_LAMBDA_PROJECTIVE: |
| | | 1500 | | { |
| | | 1501 | | ECFieldElement X = RawXCoord, L = RawYCoord; |
| | | 1502 | | |
| | | 1503 | | // Y is actually Lambda (X + Y/X) here |
| | | 1504 | | ECFieldElement L2 = L.Add(X).Multiply(scale).Add(X); |
| | | 1505 | | |
| | | 1506 | | return Curve.CreateRawPoint(X, L2, RawZCoords, IsCompressed); |
| | | 1507 | | } |
| | | 1508 | | default: |
| | | 1509 | | { |
| | | 1510 | | return base.ScaleY(scale); |
| | | 1511 | | } |
| | | 1512 | | } |
| | | 1513 | | } |
| | | 1514 | | |
| | | 1515 | | public override ECPoint Subtract(ECPoint b) |
| | | 1516 | | { |
| | | 1517 | | if (b.IsInfinity) |
| | | 1518 | | return this; |
| | | 1519 | | |
| | | 1520 | | // Add -b |
| | | 1521 | | return Add(b.Negate()); |
| | | 1522 | | } |
| | | 1523 | | |
| | | 1524 | | public virtual AbstractF2mPoint Tau() |
| | | 1525 | | { |
| | | 1526 | | if (this.IsInfinity) |
| | | 1527 | | return this; |
| | | 1528 | | |
| | | 1529 | | ECCurve curve = this.Curve; |
| | | 1530 | | int coord = curve.CoordinateSystem; |
| | | 1531 | | |
| | | 1532 | | ECFieldElement X1 = this.RawXCoord; |
| | | 1533 | | |
| | | 1534 | | switch (coord) |
| | | 1535 | | { |
| | | 1536 | | case ECCurve.COORD_AFFINE: |
| | | 1537 | | case ECCurve.COORD_LAMBDA_AFFINE: |
| | | 1538 | | { |
| | | 1539 | | ECFieldElement Y1 = this.RawYCoord; |
| | | 1540 | | return (AbstractF2mPoint)curve.CreateRawPoint(X1.Square(), Y1.Square(), IsCompressed); |
| | | 1541 | | } |
| | | 1542 | | case ECCurve.COORD_HOMOGENEOUS: |
| | | 1543 | | case ECCurve.COORD_LAMBDA_PROJECTIVE: |
| | | 1544 | | { |
| | | 1545 | | ECFieldElement Y1 = this.RawYCoord, Z1 = this.RawZCoords[0]; |
| | | 1546 | | return (AbstractF2mPoint)curve.CreateRawPoint(X1.Square(), Y1.Square(), |
| | | 1547 | | new ECFieldElement[] { Z1.Square() }, IsCompressed); |
| | | 1548 | | } |
| | | 1549 | | default: |
| | | 1550 | | { |
| | | 1551 | | throw new InvalidOperationException("unsupported coordinate system"); |
| | | 1552 | | } |
| | | 1553 | | } |
| | | 1554 | | } |
| | | 1555 | | |
| | | 1556 | | public virtual AbstractF2mPoint TauPow(int pow) |
| | | 1557 | | { |
| | | 1558 | | if (this.IsInfinity) |
| | | 1559 | | return this; |
| | | 1560 | | |
| | | 1561 | | ECCurve curve = this.Curve; |
| | | 1562 | | int coord = curve.CoordinateSystem; |
| | | 1563 | | |
| | | 1564 | | ECFieldElement X1 = this.RawXCoord; |
| | | 1565 | | |
| | | 1566 | | switch (coord) |
| | | 1567 | | { |
| | | 1568 | | case ECCurve.COORD_AFFINE: |
| | | 1569 | | case ECCurve.COORD_LAMBDA_AFFINE: |
| | | 1570 | | { |
| | | 1571 | | ECFieldElement Y1 = this.RawYCoord; |
| | | 1572 | | return (AbstractF2mPoint)curve.CreateRawPoint(X1.SquarePow(pow), Y1.SquarePow(pow), IsCompressed); |
| | | 1573 | | } |
| | | 1574 | | case ECCurve.COORD_HOMOGENEOUS: |
| | | 1575 | | case ECCurve.COORD_LAMBDA_PROJECTIVE: |
| | | 1576 | | { |
| | | 1577 | | ECFieldElement Y1 = this.RawYCoord, Z1 = this.RawZCoords[0]; |
| | | 1578 | | return (AbstractF2mPoint)curve.CreateRawPoint(X1.SquarePow(pow), Y1.SquarePow(pow), |
| | | 1579 | | new ECFieldElement[] { Z1.SquarePow(pow) }, IsCompressed); |
| | | 1580 | | } |
| | | 1581 | | default: |
| | | 1582 | | { |
| | | 1583 | | throw new InvalidOperationException("unsupported coordinate system"); |
| | | 1584 | | } |
| | | 1585 | | } |
| | | 1586 | | } |
| | | 1587 | | } |
| | | 1588 | | |
| | | 1589 | | /** |
| | | 1590 | | * Elliptic curve points over F2m |
| | | 1591 | | */ |
| | | 1592 | | internal class F2mPoint |
| | | 1593 | | : AbstractF2mPoint |
| | | 1594 | | { |
| | | 1595 | | /** |
| | | 1596 | | * @param curve base curve |
| | | 1597 | | * @param x x point |
| | | 1598 | | * @param y y point |
| | | 1599 | | */ |
| | | 1600 | | public F2mPoint( |
| | | 1601 | | ECCurve curve, |
| | | 1602 | | ECFieldElement x, |
| | | 1603 | | ECFieldElement y) |
| | 0 | 1604 | | : this(curve, x, y, false) |
| | 0 | 1605 | | { |
| | 0 | 1606 | | } |
| | | 1607 | | |
| | | 1608 | | /** |
| | | 1609 | | * @param curve base curve |
| | | 1610 | | * @param x x point |
| | | 1611 | | * @param y y point |
| | | 1612 | | * @param withCompression true if encode with point compression. |
| | | 1613 | | */ |
| | | 1614 | | public F2mPoint( |
| | | 1615 | | ECCurve curve, |
| | | 1616 | | ECFieldElement x, |
| | | 1617 | | ECFieldElement y, |
| | | 1618 | | bool withCompression) |
| | 0 | 1619 | | : base(curve, x, y, withCompression) |
| | 0 | 1620 | | { |
| | 0 | 1621 | | if ((x == null) != (y == null)) |
| | 0 | 1622 | | { |
| | 0 | 1623 | | throw new ArgumentException("Exactly one of the field elements is null"); |
| | | 1624 | | } |
| | | 1625 | | |
| | 0 | 1626 | | if (x != null) |
| | 0 | 1627 | | { |
| | | 1628 | | // Check if x and y are elements of the same field |
| | 0 | 1629 | | F2mFieldElement.CheckFieldElements(x, y); |
| | | 1630 | | |
| | | 1631 | | // Check if x and a are elements of the same field |
| | 0 | 1632 | | if (curve != null) |
| | 0 | 1633 | | { |
| | 0 | 1634 | | F2mFieldElement.CheckFieldElements(x, curve.A); |
| | 0 | 1635 | | } |
| | 0 | 1636 | | } |
| | 0 | 1637 | | } |
| | | 1638 | | |
| | | 1639 | | internal F2mPoint(ECCurve curve, ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, bool withCompression) |
| | 0 | 1640 | | : base(curve, x, y, zs, withCompression) |
| | 0 | 1641 | | { |
| | 0 | 1642 | | } |
| | | 1643 | | |
| | | 1644 | | protected override ECPoint Detach() |
| | 0 | 1645 | | { |
| | 0 | 1646 | | return new F2mPoint(null, AffineXCoord, AffineYCoord, false); |
| | 0 | 1647 | | } |
| | | 1648 | | |
| | | 1649 | | public override ECFieldElement YCoord |
| | | 1650 | | { |
| | | 1651 | | get |
| | 0 | 1652 | | { |
| | 0 | 1653 | | int coord = this.CurveCoordinateSystem; |
| | | 1654 | | |
| | 0 | 1655 | | switch (coord) |
| | | 1656 | | { |
| | | 1657 | | case ECCurve.COORD_LAMBDA_AFFINE: |
| | | 1658 | | case ECCurve.COORD_LAMBDA_PROJECTIVE: |
| | 0 | 1659 | | { |
| | 0 | 1660 | | ECFieldElement X = RawXCoord, L = RawYCoord; |
| | | 1661 | | |
| | 0 | 1662 | | if (this.IsInfinity || X.IsZero) |
| | 0 | 1663 | | return L; |
| | | 1664 | | |
| | | 1665 | | // Y is actually Lambda (X + Y/X) here; convert to affine value on the fly |
| | 0 | 1666 | | ECFieldElement Y = L.Add(X).Multiply(X); |
| | 0 | 1667 | | if (ECCurve.COORD_LAMBDA_PROJECTIVE == coord) |
| | 0 | 1668 | | { |
| | 0 | 1669 | | ECFieldElement Z = RawZCoords[0]; |
| | 0 | 1670 | | if (!Z.IsOne) |
| | 0 | 1671 | | { |
| | 0 | 1672 | | Y = Y.Divide(Z); |
| | 0 | 1673 | | } |
| | 0 | 1674 | | } |
| | 0 | 1675 | | return Y; |
| | | 1676 | | } |
| | | 1677 | | default: |
| | 0 | 1678 | | { |
| | 0 | 1679 | | return RawYCoord; |
| | | 1680 | | } |
| | | 1681 | | } |
| | 0 | 1682 | | } |
| | | 1683 | | } |
| | | 1684 | | |
| | | 1685 | | protected internal override bool CompressionYTilde |
| | | 1686 | | { |
| | | 1687 | | get |
| | 0 | 1688 | | { |
| | 0 | 1689 | | ECFieldElement X = this.RawXCoord; |
| | 0 | 1690 | | if (X.IsZero) |
| | 0 | 1691 | | { |
| | 0 | 1692 | | return false; |
| | | 1693 | | } |
| | | 1694 | | |
| | 0 | 1695 | | ECFieldElement Y = this.RawYCoord; |
| | | 1696 | | |
| | 0 | 1697 | | switch (this.CurveCoordinateSystem) |
| | | 1698 | | { |
| | | 1699 | | case ECCurve.COORD_LAMBDA_AFFINE: |
| | | 1700 | | case ECCurve.COORD_LAMBDA_PROJECTIVE: |
| | 0 | 1701 | | { |
| | | 1702 | | // Y is actually Lambda (X + Y/X) here |
| | 0 | 1703 | | return Y.TestBitZero() != X.TestBitZero(); |
| | | 1704 | | } |
| | | 1705 | | default: |
| | 0 | 1706 | | { |
| | 0 | 1707 | | return Y.Divide(X).TestBitZero(); |
| | | 1708 | | } |
| | | 1709 | | } |
| | 0 | 1710 | | } |
| | | 1711 | | } |
| | | 1712 | | |
| | | 1713 | | public override ECPoint Add(ECPoint b) |
| | 0 | 1714 | | { |
| | 0 | 1715 | | if (this.IsInfinity) |
| | 0 | 1716 | | return b; |
| | 0 | 1717 | | if (b.IsInfinity) |
| | 0 | 1718 | | return this; |
| | | 1719 | | |
| | 0 | 1720 | | ECCurve curve = this.Curve; |
| | 0 | 1721 | | int coord = curve.CoordinateSystem; |
| | | 1722 | | |
| | 0 | 1723 | | ECFieldElement X1 = this.RawXCoord; |
| | 0 | 1724 | | ECFieldElement X2 = b.RawXCoord; |
| | | 1725 | | |
| | 0 | 1726 | | switch (coord) |
| | | 1727 | | { |
| | | 1728 | | case ECCurve.COORD_AFFINE: |
| | 0 | 1729 | | { |
| | 0 | 1730 | | ECFieldElement Y1 = this.RawYCoord; |
| | 0 | 1731 | | ECFieldElement Y2 = b.RawYCoord; |
| | | 1732 | | |
| | 0 | 1733 | | ECFieldElement dx = X1.Add(X2), dy = Y1.Add(Y2); |
| | 0 | 1734 | | if (dx.IsZero) |
| | 0 | 1735 | | { |
| | 0 | 1736 | | if (dy.IsZero) |
| | 0 | 1737 | | { |
| | 0 | 1738 | | return Twice(); |
| | | 1739 | | } |
| | | 1740 | | |
| | 0 | 1741 | | return curve.Infinity; |
| | | 1742 | | } |
| | | 1743 | | |
| | 0 | 1744 | | ECFieldElement L = dy.Divide(dx); |
| | | 1745 | | |
| | 0 | 1746 | | ECFieldElement X3 = L.Square().Add(L).Add(dx).Add(curve.A); |
| | 0 | 1747 | | ECFieldElement Y3 = L.Multiply(X1.Add(X3)).Add(X3).Add(Y1); |
| | | 1748 | | |
| | 0 | 1749 | | return new F2mPoint(curve, X3, Y3, IsCompressed); |
| | | 1750 | | } |
| | | 1751 | | case ECCurve.COORD_HOMOGENEOUS: |
| | 0 | 1752 | | { |
| | 0 | 1753 | | ECFieldElement Y1 = this.RawYCoord, Z1 = this.RawZCoords[0]; |
| | 0 | 1754 | | ECFieldElement Y2 = b.RawYCoord, Z2 = b.RawZCoords[0]; |
| | | 1755 | | |
| | 0 | 1756 | | bool Z1IsOne = Z1.IsOne; |
| | 0 | 1757 | | ECFieldElement U1 = Y2, V1 = X2; |
| | 0 | 1758 | | if (!Z1IsOne) |
| | 0 | 1759 | | { |
| | 0 | 1760 | | U1 = U1.Multiply(Z1); |
| | 0 | 1761 | | V1 = V1.Multiply(Z1); |
| | 0 | 1762 | | } |
| | | 1763 | | |
| | 0 | 1764 | | bool Z2IsOne = Z2.IsOne; |
| | 0 | 1765 | | ECFieldElement U2 = Y1, V2 = X1; |
| | 0 | 1766 | | if (!Z2IsOne) |
| | 0 | 1767 | | { |
| | 0 | 1768 | | U2 = U2.Multiply(Z2); |
| | 0 | 1769 | | V2 = V2.Multiply(Z2); |
| | 0 | 1770 | | } |
| | | 1771 | | |
| | 0 | 1772 | | ECFieldElement U = U1.Add(U2); |
| | 0 | 1773 | | ECFieldElement V = V1.Add(V2); |
| | | 1774 | | |
| | 0 | 1775 | | if (V.IsZero) |
| | 0 | 1776 | | { |
| | 0 | 1777 | | if (U.IsZero) |
| | 0 | 1778 | | { |
| | 0 | 1779 | | return Twice(); |
| | | 1780 | | } |
| | | 1781 | | |
| | 0 | 1782 | | return curve.Infinity; |
| | | 1783 | | } |
| | | 1784 | | |
| | 0 | 1785 | | ECFieldElement VSq = V.Square(); |
| | 0 | 1786 | | ECFieldElement VCu = VSq.Multiply(V); |
| | 0 | 1787 | | ECFieldElement W = Z1IsOne ? Z2 : Z2IsOne ? Z1 : Z1.Multiply(Z2); |
| | 0 | 1788 | | ECFieldElement uv = U.Add(V); |
| | 0 | 1789 | | ECFieldElement A = uv.MultiplyPlusProduct(U, VSq, curve.A).Multiply(W).Add(VCu); |
| | | 1790 | | |
| | 0 | 1791 | | ECFieldElement X3 = V.Multiply(A); |
| | 0 | 1792 | | ECFieldElement VSqZ2 = Z2IsOne ? VSq : VSq.Multiply(Z2); |
| | 0 | 1793 | | ECFieldElement Y3 = U.MultiplyPlusProduct(X1, V, Y1).MultiplyPlusProduct(VSqZ2, uv, A); |
| | 0 | 1794 | | ECFieldElement Z3 = VCu.Multiply(W); |
| | | 1795 | | |
| | 0 | 1796 | | return new F2mPoint(curve, X3, Y3, new ECFieldElement[] { Z3 }, IsCompressed); |
| | | 1797 | | } |
| | | 1798 | | case ECCurve.COORD_LAMBDA_PROJECTIVE: |
| | 0 | 1799 | | { |
| | 0 | 1800 | | if (X1.IsZero) |
| | 0 | 1801 | | { |
| | 0 | 1802 | | if (X2.IsZero) |
| | 0 | 1803 | | return curve.Infinity; |
| | | 1804 | | |
| | 0 | 1805 | | return b.Add(this); |
| | | 1806 | | } |
| | | 1807 | | |
| | 0 | 1808 | | ECFieldElement L1 = this.RawYCoord, Z1 = this.RawZCoords[0]; |
| | 0 | 1809 | | ECFieldElement L2 = b.RawYCoord, Z2 = b.RawZCoords[0]; |
| | | 1810 | | |
| | 0 | 1811 | | bool Z1IsOne = Z1.IsOne; |
| | 0 | 1812 | | ECFieldElement U2 = X2, S2 = L2; |
| | 0 | 1813 | | if (!Z1IsOne) |
| | 0 | 1814 | | { |
| | 0 | 1815 | | U2 = U2.Multiply(Z1); |
| | 0 | 1816 | | S2 = S2.Multiply(Z1); |
| | 0 | 1817 | | } |
| | | 1818 | | |
| | 0 | 1819 | | bool Z2IsOne = Z2.IsOne; |
| | 0 | 1820 | | ECFieldElement U1 = X1, S1 = L1; |
| | 0 | 1821 | | if (!Z2IsOne) |
| | 0 | 1822 | | { |
| | 0 | 1823 | | U1 = U1.Multiply(Z2); |
| | 0 | 1824 | | S1 = S1.Multiply(Z2); |
| | 0 | 1825 | | } |
| | | 1826 | | |
| | 0 | 1827 | | ECFieldElement A = S1.Add(S2); |
| | 0 | 1828 | | ECFieldElement B = U1.Add(U2); |
| | | 1829 | | |
| | 0 | 1830 | | if (B.IsZero) |
| | 0 | 1831 | | { |
| | 0 | 1832 | | if (A.IsZero) |
| | 0 | 1833 | | { |
| | 0 | 1834 | | return Twice(); |
| | | 1835 | | } |
| | | 1836 | | |
| | 0 | 1837 | | return curve.Infinity; |
| | | 1838 | | } |
| | | 1839 | | |
| | | 1840 | | ECFieldElement X3, L3, Z3; |
| | 0 | 1841 | | if (X2.IsZero) |
| | 0 | 1842 | | { |
| | | 1843 | | // TODO This can probably be optimized quite a bit |
| | 0 | 1844 | | ECPoint p = this.Normalize(); |
| | 0 | 1845 | | X1 = p.RawXCoord; |
| | 0 | 1846 | | ECFieldElement Y1 = p.YCoord; |
| | | 1847 | | |
| | 0 | 1848 | | ECFieldElement Y2 = L2; |
| | 0 | 1849 | | ECFieldElement L = Y1.Add(Y2).Divide(X1); |
| | | 1850 | | |
| | 0 | 1851 | | X3 = L.Square().Add(L).Add(X1).Add(curve.A); |
| | 0 | 1852 | | if (X3.IsZero) |
| | 0 | 1853 | | { |
| | 0 | 1854 | | return new F2mPoint(curve, X3, curve.B.Sqrt(), IsCompressed); |
| | | 1855 | | } |
| | | 1856 | | |
| | 0 | 1857 | | ECFieldElement Y3 = L.Multiply(X1.Add(X3)).Add(X3).Add(Y1); |
| | 0 | 1858 | | L3 = Y3.Divide(X3).Add(X3); |
| | 0 | 1859 | | Z3 = curve.FromBigInteger(BigInteger.One); |
| | 0 | 1860 | | } |
| | | 1861 | | else |
| | 0 | 1862 | | { |
| | 0 | 1863 | | B = B.Square(); |
| | | 1864 | | |
| | 0 | 1865 | | ECFieldElement AU1 = A.Multiply(U1); |
| | 0 | 1866 | | ECFieldElement AU2 = A.Multiply(U2); |
| | | 1867 | | |
| | 0 | 1868 | | X3 = AU1.Multiply(AU2); |
| | 0 | 1869 | | if (X3.IsZero) |
| | 0 | 1870 | | { |
| | 0 | 1871 | | return new F2mPoint(curve, X3, curve.B.Sqrt(), IsCompressed); |
| | | 1872 | | } |
| | | 1873 | | |
| | 0 | 1874 | | ECFieldElement ABZ2 = A.Multiply(B); |
| | 0 | 1875 | | if (!Z2IsOne) |
| | 0 | 1876 | | { |
| | 0 | 1877 | | ABZ2 = ABZ2.Multiply(Z2); |
| | 0 | 1878 | | } |
| | | 1879 | | |
| | 0 | 1880 | | L3 = AU2.Add(B).SquarePlusProduct(ABZ2, L1.Add(Z1)); |
| | | 1881 | | |
| | 0 | 1882 | | Z3 = ABZ2; |
| | 0 | 1883 | | if (!Z1IsOne) |
| | 0 | 1884 | | { |
| | 0 | 1885 | | Z3 = Z3.Multiply(Z1); |
| | 0 | 1886 | | } |
| | 0 | 1887 | | } |
| | | 1888 | | |
| | 0 | 1889 | | return new F2mPoint(curve, X3, L3, new ECFieldElement[] { Z3 }, IsCompressed); |
| | | 1890 | | } |
| | | 1891 | | default: |
| | 0 | 1892 | | { |
| | 0 | 1893 | | throw new InvalidOperationException("unsupported coordinate system"); |
| | | 1894 | | } |
| | | 1895 | | } |
| | 0 | 1896 | | } |
| | | 1897 | | |
| | | 1898 | | /* (non-Javadoc) |
| | | 1899 | | * @see Org.BouncyCastle.Math.EC.ECPoint#twice() |
| | | 1900 | | */ |
| | | 1901 | | public override ECPoint Twice() |
| | 0 | 1902 | | { |
| | 0 | 1903 | | if (this.IsInfinity) |
| | 0 | 1904 | | return this; |
| | | 1905 | | |
| | 0 | 1906 | | ECCurve curve = this.Curve; |
| | | 1907 | | |
| | 0 | 1908 | | ECFieldElement X1 = this.RawXCoord; |
| | 0 | 1909 | | if (X1.IsZero) |
| | 0 | 1910 | | { |
| | | 1911 | | // A point with X == 0 is it's own additive inverse |
| | 0 | 1912 | | return curve.Infinity; |
| | | 1913 | | } |
| | | 1914 | | |
| | 0 | 1915 | | int coord = curve.CoordinateSystem; |
| | | 1916 | | |
| | 0 | 1917 | | switch (coord) |
| | | 1918 | | { |
| | | 1919 | | case ECCurve.COORD_AFFINE: |
| | 0 | 1920 | | { |
| | 0 | 1921 | | ECFieldElement Y1 = this.RawYCoord; |
| | | 1922 | | |
| | 0 | 1923 | | ECFieldElement L1 = Y1.Divide(X1).Add(X1); |
| | | 1924 | | |
| | 0 | 1925 | | ECFieldElement X3 = L1.Square().Add(L1).Add(curve.A); |
| | 0 | 1926 | | ECFieldElement Y3 = X1.SquarePlusProduct(X3, L1.AddOne()); |
| | | 1927 | | |
| | 0 | 1928 | | return new F2mPoint(curve, X3, Y3, IsCompressed); |
| | | 1929 | | } |
| | | 1930 | | case ECCurve.COORD_HOMOGENEOUS: |
| | 0 | 1931 | | { |
| | 0 | 1932 | | ECFieldElement Y1 = this.RawYCoord, Z1 = this.RawZCoords[0]; |
| | | 1933 | | |
| | 0 | 1934 | | bool Z1IsOne = Z1.IsOne; |
| | 0 | 1935 | | ECFieldElement X1Z1 = Z1IsOne ? X1 : X1.Multiply(Z1); |
| | 0 | 1936 | | ECFieldElement Y1Z1 = Z1IsOne ? Y1 : Y1.Multiply(Z1); |
| | | 1937 | | |
| | 0 | 1938 | | ECFieldElement X1Sq = X1.Square(); |
| | 0 | 1939 | | ECFieldElement S = X1Sq.Add(Y1Z1); |
| | 0 | 1940 | | ECFieldElement V = X1Z1; |
| | 0 | 1941 | | ECFieldElement vSquared = V.Square(); |
| | 0 | 1942 | | ECFieldElement sv = S.Add(V); |
| | 0 | 1943 | | ECFieldElement h = sv.MultiplyPlusProduct(S, vSquared, curve.A); |
| | | 1944 | | |
| | 0 | 1945 | | ECFieldElement X3 = V.Multiply(h); |
| | 0 | 1946 | | ECFieldElement Y3 = X1Sq.Square().MultiplyPlusProduct(V, h, sv); |
| | 0 | 1947 | | ECFieldElement Z3 = V.Multiply(vSquared); |
| | | 1948 | | |
| | 0 | 1949 | | return new F2mPoint(curve, X3, Y3, new ECFieldElement[] { Z3 }, IsCompressed); |
| | | 1950 | | } |
| | | 1951 | | case ECCurve.COORD_LAMBDA_PROJECTIVE: |
| | 0 | 1952 | | { |
| | 0 | 1953 | | ECFieldElement L1 = this.RawYCoord, Z1 = this.RawZCoords[0]; |
| | | 1954 | | |
| | 0 | 1955 | | bool Z1IsOne = Z1.IsOne; |
| | 0 | 1956 | | ECFieldElement L1Z1 = Z1IsOne ? L1 : L1.Multiply(Z1); |
| | 0 | 1957 | | ECFieldElement Z1Sq = Z1IsOne ? Z1 : Z1.Square(); |
| | 0 | 1958 | | ECFieldElement a = curve.A; |
| | 0 | 1959 | | ECFieldElement aZ1Sq = Z1IsOne ? a : a.Multiply(Z1Sq); |
| | 0 | 1960 | | ECFieldElement T = L1.Square().Add(L1Z1).Add(aZ1Sq); |
| | 0 | 1961 | | if (T.IsZero) |
| | 0 | 1962 | | { |
| | 0 | 1963 | | return new F2mPoint(curve, T, curve.B.Sqrt(), IsCompressed); |
| | | 1964 | | } |
| | | 1965 | | |
| | 0 | 1966 | | ECFieldElement X3 = T.Square(); |
| | 0 | 1967 | | ECFieldElement Z3 = Z1IsOne ? T : T.Multiply(Z1Sq); |
| | | 1968 | | |
| | 0 | 1969 | | ECFieldElement b = curve.B; |
| | | 1970 | | ECFieldElement L3; |
| | 0 | 1971 | | if (b.BitLength < (curve.FieldSize >> 1)) |
| | 0 | 1972 | | { |
| | 0 | 1973 | | ECFieldElement t1 = L1.Add(X1).Square(); |
| | | 1974 | | ECFieldElement t2; |
| | 0 | 1975 | | if (b.IsOne) |
| | 0 | 1976 | | { |
| | 0 | 1977 | | t2 = aZ1Sq.Add(Z1Sq).Square(); |
| | 0 | 1978 | | } |
| | | 1979 | | else |
| | 0 | 1980 | | { |
| | | 1981 | | // TODO Can be calculated with one square if we pre-compute sqrt(b) |
| | 0 | 1982 | | t2 = aZ1Sq.SquarePlusProduct(b, Z1Sq.Square()); |
| | 0 | 1983 | | } |
| | 0 | 1984 | | L3 = t1.Add(T).Add(Z1Sq).Multiply(t1).Add(t2).Add(X3); |
| | 0 | 1985 | | if (a.IsZero) |
| | 0 | 1986 | | { |
| | 0 | 1987 | | L3 = L3.Add(Z3); |
| | 0 | 1988 | | } |
| | 0 | 1989 | | else if (!a.IsOne) |
| | 0 | 1990 | | { |
| | 0 | 1991 | | L3 = L3.Add(a.AddOne().Multiply(Z3)); |
| | 0 | 1992 | | } |
| | 0 | 1993 | | } |
| | | 1994 | | else |
| | 0 | 1995 | | { |
| | 0 | 1996 | | ECFieldElement X1Z1 = Z1IsOne ? X1 : X1.Multiply(Z1); |
| | 0 | 1997 | | L3 = X1Z1.SquarePlusProduct(T, L1Z1).Add(X3).Add(Z3); |
| | 0 | 1998 | | } |
| | | 1999 | | |
| | 0 | 2000 | | return new F2mPoint(curve, X3, L3, new ECFieldElement[] { Z3 }, IsCompressed); |
| | | 2001 | | } |
| | | 2002 | | default: |
| | 0 | 2003 | | { |
| | 0 | 2004 | | throw new InvalidOperationException("unsupported coordinate system"); |
| | | 2005 | | } |
| | | 2006 | | } |
| | 0 | 2007 | | } |
| | | 2008 | | |
| | | 2009 | | public override ECPoint TwicePlus(ECPoint b) |
| | 0 | 2010 | | { |
| | 0 | 2011 | | if (this.IsInfinity) |
| | 0 | 2012 | | return b; |
| | 0 | 2013 | | if (b.IsInfinity) |
| | 0 | 2014 | | return Twice(); |
| | | 2015 | | |
| | 0 | 2016 | | ECCurve curve = this.Curve; |
| | | 2017 | | |
| | 0 | 2018 | | ECFieldElement X1 = this.RawXCoord; |
| | 0 | 2019 | | if (X1.IsZero) |
| | 0 | 2020 | | { |
| | | 2021 | | // A point with X == 0 is it's own additive inverse |
| | 0 | 2022 | | return b; |
| | | 2023 | | } |
| | | 2024 | | |
| | 0 | 2025 | | int coord = curve.CoordinateSystem; |
| | | 2026 | | |
| | 0 | 2027 | | switch (coord) |
| | | 2028 | | { |
| | | 2029 | | case ECCurve.COORD_LAMBDA_PROJECTIVE: |
| | 0 | 2030 | | { |
| | | 2031 | | // NOTE: twicePlus() only optimized for lambda-affine argument |
| | 0 | 2032 | | ECFieldElement X2 = b.RawXCoord, Z2 = b.RawZCoords[0]; |
| | 0 | 2033 | | if (X2.IsZero || !Z2.IsOne) |
| | 0 | 2034 | | { |
| | 0 | 2035 | | return Twice().Add(b); |
| | | 2036 | | } |
| | | 2037 | | |
| | 0 | 2038 | | ECFieldElement L1 = this.RawYCoord, Z1 = this.RawZCoords[0]; |
| | 0 | 2039 | | ECFieldElement L2 = b.RawYCoord; |
| | | 2040 | | |
| | 0 | 2041 | | ECFieldElement X1Sq = X1.Square(); |
| | 0 | 2042 | | ECFieldElement L1Sq = L1.Square(); |
| | 0 | 2043 | | ECFieldElement Z1Sq = Z1.Square(); |
| | 0 | 2044 | | ECFieldElement L1Z1 = L1.Multiply(Z1); |
| | | 2045 | | |
| | 0 | 2046 | | ECFieldElement T = curve.A.Multiply(Z1Sq).Add(L1Sq).Add(L1Z1); |
| | 0 | 2047 | | ECFieldElement L2plus1 = L2.AddOne(); |
| | 0 | 2048 | | ECFieldElement A = curve.A.Add(L2plus1).Multiply(Z1Sq).Add(L1Sq).MultiplyPlusProduct(T, X1Sq, Z1Sq); |
| | 0 | 2049 | | ECFieldElement X2Z1Sq = X2.Multiply(Z1Sq); |
| | 0 | 2050 | | ECFieldElement B = X2Z1Sq.Add(T).Square(); |
| | | 2051 | | |
| | 0 | 2052 | | if (B.IsZero) |
| | 0 | 2053 | | { |
| | 0 | 2054 | | if (A.IsZero) |
| | 0 | 2055 | | { |
| | 0 | 2056 | | return b.Twice(); |
| | | 2057 | | } |
| | | 2058 | | |
| | 0 | 2059 | | return curve.Infinity; |
| | | 2060 | | } |
| | | 2061 | | |
| | 0 | 2062 | | if (A.IsZero) |
| | 0 | 2063 | | { |
| | 0 | 2064 | | return new F2mPoint(curve, A, curve.B.Sqrt(), IsCompressed); |
| | | 2065 | | } |
| | | 2066 | | |
| | 0 | 2067 | | ECFieldElement X3 = A.Square().Multiply(X2Z1Sq); |
| | 0 | 2068 | | ECFieldElement Z3 = A.Multiply(B).Multiply(Z1Sq); |
| | 0 | 2069 | | ECFieldElement L3 = A.Add(B).Square().MultiplyPlusProduct(T, L2plus1, Z3); |
| | | 2070 | | |
| | 0 | 2071 | | return new F2mPoint(curve, X3, L3, new ECFieldElement[] { Z3 }, IsCompressed); |
| | | 2072 | | } |
| | | 2073 | | default: |
| | 0 | 2074 | | { |
| | 0 | 2075 | | return Twice().Add(b); |
| | | 2076 | | } |
| | | 2077 | | } |
| | 0 | 2078 | | } |
| | | 2079 | | |
| | | 2080 | | public override ECPoint Negate() |
| | 0 | 2081 | | { |
| | 0 | 2082 | | if (this.IsInfinity) |
| | 0 | 2083 | | return this; |
| | | 2084 | | |
| | 0 | 2085 | | ECFieldElement X = this.RawXCoord; |
| | 0 | 2086 | | if (X.IsZero) |
| | 0 | 2087 | | return this; |
| | | 2088 | | |
| | 0 | 2089 | | ECCurve curve = this.Curve; |
| | 0 | 2090 | | int coord = curve.CoordinateSystem; |
| | | 2091 | | |
| | 0 | 2092 | | switch (coord) |
| | | 2093 | | { |
| | | 2094 | | case ECCurve.COORD_AFFINE: |
| | 0 | 2095 | | { |
| | 0 | 2096 | | ECFieldElement Y = this.RawYCoord; |
| | 0 | 2097 | | return new F2mPoint(curve, X, Y.Add(X), IsCompressed); |
| | | 2098 | | } |
| | | 2099 | | case ECCurve.COORD_HOMOGENEOUS: |
| | 0 | 2100 | | { |
| | 0 | 2101 | | ECFieldElement Y = this.RawYCoord, Z = this.RawZCoords[0]; |
| | 0 | 2102 | | return new F2mPoint(curve, X, Y.Add(X), new ECFieldElement[] { Z }, IsCompressed); |
| | | 2103 | | } |
| | | 2104 | | case ECCurve.COORD_LAMBDA_AFFINE: |
| | 0 | 2105 | | { |
| | 0 | 2106 | | ECFieldElement L = this.RawYCoord; |
| | 0 | 2107 | | return new F2mPoint(curve, X, L.AddOne(), IsCompressed); |
| | | 2108 | | } |
| | | 2109 | | case ECCurve.COORD_LAMBDA_PROJECTIVE: |
| | 0 | 2110 | | { |
| | | 2111 | | // L is actually Lambda (X + Y/X) here |
| | 0 | 2112 | | ECFieldElement L = this.RawYCoord, Z = this.RawZCoords[0]; |
| | 0 | 2113 | | return new F2mPoint(curve, X, L.Add(Z), new ECFieldElement[] { Z }, IsCompressed); |
| | | 2114 | | } |
| | | 2115 | | default: |
| | 0 | 2116 | | { |
| | 0 | 2117 | | throw new InvalidOperationException("unsupported coordinate system"); |
| | | 2118 | | } |
| | | 2119 | | } |
| | 0 | 2120 | | } |
| | | 2121 | | } |
| | | 2122 | | } |