BouncyCastle stopped working on Android 13

[markusbug]

I have a system service running on Android which uses BouncyCastle to create a "secp256k1" KeyPair. This is the code:

KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("ECDSA", "BC");
ECGenParameterSpec ecGenParameterSpec = new ECGenParameterSpec("secp256k1");

And before executing this piece of code I call the setupBouncyCastle method, which is this:

    private Provider setupBouncyCastle() {
        final Provider provider = Security.getProvider(BouncyCastleProvider.PROVIDER_NAME);
        if (provider == null) {
            // Web3j will set up the provider lazily when it's first used.
            return provider;
        }
        if (provider.getClass().equals(BouncyCastleProvider.class)) {
            // BC with same package name, shouldn't happen in real life.
            return provider;
        }
        // Android registers its own BC provider. As it might be outdated and might not
        // include
        // all needed ciphers, we substitute it with a known BC bundled in the app.
        // Android's BC has its package rewritten to "com.android.org.bouncycastle" and
        // because
        // of that it's possible to have another BC implementation loaded in VM.
        Security.removeProvider(BouncyCastleProvider.PROVIDER_NAME);
        Security.insertProviderAt(new BouncyCastleProvider(), 1);
        return provider;
    }

This all worked perfectly fine on Android 12L, but I am upgrading to Android 13 and now I get the exception: java.security.NoSuchAlgorithmException: no such algorithm: ECDSA for provider BC. Note: This is the same exception that I got on Android 12L if I didn't execute setupBouncyCastle. It seems like this method stopped working on Android 13?

If anybody has some details or an idea of what could be going on would be greatly appreciated!

Thanks in advance!