Challenges

Hill CPTA

Authorvortex
CategoryCrypto
Tags None
Points23
DateWed 14 September 2011
Help forum3 posts
Afterwards forum4 posts
StateUp
StatusNot Solved
Solvers 23
Votes9.83 (18 votes)
Description
In this challenge, you are going to attack a variant of the Hill cipher.
 
Numerous documents will tell you how to recover the key of a Hill cipher with a few plaintext/ciphertext pairs.
This attack requires the knowledge of the values attributed to the letters.
 
Here, these values will be unknown to you. In compensation, you will be allowed to choose up to 32 plaintext blocks and get their encrypted values. The matrix and the permutation alphabet will be different each time.
 
The page hill_cpta.php takes a cpta GET variable, which contains your plaintext blocks (uppercase, separated with underscores, like cpta=ABC_DEF_GHI).
 
You will get, besides the corresponding ciphertexts, five 'challenges', or random ciphertexts, that you will have to decrypt (the decrypted values won't be intelligible).
You will then send your answer to the same page in a solution GET variable.
 
You have 10 minutes to solve it.
 
Example:
  1. Call hill_cpta.php?cpta=JNA_CEB_UXQ_OKS_IRE_XQV (those six blocks probably aren't enough)
  2. The page computes a matrix: 
    [[25, 8, 8], [7, 3, 15], [8, 21, 22]]
    and determines the letter values: 
    A : 22 , B : 3  , C : 14 , D : 11 , E : 0  , F : 8  , G : 25 , H : 13 ,
I : 20 , J : 24 , K : 19 , L : 6  , M : 10 , N : 2  , O : 18 , P : 15 ,
Q : 7  , R : 16 , S : 17 , T : 4  , U : 9  , V : 23 , W : 5  , X : 12 ,
Y : 1  , Z : 21
  3. Answer of the script: 
    JNA -> XMR
CEB -> MHA
UXQ -> HAM
OKS -> MAQ
IRE -> TLN
XQV -> IFZ
Challenge #1: JLI
Challenge #2: RGE
Challenge #3: ZWN
Challenge #4: UIJ
Challenge #5: QOP
  4. Call the page hill_cpta.php?solution=ARL_JRP_QCA_KMH_WKN, and get the password (don't forget the PHPSESSID if you're doing that with your own client).

 Source of hill_cpta.php
Please use it to ensure that you have a reasonnable success rate before spamming the site (I reached about 1/2, but you can do better).
Needless to say, online brute-force is prohibited.

It can probably be solved in many ways. I hope you'll enjoy it.

Links:
  1. An explanation of the Hill cipher
  2. Hill Ciphers and Modular Linear Algebra
  3. How To Compute The Modular Inverse Of A Matrix
  4. Mathworld
  5. An explanation of the Hill cipher(in French)
Flag
Solvers
Login


No account yet? Register.
Last challenges
Last forum posts