diff --git a/ChangeLog.d/aria-alt.txt b/ChangeLog.d/aria-alt.txt
new file mode 100644
index 0000000..20aaa2b
--- /dev/null
+++ b/ChangeLog.d/aria-alt.txt
@@ -0,0 +1,5 @@
+Bugfix
+   * Fix some issues affecting MBEDTLS_ARIA_ALT implementations: a misplaced
+     directive in a header and a missing initialization in the self-test.
+   * Fix a missing initialization in the Camellia self-test, affecting
+     MBEDTLS_CAMELLIA_ALT implementations.
diff --git a/ChangeLog.d/psa-without-genprime-fix.txt b/ChangeLog.d/psa-without-genprime-fix.txt
new file mode 100644
index 0000000..8a7153a
--- /dev/null
+++ b/ChangeLog.d/psa-without-genprime-fix.txt
@@ -0,0 +1,5 @@
+Bugfix
+   * Restore the ability to configure PSA via Mbed TLS options to support RSA
+     key pair operations but exclude RSA key generation. When MBEDTLS_GENPRIME
+     is not defined PSA will no longer attempt to use mbedtls_rsa_gen_key().
+     Fixes #4512.
diff --git a/include/mbedtls/aria.h b/include/mbedtls/aria.h
index a4b27b3..6c73d10 100644
--- a/include/mbedtls/aria.h
+++ b/include/mbedtls/aria.h
@@ -61,14 +61,14 @@
 /* MBEDTLS_ERR_ARIA_HW_ACCEL_FAILED is deprecated and should not be used. */
 #define MBEDTLS_ERR_ARIA_HW_ACCEL_FAILED      -0x0058  /**< ARIA hardware accelerator failed. */
 
-#if !defined(MBEDTLS_ARIA_ALT)
-// Regular implementation
-//
-
 #ifdef __cplusplus
 extern "C" {
 #endif
 
+#if !defined(MBEDTLS_ARIA_ALT)
+// Regular implementation
+//
+
 /**
  * \brief The ARIA context-type definition.
  */
diff --git a/library/aria.c b/library/aria.c
index 1875635..a5786b3 100644
--- a/library/aria.c
+++ b/library/aria.c
@@ -921,7 +921,7 @@
         {                                   \
             if( verbose )                   \
                 mbedtls_printf( "failed\n" );       \
-            return( 1 );                    \
+            goto exit;                              \
         } else {                            \
             if( verbose )                   \
                 mbedtls_printf( "passed\n" );       \
@@ -935,6 +935,7 @@
     int i;
     uint8_t blk[MBEDTLS_ARIA_BLOCKSIZE];
     mbedtls_aria_context ctx;
+    int ret = 1;
 
 #if (defined(MBEDTLS_CIPHER_MODE_CFB) || defined(MBEDTLS_CIPHER_MODE_CTR))
     size_t j;
@@ -946,6 +947,8 @@
     uint8_t buf[48], iv[MBEDTLS_ARIA_BLOCKSIZE];
 #endif
 
+    mbedtls_aria_init( &ctx );
+
     /*
      * Test set 1
      */
@@ -1065,7 +1068,11 @@
         mbedtls_printf( "\n" );
 #endif /* MBEDTLS_CIPHER_MODE_CTR */
 
-    return( 0 );
+    ret = 0;
+
+exit:
+    mbedtls_aria_free( &ctx );
+    return( ret );
 }
 
 #endif /* MBEDTLS_SELF_TEST */
diff --git a/library/camellia.c b/library/camellia.c
index d60f931..f7e0136 100644
--- a/library/camellia.c
+++ b/library/camellia.c
@@ -942,9 +942,11 @@
     unsigned char nonce_counter[16];
     unsigned char stream_block[16];
 #endif
+    int ret = 1;
 
     mbedtls_camellia_context ctx;
 
+    mbedtls_camellia_init( &ctx );
     memset( key, 0, 32 );
 
     for( j = 0; j < 6; j++ ) {
@@ -974,8 +976,7 @@
         {
             if( verbose != 0 )
                 mbedtls_printf( "failed\n" );
-
-            return( 1 );
+            goto exit;
         }
     }
 
@@ -1027,8 +1028,7 @@
             {
                 if( verbose != 0 )
                     mbedtls_printf( "failed\n" );
-
-                return( 1 );
+                goto exit;
             }
         }
 
@@ -1071,8 +1071,7 @@
             {
                 if( verbose != 0 )
                     mbedtls_printf( "failed\n" );
-
-                return( 1 );
+                goto exit;
             }
         }
         else
@@ -1087,8 +1086,7 @@
             {
                 if( verbose != 0 )
                     mbedtls_printf( "failed\n" );
-
-                return( 1 );
+                goto exit;
             }
         }
 
@@ -1100,7 +1098,11 @@
         mbedtls_printf( "\n" );
 #endif /* MBEDTLS_CIPHER_MODE_CTR */
 
-    return( 0 );
+    ret = 0;
+
+exit:
+    mbedtls_camellia_free( &ctx );
+    return( ret );
 }
 
 #endif /* MBEDTLS_SELF_TEST */
diff --git a/library/psa_crypto.c b/library/psa_crypto.c
index f92b5c4..339370e 100644
--- a/library/psa_crypto.c
+++ b/library/psa_crypto.c
@@ -4872,7 +4872,8 @@
     }
     else
 
-#if defined(MBEDTLS_PSA_BUILTIN_KEY_TYPE_RSA_KEY_PAIR)
+#if defined(MBEDTLS_PSA_BUILTIN_KEY_TYPE_RSA_KEY_PAIR) && \
+    defined(MBEDTLS_GENPRIME)
     if ( type == PSA_KEY_TYPE_RSA_KEY_PAIR )
     {
         return( mbedtls_psa_rsa_generate_key( attributes,
@@ -4881,7 +4882,8 @@
                                               key_buffer_length ) );
     }
     else
-#endif /* defined(MBEDTLS_PSA_BUILTIN_KEY_TYPE_RSA_KEY_PAIR) */
+#endif /* defined(MBEDTLS_PSA_BUILTIN_KEY_TYPE_RSA_KEY_PAIR)
+        * defined(MBEDTLS_GENPRIME) */
 
 #if defined(MBEDTLS_PSA_BUILTIN_KEY_TYPE_ECC_KEY_PAIR)
     if ( PSA_KEY_TYPE_IS_ECC( type ) && PSA_KEY_TYPE_IS_KEY_PAIR( type ) )
diff --git a/library/psa_crypto_rsa.c b/library/psa_crypto_rsa.c
index 1ab1e94..08db7a4 100644
--- a/library/psa_crypto_rsa.c
+++ b/library/psa_crypto_rsa.c
@@ -274,7 +274,8 @@
 #endif /* defined(BUILTIN_KEY_TYPE_RSA_KEY_PAIR) ||
         * defined(BUILTIN_KEY_TYPE_RSA_PUBLIC_KEY) */
 
-#if defined(BUILTIN_KEY_TYPE_RSA_KEY_PAIR)
+#if defined(BUILTIN_KEY_TYPE_RSA_KEY_PAIR) && \
+    defined(MBEDTLS_GENPRIME)
 static psa_status_t psa_rsa_read_exponent( const uint8_t *domain_parameters,
                                            size_t domain_parameters_size,
                                            int *exponent )
@@ -332,7 +333,8 @@
 
     return( status );
 }
-#endif /* defined(BUILTIN_KEY_TYPE_RSA_KEY_PAIR) */
+#endif /* defined(BUILTIN_KEY_TYPE_RSA_KEY_PAIR)
+        * defined(MBEDTLS_GENPRIME) */
 
 /****************************************************************/
 /* Sign/verify hashes */
@@ -565,7 +567,8 @@
 #endif /* defined(MBEDTLS_PSA_BUILTIN_KEY_TYPE_RSA_KEY_PAIR) ||
         * defined(MBEDTLS_PSA_BUILTIN_KEY_TYPE_RSA_PUBLIC_KEY) */
 
-#if defined(MBEDTLS_PSA_BUILTIN_KEY_TYPE_RSA_KEY_PAIR)
+#if defined(MBEDTLS_PSA_BUILTIN_KEY_TYPE_RSA_KEY_PAIR) && \
+    defined(MBEDTLS_GENPRIME)
 psa_status_t mbedtls_psa_rsa_generate_key(
     const psa_key_attributes_t *attributes,
     uint8_t *key_buffer, size_t key_buffer_size, size_t *key_buffer_length )
@@ -573,7 +576,8 @@
     return( rsa_generate_key( attributes, key_buffer, key_buffer_size,
                               key_buffer_length ) );
 }
-#endif /* defined(MBEDTLS_PSA_BUILTIN_KEY_TYPE_RSA_KEY_PAIR) */
+#endif /* defined(MBEDTLS_PSA_BUILTIN_KEY_TYPE_RSA_KEY_PAIR)
+        * defined(MBEDTLS_GENPRIME) */
 
 #if defined(MBEDTLS_PSA_BUILTIN_ALG_RSA_PKCS1V15_SIGN) || \
     defined(MBEDTLS_PSA_BUILTIN_ALG_RSA_PSS)
diff --git a/tests/scripts/all.sh b/tests/scripts/all.sh
index 0713ed4..dd3dbb7 100755
--- a/tests/scripts/all.sh
+++ b/tests/scripts/all.sh
@@ -848,6 +848,15 @@
     support_test_zlib_make "$@"
 }
 
+component_test_psa_crypto_rsa_no_genprime() {
+    msg "build: default config minus MBEDTLS_GENPRIME"
+    scripts/config.py unset MBEDTLS_GENPRIME
+    make
+
+    msg "test: default config minus MBEDTLS_GENPRIME"
+    make test
+}
+
 component_test_ref_configs () {
     msg "test/build: ref-configs (ASan build)" # ~ 6 min 20s
     CC=gcc cmake -D CMAKE_BUILD_TYPE:String=Asan .
diff --git a/tests/suites/test_suite_psa_crypto.data b/tests/suites/test_suite_psa_crypto.data
index cb0cb9c..4d9c7b6 100644
--- a/tests/suites/test_suite_psa_crypto.data
+++ b/tests/suites/test_suite_psa_crypto.data
@@ -3369,7 +3369,7 @@
 generate_key:PSA_KEY_TYPE_RSA_KEY_PAIR:512:PSA_KEY_USAGE_EXPORT | PSA_KEY_USAGE_ENCRYPT | PSA_KEY_USAGE_DECRYPT:PSA_ALG_RSA_PKCS1V15_CRYPT:PSA_SUCCESS:0
 
 PSA generate key: RSA, 1024 bits, good, encrypt (OAEP SHA-256)
-depends_on:PSA_WANT_ALG_RSA_OAEP:PSA_WANT_ALG_SHA_256:PSA_WANT_KEY_TYPE_RSA_KEY_PAIR:MBEDTLS_MD_C
+depends_on:PSA_WANT_ALG_RSA_OAEP:PSA_WANT_ALG_SHA_256:PSA_WANT_KEY_TYPE_RSA_KEY_PAIR:MBEDTLS_GENPRIME:MBEDTLS_MD_C
 generate_key:PSA_KEY_TYPE_RSA_KEY_PAIR:1024:PSA_KEY_USAGE_EXPORT | PSA_KEY_USAGE_ENCRYPT | PSA_KEY_USAGE_DECRYPT:PSA_ALG_RSA_OAEP(PSA_ALG_SHA_256):PSA_SUCCESS:0
 
 PSA generate key: RSA, 0 bits: invalid