| | | 1 | | using System; |
| | | 2 | | using System.Collections; |
| | | 3 | | using System.Collections.Generic; |
| | | 4 | | using Renci.SshNet.Security.Org.BouncyCastle.Math.EC.Abc; |
| | | 5 | | using Renci.SshNet.Security.Org.BouncyCastle.Math.EC.Endo; |
| | | 6 | | using Renci.SshNet.Security.Org.BouncyCastle.Math.EC.Multiplier; |
| | | 7 | | using Renci.SshNet.Security.Org.BouncyCastle.Math.Field; |
| | | 8 | | using Renci.SshNet.Security.Org.BouncyCastle.Math.Raw; |
| | | 9 | | using Renci.SshNet.Security.Org.BouncyCastle.Utilities; |
| | | 10 | | |
| | | 11 | | namespace Renci.SshNet.Security.Org.BouncyCastle.Math.EC |
| | | 12 | | { |
| | | 13 | | /// <remarks>Base class for an elliptic curve.</remarks> |
| | | 14 | | internal abstract class ECCurve |
| | | 15 | | { |
| | | 16 | | public const int COORD_AFFINE = 0; |
| | | 17 | | public const int COORD_HOMOGENEOUS = 1; |
| | | 18 | | public const int COORD_JACOBIAN = 2; |
| | | 19 | | public const int COORD_JACOBIAN_CHUDNOVSKY = 3; |
| | | 20 | | public const int COORD_JACOBIAN_MODIFIED = 4; |
| | | 21 | | public const int COORD_LAMBDA_AFFINE = 5; |
| | | 22 | | public const int COORD_LAMBDA_PROJECTIVE = 6; |
| | | 23 | | public const int COORD_SKEWED = 7; |
| | | 24 | | |
| | | 25 | | public static int[] GetAllCoordinateSystems() |
| | | 26 | | { |
| | | 27 | | return new int[]{ COORD_AFFINE, COORD_HOMOGENEOUS, COORD_JACOBIAN, COORD_JACOBIAN_CHUDNOVSKY, |
| | | 28 | | COORD_JACOBIAN_MODIFIED, COORD_LAMBDA_AFFINE, COORD_LAMBDA_PROJECTIVE, COORD_SKEWED }; |
| | | 29 | | } |
| | | 30 | | |
| | | 31 | | internal class Config |
| | | 32 | | { |
| | | 33 | | protected ECCurve outer; |
| | | 34 | | protected int coord; |
| | | 35 | | protected ECEndomorphism endomorphism; |
| | | 36 | | protected ECMultiplier multiplier; |
| | | 37 | | |
| | | 38 | | internal Config(ECCurve outer, int coord, ECEndomorphism endomorphism, ECMultiplier multiplier) |
| | | 39 | | { |
| | | 40 | | this.outer = outer; |
| | | 41 | | this.coord = coord; |
| | | 42 | | this.endomorphism = endomorphism; |
| | | 43 | | this.multiplier = multiplier; |
| | | 44 | | } |
| | | 45 | | |
| | | 46 | | public Config SetCoordinateSystem(int coord) |
| | | 47 | | { |
| | | 48 | | this.coord = coord; |
| | | 49 | | return this; |
| | | 50 | | } |
| | | 51 | | |
| | | 52 | | public Config SetEndomorphism(ECEndomorphism endomorphism) |
| | | 53 | | { |
| | | 54 | | this.endomorphism = endomorphism; |
| | | 55 | | return this; |
| | | 56 | | } |
| | | 57 | | |
| | | 58 | | public Config SetMultiplier(ECMultiplier multiplier) |
| | | 59 | | { |
| | | 60 | | this.multiplier = multiplier; |
| | | 61 | | return this; |
| | | 62 | | } |
| | | 63 | | |
| | | 64 | | public ECCurve Create() |
| | | 65 | | { |
| | | 66 | | if (!outer.SupportsCoordinateSystem(coord)) |
| | | 67 | | { |
| | | 68 | | throw new InvalidOperationException("unsupported coordinate system"); |
| | | 69 | | } |
| | | 70 | | |
| | | 71 | | ECCurve c = outer.CloneCurve(); |
| | | 72 | | if (c == outer) |
| | | 73 | | { |
| | | 74 | | throw new InvalidOperationException("implementation returned current curve"); |
| | | 75 | | } |
| | | 76 | | |
| | | 77 | | c.m_coord = coord; |
| | | 78 | | c.m_endomorphism = endomorphism; |
| | | 79 | | c.m_multiplier = multiplier; |
| | | 80 | | |
| | | 81 | | return c; |
| | | 82 | | } |
| | | 83 | | } |
| | | 84 | | |
| | | 85 | | protected readonly IFiniteField m_field; |
| | | 86 | | protected ECFieldElement m_a, m_b; |
| | | 87 | | protected BigInteger m_order, m_cofactor; |
| | | 88 | | |
| | | 89 | | protected int m_coord = COORD_AFFINE; |
| | | 90 | | protected ECEndomorphism m_endomorphism = null; |
| | | 91 | | protected ECMultiplier m_multiplier = null; |
| | | 92 | | |
| | | 93 | | protected ECCurve(IFiniteField field) |
| | | 94 | | { |
| | | 95 | | this.m_field = field; |
| | | 96 | | } |
| | | 97 | | |
| | | 98 | | public abstract int FieldSize { get; } |
| | | 99 | | public abstract ECFieldElement FromBigInteger(BigInteger x); |
| | | 100 | | public abstract bool IsValidFieldElement(BigInteger x); |
| | | 101 | | |
| | | 102 | | public virtual Config Configure() |
| | | 103 | | { |
| | | 104 | | return new Config(this, this.m_coord, this.m_endomorphism, this.m_multiplier); |
| | | 105 | | } |
| | | 106 | | |
| | | 107 | | public virtual ECPoint ValidatePoint(BigInteger x, BigInteger y) |
| | | 108 | | { |
| | | 109 | | ECPoint p = CreatePoint(x, y); |
| | | 110 | | if (!p.IsValid()) |
| | | 111 | | { |
| | | 112 | | throw new ArgumentException("Invalid point coordinates"); |
| | | 113 | | } |
| | | 114 | | return p; |
| | | 115 | | } |
| | | 116 | | |
| | | 117 | | public virtual ECPoint ValidatePoint(BigInteger x, BigInteger y, bool withCompression) |
| | | 118 | | { |
| | | 119 | | ECPoint p = CreatePoint(x, y, withCompression); |
| | | 120 | | if (!p.IsValid()) |
| | | 121 | | { |
| | | 122 | | throw new ArgumentException("Invalid point coordinates"); |
| | | 123 | | } |
| | | 124 | | return p; |
| | | 125 | | } |
| | | 126 | | |
| | | 127 | | public virtual ECPoint CreatePoint(BigInteger x, BigInteger y) |
| | | 128 | | { |
| | | 129 | | return CreatePoint(x, y, false); |
| | | 130 | | } |
| | | 131 | | |
| | | 132 | | public virtual ECPoint CreatePoint(BigInteger x, BigInteger y, bool withCompression) |
| | | 133 | | { |
| | | 134 | | return CreateRawPoint(FromBigInteger(x), FromBigInteger(y), withCompression); |
| | | 135 | | } |
| | | 136 | | |
| | | 137 | | protected abstract ECCurve CloneCurve(); |
| | | 138 | | |
| | | 139 | | protected internal abstract ECPoint CreateRawPoint(ECFieldElement x, ECFieldElement y, bool withCompression); |
| | | 140 | | |
| | | 141 | | protected internal abstract ECPoint CreateRawPoint(ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, bool |
| | | 142 | | |
| | | 143 | | protected virtual ECMultiplier CreateDefaultMultiplier() |
| | | 144 | | { |
| | | 145 | | GlvEndomorphism glvEndomorphism = m_endomorphism as GlvEndomorphism; |
| | | 146 | | if (glvEndomorphism != null) |
| | | 147 | | { |
| | | 148 | | return new GlvMultiplier(this, glvEndomorphism); |
| | | 149 | | } |
| | | 150 | | |
| | | 151 | | return new WNafL2RMultiplier(); |
| | | 152 | | } |
| | | 153 | | |
| | | 154 | | public virtual bool SupportsCoordinateSystem(int coord) |
| | | 155 | | { |
| | | 156 | | return coord == COORD_AFFINE; |
| | | 157 | | } |
| | | 158 | | |
| | | 159 | | public virtual PreCompInfo GetPreCompInfo(ECPoint point, string name) |
| | | 160 | | { |
| | | 161 | | CheckPoint(point); |
| | | 162 | | |
| | | 163 | | IDictionary table; |
| | | 164 | | lock (point) |
| | | 165 | | { |
| | | 166 | | table = point.m_preCompTable; |
| | | 167 | | } |
| | | 168 | | |
| | | 169 | | if (null == table) |
| | | 170 | | return null; |
| | | 171 | | |
| | | 172 | | lock (table) |
| | | 173 | | { |
| | | 174 | | return (PreCompInfo)table[name]; |
| | | 175 | | } |
| | | 176 | | } |
| | | 177 | | |
| | | 178 | | /** |
| | | 179 | | * Compute a <code>PreCompInfo</code> for a point on this curve, under a given name. Used by |
| | | 180 | | * <code>ECMultiplier</code>s to save the precomputation for this <code>ECPoint</code> for use |
| | | 181 | | * by subsequent multiplication. |
| | | 182 | | * |
| | | 183 | | * @param point |
| | | 184 | | * The <code>ECPoint</code> to store precomputations for. |
| | | 185 | | * @param name |
| | | 186 | | * A <code>String</code> used to index precomputations of different types. |
| | | 187 | | * @param callback |
| | | 188 | | * Called to calculate the <code>PreCompInfo</code>. |
| | | 189 | | */ |
| | | 190 | | public virtual PreCompInfo Precompute(ECPoint point, string name, IPreCompCallback callback) |
| | | 191 | | { |
| | | 192 | | CheckPoint(point); |
| | | 193 | | |
| | | 194 | | IDictionary table; |
| | | 195 | | lock (point) |
| | | 196 | | { |
| | | 197 | | table = point.m_preCompTable; |
| | | 198 | | if (null == table) |
| | | 199 | | { |
| | | 200 | | point.m_preCompTable = table = new Dictionary<object, object>(4); |
| | | 201 | | } |
| | | 202 | | } |
| | | 203 | | |
| | | 204 | | lock (table) |
| | | 205 | | { |
| | | 206 | | PreCompInfo existing = (PreCompInfo)table[name]; |
| | | 207 | | PreCompInfo result = callback.Precompute(existing); |
| | | 208 | | |
| | | 209 | | if (result != existing) |
| | | 210 | | { |
| | | 211 | | table[name] = result; |
| | | 212 | | } |
| | | 213 | | |
| | | 214 | | return result; |
| | | 215 | | } |
| | | 216 | | } |
| | | 217 | | |
| | | 218 | | public virtual ECPoint ImportPoint(ECPoint p) |
| | | 219 | | { |
| | | 220 | | if (this == p.Curve) |
| | | 221 | | { |
| | | 222 | | return p; |
| | | 223 | | } |
| | | 224 | | if (p.IsInfinity) |
| | | 225 | | { |
| | | 226 | | return Infinity; |
| | | 227 | | } |
| | | 228 | | |
| | | 229 | | // TODO Default behaviour could be improved if the two curves have the same coordinate system by copying any |
| | | 230 | | p = p.Normalize(); |
| | | 231 | | |
| | | 232 | | return CreatePoint(p.XCoord.ToBigInteger(), p.YCoord.ToBigInteger(), p.IsCompressed); |
| | | 233 | | } |
| | | 234 | | |
| | | 235 | | /** |
| | | 236 | | * Normalization ensures that any projective coordinate is 1, and therefore that the x, y |
| | | 237 | | * coordinates reflect those of the equivalent point in an affine coordinate system. Where more |
| | | 238 | | * than one point is to be normalized, this method will generally be more efficient than |
| | | 239 | | * normalizing each point separately. |
| | | 240 | | * |
| | | 241 | | * @param points |
| | | 242 | | * An array of points that will be updated in place with their normalized versions, |
| | | 243 | | * where necessary |
| | | 244 | | */ |
| | | 245 | | public virtual void NormalizeAll(ECPoint[] points) |
| | | 246 | | { |
| | | 247 | | NormalizeAll(points, 0, points.Length, null); |
| | | 248 | | } |
| | | 249 | | |
| | | 250 | | /** |
| | | 251 | | * Normalization ensures that any projective coordinate is 1, and therefore that the x, y |
| | | 252 | | * coordinates reflect those of the equivalent point in an affine coordinate system. Where more |
| | | 253 | | * than one point is to be normalized, this method will generally be more efficient than |
| | | 254 | | * normalizing each point separately. An (optional) z-scaling factor can be applied; effectively |
| | | 255 | | * each z coordinate is scaled by this value prior to normalization (but only one |
| | | 256 | | * actual multiplication is needed). |
| | | 257 | | * |
| | | 258 | | * @param points |
| | | 259 | | * An array of points that will be updated in place with their normalized versions, |
| | | 260 | | * where necessary |
| | | 261 | | * @param off |
| | | 262 | | * The start of the range of points to normalize |
| | | 263 | | * @param len |
| | | 264 | | * The length of the range of points to normalize |
| | | 265 | | * @param iso |
| | | 266 | | * The (optional) z-scaling factor - can be null |
| | | 267 | | */ |
| | | 268 | | public virtual void NormalizeAll(ECPoint[] points, int off, int len, ECFieldElement iso) |
| | | 269 | | { |
| | | 270 | | CheckPoints(points, off, len); |
| | | 271 | | |
| | | 272 | | switch (this.CoordinateSystem) |
| | | 273 | | { |
| | | 274 | | case ECCurve.COORD_AFFINE: |
| | | 275 | | case ECCurve.COORD_LAMBDA_AFFINE: |
| | | 276 | | { |
| | | 277 | | if (iso != null) |
| | | 278 | | throw new ArgumentException("not valid for affine coordinates", "iso"); |
| | | 279 | | |
| | | 280 | | return; |
| | | 281 | | } |
| | | 282 | | } |
| | | 283 | | |
| | | 284 | | /* |
| | | 285 | | * Figure out which of the points actually need to be normalized |
| | | 286 | | */ |
| | | 287 | | ECFieldElement[] zs = new ECFieldElement[len]; |
| | | 288 | | int[] indices = new int[len]; |
| | | 289 | | int count = 0; |
| | | 290 | | for (int i = 0; i < len; ++i) |
| | | 291 | | { |
| | | 292 | | ECPoint p = points[off + i]; |
| | | 293 | | if (null != p && (iso != null || !p.IsNormalized())) |
| | | 294 | | { |
| | | 295 | | zs[count] = p.GetZCoord(0); |
| | | 296 | | indices[count++] = off + i; |
| | | 297 | | } |
| | | 298 | | } |
| | | 299 | | |
| | | 300 | | if (count == 0) |
| | | 301 | | { |
| | | 302 | | return; |
| | | 303 | | } |
| | | 304 | | |
| | | 305 | | ECAlgorithms.MontgomeryTrick(zs, 0, count, iso); |
| | | 306 | | |
| | | 307 | | for (int j = 0; j < count; ++j) |
| | | 308 | | { |
| | | 309 | | int index = indices[j]; |
| | | 310 | | points[index] = points[index].Normalize(zs[j]); |
| | | 311 | | } |
| | | 312 | | } |
| | | 313 | | |
| | | 314 | | public abstract ECPoint Infinity { get; } |
| | | 315 | | |
| | | 316 | | public virtual IFiniteField Field |
| | | 317 | | { |
| | | 318 | | get { return m_field; } |
| | | 319 | | } |
| | | 320 | | |
| | | 321 | | public virtual ECFieldElement A |
| | | 322 | | { |
| | | 323 | | get { return m_a; } |
| | | 324 | | } |
| | | 325 | | |
| | | 326 | | public virtual ECFieldElement B |
| | | 327 | | { |
| | | 328 | | get { return m_b; } |
| | | 329 | | } |
| | | 330 | | |
| | | 331 | | public virtual BigInteger Order |
| | | 332 | | { |
| | | 333 | | get { return m_order; } |
| | | 334 | | } |
| | | 335 | | |
| | | 336 | | public virtual BigInteger Cofactor |
| | | 337 | | { |
| | | 338 | | get { return m_cofactor; } |
| | | 339 | | } |
| | | 340 | | |
| | | 341 | | public virtual int CoordinateSystem |
| | | 342 | | { |
| | | 343 | | get { return m_coord; } |
| | | 344 | | } |
| | | 345 | | |
| | | 346 | | /** |
| | | 347 | | * Create a cache-safe lookup table for the specified sequence of points. All the points MUST |
| | | 348 | | * belong to this <code>ECCurve</code> instance, and MUST already be normalized. |
| | | 349 | | */ |
| | | 350 | | public virtual ECLookupTable CreateCacheSafeLookupTable(ECPoint[] points, int off, int len) |
| | | 351 | | { |
| | | 352 | | int FE_BYTES = (FieldSize + 7) / 8; |
| | | 353 | | byte[] table = new byte[len * FE_BYTES * 2]; |
| | | 354 | | { |
| | | 355 | | int pos = 0; |
| | | 356 | | for (int i = 0; i < len; ++i) |
| | | 357 | | { |
| | | 358 | | ECPoint p = points[off + i]; |
| | | 359 | | byte[] px = p.RawXCoord.ToBigInteger().ToByteArray(); |
| | | 360 | | byte[] py = p.RawYCoord.ToBigInteger().ToByteArray(); |
| | | 361 | | |
| | | 362 | | int pxStart = px.Length > FE_BYTES ? 1 : 0, pxLen = px.Length - pxStart; |
| | | 363 | | int pyStart = py.Length > FE_BYTES ? 1 : 0, pyLen = py.Length - pyStart; |
| | | 364 | | |
| | | 365 | | Array.Copy(px, pxStart, table, pos + FE_BYTES - pxLen, pxLen); pos += FE_BYTES; |
| | | 366 | | Array.Copy(py, pyStart, table, pos + FE_BYTES - pyLen, pyLen); pos += FE_BYTES; |
| | | 367 | | } |
| | | 368 | | } |
| | | 369 | | |
| | | 370 | | return new DefaultLookupTable(this, table, len); |
| | | 371 | | } |
| | | 372 | | |
| | | 373 | | protected virtual void CheckPoint(ECPoint point) |
| | | 374 | | { |
| | | 375 | | if (null == point || (this != point.Curve)) |
| | | 376 | | throw new ArgumentException("must be non-null and on this curve", "point"); |
| | | 377 | | } |
| | | 378 | | |
| | | 379 | | protected virtual void CheckPoints(ECPoint[] points) |
| | | 380 | | { |
| | | 381 | | CheckPoints(points, 0, points.Length); |
| | | 382 | | } |
| | | 383 | | |
| | | 384 | | protected virtual void CheckPoints(ECPoint[] points, int off, int len) |
| | | 385 | | { |
| | | 386 | | if (points == null) |
| | | 387 | | throw new ArgumentNullException("points"); |
| | | 388 | | if (off < 0 || len < 0 || (off > (points.Length - len))) |
| | | 389 | | throw new ArgumentException("invalid range specified", "points"); |
| | | 390 | | |
| | | 391 | | for (int i = 0; i < len; ++i) |
| | | 392 | | { |
| | | 393 | | ECPoint point = points[off + i]; |
| | | 394 | | if (null != point && this != point.Curve) |
| | | 395 | | throw new ArgumentException("entries must be null or on this curve", "points"); |
| | | 396 | | } |
| | | 397 | | } |
| | | 398 | | |
| | | 399 | | public virtual bool Equals(ECCurve other) |
| | | 400 | | { |
| | | 401 | | if (this == other) |
| | | 402 | | return true; |
| | | 403 | | if (null == other) |
| | | 404 | | return false; |
| | | 405 | | return Field.Equals(other.Field) |
| | | 406 | | && A.ToBigInteger().Equals(other.A.ToBigInteger()) |
| | | 407 | | && B.ToBigInteger().Equals(other.B.ToBigInteger()); |
| | | 408 | | } |
| | | 409 | | |
| | | 410 | | public override bool Equals(object obj) |
| | | 411 | | { |
| | | 412 | | return Equals(obj as ECCurve); |
| | | 413 | | } |
| | | 414 | | |
| | | 415 | | public override int GetHashCode() |
| | | 416 | | { |
| | | 417 | | return Field.GetHashCode() |
| | | 418 | | ^ Integers.RotateLeft(A.ToBigInteger().GetHashCode(), 8) |
| | | 419 | | ^ Integers.RotateLeft(B.ToBigInteger().GetHashCode(), 16); |
| | | 420 | | } |
| | | 421 | | |
| | | 422 | | protected abstract ECPoint DecompressPoint(int yTilde, BigInteger X1); |
| | | 423 | | |
| | | 424 | | public virtual ECEndomorphism GetEndomorphism() |
| | | 425 | | { |
| | | 426 | | return m_endomorphism; |
| | | 427 | | } |
| | | 428 | | |
| | | 429 | | /** |
| | | 430 | | * Sets the default <code>ECMultiplier</code>, unless already set. |
| | | 431 | | */ |
| | | 432 | | public virtual ECMultiplier GetMultiplier() |
| | | 433 | | { |
| | | 434 | | lock (this) |
| | | 435 | | { |
| | | 436 | | if (this.m_multiplier == null) |
| | | 437 | | { |
| | | 438 | | this.m_multiplier = CreateDefaultMultiplier(); |
| | | 439 | | } |
| | | 440 | | return this.m_multiplier; |
| | | 441 | | } |
| | | 442 | | } |
| | | 443 | | |
| | | 444 | | /** |
| | | 445 | | * Decode a point on this curve from its ASN.1 encoding. The different |
| | | 446 | | * encodings are taken account of, including point compression for |
| | | 447 | | * <code>F<sub>p</sub></code> (X9.62 s 4.2.1 pg 17). |
| | | 448 | | * @return The decoded point. |
| | | 449 | | */ |
| | | 450 | | public virtual ECPoint DecodePoint(byte[] encoded) |
| | | 451 | | { |
| | | 452 | | ECPoint p = null; |
| | | 453 | | int expectedLength = (FieldSize + 7) / 8; |
| | | 454 | | |
| | | 455 | | byte type = encoded[0]; |
| | | 456 | | switch (type) |
| | | 457 | | { |
| | | 458 | | case 0x00: // infinity |
| | | 459 | | { |
| | | 460 | | if (encoded.Length != 1) |
| | | 461 | | throw new ArgumentException("Incorrect length for infinity encoding", "encoded"); |
| | | 462 | | |
| | | 463 | | p = Infinity; |
| | | 464 | | break; |
| | | 465 | | } |
| | | 466 | | |
| | | 467 | | case 0x02: // compressed |
| | | 468 | | case 0x03: // compressed |
| | | 469 | | { |
| | | 470 | | if (encoded.Length != (expectedLength + 1)) |
| | | 471 | | throw new ArgumentException("Incorrect length for compressed encoding", "encoded"); |
| | | 472 | | |
| | | 473 | | int yTilde = type & 1; |
| | | 474 | | BigInteger X = new BigInteger(1, encoded, 1, expectedLength); |
| | | 475 | | |
| | | 476 | | p = DecompressPoint(yTilde, X); |
| | | 477 | | if (!p.ImplIsValid(true, true)) |
| | | 478 | | throw new ArgumentException("Invalid point"); |
| | | 479 | | |
| | | 480 | | break; |
| | | 481 | | } |
| | | 482 | | |
| | | 483 | | case 0x04: // uncompressed |
| | | 484 | | { |
| | | 485 | | if (encoded.Length != (2 * expectedLength + 1)) |
| | | 486 | | throw new ArgumentException("Incorrect length for uncompressed encoding", "encoded"); |
| | | 487 | | |
| | | 488 | | BigInteger X = new BigInteger(1, encoded, 1, expectedLength); |
| | | 489 | | BigInteger Y = new BigInteger(1, encoded, 1 + expectedLength, expectedLength); |
| | | 490 | | |
| | | 491 | | p = ValidatePoint(X, Y); |
| | | 492 | | break; |
| | | 493 | | } |
| | | 494 | | |
| | | 495 | | case 0x06: // hybrid |
| | | 496 | | case 0x07: // hybrid |
| | | 497 | | { |
| | | 498 | | if (encoded.Length != (2 * expectedLength + 1)) |
| | | 499 | | throw new ArgumentException("Incorrect length for hybrid encoding", "encoded"); |
| | | 500 | | |
| | | 501 | | BigInteger X = new BigInteger(1, encoded, 1, expectedLength); |
| | | 502 | | BigInteger Y = new BigInteger(1, encoded, 1 + expectedLength, expectedLength); |
| | | 503 | | |
| | | 504 | | if (Y.TestBit(0) != (type == 0x07)) |
| | | 505 | | throw new ArgumentException("Inconsistent Y coordinate in hybrid encoding", "encoded"); |
| | | 506 | | |
| | | 507 | | p = ValidatePoint(X, Y); |
| | | 508 | | break; |
| | | 509 | | } |
| | | 510 | | |
| | | 511 | | default: |
| | | 512 | | throw new FormatException("Invalid point encoding " + type); |
| | | 513 | | } |
| | | 514 | | |
| | | 515 | | if (type != 0x00 && p.IsInfinity) |
| | | 516 | | throw new ArgumentException("Invalid infinity encoding", "encoded"); |
| | | 517 | | |
| | | 518 | | return p; |
| | | 519 | | } |
| | | 520 | | |
| | | 521 | | private class DefaultLookupTable |
| | | 522 | | : ECLookupTable |
| | | 523 | | { |
| | | 524 | | private readonly ECCurve m_outer; |
| | | 525 | | private readonly byte[] m_table; |
| | | 526 | | private readonly int m_size; |
| | | 527 | | |
| | | 528 | | internal DefaultLookupTable(ECCurve outer, byte[] table, int size) |
| | | 529 | | { |
| | | 530 | | this.m_outer = outer; |
| | | 531 | | this.m_table = table; |
| | | 532 | | this.m_size = size; |
| | | 533 | | } |
| | | 534 | | |
| | | 535 | | public virtual int Size |
| | | 536 | | { |
| | | 537 | | get { return m_size; } |
| | | 538 | | } |
| | | 539 | | |
| | | 540 | | public virtual ECPoint Lookup(int index) |
| | | 541 | | { |
| | | 542 | | int FE_BYTES = (m_outer.FieldSize + 7) / 8; |
| | | 543 | | byte[] x = new byte[FE_BYTES], y = new byte[FE_BYTES]; |
| | | 544 | | int pos = 0; |
| | | 545 | | |
| | | 546 | | for (int i = 0; i < m_size; ++i) |
| | | 547 | | { |
| | | 548 | | byte MASK = (byte)(((i ^ index) - 1) >> 31); |
| | | 549 | | |
| | | 550 | | for (int j = 0; j < FE_BYTES; ++j) |
| | | 551 | | { |
| | | 552 | | x[j] ^= (byte)(m_table[pos + j] & MASK); |
| | | 553 | | y[j] ^= (byte)(m_table[pos + FE_BYTES + j] & MASK); |
| | | 554 | | } |
| | | 555 | | |
| | | 556 | | pos += (FE_BYTES * 2); |
| | | 557 | | } |
| | | 558 | | |
| | | 559 | | ECFieldElement X = m_outer.FromBigInteger(new BigInteger(1, x)); |
| | | 560 | | ECFieldElement Y = m_outer.FromBigInteger(new BigInteger(1, y)); |
| | | 561 | | return m_outer.CreateRawPoint(X, Y, false); |
| | | 562 | | } |
| | | 563 | | } |
| | | 564 | | } |
| | | 565 | | |
| | | 566 | | internal abstract class AbstractFpCurve |
| | | 567 | | : ECCurve |
| | | 568 | | { |
| | | 569 | | protected AbstractFpCurve(BigInteger q) |
| | | 570 | | : base(FiniteFields.GetPrimeField(q)) |
| | | 571 | | { |
| | | 572 | | } |
| | | 573 | | |
| | | 574 | | public override bool IsValidFieldElement(BigInteger x) |
| | | 575 | | { |
| | | 576 | | return x != null && x.SignValue >= 0 && x.CompareTo(Field.Characteristic) < 0; |
| | | 577 | | } |
| | | 578 | | |
| | | 579 | | protected override ECPoint DecompressPoint(int yTilde, BigInteger X1) |
| | | 580 | | { |
| | | 581 | | ECFieldElement x = FromBigInteger(X1); |
| | | 582 | | ECFieldElement rhs = x.Square().Add(A).Multiply(x).Add(B); |
| | | 583 | | ECFieldElement y = rhs.Sqrt(); |
| | | 584 | | |
| | | 585 | | /* |
| | | 586 | | * If y is not a square, then we haven't got a point on the curve |
| | | 587 | | */ |
| | | 588 | | if (y == null) |
| | | 589 | | throw new ArgumentException("Invalid point compression"); |
| | | 590 | | |
| | | 591 | | if (y.TestBitZero() != (yTilde == 1)) |
| | | 592 | | { |
| | | 593 | | // Use the other root |
| | | 594 | | y = y.Negate(); |
| | | 595 | | } |
| | | 596 | | |
| | | 597 | | return CreateRawPoint(x, y, true); |
| | | 598 | | } |
| | | 599 | | } |
| | | 600 | | |
| | | 601 | | /** |
| | | 602 | | * Elliptic curve over Fp |
| | | 603 | | */ |
| | | 604 | | internal class FpCurve |
| | | 605 | | : AbstractFpCurve |
| | | 606 | | { |
| | | 607 | | private const int FP_DEFAULT_COORDS = COORD_JACOBIAN_MODIFIED; |
| | | 608 | | |
| | | 609 | | protected readonly BigInteger m_q, m_r; |
| | | 610 | | protected readonly FpPoint m_infinity; |
| | | 611 | | |
| | | 612 | | public FpCurve(BigInteger q, BigInteger a, BigInteger b) |
| | | 613 | | : this(q, a, b, null, null) |
| | | 614 | | { |
| | | 615 | | } |
| | | 616 | | |
| | | 617 | | public FpCurve(BigInteger q, BigInteger a, BigInteger b, BigInteger order, BigInteger cofactor) |
| | | 618 | | : base(q) |
| | | 619 | | { |
| | | 620 | | this.m_q = q; |
| | | 621 | | this.m_r = FpFieldElement.CalculateResidue(q); |
| | | 622 | | this.m_infinity = new FpPoint(this, null, null, false); |
| | | 623 | | |
| | | 624 | | this.m_a = FromBigInteger(a); |
| | | 625 | | this.m_b = FromBigInteger(b); |
| | | 626 | | this.m_order = order; |
| | | 627 | | this.m_cofactor = cofactor; |
| | | 628 | | this.m_coord = FP_DEFAULT_COORDS; |
| | | 629 | | } |
| | | 630 | | |
| | | 631 | | protected FpCurve(BigInteger q, BigInteger r, ECFieldElement a, ECFieldElement b) |
| | | 632 | | : this(q, r, a, b, null, null) |
| | | 633 | | { |
| | | 634 | | } |
| | | 635 | | |
| | | 636 | | protected FpCurve(BigInteger q, BigInteger r, ECFieldElement a, ECFieldElement b, BigInteger order, BigInteger c |
| | | 637 | | : base(q) |
| | | 638 | | { |
| | | 639 | | this.m_q = q; |
| | | 640 | | this.m_r = r; |
| | | 641 | | this.m_infinity = new FpPoint(this, null, null, false); |
| | | 642 | | |
| | | 643 | | this.m_a = a; |
| | | 644 | | this.m_b = b; |
| | | 645 | | this.m_order = order; |
| | | 646 | | this.m_cofactor = cofactor; |
| | | 647 | | this.m_coord = FP_DEFAULT_COORDS; |
| | | 648 | | } |
| | | 649 | | |
| | | 650 | | protected override ECCurve CloneCurve() |
| | | 651 | | { |
| | | 652 | | return new FpCurve(m_q, m_r, m_a, m_b, m_order, m_cofactor); |
| | | 653 | | } |
| | | 654 | | |
| | | 655 | | public override bool SupportsCoordinateSystem(int coord) |
| | | 656 | | { |
| | | 657 | | switch (coord) |
| | | 658 | | { |
| | | 659 | | case COORD_AFFINE: |
| | | 660 | | case COORD_HOMOGENEOUS: |
| | | 661 | | case COORD_JACOBIAN: |
| | | 662 | | case COORD_JACOBIAN_MODIFIED: |
| | | 663 | | return true; |
| | | 664 | | default: |
| | | 665 | | return false; |
| | | 666 | | } |
| | | 667 | | } |
| | | 668 | | |
| | | 669 | | public virtual BigInteger Q |
| | | 670 | | { |
| | | 671 | | get { return m_q; } |
| | | 672 | | } |
| | | 673 | | |
| | | 674 | | public override ECPoint Infinity |
| | | 675 | | { |
| | | 676 | | get { return m_infinity; } |
| | | 677 | | } |
| | | 678 | | |
| | | 679 | | public override int FieldSize |
| | | 680 | | { |
| | | 681 | | get { return m_q.BitLength; } |
| | | 682 | | } |
| | | 683 | | |
| | | 684 | | public override ECFieldElement FromBigInteger(BigInteger x) |
| | | 685 | | { |
| | | 686 | | return new FpFieldElement(this.m_q, this.m_r, x); |
| | | 687 | | } |
| | | 688 | | |
| | | 689 | | protected internal override ECPoint CreateRawPoint(ECFieldElement x, ECFieldElement y, bool withCompression) |
| | | 690 | | { |
| | | 691 | | return new FpPoint(this, x, y, withCompression); |
| | | 692 | | } |
| | | 693 | | |
| | | 694 | | protected internal override ECPoint CreateRawPoint(ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, bool |
| | | 695 | | { |
| | | 696 | | return new FpPoint(this, x, y, zs, withCompression); |
| | | 697 | | } |
| | | 698 | | |
| | | 699 | | public override ECPoint ImportPoint(ECPoint p) |
| | | 700 | | { |
| | | 701 | | if (this != p.Curve && this.CoordinateSystem == COORD_JACOBIAN && !p.IsInfinity) |
| | | 702 | | { |
| | | 703 | | switch (p.Curve.CoordinateSystem) |
| | | 704 | | { |
| | | 705 | | case COORD_JACOBIAN: |
| | | 706 | | case COORD_JACOBIAN_CHUDNOVSKY: |
| | | 707 | | case COORD_JACOBIAN_MODIFIED: |
| | | 708 | | return new FpPoint(this, |
| | | 709 | | FromBigInteger(p.RawXCoord.ToBigInteger()), |
| | | 710 | | FromBigInteger(p.RawYCoord.ToBigInteger()), |
| | | 711 | | new ECFieldElement[] { FromBigInteger(p.GetZCoord(0).ToBigInteger()) }, |
| | | 712 | | p.IsCompressed); |
| | | 713 | | default: |
| | | 714 | | break; |
| | | 715 | | } |
| | | 716 | | } |
| | | 717 | | |
| | | 718 | | return base.ImportPoint(p); |
| | | 719 | | } |
| | | 720 | | } |
| | | 721 | | |
| | | 722 | | internal abstract class AbstractF2mCurve |
| | | 723 | | : ECCurve |
| | | 724 | | { |
| | | 725 | | public static BigInteger Inverse(int m, int[] ks, BigInteger x) |
| | 0 | 726 | | { |
| | 0 | 727 | | return new LongArray(x).ModInverse(m, ks).ToBigInteger(); |
| | 0 | 728 | | } |
| | | 729 | | |
| | | 730 | | /** |
| | | 731 | | * The auxiliary values <code>s<sub>0</sub></code> and |
| | | 732 | | * <code>s<sub>1</sub></code> used for partial modular reduction for |
| | | 733 | | * Koblitz curves. |
| | | 734 | | */ |
| | 0 | 735 | | private BigInteger[] si = null; |
| | | 736 | | |
| | | 737 | | private static IFiniteField BuildField(int m, int k1, int k2, int k3) |
| | 0 | 738 | | { |
| | 0 | 739 | | if (k1 == 0) |
| | 0 | 740 | | { |
| | 0 | 741 | | throw new ArgumentException("k1 must be > 0"); |
| | | 742 | | } |
| | | 743 | | |
| | 0 | 744 | | if (k2 == 0) |
| | 0 | 745 | | { |
| | 0 | 746 | | if (k3 != 0) |
| | 0 | 747 | | { |
| | 0 | 748 | | throw new ArgumentException("k3 must be 0 if k2 == 0"); |
| | | 749 | | } |
| | | 750 | | |
| | 0 | 751 | | return FiniteFields.GetBinaryExtensionField(new int[]{ 0, k1, m }); |
| | | 752 | | } |
| | | 753 | | |
| | 0 | 754 | | if (k2 <= k1) |
| | 0 | 755 | | { |
| | 0 | 756 | | throw new ArgumentException("k2 must be > k1"); |
| | | 757 | | } |
| | | 758 | | |
| | 0 | 759 | | if (k3 <= k2) |
| | 0 | 760 | | { |
| | 0 | 761 | | throw new ArgumentException("k3 must be > k2"); |
| | | 762 | | } |
| | | 763 | | |
| | 0 | 764 | | return FiniteFields.GetBinaryExtensionField(new int[]{ 0, k1, k2, k3, m }); |
| | 0 | 765 | | } |
| | | 766 | | |
| | | 767 | | protected AbstractF2mCurve(int m, int k1, int k2, int k3) |
| | 0 | 768 | | : base(BuildField(m, k1, k2, k3)) |
| | 0 | 769 | | { |
| | 0 | 770 | | } |
| | | 771 | | |
| | | 772 | | public override bool IsValidFieldElement(BigInteger x) |
| | 0 | 773 | | { |
| | 0 | 774 | | return x != null && x.SignValue >= 0 && x.BitLength <= FieldSize; |
| | 0 | 775 | | } |
| | | 776 | | |
| | | 777 | | public override ECPoint CreatePoint(BigInteger x, BigInteger y, bool withCompression) |
| | 0 | 778 | | { |
| | 0 | 779 | | ECFieldElement X = FromBigInteger(x), Y = FromBigInteger(y); |
| | | 780 | | |
| | 0 | 781 | | switch (this.CoordinateSystem) |
| | | 782 | | { |
| | | 783 | | case COORD_LAMBDA_AFFINE: |
| | | 784 | | case COORD_LAMBDA_PROJECTIVE: |
| | 0 | 785 | | { |
| | 0 | 786 | | if (X.IsZero) |
| | 0 | 787 | | { |
| | 0 | 788 | | if (!Y.Square().Equals(B)) |
| | 0 | 789 | | throw new ArgumentException(); |
| | 0 | 790 | | } |
| | | 791 | | else |
| | 0 | 792 | | { |
| | | 793 | | // Y becomes Lambda (X + Y/X) here |
| | 0 | 794 | | Y = Y.Divide(X).Add(X); |
| | 0 | 795 | | } |
| | 0 | 796 | | break; |
| | | 797 | | } |
| | | 798 | | default: |
| | 0 | 799 | | { |
| | 0 | 800 | | break; |
| | | 801 | | } |
| | | 802 | | } |
| | | 803 | | |
| | 0 | 804 | | return CreateRawPoint(X, Y, withCompression); |
| | 0 | 805 | | } |
| | | 806 | | |
| | | 807 | | protected override ECPoint DecompressPoint(int yTilde, BigInteger X1) |
| | 0 | 808 | | { |
| | 0 | 809 | | ECFieldElement xp = FromBigInteger(X1), yp = null; |
| | 0 | 810 | | if (xp.IsZero) |
| | 0 | 811 | | { |
| | 0 | 812 | | yp = B.Sqrt(); |
| | 0 | 813 | | } |
| | | 814 | | else |
| | 0 | 815 | | { |
| | 0 | 816 | | ECFieldElement beta = xp.Square().Invert().Multiply(B).Add(A).Add(xp); |
| | 0 | 817 | | ECFieldElement z = SolveQuadraticEquation(beta); |
| | | 818 | | |
| | 0 | 819 | | if (z != null) |
| | 0 | 820 | | { |
| | 0 | 821 | | if (z.TestBitZero() != (yTilde == 1)) |
| | 0 | 822 | | { |
| | 0 | 823 | | z = z.AddOne(); |
| | 0 | 824 | | } |
| | | 825 | | |
| | 0 | 826 | | switch (this.CoordinateSystem) |
| | | 827 | | { |
| | | 828 | | case COORD_LAMBDA_AFFINE: |
| | | 829 | | case COORD_LAMBDA_PROJECTIVE: |
| | 0 | 830 | | { |
| | 0 | 831 | | yp = z.Add(xp); |
| | 0 | 832 | | break; |
| | | 833 | | } |
| | | 834 | | default: |
| | 0 | 835 | | { |
| | 0 | 836 | | yp = z.Multiply(xp); |
| | 0 | 837 | | break; |
| | | 838 | | } |
| | | 839 | | } |
| | 0 | 840 | | } |
| | 0 | 841 | | } |
| | | 842 | | |
| | 0 | 843 | | if (yp == null) |
| | 0 | 844 | | throw new ArgumentException("Invalid point compression"); |
| | | 845 | | |
| | 0 | 846 | | return CreateRawPoint(xp, yp, true); |
| | 0 | 847 | | } |
| | | 848 | | |
| | | 849 | | /** |
| | | 850 | | * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62 |
| | | 851 | | * D.1.6) The other solution is <code>z + 1</code>. |
| | | 852 | | * |
| | | 853 | | * @param beta |
| | | 854 | | * The value to solve the quadratic equation for. |
| | | 855 | | * @return the solution for <code>z<sup>2</sup> + z = beta</code> or |
| | | 856 | | * <code>null</code> if no solution exists. |
| | | 857 | | */ |
| | | 858 | | internal ECFieldElement SolveQuadraticEquation(ECFieldElement beta) |
| | 0 | 859 | | { |
| | 0 | 860 | | if (beta.IsZero) |
| | 0 | 861 | | return beta; |
| | | 862 | | |
| | 0 | 863 | | ECFieldElement gamma, z, zeroElement = FromBigInteger(BigInteger.Zero); |
| | | 864 | | |
| | 0 | 865 | | int m = FieldSize; |
| | | 866 | | do |
| | 0 | 867 | | { |
| | 0 | 868 | | ECFieldElement t = FromBigInteger(BigInteger.Arbitrary(m)); |
| | 0 | 869 | | z = zeroElement; |
| | 0 | 870 | | ECFieldElement w = beta; |
| | 0 | 871 | | for (int i = 1; i < m; i++) |
| | 0 | 872 | | { |
| | 0 | 873 | | ECFieldElement w2 = w.Square(); |
| | 0 | 874 | | z = z.Square().Add(w2.Multiply(t)); |
| | 0 | 875 | | w = w2.Add(beta); |
| | 0 | 876 | | } |
| | 0 | 877 | | if (!w.IsZero) |
| | 0 | 878 | | { |
| | 0 | 879 | | return null; |
| | | 880 | | } |
| | 0 | 881 | | gamma = z.Square().Add(z); |
| | 0 | 882 | | } |
| | 0 | 883 | | while (gamma.IsZero); |
| | | 884 | | |
| | 0 | 885 | | return z; |
| | 0 | 886 | | } |
| | | 887 | | |
| | | 888 | | /** |
| | | 889 | | * @return the auxiliary values <code>s<sub>0</sub></code> and |
| | | 890 | | * <code>s<sub>1</sub></code> used for partial modular reduction for |
| | | 891 | | * Koblitz curves. |
| | | 892 | | */ |
| | | 893 | | internal virtual BigInteger[] GetSi() |
| | 0 | 894 | | { |
| | 0 | 895 | | if (si == null) |
| | 0 | 896 | | { |
| | 0 | 897 | | lock (this) |
| | 0 | 898 | | { |
| | 0 | 899 | | if (si == null) |
| | 0 | 900 | | { |
| | 0 | 901 | | si = Tnaf.GetSi(this); |
| | 0 | 902 | | } |
| | 0 | 903 | | } |
| | 0 | 904 | | } |
| | 0 | 905 | | return si; |
| | 0 | 906 | | } |
| | | 907 | | |
| | | 908 | | /** |
| | | 909 | | * Returns true if this is a Koblitz curve (ABC curve). |
| | | 910 | | * @return true if this is a Koblitz curve (ABC curve), false otherwise |
| | | 911 | | */ |
| | | 912 | | public virtual bool IsKoblitz |
| | | 913 | | { |
| | | 914 | | get |
| | 0 | 915 | | { |
| | 0 | 916 | | return m_order != null && m_cofactor != null && m_b.IsOne && (m_a.IsZero || m_a.IsOne); |
| | 0 | 917 | | } |
| | | 918 | | } |
| | | 919 | | } |
| | | 920 | | |
| | | 921 | | /** |
| | | 922 | | * Elliptic curves over F2m. The Weierstrass equation is given by |
| | | 923 | | * <code>y<sup>2</sup> + xy = x<sup>3</sup> + ax<sup>2</sup> + b</code>. |
| | | 924 | | */ |
| | | 925 | | internal class F2mCurve |
| | | 926 | | : AbstractF2mCurve |
| | | 927 | | { |
| | | 928 | | private const int F2M_DEFAULT_COORDS = COORD_LAMBDA_PROJECTIVE; |
| | | 929 | | |
| | | 930 | | /** |
| | | 931 | | * The exponent <code>m</code> of <code>F<sub>2<sup>m</sup></sub></code>. |
| | | 932 | | */ |
| | | 933 | | private readonly int m; |
| | | 934 | | |
| | | 935 | | /** |
| | | 936 | | * TPB: The integer <code>k</code> where <code>x<sup>m</sup> + |
| | | 937 | | * x<sup>k</sup> + 1</code> represents the reduction polynomial |
| | | 938 | | * <code>f(z)</code>.<br/> |
| | | 939 | | * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> + |
| | | 940 | | * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> |
| | | 941 | | * represents the reduction polynomial <code>f(z)</code>.<br/> |
| | | 942 | | */ |
| | | 943 | | private readonly int k1; |
| | | 944 | | |
| | | 945 | | /** |
| | | 946 | | * TPB: Always set to <code>0</code><br/> |
| | | 947 | | * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> + |
| | | 948 | | * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> |
| | | 949 | | * represents the reduction polynomial <code>f(z)</code>.<br/> |
| | | 950 | | */ |
| | | 951 | | private readonly int k2; |
| | | 952 | | |
| | | 953 | | /** |
| | | 954 | | * TPB: Always set to <code>0</code><br/> |
| | | 955 | | * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> + |
| | | 956 | | * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> |
| | | 957 | | * represents the reduction polynomial <code>f(z)</code>.<br/> |
| | | 958 | | */ |
| | | 959 | | private readonly int k3; |
| | | 960 | | |
| | | 961 | | /** |
| | | 962 | | * The point at infinity on this curve. |
| | | 963 | | */ |
| | | 964 | | protected readonly F2mPoint m_infinity; |
| | | 965 | | |
| | | 966 | | /** |
| | | 967 | | * Constructor for Trinomial Polynomial Basis (TPB). |
| | | 968 | | * @param m The exponent <code>m</code> of |
| | | 969 | | * <code>F<sub>2<sup>m</sup></sub></code>. |
| | | 970 | | * @param k The integer <code>k</code> where <code>x<sup>m</sup> + |
| | | 971 | | * x<sup>k</sup> + 1</code> represents the reduction |
| | | 972 | | * polynomial <code>f(z)</code>. |
| | | 973 | | * @param a The coefficient <code>a</code> in the Weierstrass equation |
| | | 974 | | * for non-supersingular elliptic curves over |
| | | 975 | | * <code>F<sub>2<sup>m</sup></sub></code>. |
| | | 976 | | * @param b The coefficient <code>b</code> in the Weierstrass equation |
| | | 977 | | * for non-supersingular elliptic curves over |
| | | 978 | | * <code>F<sub>2<sup>m</sup></sub></code>. |
| | | 979 | | */ |
| | | 980 | | [Obsolete("Use constructor taking order/cofactor")] |
| | | 981 | | public F2mCurve( |
| | | 982 | | int m, |
| | | 983 | | int k, |
| | | 984 | | BigInteger a, |
| | | 985 | | BigInteger b) |
| | | 986 | | : this(m, k, 0, 0, a, b, null, null) |
| | | 987 | | { |
| | | 988 | | } |
| | | 989 | | |
| | | 990 | | /** |
| | | 991 | | * Constructor for Trinomial Polynomial Basis (TPB). |
| | | 992 | | * @param m The exponent <code>m</code> of |
| | | 993 | | * <code>F<sub>2<sup>m</sup></sub></code>. |
| | | 994 | | * @param k The integer <code>k</code> where <code>x<sup>m</sup> + |
| | | 995 | | * x<sup>k</sup> + 1</code> represents the reduction |
| | | 996 | | * polynomial <code>f(z)</code>. |
| | | 997 | | * @param a The coefficient <code>a</code> in the Weierstrass equation |
| | | 998 | | * for non-supersingular elliptic curves over |
| | | 999 | | * <code>F<sub>2<sup>m</sup></sub></code>. |
| | | 1000 | | * @param b The coefficient <code>b</code> in the Weierstrass equation |
| | | 1001 | | * for non-supersingular elliptic curves over |
| | | 1002 | | * <code>F<sub>2<sup>m</sup></sub></code>. |
| | | 1003 | | * @param order The order of the main subgroup of the elliptic curve. |
| | | 1004 | | * @param cofactor The cofactor of the elliptic curve, i.e. |
| | | 1005 | | * <code>#E<sub>a</sub>(F<sub>2<sup>m</sup></sub>) = h * n</code>. |
| | | 1006 | | */ |
| | | 1007 | | public F2mCurve( |
| | | 1008 | | int m, |
| | | 1009 | | int k, |
| | | 1010 | | BigInteger a, |
| | | 1011 | | BigInteger b, |
| | | 1012 | | BigInteger order, |
| | | 1013 | | BigInteger cofactor) |
| | | 1014 | | : this(m, k, 0, 0, a, b, order, cofactor) |
| | | 1015 | | { |
| | | 1016 | | } |
| | | 1017 | | |
| | | 1018 | | /** |
| | | 1019 | | * Constructor for Pentanomial Polynomial Basis (PPB). |
| | | 1020 | | * @param m The exponent <code>m</code> of |
| | | 1021 | | * <code>F<sub>2<sup>m</sup></sub></code>. |
| | | 1022 | | * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> + |
| | | 1023 | | * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> |
| | | 1024 | | * represents the reduction polynomial <code>f(z)</code>. |
| | | 1025 | | * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> + |
| | | 1026 | | * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> |
| | | 1027 | | * represents the reduction polynomial <code>f(z)</code>. |
| | | 1028 | | * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> + |
| | | 1029 | | * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> |
| | | 1030 | | * represents the reduction polynomial <code>f(z)</code>. |
| | | 1031 | | * @param a The coefficient <code>a</code> in the Weierstrass equation |
| | | 1032 | | * for non-supersingular elliptic curves over |
| | | 1033 | | * <code>F<sub>2<sup>m</sup></sub></code>. |
| | | 1034 | | * @param b The coefficient <code>b</code> in the Weierstrass equation |
| | | 1035 | | * for non-supersingular elliptic curves over |
| | | 1036 | | * <code>F<sub>2<sup>m</sup></sub></code>. |
| | | 1037 | | */ |
| | | 1038 | | [Obsolete("Use constructor taking order/cofactor")] |
| | | 1039 | | public F2mCurve( |
| | | 1040 | | int m, |
| | | 1041 | | int k1, |
| | | 1042 | | int k2, |
| | | 1043 | | int k3, |
| | | 1044 | | BigInteger a, |
| | | 1045 | | BigInteger b) |
| | | 1046 | | : this(m, k1, k2, k3, a, b, null, null) |
| | | 1047 | | { |
| | | 1048 | | } |
| | | 1049 | | |
| | | 1050 | | /** |
| | | 1051 | | * Constructor for Pentanomial Polynomial Basis (PPB). |
| | | 1052 | | * @param m The exponent <code>m</code> of |
| | | 1053 | | * <code>F<sub>2<sup>m</sup></sub></code>. |
| | | 1054 | | * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> + |
| | | 1055 | | * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> |
| | | 1056 | | * represents the reduction polynomial <code>f(z)</code>. |
| | | 1057 | | * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> + |
| | | 1058 | | * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> |
| | | 1059 | | * represents the reduction polynomial <code>f(z)</code>. |
| | | 1060 | | * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> + |
| | | 1061 | | * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> |
| | | 1062 | | * represents the reduction polynomial <code>f(z)</code>. |
| | | 1063 | | * @param a The coefficient <code>a</code> in the Weierstrass equation |
| | | 1064 | | * for non-supersingular elliptic curves over |
| | | 1065 | | * <code>F<sub>2<sup>m</sup></sub></code>. |
| | | 1066 | | * @param b The coefficient <code>b</code> in the Weierstrass equation |
| | | 1067 | | * for non-supersingular elliptic curves over |
| | | 1068 | | * <code>F<sub>2<sup>m</sup></sub></code>. |
| | | 1069 | | * @param order The order of the main subgroup of the elliptic curve. |
| | | 1070 | | * @param cofactor The cofactor of the elliptic curve, i.e. |
| | | 1071 | | * <code>#E<sub>a</sub>(F<sub>2<sup>m</sup></sub>) = h * n</code>. |
| | | 1072 | | */ |
| | | 1073 | | public F2mCurve( |
| | | 1074 | | int m, |
| | | 1075 | | int k1, |
| | | 1076 | | int k2, |
| | | 1077 | | int k3, |
| | | 1078 | | BigInteger a, |
| | | 1079 | | BigInteger b, |
| | | 1080 | | BigInteger order, |
| | | 1081 | | BigInteger cofactor) |
| | | 1082 | | : base(m, k1, k2, k3) |
| | | 1083 | | { |
| | | 1084 | | this.m = m; |
| | | 1085 | | this.k1 = k1; |
| | | 1086 | | this.k2 = k2; |
| | | 1087 | | this.k3 = k3; |
| | | 1088 | | this.m_order = order; |
| | | 1089 | | this.m_cofactor = cofactor; |
| | | 1090 | | this.m_infinity = new F2mPoint(this, null, null, false); |
| | | 1091 | | |
| | | 1092 | | if (k1 == 0) |
| | | 1093 | | throw new ArgumentException("k1 must be > 0"); |
| | | 1094 | | |
| | | 1095 | | if (k2 == 0) |
| | | 1096 | | { |
| | | 1097 | | if (k3 != 0) |
| | | 1098 | | throw new ArgumentException("k3 must be 0 if k2 == 0"); |
| | | 1099 | | } |
| | | 1100 | | else |
| | | 1101 | | { |
| | | 1102 | | if (k2 <= k1) |
| | | 1103 | | throw new ArgumentException("k2 must be > k1"); |
| | | 1104 | | |
| | | 1105 | | if (k3 <= k2) |
| | | 1106 | | throw new ArgumentException("k3 must be > k2"); |
| | | 1107 | | } |
| | | 1108 | | |
| | | 1109 | | this.m_a = FromBigInteger(a); |
| | | 1110 | | this.m_b = FromBigInteger(b); |
| | | 1111 | | this.m_coord = F2M_DEFAULT_COORDS; |
| | | 1112 | | } |
| | | 1113 | | |
| | | 1114 | | protected F2mCurve(int m, int k1, int k2, int k3, ECFieldElement a, ECFieldElement b, BigInteger order, BigInteg |
| | | 1115 | | : base(m, k1, k2, k3) |
| | | 1116 | | { |
| | | 1117 | | this.m = m; |
| | | 1118 | | this.k1 = k1; |
| | | 1119 | | this.k2 = k2; |
| | | 1120 | | this.k3 = k3; |
| | | 1121 | | this.m_order = order; |
| | | 1122 | | this.m_cofactor = cofactor; |
| | | 1123 | | |
| | | 1124 | | this.m_infinity = new F2mPoint(this, null, null, false); |
| | | 1125 | | this.m_a = a; |
| | | 1126 | | this.m_b = b; |
| | | 1127 | | this.m_coord = F2M_DEFAULT_COORDS; |
| | | 1128 | | } |
| | | 1129 | | |
| | | 1130 | | protected override ECCurve CloneCurve() |
| | | 1131 | | { |
| | | 1132 | | return new F2mCurve(m, k1, k2, k3, m_a, m_b, m_order, m_cofactor); |
| | | 1133 | | } |
| | | 1134 | | |
| | | 1135 | | public override bool SupportsCoordinateSystem(int coord) |
| | | 1136 | | { |
| | | 1137 | | switch (coord) |
| | | 1138 | | { |
| | | 1139 | | case COORD_AFFINE: |
| | | 1140 | | case COORD_HOMOGENEOUS: |
| | | 1141 | | case COORD_LAMBDA_PROJECTIVE: |
| | | 1142 | | return true; |
| | | 1143 | | default: |
| | | 1144 | | return false; |
| | | 1145 | | } |
| | | 1146 | | } |
| | | 1147 | | |
| | | 1148 | | protected override ECMultiplier CreateDefaultMultiplier() |
| | | 1149 | | { |
| | | 1150 | | if (IsKoblitz) |
| | | 1151 | | { |
| | | 1152 | | return new WTauNafMultiplier(); |
| | | 1153 | | } |
| | | 1154 | | |
| | | 1155 | | return base.CreateDefaultMultiplier(); |
| | | 1156 | | } |
| | | 1157 | | |
| | | 1158 | | public override int FieldSize |
| | | 1159 | | { |
| | | 1160 | | get { return m; } |
| | | 1161 | | } |
| | | 1162 | | |
| | | 1163 | | public override ECFieldElement FromBigInteger(BigInteger x) |
| | | 1164 | | { |
| | | 1165 | | return new F2mFieldElement(this.m, this.k1, this.k2, this.k3, x); |
| | | 1166 | | } |
| | | 1167 | | |
| | | 1168 | | protected internal override ECPoint CreateRawPoint(ECFieldElement x, ECFieldElement y, bool withCompression) |
| | | 1169 | | { |
| | | 1170 | | return new F2mPoint(this, x, y, withCompression); |
| | | 1171 | | } |
| | | 1172 | | |
| | | 1173 | | protected internal override ECPoint CreateRawPoint(ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, bool |
| | | 1174 | | { |
| | | 1175 | | return new F2mPoint(this, x, y, zs, withCompression); |
| | | 1176 | | } |
| | | 1177 | | |
| | | 1178 | | public override ECPoint Infinity |
| | | 1179 | | { |
| | | 1180 | | get { return m_infinity; } |
| | | 1181 | | } |
| | | 1182 | | |
| | | 1183 | | public int M |
| | | 1184 | | { |
| | | 1185 | | get { return m; } |
| | | 1186 | | } |
| | | 1187 | | |
| | | 1188 | | /** |
| | | 1189 | | * Return true if curve uses a Trinomial basis. |
| | | 1190 | | * |
| | | 1191 | | * @return true if curve Trinomial, false otherwise. |
| | | 1192 | | */ |
| | | 1193 | | public bool IsTrinomial() |
| | | 1194 | | { |
| | | 1195 | | return k2 == 0 && k3 == 0; |
| | | 1196 | | } |
| | | 1197 | | |
| | | 1198 | | public int K1 |
| | | 1199 | | { |
| | | 1200 | | get { return k1; } |
| | | 1201 | | } |
| | | 1202 | | |
| | | 1203 | | public int K2 |
| | | 1204 | | { |
| | | 1205 | | get { return k2; } |
| | | 1206 | | } |
| | | 1207 | | |
| | | 1208 | | public int K3 |
| | | 1209 | | { |
| | | 1210 | | get { return k3; } |
| | | 1211 | | } |
| | | 1212 | | |
| | | 1213 | | public override ECLookupTable CreateCacheSafeLookupTable(ECPoint[] points, int off, int len) |
| | | 1214 | | { |
| | | 1215 | | int FE_LONGS = (m + 63) / 64; |
| | | 1216 | | |
| | | 1217 | | long[] table = new long[len * FE_LONGS * 2]; |
| | | 1218 | | { |
| | | 1219 | | int pos = 0; |
| | | 1220 | | for (int i = 0; i < len; ++i) |
| | | 1221 | | { |
| | | 1222 | | ECPoint p = points[off + i]; |
| | | 1223 | | ((F2mFieldElement)p.RawXCoord).x.CopyTo(table, pos); pos += FE_LONGS; |
| | | 1224 | | ((F2mFieldElement)p.RawYCoord).x.CopyTo(table, pos); pos += FE_LONGS; |
| | | 1225 | | } |
| | | 1226 | | } |
| | | 1227 | | |
| | | 1228 | | return new DefaultF2mLookupTable(this, table, len); |
| | | 1229 | | } |
| | | 1230 | | |
| | | 1231 | | private class DefaultF2mLookupTable |
| | | 1232 | | : ECLookupTable |
| | | 1233 | | { |
| | | 1234 | | private readonly F2mCurve m_outer; |
| | | 1235 | | private readonly long[] m_table; |
| | | 1236 | | private readonly int m_size; |
| | | 1237 | | |
| | | 1238 | | internal DefaultF2mLookupTable(F2mCurve outer, long[] table, int size) |
| | | 1239 | | { |
| | | 1240 | | this.m_outer = outer; |
| | | 1241 | | this.m_table = table; |
| | | 1242 | | this.m_size = size; |
| | | 1243 | | } |
| | | 1244 | | |
| | | 1245 | | public virtual int Size |
| | | 1246 | | { |
| | | 1247 | | get { return m_size; } |
| | | 1248 | | } |
| | | 1249 | | |
| | | 1250 | | public virtual ECPoint Lookup(int index) |
| | | 1251 | | { |
| | | 1252 | | int m = m_outer.m; |
| | | 1253 | | int[] ks = m_outer.IsTrinomial() ? new int[]{ m_outer.k1 } : new int[]{ m_outer.k1, m_outer.k2, m_outer. |
| | | 1254 | | |
| | | 1255 | | int FE_LONGS = (m_outer.m + 63) / 64; |
| | | 1256 | | long[] x = new long[FE_LONGS], y = new long[FE_LONGS]; |
| | | 1257 | | int pos = 0; |
| | | 1258 | | |
| | | 1259 | | for (int i = 0; i < m_size; ++i) |
| | | 1260 | | { |
| | | 1261 | | long MASK =((i ^ index) - 1) >> 31; |
| | | 1262 | | |
| | | 1263 | | for (int j = 0; j < FE_LONGS; ++j) |
| | | 1264 | | { |
| | | 1265 | | x[j] ^= m_table[pos + j] & MASK; |
| | | 1266 | | y[j] ^= m_table[pos + FE_LONGS + j] & MASK; |
| | | 1267 | | } |
| | | 1268 | | |
| | | 1269 | | pos += (FE_LONGS * 2); |
| | | 1270 | | } |
| | | 1271 | | |
| | | 1272 | | ECFieldElement X = new F2mFieldElement(m, ks, new LongArray(x)); |
| | | 1273 | | ECFieldElement Y = new F2mFieldElement(m, ks, new LongArray(y)); |
| | | 1274 | | return m_outer.CreateRawPoint(X, Y, false); |
| | | 1275 | | } |
| | | 1276 | | } |
| | | 1277 | | } |
| | | 1278 | | } |