How to thoroughly test classes that use interfaces

I implemented a class that uses several different algorithms that need to be interchangeable, thus, I use interfaces. Now I want to test my class, but since I used Interfaces, I can not instantiate the algorithms.

What is the best way to test the class independently from the interfaces? In the test, I would like to assume that every interface behaves like it is supposed to be.

Background:

I'm currently working on a project where I have to implement a cryptographic construction that uses several cryptographic primitives (like Signatures, Macs etc.). The goal of this implementation is to have one generic implementation that uses no specific primitives and then instantiating the primitives so that the construction actually works.

I implemented the generic construction using only interfaces. I use Factories to get specific primitives, and everything seems good so far. But, of course, I need to test my code.

I researched a bit, and unfortunately, I did not find an exact answer to my question (Maybe, because I used the wrong search queries). Most of the time people want to test interfaces or the implementation of an interface. But that does not apply to my case.

I read about Mockito, but most examples are straightforward, where Mockito simulates a database, and I do not know if Mockito is still the best way to test in my case, especially if I want to simulate Signatures, where I use asymmetric keys. If I use Mockito, I imagine the code gets messy, because of the "in-line" nature of Mockitos declarations.

Is Mockito (or Mocks in general) applicable for this kind of test, or do I have to implement (basic) implementations of my interfaces?

Example:

So my 'main' class has an algorithm set:

AlgorithmSet algorithmSet;

This algorithmSet consists of AlgorithmFactories

HashFactory HashFactory;
SignatureFactory signatureFactory;
SymmetricKeyFactory keyFactory;

In my 'main' class I call functions of the algorithm similar to this:

Signature signatureScheme = algorithmSet.getSignatureFactory().getSignature();
SignatureKeyPair keyPair = signatureScheme.generateKey();
SignatureOutput signature = signatureScheme.sign(keyPair.getPrivateKey(), message);

This is only a small example I put together for the sake of this question, so my actual code looks a bit different, but this is the gist of it.

Signature, SignatureKeyPair, SignatureOutput are all interfaces because in my 'main' class I do not care what they are if they fulfill their purpose.

What is the best way to test the 'main' class in my case? Is Mockito still the best way? Or is it better to make basic implementations of all the interfaces to enhance readability? There are like 5 algorithms( each with Output, Keys and so on). Or is there another way I did not manage to find yet?

I really appreciate every help and thanks for reading!