diff --git a/compos/Android.bp b/compos/Android.bp
index 8d0ba3b..658f8bf 100644
--- a/compos/Android.bp
+++ b/compos/Android.bp
@@ -7,9 +7,7 @@
     srcs: ["src/compsvc_main.rs"],
     rustlibs: [
         "android.hardware.security.dice-V1-rust",
-        "android.hardware.security.keymint-V1-rust",
         "android.security.dice-rust",
-        "android.system.keystore2-V1-rust",
         "android.system.virtualmachineservice-rust",
         "authfs_aidl_interface-rust",
         "compos_aidl_interface-rust",
@@ -20,6 +18,7 @@
         "libbinder_rs",
         "libclap",
         "libcompos_common",
+        "libcompos_native_rust",
         "libenv_logger",
         "liblibc",
         "liblog_rust",
@@ -35,6 +34,7 @@
     prefer_rlib: true,
     shared_libs: [
         "libbinder_rpc_unstable",
+        "libcrypto",
     ],
 }
 
diff --git a/compos/aidl/com/android/compos/CompOsKeyData.aidl b/compos/aidl/com/android/compos/CompOsKeyData.aidl
index 381ec0d..dafb009 100644
--- a/compos/aidl/com/android/compos/CompOsKeyData.aidl
+++ b/compos/aidl/com/android/compos/CompOsKeyData.aidl
@@ -19,9 +19,10 @@
 /** {@hide} */
 parcelable CompOsKeyData {
     /**
-     * Self-signed certificate (X.509 DER) containing the public key.
+     * The public key, as a DER-encoded RSAPublicKey
+     * (https://datatracker.ietf.org/doc/html/rfc8017#appendix-A.1.1).
      */
-    byte[] certificate;
+    byte[] publicKey;
 
     /**
      * Opaque encrypted blob containing the private key and related metadata.
diff --git a/compos/compos_key_cmd/Android.bp b/compos/compos_key_cmd/Android.bp
index 9d5a490..d412f66 100644
--- a/compos/compos_key_cmd/Android.bp
+++ b/compos/compos_key_cmd/Android.bp
@@ -17,7 +17,6 @@
         "libbase",
         "libbinder_ndk",
         "libbinder_rpc_unstable",
-        "libcrypto",
         "libfsverity",
         "libprotobuf-cpp-lite",
     ],
diff --git a/compos/compos_key_cmd/compos_key_cmd.cpp b/compos/compos_key_cmd/compos_key_cmd.cpp
index 4312a5a..07ff636 100644
--- a/compos/compos_key_cmd/compos_key_cmd.cpp
+++ b/compos/compos_key_cmd/compos_key_cmd.cpp
@@ -27,10 +27,6 @@
 #include <asm/byteorder.h>
 #include <libfsverity.h>
 #include <linux/fsverity.h>
-#include <openssl/evp.h>
-#include <openssl/mem.h>
-#include <openssl/sha.h>
-#include <openssl/x509.h>
 #include <stdio.h>
 #include <unistd.h>
 
@@ -331,37 +327,6 @@
 
 } // namespace
 
-static Result<std::vector<uint8_t>> extractRsaPublicKey(
-        const std::vector<uint8_t>& der_certificate) {
-    auto data = der_certificate.data();
-    bssl::UniquePtr<X509> x509(d2i_X509(nullptr, &data, der_certificate.size()));
-    if (!x509) {
-        return Error() << "Failed to parse certificate";
-    }
-    if (data != der_certificate.data() + der_certificate.size()) {
-        return Error() << "Certificate has unexpected trailing data";
-    }
-
-    bssl::UniquePtr<EVP_PKEY> pkey(X509_get_pubkey(x509.get()));
-    if (EVP_PKEY_base_id(pkey.get()) != EVP_PKEY_RSA) {
-        return Error() << "Subject key is not RSA";
-    }
-    RSA* rsa = EVP_PKEY_get0_RSA(pkey.get());
-    if (!rsa) {
-        return Error() << "Failed to extract RSA key";
-    }
-
-    uint8_t* out = nullptr;
-    int size = i2d_RSAPublicKey(rsa, &out);
-    if (size < 0 || !out) {
-        return Error() << "Failed to convert to RSAPublicKey";
-    }
-
-    bssl::UniquePtr<uint8_t> buffer(out);
-    std::vector<uint8_t> result(out, out + size);
-    return result;
-}
-
 static Result<void> generate(TargetVm& vm, const std::string& blob_file,
                              const std::string& public_key_file) {
     auto cid = vm.resolveCid();
@@ -379,15 +344,11 @@
         return Error() << "Failed to generate key: " << status.getDescription();
     }
 
-    auto public_key = extractRsaPublicKey(key_data.certificate);
-    if (!public_key.ok()) {
-        return Error() << "Failed to extract public key from cert: " << public_key.error();
-    }
     if (!writeBytesToFile(key_data.keyBlob, blob_file)) {
         return Error() << "Failed to write keyBlob to " << blob_file;
     }
 
-    if (!writeBytesToFile(public_key.value(), public_key_file)) {
+    if (!writeBytesToFile(key_data.publicKey, public_key_file)) {
         return Error() << "Failed to write public key to " << public_key_file;
     }
 
diff --git a/compos/composd/native/Android.bp b/compos/composd/native/Android.bp
index 135f4d4..ccd8651 100644
--- a/compos/composd/native/Android.bp
+++ b/compos/composd/native/Android.bp
@@ -8,40 +8,10 @@
     srcs: ["lib.rs"],
     rustlibs: [
         "libanyhow",
-        "libcxx",
         "liblibc",
     ],
-    static_libs: [
-        "libcomposd_native_cpp",
-    ],
     shared_libs: [
         "libartpalette-system",
-        "libcrypto",
     ],
     apex_available: ["com.android.compos"],
 }
-
-cc_library_static {
-    name: "libcomposd_native_cpp",
-    srcs: ["composd_native.cpp"],
-    shared_libs: ["libcrypto"],
-    generated_headers: ["composd_native_header"],
-    generated_sources: ["composd_native_code"],
-    apex_available: ["com.android.compos"],
-}
-
-genrule {
-    name: "composd_native_code",
-    tools: ["cxxbridge"],
-    cmd: "$(location cxxbridge) $(in) >> $(out)",
-    srcs: ["lib.rs"],
-    out: ["composd_native_cxx_generated.cc"],
-}
-
-genrule {
-    name: "composd_native_header",
-    tools: ["cxxbridge"],
-    cmd: "$(location cxxbridge) $(in) --header >> $(out)",
-    srcs: ["lib.rs"],
-    out: ["lib.rs.h"],
-}
diff --git a/compos/composd/native/composd_native.cpp b/compos/composd/native/composd_native.cpp
deleted file mode 100644
index ebed816..0000000
--- a/compos/composd/native/composd_native.cpp
+++ /dev/null
@@ -1,66 +0,0 @@
-/*
- * Copyright (C) 2021 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.
- */
-
-#include "composd_native.h"
-
-#include <openssl/evp.h>
-#include <openssl/mem.h>
-#include <openssl/sha.h>
-#include <openssl/x509.h>
-
-#include <algorithm>
-#include <iterator>
-
-using rust::Slice;
-using rust::String;
-
-namespace {
-KeyResult make_error(const char* message) {
-    return KeyResult{{}, message};
-}
-} // namespace
-
-KeyResult extract_rsa_public_key(rust::Slice<const uint8_t> der_certificate) {
-    auto data = der_certificate.data();
-    bssl::UniquePtr<X509> x509(d2i_X509(nullptr, &data, der_certificate.size()));
-    if (!x509) {
-        return make_error("Failed to parse certificate");
-    }
-    if (data != der_certificate.data() + der_certificate.size()) {
-        return make_error("Certificate has unexpected trailing data");
-    }
-
-    bssl::UniquePtr<EVP_PKEY> pkey(X509_get_pubkey(x509.get()));
-    if (EVP_PKEY_base_id(pkey.get()) != EVP_PKEY_RSA) {
-        return make_error("Subject key is not RSA");
-    }
-    RSA* rsa = EVP_PKEY_get0_RSA(pkey.get());
-    if (!rsa) {
-        return make_error("Failed to extract RSA key");
-    }
-
-    uint8_t* out = nullptr;
-    int size = i2d_RSAPublicKey(rsa, &out);
-    if (size < 0 || !out) {
-        return make_error("Failed to convert to RSAPublicKey");
-    }
-    bssl::UniquePtr<uint8_t> buffer(out);
-
-    KeyResult result;
-    result.key.reserve(size);
-    std::copy(out, out + size, std::back_inserter(result.key));
-    return result;
-}
diff --git a/compos/composd/native/lib.rs b/compos/composd/native/lib.rs
index cbec7fd..042eb2a 100644
--- a/compos/composd/native/lib.rs
+++ b/compos/composd/native/lib.rs
@@ -15,28 +15,6 @@
 //! Native helpers for composd.
 
 pub use art::*;
-pub use crypto::*;
-
-#[cxx::bridge]
-mod crypto {
-    /// Contains either a key or a reason why the key could not be extracted.
-    struct KeyResult {
-        /// The extracted key. If empty, the attempt to extract the key failed.
-        key: Vec<u8>,
-        /// A description of what went wrong if the attempt failed.
-        error: String,
-    }
-
-    unsafe extern "C++" {
-        include!("composd_native.h");
-
-        // SAFETY: The C++ implementation manages its own memory, and does not retain or abuse
-        // the der_certificate reference. cxx handles the mapping of the return value.
-
-        /// Parse the supplied DER X.509 certificate and extract the subject's RsaPublicKey.
-        fn extract_rsa_public_key(der_certificate: &[u8]) -> KeyResult;
-    }
-}
 
 mod art {
     use anyhow::{anyhow, Result};
diff --git a/compos/composd/src/instance_starter.rs b/compos/composd/src/instance_starter.rs
index 4fed98a..a886584 100644
--- a/compos/composd/src/instance_starter.rs
+++ b/compos/composd/src/instance_starter.rs
@@ -138,13 +138,7 @@
 
         let key_data = service.generateSigningKey().context("Generating signing key")?;
         fs::write(&self.key_blob, &key_data.keyBlob).context("Writing key blob")?;
-
-        let key_result = composd_native::extract_rsa_public_key(&key_data.certificate);
-        let rsa_public_key = key_result.key;
-        if rsa_public_key.is_empty() {
-            bail!("Failed to extract public key from certificate: {}", key_result.error);
-        }
-        fs::write(&self.public_key, &rsa_public_key).context("Writing public key")?;
+        fs::write(&self.public_key, &key_data.publicKey).context("Writing public key")?;
 
         // Unlike when starting an existing instance, we don't need to verify the key, since we
         // just generated it and have it in memory.
diff --git a/compos/native/Android.bp b/compos/native/Android.bp
new file mode 100644
index 0000000..84e312a
--- /dev/null
+++ b/compos/native/Android.bp
@@ -0,0 +1,46 @@
+package {
+    default_applicable_licenses: ["Android-Apache-2.0"],
+}
+
+rust_library {
+    name: "libcompos_native_rust",
+    crate_name: "compos_native",
+    srcs: ["lib.rs"],
+    rustlibs: [
+        "libanyhow",
+        "libcxx",
+        "liblibc",
+    ],
+    static_libs: [
+        "libcompos_native_cpp",
+    ],
+    shared_libs: [
+        "libcrypto",
+    ],
+    apex_available: ["com.android.compos"],
+}
+
+cc_library_static {
+    name: "libcompos_native_cpp",
+    srcs: ["compos_native.cpp"],
+    shared_libs: ["libcrypto"],
+    generated_headers: ["compos_native_header"],
+    generated_sources: ["compos_native_code"],
+    apex_available: ["com.android.compos"],
+}
+
+genrule {
+    name: "compos_native_code",
+    tools: ["cxxbridge"],
+    cmd: "$(location cxxbridge) $(in) >> $(out)",
+    srcs: ["lib.rs"],
+    out: ["compos_native_cxx_generated.cc"],
+}
+
+genrule {
+    name: "compos_native_header",
+    tools: ["cxxbridge"],
+    cmd: "$(location cxxbridge) $(in) --header >> $(out)",
+    srcs: ["lib.rs"],
+    out: ["lib.rs.h"],
+}
diff --git a/compos/native/compos_native.cpp b/compos/native/compos_native.cpp
new file mode 100644
index 0000000..f529421
--- /dev/null
+++ b/compos/native/compos_native.cpp
@@ -0,0 +1,112 @@
+/*
+ * Copyright (C) 2021 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.
+ */
+
+#include "compos_native.h"
+
+#include <openssl/bn.h>
+#include <openssl/mem.h>
+#include <openssl/nid.h>
+#include <openssl/rsa.h>
+#include <openssl/sha.h>
+
+#include <algorithm>
+#include <iterator>
+#include <vector>
+
+namespace {
+KeyResult make_key_error(const char* message) {
+    return KeyResult{{}, {}, message};
+}
+
+SignResult make_sign_error(const char* message) {
+    return SignResult{{}, message};
+}
+} // namespace
+
+constexpr int KEY_BITS = 2048;
+
+KeyResult generate_key_pair() {
+    bssl::UniquePtr<RSA> key_pair(RSA_new());
+
+    // This function specifies that the public exponent is always 65537, which is good because
+    // that's  what odsign is expecting.
+    if (!RSA_generate_key_fips(key_pair.get(), KEY_BITS, /*callback=*/nullptr)) {
+        return make_key_error("Failed to generate key pair");
+    }
+
+    KeyResult result;
+
+    uint8_t* out;
+    int size;
+    bssl::UniquePtr<uint8_t> out_owner;
+
+    // Extract public key as DER.
+    out = nullptr;
+    size = i2d_RSAPublicKey(key_pair.get(), &out);
+    if (size < 0 || !out) {
+        return make_key_error("Failed to get RSAPublicKey");
+    }
+    out_owner.reset(out);
+
+    result.public_key.reserve(size);
+    std::copy(out, out + size, std::back_inserter(result.public_key));
+    out_owner.reset();
+
+    // And ditto for the private key (which actually includes the public bits).
+    out = nullptr;
+    size = i2d_RSAPrivateKey(key_pair.get(), &out);
+    if (size < 0 || !out) {
+        return make_key_error("Failed to get RSAPrivateKey");
+    }
+    out_owner.reset(out);
+
+    result.private_key.reserve(size);
+    std::copy(out, out + size, std::back_inserter(result.private_key));
+    out_owner.reset();
+
+    return result;
+}
+
+SignResult sign(rust::Slice<const uint8_t> private_key, rust::Slice<const uint8_t> data) {
+    uint8_t digest[SHA256_DIGEST_LENGTH];
+    SHA256(data.data(), data.size(), digest);
+
+    const uint8_t* key_in = private_key.data();
+    bssl::UniquePtr<RSA> key(d2i_RSAPrivateKey(nullptr, &key_in, private_key.size()));
+    if (!key) {
+        return make_sign_error("Failed to load RSAPrivateKey");
+    }
+
+    // rust::Vec doesn't support resize, so we need our own buffer.
+    // The signature is always less than the modulus (public key), so
+    // will fit in KEY_BITS.
+
+    uint8_t signature[KEY_BITS / 8];
+    if (sizeof(signature) < RSA_size(key.get())) {
+        return make_sign_error("Signing key is too large");
+    }
+    unsigned signature_len = 0;
+
+    if (!RSA_sign(NID_sha256, digest, sizeof(digest), signature, &signature_len, key.get())) {
+        return make_sign_error("Failed to sign");
+    }
+
+    SignResult result;
+    result.signature.reserve(signature_len);
+    std::copy(signature, signature + signature_len, std::back_inserter(result.signature));
+
+    return result;
+}
diff --git a/compos/composd/native/composd_native.h b/compos/native/compos_native.h
similarity index 83%
rename from compos/composd/native/composd_native.h
rename to compos/native/compos_native.h
index 112ef73..6497c9b 100644
--- a/compos/composd/native/composd_native.h
+++ b/compos/native/compos_native.h
@@ -18,4 +18,6 @@
 
 #include "lib.rs.h"
 
-KeyResult extract_rsa_public_key(rust::Slice<const uint8_t> der_certificate);
+KeyResult generate_key_pair();
+
+SignResult sign(rust::Slice<const uint8_t> private_key, rust::Slice<const uint8_t> data);
diff --git a/compos/native/lib.rs b/compos/native/lib.rs
new file mode 100644
index 0000000..a5f0cc5
--- /dev/null
+++ b/compos/native/lib.rs
@@ -0,0 +1,59 @@
+// Copyright 2021, 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.
+
+//! Native helpers for CompOS.
+
+pub use crypto::*;
+
+#[cxx::bridge]
+mod crypto {
+    /// Contains either a key pair or a reason why the key could not be extracted.
+    struct KeyResult {
+        /// The DER-encoded RSAPublicKey
+        /// (https://datatracker.ietf.org/doc/html/rfc8017#appendix-A.1.1).
+        public_key: Vec<u8>,
+        /// The DER-encoded RSAPrivateKey
+        /// (https://datatracker.ietf.org/doc/html/rfc8017#appendix-A.1.2).
+        /// Note that this is unencrypted.
+        private_key: Vec<u8>,
+        /// A description of what went wrong if the attempt failed.
+        error: String,
+    }
+
+    /// Contains either a signature or a reason why signing failed.
+    struct SignResult {
+        /// The RSAES-PKCS1-v1_5 signature
+        /// (https://datatracker.ietf.org/doc/html/rfc3447#section-7.2).
+        signature: Vec<u8>,
+        /// A description of what went wrong if the attempt failed.
+        error: String,
+    }
+
+    unsafe extern "C++" {
+        include!("compos_native.h");
+
+        // SAFETY: The C++ implementation manages its own memory. cxx handles the mapping of the
+        // return value.
+
+        /// Generate a public/private key pair.
+        fn generate_key_pair() -> KeyResult;
+
+        // SAFETY: The C++ implementation manages its own memory, and does not retain or abuse
+        // the references passed to it. cxx handles the mapping of the return value.
+
+        /// Sign data using a SHA256 digest and RSAES-PKCS1-v1_5 using the given
+        /// DER-encoded RSAPrivateKey.
+        fn sign(private_key: &[u8], data: &[u8]) -> SignResult;
+    }
+}
diff --git a/compos/src/artifact_signer.rs b/compos/src/artifact_signer.rs
index a4b47d6..e1b0efa 100644
--- a/compos/src/artifact_signer.rs
+++ b/compos/src/artifact_signer.rs
@@ -19,8 +19,8 @@
 
 #![allow(dead_code)] // Will be used soon
 
-use crate::compos_key_service::Signer;
 use crate::fsverity;
+use crate::signing_key::Signer;
 use anyhow::{anyhow, Context, Result};
 use odsign_proto::odsign_info::OdsignInfo;
 use protobuf::Message;
diff --git a/compos/src/blob_encryption.rs b/compos/src/blob_encryption.rs
new file mode 100644
index 0000000..0db09ba
--- /dev/null
+++ b/compos/src/blob_encryption.rs
@@ -0,0 +1,118 @@
+/*
+ * Copyright 2022 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.
+ */
+
+//! Allows for data to be encrypted and authenticated (AEAD) with a key derived from some secret.
+//! The encrypted blob can be passed to the untrusted host without revealing the encrypted data
+//! but with the key the data can be retrieved as long as the blob has not been tampered with.
+
+use anyhow::{bail, Context, Result};
+use ring::{
+    aead::{Aad, LessSafeKey, Nonce, AES_256_GCM, NONCE_LEN},
+    hkdf::{Salt, HKDF_SHA256},
+    rand::{SecureRandom, SystemRandom},
+};
+
+// Non-secret input to the AEAD key derivation
+const KDF_INFO: &[u8] = b"CompOS blob sealing key";
+
+pub fn derive_aead_key(input_keying_material: &[u8]) -> Result<LessSafeKey> {
+    // Derive key using HKDF - see https://datatracker.ietf.org/doc/html/rfc5869#section-2
+    let salt = [];
+    let prk = Salt::new(HKDF_SHA256, &salt).extract(input_keying_material);
+    let okm = prk.expand(&[KDF_INFO], &AES_256_GCM).context("HKDF failed")?;
+    // LessSafeKey is only less safe in that it has less inherent protection against nonce
+    // reuse; we are safe because we use a new random nonce for each sealing operation.
+    // (See https://github.com/briansmith/ring/issues/899.)
+    Ok(LessSafeKey::new(okm.into()))
+}
+
+pub fn encrypt_bytes(key: LessSafeKey, bytes: &[u8]) -> Result<Vec<u8>> {
+    let mut output = Vec::with_capacity(bytes.len() + NONCE_LEN + key.algorithm().tag_len());
+
+    // Generate a unique nonce, since we may use the same key more than once, and put it at the
+    // start of the output blob.
+    let mut nonce_bytes = [0u8; NONCE_LEN];
+    SystemRandom::new().fill(&mut nonce_bytes).context("Failed to generate random nonce")?;
+    output.extend_from_slice(&nonce_bytes);
+
+    // Copy input to output then encrypt & seal it in place.
+    output.extend_from_slice(bytes);
+    let nonce = Nonce::assume_unique_for_key(nonce_bytes);
+    let tag = key
+        .seal_in_place_separate_tag(nonce, Aad::empty(), &mut output[NONCE_LEN..])
+        .context("Failed to seal blob")?;
+    output.extend_from_slice(tag.as_ref());
+
+    Ok(output)
+}
+
+pub fn decrypt_bytes(key: LessSafeKey, bytes: &[u8]) -> Result<Vec<u8>> {
+    if bytes.len() < NONCE_LEN + key.algorithm().tag_len() {
+        bail!("Encrypted blob is too small");
+    }
+
+    // We expect the nonce at the start followed by the sealed data (encrypted data +
+    // authentication tag).
+    let nonce = Nonce::try_assume_unique_for_key(&bytes[..NONCE_LEN]).unwrap();
+    let mut output = bytes[NONCE_LEN..].to_vec();
+
+    // Verify & decrypt the data in place
+    let unsealed_size =
+        key.open_in_place(nonce, Aad::empty(), &mut output).context("Failed to unseal blob")?.len();
+
+    // Remove the tag after the plaintext
+    output.truncate(unsealed_size);
+
+    Ok(output)
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_round_trip_data() -> Result<()> {
+        let input_keying_material = b"Key is derived from this";
+        let original_bytes = b"This is the secret data";
+
+        let key = derive_aead_key(input_keying_material)?;
+        let blob = encrypt_bytes(key, original_bytes)?;
+
+        let key = derive_aead_key(input_keying_material)?;
+        let decoded_bytes = decrypt_bytes(key, &blob)?;
+
+        assert_eq!(decoded_bytes, original_bytes);
+        Ok(())
+    }
+
+    #[test]
+    fn test_modified_data_detected() -> Result<()> {
+        let input_keying_material = b"Key is derived from this";
+        let original_bytes = b"This is the secret data";
+
+        let key = derive_aead_key(input_keying_material)?;
+        let mut blob = encrypt_bytes(key, original_bytes)?;
+
+        // Flip a bit.
+        blob[0] ^= 1;
+
+        let key = derive_aead_key(input_keying_material)?;
+        let decoded_bytes = decrypt_bytes(key, &blob);
+
+        assert!(decoded_bytes.is_err());
+        Ok(())
+    }
+}
diff --git a/compos/src/blob_encryptor.rs b/compos/src/blob_encryptor.rs
deleted file mode 100644
index ed4484e..0000000
--- a/compos/src/blob_encryptor.rs
+++ /dev/null
@@ -1,132 +0,0 @@
-/*
- * Copyright 2022 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.
- */
-
-//! Allows for data to be encrypted and authenticated (AEAD) with a key derived from some secret.
-//! The encrypted blob can be passed to the untrusted host without revealing the encrypted data
-//! but with the key the data can be retrieved as long as the blob has not been tampered with.
-
-use anyhow::{bail, Context, Result};
-use ring::{
-    aead::{Aad, LessSafeKey, Nonce, AES_256_GCM, NONCE_LEN},
-    hkdf::{Salt, HKDF_SHA256},
-    rand::{SecureRandom, SystemRandom},
-};
-
-pub struct BlobEncryptor {
-    random: SystemRandom,
-}
-
-// Non-secret input to the AEAD key derivation
-const KDF_INFO: &[u8] = b"CompOS blob sealing key";
-
-impl BlobEncryptor {
-    pub fn new() -> Self {
-        Self { random: SystemRandom::new() }
-    }
-
-    pub fn derive_aead_key(&self, input_keying_material: &[u8]) -> Result<LessSafeKey> {
-        // Derive key using HKDF - see https://datatracker.ietf.org/doc/html/rfc5869#section-2
-        let salt = [];
-        let prk = Salt::new(HKDF_SHA256, &salt).extract(input_keying_material);
-        let okm = prk.expand(&[KDF_INFO], &AES_256_GCM).context("HKDF failed")?;
-        // LessSafeKey is only less safe in that it has less inherent protection against nonce
-        // reuse; we are safe because we use a new random nonce for each sealing operation.
-        // (See https://github.com/briansmith/ring/issues/899.)
-        Ok(LessSafeKey::new(okm.into()))
-    }
-
-    pub fn encrypt_bytes(&self, key: LessSafeKey, bytes: &[u8]) -> Result<Vec<u8>> {
-        let mut output = Vec::with_capacity(bytes.len() + NONCE_LEN + key.algorithm().tag_len());
-
-        // Generate a unique nonce, since we may use the same key more than once, and put it at the
-        // start of the output blob.
-        let mut nonce_bytes = [0u8; NONCE_LEN];
-        self.random.fill(&mut nonce_bytes).context("Failed to generate random nonce")?;
-        output.extend_from_slice(&nonce_bytes);
-
-        // Copy input to output then encrypt & seal it in place.
-        output.extend_from_slice(bytes);
-        let nonce = Nonce::assume_unique_for_key(nonce_bytes);
-        let tag = key
-            .seal_in_place_separate_tag(nonce, Aad::empty(), &mut output[NONCE_LEN..])
-            .context("Failed to seal blob")?;
-        output.extend_from_slice(tag.as_ref());
-
-        Ok(output)
-    }
-
-    pub fn decrypt_bytes(&self, key: LessSafeKey, bytes: &[u8]) -> Result<Vec<u8>> {
-        if bytes.len() < NONCE_LEN + key.algorithm().tag_len() {
-            bail!("Encrypted blob is too small");
-        }
-
-        // We expect the nonce at the start followed by the sealed data (encrypted data +
-        // authentication tag).
-        let nonce = Nonce::try_assume_unique_for_key(&bytes[..NONCE_LEN]).unwrap();
-        let mut output = bytes[NONCE_LEN..].to_vec();
-
-        // Verify & decrypt the data in place
-        let unsealed_size = key
-            .open_in_place(nonce, Aad::empty(), &mut output)
-            .context("Failed to unseal blob")?
-            .len();
-
-        // Remove the tag after the plaintext
-        output.truncate(unsealed_size);
-
-        Ok(output)
-    }
-}
-
-#[cfg(test)]
-mod tests {
-    use super::*;
-
-    #[test]
-    fn test_round_trip_data() -> Result<()> {
-        let encryptor = BlobEncryptor::new();
-        let input_keying_material = b"Key is derived from this";
-        let original_bytes = b"This is the secret data";
-
-        let key = encryptor.derive_aead_key(input_keying_material)?;
-        let blob = encryptor.encrypt_bytes(key, original_bytes)?;
-
-        let key = encryptor.derive_aead_key(input_keying_material)?;
-        let decoded_bytes = encryptor.decrypt_bytes(key, &blob)?;
-
-        assert_eq!(decoded_bytes, original_bytes);
-        Ok(())
-    }
-
-    #[test]
-    fn test_modified_data_detected() -> Result<()> {
-        let encryptor = BlobEncryptor::new();
-        let input_keying_material = b"Key is derived from this";
-        let original_bytes = b"This is the secret data";
-
-        let key = encryptor.derive_aead_key(input_keying_material)?;
-        let mut blob = encryptor.encrypt_bytes(key, original_bytes)?;
-
-        // Flip a bit.
-        blob[0] ^= 1;
-
-        let key = encryptor.derive_aead_key(input_keying_material)?;
-        let decoded_bytes = encryptor.decrypt_bytes(key, &blob);
-
-        assert!(decoded_bytes.is_err());
-        Ok(())
-    }
-}
diff --git a/compos/src/compilation.rs b/compos/src/compilation.rs
index 6db31b6..850a0a8 100644
--- a/compos/src/compilation.rs
+++ b/compos/src/compilation.rs
@@ -26,7 +26,7 @@
 use std::process::Command;
 
 use crate::artifact_signer::ArtifactSigner;
-use crate::compos_key_service::Signer;
+use crate::signing_key::Signer;
 use authfs_aidl_interface::aidl::com::android::virt::fs::{
     AuthFsConfig::{
         AuthFsConfig, InputDirFdAnnotation::InputDirFdAnnotation,
diff --git a/compos/src/compos_key_service.rs b/compos/src/compos_key_service.rs
deleted file mode 100644
index 086a162..0000000
--- a/compos/src/compos_key_service.rs
+++ /dev/null
@@ -1,148 +0,0 @@
-// Copyright 2021, 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.
-
-//! Provides a binder service for key generation & verification for CompOs. We assume we have
-//! access to Keystore in the VM, but not persistent storage; instead the host stores the key
-//! on our behalf via this service.
-
-use android_hardware_security_keymint::aidl::android::hardware::security::keymint::{
-    Algorithm::Algorithm, Digest::Digest, KeyParameter::KeyParameter,
-    KeyParameterValue::KeyParameterValue, KeyPurpose::KeyPurpose, PaddingMode::PaddingMode,
-    SecurityLevel::SecurityLevel, Tag::Tag,
-};
-use android_system_keystore2::aidl::android::system::keystore2::{
-    Domain::Domain, IKeystoreSecurityLevel::IKeystoreSecurityLevel,
-    IKeystoreService::IKeystoreService, KeyDescriptor::KeyDescriptor,
-};
-use android_system_keystore2::binder::{wait_for_interface, Strong};
-use anyhow::{anyhow, Context, Result};
-use compos_aidl_interface::aidl::com::android::compos::CompOsKeyData::CompOsKeyData;
-use ring::rand::{SecureRandom, SystemRandom};
-use ring::signature;
-use scopeguard::ScopeGuard;
-
-/// Keystore2 namespace ID, used for access control to keys. In a VM we can use the generic ID
-/// allocated for payloads. See microdroid's keystore2_key_contexts.
-const KEYSTORE_NAMESPACE: i64 = 140;
-
-const KEYSTORE_SERVICE_NAME: &str = "android.system.keystore2.IKeystoreService/default";
-const PURPOSE_SIGN: KeyParameter =
-    KeyParameter { tag: Tag::PURPOSE, value: KeyParameterValue::KeyPurpose(KeyPurpose::SIGN) };
-const ALGORITHM: KeyParameter =
-    KeyParameter { tag: Tag::ALGORITHM, value: KeyParameterValue::Algorithm(Algorithm::RSA) };
-const PADDING: KeyParameter = KeyParameter {
-    tag: Tag::PADDING,
-    value: KeyParameterValue::PaddingMode(PaddingMode::RSA_PKCS1_1_5_SIGN),
-};
-const DIGEST: KeyParameter =
-    KeyParameter { tag: Tag::DIGEST, value: KeyParameterValue::Digest(Digest::SHA_2_256) };
-const KEY_SIZE: KeyParameter =
-    KeyParameter { tag: Tag::KEY_SIZE, value: KeyParameterValue::Integer(2048) };
-const EXPONENT: KeyParameter =
-    KeyParameter { tag: Tag::RSA_PUBLIC_EXPONENT, value: KeyParameterValue::LongInteger(65537) };
-const NO_AUTH_REQUIRED: KeyParameter =
-    KeyParameter { tag: Tag::NO_AUTH_REQUIRED, value: KeyParameterValue::BoolValue(true) };
-
-const BLOB_KEY_DESCRIPTOR: KeyDescriptor =
-    KeyDescriptor { domain: Domain::BLOB, nspace: KEYSTORE_NAMESPACE, alias: None, blob: None };
-
-/// An internal service for CompOS key management.
-#[derive(Clone)]
-pub struct CompOsKeyService {
-    random: SystemRandom,
-    security_level: Strong<dyn IKeystoreSecurityLevel>,
-}
-
-impl CompOsKeyService {
-    pub fn new() -> Result<Self> {
-        let keystore_service = wait_for_interface::<dyn IKeystoreService>(KEYSTORE_SERVICE_NAME)
-            .context("No Keystore service")?;
-
-        Ok(CompOsKeyService {
-            random: SystemRandom::new(),
-            security_level: keystore_service
-                .getSecurityLevel(SecurityLevel::TRUSTED_ENVIRONMENT)
-                .context("Getting SecurityLevel failed")?,
-        })
-    }
-
-    pub fn generate(&self) -> Result<CompOsKeyData> {
-        let key_descriptor = BLOB_KEY_DESCRIPTOR;
-        let key_parameters =
-            [PURPOSE_SIGN, ALGORITHM, PADDING, DIGEST, KEY_SIZE, EXPONENT, NO_AUTH_REQUIRED];
-        let attestation_key = None;
-        let flags = 0;
-        let entropy = [];
-
-        let key_metadata = self
-            .security_level
-            .generateKey(&key_descriptor, attestation_key, &key_parameters, flags, &entropy)
-            .context("Generating key failed")?;
-
-        if let (Some(certificate), Some(blob)) = (key_metadata.certificate, key_metadata.key.blob) {
-            Ok(CompOsKeyData { certificate, keyBlob: blob })
-        } else {
-            Err(anyhow!("Missing cert or blob"))
-        }
-    }
-
-    pub fn verify(&self, key_blob: &[u8], public_key: &[u8]) -> Result<()> {
-        let mut data = [0u8; 32];
-        self.random.fill(&mut data).context("No random data")?;
-
-        let signature = self.new_signer(key_blob).sign(&data)?;
-
-        let public_key =
-            signature::UnparsedPublicKey::new(&signature::RSA_PKCS1_2048_8192_SHA256, public_key);
-        public_key.verify(&data, &signature).context("Signature verification failed")?;
-
-        Ok(())
-    }
-
-    pub fn new_signer(&self, key_blob: &[u8]) -> Signer {
-        Signer { key_blob: key_blob.to_vec(), security_level: self.security_level.clone() }
-    }
-}
-
-pub struct Signer {
-    key_blob: Vec<u8>,
-    security_level: Strong<dyn IKeystoreSecurityLevel>,
-}
-
-impl Signer {
-    pub fn sign(self, data: &[u8]) -> Result<Vec<u8>> {
-        let key_descriptor = KeyDescriptor { blob: Some(self.key_blob), ..BLOB_KEY_DESCRIPTOR };
-        let operation_parameters = [PURPOSE_SIGN, ALGORITHM, PADDING, DIGEST];
-        let forced = false;
-
-        let response = self
-            .security_level
-            .createOperation(&key_descriptor, &operation_parameters, forced)
-            .context("Creating key failed")?;
-        let operation = scopeguard::guard(
-            response.iOperation.ok_or_else(|| anyhow!("No operation created"))?,
-            |op| op.abort().unwrap_or_default(),
-        );
-
-        if response.operationChallenge.is_some() {
-            return Err(anyhow!("Key requires user authorization"));
-        }
-
-        let signature = operation.finish(Some(data), None).context("Signing failed")?;
-        // Operation has finished, we're no longer responsible for aborting it
-        ScopeGuard::into_inner(operation);
-
-        signature.ok_or_else(|| anyhow!("No signature returned"))
-    }
-}
diff --git a/compos/src/compsvc.rs b/compos/src/compsvc.rs
index 60e77a7..e4cdb40 100644
--- a/compos/src/compsvc.rs
+++ b/compos/src/compsvc.rs
@@ -27,8 +27,7 @@
 use std::sync::RwLock;
 
 use crate::compilation::{odrefresh, OdrefreshContext};
-use crate::compos_key_service::{CompOsKeyService, Signer};
-use crate::dice::Dice;
+use crate::signing_key::{Signer, SigningKey};
 use authfs_aidl_interface::aidl::com::android::virt::fs::IAuthFsService::IAuthFsService;
 use compos_aidl_interface::aidl::com::android::compos::{
     CompOsKeyData::CompOsKeyData,
@@ -45,8 +44,7 @@
 pub fn new_binder() -> Result<Strong<dyn ICompOsService>> {
     let service = CompOsService {
         odrefresh_path: PathBuf::from(ODREFRESH_PATH),
-        key_service: CompOsKeyService::new()?,
-        dice: Dice::new()?,
+        signing_key: SigningKey::new()?,
         key_blob: RwLock::new(Vec::new()),
     };
     Ok(BnCompOsService::new_binder(service, BinderFeatures::default()))
@@ -54,8 +52,7 @@
 
 struct CompOsService {
     odrefresh_path: PathBuf,
-    key_service: CompOsKeyService,
-    dice: Dice,
+    signing_key: SigningKey,
     key_blob: RwLock<Vec<u8>>,
 }
 
@@ -65,13 +62,9 @@
         if key.is_empty() {
             Err(new_binder_exception(ExceptionCode::ILLEGAL_STATE, "Key is not initialized"))
         } else {
-            Ok(self.key_service.new_signer(key))
+            Ok(self.signing_key.new_signer(key))
         }
     }
-
-    fn get_boot_certificate_chain(&self) -> Result<Vec<u8>> {
-        self.dice.get_boot_certificate_chain()
-    }
 }
 
 impl Interface for CompOsService {}
@@ -114,11 +107,11 @@
     }
 
     fn generateSigningKey(&self) -> BinderResult<CompOsKeyData> {
-        to_binder_result(self.key_service.generate())
+        to_binder_result(self.signing_key.generate())
     }
 
     fn verifySigningKey(&self, key_blob: &[u8], public_key: &[u8]) -> BinderResult<bool> {
-        Ok(if let Err(e) = self.key_service.verify(key_blob, public_key) {
+        Ok(if let Err(e) = self.signing_key.verify(key_blob, public_key) {
             warn!("Signing key verification failed: {:?}", e);
             false
         } else {
@@ -127,7 +120,7 @@
     }
 
     fn getBootCertificateChain(&self) -> BinderResult<Vec<u8>> {
-        to_binder_result(self.get_boot_certificate_chain())
+        to_binder_result(self.signing_key.get_boot_certificate_chain())
     }
 }
 
diff --git a/compos/src/compsvc_main.rs b/compos/src/compsvc_main.rs
index 23a6ed0..c2923f0 100644
--- a/compos/src/compsvc_main.rs
+++ b/compos/src/compsvc_main.rs
@@ -17,9 +17,8 @@
 //! A tool to start a standalone compsvc server that serves over RPC binder.
 
 mod artifact_signer;
-mod blob_encryptor;
+mod blob_encryption;
 mod compilation;
-mod compos_key_service;
 mod compsvc;
 mod dice;
 mod fsverity;
diff --git a/compos/src/dice.rs b/compos/src/dice.rs
index cdfc387..d9bb1db 100644
--- a/compos/src/dice.rs
+++ b/compos/src/dice.rs
@@ -20,6 +20,7 @@
 use android_security_dice::binder::{wait_for_interface, Strong};
 use anyhow::{Context, Result};
 
+#[derive(Clone)]
 pub struct Dice {
     node: Strong<dyn IDiceNode>,
 }
diff --git a/compos/src/signing_key.rs b/compos/src/signing_key.rs
index 62c7a40..990f9b0 100644
--- a/compos/src/signing_key.rs
+++ b/compos/src/signing_key.rs
@@ -19,60 +19,83 @@
 
 #![allow(dead_code, unused_variables)]
 
-use crate::blob_encryptor::BlobEncryptor;
+use crate::blob_encryption;
 use crate::dice::Dice;
-use anyhow::{bail, Result};
+use anyhow::{bail, Context, Result};
 use compos_aidl_interface::aidl::com::android::compos::CompOsKeyData::CompOsKeyData;
-use ring::rand::SystemRandom;
+use ring::{
+    rand::{SecureRandom, SystemRandom},
+    signature,
+};
 
 pub struct SigningKey {
-    random: SystemRandom,
     dice: Dice,
-    blob_encryptor: BlobEncryptor,
 }
 
 impl SigningKey {
     pub fn new() -> Result<Self> {
-        Ok(Self {
-            random: SystemRandom::new(),
-            dice: Dice::new()?,
-            blob_encryptor: BlobEncryptor::new(),
-        })
+        Ok(Self { dice: Dice::new()? })
+    }
+
+    pub fn get_boot_certificate_chain(&self) -> Result<Vec<u8>> {
+        Dice::new()?.get_boot_certificate_chain()
     }
 
     pub fn generate(&self) -> Result<CompOsKeyData> {
-        // TODO: generate key pair; get aead key; generate random nonce; encrypt private key;
-        // generate self-signed cert
-        bail!("Not implemented")
+        let key_result = compos_native::generate_key_pair();
+        if key_result.public_key.is_empty() || key_result.private_key.is_empty() {
+            bail!("Failed to generate key pair: {}", key_result.error);
+        }
+
+        let encrypted = encrypt_private_key(&self.dice, &key_result.private_key)?;
+        Ok(CompOsKeyData { publicKey: key_result.public_key, keyBlob: encrypted })
     }
 
     pub fn verify(&self, key_blob: &[u8], public_key: &[u8]) -> Result<()> {
-        bail!("Not implemented")
+        // We verify the private key by verifying the AEAD authentication tag in the signer.
+        // To verify the public key matches, we sign a block of random data with the private key,
+        // and then check that the signature matches the purported key.
+        let mut data = [0u8; 32]; // Size is fairly arbitrary.
+        SystemRandom::new().fill(&mut data).context("No random data")?;
+
+        let signature = self.new_signer(key_blob).sign(&data)?;
+
+        let public_key =
+            signature::UnparsedPublicKey::new(&signature::RSA_PKCS1_2048_8192_SHA256, public_key);
+        public_key.verify(&data, &signature).context("Signature verification failed")?;
+
+        Ok(())
     }
 
     pub fn new_signer(&self, key_blob: &[u8]) -> Signer {
-        Signer { key_blob: key_blob.to_owned() }
-    }
-
-    fn encrypt_private_key(&self, private_key: &[u8]) -> Result<Vec<u8>> {
-        let cdi = self.dice.get_sealing_cdi()?;
-        let aead_key = self.blob_encryptor.derive_aead_key(&cdi)?;
-        self.blob_encryptor.encrypt_bytes(aead_key, private_key)
-    }
-
-    fn decrypt_private_key(&self, blob: &[u8]) -> Result<Vec<u8>> {
-        let cdi = self.dice.get_sealing_cdi()?;
-        let aead_key = self.blob_encryptor.derive_aead_key(&cdi)?;
-        self.blob_encryptor.decrypt_bytes(aead_key, blob)
+        Signer { key_blob: key_blob.to_owned(), dice: self.dice.clone() }
     }
 }
 
 pub struct Signer {
     key_blob: Vec<u8>,
+    dice: Dice,
 }
 
 impl Signer {
     pub fn sign(self, data: &[u8]) -> Result<Vec<u8>> {
-        bail!("Not implemented")
+        let private_key = decrypt_private_key(&self.dice, &self.key_blob)?;
+        let sign_result = compos_native::sign(&private_key, data);
+        if sign_result.signature.is_empty() {
+            bail!("Failed to sign: {}", sign_result.error);
+        }
+        Ok(sign_result.signature)
     }
 }
+
+fn encrypt_private_key(dice: &Dice, private_key: &[u8]) -> Result<Vec<u8>> {
+    let cdi = dice.get_sealing_cdi()?;
+    let aead_key = blob_encryption::derive_aead_key(&cdi)?;
+    blob_encryption::encrypt_bytes(aead_key, private_key)
+}
+
+fn decrypt_private_key(dice: &Dice, blob: &[u8]) -> Result<Vec<u8>> {
+    let cdi = dice.get_sealing_cdi()?;
+    let aead_key = blob_encryption::derive_aead_key(&cdi)?;
+    blob_encryption::decrypt_bytes(aead_key, blob)
+}