`root@Cryptography`

I'm interested in there being a Cryptography section of the Fanzine, but I get lost after swapping letters around. Does anyone care to gift the r-faction with some crypto?

—

[ `@-rep +1 `

|` c-rep +1 `

|` g-rep +1 `

|` r-rep +1 `

]

Thu, 2010-09-23 19:19

#1
Cryptography

`root@Cryptography`

I'm interested in there being a Cryptography section of the Fanzine, but I get lost after swapping letters around. Does anyone care to gift the r-faction with some crypto?

—

[ `@-rep +1 `

|` c-rep +1 `

|` g-rep +1 `

|` r-rep +1 `

]

root wrote:Do you mean, 'real' crypto?

root wrote:Do you want real life existing crypto algorithms (like the algorithm to AES) or are you looking more for theoretical crypto (like quantum crypto)? Note that current crypto (no matter how good it is) has a shelf life of about 10 years max. After that it is effectively useless (no one relies on DES any more as an example). Since EP is at the very least 70 years beyond today, our current crypto would be as effective as Ceasar Crypto is today.

The key to analytical crypto (the type used since the beginning of time) is the complexity and size of the key will determine the life time of your security. For instance given modern computers, an AES key (standard 128bit encryption) would last for about 24 hours from a brute force attack (ie randomly entering in codes till one works). Analytical crypto is always cursed with the fact that More's Law is always working against it and your algorithm and key need to constantly grow in order to stay ahead of the best brute force attackers.

Quantum crypto in contrast is as complex as your quantum computer, and the time needed to break the key is close to infinite (due to the nature of the key and quantum computing). This is the current Holy Grail of Cryptography as only the person intended to decrypt the code can. As my old army sergeant use to say, it's FM (F@#%$ Magic).

Jovian Motto:

Your mind is original. Preserve it.

Your body is a temple. Maintain it.

Immortality is an illusion. Forget it.

Are you looking for stuff about RL cryptography - or more crypto puzzles for people to solve?

I fix broken things. If you need something fixed, mention it on the suggestions board.

I also sometimes speak as website administrator and/ moderator.

`root@Cryptography`

I'm actually looking for all of it. I am thinking of writing little crypto puzzles, but including some educational facts about real life cryptography and how cryptography will change in the future. I've learned quite a bit just from TRBMInsanities reply.

TRBMInsanity, I thought that an appropriately complicated encryption worked because a brute strength decryption is likely to produce false "solutions" that appear to be correct? As the size of your message increases, the likelihood of a false positive drops, but when the encrypted message is also in jargon or an odd language, how can you tell that you've found the correct key?

[

`@-rep +1`

|`c-rep +1`

|`g-rep +1`

|`r-rep +1`

]Currently the common crypto algorithms run based on how extremely difficult it is to take a remainder from division and figure out the numbers used to derive it. I suppose if you don't know ANYTHING about the message prior (including a document signed by the sender's private key), you could be generating a list of random original messages as guesses. However, if the message is of sufficient length, it's not hard to eliminate 99% of them on the grounds that it simply isn't language. This isn't a situation where any original message is possible while trying to reverse/guess the encryption, so it's not a huge issue.

The way cryptography works right now is, basically, we have a set of problems called NP, which means Not P, with P meaning, more or less, 'easy'. These problems are tremendously difficult and time-consuming to calculate. But doing that same problem the other way (i.e., work from the answer to find the question), it's P - very easy. (An example is above - X divided by Y has a remainder of 13. Solve for X and Y. Compare to 283 divided by 45 has a remainder of Z.)

The problem EP brings up is that Quantum Computers (and, although it's not mentioned, biological computers) solve problems in a fundamentally different way. Many problems which are NP for a computer may be P for a biological computer (and, funny enough, vice versa). So once you have a quantum computer, the classic encryption methodology has to move on.

You are ultimately going to have a few types of encryption in EP:

P for everyone. Examples are Caesar Ciphers, letter substitions, foreign languages, etc. These can be cracked in trivial time. While currently the mystery can be one of 'guess the method' (is this message a letter substitution? Is it written backwards? Is it Cherokee?) in EP you're going to find that extremely ineffective unless the sender is so alien in mindset that nothing in our entire racial history would give us a clue as to what it means (for example, a message written in the Factor language is effectively encrypted and may be impossible to crack without further information).

NP for computers, P for quantum computers. These are some sort of problem which, as I said above, takes a P amount of time to solve one way, but an NP amount of time to solve the other. Examples include the modulus (remainder) problems, pathing problems (like the travelling salesman problem), etc. If you read the wikipedia article on NP, this should give you some background, but you don't need to dive too deep. Likely, the majority of these can be cracked by quantum computers in P time.

P for quantum computers, NP for normal computers. This encryption is just for a laugh. No one would really use it.

NP for everyone. Because I don't understand quantum computers, I don't know what an NP quantum computer problem is. Apparently the authors of EP don't either. You could be the first! Go for it.

An important note on the 'P' section above. Note that I said 'anything which cannot be predicted given the whole of our racial history'. Anything which you can create that does not tie into our racial history can create an effective algorithm in this category which will be effective. An example of this is a one-time pad. A one-time pad is when you have a super-long code. When you send me a message, you start it by saying "start with character 4,528 (or whatever) of our shared code'. You then run each number in the message through an XOR function with each number in the code. The result is effectively unbreakable - as long as the code is unpredictable. If our code is a book, or if it's intercepted in transit or so on, the bad guy spy can likely crack it. An example source for a code is recording the audio feedback on a microphone, or certain functions regarding heat, or the decay of radioactive materials, which are effectively unpredictable. The code then needs to be sent securely, likely by courier, to everyone you want to have access to it. It needs to be kept secure, and you need to make sure you never use the same part of the code twice.

Quantum encryption in EP apparently may function very similarly to this. Again, it's a P problem. But unlike a one-time pad, the key can't be copied or determined from data analysis. Quantum encryption may also be an anti-tampering mechanism - if the message is opened, the quantum bits no longer match, and both parties know a third party has read it. Not the same as encryption, but still a useful tool.

Hope that helps.

You know when you have the correct key when you have access to the information or system protected by the key. But you are right you will always have more chances of entering the wrong key then the right one (which is why a lot of encrypted systems with vital data have lock out features only allowing x number of attempts before a manual, on-site reset must be done (or in some cases with military crypto, the data and device it is stored in self destruct)).

On a side note, as I pointed out above, for analytical crypto the processing power of the standard computer will determine how big and complex your crypto and key need to be, what is the processing power of EP computers?

That being said, the weakest theoretical quantum computer can break the most complex and largest analytical crypto in less then a nano second (due to the nature of quantum computing). Are quantum computers available in EP?

Jovian Motto:

Your mind is original. Preserve it.

Your body is a temple. Maintain it.

Immortality is an illusion. Forget it.

I guess another thing to consider is the life time of the data being protected.

While a 128-bit AES can be broken in 24 hours, if the protected data only have value for a manner of minutes its good enough.

Time is always a factor. That is why encrypted transmissions are never as encrypted as formal messages. This is all assuming though that you know how good your opponent's decrypting program is.

Jovian Motto:

Your mind is original. Preserve it.

Your body is a temple. Maintain it.

Immortality is an illusion. Forget it.

`root@Cryptography`

I imagine any intel group in EP has to be going nuts trying to figure out what the Factors can decrypt when they slime mold together.

[

`@-rep +1`

|`c-rep +1`

|`g-rep +1`

|`r-rep +1`

]TBRMInsanity wrote:I think your time scales are a *LITTLE* off. In fact, the current quantum computers take quite a good deal of time just to do basic functions like arithmetic. However, yes, it would solve in P time rather than NP, which is an order of magnitude of difference.

Yes, EP has quantum computers.

As a noted exception, there are one-time pads which are guaranteed unbreakable as long as the pad isn't reused. However, there are practical limitations in safely transporting the pad to the entity with whom you'd like to securely communicate.

Escorting a shipment of one-time pads might even make for a decent EP mission.

`root@Cryptography`

clem wrote:[

`@-rep +1`

|`c-rep +1`

|`g-rep +1`

|`r-rep +1`

]nezumi.hebereke wrote:No, NP is *WAY* more than an order of magnitude (compare the time it takes to solve the travelling salesman problem (N!) and bubble-sort a list (N^2) - you can get as many orders of magnitude of difference as you want by using a large N).

However, quantum computers just give you an exponential speedup (on some problems). They do not turn NP into P strictly speaking (see the writings of Scott Aaronson, "Great ideas in computer science", a bit down in the right column of http://www.scottaaronson.com/blog/ ).

root wrote:That is not exactly correct. A common cryptanalytic attack requires searching for patterns in the cyphertext and making educated guesses based upon what language the cryptologers think was used in the message to determine the parameters of success. This is mitigated somewhat by compressing the data before encrypting it. It could also be said that this is mitigated by using session keys to encrypt the payload but using other keys (a shared key or a public key) to then encrypt the session key before prepending it to the cyphertext.

nezumi.hebereke wrote:Almost but not quite. Factoring a composite value formed from the multiplication of very large relatively prime numbers is more accurate.

nezumi.hebereke wrote:As a bonus, it would also likely corrupt the cyphertext,rendering it useless to anyone.

What I know about Quantum Computing and Quantum Encryption I've picked up second hand from Tranhumanists like Ray Kurzweil. Does someone have a link or resource that explains these subject better then the 100,000 KM view? It interests me greatly. I know a lot about current encryption methods but nothing of possible future methods.

Your mind is original. Preserve it.

Your body is a temple. Maintain it.

Immortality is an illusion. Forget it.

For foundational stuff, I'd go with Bennett and Brassard's 1984 paper on the subject, or Brassard, Crepeau, Jozsa, and Langois' 1993 paper "A Quantum Bit Commitment Scheme Provably Unbreakable by both Parties". Both should be available through your local public or university library.

Loyal Citizen wrote:Thank you

+1 I-Rep

Your mind is original. Preserve it.

Your body is a temple. Maintain it.

Immortality is an illusion. Forget it.