diff --git a/CHANGELOG.rst b/CHANGELOG.rst
index 7a65454..0f26be4 100644
--- a/CHANGELOG.rst
+++ b/CHANGELOG.rst
@@ -22,6 +22,15 @@
 * Added :class:`~cryptography.hazmat.primitives.ciphers.modes.ECB` support
   for :class:`~cryptography.hazmat.primitives.ciphers.algorithms.TripleDES` on
   :doc:`/hazmat/backends/commoncrypto` and :doc:`/hazmat/backends/openssl`.
+* Deprecated :class:`~cryptography.hazmat.primitives.asymmetric.rsa.RSAPrivateKey`
+  in favor of backend specific providers of the
+  :class:`~cryptography.hazmat.primitives.interfaces.RSAPrivateKey` interface.
+* Deprecated :class:`~cryptography.hazmat.primitives.asymmetric.rsa.RSAPublicKey`
+  in favor of backend specific providers of the
+  :class:`~cryptography.hazmat.primitives.interfaces.RSAPublicKey` interface.
+* Deprecated ``encrypt_rsa``, ``decrypt_rsa``, ``create_rsa_signature_ctx`` and
+  ``create_rsa_verification_ctx`` on
+  :class:`~cryptography.hazmat.backends.interfaces.RSABackend`.
 
 0.4 - 2014-05-03
 ~~~~~~~~~~~~~~~~
diff --git a/cryptography/hazmat/backends/openssl/backend.py b/cryptography/hazmat/backends/openssl/backend.py
index 0a7a28b..bf97e42 100644
--- a/cryptography/hazmat/backends/openssl/backend.py
+++ b/cryptography/hazmat/backends/openssl/backend.py
@@ -16,6 +16,7 @@
 import collections
 import itertools
 import math
+import warnings
 
 import six
 
@@ -533,6 +534,12 @@
         return ctx
 
     def create_rsa_signature_ctx(self, private_key, padding, algorithm):
+        warnings.warn(
+            "create_rsa_signature_ctx is deprecated and will be removed in a "
+            "future version.",
+            utils.DeprecatedIn05,
+            stacklevel=2
+        )
         rsa_cdata = self._rsa_cdata_from_private_key(private_key)
         rsa_cdata = self._ffi.gc(rsa_cdata, self._lib.RSA_free)
         key = _RSAPrivateKey(self, rsa_cdata)
@@ -540,6 +547,12 @@
 
     def create_rsa_verification_ctx(self, public_key, signature, padding,
                                     algorithm):
+        warnings.warn(
+            "create_rsa_verification_ctx is deprecated and will be removed in "
+            "a future version.",
+            utils.DeprecatedIn05,
+            stacklevel=2
+        )
         rsa_cdata = self._rsa_cdata_from_public_key(public_key)
         rsa_cdata = self._ffi.gc(rsa_cdata, self._lib.RSA_free)
         key = _RSAPublicKey(self, rsa_cdata)
@@ -654,12 +667,24 @@
             return True
 
     def decrypt_rsa(self, private_key, ciphertext, padding):
+        warnings.warn(
+            "decrypt_rsa is deprecated and will be removed in a future "
+            "version.",
+            utils.DeprecatedIn05,
+            stacklevel=2
+        )
         rsa_cdata = self._rsa_cdata_from_private_key(private_key)
         rsa_cdata = self._ffi.gc(rsa_cdata, self._lib.RSA_free)
         key = _RSAPrivateKey(self, rsa_cdata)
         return key.decrypt(ciphertext, padding)
 
     def encrypt_rsa(self, public_key, plaintext, padding):
+        warnings.warn(
+            "encrypt_rsa is deprecated and will be removed in a future "
+            "version.",
+            utils.DeprecatedIn05,
+            stacklevel=2
+        )
         rsa_cdata = self._rsa_cdata_from_public_key(public_key)
         rsa_cdata = self._ffi.gc(rsa_cdata, self._lib.RSA_free)
         key = _RSAPublicKey(self, rsa_cdata)
diff --git a/cryptography/hazmat/bindings/openssl/err.py b/cryptography/hazmat/bindings/openssl/err.py
index f97fd5d..8ed97d0 100644
--- a/cryptography/hazmat/bindings/openssl/err.py
+++ b/cryptography/hazmat/bindings/openssl/err.py
@@ -18,8 +18,6 @@
 """
 
 TYPES = """
-static const long Cryptography_HAS_102_ERROR_CODES;
-static const long Cryptography_HAS_100_ERROR_CODES;
 static const int Cryptography_HAS_REMOVE_THREAD_STATE;
 static const int Cryptography_HAS_098H_ERROR_CODES;
 static const int Cryptography_HAS_098C_CAMELLIA_CODES;
@@ -30,7 +28,6 @@
 };
 typedef struct ERR_string_data_st ERR_STRING_DATA;
 
-
 static const int ERR_LIB_EVP;
 static const int ERR_LIB_PEM;
 static const int ERR_LIB_ASN1;
@@ -223,70 +220,6 @@
 static const int RSA_R_DIGEST_TOO_BIG_FOR_RSA_KEY;
 static const int RSA_R_BLOCK_TYPE_IS_NOT_01;
 static const int RSA_R_BLOCK_TYPE_IS_NOT_02;
-
-static const int X509_V_OK;
-static const int X509_V_ERR_UNABLE_TO_GET_ISSUER_CERT;
-static const int X509_V_ERR_UNABLE_TO_GET_CRL;
-static const int X509_V_ERR_UNABLE_TO_DECRYPT_CERT_SIGNATURE;
-static const int X509_V_ERR_UNABLE_TO_DECRYPT_CRL_SIGNATURE;
-static const int X509_V_ERR_UNABLE_TO_DECODE_ISSUER_PUBLIC_KEY;
-static const int X509_V_ERR_CERT_SIGNATURE_FAILURE;
-static const int X509_V_ERR_CRL_SIGNATURE_FAILURE;
-static const int X509_V_ERR_CERT_NOT_YET_VALID;
-static const int X509_V_ERR_CERT_HAS_EXPIRED;
-static const int X509_V_ERR_CRL_NOT_YET_VALID;
-static const int X509_V_ERR_CRL_HAS_EXPIRED;
-static const int X509_V_ERR_ERROR_IN_CERT_NOT_BEFORE_FIELD;
-static const int X509_V_ERR_ERROR_IN_CERT_NOT_AFTER_FIELD;
-static const int X509_V_ERR_ERROR_IN_CRL_LAST_UPDATE_FIELD;
-static const int X509_V_ERR_ERROR_IN_CRL_NEXT_UPDATE_FIELD;
-static const int X509_V_ERR_OUT_OF_MEM;
-static const int X509_V_ERR_DEPTH_ZERO_SELF_SIGNED_CERT;
-static const int X509_V_ERR_SELF_SIGNED_CERT_IN_CHAIN;
-static const int X509_V_ERR_UNABLE_TO_GET_ISSUER_CERT_LOCALLY;
-static const int X509_V_ERR_UNABLE_TO_VERIFY_LEAF_SIGNATURE;
-static const int X509_V_ERR_CERT_CHAIN_TOO_LONG;
-static const int X509_V_ERR_CERT_REVOKED;
-static const int X509_V_ERR_INVALID_CA;
-static const int X509_V_ERR_PATH_LENGTH_EXCEEDED;
-static const int X509_V_ERR_INVALID_PURPOSE;
-static const int X509_V_ERR_CERT_UNTRUSTED;
-static const int X509_V_ERR_CERT_REJECTED;
-static const int X509_V_ERR_SUBJECT_ISSUER_MISMATCH;
-static const int X509_V_ERR_AKID_SKID_MISMATCH;
-static const int X509_V_ERR_AKID_ISSUER_SERIAL_MISMATCH;
-static const int X509_V_ERR_KEYUSAGE_NO_CERTSIGN;
-static const int X509_V_ERR_UNABLE_TO_GET_CRL_ISSUER;
-static const int X509_V_ERR_UNHANDLED_CRITICAL_EXTENSION;
-static const int X509_V_ERR_KEYUSAGE_NO_CRL_SIGN;
-static const int X509_V_ERR_UNHANDLED_CRITICAL_CRL_EXTENSION;
-static const int X509_V_ERR_INVALID_NON_CA;
-static const int X509_V_ERR_PROXY_PATH_LENGTH_EXCEEDED;
-static const int X509_V_ERR_KEYUSAGE_NO_DIGITAL_SIGNATURE;
-static const int X509_V_ERR_PROXY_CERTIFICATES_NOT_ALLOWED;
-static const int X509_V_ERR_INVALID_EXTENSION;
-static const int X509_V_ERR_INVALID_POLICY_EXTENSION;
-static const int X509_V_ERR_NO_EXPLICIT_POLICY;
-static const int X509_V_ERR_DIFFERENT_CRL_SCOPE;
-static const int X509_V_ERR_UNSUPPORTED_EXTENSION_FEATURE;
-static const int X509_V_ERR_UNNESTED_RESOURCE;
-static const int X509_V_ERR_PERMITTED_VIOLATION;
-static const int X509_V_ERR_EXCLUDED_VIOLATION;
-static const int X509_V_ERR_SUBTREE_MINMAX;
-static const int X509_V_ERR_UNSUPPORTED_CONSTRAINT_TYPE;
-static const int X509_V_ERR_UNSUPPORTED_CONSTRAINT_SYNTAX;
-static const int X509_V_ERR_UNSUPPORTED_NAME_SYNTAX;
-static const int X509_V_ERR_CRL_PATH_VALIDATION_ERROR;
-static const int X509_V_ERR_SUITE_B_INVALID_VERSION;
-static const int X509_V_ERR_SUITE_B_INVALID_ALGORITHM;
-static const int X509_V_ERR_SUITE_B_INVALID_CURVE;
-static const int X509_V_ERR_SUITE_B_INVALID_SIGNATURE_ALGORITHM;
-static const int X509_V_ERR_SUITE_B_LOS_NOT_ALLOWED;
-static const int X509_V_ERR_SUITE_B_CANNOT_SIGN_P_384_WITH_P_256;
-static const int X509_V_ERR_HOSTNAME_MISMATCH;
-static const int X509_V_ERR_EMAIL_MISMATCH;
-static const int X509_V_ERR_IP_ADDRESS_MISMATCH;
-static const int X509_V_ERR_APPLICATION_VERIFICATION;
 """
 
 FUNCTIONS = """
@@ -343,38 +276,6 @@
 """
 
 CUSTOMIZATIONS = """
-// OpenSSL 1.0.2+
-#if OPENSSL_VERSION_NUMBER >= 0x10002000L
-static const long Cryptography_HAS_102_ERROR_CODES = 1;
-#else
-static const long Cryptography_HAS_102_ERROR_CODES = 0;
-static const long X509_V_ERR_SUITE_B_INVALID_VERSION = 0;
-static const long X509_V_ERR_SUITE_B_INVALID_ALGORITHM = 0;
-static const long X509_V_ERR_SUITE_B_INVALID_CURVE = 0;
-static const long X509_V_ERR_SUITE_B_INVALID_SIGNATURE_ALGORITHM = 0;
-static const long X509_V_ERR_SUITE_B_LOS_NOT_ALLOWED = 0;
-static const long X509_V_ERR_SUITE_B_CANNOT_SIGN_P_384_WITH_P_256 = 0;
-static const long X509_V_ERR_HOSTNAME_MISMATCH = 0;
-static const long X509_V_ERR_EMAIL_MISMATCH = 0;
-static const long X509_V_ERR_IP_ADDRESS_MISMATCH = 0;
-#endif
-
-// OpenSSL 1.0.0+
-#if OPENSSL_VERSION_NUMBER >= 0x10000000L
-static const long Cryptography_HAS_100_ERROR_CODES = 1;
-#else
-static const long Cryptography_HAS_100_ERROR_CODES = 0;
-static const long X509_V_ERR_DIFFERENT_CRL_SCOPE = 0;
-static const long X509_V_ERR_UNSUPPORTED_EXTENSION_FEATURE = 0;
-static const long X509_V_ERR_PERMITTED_VIOLATION = 0;
-static const long X509_V_ERR_EXCLUDED_VIOLATION = 0;
-static const long X509_V_ERR_SUBTREE_MINMAX = 0;
-static const long X509_V_ERR_UNSUPPORTED_CONSTRAINT_TYPE = 0;
-static const long X509_V_ERR_UNSUPPORTED_CONSTRAINT_SYNTAX = 0;
-static const long X509_V_ERR_UNSUPPORTED_NAME_SYNTAX = 0;
-static const long X509_V_ERR_CRL_PATH_VALIDATION_ERROR = 0;
-#endif
-
 #if OPENSSL_VERSION_NUMBER >= 0x10000000L
 static const long Cryptography_HAS_REMOVE_THREAD_STATE = 1;
 #else
@@ -405,33 +306,9 @@
 static const int EVP_F_CAMELLIA_INIT_KEY = 0;
 static const int EVP_R_CAMELLIA_KEY_SETUP_FAILED = 0;
 #endif
-
 """
 
 CONDITIONAL_NAMES = {
-    "Cryptography_HAS_102_ERROR_CODES": [
-        'X509_V_ERR_SUITE_B_INVALID_VERSION',
-        'X509_V_ERR_SUITE_B_INVALID_ALGORITHM',
-        'X509_V_ERR_SUITE_B_INVALID_CURVE',
-        'X509_V_ERR_SUITE_B_INVALID_SIGNATURE_ALGORITHM',
-        'X509_V_ERR_SUITE_B_LOS_NOT_ALLOWED',
-        'X509_V_ERR_SUITE_B_CANNOT_SIGN_P_384_WITH_P_256',
-        'X509_V_ERR_HOSTNAME_MISMATCH',
-        'X509_V_ERR_EMAIL_MISMATCH',
-        'X509_V_ERR_IP_ADDRESS_MISMATCH'
-    ],
-    "Cryptography_HAS_100_ERROR_CODES": [
-        'X509_V_ERR_DIFFERENT_CRL_SCOPE',
-        'X509_V_ERR_UNSUPPORTED_EXTENSION_FEATURE',
-        'X509_V_ERR_UNNESTED_RESOURCE',
-        'X509_V_ERR_PERMITTED_VIOLATION',
-        'X509_V_ERR_EXCLUDED_VIOLATION',
-        'X509_V_ERR_SUBTREE_MINMAX',
-        'X509_V_ERR_UNSUPPORTED_CONSTRAINT_TYPE',
-        'X509_V_ERR_UNSUPPORTED_CONSTRAINT_SYNTAX',
-        'X509_V_ERR_UNSUPPORTED_NAME_SYNTAX',
-        'X509_V_ERR_CRL_PATH_VALIDATION_ERROR',
-    ],
     "Cryptography_HAS_REMOVE_THREAD_STATE": [
         "ERR_remove_thread_state"
     ],
diff --git a/cryptography/hazmat/bindings/openssl/ssl.py b/cryptography/hazmat/bindings/openssl/ssl.py
index 79f13b6..018a141 100644
--- a/cryptography/hazmat/bindings/openssl/ssl.py
+++ b/cryptography/hazmat/bindings/openssl/ssl.py
@@ -127,7 +127,6 @@
 static const long SSL_MODE_ACCEPT_MOVING_WRITE_BUFFER;
 static const long SSL_MODE_AUTO_RETRY;
 static const long SSL3_RANDOM_SIZE;
-typedef ... X509_STORE_CTX;
 typedef ... SSL_METHOD;
 typedef struct ssl_st {
     int version;
@@ -226,16 +225,6 @@
 
 void SSL_CTX_set_client_CA_list(SSL_CTX *, Cryptography_STACK_OF_X509_NAME *);
 
-
-/*  X509_STORE_CTX */
-int X509_STORE_CTX_get_error(X509_STORE_CTX *);
-void X509_STORE_CTX_set_error(X509_STORE_CTX *, int);
-int X509_STORE_CTX_get_error_depth(X509_STORE_CTX *);
-X509 *X509_STORE_CTX_get_current_cert(X509_STORE_CTX *);
-int X509_STORE_CTX_set_ex_data(X509_STORE_CTX *, int, void *);
-void *X509_STORE_CTX_get_ex_data(X509_STORE_CTX *, int);
-
-
 /*  SSL_SESSION */
 void SSL_SESSION_free(SSL_SESSION *);
 
diff --git a/cryptography/hazmat/bindings/openssl/x509.py b/cryptography/hazmat/bindings/openssl/x509.py
index c0be306..3785cc6 100644
--- a/cryptography/hazmat/bindings/openssl/x509.py
+++ b/cryptography/hazmat/bindings/openssl/x509.py
@@ -76,7 +76,6 @@
     ...;
 } X509;
 
-typedef ... X509_STORE;
 typedef ... NETSCAPE_SPKI;
 """
 
@@ -166,12 +165,6 @@
 ASN1_INTEGER *X509_get_serialNumber(X509 *);
 int X509_set_serialNumber(X509 *, ASN1_INTEGER *);
 
-/*  X509_STORE */
-X509_STORE *X509_STORE_new(void);
-void X509_STORE_free(X509_STORE *);
-int X509_STORE_add_cert(X509_STORE *, X509 *);
-int X509_verify_cert(X509_STORE_CTX *);
-
 const char *X509_verify_cert_error_string(long);
 
 const char *X509_get_default_cert_area(void);
diff --git a/cryptography/hazmat/bindings/openssl/x509_vfy.py b/cryptography/hazmat/bindings/openssl/x509_vfy.py
index a5dcb6a..031a522 100644
--- a/cryptography/hazmat/bindings/openssl/x509_vfy.py
+++ b/cryptography/hazmat/bindings/openssl/x509_vfy.py
@@ -28,17 +28,89 @@
 
 TYPES = """
 static const long Cryptography_HAS_X509_VERIFY_PARAM_SET_HOSTFLAGS;
+static const long Cryptography_HAS_102_VERIFICATION_ERROR_CODES;
 static const long Cryptography_HAS_102_VERIFICATION_PARAMS;
 static const long Cryptography_HAS_X509_V_FLAG_TRUSTED_FIRST;
+static const long Cryptography_HAS_100_VERIFICATION_ERROR_CODES;
 static const long Cryptography_HAS_100_VERIFICATION_PARAMS;
 static const long Cryptography_HAS_X509_V_FLAG_CHECK_SS_SIGNATURE;
 
 typedef ... Cryptography_STACK_OF_ASN1_OBJECT;
+
+typedef ... X509_STORE;
+typedef ... X509_STORE_CTX;
 typedef ... X509_VERIFY_PARAM;
 
 /* While these are defined in the source as ints, they're tagged here
    as longs, just in case they ever grow to large, such as what we saw
    with OP_ALL. */
+
+// Verification error codes
+static const int X509_V_OK;
+static const int X509_V_ERR_UNABLE_TO_GET_ISSUER_CERT;
+static const int X509_V_ERR_UNABLE_TO_GET_CRL;
+static const int X509_V_ERR_UNABLE_TO_DECRYPT_CERT_SIGNATURE;
+static const int X509_V_ERR_UNABLE_TO_DECRYPT_CRL_SIGNATURE;
+static const int X509_V_ERR_UNABLE_TO_DECODE_ISSUER_PUBLIC_KEY;
+static const int X509_V_ERR_CERT_SIGNATURE_FAILURE;
+static const int X509_V_ERR_CRL_SIGNATURE_FAILURE;
+static const int X509_V_ERR_CERT_NOT_YET_VALID;
+static const int X509_V_ERR_CERT_HAS_EXPIRED;
+static const int X509_V_ERR_CRL_NOT_YET_VALID;
+static const int X509_V_ERR_CRL_HAS_EXPIRED;
+static const int X509_V_ERR_ERROR_IN_CERT_NOT_BEFORE_FIELD;
+static const int X509_V_ERR_ERROR_IN_CERT_NOT_AFTER_FIELD;
+static const int X509_V_ERR_ERROR_IN_CRL_LAST_UPDATE_FIELD;
+static const int X509_V_ERR_ERROR_IN_CRL_NEXT_UPDATE_FIELD;
+static const int X509_V_ERR_OUT_OF_MEM;
+static const int X509_V_ERR_DEPTH_ZERO_SELF_SIGNED_CERT;
+static const int X509_V_ERR_SELF_SIGNED_CERT_IN_CHAIN;
+static const int X509_V_ERR_UNABLE_TO_GET_ISSUER_CERT_LOCALLY;
+static const int X509_V_ERR_UNABLE_TO_VERIFY_LEAF_SIGNATURE;
+static const int X509_V_ERR_CERT_CHAIN_TOO_LONG;
+static const int X509_V_ERR_CERT_REVOKED;
+static const int X509_V_ERR_INVALID_CA;
+static const int X509_V_ERR_PATH_LENGTH_EXCEEDED;
+static const int X509_V_ERR_INVALID_PURPOSE;
+static const int X509_V_ERR_CERT_UNTRUSTED;
+static const int X509_V_ERR_CERT_REJECTED;
+static const int X509_V_ERR_SUBJECT_ISSUER_MISMATCH;
+static const int X509_V_ERR_AKID_SKID_MISMATCH;
+static const int X509_V_ERR_AKID_ISSUER_SERIAL_MISMATCH;
+static const int X509_V_ERR_KEYUSAGE_NO_CERTSIGN;
+static const int X509_V_ERR_UNABLE_TO_GET_CRL_ISSUER;
+static const int X509_V_ERR_UNHANDLED_CRITICAL_EXTENSION;
+static const int X509_V_ERR_KEYUSAGE_NO_CRL_SIGN;
+static const int X509_V_ERR_UNHANDLED_CRITICAL_CRL_EXTENSION;
+static const int X509_V_ERR_INVALID_NON_CA;
+static const int X509_V_ERR_PROXY_PATH_LENGTH_EXCEEDED;
+static const int X509_V_ERR_KEYUSAGE_NO_DIGITAL_SIGNATURE;
+static const int X509_V_ERR_PROXY_CERTIFICATES_NOT_ALLOWED;
+static const int X509_V_ERR_INVALID_EXTENSION;
+static const int X509_V_ERR_INVALID_POLICY_EXTENSION;
+static const int X509_V_ERR_NO_EXPLICIT_POLICY;
+static const int X509_V_ERR_DIFFERENT_CRL_SCOPE;
+static const int X509_V_ERR_UNSUPPORTED_EXTENSION_FEATURE;
+static const int X509_V_ERR_UNNESTED_RESOURCE;
+static const int X509_V_ERR_PERMITTED_VIOLATION;
+static const int X509_V_ERR_EXCLUDED_VIOLATION;
+static const int X509_V_ERR_SUBTREE_MINMAX;
+static const int X509_V_ERR_UNSUPPORTED_CONSTRAINT_TYPE;
+static const int X509_V_ERR_UNSUPPORTED_CONSTRAINT_SYNTAX;
+static const int X509_V_ERR_UNSUPPORTED_NAME_SYNTAX;
+static const int X509_V_ERR_CRL_PATH_VALIDATION_ERROR;
+static const int X509_V_ERR_SUITE_B_INVALID_VERSION;
+static const int X509_V_ERR_SUITE_B_INVALID_ALGORITHM;
+static const int X509_V_ERR_SUITE_B_INVALID_CURVE;
+static const int X509_V_ERR_SUITE_B_INVALID_SIGNATURE_ALGORITHM;
+static const int X509_V_ERR_SUITE_B_LOS_NOT_ALLOWED;
+static const int X509_V_ERR_SUITE_B_CANNOT_SIGN_P_384_WITH_P_256;
+static const int X509_V_ERR_HOSTNAME_MISMATCH;
+static const int X509_V_ERR_EMAIL_MISMATCH;
+static const int X509_V_ERR_IP_ADDRESS_MISMATCH;
+static const int X509_V_ERR_APPLICATION_VERIFICATION;
+
+// Verification parameters
 static const long X509_V_FLAG_CB_ISSUER_CHECK;
 static const long X509_V_FLAG_USE_CHECK_TIME;
 static const long X509_V_FLAG_CRL_CHECK;
@@ -62,6 +134,22 @@
 """
 
 FUNCTIONS = """
+int X509_verify_cert(X509_STORE_CTX *);
+
+// X509_STORE
+X509_STORE *X509_STORE_new(void);
+void X509_STORE_free(X509_STORE *);
+int X509_STORE_add_cert(X509_STORE *, X509 *);
+
+// X509_STORE_CTX
+int X509_STORE_CTX_get_error(X509_STORE_CTX *);
+void X509_STORE_CTX_set_error(X509_STORE_CTX *, int);
+int X509_STORE_CTX_get_error_depth(X509_STORE_CTX *);
+X509 *X509_STORE_CTX_get_current_cert(X509_STORE_CTX *);
+int X509_STORE_CTX_set_ex_data(X509_STORE_CTX *, int, void *);
+void *X509_STORE_CTX_get_ex_data(X509_STORE_CTX *, int);
+
+// X509_VERIFY_PARAM
 X509_VERIFY_PARAM *X509_VERIFY_PARAM_new(void);
 int X509_VERIFY_PARAM_set_flags(X509_VERIFY_PARAM *, unsigned long);
 int X509_VERIFY_PARAM_clear_flags(X509_VERIFY_PARAM *, unsigned long);
@@ -97,7 +185,23 @@
                                         unsigned int) = NULL;
 #endif
 
-// OpenSSL 1.0.2+
+// OpenSSL 1.0.2+ verification error codes
+#if OPENSSL_VERSION_NUMBER >= 0x10002000L
+static const long Cryptography_HAS_102_VERIFICATION_ERROR_CODES = 1;
+#else
+static const long Cryptography_HAS_102_VERIFICATION_ERROR_CODES = 0;
+static const long X509_V_ERR_SUITE_B_INVALID_VERSION = 0;
+static const long X509_V_ERR_SUITE_B_INVALID_ALGORITHM = 0;
+static const long X509_V_ERR_SUITE_B_INVALID_CURVE = 0;
+static const long X509_V_ERR_SUITE_B_INVALID_SIGNATURE_ALGORITHM = 0;
+static const long X509_V_ERR_SUITE_B_LOS_NOT_ALLOWED = 0;
+static const long X509_V_ERR_SUITE_B_CANNOT_SIGN_P_384_WITH_P_256 = 0;
+static const long X509_V_ERR_HOSTNAME_MISMATCH = 0;
+static const long X509_V_ERR_EMAIL_MISMATCH = 0;
+static const long X509_V_ERR_IP_ADDRESS_MISMATCH = 0;
+#endif
+
+// OpenSSL 1.0.2+ verification parameters
 #if OPENSSL_VERSION_NUMBER >= 0x10002000L
 static const long Cryptography_HAS_102_VERIFICATION_PARAMS = 1;
 #else
@@ -125,7 +229,23 @@
 static const long X509_V_FLAG_TRUSTED_FIRST = 0;
 #endif
 
-// OpenSSL 1.0.0+
+// OpenSSL 1.0.0+ verification error codes
+#if OPENSSL_VERSION_NUMBER >= 0x10000000L
+static const long Cryptography_HAS_100_VERIFICATION_ERROR_CODES = 1;
+#else
+static const long Cryptography_HAS_100_VERIFICATION_ERROR_CODES = 0;
+static const long X509_V_ERR_DIFFERENT_CRL_SCOPE = 0;
+static const long X509_V_ERR_UNSUPPORTED_EXTENSION_FEATURE = 0;
+static const long X509_V_ERR_PERMITTED_VIOLATION = 0;
+static const long X509_V_ERR_EXCLUDED_VIOLATION = 0;
+static const long X509_V_ERR_SUBTREE_MINMAX = 0;
+static const long X509_V_ERR_UNSUPPORTED_CONSTRAINT_TYPE = 0;
+static const long X509_V_ERR_UNSUPPORTED_CONSTRAINT_SYNTAX = 0;
+static const long X509_V_ERR_UNSUPPORTED_NAME_SYNTAX = 0;
+static const long X509_V_ERR_CRL_PATH_VALIDATION_ERROR = 0;
+#endif
+
+// OpenSSL 1.0.0+ verification parameters
 #if OPENSSL_VERSION_NUMBER >= 0x10000000L
 static const long Cryptography_HAS_100_VERIFICATION_PARAMS = 1;
 #else
@@ -147,6 +267,17 @@
     "Cryptography_HAS_X509_VERIFY_PARAM_SET_HOSTFLAGS": [
         "X509_VERIFY_PARAM_set_hostflags",
     ],
+    "Cryptography_HAS_102_VERIFICATION_ERROR_CODES": [
+        'X509_V_ERR_SUITE_B_INVALID_VERSION',
+        'X509_V_ERR_SUITE_B_INVALID_ALGORITHM',
+        'X509_V_ERR_SUITE_B_INVALID_CURVE',
+        'X509_V_ERR_SUITE_B_INVALID_SIGNATURE_ALGORITHM',
+        'X509_V_ERR_SUITE_B_LOS_NOT_ALLOWED',
+        'X509_V_ERR_SUITE_B_CANNOT_SIGN_P_384_WITH_P_256',
+        'X509_V_ERR_HOSTNAME_MISMATCH',
+        'X509_V_ERR_EMAIL_MISMATCH',
+        'X509_V_ERR_IP_ADDRESS_MISMATCH'
+    ],
     "Cryptography_HAS_102_VERIFICATION_PARAMS": [
         "X509_V_FLAG_SUITEB_128_LOS_ONLY",
         "X509_V_FLAG_SUITEB_192_LOS",
@@ -161,6 +292,18 @@
     "Cryptography_HAS_X509_V_FLAG_TRUSTED_FIRST": [
         "X509_V_FLAG_TRUSTED_FIRST",
     ],
+    "Cryptography_HAS_100_VERIFICATION_ERROR_CODES": [
+        'X509_V_ERR_DIFFERENT_CRL_SCOPE',
+        'X509_V_ERR_UNSUPPORTED_EXTENSION_FEATURE',
+        'X509_V_ERR_UNNESTED_RESOURCE',
+        'X509_V_ERR_PERMITTED_VIOLATION',
+        'X509_V_ERR_EXCLUDED_VIOLATION',
+        'X509_V_ERR_SUBTREE_MINMAX',
+        'X509_V_ERR_UNSUPPORTED_CONSTRAINT_TYPE',
+        'X509_V_ERR_UNSUPPORTED_CONSTRAINT_SYNTAX',
+        'X509_V_ERR_UNSUPPORTED_NAME_SYNTAX',
+        'X509_V_ERR_CRL_PATH_VALIDATION_ERROR',
+    ],
     "Cryptography_HAS_100_VERIFICATION_PARAMS": [
         "Cryptography_HAS_100_VERIFICATION_PARAMS",
         "X509_V_FLAG_EXTENDED_CRL_SUPPORT",
diff --git a/cryptography/hazmat/primitives/asymmetric/rsa.py b/cryptography/hazmat/primitives/asymmetric/rsa.py
index 18ca0db..fc117cd 100644
--- a/cryptography/hazmat/primitives/asymmetric/rsa.py
+++ b/cryptography/hazmat/primitives/asymmetric/rsa.py
@@ -13,12 +13,13 @@
 
 from __future__ import absolute_import, division, print_function
 
+import warnings
+
 import six
 
 from cryptography import utils
 from cryptography.exceptions import UnsupportedAlgorithm, _Reasons
 from cryptography.hazmat.backends.interfaces import RSABackend
-from cryptography.hazmat.primitives import interfaces
 
 
 def generate_private_key(public_exponent, key_size, backend):
@@ -93,9 +94,14 @@
         raise ValueError("e must be odd.")
 
 
-@utils.register_interface(interfaces.RSAPublicKey)
 class RSAPublicKey(object):
     def __init__(self, public_exponent, modulus):
+        warnings.warn(
+            "The RSAPublicKey class is deprecated and will be removed in a "
+            "future version.",
+            utils.DeprecatedIn05,
+            stacklevel=2
+        )
         if (
             not isinstance(public_exponent, six.integer_types) or
             not isinstance(modulus, six.integer_types)
@@ -183,10 +189,15 @@
     return private_exponent % (q - 1)
 
 
-@utils.register_interface(interfaces.RSAPrivateKey)
 class RSAPrivateKey(object):
     def __init__(self, p, q, private_exponent, dmp1, dmq1, iqmp,
                  public_exponent, modulus):
+        warnings.warn(
+            "The RSAPrivateKey class is deprecated and will be removed in a "
+            "future version.",
+            utils.DeprecatedIn05,
+            stacklevel=2
+        )
         if (
             not isinstance(p, six.integer_types) or
             not isinstance(q, six.integer_types) or
@@ -213,6 +224,11 @@
 
     @classmethod
     def generate(cls, public_exponent, key_size, backend):
+        warnings.warn(
+            "generate is deprecated and will be removed in a future version.",
+            utils.DeprecatedIn05,
+            stacklevel=2
+        )
         if not isinstance(backend, RSABackend):
             raise UnsupportedAlgorithm(
                 "Backend object does not implement RSABackend.",
diff --git a/cryptography/hazmat/primitives/interfaces.py b/cryptography/hazmat/primitives/interfaces.py
index 33af438..7185256 100644
--- a/cryptography/hazmat/primitives/interfaces.py
+++ b/cryptography/hazmat/primitives/interfaces.py
@@ -186,7 +186,7 @@
 @six.add_metaclass(abc.ABCMeta)
 class RSAPrivateKey(object):
     @abc.abstractmethod
-    def signer(self, padding, algorithm, backend):
+    def signer(self, padding, algorithm):
         """
         Returns an AsymmetricSignatureContext used for signing data.
         """
@@ -221,7 +221,7 @@
 @six.add_metaclass(abc.ABCMeta)
 class RSAPublicKey(object):
     @abc.abstractmethod
-    def verifier(self, signature, padding, algorithm, backend):
+    def verifier(self, signature, padding, algorithm):
         """
         Returns an AsymmetricVerificationContext used for verifying signatures.
         """
diff --git a/cryptography/utils.py b/cryptography/utils.py
index 484eec9..1db1615 100644
--- a/cryptography/utils.py
+++ b/cryptography/utils.py
@@ -17,6 +17,7 @@
 
 
 DeprecatedIn04 = DeprecationWarning
+DeprecatedIn05 = PendingDeprecationWarning
 
 
 def register_interface(iface):
diff --git a/docs/hazmat/backends/interfaces.rst b/docs/hazmat/backends/interfaces.rst
index 1a2603b..a18a3d5 100644
--- a/docs/hazmat/backends/interfaces.rst
+++ b/docs/hazmat/backends/interfaces.rst
@@ -215,6 +215,8 @@
 
     .. method:: create_rsa_signature_ctx(private_key, padding, algorithm)
 
+        .. deprecated:: 0.5
+
         :param private_key: An instance of an
             :class:`~cryptography.hazmat.primitives.interfaces.RSAPrivateKey`
             provider.
@@ -232,6 +234,8 @@
 
     .. method:: create_rsa_verification_ctx(public_key, signature, padding, algorithm)
 
+        .. deprecated:: 0.5
+
         :param public_key: An instance of a
             :class:`~cryptography.hazmat.primitives.interfaces.RSAPublicKey`
             provider.
@@ -285,6 +289,8 @@
 
     .. method:: decrypt_rsa(private_key, ciphertext, padding)
 
+        .. deprecated:: 0.5
+
         :param private_key: An instance of an
             :class:`~cryptography.hazmat.primitives.interfaces.RSAPrivateKey`
             provider.
@@ -305,6 +311,8 @@
 
     .. method:: encrypt_rsa(public_key, plaintext, padding)
 
+        .. deprecated:: 0.5
+
         :param public_key: An instance of an
             :class:`~cryptography.hazmat.primitives.interfaces.RSAPublicKey`
             provider.
diff --git a/docs/hazmat/primitives/interfaces.rst b/docs/hazmat/primitives/interfaces.rst
index 8e6c254..029c4c1 100644
--- a/docs/hazmat/primitives/interfaces.rst
+++ b/docs/hazmat/primitives/interfaces.rst
@@ -112,7 +112,7 @@
 
     An `RSA`_ private key.
 
-    .. method:: signer(padding, algorithm, backend)
+    .. method:: signer(padding, algorithm)
 
         .. versionadded:: 0.3
 
@@ -126,14 +126,10 @@
             :class:`~cryptography.hazmat.primitives.interfaces.HashAlgorithm`
             provider.
 
-        :param backend: A
-            :class:`~cryptography.hazmat.backends.interfaces.RSABackend`
-            provider.
-
         :returns:
             :class:`~cryptography.hazmat.primitives.interfaces.AsymmetricSignatureContext`
 
-    .. method:: decrypt(ciphertext, padding, backend)
+    .. method:: decrypt(ciphertext, padding)
 
         .. versionadded:: 0.4
 
@@ -145,10 +141,6 @@
             :class:`~cryptography.hazmat.primitives.interfaces.AsymmetricPadding`
             provider.
 
-        :param backend: A
-            :class:`~cryptography.hazmat.backends.interfaces.RSABackend`
-            provider.
-
         :return bytes: Decrypted data.
 
     .. method:: public_key()
@@ -186,7 +178,7 @@
 
     An `RSA`_ public key.
 
-    .. method:: verifier(signature, padding, algorithm, backend)
+    .. method:: verifier(signature, padding, algorithm)
 
         .. versionadded:: 0.3
 
@@ -203,14 +195,10 @@
             :class:`~cryptography.hazmat.primitives.interfaces.HashAlgorithm`
             provider.
 
-        :param backend: A
-            :class:`~cryptography.hazmat.backends.interfaces.RSABackend`
-            provider.
-
         :returns:
             :class:`~cryptography.hazmat.primitives.interfaces.AsymmetricVerificationContext`
 
-    .. method:: encrypt(plaintext, padding, backend)
+    .. method:: encrypt(plaintext, padding)
 
         .. versionadded:: 0.4
 
@@ -222,10 +210,6 @@
             :class:`~cryptography.hazmat.primitives.interfaces.AsymmetricPadding`
             provider.
 
-        :param backend: A
-            :class:`~cryptography.hazmat.backends.interfaces.RSABackend`
-            provider.
-
         :return bytes: Encrypted data.
 
     .. attribute:: key_size
diff --git a/tests/hazmat/backends/test_openssl.py b/tests/hazmat/backends/test_openssl.py
index 75369ef..f9e692b 100644
--- a/tests/hazmat/backends/test_openssl.py
+++ b/tests/hazmat/backends/test_openssl.py
@@ -488,3 +488,41 @@
         monkeypatch.setattr(backend._lib, "Cryptography_HAS_EC", 0)
 
         assert backend._supported_curves() == []
+
+
+class TestDeprecatedRSABackendMethods(object):
+    def test_create_rsa_signature_ctx(self):
+        private_key = rsa.RSAPrivateKey.generate(65537, 512, backend)
+        pytest.deprecated_call(
+            backend.create_rsa_signature_ctx,
+            private_key,
+            padding.PKCS1v15(),
+            hashes.SHA1()
+        )
+
+    def test_create_rsa_verification_ctx(self):
+        private_key = rsa.RSAPrivateKey.generate(65537, 512, backend)
+        public_key = private_key.public_key()
+        pytest.deprecated_call(
+            backend.create_rsa_verification_ctx,
+            public_key,
+            b"\x00" * 64,
+            padding.PKCS1v15(),
+            hashes.SHA1()
+        )
+
+    def test_encrypt_decrypt_rsa(self):
+        private_key = rsa.RSAPrivateKey.generate(65537, 512, backend)
+        public_key = private_key.public_key()
+        ct = pytest.deprecated_call(
+            backend.encrypt_rsa,
+            public_key,
+            b"\x00" * 32,
+            padding.PKCS1v15()
+        )
+        pytest.deprecated_call(
+            backend.decrypt_rsa,
+            private_key,
+            ct,
+            padding.PKCS1v15()
+        )
diff --git a/tests/hazmat/primitives/test_rsa.py b/tests/hazmat/primitives/test_rsa.py
index ffaaf58..5c5422e 100644
--- a/tests/hazmat/primitives/test_rsa.py
+++ b/tests/hazmat/primitives/test_rsa.py
@@ -104,7 +104,12 @@
             _check_rsa_private_numbers(skey.private_numbers())
 
     def test_generate_rsa_key_class_method(self, backend):
-        skey = rsa.RSAPrivateKey.generate(65537, 512, backend)
+        skey = pytest.deprecated_call(
+            rsa.RSAPrivateKey.generate,
+            65537,
+            512,
+            backend
+        )
         assert skey.key_size == 512
         assert skey.public_exponent == 65537
 
@@ -169,11 +174,21 @@
 
     def test_invalid_private_key_argument_types(self):
         with pytest.raises(TypeError):
-            rsa.RSAPrivateKey(None, None, None, None, None, None, None, None)
+            pytest.deprecated_call(
+                rsa.RSAPrivateKey,
+                None,
+                None,
+                None,
+                None,
+                None,
+                None,
+                None,
+                None
+            )
 
     def test_invalid_public_key_argument_types(self):
         with pytest.raises(TypeError):
-            rsa.RSAPublicKey(None, None)
+            pytest.deprecated_call(rsa.RSAPublicKey, None, None)
 
     def test_invalid_private_key_argument_values(self):
         # Start with p=3, q=11, private_exponent=3, public_exponent=7,
@@ -182,7 +197,8 @@
 
         # Test a modulus < 3.
         with pytest.raises(ValueError):
-            rsa.RSAPrivateKey(
+            pytest.deprecated_call(
+                rsa.RSAPrivateKey,
                 p=3,
                 q=11,
                 private_exponent=3,
@@ -195,7 +211,8 @@
 
         # Test a modulus != p * q.
         with pytest.raises(ValueError):
-            rsa.RSAPrivateKey(
+            pytest.deprecated_call(
+                rsa.RSAPrivateKey,
                 p=3,
                 q=11,
                 private_exponent=3,
@@ -208,7 +225,8 @@
 
         # Test a p > modulus.
         with pytest.raises(ValueError):
-            rsa.RSAPrivateKey(
+            pytest.deprecated_call(
+                rsa.RSAPrivateKey,
                 p=37,
                 q=11,
                 private_exponent=3,
@@ -221,7 +239,8 @@
 
         # Test a q > modulus.
         with pytest.raises(ValueError):
-            rsa.RSAPrivateKey(
+            pytest.deprecated_call(
+                rsa.RSAPrivateKey,
                 p=3,
                 q=37,
                 private_exponent=3,
@@ -234,7 +253,8 @@
 
         # Test a dmp1 > modulus.
         with pytest.raises(ValueError):
-            rsa.RSAPrivateKey(
+            pytest.deprecated_call(
+                rsa.RSAPrivateKey,
                 p=3,
                 q=11,
                 private_exponent=3,
@@ -247,7 +267,8 @@
 
         # Test a dmq1 > modulus.
         with pytest.raises(ValueError):
-            rsa.RSAPrivateKey(
+            pytest.deprecated_call(
+                rsa.RSAPrivateKey,
                 p=3,
                 q=11,
                 private_exponent=3,
@@ -260,7 +281,8 @@
 
         # Test an iqmp > modulus.
         with pytest.raises(ValueError):
-            rsa.RSAPrivateKey(
+            pytest.deprecated_call(
+                rsa.RSAPrivateKey,
                 p=3,
                 q=11,
                 private_exponent=3,
@@ -273,7 +295,8 @@
 
         # Test a private_exponent > modulus
         with pytest.raises(ValueError):
-            rsa.RSAPrivateKey(
+            pytest.deprecated_call(
+                rsa.RSAPrivateKey,
                 p=3,
                 q=11,
                 private_exponent=37,
@@ -286,7 +309,8 @@
 
         # Test a public_exponent < 3
         with pytest.raises(ValueError):
-            rsa.RSAPrivateKey(
+            pytest.deprecated_call(
+                rsa.RSAPrivateKey,
                 p=3,
                 q=11,
                 private_exponent=3,
@@ -299,7 +323,8 @@
 
         # Test a public_exponent > modulus
         with pytest.raises(ValueError):
-            rsa.RSAPrivateKey(
+            pytest.deprecated_call(
+                rsa.RSAPrivateKey,
                 p=3,
                 q=11,
                 private_exponent=3,
@@ -312,7 +337,8 @@
 
         # Test a public_exponent that is not odd.
         with pytest.raises(ValueError):
-            rsa.RSAPrivateKey(
+            pytest.deprecated_call(
+                rsa.RSAPrivateKey,
                 p=3,
                 q=11,
                 private_exponent=3,
@@ -325,7 +351,8 @@
 
         # Test a dmp1 that is not odd.
         with pytest.raises(ValueError):
-            rsa.RSAPrivateKey(
+            pytest.deprecated_call(
+                rsa.RSAPrivateKey,
                 p=3,
                 q=11,
                 private_exponent=3,
@@ -338,7 +365,8 @@
 
         # Test a dmq1 that is not odd.
         with pytest.raises(ValueError):
-            rsa.RSAPrivateKey(
+            pytest.deprecated_call(
+                rsa.RSAPrivateKey,
                 p=3,
                 q=11,
                 private_exponent=3,
@@ -355,19 +383,27 @@
 
         # Test a modulus < 3.
         with pytest.raises(ValueError):
-            rsa.RSAPublicKey(public_exponent=7, modulus=2)
+            pytest.deprecated_call(
+                rsa.RSAPublicKey, public_exponent=7, modulus=2
+            )
 
         # Test a public_exponent < 3
         with pytest.raises(ValueError):
-            rsa.RSAPublicKey(public_exponent=1, modulus=15)
+            pytest.deprecated_call(
+                rsa.RSAPublicKey, public_exponent=1, modulus=15
+            )
 
         # Test a public_exponent > modulus
         with pytest.raises(ValueError):
-            rsa.RSAPublicKey(public_exponent=17, modulus=15)
+            pytest.deprecated_call(
+                rsa.RSAPublicKey, public_exponent=17, modulus=15
+            )
 
         # Test a public_exponent that is not odd.
         with pytest.raises(ValueError):
-            rsa.RSAPublicKey(public_exponent=6, modulus=15)
+            pytest.deprecated_call(
+                rsa.RSAPublicKey, public_exponent=6, modulus=15
+            )
 
 
 def test_rsa_generate_invalid_backend():
@@ -377,7 +413,9 @@
         rsa.generate_private_key(65537, 2048, pretend_backend)
 
     with raises_unsupported_algorithm(_Reasons.BACKEND_MISSING_INTERFACE):
-        rsa.RSAPrivateKey.generate(65537, 2048, pretend_backend)
+        pytest.deprecated_call(
+            rsa.RSAPrivateKey.generate, 65537, 2048, pretend_backend
+        )
 
 
 @pytest.mark.rsa
@@ -398,7 +436,8 @@
     )
     def test_pkcs1v15_signing(self, pkcs1_example, backend):
         private, public, example = pkcs1_example
-        private_key = rsa.RSAPrivateKey(
+        private_key = pytest.deprecated_call(
+            rsa.RSAPrivateKey,
             p=private["p"],
             q=private["q"],
             private_exponent=private["private_exponent"],
@@ -432,7 +471,8 @@
     )
     def test_pss_signing(self, pkcs1_example, backend):
         private, public, example = pkcs1_example
-        private_key = rsa.RSAPrivateKey(
+        private_key = pytest.deprecated_call(
+            rsa.RSAPrivateKey,
             p=private["p"],
             q=private["q"],
             private_exponent=private["private_exponent"],
@@ -637,7 +677,8 @@
 
     def test_rsa_signer_invalid_backend(self, backend):
         pretend_backend = object()
-        private_key = rsa.RSAPrivateKey(
+        private_key = pytest.deprecated_call(
+            rsa.RSAPrivateKey,
             p=RSA_KEY_512.p,
             q=RSA_KEY_512.q,
             private_exponent=RSA_KEY_512.d,
@@ -952,7 +993,12 @@
 
     def test_rsa_verifier_invalid_backend(self, backend):
         pretend_backend = object()
-        private_key = rsa.RSAPrivateKey.generate(65537, 2048, backend)
+        private_key = pytest.deprecated_call(
+            rsa.RSAPrivateKey.generate,
+            65537,
+            2048,
+            backend
+        )
         public_key = private_key.public_key()
 
         with raises_unsupported_algorithm(_Reasons.BACKEND_MISSING_INTERFACE):
@@ -1439,7 +1485,9 @@
 
     def test_rsa_decrypt_invalid_backend(self, backend):
         pretend_backend = object()
-        private_key = rsa.RSAPrivateKey.generate(65537, 2048, backend)
+        private_key = pytest.deprecated_call(
+            rsa.RSAPrivateKey.generate, 65537, 2048, backend
+        )
 
         with raises_unsupported_algorithm(_Reasons.BACKEND_MISSING_INTERFACE):
             private_key.decrypt(
@@ -1468,7 +1516,8 @@
     )
     def test_decrypt_oaep_vectors(self, vector, backend):
         private, public, example = vector
-        skey = rsa.RSAPrivateKey(
+        skey = pytest.deprecated_call(
+            rsa.RSAPrivateKey,
             p=private["p"],
             q=private["q"],
             private_exponent=private["private_exponent"],
@@ -1608,7 +1657,9 @@
 
     def test_rsa_encrypt_invalid_backend(self, backend):
         pretend_backend = object()
-        private_key = rsa.RSAPrivateKey.generate(65537, 512, backend)
+        private_key = pytest.deprecated_call(
+            rsa.RSAPrivateKey.generate, 65537, 512, backend
+        )
         public_key = private_key.public_key()
 
         with raises_unsupported_algorithm(_Reasons.BACKEND_MISSING_INTERFACE):