diff --git a/verity/BootSignature.java b/verity/BootSignature.java
index 740e226..4ee3309 100644
--- a/verity/BootSignature.java
+++ b/verity/BootSignature.java
@@ -17,50 +17,58 @@
 package com.android.verity;
 
 import java.io.IOException;
+import java.nio.ByteBuffer;
+import java.nio.ByteOrder;
 import java.security.PrivateKey;
+import java.security.Security;
+import java.security.cert.X509Certificate;
+import java.security.cert.CertificateEncodingException;
 import java.util.Arrays;
 import org.bouncycastle.asn1.ASN1Encodable;
 import org.bouncycastle.asn1.ASN1EncodableVector;
 import org.bouncycastle.asn1.ASN1Integer;
 import org.bouncycastle.asn1.ASN1Object;
 import org.bouncycastle.asn1.ASN1Primitive;
+import org.bouncycastle.asn1.ASN1InputStream;
 import org.bouncycastle.asn1.DEROctetString;
 import org.bouncycastle.asn1.DERPrintableString;
 import org.bouncycastle.asn1.DERSequence;
-import org.bouncycastle.asn1.pkcs.PKCSObjectIdentifiers;
 import org.bouncycastle.asn1.util.ASN1Dump;
 import org.bouncycastle.asn1.x509.AlgorithmIdentifier;
+import org.bouncycastle.jce.provider.BouncyCastleProvider;
 
 /**
  *    AndroidVerifiedBootSignature DEFINITIONS ::=
  *    BEGIN
- *        FormatVersion ::= INTEGER
- *        AlgorithmIdentifier ::=  SEQUENCE {
+ *        formatVersion ::= INTEGER
+ *        certificate ::= Certificate
+ *        algorithmIdentifier ::= SEQUENCE {
  *            algorithm OBJECT IDENTIFIER,
  *            parameters ANY DEFINED BY algorithm OPTIONAL
  *        }
- *        AuthenticatedAttributes ::= SEQUENCE {
+ *        authenticatedAttributes ::= SEQUENCE {
  *            target CHARACTER STRING,
  *            length INTEGER
  *        }
- *        Signature ::= OCTET STRING
+ *        signature ::= OCTET STRING
  *     END
  */
 
 public class BootSignature extends ASN1Object
 {
     private ASN1Integer             formatVersion;
+    private ASN1Encodable           certificate;
     private AlgorithmIdentifier     algorithmIdentifier;
     private DERPrintableString      target;
     private ASN1Integer             length;
     private DEROctetString          signature;
 
+    private static final int FORMAT_VERSION = 1;
+
     public BootSignature(String target, int length) {
-        this.formatVersion = new ASN1Integer(0);
+        this.formatVersion = new ASN1Integer(FORMAT_VERSION);
         this.target = new DERPrintableString(target);
         this.length = new ASN1Integer(length);
-        this.algorithmIdentifier = new AlgorithmIdentifier(
-                PKCSObjectIdentifiers.sha1WithRSAEncryption);
     }
 
     public ASN1Object getAuthenticatedAttributes() {
@@ -74,10 +82,17 @@
         return getAuthenticatedAttributes().getEncoded();
     }
 
-    public void setSignature(byte[] sig) {
+    public void setSignature(byte[] sig, AlgorithmIdentifier algId) {
+        algorithmIdentifier = algId;
         signature = new DEROctetString(sig);
     }
 
+    public void setCertificate(X509Certificate cert)
+            throws Exception, IOException, CertificateEncodingException {
+        ASN1InputStream s = new ASN1InputStream(cert.getEncoded());
+        certificate = s.readObject();
+    }
+
     public byte[] generateSignableImage(byte[] image) throws IOException {
         byte[] attrs = getEncodedAuthenticatedAttributes();
         byte[] signable = Arrays.copyOf(image, image.length + attrs.length);
@@ -95,30 +110,93 @@
     public ASN1Primitive toASN1Primitive() {
         ASN1EncodableVector v = new ASN1EncodableVector();
         v.add(formatVersion);
+        v.add(certificate);
         v.add(algorithmIdentifier);
         v.add(getAuthenticatedAttributes());
         v.add(signature);
         return new DERSequence(v);
     }
 
+    public static int getSignableImageSize(byte[] data) throws Exception {
+        if (!Arrays.equals(Arrays.copyOfRange(data, 0, 8),
+                "ANDROID!".getBytes("US-ASCII"))) {
+            throw new IllegalArgumentException("Invalid image header: missing magic");
+        }
+
+        ByteBuffer image = ByteBuffer.wrap(data);
+        image.order(ByteOrder.LITTLE_ENDIAN);
+
+        image.getLong(); // magic
+        int kernelSize = image.getInt();
+        image.getInt(); // kernel_addr
+        int ramdskSize = image.getInt();
+        image.getInt(); // ramdisk_addr
+        int secondSize = image.getInt();
+        image.getLong(); // second_addr + tags_addr
+        int pageSize = image.getInt();
+
+        int length = pageSize // include the page aligned image header
+                + ((kernelSize + pageSize - 1) / pageSize) * pageSize
+                + ((ramdskSize + pageSize - 1) / pageSize) * pageSize
+                + ((secondSize + pageSize - 1) / pageSize) * pageSize;
+
+        length = ((length + pageSize - 1) / pageSize) * pageSize;
+
+        if (length <= 0) {
+            throw new IllegalArgumentException("Invalid image header: invalid length");
+        }
+
+        return length;
+    }
+
     public static void doSignature( String target,
                                     String imagePath,
                                     String keyPath,
+                                    String certPath,
                                     String outPath) throws Exception {
+
         byte[] image = Utils.read(imagePath);
+        int signableSize = getSignableImageSize(image);
+
+        if (signableSize < image.length) {
+            System.err.println("NOTE: truncating file " + imagePath +
+                    " from " + image.length + " to " + signableSize + " bytes");
+            image = Arrays.copyOf(image, signableSize);
+        } else if (signableSize > image.length) {
+            throw new IllegalArgumentException("Invalid image: too short, expected " +
+                    signableSize + " bytes");
+        }
+
         BootSignature bootsig = new BootSignature(target, image.length);
-        PrivateKey key = Utils.loadPEMPrivateKeyFromFile(keyPath);
-        bootsig.setSignature(bootsig.sign(image, key));
+
+        X509Certificate cert = Utils.loadPEMCertificate(certPath);
+        bootsig.setCertificate(cert);
+
+        PrivateKey key = Utils.loadDERPrivateKeyFromFile(keyPath);
+        bootsig.setSignature(bootsig.sign(image, key),
+            Utils.getSignatureAlgorithmIdentifier(key));
+
         byte[] encoded_bootsig = bootsig.getEncoded();
         byte[] image_with_metadata = Arrays.copyOf(image, image.length + encoded_bootsig.length);
-        for (int i=0; i < encoded_bootsig.length; i++) {
-            image_with_metadata[i+image.length] = encoded_bootsig[i];
-        }
+
+        System.arraycopy(encoded_bootsig, 0, image_with_metadata,
+                image.length, encoded_bootsig.length);
+
         Utils.write(image_with_metadata, outPath);
     }
 
-    // java -cp ../../../out/host/common/obj/JAVA_LIBRARIES/AndroidVerifiedBootSigner_intermediates/classes/ com.android.verity.AndroidVerifiedBootSigner boot ../../../out/target/product/flounder/boot.img ../../../build/target/product/security/verity_private_dev_key /tmp/boot.img.signed
+    /* java -cp
+        ../../../out/host/common/obj/JAVA_LIBRARIES/BootSignature_intermediates/\
+            classes/com.android.verity.BootSignature \
+        boot \
+        ../../../out/target/product/flounder/boot.img \
+        ../../../build/target/product/security/verity_private_dev_key \
+        ../../../build/target/product/security/verity.pk8 \
+        ../../../build/target/product/security/verity.x509.pem \
+        /tmp/boot.img.signed
+    */
     public static void main(String[] args) throws Exception {
-        doSignature(args[0], args[1], args[2], args[3]);
+        Security.addProvider(new BouncyCastleProvider());
+        doSignature(args[0], args[1], args[2], args[3], args[4]);
     }
-}
\ No newline at end of file
+}
diff --git a/verity/KeystoreSigner.java b/verity/KeystoreSigner.java
index d57f328..c020fb6 100644
--- a/verity/KeystoreSigner.java
+++ b/verity/KeystoreSigner.java
@@ -113,7 +113,8 @@
         byte[] innerKeystore = getInnerKeystore();
         byte[] rawSignature = Utils.sign(privateKey, innerKeystore);
         signature = new BootSignature("keystore", innerKeystore.length);
-        signature.setSignature(rawSignature);
+        signature.setSignature(rawSignature,
+                new AlgorithmIdentifier(PKCSObjectIdentifiers.sha1WithRSAEncryption));
     }
 
     public void dump() throws Exception {
@@ -134,4 +135,4 @@
         ks.sign(Utils.loadPEMPrivateKeyFromFile(privkeyFname));
         Utils.write(ks.getEncoded(), outfileFname);
     }
-}
\ No newline at end of file
+}
diff --git a/verity/Utils.java b/verity/Utils.java
index 2c1e7bb..4eba552 100644
--- a/verity/Utils.java
+++ b/verity/Utils.java
@@ -18,22 +18,60 @@
 
 import java.lang.reflect.Constructor;
 import java.io.File;
+import java.io.ByteArrayInputStream;
+import java.io.Console;
 import java.io.FileInputStream;
 import java.io.FileOutputStream;
+import java.io.InputStreamReader;
 import java.io.IOException;
+import java.security.GeneralSecurityException;
+import java.security.Key;
 import java.security.PrivateKey;
 import java.security.PublicKey;
 import java.security.KeyFactory;
 import java.security.Provider;
 import java.security.Security;
 import java.security.Signature;
+import java.security.cert.Certificate;
+import java.security.cert.CertificateFactory;
+import java.security.cert.X509Certificate;
 import java.security.spec.X509EncodedKeySpec;
 import java.security.spec.PKCS8EncodedKeySpec;
+import java.security.spec.InvalidKeySpecException;
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.Map;
 
+import javax.crypto.Cipher;
+import javax.crypto.EncryptedPrivateKeyInfo;
+import javax.crypto.SecretKeyFactory;
+import javax.crypto.spec.PBEKeySpec;
+
+import org.bouncycastle.asn1.ASN1InputStream;
+import org.bouncycastle.asn1.ASN1ObjectIdentifier;
+import org.bouncycastle.asn1.pkcs.PrivateKeyInfo;
+import org.bouncycastle.asn1.pkcs.PKCSObjectIdentifiers;
+import org.bouncycastle.asn1.x509.AlgorithmIdentifier;
 import org.bouncycastle.util.encoders.Base64;
 
 public class Utils {
 
+    private static final Map<String, String> ID_TO_ALG;
+    private static final Map<String, String> ALG_TO_ID;
+
+    static {
+        ID_TO_ALG = new HashMap<String, String>();
+        ALG_TO_ID = new HashMap<String, String>();
+
+        ID_TO_ALG.put(PKCSObjectIdentifiers.sha1WithRSAEncryption.getId(), "SHA1withRSA");
+        ID_TO_ALG.put(PKCSObjectIdentifiers.sha256WithRSAEncryption.getId(), "SHA256withRSA");
+        ID_TO_ALG.put(PKCSObjectIdentifiers.sha512WithRSAEncryption.getId(), "SHA512withRSA");
+
+        ALG_TO_ID.put("SHA1withRSA", PKCSObjectIdentifiers.sha1WithRSAEncryption.getId());
+        ALG_TO_ID.put("SHA256withRSA", PKCSObjectIdentifiers.sha256WithRSAEncryption.getId());
+        ALG_TO_ID.put("SHA512withRSA", PKCSObjectIdentifiers.sha512WithRSAEncryption.getId());
+    }
+
     private static void loadProviderIfNecessary(String providerClassName) {
         if (providerClassName == null) {
             return;
@@ -88,10 +126,45 @@
         return Base64.decode(base64_der);
     }
 
+    private static PKCS8EncodedKeySpec decryptPrivateKey(byte[] encryptedPrivateKey)
+        throws GeneralSecurityException {
+        EncryptedPrivateKeyInfo epkInfo;
+        try {
+            epkInfo = new EncryptedPrivateKeyInfo(encryptedPrivateKey);
+        } catch (IOException ex) {
+            // Probably not an encrypted key.
+            return null;
+        }
+
+        char[] password = System.console().readPassword("Password for the private key file: ");
+
+        SecretKeyFactory skFactory = SecretKeyFactory.getInstance(epkInfo.getAlgName());
+        Key key = skFactory.generateSecret(new PBEKeySpec(password));
+        Arrays.fill(password, '\0');
+
+        Cipher cipher = Cipher.getInstance(epkInfo.getAlgName());
+        cipher.init(Cipher.DECRYPT_MODE, key, epkInfo.getAlgParameters());
+
+        try {
+            return epkInfo.getKeySpec(cipher);
+        } catch (InvalidKeySpecException ex) {
+            System.err.println("Password may be bad.");
+            throw ex;
+        }
+    }
+
     static PrivateKey loadDERPrivateKey(byte[] der) throws Exception {
-        PKCS8EncodedKeySpec keySpec = new PKCS8EncodedKeySpec(der);
-        KeyFactory keyFactory = KeyFactory.getInstance("RSA");
-        return (PrivateKey) keyFactory.generatePrivate(keySpec);
+        PKCS8EncodedKeySpec spec = decryptPrivateKey(der);
+
+        if (spec == null) {
+            spec = new PKCS8EncodedKeySpec(der);
+        }
+
+        ASN1InputStream bIn = new ASN1InputStream(new ByteArrayInputStream(spec.getEncoded()));
+        PrivateKeyInfo pki = PrivateKeyInfo.getInstance(bIn.readObject());
+        String algOid = pki.getPrivateKeyAlgorithm().getAlgorithm().getId();
+
+        return KeyFactory.getInstance(algOid).generatePrivate(spec);
     }
 
     static PrivateKey loadPEMPrivateKey(byte[] pem) throws Exception {
@@ -128,8 +201,33 @@
         return loadDERPublicKey(read(keyFname));
     }
 
+    static X509Certificate loadPEMCertificate(String fname) throws Exception {
+        try (FileInputStream fis = new FileInputStream(fname)) {
+            CertificateFactory cf = CertificateFactory.getInstance("X.509");
+            return (X509Certificate) cf.generateCertificate(fis);
+        }
+    }
+
+    private static String getSignatureAlgorithm(Key key) {
+        if ("RSA".equals(key.getAlgorithm())) {
+            return "SHA256withRSA";
+        } else {
+            throw new IllegalArgumentException("Unsupported key type " + key.getAlgorithm());
+        }
+    }
+
+    static AlgorithmIdentifier getSignatureAlgorithmIdentifier(Key key) {
+        String id = ALG_TO_ID.get(getSignatureAlgorithm(key));
+
+        if (id == null) {
+            throw new IllegalArgumentException("Unsupported key type " + key.getAlgorithm());
+        }
+
+        return new AlgorithmIdentifier(new ASN1ObjectIdentifier(id));
+    }
+
     static byte[] sign(PrivateKey privateKey, byte[] input) throws Exception {
-        Signature signer = Signature.getInstance("SHA1withRSA");
+        Signature signer = Signature.getInstance(getSignatureAlgorithm(privateKey));
         signer.initSign(privateKey);
         signer.update(input);
         return signer.sign();
@@ -153,4 +251,4 @@
         out.write(data);
         out.close();
     }
-}
\ No newline at end of file
+}