RSA blinding on CRT operations to counter timing attacks
diff --git a/ChangeLog b/ChangeLog
index a420e6c..36704f1 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -12,6 +12,8 @@
 Security
    * Fixed potential heap buffer overflow on large hostname setting
    * Fixed potential negative value misinterpretation in load_file()
+   * RSA blinding on CRT operations to counter timing attacks
+     (found by Cyril Arnaud and Pierre-Alain Fouque)
 
 = Version 1.2.8 released 2013-06-19
 Features
diff --git a/include/polarssl/rsa.h b/include/polarssl/rsa.h
index f9a0220..64e7f6c 100644
--- a/include/polarssl/rsa.h
+++ b/include/polarssl/rsa.h
@@ -151,6 +151,11 @@
     mpi RP;                     /*!<  cached R^2 mod P  */
     mpi RQ;                     /*!<  cached R^2 mod Q  */
 
+#if !defined(POLARSSL_RSA_NO_CRT)
+    mpi Vi;                     /*!<  cached blinding value     */
+    mpi Vf;                     /*!<  cached un-blinding value  */
+#endif
+
     int padding;                /*!<  RSA_PKCS_V15 for 1.5 padding and
                                       RSA_PKCS_v21 for OAEP/PSS         */
     int hash_id;                /*!<  Hash identifier of md_type_t as
@@ -242,6 +247,8 @@
  * \brief          Do an RSA private key operation
  *
  * \param ctx      RSA context
+ * \param f_rng    RNG function (Needed for blinding)
+ * \param p_rng    RNG parameter
  * \param input    input buffer
  * \param output   output buffer
  *
@@ -251,6 +258,8 @@
  *                 enough (eg. 128 bytes if RSA-1024 is used).
  */
 int rsa_private( rsa_context *ctx,
+                 int (*f_rng)(void *, unsigned char *, size_t),
+                 void *p_rng,
                  const unsigned char *input,
                  unsigned char *output );
 
@@ -260,7 +269,8 @@
  *                 RSA operation.
  *
  * \param ctx      RSA context
- * \param f_rng    RNG function (Needed for padding and PKCS#1 v2.1 encoding)
+ * \param f_rng    RNG function (Needed for padding and PKCS#1 v2.1 encoding
+ *                               and RSA_PRIVATE)
  * \param p_rng    RNG parameter
  * \param mode     RSA_PUBLIC or RSA_PRIVATE
  * \param ilen     contains the plaintext length
@@ -283,7 +293,7 @@
  * \brief          Perform a PKCS#1 v1.5 encryption (RSAES-PKCS1-v1_5-ENCRYPT)
  *
  * \param ctx      RSA context
- * \param f_rng    RNG function (Needed for padding)
+ * \param f_rng    RNG function (Needed for padding and RSA_PRIVATE)
  * \param p_rng    RNG parameter
  * \param mode     RSA_PUBLIC or RSA_PRIVATE
  * \param ilen     contains the plaintext length
@@ -306,7 +316,8 @@
  * \brief          Perform a PKCS#1 v2.1 OAEP encryption (RSAES-OAEP-ENCRYPT)
  *
  * \param ctx      RSA context
- * \param f_rng    RNG function (Needed for padding and PKCS#1 v2.1 encoding)
+ * \param f_rng    RNG function (Needed for padding and PKCS#1 v2.1 encoding
+ *                               and RSA_PRIVATE)
  * \param p_rng    RNG parameter
  * \param mode     RSA_PUBLIC or RSA_PRIVATE
  * \param label    buffer holding the custom label to use
@@ -335,6 +346,8 @@
  *                 the message padding
  *
  * \param ctx      RSA context
+ * \param f_rng    RNG function (Only needed for RSA_PRIVATE)
+ * \param p_rng    RNG parameter
  * \param mode     RSA_PUBLIC or RSA_PRIVATE
  * \param olen     will contain the plaintext length
  * \param input    buffer holding the encrypted data
@@ -348,6 +361,8 @@
  *                 an error is thrown.
  */
 int rsa_pkcs1_decrypt( rsa_context *ctx,
+                       int (*f_rng)(void *, unsigned char *, size_t),
+                       void *p_rng,
                        int mode, size_t *olen,
                        const unsigned char *input,
                        unsigned char *output,
@@ -357,6 +372,8 @@
  * \brief          Perform a PKCS#1 v1.5 decryption (RSAES-PKCS1-v1_5-DECRYPT)
  *
  * \param ctx      RSA context
+ * \param f_rng    RNG function (Only needed for RSA_PRIVATE)
+ * \param p_rng    RNG parameter
  * \param mode     RSA_PUBLIC or RSA_PRIVATE
  * \param olen     will contain the plaintext length
  * \param input    buffer holding the encrypted data
@@ -370,6 +387,8 @@
  *                 an error is thrown.
  */
 int rsa_rsaes_pkcs1_v15_decrypt( rsa_context *ctx,
+                                 int (*f_rng)(void *, unsigned char *, size_t),
+                                 void *p_rng,
                                  int mode, size_t *olen,
                                  const unsigned char *input,
                                  unsigned char *output,
@@ -379,6 +398,8 @@
  * \brief          Perform a PKCS#1 v2.1 OAEP decryption (RSAES-OAEP-DECRYPT)
  *
  * \param ctx      RSA context
+ * \param f_rng    RNG function (Only needed for RSA_PRIVATE)
+ * \param p_rng    RNG parameter
  * \param mode     RSA_PUBLIC or RSA_PRIVATE
  * \param label    buffer holding the custom label to use
  * \param label_len contains the label length
@@ -394,6 +415,8 @@
  *                 an error is thrown.
  */
 int rsa_rsaes_oaep_decrypt( rsa_context *ctx,
+                            int (*f_rng)(void *, unsigned char *, size_t),
+                            void *p_rng,
                             int mode,
                             const unsigned char *label, size_t label_len,
                             size_t *olen,
@@ -407,7 +430,8 @@
  *                 a message digest
  *
  * \param ctx      RSA context
- * \param f_rng    RNG function (Needed for PKCS#1 v2.1 encoding)
+ * \param f_rng    RNG function (Needed for PKCS#1 v2.1 encoding and for
+ *                 RSA_PRIVATE)
  * \param p_rng    RNG parameter
  * \param mode     RSA_PUBLIC or RSA_PRIVATE
  * \param hash_id  SIG_RSA_RAW, SIG_RSA_MD{2,4,5} or SIG_RSA_SHA{1,224,256,384,512}
@@ -440,6 +464,8 @@
  * \brief          Perform a PKCS#1 v1.5 signature (RSASSA-PKCS1-v1_5-SIGN)
  *
  * \param ctx      RSA context
+ * \param f_rng    RNG function (Only needed for RSA_PRIVATE)
+ * \param p_rng    RNG parameter
  * \param mode     RSA_PUBLIC or RSA_PRIVATE
  * \param hash_id  SIG_RSA_RAW, SIG_RSA_MD{2,4,5} or SIG_RSA_SHA{1,224,256,384,512}
  * \param hashlen  message digest length (for SIG_RSA_RAW only)
@@ -453,6 +479,8 @@
  *                 of ctx->N (eg. 128 bytes if RSA-1024 is used).
  */
 int rsa_rsassa_pkcs1_v15_sign( rsa_context *ctx,
+                               int (*f_rng)(void *, unsigned char *, size_t),
+                               void *p_rng,
                                int mode,
                                int hash_id,
                                unsigned int hashlen,
@@ -463,7 +491,8 @@
  * \brief          Perform a PKCS#1 v2.1 PSS signature (RSASSA-PSS-SIGN)
  *
  * \param ctx      RSA context
- * \param f_rng    RNG function (Needed for PKCS#1 v2.1 encoding)
+ * \param f_rng    RNG function (Needed for PKCS#1 v2.1 encoding and for
+ *                               RSA_PRIVATE)
  * \param p_rng    RNG parameter
  * \param mode     RSA_PUBLIC or RSA_PRIVATE
  * \param hash_id  SIG_RSA_RAW, SIG_RSA_MD{2,4,5} or SIG_RSA_SHA{1,224,256,384,512}
@@ -498,6 +527,8 @@
  *                 the message digest
  *
  * \param ctx      points to an RSA public key
+ * \param f_rng    RNG function (Only needed for RSA_PRIVATE)
+ * \param p_rng    RNG parameter
  * \param mode     RSA_PUBLIC or RSA_PRIVATE
  * \param hash_id  SIG_RSA_RAW, SIG_RSA_MD{2,4,5} or SIG_RSA_SHA{1,224,256,384,512}
  * \param hashlen  message digest length (for SIG_RSA_RAW only)
@@ -517,6 +548,8 @@
  *                 keep both hashes the same.
  */
 int rsa_pkcs1_verify( rsa_context *ctx,
+                      int (*f_rng)(void *, unsigned char *, size_t),
+                      void *p_rng,
                       int mode,
                       int hash_id,
                       unsigned int hashlen,
@@ -527,6 +560,8 @@
  * \brief          Perform a PKCS#1 v1.5 verification (RSASSA-PKCS1-v1_5-VERIFY)
  *
  * \param ctx      points to an RSA public key
+ * \param f_rng    RNG function (Only needed for RSA_PRIVATE)
+ * \param p_rng    RNG parameter
  * \param mode     RSA_PUBLIC or RSA_PRIVATE
  * \param hash_id  SIG_RSA_RAW, SIG_RSA_MD{2,4,5} or SIG_RSA_SHA{1,224,256,384,512}
  * \param hashlen  message digest length (for SIG_RSA_RAW only)
@@ -540,6 +575,8 @@
  *                 of ctx->N (eg. 128 bytes if RSA-1024 is used).
  */
 int rsa_rsassa_pkcs1_v15_verify( rsa_context *ctx,
+                                 int (*f_rng)(void *, unsigned char *, size_t),
+                                 void *p_rng,
                                  int mode,
                                  int hash_id,
                                  unsigned int hashlen,
@@ -551,6 +588,8 @@
  * \brief          Do a public RSA and check the message digest
  *
  * \param ctx      points to an RSA public key
+ * \param f_rng    RNG function (Only needed for RSA_PRIVATE)
+ * \param p_rng    RNG parameter
  * \param mode     RSA_PUBLIC or RSA_PRIVATE
  * \param hash_id  SIG_RSA_RAW, SIG_RSA_MD{2,4,5} or SIG_RSA_SHA{1,224,256,384,512}
  * \param hashlen  message digest length (for SIG_RSA_RAW only)
@@ -570,6 +609,8 @@
  *                 keep both hashes the same.
  */
 int rsa_rsassa_pss_verify( rsa_context *ctx,
+                           int (*f_rng)(void *, unsigned char *, size_t),
+                           void *p_rng,
                            int mode,
                            int hash_id,
                            unsigned int hashlen,
diff --git a/include/polarssl/ssl.h b/include/polarssl/ssl.h
index fa644fe..3fc956d 100644
--- a/include/polarssl/ssl.h
+++ b/include/polarssl/ssl.h
@@ -270,7 +270,9 @@
  * Generic function pointers for allowing external RSA private key
  * implementations.
  */
-typedef int (*rsa_decrypt_func)( void *ctx, int mode, size_t *olen,
+typedef int (*rsa_decrypt_func)( void *ctx,
+                        int (*f_rng)(void *, unsigned char *, size_t),
+                        void *p_rng, int mode, size_t *olen,
                         const unsigned char *input, unsigned char *output,
                         size_t output_max_len ); 
 typedef int (*rsa_sign_func)( void *ctx,
diff --git a/library/rsa.c b/library/rsa.c
index e53d9a2..1ef97f8 100644
--- a/library/rsa.c
+++ b/library/rsa.c
@@ -252,10 +252,47 @@
     return( 0 );
 }
 
+#if !defined(POLARSSL_RSA_NO_CRT)
+/*
+ * Generate or update blinding values, see section 10 of:
+ *  KOCHER, Paul C. Timing attacks on implementations of Diffie-Hellman, RSA,
+ *  DSS, and other systems. In : Advances in Cryptology—CRYPTO’96. Springer
+ *  Berlin Heidelberg, 1996. p. 104-113.
+ */
+static int rsa_prepare_blinding( rsa_context *ctx,
+                 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
+{
+    int ret;
+
+    if( ctx->Vf.p != NULL )
+    {
+        /* We already have blinding values, just update them by squaring */
+        MPI_CHK( mpi_mul_mpi( &ctx->Vi, &ctx->Vi, &ctx->Vi ) );
+        MPI_CHK( mpi_mod_mpi( &ctx->Vi, &ctx->Vi, &ctx->N ) );
+        MPI_CHK( mpi_mul_mpi( &ctx->Vf, &ctx->Vf, &ctx->Vf ) );
+        MPI_CHK( mpi_mod_mpi( &ctx->Vf, &ctx->Vf, &ctx->N ) );
+
+        return( 0 );
+    }
+
+    /* Unblinding value: Vf = random number */
+    MPI_CHK( mpi_fill_random( &ctx->Vf, ctx->len - 1, f_rng, p_rng ) );
+
+    /* Blinding value: Vi =  Vf^(-e) mod N */
+    MPI_CHK( mpi_inv_mod( &ctx->Vi, &ctx->Vf, &ctx->N ) );
+    MPI_CHK( mpi_exp_mod( &ctx->Vi, &ctx->Vi, &ctx->E, &ctx->N, &ctx->RN ) );
+
+cleanup:
+    return( ret );
+}
+#endif
+
 /*
  * Do an RSA private key operation
  */
 int rsa_private( rsa_context *ctx,
+                 int (*f_rng)(void *, unsigned char *, size_t),
+                 void *p_rng,
                  const unsigned char *input,
                  unsigned char *output )
 {
@@ -276,6 +313,17 @@
 #if defined(POLARSSL_RSA_NO_CRT)
     MPI_CHK( mpi_exp_mod( &T, &T, &ctx->D, &ctx->N, &ctx->RN ) );
 #else
+    if( f_rng != NULL )
+    {
+        /*
+         * Blinding
+         * T = T * Vi mod N
+         */
+        MPI_CHK( rsa_prepare_blinding( ctx, f_rng, p_rng ) );
+        MPI_CHK( mpi_mul_mpi( &T, &T, &ctx->Vi ) );
+        MPI_CHK( mpi_mod_mpi( &T, &T, &ctx->N ) );
+    }
+
     /*
      * faster decryption using the CRT
      *
@@ -297,6 +345,16 @@
      */
     MPI_CHK( mpi_mul_mpi( &T1, &T, &ctx->Q ) );
     MPI_CHK( mpi_add_mpi( &T, &T2, &T1 ) );
+
+    if( f_rng != NULL )
+    {
+        /*
+         * Unblind
+         * T = T * Vf mod N
+         */
+        MPI_CHK( mpi_mul_mpi( &T, &T, &ctx->Vf ) );
+        MPI_CHK( mpi_mod_mpi( &T, &T, &ctx->N ) );
+    }
 #endif
 
     olen = ctx->len;
@@ -430,7 +488,7 @@
 
     return( ( mode == RSA_PUBLIC )
             ? rsa_public(  ctx, output, output )
-            : rsa_private( ctx, output, output ) );
+            : rsa_private( ctx, f_rng, p_rng, output, output ) );
 }
 #endif /* POLARSSL_PKCS1_V21 */
 
@@ -492,7 +550,7 @@
 
     return( ( mode == RSA_PUBLIC )
             ? rsa_public(  ctx, output, output )
-            : rsa_private( ctx, output, output ) );
+            : rsa_private( ctx, f_rng, p_rng, output, output ) );
 }
 
 /*
@@ -527,7 +585,9 @@
  * Implementation of the PKCS#1 v2.1 RSAES-OAEP-DECRYPT function
  */
 int rsa_rsaes_oaep_decrypt( rsa_context *ctx,
-                            int mode, 
+                            int (*f_rng)(void *, unsigned char *, size_t),
+                            void *p_rng,
+                            int mode,
                             const unsigned char *label, size_t label_len,
                             size_t *olen,
                             const unsigned char *input,
@@ -553,7 +613,7 @@
 
     ret = ( mode == RSA_PUBLIC )
           ? rsa_public(  ctx, input, buf )
-          : rsa_private( ctx, input, buf );
+          : rsa_private( ctx, f_rng, p_rng, input, buf );
 
     if( ret != 0 )
         return( ret );
@@ -618,6 +678,8 @@
  * Implementation of the PKCS#1 v2.1 RSAES-PKCS1-V1_5-DECRYPT function
  */
 int rsa_rsaes_pkcs1_v15_decrypt( rsa_context *ctx,
+                                 int (*f_rng)(void *, unsigned char *, size_t),
+                                 void *p_rng,
                                  int mode, size_t *olen,
                                  const unsigned char *input,
                                  unsigned char *output,
@@ -639,7 +701,7 @@
 
     ret = ( mode == RSA_PUBLIC )
           ? rsa_public(  ctx, input, buf )
-          : rsa_private( ctx, input, buf );
+          : rsa_private( ctx, f_rng, p_rng, input, buf );
 
     if( ret != 0 )
         return( ret );
@@ -711,6 +773,8 @@
  * Do an RSA operation, then remove the message padding
  */
 int rsa_pkcs1_decrypt( rsa_context *ctx,
+                       int (*f_rng)(void *, unsigned char *, size_t),
+                       void *p_rng,
                        int mode, size_t *olen,
                        const unsigned char *input,
                        unsigned char *output,
@@ -719,13 +783,13 @@
     switch( ctx->padding )
     {
         case RSA_PKCS_V15:
-            return rsa_rsaes_pkcs1_v15_decrypt( ctx, mode, olen, input, output,
-                                                output_max_len );
+            return rsa_rsaes_pkcs1_v15_decrypt( ctx, f_rng, p_rng, mode, olen,
+                                                input, output, output_max_len );
 
 #if defined(POLARSSL_PKCS1_V21)
         case RSA_PKCS_V21:
-            return rsa_rsaes_oaep_decrypt( ctx, mode, NULL, 0, olen, input,
-                                           output, output_max_len );
+            return rsa_rsaes_oaep_decrypt( ctx, f_rng, p_rng, mode, NULL, 0,
+                                           olen, input, output, output_max_len );
 #endif
 
         default:
@@ -848,7 +912,7 @@
 
     return( ( mode == RSA_PUBLIC )
             ? rsa_public(  ctx, sig, sig )
-            : rsa_private( ctx, sig, sig ) );
+            : rsa_private( ctx, f_rng, p_rng, sig, sig ) );
 }
 #endif /* POLARSSL_PKCS1_V21 */
 
@@ -859,6 +923,8 @@
  * Do an RSA operation to sign the message digest
  */
 int rsa_rsassa_pkcs1_v15_sign( rsa_context *ctx,
+                               int (*f_rng)(void *, unsigned char *, size_t),
+                               void *p_rng,
                                int mode,
                                int hash_id,
                                unsigned int hashlen,
@@ -971,7 +1037,7 @@
 
     return( ( mode == RSA_PUBLIC )
             ? rsa_public(  ctx, sig, sig )
-            : rsa_private( ctx, sig, sig ) );
+            : rsa_private( ctx, f_rng, p_rng, sig, sig ) );
 }
 
 /*
@@ -989,7 +1055,7 @@
     switch( ctx->padding )
     {
         case RSA_PKCS_V15:
-            return rsa_rsassa_pkcs1_v15_sign( ctx, mode, hash_id,
+            return rsa_rsassa_pkcs1_v15_sign( ctx, f_rng, p_rng, mode, hash_id,
                                               hashlen, hash, sig );
 
 #if defined(POLARSSL_PKCS1_V21)
@@ -1008,6 +1074,8 @@
  * Implementation of the PKCS#1 v2.1 RSASSA-PSS-VERIFY function
  */
 int rsa_rsassa_pss_verify( rsa_context *ctx,
+                           int (*f_rng)(void *, unsigned char *, size_t),
+                           void *p_rng,
                            int mode,
                            int hash_id,
                            unsigned int hashlen,
@@ -1035,7 +1103,7 @@
 
     ret = ( mode == RSA_PUBLIC )
           ? rsa_public(  ctx, sig, buf )
-          : rsa_private( ctx, sig, buf );
+          : rsa_private( ctx, f_rng, p_rng, sig, buf );
 
     if( ret != 0 )
         return( ret );
@@ -1139,6 +1207,8 @@
  * Implementation of the PKCS#1 v2.1 RSASSA-PKCS1-v1_5-VERIFY function
  */
 int rsa_rsassa_pkcs1_v15_verify( rsa_context *ctx,
+                                 int (*f_rng)(void *, unsigned char *, size_t),
+                                 void *p_rng,
                                  int mode,
                                  int hash_id,
                                  unsigned int hashlen,
@@ -1160,7 +1230,7 @@
 
     ret = ( mode == RSA_PUBLIC )
           ? rsa_public(  ctx, sig, buf )
-          : rsa_private( ctx, sig, buf );
+          : rsa_private( ctx, f_rng, p_rng, sig, buf );
 
     if( ret != 0 )
         return( ret );
@@ -1247,6 +1317,8 @@
  * Do an RSA operation and check the message digest
  */
 int rsa_pkcs1_verify( rsa_context *ctx,
+                      int (*f_rng)(void *, unsigned char *, size_t),
+                      void *p_rng,
                       int mode,
                       int hash_id,
                       unsigned int hashlen,
@@ -1256,12 +1328,12 @@
     switch( ctx->padding )
     {
         case RSA_PKCS_V15:
-            return rsa_rsassa_pkcs1_v15_verify( ctx, mode, hash_id,
-                                                hashlen, hash, sig );
+            return rsa_rsassa_pkcs1_v15_verify( ctx, f_rng, p_rng, mode,
+                                                hash_id, hashlen, hash, sig );
 
 #if defined(POLARSSL_PKCS1_V21)
         case RSA_PKCS_V21:
-            return rsa_rsassa_pss_verify( ctx, mode, hash_id,
+            return rsa_rsassa_pss_verify( ctx, f_rng, p_rng, mode, hash_id,
                                           hashlen, hash, sig );
 #endif
 
@@ -1348,7 +1420,7 @@
 
     for( i = 0; i < len; ++i )
         output[i] = rand();
-    
+
     return( 0 );
 }
 
@@ -1407,7 +1479,7 @@
     if( verbose != 0 )
         printf( "passed\n  PKCS#1 decryption : " );
 
-    if( rsa_pkcs1_decrypt( &rsa, RSA_PRIVATE, &len,
+    if( rsa_pkcs1_decrypt( &rsa, &myrand, NULL, RSA_PRIVATE, &len,
                            rsa_ciphertext, rsa_decrypted,
                            sizeof(rsa_decrypted) ) != 0 )
     {
@@ -1431,7 +1503,7 @@
 
     sha1( rsa_plaintext, PT_LEN, sha1sum );
 
-    if( rsa_pkcs1_sign( &rsa, NULL, NULL, RSA_PRIVATE, SIG_RSA_SHA1, 20,
+    if( rsa_pkcs1_sign( &rsa, &myrand, NULL, RSA_PRIVATE, SIG_RSA_SHA1, 20,
                         sha1sum, rsa_ciphertext ) != 0 )
     {
         if( verbose != 0 )
@@ -1443,7 +1515,7 @@
     if( verbose != 0 )
         printf( "passed\n  PKCS#1 sig. verify: " );
 
-    if( rsa_pkcs1_verify( &rsa, RSA_PUBLIC, SIG_RSA_SHA1, 20,
+    if( rsa_pkcs1_verify( &rsa, &myrand, NULL, RSA_PUBLIC, SIG_RSA_SHA1, 20,
                           sha1sum, rsa_ciphertext ) != 0 )
     {
         if( verbose != 0 )
diff --git a/library/ssl_cli.c b/library/ssl_cli.c
index e4a102b..2dca657 100644
--- a/library/ssl_cli.c
+++ b/library/ssl_cli.c
@@ -875,7 +875,7 @@
     SSL_DEBUG_BUF( 3, "parameters hash", hash, hashlen );
 
     if( ( ret = rsa_pkcs1_verify( &ssl->session_negotiate->peer_cert->rsa,
-                                  RSA_PUBLIC,
+                                  NULL, NULL, RSA_PUBLIC,
                                   hash_id, hashlen, hash, p ) ) != 0 )
     {
         SSL_DEBUG_RET( 1, "rsa_pkcs1_verify", ret );
diff --git a/library/ssl_srv.c b/library/ssl_srv.c
index 9ba2294..c62c412 100644
--- a/library/ssl_srv.c
+++ b/library/ssl_srv.c
@@ -1376,7 +1376,8 @@
         }
 
         if( ssl->rsa_key ) {
-            ret = ssl->rsa_decrypt( ssl->rsa_key, RSA_PRIVATE,
+            ret = ssl->rsa_decrypt( ssl->rsa_key, ssl->f_rng, ssl->p_rng,
+                                    RSA_PRIVATE,
                                    &ssl->handshake->pmslen,
                                     ssl->in_msg + i,
                                     ssl->handshake->premaster,
@@ -1497,7 +1498,8 @@
         return( POLARSSL_ERR_SSL_BAD_HS_CERTIFICATE_VERIFY );
     }
 
-    ret = rsa_pkcs1_verify( &ssl->session_negotiate->peer_cert->rsa, RSA_PUBLIC,
+    ret = rsa_pkcs1_verify( &ssl->session_negotiate->peer_cert->rsa, 
+                            NULL, NULL, RSA_PUBLIC,
                             hash_id, hashlen, hash, ssl->in_msg + 6 + n );
     if( ret != 0 )
     {
diff --git a/library/ssl_tls.c b/library/ssl_tls.c
index 1574217..2534379 100644
--- a/library/ssl_tls.c
+++ b/library/ssl_tls.c
@@ -65,12 +65,14 @@
 int (*ssl_hw_record_finish)(ssl_context *ssl) = NULL;
 #endif
 
-static int ssl_rsa_decrypt( void *ctx, int mode, size_t *olen,
+static int ssl_rsa_decrypt( void *ctx,
+                        int (*f_rng)(void *, unsigned char *, size_t),
+                        void *p_rng, int mode, size_t *olen,
                         const unsigned char *input, unsigned char *output,
                         size_t output_max_len )
 {
-    return rsa_pkcs1_decrypt( (rsa_context *) ctx, mode, olen, input, output,
-                              output_max_len );
+    return rsa_pkcs1_decrypt( (rsa_context *) ctx, f_rng, p_rng, mode, olen,
+                              input, output, output_max_len );
 }
 
 static int ssl_rsa_sign( void *ctx,
diff --git a/library/x509parse.c b/library/x509parse.c
index 4b4be66..2aa0499 100644
--- a/library/x509parse.c
+++ b/library/x509parse.c
@@ -3234,7 +3234,7 @@
 
         x509_hash( crl_list->tbs.p, crl_list->tbs.len, hash_id, hash );
 
-        if( !rsa_pkcs1_verify( &ca->rsa, RSA_PUBLIC, hash_id,
+        if( !rsa_pkcs1_verify( &ca->rsa, NULL, NULL, RSA_PUBLIC, hash_id,
                               0, hash, crl_list->sig.p ) == 0 )
         {
             /*
@@ -3367,7 +3367,7 @@
 
         x509_hash( child->tbs.p, child->tbs.len, hash_id, hash );
 
-        if( rsa_pkcs1_verify( &trust_ca->rsa, RSA_PUBLIC, hash_id,
+        if( rsa_pkcs1_verify( &trust_ca->rsa, NULL, NULL, RSA_PUBLIC, hash_id,
                     0, hash, child->sig.p ) != 0 )
         {
             trust_ca = trust_ca->next;
@@ -3434,8 +3434,8 @@
 
     x509_hash( child->tbs.p, child->tbs.len, hash_id, hash );
 
-    if( rsa_pkcs1_verify( &parent->rsa, RSA_PUBLIC, hash_id, 0, hash,
-                           child->sig.p ) != 0 )
+    if( rsa_pkcs1_verify( &parent->rsa, NULL, NULL, RSA_PUBLIC, hash_id, 0,
+                           hash, child->sig.p ) != 0 )
         *flags |= BADCERT_NOT_TRUSTED;
         
     /* Check trusted CA's CRL for the given crt */
diff --git a/programs/pkey/dh_client.c b/programs/pkey/dh_client.c
index b3a2476..68b56aa 100644
--- a/programs/pkey/dh_client.c
+++ b/programs/pkey/dh_client.c
@@ -205,7 +205,7 @@
 
     sha1( buf, (int)( p - 2 - buf ), hash );
 
-    if( ( ret = rsa_pkcs1_verify( &rsa, RSA_PUBLIC, SIG_RSA_SHA1,
+    if( ( ret = rsa_pkcs1_verify( &rsa, NULL, NULL, RSA_PUBLIC, SIG_RSA_SHA1,
                                   0, hash, p ) ) != 0 )
     {
         printf( " failed\n  ! rsa_pkcs1_verify returned %d\n\n", ret );
diff --git a/programs/pkey/dh_server.c b/programs/pkey/dh_server.c
index 9ea2a78..54d6e36 100644
--- a/programs/pkey/dh_server.c
+++ b/programs/pkey/dh_server.c
@@ -197,8 +197,8 @@
     buf[n    ] = (unsigned char)( rsa.len >> 8 );
     buf[n + 1] = (unsigned char)( rsa.len      );
 
-    if( ( ret = rsa_pkcs1_sign( &rsa, NULL, NULL, RSA_PRIVATE, SIG_RSA_SHA1,
-                                0, hash, buf + n + 2 ) ) != 0 )
+    if( ( ret = rsa_pkcs1_sign( &rsa, ctr_drbg_random, &ctr_drbg, RSA_PRIVATE,
+                                SIG_RSA_SHA1, 0, hash, buf + n + 2 ) ) != 0 )
     {
         printf( " failed\n  ! rsa_pkcs1_sign returned %d\n\n", ret );
         goto exit;
diff --git a/programs/pkey/rsa_decrypt.c b/programs/pkey/rsa_decrypt.c
index 0b168f4..d4f54ad 100644
--- a/programs/pkey/rsa_decrypt.c
+++ b/programs/pkey/rsa_decrypt.c
@@ -33,16 +33,20 @@
 #include "polarssl/config.h"
 
 #include "polarssl/rsa.h"
+#include "polarssl/ctr_drbg.h"
+#include "polarssl/entropy.h"
 
 #if !defined(POLARSSL_BIGNUM_C) || !defined(POLARSSL_RSA_C) ||  \
-    !defined(POLARSSL_FS_IO)
+    !defined(POLARSSL_FS_IO) || !defined(POLARSSL_ENTROPY_C) || \
+    !defined(POLARSSL_CTR_DRBG_C)
 int main( int argc, char *argv[] )
 {
     ((void) argc);
     ((void) argv);
 
     printf("POLARSSL_BIGNUM_C and/or POLARSSL_RSA_C and/or "
-           "POLARSSL_FS_IO not defined.\n");
+           "POLARSSL_FS_IO and/or POLARSSL_ENTROPY_C and/or "
+           "POLARSSL_CTR_DRBG_C not defined.\n");
     return( 0 );
 }
 #else
@@ -52,8 +56,11 @@
     int ret, c;
     size_t i;
     rsa_context rsa;
+    entropy_context entropy;
+    ctr_drbg_context ctr_drbg;
     unsigned char result[1024];
     unsigned char buf[512];
+    const char *pers = "rsa_decrypt";
     ((void) argv);
 
     memset(result, 0, sizeof( result ) );
@@ -70,6 +77,18 @@
         goto exit;
     }
 
+    printf( "\n  . Seeding the random number generator..." );
+    fflush( stdout );
+
+    entropy_init( &entropy );
+    if( ( ret = ctr_drbg_init( &ctr_drbg, entropy_func, &entropy,
+                               (const unsigned char *) pers,
+                               strlen( pers ) ) ) != 0 )
+    {
+        printf( " failed\n  ! ctr_drbg_init returned %d\n", ret );
+        goto exit;
+    }
+
     printf( "\n  . Reading private key from rsa_priv.txt" );
     fflush( stdout );
 
@@ -130,7 +149,8 @@
     printf( "\n  . Decrypting the encrypted data" );
     fflush( stdout );
 
-    if( ( ret = rsa_pkcs1_decrypt( &rsa, RSA_PRIVATE, &i, buf, result,
+    if( ( ret = rsa_pkcs1_decrypt( &rsa, ctr_drbg_random, &ctr_drbg,
+                                   RSA_PRIVATE, &i, buf, result,
                                    1024 ) ) != 0 )
     {
         printf( " failed\n  ! rsa_pkcs1_decrypt returned %d\n\n", ret );
diff --git a/programs/pkey/rsa_sign.c b/programs/pkey/rsa_sign.c
index e77dc92..dc49fac 100644
--- a/programs/pkey/rsa_sign.c
+++ b/programs/pkey/rsa_sign.c
@@ -34,16 +34,21 @@
 
 #include "polarssl/rsa.h"
 #include "polarssl/sha1.h"
+#include "polarssl/ctr_drbg.h"
+#include "polarssl/entropy.h"
 
 #if !defined(POLARSSL_BIGNUM_C) || !defined(POLARSSL_RSA_C) ||  \
-    !defined(POLARSSL_SHA1_C) || !defined(POLARSSL_FS_IO)
+    !defined(POLARSSL_SHA1_C) || !defined(POLARSSL_FS_IO) ||    \
+    !defined(POLARSSL_ENTROPY_C) || !defined(POLARSSL_CTR_DRBG_C)
 int main( int argc, char *argv[] )
 {
     ((void) argc);
     ((void) argv);
 
     printf("POLARSSL_BIGNUM_C and/or POLARSSL_RSA_C and/or "
-           "POLARSSL_SHA1_C and/or POLARSSL_FS_IO not defined.\n");
+           "POLARSSL_SHA1_C and/or POLARSSL_FS_IO "
+           "and/or POLARSSL_ENTROPY_C and/or POLARSSL_CTR_DRBG_C "
+           "not defined.\n");
     return( 0 );
 }
 #else
@@ -53,8 +58,11 @@
     int ret;
     size_t i;
     rsa_context rsa;
+    entropy_context entropy;
+    ctr_drbg_context ctr_drbg;
     unsigned char hash[20];
     unsigned char buf[POLARSSL_MPI_MAX_SIZE];
+    const char *pers = "rsa_decrypt";
 
     ret = 1;
 
@@ -69,6 +77,18 @@
         goto exit;
     }
 
+    printf( "\n  . Seeding the random number generator..." );
+    fflush( stdout );
+
+    entropy_init( &entropy );
+    if( ( ret = ctr_drbg_init( &ctr_drbg, entropy_func, &entropy,
+                               (const unsigned char *) pers,
+                               strlen( pers ) ) ) != 0 )
+    {
+        printf( " failed\n  ! ctr_drbg_init returned %d\n", ret );
+        goto exit;
+    }
+
     printf( "\n  . Reading private key from rsa_priv.txt" );
     fflush( stdout );
 
@@ -120,8 +140,8 @@
         goto exit;
     }
 
-    if( ( ret = rsa_pkcs1_sign( &rsa, NULL, NULL, RSA_PRIVATE, SIG_RSA_SHA1,
-                                20, hash, buf ) ) != 0 )
+    if( ( ret = rsa_pkcs1_sign( &rsa, ctr_drbg_random, &ctr_drbg, RSA_PRIVATE,
+                                SIG_RSA_SHA1, 20, hash, buf ) ) != 0 )
     {
         printf( " failed\n  ! rsa_pkcs1_sign returned -0x%0x\n\n", -ret );
         goto exit;
diff --git a/programs/pkey/rsa_verify.c b/programs/pkey/rsa_verify.c
index 2edd70a..db3a010 100644
--- a/programs/pkey/rsa_verify.c
+++ b/programs/pkey/rsa_verify.c
@@ -131,7 +131,7 @@
         goto exit;
     }
 
-    if( ( ret = rsa_pkcs1_verify( &rsa, RSA_PUBLIC, SIG_RSA_SHA1,
+    if( ( ret = rsa_pkcs1_verify( &rsa, NULL, NULL, RSA_PUBLIC, SIG_RSA_SHA1,
                                   20, hash, buf ) ) != 0 )
     {
         printf( " failed\n  ! rsa_pkcs1_verify returned -0x%0x\n\n", -ret );
diff --git a/programs/pkey/rsa_verify_pss.c b/programs/pkey/rsa_verify_pss.c
index ccac58d..b77fbca 100644
--- a/programs/pkey/rsa_verify_pss.c
+++ b/programs/pkey/rsa_verify_pss.c
@@ -124,7 +124,7 @@
         goto exit;
     }
 
-    if( ( ret = rsa_pkcs1_verify( &rsa, RSA_PUBLIC, SIG_RSA_SHA1,
+    if( ( ret = rsa_pkcs1_verify( &rsa, NULL, NULL, RSA_PUBLIC, SIG_RSA_SHA1,
                                   20, hash, buf ) ) != 0 )
     {
         printf( " failed\n  ! rsa_pkcs1_verify returned %d\n\n", ret );
diff --git a/programs/test/benchmark.c b/programs/test/benchmark.c
index 86de2c6..08e3d63 100644
--- a/programs/test/benchmark.c
+++ b/programs/test/benchmark.c
@@ -439,7 +439,7 @@
     for( i = 1; ! alarmed; i++ )
     {
         buf[0] = 0;
-        rsa_private( &rsa, buf, buf );
+        rsa_private( &rsa, myrand, NULL, buf, buf );
     }
 
     printf( "%9lu private/s\n", i / 3 );
@@ -468,7 +468,7 @@
     for( i = 1; ! alarmed; i++ )
     {
         buf[0] = 0;
-        rsa_private( &rsa, buf, buf );
+        rsa_private( &rsa, myrand, NULL, buf, buf );
     }
 
     printf( "%9lu private/s\n", i / 3 );
@@ -497,7 +497,7 @@
     for( i = 1; ! alarmed; i++ )
     {
         buf[0] = 0;
-        rsa_private( &rsa, buf, buf );
+        rsa_private( &rsa, myrand, NULL, buf, buf );
     }
 
     printf( "%9lu private/s\n", i / 3 );
diff --git a/programs/test/o_p_test.c b/programs/test/o_p_test.c
index 3531d54..edb3107 100644
--- a/programs/test/o_p_test.c
+++ b/programs/test/o_p_test.c
@@ -185,7 +185,7 @@
     printf( "  . Generating the RSA decrypted value for OpenSSL (PUBLIC) with PolarSSL (PRIVATE) ..." );
     fflush( stdout );
 
-    if( ( ret = rsa_pkcs1_decrypt( &p_rsa, RSA_PRIVATE, &olen, o_pub_encrypted, p_pub_decrypted, 1024 ) ) != 0 )
+    if( ( ret = rsa_pkcs1_decrypt( &p_rsa, ctr_drbg_random, &ctr_drbg, RSA_PRIVATE, &olen, o_pub_encrypted, p_pub_decrypted, 1024 ) ) != 0 )
     {
         printf( " failed\n  ! rsa_pkcs1_decrypt returned %d\n\n", ret );
     }
@@ -209,7 +209,7 @@
     printf( "  . Generating the RSA decrypted value for OpenSSL (PRIVATE) with PolarSSL (PUBLIC) ..." );
     fflush( stdout );
 
-    if( ( ret = rsa_pkcs1_decrypt( &p_rsa, RSA_PUBLIC, &olen, o_priv_encrypted, p_priv_decrypted, 1024 ) ) != 0 )
+    if( ( ret = rsa_pkcs1_decrypt( &p_rsa, ctr_drbg_random, &ctr_drbg, RSA_PUBLIC, &olen, o_priv_encrypted, p_priv_decrypted, 1024 ) ) != 0 )
     {
         printf( " failed\n  ! rsa_pkcs1_decrypt returned %d\n\n", ret );
     }
diff --git a/tests/suites/test_suite_pkcs1_v21.function b/tests/suites/test_suite_pkcs1_v21.function
index 0c5db1a..2157d0f 100644
--- a/tests/suites/test_suite_pkcs1_v21.function
+++ b/tests/suites/test_suite_pkcs1_v21.function
@@ -61,6 +61,9 @@
     rsa_context ctx;
     mpi P1, Q1, H, G;
     size_t output_len;
+    rnd_pseudo_info rnd_info;
+
+    memset( &rnd_info, 0, sizeof( rnd_pseudo_info ) );
 
     mpi_init( &P1 ); mpi_init( &Q1 ); mpi_init( &H ); mpi_init( &G );
     rsa_init( &ctx, RSA_PKCS_V21, {hash} );
@@ -88,7 +91,7 @@
 
     unhexify( message_str, {message_hex_string} );
 
-    TEST_ASSERT( rsa_pkcs1_decrypt( &ctx, RSA_PRIVATE, &output_len, message_str, output, 1000 ) == {result} );
+    TEST_ASSERT( rsa_pkcs1_decrypt( &ctx, rnd_pseudo_rand, &rnd_info, RSA_PRIVATE, &output_len, message_str, output, 1000 ) == {result} );
     if( {result} == 0 )
     {
         hexify( output_str, output, ctx.len );
@@ -260,7 +263,7 @@
 #endif
     }
 
-    TEST_ASSERT( rsa_pkcs1_verify( &ctx, RSA_PUBLIC, {digest}, 0, hash_result, result_str ) == {result} );
+    TEST_ASSERT( rsa_pkcs1_verify( &ctx, NULL, NULL, RSA_PUBLIC, {digest}, 0, hash_result, result_str ) == {result} );
 
     rsa_free( &ctx );
 }
diff --git a/tests/suites/test_suite_rsa.function b/tests/suites/test_suite_rsa.function
index 6143db1..0e7bb65 100644
--- a/tests/suites/test_suite_rsa.function
+++ b/tests/suites/test_suite_rsa.function
@@ -24,6 +24,9 @@
     rsa_context ctx;
     mpi P1, Q1, H, G;
     int msg_len;
+    rnd_pseudo_info rnd_info;
+
+    memset( &rnd_info, 0, sizeof( rnd_pseudo_info ) );
 
     mpi_init( &P1 ); mpi_init( &Q1 ); mpi_init( &H ); mpi_init( &G );
     rsa_init( &ctx, {padding_mode}, 0 );
@@ -92,7 +95,7 @@
 #endif
     }
 
-    TEST_ASSERT( rsa_pkcs1_sign( &ctx, NULL, NULL, RSA_PRIVATE, {digest}, 0, hash_result, output ) == {result} );
+    TEST_ASSERT( rsa_pkcs1_sign( &ctx, rnd_pseudo_rand, &rnd_info, RSA_PRIVATE, {digest}, 0, hash_result, output ) == {result} );
     if( {result} == 0 )
     {
         hexify( output_str, output, ctx.len );
@@ -168,7 +171,7 @@
 #endif
     }
 
-    TEST_ASSERT( rsa_pkcs1_verify( &ctx, RSA_PUBLIC, {digest}, 0, hash_result, result_str ) == {result} );
+    TEST_ASSERT( rsa_pkcs1_verify( &ctx, NULL, NULL, RSA_PUBLIC, {digest}, 0, hash_result, result_str ) == {result} );
 
     rsa_free( &ctx );
 }
@@ -185,6 +188,9 @@
     rsa_context ctx;
     mpi P1, Q1, H, G;
     int hash_len;
+    rnd_pseudo_info rnd_info;
+
+    memset( &rnd_info, 0, sizeof( rnd_pseudo_info ) );
 
     mpi_init( &P1 ); mpi_init( &Q1 ); mpi_init( &H ); mpi_init( &G );
     rsa_init( &ctx, {padding_mode}, 0 );
@@ -214,7 +220,7 @@
     unhexify( message_str, {message_hex_string} );
     hash_len = unhexify( hash_result, {hash_result_string} );
 
-    TEST_ASSERT( rsa_pkcs1_sign( &ctx, NULL, NULL, RSA_PRIVATE, SIG_RSA_RAW, hash_len, hash_result, output ) == 0 );
+    TEST_ASSERT( rsa_pkcs1_sign( &ctx, rnd_pseudo_rand, &rnd_info, RSA_PRIVATE, SIG_RSA_RAW, hash_len, hash_result, output ) == 0 );
 
     hexify( output_str, output, ctx.len );
 
@@ -249,7 +255,7 @@
     hash_len = unhexify( hash_result, {hash_result_string} );
     unhexify( result_str, {result_hex_str} );
 
-    TEST_ASSERT( rsa_pkcs1_verify( &ctx, RSA_PUBLIC, SIG_RSA_RAW, hash_len, hash_result, result_str ) == {correct} );
+    TEST_ASSERT( rsa_pkcs1_verify( &ctx, NULL, NULL, RSA_PUBLIC, SIG_RSA_RAW, hash_len, hash_result, result_str ) == {correct} );
 
     rsa_free( &ctx );
 }
@@ -335,6 +341,9 @@
     rsa_context ctx;
     mpi P1, Q1, H, G;
     size_t output_len;
+    rnd_pseudo_info rnd_info;
+
+    memset( &rnd_info, 0, sizeof( rnd_pseudo_info ) );
 
     mpi_init( &P1 ); mpi_init( &Q1 ); mpi_init( &H ); mpi_init( &G );
     rsa_init( &ctx, {padding_mode}, 0 );
@@ -363,7 +372,7 @@
     unhexify( message_str, {message_hex_string} );
     output_len = 0;
 
-    TEST_ASSERT( rsa_pkcs1_decrypt( &ctx, RSA_PRIVATE, &output_len, message_str, output, {max_output} ) == {result} );
+    TEST_ASSERT( rsa_pkcs1_decrypt( &ctx, rnd_pseudo_rand, &rnd_info, RSA_PRIVATE, &output_len, message_str, output, {max_output} ) == {result} );
     if( {result} == 0 )
     {
         hexify( output_str, output, ctx.len );
@@ -417,6 +426,9 @@
     unsigned char output_str[1000];
     rsa_context ctx;
     mpi P1, Q1, H, G;
+    rnd_pseudo_info rnd_info;
+
+    memset( &rnd_info, 0, sizeof( rnd_pseudo_info ) );
 
     mpi_init( &P1 ); mpi_init( &Q1 ); mpi_init( &H ); mpi_init( &G );
     rsa_init( &ctx, RSA_PKCS_V15, 0 );
@@ -444,7 +456,7 @@
 
     unhexify( message_str, {message_hex_string} );
 
-    TEST_ASSERT( rsa_private( &ctx, message_str, output ) == {result} );
+    TEST_ASSERT( rsa_private( &ctx, rnd_pseudo_rand, &rnd_info, message_str, output ) == {result} );
     if( {result} == 0 )
     {
         hexify( output_str, output, ctx.len );