diff --git a/ChangeLog b/ChangeLog
index 27c7556..4e67443 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,8 @@
+2012-04-03  Jean-Paul Calderone  <exarkun@twistedmatrix.com>
+
+	* OpenSSL/crypto/pkey.c: Release the GIL around RSA and DSA key
+	  generation, based on code from INADA Naoki.
+
 2012-02-13  Jean-Paul Calderone  <exarkun@twistedmatrix.com>
 
 	* OpenSSL/ssl/ssl.c: Add session cache related constants for use
diff --git a/OpenSSL/crypto/pkey.c b/OpenSSL/crypto/pkey.c
index b9472ec..f23ec70 100644
--- a/OpenSSL/crypto/pkey.c
+++ b/OpenSSL/crypto/pkey.c
@@ -52,19 +52,30 @@
                 PyErr_SetString(PyExc_ValueError, "Invalid number of bits");
                 return NULL;
             }
-            if ((rsa = RSA_generate_key(bits, 0x10001, NULL, NULL)) == NULL)
+            Py_BEGIN_ALLOW_THREADS;
+            rsa = RSA_generate_key(bits, 0x10001, NULL, NULL);
+            Py_END_ALLOW_THREADS;
+            if (rsa == NULL) {
                 FAIL();
-            if (!EVP_PKEY_assign_RSA(self->pkey, rsa))
+            }
+            if (!EVP_PKEY_assign_RSA(self->pkey, rsa)) {
                 FAIL();
+            }
 	    break;
 
         case crypto_TYPE_DSA:
-            if ((dsa = DSA_generate_parameters(bits, NULL, 0, NULL, NULL, NULL, NULL)) == NULL)
+            Py_BEGIN_ALLOW_THREADS;
+            dsa = DSA_generate_parameters(bits, NULL, 0, NULL, NULL, NULL, NULL);
+            Py_END_ALLOW_THREADS;
+            if (dsa == NULL) {
                 FAIL();
-            if (!DSA_generate_key(dsa))
+            }
+            if (!DSA_generate_key(dsa)) {
                 FAIL();
-            if (!EVP_PKEY_assign_DSA(self->pkey, dsa))
+            }
+            if (!EVP_PKEY_assign_DSA(self->pkey, dsa)) {
                 FAIL();
+            }
 	    break;
 
         default:
diff --git a/leakcheck/thread-key-gen.py b/leakcheck/thread-key-gen.py
new file mode 100644
index 0000000..62e1a58
--- /dev/null
+++ b/leakcheck/thread-key-gen.py
@@ -0,0 +1,38 @@
+# Copyright (C) Jean-Paul Calderone
+# See LICENSE for details.
+#
+# Stress tester for thread-related bugs in RSA and DSA key generation.  0.12 and
+# older held the GIL during these operations.  Subsequent versions release it
+# during them.
+
+from threading import Thread
+
+from OpenSSL.crypto import TYPE_RSA, TYPE_DSA, PKey
+
+def generate_rsa():
+    keys = []
+    for i in range(100):
+        key = PKey()
+        key.generate_key(TYPE_RSA, 1024)
+        keys.append(key)
+
+def generate_dsa():
+    keys = []
+    for i in range(100):
+        key = PKey()
+        key.generate_key(TYPE_DSA, 512)
+        keys.append(key)
+
+
+def main():
+    threads = []
+    for i in range(3):
+        t = Thread(target=generate_rsa, args=())
+        threads.append(t)
+        t = Thread(target=generate_dsa, args=())
+        threads.append(t)
+
+    for t in threads:
+        t.start()
+
+main()