Extracurricular challenges

[upsidedown]

Since I have a couple of Hill ciphers I want to post, here’s a topic for ciphers from competitors (distinct from Programming/Puzzles).

To prove you’ve solved one, post md5(your username || UPPERCASE PLAINTEXT) (read on if you don’t know what this means).

In case people are unfamiliar, this proof method was originally proposed by madness a few years ago. Anyone who knows the plaintext can verify that you solved the cipher, but the output of the md5 function (a hash function) does not reveal the solution to others (and it can’t be forged without knowing the plaintext). You can generate a proof with the following python code:

from hashlib import md5
def proof(username, plaintext):
    string = username + plaintext.upper()
    return md5(bytes(string, encoding="utf-8")).digest().hex()

plaintext = "....."
print(proof("upsidedown", plaintext))

[upsidedown]

After some additional optimisation I got the program that solves the first cipher down to 25 seconds and the program that solves the second cipher down to 1.5 seconds.

[upsidedown]

Here is the first of 2 hill ciphertexts, inspired by madness’ suggestion of a constant vector addition.

For both ciphers, if there were fewer letters in the keyword than the matrix size and (for example) the keyword ended with X, I would have filled the remaining matrix entries with Y, Z, ., _, A, B, and so on until the matrix was full. I filled the matrix in the standard way, left-to-right, top-to-bottom, without discarding duplicate letters.

First cipher: upsidedown-2025-1

This cipher uses a 3×3 matrix (mod 28), generated by a keyword, with a constant vector (size 3) added to each block AFTER encryption. Alphabet: ABCDEFGHIJKLMNOPQRSTUVWXYZ._ (the underscore is used as a space character in the plaintext)

DXZZGMXHP.HVMGIAOIYTFYWAJOUGLDSLTAOOPHLRHXYRMZ_TFCMAGGYAZOPJFIQBPXSLTKRGZLB
FWEPPRHZMYFFSJYVP_MDHCSKQFITE_ZVBYF.DYIRUDMZPJEJFWEOIJBMSUCFRHXWRAHEIAGNMNG
NRCHFRIMAHBGZTXMDTMVA_MAYOEIAVWGUI.GYF.H_ZTD_AEDYWAUCFZT_YQ_AHPAGUCQAECORF.
QQOAGUNUPB_KQ_FGAUXZANJGTBBEJ.BTOXLO_NFMTF_DDAGGMHHDWATDDQ_FIHZ.__HJK_AWADL
JJOAQBDNJEDQB.A_POYTFECGYYYHUALJWZLBZKAQWEQ_FIMMBTOQWULXSMGIFDDKRGMCSAGMKGY
UCDSQU.SAMDRTBGBTOLJWP_KQFQ_TCLJSRPIYF..WRVNGIPHUOGDNDGKFBHLQHPP.ABTOR.KH_S
YZITWECGLIVSDMAYMF.SFIHLS.ILAEJJMXVGAGNIHZGLDIHLKRGYUFARWPDWECEBTODAMA.E_CV
YMLCBSPDWECEBTONWOMF_VETIXZVBGTXCWGUAGGUFSYSKAGMW.GXJ.YKVB.SIB.DMAAHPEDQX.E
EQ_ZQU.SAMDRTBGBTOLJWQGLYMFAOWDGY_Z_GAUTPW_RC_VVDHJNE.ECEMYNYTVWROAGAGMNXVD
FJAPGXQ_TKRGBTOUOPQBTYHXWROAGAUOWJOUYSJR__XEMIPHUQMZTXUXFNBQDRWYVDKKIQ.YULL
LJSZOIEDQB.AGMNXVDMOYJWAMNUNHONRXQ_TNVSLC.UQMBNKX.EQQOAIMZTXR__CAMUXFPOHW.G
R_BFEJMSBPW_Q_TAOWFNGAGACQAECORF.QQOAGUNUPB_KYFFODBMALEVWAGAAQQLT_AQLAOIAJP
GWKC.STLXARILKDUCF.LFAGGUFEJBFTXKJJ.EZNLEMIXLP.MTPWLHPJQIYIVABVCWGMWEWIHQU_
.IURWFHIYPB_I.GYF._BOPCQECESAZFLXUXTNVSLJWZKO_OBZDHERQLABL_TSKAAGUZERMBS.WK
ASZMQCF.MQQOQCAFEXQFQ_TCTBBYF..WRVNGIPHUMVYLLUMAHRXEOMX_JOXVAMTTDDKRGDSIXJ.
QQBUYITBBYTFYGBIPHODPWROAGAPWHAXHUBMXMKUOKXBTECED_W_KRECEIKQAOWG.HYF.XONUXT
UDHWBFQENHOLECEYMRGTSYTFAWTQSIIPHTSVMZ_JJ.IIXUCFRVCPDWQQOUQMPFORUDQGTMOYMRL
FXKDFHW.YBTOIPHUXTUDHWBFAGGADBXX.AUGYTFAWFPWBYMFBCJOGAMRZTLWTDRK_PGWKHRWI.S
_VSIPHDZGWKSAOIAUGYTFFNGMGIUCFFRKZQAEO.DVQTKRCPLWROAGAXBLGWKVET

I have a program that solves this (ciphertext-only) in about two minutes. I can give cribs if needed.

The addition of a constant vector is more or less the same thing as composing a Vigenere cipher on top of the Hill cipher. So if you make the matrix the identity matrix this gives just a Vigenere. When the matrix (and thus the addition vector) is one dimensional you get an affine shift cipher, so this system is really very general and definitely worth studying! Harry

[upsidedown]

Second cipher: upsidedown-2025-2

5×5 matrix (mod 31), this matrix is keyed with a multi-word phrase from my favourite film, with a constant vector (size 5) added to each block BEFORE encryption. Alphabet: ABCDEFGHIJKLMNOPQRSTUVWXYZ09:._ (ditto for underscore character)

If you’ve watched my favourite film you might be able to derive some cribs from the selection of symbols included in the alphabet.

KENMTZF9NM9EVTSUSSQHO_.SUQYEEGIODJZOKMSV:ISDOKN0ZSLQNK.IYOKOGACFTHMROILKNNR
IVC9IRSWGDQ:J0ZWNENQJMWWKBKSAF:ISDOKN0ZSTUNW.FR.F0VMW:0P_TKNEP:XMMXFUROMY.M
XN9PB9AEFQBJ9UMBCFTTQBBPLEBTSKIJZWOX0QS:WBCYCKHE0QMZOOFUIAKW_DJTD:ISDOKN0ZS
MU0ZM_FGIXHUQKLHY0DRRI9TMJDHJDGOB.TJDFX.9BXOUTTLC.XGRWBIYOKOF0N:MFUNTQPJNDM
FR.F0J.ICT0B.DOJWHE0RD.MKAGFFUT:D:LHAADGISEQEI9EXH.I.0NIOUVTWOUSV9KGURPBXTA
AS9O9GWK.RLP0AZHHAAPULMR_VQVZCX.UBMYQ:FGBRZWGHKHIP0CCMF9AISQLU0__PNJKPL9PHY
VQZHHNCNKMIZEOUPQDHV:YNVFDYPYNTTLC.EURXI_IEGCREUKHKCPQ.PVI0.U9RZ:JZPPFSDLQ.
GDPTJKSPRONEKQUD_PHZBT9XAE.OGEFNQHKDEOSVMAMPCKDGAMZNCJSV.WBR:.ZVUBELOLPJNDM
RZ:C..XCSXY.R:L9TAKEJWFQGPFRWZ9FK9O.TVZB0_0__MUTLKDR0J.LL9GGKP.RKMCO_LNFWCU
MSGBNHVQ.0FJSQVPNF_RGCX_GIHT:ZPUNG:VIHKXUOPGG.ZB.OM_Q0NUGUTOTP.BNU_GJGVMXKC
UQVSNGPKV_FWWDY9NU:SKRBBDXEOKC_JLD.VOOMFBKHOLI9BQ_SLIWDXMKG_XTOE0EL_PDQ9GXU
FWDTTGFVIUDZJQ0QNCDGLSFM:IMKNUN.KGOC_XFPGY_XZCVHWPSDLQ.GDPTJF.M.ALDSRTBR.P:
ENOLINMBQZTF.GLKGRPZXTMSQSVAEGWGVT:LD0:LLO.MGIKYYWSDQRXNOFUFCVQ9:_IUCODMELM
V:NYIKQTXLYW9YWZ9::FXYPU.LMD_PTEVS9EBD.S0VG9.PNJKPNQGCY9DDEU

As before, I have a program which solves this in under two minutes.

[upsidedown]

Have my previous two posts in this topic been lost?

No, they were in the pipeline, but the Elves got trapped by the Cloudflare outages and couldn’t find their way back. All present and correct now. Harry

[Crackerjack_404]

@upsidedown

Sorry if this sounds really obvious, but which cipher are you referring to? Is it ciphers from the challenges or some other hill ciphers?

[Puzzling_Pelican]

MD5(“Puzzling_Pelican”, upper case solution to part 1 (still using _)) = 912073d52b1cfa07506a24c935404ffa

That was a nice cipher.
P.S. Your points for the bonus cipher challenge (for anyone who hasn’t seen it, look at the daily cipher thread) have been refunded and I have fixed the issue you found. You still have the final two ciphers, one of which you still have time to break before madness :), enjoy!

[upsidedown]

@Puzzling_Pelican correct, well done 🙂 Thanks for refunding the points, but since I did deliberately request one (but not two) of the hints could you deduct the points for just that one from my score? I’ll definitely have another crack at the last two ciphers in the coming days.

Perhaps we can all discuss our methods for solving my pair of hill ciphertexts in a week or so.

Also, I omitted a decimal point in my “25 seconds”, it was meant to be “.25 seconds” (but now I’ve got it down to ~10ms).

[Puzzling_Pelican]

And part 2:
MD5(“Puzzling_Pelican”, solution to part 2) = 430312e8fade8be57af771bdaec58359

Nice job on the ciphers, they were a lot of fun to break and I look forward to a part 3!

[the_cryptographer_formerly_known_as_madness]

md5(“madness” + PLAINTEXT_113625) = 198ff90b92432257f2bbf044c6a7e570

I posted a note in the topic “!” about how the description of #113625 is backwards; sorry, please read it there. So, @upsidedown, could I please see the code you used to generate the next one, #113626, before I spawn an A.I. superintelligence from the future to attack it? Thank you for that and for the challenges.

[Robb27]

I am following this with interest. Work unfortunately has been busy for me, leaving just enough time to look at the main Challenges this year, and not really look in to these very interesting extension challenges. I may not get chance until after Christmas.

@upsidedown
I can see the approach to decryption, but getting this down to milliseconds for a 3×3 Hill, even given the understanding of how you generated your keyword, that sounds impressive (unless the key word prior to the padding is very short ;-). I’d be interested in seeing your code, either in full or psuedo at an appropriate point.

… and to anyone adding these extra challenges, thank-you for your time in compiling and posting them. They are always appreciated.

[upsidedown]

@Puzzling_Pelican yep, correct again. Glad you enjoyed them! I may have an idea for a part 3 so we shall see.

@madness md5 correct.

Would you not agree that since matrix multiplication is distributive over addition, ie. M(u + v) = Mu + Mv, it doesn’t actually matter whether the shifts were applied before or after the matrix multiplication?

Suppose the encryption matrix is E, its inverse is D, and we add vector v before encryption (vectors p and c for plain/cipher):

# shifts added BEFORE matrix encryption
 E(p + v) = c
  Ep + Ev = c

let u     = Ev

# shifts added AFTER matrix encryption
  Ep +  u = c

Here’s the code for upsidedown-2025-2 as requested:

import numpy as np
alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ09:._"
m = len(alphabet)
size = 5
vector = "AAAAA"
# The actual key phrase has more than one letter!
keyword = "A"

V = list(alphabet.index(c) for c in vector)
V = np.array(V)

# extend key phrase to fill matrix
E = list(alphabet.index(c) for c in keyword)[:size**2]
while len(E) < size**2:
    E.append((E[-1] + 1) % m)
assert len(E) == size**2

# create encryption matrix E
E = np.array(E)
E = np.reshape(E, shape=(size, size))

# convert plaintext to numeric array
plaintext = "THE_PLAINTEXT_WITH_UNDERSCORES"
plaintext = "".join(c for c in plaintext if c in alphabet)
plaintext = list(alphabet.index(c) for c in plaintext)
plaintext = np.array(plaintext)
assert len(plaintext) % size == 0

# [aaaaabbbbbccccc] => [[aaaaa],[bbbbb],[ccccc]]
plaintext = plaintext.reshape(len(plaintext) // size, size)
# (p + V) % m
plaintext = (plaintext + V) % m
# matvec multiplies E by each vector in plaintext
# E(p + V) % m
ciphertext = np.matvec(E, plaintext) % m
ciphertext = ciphertext.reshape(len(ciphertext) * size)
print("".join(alphabet[c] for c in ciphertext))

[Puzzling_Pelican]

@the_cryptographer_formerly_known_as_madness
Correct me if I am wrong but does the order of multiplying and adding the vector make a difference? It appears that both are reversible by multiplying by the inverse matrix and subtracting a vector, only that when reversing text encoded with the addition after encoding, this vector is not just the negative but takes into account all of the shifts and values in the matrix, however is still a value between 0 and MOD.

Example for 2×2:
Shifts S1 and S2
Addition before multiplication:
Encryption:

╭     ╮ ╭      ╮   ╭   ╮  
| A B | | x+S1 | = | m | 
| C D | | y+S2 |   | n | 
╰     ╯ ╰      ╯   ╰   ╯ 

Decryption:
Let a,b,c,d be the modular inverse of the matrix

╭     ╮ ╭   ╮   ╭    ╮   ╭   ╮   
| a b | | m | - | S1 | = | x | 
| c d | | n |   | S2 |   | y | 
╰     ╯ ╰   ╯   ╰    ╯   ╰   ╯ 

Addition after multiplication

╭     ╮ ╭   ╮   ╭    ╮   ╭   ╮   
| A B | | x | + | S1 | = | m | 
| C D | | y |   | S2 |   | n | 
╰     ╯ ╰   ╯   ╰    ╯   ╰   ╯ 

so

╭     ╮ ╭   ╮   ╭      ╮  
| A B | | x | = | m-S1 | 
| C D | | y |   | n-S2 | 
╰     ╯ ╰   ╯   ╰      ╯ 

Decryption:

╭     ╮ ╭      ╮   ╭   ╮  
| a b | | m-S1 | = | x | 
| c d | | n-S2 |   | y | 
╰     ╯ ╰      ╯   ╰   ╯ 

so

╭                   ╮   ╭   ╮  
| am+bn - (aS1+bS2) | = | x | 
| cm+dn - (cS1+dS2) |   | y | 
╰                   ╯   ╰   ╯ 

Giving

╭     ╮ ╭   ╮   ╭         ╮   ╭   ╮   
| a b | | m | - | aS1+bS2 | = | x | 
| c d | | n |   | cS1+dS2 |   | y | 
╰     ╯ ╰   ╯   ╰         ╯   ╰   ╯ 

Where the vector subtracted is equivalent to just a new shift vector.

When decoding both ciphers, I first multiplied by a matrix (which must have been the modular inverse of the key) then added a different shift to every row of the output vector.

I may be completely wrong in which case both ciphers had the addition before multiplication during encryption.

I hope this helps and good luck with the 5×5.

P.S. Use the hint button for 10B in my challenge, it will be near impossible to guess how the cipher works with no extra information (it took me over a year to design the cipher used).

[upsidedown]

@Robb27 I’ll defer releasing the pseudocode for my algorithm to give people more time to solve this, but I will reveal some details.

While there are some additional optimisations for these ciphers, the core algorithm is described in #113373.

My program does a brute-force search of the entire 3×3 matrix + length 3 shift vector space (and likewise for 5×5 + 5), it doesn’t know about keywords or padding. It’s written in Rust and uses all 12 logical cores of my CPU, so you could say I am cheating a little bit by saying 10ms, it would be around 12x slower on a single core. I might investigate writing a solver in a GPU compute shader as well, since GPUs are rather good at matrix multiplication and should be able to handle larger matrices.

[the_cryptographer_formerly_known_as_madness]

@upsidedown,

It turns out that what was true yesterday is no longer true today. How this could possibly be is a question to ask my pet mice. But as for today, you are correct.

@others,
The secret to solving Hill + Vigenère ciphers quickly is that you only have to do one row of the inverse matrix at a time.

[Author]

Posts