If you are using Spongy Castle (which is a repackage of Bouncy Castle for Android), and are coming across a java.lang.NoClassDefFoundError like below on Android 4.x, you should perhaps check if you multi-dex is properly setup.
If you are using multi-dex, go through the documentation, and make sure it is properly setup.
In one app, where I was getting this error, it turned out the <application> tag was missing an attribute:
The error I was getting from Spongy Castle because of incorrect multi-dex setup: