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/native/compos_native.h b/compos/native/compos_native.h
new file mode 100644
index 0000000..6497c9b
--- /dev/null
+++ b/compos/native/compos_native.h
@@ -0,0 +1,23 @@
+/*
+ * 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 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;
+    }
+}