diff --git a/verity/BootSignature.java b/verity/BootSignature.java
index c45224a..03eb32a 100644
--- a/verity/BootSignature.java
+++ b/verity/BootSignature.java
@@ -128,6 +128,18 @@
         return getAuthenticatedAttributes().getEncoded();
     }
 
+    public AlgorithmIdentifier getAlgorithmIdentifier() {
+        return algorithmIdentifier;
+    }
+
+    public PublicKey getPublicKey() {
+        return publicKey;
+    }
+
+    public byte[] getSignature() {
+        return signature.getOctets();
+    }
+
     public void setSignature(byte[] sig, AlgorithmIdentifier algId) {
         algorithmIdentifier = algId;
         signature = new DEROctetString(sig);
diff --git a/verity/KeystoreSigner.java b/verity/KeystoreSigner.java
index 3d946a6..0927d54 100644
--- a/verity/KeystoreSigner.java
+++ b/verity/KeystoreSigner.java
@@ -21,11 +21,15 @@
 import java.security.PublicKey;
 import java.security.Security;
 import java.security.Signature;
+import java.security.cert.X509Certificate;
+import java.util.Enumeration;
 import org.bouncycastle.asn1.ASN1Encodable;
 import org.bouncycastle.asn1.ASN1EncodableVector;
+import org.bouncycastle.asn1.ASN1InputStream;
 import org.bouncycastle.asn1.ASN1Integer;
 import org.bouncycastle.asn1.ASN1Object;
 import org.bouncycastle.asn1.ASN1Primitive;
+import org.bouncycastle.asn1.ASN1Sequence;
 import org.bouncycastle.asn1.DEROctetString;
 import org.bouncycastle.asn1.DERPrintableString;
 import org.bouncycastle.asn1.DERSequence;
@@ -63,8 +67,7 @@
         this.keyMaterial = new RSAPublicKey(
                 k.getModulus(),
                 k.getPublicExponent());
-        this.algorithmIdentifier = new AlgorithmIdentifier(
-                PKCSObjectIdentifiers.sha256WithRSAEncryption);
+        this.algorithmIdentifier = Utils.getSignatureAlgorithmIdentifier(key);
     }
 
     public ASN1Primitive toASN1Primitive() {
@@ -81,12 +84,15 @@
 
 class BootKeystore extends ASN1Object
 {
-    private ASN1Integer                     formatVersion;
-    private ASN1EncodableVector             keyBag;
-    private BootSignature    signature;
+    private ASN1Integer             formatVersion;
+    private ASN1EncodableVector     keyBag;
+    private BootSignature           signature;
+    private X509Certificate         certificate;
+
+    private static final int FORMAT_VERSION = 0;
 
     public BootKeystore() {
-        this.formatVersion = new ASN1Integer(0);
+        this.formatVersion = new ASN1Integer(FORMAT_VERSION);
         this.keyBag = new ASN1EncodableVector();
     }
 
@@ -96,6 +102,10 @@
         keyBag.add(k);
     }
 
+    public void setCertificate(X509Certificate cert) {
+        certificate = cert;
+    }
+
     public byte[] getInnerKeystore() throws Exception {
         ASN1EncodableVector v = new ASN1EncodableVector();
         v.add(formatVersion);
@@ -111,10 +121,36 @@
         return new DERSequence(v);
     }
 
+    public void parse(byte[] input) throws Exception {
+        ASN1InputStream stream = new ASN1InputStream(input);
+        ASN1Sequence sequence = (ASN1Sequence) stream.readObject();
+
+        formatVersion = (ASN1Integer) sequence.getObjectAt(0);
+        if (formatVersion.getValue().intValue() != FORMAT_VERSION) {
+            throw new IllegalArgumentException("Unsupported format version");
+        }
+
+        ASN1Sequence keys = (ASN1Sequence) sequence.getObjectAt(1);
+        Enumeration e = keys.getObjects();
+        while (e.hasMoreElements()) {
+            keyBag.add((ASN1Encodable) e.nextElement());
+        }
+
+        ASN1Object sig = sequence.getObjectAt(2).toASN1Primitive();
+        signature = new BootSignature(sig.getEncoded());
+    }
+
+    public boolean verify() throws Exception {
+        byte[] innerKeystore = getInnerKeystore();
+        return Utils.verify(signature.getPublicKey(), innerKeystore,
+                signature.getSignature(), signature.getAlgorithmIdentifier());
+    }
+
     public void sign(PrivateKey privateKey) throws Exception {
         byte[] innerKeystore = getInnerKeystore();
         byte[] rawSignature = Utils.sign(privateKey, innerKeystore);
         signature = new BootSignature("keystore", innerKeystore.length);
+        signature.setCertificate(certificate);
         signature.setSignature(rawSignature,
                 Utils.getSignatureAlgorithmIdentifier(privateKey));
     }
@@ -123,19 +159,49 @@
         System.out.println(ASN1Dump.dumpAsString(toASN1Primitive()));
     }
 
-    // USAGE:
-    //      AndroidVerifiedBootKeystoreSigner <privkeyFile> <outfile> <pubkeyFile0> ... <pubkeyFileN-1>
-    // EG:
-    //     java -cp ../../../out/host/common/obj/JAVA_LIBRARIES/AndroidVerifiedBootKeystoreSigner_intermediates/classes/ com.android.verity.AndroidVerifiedBootKeystoreSigner ../../../build/target/product/security/verity_private_dev_key /tmp/keystore.out /tmp/k
+    private static void usage() {
+        System.err.println("usage: KeystoreSigner <privatekey.pk8> " +
+                "<certificate.x509.pem> <outfile> <publickey0.der> " +
+                "... <publickeyN-1.der> | -verify <keystore>");
+        System.exit(1);
+    }
+
     public static void main(String[] args) throws Exception {
-        Security.addProvider(new BouncyCastleProvider());
-        String privkeyFname = args[0];
-        String outfileFname = args[1];
-        BootKeystore ks = new BootKeystore();
-        for (int i=2; i < args.length; i++) {
-            ks.addPublicKey(Utils.read(args[i]));
+        if (args.length < 2) {
+            usage();
+            return;
         }
-        ks.sign(Utils.loadDERPrivateKeyFromFile(privkeyFname));
-        Utils.write(ks.getEncoded(), outfileFname);
+
+        Security.addProvider(new BouncyCastleProvider());
+        BootKeystore ks = new BootKeystore();
+
+        if ("-verify".equals(args[0])) {
+            ks.parse(Utils.read(args[1]));
+
+            try {
+                if (ks.verify()) {
+                    System.err.println("Signature is VALID");
+                    System.exit(0);
+                } else {
+                    System.err.println("Signature is INVALID");
+                }
+            } catch (Exception e) {
+                e.printStackTrace(System.err);
+            }
+            System.exit(1);
+        } else {
+            String privkeyFname = args[0];
+            String certFname = args[1];
+            String outfileFname = args[2];
+
+            ks.setCertificate(Utils.loadPEMCertificate(certFname));
+
+            for (int i = 3; i < args.length; i++) {
+                ks.addPublicKey(Utils.read(args[i]));
+            }
+
+            ks.sign(Utils.loadDERPrivateKeyFromFile(privkeyFname));
+            Utils.write(ks.getEncoded(), outfileFname);
+        }
     }
 }
diff --git a/verity/KeystoreSigner.mf b/verity/KeystoreSigner.mf
index a4fee27..472b7c4 100644
--- a/verity/KeystoreSigner.mf
+++ b/verity/KeystoreSigner.mf
@@ -1 +1 @@
-Main-Class: com.android.verity.KeystoreSigner
\ No newline at end of file
+Main-Class: com.android.verity.BootKeystore
diff --git a/verity/VeritySigner.java b/verity/VeritySigner.java
index d11878a..9d85747 100644
--- a/verity/VeritySigner.java
+++ b/verity/VeritySigner.java
@@ -16,21 +16,54 @@
 
 package com.android.verity;
 
+import java.security.PublicKey;
 import java.security.PrivateKey;
 import java.security.Security;
+import java.security.cert.X509Certificate;
 import org.bouncycastle.jce.provider.BouncyCastleProvider;
 
 public class VeritySigner {
 
-    // USAGE:
-    //     VeritySigner <contentfile> <key.pem> <sigfile>
-    // To verify that this has correct output:
-    //     openssl rsautl -raw -inkey <key.pem> -encrypt -in <sigfile> > /tmp/dump
+    private static void usage() {
+        System.err.println("usage: VeritySigner <contentfile> <key.pk8> " +
+                "<sigfile> | <contentfile> <certificate.x509.pem> <sigfile> " +
+                "-verify");
+        System.exit(1);
+    }
+
     public static void main(String[] args) throws Exception {
+        if (args.length < 3) {
+            usage();
+            return;
+        }
+
         Security.addProvider(new BouncyCastleProvider());
+
         byte[] content = Utils.read(args[0]);
-        PrivateKey privateKey = Utils.loadDERPrivateKey(Utils.read(args[1]));
-        byte[] signature = Utils.sign(privateKey, content);
-        Utils.write(signature, args[2]);
+
+        if (args.length > 3 && "-verify".equals(args[3])) {
+            X509Certificate cert = Utils.loadPEMCertificate(args[1]);
+            PublicKey publicKey = cert.getPublicKey();
+
+            byte[] signature = Utils.read(args[2]);
+
+            try {
+                if (Utils.verify(publicKey, content, signature,
+                            Utils.getSignatureAlgorithmIdentifier(publicKey))) {
+                    System.err.println("Signature is VALID");
+                    System.exit(0);
+                } else {
+                    System.err.println("Signature is INVALID");
+                }
+            } catch (Exception e) {
+                e.printStackTrace(System.err);
+            }
+
+            System.exit(1);
+        } else {
+            PrivateKey privateKey = Utils.loadDERPrivateKey(Utils.read(args[1]));
+            byte[] signature = Utils.sign(privateKey, content);
+            Utils.write(signature, args[2]);
+        }
     }
 }
diff --git a/verity/keystore_signer b/verity/keystore_signer
old mode 100644
new mode 100755
index 7619c54..445f0c9
--- a/verity/keystore_signer
+++ b/verity/keystore_signer
@@ -5,4 +5,4 @@
 KEYSTORESIGNER_HOME=`dirname "$0"`
 KEYSTORESIGNER_HOME=`dirname "$KEYSTORESIGNER_HOME"`
 
-java -Xmx512M -jar "$KEYSTORESIGNER_HOME"/framework/KeystoreSigner.jar "$@"
\ No newline at end of file
+java -Xmx512M -jar "$KEYSTORESIGNER_HOME"/framework/BootKeystoreSigner.jar "$@"