Merchants who take credit cards over the Internet for payment need to get rid of the number the microsecond after they've placed a hold on the funds, because it is impossible to store that number in a form that is both searchable and secure. The best choice to limit the liability and exposure for your company is to pass the buck--cryptographically--as soon and as quickly as possible. This means using a credit card processor, like Authorize.Net, which can exchange the number for a transaction ID (called tokenization). The transaction ID is worthless to a hacker, because he can't use it to charge the card again and the money couldn't be redirected to his account or benefit either. This card processing company should also be able to perform a search on the card number and return all of the transaction IDs that were associated with it, should the need arise--which it will.
When securing your customer's payment data, you need to assume that there is no server that can be completely secured against intrusion. If you lose your database for whatever reason (SQL injection, rogue employee, stolen backup tapes, some idiot plugging in a USB flash drive they found in a nearby cafe) you want to be confident that the attacker will gain nothing of particular value to him, and nothing that'd harm your customers. Unless you're running a bordello, you can assume the loss of names and addresses isn't nearly as bad as losing credit cards. Despite the practice of using Card Security Codes (a value you're prohibited from storing on disk at all) those 16-digit numbers are still far too potent.
Tokenization is the best choice even if you need to re-bill a card for subscriptions or extend a convenience to repeat customers. But why? Many merchants think they can ignore this advice because they use cryptography and have legitimate business reasons to store the full card number anyway.
In the course of disputing a charge a cardholder (sometimes your customer, sometimes just a fraud victim) will take up the issue with her credit card company. This may be, in fact, the only thing they can do if they were a victim of fraud because they may not even know how to contact you. From your point of view all you'll know about the complaint will be a letter that comes in the mail with the credit card account number printed on it, the dollar amount, and a statement that the charge is being reversed (the letter isn't even in a security envelope). For you, the merchant, it'll be necessary to search for the order that was paid for with that card, mark it as fraudulent and begin whatever recovery process you can (police, reversing shipments, insurance claims, etc.).
And it's necessary to collect data on fraudulent orders because the credit card companies will stick you with the bill. You shipped the goods, but the money just evaporated from your account, and to prevent that from happening again you need to know where it was shipped and who placed the order so you can cancel any more orders that come in from the same crook.
Storing card numbers in an unsearchable form is simple with the correct discipline: encrypt with an asymmetric cipher (PGP will do) and practice good key management. But these ciphers use a random session key every time they encrypt something, so it isn't possible to search with a number by--say--encrypting the same number with the same cipher and key and searching your database for the ciphertext.
"Ah hah, but I'll just hash the number!" you say, knowing that hashing algorithms like the SHA family are extremely preimage resistant--meaning you can't take a hash value and run it in reverse to discover the original number. This is even a recommendation of the PCI (Payment Card Industry), who seem to think it's fine. You can't "un-bake a cake", so to speak.
But credit card numbers are so small. They're only 14 to 16 digits. If you merely hashed them then a hacker with a rainbow table would unlock your entire database in seconds.
So you'll salt them, right? You'll salt the hash (concatenate the number with a unique word) and that will prevent the use of a rainbow table, right? Wrong again.
First of all, never consider the salt to be like a secret password. In order to salt the card number your server will need to have the salt value in a plaintext form. Even if you encrypt the salt, the key to decrypt it will still need to be on the server--on disk or in recoverable RAM. Since we're assuming that the hacker has already compromised your server in order to steal the database in the first place, then we can't count on the salt being secret either.
The salt means the attacker won't be able to use a rainbow table alright, but now the recovery of almost all the card numbers in your database is just a matter of time. In fact, over 70% of all hashed credit card numbers can be discovered via brute-force attack--without a rainbow table--in less than 2 days. Here's why:
After all this, an attacker may have a mere 6-digit keyspace to brute-force for each number. Who needs a rainbow table now?
Any firm that must store card numbers in a searchable form has an intractable problem foisted on them by the credit card industry itself: credit card numbers are inherently insecure. So you try your best to live up to the spirit of the PCI requirements and strengthen those hashes by re-hashing them a hundred thousand times, forcing a contemporary Intel Pentium to spend a whole whopping second on each hash value. But the attacker just comes back with a botnet--a hundred thousand compromised desktop PCs strong--and breaks through that barrier like tissue.
TJX and Heartland are two examples of how badly it can go when credit card databases are compromised, and the mess is horrific to clean up. In addition to unauthorized theft, consumers are now seeing how the merchants they thought they could trust are in cahoots with semi-legitimized scammers, in league to trick them into approving the transfer of their account numbers behind the scenes.
Credit card numbers are doomed as a form of online payment.
It's in a consumer's best interest to use a form of payment that cannot be re-billed, such as PayPal or Google Checkout. With both of these payment methods the merchant gets nothing but a transaction ID from the beginning, and as a merchant you want this. It means no more liability and no more front-page headlines when your database gets compromised.
But until it becomes commercially practical to eschew credit cards as a form of payment, the best strategy is to wash your hands of the number--at least in searchable form--as soon as possible. In fact, it's probably in your best interests not to keep the number in any form at all, even PGP encrypted, in case there's a mishap with your key management. Processing intermediaries like Cybersource/Authorize.net can tokenize the card number and relieve you of a risk that you don't need. They can also provide options for recurring billing (subscriptions, repeat customers).
If you chose to dance with the devil, however, keep these things in mind: