Sort DER sets without encoding elements

35 files changed, 593 insertions, 83 deletions

diff --git a/crypto/src/asn1/Asn1GeneralizedTime.cs b/crypto/src/asn1/Asn1GeneralizedTime.cs
index beabbdfa5..affad50e2 100644
--- a/crypto/src/asn1/Asn1GeneralizedTime.cs
+++ b/crypto/src/asn1/Asn1GeneralizedTime.cs
@@ -117,6 +117,17 @@ namespace Org.BouncyCastle.Asn1
             return new PrimitiveEncoding(tagClass, tagNo, GetContents(encoding));
         }
 
+        internal sealed override DerEncoding GetEncodingDer()
+        {
+            return new PrimitiveDerEncoding(Asn1Tags.Universal, Asn1Tags.GeneralizedTime,
+                GetContents(Asn1OutputStream.EncodingDer));
+        }
+
+        internal sealed override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            return new PrimitiveDerEncoding(tagClass, tagNo, GetContents(Asn1OutputStream.EncodingDer));
+        }
+
         protected override bool Asn1Equals(Asn1Object asn1Object)
         {
             if (!(asn1Object is Asn1GeneralizedTime that))
diff --git a/crypto/src/asn1/Asn1Object.cs b/crypto/src/asn1/Asn1Object.cs
index d84350cd2..a0e75c531 100644
--- a/crypto/src/asn1/Asn1Object.cs
+++ b/crypto/src/asn1/Asn1Object.cs
@@ -93,6 +93,10 @@ namespace Org.BouncyCastle.Asn1
 
         internal abstract IAsn1Encoding GetEncodingImplicit(int encoding, int tagClass, int tagNo);
 
+        internal abstract DerEncoding GetEncodingDer();
+
+        internal abstract DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo);
+
         protected abstract bool Asn1Equals(Asn1Object asn1Object);
 		protected abstract int Asn1GetHashCode();
 
diff --git a/crypto/src/asn1/Asn1ObjectDescriptor.cs b/crypto/src/asn1/Asn1ObjectDescriptor.cs
index 13521a744..0d478a46d 100644
--- a/crypto/src/asn1/Asn1ObjectDescriptor.cs
+++ b/crypto/src/asn1/Asn1ObjectDescriptor.cs
@@ -101,6 +101,16 @@ namespace Org.BouncyCastle.Asn1
             return m_baseGraphicString.GetEncodingImplicit(encoding, tagClass, tagNo);
         }
 
+        internal sealed override DerEncoding GetEncodingDer()
+        {
+            return m_baseGraphicString.GetEncodingDerImplicit(Asn1Tags.Universal, Asn1Tags.ObjectDescriptor);
+        }
+
+        internal sealed override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            return m_baseGraphicString.GetEncodingDerImplicit(tagClass, tagNo);
+        }
+
         protected override int Asn1GetHashCode()
         {
             return ~m_baseGraphicString.CallAsn1GetHashCode();
diff --git a/crypto/src/asn1/Asn1OutputStream.cs b/crypto/src/asn1/Asn1OutputStream.cs
index 4770235d3..5fd36aa42 100644
--- a/crypto/src/asn1/Asn1OutputStream.cs
+++ b/crypto/src/asn1/Asn1OutputStream.cs
@@ -181,6 +181,17 @@ namespace Org.BouncyCastle.Asn1
             return contentsEncodings;
         }
 
+        internal static DerEncoding[] GetContentsEncodingsDer(Asn1Encodable[] elements)
+        {
+            int count = elements.Length;
+            DerEncoding[] contentsEncodings = new DerEncoding[count];
+            for (int i = 0; i < count; ++i)
+            {
+                contentsEncodings[i] = elements[i].ToAsn1Object().GetEncodingDer();
+            }
+            return contentsEncodings;
+        }
+
         internal static int GetLengthOfContents(IAsn1Encoding[] contentsEncodings)
         {
             int contentsLength = 0;
diff --git a/crypto/src/asn1/Asn1RelativeOid.cs b/crypto/src/asn1/Asn1RelativeOid.cs
index 3c4bf237a..b7df4b75a 100644
--- a/crypto/src/asn1/Asn1RelativeOid.cs
+++ b/crypto/src/asn1/Asn1RelativeOid.cs
@@ -127,6 +127,16 @@ namespace Org.BouncyCastle.Asn1
             return new PrimitiveEncoding(tagClass, tagNo, GetContents());
         }
 
+        internal sealed override DerEncoding GetEncodingDer()
+        {
+            return new PrimitiveDerEncoding(Asn1Tags.Universal, Asn1Tags.RelativeOid, GetContents());
+        }
+
+        internal sealed override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            return new PrimitiveDerEncoding(tagClass, tagNo, GetContents());
+        }
+
         private void DoOutput(MemoryStream bOut)
         {
             OidTokenizer tok = new OidTokenizer(identifier);
diff --git a/crypto/src/asn1/Asn1Set.cs b/crypto/src/asn1/Asn1Set.cs
index 514c8c77c..0122971f6 100644
--- a/crypto/src/asn1/Asn1Set.cs
+++ b/crypto/src/asn1/Asn1Set.cs
@@ -77,13 +77,13 @@ namespace Org.BouncyCastle.Asn1
             return (Asn1Set)Meta.Instance.GetContextInstance(taggedObject, declaredExplicit);
         }
 
-        internal Asn1Encodable[] m_sortedElements;
         internal readonly Asn1Encodable[] m_elements;
+        internal DerEncoding[] m_sortedDerEncodings;
 
         protected internal Asn1Set()
         {
             m_elements = Asn1EncodableVector.EmptyElements;
-            m_sortedElements = m_elements;
+            m_sortedDerEncodings = null;
         }
 
         protected internal Asn1Set(Asn1Encodable element)
@@ -92,7 +92,7 @@ namespace Org.BouncyCastle.Asn1
                 throw new ArgumentNullException(nameof(element));
 
             m_elements = new Asn1Encodable[]{ element };
-            m_sortedElements = m_elements;
+            m_sortedDerEncodings = null;
         }
 
         protected internal Asn1Set(Asn1Encodable[] elements, bool doSort)
@@ -101,14 +101,15 @@ namespace Org.BouncyCastle.Asn1
                 throw new NullReferenceException("'elements' cannot be null, or contain null");
 
             elements = Asn1EncodableVector.CloneElements(elements);
+            DerEncoding[] sortedDerEncodings = null;
 
             if (doSort && elements.Length > 1)
             {
-                Sort(elements);
+                sortedDerEncodings = SortElements(elements);
             }
 
             m_elements = elements;
-            m_sortedElements = doSort || elements.Length <= 1 ? elements : null;
+            m_sortedDerEncodings = sortedDerEncodings;
         }
 
         protected internal Asn1Set(Asn1EncodableVector elementVector, bool doSort)
@@ -117,24 +118,28 @@ namespace Org.BouncyCastle.Asn1
                 throw new ArgumentNullException(nameof(elementVector));
 
             Asn1Encodable[] elements;
+            DerEncoding[] sortedDerEncodings;
+
             if (doSort && elementVector.Count > 1)
             {
                 elements = elementVector.CopyElements();
-                Sort(elements);
+                sortedDerEncodings = SortElements(elements);
             }
             else
             {
                 elements = elementVector.TakeElements();
+                sortedDerEncodings = null;
             }
 
             m_elements = elements;
-            m_sortedElements = doSort || elementVector.Count <= 1 ? elements : null;
+            m_sortedDerEncodings = sortedDerEncodings;
         }
 
         protected internal Asn1Set(bool isSorted, Asn1Encodable[] elements)
         {
+            Debug.Assert(!isSorted);
             m_elements = elements;
-            m_sortedElements = isSorted || elements.Length <= 1 ? elements : null;
+            m_sortedDerEncodings = null;
         }
 
         System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
@@ -264,65 +269,11 @@ namespace Org.BouncyCastle.Asn1
             return CollectionUtilities.ToString(m_elements);
         }
 
-        internal static void Sort(Asn1Encodable[] elements)
-        {
-            int count = elements.Length;
-            if (count > 1)
-            {
-                byte[][] keys = new byte[count][];
-                for (int i = 0; i < count; ++i)
-                {
-                    keys[i] = elements[i].GetEncoded(Der);
-                }
-                Array.Sort(keys, elements, DerComparer.Instance);
-            }
-        }
-
-        private class DerComparer
-            : IComparer<byte[]>
+        private static DerEncoding[] SortElements(Asn1Encodable[] elements)
         {
-            internal static DerComparer Instance = new DerComparer();
-
-            private DerComparer()
-            {
-            }
-
-            public int Compare(byte[] a, byte[] b)
-            {
-                Debug.Assert(a.Length >= 2 && b.Length >= 2);
-
-                /*
-                 * NOTE: Set elements in DER encodings are ordered first according to their tags (class and
-                 * number); the CONSTRUCTED bit is not part of the tag.
-                 * 
-                 * For SET-OF, this is unimportant. All elements have the same tag and DER requires them to
-                 * either all be in constructed form or all in primitive form, according to that tag. The
-                 * elements are effectively ordered according to their content octets.
-                 * 
-                 * For SET, the elements will have distinct tags, and each will be in constructed or
-                 * primitive form accordingly. Failing to ignore the CONSTRUCTED bit could therefore lead to
-                 * ordering inversions.
-                 */
-                int a0 = a[0] & ~Asn1Tags.Constructed;
-                int b0 = b[0] & ~Asn1Tags.Constructed;
-                if (a0 != b0)
-                    return a0 < b0 ? -1 : 1;
-
-#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
-                int compareLength = System.Math.Min(a.Length, b.Length) - 1;
-                return a.AsSpan(1, compareLength).SequenceCompareTo(b.AsSpan(1, compareLength));
-#else
-                int len = System.Math.Min(a.Length, b.Length);
-                for (int i = 1; i < len; ++i)
-                {
-                    byte ai = a[i], bi = b[i];
-                    if (ai != bi)
-                        return ai < bi ? -1 : 1;
-                }
-                Debug.Assert(a.Length == b.Length);
-                return 0;
-#endif
-            }
+            var derEncodings = Asn1OutputStream.GetContentsEncodingsDer(elements);
+            Array.Sort(derEncodings, elements);
+            return derEncodings;
         }
     }
 }
diff --git a/crypto/src/asn1/Asn1UtcTime.cs b/crypto/src/asn1/Asn1UtcTime.cs
index bd06a3258..bb9b6de8b 100644
--- a/crypto/src/asn1/Asn1UtcTime.cs
+++ b/crypto/src/asn1/Asn1UtcTime.cs
@@ -174,6 +174,17 @@ namespace Org.BouncyCastle.Asn1
             return new PrimitiveEncoding(tagClass, tagNo, GetContents(encoding));
         }
 
+        internal sealed override DerEncoding GetEncodingDer()
+        {
+            return new PrimitiveDerEncoding(Asn1Tags.Universal, Asn1Tags.UtcTime,
+                GetContents(Asn1OutputStream.EncodingDer));
+        }
+
+        internal sealed override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            return new PrimitiveDerEncoding(tagClass, tagNo, GetContents(Asn1OutputStream.EncodingDer));
+        }
+
         protected override bool Asn1Equals(Asn1Object asn1Object)
         {
             if (!(asn1Object is Asn1UtcTime that))
diff --git a/crypto/src/asn1/ConstructedDerEncoding.cs b/crypto/src/asn1/ConstructedDerEncoding.cs
new file mode 100644
index 000000000..3df7841e8
--- /dev/null
+++ b/crypto/src/asn1/ConstructedDerEncoding.cs
@@ -0,0 +1,52 @@
+using System;
+using System.Diagnostics;
+
+namespace Org.BouncyCastle.Asn1
+{
+    internal class ConstructedDerEncoding
+        : DerEncoding
+    {
+        private readonly DerEncoding[] m_contentsElements;
+        private readonly int m_contentsLength;
+
+        internal ConstructedDerEncoding(int tagClass, int tagNo, DerEncoding[] contentsElements)
+            : base(tagClass, tagNo)
+        {
+            Debug.Assert(contentsElements != null);
+            m_contentsElements = contentsElements;
+            m_contentsLength = Asn1OutputStream.GetLengthOfContents(contentsElements);
+        }
+
+        protected internal override int CompareLengthAndContents(DerEncoding other)
+        {
+            if (!(other is ConstructedDerEncoding that))
+                throw new InvalidOperationException();
+
+            if (this.m_contentsLength != that.m_contentsLength)
+                return this.m_contentsLength - that.m_contentsLength;
+
+            int length = System.Math.Min(this.m_contentsElements.Length, that.m_contentsElements.Length);
+            for (int i = 0; i < length; i++)
+            {
+                int c = this.m_contentsElements[i].CompareTo(that.m_contentsElements[i]);
+                if (c != 0)
+                    return c;
+            }
+
+            Debug.Assert(this.m_contentsElements.Length == that.m_contentsElements.Length);
+            return this.m_contentsElements.Length - that.m_contentsElements.Length;
+        }
+
+        public override void Encode(Asn1OutputStream asn1Out)
+        {
+            asn1Out.WriteIdentifier(Asn1Tags.Constructed | m_tagClass, m_tagNo);
+            asn1Out.WriteDL(m_contentsLength);
+            asn1Out.EncodeContents(m_contentsElements);
+        }
+
+        public override int GetLength()
+        {
+            return Asn1OutputStream.GetLengthOfEncodingDL(m_tagNo, m_contentsLength);
+        }
+    }
+}
diff --git a/crypto/src/asn1/DERExternal.cs b/crypto/src/asn1/DERExternal.cs
index 207930062..45d4d663d 100644
--- a/crypto/src/asn1/DERExternal.cs
+++ b/crypto/src/asn1/DERExternal.cs
@@ -156,6 +156,16 @@ namespace Org.BouncyCastle.Asn1
             return BuildSequence().GetEncodingImplicit(encoding, tagClass, tagNo);
         }
 
+        internal sealed override DerEncoding GetEncodingDer()
+        {
+            return BuildSequence().GetEncodingDerImplicit(Asn1Tags.Universal, Asn1Tags.External);
+        }
+
+        internal sealed override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            return BuildSequence().GetEncodingDerImplicit(tagClass, tagNo);
+        }
+
         protected override int Asn1GetHashCode()
 		{
             return Objects.GetHashCode(this.directReference)
diff --git a/crypto/src/asn1/DerBMPString.cs b/crypto/src/asn1/DerBMPString.cs
index bf21fa424..71a3f132e 100644
--- a/crypto/src/asn1/DerBMPString.cs
+++ b/crypto/src/asn1/DerBMPString.cs
@@ -154,6 +154,16 @@ namespace Org.BouncyCastle.Asn1
             return new PrimitiveEncoding(tagClass, tagNo, GetContents());
         }
 
+        internal sealed override DerEncoding GetEncodingDer()
+        {
+            return new PrimitiveDerEncoding(Asn1Tags.Universal, Asn1Tags.BmpString, GetContents());
+        }
+
+        internal sealed override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            return new PrimitiveDerEncoding(tagClass, tagNo, GetContents());
+        }
+
         private byte[] GetContents()
         {
             char[] c = m_str.ToCharArray();
diff --git a/crypto/src/asn1/DerBitString.cs b/crypto/src/asn1/DerBitString.cs
index 44b3bb95a..2712c3056 100644
--- a/crypto/src/asn1/DerBitString.cs
+++ b/crypto/src/asn1/DerBitString.cs
@@ -266,6 +266,38 @@ namespace Org.BouncyCastle.Asn1
             return new PrimitiveEncoding(tagClass, tagNo, contents);
         }
 
+        internal sealed override DerEncoding GetEncodingDer()
+        {
+            int padBits = contents[0];
+            if (padBits != 0)
+            {
+                int last = contents.Length - 1;
+                byte lastBer = contents[last];
+                byte lastDer = (byte)(lastBer & (0xFF << padBits));
+
+                if (lastBer != lastDer)
+                    return new PrimitiveDerEncodingSuffixed(Asn1Tags.Universal, Asn1Tags.BitString, contents, lastDer);
+            }
+
+            return new PrimitiveDerEncoding(Asn1Tags.Universal, Asn1Tags.BitString, contents);
+        }
+
+        internal sealed override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            int padBits = contents[0];
+            if (padBits != 0)
+            {
+                int last = contents.Length - 1;
+                byte lastBer = contents[last];
+                byte lastDer = (byte)(lastBer & (0xFF << padBits));
+
+                if (lastBer != lastDer)
+                    return new PrimitiveDerEncodingSuffixed(tagClass, tagNo, contents, lastDer);
+            }
+
+            return new PrimitiveDerEncoding(tagClass, tagNo, contents);
+        }
+
         protected override int Asn1GetHashCode()
 		{
             if (contents.Length < 2)
diff --git a/crypto/src/asn1/DerBoolean.cs b/crypto/src/asn1/DerBoolean.cs
index 6256db6e0..61a4dddb2 100644
--- a/crypto/src/asn1/DerBoolean.cs
+++ b/crypto/src/asn1/DerBoolean.cs
@@ -112,6 +112,17 @@ namespace Org.BouncyCastle.Asn1
             return new PrimitiveEncoding(tagClass, tagNo, GetContents(encoding));
         }
 
+        internal sealed override DerEncoding GetEncodingDer()
+        {
+            return new PrimitiveDerEncoding(Asn1Tags.Universal, Asn1Tags.Boolean,
+                GetContents(Asn1OutputStream.EncodingDer));
+        }
+
+        internal sealed override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            return new PrimitiveDerEncoding(tagClass, tagNo, GetContents(Asn1OutputStream.EncodingDer));
+        }
+
         protected override bool Asn1Equals(
             Asn1Object asn1Object)
         {
diff --git a/crypto/src/asn1/DerEncoding.cs b/crypto/src/asn1/DerEncoding.cs
new file mode 100644
index 000000000..8de808d8c
--- /dev/null
+++ b/crypto/src/asn1/DerEncoding.cs
@@ -0,0 +1,38 @@
+using System;
+using System.Diagnostics;
+
+namespace Org.BouncyCastle.Asn1
+{
+    internal abstract class DerEncoding
+        : IAsn1Encoding, IComparable<DerEncoding>
+    {
+        protected internal readonly int m_tagClass;
+        protected internal readonly int m_tagNo;
+
+        protected internal DerEncoding(int tagClass, int tagNo)
+        {
+            Debug.Assert((tagClass & Asn1Tags.Private) == tagClass);
+            Debug.Assert(tagNo >= 0);
+            m_tagClass = tagClass;
+            m_tagNo = tagNo;
+        }
+
+        protected internal abstract int CompareLengthAndContents(DerEncoding other);
+
+        public int CompareTo(DerEncoding other)
+        {
+            Debug.Assert(other != null);
+            if (other == null)
+                return 1;
+            if (m_tagClass != other.m_tagClass)
+                return m_tagClass - other.m_tagClass;
+            if (m_tagNo != other.m_tagNo)
+                return m_tagNo - other.m_tagNo;
+            return CompareLengthAndContents(other);
+        }
+
+        public abstract void Encode(Asn1OutputStream asn1Out);
+
+        public abstract int GetLength();
+    }
+}
diff --git a/crypto/src/asn1/DerEnumerated.cs b/crypto/src/asn1/DerEnumerated.cs
index b85c5a43e..f4725513e 100644
--- a/crypto/src/asn1/DerEnumerated.cs
+++ b/crypto/src/asn1/DerEnumerated.cs
@@ -154,6 +154,16 @@ namespace Org.BouncyCastle.Asn1
             return new PrimitiveEncoding(tagClass, tagNo, contents);
         }
 
+        internal sealed override DerEncoding GetEncodingDer()
+        {
+            return new PrimitiveDerEncoding(Asn1Tags.Universal, Asn1Tags.Enumerated, contents);
+        }
+
+        internal sealed override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            return new PrimitiveDerEncoding(tagClass, tagNo, contents);
+        }
+
         protected override bool Asn1Equals(Asn1Object asn1Object)
         {
             DerEnumerated other = asn1Object as DerEnumerated;
diff --git a/crypto/src/asn1/DerGeneralString.cs b/crypto/src/asn1/DerGeneralString.cs
index 6a378307d..bfc6f6fd5 100644
--- a/crypto/src/asn1/DerGeneralString.cs
+++ b/crypto/src/asn1/DerGeneralString.cs
@@ -97,6 +97,16 @@ namespace Org.BouncyCastle.Asn1
             return new PrimitiveEncoding(tagClass, tagNo, m_contents);
         }
 
+        internal sealed override DerEncoding GetEncodingDer()
+        {
+            return new PrimitiveDerEncoding(Asn1Tags.Universal, Asn1Tags.GeneralString, m_contents);
+        }
+
+        internal sealed override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            return new PrimitiveDerEncoding(tagClass, tagNo, m_contents);
+        }
+
         protected override bool Asn1Equals(Asn1Object asn1Object)
         {
             DerGeneralString that = asn1Object as DerGeneralString;
diff --git a/crypto/src/asn1/DerGraphicString.cs b/crypto/src/asn1/DerGraphicString.cs
index 85330eb33..7c3d1edb2 100644
--- a/crypto/src/asn1/DerGraphicString.cs
+++ b/crypto/src/asn1/DerGraphicString.cs
@@ -104,6 +104,16 @@ namespace Org.BouncyCastle.Asn1
             return new PrimitiveEncoding(tagClass, tagNo, m_contents);
         }
 
+        internal sealed override DerEncoding GetEncodingDer()
+        {
+            return new PrimitiveDerEncoding(Asn1Tags.Universal, Asn1Tags.GraphicString, m_contents);
+        }
+
+        internal sealed override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            return new PrimitiveDerEncoding(tagClass, tagNo, m_contents);
+        }
+
         protected override int Asn1GetHashCode()
 		{
             return Arrays.GetHashCode(m_contents);
diff --git a/crypto/src/asn1/DerIA5String.cs b/crypto/src/asn1/DerIA5String.cs
index de2860130..337cf2c2e 100644
--- a/crypto/src/asn1/DerIA5String.cs
+++ b/crypto/src/asn1/DerIA5String.cs
@@ -127,6 +127,16 @@ namespace Org.BouncyCastle.Asn1
             return new PrimitiveEncoding(tagClass, tagNo, m_contents);
         }
 
+        internal sealed override DerEncoding GetEncodingDer()
+        {
+            return new PrimitiveDerEncoding(Asn1Tags.Universal, Asn1Tags.IA5String, m_contents);
+        }
+
+        internal sealed override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            return new PrimitiveDerEncoding(tagClass, tagNo, m_contents);
+        }
+
         protected override bool Asn1Equals(Asn1Object asn1Object)
         {
             DerIA5String that = asn1Object as DerIA5String;
diff --git a/crypto/src/asn1/DerInteger.cs b/crypto/src/asn1/DerInteger.cs
index 663a00169..85585bea3 100644
--- a/crypto/src/asn1/DerInteger.cs
+++ b/crypto/src/asn1/DerInteger.cs
@@ -196,6 +196,16 @@ namespace Org.BouncyCastle.Asn1
             return new PrimitiveEncoding(tagClass, tagNo, bytes);
         }
 
+        internal sealed override DerEncoding GetEncodingDer()
+        {
+            return new PrimitiveDerEncoding(Asn1Tags.Universal, Asn1Tags.Integer, bytes);
+        }
+
+        internal sealed override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            return new PrimitiveDerEncoding(tagClass, tagNo, bytes);
+        }
+
         protected override int Asn1GetHashCode()
 		{
 			return Arrays.GetHashCode(bytes);
diff --git a/crypto/src/asn1/DerNull.cs b/crypto/src/asn1/DerNull.cs
index ddf61391b..de1fe4c96 100644
--- a/crypto/src/asn1/DerNull.cs
+++ b/crypto/src/asn1/DerNull.cs
@@ -26,6 +26,16 @@ namespace Org.BouncyCastle.Asn1
             return new PrimitiveEncoding(tagClass, tagNo, ZeroBytes);
         }
 
+        internal sealed override DerEncoding GetEncodingDer()
+        {
+            return new PrimitiveDerEncoding(Asn1Tags.Universal, Asn1Tags.Null, ZeroBytes);
+        }
+
+        internal sealed override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            return new PrimitiveDerEncoding(tagClass, tagNo, ZeroBytes);
+        }
+
         protected override bool Asn1Equals(Asn1Object asn1Object)
 		{
 			return asn1Object is DerNull;
diff --git a/crypto/src/asn1/DerNumericString.cs b/crypto/src/asn1/DerNumericString.cs
index 819d946b1..2daca8b66 100644
--- a/crypto/src/asn1/DerNumericString.cs
+++ b/crypto/src/asn1/DerNumericString.cs
@@ -127,6 +127,16 @@ namespace Org.BouncyCastle.Asn1
             return new PrimitiveEncoding(tagClass, tagNo, m_contents);
         }
 
+        internal sealed override DerEncoding GetEncodingDer()
+        {
+            return new PrimitiveDerEncoding(Asn1Tags.Universal, Asn1Tags.NumericString, m_contents);
+        }
+
+        internal sealed override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            return new PrimitiveDerEncoding(tagClass, tagNo, m_contents);
+        }
+
         protected override bool Asn1Equals(Asn1Object asn1Object)
 		{
 			DerNumericString that = asn1Object as DerNumericString;
diff --git a/crypto/src/asn1/DerObjectIdentifier.cs b/crypto/src/asn1/DerObjectIdentifier.cs
index 44388d51f..835f18d3d 100644
--- a/crypto/src/asn1/DerObjectIdentifier.cs
+++ b/crypto/src/asn1/DerObjectIdentifier.cs
@@ -158,6 +158,16 @@ namespace Org.BouncyCastle.Asn1
             return new PrimitiveEncoding(tagClass, tagNo, GetContents());
         }
 
+        internal sealed override DerEncoding GetEncodingDer()
+        {
+            return new PrimitiveDerEncoding(Asn1Tags.Universal, Asn1Tags.ObjectIdentifier, GetContents());
+        }
+
+        internal sealed override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            return new PrimitiveDerEncoding(tagClass, tagNo, GetContents());
+        }
+
         private void DoOutput(MemoryStream bOut)
         {
             OidTokenizer tok = new OidTokenizer(identifier);
diff --git a/crypto/src/asn1/DerOctetString.cs b/crypto/src/asn1/DerOctetString.cs
index ea13765ec..3680a6fd4 100644
--- a/crypto/src/asn1/DerOctetString.cs
+++ b/crypto/src/asn1/DerOctetString.cs
@@ -31,6 +31,16 @@ namespace Org.BouncyCastle.Asn1
             return new PrimitiveEncoding(tagClass, tagNo, contents);
         }
 
+        internal sealed override DerEncoding GetEncodingDer()
+        {
+            return new PrimitiveDerEncoding(Asn1Tags.Universal, Asn1Tags.OctetString, contents);
+        }
+
+        internal sealed override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            return new PrimitiveDerEncoding(tagClass, tagNo, contents);
+        }
+
         internal static void Encode(Asn1OutputStream asn1Out, byte[] buf, int off, int len)
 		{
             asn1Out.WriteIdentifier(Asn1Tags.Universal, Asn1Tags.OctetString);
diff --git a/crypto/src/asn1/DerPrintableString.cs b/crypto/src/asn1/DerPrintableString.cs
index 5830afa47..563e6fb58 100644
--- a/crypto/src/asn1/DerPrintableString.cs
+++ b/crypto/src/asn1/DerPrintableString.cs
@@ -127,6 +127,16 @@ namespace Org.BouncyCastle.Asn1
             return new PrimitiveEncoding(tagClass, tagNo, m_contents);
         }
 
+        internal sealed override DerEncoding GetEncodingDer()
+        {
+            return new PrimitiveDerEncoding(Asn1Tags.Universal, Asn1Tags.PrintableString, m_contents);
+        }
+
+        internal sealed override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            return new PrimitiveDerEncoding(tagClass, tagNo, m_contents);
+        }
+
         protected override bool Asn1Equals(
 			Asn1Object asn1Object)
 		{
diff --git a/crypto/src/asn1/DerSequence.cs b/crypto/src/asn1/DerSequence.cs
index a1d93d0da..43d1a9167 100644
--- a/crypto/src/asn1/DerSequence.cs
+++ b/crypto/src/asn1/DerSequence.cs
@@ -66,6 +66,18 @@ namespace Org.BouncyCastle.Asn1
                 Asn1OutputStream.GetContentsEncodings(Asn1OutputStream.EncodingDer, elements));
         }
 
+        internal override DerEncoding GetEncodingDer()
+        {
+            return new ConstructedDerEncoding(Asn1Tags.Universal, Asn1Tags.Sequence,
+                Asn1OutputStream.GetContentsEncodingsDer(elements));
+        }
+
+        internal override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            return new ConstructedDerEncoding(tagClass, tagNo,
+                Asn1OutputStream.GetContentsEncodingsDer(elements));
+        }
+
         internal override DerBitString ToAsn1BitString()
         {
             return new DerBitString(BerBitString.FlattenBitStrings(GetConstructedBitStrings()), false);
diff --git a/crypto/src/asn1/DerSet.cs b/crypto/src/asn1/DerSet.cs
index db4c7b1a2..99a8dc284 100644
--- a/crypto/src/asn1/DerSet.cs
+++ b/crypto/src/asn1/DerSet.cs
@@ -1,5 +1,7 @@
 using System;
 
+using Org.BouncyCastle.Utilities;
+
 namespace Org.BouncyCastle.Asn1
 {
 	/**
@@ -61,31 +63,37 @@ namespace Org.BouncyCastle.Asn1
 
         internal override IAsn1Encoding GetEncoding(int encoding)
         {
-            return new ConstructedDLEncoding(Asn1Tags.Universal, Asn1Tags.Set,
-                Asn1OutputStream.GetContentsEncodings(Asn1OutputStream.EncodingDer, GetSortedElements()));
+            return new ConstructedDLEncoding(Asn1Tags.Universal, Asn1Tags.Set, GetSortedDerEncodings());
         }
 
         internal override IAsn1Encoding GetEncodingImplicit(int encoding, int tagClass, int tagNo)
         {
-            return new ConstructedDLEncoding(tagClass, tagNo,
-                Asn1OutputStream.GetContentsEncodings(Asn1OutputStream.EncodingDer, GetSortedElements()));
+            return new ConstructedDLEncoding(tagClass, tagNo, GetSortedDerEncodings());
         }
 
-        private Asn1Encodable[] GetSortedElements()
+        internal override DerEncoding GetEncodingDer()
         {
-			if (m_sortedElements == null)
-			{
-                int count = m_elements.Length;
-                Asn1Object[] asn1Objects = new Asn1Object[count];
-                for (int i = 0; i < count; ++i)
-                {
-                    asn1Objects[i] = m_elements[i].ToAsn1Object();
-                }
-				Sort(asn1Objects);
-                m_sortedElements = asn1Objects;
-            }
+            return new ConstructedDerEncoding(Asn1Tags.Universal, Asn1Tags.Set, GetSortedDerEncodings());
+        }
+
+        internal override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            return new ConstructedDerEncoding(tagClass, tagNo, GetSortedDerEncodings());
+        }
 
-			return m_sortedElements;
+        private DerEncoding[] GetSortedDerEncodings()
+        {
+            return Objects.EnsureSingletonInitialized(ref m_sortedDerEncodings, m_elements, CreateSortedDerEncodings);
+        }
+
+        private static DerEncoding[] CreateSortedDerEncodings(Asn1Encodable[] elements)
+        {
+            var derEncodings = Asn1OutputStream.GetContentsEncodingsDer(elements);
+            if (derEncodings.Length > 1)
+            {
+                Array.Sort(derEncodings);
+            }
+            return derEncodings;
         }
     }
 }
diff --git a/crypto/src/asn1/DerT61String.cs b/crypto/src/asn1/DerT61String.cs
index 45f57ae0a..998a43bc2 100644
--- a/crypto/src/asn1/DerT61String.cs
+++ b/crypto/src/asn1/DerT61String.cs
@@ -107,6 +107,16 @@ namespace Org.BouncyCastle.Asn1
             return new PrimitiveEncoding(tagClass, tagNo, m_contents);
         }
 
+        internal sealed override DerEncoding GetEncodingDer()
+        {
+            return new PrimitiveDerEncoding(Asn1Tags.Universal, Asn1Tags.T61String, m_contents);
+        }
+
+        internal sealed override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            return new PrimitiveDerEncoding(tagClass, tagNo, m_contents);
+        }
+
         public byte[] GetOctets()
         {
             return Arrays.Clone(m_contents);
diff --git a/crypto/src/asn1/DerTaggedObject.cs b/crypto/src/asn1/DerTaggedObject.cs
index dbcc19760..3e8067c0c 100644
--- a/crypto/src/asn1/DerTaggedObject.cs
+++ b/crypto/src/asn1/DerTaggedObject.cs
@@ -69,6 +69,26 @@ namespace Org.BouncyCastle.Asn1
             return new ConstructedDLEncoding(tagClass, tagNo, new IAsn1Encoding[]{ baseObject.GetEncoding(encoding) });
         }
 
+        internal sealed override DerEncoding GetEncodingDer()
+        {
+            Asn1Object baseObject = GetBaseObject().ToAsn1Object();
+
+            if (!IsExplicit())
+                return baseObject.GetEncodingDerImplicit(TagClass, TagNo);
+
+            return new ConstructedDerEncoding(TagClass, TagNo, new DerEncoding[]{ baseObject.GetEncodingDer() });
+        }
+
+        internal sealed override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            Asn1Object baseObject = GetBaseObject().ToAsn1Object();
+
+            if (!IsExplicit())
+                return baseObject.GetEncodingDerImplicit(tagClass, tagNo);
+
+            return new ConstructedDerEncoding(tagClass, tagNo, new DerEncoding[]{ baseObject.GetEncodingDer() });
+        }
+
         internal override Asn1Sequence RebuildConstructed(Asn1Object asn1Object)
         {
             return new DerSequence(asn1Object);
diff --git a/crypto/src/asn1/DerUTF8String.cs b/crypto/src/asn1/DerUTF8String.cs
index 9472f5082..9bee962e7 100644
--- a/crypto/src/asn1/DerUTF8String.cs
+++ b/crypto/src/asn1/DerUTF8String.cs
@@ -116,6 +116,16 @@ namespace Org.BouncyCastle.Asn1
             return new PrimitiveEncoding(tagClass, tagNo, m_contents);
         }
 
+        internal sealed override DerEncoding GetEncodingDer()
+        {
+            return new PrimitiveDerEncoding(Asn1Tags.Universal, Asn1Tags.Utf8String, m_contents);
+        }
+
+        internal sealed override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            return new PrimitiveDerEncoding(tagClass, tagNo, m_contents);
+        }
+
         internal static DerUtf8String CreatePrimitive(byte[] contents)
         {
             return new DerUtf8String(contents, false);
diff --git a/crypto/src/asn1/DerUniversalString.cs b/crypto/src/asn1/DerUniversalString.cs
index 1183ed1f3..d65121ab0 100644
--- a/crypto/src/asn1/DerUniversalString.cs
+++ b/crypto/src/asn1/DerUniversalString.cs
@@ -119,6 +119,16 @@ namespace Org.BouncyCastle.Asn1
             return new PrimitiveEncoding(tagClass, tagNo, m_contents);
         }
 
+        internal sealed override DerEncoding GetEncodingDer()
+        {
+            return new PrimitiveDerEncoding(Asn1Tags.Universal, Asn1Tags.UniversalString, m_contents);
+        }
+
+        internal sealed override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            return new PrimitiveDerEncoding(tagClass, tagNo, m_contents);
+        }
+
         protected override bool Asn1Equals(Asn1Object asn1Object)
         {
             DerUniversalString that = asn1Object as DerUniversalString;
diff --git a/crypto/src/asn1/DerVideotexString.cs b/crypto/src/asn1/DerVideotexString.cs
index 636af0499..5019a6668 100644
--- a/crypto/src/asn1/DerVideotexString.cs
+++ b/crypto/src/asn1/DerVideotexString.cs
@@ -104,6 +104,16 @@ namespace Org.BouncyCastle.Asn1
             return new PrimitiveEncoding(tagClass, tagNo, m_contents);
         }
 
+        internal sealed override DerEncoding GetEncodingDer()
+        {
+            return new PrimitiveDerEncoding(Asn1Tags.Universal, Asn1Tags.VideotexString, m_contents);
+        }
+
+        internal sealed override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            return new PrimitiveDerEncoding(tagClass, tagNo, m_contents);
+        }
+
         protected override bool Asn1Equals(Asn1Object asn1Object)
         {
             DerVideotexString that = asn1Object as DerVideotexString;
diff --git a/crypto/src/asn1/DerVisibleString.cs b/crypto/src/asn1/DerVisibleString.cs
index 77fe54c9a..4c939988e 100644
--- a/crypto/src/asn1/DerVisibleString.cs
+++ b/crypto/src/asn1/DerVisibleString.cs
@@ -112,6 +112,16 @@ namespace Org.BouncyCastle.Asn1
             return new PrimitiveEncoding(tagClass, tagNo, m_contents);
         }
 
+        internal sealed override DerEncoding GetEncodingDer()
+        {
+            return new PrimitiveDerEncoding(Asn1Tags.Universal, Asn1Tags.VisibleString, m_contents);
+        }
+
+        internal sealed override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            return new PrimitiveDerEncoding(tagClass, tagNo, m_contents);
+        }
+
         protected override bool Asn1Equals(Asn1Object asn1Object)
         {
             DerVisibleString that = asn1Object as DerVisibleString;
diff --git a/crypto/src/asn1/PrimitiveDerEncoding.cs b/crypto/src/asn1/PrimitiveDerEncoding.cs
new file mode 100644
index 000000000..ef5f67b26
--- /dev/null
+++ b/crypto/src/asn1/PrimitiveDerEncoding.cs
@@ -0,0 +1,56 @@
+using System;
+using System.Diagnostics;
+
+namespace Org.BouncyCastle.Asn1
+{
+    internal class PrimitiveDerEncoding
+        : DerEncoding
+    {
+        internal readonly byte[] m_contentsOctets;
+
+        internal PrimitiveDerEncoding(int tagClass, int tagNo, byte[] contentsOctets)
+            : base (tagClass, tagNo)
+        {
+            Debug.Assert(contentsOctets != null);
+            m_contentsOctets = contentsOctets;
+        }
+
+        protected internal override int CompareLengthAndContents(DerEncoding other)
+        {
+            if (other is PrimitiveDerEncodingSuffixed suffixed)
+                return -suffixed.CompareLengthAndContents(this);
+
+            if (!(other is PrimitiveDerEncoding that))
+                throw new InvalidOperationException();
+
+            int length = this.m_contentsOctets.Length;
+            if (length != that.m_contentsOctets.Length)
+                return length - that.m_contentsOctets.Length;
+
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+            return this.m_contentsOctets.AsSpan(0, length).SequenceCompareTo(
+                   that.m_contentsOctets.AsSpan(0, length));
+#else
+            for (int i = 0; i < length; i++)
+            {
+                byte ai = this.m_contentsOctets[i], bi = that.m_contentsOctets[i];
+                if (ai != bi)
+                    return ai - bi;
+            }
+            return 0;
+#endif
+        }
+
+        public override void Encode(Asn1OutputStream asn1Out)
+        {
+            asn1Out.WriteIdentifier(m_tagClass, m_tagNo);
+            asn1Out.WriteDL(m_contentsOctets.Length);
+            asn1Out.Write(m_contentsOctets, 0, m_contentsOctets.Length);
+        }
+
+        public override int GetLength()
+        {
+            return Asn1OutputStream.GetLengthOfEncodingDL(m_tagNo, m_contentsOctets.Length);
+        }
+    }
+}
diff --git a/crypto/src/asn1/PrimitiveDerEncodingSuffixed.cs b/crypto/src/asn1/PrimitiveDerEncodingSuffixed.cs
new file mode 100644
index 000000000..7f9f38d99
--- /dev/null
+++ b/crypto/src/asn1/PrimitiveDerEncodingSuffixed.cs
@@ -0,0 +1,83 @@
+using System;
+using System.Diagnostics;
+
+namespace Org.BouncyCastle.Asn1
+{
+    internal class PrimitiveDerEncodingSuffixed
+        : DerEncoding
+    {
+        private readonly byte[] m_contentsOctets;
+        private readonly byte m_contentsSuffix;
+
+        internal PrimitiveDerEncodingSuffixed(int tagClass, int tagNo, byte[] contentsOctets, byte contentsSuffix)
+            : base(tagClass, tagNo)
+        {
+            Debug.Assert(contentsOctets != null);
+            Debug.Assert(contentsOctets.Length > 0);
+            m_contentsOctets = contentsOctets;
+            m_contentsSuffix = contentsSuffix;
+        }
+
+        protected internal override int CompareLengthAndContents(DerEncoding other)
+        {
+            if (other is PrimitiveDerEncodingSuffixed suff)
+            {
+                return CompareSuffixed(this.m_contentsOctets, this.m_contentsSuffix,
+                                       suff.m_contentsOctets, suff.m_contentsSuffix);
+            }
+            else if (other is PrimitiveDerEncoding that)
+            {
+                int length = that.m_contentsOctets.Length;
+                if (length == 0)
+                    return this.m_contentsOctets.Length;
+
+                return CompareSuffixed(this.m_contentsOctets, this.m_contentsSuffix,
+                                       that.m_contentsOctets, that.m_contentsOctets[length - 1]);
+            }
+            else
+            {
+                throw new InvalidOperationException();
+            }
+        }
+
+        public override void Encode(Asn1OutputStream asn1Out)
+        {
+            asn1Out.WriteIdentifier(m_tagClass, m_tagNo);
+            asn1Out.WriteDL(m_contentsOctets.Length);
+            asn1Out.Write(m_contentsOctets, 0, m_contentsOctets.Length - 1);
+            asn1Out.WriteByte(m_contentsSuffix);
+        }
+
+        public override int GetLength()
+        {
+            return Asn1OutputStream.GetLengthOfEncodingDL(m_tagNo, m_contentsOctets.Length);
+        }
+
+        private static int CompareSuffixed(byte[] octetsA, byte suffixA, byte[] octetsB, byte suffixB)
+        {
+            Debug.Assert(octetsA.Length > 0);
+            Debug.Assert(octetsB.Length > 0);
+
+            int length = octetsA.Length;
+            if (length != octetsB.Length)
+                return length - octetsB.Length;
+
+            int last = length - 1;
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+            int c = octetsA.AsSpan(0, last).SequenceCompareTo(
+                    octetsB.AsSpan(0, last));
+            if (c != 0)
+                return c;
+#else
+            for (int i = 0; i < last; i++)
+            {
+                byte ai = octetsA[i], bi = octetsB[i];
+                if (ai != bi)
+                    return ai - bi;
+            }
+#endif
+
+            return suffixA - suffixB;
+        }
+    }
+}
diff --git a/crypto/src/pqc/asn1/CmcePrivateKey.cs b/crypto/src/pqc/asn1/CmcePrivateKey.cs
index dba42f6c1..042325d1d 100644
--- a/crypto/src/pqc/asn1/CmcePrivateKey.cs
+++ b/crypto/src/pqc/asn1/CmcePrivateKey.cs
@@ -123,6 +123,16 @@ namespace Org.BouncyCastle.Pqc.Asn1
             return ToAsn1Primitive().GetEncodingImplicit(encoding, tagClass, tagNo);
         }
 
+        internal sealed override DerEncoding GetEncodingDer()
+        {
+            return ToAsn1Primitive().GetEncodingDer();
+        }
+
+        internal sealed override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            return ToAsn1Primitive().GetEncodingDerImplicit(tagClass, tagNo);
+        }
+
         protected override bool Asn1Equals(Asn1Object asn1Object)
         {
             return ToAsn1Primitive().CallAsn1Equals(asn1Object);
diff --git a/crypto/src/pqc/asn1/CmcePublicKey.cs b/crypto/src/pqc/asn1/CmcePublicKey.cs
index e811c0d97..26bd6e438 100644
--- a/crypto/src/pqc/asn1/CmcePublicKey.cs
+++ b/crypto/src/pqc/asn1/CmcePublicKey.cs
@@ -47,6 +47,16 @@ namespace Org.BouncyCastle.Pqc.Asn1
             return ToAsn1Primitive().GetEncodingImplicit(encoding, tagClass, tagNo);
         }
 
+        internal override DerEncoding GetEncodingDer()
+        {
+            return ToAsn1Primitive().GetEncodingDer();
+        }
+
+        internal override DerEncoding GetEncodingDerImplicit(int tagClass, int tagNo)
+        {
+            return ToAsn1Primitive().GetEncodingDerImplicit(tagClass, tagNo);
+        }
+
         protected override bool Asn1Equals(Asn1Object asn1Object)
         {
             return ToAsn1Primitive().CallAsn1Equals(asn1Object);