diff --git a/ChangeLog b/ChangeLog
index 2f6a3c5..7f7726b 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,10 @@
 PolarSSL ChangeLog (Sorted per branch, date)
 
+= PolarSSL 1.3 branch
+Bugfix
+   * ecp_gen_keypair() does more tries to prevent failure because of
+     statistics
+
 = PolarSSL 1.3.4 released on 2014-01-27
 Features
    * Support for the Koblitz curves: secp192k1, secp224k1, secp256k1
diff --git a/library/ecp.c b/library/ecp.c
index b1c4548..a27d30e 100644
--- a/library/ecp.c
+++ b/library/ecp.c
@@ -1796,7 +1796,16 @@
             MPI_CHK( mpi_read_binary( d, rnd, n_size ) );
             MPI_CHK( mpi_shift_r( d, 8 * n_size - grp->nbits ) );
 
-            if( count++ > 10 )
+            /*
+             * Each try has at worst a probability 1/2 of failing (the msb has
+             * a probability 1/2 of being 0, and then the result will be < N),
+             * so after 30 tries failure probability is a most 2**(-30).
+             *
+             * For most curves, 1 try is enough with overwhelming probability,
+             * since N starts with a lot of 1s in binary, but some curves
+             * such as secp224k1 are actually very close to the worst case.
+             */
+            if( ++count > 30 )
                 return( POLARSSL_ERR_ECP_RANDOM_FAILED );
         }
         while( mpi_cmp_int( d, 1 ) < 0 ||