Cryptogram: AES Broken?

bcrowell writes "The latest CryptoGram reports that AES (Rijndael) and Serpent may have been broken. The good news is that when cryptographers say 'broken' they don't necessarily mean broken in a way that is practical to exploit right now. Still, maybe we need to assume that any given type of crypto is only temporary. All of cryptography depends on a small number of problems that are believed to be hard. And all bets are definitely off when quantum computers arrive on the scene. Maybe someday we'll look back fondly on the golden age of privacy."

Comments

gross oversimplification

[jukal]

Basically, the attack works by trying to express the entire algorithm as multivariate quadratic polynomials, and then using an innovative technique to treat the terms of those polynomials as individual variables. This gives you a system of linear equations in a quadratically large number of variables, which you have to solve. There are a bunch of minimization techniques, and several other clever tricks you can use to make the solution easier. (This is a gross oversimplification of the paper; read it for more detail.)

Uhm. emm. EZ? :)

Factorisation of large primes is easy

[Anonymous Coward]

Contrary to what appears to be a prevailing belief on slashdot that it's difficult to factor large primes, with current advances in parallel computation and quantum computing this is actually quite an easy task. I present to you the following 1024 bit prime:

111961017586322450238441928964701918986406535146 65 33122260611723888664118831927114653575316547424879 67054992318167167095961043128510261482045202676936 47431644268978597959467064464952515251208388024556 04572811477056415455786097885500638657240210061581 08559815836672945846673382320520984676311151395887 519279703

Now we have to factor it. We step up to the main terminal of our quantum computer beowulf cluster and type in the question, "Of which numbers is this the product?". Qubits flip, waveforms collapse, a cat in a box somewhere dies (of radiation poisoning, strangely, or charmingly), and out pops the statement:

111961017586322450238441928964701918986406535146 65 33122260611723888664118831927114653575316547424879 67054992318167167095961043128510261482045202676936 47431644268978597959467064464952515251208388024556 04572811477056415455786097885500638657240210061581 08559815836672945846673382320520984676311151395887 519279703 * 1 = 11196101758632245023844192896470191898640653514665 33122260611723888664118831927114653575316547424879 67054992318167167095961043128510261482045202676936 47431644268978597959467064464952515251208388024556 04572811477056415455786097885500638657240210061581 08559815836672945846673382320520984676311151395887 519279703