[ Date Index ] [ Thread Index ] [ <= Previous by date / thread ] [ Next by date / thread => ]
On Fri, 6 Sep 2013, bad apple wrote:
formally proved maths remains invulnerable
I'd like to nuance this a little. TL;DR in theory this isn't true, in practise it is.When crypto uses maths, it's usually a computation that can not easily be inversed. RSA, for instance, is based on the fact that it is (relatively) easy to two find prime numbers of a given length n, but it's really hard, given the composite number (of length 2n), to find the original two prime numbers. Depending on n, it's a difference between "takes less than a second" and "takes centuries".
The tricky bit here is the 'easily'. It hasn't been proven in this case (and many other cases) that there really isn't a fast algorithm for factoring large integers. In theory, someone could find such an algorithm tomorrow and thus break most of the assymmetric crypto used in the world.
In practise, because RSA is old (it was invented in the 1970s) and the interest in integer factorization is even older, it's generally believed that there isn't an easy way to factor large integers.
There has been some fuss made (in a BlackHat presentation that got picked up in the press) about recent developments in discrete logarithms, another 'hard' problem that's important for cryptography, and again, it's not really proven that it's hard. Here, in some very special cases, it turns out to be not as hard as one thought. Most experts believe that these cases are too special to have any serious consequences, but it can't ever be 100% exclused that one day someone makes a major breakthrough - or that someone, like the NSA, has already done so.
Some newer cryptography uses elliptic curves. This uses maths that's a lot less basic than RSA (or Diffie-Helman) and doesn't go as far back as those algorithms. This makes it slightly more likely that someone will find (or will have found) weaknesses in the mathematics that's used. It's still extremely unlikely that the 'hard' problem for elliptic curves turns out to be easy, but there may be special cases (i.e. special curves) for which this is the case.
In this context, it may be worth having a look at http://en.wikipedia.org/wiki/Dual_EC_DRBG#Controversywhich is about a crypto standard that possibly includes backdoors. Technically, this still means the implementation that's wrong, not the maths, but the backdoor is inside the way the maths is used, not in the code.
Martijn. -- The Mailing List for the Devon & Cornwall LUG http://mailman.dclug.org.uk/listinfo/list FAQ: http://www.dcglug.org.uk/listfaq