diff --git a/rialto/Android.bp b/rialto/Android.bp
index 728c1eb..1ab02e9 100644
--- a/rialto/Android.bp
+++ b/rialto/Android.bp
@@ -109,17 +109,21 @@
         "android.system.virtualizationservice-rust",
         "libandroid_logger",
         "libanyhow",
+        "libbssl_avf_nostd",
         "libciborium",
         "libclient_vm_csr",
+        "libcoset",
         "libdiced_sample_inputs",
         "liblibc",
         "liblog_rust",
         "libservice_vm_comm",
         "libservice_vm_manager",
         "libvmclient",
+        "libx509_parser",
     ],
     data: [
         ":rialto_unsigned",
+        ":test_rkp_cert_chain",
     ],
     test_suites: ["general-tests"],
     enabled: false,
diff --git a/rialto/tests/test.rs b/rialto/tests/test.rs
index 0f59350..85c3efe 100644
--- a/rialto/tests/test.rs
+++ b/rialto/tests/test.rs
@@ -22,22 +22,32 @@
     binder::{ParcelFileDescriptor, ProcessState},
 };
 use anyhow::{bail, Context, Result};
+use bssl_avf::{sha256, EcKey, EvpPKey};
 use ciborium::value::Value;
 use client_vm_csr::generate_attestation_key_and_csr;
+use coset::{CborSerializable, CoseMac0, CoseSign};
 use log::info;
 use service_vm_comm::{
-    ClientVmAttestationParams, EcdsaP256KeyPair, GenerateCertificateRequestParams, Request,
-    RequestProcessingError, Response, VmType,
+    ClientVmAttestationParams, Csr, CsrPayload, EcdsaP256KeyPair, GenerateCertificateRequestParams,
+    Request, Response, VmType,
 };
 use service_vm_manager::ServiceVm;
+use std::fs;
 use std::fs::File;
 use std::io;
 use std::panic;
 use std::path::PathBuf;
 use vmclient::VmInstance;
+use x509_parser::{
+    certificate::X509Certificate,
+    der_parser::{der::parse_der, oid, oid::Oid},
+    prelude::FromDer,
+    x509::{AlgorithmIdentifier, SubjectPublicKeyInfo, X509Version},
+};
 
 const UNSIGNED_RIALTO_PATH: &str = "/data/local/tmp/rialto_test/arm64/rialto_unsigned.bin";
 const INSTANCE_IMG_PATH: &str = "/data/local/tmp/rialto_test/arm64/instance.img";
+const TEST_CERT_CHAIN_PATH: &str = "testdata/rkp_cert_chain.der";
 
 #[test]
 fn process_requests_in_protected_vm() -> Result<()> {
@@ -55,7 +65,7 @@
     check_processing_reverse_request(&mut vm)?;
     let key_pair = check_processing_generating_key_pair_request(&mut vm)?;
     check_processing_generating_certificate_request(&mut vm, &key_pair.maced_public_key)?;
-    check_attestation_request(&mut vm, &key_pair.key_blob)?;
+    check_attestation_request(&mut vm, &key_pair)?;
     Ok(())
 }
 
@@ -110,7 +120,10 @@
     }
 }
 
-fn check_attestation_request(vm: &mut ServiceVm, key_blob: &[u8]) -> Result<()> {
+fn check_attestation_request(
+    vm: &mut ServiceVm,
+    remotely_provisioned_key_pair: &EcdsaP256KeyPair,
+) -> Result<()> {
     /// The following data was generated randomly with urandom.
     const CHALLENGE: [u8; 16] = [
         0x7d, 0x86, 0x58, 0x79, 0x3a, 0x09, 0xdf, 0x1c, 0xa5, 0x80, 0x80, 0x15, 0x2b, 0x13, 0x17,
@@ -118,10 +131,18 @@
     ];
     let dice_artifacts = diced_sample_inputs::make_sample_bcc_and_cdis()?;
     let attestation_data = generate_attestation_key_and_csr(&CHALLENGE, &dice_artifacts)?;
+    let cert_chain = fs::read(TEST_CERT_CHAIN_PATH)?;
+    let (remaining, cert) = X509Certificate::from_der(&cert_chain)?;
 
+    // Builds the mock parameters for the client VM attestation.
+    // The `csr` and `remotely_provisioned_key_blob` parameters are extracted from the same
+    // libraries as in production.
+    // The `remotely_provisioned_cert` parameter is an RKP certificate extracted from a test
+    // certificate chain retrieved from RKPD.
     let params = ClientVmAttestationParams {
-        csr: attestation_data.csr.into_cbor_vec()?,
-        remotely_provisioned_key_blob: key_blob.to_vec(),
+        csr: attestation_data.csr.clone().into_cbor_vec()?,
+        remotely_provisioned_key_blob: remotely_provisioned_key_pair.key_blob.to_vec(),
+        remotely_provisioned_cert: cert_chain[..(cert_chain.len() - remaining.len())].to_vec(),
     };
     let request = Request::RequestClientVmAttestation(params);
 
@@ -129,12 +150,76 @@
     info!("Received response: {response:?}.");
 
     match response {
-        // TODO(b/309441500): Check the certificate once it is implemented.
-        Response::Err(RequestProcessingError::OperationUnimplemented) => Ok(()),
+        Response::RequestClientVmAttestation(certificate) => {
+            check_certificate_for_client_vm(
+                &certificate,
+                &remotely_provisioned_key_pair.maced_public_key,
+                &attestation_data.csr,
+                &cert,
+            )?;
+            Ok(())
+        }
         _ => bail!("Incorrect response type: {response:?}"),
     }
 }
 
+fn check_certificate_for_client_vm(
+    certificate: &[u8],
+    maced_public_key: &[u8],
+    csr: &Csr,
+    parent_certificate: &X509Certificate,
+) -> Result<()> {
+    let cose_mac = CoseMac0::from_slice(maced_public_key)?;
+    let authority_public_key = EcKey::from_cose_public_key(&cose_mac.payload.unwrap()).unwrap();
+    let (remaining, cert) = X509Certificate::from_der(certificate)?;
+    assert!(remaining.is_empty());
+
+    // Checks the certificate signature against the authority public key.
+    const ECDSA_WITH_SHA_256: Oid<'static> = oid!(1.2.840 .10045 .4 .3 .2);
+    let expected_algorithm =
+        AlgorithmIdentifier { algorithm: ECDSA_WITH_SHA_256, parameters: None };
+    assert_eq!(expected_algorithm, cert.signature_algorithm);
+    let digest = sha256(cert.tbs_certificate.as_ref()).unwrap();
+    authority_public_key
+        .ecdsa_verify(cert.signature_value.as_ref(), &digest)
+        .expect("Failed to verify the certificate signature with the authority public key");
+
+    // Checks that the certificate's subject public key is equal to the key in the CSR.
+    let cose_sign = CoseSign::from_slice(&csr.signed_csr_payload)?;
+    let csr_payload =
+        cose_sign.payload.as_ref().and_then(|v| CsrPayload::from_cbor_slice(v).ok()).unwrap();
+    let subject_public_key = EcKey::from_cose_public_key(&csr_payload.public_key).unwrap();
+    let expected_spki_data =
+        EvpPKey::try_from(subject_public_key).unwrap().subject_public_key_info().unwrap();
+    let (remaining, expected_spki) = SubjectPublicKeyInfo::from_der(&expected_spki_data)?;
+    assert!(remaining.is_empty());
+    assert_eq!(&expected_spki, cert.public_key());
+
+    // Checks the certificate extension.
+    const ATTESTATION_EXTENSION_OID: Oid<'static> = oid!(1.3.6 .1 .4 .1 .11129 .2 .1 .29 .1);
+    let extensions = cert.extensions();
+    assert_eq!(1, extensions.len());
+    let extension = &extensions[0];
+    assert_eq!(ATTESTATION_EXTENSION_OID, extension.oid);
+    assert!(!extension.critical);
+    let (remaining, extension) = parse_der(extension.value)?;
+    assert!(remaining.is_empty());
+    let attestation_ext = extension.as_sequence()?;
+    assert_eq!(1, attestation_ext.len());
+    assert_eq!(csr_payload.challenge, attestation_ext[0].as_slice()?);
+
+    // Checks other fields on the certificate
+    assert_eq!(X509Version::V3, cert.version());
+    assert_eq!(parent_certificate.validity(), cert.validity());
+    assert_eq!(
+        String::from("CN=Android Protected Virtual Machine Key"),
+        cert.subject().to_string()
+    );
+    assert_eq!(parent_certificate.subject(), cert.issuer());
+
+    Ok(())
+}
+
 /// TODO(b/300625792): Check the CSR with libhwtrust once the CSR is complete.
 fn check_csr(csr: Vec<u8>) -> Result<()> {
     let mut reader = io::Cursor::new(csr);
diff --git a/service_vm/comm/Android.bp b/service_vm/comm/Android.bp
index 6e05587..bdfc099 100644
--- a/service_vm/comm/Android.bp
+++ b/service_vm/comm/Android.bp
@@ -24,6 +24,7 @@
         "libbssl_avf_error_nostd",
         "libciborium_nostd",
         "libcoset_nostd",
+        "libder_nostd",
         "liblog_rust_nostd",
         "libserde_nostd",
     ],
diff --git a/service_vm/comm/src/message.rs b/service_vm/comm/src/message.rs
index 6dd0ccd..87c8378 100644
--- a/service_vm/comm/src/message.rs
+++ b/service_vm/comm/src/message.rs
@@ -66,6 +66,13 @@
 
     /// The key blob retrieved from RKPD by virtualizationservice.
     pub remotely_provisioned_key_blob: Vec<u8>,
+
+    /// The leaf certificate of the certificate chain retrieved from RKPD by
+    /// virtualizationservice.
+    ///
+    /// This certificate is a DER-encoded X.509 certificate that includes the remotely
+    /// provisioned public key.
+    pub remotely_provisioned_cert: Vec<u8>,
 }
 
 /// Represents a response to a request sent to the service VM.
@@ -120,6 +127,9 @@
 
     /// The requested operation has not been implemented.
     OperationUnimplemented,
+
+    /// An error happened during the DER encoding/decoding.
+    DerError,
 }
 
 impl fmt::Display for RequestProcessingError {
@@ -142,6 +152,9 @@
             Self::OperationUnimplemented => {
                 write!(f, "The requested operation has not been implemented")
             }
+            Self::DerError => {
+                write!(f, "An error happened during the DER encoding/decoding")
+            }
         }
     }
 }
@@ -166,6 +179,14 @@
     }
 }
 
+#[cfg(not(feature = "std"))]
+impl From<der::Error> for RequestProcessingError {
+    fn from(e: der::Error) -> Self {
+        error!("DER encoding/decoding error: {e}");
+        Self::DerError
+    }
+}
+
 /// Represents the params passed to GenerateCertificateRequest
 #[derive(Clone, Debug, Serialize, Deserialize)]
 pub struct GenerateCertificateRequestParams {
diff --git a/service_vm/requests/Android.bp b/service_vm/requests/Android.bp
index ecede8b..52b54b4 100644
--- a/service_vm/requests/Android.bp
+++ b/service_vm/requests/Android.bp
@@ -21,10 +21,13 @@
         "libcbor_util_nostd",
         "libciborium_nostd",
         "libcoset_nostd",
+        "libder_nostd",
         "libdiced_open_dice_nostd",
         "liblog_rust_nostd",
         "libserde_nostd",
         "libservice_vm_comm_nostd",
+        "libspki_nostd",
+        "libx509_cert_nostd",
         "libzeroize_nostd",
     ],
 }
diff --git a/service_vm/requests/src/cert.rs b/service_vm/requests/src/cert.rs
new file mode 100644
index 0000000..68ca382
--- /dev/null
+++ b/service_vm/requests/src/cert.rs
@@ -0,0 +1,130 @@
+// Copyright 2023, 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.
+
+//! Generation of certificates and attestation extensions.
+
+use alloc::vec;
+use der::{
+    asn1::{BitStringRef, ObjectIdentifier, UIntRef},
+    oid::AssociatedOid,
+    Decode, Sequence,
+};
+use spki::{AlgorithmIdentifier, SubjectPublicKeyInfo};
+use x509_cert::{
+    certificate::{Certificate, TbsCertificate, Version},
+    ext::Extension,
+    name::Name,
+    time::Validity,
+};
+
+/// OID value for ECDSA with SHA-256, see RFC 5912 s6.
+const ECDSA_WITH_SHA_256: ObjectIdentifier = ObjectIdentifier::new_unwrap("1.2.840.10045.4.3.2");
+
+/// OID value for the protected VM remote attestation extension.
+///
+/// This OID value was added at cl/584542390.
+const AVF_ATTESTATION_EXTENSION_V1: ObjectIdentifier =
+    ObjectIdentifier::new_unwrap("1.3.6.1.4.1.11129.2.1.29.1");
+
+/// Attestation extension contents
+///
+/// ```asn1
+/// AttestationDescription ::= SEQUENCE {
+///     attestationChallenge       OCTET_STRING,
+/// }
+/// ```
+/// TODO(b/312448064): Add VM root of trust and payload information to the extension.
+#[derive(Debug, Clone, Sequence)]
+pub(crate) struct AttestationExtension<'a> {
+    #[asn1(type = "OCTET STRING")]
+    attestation_challenge: &'a [u8],
+}
+
+impl<'a> AssociatedOid for AttestationExtension<'a> {
+    const OID: ObjectIdentifier = AVF_ATTESTATION_EXTENSION_V1;
+}
+
+impl<'a> AttestationExtension<'a> {
+    pub(crate) fn new(challenge: &'a [u8]) -> Self {
+        Self { attestation_challenge: challenge }
+    }
+}
+
+/// Builds an X.509 `Certificate` as defined in RFC 5280 Section 4.1:
+///
+/// ```asn1
+/// Certificate  ::=  SEQUENCE  {
+///   tbsCertificate       TBSCertificate,
+///   signatureAlgorithm   AlgorithmIdentifier,
+///   signature            BIT STRING
+/// }
+/// ```
+pub(crate) fn build_certificate<'a>(
+    tbs_cert: TbsCertificate<'a>,
+    signature: &'a [u8],
+) -> der::Result<Certificate<'a>> {
+    Ok(Certificate {
+        signature_algorithm: tbs_cert.signature,
+        tbs_certificate: tbs_cert,
+        signature: BitStringRef::new(0, signature)?,
+    })
+}
+
+/// Builds an X.509 `TbsCertificate` as defined in RFC 5280 Section 4.1:
+///
+/// ```asn1
+/// TBSCertificate  ::=  SEQUENCE  {
+///   version         [0]  EXPLICIT Version DEFAULT v1,
+///   serialNumber         CertificateSerialNumber,
+///   signature            AlgorithmIdentifier,
+///   issuer               Name,
+///   validity             Validity,
+///   subject              Name,
+///   subjectPublicKeyInfo SubjectPublicKeyInfo,
+///   issuerUniqueID  [1]  IMPLICIT UniqueIdentifier OPTIONAL,
+///                        -- If present, version MUST be v2 or v3
+///   subjectUniqueID [2]  IMPLICIT UniqueIdentifier OPTIONAL,
+///                        -- If present, version MUST be v2 or v3
+///   extensions      [3]  Extensions OPTIONAL
+///                        -- If present, version MUST be v3 --
+/// }
+/// ```
+pub(crate) fn build_tbs_certificate<'a>(
+    serial_number: &'a [u8],
+    issuer: Name<'a>,
+    subject: Name<'a>,
+    validity: Validity,
+    subject_public_key_info: &'a [u8],
+    attestation_ext: &'a [u8],
+) -> der::Result<TbsCertificate<'a>> {
+    let signature = AlgorithmIdentifier { oid: ECDSA_WITH_SHA_256, parameters: None };
+    let subject_public_key_info = SubjectPublicKeyInfo::from_der(subject_public_key_info)?;
+    let extensions = vec![Extension {
+        extn_id: AttestationExtension::OID,
+        critical: false,
+        extn_value: attestation_ext,
+    }];
+    Ok(TbsCertificate {
+        version: Version::V3,
+        serial_number: UIntRef::new(serial_number)?,
+        signature,
+        issuer,
+        validity,
+        subject,
+        subject_public_key_info,
+        issuer_unique_id: None,
+        subject_unique_id: None,
+        extensions: Some(extensions),
+    })
+}
diff --git a/service_vm/requests/src/client_vm.rs b/service_vm/requests/src/client_vm.rs
index 612605f..e1f345c 100644
--- a/service_vm/requests/src/client_vm.rs
+++ b/service_vm/requests/src/client_vm.rs
@@ -15,14 +15,17 @@
 //! This module contains functions related to the attestation of the
 //! client VM.
 
+use crate::cert;
 use crate::keyblob::decrypt_private_key;
 use alloc::vec::Vec;
-use bssl_avf::{sha256, EcKey};
+use bssl_avf::{rand_bytes, sha256, EcKey, EvpPKey};
 use core::result;
 use coset::{CborSerializable, CoseSign};
+use der::{Decode, Encode};
 use diced_open_dice::DiceArtifacts;
 use log::error;
 use service_vm_comm::{ClientVmAttestationParams, Csr, CsrPayload, RequestProcessingError};
+use x509_cert::{certificate::Certificate, name::Name};
 
 type Result<T> = result::Result<T, RequestProcessingError>;
 
@@ -50,21 +53,41 @@
     cose_sign.verify_signature(ATTESTATION_KEY_SIGNATURE_INDEX, aad, |signature, message| {
         ecdsa_verify(&ec_public_key, signature, message)
     })?;
+    let subject_public_key_info = EvpPKey::try_from(ec_public_key)?.subject_public_key_info()?;
 
     // TODO(b/278717513): Compare client VM's DICE chain in the `csr` up to pvmfw
     // cert with RKP VM's DICE chain.
 
+    // Builds the TBSCertificate.
+    // The serial number can be up to 20 bytes according to RFC5280 s4.1.2.2.
+    // In this case, a serial number with a length of 20 bytes is used to ensure that each
+    // certificate signed by RKP VM has a unique serial number.
+    let mut serial_number = [0u8; 20];
+    rand_bytes(&mut serial_number)?;
+    let subject = Name::encode_from_string("CN=Android Protected Virtual Machine Key")?;
+    let rkp_cert = Certificate::from_der(&params.remotely_provisioned_cert)?;
+    let attestation_ext = cert::AttestationExtension::new(&csr_payload.challenge).to_vec()?;
+    let tbs_cert = cert::build_tbs_certificate(
+        &serial_number,
+        rkp_cert.tbs_certificate.subject,
+        Name::from_der(&subject)?,
+        rkp_cert.tbs_certificate.validity,
+        &subject_public_key_info,
+        &attestation_ext,
+    )?;
+
+    // Signs the TBSCertificate and builds the Certificate.
+    // The two private key structs below will be zeroed out on drop.
     let private_key =
         decrypt_private_key(&params.remotely_provisioned_key_blob, dice_artifacts.cdi_seal())
             .map_err(|e| {
                 error!("Failed to decrypt the remotely provisioned key blob: {e}");
                 RequestProcessingError::FailedToDecryptKeyBlob
             })?;
-    let _ec_private_key = EcKey::from_ec_private_key(private_key.as_slice())?;
-
-    // TODO(b/309441500): Build a new certificate signed with the remotely provisioned
-    // `_private_key`.
-    Err(RequestProcessingError::OperationUnimplemented)
+    let ec_private_key = EcKey::from_ec_private_key(private_key.as_slice())?;
+    let signature = ecdsa_sign(&ec_private_key, &tbs_cert.to_vec()?)?;
+    let certificate = cert::build_certificate(tbs_cert, &signature)?;
+    Ok(certificate.to_vec()?)
 }
 
 fn ecdsa_verify(key: &EcKey, signature: &[u8], message: &[u8]) -> bssl_avf::Result<()> {
@@ -72,3 +95,8 @@
     let digest = sha256(message)?;
     key.ecdsa_verify(signature, &digest)
 }
+
+fn ecdsa_sign(key: &EcKey, message: &[u8]) -> bssl_avf::Result<Vec<u8>> {
+    let digest = sha256(message)?;
+    key.ecdsa_sign(&digest)
+}
diff --git a/service_vm/requests/src/lib.rs b/service_vm/requests/src/lib.rs
index b2db298..3f687a4 100644
--- a/service_vm/requests/src/lib.rs
+++ b/service_vm/requests/src/lib.rs
@@ -19,6 +19,7 @@
 extern crate alloc;
 
 mod api;
+mod cert;
 mod client_vm;
 mod keyblob;
 mod pub_key;
diff --git a/virtualizationservice/src/aidl.rs b/virtualizationservice/src/aidl.rs
index d1f7291..3ac1e60 100644
--- a/virtualizationservice/src/aidl.rs
+++ b/virtualizationservice/src/aidl.rs
@@ -196,10 +196,14 @@
             ))
             .with_log();
         }
-        let certificate = request_attestation(csr, &attestation_key.keyBlob)
-            .context("Failed to request attestation")
-            .with_log()
-            .or_service_specific_exception(-1)?;
+        let certificate = request_attestation(
+            csr.to_vec(),
+            attestation_key.keyBlob,
+            certificate_chain[0].encodedCertificate.clone(),
+        )
+        .context("Failed to request attestation")
+        .with_log()
+        .or_service_specific_exception(-1)?;
         certificate_chain.insert(0, Certificate { encodedCertificate: certificate });
 
         Ok(certificate_chain)
diff --git a/virtualizationservice/src/rkpvm.rs b/virtualizationservice/src/rkpvm.rs
index 5087120..79e09b0 100644
--- a/virtualizationservice/src/rkpvm.rs
+++ b/virtualizationservice/src/rkpvm.rs
@@ -24,15 +24,14 @@
 use service_vm_manager::ServiceVm;
 
 pub(crate) fn request_attestation(
-    csr: &[u8],
-    remotely_provisioned_keyblob: &[u8],
+    csr: Vec<u8>,
+    remotely_provisioned_key_blob: Vec<u8>,
+    remotely_provisioned_cert: Vec<u8>,
 ) -> Result<Vec<u8>> {
     let mut vm = ServiceVm::start()?;
 
-    let params = ClientVmAttestationParams {
-        csr: csr.to_vec(),
-        remotely_provisioned_key_blob: remotely_provisioned_keyblob.to_vec(),
-    };
+    let params =
+        ClientVmAttestationParams { csr, remotely_provisioned_key_blob, remotely_provisioned_cert };
     let request = Request::RequestClientVmAttestation(params);
     match vm.process_request(request).context("Failed to process request")? {
         Response::RequestClientVmAttestation(cert) => Ok(cert),