Cryptography

[CodeSlinger]

mugaliens and I started having a little side-conversation about cryptography in a Q&A thread. Since that thread had nothing to do with cryptography, I thought it best to take our conversation into its own thread. The comments thus far:


Glamorizing comments such as "Financial and other information would be prodigiously safer with a quantum computer" are pure bunk. We can encrypt data safely without fear of decryption right now, not for billions of years, but forever.

It's easy! Just use a keyspace larger than the dataset. That renders the solution set equal to or larger than all possible solutions.

Encryption 101, and has been known for at least half a century... Crikey!

What ignorant reporters won't do to sell their stories.

Still, actually stopping light... THAT's amazing!

The encryption aspect - pure bunk. We've had that problem solved for decades.


Can you expand on this? It doesn't sound right to me. The way I'm thinking about it, unless your keyspace is infinitely large, it will only take finite time to search the entire keyspace and find the correct decryption key.

When the keyspace is truly random, and of the same size as the message, the solution set encompasses all possible solutions. Encryption 101.

[CodeSlinger]

Funnily enough, as I was copying/pasting the comments, I think I finally understood what mugaliens was saying. mugaliens, are you talking about one time pads?

[mugaliens]

Funnily enough, as I was copying/pasting the comments, I think I finally understood what mugaliens was saying. mugaliens, are you talking about one time pads?

Yes!

[tdvance]

"Financial and other information would be prodigiously safer with a quantum computer"

You mean, "quantum cryptography"? The thing with quantum computers is that they can *break* certain cryptography in use today. Quantum Cryptography (implemented correctly, as always!) is provably secure (given that quantum mechanics is essentially right-specifically, that the principle that you cannot clone a state is true).

A one-time pad, as mentioned, is provably secure too (if done right--i.e. the random keystream is truly random and not made with, say, the "rand" function in C).

Todd

[SpaceShot]

One time pads are the ultimate and perfect cryptography. They have some problems.

1) Random enough distribution of the pad keys
2) Delivery of the pad

There are probably other issues... this is off the top of my head.

This makes one time pads prohibitive for all applications because they are expensive in time and money. Do you deliver the pad by courier? You also have to trust the courier. Trust can be established with time and money.

I think the general field of cryptography looks for methods of encryption that are "cheap" but still resilent for "long enough". If long enough is a few years, there is plenty of free encryption.

I think the public cryptography community probably believes that the right choice of alogrithm and method could produce messages secure enough to last "for the forseeable future" with foreseeable technology advances.

I guess the point is it's a tradeoff. With infinite time and resources you can make something unbreakable. Most folks have less (even massive financial institutions).

Can't dispute anything else that has been said, though.

[mike alexander]

The other possibility would be to just send out the truth in clear. Nobody would believe it.

[HenrikOlsen]

Or encrypt everything.
Only encrypting the important stuff is a very big help for the snoopers as that tells them which messages are valuable enough to bother with, and which they don't have to waste resources on.

[Chuck]

It's sufficient that your encryption scheme makes cracking your code more expensive than the data is worth which means that even if your enemy reads your message, you've still come out ahead.

[hhEb09'1]

It's sufficient that your encryption scheme makes cracking your code more expensive than the data is worth which means that even if your enemy reads your message, you've still come out ahead.No, they've come out behind! :)

[HenrikOlsen]

Unfortunately, cost of cracking is plummeting.
As an example, for encryption schemes based on the difficulty of factoring composites of large primes, the practical limit is rising faster than most have expected, to the point where my personal record is factoring a 830+ bit number, and that was 2-3 years ago and was done in less than a week.

[danscope]

Just use symbols instead of letters, with an occasional permutating inner code.
Done.
Best regards, Dan

[hhEb09'1]

Just use symbols instead of letters, with an occasional permutating inner code.
Done.Done what? :)

It's not a simple thing. Besides, code schemes are judged on their utility. They have to be able to be used often--and that usually means that the opponent knows your scheme, just not your key.

A personal code between two spouses is probably doable. :)

[tdvance]

Unfortunately, cost of cracking is plummeting.
As an example, for encryption schemes based on the difficulty of factoring composites of large primes, the practical limit is rising faster than most have expected, to the point where my personal record is factoring a 830+ bit number, and that was 2-3 years ago and was done in less than a week.

Heck, i can factor a 10000-bit number!

2^10000 is 2*2*2*2*2*2*....

[HenrikOlsen]

That wasn't factoring, as you already knew the factors through construction.
Try factoring (2^10000)-1 instead.

[Moose]

One time pads are pretty good. But they're not unbreakable by any stretch. You don't attack the message. You trojan horse the sending equipment. You trojan horse the receiving equipment. You make the randomizer non-random. You fake some pads (with a third copy) and inject them into the communication chain. You compromise the clerks.

[C Add]

That wasn't factoring, as you already knew the factors through construction.

it looks like factoring to me, but his number is 10001 bits

Try factoring (2^10000)-1 instead.

that number is harder

[hhEb09'1]

Try factoring (2^10000)-1 instead.It's divisible by 3. :)

And every other number 2(2n5m)-1, n, m, less than or equal to 4One time pads are pretty good. But they're not unbreakable by any stretch.One time pads are unbreakable, in the usual sense of that meaning.You don't attack the message. You trojan horse the sending equipment. You trojan horse the receiving equipment. You make the randomizer non-random. You fake some pads (with a third copy) and inject them into the communication chain. You compromise the clerks.Sure, but then, you're not breaking the one time pad. Those methods are always available, even when your opponent is not using code! :)

[tdvance]

yeah--I can find "some" factors easily, as suggested by hhEb09'1---


if x is a factor of 10000, then

2^x - 1 is a factor of 2^10000 - 1

(which is why Merseine "primes" are of the form 2^p - 1).

but my point was, it's easy to factor "a" number of a given size. What is hard is factoring an arbitrary number of a given (large) size. When it comes to factoring, all numbers are not created equal. e.g. I think it's Euler's method that will, really quickly, factor a large number if it is a product of twin primes, that is, where one prime is p, and the other happens to be p+2. Of course, if you knew in advance it was a product of twin primes, you'd take the square root, then the integer just below and the integer just above it--but Euler's method is more general.

---

one time pads are unbreakable --- if done right, i.e. the digits are truly random. The only way to "break" it is to either steal the plain text or steal the one time pad--but that's not breaking the code. That's what doors, locks, guards, and guns are for. Quantum cryptography is no better than the one-time pad if you allow "doing things other than breaking the code". It's better in that no pre-arranged one-time pad has to be distributed.

Now, if you want to know about insecurity, read some of Feynman's books--I wish I remembered the one (or ones, it's repeated) where he described his stint on the Manhattan project and how he opened people's safes to prove to them that, for example, using a permutation of the first 6 digits of Pi or e, or birthdays or relative's birthdays for a combination wasn't a good idea. He learned to try lots of combos really fast and could go through all the easy choices quickly. If they failed, he had other methods, like looking what number the lock is on when the safe is open--that gets him the last of the three numbers for free.

(as I learned as a 7 or 8 y/o child, not spinning the dial far enough makes things a lot easier--I watch grandpa open his safe, last number was "50"--he closed it, gave a quick spin, I just turned it back to 50 and opened it right up! He never gave it just a "quick spin" again!)

[hhEb09'1]

Of course, if you knew in advance it was a product of twin primes, you'd take the square root, then the integer just below and the integer just above it--but Euler's method is more general.The odd integer just below, and the odd integer just above it. :)

[Chuck]

A better scheme is to arrange to have the opposition not even suspect that messages are being sent.