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/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 682a36d..54821db 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.
         """
@@ -215,7 +215,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):