diff --git a/virtualizationservice/src/remote_provisioning.rs b/virtualizationservice/src/remote_provisioning.rs
index 599a614..06f8ad4 100644
--- a/virtualizationservice/src/remote_provisioning.rs
+++ b/virtualizationservice/src/remote_provisioning.rs
@@ -14,17 +14,20 @@
 
 //! IRemotelyProvisionedComponent HAL implementation.
 
+use crate::rkpvm;
 use android_hardware_security_rkp::aidl::android::hardware::security::keymint::{
     DeviceInfo::DeviceInfo,
     IRemotelyProvisionedComponent::{
-        BnRemotelyProvisionedComponent, IRemotelyProvisionedComponent, STATUS_REMOVED,
+        BnRemotelyProvisionedComponent, IRemotelyProvisionedComponent, STATUS_FAILED,
+        STATUS_REMOVED,
     },
     MacedPublicKey::MacedPublicKey,
     ProtectedData::ProtectedData,
     RpcHardwareInfo::{RpcHardwareInfo, CURVE_NONE, MIN_SUPPORTED_NUM_KEYS_IN_CSR},
 };
+use anyhow::Context;
 use avflog::LogResult;
-use binder::{BinderFeatures, ExceptionCode, Interface, Result as BinderResult, Status, Strong};
+use binder::{BinderFeatures, Interface, IntoBinderResult, Result as BinderResult, Status, Strong};
 
 /// Constructs a binder object that implements `IRemotelyProvisionedComponent`.
 pub(crate) fn new_binder() -> Strong<dyn IRemotelyProvisionedComponent> {
@@ -53,7 +56,7 @@
     fn generateEcdsaP256KeyPair(
         &self,
         testMode: bool,
-        _macedPublicKey: &mut MacedPublicKey,
+        macedPublicKey: &mut MacedPublicKey,
     ) -> BinderResult<Vec<u8>> {
         if testMode {
             return Err(Status::new_service_specific_error_str(
@@ -62,8 +65,12 @@
             ))
             .with_log();
         }
-        // TODO(b/274881098): Implement this.
-        Err(Status::new_exception(ExceptionCode::UNSUPPORTED_OPERATION, None)).with_log()
+        let key_pair = rkpvm::generate_ecdsa_p256_key_pair()
+            .context("Failed to generate ECDSA P-256 key pair")
+            .with_log()
+            .or_service_specific_exception(STATUS_FAILED)?;
+        macedPublicKey.macedKey = key_pair.maced_public_key;
+        Ok(key_pair.key_blob)
     }
 
     fn generateCertificateRequest(
@@ -84,10 +91,13 @@
 
     fn generateCertificateRequestV2(
         &self,
-        _keysToSign: &[MacedPublicKey],
-        _challenge: &[u8],
+        keysToSign: &[MacedPublicKey],
+        challenge: &[u8],
     ) -> BinderResult<Vec<u8>> {
-        // TODO(b/274881098): Implement this.
-        Err(Status::new_exception(ExceptionCode::UNSUPPORTED_OPERATION, None)).with_log()
+        // TODO(b/299259624): Validate the MAC of the keys to certify.
+        rkpvm::generate_certificate_request(keysToSign, challenge)
+            .context("Failed to generate certificate request")
+            .with_log()
+            .or_service_specific_exception(STATUS_FAILED)
     }
 }
diff --git a/virtualizationservice/src/rkpvm.rs b/virtualizationservice/src/rkpvm.rs
index dbadd60..80953b5 100644
--- a/virtualizationservice/src/rkpvm.rs
+++ b/virtualizationservice/src/rkpvm.rs
@@ -16,8 +16,9 @@
 //! The RKP VM will be recognized and attested by the RKP server periodically and
 //! serves as a trusted platform to attest a client VM.
 
+use android_hardware_security_rkp::aidl::android::hardware::security::keymint::MacedPublicKey::MacedPublicKey;
 use anyhow::{bail, Context, Result};
-use service_vm_comm::{Request, Response};
+use service_vm_comm::{EcdsaP256KeyPair, GenerateCertificateRequestParams, Request, Response};
 use service_vm_manager::ServiceVm;
 
 pub(crate) fn request_certificate(csr: &[u8]) -> Result<Vec<u8>> {
@@ -31,3 +32,29 @@
         _ => bail!("Incorrect response type"),
     }
 }
+
+pub(crate) fn generate_ecdsa_p256_key_pair() -> Result<EcdsaP256KeyPair> {
+    let mut vm = ServiceVm::start()?;
+    let request = Request::GenerateEcdsaP256KeyPair;
+    match vm.process_request(request).context("Failed to process request")? {
+        Response::GenerateEcdsaP256KeyPair(key_pair) => Ok(key_pair),
+        _ => bail!("Incorrect response type"),
+    }
+}
+
+pub(crate) fn generate_certificate_request(
+    keys_to_sign: &[MacedPublicKey],
+    challenge: &[u8],
+) -> Result<Vec<u8>> {
+    let params = GenerateCertificateRequestParams {
+        keys_to_sign: keys_to_sign.iter().map(|v| v.macedKey.to_vec()).collect(),
+        challenge: challenge.to_vec(),
+    };
+    let request = Request::GenerateCertificateRequest(params);
+
+    let mut vm = ServiceVm::start()?;
+    match vm.process_request(request).context("Failed to process request")? {
+        Response::GenerateCertificateRequest(csr) => Ok(csr),
+        _ => bail!("Incorrect response type"),
+    }
+}