RSA Verification Support

Blocked on #673. After that lands this will be rebased.