8
$\begingroup$

Short version of the backstory

A college professor of mine stated that one could not come up with a single-step encryption method that used an algorithmic process (as opposed to pre-shared randomization, like a one-time pad) to reliably and un-crackably encode messages, insisting that the better method would be to layer multiple methods with entirely different processes so that a code-breaker would not get any meaningful results from their attempts. That, aside from meeting in person and sharing one-time pads, you couldn't put out something that was secure against a persistent and well-equipped codebreaker. I, being young and stupid, disagreed.

I started by developing terrible methods. For example, rather than a standard shift cipher of a set amount, I tried doubling the value of each letter in the message. Yeah, like I said, stupid. But, from there, my process grew.

Ultimately, I came up with a system that I think works pretty well. I would love to test it out on someone, but my local area is not exactly brimming with cryptanalysts. So I present to you, Stack Exchange, the beta version. It is simpler than my actual process in several ways, but follows the same general process. I fear the full method may be too difficult, so let's see how this goes.

Are you done talking yet, MisterB? Get on with it!

Yes, sorry.

To be clear, the same encryption process is applied to each of the following examples, and is the same as it would be when applied to any message. When I say "a single process," I mean that it is not a combination of multiple alterations/replacements/etc. It could be "shift first letter up one, second letter down two, third letter up three..." (which it ISN'T), but that's still a single instruction as it could be explained in general for the Nth step, as opposed to "Vignere the message, then AtBash the message, then Playfair the message." Hopefully I'm explaining that well enough.

Here are a handful of examples of plaintext and the encoded result. I can provide more. I'm putting them pre-formatted so there's no ambiguity in the letters (upper-case I vs lower-case L, for example). Note that this formatting is not important, and it could just as accurately be handwritten in cursive, or presented in any other font or format that was legible.

No pre-shared key is necessary. There is no password that must be known to encode or decode the messages. Everything necessary for any message is present in the message itself, and receiving the encoded result is sufficient to find the plaintext, so long as you know the process.

Plain: Sample
Encoded version: Wevttn

Plain: A longer sample
Encoded version: IgNxvjhvfUattml

Plain: ABCDEFG
Encoded version: Gfhkjgj

Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Encoded version: Akldfolilotntvsxtrsvbxyazz

Plain: This is a test phrase
Encoded version: YpkxgNyiEiYj x Phxf m

Plain: This is a test phrase with more words
Encoded version: TpkzfKxcAbBmuuiVpzjanfDmvleOotefCoxfs

Plain: This is a test phrase with even more words in it
Encoded version: Bjqu DucAb jxtiQovbsmgDmwnfExhrhVsxlgCptft JsbMu

Plain: Stack Exchange
Encoded version: ZxbipgHeiohqpi

Plain: Puzzling Stack Exchange
Encoded version: WcdgojsicVucjliJadmjukh

Plain: Puzzling Stack Exchange might solve this
Encoded version: Swcdqnqi VwgjphKcfqjunmgMqopzeWrsvkgXkrt

Now for your challenge: I'd like you to show your understanding of the process by doing two things:

1) Decode this:

LhFnfXpegTpewtiswaUtlbfrdNwjv

2) Encode this:

I know how to encode this phrase

Another important thing: you'll want a computer for this. It is technically possible to do by hand, but it would be cumbersome, as with many ciphers. The longer the message, the more difficult it becomes. But the ability to write programs is not at all required. I encoded all of these without any programming (and without using an online encoding/decoding program).

I've seen you folks on Stack Exchange solve some ridiculously complex codes and puzzles using what can be described as nothing less than wizardry. So if anyone can do this, some subset of you can. The "unbeatable" was a bait title, sure. But in upholding my stance against my professor, I'm hoping it can be done with a reliable (but difficult) algorithm to detect. I'd like it if safe encryption can be accomplished this way, rather than simply won by one-time pads.

I'll offer hints if there is interest in the challenge and it remains unsolved, but the Stack Exchange sorcerers may not even need them. And, if this is too easy, I can present my final product and see if that fails in short order, as well. I'd rather you all find it than my professor!

$\endgroup$
  • $\begingroup$ I guess answer to 1 could be I know how to decode this phrase:) $\endgroup$ – Preet Oct 27 '17 at 0:35
  • $\begingroup$ A couple of observations. 1. Ciphertext is always same number of characters as plaintext. 2. Spaces frequently turn into letters. 3. Letters in ciphertext are capital if and only if their position is that of the start of a plaintext word. (So on information-theoretic grounds I'm guessing that the cipher doesn't distinguish between uppercase and lowercase in the plaintext.) 4. It seems like ciphertext letters are usually not very far in the alphabet from corresponding plaintext letters. $\endgroup$ – Gareth McCaughan Oct 27 '17 at 2:47
  • $\begingroup$ 5. Ciphertext character corresponding to a space seems always to be space or a-i. This suggests that we regard space as "letter 0" and that spaces are always adjusted upward by 0-9. In fact it looks to me as if this is true of all characters, so now we are looking for a way to turn plaintext into an equal-length sequence of digits. $\endgroup$ – Gareth McCaughan Oct 27 '17 at 2:49
  • $\begingroup$ 6. However, what happens to ABCDEFG in no obvious way resembles what happens to the start of ABCD...XYZ, suggesting that whatever process yields these single-digit offsets is somewhat "global". (We have 6457513 in the first case, 0990195... in the second.) $\endgroup$ – Gareth McCaughan Oct 27 '17 at 2:53
  • 2
    $\begingroup$ Incidentally, even if no one cracks this your professor is still right and you are still wrong. Suppose you use a cipher of this kind ... and then, one day, either someone you're communicating with gives away the secret or your adversary puts in immense effort and does crack it. From that point, the cipher is useless. Even if you discover that your messages have been read, you need to pick a completely new cipher. Whereas with something more standard, in that situation you just need to change your keys. $\endgroup$ – Gareth McCaughan Oct 27 '17 at 11:15
14
$\begingroup$

To encrypt: Suppose the plaintext

has N characters.

Then

compute the decimal expansion of sqrt(N), and add successive digits after the decimal point, mod 27, to the characters of the plaintext, taking space as 0 and A-Z as 1-26. (Ignore digits before the decimal point; equivalently, take the fractional part. To be absolutely explicit, we are writing frac(sqrt(N)) in base 10, not base 27, though the latter would have obvious advantages.) Capitalize letters that were at the starts of words in the plaintext.

So, for instance, let's decrypt LhFnfXpegTpewtiswaUtlbfrdNwjv as requested.

This has 29 characters. The fractional part of sqrt(29) is about .3851648071345040312507104915403295562951201616. So shift the letters back by those amounts; we get I AM THE SMARTEST SOLUER EVER which appears to have a single off-by-one error in it.

And let's encrypt I know how to encode this phrase.

This has 32 characters. Fractional part of sqrt(32) is about .656854249492380195206754896838792314278687501507792. We get OeQvtabLxaiVrhEoltfefAmmaiVpui n.

Exercise for the reader: what do you get when you "encrypt" This is annoying?

$\endgroup$
  • 4
    $\begingroup$ Are you trying to make us type sqrt(16) into our scientific calculators -- and then feel silly about it? :) $\endgroup$ – M Oehm Oct 27 '17 at 12:56
  • $\begingroup$ That would be one of several acceptable outcomes :-). $\endgroup$ – Gareth McCaughan Oct 27 '17 at 12:57
  • $\begingroup$ I knew I should have started with a harder version. And you didn't even need the clues I gave in the question, it looks like! (Did you even see them?) Maybe I should post one of my subsequent revisions. Nicely done! $\endgroup$ – Mister B Oct 27 '17 at 15:20
  • $\begingroup$ And you're right about the transcription error. I did the rotations by hand on paper, so I must have miscounted. $\endgroup$ – Mister B Oct 27 '17 at 15:21
  • $\begingroup$ I'm sorry to say I didn't spot any clues in the question. In fact, I still don't, though I do see a few oddly phrased portions of the question that might hold some secrets. $\endgroup$ – Gareth McCaughan Oct 27 '17 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.