Calculating the breakability of a given encryption method

Question

I will soon be doing a very important project for school. The main goal of my project is to find a mathematical way to calculate the breakability of a given encryption method of ciphertext. Is there any way as to how I can calculate how long time it would take a computer the break an RSA encryption or a Vigenère cipher or even a monoalphabetic substitution cipher? And is it possible for a computer or to create an algorithm(s) for a computer to something like frequency analysis?

Answer 1

For "symmetric cryptographic algorithms" (symmetric encryption, MAC...), things are simple: a non-broken cryptographic algorithm is such that it uses an n-bit key, and the fastest method to find the key is trying out all possible keys until the right one is found (that is called exhaustive search or brute force). The algorithm is said "non-broken" precisely because there is no known faster method than exhaustive search. With exhaustive search and an n-bit key, the average number of tries before hitting the right key is 2^n-1. So just multiply that number by the time it takes you to try one key, and you have the complete attack time. Exhaustive search is an embarrassingly parallel problem, meaning that with twice as many computers you find the solution twice as fast.

The effort of trying one key depends on the algorithm and on the context. For instance, for encryption with a block cipher, it usually suffices to decrypt one block (something done within a few dozens or hundreds of clock cycles on a CPU) to see if the corresponding decrypted block is plausible or not (e.g. you know the plaintext is some XML file and you look for the XML header in the first block). When trying to break a MAC, you have to recompute it for each key, which can be expensive if the original MAC was computed over, say, a 50 MB file.

---

Exhaustive search is the attack of choice on symmetric algorithms, where keys are just bunches of bits, and any sequence of bits of the right size is a possible key value. This is not so for asymmetric algorithms such as RSA and ECDSA, where the keys have a lot of internal mathematical structure, and breaking the key means unravelling that structure, which can normally be done a lot faster than trying out all sequences of bits. Since mathematics are involved, things are quite complex. See this site for cost estimates. Note that it is about cost, not just time: depending on the kind of thing you are trying to do, you may need a lot of CPU and a lot of very fast RAM.

---

Pre-computer era cryptosystems, such as Vigenere and its ilk, are invariably weak and breakable within a fraction of a second. Basically, all systems that were practical (a human operator could run them without spending a whole day to encrypt a simple sentence) were also breakable through the sheer mindpower of some specialized individuals (Edgar Allan Poe was rumoured to be extremely good at this kind of task). What a human brain could do in a day back in the 19th century, is now doable in less than a second with a computer. And yes, frequency analysis and all the breaking can be fully automated (a nice programming exercise, but nothing conceptually hard).

Speaking of Poe, read this. This is Poe explaining (through a short story) how to break a substitution cipher, in all its analytic glory; writing all the steps as a computer program is a mere translation from Poe's prose to the aridity of the syntax of a programming language.