prime numbers

3 Articles

Imitating Art In Life With A Reverse-Engineered Tattoo

March 23, 2019 by 6 Comments

In general, tattoo artists are not electrical engineers. That’s fine; the world needs both professions. But when you need a circuit designed, you’re better off turning to an EE rather than a tattoo artist. And you certainly don’t want an EE doing your new ink. Disaster lies that way.

Surprisingly, [Missa]’s tattoo of a heart-shaped circuit turned out at least to be plausible design, even if it’s not clear what it’s supposed to do. So her friend [Jeremy Elson] took up the challenge to create a circuit that looked like the tattoo while actually doing something useful. He had to work around the results of tattoo artistic license, like sending traces off to the board’s edge and stranding surface-mount components without any traces. The artist had rendered an 8-pin DIP device, albeit somewhat proportionally challenged, so [Jeremy] went with an ATtiny85, threw on a couple of SMD resistors and a cap, and placed two LEDs for the necessary blinkenlights. Most of the SMDs are fed from traces on the back of the board that resurface through vias, and a small coin cell hidden on the back powers it. One LED blinks “Happy Birthday [Missa]” in Morse, while the other blinks prime numbers from 2 to 23 – we’ll assume this means it was [Missa]’s 23rd birthday.

There’s a surprising amount of crossover between the worlds of electronics and tattooing. We’ve featured functional temporary tattoo circuits, prison-expedient tattoo guns, and even a CNC tattoo machine.

Continue reading “Imitating Art In Life With A Reverse-Engineered Tattoo” →

RSA Encryption Cracked Easily (Sometimes)

January 16, 2019 by 32 Comments

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)” →

Prime Numbers Are Stranger Than You Thought

March 14, 2016 by 135 Comments

If you’ve spent any time around prime numbers, you know they’re a pretty odd bunch. (Get it?) But it turns out that they’re even stranger than we knew — until recently. According to this very readable writeup of brand-new research by [Kannan Soundararajan] and [Robert Lemkein], the final digits of prime numbers repel each other.

More straightforwardly stated, if you pick any given prime number, the last digit of the next-largest prime number is disproportionately unlikely to match the final digit of your prime. Even stranger, they seem to have preferences. For instance, if your prime ends in 3, it’s more likely that the next prime will end in 9 than in 1 or 7. Whoah!

Even spookier? The finding holds up in many different bases. It was actually first noticed in base-three. The original paper is up on Arxiv, so go check it out.

This is a brand-new finding that’s been hiding under people’s noses essentially forever. The going assumption was that primes were distributed essentially randomly, and now we have empirical evidence that it’s not true. What this means for cryptology or mathematics? Nobody knows, yet. Anyone up for wild speculation? That’s what the comments section is for.

(Headline photo of researchers Kannan Soundararajan and Robert Lemke: Waheeda Khalfan)