What is the correct test/s to do in asymmetric algorithms to test their security?

Question

I would do some test for evaluating security in asymmetric algorithms such as RSA and ElGamal to evaluate which of both are safer.

The basic problem is that I need to test the security of some symmetric and asymmetric algorithms to evaluate their security and to know which algorithm is more secure and his strength against real-time attacks. In both type of algorithms I have made a table with their vulnerabilities, but I want to test their security with some specific test. Then, I need a test that allows me to conclude that algorithm is safer, for both symmetric and asymmetric algorithms.

For instance, in symmetric algorithms the test that you can use is the avalanche effect link, but in asymmetric algorithms I have not found anyone and I only know that the avalanche effect is not for this type of cryptography.

Any suggestions on the possible test?

Answer 1

If you're looking to test the parameters for an RSA or ElGamal implementation, well, that's fairly straightforward (assuming you can look at the innards of the implementation, and ask "are these primes drawn from a random distribution, do you get the RSA padding right, are you secure against the relevant side channel attacks, etc). You really do need to know your crypto, but it's not that hard.

On the other hand, if you've devised your own public key cryptosystem, well, that's much harder. Actually, symmetric cryptosystems aren't that much easier; the 'avalanche' test that you alluded to is a very weak test; a cipher can easily pass that with flying colors, and still be very weak.

In both cases, the real test is 'can a clever individual who has access to the ciphertext, possibly some plaintext, and (in the case of public key cryptosystems) the public key find an attack'. That's not an easy question to answer (or so you hope, if there is an easy answer, it's be 'yes, here's this attack').

With public key cryptosytems, the obvious place to start is the 'hard problem' they're based on; why precisely do we think it's hard. For RSA, well, it's the "RSA problem" (typically, people say factoring, however that's not proven to be true); for ElGamal, it's the Diffie-Hellman problem. In your case, you need to consider what problem makes it easy (with a public key) to perform in one direction, and hard (with a public key, but not the private) to perform in the other direction.

Issues with the hard problem aren't the only possible way a system can fail (consider RSA with no padding; the RSA problem remains hard, but we can find ways to break the system by taking advantage of the homomorphic properties of raw RSA); however it's the obvious place to start.

Answer 2

Cycle length distributions and other pseudorandom characteristics of the encryption and decryption mappings come to mind. For example, $$f_e:Z_{pq}^{\ast}\rightarrow Z_{pq}^{\ast}$$ for the map $f_e:m\rightarrow m^e$ for RSA.

Other obvious tests and theoretical results have been focused on behaviour of certain bits of such mappings. Their behaviour under restrictions such as fixing a certain fraction of bits of $e$ and varying the rest, or restricting the bitsize of say $e$ to a fraction of the bitsize of $pq,$ and then investigating security. There are attacks on RSA under such restrictions, e.g., by Coppersmith.