Need to send REST Header timestamp in EPOCH milliseconds, getting Malformed JSON error from Gateway

Outside vendor wants us to send REST header timestamp in EPOCH milliseconds, expecting 13 characters. Test works in Postman, but in PeopleSoft, we get a "400 Bad Request" error with a gateway response that includes the following:

{"type":"GATEWAY","code":"121","message":"Malformed JSON"}

If we send EPOCH seconds (10 characters), this does get to the vendor, but we get a "401 Unauthorized" error a response that includes:

"error":[{"type":"APIM","message":"ApiKey and/or Authentication supplied are invalid."}

The vendor says the EPOCH time they are receiving in seconds is too short, it must be in milliseconds.

If I take the seconds and multiply by 10 or 100, we still get the second error response from the vendor, but avoid the "Malformed JSON" from the gateway. But as soon as we go to milliseconds precision, or go to 13 characters by multiplying seconds by 1000 or padding "000" to the timestamp string, we get the malformed json error.