diff --git a/.codeclimate.yml b/.codeclimate.yml
index 92ec005..907c00b 100644
--- a/.codeclimate.yml
+++ b/.codeclimate.yml
@@ -15,4 +15,3 @@
   - "**.py"
 exclude_paths:
 - tests/**/*
-- rsa/_version*.py
diff --git a/.gitignore b/.gitignore
index a90d26c..1f5a640 100644
--- a/.gitignore
+++ b/.gitignore
@@ -8,10 +8,12 @@
 /distribute*.tar.gz
 /distribute*.egg
 
-/.tox/
-/.coverage
-/.coverage.*
-/.cache/
+.tox/
+.coverage
+.coverage.*
+.cache/
+.pytest_cache/
+__pycache__/
 
 /build/
 /doc/_build/
diff --git a/.travis.yml b/.travis.yml
index 5304305..9b4da02 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -1,28 +1,30 @@
 language: python
-
-# Python 3.5 specified to make tox environment 'py35' work.
-# See: https://github.com/travis-ci/travis-ci/issues/4794
-python:
-  - 3.5
+cache: pip
 
 # Environment changes have to be manually synced with 'tox.ini'.
 # See: https://github.com/travis-ci/travis-ci/issues/3024
-env:
-  - TOXENV=py26
-  - TOXENV=py27
-  - TOXENV=py33
-  - TOXENV=py34
-  - TOXENV=py35
-  - TOXENV=pypy
+
+# Python 3.7 is not yet supported by Travis CI.
+# See: https://github.com/travis-ci/travis-ci/issues/9815
+
+python:
+  - "2.7"
+  - "3.4"
+  - "3.5"
+  - "3.6"
+  - "3.7-dev"
+
+# This is blocked by https://github.com/pypa/pipenv/issues/2449,
+# also see https://github.com/pypa/pipenv/projects/7
+#  - "pypy"
+  - "pypy3.5"
 
 install:
-  - pip install -r requirements.txt
-  - pip install coveralls
+  - pip install pipenv
+  - pipenv install --dev
 
 script:
-  - tox
+  - pipenv run py.test
 
 after_success:
-  # Coveralls submission only for py35 environment, because of being the only
-  # one that executes doctest-modules testing, according to tox.ini.
-  - if [ ${TOXENV} = "py35" ]; then coveralls; fi
+  - pipenv run coveralls
diff --git a/CHANGELOG.txt b/CHANGELOG.txt
index 49c8ab2..f8ed650 100644
--- a/CHANGELOG.txt
+++ b/CHANGELOG.txt
@@ -1,6 +1,29 @@
 Python-RSA changelog
 ========================================
 
+Version 4.0 - released 2018-09-16
+----------------------------------------
+
+- Removed deprecated modules:
+    - rsa.varblock
+    - rsa.bigfile
+    - rsa._version133
+    - rsa._version200
+- Removed CLI commands that use the VARBLOCK/bigfile format.
+- Ensured that PublicKey.save_pkcs1() and PrivateKey.save_pkcs1() always return bytes.
+- Dropped support for Python 2.6 and 3.3.
+- Dropped support for Psyco.
+- Miller-Rabin iterations determined by bitsize of key.
+  [#58](https://github.com/sybrenstuvel/python-rsa/pull/58)
+- Added function `rsa.find_signature_hash()` to return the name of the hashing
+  algorithm used to sign a message. `rsa.verify()` now also returns that name,
+  instead of always returning `True`.
+  [#78](https://github.com/sybrenstuvel/python-rsa/issues/13)
+- Add support for SHA-224 for PKCS1 signatures.
+  [#104](https://github.com/sybrenstuvel/python-rsa/pull/104)
+- Transitioned from `requirements.txt` to Pipenv for package management.
+
+
 Version 3.4.2 - released 2016-03-29
 ----------------------------------------
 
@@ -17,7 +40,7 @@
 Version 3.4 - released 2016-03-17
 ----------------------------------------
 
-- Moved development to Github: https://github.com/sybrenstuvel/python-rsa
+- Moved development to GitHub: https://github.com/sybrenstuvel/python-rsa
 - Solved side-channel vulnerability by implementing blinding, fixes #19
 - Deprecated the VARBLOCK format and rsa.bigfile module due to security issues, see
     https://github.com/sybrenstuvel/python-rsa/issues/13
@@ -33,7 +56,7 @@
 [1] https://travis-ci.org/sybrenstuvel/python-rsa
 [2] https://coveralls.io/github/sybrenstuvel/python-rsa
 [3] https://codeclimate.com/github/sybrenstuvel/python-rsa
-[4] http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pd
+[4] http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf
 
 
 Version 3.3 - released 2016-01-13
@@ -121,7 +144,7 @@
   the size of both ``p`` and ``q``. This is the common interpretation of
   RSA keysize. To get the old behaviour, double the keysize when generating a
   new key.
-  
+
 - Added a lot of doctests
 
 - Added random-padded encryption and decryption using PKCS#1 version 1.5
@@ -139,4 +162,3 @@
 ----------------------------------------
 
 - Security improvements by Barry Mead.
-
diff --git a/METADATA b/METADATA
index acf4820..937090d 100644
--- a/METADATA
+++ b/METADATA
@@ -1,9 +1,5 @@
 name: "rsa"
-description:
-    "Python-RSA is a pure-Python RSA implementation. It supports encryption and "
-    "decryption, signing and verifying signatures, and key generation according to "
-    "PKCS#1 version 1.5."
-
+description: "Python-RSA is a pure-Python RSA implementation. It supports encryption and decryption, signing and verifying signatures, and key generation according to PKCS#1 version 1.5."
 third_party {
   url {
     type: HOMEPAGE
@@ -13,6 +9,10 @@
     type: GIT
     value: "https://github.com/sybrenstuvel/python-rsa/"
   }
-  version: "3.4.2"
-  last_upgrade_date { year: 2018 month: 6 day: 4 }
+  version: "version-4.0"
+  last_upgrade_date {
+    year: 2019
+    month: 2
+    day: 1
+  }
 }
diff --git a/Pipfile b/Pipfile
new file mode 100644
index 0000000..89ec5fd
--- /dev/null
+++ b/Pipfile
@@ -0,0 +1,19 @@
+[[source]]
+url = "https://pypi.org/simple"
+verify_ssl = true
+name = "pypi"
+
+[packages]
+"pyasn1" = ">=0.1.3"
+
+[dev-packages]
+tox = "*"
+mock = ">=2.0.0"
+Sphinx = "*"
+coveralls = "*"
+pytest = "*"
+pytest-cov = "*"
+pathlib2 = {version = "*", markers="python_version < '3.6'"}
+
+[requires]
+python_version = "3.6"
diff --git a/Pipfile.lock b/Pipfile.lock
new file mode 100644
index 0000000..03fc240
--- /dev/null
+++ b/Pipfile.lock
@@ -0,0 +1,319 @@
+{
+    "_meta": {
+        "hash": {
+            "sha256": "a86e76a85c3a86f6a44f1b5f48205749c451c830746cbc535c66e72d8f5313cb"
+        },
+        "pipfile-spec": 6,
+        "requires": {
+            "python_version": "3.6"
+        },
+        "sources": [
+            {
+                "name": "pypi",
+                "url": "https://pypi.org/simple",
+                "verify_ssl": true
+            }
+        ]
+    },
+    "default": {
+        "pyasn1": {
+            "hashes": [
+                "sha256:b9d3abc5031e61927c82d4d96c1cec1e55676c1a991623cfed28faea73cdd7ca",
+                "sha256:f58f2a3d12fd754aa123e9fa74fb7345333000a035f3921dbdaa08597aa53137"
+            ],
+            "index": "pypi",
+            "version": "==0.4.4"
+        }
+    },
+    "develop": {
+        "alabaster": {
+            "hashes": [
+                "sha256:674bb3bab080f598371f4443c5008cbfeb1a5e622dd312395d2d82af2c54c456",
+                "sha256:b63b1f4dc77c074d386752ec4a8a7517600f6c0db8cd42980cae17ab7b3275d7"
+            ],
+            "version": "==0.7.11"
+        },
+        "atomicwrites": {
+            "hashes": [
+                "sha256:0312ad34fcad8fac3704d441f7b317e50af620823353ec657a53e981f92920c0",
+                "sha256:ec9ae8adaae229e4f8446952d204a3e4b5fdd2d099f9be3aaf556120135fb3ee"
+            ],
+            "markers": "python_version >= '2.7' and python_version != '3.1.*' and python_version != '3.3.*' and python_version != '3.0.*' and python_version != '3.2.*'",
+            "version": "==1.2.1"
+        },
+        "attrs": {
+            "hashes": [
+                "sha256:10cbf6e27dbce8c30807caf056c8eb50917e0eaafe86347671b57254006c3e69",
+                "sha256:ca4be454458f9dec299268d472aaa5a11f67a4ff70093396e1ceae9c76cf4bbb"
+            ],
+            "version": "==18.2.0"
+        },
+        "babel": {
+            "hashes": [
+                "sha256:6778d85147d5d85345c14a26aada5e478ab04e39b078b0745ee6870c2b5cf669",
+                "sha256:8cba50f48c529ca3fa18cf81fa9403be176d374ac4d60738b839122dfaaa3d23"
+            ],
+            "version": "==2.6.0"
+        },
+        "certifi": {
+            "hashes": [
+                "sha256:376690d6f16d32f9d1fe8932551d80b23e9d393a8578c5633a2ed39a64861638",
+                "sha256:456048c7e371c089d0a77a5212fb37a2c2dce1e24146e3b7e0261736aaeaa22a"
+            ],
+            "version": "==2018.8.24"
+        },
+        "chardet": {
+            "hashes": [
+                "sha256:84ab92ed1c4d4f16916e05906b6b75a6c0fb5db821cc65e70cbd64a3e2a5eaae",
+                "sha256:fc323ffcaeaed0e0a02bf4d117757b98aed530d9ed4531e3e15460124c106691"
+            ],
+            "version": "==3.0.4"
+        },
+        "colorama": {
+            "hashes": [
+                "sha256:463f8483208e921368c9f306094eb6f725c6ca42b0f97e313cb5d5512459feda",
+                "sha256:48eb22f4f8461b1df5734a074b57042430fb06e1d61bd1e11b078c0fe6d7a1f1"
+            ],
+            "markers": "sys_platform == 'win32'",
+            "version": "==0.3.9"
+        },
+        "coverage": {
+            "hashes": [
+                "sha256:03481e81d558d30d230bc12999e3edffe392d244349a90f4ef9b88425fac74ba",
+                "sha256:0b136648de27201056c1869a6c0d4e23f464750fd9a9ba9750b8336a244429ed",
+                "sha256:10a46017fef60e16694a30627319f38a2b9b52e90182dddb6e37dcdab0f4bf95",
+                "sha256:198626739a79b09fa0a2f06e083ffd12eb55449b5f8bfdbeed1df4910b2ca640",
+                "sha256:23d341cdd4a0371820eb2b0bd6b88f5003a7438bbedb33688cd33b8eae59affd",
+                "sha256:28b2191e7283f4f3568962e373b47ef7f0392993bb6660d079c62bd50fe9d162",
+                "sha256:2a5b73210bad5279ddb558d9a2bfedc7f4bf6ad7f3c988641d83c40293deaec1",
+                "sha256:2eb564bbf7816a9d68dd3369a510be3327f1c618d2357fa6b1216994c2e3d508",
+                "sha256:337ded681dd2ef9ca04ef5d93cfc87e52e09db2594c296b4a0a3662cb1b41249",
+                "sha256:3a2184c6d797a125dca8367878d3b9a178b6fdd05fdc2d35d758c3006a1cd694",
+                "sha256:3c79a6f7b95751cdebcd9037e4d06f8d5a9b60e4ed0cd231342aa8ad7124882a",
+                "sha256:3d72c20bd105022d29b14a7d628462ebdc61de2f303322c0212a054352f3b287",
+                "sha256:3eb42bf89a6be7deb64116dd1cc4b08171734d721e7a7e57ad64cc4ef29ed2f1",
+                "sha256:4635a184d0bbe537aa185a34193898eee409332a8ccb27eea36f262566585000",
+                "sha256:56e448f051a201c5ebbaa86a5efd0ca90d327204d8b059ab25ad0f35fbfd79f1",
+                "sha256:5a13ea7911ff5e1796b6d5e4fbbf6952381a611209b736d48e675c2756f3f74e",
+                "sha256:69bf008a06b76619d3c3f3b1983f5145c75a305a0fea513aca094cae5c40a8f5",
+                "sha256:6bc583dc18d5979dc0f6cec26a8603129de0304d5ae1f17e57a12834e7235062",
+                "sha256:701cd6093d63e6b8ad7009d8a92425428bc4d6e7ab8d75efbb665c806c1d79ba",
+                "sha256:7608a3dd5d73cb06c531b8925e0ef8d3de31fed2544a7de6c63960a1e73ea4bc",
+                "sha256:76ecd006d1d8f739430ec50cc872889af1f9c1b6b8f48e29941814b09b0fd3cc",
+                "sha256:7aa36d2b844a3e4a4b356708d79fd2c260281a7390d678a10b91ca595ddc9e99",
+                "sha256:7d3f553904b0c5c016d1dad058a7554c7ac4c91a789fca496e7d8347ad040653",
+                "sha256:7e1fe19bd6dce69d9fd159d8e4a80a8f52101380d5d3a4d374b6d3eae0e5de9c",
+                "sha256:8c3cb8c35ec4d9506979b4cf90ee9918bc2e49f84189d9bf5c36c0c1119c6558",
+                "sha256:9d6dd10d49e01571bf6e147d3b505141ffc093a06756c60b053a859cb2128b1f",
+                "sha256:be6cfcd8053d13f5f5eeb284aa8a814220c3da1b0078fa859011c7fffd86dab9",
+                "sha256:c1bb572fab8208c400adaf06a8133ac0712179a334c09224fb11393e920abcdd",
+                "sha256:de4418dadaa1c01d497e539210cb6baa015965526ff5afc078c57ca69160108d",
+                "sha256:e05cb4d9aad6233d67e0541caa7e511fa4047ed7750ec2510d466e806e0255d6",
+                "sha256:f3f501f345f24383c0000395b26b726e46758b71393267aeae0bd36f8b3ade80"
+            ],
+            "markers": "python_version != '3.1.*' and python_version >= '2.6' and python_version != '3.2.*' and python_version != '3.0.*' and python_version < '4'",
+            "version": "==4.5.1"
+        },
+        "coveralls": {
+            "hashes": [
+                "sha256:9dee67e78ec17b36c52b778247762851c8e19a893c9a14e921a2fc37f05fac22",
+                "sha256:aec5a1f5e34224b9089664a1b62217732381c7de361b6ed1b3c394d7187b352a"
+            ],
+            "index": "pypi",
+            "version": "==1.5.0"
+        },
+        "docopt": {
+            "hashes": [
+                "sha256:49b3a825280bd66b3aa83585ef59c4a8c82f2c8a522dbe754a8bc8d08c85c491"
+            ],
+            "version": "==0.6.2"
+        },
+        "docutils": {
+            "hashes": [
+                "sha256:02aec4bd92ab067f6ff27a38a38a41173bf01bed8f89157768c1573f53e474a6",
+                "sha256:51e64ef2ebfb29cae1faa133b3710143496eca21c530f3f71424d77687764274",
+                "sha256:7a4bd47eaf6596e1295ecb11361139febe29b084a87bf005bf899f9a42edc3c6"
+            ],
+            "version": "==0.14"
+        },
+        "idna": {
+            "hashes": [
+                "sha256:156a6814fb5ac1fc6850fb002e0852d56c0c8d2531923a51032d1b70760e186e",
+                "sha256:684a38a6f903c1d71d6d5fac066b58d7768af4de2b832e426ec79c30daa94a16"
+            ],
+            "version": "==2.7"
+        },
+        "imagesize": {
+            "hashes": [
+                "sha256:3f349de3eb99145973fefb7dbe38554414e5c30abd0c8e4b970a7c9d09f3a1d8",
+                "sha256:f3832918bc3c66617f92e35f5d70729187676313caa60c187eb0f28b8fe5e3b5"
+            ],
+            "markers": "python_version != '3.1.*' and python_version != '3.3.*' and python_version != '3.2.*' and python_version >= '2.7' and python_version != '3.0.*'",
+            "version": "==1.1.0"
+        },
+        "jinja2": {
+            "hashes": [
+                "sha256:74c935a1b8bb9a3947c50a54766a969d4846290e1e788ea44c1392163723c3bd",
+                "sha256:f84be1bb0040caca4cea721fcbbbbd61f9be9464ca236387158b0feea01914a4"
+            ],
+            "version": "==2.10"
+        },
+        "markupsafe": {
+            "hashes": [
+                "sha256:a6be69091dac236ea9c6bc7d012beab42010fa914c459791d627dad4910eb665"
+            ],
+            "version": "==1.0"
+        },
+        "mock": {
+            "hashes": [
+                "sha256:5ce3c71c5545b472da17b72268978914d0252980348636840bd34a00b5cc96c1",
+                "sha256:b158b6df76edd239b8208d481dc46b6afd45a846b7812ff0ce58971cf5bc8bba"
+            ],
+            "index": "pypi",
+            "version": "==2.0.0"
+        },
+        "more-itertools": {
+            "hashes": [
+                "sha256:c187a73da93e7a8acc0001572aebc7e3c69daf7bf6881a2cea10650bd4420092",
+                "sha256:c476b5d3a34e12d40130bc2f935028b5f636df8f372dc2c1c01dc19681b2039e",
+                "sha256:fcbfeaea0be121980e15bc97b3817b5202ca73d0eae185b4550cbfce2a3ebb3d"
+            ],
+            "version": "==4.3.0"
+        },
+        "packaging": {
+            "hashes": [
+                "sha256:e9215d2d2535d3ae866c3d6efc77d5b24a0192cce0ff20e42896cc0664f889c0",
+                "sha256:f019b770dd64e585a99714f1fd5e01c7a8f11b45635aa953fd41c689a657375b"
+            ],
+            "version": "==17.1"
+        },
+        "pbr": {
+            "hashes": [
+                "sha256:1b8be50d938c9bb75d0eaf7eda111eec1bf6dc88a62a6412e33bf077457e0f45",
+                "sha256:b486975c0cafb6beeb50ca0e17ba047647f229087bd74e37f4a7e2cac17d2caa"
+            ],
+            "version": "==4.2.0"
+        },
+        "pluggy": {
+            "hashes": [
+                "sha256:6e3836e39f4d36ae72840833db137f7b7d35105079aee6ec4a62d9f80d594dd1",
+                "sha256:95eb8364a4708392bae89035f45341871286a333f749c3141c20573d2b3876e1"
+            ],
+            "markers": "python_version != '3.1.*' and python_version != '3.3.*' and python_version != '3.2.*' and python_version >= '2.7' and python_version != '3.0.*'",
+            "version": "==0.7.1"
+        },
+        "py": {
+            "hashes": [
+                "sha256:06a30435d058473046be836d3fc4f27167fd84c45b99704f2fb5509ef61f9af1",
+                "sha256:50402e9d1c9005d759426988a492e0edaadb7f4e68bcddfea586bc7432d009c6"
+            ],
+            "markers": "python_version != '3.1.*' and python_version != '3.3.*' and python_version != '3.2.*' and python_version >= '2.7' and python_version != '3.0.*'",
+            "version": "==1.6.0"
+        },
+        "pygments": {
+            "hashes": [
+                "sha256:78f3f434bcc5d6ee09020f92ba487f95ba50f1e3ef83ae96b9d5ffa1bab25c5d",
+                "sha256:dbae1046def0efb574852fab9e90209b23f556367b5a320c0bcb871c77c3e8cc"
+            ],
+            "version": "==2.2.0"
+        },
+        "pyparsing": {
+            "hashes": [
+                "sha256:0832bcf47acd283788593e7a0f542407bd9550a55a8a8435214a1960e04bcb04",
+                "sha256:fee43f17a9c4087e7ed1605bd6df994c6173c1e977d7ade7b651292fab2bd010"
+            ],
+            "version": "==2.2.0"
+        },
+        "pytest": {
+            "hashes": [
+                "sha256:453cbbbe5ce6db38717d282b758b917de84802af4288910c12442984bde7b823",
+                "sha256:a8a07f84e680482eb51e244370aaf2caa6301ef265f37c2bdefb3dd3b663f99d"
+            ],
+            "index": "pypi",
+            "version": "==3.8.0"
+        },
+        "pytest-cov": {
+            "hashes": [
+                "sha256:513c425e931a0344944f84ea47f3956be0e416d95acbd897a44970c8d926d5d7",
+                "sha256:e360f048b7dae3f2f2a9a4d067b2dd6b6a015d384d1577c994a43f3f7cbad762"
+            ],
+            "index": "pypi",
+            "version": "==2.6.0"
+        },
+        "pytz": {
+            "hashes": [
+                "sha256:a061aa0a9e06881eb8b3b2b43f05b9439d6583c206d0a6c340ff72a7b6669053",
+                "sha256:ffb9ef1de172603304d9d2819af6f5ece76f2e85ec10692a524dd876e72bf277"
+            ],
+            "version": "==2018.5"
+        },
+        "requests": {
+            "hashes": [
+                "sha256:63b52e3c866428a224f97cab011de738c36aec0185aa91cfacd418b5d58911d1",
+                "sha256:ec22d826a36ed72a7358ff3fe56cbd4ba69dd7a6718ffd450ff0e9df7a47ce6a"
+            ],
+            "version": "==2.19.1"
+        },
+        "six": {
+            "hashes": [
+                "sha256:70e8a77beed4562e7f14fe23a786b54f6296e34344c23bc42f07b15018ff98e9",
+                "sha256:832dc0e10feb1aa2c68dcc57dbb658f1c7e65b9b61af69048abc87a2db00a0eb"
+            ],
+            "version": "==1.11.0"
+        },
+        "snowballstemmer": {
+            "hashes": [
+                "sha256:919f26a68b2c17a7634da993d91339e288964f93c274f1343e3bbbe2096e1128",
+                "sha256:9f3bcd3c401c3e862ec0ebe6d2c069ebc012ce142cce209c098ccb5b09136e89"
+            ],
+            "version": "==1.2.1"
+        },
+        "sphinx": {
+            "hashes": [
+                "sha256:95acd6648902333647a0e0564abdb28a74b0a76d2333148aa35e5ed1f56d3c4b",
+                "sha256:c091dbdd5cc5aac6eb95d591a819fd18bccec90ffb048ec465b165a48b839b45"
+            ],
+            "index": "pypi",
+            "version": "==1.8.0"
+        },
+        "sphinxcontrib-websupport": {
+            "hashes": [
+                "sha256:68ca7ff70785cbe1e7bccc71a48b5b6d965d79ca50629606c7861a21b206d9dd",
+                "sha256:9de47f375baf1ea07cdb3436ff39d7a9c76042c10a769c52353ec46e4e8fc3b9"
+            ],
+            "markers": "python_version != '3.1.*' and python_version != '3.3.*' and python_version != '3.2.*' and python_version >= '2.7' and python_version != '3.0.*'",
+            "version": "==1.1.0"
+        },
+        "toml": {
+            "hashes": [
+                "sha256:380178cde50a6a79f9d2cf6f42a62a5174febe5eea4126fe4038785f1d888d42",
+                "sha256:a7901919d3e4f92ffba7ff40a9d697e35bbbc8a8049fe8da742f34c83606d957"
+            ],
+            "version": "==0.9.6"
+        },
+        "tox": {
+            "hashes": [
+                "sha256:433bb93c57edae263150767e672a0d468ab4fefcc1958eb4013e56a670bb851e",
+                "sha256:bfb4e4efb7c61a54bc010a5c00fdbe0973bc4bdf04090bfcd3c93c901006177c"
+            ],
+            "index": "pypi",
+            "version": "==3.3.0"
+        },
+        "urllib3": {
+            "hashes": [
+                "sha256:a68ac5e15e76e7e5dd2b8f94007233e01effe3e50e8daddf69acfd81cb686baf",
+                "sha256:b5725a0bd4ba422ab0e66e89e030c806576753ea3ee08554382c14e685d117b5"
+            ],
+            "markers": "python_version != '3.1.*' and python_version >= '2.6' and python_version != '3.3.*' and python_version != '3.2.*' and python_version != '3.0.*' and python_version < '4'",
+            "version": "==1.23"
+        },
+        "virtualenv": {
+            "hashes": [
+                "sha256:2ce32cd126117ce2c539f0134eb89de91a8413a29baac49cbab3eb50e2026669",
+                "sha256:ca07b4c0b54e14a91af9f34d0919790b016923d157afda5efdde55c96718f752"
+            ],
+            "markers": "python_version != '3.1.*' and python_version != '3.2.*' and python_version != '3.0.*' and python_version >= '2.7'",
+            "version": "==16.0.0"
+        }
+    }
+}
diff --git a/README.md b/README.md
index ba1013b..c5e0f2d 100644
--- a/README.md
+++ b/README.md
@@ -1,13 +1,10 @@
 Pure Python RSA implementation
 ==============================
 
-[![PyPI](https://img.shields.io/pypi/v/rsa.svg)](https://pypi.python.org/pypi/rsa)
-[![Build Status](https://travis-ci.org/sybrenstuvel/python-rsa.svg?branch=master)]
-    (https://travis-ci.org/sybrenstuvel/python-rsa)
-[![Coverage Status](https://coveralls.io/repos/github/sybrenstuvel/python-rsa/badge.svg?branch=master)]
-    (https://coveralls.io/github/sybrenstuvel/python-rsa?branch=master)
-[![Code Climate](https://img.shields.io/codeclimate/github/sybrenstuvel/python-rsa.svg)]
-    (https://codeclimate.com/github/sybrenstuvel/python-rsa)
+[![PyPI](https://img.shields.io/pypi/v/rsa.svg)](https://pypi.org/project/rsa/)
+[![Build Status](https://travis-ci.org/sybrenstuvel/python-rsa.svg?branch=master)](https://travis-ci.org/sybrenstuvel/python-rsa)
+[![Coverage Status](https://coveralls.io/repos/github/sybrenstuvel/python-rsa/badge.svg?branch=master)](https://coveralls.io/github/sybrenstuvel/python-rsa?branch=master)
+[![Code Climate](https://img.shields.io/codeclimate/github/sybrenstuvel/python-rsa.svg)](https://codeclimate.com/github/sybrenstuvel/python-rsa)
 
 [Python-RSA](https://stuvel.eu/rsa) is a pure-Python RSA implementation. It supports
 encryption and decryption, signing and verifying signatures, and key
@@ -21,16 +18,16 @@
 
     pip install rsa
 
-or download it from the [Python Package Index](https://pypi.python.org/pypi/rsa).
+or download it from the [Python Package Index](https://pypi.org/project/rsa/).
 
-The source code is maintained at [Github](https://github.com/sybrenstuvel/python-rsa/) and is
+The source code is maintained at [GitHub](https://github.com/sybrenstuvel/python-rsa/) and is
 licensed under the [Apache License, version 2.0](https://www.apache.org/licenses/LICENSE-2.0)
 
 
-Plans for the future
+Major changes in 4.0
 --------------------
 
-Version 3.4 is the last version in the 3.x range. Version 4.0 will drop the following modules,
+Version 3.4 was the last version in the 3.x range. Version 4.0 drops the following modules,
 as they are insecure:
 
 - `rsa._version133`
@@ -38,7 +35,9 @@
 - `rsa.bigfile`
 - `rsa.varblock`
 
-Those modules are marked as deprecated in version 3.4.
+Those modules were marked as deprecated in version 3.4.
 
-Furthermore, in 4.0 the I/O functions will be streamlined to always work with bytes on all
+Furthermore, in 4.0 the I/O functions is streamlined to always work with bytes on all
 supported versions of Python.
+
+Version 4.0 drops support for Python 2.6 and 3.3.
diff --git a/doc/cli.rst b/doc/cli.rst
index af2b5f1..30864d7 100644
--- a/doc/cli.rst
+++ b/doc/cli.rst
@@ -13,31 +13,30 @@
 .. index:: pyrsa-verify, pyrsa-priv2pub, pyrsa-encrypt-bigfile
 .. index:: pyrsa-decrypt-bigfile, pyrsa-decrypt-bigfile
 
-+-----------------------+--------------------------------------------------+-----------------------------------------+
-| Command               | Usage                                            | Core function                           |
-+=======================+==================================================+=========================================+
-| pyrsa-keygen          | Generates a new RSA keypair in PEM or DER format | :py:func:`rsa.newkeys`                  |
-+-----------------------+--------------------------------------------------+-----------------------------------------+
-| pyrsa-encrypt         | Encrypts a file. The file must be shorter than   | :py:func:`rsa.encrypt`                  |
-|                       | the key length in order to be encrypted.         |                                         |
-+-----------------------+--------------------------------------------------+-----------------------------------------+
-| pyrsa-decrypt         | Decrypts a file.                                 | :py:func:`rsa.decrypt`                  |
-+-----------------------+--------------------------------------------------+-----------------------------------------+
-| pyrsa-sign            | Signs a file, outputs the signature.             | :py:func:`rsa.sign`                     |
-+-----------------------+--------------------------------------------------+-----------------------------------------+
-| pyrsa-verify          | Verifies a signature. The result is written to   | :py:func:`rsa.verify`                   |
-|                       | the console as well as returned in the exit      |                                         |
-|                       | status code.                                     |                                         |
-+-----------------------+--------------------------------------------------+-----------------------------------------+
-| pyrsa-priv2pub        | Reads a private key and outputs the              | \-                                      |
-|                       | corresponding public key.                        |                                         |
-+-----------------------+--------------------------------------------------+-----------------------------------------+
-| pyrsa-encrypt-bigfile | Encrypts a file to an encrypted VARBLOCK file.   | :py:func:`rsa.bigfile.encrypt_bigfile`  |
-|                       | The file can be larger than the key length, but  |                                         |
-|                       | the output file is only compatible with          |                                         |
-|                       | Python-RSA.                                      |                                         |
-+-----------------------+--------------------------------------------------+-----------------------------------------+
-| pyrsa-decrypt-bigfile | Decrypts an encrypted VARBLOCK file.             | :py:func:`rsa.bigfile.encrypt_bigfile`  |
-+-----------------------+--------------------------------------------------+-----------------------------------------+
-
-
++-------------------------+--------------------------------------------------+-----------------------------------------+
+| Command                 | Usage                                            | Core function                           |
++=========================+==================================================+=========================================+
+| pyrsa-keygen            | Generates a new RSA keypair in PEM or DER format | :py:func:`rsa.newkeys`                  |
++-------------------------+--------------------------------------------------+-----------------------------------------+
+| pyrsa-encrypt           | Encrypts a file. The file must be shorter than   | :py:func:`rsa.encrypt`                  |
+|                         | the key length in order to be encrypted.         |                                         |
++-------------------------+--------------------------------------------------+-----------------------------------------+
+| pyrsa-decrypt           | Decrypts a file.                                 | :py:func:`rsa.decrypt`                  |
++-------------------------+--------------------------------------------------+-----------------------------------------+
+| pyrsa-sign              | Signs a file, outputs the signature.             | :py:func:`rsa.sign`                     |
++-------------------------+--------------------------------------------------+-----------------------------------------+
+| pyrsa-verify            | Verifies a signature. The result is written to   | :py:func:`rsa.verify`                   |
+|                         | the console as well as returned in the exit      |                                         |
+|                         | status code.                                     |                                         |
++-------------------------+--------------------------------------------------+-----------------------------------------+
+| pyrsa-priv2pub          | Reads a private key and outputs the              | \-                                      |
+|                         | corresponding public key.                        |                                         |
++-------------------------+--------------------------------------------------+-----------------------------------------+
+| *pyrsa-encrypt-bigfile* | *Encrypts a file to an encrypted VARBLOCK file.  | *Deprecated in Python-RSA 3.4 and       |
+|                         | The file can be larger than the key length, but  | removed from version 4.0.*              |
+|                         | the output file is only compatible with          |                                         |
+|                         | Python-RSA.*                                     |                                         |
++-------------------------+--------------------------------------------------+-----------------------------------------+
+| *pyrsa-decrypt-bigfile* | *Decrypts an encrypted VARBLOCK file.*           | *Deprecated in Python-RSA 3.4 and       |
+|                         |                                                  | removed from version 4.0.*              |
++-------------------------+--------------------------------------------------+-----------------------------------------+
diff --git a/doc/compatibility.rst b/doc/compatibility.rst
index aedfcb6..be4d295 100644
--- a/doc/compatibility.rst
+++ b/doc/compatibility.rst
@@ -16,7 +16,7 @@
 
 Signatures:
     PKCS#1 v1.5 using the following hash methods:
-    MD5, SHA-1, SHA-256, SHA-384, SHA-512
+    MD5, SHA-1, SHA-224, SHA-256, SHA-384, SHA-512
 
 Private keys:
     PKCS#1 v1.5 in PEM and DER format, ASN.1 type RSAPrivateKey
@@ -25,7 +25,8 @@
     PKCS#1 v1.5 in PEM and DER format, ASN.1 type RSAPublicKey
 
 :ref:`VARBLOCK <bigfiles>` encryption:
-    Python-RSA only, not compatible with any other known application.
+    Deprecated in Python-RSA 3.4 and removed from Python-RSA 4.0.
+    Was Python-RSA only, not compatible with any other known application.
 
 .. _openssl:
 
@@ -59,4 +60,3 @@
     openssl rsa -in privatekey-pkcs8.pem -out privatekey.pem
 
 You can then extract the corresponding public key as described above.
-
diff --git a/doc/conf.py b/doc/conf.py
index 95317b2..3331a86 100644
--- a/doc/conf.py
+++ b/doc/conf.py
@@ -28,7 +28,7 @@
 # Add any Sphinx extension module names here, as strings. They can be extensions
 # coming with Sphinx (named 'sphinx.ext.*') or your custom ones.
 extensions = ['sphinx.ext.autodoc', 'sphinx.ext.doctest', 'sphinx.ext.todo',
-              'sphinx.ext.coverage', 'sphinx.ext.pngmath']
+              'sphinx.ext.coverage']
 
 # I would like to add 'sphinx.ext.viewcode', but it causes a UnicodeDecodeError
 
@@ -46,7 +46,7 @@
 
 # General information about the project.
 project = u'Python-RSA'
-copyright = u'2011-2016, Sybren A. Stüvel'
+copyright = u'2011-2018, Sybren A. Stüvel'
 
 # The version info for the project you're documenting, acts as replacement for
 # |version| and |release|, also used in various other places throughout the
diff --git a/doc/installation.rst b/doc/installation.rst
index 578dc86..32dc257 100644
--- a/doc/installation.rst
+++ b/doc/installation.rst
@@ -5,23 +5,18 @@
 or easy_install. Either one will work::
 
     pip install rsa
-    easy_install rsa
 
-Depending on your system you may need to use ``sudo pip`` or ``sudo
-easy_install``.
+Depending on your system you may need to use ``sudo pip`` if you want to install
+the library system-wide.
 
 Installation from source is also quite easy. Download the source and
 then type::
 
     python setup.py install
 
-or if that doesn't work::
-
-    sudo python setup.py install
-
 
 The sources are tracked in our `Git repository`_ at
-Github. It also hosts the `issue tracker`_.
+GitHub. It also hosts the `issue tracker`_.
 
 .. _`Git repository`: https://github.com/sybrenstuvel/python-rsa.git
 .. _`issue tracker`: https://github.com/sybrenstuvel/python-rsa/issues
@@ -49,7 +44,7 @@
 
 Once these are installed, use Git_ to get a copy of the source::
 
-    hg clone https://github.com/sybrenstuvel/python-rsa.git
+    git clone https://github.com/sybrenstuvel/python-rsa.git
     python setup.py develop
 
 .. _Git: https://git-scm.com/
diff --git a/doc/reference.rst b/doc/reference.rst
index d1b0b6d..9da7c6b 100644
--- a/doc/reference.rst
+++ b/doc/reference.rst
@@ -15,6 +15,8 @@
 
 .. autofunction:: rsa.verify
 
+.. autofunction:: rsa.find_signature_hash
+
 .. autofunction:: rsa.newkeys(keysize)
 
 
@@ -49,32 +51,13 @@
 
 .. index:: VARBLOCK (file format)
 
-Module: rsa.bigfile
--------------------
-
-.. warning::
-
-    The :py:mod:`rsa.bigfile` module is NOT recommended for general use, has been
-    deprecated since Python-RSA 3.4, and will be removed in a future release. It's
-    vulnerable to a number of attacks. See :ref:`bigfiles` for more information.
-
-The :py:mod:`rsa.bigfile` module contains functions for encrypting and
-decrypting files that are larger than the RSA key. See
-:ref:`bigfiles` for more information.
-
-.. autofunction:: rsa.bigfile.encrypt_bigfile
-
-.. autofunction:: rsa.bigfile.decrypt_bigfile
-
-.. _VARBLOCK:
-
 The VARBLOCK file format
 ++++++++++++++++++++++++
 
 .. warning::
 
     The VARBLOCK format is NOT recommended for general use, has been deprecated since
-    Python-RSA 3.4, and will be removed in a future release. It's vulnerable to a
+    Python-RSA 3.4, and was removed in version 4.0. It's vulnerable to a
     number of attacks. See :ref:`bigfiles` for more information.
 
 The VARBLOCK file format allows us to encrypt files that are larger
@@ -109,4 +92,3 @@
 .. autofunction:: rsa.core.encrypt_int
 
 .. autofunction:: rsa.core.decrypt_int
-
diff --git a/doc/upgrading.rst b/doc/upgrading.rst
index 0ec18eb..3381baa 100644
--- a/doc/upgrading.rst
+++ b/doc/upgrading.rst
@@ -1,6 +1,22 @@
 Upgrading from older versions
 =============================
 
+From versions older than Python-RSA 4.0
+---------------------------------------
+
+Support for the VARBLOCK/bigfile format has been dropped in version 4.0, after
+being deprecated for a year. There is no alternative implementation in
+Python-RSA 4.0. If you need this, or have ideas on how to do handle encryption
+of large files securely and in a compatible way with existing standards,
+`open a ticket to discuss this`_.
+
+.. _open a ticket to discuss this:
+    https://github.com/sybrenstuvel/python-rsa/issues/new
+
+
+From versions older than Python-RSA 3.4
+---------------------------------------
+
 Previous versions of Python-RSA were less secure than the current
 version. In order to be able to gradually upgrade your software, those
 old versions will be available until Python-RSA 4.0.
@@ -34,8 +50,7 @@
 
 The random padding introduced in version 3.0 made things much more
 secure, but also requires a larger key to encrypt the same message.
-You can either generate a new key with :py:func:`rsa.newkeys`, or use
-:py:func:`rsa.bigfile.encrypt_bigfile` to encrypt your files.
+
 
 Converting keys
 ---------------
@@ -70,4 +85,3 @@
 
     old_priv_key.update(old_pub_key)
     priv_key = rsa.PrivateKey(**old_priv_key)
-
diff --git a/doc/usage.rst b/doc/usage.rst
index a3d128d..b1244d4 100644
--- a/doc/usage.rst
+++ b/doc/usage.rst
@@ -13,13 +13,13 @@
     The private key is called *private* for a reason. Never share this
     key with anyone.
 
-The public key is used for encypting a message such that it can only
+The public key is used for encrypting a message such that it can only
 be read by the owner of the private key. As such it's also referred to
 as the *encryption key*. Decrypting a message can only be done using
 the private key, hence it's also called the *decryption key*.
 
 The private key is used for signing a message. With this signature and
-the public key, the receiver can verifying that a message was signed
+the public key, the receiver can verify that a message was signed
 by the owner of the private key, and that the message was not modified
 after signing.
 
@@ -90,32 +90,6 @@
 generates a 4096-bit key in 3.5 seconds on the same machine as used
 above. See :ref:`openssl` for more information.
 
-Key size requirements
----------------------
-
-Python-RSA version 3.0 introduced PKCS#1-style random padding. This
-means that 11 bytes (88 bits) of your key are no longer usable for
-encryption, so keys smaller than this are unusable. The larger the
-key, the higher the security.
-
-Creating signatures also requires a key of a certain size, depending
-on the used hash method:
-
-+-------------+-----------------------------------+
-| Hash method | Suggested minimum key size (bits) |
-+=============+===================================+
-| MD5         | 360                               |
-+-------------+-----------------------------------+
-| SHA-1       | 368                               |
-+-------------+-----------------------------------+
-| SHA-256     | 496                               |
-+-------------+-----------------------------------+
-| SHA-384     | 624                               |
-+-------------+-----------------------------------+
-| SHA-512     | 752                               |
-+-------------+-----------------------------------+
-
-
 
 Encryption and decryption
 -------------------------
@@ -198,11 +172,20 @@
     >>> (pubkey, privkey) = rsa.newkeys(512)
     >>> message = 'Go left at the blue tree'
     >>> signature = rsa.sign(message, privkey, 'SHA-1')
-    
+
 This hashes the message using SHA-1. Other hash methods are also
 possible, check the :py:func:`rsa.sign` function documentation for
 details. The hash is then signed with the private key.
 
+It is possible to calculate the hash and signature in separate operations
+(i.e for generating the hash on a client machine and then sign with a
+private key on remote server). To hash a message use the :py:func:`rsa.compute_hash`
+function and then use the :py:func:`rsa.sign_hash` function to sign the hash:
+
+    >>> message = 'Go left at the blue tree'
+    >>> hash = rsa.compute_hash(message, 'SHA-1')
+    >>> signature = rsa.sign_hash(hash, privkey, 'SHA-1')
+
 In order to verify the signature, use the :py:func:`rsa.verify`
 function. This function returns True if the verification is successful:
 
@@ -285,7 +268,7 @@
 .. warning::
 
     The VARBLOCK format is NOT recommended for general use, has been deprecated since
-    Python-RSA 3.4, and will be removed in a future release. It's vulnerable to a
+    Python-RSA 3.4, and has been removed in version 4.0. It's vulnerable to a
     number of attacks:
 
     1. decrypt/encrypt_bigfile() does not implement `Authenticated encryption`_ nor
@@ -294,60 +277,11 @@
     2. decrypt/encrypt_bigfile() does not use hybrid encryption (it uses plain RSA)
        and has no method for chaining, so block reordering is possible.
 
-    See `issue #19 on Github`_ for more information.
+    See `issue #19 on GitHub`_ for more information.
 
 .. _Authenticated encryption: https://en.wikipedia.org/wiki/Authenticated_encryption
-.. _issue #19 on Github: https://github.com/sybrenstuvel/python-rsa/issues/13
+.. _issue #19 on GitHub: https://github.com/sybrenstuvel/python-rsa/issues/13
 
-
-As far as we know, there is no pure-Python AES encryption. Previous
-versions of Python-RSA included functionality to encrypt large files
-with just RSA, and so does this version. The format has been improved,
-though.
-
-Encrypting works as follows: the input file is split into blocks that
-are just large enough to encrypt with your RSA key. Every block is
-then encrypted using RSA, and the encrypted blocks are assembled into
-the output file. This file format is called the :ref:`VARBLOCK
-<VARBLOCK>` format.
-
-Decrypting works in reverse. The encrypted file is separated into
-encrypted blocks. Those are decrypted, and assembled into the original
-file.
-
-.. note::
-
-    The file will get larger after encryption, as each encrypted block
-    has 8 bytes of random padding and 3 more bytes of overhead.
-
-Since these encryption/decryption functions are potentially called on
-very large files, they use another approach. Where the regular
-functions store the message in memory in its entirety, these functions
-work on one block at the time. As a result, you should call them with
-:py:class:`file`-like objects as the parameters.
-
-Before using we of course need a keypair:
-
->>> import rsa
->>> (pub_key, priv_key) = rsa.newkeys(512)
-
-Encryption works on file handles using the
-:py:func:`rsa.bigfile.encrypt_bigfile` function:
-
->>> from rsa.bigfile import *
->>> with open('inputfile', 'rb') as infile, open('outputfile', 'wb') as outfile:
-...     encrypt_bigfile(infile, outfile, pub_key)
-
-As does decryption using the :py:func:`rsa.bigfile.decrypt_bigfile`
-function:
-
->>> from rsa.bigfile import *
->>> with open('inputfile', 'rb') as infile, open('outputfile', 'wb') as outfile:
-...     decrypt_bigfile(infile, outfile, priv_key)
-
-.. note::
-
-    :py:func:`rsa.sign` and :py:func:`rsa.verify` work on arbitrarily
-    long files, so they do not have a "bigfile" equivalent.
-
-
+As of Python-RSA version 4.0, the VARBLOCK format has been removed from the
+library. For now, this section is kept here to document the issues with that
+format, and ensure we don't do something like that again.
diff --git a/requirements.txt b/requirements.txt
deleted file mode 100644
index f1c6af1..0000000
--- a/requirements.txt
+++ /dev/null
@@ -1,4 +0,0 @@
-sphinx
-pyasn1>=0.1.3
-tox
-wheel
diff --git a/rsa/__init__.py b/rsa/__init__.py
index c572c06..9b05c6c 100644
--- a/rsa/__init__.py
+++ b/rsa/__init__.py
@@ -18,19 +18,18 @@
 Module for calculating large primes, and RSA encryption, decryption, signing
 and verification. Includes generating public and private keys.
 
-WARNING: this implementation does not use random padding, compression of the
-cleartext input to prevent repetitions, or other common security improvements.
-Use with care.
+WARNING: this implementation does not use compression of the cleartext input to
+prevent repetitions, or other common security improvements. Use with care.
 
 """
 
 from rsa.key import newkeys, PrivateKey, PublicKey
 from rsa.pkcs1 import encrypt, decrypt, sign, verify, DecryptionError, \
-    VerificationError
+    VerificationError, find_signature_hash,  sign_hash, compute_hash
 
 __author__ = "Sybren Stuvel, Barry Mead and Yesudeep Mangalapilly"
-__date__ = "2016-03-29"
-__version__ = '3.4.2'
+__date__ = "2018-09-16"
+__version__ = '4.0'
 
 # Do doctest if we're run directly
 if __name__ == "__main__":
@@ -39,4 +38,5 @@
     doctest.testmod()
 
 __all__ = ["newkeys", "encrypt", "decrypt", "sign", "verify", 'PublicKey',
-           'PrivateKey', 'DecryptionError', 'VerificationError']
+           'PrivateKey', 'DecryptionError', 'VerificationError',
+           'compute_hash', 'sign_hash']
diff --git a/rsa/_compat.py b/rsa/_compat.py
index 93393d9..71197a5 100644
--- a/rsa/_compat.py
+++ b/rsa/_compat.py
@@ -18,18 +18,17 @@
 
 from __future__ import absolute_import
 
+import itertools
 import sys
 from struct import pack
 
-try:
-    MAX_INT = sys.maxsize
-except AttributeError:
-    MAX_INT = sys.maxint
-
+MAX_INT = sys.maxsize
 MAX_INT64 = (1 << 63) - 1
 MAX_INT32 = (1 << 31) - 1
 MAX_INT16 = (1 << 15) - 1
 
+PY2 = sys.version_info[0] == 2
+
 # Determine the word size of the processor.
 if MAX_INT == MAX_INT64:
     # 64-bit processor.
@@ -41,32 +40,26 @@
     # Else we just assume 64-bit processor keeping up with modern times.
     MACHINE_WORD_SIZE = 64
 
-try:
-    # < Python3
-    unicode_type = unicode
-except NameError:
-    # Python3.
-    unicode_type = str
-
-# Fake byte literals.
-if str is unicode_type:
-    def byte_literal(s):
-        return s.encode('latin1')
-else:
-    def byte_literal(s):
-        return s
-
-# ``long`` is no more. Do type detection using this instead.
-try:
+if PY2:
     integer_types = (int, long)
-except NameError:
-    integer_types = (int,)
+    range = xrange
+    zip = itertools.izip
+else:
+    integer_types = (int, )
+    range = range
+    zip = zip
 
-b = byte_literal
 
-# To avoid calling b() multiple times in tight loops.
-ZERO_BYTE = b('\x00')
-EMPTY_BYTE = b('')
+def write_to_stdout(data):
+    """Writes bytes to stdout
+
+    :type data: bytes
+    """
+    if PY2:
+        sys.stdout.write(data)
+    else:
+        # On Py3 we must use the buffer interface to write bytes.
+        sys.stdout.buffer.write(data)
 
 
 def is_bytes(obj):
@@ -109,6 +102,27 @@
     return pack("B", num)
 
 
+def xor_bytes(b1, b2):
+    """
+    Returns the bitwise XOR result between two bytes objects, b1 ^ b2.
+
+    Bitwise XOR operation is commutative, so order of parameters doesn't
+    generate different results. If parameters have different length, extra
+    length of the largest one is ignored.
+
+    :param b1:
+        First bytes object.
+    :param b2:
+        Second bytes object.
+    :returns:
+        Bytes object, result of XOR operation.
+    """
+    if PY2:
+        return ''.join(byte(ord(x) ^ ord(y)) for x, y in zip(b1, b2))
+
+    return bytes(x ^ y for x, y in zip(b1, b2))
+
+
 def get_word_alignment(num, force_arch=64,
                        _machine_word_size=MACHINE_WORD_SIZE):
     """
diff --git a/rsa/_version133.py b/rsa/_version133.py
deleted file mode 100644
index ff03b45..0000000
--- a/rsa/_version133.py
+++ /dev/null
@@ -1,441 +0,0 @@
-# -*- coding: utf-8 -*-
-#
-#  Copyright 2011 Sybren A. Stüvel <sybren@stuvel.eu>
-#
-#  Licensed under the Apache License, Version 2.0 (the "License");
-#  you may not use this file except in compliance with the License.
-#  You may obtain a copy of the License at
-#
-#      https://www.apache.org/licenses/LICENSE-2.0
-#
-#  Unless required by applicable law or agreed to in writing, software
-#  distributed under the License is distributed on an "AS IS" BASIS,
-#  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-#  See the License for the specific language governing permissions and
-#  limitations under the License.
-
-"""Deprecated version of the RSA module
-
-.. deprecated:: 2.0
-
-    This submodule is deprecated and will be completely removed as of version 4.0.
-
-Module for calculating large primes, and RSA encryption, decryption,
-signing and verification. Includes generating public and private keys.
-
-WARNING: this code implements the mathematics of RSA. It is not suitable for
-real-world secure cryptography purposes. It has not been reviewed by a security
-expert. It does not include padding of data. There are many ways in which the
-output of this module, when used without any modification, can be sucessfully
-attacked.
-"""
-
-__author__ = "Sybren Stuvel, Marloes de Boer and Ivo Tamboer"
-__date__ = "2010-02-05"
-__version__ = '1.3.3'
-
-# NOTE: Python's modulo can return negative numbers. We compensate for
-# this behaviour using the abs() function
-
-try:
-    import cPickle as pickle
-except ImportError:
-    import pickle
-from pickle import dumps, loads
-import base64
-import math
-import os
-import random
-import sys
-import types
-import zlib
-
-from rsa._compat import byte
-
-# Display a warning that this insecure version is imported.
-import warnings
-warnings.warn('Insecure version of the RSA module is imported as %s, be careful'
-        % __name__)
-warnings.warn('This submodule is deprecated and will be completely removed as of version 4.0.',
-              DeprecationWarning)
-
-
-def gcd(p, q):
-    """Returns the greatest common divisor of p and q
-
-
-    >>> gcd(42, 6)
-    6
-    """
-    if p<q: return gcd(q, p)
-    if q == 0: return p
-    return gcd(q, abs(p%q))
-
-def bytes2int(bytes):
-    """Converts a list of bytes or a string to an integer
-    """
-
-    if not (type(bytes) is types.ListType or type(bytes) is types.StringType):
-        raise TypeError("You must pass a string or a list")
-
-    # Convert byte stream to integer
-    integer = 0
-    for byte in bytes:
-        integer *= 256
-        if type(byte) is types.StringType: byte = ord(byte)
-        integer += byte
-
-    return integer
-
-def int2bytes(number):
-    """Converts a number to a string of bytes
-    """
-
-    if not (type(number) is types.LongType or type(number) is types.IntType):
-        raise TypeError("You must pass a long or an int")
-
-    string = ""
-
-    while number > 0:
-        string = "%s%s" % (byte(number & 0xFF), string)
-        number /= 256
-    
-    return string
-
-def fast_exponentiation(a, p, n):
-    """Calculates r = a^p mod n
-    """
-    result = a % n
-    remainders = []
-    while p != 1:
-        remainders.append(p & 1)
-        p = p >> 1
-    while remainders:
-        rem = remainders.pop()
-        result = ((a ** rem) * result ** 2) % n
-    return result
-
-def read_random_int(nbits):
-    """Reads a random integer of approximately nbits bits rounded up
-    to whole bytes"""
-
-    nbytes = ceil(nbits/8.)
-    randomdata = os.urandom(nbytes)
-    return bytes2int(randomdata)
-
-def ceil(x):
-    """ceil(x) -> int(math.ceil(x))"""
-
-    return int(math.ceil(x))
-    
-def randint(minvalue, maxvalue):
-    """Returns a random integer x with minvalue <= x <= maxvalue"""
-
-    # Safety - get a lot of random data even if the range is fairly
-    # small
-    min_nbits = 32
-
-    # The range of the random numbers we need to generate
-    range = maxvalue - minvalue
-
-    # Which is this number of bytes
-    rangebytes = ceil(math.log(range, 2) / 8.)
-
-    # Convert to bits, but make sure it's always at least min_nbits*2
-    rangebits = max(rangebytes * 8, min_nbits * 2)
-    
-    # Take a random number of bits between min_nbits and rangebits
-    nbits = random.randint(min_nbits, rangebits)
-    
-    return (read_random_int(nbits) % range) + minvalue
-
-def fermat_little_theorem(p):
-    """Returns 1 if p may be prime, and something else if p definitely
-    is not prime"""
-
-    a = randint(1, p-1)
-    return fast_exponentiation(a, p-1, p)
-
-def jacobi(a, b):
-    """Calculates the value of the Jacobi symbol (a/b)
-    """
-
-    if a % b == 0:
-        return 0
-    result = 1
-    while a > 1:
-        if a & 1:
-            if ((a-1)*(b-1) >> 2) & 1:
-                result = -result
-            b, a = a, b % a
-        else:
-            if ((b ** 2 - 1) >> 3) & 1:
-                result = -result
-            a = a >> 1
-    return result
-
-def jacobi_witness(x, n):
-    """Returns False if n is an Euler pseudo-prime with base x, and
-    True otherwise.
-    """
-
-    j = jacobi(x, n) % n
-    f = fast_exponentiation(x, (n-1)/2, n)
-
-    if j == f: return False
-    return True
-
-def randomized_primality_testing(n, k):
-    """Calculates whether n is composite (which is always correct) or
-    prime (which is incorrect with error probability 2**-k)
-
-    Returns False if the number if composite, and True if it's
-    probably prime.
-    """
-
-    q = 0.5     # Property of the jacobi_witness function
-
-    # t = int(math.ceil(k / math.log(1/q, 2)))
-    t = ceil(k / math.log(1/q, 2))
-    for i in range(t+1):
-        x = randint(1, n-1)
-        if jacobi_witness(x, n): return False
-    
-    return True
-
-def is_prime(number):
-    """Returns True if the number is prime, and False otherwise.
-    """
-
-    """
-    if not fermat_little_theorem(number) == 1:
-        # Not prime, according to Fermat's little theorem
-        return False
-    """
-
-    if randomized_primality_testing(number, 5):
-        # Prime, according to Jacobi
-        return True
-    
-    # Not prime
-    return False
-
-    
-def getprime(nbits):
-    """Returns a prime number of max. 'math.ceil(nbits/8)*8' bits. In
-    other words: nbits is rounded up to whole bytes.
-    """
-
-    nbytes = int(math.ceil(nbits/8.))
-
-    while True:
-        integer = read_random_int(nbits)
-
-        # Make sure it's odd
-        integer |= 1
-
-        # Test for primeness
-        if is_prime(integer): break
-
-        # Retry if not prime
-
-    return integer
-
-def are_relatively_prime(a, b):
-    """Returns True if a and b are relatively prime, and False if they
-    are not.
-    """
-
-    d = gcd(a, b)
-    return (d == 1)
-
-def find_p_q(nbits):
-    """Returns a tuple of two different primes of nbits bits"""
-
-    p = getprime(nbits)
-    while True:
-        q = getprime(nbits)
-        if not q == p: break
-    
-    return (p, q)
-
-def extended_euclid_gcd(a, b):
-    """Returns a tuple (d, i, j) such that d = gcd(a, b) = ia + jb
-    """
-
-    if b == 0:
-        return (a, 1, 0)
-
-    q = abs(a % b)
-    r = long(a / b)
-    (d, k, l) = extended_euclid_gcd(b, q)
-
-    return (d, l, k - l*r)
-
-# Main function: calculate encryption and decryption keys
-def calculate_keys(p, q, nbits):
-    """Calculates an encryption and a decryption key for p and q, and
-    returns them as a tuple (e, d)"""
-
-    n = p * q
-    phi_n = (p-1) * (q-1)
-
-    while True:
-        # Make sure e has enough bits so we ensure "wrapping" through
-        # modulo n
-        e = getprime(max(8, nbits/2))
-        if are_relatively_prime(e, n) and are_relatively_prime(e, phi_n): break
-
-    (d, i, j) = extended_euclid_gcd(e, phi_n)
-
-    if not d == 1:
-        raise Exception("e (%d) and phi_n (%d) are not relatively prime" % (e, phi_n))
-
-    if not (e * i) % phi_n == 1:
-        raise Exception("e (%d) and i (%d) are not mult. inv. modulo phi_n (%d)" % (e, i, phi_n))
-
-    return (e, i)
-
-
-def gen_keys(nbits):
-    """Generate RSA keys of nbits bits. Returns (p, q, e, d).
-
-    Note: this can take a long time, depending on the key size.
-    """
-
-    while True:
-        (p, q) = find_p_q(nbits)
-        (e, d) = calculate_keys(p, q, nbits)
-
-        # For some reason, d is sometimes negative. We don't know how
-        # to fix it (yet), so we keep trying until everything is shiny
-        if d > 0: break
-
-    return (p, q, e, d)
-
-def gen_pubpriv_keys(nbits):
-    """Generates public and private keys, and returns them as (pub,
-    priv).
-
-    The public key consists of a dict {e: ..., , n: ....). The private
-    key consists of a dict {d: ...., p: ...., q: ....).
-    """
-    
-    (p, q, e, d) = gen_keys(nbits)
-
-    return ( {'e': e, 'n': p*q}, {'d': d, 'p': p, 'q': q} )
-
-def encrypt_int(message, ekey, n):
-    """Encrypts a message using encryption key 'ekey', working modulo
-    n"""
-
-    if type(message) is types.IntType:
-        return encrypt_int(long(message), ekey, n)
-
-    if not type(message) is types.LongType:
-        raise TypeError("You must pass a long or an int")
-
-    if message > 0 and \
-            math.floor(math.log(message, 2)) > math.floor(math.log(n, 2)):
-        raise OverflowError("The message is too long")
-
-    return fast_exponentiation(message, ekey, n)
-
-def decrypt_int(cyphertext, dkey, n):
-    """Decrypts a cypher text using the decryption key 'dkey', working
-    modulo n"""
-
-    return encrypt_int(cyphertext, dkey, n)
-
-def sign_int(message, dkey, n):
-    """Signs 'message' using key 'dkey', working modulo n"""
-
-    return decrypt_int(message, dkey, n)
-
-def verify_int(signed, ekey, n):
-    """verifies 'signed' using key 'ekey', working modulo n"""
-
-    return encrypt_int(signed, ekey, n)
-
-def picklechops(chops):
-    """Pickles and base64encodes it's argument chops"""
-
-    value = zlib.compress(dumps(chops))
-    encoded = base64.encodestring(value)
-    return encoded.strip()
-
-def unpicklechops(string):
-    """base64decodes and unpickes it's argument string into chops"""
-
-    return loads(zlib.decompress(base64.decodestring(string)))
-
-def chopstring(message, key, n, funcref):
-    """Splits 'message' into chops that are at most as long as n,
-    converts these into integers, and calls funcref(integer, key, n)
-    for each chop.
-
-    Used by 'encrypt' and 'sign'.
-    """
-
-    msglen = len(message)
-    mbits = msglen * 8
-    nbits = int(math.floor(math.log(n, 2)))
-    nbytes = nbits / 8
-    blocks = msglen / nbytes
-
-    if msglen % nbytes > 0:
-        blocks += 1
-
-    cypher = []
-    
-    for bindex in range(blocks):
-        offset = bindex * nbytes
-        block = message[offset:offset+nbytes]
-        value = bytes2int(block)
-        cypher.append(funcref(value, key, n))
-
-    return picklechops(cypher)
-
-def gluechops(chops, key, n, funcref):
-    """Glues chops back together into a string.  calls
-    funcref(integer, key, n) for each chop.
-
-    Used by 'decrypt' and 'verify'.
-    """
-    message = ""
-
-    chops = unpicklechops(chops)
-    
-    for cpart in chops:
-        mpart = funcref(cpart, key, n)
-        message += int2bytes(mpart)
-    
-    return message
-
-def encrypt(message, key):
-    """Encrypts a string 'message' with the public key 'key'"""
-    
-    return chopstring(message, key['e'], key['n'], encrypt_int)
-
-def sign(message, key):
-    """Signs a string 'message' with the private key 'key'"""
-    
-    return chopstring(message, key['d'], key['p']*key['q'], decrypt_int)
-
-def decrypt(cypher, key):
-    """Decrypts a cypher with the private key 'key'"""
-
-    return gluechops(cypher, key['d'], key['p']*key['q'], decrypt_int)
-
-def verify(cypher, key):
-    """Verifies a cypher with the public key 'key'"""
-
-    return gluechops(cypher, key['e'], key['n'], encrypt_int)
-
-# Do doctest if we're not imported
-if __name__ == "__main__":
-    import doctest
-    doctest.testmod()
-
-__all__ = ["gen_pubpriv_keys", "encrypt", "decrypt", "sign", "verify"]
-
diff --git a/rsa/_version200.py b/rsa/_version200.py
deleted file mode 100644
index 1a16949..0000000
--- a/rsa/_version200.py
+++ /dev/null
@@ -1,513 +0,0 @@
-# -*- coding: utf-8 -*-
-#
-#  Copyright 2011 Sybren A. Stüvel <sybren@stuvel.eu>
-#
-#  Licensed under the Apache License, Version 2.0 (the "License");
-#  you may not use this file except in compliance with the License.
-#  You may obtain a copy of the License at
-#
-#      https://www.apache.org/licenses/LICENSE-2.0
-#
-#  Unless required by applicable law or agreed to in writing, software
-#  distributed under the License is distributed on an "AS IS" BASIS,
-#  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-#  See the License for the specific language governing permissions and
-#  limitations under the License.
-
-"""Deprecated version of the RSA module
-
-.. deprecated:: 3.0
-
-    This submodule is deprecated and will be completely removed as of version 4.0.
-
-"""
-
-__author__ = "Sybren Stuvel, Marloes de Boer, Ivo Tamboer, and Barry Mead"
-__date__ = "2010-02-08"
-__version__ = '2.0'
-
-import math
-import os
-import random
-import sys
-import types
-from rsa._compat import byte
-
-# Display a warning that this insecure version is imported.
-import warnings
-warnings.warn('Insecure version of the RSA module is imported as %s' % __name__)
-warnings.warn('This submodule is deprecated and will be completely removed as of version 4.0.',
-              DeprecationWarning)
-
-
-def bit_size(number):
-    """Returns the number of bits required to hold a specific long number"""
-
-    return int(math.ceil(math.log(number,2)))
-
-def gcd(p, q):
-    """Returns the greatest common divisor of p and q
-    >>> gcd(48, 180)
-    12
-    """
-    # Iterateive Version is faster and uses much less stack space
-    while q != 0:
-        if p < q: (p,q) = (q,p)
-        (p,q) = (q, p % q)
-    return p
-    
-
-def bytes2int(bytes):
-    r"""Converts a list of bytes or a string to an integer
-    """
-
-    if not (type(bytes) is types.ListType or type(bytes) is types.StringType):
-        raise TypeError("You must pass a string or a list")
-
-    # Convert byte stream to integer
-    integer = 0
-    for byte in bytes:
-        integer *= 256
-        if type(byte) is types.StringType: byte = ord(byte)
-        integer += byte
-
-    return integer
-
-def int2bytes(number):
-    """
-    Converts a number to a string of bytes
-    """
-
-    if not (type(number) is types.LongType or type(number) is types.IntType):
-        raise TypeError("You must pass a long or an int")
-
-    string = ""
-
-    while number > 0:
-        string = "%s%s" % (byte(number & 0xFF), string)
-        number /= 256
-    
-    return string
-
-def to64(number):
-    """Converts a number in the range of 0 to 63 into base 64 digit
-    character in the range of '0'-'9', 'A'-'Z', 'a'-'z','-','_'.
-    """
-
-    if not (type(number) is types.LongType or type(number) is types.IntType):
-        raise TypeError("You must pass a long or an int")
-
-    if 0 <= number <= 9:            #00-09 translates to '0' - '9'
-        return byte(number + 48)
-
-    if 10 <= number <= 35:
-        return byte(number + 55)     #10-35 translates to 'A' - 'Z'
-
-    if 36 <= number <= 61:
-        return byte(number + 61)     #36-61 translates to 'a' - 'z'
-
-    if number == 62:                # 62   translates to '-' (minus)
-        return byte(45)
-
-    if number == 63:                # 63   translates to '_' (underscore)
-        return byte(95)
-
-    raise ValueError('Invalid Base64 value: %i' % number)
-
-
-def from64(number):
-    """Converts an ordinal character value in the range of
-    0-9,A-Z,a-z,-,_ to a number in the range of 0-63.
-    """
-
-    if not (type(number) is types.LongType or type(number) is types.IntType):
-        raise TypeError("You must pass a long or an int")
-
-    if 48 <= number <= 57:         #ord('0') - ord('9') translates to 0-9
-        return(number - 48)
-
-    if 65 <= number <= 90:         #ord('A') - ord('Z') translates to 10-35
-        return(number - 55)
-
-    if 97 <= number <= 122:        #ord('a') - ord('z') translates to 36-61
-        return(number - 61)
-
-    if number == 45:               #ord('-') translates to 62
-        return(62)
-
-    if number == 95:               #ord('_') translates to 63
-        return(63)
-
-    raise ValueError('Invalid Base64 value: %i' % number)
-
-
-def int2str64(number):
-    """Converts a number to a string of base64 encoded characters in
-    the range of '0'-'9','A'-'Z,'a'-'z','-','_'.
-    """
-
-    if not (type(number) is types.LongType or type(number) is types.IntType):
-        raise TypeError("You must pass a long or an int")
-
-    string = ""
-
-    while number > 0:
-        string = "%s%s" % (to64(number & 0x3F), string)
-        number /= 64
-
-    return string
-
-
-def str642int(string):
-    """Converts a base64 encoded string into an integer.
-    The chars of this string in in the range '0'-'9','A'-'Z','a'-'z','-','_'
-    """
-
-    if not (type(string) is types.ListType or type(string) is types.StringType):
-        raise TypeError("You must pass a string or a list")
-
-    integer = 0
-    for byte in string:
-        integer *= 64
-        if type(byte) is types.StringType: byte = ord(byte)
-        integer += from64(byte)
-
-    return integer
-
-def read_random_int(nbits):
-    """Reads a random integer of approximately nbits bits rounded up
-    to whole bytes"""
-
-    nbytes = int(math.ceil(nbits/8.))
-    randomdata = os.urandom(nbytes)
-    return bytes2int(randomdata)
-
-def randint(minvalue, maxvalue):
-    """Returns a random integer x with minvalue <= x <= maxvalue"""
-
-    # Safety - get a lot of random data even if the range is fairly
-    # small
-    min_nbits = 32
-
-    # The range of the random numbers we need to generate
-    range = (maxvalue - minvalue) + 1
-
-    # Which is this number of bytes
-    rangebytes = ((bit_size(range) + 7) / 8)
-
-    # Convert to bits, but make sure it's always at least min_nbits*2
-    rangebits = max(rangebytes * 8, min_nbits * 2)
-    
-    # Take a random number of bits between min_nbits and rangebits
-    nbits = random.randint(min_nbits, rangebits)
-    
-    return (read_random_int(nbits) % range) + minvalue
-
-def jacobi(a, b):
-    """Calculates the value of the Jacobi symbol (a/b)
-    where both a and b are positive integers, and b is odd
-    """
-
-    if a == 0: return 0
-    result = 1
-    while a > 1:
-        if a & 1:
-            if ((a-1)*(b-1) >> 2) & 1:
-                result = -result
-            a, b = b % a, a
-        else:
-            if (((b * b) - 1) >> 3) & 1:
-                result = -result
-            a >>= 1
-    if a == 0: return 0
-    return result
-
-def jacobi_witness(x, n):
-    """Returns False if n is an Euler pseudo-prime with base x, and
-    True otherwise.
-    """
-
-    j = jacobi(x, n) % n
-    f = pow(x, (n-1)/2, n)
-
-    if j == f: return False
-    return True
-
-def randomized_primality_testing(n, k):
-    """Calculates whether n is composite (which is always correct) or
-    prime (which is incorrect with error probability 2**-k)
-
-    Returns False if the number is composite, and True if it's
-    probably prime.
-    """
-
-    # 50% of Jacobi-witnesses can report compositness of non-prime numbers
-
-    for i in range(k):
-        x = randint(1, n-1)
-        if jacobi_witness(x, n): return False
-    
-    return True
-
-def is_prime(number):
-    """Returns True if the number is prime, and False otherwise.
-    """
-
-    if randomized_primality_testing(number, 6):
-        # Prime, according to Jacobi
-        return True
-    
-    # Not prime
-    return False
-
-    
-def getprime(nbits):
-    """Returns a prime number of max. 'math.ceil(nbits/8)*8' bits. In
-    other words: nbits is rounded up to whole bytes.
-    """
-
-    while True:
-        integer = read_random_int(nbits)
-
-        # Make sure it's odd
-        integer |= 1
-
-        # Test for primeness
-        if is_prime(integer): break
-
-        # Retry if not prime
-
-    return integer
-
-def are_relatively_prime(a, b):
-    """Returns True if a and b are relatively prime, and False if they
-    are not.
-
-    >>> are_relatively_prime(2, 3)
-    1
-    >>> are_relatively_prime(2, 4)
-    0
-    """
-
-    d = gcd(a, b)
-    return (d == 1)
-
-def find_p_q(nbits):
-    """Returns a tuple of two different primes of nbits bits"""
-    pbits = nbits + (nbits/16)  #Make sure that p and q aren't too close
-    qbits = nbits - (nbits/16)  #or the factoring programs can factor n
-    p = getprime(pbits)
-    while True:
-        q = getprime(qbits)
-        #Make sure p and q are different.
-        if not q == p: break
-    return (p, q)
-
-def extended_gcd(a, b):
-    """Returns a tuple (r, i, j) such that r = gcd(a, b) = ia + jb
-    """
-    # r = gcd(a,b) i = multiplicitive inverse of a mod b
-    #      or      j = multiplicitive inverse of b mod a
-    # Neg return values for i or j are made positive mod b or a respectively
-    # Iterateive Version is faster and uses much less stack space
-    x = 0
-    y = 1
-    lx = 1
-    ly = 0
-    oa = a                             #Remember original a/b to remove 
-    ob = b                             #negative values from return results
-    while b != 0:
-        q = long(a/b)
-        (a, b)  = (b, a % b)
-        (x, lx) = ((lx - (q * x)),x)
-        (y, ly) = ((ly - (q * y)),y)
-    if (lx < 0): lx += ob              #If neg wrap modulo orignal b
-    if (ly < 0): ly += oa              #If neg wrap modulo orignal a
-    return (a, lx, ly)                 #Return only positive values
-
-# Main function: calculate encryption and decryption keys
-def calculate_keys(p, q, nbits):
-    """Calculates an encryption and a decryption key for p and q, and
-    returns them as a tuple (e, d)"""
-
-    n = p * q
-    phi_n = (p-1) * (q-1)
-
-    while True:
-        # Make sure e has enough bits so we ensure "wrapping" through
-        # modulo n
-        e = max(65537,getprime(nbits/4))
-        if are_relatively_prime(e, n) and are_relatively_prime(e, phi_n): break
-
-    (d, i, j) = extended_gcd(e, phi_n)
-
-    if not d == 1:
-        raise Exception("e (%d) and phi_n (%d) are not relatively prime" % (e, phi_n))
-    if (i < 0):
-        raise Exception("New extended_gcd shouldn't return negative values")
-    if not (e * i) % phi_n == 1:
-        raise Exception("e (%d) and i (%d) are not mult. inv. modulo phi_n (%d)" % (e, i, phi_n))
-
-    return (e, i)
-
-
-def gen_keys(nbits):
-    """Generate RSA keys of nbits bits. Returns (p, q, e, d).
-
-    Note: this can take a long time, depending on the key size.
-    """
-
-    (p, q) = find_p_q(nbits)
-    (e, d) = calculate_keys(p, q, nbits)
-
-    return (p, q, e, d)
-
-def newkeys(nbits):
-    """Generates public and private keys, and returns them as (pub,
-    priv).
-
-    The public key consists of a dict {e: ..., , n: ....). The private
-    key consists of a dict {d: ...., p: ...., q: ....).
-    """
-    nbits = max(9,nbits)           # Don't let nbits go below 9 bits
-    (p, q, e, d) = gen_keys(nbits)
-
-    return ( {'e': e, 'n': p*q}, {'d': d, 'p': p, 'q': q} )
-
-def encrypt_int(message, ekey, n):
-    """Encrypts a message using encryption key 'ekey', working modulo n"""
-
-    if type(message) is types.IntType:
-        message = long(message)
-
-    if not type(message) is types.LongType:
-        raise TypeError("You must pass a long or int")
-
-    if message < 0 or message > n:
-        raise OverflowError("The message is too long")
-
-    #Note: Bit exponents start at zero (bit counts start at 1) this is correct
-    safebit = bit_size(n) - 2                   #compute safe bit (MSB - 1)
-    message += (1 << safebit)                   #add safebit to ensure folding
-
-    return pow(message, ekey, n)
-
-def decrypt_int(cyphertext, dkey, n):
-    """Decrypts a cypher text using the decryption key 'dkey', working
-    modulo n"""
-
-    message = pow(cyphertext, dkey, n)
-
-    safebit = bit_size(n) - 2                   #compute safe bit (MSB - 1)
-    message -= (1 << safebit)                   #remove safebit before decode
-
-    return message
-
-def encode64chops(chops):
-    """base64encodes chops and combines them into a ',' delimited string"""
-
-    chips = []                              #chips are character chops
-
-    for value in chops:
-        chips.append(int2str64(value))
-
-    #delimit chops with comma
-    encoded = ','.join(chips)
-
-    return encoded
-
-def decode64chops(string):
-    """base64decodes and makes a ',' delimited string into chops"""
-
-    chips = string.split(',')               #split chops at commas
-
-    chops = []
-
-    for string in chips:                    #make char chops (chips) into chops
-        chops.append(str642int(string))
-
-    return chops
-
-def chopstring(message, key, n, funcref):
-    """Chops the 'message' into integers that fit into n,
-    leaving room for a safebit to be added to ensure that all
-    messages fold during exponentiation.  The MSB of the number n
-    is not independant modulo n (setting it could cause overflow), so
-    use the next lower bit for the safebit.  Therefore reserve 2-bits
-    in the number n for non-data bits.  Calls specified encryption
-    function for each chop.
-
-    Used by 'encrypt' and 'sign'.
-    """
-
-    msglen = len(message)
-    mbits = msglen * 8
-    #Set aside 2-bits so setting of safebit won't overflow modulo n.
-    nbits = bit_size(n) - 2             # leave room for safebit
-    nbytes = nbits / 8
-    blocks = msglen / nbytes
-
-    if msglen % nbytes > 0:
-        blocks += 1
-
-    cypher = []
-    
-    for bindex in range(blocks):
-        offset = bindex * nbytes
-        block = message[offset:offset+nbytes]
-        value = bytes2int(block)
-        cypher.append(funcref(value, key, n))
-
-    return encode64chops(cypher)   #Encode encrypted ints to base64 strings
-
-def gluechops(string, key, n, funcref):
-    """Glues chops back together into a string.  calls
-    funcref(integer, key, n) for each chop.
-
-    Used by 'decrypt' and 'verify'.
-    """
-    message = ""
-
-    chops = decode64chops(string)  #Decode base64 strings into integer chops
-    
-    for cpart in chops:
-        mpart = funcref(cpart, key, n) #Decrypt each chop
-        message += int2bytes(mpart)    #Combine decrypted strings into a msg
-    
-    return message
-
-def encrypt(message, key):
-    """Encrypts a string 'message' with the public key 'key'"""
-    if 'n' not in key:
-        raise Exception("You must use the public key with encrypt")
-
-    return chopstring(message, key['e'], key['n'], encrypt_int)
-
-def sign(message, key):
-    """Signs a string 'message' with the private key 'key'"""
-    if 'p' not in key:
-        raise Exception("You must use the private key with sign")
-
-    return chopstring(message, key['d'], key['p']*key['q'], encrypt_int)
-
-def decrypt(cypher, key):
-    """Decrypts a string 'cypher' with the private key 'key'"""
-    if 'p' not in key:
-        raise Exception("You must use the private key with decrypt")
-
-    return gluechops(cypher, key['d'], key['p']*key['q'], decrypt_int)
-
-def verify(cypher, key):
-    """Verifies a string 'cypher' with the public key 'key'"""
-    if 'n' not in key:
-        raise Exception("You must use the public key with verify")
-
-    return gluechops(cypher, key['e'], key['n'], decrypt_int)
-
-# Do doctest if we're not imported
-if __name__ == "__main__":
-    import doctest
-    doctest.testmod()
-
-__all__ = ["newkeys", "encrypt", "decrypt", "sign", "verify"]
-
diff --git a/rsa/bigfile.py b/rsa/bigfile.py
deleted file mode 100644
index 3a09716..0000000
--- a/rsa/bigfile.py
+++ /dev/null
@@ -1,135 +0,0 @@
-# -*- coding: utf-8 -*-
-#
-#  Copyright 2011 Sybren A. Stüvel <sybren@stuvel.eu>
-#
-#  Licensed under the Apache License, Version 2.0 (the "License");
-#  you may not use this file except in compliance with the License.
-#  You may obtain a copy of the License at
-#
-#      https://www.apache.org/licenses/LICENSE-2.0
-#
-#  Unless required by applicable law or agreed to in writing, software
-#  distributed under the License is distributed on an "AS IS" BASIS,
-#  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-#  See the License for the specific language governing permissions and
-#  limitations under the License.
-
-"""Large file support
-
-.. deprecated:: 3.4
-
-    The VARBLOCK format is NOT recommended for general use, has been deprecated since
-    Python-RSA 3.4, and will be removed in a future release. It's vulnerable to a
-    number of attacks:
-
-    1. decrypt/encrypt_bigfile() does not implement `Authenticated encryption`_ nor
-       uses MACs to verify messages before decrypting public key encrypted messages.
-
-    2. decrypt/encrypt_bigfile() does not use hybrid encryption (it uses plain RSA)
-       and has no method for chaining, so block reordering is possible.
-
-    See `issue #19 on Github`_ for more information.
-
-.. _Authenticated encryption: https://en.wikipedia.org/wiki/Authenticated_encryption
-.. _issue #19 on Github: https://github.com/sybrenstuvel/python-rsa/issues/13
-
-
-This module contains functions to:
-
-    - break a file into smaller blocks, and encrypt them, and store the
-      encrypted blocks in another file.
-
-    - take such an encrypted files, decrypt its blocks, and reconstruct the
-      original file.
-
-The encrypted file format is as follows, where || denotes byte concatenation:
-
-    FILE := VERSION || BLOCK || BLOCK ...
-
-    BLOCK := LENGTH || DATA
-
-    LENGTH := varint-encoded length of the subsequent data. Varint comes from
-    Google Protobuf, and encodes an integer into a variable number of bytes.
-    Each byte uses the 7 lowest bits to encode the value. The highest bit set
-    to 1 indicates the next byte is also part of the varint. The last byte will
-    have this bit set to 0.
-
-This file format is called the VARBLOCK format, in line with the varint format
-used to denote the block sizes.
-
-"""
-
-import warnings
-
-from rsa import key, common, pkcs1, varblock
-from rsa._compat import byte
-
-
-def encrypt_bigfile(infile, outfile, pub_key):
-    """Encrypts a file, writing it to 'outfile' in VARBLOCK format.
-
-    .. deprecated:: 3.4
-        This function was deprecated in Python-RSA version 3.4 due to security issues
-        in the VARBLOCK format. See the documentation_ for more information.
-
-    .. _documentation: https://stuvel.eu/python-rsa-doc/usage.html#working-with-big-files
-
-    :param infile: file-like object to read the cleartext from
-    :param outfile: file-like object to write the crypto in VARBLOCK format to
-    :param pub_key: :py:class:`rsa.PublicKey` to encrypt with
-
-    """
-
-    warnings.warn("The 'rsa.bigfile.encrypt_bigfile' function was deprecated in Python-RSA version "
-                  "3.4 due to security issues in the VARBLOCK format. See "
-                  "https://stuvel.eu/python-rsa-doc/usage.html#working-with-big-files "
-                  "for more information.",
-                  DeprecationWarning, stacklevel=2)
-
-    if not isinstance(pub_key, key.PublicKey):
-        raise TypeError('Public key required, but got %r' % pub_key)
-
-    key_bytes = common.bit_size(pub_key.n) // 8
-    blocksize = key_bytes - 11  # keep space for PKCS#1 padding
-
-    # Write the version number to the VARBLOCK file
-    outfile.write(byte(varblock.VARBLOCK_VERSION))
-
-    # Encrypt and write each block
-    for block in varblock.yield_fixedblocks(infile, blocksize):
-        crypto = pkcs1.encrypt(block, pub_key)
-
-        varblock.write_varint(outfile, len(crypto))
-        outfile.write(crypto)
-
-
-def decrypt_bigfile(infile, outfile, priv_key):
-    """Decrypts an encrypted VARBLOCK file, writing it to 'outfile'
-
-    .. deprecated:: 3.4
-        This function was deprecated in Python-RSA version 3.4 due to security issues
-        in the VARBLOCK format. See the documentation_ for more information.
-
-    .. _documentation: https://stuvel.eu/python-rsa-doc/usage.html#working-with-big-files
-
-    :param infile: file-like object to read the crypto in VARBLOCK format from
-    :param outfile: file-like object to write the cleartext to
-    :param priv_key: :py:class:`rsa.PrivateKey` to decrypt with
-
-    """
-
-    warnings.warn("The 'rsa.bigfile.decrypt_bigfile' function was deprecated in Python-RSA version "
-                  "3.4 due to security issues in the VARBLOCK format. See "
-                  "https://stuvel.eu/python-rsa-doc/usage.html#working-with-big-files "
-                  "for more information.",
-                  DeprecationWarning, stacklevel=2)
-
-    if not isinstance(priv_key, key.PrivateKey):
-        raise TypeError('Private key required, but got %r' % priv_key)
-
-    for block in varblock.yield_varblocks(infile):
-        cleartext = pkcs1.decrypt(block, priv_key)
-        outfile.write(cleartext)
-
-
-__all__ = ['encrypt_bigfile', 'decrypt_bigfile']
diff --git a/rsa/cli.py b/rsa/cli.py
index 3a21878..6450af4 100644
--- a/rsa/cli.py
+++ b/rsa/cli.py
@@ -26,7 +26,6 @@
 from optparse import OptionParser
 
 import rsa
-import rsa.bigfile
 import rsa.pkcs1
 
 HASH_METHODS = sorted(rsa.pkcs1.HASH_METHODS.keys())
@@ -84,7 +83,7 @@
             outfile.write(data)
     else:
         print('Writing private key to stdout', file=sys.stderr)
-        sys.stdout.write(data)
+        rsa._compat.write_to_stdout(data)
 
 
 class CryptoOperation(object):
@@ -113,7 +112,7 @@
         self.output_help = self.output_help % self.__class__.__dict__
 
     @abc.abstractmethod
-    def perform_operation(self, indata, key, cli_args=None):
+    def perform_operation(self, indata, key, cli_args):
         """Performs the program's operation.
 
         Implement in a subclass.
@@ -190,7 +189,7 @@
                 outfile.write(outdata)
         else:
             print('Writing output to stdout', file=sys.stderr)
-            sys.stdout.write(outdata)
+            rsa._compat.write_to_stdout(outdata)
 
 
 class EncryptOperation(CryptoOperation):
@@ -198,8 +197,7 @@
 
     keyname = 'public'
     description = ('Encrypts a file. The file must be shorter than the key '
-                   'length in order to be encrypted. For larger files, use the '
-                   'pyrsa-encrypt-bigfile command.')
+                   'length in order to be encrypted.')
     operation = 'encrypt'
     operation_past = 'encrypted'
     operation_progressive = 'encrypting'
@@ -215,8 +213,7 @@
 
     keyname = 'private'
     description = ('Decrypts a file. The original file must be shorter than '
-                   'the key length in order to have been encrypted. For larger '
-                   'files, use the pyrsa-decrypt-bigfile command.')
+                   'the key length in order to have been encrypted.')
     operation = 'decrypt'
     operation_past = 'decrypted'
     operation_progressive = 'decrypting'
@@ -285,99 +282,7 @@
         print('Verification OK', file=sys.stderr)
 
 
-class BigfileOperation(CryptoOperation):
-    """CryptoOperation that doesn't read the entire file into memory."""
-
-    def __init__(self):
-        CryptoOperation.__init__(self)
-
-        self.file_objects = []
-
-    def __del__(self):
-        """Closes any open file handles."""
-
-        for fobj in self.file_objects:
-            fobj.close()
-
-    def __call__(self):
-        """Runs the program."""
-
-        (cli, cli_args) = self.parse_cli()
-
-        key = self.read_key(cli_args[0], cli.keyform)
-
-        # Get the file handles
-        infile = self.get_infile(cli.input)
-        outfile = self.get_outfile(cli.output)
-
-        # Call the operation
-        print(self.operation_progressive.title(), file=sys.stderr)
-        self.perform_operation(infile, outfile, key, cli_args)
-
-    def get_infile(self, inname):
-        """Returns the input file object"""
-
-        if inname:
-            print('Reading input from %s' % inname, file=sys.stderr)
-            fobj = open(inname, 'rb')
-            self.file_objects.append(fobj)
-        else:
-            print('Reading input from stdin', file=sys.stderr)
-            fobj = sys.stdin
-
-        return fobj
-
-    def get_outfile(self, outname):
-        """Returns the output file object"""
-
-        if outname:
-            print('Will write output to %s' % outname, file=sys.stderr)
-            fobj = open(outname, 'wb')
-            self.file_objects.append(fobj)
-        else:
-            print('Will write output to stdout', file=sys.stderr)
-            fobj = sys.stdout
-
-        return fobj
-
-
-class EncryptBigfileOperation(BigfileOperation):
-    """Encrypts a file to VARBLOCK format."""
-
-    keyname = 'public'
-    description = ('Encrypts a file to an encrypted VARBLOCK file. The file '
-                   'can be larger than the key length, but the output file is only '
-                   'compatible with Python-RSA.')
-    operation = 'encrypt'
-    operation_past = 'encrypted'
-    operation_progressive = 'encrypting'
-
-    def perform_operation(self, infile, outfile, pub_key, cli_args=None):
-        """Encrypts files to VARBLOCK."""
-
-        return rsa.bigfile.encrypt_bigfile(infile, outfile, pub_key)
-
-
-class DecryptBigfileOperation(BigfileOperation):
-    """Decrypts a file in VARBLOCK format."""
-
-    keyname = 'private'
-    description = ('Decrypts an encrypted VARBLOCK file that was encrypted '
-                   'with pyrsa-encrypt-bigfile')
-    operation = 'decrypt'
-    operation_past = 'decrypted'
-    operation_progressive = 'decrypting'
-    key_class = rsa.PrivateKey
-
-    def perform_operation(self, infile, outfile, priv_key, cli_args=None):
-        """Decrypts a VARBLOCK file."""
-
-        return rsa.bigfile.decrypt_bigfile(infile, outfile, priv_key)
-
-
 encrypt = EncryptOperation()
 decrypt = DecryptOperation()
 sign = SignOperation()
 verify = VerifyOperation()
-encrypt_bigfile = EncryptBigfileOperation()
-decrypt_bigfile = DecryptBigfileOperation()
diff --git a/rsa/common.py b/rsa/common.py
index e074334..f7aa2d1 100644
--- a/rsa/common.py
+++ b/rsa/common.py
@@ -14,17 +14,25 @@
 #  See the License for the specific language governing permissions and
 #  limitations under the License.
 
+from rsa._compat import zip
+
 """Common functionality shared by several modules."""
 
 
+class NotRelativePrimeError(ValueError):
+    def __init__(self, a, b, d, msg=None):
+        super(NotRelativePrimeError, self).__init__(
+            msg or "%d and %d are not relatively prime, divider=%i" % (a, b, d))
+        self.a = a
+        self.b = b
+        self.d = d
+
+
 def bit_size(num):
     """
     Number of bits needed to represent a integer excluding any prefix
     0 bits.
 
-    As per definition from https://wiki.python.org/moin/BitManipulation and
-    to match the behavior of the Python 3 API.
-
     Usage::
 
         >>> bit_size(1023)
@@ -41,41 +49,11 @@
     :returns:
         Returns the number of bits in the integer.
     """
-    if num == 0:
-        return 0
-    if num < 0:
-        num = -num
 
-    # Make sure this is an int and not a float.
-    num & 1
-
-    hex_num = "%x" % num
-    return ((len(hex_num) - 1) * 4) + {
-        '0': 0, '1': 1, '2': 2, '3': 2,
-        '4': 3, '5': 3, '6': 3, '7': 3,
-        '8': 4, '9': 4, 'a': 4, 'b': 4,
-        'c': 4, 'd': 4, 'e': 4, 'f': 4,
-    }[hex_num[0]]
-
-
-def _bit_size(number):
-    """
-    Returns the number of bits required to hold a specific long number.
-    """
-    if number < 0:
-        raise ValueError('Only nonnegative numbers possible: %s' % number)
-
-    if number == 0:
-        return 0
-
-    # This works, even with very large numbers. When using math.log(number, 2),
-    # you'll get rounding errors and it'll fail.
-    bits = 0
-    while number:
-        bits += 1
-        number >>= 1
-
-    return bits
+    try:
+        return num.bit_length()
+    except AttributeError:
+        raise TypeError('bit_size(num) only supports integers, not %r' % type(num))
 
 
 def byte_size(number):
@@ -98,11 +76,33 @@
     :returns:
         The number of bytes required to hold a specific long number.
     """
-    quanta, mod = divmod(bit_size(number), 8)
-    if mod or number == 0:
+    if number == 0:
+        return 1
+    return ceil_div(bit_size(number), 8)
+
+
+def ceil_div(num, div):
+    """
+    Returns the ceiling function of a division between `num` and `div`.
+
+    Usage::
+
+        >>> ceil_div(100, 7)
+        15
+        >>> ceil_div(100, 10)
+        10
+        >>> ceil_div(1, 4)
+        1
+
+    :param num: Division's numerator, a number
+    :param div: Division's divisor, a number
+
+    :return: Rounded up result of the division between the parameters.
+    """
+    quanta, mod = divmod(num, div)
+    if mod:
         quanta += 1
     return quanta
-    # return int(math.ceil(bit_size(number) / 8.0))
 
 
 def extended_gcd(a, b):
@@ -131,7 +131,7 @@
 
 
 def inverse(x, n):
-    """Returns x^-1 (mod n)
+    """Returns the inverse of x % n under multiplication, a.k.a x^-1 (mod n)
 
     >>> inverse(7, 4)
     3
@@ -142,7 +142,7 @@
     (divider, inv, _) = extended_gcd(x, n)
 
     if divider != 1:
-        raise ValueError("x (%d) and n (%d) are not relatively prime" % (x, n))
+        raise NotRelativePrimeError(x, n, divider)
 
     return inv
 
diff --git a/rsa/key.py b/rsa/key.py
index 64600a2..1004412 100644
--- a/rsa/key.py
+++ b/rsa/key.py
@@ -34,14 +34,16 @@
 """
 
 import logging
-from rsa._compat import b
+import warnings
 
+from rsa._compat import range
 import rsa.prime
 import rsa.pem
 import rsa.common
 import rsa.randnum
 import rsa.core
 
+
 log = logging.getLogger(__name__)
 DEFAULT_EXPONENT = 65537
 
@@ -56,14 +58,55 @@
         self.e = e
 
     @classmethod
+    def _load_pkcs1_pem(cls, keyfile):
+        """Loads a key in PKCS#1 PEM format, implement in a subclass.
+
+        :param keyfile: contents of a PEM-encoded file that contains
+            the public key.
+        :type keyfile: bytes
+
+        :return: the loaded key
+        :rtype: AbstractKey
+        """
+
+    @classmethod
+    def _load_pkcs1_der(cls, keyfile):
+        """Loads a key in PKCS#1 PEM format, implement in a subclass.
+
+        :param keyfile: contents of a DER-encoded file that contains
+            the public key.
+        :type keyfile: bytes
+
+        :return: the loaded key
+        :rtype: AbstractKey
+        """
+
+    def _save_pkcs1_pem(self):
+        """Saves the key in PKCS#1 PEM format, implement in a subclass.
+
+        :returns: the PEM-encoded key.
+        :rtype: bytes
+        """
+
+    def _save_pkcs1_der(self):
+        """Saves the key in PKCS#1 DER format, implement in a subclass.
+
+        :returns: the DER-encoded key.
+        :rtype: bytes
+        """
+
+    @classmethod
     def load_pkcs1(cls, keyfile, format='PEM'):
         """Loads a key in PKCS#1 DER or PEM format.
 
         :param keyfile: contents of a DER- or PEM-encoded file that contains
-            the public key.
+            the key.
+        :type keyfile: bytes
         :param format: the format of the file to load; 'PEM' or 'DER'
+        :type format: str
 
-        :return: a PublicKey object
+        :return: the loaded key
+        :rtype: AbstractKey
         """
 
         methods = {
@@ -87,10 +130,12 @@
                                                                         formats))
 
     def save_pkcs1(self, format='PEM'):
-        """Saves the public key in PKCS#1 DER or PEM format.
+        """Saves the key in PKCS#1 DER or PEM format.
 
         :param format: the format to save; 'PEM' or 'DER'
-        :returns: the DER- or PEM-encoded public key.
+        :type format: str
+        :returns: the DER- or PEM-encoded key.
+        :rtype: bytes
         """
 
         methods = {
@@ -139,7 +184,7 @@
     This key is also known as the 'encryption key'. It contains the 'n' and 'e'
     values.
 
-    Supports attributes as well as dictionary-like access. Attribute accesss is
+    Supports attributes as well as dictionary-like access. Attribute access is
     faster, though.
 
     >>> PublicKey(5, 3)
@@ -185,6 +230,9 @@
     def __ne__(self, other):
         return not (self == other)
 
+    def __hash__(self):
+        return hash((self.n, self.e))
+
     @classmethod
     def _load_pkcs1_der(cls, keyfile):
         """Loads a key in PKCS#1 DER format.
@@ -215,7 +263,8 @@
     def _save_pkcs1_der(self):
         """Saves the public key in PKCS#1 DER format.
 
-        @returns: the DER-encoded public key.
+        :returns: the DER-encoded public key.
+        :rtype: bytes
         """
 
         from pyasn1.codec.der import encoder
@@ -247,6 +296,7 @@
         """Saves a PKCS#1 PEM-encoded public key file.
 
         :return: contents of a PEM-encoded file that contains the public key.
+        :rtype: bytes
         """
 
         der = self._save_pkcs1_der()
@@ -264,6 +314,7 @@
 
         :param keyfile: contents of a PEM-encoded file that contains the public
             key, from OpenSSL.
+        :type keyfile: bytes
         :return: a PublicKey object
         """
 
@@ -277,6 +328,7 @@
         :param keyfile: contents of a DER-encoded file that contains the public
             key, from OpenSSL.
         :return: a PublicKey object
+        :rtype: bytes
 
         """
 
@@ -298,57 +350,36 @@
     This key is also known as the 'decryption key'. It contains the 'n', 'e',
     'd', 'p', 'q' and other values.
 
-    Supports attributes as well as dictionary-like access. Attribute accesss is
+    Supports attributes as well as dictionary-like access. Attribute access is
     faster, though.
 
     >>> PrivateKey(3247, 65537, 833, 191, 17)
     PrivateKey(3247, 65537, 833, 191, 17)
 
-    exp1, exp2 and coef can be given, but if None or omitted they will be calculated:
+    exp1, exp2 and coef will be calculated:
 
-    >>> pk = PrivateKey(3727264081, 65537, 3349121513, 65063, 57287, exp2=4)
+    >>> pk = PrivateKey(3727264081, 65537, 3349121513, 65063, 57287)
     >>> pk.exp1
     55063
-    >>> pk.exp2  # this is of course not a correct value, but it is the one we passed.
-    4
+    >>> pk.exp2
+    10095
     >>> pk.coef
     50797
 
-    If you give exp1, exp2 or coef, they will be used as-is:
-
-    >>> pk = PrivateKey(1, 2, 3, 4, 5, 6, 7, 8)
-    >>> pk.exp1
-    6
-    >>> pk.exp2
-    7
-    >>> pk.coef
-    8
-
     """
 
     __slots__ = ('n', 'e', 'd', 'p', 'q', 'exp1', 'exp2', 'coef')
 
-    def __init__(self, n, e, d, p, q, exp1=None, exp2=None, coef=None):
+    def __init__(self, n, e, d, p, q):
         AbstractKey.__init__(self, n, e)
         self.d = d
         self.p = p
         self.q = q
 
-        # Calculate the other values if they aren't supplied
-        if exp1 is None:
-            self.exp1 = int(d % (p - 1))
-        else:
-            self.exp1 = exp1
-
-        if exp2 is None:
-            self.exp2 = int(d % (q - 1))
-        else:
-            self.exp2 = exp2
-
-        if coef is None:
-            self.coef = rsa.common.inverse(q, p)
-        else:
-            self.coef = coef
+        # Calculate exponents and coefficient.
+        self.exp1 = int(d % (p - 1))
+        self.exp2 = int(d % (q - 1))
+        self.coef = rsa.common.inverse(q, p)
 
     def __getitem__(self, key):
         return getattr(self, key)
@@ -383,6 +414,9 @@
     def __ne__(self, other):
         return not (self == other)
 
+    def __hash__(self):
+        return hash((self.n, self.e, self.d, self.p, self.q, self.exp1, self.exp2, self.coef))
+
     def blinded_decrypt(self, encrypted):
         """Decrypts the message using blinding to prevent side-channel attacks.
 
@@ -420,6 +454,7 @@
 
         :param keyfile: contents of a DER-encoded file that contains the private
             key.
+        :type keyfile: bytes
         :return: a PrivateKey object
 
         First let's construct a DER encoded key:
@@ -456,13 +491,26 @@
         if priv[0] != 0:
             raise ValueError('Unable to read this file, version %s != 0' % priv[0])
 
-        as_ints = tuple(int(x) for x in priv[1:9])
-        return cls(*as_ints)
+        as_ints = map(int, priv[1:6])
+        key = cls(*as_ints)
+
+        exp1, exp2, coef = map(int, priv[6:9])
+
+        if (key.exp1, key.exp2, key.coef) != (exp1, exp2, coef):
+            warnings.warn(
+                'You have provided a malformed keyfile. Either the exponents '
+                'or the coefficient are incorrect. Using the correct values '
+                'instead.',
+                UserWarning,
+            )
+
+        return key
 
     def _save_pkcs1_der(self):
         """Saves the private key in PKCS#1 DER format.
 
-        @returns: the DER-encoded private key.
+        :returns: the DER-encoded private key.
+        :rtype: bytes
         """
 
         from pyasn1.type import univ, namedtype
@@ -470,15 +518,15 @@
 
         class AsnPrivKey(univ.Sequence):
             componentType = namedtype.NamedTypes(
-                    namedtype.NamedType('version', univ.Integer()),
-                    namedtype.NamedType('modulus', univ.Integer()),
-                    namedtype.NamedType('publicExponent', univ.Integer()),
-                    namedtype.NamedType('privateExponent', univ.Integer()),
-                    namedtype.NamedType('prime1', univ.Integer()),
-                    namedtype.NamedType('prime2', univ.Integer()),
-                    namedtype.NamedType('exponent1', univ.Integer()),
-                    namedtype.NamedType('exponent2', univ.Integer()),
-                    namedtype.NamedType('coefficient', univ.Integer()),
+                namedtype.NamedType('version', univ.Integer()),
+                namedtype.NamedType('modulus', univ.Integer()),
+                namedtype.NamedType('publicExponent', univ.Integer()),
+                namedtype.NamedType('privateExponent', univ.Integer()),
+                namedtype.NamedType('prime1', univ.Integer()),
+                namedtype.NamedType('prime2', univ.Integer()),
+                namedtype.NamedType('exponent1', univ.Integer()),
+                namedtype.NamedType('exponent2', univ.Integer()),
+                namedtype.NamedType('coefficient', univ.Integer()),
             )
 
         # Create the ASN object
@@ -504,20 +552,22 @@
 
         :param keyfile: contents of a PEM-encoded file that contains the private
             key.
+        :type keyfile: bytes
         :return: a PrivateKey object
         """
 
-        der = rsa.pem.load_pem(keyfile, b('RSA PRIVATE KEY'))
+        der = rsa.pem.load_pem(keyfile, b'RSA PRIVATE KEY')
         return cls._load_pkcs1_der(der)
 
     def _save_pkcs1_pem(self):
         """Saves a PKCS#1 PEM-encoded private key file.
 
         :return: contents of a PEM-encoded file that contains the private key.
+        :rtype: bytes
         """
 
         der = self._save_pkcs1_der()
-        return rsa.pem.save_pem(der, b('RSA PRIVATE KEY'))
+        return rsa.pem.save_pem(der, b'RSA PRIVATE KEY')
 
 
 def find_p_q(nbits, getprime_func=rsa.prime.getprime, accurate=True):
@@ -615,9 +665,11 @@
 
     try:
         d = rsa.common.inverse(exponent, phi_n)
-    except ValueError:
-        raise ValueError("e (%d) and phi_n (%d) are not relatively prime" %
-                         (exponent, phi_n))
+    except rsa.common.NotRelativePrimeError as ex:
+        raise rsa.common.NotRelativePrimeError(
+            exponent, phi_n, ex.d,
+            msg="e (%d) and phi_n (%d) are not relatively prime (divider=%i)" %
+                (exponent, phi_n, ex.d))
 
     if (exponent * d) % phi_n != 1:
         raise ValueError("e (%d) and d (%d) are not mult. inv. modulo "
@@ -731,7 +783,7 @@
             if failures:
                 break
 
-            if (count and count % 10 == 0) or count == 1:
+            if (count % 10 == 0 and count) or count == 1:
                 print('%i times' % count)
     except KeyboardInterrupt:
         print('Aborted')
diff --git a/rsa/machine_size.py b/rsa/machine_size.py
new file mode 100644
index 0000000..2a871b8
--- /dev/null
+++ b/rsa/machine_size.py
@@ -0,0 +1,74 @@
+# -*- coding: utf-8 -*-
+#
+#  Copyright 2011 Sybren A. Stüvel <sybren@stuvel.eu>
+#
+#  Licensed under the Apache License, Version 2.0 (the "License");
+#  you may not use this file except in compliance with the License.
+#  You may obtain a copy of the License at
+#
+#      https://www.apache.org/licenses/LICENSE-2.0
+#
+#  Unless required by applicable law or agreed to in writing, software
+#  distributed under the License is distributed on an "AS IS" BASIS,
+#  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+#  See the License for the specific language governing permissions and
+#  limitations under the License.
+
+"""Detection of 32-bit and 64-bit machines and byte alignment."""
+
+import sys
+
+MAX_INT = sys.maxsize
+MAX_INT64 = (1 << 63) - 1
+MAX_INT32 = (1 << 31) - 1
+MAX_INT16 = (1 << 15) - 1
+
+# Determine the word size of the processor.
+if MAX_INT == MAX_INT64:
+    # 64-bit processor.
+    MACHINE_WORD_SIZE = 64
+elif MAX_INT == MAX_INT32:
+    # 32-bit processor.
+    MACHINE_WORD_SIZE = 32
+else:
+    # Else we just assume 64-bit processor keeping up with modern times.
+    MACHINE_WORD_SIZE = 64
+
+
+def get_word_alignment(num, force_arch=64,
+                       _machine_word_size=MACHINE_WORD_SIZE):
+    """
+    Returns alignment details for the given number based on the platform
+    Python is running on.
+
+    :param num:
+        Unsigned integral number.
+    :param force_arch:
+        If you don't want to use 64-bit unsigned chunks, set this to
+        anything other than 64. 32-bit chunks will be preferred then.
+        Default 64 will be used when on a 64-bit machine.
+    :param _machine_word_size:
+        (Internal) The machine word size used for alignment.
+    :returns:
+        4-tuple::
+
+            (word_bits, word_bytes,
+             max_uint, packing_format_type)
+    """
+    max_uint64 = 0xffffffffffffffff
+    max_uint32 = 0xffffffff
+    max_uint16 = 0xffff
+    max_uint8 = 0xff
+
+    if force_arch == 64 and _machine_word_size >= 64 and num > max_uint32:
+        # 64-bit unsigned integer.
+        return 64, 8, max_uint64, "Q"
+    elif num > max_uint16:
+        # 32-bit unsigned integer
+        return 32, 4, max_uint32, "L"
+    elif num > max_uint8:
+        # 16-bit unsigned integer.
+        return 16, 2, max_uint16, "H"
+    else:
+        # 8-bit unsigned integer.
+        return 8, 1, max_uint8, "B"
diff --git a/rsa/parallel.py b/rsa/parallel.py
index edc924f..a3fe312 100644
--- a/rsa/parallel.py
+++ b/rsa/parallel.py
@@ -28,6 +28,7 @@
 
 import multiprocessing as mp
 
+from rsa._compat import range
 import rsa.prime
 import rsa.randnum
 
@@ -94,7 +95,7 @@
         if failures:
             break
 
-        if count and count % 10 == 0:
+        if count % 10 == 0 and count:
             print('%i times' % count)
 
     print('Doctests done')
diff --git a/rsa/pem.py b/rsa/pem.py
index 0f68cb2..2ddfae8 100644
--- a/rsa/pem.py
+++ b/rsa/pem.py
@@ -17,19 +17,20 @@
 """Functions that load and write PEM-encoded files."""
 
 import base64
-from rsa._compat import b, is_bytes
+
+from rsa._compat import is_bytes, range
 
 
 def _markers(pem_marker):
     """
-    Returns the start and end PEM markers
+    Returns the start and end PEM markers, as bytes.
     """
 
-    if is_bytes(pem_marker):
-        pem_marker = pem_marker.decode('utf-8')
+    if not is_bytes(pem_marker):
+        pem_marker = pem_marker.encode('ascii')
 
-    return (b('-----BEGIN %s-----' % pem_marker),
-            b('-----END %s-----' % pem_marker))
+    return (b'-----BEGIN ' + pem_marker + b'-----',
+            b'-----END ' + pem_marker + b'-----')
 
 
 def load_pem(contents, pem_marker):
@@ -81,7 +82,7 @@
             break
 
         # Load fields
-        if b(':') in line:
+        if b':' in line:
             continue
 
         pem_lines.append(line)
@@ -94,7 +95,7 @@
         raise ValueError('No PEM end marker "%s" found' % pem_end)
 
     # Base64-decode the contents
-    pem = b('').join(pem_lines)
+    pem = b''.join(pem_lines)
     return base64.standard_b64decode(pem)
 
 
@@ -106,13 +107,13 @@
         when your file has '-----BEGIN RSA PRIVATE KEY-----' and
         '-----END RSA PRIVATE KEY-----' markers.
 
-    :return: the base64-encoded content between the start and end markers.
+    :return: the base64-encoded content between the start and end markers, as bytes.
 
     """
 
     (pem_start, pem_end) = _markers(pem_marker)
 
-    b64 = base64.standard_b64encode(contents).replace(b('\n'), b(''))
+    b64 = base64.standard_b64encode(contents).replace(b'\n', b'')
     pem_lines = [pem_start]
 
     for block_start in range(0, len(b64), 64):
@@ -120,6 +121,6 @@
         pem_lines.append(block)
 
     pem_lines.append(pem_end)
-    pem_lines.append(b(''))
+    pem_lines.append(b'')
 
-    return b('\n').join(pem_lines)
+    return b'\n'.join(pem_lines)
diff --git a/rsa/pkcs1.py b/rsa/pkcs1.py
index 28f0dc5..84f0e3b 100644
--- a/rsa/pkcs1.py
+++ b/rsa/pkcs1.py
@@ -31,21 +31,23 @@
 import hashlib
 import os
 
-from rsa._compat import b
+from rsa._compat import range
 from rsa import common, transform, core
 
 # ASN.1 codes that describe the hash algorithm used.
 HASH_ASN1 = {
-    'MD5': b('\x30\x20\x30\x0c\x06\x08\x2a\x86\x48\x86\xf7\x0d\x02\x05\x05\x00\x04\x10'),
-    'SHA-1': b('\x30\x21\x30\x09\x06\x05\x2b\x0e\x03\x02\x1a\x05\x00\x04\x14'),
-    'SHA-256': b('\x30\x31\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x01\x05\x00\x04\x20'),
-    'SHA-384': b('\x30\x41\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x02\x05\x00\x04\x30'),
-    'SHA-512': b('\x30\x51\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x03\x05\x00\x04\x40'),
+    'MD5': b'\x30\x20\x30\x0c\x06\x08\x2a\x86\x48\x86\xf7\x0d\x02\x05\x05\x00\x04\x10',
+    'SHA-1': b'\x30\x21\x30\x09\x06\x05\x2b\x0e\x03\x02\x1a\x05\x00\x04\x14',
+    'SHA-224': b'\x30\x2d\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x04\x05\x00\x04\x1c',
+    'SHA-256': b'\x30\x31\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x01\x05\x00\x04\x20',
+    'SHA-384': b'\x30\x41\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x02\x05\x00\x04\x30',
+    'SHA-512': b'\x30\x51\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x03\x05\x00\x04\x40',
 }
 
 HASH_METHODS = {
     'MD5': hashlib.md5,
     'SHA-1': hashlib.sha1,
+    'SHA-224': hashlib.sha224,
     'SHA-256': hashlib.sha256,
     'SHA-384': hashlib.sha384,
     'SHA-512': hashlib.sha512,
@@ -87,7 +89,7 @@
                             ' space for %i' % (msglength, max_msglength))
 
     # Get random padding
-    padding = b('')
+    padding = b''
     padding_length = target_length - msglength - 3
 
     # We remove 0-bytes, so we'll end up with less padding than we've asked for,
@@ -99,15 +101,15 @@
         # after removing the 0-bytes. This increases the chance of getting
         # enough bytes, especially when needed_bytes is small
         new_padding = os.urandom(needed_bytes + 5)
-        new_padding = new_padding.replace(b('\x00'), b(''))
+        new_padding = new_padding.replace(b'\x00', b'')
         padding = padding + new_padding[:needed_bytes]
 
     assert len(padding) == padding_length
 
-    return b('').join([b('\x00\x02'),
-                       padding,
-                       b('\x00'),
-                       message])
+    return b''.join([b'\x00\x02',
+                     padding,
+                     b'\x00',
+                     message])
 
 
 def _pad_for_signing(message, target_length):
@@ -138,10 +140,10 @@
 
     padding_length = target_length - msglength - 3
 
-    return b('').join([b('\x00\x01'),
-                       padding_length * b('\xff'),
-                       b('\x00'),
-                       message])
+    return b''.join([b'\x00\x01',
+                     padding_length * b'\xff',
+                     b'\x00',
+                     message])
 
 
 def encrypt(message, pub_key):
@@ -233,19 +235,53 @@
     cleartext = transform.int2bytes(decrypted, blocksize)
 
     # If we can't find the cleartext marker, decryption failed.
-    if cleartext[0:2] != b('\x00\x02'):
+    if cleartext[0:2] != b'\x00\x02':
         raise DecryptionError('Decryption failed')
 
     # Find the 00 separator between the padding and the message
     try:
-        sep_idx = cleartext.index(b('\x00'), 2)
+        sep_idx = cleartext.index(b'\x00', 2)
     except ValueError:
         raise DecryptionError('Decryption failed')
 
     return cleartext[sep_idx + 1:]
 
 
-def sign(message, priv_key, hash):
+def sign_hash(hash_value, priv_key, hash_method):
+    """Signs a precomputed hash with the private key.
+
+    Hashes the message, then signs the hash with the given key. This is known
+    as a "detached signature", because the message itself isn't altered.
+
+    :param hash_value: A precomputed hash to sign (ignores message). Should be set to
+        None if needing to hash and sign message.
+    :param priv_key: the :py:class:`rsa.PrivateKey` to sign with
+    :param hash_method: the hash method used on the message. Use 'MD5', 'SHA-1',
+        'SHA-224', SHA-256', 'SHA-384' or 'SHA-512'.
+    :return: a message signature block.
+    :raise OverflowError: if the private key is too small to contain the
+        requested hash.
+
+    """
+
+    # Get the ASN1 code for this hash method
+    if hash_method not in HASH_ASN1:
+        raise ValueError('Invalid hash method: %s' % hash_method)
+    asn1code = HASH_ASN1[hash_method]
+
+    # Encrypt the hash with the private key
+    cleartext = asn1code + hash_value
+    keylength = common.byte_size(priv_key.n)
+    padded = _pad_for_signing(cleartext, keylength)
+
+    payload = transform.bytes2int(padded)
+    encrypted = priv_key.blinded_encrypt(payload)
+    block = transform.int2bytes(encrypted, keylength)
+
+    return block
+
+
+def sign(message, priv_key, hash_method):
     """Signs the message with the private key.
 
     Hashes the message, then signs the hash with the given key. This is known
@@ -255,32 +291,16 @@
         object. If ``message`` has a ``read()`` method, it is assumed to be a
         file-like object.
     :param priv_key: the :py:class:`rsa.PrivateKey` to sign with
-    :param hash: the hash method used on the message. Use 'MD5', 'SHA-1',
-        'SHA-256', 'SHA-384' or 'SHA-512'.
+    :param hash_method: the hash method used on the message. Use 'MD5', 'SHA-1',
+        'SHA-224', SHA-256', 'SHA-384' or 'SHA-512'.
     :return: a message signature block.
     :raise OverflowError: if the private key is too small to contain the
         requested hash.
 
     """
 
-    # Get the ASN1 code for this hash method
-    if hash not in HASH_ASN1:
-        raise ValueError('Invalid hash method: %s' % hash)
-    asn1code = HASH_ASN1[hash]
-
-    # Calculate the hash
-    hash = _hash(message, hash)
-
-    # Encrypt the hash with the private key
-    cleartext = asn1code + hash
-    keylength = common.byte_size(priv_key.n)
-    padded = _pad_for_signing(cleartext, keylength)
-
-    payload = transform.bytes2int(padded)
-    encrypted = priv_key.blinded_encrypt(payload)
-    block = transform.int2bytes(encrypted, keylength)
-
-    return block
+    msg_hash = compute_hash(message, hash_method)
+    return sign_hash(msg_hash, priv_key, hash_method)
 
 
 def verify(message, signature, pub_key):
@@ -294,6 +314,7 @@
     :param signature: the signature block, as created with :py:func:`rsa.sign`.
     :param pub_key: the :py:class:`rsa.PublicKey` of the person signing the message.
     :raise VerificationError: when the signature doesn't match the message.
+    :returns: the name of the used hash.
 
     """
 
@@ -304,7 +325,7 @@
 
     # Get the hash method
     method_name = _find_method_hash(clearsig)
-    message_hash = _hash(message, method_name)
+    message_hash = compute_hash(message, method_name)
 
     # Reconstruct the expected padded hash
     cleartext = HASH_ASN1[method_name] + message_hash
@@ -314,10 +335,50 @@
     if expected != clearsig:
         raise VerificationError('Verification failed')
 
-    return True
+    return method_name
 
 
-def _hash(message, method_name):
+def find_signature_hash(signature, pub_key):
+    """Returns the hash name detected from the signature.
+
+    If you also want to verify the message, use :py:func:`rsa.verify()` instead.
+    It also returns the name of the used hash.
+
+    :param signature: the signature block, as created with :py:func:`rsa.sign`.
+    :param pub_key: the :py:class:`rsa.PublicKey` of the person signing the message.
+    :returns: the name of the used hash.
+    """
+
+    keylength = common.byte_size(pub_key.n)
+    encrypted = transform.bytes2int(signature)
+    decrypted = core.decrypt_int(encrypted, pub_key.e, pub_key.n)
+    clearsig = transform.int2bytes(decrypted, keylength)
+
+    return _find_method_hash(clearsig)
+
+
+def yield_fixedblocks(infile, blocksize):
+    """Generator, yields each block of ``blocksize`` bytes in the input file.
+
+    :param infile: file to read and separate in blocks.
+    :param blocksize: block size in bytes.
+    :returns: a generator that yields the contents of each block
+    """
+
+    while True:
+        block = infile.read(blocksize)
+
+        read_bytes = len(block)
+        if read_bytes == 0:
+            break
+
+        yield block
+
+        if read_bytes < blocksize:
+            break
+
+
+def compute_hash(message, method_name):
     """Returns the message digest.
 
     :param message: the signed message. Can be an 8-bit string or a file-like
@@ -335,11 +396,8 @@
     hasher = method()
 
     if hasattr(message, 'read') and hasattr(message.read, '__call__'):
-        # Late import to prevent DeprecationWarnings.
-        from . import varblock
-
         # read as 1K blocks
-        for block in varblock.yield_fixedblocks(message, 1024):
+        for block in yield_fixedblocks(message, 1024):
             hasher.update(block)
     else:
         # hash the message object itself.
@@ -375,7 +433,7 @@
         if failures:
             break
 
-        if count and count % 100 == 0:
+        if count % 100 == 0 and count:
             print('%i times' % count)
 
     print('Doctests done')
diff --git a/rsa/pkcs1_v2.py b/rsa/pkcs1_v2.py
new file mode 100644
index 0000000..5f9c7dd
--- /dev/null
+++ b/rsa/pkcs1_v2.py
@@ -0,0 +1,103 @@
+# -*- coding: utf-8 -*-
+#
+#  Copyright 2011 Sybren A. Stüvel <sybren@stuvel.eu>
+#
+#  Licensed under the Apache License, Version 2.0 (the "License");
+#  you may not use this file except in compliance with the License.
+#  You may obtain a copy of the License at
+#
+#      https://www.apache.org/licenses/LICENSE-2.0
+#
+#  Unless required by applicable law or agreed to in writing, software
+#  distributed under the License is distributed on an "AS IS" BASIS,
+#  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+#  See the License for the specific language governing permissions and
+#  limitations under the License.
+
+"""Functions for PKCS#1 version 2 encryption and signing
+
+This module implements certain functionality from PKCS#1 version 2. Main
+documentation is RFC 2437: https://tools.ietf.org/html/rfc2437
+"""
+
+from rsa._compat import range
+from rsa import (
+    common,
+    pkcs1,
+    transform,
+)
+
+
+def mgf1(seed, length, hasher='SHA-1'):
+    """
+    MGF1 is a Mask Generation Function based on a hash function.
+
+    A mask generation function takes an octet string of variable length and a
+    desired output length as input, and outputs an octet string of the desired
+    length. The plaintext-awareness of RSAES-OAEP relies on the random nature of
+    the output of the mask generation function, which in turn relies on the
+    random nature of the underlying hash.
+
+    :param bytes seed: seed from which mask is generated, an octet string
+    :param int length: intended length in octets of the mask, at most 2^32(hLen)
+    :param str hasher: hash function (hLen denotes the length in octets of the hash
+        function output)
+
+    :return: mask, an octet string of length `length`
+    :rtype: bytes
+
+    :raise OverflowError: when `length` is too large for the specified `hasher`
+    :raise ValueError: when specified `hasher` is invalid
+    """
+
+    try:
+        hash_length = pkcs1.HASH_METHODS[hasher]().digest_size
+    except KeyError:
+        raise ValueError(
+            'Invalid `hasher` specified. Please select one of: {hash_list}'.format(
+                hash_list=', '.join(sorted(pkcs1.HASH_METHODS.keys()))
+            )
+        )
+
+    # If l > 2^32(hLen), output "mask too long" and stop.
+    if length > (2**32 * hash_length):
+        raise OverflowError(
+            "Desired length should be at most 2**32 times the hasher's output "
+            "length ({hash_length} for {hasher} function)".format(
+                hash_length=hash_length,
+                hasher=hasher,
+            )
+        )
+
+    # Looping `counter` from 0 to ceil(l / hLen)-1, build `output` based on the
+    # hashes formed by (`seed` + C), being `C` an octet string of length 4
+    # generated by converting `counter` with the primitive I2OSP
+    output = b''.join(
+        pkcs1.compute_hash(
+            seed + transform.int2bytes(counter, fill_size=4),
+            method_name=hasher,
+        )
+        for counter in range(common.ceil_div(length, hash_length) + 1)
+    )
+
+    # Output the leading `length` octets of `output` as the octet string mask.
+    return output[:length]
+
+
+__all__ = [
+    'mgf1',
+]
+
+if __name__ == '__main__':
+    print('Running doctests 1000x or until failure')
+    import doctest
+
+    for count in range(1000):
+        (failures, tests) = doctest.testmod()
+        if failures:
+            break
+
+        if count % 100 == 0 and count:
+            print('%i times' % count)
+
+    print('Doctests done')
diff --git a/rsa/prime.py b/rsa/prime.py
index 6f23f9d..3d63542 100644
--- a/rsa/prime.py
+++ b/rsa/prime.py
@@ -20,6 +20,8 @@
 Roberto Tamassia, 2002.
 """
 
+from rsa._compat import range
+import rsa.common
 import rsa.randnum
 
 __all__ = ['getprime', 'are_relatively_prime']
@@ -37,6 +39,32 @@
     return p
 
 
+def get_primality_testing_rounds(number):
+    """Returns minimum number of rounds for Miller-Rabing primality testing,
+    based on number bitsize.
+
+    According to NIST FIPS 186-4, Appendix C, Table C.3, minimum number of
+    rounds of M-R testing, using an error probability of 2 ** (-100), for
+    different p, q bitsizes are:
+      * p, q bitsize: 512; rounds: 7
+      * p, q bitsize: 1024; rounds: 4
+      * p, q bitsize: 1536; rounds: 3
+    See: http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf
+    """
+
+    # Calculate number bitsize.
+    bitsize = rsa.common.bit_size(number)
+    # Set number of rounds.
+    if bitsize >= 1536:
+        return 3
+    if bitsize >= 1024:
+        return 4
+    if bitsize >= 512:
+        return 7
+    # For smaller bitsizes, set arbitrary number of rounds.
+    return 10
+
+
 def miller_rabin_primality_testing(n, k):
     """Calculates whether n is composite (which is always correct) or prime
     (which theoretically is incorrect with error probability 4**-k), by
@@ -69,7 +97,7 @@
     # Test k witnesses.
     for _ in range(k):
         # Generate random integer a, where 2 <= a <= (n - 2)
-        a = rsa.randnum.randint(n - 4) + 2
+        a = rsa.randnum.randint(n - 3) + 1
 
         x = pow(a, d, n)
         if x == 1 or x == n - 1:
@@ -99,26 +127,21 @@
     False
     >>> is_prime(41)
     True
-    >>> [x for x in range(901, 1000) if is_prime(x)]
-    [907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
     """
 
     # Check for small numbers.
     if number < 10:
-        return number in [2, 3, 5, 7]
+        return number in {2, 3, 5, 7}
 
     # Check for even numbers.
     if not (number & 1):
         return False
 
-    # According to NIST FIPS 186-4, Appendix C, Table C.3, minimum number of
-    # rounds of M-R testing, using an error probability of 2 ** (-100), for
-    # different p, q bitsizes are:
-    #   * p, q bitsize: 512; rounds: 7
-    #   * p, q bitsize: 1024; rounds: 4
-    #   * p, q bitsize: 1536; rounds: 3
-    # See: http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf
-    return miller_rabin_primality_testing(number, 7)
+    # Calculate minimum number of rounds.
+    k = get_primality_testing_rounds(number)
+
+    # Run primality testing with (minimum + 1) rounds.
+    return miller_rabin_primality_testing(number, k + 1)
 
 
 def getprime(nbits):
@@ -172,7 +195,7 @@
         if failures:
             break
 
-        if count and count % 100 == 0:
+        if count % 100 == 0 and count:
             print('%i times' % count)
 
     print('Doctests done')
diff --git a/rsa/randnum.py b/rsa/randnum.py
index 3c788a5..310acaa 100644
--- a/rsa/randnum.py
+++ b/rsa/randnum.py
@@ -88,7 +88,7 @@
         if value <= maxvalue:
             break
 
-        if tries and tries % 10 == 0:
+        if tries % 10 == 0 and tries:
             # After a lot of tries to get the right number of bits but still
             # smaller than maxvalue, decrease the number of bits by 1. That'll
             # dramatically increase the chances to get a large enough number.
diff --git a/rsa/transform.py b/rsa/transform.py
index 16061a9..628d0af 100644
--- a/rsa/transform.py
+++ b/rsa/transform.py
@@ -21,20 +21,11 @@
 
 from __future__ import absolute_import
 
-try:
-    # We'll use psyco if available on 32-bit architectures to speed up code.
-    # Using psyco (if available) cuts down the execution time on Python 2.5
-    # at least by half.
-    import psyco
-
-    psyco.full()
-except ImportError:
-    pass
-
 import binascii
 from struct import pack
-from rsa import common
-from rsa._compat import is_integer, b, byte, get_word_alignment, ZERO_BYTE, EMPTY_BYTE
+
+from rsa._compat import byte, is_integer
+from rsa import common, machine_size
 
 
 def bytes2int(raw_bytes):
@@ -92,7 +83,7 @@
     # Do some bounds checking
     if number == 0:
         needed_bytes = 1
-        raw_bytes = [ZERO_BYTE]
+        raw_bytes = [b'\x00']
     else:
         needed_bytes = common.byte_size(number)
         raw_bytes = []
@@ -110,14 +101,14 @@
 
     # Pad with zeroes to fill the block
     if block_size and block_size > 0:
-        padding = (block_size - needed_bytes) * ZERO_BYTE
+        padding = (block_size - needed_bytes) * b'\x00'
     else:
-        padding = EMPTY_BYTE
+        padding = b''
 
-    return padding + EMPTY_BYTE.join(raw_bytes)
+    return padding + b''.join(raw_bytes)
 
 
-def bytes_leading(raw_bytes, needle=ZERO_BYTE):
+def bytes_leading(raw_bytes, needle=b'\x00'):
     """
     Finds the number of prefixed byte occurrences in the haystack.
 
@@ -126,7 +117,7 @@
     :param raw_bytes:
         Raw bytes.
     :param needle:
-        The byte to count. Default \000.
+        The byte to count. Default \x00.
     :returns:
         The number of leading needle bytes.
     """
@@ -186,11 +177,11 @@
     # Ensure these are integers.
     number & 1
 
-    raw_bytes = b('')
+    raw_bytes = b''
 
     # Pack the integer one machine word at a time into bytes.
     num = number
-    word_bits, _, max_uint, pack_type = get_word_alignment(num)
+    word_bits, _, max_uint, pack_type = machine_size.get_word_alignment(num)
     pack_format = ">%s" % pack_type
     while num > 0:
         raw_bytes = pack(pack_format, num & max_uint) + raw_bytes
@@ -198,7 +189,7 @@
     # Obtain the index of the first non-zero byte.
     zero_leading = bytes_leading(raw_bytes)
     if number == 0:
-        raw_bytes = ZERO_BYTE
+        raw_bytes = b'\x00'
     # De-padding.
     raw_bytes = raw_bytes[zero_leading:]
 
@@ -209,12 +200,12 @@
                     "Need %d bytes for number, but fill size is %d" %
                     (length, fill_size)
             )
-        raw_bytes = raw_bytes.rjust(fill_size, ZERO_BYTE)
+        raw_bytes = raw_bytes.rjust(fill_size, b'\x00')
     elif chunk_size and chunk_size > 0:
         remainder = length % chunk_size
         if remainder:
             padding_size = chunk_size - remainder
-            raw_bytes = raw_bytes.rjust(length + padding_size, ZERO_BYTE)
+            raw_bytes = raw_bytes.rjust(length + padding_size, b'\x00')
     return raw_bytes
 
 
diff --git a/rsa/varblock.py b/rsa/varblock.py
deleted file mode 100644
index 1c8d839..0000000
--- a/rsa/varblock.py
+++ /dev/null
@@ -1,179 +0,0 @@
-# -*- coding: utf-8 -*-
-#
-#  Copyright 2011 Sybren A. Stüvel <sybren@stuvel.eu>
-#
-#  Licensed under the Apache License, Version 2.0 (the "License");
-#  you may not use this file except in compliance with the License.
-#  You may obtain a copy of the License at
-#
-#      https://www.apache.org/licenses/LICENSE-2.0
-#
-#  Unless required by applicable law or agreed to in writing, software
-#  distributed under the License is distributed on an "AS IS" BASIS,
-#  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-#  See the License for the specific language governing permissions and
-#  limitations under the License.
-
-"""VARBLOCK file support
-
-.. deprecated:: 3.4
-
-    The VARBLOCK format is NOT recommended for general use, has been deprecated since
-    Python-RSA 3.4, and will be removed in a future release. It's vulnerable to a
-    number of attacks:
-
-    1. decrypt/encrypt_bigfile() does not implement `Authenticated encryption`_ nor
-       uses MACs to verify messages before decrypting public key encrypted messages.
-
-    2. decrypt/encrypt_bigfile() does not use hybrid encryption (it uses plain RSA)
-       and has no method for chaining, so block reordering is possible.
-
-    See `issue #19 on Github`_ for more information.
-
-.. _Authenticated encryption: https://en.wikipedia.org/wiki/Authenticated_encryption
-.. _issue #19 on Github: https://github.com/sybrenstuvel/python-rsa/issues/13
-
-
-The VARBLOCK file format is as follows, where || denotes byte concatenation:
-
-    FILE := VERSION || BLOCK || BLOCK ...
-
-    BLOCK := LENGTH || DATA
-
-    LENGTH := varint-encoded length of the subsequent data. Varint comes from
-    Google Protobuf, and encodes an integer into a variable number of bytes.
-    Each byte uses the 7 lowest bits to encode the value. The highest bit set
-    to 1 indicates the next byte is also part of the varint. The last byte will
-    have this bit set to 0.
-
-This file format is called the VARBLOCK format, in line with the varint format
-used to denote the block sizes.
-
-"""
-
-import warnings
-
-from rsa._compat import byte, b
-
-ZERO_BYTE = b('\x00')
-VARBLOCK_VERSION = 1
-
-warnings.warn("The 'rsa.varblock' module was deprecated in Python-RSA version "
-              "3.4 due to security issues in the VARBLOCK format. See "
-              "https://github.com/sybrenstuvel/python-rsa/issues/13 for more information.",
-              DeprecationWarning)
-
-
-def read_varint(infile):
-    """Reads a varint from the file.
-
-    When the first byte to be read indicates EOF, (0, 0) is returned. When an
-    EOF occurs when at least one byte has been read, an EOFError exception is
-    raised.
-
-    :param infile: the file-like object to read from. It should have a read()
-        method.
-    :returns: (varint, length), the read varint and the number of read bytes.
-    """
-
-    varint = 0
-    read_bytes = 0
-
-    while True:
-        char = infile.read(1)
-        if len(char) == 0:
-            if read_bytes == 0:
-                return 0, 0
-            raise EOFError('EOF while reading varint, value is %i so far' %
-                           varint)
-
-        byte = ord(char)
-        varint += (byte & 0x7F) << (7 * read_bytes)
-
-        read_bytes += 1
-
-        if not byte & 0x80:
-            return varint, read_bytes
-
-
-def write_varint(outfile, value):
-    """Writes a varint to a file.
-
-    :param outfile: the file-like object to write to. It should have a write()
-        method.
-    :returns: the number of written bytes.
-    """
-
-    # there is a big difference between 'write the value 0' (this case) and
-    # 'there is nothing left to write' (the false-case of the while loop)
-
-    if value == 0:
-        outfile.write(ZERO_BYTE)
-        return 1
-
-    written_bytes = 0
-    while value > 0:
-        to_write = value & 0x7f
-        value >>= 7
-
-        if value > 0:
-            to_write |= 0x80
-
-        outfile.write(byte(to_write))
-        written_bytes += 1
-
-    return written_bytes
-
-
-def yield_varblocks(infile):
-    """Generator, yields each block in the input file.
-
-    :param infile: file to read, is expected to have the VARBLOCK format as
-        described in the module's docstring.
-    @yields the contents of each block.
-    """
-
-    # Check the version number
-    first_char = infile.read(1)
-    if len(first_char) == 0:
-        raise EOFError('Unable to read VARBLOCK version number')
-
-    version = ord(first_char)
-    if version != VARBLOCK_VERSION:
-        raise ValueError('VARBLOCK version %i not supported' % version)
-
-    while True:
-        (block_size, read_bytes) = read_varint(infile)
-
-        # EOF at block boundary, that's fine.
-        if read_bytes == 0 and block_size == 0:
-            break
-
-        block = infile.read(block_size)
-
-        read_size = len(block)
-        if read_size != block_size:
-            raise EOFError('Block size is %i, but could read only %i bytes' %
-                           (block_size, read_size))
-
-        yield block
-
-
-def yield_fixedblocks(infile, blocksize):
-    """Generator, yields each block of ``blocksize`` bytes in the input file.
-
-    :param infile: file to read and separate in blocks.
-    :returns: a generator that yields the contents of each block
-    """
-
-    while True:
-        block = infile.read(blocksize)
-
-        read_bytes = len(block)
-        if read_bytes == 0:
-            break
-
-        yield block
-
-        if read_bytes < blocksize:
-            break
diff --git a/setup.cfg b/setup.cfg
index a38d4c4..ed8a958 100644
--- a/setup.cfg
+++ b/setup.cfg
@@ -1,5 +1,5 @@
-[nosetests]
-verbosity=2
-
 [bdist_wheel]
 universal = 1
+
+[metadata]
+license_file = LICENSE
diff --git a/setup.py b/setup.py
index cd73fe8..18f339e 100755
--- a/setup.py
+++ b/setup.py
@@ -16,10 +16,15 @@
 
 from setuptools import setup
 
+with open('README.md') as f:
+    long_description = f.read()
+
 if __name__ == '__main__':
     setup(name='rsa',
-          version='3.4.2',
+          version='4.0',
           description='Pure-Python RSA implementation',
+          long_description=long_description,
+          long_description_content_type='text/markdown',
           author='Sybren A. Stuvel',
           author_email='sybren@stuvel.eu',
           maintainer='Sybren A. Stuvel',
@@ -36,12 +41,14 @@
               'Operating System :: OS Independent',
               'Programming Language :: Python',
               'Programming Language :: Python :: 2',
-              'Programming Language :: Python :: 2.6',
               'Programming Language :: Python :: 2.7',
               'Programming Language :: Python :: 3',
-              'Programming Language :: Python :: 3.3',
               'Programming Language :: Python :: 3.4',
               'Programming Language :: Python :: 3.5',
+              'Programming Language :: Python :: 3.6',
+              'Programming Language :: Python :: 3.7',
+              'Programming Language :: Python :: Implementation :: CPython',
+              'Programming Language :: Python :: Implementation :: PyPy',
               'Topic :: Security :: Cryptography',
           ],
           install_requires=[
@@ -54,8 +61,6 @@
               'pyrsa-decrypt = rsa.cli:decrypt',
               'pyrsa-sign = rsa.cli:sign',
               'pyrsa-verify = rsa.cli:verify',
-              'pyrsa-encrypt-bigfile = rsa.cli:encrypt_bigfile',
-              'pyrsa-decrypt-bigfile = rsa.cli:decrypt_bigfile',
           ]},
 
           )
diff --git a/speed.sh b/speed.sh
index 72cc9ad..e06d825 100755
--- a/speed.sh
+++ b/speed.sh
@@ -28,9 +28,7 @@
 
 python_versions="
     pypy
-    python2.6
     python2.7
-    python3.3
     python3.4
     python3.5
 "
@@ -43,12 +41,3 @@
         "$version" -mtimeit -s'from rsa.transform import _int2bytes; n = 1<<4096' '_int2bytes(n)'
     fi
 done
-
-echo "bit_size speed test"
-for version in $python_versions; do
-    if check_command "$version"; then
-        echo "$version"
-        "$version" -mtimeit -s'from rsa.common import bit_size; n = 1<<4096' 'bit_size(n)'
-        "$version" -mtimeit -s'from rsa.common import _bit_size; n = 1<<4096' '_bit_size(n)'
-    fi
-done
diff --git a/tests/test_bigfile.py b/tests/test_bigfile.py
deleted file mode 100644
index 70278dc..0000000
--- a/tests/test_bigfile.py
+++ /dev/null
@@ -1,73 +0,0 @@
-# -*- coding: utf-8 -*-
-#
-#  Copyright 2011 Sybren A. Stüvel <sybren@stuvel.eu>
-#
-#  Licensed under the Apache License, Version 2.0 (the "License");
-#  you may not use this file except in compliance with the License.
-#  You may obtain a copy of the License at
-#
-#      https://www.apache.org/licenses/LICENSE-2.0
-#
-#  Unless required by applicable law or agreed to in writing, software
-#  distributed under the License is distributed on an "AS IS" BASIS,
-#  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-#  See the License for the specific language governing permissions and
-#  limitations under the License.
-
-"""Tests block operations."""
-
-from rsa._compat import b
-
-try:
-    from StringIO import StringIO as BytesIO
-except ImportError:
-    from io import BytesIO
-import unittest
-
-import rsa
-from rsa import bigfile, varblock, pkcs1
-
-
-class BigfileTest(unittest.TestCase):
-    def test_encrypt_decrypt_bigfile(self):
-        # Expected block size + 11 bytes padding
-        pub_key, priv_key = rsa.newkeys((6 + 11) * 8)
-
-        # Encrypt the file
-        message = b('123456Sybren')
-        infile = BytesIO(message)
-        outfile = BytesIO()
-
-        bigfile.encrypt_bigfile(infile, outfile, pub_key)
-
-        # Test
-        crypto = outfile.getvalue()
-
-        cryptfile = BytesIO(crypto)
-        clearfile = BytesIO()
-
-        bigfile.decrypt_bigfile(cryptfile, clearfile, priv_key)
-        self.assertEquals(clearfile.getvalue(), message)
-
-        # We have 2x6 bytes in the message, so that should result in two
-        # bigfile.
-        cryptfile.seek(0)
-        varblocks = list(varblock.yield_varblocks(cryptfile))
-        self.assertEqual(2, len(varblocks))
-
-    def test_sign_verify_bigfile(self):
-        # Large enough to store MD5-sum and ASN.1 code for MD5
-        pub_key, priv_key = rsa.newkeys((34 + 11) * 8)
-
-        # Sign the file
-        msgfile = BytesIO(b('123456Sybren'))
-        signature = pkcs1.sign(msgfile, priv_key, 'MD5')
-
-        # Check the signature
-        msgfile.seek(0)
-        self.assertTrue(pkcs1.verify(msgfile, signature, pub_key))
-
-        # Alter the message, re-check
-        msgfile = BytesIO(b('123456sybren'))
-        self.assertRaises(pkcs1.VerificationError,
-                          pkcs1.verify, msgfile, signature, pub_key)
diff --git a/tests/test_cli.py b/tests/test_cli.py
new file mode 100644
index 0000000..7ce57eb
--- /dev/null
+++ b/tests/test_cli.py
@@ -0,0 +1,296 @@
+"""
+Unit tests for CLI entry points.
+"""
+
+from __future__ import print_function
+
+import unittest
+import sys
+import functools
+from contextlib import contextmanager
+
+import os
+from io import StringIO, BytesIO
+
+import rsa
+import rsa.cli
+import rsa.util
+from rsa._compat import PY2
+
+
+def make_buffer():
+    if PY2:
+        return BytesIO()
+    buf = StringIO()
+    buf.buffer = BytesIO()
+    return buf
+
+
+def get_bytes_out(out):
+    if PY2:
+        # Python 2.x writes 'str' to stdout
+        return out.getvalue()
+    # Python 3.x writes 'bytes' to stdout.buffer
+    return out.buffer.getvalue()
+
+
+@contextmanager
+def captured_output():
+    """Captures output to stdout and stderr"""
+
+    new_out, new_err = make_buffer(), make_buffer()
+    old_out, old_err = sys.stdout, sys.stderr
+    try:
+        sys.stdout, sys.stderr = new_out, new_err
+        yield new_out, new_err
+    finally:
+        sys.stdout, sys.stderr = old_out, old_err
+
+
+@contextmanager
+def cli_args(*new_argv):
+    """Updates sys.argv[1:] for a single test."""
+
+    old_args = sys.argv[:]
+    sys.argv[1:] = [str(arg) for arg in new_argv]
+
+    try:
+        yield
+    finally:
+        sys.argv[1:] = old_args
+
+
+def remove_if_exists(fname):
+    """Removes a file if it exists."""
+
+    if os.path.exists(fname):
+        os.unlink(fname)
+
+
+def cleanup_files(*filenames):
+    """Makes sure the files don't exist when the test runs, and deletes them afterward."""
+
+    def remove():
+        for fname in filenames:
+            remove_if_exists(fname)
+
+    def decorator(func):
+        @functools.wraps(func)
+        def wrapper(*args, **kwargs):
+            remove()
+            try:
+                return func(*args, **kwargs)
+            finally:
+                remove()
+
+        return wrapper
+
+    return decorator
+
+
+class AbstractCliTest(unittest.TestCase):
+    @classmethod
+    def setUpClass(cls):
+        # Ensure there is a key to use
+        cls.pub_key, cls.priv_key = rsa.newkeys(512)
+        cls.pub_fname = '%s.pub' % cls.__name__
+        cls.priv_fname = '%s.key' % cls.__name__
+
+        with open(cls.pub_fname, 'wb') as outfile:
+            outfile.write(cls.pub_key.save_pkcs1())
+
+        with open(cls.priv_fname, 'wb') as outfile:
+            outfile.write(cls.priv_key.save_pkcs1())
+
+    @classmethod
+    def tearDownClass(cls):
+        if hasattr(cls, 'pub_fname'):
+            remove_if_exists(cls.pub_fname)
+        if hasattr(cls, 'priv_fname'):
+            remove_if_exists(cls.priv_fname)
+
+    def assertExits(self, status_code, func, *args, **kwargs):
+        try:
+            func(*args, **kwargs)
+        except SystemExit as ex:
+            if status_code == ex.code:
+                return
+            self.fail('SystemExit() raised by %r, but exited with code %r, expected %r' % (
+                func, ex.code, status_code))
+        else:
+            self.fail('SystemExit() not raised by %r' % func)
+
+
+class KeygenTest(AbstractCliTest):
+    def test_keygen_no_args(self):
+        with cli_args():
+            self.assertExits(1, rsa.cli.keygen)
+
+    def test_keygen_priv_stdout(self):
+        with captured_output() as (out, err):
+            with cli_args(128):
+                rsa.cli.keygen()
+
+        lines = get_bytes_out(out).splitlines()
+        self.assertEqual(b'-----BEGIN RSA PRIVATE KEY-----', lines[0])
+        self.assertEqual(b'-----END RSA PRIVATE KEY-----', lines[-1])
+
+        # The key size should be shown on stderr
+        self.assertTrue('128-bit key' in err.getvalue())
+
+    @cleanup_files('test_cli_privkey_out.pem')
+    def test_keygen_priv_out_pem(self):
+        with captured_output() as (out, err):
+            with cli_args('--out=test_cli_privkey_out.pem', '--form=PEM', 128):
+                rsa.cli.keygen()
+
+        # The key size should be shown on stderr
+        self.assertTrue('128-bit key' in err.getvalue())
+
+        # The output file should be shown on stderr
+        self.assertTrue('test_cli_privkey_out.pem' in err.getvalue())
+
+        # If we can load the file as PEM, it's good enough.
+        with open('test_cli_privkey_out.pem', 'rb') as pemfile:
+            rsa.PrivateKey.load_pkcs1(pemfile.read())
+
+    @cleanup_files('test_cli_privkey_out.der')
+    def test_keygen_priv_out_der(self):
+        with captured_output() as (out, err):
+            with cli_args('--out=test_cli_privkey_out.der', '--form=DER', 128):
+                rsa.cli.keygen()
+
+        # The key size should be shown on stderr
+        self.assertTrue('128-bit key' in err.getvalue())
+
+        # The output file should be shown on stderr
+        self.assertTrue('test_cli_privkey_out.der' in err.getvalue())
+
+        # If we can load the file as der, it's good enough.
+        with open('test_cli_privkey_out.der', 'rb') as derfile:
+            rsa.PrivateKey.load_pkcs1(derfile.read(), format='DER')
+
+    @cleanup_files('test_cli_privkey_out.pem', 'test_cli_pubkey_out.pem')
+    def test_keygen_pub_out_pem(self):
+        with captured_output() as (out, err):
+            with cli_args('--out=test_cli_privkey_out.pem',
+                          '--pubout=test_cli_pubkey_out.pem',
+                          '--form=PEM', 256):
+                rsa.cli.keygen()
+
+        # The key size should be shown on stderr
+        self.assertTrue('256-bit key' in err.getvalue())
+
+        # The output files should be shown on stderr
+        self.assertTrue('test_cli_privkey_out.pem' in err.getvalue())
+        self.assertTrue('test_cli_pubkey_out.pem' in err.getvalue())
+
+        # If we can load the file as PEM, it's good enough.
+        with open('test_cli_pubkey_out.pem', 'rb') as pemfile:
+            rsa.PublicKey.load_pkcs1(pemfile.read())
+
+
+class EncryptDecryptTest(AbstractCliTest):
+    def test_empty_decrypt(self):
+        with cli_args():
+            self.assertExits(1, rsa.cli.decrypt)
+
+    def test_empty_encrypt(self):
+        with cli_args():
+            self.assertExits(1, rsa.cli.encrypt)
+
+    @cleanup_files('encrypted.txt', 'cleartext.txt')
+    def test_encrypt_decrypt(self):
+        with open('cleartext.txt', 'wb') as outfile:
+            outfile.write(b'Hello cleartext RSA users!')
+
+        with cli_args('-i', 'cleartext.txt', '--out=encrypted.txt', self.pub_fname):
+            with captured_output():
+                rsa.cli.encrypt()
+
+        with cli_args('-i', 'encrypted.txt', self.priv_fname):
+            with captured_output() as (out, err):
+                rsa.cli.decrypt()
+
+        # We should have the original cleartext on stdout now.
+        output = get_bytes_out(out)
+        self.assertEqual(b'Hello cleartext RSA users!', output)
+
+    @cleanup_files('encrypted.txt', 'cleartext.txt')
+    def test_encrypt_decrypt_unhappy(self):
+        with open('cleartext.txt', 'wb') as outfile:
+            outfile.write(b'Hello cleartext RSA users!')
+
+        with cli_args('-i', 'cleartext.txt', '--out=encrypted.txt', self.pub_fname):
+            with captured_output():
+                rsa.cli.encrypt()
+
+        # Change a few bytes in the encrypted stream.
+        with open('encrypted.txt', 'r+b') as encfile:
+            encfile.seek(40)
+            encfile.write(b'hahaha')
+
+        with cli_args('-i', 'encrypted.txt', self.priv_fname):
+            with captured_output() as (out, err):
+                self.assertRaises(rsa.DecryptionError, rsa.cli.decrypt)
+
+
+class SignVerifyTest(AbstractCliTest):
+    def test_empty_verify(self):
+        with cli_args():
+            self.assertExits(1, rsa.cli.verify)
+
+    def test_empty_sign(self):
+        with cli_args():
+            self.assertExits(1, rsa.cli.sign)
+
+    @cleanup_files('signature.txt', 'cleartext.txt')
+    def test_sign_verify(self):
+        with open('cleartext.txt', 'wb') as outfile:
+            outfile.write(b'Hello RSA users!')
+
+        with cli_args('-i', 'cleartext.txt', '--out=signature.txt', self.priv_fname, 'SHA-256'):
+            with captured_output():
+                rsa.cli.sign()
+
+        with cli_args('-i', 'cleartext.txt', self.pub_fname, 'signature.txt'):
+            with captured_output() as (out, err):
+                rsa.cli.verify()
+
+        self.assertFalse(b'Verification OK' in get_bytes_out(out))
+
+    @cleanup_files('signature.txt', 'cleartext.txt')
+    def test_sign_verify_unhappy(self):
+        with open('cleartext.txt', 'wb') as outfile:
+            outfile.write(b'Hello RSA users!')
+
+        with cli_args('-i', 'cleartext.txt', '--out=signature.txt', self.priv_fname, 'SHA-256'):
+            with captured_output():
+                rsa.cli.sign()
+
+        # Change a few bytes in the cleartext file.
+        with open('cleartext.txt', 'r+b') as encfile:
+            encfile.seek(6)
+            encfile.write(b'DSA')
+
+        with cli_args('-i', 'cleartext.txt', self.pub_fname, 'signature.txt'):
+            with captured_output() as (out, err):
+                self.assertExits('Verification failed.', rsa.cli.verify)
+
+
+class PrivatePublicTest(AbstractCliTest):
+    """Test CLI command to convert a private to a public key."""
+
+    @cleanup_files('test_private_to_public.pem')
+    def test_private_to_public(self):
+
+        with cli_args('-i', self.priv_fname, '-o', 'test_private_to_public.pem'):
+            with captured_output():
+                rsa.util.private_to_public()
+
+        # Check that the key is indeed valid.
+        with open('test_private_to_public.pem', 'rb') as pemfile:
+            key = rsa.PublicKey.load_pkcs1(pemfile.read())
+
+        self.assertEqual(self.priv_key.n, key.n)
+        self.assertEqual(self.priv_key.e, key.e)
diff --git a/tests/test_common.py b/tests/test_common.py
index 453dcc8..af13695 100644
--- a/tests/test_common.py
+++ b/tests/test_common.py
@@ -17,14 +17,14 @@
 
 import unittest
 import struct
-from rsa._compat import byte, b
-from rsa.common import byte_size, bit_size, _bit_size
+from rsa._compat import byte
+from rsa.common import byte_size, bit_size, inverse
 
 
 class TestByte(unittest.TestCase):
     def test_values(self):
-        self.assertEqual(byte(0), b('\x00'))
-        self.assertEqual(byte(255), b('\xff'))
+        self.assertEqual(byte(0), b'\x00')
+        self.assertEqual(byte(255), b'\xff')
 
     def test_struct_error_when_out_of_bounds(self):
         self.assertRaises(struct.error, byte, 256)
@@ -69,9 +69,28 @@
         self.assertEqual(bit_size((1 << 1024) + 1), 1025)
         self.assertEqual(bit_size((1 << 1024) - 1), 1024)
 
-        self.assertEqual(_bit_size(1023), 10)
-        self.assertEqual(_bit_size(1024), 11)
-        self.assertEqual(_bit_size(1025), 11)
-        self.assertEqual(_bit_size(1 << 1024), 1025)
-        self.assertEqual(_bit_size((1 << 1024) + 1), 1025)
-        self.assertEqual(_bit_size((1 << 1024) - 1), 1024)
+    def test_negative_values(self):
+        self.assertEqual(bit_size(-1023), 10)
+        self.assertEqual(bit_size(-1024), 11)
+        self.assertEqual(bit_size(-1025), 11)
+        self.assertEqual(bit_size(-1 << 1024), 1025)
+        self.assertEqual(bit_size(-((1 << 1024) + 1)), 1025)
+        self.assertEqual(bit_size(-((1 << 1024) - 1)), 1024)
+
+    def test_bad_type(self):
+        self.assertRaises(TypeError, bit_size, [])
+        self.assertRaises(TypeError, bit_size, ())
+        self.assertRaises(TypeError, bit_size, dict())
+        self.assertRaises(TypeError, bit_size, "")
+        self.assertRaises(TypeError, bit_size, None)
+        self.assertRaises(TypeError, bit_size, 0.0)
+
+
+class TestInverse(unittest.TestCase):
+    def test_normal(self):
+        self.assertEqual(3, inverse(7, 4))
+        self.assertEqual(9, inverse(5, 11))
+
+    def test_not_relprime(self):
+        self.assertRaises(ValueError, inverse, 4, 8)
+        self.assertRaises(ValueError, inverse, 25, 5)
diff --git a/tests/test_compat.py b/tests/test_compat.py
index 8cbf101..62e933f 100644
--- a/tests/test_compat.py
+++ b/tests/test_compat.py
@@ -17,10 +17,12 @@
 import unittest
 import struct
 
-from rsa._compat import is_bytes, byte
+from rsa._compat import byte, is_bytes, range, xor_bytes
 
 
 class TestByte(unittest.TestCase):
+    """Tests for single bytes."""
+
     def test_byte(self):
         for i in range(256):
             byt = byte(i)
@@ -30,3 +32,49 @@
     def test_raises_StructError_on_overflow(self):
         self.assertRaises(struct.error, byte, 256)
         self.assertRaises(struct.error, byte, -1)
+
+    def test_byte_literal(self):
+        self.assertIsInstance(b'abc', bytes)
+
+
+class TestBytes(unittest.TestCase):
+    """Tests for bytes objects."""
+
+    def setUp(self):
+        self.b1 = b'\xff\xff\xff\xff'
+        self.b2 = b'\x00\x00\x00\x00'
+        self.b3 = b'\xf0\xf0\xf0\xf0'
+        self.b4 = b'\x4d\x23\xca\xe2'
+        self.b5 = b'\x9b\x61\x3b\xdc'
+        self.b6 = b'\xff\xff'
+
+        self.byte_strings = (self.b1, self.b2, self.b3, self.b4, self.b5, self.b6)
+
+    def test_xor_bytes(self):
+        self.assertEqual(xor_bytes(self.b1, self.b2), b'\xff\xff\xff\xff')
+        self.assertEqual(xor_bytes(self.b1, self.b3), b'\x0f\x0f\x0f\x0f')
+        self.assertEqual(xor_bytes(self.b1, self.b4), b'\xb2\xdc\x35\x1d')
+        self.assertEqual(xor_bytes(self.b1, self.b5), b'\x64\x9e\xc4\x23')
+        self.assertEqual(xor_bytes(self.b2, self.b3), b'\xf0\xf0\xf0\xf0')
+        self.assertEqual(xor_bytes(self.b2, self.b4), b'\x4d\x23\xca\xe2')
+        self.assertEqual(xor_bytes(self.b2, self.b5), b'\x9b\x61\x3b\xdc')
+        self.assertEqual(xor_bytes(self.b3, self.b4), b'\xbd\xd3\x3a\x12')
+        self.assertEqual(xor_bytes(self.b3, self.b5), b'\x6b\x91\xcb\x2c')
+        self.assertEqual(xor_bytes(self.b4, self.b5), b'\xd6\x42\xf1\x3e')
+
+    def test_xor_bytes_length(self):
+        self.assertEqual(xor_bytes(self.b1, self.b6), b'\x00\x00')
+        self.assertEqual(xor_bytes(self.b2, self.b6), b'\xff\xff')
+        self.assertEqual(xor_bytes(self.b3, self.b6), b'\x0f\x0f')
+        self.assertEqual(xor_bytes(self.b4, self.b6), b'\xb2\xdc')
+        self.assertEqual(xor_bytes(self.b5, self.b6), b'\x64\x9e')
+        self.assertEqual(xor_bytes(self.b6, b''), b'')
+
+    def test_xor_bytes_commutative(self):
+        for first in self.byte_strings:
+            for second in self.byte_strings:
+                min_length = min(len(first), len(second))
+                result = xor_bytes(first, second)
+
+                self.assertEqual(result, xor_bytes(second, first))
+                self.assertEqual(len(result), min_length)
diff --git a/tests/test_key.py b/tests/test_key.py
index 0e62f55..9db30ce 100644
--- a/tests/test_key.py
+++ b/tests/test_key.py
@@ -40,3 +40,40 @@
 
         self.assertEqual(0x10001, priv.e)
         self.assertEqual(0x10001, pub.e)
+
+    def test_exponents_coefficient_calculation(self):
+        pk = rsa.key.PrivateKey(3727264081, 65537, 3349121513, 65063, 57287)
+
+        self.assertEqual(pk.exp1, 55063)
+        self.assertEqual(pk.exp2, 10095)
+        self.assertEqual(pk.coef, 50797)
+
+    def test_custom_getprime_func(self):
+        # List of primes to test with, in order [p, q, p, q, ....]
+        # By starting with two of the same primes, we test that this is
+        # properly rejected.
+        primes = [64123, 64123, 64123, 50957, 39317, 33107]
+
+        def getprime(_):
+            return primes.pop(0)
+
+        # This exponent will cause two other primes to be generated.
+        exponent = 136407
+
+        (p, q, e, d) = rsa.key.gen_keys(64,
+                                        accurate=False,
+                                        getprime_func=getprime,
+                                        exponent=exponent)
+        self.assertEqual(39317, p)
+        self.assertEqual(33107, q)
+
+
+class HashTest(unittest.TestCase):
+    """Test hashing of keys"""
+
+    def test_hash_possible(self):
+        priv, pub = rsa.key.newkeys(16)
+
+        # This raises a TypeError when hashing isn't possible.
+        hash(priv)
+        hash(pub)
diff --git a/tests/test_load_save_keys.py b/tests/test_load_save_keys.py
index 6f374cf..55bd5a4 100644
--- a/tests/test_load_save_keys.py
+++ b/tests/test_load_save_keys.py
@@ -14,62 +14,63 @@
 #  See the License for the specific language governing permissions and
 #  limitations under the License.
 
-'''Unittest for saving and loading keys.'''
+"""Unittest for saving and loading keys."""
 
 import base64
-import unittest
+import mock
 import os.path
 import pickle
+import unittest
+import warnings
 
-from rsa._compat import b
-
+from rsa._compat import range
 import rsa.key
 
-B64PRIV_DER = b('MC4CAQACBQDeKYlRAgMBAAECBQDHn4npAgMA/icCAwDfxwIDANcXAgInbwIDAMZt')
+B64PRIV_DER = b'MC4CAQACBQDeKYlRAgMBAAECBQDHn4npAgMA/icCAwDfxwIDANcXAgInbwIDAMZt'
 PRIVATE_DER = base64.standard_b64decode(B64PRIV_DER)
 
-B64PUB_DER = b('MAwCBQDeKYlRAgMBAAE=')
+B64PUB_DER = b'MAwCBQDeKYlRAgMBAAE='
 PUBLIC_DER = base64.standard_b64decode(B64PUB_DER)
 
-PRIVATE_PEM = b('''
+PRIVATE_PEM = b'''\
 -----BEGIN CONFUSING STUFF-----
 Cruft before the key
 
 -----BEGIN RSA PRIVATE KEY-----
 Comment: something blah
 
-%s
+''' + B64PRIV_DER + b'''
 -----END RSA PRIVATE KEY-----
 
 Stuff after the key
 -----END CONFUSING STUFF-----
-''' % B64PRIV_DER.decode("utf-8"))
+'''
 
-CLEAN_PRIVATE_PEM = b('''\
+CLEAN_PRIVATE_PEM = b'''\
 -----BEGIN RSA PRIVATE KEY-----
-%s
+''' + B64PRIV_DER + b'''
 -----END RSA PRIVATE KEY-----
-''' % B64PRIV_DER.decode("utf-8"))
+'''
 
-PUBLIC_PEM = b('''
+PUBLIC_PEM = b'''\
 -----BEGIN CONFUSING STUFF-----
 Cruft before the key
 
 -----BEGIN RSA PUBLIC KEY-----
 Comment: something blah
 
-%s
+''' + B64PUB_DER + b'''
 -----END RSA PUBLIC KEY-----
 
 Stuff after the key
 -----END CONFUSING STUFF-----
-''' % B64PUB_DER.decode("utf-8"))
+'''
 
-CLEAN_PUBLIC_PEM = b('''\
+CLEAN_PUBLIC_PEM = b'''\
 -----BEGIN RSA PUBLIC KEY-----
-%s
+''' + B64PUB_DER + b'''
 -----END RSA PUBLIC KEY-----
-''' % B64PUB_DER.decode("utf-8"))
+'''
 
 
 class DerTest(unittest.TestCase):
@@ -82,6 +83,39 @@
         expected = rsa.key.PrivateKey(3727264081, 65537, 3349121513, 65063, 57287)
 
         self.assertEqual(expected, key)
+        self.assertEqual(key.exp1, 55063)
+        self.assertEqual(key.exp2, 10095)
+        self.assertEqual(key.coef, 50797)
+
+    @mock.patch('pyasn1.codec.der.decoder.decode')
+    def test_load_malformed_private_key(self, der_decode):
+        """Test loading malformed private DER keys."""
+
+        # Decode returns an invalid exp2 value.
+        der_decode.return_value = (
+            [0, 3727264081, 65537, 3349121513, 65063, 57287, 55063, 0, 50797],
+            0,
+        )
+
+        with warnings.catch_warnings(record=True) as w:
+            # Always print warnings
+            warnings.simplefilter('always')
+
+            # Load 3 keys
+            for _ in range(3):
+                key = rsa.key.PrivateKey.load_pkcs1(PRIVATE_DER, 'DER')
+
+            # Check that 3 warnings were generated.
+            self.assertEqual(3, len(w))
+
+            for warning in w:
+                self.assertTrue(issubclass(warning.category, UserWarning))
+                self.assertIn('malformed', str(warning.message))
+
+        # Check that we are creating the key with correct values
+        self.assertEqual(key.exp1, 55063)
+        self.assertEqual(key.exp2, 10095)
+        self.assertEqual(key.coef, 50797)
 
     def test_save_private_key(self):
         """Test saving private DER keys."""
@@ -89,6 +123,7 @@
         key = rsa.key.PrivateKey(3727264081, 65537, 3349121513, 65063, 57287)
         der = key.save_pkcs1('DER')
 
+        self.assertIsInstance(der, bytes)
         self.assertEqual(PRIVATE_DER, der)
 
     def test_load_public_key(self):
@@ -105,6 +140,7 @@
         key = rsa.key.PublicKey(3727264081, 65537)
         der = key.save_pkcs1('DER')
 
+        self.assertIsInstance(der, bytes)
         self.assertEqual(PUBLIC_DER, der)
 
 
@@ -118,6 +154,9 @@
         expected = rsa.key.PrivateKey(3727264081, 65537, 3349121513, 65063, 57287)
 
         self.assertEqual(expected, key)
+        self.assertEqual(key.exp1, 55063)
+        self.assertEqual(key.exp2, 10095)
+        self.assertEqual(key.coef, 50797)
 
     def test_save_private_key(self):
         """Test saving private PEM files."""
@@ -125,6 +164,7 @@
         key = rsa.key.PrivateKey(3727264081, 65537, 3349121513, 65063, 57287)
         pem = key.save_pkcs1('PEM')
 
+        self.assertIsInstance(pem, bytes)
         self.assertEqual(CLEAN_PRIVATE_PEM, pem)
 
     def test_load_public_key(self):
@@ -141,6 +181,7 @@
         key = rsa.key.PublicKey(3727264081, 65537)
         pem = key.save_pkcs1('PEM')
 
+        self.assertIsInstance(pem, bytes)
         self.assertEqual(CLEAN_PUBLIC_PEM, pem)
 
     def test_load_from_disk(self):
diff --git a/tests/test_pem.py b/tests/test_pem.py
index 952ec79..5fb9600 100644
--- a/tests/test_pem.py
+++ b/tests/test_pem.py
@@ -17,7 +17,7 @@
 
 import unittest
 
-from rsa._compat import b
+from rsa._compat import is_bytes
 from rsa.pem import _markers
 import rsa.key
 
@@ -49,8 +49,8 @@
 class TestMarkers(unittest.TestCase):
     def test_values(self):
         self.assertEqual(_markers('RSA PRIVATE KEY'),
-                         (b('-----BEGIN RSA PRIVATE KEY-----'),
-                          b('-----END RSA PRIVATE KEY-----')))
+                         (b'-----BEGIN RSA PRIVATE KEY-----',
+                          b'-----END RSA PRIVATE KEY-----'))
 
 
 class TestBytesAndStrings(unittest.TestCase):
@@ -72,3 +72,31 @@
         key = rsa.key.PrivateKey.load_pkcs1(private_key_pem.encode('ascii'))
         self.assertEqual(prime1, key.p)
         self.assertEqual(prime2, key.q)
+
+
+class TestByteOutput(unittest.TestCase):
+    """Tests that PEM and DER are returned as bytes."""
+
+    def test_bytes_public(self):
+        key = rsa.key.PublicKey.load_pkcs1_openssl_pem(public_key_pem)
+        self.assertTrue(is_bytes(key.save_pkcs1(format='DER')))
+        self.assertTrue(is_bytes(key.save_pkcs1(format='PEM')))
+
+    def test_bytes_private(self):
+        key = rsa.key.PrivateKey.load_pkcs1(private_key_pem)
+        self.assertTrue(is_bytes(key.save_pkcs1(format='DER')))
+        self.assertTrue(is_bytes(key.save_pkcs1(format='PEM')))
+
+
+class TestByteInput(unittest.TestCase):
+    """Tests that PEM and DER can be loaded from bytes."""
+
+    def test_bytes_public(self):
+        key = rsa.key.PublicKey.load_pkcs1_openssl_pem(public_key_pem.encode('ascii'))
+        self.assertTrue(is_bytes(key.save_pkcs1(format='DER')))
+        self.assertTrue(is_bytes(key.save_pkcs1(format='PEM')))
+
+    def test_bytes_private(self):
+        key = rsa.key.PrivateKey.load_pkcs1(private_key_pem.encode('ascii'))
+        self.assertTrue(is_bytes(key.save_pkcs1(format='DER')))
+        self.assertTrue(is_bytes(key.save_pkcs1(format='PEM')))
diff --git a/tests/test_pkcs1.py b/tests/test_pkcs1.py
index 39555f6..5377b30 100644
--- a/tests/test_pkcs1.py
+++ b/tests/test_pkcs1.py
@@ -21,7 +21,7 @@
 
 import rsa
 from rsa import pkcs1
-from rsa._compat import byte, b, is_bytes
+from rsa._compat import byte, is_bytes
 
 
 class BinaryTest(unittest.TestCase):
@@ -48,7 +48,8 @@
         a = encrypted[5]
         if is_bytes(a):
             a = ord(a)
-        encrypted = encrypted[:5] + byte(a + 1) + encrypted[6:]
+        altered_a = (a + 1) % 256
+        encrypted = encrypted[:5] + byte(altered_a) + encrypted[6:]
 
         self.assertRaises(pkcs1.DecryptionError, pkcs1.decrypt, encrypted,
                           self.priv)
@@ -72,27 +73,32 @@
     def test_sign_verify(self):
         """Test happy flow of sign and verify"""
 
-        message = b('je moeder')
-        print("\tMessage:   %r" % message)
-
+        message = b'je moeder'
         signature = pkcs1.sign(message, self.priv, 'SHA-256')
-        print("\tSignature: %r" % signature)
 
-        self.assertTrue(pkcs1.verify(message, signature, self.pub))
+        self.assertEqual('SHA-256', pkcs1.verify(message, signature, self.pub))
+
+    def test_find_signature_hash(self):
+        """Test happy flow of sign and find_signature_hash"""
+
+        message = b'je moeder'
+        signature = pkcs1.sign(message, self.priv, 'SHA-256')
+
+        self.assertEqual('SHA-256', pkcs1.find_signature_hash(signature, self.pub))
 
     def test_alter_message(self):
         """Altering the message should let the verification fail."""
 
-        signature = pkcs1.sign(b('je moeder'), self.priv, 'SHA-256')
+        signature = pkcs1.sign(b'je moeder', self.priv, 'SHA-256')
         self.assertRaises(pkcs1.VerificationError, pkcs1.verify,
-                          b('mijn moeder'), signature, self.pub)
+                          b'mijn moeder', signature, self.pub)
 
     def test_sign_different_key(self):
         """Signing with another key should let the verification fail."""
 
         (otherpub, _) = rsa.newkeys(512)
 
-        message = b('je moeder')
+        message = b'je moeder'
         signature = pkcs1.sign(message, self.priv, 'SHA-256')
         self.assertRaises(pkcs1.VerificationError, pkcs1.verify,
                           message, signature, otherpub)
@@ -105,3 +111,24 @@
         signature2 = pkcs1.sign(message, self.priv, 'SHA-1')
 
         self.assertEqual(signature1, signature2)
+
+    def test_split_hash_sign(self):
+        """Hashing and then signing should match with directly signing the message. """
+
+        message = b'je moeder'
+        msg_hash = pkcs1.compute_hash(message, 'SHA-256')
+        signature1 = pkcs1.sign_hash(msg_hash, self.priv, 'SHA-256')
+
+        # Calculate the signature using the unified method
+        signature2 = pkcs1.sign(message, self.priv, 'SHA-256')
+
+        self.assertEqual(signature1, signature2)
+
+    def test_hash_sign_verify(self):
+        """Test happy flow of hash, sign, and verify"""
+
+        message = b'je moeder'
+        msg_hash = pkcs1.compute_hash(message, 'SHA-224')
+        signature = pkcs1.sign_hash(msg_hash, self.priv, 'SHA-224')
+
+        self.assertTrue(pkcs1.verify(message, signature, self.pub))
diff --git a/tests/test_pkcs1_v2.py b/tests/test_pkcs1_v2.py
new file mode 100644
index 0000000..1d8f001
--- /dev/null
+++ b/tests/test_pkcs1_v2.py
@@ -0,0 +1,83 @@
+# -*- coding: utf-8 -*-
+#
+#  Copyright 2011 Sybren A. Stüvel <sybren@stuvel.eu>
+#
+#  Licensed under the Apache License, Version 2.0 (the "License");
+#  you may not use this file except in compliance with the License.
+#  You may obtain a copy of the License at
+#
+#      https://www.apache.org/licenses/LICENSE-2.0
+#
+#  Unless required by applicable law or agreed to in writing, software
+#  distributed under the License is distributed on an "AS IS" BASIS,
+#  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+#  See the License for the specific language governing permissions and
+#  limitations under the License.
+
+"""Tests PKCS #1 version 2 functionality.
+
+Most of the mocked values come from the test vectors found at:
+http://www.itomorrowmag.com/emc-plus/rsa-labs/standards-initiatives/pkcs-rsa-cryptography-standard.htm
+"""
+
+import unittest
+
+from rsa import pkcs1_v2
+
+
+class MGFTest(unittest.TestCase):
+    def test_oaep_int_db_mask(self):
+        seed = (
+            b'\xaa\xfd\x12\xf6\x59\xca\xe6\x34\x89\xb4\x79\xe5\x07\x6d\xde\xc2'
+            b'\xf0\x6c\xb5\x8f'
+        )
+        db = (
+            b'\xda\x39\xa3\xee\x5e\x6b\x4b\x0d\x32\x55\xbf\xef\x95\x60\x18\x90'
+            b'\xaf\xd8\x07\x09\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
+            b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
+            b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
+            b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
+            b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01\xd4\x36\xe9\x95\x69'
+            b'\xfd\x32\xa7\xc8\xa0\x5b\xbc\x90\xd3\x2c\x49'
+        )
+        masked_db = (
+            b'\xdc\xd8\x7d\x5c\x68\xf1\xee\xa8\xf5\x52\x67\xc3\x1b\x2e\x8b\xb4'
+            b'\x25\x1f\x84\xd7\xe0\xb2\xc0\x46\x26\xf5\xaf\xf9\x3e\xdc\xfb\x25'
+            b'\xc9\xc2\xb3\xff\x8a\xe1\x0e\x83\x9a\x2d\xdb\x4c\xdc\xfe\x4f\xf4'
+            b'\x77\x28\xb4\xa1\xb7\xc1\x36\x2b\xaa\xd2\x9a\xb4\x8d\x28\x69\xd5'
+            b'\x02\x41\x21\x43\x58\x11\x59\x1b\xe3\x92\xf9\x82\xfb\x3e\x87\xd0'
+            b'\x95\xae\xb4\x04\x48\xdb\x97\x2f\x3a\xc1\x4f\x7b\xc2\x75\x19\x52'
+            b'\x81\xce\x32\xd2\xf1\xb7\x6d\x4d\x35\x3e\x2d'
+        )
+
+        # dbMask = MGF(seed, length(DB))
+        db_mask = pkcs1_v2.mgf1(seed, length=len(db))
+        expected_db_mask = (
+            b'\x06\xe1\xde\xb2\x36\x9a\xa5\xa5\xc7\x07\xd8\x2c\x8e\x4e\x93\x24'
+            b'\x8a\xc7\x83\xde\xe0\xb2\xc0\x46\x26\xf5\xaf\xf9\x3e\xdc\xfb\x25'
+            b'\xc9\xc2\xb3\xff\x8a\xe1\x0e\x83\x9a\x2d\xdb\x4c\xdc\xfe\x4f\xf4'
+            b'\x77\x28\xb4\xa1\xb7\xc1\x36\x2b\xaa\xd2\x9a\xb4\x8d\x28\x69\xd5'
+            b'\x02\x41\x21\x43\x58\x11\x59\x1b\xe3\x92\xf9\x82\xfb\x3e\x87\xd0'
+            b'\x95\xae\xb4\x04\x48\xdb\x97\x2f\x3a\xc1\x4e\xaf\xf4\x9c\x8c\x3b'
+            b'\x7c\xfc\x95\x1a\x51\xec\xd1\xdd\xe6\x12\x64'
+        )
+
+        self.assertEqual(db_mask, expected_db_mask)
+
+        # seedMask = MGF(maskedDB, length(seed))
+        seed_mask = pkcs1_v2.mgf1(masked_db, length=len(seed))
+        expected_seed_mask = (
+            b'\x41\x87\x0b\x5a\xb0\x29\xe6\x57\xd9\x57\x50\xb5\x4c\x28\x3c\x08'
+            b'\x72\x5d\xbe\xa9'
+        )
+
+        self.assertEqual(seed_mask, expected_seed_mask)
+
+    def test_invalid_hasher(self):
+        """Tests an invalid hasher generates an exception"""
+        with self.assertRaises(ValueError):
+            pkcs1_v2.mgf1(b'\x06\xe1\xde\xb2', length=8, hasher='SHA2')
+
+    def test_invalid_length(self):
+        with self.assertRaises(OverflowError):
+            pkcs1_v2.mgf1(b'\x06\xe1\xde\xb2', length=2**50)
diff --git a/tests/test_prime.py b/tests/test_prime.py
index a47c3f2..f3bda9b 100644
--- a/tests/test_prime.py
+++ b/tests/test_prime.py
@@ -18,7 +18,9 @@
 
 import unittest
 
+from rsa._compat import range
 import rsa.prime
+import rsa.randnum
 
 
 class PrimeTest(unittest.TestCase):
@@ -42,3 +44,67 @@
         # Test around the 50th millionth known prime.
         self.assertTrue(rsa.prime.is_prime(982451653))
         self.assertFalse(rsa.prime.is_prime(982451653 * 961748941))
+
+    def test_miller_rabin_primality_testing(self):
+        """Uses monkeypatching to ensure certain random numbers.
+
+        This allows us to predict/control the code path.
+        """
+
+        randints = []
+
+        def fake_randint(maxvalue):
+            return randints.pop(0)
+
+        orig_randint = rsa.randnum.randint
+        rsa.randnum.randint = fake_randint
+        try:
+            # 'n is composite'
+            randints.append(2630484832)  # causes the 'n is composite' case with n=3784949785
+            self.assertEqual(False, rsa.prime.miller_rabin_primality_testing(2787998641, 7))
+            self.assertEqual([], randints)
+
+            # 'Exit inner loop and continue with next witness'
+            randints.extend([
+                2119139098,  # causes 'Exit inner loop and continue with next witness'
+                # the next witnesses for the above case:
+                3051067716, 3603501763, 3230895847, 3687808133, 3760099987, 4026931495, 3022471882,
+            ])
+            self.assertEqual(True, rsa.prime.miller_rabin_primality_testing(2211417913,
+                                                                            len(randints)))
+            self.assertEqual([], randints)
+        finally:
+            rsa.randnum.randint = orig_randint
+
+    def test_mersenne_primes(self):
+        """Tests first known Mersenne primes.
+
+        Mersenne primes are prime numbers that can be written in the form
+        `Mn = 2**n - 1` for some integer `n`. For the list of known Mersenne
+        primes, see:
+        https://en.wikipedia.org/wiki/Mersenne_prime#List_of_known_Mersenne_primes
+        """
+
+        # List of known Mersenne exponents.
+        known_mersenne_exponents = [
+            2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279,
+            2203, 2281, 4423,
+        ]
+
+        # Test Mersenne primes.
+        for exp in known_mersenne_exponents:
+            self.assertTrue(rsa.prime.is_prime(2**exp - 1))
+
+    def test_get_primality_testing_rounds(self):
+        """Test round calculation for primality testing."""
+
+        self.assertEqual(rsa.prime.get_primality_testing_rounds(1 << 63),  10)
+        self.assertEqual(rsa.prime.get_primality_testing_rounds(1 << 127), 10)
+        self.assertEqual(rsa.prime.get_primality_testing_rounds(1 << 255), 10)
+        self.assertEqual(rsa.prime.get_primality_testing_rounds(1 << 511),  7)
+        self.assertEqual(rsa.prime.get_primality_testing_rounds(1 << 767),  7)
+        self.assertEqual(rsa.prime.get_primality_testing_rounds(1 << 1023), 4)
+        self.assertEqual(rsa.prime.get_primality_testing_rounds(1 << 1279), 4)
+        self.assertEqual(rsa.prime.get_primality_testing_rounds(1 << 1535), 3)
+        self.assertEqual(rsa.prime.get_primality_testing_rounds(1 << 2047), 3)
+        self.assertEqual(rsa.prime.get_primality_testing_rounds(1 << 4095), 3)
diff --git a/tests/test_transform.py b/tests/test_transform.py
index 7fe121b..fe0970c 100644
--- a/tests/test_transform.py
+++ b/tests/test_transform.py
@@ -15,37 +15,36 @@
 #  limitations under the License.
 
 import unittest
-from rsa._compat import b
 from rsa.transform import int2bytes, bytes2int, _int2bytes
 
 
 class Test_int2bytes(unittest.TestCase):
     def test_accuracy(self):
-        self.assertEqual(int2bytes(123456789), b('\x07[\xcd\x15'))
-        self.assertEqual(_int2bytes(123456789), b('\x07[\xcd\x15'))
+        self.assertEqual(int2bytes(123456789), b'\x07[\xcd\x15')
+        self.assertEqual(_int2bytes(123456789), b'\x07[\xcd\x15')
 
     def test_codec_identity(self):
         self.assertEqual(bytes2int(int2bytes(123456789, 128)), 123456789)
         self.assertEqual(bytes2int(_int2bytes(123456789, 128)), 123456789)
 
     def test_chunk_size(self):
-        self.assertEqual(int2bytes(123456789, 6), b('\x00\x00\x07[\xcd\x15'))
+        self.assertEqual(int2bytes(123456789, 6), b'\x00\x00\x07[\xcd\x15')
         self.assertEqual(int2bytes(123456789, 7),
-                         b('\x00\x00\x00\x07[\xcd\x15'))
+                         b'\x00\x00\x00\x07[\xcd\x15')
 
         self.assertEqual(_int2bytes(123456789, 6),
-                         b('\x00\x00\x07[\xcd\x15'))
+                         b'\x00\x00\x07[\xcd\x15')
         self.assertEqual(_int2bytes(123456789, 7),
-                         b('\x00\x00\x00\x07[\xcd\x15'))
+                         b'\x00\x00\x00\x07[\xcd\x15')
 
     def test_zero(self):
-        self.assertEqual(int2bytes(0, 4), b('\x00') * 4)
-        self.assertEqual(int2bytes(0, 7), b('\x00') * 7)
-        self.assertEqual(int2bytes(0), b('\x00'))
+        self.assertEqual(int2bytes(0, 4), b'\x00' * 4)
+        self.assertEqual(int2bytes(0, 7), b'\x00' * 7)
+        self.assertEqual(int2bytes(0), b'\x00')
 
-        self.assertEqual(_int2bytes(0, 4), b('\x00') * 4)
-        self.assertEqual(_int2bytes(0, 7), b('\x00') * 7)
-        self.assertEqual(_int2bytes(0), b('\x00'))
+        self.assertEqual(_int2bytes(0, 4), b'\x00' * 4)
+        self.assertEqual(_int2bytes(0, 7), b'\x00' * 7)
+        self.assertEqual(_int2bytes(0), b'\x00')
 
     def test_correctness_against_base_implementation(self):
         # Slow test.
diff --git a/tests/test_varblock.py b/tests/test_varblock.py
deleted file mode 100644
index d1c3730..0000000
--- a/tests/test_varblock.py
+++ /dev/null
@@ -1,88 +0,0 @@
-# -*- coding: utf-8 -*-
-#
-#  Copyright 2011 Sybren A. Stüvel <sybren@stuvel.eu>
-#
-#  Licensed under the Apache License, Version 2.0 (the "License");
-#  you may not use this file except in compliance with the License.
-#  You may obtain a copy of the License at
-#
-#      https://www.apache.org/licenses/LICENSE-2.0
-#
-#  Unless required by applicable law or agreed to in writing, software
-#  distributed under the License is distributed on an "AS IS" BASIS,
-#  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-#  See the License for the specific language governing permissions and
-#  limitations under the License.
-
-"""Tests varblock operations."""
-
-try:
-    from StringIO import StringIO as BytesIO
-except ImportError:
-    from io import BytesIO
-import unittest
-
-from rsa._compat import b
-from rsa import varblock
-
-
-class VarintTest(unittest.TestCase):
-    def test_read_varint(self):
-        encoded = b('\xac\x02crummy')
-        infile = BytesIO(encoded)
-
-        (decoded, read) = varblock.read_varint(infile)
-
-        # Test the returned values
-        self.assertEqual(300, decoded)
-        self.assertEqual(2, read)
-
-        # The rest of the file should be untouched
-        self.assertEqual(b('crummy'), infile.read())
-
-    def test_read_zero(self):
-        encoded = b('\x00crummy')
-        infile = BytesIO(encoded)
-
-        (decoded, read) = varblock.read_varint(infile)
-
-        # Test the returned values
-        self.assertEqual(0, decoded)
-        self.assertEqual(1, read)
-
-        # The rest of the file should be untouched
-        self.assertEqual(b('crummy'), infile.read())
-
-    def test_write_varint(self):
-        expected = b('\xac\x02')
-        outfile = BytesIO()
-
-        written = varblock.write_varint(outfile, 300)
-
-        # Test the returned values
-        self.assertEqual(expected, outfile.getvalue())
-        self.assertEqual(2, written)
-
-    def test_write_zero(self):
-        outfile = BytesIO()
-        written = varblock.write_varint(outfile, 0)
-
-        # Test the returned values
-        self.assertEqual(b('\x00'), outfile.getvalue())
-        self.assertEqual(1, written)
-
-
-class VarblockTest(unittest.TestCase):
-    def test_yield_varblock(self):
-        infile = BytesIO(b('\x01\x0512345\x06Sybren'))
-
-        varblocks = list(varblock.yield_varblocks(infile))
-        self.assertEqual([b('12345'), b('Sybren')], varblocks)
-
-
-class FixedblockTest(unittest.TestCase):
-    def test_yield_fixedblock(self):
-        infile = BytesIO(b('123456Sybren'))
-
-        fixedblocks = list(varblock.yield_fixedblocks(infile, 6))
-        self.assertEqual([b('123456'), b('Sybren')], fixedblocks)
diff --git a/tox.ini b/tox.ini
index 2aa7823..a3109e4 100644
--- a/tox.ini
+++ b/tox.ini
@@ -1,20 +1,20 @@
 [tox]
 # Environment changes have to be manually synced with '.travis.yml'.
-envlist = py26,py27,py33,py34,py35,pypy
+envlist = py27,py34,py35,py36,p37,pypy
 
 [pytest]
 addopts = -v --cov rsa --cov-report term-missing
 
 [testenv]
-commands=py.test []
-deps=pyasn1 >=0.1.3
-     coverage >=3.5
-     PyTest
-     pytest-xdist
-     pytest-cov
+deps = pipenv
+commands=
+    pipenv install --dev
+    pipenv run py.test tests
 
-[testenv:py35]
-commands=py.test --doctest-modules []
+[testenv:py36]
+commands=
+    pipenv install --dev --ignore-pipfile
+    pipenv run py.test --doctest-modules rsa tests
 
 [pep8]
 max-line-length = 100