diff --git a/compos/composd/Android.bp b/compos/composd/Android.bp
index 30d07ab..0a25f05 100644
--- a/compos/composd/Android.bp
+++ b/compos/composd/Android.bp
@@ -15,6 +15,7 @@
         "libanyhow",
         "libbinder_rs",
         "libcompos_common",
+        "libcomposd_native_rust",
         "libnum_traits",
         "liblog_rust",
     ],
diff --git a/compos/composd/native/Android.bp b/compos/composd/native/Android.bp
new file mode 100644
index 0000000..ad0afd9
--- /dev/null
+++ b/compos/composd/native/Android.bp
@@ -0,0 +1,42 @@
+package {
+    default_applicable_licenses: ["Android-Apache-2.0"],
+}
+
+rust_library {
+    name: "libcomposd_native_rust",
+    crate_name: "composd_native",
+    srcs: ["lib.rs"],
+    rustlibs: [
+        "libcxx",
+    ],
+    static_libs: [
+        "libcomposd_native_cpp",
+    ],
+    shared_libs: ["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
new file mode 100644
index 0000000..ebed816
--- /dev/null
+++ b/compos/composd/native/composd_native.cpp
@@ -0,0 +1,66 @@
+/*
+ * 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/composd_native.h b/compos/composd/native/composd_native.h
new file mode 100644
index 0000000..112ef73
--- /dev/null
+++ b/compos/composd/native/composd_native.h
@@ -0,0 +1,21 @@
+/*
+ * 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.
+ */
+
+#pragma once
+
+#include "lib.rs.h"
+
+KeyResult extract_rsa_public_key(rust::Slice<const uint8_t> der_certificate);
diff --git a/compos/composd/native/lib.rs b/compos/composd/native/lib.rs
new file mode 100644
index 0000000..ace9600
--- /dev/null
+++ b/compos/composd/native/lib.rs
@@ -0,0 +1,38 @@
+// 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.
+
+//! Bindings native helpers for composd.
+
+pub use ffi::*;
+
+#[cxx::bridge]
+mod ffi {
+    /// 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;
+    }
+}
diff --git a/compos/composd/src/instance_starter.rs b/compos/composd/src/instance_starter.rs
index 5352250..ec95ff8 100644
--- a/compos/composd/src/instance_starter.rs
+++ b/compos/composd/src/instance_starter.rs
@@ -74,7 +74,7 @@
         let compos_instance = self.start_existing_instance();
         match compos_instance {
             Ok(_) => return compos_instance,
-            Err(e) => warn!("Failed to start {}: {}", self.instance_name, e),
+            Err(e) => warn!("Failed to start: {}", e),
         }
 
         self.start_new_instance(service)
@@ -84,6 +84,8 @@
         // No point even trying if the files we need aren't there.
         self.check_files_exist()?;
 
+        info!("Starting {} CompOs instance", self.instance_name);
+
         let key_blob = fs::read(&self.key_blob).context("Reading private key blob")?;
         let public_key = fs::read(&self.public_key).context("Reading public key")?;
 
@@ -119,8 +121,13 @@
 
         let key_data = service.generateSigningKey().context("Generating signing key")?;
         fs::write(&self.key_blob, &key_data.keyBlob).context("Writing key blob")?;
-        // TODO: Extract public key from cert
-        fs::write(&self.public_key, &key_data.certificate).context("Writing public key")?;
+
+        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")?;
 
         // We don't need to verify the key, since we just generated it and have it in memory.