diff --git a/src/ca-module.cpp b/src/ca-module.cpp
index 802049a..4d055e3 100644
--- a/src/ca-module.cpp
+++ b/src/ca-module.cpp
@@ -48,6 +48,7 @@
   // load the config and create storage
   m_config.load(configPath);
   m_storage = CaStorage::createCaStorage(storageType, m_config.m_caItem.m_caPrefix, "");
+  random::generateSecureBytes(m_requestIdGenKey, 16);
 
   registerPrefix();
 }
@@ -325,7 +326,15 @@
   }
 
   // create new request instance
-  std::string requestId = std::to_string(random::generateWord64());
+  uint64_t requestIdData[2];
+  size_t idDataLen = 16;
+  Block certNameData = clientCert->getName().wireEncode();
+  hmac_sha_256(m_requestIdGenKey, 16, certNameData.value(), certNameData.value_size(), reinterpret_cast<uint8_t *>(requestIdData), &idDataLen);
+  std::stringstream ss;
+  ss << std::hex << std::noshowbase<< requestIdData[0] << requestIdData[1];
+
+  std::string requestId = ss.str();
+
   CaState requestState(m_config.m_caItem.m_caPrefix, requestId, requestType, Status::BEFORE_CHALLENGE, *clientCert,
                        makeBinaryBlock(tlv::ContentType_Key, aesKey, sizeof(aesKey)));
   try {
diff --git a/src/ca-module.hpp b/src/ca-module.hpp
index bcf7b7b..8172688 100644
--- a/src/ca-module.hpp
+++ b/src/ca-module.hpp
@@ -109,6 +109,7 @@
   CaConfig m_config;
   unique_ptr<CaStorage> m_storage;
   security::v2::KeyChain& m_keyChain;
+  uint8_t m_requestIdGenKey[16];
 
   std::list<RegisteredPrefixHandle> m_registeredPrefixHandles;
   std::list<InterestFilterHandle> m_interestFilterHandles;
diff --git a/src/crypto-support/crypto-helper.cpp b/src/crypto-support/crypto-helper.cpp
index 7813187..915dce2 100644
--- a/src/crypto-support/crypto-helper.cpp
+++ b/src/crypto-support/crypto-helper.cpp
@@ -374,6 +374,48 @@
   }
 }
 
+int
+hmac_sha_256(const uint8_t* key, size_t key_len,
+             const uint8_t* cleartext, size_t cleartext_len,
+             uint8_t* output, size_t* output_len)
+{
+    if (!key || !cleartext || !output) {
+        return -1;
+    }
+
+    auto private_key = EVP_PKEY_new_mac_key(EVP_PKEY_HMAC, nullptr, key, key_len);
+    auto hmac_context = EVP_MD_CTX_new();
+    if (!private_key || !hmac_context) {
+        handleErrors("Cannot create and initialise the context when calling HMAC_CTX_new()");
+        return -1;
+    }
+
+    if (EVP_DigestSignInit(hmac_context, nullptr, EVP_sha256(), nullptr, private_key) != 1) {
+        handleErrors("Cannot initialize DigestSign when calling EVP_DigestSignInit()");
+        EVP_MD_CTX_free(hmac_context);
+        EVP_PKEY_free(private_key);
+        return -1;
+    }
+
+    if (EVP_DigestSignUpdate(hmac_context, cleartext, cleartext_len) != 1) {
+        handleErrors("Cannot update DigestSign when calling EVP_DigestSignUpdate()");
+        EVP_MD_CTX_free(hmac_context);
+        EVP_PKEY_free(private_key);
+        return -1;
+    }
+
+    if (EVP_DigestSignFinal(hmac_context, output, output_len) != 1) {
+        handleErrors("Cannot finish DigestSign when calling EVP_DigestSignFinal()");
+        EVP_MD_CTX_free(hmac_context);
+        EVP_PKEY_free(private_key);
+        return -1;
+    }
+
+    EVP_MD_CTX_free(hmac_context);
+    EVP_PKEY_free(private_key);
+    return 0;
+}
+
 void
 handleErrors(const std::string& errorInfo)
 {
diff --git a/src/crypto-support/crypto-helper.hpp b/src/crypto-support/crypto-helper.hpp
index aaa4237..88f1519 100644
--- a/src/crypto-support/crypto-helper.hpp
+++ b/src/crypto-support/crypto-helper.hpp
@@ -108,6 +108,21 @@
 aes_gcm_128_decrypt(const uint8_t* ciphertext, size_t ciphertext_len, const uint8_t* associated, size_t associated_len,
                     const uint8_t* tag, const uint8_t* key, const uint8_t* iv, uint8_t* plaintext);
 
+/**
+ * HMAC SHA 256 keyed hash function
+ * @param key the key for the function
+ * @param key_len the length of the key
+ * @param cleartext the cleartext array to be hashed
+ * @param cleartext_len the length of the array
+ * @param output the output array
+ * @param output_len the longest output len possible (changed to actual on return).
+ * @return 0 if successful, -1 if failed
+ */
+int
+hmac_sha_256(const uint8_t* key, size_t key_len,
+             const uint8_t* cleartext, size_t cleartext_len,
+             uint8_t* output, size_t* output_len);
+
 void
 handleErrors(const std::string& errorInfo);