diff --git a/tests/test_crypto.py b/tests/test_crypto.py
index 5642120..d1c261b 100644
--- a/tests/test_crypto.py
+++ b/tests/test_crypto.py
@@ -573,7 +573,7 @@
     """
     # Basic setup stuff to generate a certificate
     pkey = PKey()
-    pkey.generate_key(TYPE_RSA, 384)
+    pkey.generate_key(TYPE_RSA, 512)
     req = X509Req()
     req.set_pubkey(pkey)
     # Authority good you have.
@@ -917,7 +917,7 @@
         `PKey.generate_key` generates an RSA key when passed `TYPE_RSA` as a
         type and a reasonable number of bits.
         """
-        bits = 128
+        bits = 512
         key = PKey()
         key.generate_key(TYPE_RSA, bits)
         assert key.type() == TYPE_RSA
diff --git a/tests/test_ssl.py b/tests/test_ssl.py
index a5eb3db..f36890d 100644
--- a/tests/test_ssl.py
+++ b/tests/test_ssl.py
@@ -519,7 +519,7 @@
         `Context.use_privatekey` takes an `OpenSSL.crypto.PKey` instance.
         """
         key = PKey()
-        key.generate_key(TYPE_RSA, 128)
+        key.generate_key(TYPE_RSA, 512)
         ctx = Context(TLSv1_METHOD)
         ctx.use_privatekey(key)
         with pytest.raises(TypeError):
@@ -540,7 +540,7 @@
         arguments does not raise an exception.
         """
         key = PKey()
-        key.generate_key(TYPE_RSA, 128)
+        key.generate_key(TYPE_RSA, 512)
 
         with open(pemfile, "wt") as pem:
             pem.write(
@@ -843,7 +843,7 @@
         passphrase.  Return the path to the new file.
         """
         key = PKey()
-        key.generate_key(TYPE_RSA, 128)
+        key.generate_key(TYPE_RSA, 512)
         pem = dump_privatekey(FILETYPE_PEM, key, "blowfish", passphrase)
         with open(tmpfile, 'w') as fObj:
             fObj.write(pem.decode('ascii'))