Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Skyrunner]

A long long train of thought led me here.

Mainly, my math textbook introduced the Hill cipher as an example of where invertible matrices are used. I searched around a bit and started wondering: how are attacks done? Do the attackers have to know what algorithm the cipher text used to attack it? Or is there some magical way to decrypt stuff? XD

How do people figure out what a particular cipher text means? And how do I tell how secure an encryption is?

(I don't know where this would go, so here in GD I plop it...)

[Leafsnail]

My general understanding is the cryptography itself is extremely powerful.  It's virtually impossible to make a direct attack on high security modern encryption methods.

Therefore most attempts to hack into encrypted systems tend to try and go around the cryptography itself and exploit other weaknesses.  Maybe the program that does the encryption has a security flaw that will allow you to find out or completely bypass the password if you talk to it in the right way.  Or maybe you can find the piece of paper the password was written on, or trick the guy who knows the password into telling you with a well-faked email.  Maybe you can get some kind of surveillance equipment to watch or listen to the guy input the password, and so on.  Basically you want to attack the "human" part of the system.

[misko27]

There is a complicated Cipher I regard as the best in the world. It's a simple word shifter, or so it seems. The Kicker is, instead of adjusting it for a certain number, it adjusts a seemingly random number each time. The best part is it isn't actually random, so a human with enough time and the key can decode it. The trick?

The Key is a book decided before hand. every letter is adjusted down the alphabet depending on how far that particular letter is from A. I.e. if the first letter was C and the first letter of you message is L, the first thing in the encrypted thign would be N!

Invented by Augustus Ceasar.

[palsch]

There is a complicated Cipher I regard as the best in the world. It's a simple word shifter, or so it seems. The Kicker is, instead of adjusting it for a certain number, it adjusts a seemingly random number each time. The best part is it isn't actually random, so a human with enough time and the key can decode it. The trick?

The Key is a book decided before hand. every letter is adjusted down the alphabet depending on how far that particular letter is from A. I.e. if the first letter was C and the first letter of you message is L, the first thing in the encrypted thign would be N!

Invented by Augustus Ceasar.

This is just a variation on the one-time-pad with glaring vulnerabilities.

An ideal one-time-pad shifts every character of the plain text by a random value to generate the cypher text. The very randomness is essential; most direct vulnerabilities come when the method of generating randomness isn't good enough. An English language (or any other language I'm aware of) doesn't have a statistically random enough distribution of letters to work as a truly ideal one-time-pad cypher key.

Of course, it does avoid the problem of pad distribution, when you just need to let people know what book they need to track down instead of trying to pass along a secret key as long as all the messages you are ever going to send using that cypher method. Compare to the perfect one-time-pad distribution method of quantum key distribution and there is a lot going for it purely from a simplicity perspective. Not needing a perfect quantum channel between the two parties for one thing. It really depends on your priorities.

[Another]

A few quick answers.

Modern ciphers usually state which algorithm they are using and they are still strong. It is considered to be one of the fine qualities of a cipher. Pre-WW2 stuff had some weaknesses to finding statistical similarities between encrypted text and common unencrypted texts. Early and mid- cold war cyphers leaked a bit of information here and there through all the transformations. (In the 90s attack techniques became publicly known as differential cryptanalysis.) Famous and widespread in the 80s DES standard family had too small key size (originally 56 bit) and could be cracked by computing with all possible keys and noticing which results look like unencrypted (brute-forcing).

Modern cyphers belong to 2 families: symmetric key and asymmetric key. Asymmetric key is more versatile but requires more computations so is usually used just to initially exchange keys for symmetric encryption.

Security of an encryption is usually measured in how many operations have to be computed to get 50% chance to break an encryption. Most common modern asymmetric encryption depend on how difficult it is to find out which 2 large prime numbers produce a given semi-prime number. Currently there is no known better than brute-force attack on the full version of current most common symmetric key standard (AES (Rijndael)) but [non]existence of a better algorithm to crack it is not strictly mathematically proven.

A large enough quantum computer should be able to decompose large semi-prime numbers in short enough to be practical times. The largest one to date was able to find that 15=3*5.

That is a simplified perspective. I really suggest Wikipedia for all details.

[lorb]

[Skyrunner]

I wonder if rotating the bits in the output would help in any way, combined with a different cipher.

Eg, if 'A' is represented as '01001010', make it so it looks like

01 00      10 01
10 10 ->  10 00

I don't think it'll help. XD

XD

[Neonivek]

Apperantly there is a mathmatical formula that may not exist that can make all encryption useless should it be discovered... Specifically an equasion that allows you to find prime numbers.

At least that is what one math professor told me.

[Skyrunner]

You can find prime numbers!
Just very slowly...
Also, there was something about NP = P on Wikipedia, where if that preposition is true all cryptography as we know it is collectively screwed.

[palsch]

Apperantly there is a mathmatical formula that may not exist that can make all encryption useless should it be discovered... Specifically an equasion that allows you to find prime numbers.

At least that is what one math professor told me.

Shor's algorithm (which I'm actually covering this week in the quantum computation course I'm doing, so if you have detailed questions let me watch a couple hours of lectures first...) is a quantum algorithm lets you factorise any number in polynomial time as opposed to the sub-exponential time it takes on a classical computer.

If you could implement Shor's algorithm with any reasonable speed (eg, have a large enough quantum computer) then you would have to abandon all encryption methods that depend on products of large prime numbers. It's well worth noting that there are a number of candidates for post-quantum cryptography that wouldn't be vulnerable to such an attack.

[lorb]

And no matter the computing power OTP encryption is proven as impossible to crack if used correctly. It's not the most practical encryption method but will be uncrackable forever.

[Darvi]

I'unno. If it can be decrypted (as encryptions are useless if they can't), you could theoretically brute-force it by guessing the key.

[lorb]

No. With a OTP guessing the correct key is as hard as guessing the plaintext. So to decrypt a OTP encrypted message is as hard as guessing the original message with no help at all. Here is an example: I encrypted a letter using a OTP. The encrypted text is "g", which letter is the original message? (if we limit ourselves to lower case letters there is only 26 possible keys so easily bruteforced, so which one is it?)

[Vector]

Apperantly there is a mathmatical formula that may not exist that can make all encryption useless should it be discovered... Specifically an equasion that allows you to find prime numbers.

At least that is what one math professor told me.

Yeah, in my understanding that's the "strong" version of the Riemann hypothesis, i.e. an equation that will take in a number n and spit out the nth prime.

[Another]

I have to add that just finding large prime numbers fast is not very helpful. Approximately every ln(N)'th number is prime around N, so getting the pair of 'random' 2048-bit prime numbers to begin RSA with can easily be done by picking a random 2048-bit odd number and incrementing it by 2 until it is prime. There are fast efficient algorithms to check if a large number is prime or not and the whole finding large prime numbers thing is quite fast.

Anyway - in a few years it may become practical to give OTP flash drives to every person you meet with a few Gigs of random data. And for organizations to give away such drives to customers. That should provide mutual authentication and secure session key exchange (symmetric) for a lifetime as long as you both keep your pads secure from copying.