1 package org.bouncycastle.asn1; 2 3 import java.io.IOException; 4 import java.util.Enumeration; 5 import java.util.Iterator; 6 import java.util.NoSuchElementException; 7 8 import org.bouncycastle.util.Arrays; 9 10 /** 11 * ASN.1 <code>SET</code> and <code>SET OF</code> constructs. 12 * <p> 13 * Note: This does not know which syntax the set is! 14 * (The difference: ordering of SET elements or not ordering.) 15 * </p><p> 16 * DER form is always definite form length fields, while 17 * BER support uses indefinite form. 18 * </p><p> 19 * The CER form support does not exist. 20 * </p><p> 21 * <h2>X.690</h2> 22 * <h3>8: Basic encoding rules</h3> 23 * <h4>8.11 Encoding of a set value </h4> 24 * <b>8.11.1</b> The encoding of a set value shall be constructed 25 * <p> 26 * <b>8.11.2</b> The contents octets shall consist of the complete 27 * encoding of a data value from each of the types listed in the 28 * ASN.1 definition of the set type, in an order chosen by the sender, 29 * unless the type was referenced with the keyword 30 * <b>OPTIONAL</b> or the keyword <b>DEFAULT</b>. 31 * </p><p> 32 * <b>8.11.3</b> The encoding of a data value may, but need not, 33 * be present for a type which was referenced with the keyword 34 * <b>OPTIONAL</b> or the keyword <b>DEFAULT</b>. 35 * <blockquote> 36 * NOTE — The order of data values in a set value is not significant, 37 * and places no constraints on the order during transfer 38 * </blockquote> 39 * <h4>8.12 Encoding of a set-of value</h4> 40 * <p> 41 * <b>8.12.1</b> The encoding of a set-of value shall be constructed. 42 * </p><p> 43 * <b>8.12.2</b> The text of 8.10.2 applies: 44 * <i>The contents octets shall consist of zero, 45 * one or more complete encodings of data values from the type listed in 46 * the ASN.1 definition.</i> 47 * </p><p> 48 * <b>8.12.3</b> The order of data values need not be preserved by 49 * the encoding and subsequent decoding. 50 * 51 * <h3>9: Canonical encoding rules</h3> 52 * <h4>9.1 Length forms</h4> 53 * If the encoding is constructed, it shall employ the indefinite-length form. 54 * If the encoding is primitive, it shall include the fewest length octets necessary. 55 * [Contrast with 8.1.3.2 b).] 56 * <h4>9.3 Set components</h4> 57 * The encodings of the component values of a set value shall 58 * appear in an order determined by their tags as specified 59 * in 8.6 of ITU-T Rec. X.680 | ISO/IEC 8824-1. 60 * Additionally, for the purposes of determining the order in which 61 * components are encoded when one or more component is an untagged 62 * choice type, each untagged choice type is ordered as though it 63 * has a tag equal to that of the smallest tag in that choice type 64 * or any untagged choice types nested within. 65 * 66 * <h3>10: Distinguished encoding rules</h3> 67 * <h4>10.1 Length forms</h4> 68 * The definite form of length encoding shall be used, 69 * encoded in the minimum number of octets. 70 * [Contrast with 8.1.3.2 b).] 71 * <h4>10.3 Set components</h4> 72 * The encodings of the component values of a set value shall appear 73 * in an order determined by their tags as specified 74 * in 8.6 of ITU-T Rec. X.680 | ISO/IEC 8824-1. 75 * <blockquote> 76 * NOTE — Where a component of the set is an untagged choice type, 77 * the location of that component in the ordering will depend on 78 * the tag of the choice component being encoded. 79 * </blockquote> 80 * 81 * <h3>11: Restrictions on BER employed by both CER and DER</h3> 82 * <h4>11.5 Set and sequence components with default value </h4> 83 * The encoding of a set value or sequence value shall not include 84 * an encoding for any component value which is equal to 85 * its default value. 86 * <h4>11.6 Set-of components </h4> 87 * <p> 88 * The encodings of the component values of a set-of value 89 * shall appear in ascending order, the encodings being compared 90 * as octet strings with the shorter components being padded at 91 * their trailing end with 0-octets. 92 * <blockquote> 93 * NOTE — The padding octets are for comparison purposes only 94 * and do not appear in the encodings. 95 * </blockquote> 96 */ 97 public abstract class ASN1Set 98 extends ASN1Primitive 99 implements org.bouncycastle.util.Iterable<ASN1Encodable> 100 { 101 protected final ASN1Encodable[] elements; 102 protected final boolean isSorted; 103 104 /** 105 * return an ASN1Set from the given object. 106 * 107 * @param obj the object we want converted. 108 * @exception IllegalArgumentException if the object cannot be converted. 109 * @return an ASN1Set instance, or null. 110 */ getInstance( Object obj)111 public static ASN1Set getInstance( 112 Object obj) 113 { 114 if (obj == null || obj instanceof ASN1Set) 115 { 116 return (ASN1Set)obj; 117 } 118 else if (obj instanceof ASN1SetParser) 119 { 120 return ASN1Set.getInstance(((ASN1SetParser)obj).toASN1Primitive()); 121 } 122 else if (obj instanceof byte[]) 123 { 124 try 125 { 126 return ASN1Set.getInstance(ASN1Primitive.fromByteArray((byte[])obj)); 127 } 128 catch (IOException e) 129 { 130 throw new IllegalArgumentException("failed to construct set from byte[]: " + e.getMessage()); 131 } 132 } 133 else if (obj instanceof ASN1Encodable) 134 { 135 ASN1Primitive primitive = ((ASN1Encodable)obj).toASN1Primitive(); 136 137 if (primitive instanceof ASN1Set) 138 { 139 return (ASN1Set)primitive; 140 } 141 } 142 143 throw new IllegalArgumentException("unknown object in getInstance: " + obj.getClass().getName()); 144 } 145 146 /** 147 * Return an ASN1 set from a tagged object. There is a special 148 * case here, if an object appears to have been explicitly tagged on 149 * reading but we were expecting it to be implicitly tagged in the 150 * normal course of events it indicates that we lost the surrounding 151 * set - so we need to add it back (this will happen if the tagged 152 * object is a sequence that contains other sequences). If you are 153 * dealing with implicitly tagged sets you really <b>should</b> 154 * be using this method. 155 * 156 * @param taggedObject the tagged object. 157 * @param explicit true if the object is meant to be explicitly tagged 158 * false otherwise. 159 * @exception IllegalArgumentException if the tagged object cannot 160 * be converted. 161 * @return an ASN1Set instance. 162 */ getInstance( ASN1TaggedObject taggedObject, boolean explicit)163 public static ASN1Set getInstance( 164 ASN1TaggedObject taggedObject, 165 boolean explicit) 166 { 167 if (explicit) 168 { 169 if (!taggedObject.isExplicit()) 170 { 171 throw new IllegalArgumentException("object implicit - explicit expected."); 172 } 173 174 return getInstance(taggedObject.getObject()); 175 } 176 177 ASN1Primitive o = taggedObject.getObject(); 178 179 /* 180 * constructed object which appears to be explicitly tagged and it's really implicit means 181 * we have to add the surrounding set. 182 */ 183 if (taggedObject.isExplicit()) 184 { 185 if (taggedObject instanceof BERTaggedObject) 186 { 187 return new BERSet(o); 188 } 189 190 return new DLSet(o); 191 } 192 193 if (o instanceof ASN1Set) 194 { 195 ASN1Set s = (ASN1Set)o; 196 197 if (taggedObject instanceof BERTaggedObject) 198 { 199 return s; 200 } 201 202 return (ASN1Set)s.toDLObject(); 203 } 204 205 /* 206 * in this case the parser returns a sequence, convert it into a set. 207 */ 208 if (o instanceof ASN1Sequence) 209 { 210 ASN1Sequence s = (ASN1Sequence)o; 211 212 // NOTE: Will force() a LazyEncodedSequence 213 ASN1Encodable[] elements = s.toArrayInternal(); 214 215 if (taggedObject instanceof BERTaggedObject) 216 { 217 return new BERSet(false, elements); 218 } 219 220 return new DLSet(false, elements); 221 } 222 223 throw new IllegalArgumentException("unknown object in getInstance: " + taggedObject.getClass().getName()); 224 } 225 ASN1Set()226 protected ASN1Set() 227 { 228 this.elements = ASN1EncodableVector.EMPTY_ELEMENTS; 229 this.isSorted = true; 230 } 231 232 /** 233 * Create a SET containing one object 234 * @param element object to be added to the SET. 235 */ ASN1Set(ASN1Encodable element)236 protected ASN1Set(ASN1Encodable element) 237 { 238 if (null == element) 239 { 240 throw new NullPointerException("'element' cannot be null"); 241 } 242 243 this.elements = new ASN1Encodable[]{ element }; 244 this.isSorted = true; 245 } 246 247 /** 248 * Create a SET containing a vector of objects. 249 * @param elementVector a vector of objects to make up the SET. 250 * @param doSort true if should be sorted DER style, false otherwise. 251 */ ASN1Set(ASN1EncodableVector elementVector, boolean doSort)252 protected ASN1Set(ASN1EncodableVector elementVector, boolean doSort) 253 { 254 if (null == elementVector) 255 { 256 throw new NullPointerException("'elementVector' cannot be null"); 257 } 258 259 ASN1Encodable[] tmp; 260 if (doSort && elementVector.size() >= 2) 261 { 262 tmp = elementVector.copyElements(); 263 sort(tmp); 264 } 265 else 266 { 267 tmp = elementVector.takeElements(); 268 } 269 270 this.elements = tmp; 271 this.isSorted = doSort || tmp.length < 2; 272 } 273 274 /** 275 * Create a SET containing an array of objects. 276 * @param elements an array of objects to make up the SET. 277 * @param doSort true if should be sorted DER style, false otherwise. 278 */ 279 protected ASN1Set(ASN1Encodable[] elements, boolean doSort) 280 { 281 if (Arrays.isNullOrContainsNull(elements)) 282 { 283 throw new NullPointerException("'elements' cannot be null, or contain null"); 284 } 285 286 ASN1Encodable[] tmp = ASN1EncodableVector.cloneElements(elements); 287 if (doSort && tmp.length >= 2) 288 { 289 sort(tmp); 290 } 291 292 this.elements = tmp; 293 this.isSorted = doSort || tmp.length < 2; 294 } 295 296 ASN1Set(boolean isSorted, ASN1Encodable[] elements) 297 { 298 this.elements = elements; 299 this.isSorted = isSorted || elements.length < 2; 300 } 301 302 public Enumeration getObjects() 303 { 304 return new Enumeration() 305 { 306 private int pos = 0; 307 308 public boolean hasMoreElements() 309 { 310 return pos < elements.length; 311 } 312 313 public Object nextElement() 314 { 315 if (pos < elements.length) 316 { 317 return elements[pos++]; 318 } 319 throw new NoSuchElementException(); 320 } 321 }; 322 } 323 324 /** 325 * return the object at the set position indicated by index. 326 * 327 * @param index the set number (starting at zero) of the object 328 * @return the object at the set position indicated by index. 329 */ 330 public ASN1Encodable getObjectAt(int index) 331 { 332 return elements[index]; 333 } 334 335 /** 336 * return the number of objects in this set. 337 * 338 * @return the number of objects in this set. 339 */ 340 public int size() 341 { 342 return elements.length; 343 } 344 345 public ASN1Encodable[] toArray() 346 { 347 return ASN1EncodableVector.cloneElements(elements); 348 } 349 350 public ASN1SetParser parser() 351 { 352 final int count = size(); 353 354 return new ASN1SetParser() 355 { 356 private int pos = 0; 357 358 public ASN1Encodable readObject() throws IOException 359 { 360 if (count == pos) 361 { 362 return null; 363 } 364 365 ASN1Encodable obj = elements[pos++]; 366 if (obj instanceof ASN1Sequence) 367 { 368 return ((ASN1Sequence)obj).parser(); 369 } 370 if (obj instanceof ASN1Set) 371 { 372 return ((ASN1Set)obj).parser(); 373 } 374 375 return obj; 376 } 377 378 public ASN1Primitive getLoadedObject() 379 { 380 return ASN1Set.this; 381 } 382 383 public ASN1Primitive toASN1Primitive() 384 { 385 return ASN1Set.this; 386 } 387 }; 388 } 389 390 public int hashCode() 391 { 392 // return Arrays.hashCode(elements); 393 int i = elements.length; 394 int hc = i + 1; 395 396 // NOTE: Order-independent contribution of elements to avoid sorting 397 while (--i >= 0) 398 { 399 hc += elements[i].toASN1Primitive().hashCode(); 400 } 401 402 return hc; 403 } 404 405 /** 406 * Change current SET object to be encoded as {@link DERSet}. 407 * This is part of Distinguished Encoding Rules form serialization. 408 */ 409 ASN1Primitive toDERObject() 410 { 411 ASN1Encodable[] tmp; 412 if (isSorted) 413 { 414 tmp = elements; 415 } 416 else 417 { 418 tmp = new ASN1Encodable[elements.length]; 419 System.arraycopy(elements, 0, tmp, 0, tmp.length); 420 sort(tmp); 421 } 422 423 return new DERSet(true, tmp); 424 } 425 426 /** 427 * Change current SET object to be encoded as {@link DLSet}. 428 * This is part of Direct Length form serialization. 429 */ 430 ASN1Primitive toDLObject() 431 { 432 return new DLSet(isSorted, elements); 433 } 434 435 boolean asn1Equals(ASN1Primitive other) 436 { 437 if (!(other instanceof ASN1Set)) 438 { 439 return false; 440 } 441 442 ASN1Set that = (ASN1Set)other; 443 444 int count = this.size(); 445 if (that.size() != count) 446 { 447 return false; 448 } 449 450 DERSet dis = (DERSet)this.toDERObject(); 451 DERSet dat = (DERSet)that.toDERObject(); 452 453 for (int i = 0; i < count; ++i) 454 { 455 ASN1Primitive p1 = dis.elements[i].toASN1Primitive(); 456 ASN1Primitive p2 = dat.elements[i].toASN1Primitive(); 457 458 if (p1 != p2 && !p1.asn1Equals(p2)) 459 { 460 return false; 461 } 462 } 463 464 return true; 465 } 466 467 boolean isConstructed() 468 { 469 return true; 470 } 471 472 abstract void encode(ASN1OutputStream out, boolean withTag) throws IOException; 473 474 public String toString() 475 { 476 int count = size(); 477 if (0 == count) 478 { 479 return "[]"; 480 } 481 482 StringBuffer sb = new StringBuffer(); 483 sb.append('['); 484 for (int i = 0;;) 485 { 486 sb.append(elements[i]); 487 if (++i >= count) 488 { 489 break; 490 } 491 sb.append(", "); 492 } 493 sb.append(']'); 494 return sb.toString(); 495 } 496 497 public Iterator<ASN1Encodable> iterator() 498 { 499 return new Arrays.Iterator<ASN1Encodable>(toArray()); 500 } 501 502 private static byte[] getDEREncoded(ASN1Encodable obj) 503 { 504 try 505 { 506 return obj.toASN1Primitive().getEncoded(ASN1Encoding.DER); 507 } 508 catch (IOException e) 509 { 510 throw new IllegalArgumentException("cannot encode object added to SET"); 511 } 512 } 513 514 /** 515 * return true if a <= b (arrays are assumed padded with zeros). 516 */ 517 private static boolean lessThanOrEqual(byte[] a, byte[] b) 518 { 519 // assert a.length >= 2 && b.length >= 2; 520 521 /* 522 * NOTE: Set elements in DER encodings are ordered first according to their tags (class and 523 * number); the CONSTRUCTED bit is not part of the tag. 524 * 525 * For SET-OF, this is unimportant. All elements have the same tag and DER requires them to 526 * either all be in constructed form or all in primitive form, according to that tag. The 527 * elements are effectively ordered according to their content octets. 528 * 529 * For SET, the elements will have distinct tags, and each will be in constructed or 530 * primitive form accordingly. Failing to ignore the CONSTRUCTED bit could therefore lead to 531 * ordering inversions. 532 */ 533 int a0 = a[0] & ~BERTags.CONSTRUCTED; 534 int b0 = b[0] & ~BERTags.CONSTRUCTED; 535 if (a0 != b0) 536 { 537 return a0 < b0; 538 } 539 540 int last = Math.min(a.length, b.length) - 1; 541 for (int i = 1; i < last; ++i) 542 { 543 if (a[i] != b[i]) 544 { 545 return (a[i] & 0xFF) < (b[i] & 0xFF); 546 } 547 } 548 return (a[last] & 0xFF) <= (b[last] & 0xFF); 549 } 550 551 private static void sort(ASN1Encodable[] t) 552 { 553 int count = t.length; 554 if (count < 2) 555 { 556 return; 557 } 558 559 ASN1Encodable eh = t[0], ei = t[1]; 560 byte[] bh = getDEREncoded(eh), bi = getDEREncoded(ei);; 561 562 if (lessThanOrEqual(bi, bh)) 563 { 564 ASN1Encodable et = ei; ei = eh; eh = et; 565 byte[] bt = bi; bi = bh; bh = bt; 566 } 567 568 for (int i = 2; i < count; ++i) 569 { 570 ASN1Encodable e2 = t[i]; 571 byte[] b2 = getDEREncoded(e2); 572 573 if (lessThanOrEqual(bi, b2)) 574 { 575 t[i - 2] = eh; 576 eh = ei; bh = bi; 577 ei = e2; bi = b2; 578 continue; 579 } 580 581 if (lessThanOrEqual(bh, b2)) 582 { 583 t[i - 2] = eh; 584 eh = e2; bh = b2; 585 continue; 586 } 587 588 int j = i - 1; 589 while (--j > 0) 590 { 591 ASN1Encodable e1 = t[j - 1]; 592 byte[] b1 = getDEREncoded(e1); 593 594 if (lessThanOrEqual(b1, b2)) 595 { 596 break; 597 } 598 599 t[j] = e1; 600 } 601 602 t[j] = e2; 603 } 604 605 t[count - 2] = eh; 606 t[count - 1] = ei; 607 } 608 } 609