diff --git a/oauth2client/crypt.py b/oauth2client/crypt.py
index 4204417..2d31815 100644
--- a/oauth2client/crypt.py
+++ b/oauth2client/crypt.py
@@ -20,109 +20,240 @@
 import logging
 import time
 
-from OpenSSL import crypto
 from anyjson import simplejson
 
 
-logger = logging.getLogger(__name__)
-
 CLOCK_SKEW_SECS = 300  # 5 minutes in seconds
 AUTH_TOKEN_LIFETIME_SECS = 300  # 5 minutes in seconds
 MAX_TOKEN_LIFETIME_SECS = 86400  # 1 day in seconds
 
 
+logger = logging.getLogger(__name__)
+
+
 class AppIdentityError(Exception):
   pass
 
 
-class Verifier(object):
-  """Verifies the signature on a message."""
-
-  def __init__(self, pubkey):
-    """Constructor.
-
-    Args:
-      pubkey, OpenSSL.crypto.PKey, The public key to verify with.
-    """
-    self._pubkey = pubkey
-
-  def verify(self, message, signature):
-    """Verifies a message against a signature.
-
-    Args:
-      message: string, The message to verify.
-      signature: string, The signature on the message.
-
-    Returns:
-      True if message was singed by the private key associated with the public
-      key that this object was constructed with.
-    """
-    try:
-      crypto.verify(self._pubkey, signature, message, 'sha256')
-      return True
-    except:
-      return False
-
-  @staticmethod
-  def from_string(key_pem, is_x509_cert):
-    """Construct a Verified instance from a string.
-
-    Args:
-      key_pem: string, public key in PEM format.
-      is_x509_cert: bool, True if key_pem is an X509 cert, otherwise it is
-        expected to be an RSA key in PEM format.
-
-    Returns:
-      Verifier instance.
-
-    Raises:
-      OpenSSL.crypto.Error if the key_pem can't be parsed.
-    """
-    if is_x509_cert:
-      pubkey = crypto.load_certificate(crypto.FILETYPE_PEM, key_pem)
-    else:
-      pubkey = crypto.load_privatekey(crypto.FILETYPE_PEM, key_pem)
-    return Verifier(pubkey)
+try:
+  from OpenSSL import crypto
 
 
-class Signer(object):
-  """Signs messages with a private key."""
+  class OpenSSLVerifier(object):
+    """Verifies the signature on a message."""
 
-  def __init__(self, pkey):
-    """Constructor.
+    def __init__(self, pubkey):
+      """Constructor.
 
-    Args:
-      pkey, OpenSSL.crypto.PKey, The private key to sign with.
-    """
-    self._key = pkey
+      Args:
+        pubkey, OpenSSL.crypto.PKey, The public key to verify with.
+      """
+      self._pubkey = pubkey
 
-  def sign(self, message):
-    """Signs a message.
+    def verify(self, message, signature):
+      """Verifies a message against a signature.
 
-    Args:
-      message: string, Message to be signed.
+      Args:
+        message: string, The message to verify.
+        signature: string, The signature on the message.
 
-    Returns:
-      string, The signature of the message for the given key.
-    """
-    return crypto.sign(self._key, message, 'sha256')
+      Returns:
+        True if message was signed by the private key associated with the public
+        key that this object was constructed with.
+      """
+      try:
+        crypto.verify(self._pubkey, signature, message, 'sha256')
+        return True
+      except:
+        return False
 
-  @staticmethod
-  def from_string(key, password='notasecret'):
-    """Construct a Signer instance from a string.
+    @staticmethod
+    def from_string(key_pem, is_x509_cert):
+      """Construct a Verified instance from a string.
 
-    Args:
-      key: string, private key in P12 format.
-      password: string, password for the private key file.
+      Args:
+        key_pem: string, public key in PEM format.
+        is_x509_cert: bool, True if key_pem is an X509 cert, otherwise it is
+          expected to be an RSA key in PEM format.
 
-    Returns:
-      Signer instance.
+      Returns:
+        Verifier instance.
 
-    Raises:
-      OpenSSL.crypto.Error if the key can't be parsed.
-    """
-    pkey = crypto.load_pkcs12(key, password).get_privatekey()
-    return Signer(pkey)
+      Raises:
+        OpenSSL.crypto.Error if the key_pem can't be parsed.
+      """
+      if is_x509_cert:
+        pubkey = crypto.load_certificate(crypto.FILETYPE_PEM, key_pem)
+      else:
+        pubkey = crypto.load_privatekey(crypto.FILETYPE_PEM, key_pem)
+      return OpenSSLVerifier(pubkey)
+
+
+  class OpenSSLSigner(object):
+    """Signs messages with a private key."""
+
+    def __init__(self, pkey):
+      """Constructor.
+
+      Args:
+        pkey, OpenSSL.crypto.PKey (or equiv), The private key to sign with.
+      """
+      self._key = pkey
+
+    def sign(self, message):
+      """Signs a message.
+
+      Args:
+        message: string, Message to be signed.
+
+      Returns:
+        string, The signature of the message for the given key.
+      """
+      return crypto.sign(self._key, message, 'sha256')
+
+    @staticmethod
+    def from_string(key, password='notasecret'):
+      """Construct a Signer instance from a string.
+
+      Args:
+        key: string, private key in PKCS12 or PEM format.
+        password: string, password for the private key file.
+
+      Returns:
+        Signer instance.
+
+      Raises:
+        OpenSSL.crypto.Error if the key can't be parsed.
+      """
+      if key.startswith('-----BEGIN '):
+        pkey = crypto.load_privatekey(crypto.FILETYPE_PEM, key)
+      else:
+        pkey = crypto.load_pkcs12(key, password).get_privatekey()
+      return OpenSSLSigner(pkey)
+
+except ImportError:
+  OpenSSLVerifier = None
+  OpenSSLSigner = None
+
+
+try:
+  from Crypto.PublicKey import RSA
+  from Crypto.Hash import SHA256
+  from Crypto.Signature import PKCS1_v1_5
+
+
+  class PyCryptoVerifier(object):
+    """Verifies the signature on a message."""
+
+    def __init__(self, pubkey):
+      """Constructor.
+
+      Args:
+        pubkey, OpenSSL.crypto.PKey (or equiv), The public key to verify with.
+      """
+      self._pubkey = pubkey
+
+    def verify(self, message, signature):
+      """Verifies a message against a signature.
+
+      Args:
+        message: string, The message to verify.
+        signature: string, The signature on the message.
+
+      Returns:
+        True if message was signed by the private key associated with the public
+        key that this object was constructed with.
+      """
+      try:
+        return PKCS1_v1_5.new(self._pubkey).verify(
+            SHA256.new(message), signature)
+      except:
+        return False
+
+    @staticmethod
+    def from_string(key_pem, is_x509_cert):
+      """Construct a Verified instance from a string.
+
+      Args:
+        key_pem: string, public key in PEM format.
+        is_x509_cert: bool, True if key_pem is an X509 cert, otherwise it is
+          expected to be an RSA key in PEM format.
+
+      Returns:
+        Verifier instance.
+
+      Raises:
+        NotImplementedError if is_x509_cert is true.
+      """
+      if is_x509_cert:
+        raise NotImplementedError(
+            'X509 certs are not supported by the PyCrypto library. '
+            'Try using PyOpenSSL if native code is an option.')
+      else:
+        pubkey = RSA.importKey(key_pem)
+      return PyCryptoVerifier(pubkey)
+
+
+  class PyCryptoSigner(object):
+    """Signs messages with a private key."""
+
+    def __init__(self, pkey):
+      """Constructor.
+
+      Args:
+        pkey, OpenSSL.crypto.PKey (or equiv), The private key to sign with.
+      """
+      self._key = pkey
+
+    def sign(self, message):
+      """Signs a message.
+
+      Args:
+        message: string, Message to be signed.
+
+      Returns:
+        string, The signature of the message for the given key.
+      """
+      return PKCS1_v1_5.new(self._key).sign(SHA256.new(message))
+
+    @staticmethod
+    def from_string(key, password='notasecret'):
+      """Construct a Signer instance from a string.
+
+      Args:
+        key: string, private key in PEM format.
+        password: string, password for private key file. Unused for PEM files.
+
+      Returns:
+        Signer instance.
+
+      Raises:
+        NotImplementedError if they key isn't in PEM format.
+      """
+      if key.startswith('-----BEGIN '):
+        pkey = RSA.importKey(key)
+      else:
+        raise NotImplementedError(
+            'PKCS12 format is not supported by the PyCrpto library. '
+            'Try converting to a "PEM" '
+            '(openssl pkcs12 -in xxxxx.p12 -nodes -nocerts > privatekey.pem) '
+            'or using PyOpenSSL if native code is an option.')
+      return PyCryptoSigner(pkey)
+
+except ImportError:
+  PyCryptoVerifier = None
+  PyCryptoSigner = None
+
+
+if OpenSSLSigner:
+  Signer = OpenSSLSigner
+  Verifier = OpenSSLVerifier
+elif PyCryptoSigner:
+  Signer = PyCryptoSigner
+  Verifier = PyCryptoVerifier
+else:
+  raise ImportError('No encryption library found. Please install either '
+                    'PyOpenSSL, or PyCrypto 2.6 or later')
 
 
 def _urlsafe_b64encode(raw_bytes):