Background We were implementing RSA-4096 encryption/decryption in a Java Spark pipeline We generated a key pair, shared the public key with the other team, and they sent back ciphertext encrypted using our public key. The Problem When we tried to decrypt the ciphertext using our private key, we got: Exception in thread "main" javax.crypto.BadPaddingException: Padding error in decryption at java.base/com.sun.crypto.provider.RSACipher.doFinal(RSACipher.java:387) at java.base/com.sun.crypto.provider.RSACipher.engineDoFinal(RSACipher.java:422) at java.base/javax.crypto.Cipher.doFinal(Cipher.java:2205) Initial Suspects We went through the usual checklist: Same key pair — public key shared matches private key we hold Key format — private key correctly converted to PKCS#8 Base64 encoding — ciphertext not corrupted Algorithm — both sides using RSA with OAEP Everything looked correct. Keys were fine. Code looked fine. Yet decryption failed every time. Root Cause Our Java code used t...