I Believe I Created an Unbreakable Cryptosystem, Confirmation Needed

[Asterisk Propernoun]

Hello_World!

KEY~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The base is 1337 (0 to 1336).

H=55
e=509
l=1205
o=798
_=319
W=562
r=900
d=29
!=1329

KEY~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

55*1337^11+

509*1337^10+

1205*1337^9+

1205*1337^8+

798*1337^7+

319*1337^6+

562*1337^5+

798*1337^4+

900*1337^3+

1205*1337^2+

29*1337^1+

1329*1337^0

1351478792050701588315749385525247210

1351478792050701588315749385525247210/1337=1010829313426104404125467004880513 R1329
!
1010829313426104404125467004880513/1337=756042867184820047962204192132 R29
d
756042867184820047962204192132/1337=565477088395527335798208071 R1205
l
565477088395527335798208071/1337=422944718321262031262683 R900
r
422944718321262031262683/1337=316338607570128669605 R798
o
316338607570128669605/1337=236603296611913739 R562
W
236603296611913739/1337=176965816463660 R319
_
176965816463660/1337=132360371326 R798
o
132360371326/1337=98998033 R1205
l
98998033/1337=74044 R1205
l
74044/1337=55 R509
e
55
H

Hello_World!

 

I'm sure you can see what I'm trying to do. I'm basically taking a bunch of letters, placing them randomly on to a random base value, treating the plaintext as if it where a number on that base value, and translating it into decimal form. I believe that this is unbeakable in a similar sense to the One-time pad, in that, with unlimited computing power, one can generate the key instantly, but would find that the key is lost inside an infinite number of other key possibilites. Is what I'm saying true?

 

Another thing I would like to have clarified. I understand that one does not simply generate random numbers on a computer, and that the numbers would only be pseudorandom; but would it be harder to find patterns in pseudorandom numbers if there where less numbers to work with?

 

Thanks.

[md65536]

No, it's not unbreakable in similar sense to a one-time pad. In a one-time pad, the encrypted message is indistinguishable from random. Here, once you know the encryption method, your message is essentially 55, 509, 1205, 1205, 798, 319, 562, 798, 900, 1205, 29, 1329.

 

There are 3 occurrences of 1205, and two of 798. It doesn't matter how big these random numbers are because there are only 26 + punctuation different possible numbers. Now your encryption is a simple letter substitution. On a long message, a modestly skilled person could figure out the words, just like in cryptograms.

 

You could fix this by creating new numbers for each occurrence of a letter, necessarily reusing numbers to encode long messages. But then it is not really any different from a one-time pad, except for the extra data and math. The problem with a one-time pad is getting the same secret pad to both parties.

[Asterisk Propernoun]

No, it's not unbreakable in similar sense to a one-time pad. In a one-time pad, the encrypted message is indistinguishable from random. Here, once you know the encryption method, your message is essentially 55, 509, 1205, 1205, 798, 319, 562, 798, 900, 1205, 29, 1329.

 

There are 3 occurrences of 1205, and two of 798. It doesn't matter how big these random numbers are because there are only 26 + punctuation different possible numbers. Now your encryption is a simple letter substitution. On a long message, a modestly skilled person could figure out the words, just like in cryptograms.

 

You could fix this by creating new numbers for each occurrence of a letter, necessarily reusing numbers to encode long messages. But then it is not really any different from a one-time pad, except for the extra data and math. The problem with a one-time pad is getting the same secret pad to both parties.

 

I believe you're forgetting the fact that the base value is also kept a secret and is a part of the key. I want you to pretend that you don't know the base value is 1337, and then try again.

Edited March 31, 2014 by Asterisk Propernoun

[Cap'n Refsmmat]

I don't follow your post. If I wanted to encrypt the message "Cap'n Refsmmat", how would I do that? What key would need to be shared between me and my recipient?

[md65536]

 

I believe you're forgetting the fact that the base value is also kept a secret and is a part of the key. I want you to pretend that you don't know the base value is 1337, and then try again.

 

Would you say that DVD encryption and other things with secret keys are unbreakable? With a key built into the system it's vulnerable. I wouldn't be able to break it but someone who knew what they were doing, who could probe the system and find clues and reverse engineer stuff could. Anyway that's "security through obscurity" and is *definitely* not what one would call "unbreakable".

 

 

If you have a truly random one-time pad, then the message is unbreakable. You've taken that and crippled it by reusing the pad (each occurrence of "o" uses the same number), so you've introduced patterns. That can be fixed though. However, security through obscurity is fairly useless. You mentioned using a calculatable, pseudo-random number generator... why not just throw all of the obscurity into that, so that it's difficult (but probably not unbreakable) to figure that part out? The manipulation involving 1337 just adds a bit more obscurity, but doesn't make it perfect.

Edited March 31, 2014 by md65536

[Asterisk Propernoun]

I don't follow your post. If I wanted to encrypt the message "Cap'n Refsmmat", how would I do that? What key would need to be shared between me and my recipient?

 

A random number that, when used as a base value, can hold all of the types of symbols you plan to put in to the text. For instance, if you where to use the alphabet and a space, then you would need to use a minimum base value of 27, or 0 to 26. You will also need to assign the symbols numbers on the base value at random. The key you want to share to your recipient and keep a secret from everyone else is the base value and how the symbols (letters, numbers, and punctuation), are spread across the base value

 

However, since using the absolute minimum base value would be the same as scrambling the letters with extra calculations involved, you'll want to use a base value that is much larger and completely random.

 

Would you say that DVD encryption and other things with secret keys are unbreakable? With a key built into the system it's vulnerable. I wouldn't be able to break it but someone who knew what they were doing, who could probe the system and find clues and reverse engineer stuff could. Anyway that's "security through obscurity" and is *definitely* not what one would call "unbreakable".

 

 

If you have a truly random one-time pad, then the message is unbreakable. You've taken that and crippled it by reusing the pad (each occurrence of "o" uses the same number), so you've introduced patterns. That can be fixed though. However, security through obscurity is fairly useless. You mentioned using a calculatable, pseudo-random number generator... why not just throw all of the obscurity into that, so that it's difficult (but probably not unbreakable) to figure that part out? The manipulation involving 1337 just adds a bit more obscurity, but doesn't make it perfect.

 

So basically what you're saying is that, by getting in to the recipient's system, you can take the key from him/her. Assuming that I'm following correctly, I'm going to ask a question. Would creating a public-key version of this fix the problem?

Edited March 31, 2014 by Asterisk Propernoun

[Cap'n Refsmmat]

A random number that, when used as a base value, can hold all of the types of symbols you plan to put in to the text. For instance, if you where to use the alphabet and a space, then you would need to use a minimum base value of 27, or 0 to 26. You will also need to assign the symbols numbers on the base value at random. The key you want to share to your recipient and keep a secret from everyone else is the base value and how the symbols (letters, numbers, and punctuation), are spread across the base value

 

However, since using the absolute minimum base value would be the same as scrambling the letters with extra calculations involved, you'll want to use a base value that is much larger and completely random.

So I'd pick a large number (the "base value") and assign each letter to a number smaller than the base value.

 

The cute part is then summing up the letter as though each were a digit in that base arithmetic.

 

So if someone intercepts your message, let's assume they know the system but don't know the base or the character assignments.

 

If the base is small (e.g. less than 2¹⁶ or something), a brute-force attack wouldn't take long. Just iterate from base 1 to n; for any base n, convert the decimal message into base n and read out the digits. Now you have the ciphertext letters, which are a simple monalphabetic substitution; you can do a frequency analysis to test if it's plausibly an enciphered English message. If the frequency analysis shows no normal English pattern, try n + 1.

 

There may be a cleverer mathematical attack but I haven't put too much thought into it.

 

(It just so happens that I'm currently reading David Kahn's excellent The Codebreakers, which you might enjoy. It describes many historical cryptosystems and their solutions, along with a great deal of history of their use and abuse.)

[md65536]

So basically what you're saying is that, by getting in to the recipient's system, you can take the key from him/her. Assuming that I'm following correctly, I'm going to ask a question. Would creating a public-key version of this fix the problem?

No, you wouldn't need to get into the system. If there are long messages or many messages, it gives you more data to try to figure out. Obscurity makes it harder, but that would just make it take longer to break, not make it unbreakable.

 

Public-key systems I think involve a "one-way function", where the public key is easy to generate but the private key is difficult to extract. Eg. factoring of numbers with hundreds of digits is very hard (not unbreakable). A key like "1337" would not be hard because you can just try every number between 0 and a few thousand or millions or whatever and see what you get.

 

If you make a system complex enough like this, and then don't allow anyone access to it, and then don't *use* it too much or send dangerous messages (eg encrypting "a", "aa", "aaa" might give someone some clues), you can probably make something that is likely to be kept secret.

 

Cracking DVD encryption involved having access to a device: '"The nomad" allegedly found this decryption algorithm through so-called reverse engineering of a Xing DVD-player, where the [decryption] keys were more or less openly accessible.' -- http://en.wikipedia.org/wiki/DeCSS

[Asterisk Propernoun]

So I'd pick a large number (the "base value") and assign each letter to a number smaller than the base value.

 

The cute part is then summing up the letter as though each were a digit in that base arithmetic.

 

So if someone intercepts your message, let's assume they know the system but don't know the base or the character assignments.

 

If the base is small (e.g. less than 2¹⁶ or something), a brute-force attack wouldn't take long. Just iterate from base 1 to n; for any base n, convert the decimal message into base n and read out the digits. Now you have the ciphertext letters, which are a simple monalphabetic substitution; you can do a frequency analysis to test if it's plausibly an enciphered English message. If the frequency analysis shows no normal English pattern, try n + 1.

 

There may be a cleverer mathematical attack but I haven't put too much thought into it.

 

(It just so happens that I'm currently reading David Kahn's excellent The Codebreakers, which you might enjoy. It describes many historical cryptosystems and their solutions, along with a great deal of history of their use and abuse.)

 

Yes, but this would only work if there was only one readable message you can get from using the method you've stated. I'm going to turn to the one time pad for an example. Let's say that Eve intercepts the one-time pad cyphertext message Alice sent to Bob and attempted a cryptanalysis on it. Assuming Eve has an infinite amount of computing power, she can figure out the key and get the plain text instantly. However, she notices that one key and the plaintext HELLO is just as likely as a different key and the plaintext LATER. I'm trying to replicate this feature and put it in to a more usable cryptosystem.

 

Now, there's another question I need an answer to. Does having more pseudorandom numbers make determining the pattern between the numbers easier to find? I've read from somewhere that a major problem with the one-time pad is that it relies on the randomness of the numbers in the key, and that making a truly random set of numbers is a non-trivial problem. Would having less pseudorandom numbers make finding the pattern between the numbers harder to find?

No, you wouldn't need to get into the system. If there are long messages or many messages, it gives you more data to try to figure out. Obscurity makes it harder, but that would just make it take longer to break, not make it unbreakable.

 

Public-key systems I think involve a "one-way function", where the public key is easy to generate but the private key is difficult to extract. Eg. factoring of numbers with hundreds of digits is very hard (not unbreakable). A key like "1337" would not be hard because you can just try every number between 0 and a few thousand or millions or whatever and see what you get.

 

If you make a system complex enough like this, and then don't allow anyone access to it, and then don't *use* it too much or send dangerous messages (eg encrypting "a", "aa", "aaa" might give someone some clues), you can probably make something that is likely to be kept secret.

 

Cracking DVD encryption involved having access to a device: '"The nomad" allegedly found this decryption algorithm through so-called reverse engineering of a Xing DVD-player, where the [decryption] keys were more or less openly accessible.' -- http://en.wikipedia.org/wiki/DeCSS

 

I'll be sure to give this a read. However, I think you should read the reply I sent to Cap'n Refsmmat. It's basically the same thing I planned on telling you, but stopped since repeating myself would unnecessarily take up more space.

[Cap'n Refsmmat]

Yes, but this would only work if there was only one readable message you can get from using the method you've stated. I'm going to turn to the one time pad for an example. Let's say that Eve intercepts the one-time pad cyphertext message Alice sent to Bob and attempted a cryptanalysis on it. Assuming Eve has an infinite amount of computing power, she can figure out the key and get the plain text instantly. However, she notices that one key and the plaintext HELLO is just as likely as a different key and the plaintext LATER. I'm trying to replicate this feature and put it in to a more usable cryptosystem.

 

Now, there's another question I need an answer to. Does having more pseudorandom numbers make determining the pattern between the numbers easier to find? I've read from somewhere that a major problem with the one-time pad is that it relies on the randomness of the numbers in the key, and that making a truly random set of numbers is a non-trivial problem. Would having less pseudorandom numbers make finding the pattern between the numbers harder to find?

But you're enciphering each repeat letter (such as both ls) with the same number. If I guess the right base, that will be represented by repeated digits in that base. So I can do a frequency analysis.

 

Basically, if I guess the right base, you only have a monalphabetic substitution. It seems like if I guess the wrong base, then the frequency distribution of digits won't be right to match an alphabet. A proper one time pad requires every letter of the message to have its own key, not just every letter of the alphabet.

[Asterisk Propernoun]

But you're enciphering each repeat letter (such as both ls) with the same number. If I guess the right base, that will be represented by repeated digits in that base. So I can do a frequency analysis.

 

Basically, if I guess the right base, you only have a monalphabetic substitution. It seems like if I guess the wrong base, then the frequency distribution of digits won't be right to match an alphabet. A proper one time pad requires every letter of the message to have its own key, not just every letter of the alphabet.

 

I think I now see why our thoughts on this are different. You're claiming that one cannot reach a solution that makes sense if they guessed the base value incorrectly, while I'm saying that it may be possible to reach an incorrect solution that can be read as if it where plaintext if one guessed the base value incorrectly. Now we just need to ask: "Which one of us is right?" Well, I believe that with a large enough base value, getting an incorrect answer that seems correct is possible.

 

A good way to prove/disprove this would be to take the ciphertext I stated in my first post (1351478792050701588315749385525247210), take the key that's attached to it (both the scrambled letters and the base value) and see if we can turn the ciphertext into a different readable message by only changing the key ( changing the message into something that isn't Hello_World!).

Edited April 1, 2014 by Asterisk Propernoun

[Cap'n Refsmmat]

Do you know about monoalphabetic ciphers and solving them via frequency tables? You can tell if a code is monoalphabetic just by looking at the frequency tables; with a quick statistical test you could figure out whether you're producing gibberish or not.

 

But suppose that doesn't work. Let's think of another attack: the known-plaintext attack, where I know that, say, the end of your message is "Signed, Asterisk Propernoun" or whatever. (Military telegrams often ended with the equivalent of "STOP", for instance, or the name of the unit sending them.)

 

Now, "Asterisk Propernoun" repeats some letters--o, e, and r, for instance. So I just have to convert your message into base n, then look at the last digits in that base and see if the 4th and 14th (e) are the same, and the 5th and 11th and 15th (r), and so on. Once I do this, I know your secret base, and I can begin to deduce the code for each character.

 

Known-plaintext attacks were an extraordinarily popular historical method of breaking ciphers.

 

You might be interested in the idea of stream ciphers, which try to approximate one-time pads:

 

https://en.wikipedia.org/wiki/Stream_cipher

[Asterisk Propernoun]

Do you know about monoalphabetic ciphers and solving them via frequency tables? You can tell if a code is monoalphabetic just by looking at the frequency tables; with a quick statistical test you could figure out whether you're producing gibberish or not.

 

But suppose that doesn't work. Let's think of another attack: the known-plaintext attack, where I know that, say, the end of your message is "Signed, Asterisk Propernoun" or whatever. (Military telegrams often ended with the equivalent of "STOP", for instance, or the name of the unit sending them.)

 

Now, "Asterisk Propernoun" repeats some letters--o, e, and r, for instance. So I just have to convert your message into base n, then look at the last digits in that base and see if the 4th and 14th (e) are the same, and the 5th and 11th and 15th (r), and so on. Once I do this, I know your secret base, and I can begin to deduce the code for each character.

 

Known-plaintext attacks were an extraordinarily popular historical method of breaking ciphers.

 

You might be interested in the idea of stream ciphers, which try to approximate one-time pads:

 

https://en.wikipedia.org/wiki/Stream_cipher

 

Ah, I see now. If the most recent question I asked is answered with a yes, then that means it would be virtually immune to ciphertext only attacks, but not to attacks that compares known plaintext to the ciphertext (not unlike how the enigma flaw was exploited in nazi Germany's enigma code). Thanks for the information. I'll try and see if I can build something with it.

Edited April 1, 2014 by Asterisk Propernoun