Airbus crypto challenge write-up

[baby]

http://cryptologie.net/article/182/airbus-crypto-challenge-write-up/

[tptacek]

This is a good writeup. If you're interested: the e=3 broadcast attack rounds out set 5 of our (unrelated) crypto challenges:

http://cryptopals.com/sets/5/

The e=3 broadcast attack is pretty unrealistic (I'm not sure we ever had to actually exploit it), but the stuff in set 6 comes up all the time, and breaks non-textbook realistic RSA.

I don't know why e=3 broadcast is so popular in entry-level crypto challenges, but this attack is also a CTF favorite.

[baby → tptacek]

ummm, I read up somewhere that e=3 used to be used quite a lot to speed up computations.

[tptacek → baby]

e=3 isn't itself a vulnerability. Read the writeup more carefully. :)

[pbsd]

> The Chinese Remainder Theorem works in a similar fashion to Lagrange Interpolation

They're not only similar---they're the same thing. Notice that f(a), for some polynomial f(x), is equivalent to f mod (x - a). Then Lagrange interpolation can be seen as recovering f from [f mod (x - a_0), f mod (x - a_1), ...], using the same mechanism---over a different ring---as the CRT. In fact, the CRT works over any ring that has unique factorization and well-behaved divisibility (i.e., greatest common divisors work as in the integers).

[sdevlin]

> RSA Encrytion uses padding (usually OAEP)

Heh.