diff --git a/docs/hazmat/primitives/padding.rst b/docs/hazmat/primitives/padding.rst
index d45a5b8..916b9bc 100644
--- a/docs/hazmat/primitives/padding.rst
+++ b/docs/hazmat/primitives/padding.rst
@@ -39,7 +39,7 @@
     :param block_size: The size of the block in bits that the data is being
                        padded to.
     :raises ValueError: Raised if block size is not a multiple of 8 or is not
-        between 0 and 255 inclusive.
+        between 0 and 2040 inclusive.
 
     .. method:: padder()
 
@@ -82,7 +82,7 @@
     :param block_size: The size of the block in bits that the data is being
         padded to.
     :raises ValueError: Raised if block size is not a multiple of 8 or is not
-        between 0 and 255 inclusive.
+        between 0 and 2040 inclusive.
 
     .. method:: padder()
 
diff --git a/src/_cffi_src/hazmat_src/padding.c b/src/_cffi_src/hazmat_src/padding.c
index 1a0c869..a6e05de 100644
--- a/src/_cffi_src/hazmat_src/padding.c
+++ b/src/_cffi_src/hazmat_src/padding.c
@@ -4,25 +4,25 @@
 
 /* Returns the value of the input with the most-significant-bit copied to all
    of the bits. */
-static uint8_t Cryptography_DUPLICATE_MSB_TO_ALL(uint8_t a) {
-    return (1 - (a >> (sizeof(uint8_t) * 8 - 1))) - 1;
+static uint16_t Cryptography_DUPLICATE_MSB_TO_ALL(uint16_t a) {
+    return (1 - (a >> (sizeof(uint16_t) * 8 - 1))) - 1;
 }
 
-/* This returns 0xFF if a < b else 0x00, but does so in a constant time
+/* This returns 0xFFFF if a < b else 0x0000, but does so in a constant time
    fashion */
-static uint8_t Cryptography_constant_time_lt(uint8_t a, uint8_t b) {
+static uint16_t Cryptography_constant_time_lt(uint16_t a, uint16_t b) {
     a -= b;
     return Cryptography_DUPLICATE_MSB_TO_ALL(a);
 }
 
 uint8_t Cryptography_check_pkcs7_padding(const uint8_t *data,
-                                         uint8_t block_len) {
-    uint8_t i;
-    uint8_t pad_size = data[block_len - 1];
-    uint8_t mismatch = 0;
+                                         uint16_t block_len) {
+    uint16_t i;
+    uint16_t pad_size = data[block_len - 1];
+    uint16_t mismatch = 0;
     for (i = 0; i < block_len; i++) {
         unsigned int mask = Cryptography_constant_time_lt(i, pad_size);
-        uint8_t b = data[block_len - 1 - i];
+        uint16_t b = data[block_len - 1 - i];
         mismatch |= (mask & (pad_size ^ b));
     }
 
@@ -31,6 +31,7 @@
     mismatch |= Cryptography_constant_time_lt(block_len, pad_size);
 
     /* Make sure any bits set are copied to the lowest bit */
+    mismatch |= mismatch >> 8;
     mismatch |= mismatch >> 4;
     mismatch |= mismatch >> 2;
     mismatch |= mismatch >> 1;
@@ -39,14 +40,14 @@
 }
 
 uint8_t Cryptography_check_ansix923_padding(const uint8_t *data,
-                                            uint8_t block_len) {
-    uint8_t i;
-    uint8_t pad_size = data[block_len - 1];
-    uint8_t mismatch = 0;
+                                            uint16_t block_len) {
+    uint16_t i;
+    uint16_t pad_size = data[block_len - 1];
+    uint16_t mismatch = 0;
     /* Skip the first one with the pad size */
     for (i = 1; i < block_len; i++) {
         unsigned int mask = Cryptography_constant_time_lt(i, pad_size);
-        uint8_t b = data[block_len - 1 - i];
+        uint16_t b = data[block_len - 1 - i];
         mismatch |= (mask & b);
     }
 
@@ -55,6 +56,7 @@
     mismatch |= Cryptography_constant_time_lt(block_len, pad_size);
 
     /* Make sure any bits set are copied to the lowest bit */
+    mismatch |= mismatch >> 8;
     mismatch |= mismatch >> 4;
     mismatch |= mismatch >> 2;
     mismatch |= mismatch >> 1;
diff --git a/src/cryptography/hazmat/primitives/padding.py b/src/cryptography/hazmat/primitives/padding.py
index 77fb8f8..a081976 100644
--- a/src/cryptography/hazmat/primitives/padding.py
+++ b/src/cryptography/hazmat/primitives/padding.py
@@ -29,8 +29,8 @@
 
 
 def _byte_padding_check(block_size):
-    if not (0 <= block_size < 256):
-        raise ValueError("block_size must be in range(0, 256).")
+    if not (0 <= block_size <= 2040):
+        raise ValueError("block_size must be in range(0, 2041).")
 
     if block_size % 8 != 0:
         raise ValueError("block_size must be a multiple of 8.")
diff --git a/tests/hazmat/primitives/test_padding.py b/tests/hazmat/primitives/test_padding.py
index e934c0a..fb72a79 100644
--- a/tests/hazmat/primitives/test_padding.py
+++ b/tests/hazmat/primitives/test_padding.py
@@ -6,6 +6,8 @@
 
 import pytest
 
+import six
+
 from cryptography.exceptions import AlreadyFinalized
 from cryptography.hazmat.primitives import padding
 
@@ -100,6 +102,20 @@
         with pytest.raises(AlreadyFinalized):
             unpadder.finalize()
 
+    def test_large_padding(self):
+        padder = padding.PKCS7(2040).padder()
+        padded_data = padder.update(b"")
+        padded_data += padder.finalize()
+
+        for i in six.iterbytes(padded_data):
+            assert i == 255
+
+        unpadder = padding.PKCS7(2040).unpadder()
+        data = unpadder.update(padded_data)
+        data += unpadder.finalize()
+
+        assert data == b""
+
 
 class TestANSIX923(object):
     @pytest.mark.parametrize("size", [127, 4096, -2])
diff --git a/tests/hypothesis/test_padding.py b/tests/hypothesis/test_padding.py
index 29d726f..a433391 100644
--- a/tests/hypothesis/test_padding.py
+++ b/tests/hypothesis/test_padding.py
@@ -8,7 +8,7 @@
 from cryptography.hazmat.primitives.padding import ANSIX923, PKCS7
 
 
-@given(integers(min_value=1, max_value=31), binary())
+@given(integers(min_value=1, max_value=255), binary())
 def test_pkcs7(block_size, data):
     # Generate in [1, 31] so we can easily get block_size in bits by
     # multiplying by 8.
@@ -21,7 +21,7 @@
     assert unpadder.update(padded) + unpadder.finalize() == data
 
 
-@given(integers(min_value=1, max_value=31), binary())
+@given(integers(min_value=1, max_value=255), binary())
 def test_ansix923(block_size, data):
     a = ANSIX923(block_size=block_size * 8)
     padder = a.padder()