Quote from: eJ3k1 on August 11, 2012, 08:38 amQuote from: pine on August 10, 2012, 04:12 pmTo put this in some perspective, in 2009 several cryptanalysts factored a 232 digit number, using hundreds of machines over 2 years (the number above is 309 digits long and you haven't even seen the length of the prime multiplication yet).Wait a second. The largest pseudoprime that is cracked (factored) was a 232 digit number. The two primes in a 1024 digit key are both around 300 long. Therefore, the pseudoprime (what you get when you multiply the two), is around 600 digits long. That is way way bigger.Can I conclude from that, that -with technology as it is today- a 1024b key is actually extremely safe and anything bigger is overkill?No. For one thing, quantum cryptanalysis with quantum computer is going to become available as a service at some point and when it does the majority of popular algorithms used in asymmetric encryption lose half their efficiency, turning a 1024 bit key into the equivalent of a 512 bit one.Secondly 1024 bit RSA keys have been already cracked using off the shelf hardware 2 years ago in 100 hours. Cryptanalysis is not just about pure computing power and factorizing to hunt primes, there are weaknesses like the fact that good pseduorandom numbers are hard to generate, human factors etc. You have to constantly keep in mind that there are people with Eisenstein levels of intellect trying to break keys/ciphers etc and being given near infinite resources by nation states. Remember that the Enigma machine was broken only partly due to cryptographic weakness, it was also human laziness or arrogance. It's less commonly known that the Japanese Navy and diplomatic office believed they had the perfect cipher machine, but the US had been reading their messages since before Pearl Harbor. They lost the war on the desks of the cryptanalysts before it even began.QuoteIn operation, the enciphering machine accepted typewritten input (in the Roman alphabet) and produced ciphertext output, and vice versa when deciphering messages. The result was a potentially excellent cryptosystem. In fact, operational errors, chiefly in key choice, made the system less secure than it could have been; in that way the Purple code shared the fate of the German Enigma machine. The cipher was broken by a team from the US Army Signals Intelligence Service, then directed by William Friedman in 1940. Reconstruction of the Purple machine was based on ideas of Larry Clark. Advances into the understanding of Purple keying procedures were made by Lt Francis A. Raven, USN. Raven discovered that the Japanese had divided the month into three 10-days periods, and within each period they used the keys of the first day with small predictable changes.The Japanese believed it to be unbreakable throughout the war, and even for some time after the war, even though they had been informed otherwise by the Germans.You can never be paranoid enough in the field of cryptography, only the paranoid survive. Like Louis said already, there is no "overkill", there is only "keep firing" and "I need to reload".