diff --git a/payload_consumer/delta_performer.cc b/payload_consumer/delta_performer.cc
index ae73d03..d76a959 100644
--- a/payload_consumer/delta_performer.cc
+++ b/payload_consumer/delta_performer.cc
@@ -1816,9 +1816,7 @@
                       !signatures_message_data_.empty());
   brillo::Blob hash_data = signed_hash_calculator_.raw_hash();
   TEST_AND_RETURN_VAL(ErrorCode::kDownloadPayloadPubKeyVerificationError,
-                      PayloadVerifier::PadRSA2048SHA256Hash(&hash_data));
-  TEST_AND_RETURN_VAL(ErrorCode::kDownloadPayloadPubKeyVerificationError,
-                      !hash_data.empty());
+                      hash_data.size() == kSHA256Size);
 
   if (!PayloadVerifier::VerifySignature(
           signatures_message_data_, public_key, hash_data)) {
diff --git a/payload_consumer/payload_metadata.cc b/payload_consumer/payload_metadata.cc
index 8b3eb4e..3739767 100644
--- a/payload_consumer/payload_metadata.cc
+++ b/payload_consumer/payload_metadata.cc
@@ -20,6 +20,7 @@
 
 #include <brillo/data_encoding.h>
 
+#include "update_engine/common/constants.h"
 #include "update_engine/common/hash_calculator.h"
 #include "update_engine/common/utils.h"
 #include "update_engine/payload_consumer/payload_constants.h"
@@ -187,16 +188,16 @@
     return ErrorCode::kDownloadMetadataSignatureMissingError;
   }
 
-  brillo::Blob calculated_metadata_hash;
+  brillo::Blob metadata_hash;
   if (!HashCalculator::RawHashOfBytes(
-          payload.data(), metadata_size_, &calculated_metadata_hash)) {
+          payload.data(), metadata_size_, &metadata_hash)) {
     LOG(ERROR) << "Unable to compute actual hash of manifest";
     return ErrorCode::kDownloadMetadataSignatureVerificationError;
   }
 
-  PayloadVerifier::PadRSA2048SHA256Hash(&calculated_metadata_hash);
-  if (calculated_metadata_hash.empty()) {
-    LOG(ERROR) << "Computed actual hash of metadata is empty.";
+  if (metadata_hash.size() != kSHA256Size) {
+    LOG(ERROR) << "Computed actual hash of metadata has incorrect size: "
+               << metadata_hash.size();
     return ErrorCode::kDownloadMetadataSignatureVerificationError;
   }
 
@@ -207,17 +208,25 @@
       LOG(ERROR) << "Unable to compute expected hash from metadata signature";
       return ErrorCode::kDownloadMetadataSignatureError;
     }
-    if (calculated_metadata_hash != expected_metadata_hash) {
+
+    brillo::Blob padded_metadata_hash = metadata_hash;
+    if (!PayloadVerifier::PadRSASHA256Hash(&padded_metadata_hash,
+                                           expected_metadata_hash.size())) {
+      LOG(ERROR) << "Failed to pad the SHA256 hash to "
+                 << expected_metadata_hash.size() << " bytes.";
+      return ErrorCode::kDownloadMetadataSignatureVerificationError;
+    }
+
+    if (padded_metadata_hash != expected_metadata_hash) {
       LOG(ERROR) << "Manifest hash verification failed. Expected hash = ";
       utils::HexDumpVector(expected_metadata_hash);
       LOG(ERROR) << "Calculated hash = ";
-      utils::HexDumpVector(calculated_metadata_hash);
+      utils::HexDumpVector(padded_metadata_hash);
       return ErrorCode::kDownloadMetadataSignatureMismatch;
     }
   } else {
-    if (!PayloadVerifier::VerifySignature(metadata_signature_protobuf,
-                                          pem_public_key,
-                                          calculated_metadata_hash)) {
+    if (!PayloadVerifier::VerifySignature(
+            metadata_signature_protobuf, pem_public_key, metadata_hash)) {
       LOG(ERROR) << "Manifest hash verification failed.";
       return ErrorCode::kDownloadMetadataSignatureMismatch;
     }
diff --git a/payload_consumer/payload_verifier.cc b/payload_consumer/payload_verifier.cc
index 3eb1da8..3a3ccbf 100644
--- a/payload_consumer/payload_verifier.cc
+++ b/payload_consumer/payload_verifier.cc
@@ -16,11 +16,13 @@
 
 #include "update_engine/payload_consumer/payload_verifier.h"
 
+#include <utility>
 #include <vector>
 
 #include <base/logging.h>
 #include <openssl/pem.h>
 
+#include "update_engine/common/constants.h"
 #include "update_engine/common/hash_calculator.h"
 #include "update_engine/common/utils.h"
 #include "update_engine/update_metadata.pb.h"
@@ -31,57 +33,27 @@
 
 namespace {
 
-// The following is a standard PKCS1-v1_5 padding for SHA256 signatures, as
-// defined in RFC3447. It is prepended to the actual signature (32 bytes) to
-// form a sequence of 256 bytes (2048 bits) that is amenable to RSA signing. The
-// padded hash will look as follows:
+// The ASN.1 DigestInfo prefix for encoding SHA256 digest. The complete 51-byte
+// DigestInfo consists of 19-byte SHA256_DIGEST_INFO_PREFIX and 32-byte SHA256
+// digest.
 //
-//    0x00 0x01 0xff ... 0xff 0x00  ASN1HEADER  SHA256HASH
-//   |--------------205-----------||----19----||----32----|
-//
-// where ASN1HEADER is the ASN.1 description of the signed data. The complete 51
-// bytes of actual data (i.e. the ASN.1 header complete with the hash) are
-// packed as follows:
-//
-//  SEQUENCE(2+49) {
+// SEQUENCE(2+49) {
 //   SEQUENCE(2+13) {
-//    OBJECT(2+9) id-sha256
-//    NULL(2+0)
+//     OBJECT(2+9) id-sha256
+//     NULL(2+0)
 //   }
 //   OCTET STRING(2+32) <actual signature bytes...>
-//  }
-// clang-format off
-const uint8_t kRSA2048SHA256Padding[] = {
-    // PKCS1-v1_5 padding
-    0x00, 0x01, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
-    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
-    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
-    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
-    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
-    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
-    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
-    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
-    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
-    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
-    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
-    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
-    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
-    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
-    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
-    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
-    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
-    0x00,
-    // ASN.1 header
-    0x30, 0x31, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03,
-    0x04, 0x02, 0x01, 0x05, 0x00, 0x04, 0x20,
+// }
+const uint8_t kSHA256DigestInfoPrefix[] = {
+    0x30, 0x31, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01,
+    0x65, 0x03, 0x04, 0x02, 0x01, 0x05, 0x00, 0x04, 0x20,
 };
-// clang-format on
 
 }  // namespace
 
 bool PayloadVerifier::VerifySignature(const string& signature_proto,
                                       const string& pem_public_key,
-                                      const brillo::Blob& hash_data) {
+                                      const brillo::Blob& sha256_hash_data) {
   Signatures signatures;
   LOG(INFO) << "signature blob size = " << signature_proto.size();
   TEST_AND_RETURN_FALSE(signatures.ParseFromString(signature_proto));
@@ -100,7 +72,9 @@
     if (!GetRawHashFromSignature(sig_data, pem_public_key, &sig_hash_data))
       continue;
 
-    if (hash_data == sig_hash_data) {
+    brillo::Blob padded_hash_data = sha256_hash_data;
+    if (PadRSASHA256Hash(&padded_hash_data, sig_hash_data.size()) &&
+        padded_hash_data == sig_hash_data) {
       LOG(INFO) << "Verified correct signature " << i + 1 << " out of "
                 << signatures.signatures_size() << " signatures.";
       return true;
@@ -108,8 +82,8 @@
     tested_hashes.push_back(sig_hash_data);
   }
   LOG(ERROR) << "None of the " << signatures.signatures_size()
-             << " signatures is correct. Expected:";
-  utils::HexDumpVector(hash_data);
+             << " signatures is correct. Expected hash before padding:";
+  utils::HexDumpVector(sha256_hash_data);
   LOG(ERROR) << "But found decrypted hashes:";
   for (const auto& sig_hash_data : tested_hashes) {
     utils::HexDumpVector(sig_hash_data);
@@ -150,13 +124,30 @@
   return true;
 }
 
-bool PayloadVerifier::PadRSA2048SHA256Hash(brillo::Blob* hash) {
-  TEST_AND_RETURN_FALSE(hash->size() == 32);
-  hash->insert(hash->begin(),
-               reinterpret_cast<const char*>(kRSA2048SHA256Padding),
-               reinterpret_cast<const char*>(kRSA2048SHA256Padding +
-                                             sizeof(kRSA2048SHA256Padding)));
-  TEST_AND_RETURN_FALSE(hash->size() == 256);
+bool PayloadVerifier::PadRSASHA256Hash(brillo::Blob* hash, size_t rsa_size) {
+  TEST_AND_RETURN_FALSE(hash->size() == kSHA256Size);
+  TEST_AND_RETURN_FALSE(rsa_size == 256 || rsa_size == 512);
+
+  // The following is a standard PKCS1-v1_5 padding for SHA256 signatures, as
+  // defined in RFC3447 section 9.2. It is prepended to the actual signature
+  // (32 bytes) to form a sequence of 256|512 bytes (2048|4096 bits) that is
+  // amenable to RSA signing. The padded hash will look as follows:
+  //
+  //    0x00 0x01 0xff ... 0xff 0x00  ASN1HEADER  SHA256HASH
+  //   |-----------205|461----------||----19----||----32----|
+  size_t padding_string_size =
+      rsa_size - hash->size() - sizeof(kSHA256DigestInfoPrefix) - 3;
+  brillo::Blob padded_result = brillo::CombineBlobs({
+      {0x00, 0x01},
+      brillo::Blob(padding_string_size, 0xff),
+      {0x00},
+      brillo::Blob(kSHA256DigestInfoPrefix,
+                   kSHA256DigestInfoPrefix + sizeof(kSHA256DigestInfoPrefix)),
+      *hash,
+  });
+
+  *hash = std::move(padded_result);
+  TEST_AND_RETURN_FALSE(hash->size() == rsa_size);
   return true;
 }
 
diff --git a/payload_consumer/payload_verifier.h b/payload_consumer/payload_verifier.h
index 09bdbf9..af8e05f 100644
--- a/payload_consumer/payload_verifier.h
+++ b/payload_consumer/payload_verifier.h
@@ -34,12 +34,13 @@
   // Interprets |signature_proto| as a protocol buffer containing the Signatures
   // message and decrypts each signature data using the |pem_public_key|.
   // |pem_public_key| should be a PEM format RSA public key data.
-  // Returns whether *any* of the decrypted hashes matches the |hash_data|.
-  // In case of any error parsing the signatures or the public key, returns
-  // false.
+  // Pads the 32 bytes |sha256_hash_data| to 256 or 512 bytes according to the
+  // PKCS#1 v1.5 standard; and returns whether *any* of the decrypted hashes
+  // matches the padded hash data. In case of any error parsing the signatures
+  // or the public key, returns false.
   static bool VerifySignature(const std::string& signature_proto,
                               const std::string& pem_public_key,
-                              const brillo::Blob& hash_data);
+                              const brillo::Blob& sha256_hash_data);
 
   // Decrypts |sig_data| with the given |pem_public_key| and populates
   // |out_hash_data| with the decoded raw hash. |pem_public_key| should be a PEM
@@ -48,12 +49,13 @@
                                       const std::string& pem_public_key,
                                       brillo::Blob* out_hash_data);
 
-  // Pads a SHA256 hash so that it may be encrypted/signed with RSA2048
-  // using the PKCS#1 v1.5 scheme.
-  // hash should be a pointer to vector of exactly 256 bits. The vector
-  // will be modified in place and will result in having a length of
-  // 2048 bits. Returns true on success, false otherwise.
-  static bool PadRSA2048SHA256Hash(brillo::Blob* hash);
+  // Pads a SHA256 hash so that it may be encrypted/signed with RSA2048 or
+  // RSA4096 using the PKCS#1 v1.5 scheme.
+  // hash should be a pointer to vector of exactly 256 bits. |rsa_size| must be
+  // one of 256 or 512 bytes. The vector will be modified in place and will
+  // result in having a length of 2048 or 4096 bits, depending on the rsa size.
+  // Returns true on success, false otherwise.
+  static bool PadRSASHA256Hash(brillo::Blob* hash, size_t rsa_size);
 
  private:
   // This should never be constructed