prompt: You will be provided with a partial code base and an issue statement explaining a problem to resolve.
  <issue>
  Some OpenSSL bignum arithmetic operations are not in constant time
  ### What's wrong:
  1. Some arithmetic operations exposed in the [OpenSSL bignum binding](https://github.com/pyca/cryptography/blob/master/src/_cffi_src/openssl/bignum.py) are not in constant time.
  2. These functions are specifically:
      1. `BN_div`
      2. `BN_mod_inverse`
      3. `BN_mod_exp`
  
  ### How to resolve:
  1. The OpenSSL solution to this is to call `BN_set_flags` on the secret BIGNUM and set the `BN_FLG_CONSTTIME` flag. [The OpenSSL docs reference this here.](https://github.com/openssl/openssl/blob/master/include/openssl/bn.h#L61)
  2. Expose the needed operations:
      1. `BN_MONT_CTX` operations.
      2. `BN_mod_exp_mont`, and `BN_mod_exp_mont_consttime` 
      3. `BN_set_flags`, `BN_get_flags`, and the `BN_FLG_CONSTTIME` flag.
  
  ### Notes:
  1. Cryptography.io isn't affected by these timing issues. I have clarified with @alex and @reaperhulk.
  2. If you are a downstream user utilizing these operations on private/secret values, then _you are affected_.
  
  </issue>
  <code>
  [start of src/_cffi_src/openssl/bignum.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 INCLUDES = """
  8 #include <openssl/bn.h>
  9 """
  10 
  11 TYPES = """
  12 typedef ... BN_CTX;
  13 typedef ... BIGNUM;
  14 typedef int... BN_ULONG;
  15 """
  16 
  17 FUNCTIONS = """
  18 BIGNUM *BN_new(void);
  19 void BN_free(BIGNUM *);
  20 void BN_clear_free(BIGNUM *);
  21 
  22 int BN_rand(BIGNUM *, int, int, int);
  23 int BN_rand_range(BIGNUM *, BIGNUM *);
  24 
  25 BN_CTX *BN_CTX_new(void);
  26 void BN_CTX_free(BN_CTX *);
  27 
  28 void BN_CTX_start(BN_CTX *);
  29 BIGNUM *BN_CTX_get(BN_CTX *);
  30 void BN_CTX_end(BN_CTX *);
  31 
  32 BIGNUM *BN_copy(BIGNUM *, const BIGNUM *);
  33 BIGNUM *BN_dup(const BIGNUM *);
  34 
  35 int BN_set_word(BIGNUM *, BN_ULONG);
  36 BN_ULONG BN_get_word(const BIGNUM *);
  37 
  38 const BIGNUM *BN_value_one(void);
  39 
  40 char *BN_bn2hex(const BIGNUM *);
  41 int BN_hex2bn(BIGNUM **, const char *);
  42 int BN_dec2bn(BIGNUM **, const char *);
  43 
  44 int BN_bn2bin(const BIGNUM *, unsigned char *);
  45 BIGNUM *BN_bin2bn(const unsigned char *, int, BIGNUM *);
  46 
  47 int BN_num_bits(const BIGNUM *);
  48 
  49 int BN_cmp(const BIGNUM *, const BIGNUM *);
  50 int BN_add(BIGNUM *, const BIGNUM *, const BIGNUM *);
  51 int BN_sub(BIGNUM *, const BIGNUM *, const BIGNUM *);
  52 int BN_mul(BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
  53 int BN_sqr(BIGNUM *, const BIGNUM *, BN_CTX *);
  54 int BN_div(BIGNUM *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
  55 int BN_nnmod(BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
  56 int BN_mod_add(BIGNUM *, const BIGNUM *, const BIGNUM *, const BIGNUM *,
  57                BN_CTX *);
  58 int BN_mod_sub(BIGNUM *, const BIGNUM *, const BIGNUM *, const BIGNUM *,
  59                BN_CTX *);
  60 int BN_mod_mul(BIGNUM *, const BIGNUM *, const BIGNUM *, const BIGNUM *,
  61                BN_CTX *);
  62 int BN_mod_sqr(BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
  63 int BN_exp(BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
  64 int BN_mod_exp(BIGNUM *, const BIGNUM *, const BIGNUM *, const BIGNUM *,
  65                BN_CTX *);
  66 int BN_gcd(BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
  67 BIGNUM *BN_mod_inverse(BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
  68 
  69 int BN_set_bit(BIGNUM *, int);
  70 int BN_clear_bit(BIGNUM *, int);
  71 
  72 int BN_is_bit_set(const BIGNUM *, int);
  73 
  74 int BN_mask_bits(BIGNUM *, int);
  75 
  76 int BN_num_bytes(const BIGNUM *);
  77 
  78 int BN_zero(BIGNUM *);
  79 int BN_one(BIGNUM *);
  80 int BN_mod(BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
  81 
  82 int BN_lshift(BIGNUM *, const BIGNUM *, int);
  83 int BN_lshift1(BIGNUM *, BIGNUM *);
  84 
  85 int BN_rshift(BIGNUM *, BIGNUM *, int);
  86 int BN_rshift1(BIGNUM *, BIGNUM *);
  87 """
  88 
  89 CUSTOMIZATIONS = """
  90 """
  91
  [end of src/_cffi_src/openssl/bignum.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/_cffi_src/openssl/bignum.py b/src/_cffi_src/openssl/bignum.py
  --- a/src/_cffi_src/openssl/bignum.py
  +++ b/src/_cffi_src/openssl/bignum.py
  @@ -10,11 +10,17 @@
   
   TYPES = """
   typedef ... BN_CTX;
  +typedef ... BN_MONT_CTX;
   typedef ... BIGNUM;
   typedef int... BN_ULONG;
   """
   
   FUNCTIONS = """
  +#define BN_FLG_CONSTTIME ...
  +
  +void BN_set_flags(BIGNUM *, int);
  +int BN_get_flags(const BIGNUM *, int);
  +
   BIGNUM *BN_new(void);
   void BN_free(BIGNUM *);
   void BN_clear_free(BIGNUM *);
  @@ -29,6 +35,10 @@
   BIGNUM *BN_CTX_get(BN_CTX *);
   void BN_CTX_end(BN_CTX *);
   
  +BN_MONT_CTX *BN_MONT_CTX_new(void);
  +int BN_MONT_CTX_set(BN_MONT_CTX *, BIGNUM *, BN_CTX *);
  +void BN_MONT_CTX_free(BN_MONT_CTX *);
  +
   BIGNUM *BN_copy(BIGNUM *, const BIGNUM *);
   BIGNUM *BN_dup(const BIGNUM *);
   
  @@ -63,6 +73,10 @@
   int BN_exp(BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
   int BN_mod_exp(BIGNUM *, const BIGNUM *, const BIGNUM *, const BIGNUM *,
                  BN_CTX *);
  +int BN_mod_exp_mont(BIGNUM *, const BIGNUM *, const BIGNUM *, const BIGNUM *,
  +                    BN_CTX *, BN_MONT_CTX *);
  +int BN_mod_exp_mont_consttime(BIGNUM *, const BIGNUM *, const BIGNUM *,
  +                              const BIGNUM *, BN_CTX *, BN_MONT_CTX *);
   int BN_gcd(BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
   BIGNUM *BN_mod_inverse(BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
  
verification_info: {"golden_diff": "diff --git a/src/_cffi_src/openssl/bignum.py b/src/_cffi_src/openssl/bignum.py\n--- a/src/_cffi_src/openssl/bignum.py\n+++ b/src/_cffi_src/openssl/bignum.py\n@@ -10,11 +10,17 @@\n \n TYPES = \"\"\"\n typedef ... BN_CTX;\n+typedef ... BN_MONT_CTX;\n typedef ... BIGNUM;\n typedef int... BN_ULONG;\n \"\"\"\n \n FUNCTIONS = \"\"\"\n+#define BN_FLG_CONSTTIME ...\n+\n+void BN_set_flags(BIGNUM *, int);\n+int BN_get_flags(const BIGNUM *, int);\n+\n BIGNUM *BN_new(void);\n void BN_free(BIGNUM *);\n void BN_clear_free(BIGNUM *);\n@@ -29,6 +35,10 @@\n BIGNUM *BN_CTX_get(BN_CTX *);\n void BN_CTX_end(BN_CTX *);\n \n+BN_MONT_CTX *BN_MONT_CTX_new(void);\n+int BN_MONT_CTX_set(BN_MONT_CTX *, BIGNUM *, BN_CTX *);\n+void BN_MONT_CTX_free(BN_MONT_CTX *);\n+\n BIGNUM *BN_copy(BIGNUM *, const BIGNUM *);\n BIGNUM *BN_dup(const BIGNUM *);\n \n@@ -63,6 +73,10 @@\n int BN_exp(BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);\n int BN_mod_exp(BIGNUM *, const BIGNUM *, const BIGNUM *, const BIGNUM *,\n                BN_CTX *);\n+int BN_mod_exp_mont(BIGNUM *, const BIGNUM *, const BIGNUM *, const BIGNUM *,\n+                    BN_CTX *, BN_MONT_CTX *);\n+int BN_mod_exp_mont_consttime(BIGNUM *, const BIGNUM *, const BIGNUM *,\n+                              const BIGNUM *, BN_CTX *, BN_MONT_CTX *);\n int BN_gcd(BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);\n BIGNUM *BN_mod_inverse(BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);\n", "issue": "Some OpenSSL bignum arithmetic operations are not in constant time\n### What's wrong:\r\n1. Some arithmetic operations exposed in the [OpenSSL bignum binding](https://github.com/pyca/cryptography/blob/master/src/_cffi_src/openssl/bignum.py) are not in constant time.\r\n2. These functions are specifically:\r\n    1. `BN_div`\r\n    2. `BN_mod_inverse`\r\n    3. `BN_mod_exp`\r\n\r\n### How to resolve:\r\n1. The OpenSSL solution to this is to call `BN_set_flags` on the secret BIGNUM and set the `BN_FLG_CONSTTIME` flag. [The OpenSSL docs reference this here.](https://github.com/openssl/openssl/blob/master/include/openssl/bn.h#L61)\r\n2. Expose the needed operations:\r\n    1. `BN_MONT_CTX` operations.\r\n    2. `BN_mod_exp_mont`, and `BN_mod_exp_mont_consttime` \r\n    3. `BN_set_flags`, `BN_get_flags`, and the `BN_FLG_CONSTTIME` flag.\r\n\r\n### Notes:\r\n1. Cryptography.io isn't affected by these timing issues. I have clarified with @alex and @reaperhulk.\r\n2. If you are a downstream user utilizing these operations on private/secret values, then _you are affected_.\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\nINCLUDES = \"\"\"\n#include <openssl/bn.h>\n\"\"\"\n\nTYPES = \"\"\"\ntypedef ... BN_CTX;\ntypedef ... BIGNUM;\ntypedef int... BN_ULONG;\n\"\"\"\n\nFUNCTIONS = \"\"\"\nBIGNUM *BN_new(void);\nvoid BN_free(BIGNUM *);\nvoid BN_clear_free(BIGNUM *);\n\nint BN_rand(BIGNUM *, int, int, int);\nint BN_rand_range(BIGNUM *, BIGNUM *);\n\nBN_CTX *BN_CTX_new(void);\nvoid BN_CTX_free(BN_CTX *);\n\nvoid BN_CTX_start(BN_CTX *);\nBIGNUM *BN_CTX_get(BN_CTX *);\nvoid BN_CTX_end(BN_CTX *);\n\nBIGNUM *BN_copy(BIGNUM *, const BIGNUM *);\nBIGNUM *BN_dup(const BIGNUM *);\n\nint BN_set_word(BIGNUM *, BN_ULONG);\nBN_ULONG BN_get_word(const BIGNUM *);\n\nconst BIGNUM *BN_value_one(void);\n\nchar *BN_bn2hex(const BIGNUM *);\nint BN_hex2bn(BIGNUM **, const char *);\nint BN_dec2bn(BIGNUM **, const char *);\n\nint BN_bn2bin(const BIGNUM *, unsigned char *);\nBIGNUM *BN_bin2bn(const unsigned char *, int, BIGNUM *);\n\nint BN_num_bits(const BIGNUM *);\n\nint BN_cmp(const BIGNUM *, const BIGNUM *);\nint BN_add(BIGNUM *, const BIGNUM *, const BIGNUM *);\nint BN_sub(BIGNUM *, const BIGNUM *, const BIGNUM *);\nint BN_mul(BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);\nint BN_sqr(BIGNUM *, const BIGNUM *, BN_CTX *);\nint BN_div(BIGNUM *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);\nint BN_nnmod(BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);\nint BN_mod_add(BIGNUM *, const BIGNUM *, const BIGNUM *, const BIGNUM *,\n               BN_CTX *);\nint BN_mod_sub(BIGNUM *, const BIGNUM *, const BIGNUM *, const BIGNUM *,\n               BN_CTX *);\nint BN_mod_mul(BIGNUM *, const BIGNUM *, const BIGNUM *, const BIGNUM *,\n               BN_CTX *);\nint BN_mod_sqr(BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);\nint BN_exp(BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);\nint BN_mod_exp(BIGNUM *, const BIGNUM *, const BIGNUM *, const BIGNUM *,\n               BN_CTX *);\nint BN_gcd(BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);\nBIGNUM *BN_mod_inverse(BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);\n\nint BN_set_bit(BIGNUM *, int);\nint BN_clear_bit(BIGNUM *, int);\n\nint BN_is_bit_set(const BIGNUM *, int);\n\nint BN_mask_bits(BIGNUM *, int);\n\nint BN_num_bytes(const BIGNUM *);\n\nint BN_zero(BIGNUM *);\nint BN_one(BIGNUM *);\nint BN_mod(BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);\n\nint BN_lshift(BIGNUM *, const BIGNUM *, int);\nint BN_lshift1(BIGNUM *, BIGNUM *);\n\nint BN_rshift(BIGNUM *, BIGNUM *, int);\nint BN_rshift1(BIGNUM *, BIGNUM *);\n\"\"\"\n\nCUSTOMIZATIONS = \"\"\"\n\"\"\"\n", "path": "src/_cffi_src/openssl/bignum.py"}]}