cass
Junior Member
Posts: 58
|
Post by cass on Mar 13, 2012 2:27:53 GMT
Cass > I was thinking about that, and I thought however that you could, not too uneasily, take a string of crypted letters, convert them into numbers, and use those numbers with a table to *generate* seemingly normal, meaningful language (which granted wouldn't make much sense, but would still look like English, as opposed to random letters). Well a one time pad just works on a big wheel. Like if I take the alphabet on a strip of paper and wrap it into a circle and just start counting round, then A would be 1 B would be 2 - and so on up to ... 25(?) letters in this alphabet I think. So if I want to encrypt the message Chocolate is tasty I can pair it with the random text dukrlotwn ie qefge It works like a clock so if you add 4 to 24 you don't get to 28, you get to 3. Okay so I've got a d, as the first letter of my random text and I've got a c as my message - so I count around 4 letters from c giving me a g... and so on until I've encrypted the thing. It's really a modified version of the Beale Cipher - which used a common word or part of a phrase as its key. Which is in turn a more complex form of the Caesar cipher - which just said move X number of letters from where you are. Anyway, the point of all this is that it doesn't matter what number you're counting up to, as long as the other person has a matching wheel. If you had a common dictionary, you could just assign each word of your message a number and use those numbers on your circle, instead of the alphabet. Which is probably a lot easier - at least given that they have computers and can just use a dictionary on there to do the decrypting - than having a table that they put on top of a layer of cryptography working on a smaller alphabet. I was more concerned that it wouldn't form a coherent narrative than that it wouldn't be English. Given that you can work your way around to anything from anything, if you select the right number of turns on your circle, you could turn your encrypted text into a reasonably coherent narrative. But to do that you'd have to know ahead of time what message you wanted to encrypt to know how many spaces your later going to want to tell him to move each word around on his wheel. And if you know that you may as well just have a codeword you can bury in a more normal conversation that just stands for the message you want to send them. ... This is also, in a round about way, why you mustn't reuse a one time pad: If you select the right key, you can turn any message of a given length into any other message of a given length. But if you have two (or more) messages using the same key, then only one of the messages will be meaningful if you use the wrong key. Which just turns it into a computationally intensive, but otherwise theoretically uninteresting, task of searching through the keys until you find the one that makes both messages make sense at the same time, (this is obviously easier the more text you have to compare.)
|
|
|
Post by warrl on Mar 14, 2012 19:35:30 GMT
Also, there's no reason the key of your one-time pad has to be *short*. You can use "War and Peace" as a key if you want. There's risk in using a short key for a long message (similar to cass's last paragraph) but no problem with using a long key for a short message.
|
|
|
Post by atteSmythe on Mar 14, 2012 19:54:25 GMT
Actually, the key of your one-time pad has to be the length of the message encoded. Otherwise the repetition makes it crackable. As I understand it, the thing that makes a one-time pad absolutely secure is that you're basically using a new key for each piece of information sent (whether that's a letter, word, etc). The only way to decrypt that is for each side to have the same key. It's worse than that: The key used must be absolutely random, or else the key itself is discoverable!
Edit: Think of it like this: Say you have a message to send, 20 characters long. If your key is only 5 characters long, it's exactly equivalent to sending four different messages with the same one-time pad.
|
|
|
Post by warrl on Mar 14, 2012 23:20:56 GMT
No, it's okay for the key to be longer than the message - you'll just ignore the excess.
From an information perspective, a one-time pad (and any other sort of substitution cipher) requires THREE keys. We commonly think of only one because we do alphabetic substitution and use the alphabet itself as two of the three keys.
Key A: a list of everything we might possibly want to encode. (Unless we have an "escape" mechanism to another encoding system embedded in our coding algorithm.) This list can contain duplicates.
Key B: a list of replacement symbols. This list cannot contain duplicates or even partial duplicates (if the list contains "into", "the", and "into the", there's a problem), but if key A does not contain duplicates the two lists can be identical. Or they can be entirely different. Key B must be at least as long as key A; it can be longer. Attention-grabbing words like "assassinate" should not feature prominently in this list.
Key C: the one-time pad; each entry in a single page of the pad describes how to line up keys A and B for encoding a set amount of one clear message (usually one letter or one word). It does not have to resemble the clear message or either of the other two keys at all.
|
|
cass
Junior Member
Posts: 58
|
Post by cass on Mar 15, 2012 0:29:15 GMT
There are other ways to ensure your message is unbreakable, but none of them make more efficient use of the key data than a one time pad anyway. Indeed it's been mathematically proven that any theoretically unbreakable encryption has to, as a minimum, use keys that meet the same standards as the keys used for OTPs. So, given that a one time pad uses the same alphabet and length for its key as for the message being encoded, the things that make it unbreakable are the random key in combination with modular arithmetic.
It is possible, if you choose a really bad method to squish your key and your message together, to end up with a finite (often fairly small) search space even with a totally random key. Say, for instance, that I'm encoding a short string of numbers
1234567890
And my random key is - somewhat improbably
0987654321
If I were just to add my key to my message I'd get
111111111111111111
Which doesn't look like much, right? Infact it doesn't look like it contains any information at all - seems perfectly regular.
But if the attacker knows that I'm using the number range 0-9 as my alphabet, (and really, he ought to be able to guess that,) he can work out that 9+9=18. This will tell him that the largest encoded chunk that can represent a single digit in my message must be two digits in length. He can then cut the message up into different sized chunks, and fairly easily work out that the first and last numbers of the key were either a 0 or a 1 - and he'll be able to guess that the rest of the numbers added up to 11 8 times and that will give him the fact that I transmitted the range of numbers 0-9 twice. One as the message and one as the key.
He could make other guesses - there are other things I could have done that would have produced that encoded text. But I couldn't have done absolutely anything and got that result. And given that language generally follows more meaningful structures the range of things he's going to be guessing over are, in reality, going to be rather limited.
Of course it's not quite that easy with a random key - unless you run out of luck I suppose - but the underlying problem remains.
There are ways around it, but generally you pay for making your message more secure by increasing the size - and thus the entropy - of your alphabet (right out to infinite, when it again becomes uncrackable.) And there's just no reason to do that when OTPs already give you an efficient use of a perfectly secure key.
Modular arithmetic ensures that information doesn't survive.
If I add the key and the message together again using mod arithmetic
Mes 1234567890 Key 0987654321 Then my result comes out as... Res 1111111111
Which really is meaningless.
Of course the result looks much the same to the eye - apart from the fact it's shorter. But if you make the same assumptions we made up the page and assign them to the new result you're going to get the wrong answer.
Edit: The other way to increase the security of your message - other than increasing the size of your alphabet - is to use a more efficient method than just adding the key to the message. This won't give you perfect security if your key length is less than the size of your message, but nonetheless it is what a great deal of encryption is about; how to make more efficient use of the limited amount of randomness you have available in reality.
|
|
|
Post by grahamf on Mar 15, 2012 1:52:51 GMT
I'm just wondering exactly what the encrypted message looks like. I don't expect Annie to be able to perfectly memorize a mumble jumbo of letters. But if it was words like "Antimony tea a blue coconut fly orange... " Annie may be more likely to remember it.
Something like that would actually explain a few hippieyear songs...
|
|
|
Post by atteSmythe on Mar 15, 2012 15:06:56 GMT
No, it's okay for the key to be longer than the message - you'll just ignore the excess. Right, the key can be longer than the message. The message can't be longer than the key. You said there's no reason the key has to be short...that's true, but there's a reason the key cannot be short!
|
|