Caveat: Provability Issues

Every asymmetric algorithm is based on some trapdoor one-way function. This leads to a critically important question: How do we know for certain that a particular function is truly one-way? Just because nobody has publicly demonstrated a technique that allows the inverse function to be calculated quickly does not actually prove anything about the security of the algorithm. If somebody has quietly discovered a fast technique to compute the inverse function, he or she could be busily decrypting enormous amounts of ciphertext every day, and the public may never become aware of it. It may seem paranoid , but high on the list of suspicions are major governments , since they employ large numbers of brilliant mathematicians who are outfitted with the most powerful computing resources available, putting them in a better position than most for cracking the trapdoor.

Most reassuring would be a rigorous mathematical proof of the inherent difficulty of computing the inverse function without knowledge of the secret key. With such a proof, further attempts at cracking the backdoor would be futile. Currently, rigorous formal proofs on the security of asymmetric algorithms are sorely lacking. Only in a few specialized (and not so useful) cases have any proofs been demonstrated in the public literature.

In spite of this worrisome lack of evidence, most cryptography experts currently believe that popular asymmetric algorithms, such as RSA, are quite secure given that a sufficient key size is used. Note that this is really just a consensus of learned opinion, which falls well short of a rigorous proof. Of course, considering that most ciphers used throughout history were assumed to be secure at the time that they were used, only to be broken using newly discovered attacks, a certain degree of anxiety is warranted.

In the case of RSA, the entire scheme depends on the widely held opinion that there are no techniques known that will allow an attacker to easily calculate the values of d, p, or q given only the public key containing n and e . Of course, this becomes more effective when you use larger values for p and q . C#'s built-in integer types top out at 64 bits for the long data type, which is nowhere near the size that we need for real asymmetric cryptography applications. Instead, we typically want to use integer data types that are represented by 1024-bit or larger words. Another worry is that this technique depends on a critical assumption that is widely believed to be true but has never been mathematically proven. The assumption is that there are in fact no tricks or fast techniques for factoring pq into its prime factors p and q . In fact, it has never been proven that factoring pq into p and q is the only way to attack RSA. If someone was either smart enough or lucky enough to dismantle these assumptions, that person could become the richest person in the world but would likely be a candidate for assassination.