2467526 - "Unexpected error" when sending messages "Send cXML to ASN Failed"

When using a Process Integration (PI) or Process Orchestration (PO) XI Adapter, messages are failing and the logs show errors similar to the following:

[Error Level] 2[Error Code] ERR204[Error Desc] Send cXML to ASN Failed (Temporary Error)[Error Message] Unexpected error occurred when sending message to <string> <class> : Unexpected error occurred when sending message to <string>
at <class>(CXMLSender.java:254)
[...]

and

Caused by: java.lang.RuntimeException: Cannot perform operation, certificate has to be signed first
at iaik.x509.X509Certificate.a(Unknown Source)
at iaik.x509.X509Certificate.getEncoded(Unknown Source)
at com.sap.security.core.server.https.SecureConnectionFactory$4.run(SecureConnectionFactory.java:750)
at java.security.AccessController.doPrivileged(Native Method)
[...]

SAP NetWeaver 7.4

certificates, XI, PO, PI, Process Integration, Process Orchestration, ECC, ECDSA, ECDHE, RSA, cipher, SSL, TLS , KBA , BC-XI-CON-AFW-SEC , Security , Problem