prompt: You will be provided with a partial code base and an issue statement explaining a problem to resolve.
  <issue>
  HKDF key-length inconsistency
  For too small key sizes, `HKDF.derive()` outputs an empty array instead of a small key:
  
  Program:
  ```python
  #!/usr/bin/env python3.5
  import cryptography
  from cryptography.hazmat.primitives import hashes
  from cryptography.hazmat.primitives.kdf.hkdf import HKDF
  from cryptography.hazmat.backends import default_backend
  
  print("cryptography.io:{}".format(cryptography.__version__))
  
  hkdf = HKDF(algorithm=hashes.SHA256(), length=4, salt=b"salt",
              info=b"some-test", backend=default_backend())
  
  key = hkdf.derive(b"my secret passphrase")
  print("Derived key: {}".format(key))
  ```
  
  Output:
  ```
  cryptography.io:1.5.2
  Derived key: b''
  ```
  
  Suggested fix:
  
  I am not quite sure why the division by 8 in the snippet below was added. The cumulative size of the output array is always `self._algorithm.digest_size * len(output)` and thus we can stop after `self._algorithm.digest_size * len(output) >= self._length`. At first I thought this might be a clever trick taken from the paper, but I didn't find it there. I guess there was a mixup between bits and bytes at some point.
  
  ```python
  # class HKDFExpand
  def _expand(self, key_material):
          output = [b""]
          counter = 1
  
          while (self._algorithm.digest_size // 8) * len(output) < self._length:
              h = hmac.HMAC(key_material, self._algorithm, backend=self._backend)
              h.update(output[-1])
              h.update(self._info)
              h.update(six.int2byte(counter))
              output.append(h.finalize())
              counter += 1
  
          return b"".join(output)[:self._length]
  ```
  
  </issue>
  <code>
  [start of src/cryptography/hazmat/primitives/kdf/hkdf.py]
  1 # This file is dual licensed under the terms of the Apache License, Version
  2 # 2.0, and the BSD License. See the LICENSE file in the root of this repository
  3 # for complete details.
  4 
  5 from __future__ import absolute_import, division, print_function
  6 
  7 import six
  8 
  9 from cryptography import utils
  10 from cryptography.exceptions import (
  11     AlreadyFinalized, InvalidKey, UnsupportedAlgorithm, _Reasons
  12 )
  13 from cryptography.hazmat.backends.interfaces import HMACBackend
  14 from cryptography.hazmat.primitives import constant_time, hmac
  15 from cryptography.hazmat.primitives.kdf import KeyDerivationFunction
  16 
  17 
  18 @utils.register_interface(KeyDerivationFunction)
  19 class HKDF(object):
  20     def __init__(self, algorithm, length, salt, info, backend):
  21         if not isinstance(backend, HMACBackend):
  22             raise UnsupportedAlgorithm(
  23                 "Backend object does not implement HMACBackend.",
  24                 _Reasons.BACKEND_MISSING_INTERFACE
  25             )
  26 
  27         self._algorithm = algorithm
  28 
  29         if not (salt is None or isinstance(salt, bytes)):
  30             raise TypeError("salt must be bytes.")
  31 
  32         if salt is None:
  33             salt = b"\x00" * (self._algorithm.digest_size // 8)
  34 
  35         self._salt = salt
  36 
  37         self._backend = backend
  38 
  39         self._hkdf_expand = HKDFExpand(self._algorithm, length, info, backend)
  40 
  41     def _extract(self, key_material):
  42         h = hmac.HMAC(self._salt, self._algorithm, backend=self._backend)
  43         h.update(key_material)
  44         return h.finalize()
  45 
  46     def derive(self, key_material):
  47         if not isinstance(key_material, bytes):
  48             raise TypeError("key_material must be bytes.")
  49 
  50         return self._hkdf_expand.derive(self._extract(key_material))
  51 
  52     def verify(self, key_material, expected_key):
  53         if not constant_time.bytes_eq(self.derive(key_material), expected_key):
  54             raise InvalidKey
  55 
  56 
  57 @utils.register_interface(KeyDerivationFunction)
  58 class HKDFExpand(object):
  59     def __init__(self, algorithm, length, info, backend):
  60         if not isinstance(backend, HMACBackend):
  61             raise UnsupportedAlgorithm(
  62                 "Backend object does not implement HMACBackend.",
  63                 _Reasons.BACKEND_MISSING_INTERFACE
  64             )
  65 
  66         self._algorithm = algorithm
  67 
  68         self._backend = backend
  69 
  70         max_length = 255 * (algorithm.digest_size // 8)
  71 
  72         if length > max_length:
  73             raise ValueError(
  74                 "Can not derive keys larger than {0} octets.".format(
  75                     max_length
  76                 ))
  77 
  78         self._length = length
  79 
  80         if not (info is None or isinstance(info, bytes)):
  81             raise TypeError("info must be bytes.")
  82 
  83         if info is None:
  84             info = b""
  85 
  86         self._info = info
  87 
  88         self._used = False
  89 
  90     def _expand(self, key_material):
  91         output = [b""]
  92         counter = 1
  93 
  94         while (self._algorithm.digest_size // 8) * len(output) < self._length:
  95             h = hmac.HMAC(key_material, self._algorithm, backend=self._backend)
  96             h.update(output[-1])
  97             h.update(self._info)
  98             h.update(six.int2byte(counter))
  99             output.append(h.finalize())
  100             counter += 1
  101 
  102         return b"".join(output)[:self._length]
  103 
  104     def derive(self, key_material):
  105         if not isinstance(key_material, bytes):
  106             raise TypeError("key_material must be bytes.")
  107 
  108         if self._used:
  109             raise AlreadyFinalized
  110 
  111         self._used = True
  112         return self._expand(key_material)
  113 
  114     def verify(self, key_material, expected_key):
  115         if not constant_time.bytes_eq(self.derive(key_material), expected_key):
  116             raise InvalidKey
  117
  [end of src/cryptography/hazmat/primitives/kdf/hkdf.py]
  </code>
  
  I need you to solve this issue by generating a single patch file that I can apply directly to this repository using git apply. Please respond with a single patch file in the following format.
  <patch>
  diff --git a/file.py b/file.py
  --- a/file.py
  +++ b/file.py
  @@ -1,27 +1,35 @@
   def euclidean(a, b):
  -    while b:
  -        a, b = b, a % b
  -    return a
  +    if b == 0:
  +        return a
  +    return euclidean(b, a % b)
   
   
   def bresenham(x0, y0, x1, y1):
       points = []
       dx = abs(x1 - x0)
       dy = abs(y1 - y0)
  -    sx = 1 if x0 < x1 else -1
  -    sy = 1 if y0 < y1 else -1
  -    err = dx - dy
  +    x, y = x0, y0
  +    sx = -1 if x0 > x1 else 1
  +    sy = -1 if y0 > y1 else 1
   
  -    while True:
  -        points.append((x0, y0))
  -        if x0 == x1 and y0 == y1:
  -            break
  -        e2 = 2 * err
  -        if e2 > -dy:
  -            err -= dy
  -            x0 += sx
  -        if e2 < dx:
  -            err += dx
  -            y0 += sy
  +    if dx > dy:
  +        err = dx / 2.0
  +        while x != x1:
  +            points.append((x, y))
  +            err -= dy
  +            if err < 0:
  +                y += sy
  +                err += dx
  +            x += sx
  +    else:
  +        err = dy / 2.0
  +        while y != y1:
  +            points.append((x, y))
  +            err -= dx
  +            if err < 0:
  +                x += sx
  +                err += dy
  +            y += sy
  +
  +    points.append((x, y))
       return points
  
  </patch>
golden_diff: diff --git a/src/cryptography/hazmat/primitives/kdf/hkdf.py b/src/cryptography/hazmat/primitives/kdf/hkdf.py
  --- a/src/cryptography/hazmat/primitives/kdf/hkdf.py
  +++ b/src/cryptography/hazmat/primitives/kdf/hkdf.py
  @@ -91,7 +91,7 @@
           output = [b""]
           counter = 1
   
  -        while (self._algorithm.digest_size // 8) * len(output) < self._length:
  +        while self._algorithm.digest_size * (len(output) - 1) < self._length:
               h = hmac.HMAC(key_material, self._algorithm, backend=self._backend)
               h.update(output[-1])
               h.update(self._info)
  
verification_info: {"golden_diff": "diff --git a/src/cryptography/hazmat/primitives/kdf/hkdf.py b/src/cryptography/hazmat/primitives/kdf/hkdf.py\n--- a/src/cryptography/hazmat/primitives/kdf/hkdf.py\n+++ b/src/cryptography/hazmat/primitives/kdf/hkdf.py\n@@ -91,7 +91,7 @@\n         output = [b\"\"]\n         counter = 1\n \n-        while (self._algorithm.digest_size // 8) * len(output) < self._length:\n+        while self._algorithm.digest_size * (len(output) - 1) < self._length:\n             h = hmac.HMAC(key_material, self._algorithm, backend=self._backend)\n             h.update(output[-1])\n             h.update(self._info)\n", "issue": "HKDF key-length inconsistency\nFor too small key sizes, `HKDF.derive()` outputs an empty array instead of a small key:\r\n\r\nProgram:\r\n```python\r\n#!/usr/bin/env python3.5\r\nimport cryptography\r\nfrom cryptography.hazmat.primitives import hashes\r\nfrom cryptography.hazmat.primitives.kdf.hkdf import HKDF\r\nfrom cryptography.hazmat.backends import default_backend\r\n\r\nprint(\"cryptography.io:{}\".format(cryptography.__version__))\r\n\r\nhkdf = HKDF(algorithm=hashes.SHA256(), length=4, salt=b\"salt\",\r\n            info=b\"some-test\", backend=default_backend())\r\n\r\nkey = hkdf.derive(b\"my secret passphrase\")\r\nprint(\"Derived key: {}\".format(key))\r\n```\r\n\r\nOutput:\r\n```\r\ncryptography.io:1.5.2\r\nDerived key: b''\r\n```\r\n\r\nSuggested fix:\r\n\r\nI am not quite sure why the division by 8 in the snippet below was added. The cumulative size of the output array is always `self._algorithm.digest_size * len(output)` and thus we can stop after `self._algorithm.digest_size * len(output) >= self._length`. At first I thought this might be a clever trick taken from the paper, but I didn't find it there. I guess there was a mixup between bits and bytes at some point.\r\n\r\n```python\r\n# class HKDFExpand\r\ndef _expand(self, key_material):\r\n        output = [b\"\"]\r\n        counter = 1\r\n\r\n        while (self._algorithm.digest_size // 8) * len(output) < self._length:\r\n            h = hmac.HMAC(key_material, self._algorithm, backend=self._backend)\r\n            h.update(output[-1])\r\n            h.update(self._info)\r\n            h.update(six.int2byte(counter))\r\n            output.append(h.finalize())\r\n            counter += 1\r\n\r\n        return b\"\".join(output)[:self._length]\r\n```\n", "before_files": [{"content": "# This file is dual licensed under the terms of the Apache License, Version\n# 2.0, and the BSD License. See the LICENSE file in the root of this repository\n# for complete details.\n\nfrom __future__ import absolute_import, division, print_function\n\nimport six\n\nfrom cryptography import utils\nfrom cryptography.exceptions import (\n    AlreadyFinalized, InvalidKey, UnsupportedAlgorithm, _Reasons\n)\nfrom cryptography.hazmat.backends.interfaces import HMACBackend\nfrom cryptography.hazmat.primitives import constant_time, hmac\nfrom cryptography.hazmat.primitives.kdf import KeyDerivationFunction\n\n\n@utils.register_interface(KeyDerivationFunction)\nclass HKDF(object):\n    def __init__(self, algorithm, length, salt, info, backend):\n        if not isinstance(backend, HMACBackend):\n            raise UnsupportedAlgorithm(\n                \"Backend object does not implement HMACBackend.\",\n                _Reasons.BACKEND_MISSING_INTERFACE\n            )\n\n        self._algorithm = algorithm\n\n        if not (salt is None or isinstance(salt, bytes)):\n            raise TypeError(\"salt must be bytes.\")\n\n        if salt is None:\n            salt = b\"\\x00\" * (self._algorithm.digest_size // 8)\n\n        self._salt = salt\n\n        self._backend = backend\n\n        self._hkdf_expand = HKDFExpand(self._algorithm, length, info, backend)\n\n    def _extract(self, key_material):\n        h = hmac.HMAC(self._salt, self._algorithm, backend=self._backend)\n        h.update(key_material)\n        return h.finalize()\n\n    def derive(self, key_material):\n        if not isinstance(key_material, bytes):\n            raise TypeError(\"key_material must be bytes.\")\n\n        return self._hkdf_expand.derive(self._extract(key_material))\n\n    def verify(self, key_material, expected_key):\n        if not constant_time.bytes_eq(self.derive(key_material), expected_key):\n            raise InvalidKey\n\n\n@utils.register_interface(KeyDerivationFunction)\nclass HKDFExpand(object):\n    def __init__(self, algorithm, length, info, backend):\n        if not isinstance(backend, HMACBackend):\n            raise UnsupportedAlgorithm(\n                \"Backend object does not implement HMACBackend.\",\n                _Reasons.BACKEND_MISSING_INTERFACE\n            )\n\n        self._algorithm = algorithm\n\n        self._backend = backend\n\n        max_length = 255 * (algorithm.digest_size // 8)\n\n        if length > max_length:\n            raise ValueError(\n                \"Can not derive keys larger than {0} octets.\".format(\n                    max_length\n                ))\n\n        self._length = length\n\n        if not (info is None or isinstance(info, bytes)):\n            raise TypeError(\"info must be bytes.\")\n\n        if info is None:\n            info = b\"\"\n\n        self._info = info\n\n        self._used = False\n\n    def _expand(self, key_material):\n        output = [b\"\"]\n        counter = 1\n\n        while (self._algorithm.digest_size // 8) * len(output) < self._length:\n            h = hmac.HMAC(key_material, self._algorithm, backend=self._backend)\n            h.update(output[-1])\n            h.update(self._info)\n            h.update(six.int2byte(counter))\n            output.append(h.finalize())\n            counter += 1\n\n        return b\"\".join(output)[:self._length]\n\n    def derive(self, key_material):\n        if not isinstance(key_material, bytes):\n            raise TypeError(\"key_material must be bytes.\")\n\n        if self._used:\n            raise AlreadyFinalized\n\n        self._used = True\n        return self._expand(key_material)\n\n    def verify(self, key_material, expected_key):\n        if not constant_time.bytes_eq(self.derive(key_material), expected_key):\n            raise InvalidKey\n", "path": "src/cryptography/hazmat/primitives/kdf/hkdf.py"}]}