To expand a little, the NSA also required the initial permutation of plaintext bits. This was done before the first 16 rounds of DES, and looked like this:
Which meant "put the 58th bit of the plaintext into the first position, put the 50th bit into the second position, etc, and THEN run through the encryption algorithm."
At the time, it was totally unclear why you had rearrange the bits in this very exact way. After all, you were about to encrypt it (and obliterate any plaintext patterns) anyway. And would it be as strong if you started with the 57th bit, instead of the 58th? The whole thing seemed so arbitrary.
Now it's true that this is robust to differential cryptanalysis, but it's also true that these bit permutations significantly slow down software implentations of DES. But it's trivial to implement the initial permutation in hardware.
In the 1970s, the hardware required to crack DES costed $20,000,000 US dollars [1] (about $120 million in today's dollar [2]). The general tinfoil-theory at the time was that 1) only the NSA had the resources to build such a machine and 2) by forcing DES to use this initial permutation, the NSA was giving themselves a significant "head-start" over everybody else using software to crack DES.
The permutations in DES have nothing to do with security; there is an excellent explanation by Thomas Pornin on what their purpose was: http://crypto.stackexchange.com/a/6/592
What was altered were the 8 S-boxes, seemingly random lookup tables that map 6- to 4-bit values. More details by Don Coppersmith himself at: http://simson.net/ref/1994/coppersmith94.pdf
I phrased that poorly (and just edited my first sentence to reflect your correction). What I was trying to add was that the NSA made some other modifications to DES that were also seen as dubious at the time.
At the time, it was totally unclear why you had rearrange the bits in this very exact way. After all, you were about to encrypt it (and obliterate any plaintext patterns) anyway. And would it be as strong if you started with the 57th bit, instead of the 58th? The whole thing seemed so arbitrary.
Now it's true that this is robust to differential cryptanalysis, but it's also true that these bit permutations significantly slow down software implentations of DES. But it's trivial to implement the initial permutation in hardware.
In the 1970s, the hardware required to crack DES costed $20,000,000 US dollars [1] (about $120 million in today's dollar [2]). The general tinfoil-theory at the time was that 1) only the NSA had the resources to build such a machine and 2) by forcing DES to use this initial permutation, the NSA was giving themselves a significant "head-start" over everybody else using software to crack DES.
[1]http://www.krapp.org/hydra/courses/analysis/3-DataEn.pdf (PDF) [2]http://www.wolframalpha.com/input/?i=%2420%2C000%2C000+1970+...