A large chunk of the global economy now rests on public key cryptography. We generally agree that with long enough keys, it is infeasible to crack things encoded that way. Until such time as it isn’t, that is. Researchers published a paper a few years ago where they cracked a large number of keys in a very short amount of time. It doesn’t work on any key, as you’ll see in a bit, but here’s the interesting part: they used an undescribed algorithm to crack the codes in a very short amount of time on a single-core computer. This piqued [William Kuszmaul’s] interest and he found some follow up papers that revealed the algorithms in question. You can read his analysis, and decide for yourself how badly this compromises common algorithms.
The basis for public key cryptography is that you multiply two large prime numbers to form a product and post it publicly. Because it is computationally difficult to find prime factors of large numbers, this is reasonably secure because it is difficult to find those prime numbers that are selected randomly.
However, the random selection leads to an unusual attack. Public keys, by their very nature, are available all over the Internet. Most of them were generated with the same algorithm and random number generation isn’t actually totally random. That means some keys share prime factors and finding a common factor between two numbers isn’t nearly as difficult.
Continue reading “RSA Encryption Cracked Easily (Sometimes)”
Encryption is one of the pillars of modern-day communications. You have devices that use encryption all the time, even if you are not aware of it. There are so many applications and systems using it that it’s hard to begin enumerating them. Ranging from satellite television to your mobile phone, from smart power meters to your car keys, from your wireless router to your browser, and from your Visa to your Bitcoins — the list is endless.
One of the great breakthroughs in the history of encryption was the invention of public key cryptography or asymmetrical cryptography in the 70’s. For centuries traditional cryptography methods were used, where some secret key or scheme had to be agreed and shared between the sender and the receiver of an encrypted message.
Asymmetric cryptography changed that. Today you can send an encrypted message to anyone. This is accomplished by the use of a pair of keys: one public key and one private key. The key properties are such that when something is encrypted with the public key, only the private key can decrypt it and vice-versa. In practice, this is usually implemented based on mathematical problems that admit no efficient solution like certain integer factorization, discrete logarithm and elliptic curve relationships.
But the game changer is that the public key doesn’t have to be kept secret. This allows cryptography to be used for authentication — proving who someone is — as well as for encryption, without requiring you to have previously exchanged secrets. In this article, I’ll get into the details of how to set yourself up so that anyone in the world is able to send you an e-mail that only you can read.
Continue reading “Practical Public Key Cryptography”
Imagine a camera that took encrypted pictures. If your camera is stolen, the only thing on the memory card would be random data that can only be unlocked with a key. If you hire a photographer, those images cannot be copied without the key. At the very least, it’s an interesting idea made impressive because this actually exists.
[Doug] recently got his hands on a Samsung NX300, a nice camera for the price that conveniently runs Linux and is kinda open-sourced by Samsung. With special firmware, [Doug] created public/private key encryption for this camera, giving only the person with the private key the ability to unlock the pictures taken with this camera.
[Doug] started his build by looking at the firmware for this camera, figuring out how to take everything apart and put it back together. With a few modifications that included encryption for all images taken with this camera, [Doug] repackaged the firmware and upgraded the camera.
The encryption firmware is available on the site, but considering how easily [Doug] was able to make this hack happen, and a great walkthrough of how to actually do it raises some interesting possibilities. The NX300 is a pretty nice camera that’s a little bit above the Canon PowerShot cameras supported by CHDK. It also runs Linux, so if you’re looking for something cool to do with a nice camera, [Doug] has a very good resource.