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;