Megan and the alphabetic cipher (smhrjc etc)

Question

I had just arrived for my lunchtime meet with Megan in Pizza Espresso, when up walks the woman herself, resplendent in a long velvet skirt and matching jacket.

"Gosh, you look beautiful."

"Thanks. Thought I'd wear something a bit special for Gwyl Canol Hydref." Seeing my blank look, she went on, "The Welsh name."

"I see." I made a mental note to look that name up later.

Megan ordered calzone, and I ordered pizza. "Nice choice of venue," I said, "I love a pizza."

"So do I, but I picked this place as it does other Italian food, too. Anyway, something in an e-mail the OH sent me the other day made me think it might be appropriate." She took a folded A4 sheet from her shoulder-bag and handed it to me.

I unfolded it, to be greeted by a tangled mess of words, right-way-up and upside-down. "Double-sided printing gone wrong, Megan?"

"The other side!" she said.

I turned the sheet over.

From: RD_Jones <[email protected]> To: Megan <[email protected]> Subject: Another cipher puzzle
Hi Megan,
I'm impressed at how your friends managed to crack my cipher puzzle. I wonder how they'll get on with this one. Same deal as last time. English text which can be found on the web. And I've enciphered the spaces.
smhrjc_aylciursmotkflexsojloluiauigkeufnzrioawvuvsk_nx_gnip_westq_n_gau_uhg_nbmvxcxixkvrxbydwqvgwhwvzlolmkgglqwwgabvgores_vvuio_gf_fcthbciljcnnngswaoicbubsr_pewfgatyqlsvyernqty__jhbqudorvbcpawkgi__shxgdssslorjlaav_asje_kg_lajoqihyzahufrkudlgwxhcdzialnenalqovl

Like a calzone? ;-)

"I see he's using letters now. And spaces -- I take it those underscores mean spaces. No mention of a key, though, so I guess we don't need one." I smiled in recognition at the last line. "So that's why you picked here -- you like calzone?"

"Never had it before. Ordered it to see what it was."

Let's see if inspiration strikes. With or without eating any Italian food, can you identify the plaintext and find out the encoding method?

Hint 1:

To make a calzone, you take a pizza base, and put fillings on one half. Then what do you do with the second half? Jasen has the right idea.

Hint 2:

Steve Mangiameli is onto something with his comment about the day on which I posted this puzzle. Might a pertinent English word appear somewhere in the plaintext? And the spaces have been enciphered. So if, for instance, you suspected that plaintext contains the word "crib", you may look for the 6-character sequence "_crib_" (where _ stands for a space).

Hint 3:

The second half of the plaintext has been combined with the first half like a calzone -- the second half is folded back over the first half. As a result, it lies upside-down. What does that correspond to in text terms? Addition -- or rather subtraction, because the second half is upside-down. Modulo what base? The set of characters seen in the ciphertext should make that clear -- remember that underscore stands for space.

The plaintext turned out to be of odd length. The resulting ciphertext is the same as it would be if the plaintext had an extra space at the end to make its length even.

Answer 1

The plaintext is...

The first stanza of the poem To Autumn by John Keats

(Exact plaintext, as enciphered):

season_of_mists_and_mellow_fruitfulness__close_bosom_friend_of_the_maturing_sun__conspiring_with_him_how_to_load_and_bless__with_fruit_the_vines_that_round_the_thatch_eves_run__to_bend_with_apples_the_mossd_cottage_trees__and_fill_all_fruit_with_ripeness_to_the_core__to_swell_the_gourd_and_plump_the_hazel_shells__with_a_sweet_kernel_to_set_budding_more__and_still_more_later_flowers_for_the_bees__until_they_think_warm_days_will_never_cease__for_summer_has_oerbrimmd_their_clammy_cells__from_to_autumn_by_john_keats_

The cipher

The cipher in this puzzle is only marginally a 'true' cipher, since approximately half the information is lost. In that way, it could almost be considered a hash function. This is how it works:

We'll start with this plaintext (using the alphabet _abcdefghijklmnopqrstuvwxyz):
this_is_a_string_of_text

Per Rosie's edit to Hint #3, if the plaintext is of odd length (as it is for the puzzle), simply add a space to the end to make it even length.

Take the plain text in two halves, and reverse the second:
this_is_a_st
txet_fo_gnir

Now, subtract the second line from the first, where _ has the value $0$ and z has the value $26$, then apply a modulus of the length of the alphabet to the result, and interpret as a character:
h$-$x
$(8 - 24)$ mod $27$
$-16$ mod $27$
$11$
k

So, applying this to our plaintext, we get:
_kdz_cd_umjb

When applying this method to a much longer plaintext, we see similar characteristics to the puzzle's ciphertext.

Solving it

We now have the ciphertext _kdz_cd_umjb. Let's say we also know the word text occurs somewhere. (This knowledge will henceforth be referred to as the crib).

When trying to determine where the string text belongs, there are two simple options (although there are also edge cases); either our crib is in the first line of plaintext, or the second. If it is in the second, it will need to be reversed.

First line case
Since $plaintext1 - plaintext2 = ciphertext$, we know that $plaintext1 - ciphertext = plaintext2$.

So, assuming that the plaintext starts with the crib, we simply need to solve this:

  text????????
- _kdz_cd_umjb
= tutu????????

Seeing that the result (reversed, since it is the second line) of utut is probably gibberish, this configuration is a no-go. We can try the same for all other positions in the first line.

Second line case
Since $plaintext1 - plaintext2 = ciphertext$, we know that $plaintext2 + ciphertext = plaintext1$.

So, assuming that the plaintext ends with the crib, we simply need to solve this (the crib is reversed, since it is in the second line):

  txet????????
+ _kdz_cd_umjb
= this????????

Seeing that the result (as is, since it is the first line) of this is an English word, this configuration is a possiblity.

Pulling it all together
The full list of words found using the two above strategies is:
utut tyai qxfp pueu ttbt zxaq gcep jkkt rnsz
this dadt xwew sxhx t_it waen xxzf trrc njov

Along with this, t_it is also a possibility. Using a longer crib may eliminate false positives. If we apply the crib text_, the false positive becomes zt_it, but we also lose the actual solution since the plaintext doesn't have a space after text.

Note that these methods will not catch the case if the crib crosses the fold, such as the word string.

We also can apply the knowledge that a _ in the ciphertext signifies matching characters in the plaintext, and other observations like this.

Another note, the alphabet in question includes the letters a through z, and _. Here, I am assuming that the space is at the beginning of the alphabet, but it may also occur at the end, which will change things. This ambiguity is equivalent to 0-indexing vs. 1-indexing for the alphabet.

Applying this knowledge to the puzzle

I initially applied this technique to the puzzle's ciphertext with the crib _equinox_. There aren't any English words in the output. Full output is in this pastebin. This suggests that the word 'equinox' does not occur in the plaintext.

I tried a number of other potential cribs, and a few resulted in recognizable English words: _autumn_ gives s_and_me, _flowers_ gives t_the_vin, and _fall_ gives melds_. (The latter doesn't actually occur in the plaintext.)

However, the big breakthrough came from the crib season_. When tried as the first word of the plaintext, it suggested that the last word is _keats_. A name! Of a poet! Plugging in _john_keats_ gives season_of_mi. I typed "john keats season of" into Google, and it led me to the Wiki page for the poem.

By trying more of the poem's first line, I was able to determine that the excerpt ends with "cells". The first stanza then. Converting that stanza to our cipher alphabet, and running it through my encipherment program, it spat out exactly matching ciphertext. Yay!