diff --git a/libcore/auth/src/main/java/javax/security/auth/x500/X500Principal.java b/libcore/auth/src/main/java/javax/security/auth/x500/X500Principal.java
index fa9dfe8..efc57d1 100644
--- a/libcore/auth/src/main/java/javax/security/auth/x500/X500Principal.java
+++ b/libcore/auth/src/main/java/javax/security/auth/x500/X500Principal.java
@@ -141,6 +141,16 @@
         }
     }
 
+// BEGIN android-added
+    private transient String canonicalName;
+    private synchronized String getCanonicalName() {
+        if (canonicalName == null) {
+            canonicalName = dn.getName(CANONICAL);
+        }
+        return canonicalName;
+    }
+// END android-added
+
     @Override
     public boolean equals(Object o) {
         if (this == o) {
@@ -150,7 +160,9 @@
             return false;
         }
         X500Principal principal = (X500Principal) o;
-        return dn.getName(CANONICAL).equals(principal.dn.getName(CANONICAL));
+// BEGIN android-changed
+        return getCanonicalName().equals(principal.getCanonicalName());
+// END android-changed
     }
 
     /**
@@ -196,13 +208,19 @@
      *             mentioned above
      */
     public String getName(String format) {
+// BEGIN android-changed
+        if (CANONICAL.equals(format)) {
+            return getCanonicalName();
+        }
+
         return dn.getName(format);
     }
 
     @Override
     public int hashCode() {
-        return dn.getName(CANONICAL).hashCode();
+        return getCanonicalName().hashCode();
     }
+// END android-changed
 
     @Override
     public String toString() {
diff --git a/libcore/security/src/main/java/org/apache/harmony/security/provider/cert/X509CertImpl.java b/libcore/security/src/main/java/org/apache/harmony/security/provider/cert/X509CertImpl.java
index ccbc4a4..d3b4563 100644
--- a/libcore/security/src/main/java/org/apache/harmony/security/provider/cert/X509CertImpl.java
+++ b/libcore/security/src/main/java/org/apache/harmony/security/provider/cert/X509CertImpl.java
@@ -95,7 +95,9 @@
     private PublicKey publicKey;
 
     // encoding of the certificate
-    private byte[] encoding;
+// BEGIN android-changed
+    private volatile byte[] encoding;
+// END android-changed
 
     //
     // ---------------------- Constructors -------------------------------
diff --git a/libcore/security/src/main/java/org/bouncycastle/jce/provider/CertPathValidatorUtilities.java b/libcore/security/src/main/java/org/bouncycastle/jce/provider/CertPathValidatorUtilities.java
index 56da91a..8383b98 100644
--- a/libcore/security/src/main/java/org/bouncycastle/jce/provider/CertPathValidatorUtilities.java
+++ b/libcore/security/src/main/java/org/bouncycastle/jce/provider/CertPathValidatorUtilities.java
@@ -78,12 +78,13 @@
         "privilegeWithdrawn",
         "aACompromise" };
     
+// BEGIN android-changed
     /**
      * Search the given Set of TrustAnchor's for one that is the
      * issuer of the given X509 certificate.
      *
      * @param cert the X509 certificate
-     * @param trustAnchors a Set of TrustAnchor's
+     * @param params with trust anchors
      *
      * @return the <code>TrustAnchor</code> object if found or
      * <code>null</code> if not.
@@ -93,15 +94,20 @@
      * has thrown an exception. This Exception can be obtainted with
      * <code>getCause()</code> method.
      **/
-    protected static final TrustAnchor findTrustAnchor(
-        X509Certificate cert,
-        CertPath        certPath,
-        int             index,
-        Set             trustAnchors) 
-        throws CertPathValidatorException
-    {
-        Iterator iter = trustAnchors.iterator();
-        TrustAnchor trust = null;
+    static final TrustAnchor findTrustAnchor(
+            X509Certificate cert,
+            CertPath certPath,
+            int index,
+            PKIXParameters params)
+            throws CertPathValidatorException {
+        // If we have a trust anchor index, use it.
+        if (params instanceof IndexedPKIXParameters) {
+            IndexedPKIXParameters indexed = (IndexedPKIXParameters) params;
+            return indexed.findTrustAnchor(cert, certPath, index);
+        }
+
+        Iterator iter = params.getTrustAnchors().iterator();
+        TrustAnchor found = null;
         PublicKey trustPublicKey = null;
         Exception invalidKeyEx = null;
 
@@ -116,65 +122,63 @@
             throw new CertPathValidatorException(ex);
         }
 
-        // BEGIN android-changed
         byte[] certBytes = null;
         try {
             certBytes = cert.getEncoded();
         } catch (Exception e) {
             // ignore, just continue
         }
-        while (iter.hasNext() && trust == null)
+        while (iter.hasNext() && found == null)
         {
-            trust = (TrustAnchor) iter.next();
-            X509Certificate trustCert = trust.getTrustedCert();
-            if (trustCert != null)
+            found = (TrustAnchor) iter.next();
+            X509Certificate foundCert = found.getTrustedCert();
+            if (foundCert != null)
             {
                 // If the trust anchor is identical to the certificate we're
                 // done. Just return the anchor.
                 // There is similar code in PKIXCertPathValidatorSpi.
                 try {
-                    byte[] trustBytes = trustCert.getEncoded();
-                    if (certBytes != null && Arrays.equals(trustBytes,
+                    byte[] foundBytes = foundCert.getEncoded();
+                    if (certBytes != null && Arrays.equals(foundBytes,
                             certBytes)) {
-                        return trust;
+                        return found;
                     }
                 } catch (Exception e) {
                     // ignore, continue and verify the certificate
                 }
-                if (certSelectX509.match(trustCert))
+                if (certSelectX509.match(foundCert))
                 {
-                    trustPublicKey = trustCert.getPublicKey();
+                    trustPublicKey = foundCert.getPublicKey();
                 }
                 else
                 {
-                    trust = null;
+                    found = null;
                 }
-        // END android-changed
             }
-            else if (trust.getCAName() != null
-                    && trust.getCAPublicKey() != null)
+            else if (found.getCAName() != null
+                    && found.getCAPublicKey() != null)
             {
                 try
                 {
                     X500Principal certIssuer = getEncodedIssuerPrincipal(cert);
-                    X500Principal caName = new X500Principal(trust.getCAName());
+                    X500Principal caName = new X500Principal(found.getCAName());
                     if (certIssuer.equals(caName))
                     {
-                        trustPublicKey = trust.getCAPublicKey();
+                        trustPublicKey = found.getCAPublicKey();
                     }
                     else
                     {
-                        trust = null;
+                        found = null;
                     }
                 }
                 catch (IllegalArgumentException ex)
                 {
-                    trust = null;
+                    found = null;
                 }
             }
             else
             {
-                trust = null;
+                found = null;
             }
 
             if (trustPublicKey != null)
@@ -186,18 +190,19 @@
                 catch (Exception ex)
                 {
                     invalidKeyEx = ex;
-                    trust = null;
+                    found = null;
                 }
             }
         }
 
-        if (trust == null && invalidKeyEx != null)
+        if (found == null && invalidKeyEx != null)
         {
             throw new CertPathValidatorException("TrustAnchor found but certificate validation failed.", invalidKeyEx, certPath, index);
         }
 
-        return trust;
+        return found;
     }
+// END android-changed
 
     protected static X500Principal getEncodedIssuerPrincipal(X509Certificate cert)
     {
diff --git a/libcore/security/src/main/java/org/bouncycastle/jce/provider/IndexedPKIXParameters.java b/libcore/security/src/main/java/org/bouncycastle/jce/provider/IndexedPKIXParameters.java
new file mode 100644
index 0000000..e8e834a
--- /dev/null
+++ b/libcore/security/src/main/java/org/bouncycastle/jce/provider/IndexedPKIXParameters.java
@@ -0,0 +1,144 @@
+/*
+ * Copyright (C) 2009 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.bouncycastle.jce.provider;
+
+import javax.security.auth.x500.X500Principal;
+
+import java.security.cert.CertPath;
+import java.security.cert.CertPathValidatorException;
+import java.security.cert.CertificateEncodingException;
+import java.security.cert.PKIXParameters;
+import java.security.cert.TrustAnchor;
+import java.security.cert.X509Certificate;
+import java.security.InvalidAlgorithmParameterException;
+import java.security.KeyStoreException;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.logging.Logger;
+import java.util.logging.Level;
+
+/**
+ * Indexes trust anchors so they can be found in O(1) time instead of O(N).
+ */
+public class IndexedPKIXParameters extends PKIXParameters {
+
+    final Map<Bytes, TrustAnchor> encodings
+            = new HashMap<Bytes, TrustAnchor>();
+    final Map<X500Principal, TrustAnchor> bySubject
+            = new HashMap<X500Principal, TrustAnchor>();
+    final Map<X500Principal, List<TrustAnchor>> byCA
+            = new HashMap<X500Principal, List<TrustAnchor>>();
+
+    public IndexedPKIXParameters(Set<TrustAnchor> anchors)
+            throws KeyStoreException, InvalidAlgorithmParameterException,
+            CertificateEncodingException {
+        super(anchors);
+
+        for (TrustAnchor anchor : anchors) {
+            X509Certificate cert = anchor.getTrustedCert();
+
+            Bytes encoded = new Bytes(cert.getEncoded());
+            encodings.put(encoded, anchor);
+
+            X500Principal subject = cert.getSubjectX500Principal();
+            if (bySubject.put(subject, anchor) != null) {
+                // TODO: Should we allow this?
+                throw new KeyStoreException("Two certs have the same subject: "
+                        + subject);
+            }
+
+            X500Principal ca = anchor.getCA();
+            List<TrustAnchor> caAnchors = byCA.get(ca);
+            if (caAnchors == null) {
+                caAnchors = new ArrayList<TrustAnchor>();
+                byCA.put(ca, caAnchors);
+            }
+            caAnchors.add(anchor);
+        }
+    }
+
+    TrustAnchor findTrustAnchor(X509Certificate cert, CertPath certPath,
+            int index) throws CertPathValidatorException {
+        // Mimic the alg in CertPathValidatorUtilities.findTrustAnchor().
+        Exception verificationException = null;
+        X500Principal issuer = cert.getIssuerX500Principal();
+
+        List<TrustAnchor> anchors = byCA.get(issuer);
+        if (anchors != null) {
+            for (TrustAnchor caAnchor : anchors) {
+                try {
+                    cert.verify(caAnchor.getCAPublicKey());
+                    return caAnchor;
+                } catch (Exception e) {
+                    verificationException = e;
+                }
+            }
+        }
+
+        TrustAnchor anchor = bySubject.get(issuer);
+        if (anchor != null) {
+            try {
+                cert.verify(anchor.getTrustedCert().getPublicKey());
+                return anchor;
+            } catch (Exception e) {
+                verificationException = e;
+            }
+        }
+
+        try {
+            Bytes encoded = new Bytes(cert.getEncoded());
+            anchor = encodings.get(encoded);
+            if (anchor != null) {
+                return anchor;
+            }
+        } catch (Exception e) { 
+            Logger.getLogger(IndexedPKIXParameters.class.getName()).log(
+                    Level.WARNING, "Error encoding cert.", e);
+        }
+
+        // Throw last verification exception.
+        if (verificationException != null) {
+            throw new CertPathValidatorException("TrustAnchor found but"
+                    + " certificate verification failed.",
+                    verificationException, certPath, index);
+        }
+
+        return null;
+    }
+
+    /**
+     * Wraps a byte[] and adds equals() and hashCode() support.
+     */
+    static class Bytes {
+        final byte[] bytes;
+        final int hash;
+        Bytes(byte[] bytes) {
+            this.bytes = bytes;
+            this.hash = Arrays.hashCode(bytes);
+        }
+        @Override public int hashCode() {
+            return hash;
+        }
+        @Override public boolean equals(Object o) {
+            return Arrays.equals(bytes, ((Bytes) o).bytes);
+        }
+    }
+}
diff --git a/libcore/security/src/main/java/org/bouncycastle/jce/provider/PKIXCertPathValidatorSpi.java b/libcore/security/src/main/java/org/bouncycastle/jce/provider/PKIXCertPathValidatorSpi.java
index 3029bce..f5d6711 100644
--- a/libcore/security/src/main/java/org/bouncycastle/jce/provider/PKIXCertPathValidatorSpi.java
+++ b/libcore/security/src/main/java/org/bouncycastle/jce/provider/PKIXCertPathValidatorSpi.java
@@ -138,7 +138,11 @@
         // (d)
         // 
         X509Certificate lastCert = (X509Certificate)certs.get(certs.size() - 1);
-        TrustAnchor trust = CertPathValidatorUtilities.findTrustAnchor(lastCert, certPath, certs.size() - 1, paramsPKIX.getTrustAnchors());
+
+// BEGIN android-changed
+        TrustAnchor trust = CertPathValidatorUtilities.findTrustAnchor(lastCert,
+                certPath, certs.size() - 1, paramsPKIX);
+// END android-changed
 
         if (trust == null)
         {
diff --git a/libcore/security/src/main/java/org/bouncycastle/jce/provider/X509CertificateObject.java b/libcore/security/src/main/java/org/bouncycastle/jce/provider/X509CertificateObject.java
index c9a4da2..d17fd59 100644
--- a/libcore/security/src/main/java/org/bouncycastle/jce/provider/X509CertificateObject.java
+++ b/libcore/security/src/main/java/org/bouncycastle/jce/provider/X509CertificateObject.java
@@ -542,23 +542,25 @@
         return JDKKeyFactory.createPublicKeyFromPublicKeyInfo(c.getSubjectPublicKeyInfo());
     }
 
+// BEGIN android-changed
+    private ByteArrayOutputStream encodedOut;
     public byte[] getEncoded()
-        throws CertificateEncodingException
-    {
-        ByteArrayOutputStream   bOut = new ByteArrayOutputStream();
-        DEROutputStream         dOut = new DEROutputStream(bOut);
-
-        try
-        {
-            dOut.writeObject(c);
-
-            return bOut.toByteArray();
+            throws CertificateEncodingException {
+        synchronized (this) {
+            if (encodedOut == null) {
+                ByteArrayOutputStream bOut = new ByteArrayOutputStream();
+                DEROutputStream dOut = new DEROutputStream(bOut);
+                try {
+                    dOut.writeObject(c);
+                    encodedOut = bOut;
+                } catch (IOException e) {
+                    throw new CertificateEncodingException(e.toString());
+                }
+            }
         }
-        catch (IOException e)
-        {
-            throw new CertificateEncodingException(e.toString());
-        }
+        return encodedOut.toByteArray();
     }
+// END android-changed
 
     public boolean equals(
         Object o)
diff --git a/libcore/x-net/src/main/java/org/apache/harmony/xnet/provider/jsse/SSLParameters.java b/libcore/x-net/src/main/java/org/apache/harmony/xnet/provider/jsse/SSLParameters.java
index fb05722..d91388a 100644
--- a/libcore/x-net/src/main/java/org/apache/harmony/xnet/provider/jsse/SSLParameters.java
+++ b/libcore/x-net/src/main/java/org/apache/harmony/xnet/provider/jsse/SSLParameters.java
@@ -28,6 +28,9 @@
 import java.security.NoSuchAlgorithmException;
 import java.security.SecureRandom;
 import java.security.UnrecoverableKeyException;
+import java.security.InvalidAlgorithmParameterException;
+import java.security.cert.CertificateEncodingException;
+
 import javax.net.ssl.KeyManager;
 import javax.net.ssl.KeyManagerFactory;
 import javax.net.ssl.TrustManager;
@@ -193,6 +196,11 @@
                 if (initialize_default) {
                     // found trustManager is default trust manager
                     defaultTrustManager = trustManager;
+// BEGIN android-added
+                    if (trustManager instanceof TrustManagerImpl) {
+                        ((TrustManagerImpl) trustManager).indexTrustAnchors();
+                    }
+// END android-added
                 }
             }
         } catch (NoSuchAlgorithmException e) {
@@ -201,6 +209,12 @@
             throw new KeyManagementException(e);
         } catch (UnrecoverableKeyException e) {
             throw new KeyManagementException(e);            
+// BEGIN android-added
+        } catch (CertificateEncodingException e) {
+            throw new KeyManagementException(e);
+        } catch (InvalidAlgorithmParameterException e) {
+            throw new KeyManagementException(e);
+// END android-added
         }
         // initialize secure random
         // BEGIN android-removed
diff --git a/libcore/x-net/src/main/java/org/apache/harmony/xnet/provider/jsse/TrustManagerImpl.java b/libcore/x-net/src/main/java/org/apache/harmony/xnet/provider/jsse/TrustManagerImpl.java
index 31f7314..15756bd 100644
--- a/libcore/x-net/src/main/java/org/apache/harmony/xnet/provider/jsse/TrustManagerImpl.java
+++ b/libcore/x-net/src/main/java/org/apache/harmony/xnet/provider/jsse/TrustManagerImpl.java
@@ -22,8 +22,11 @@
 
 package org.apache.harmony.xnet.provider.jsse;
 
+import org.bouncycastle.jce.provider.IndexedPKIXParameters;
+
 import java.security.InvalidAlgorithmParameterException;
 import java.security.KeyStore;
+import java.security.KeyStoreException;
 import java.security.cert.CertPathValidator;
 import java.security.cert.CertPathValidatorException;
 import java.security.cert.CertificateException;
@@ -90,6 +93,17 @@
         }
     }
 
+// BEGIN android-added
+    /**
+     * Indexes trust anchors so they can be found in O(1) instead of O(N) time.
+     */
+    public void indexTrustAnchors() throws CertificateEncodingException,
+            InvalidAlgorithmParameterException, KeyStoreException {
+        params = new IndexedPKIXParameters(params.getTrustAnchors());
+        params.setRevocationEnabled(false);
+    }
+// END android-added
+
     /**
      * @see javax.net.ssl.X509TrustManager#checkClientTrusted(X509Certificate[],
      *      String)