1
$\begingroup$

I was given the following exercise to solve:

The Hawaiian language consists of 12 letters. There are 7 consonants: HKLMNP and W and there are five vowels: AEIO and U. In a word, no two consecutive letters can be consonants and all words end in a vowel. Suppose you are given, without spaces, a very long list of putative decrypts of a given cipher (where you know the plaintext is Hawaiian). Let’s say you have $2^{50}$ decrypts. The decrypts may only use the 12 letters. How would you analytically recognize the answer? Quantify how efficient your method would be - and how long a text you would require to be able to (probabilistically) differentiate between the correct answer and random “noise” (where you can assume that you don't read or speak Hawaiian)?

I don't know where to begin solving this. Any sense of direction would be great.

$\endgroup$
  • 4
    $\begingroup$ This looks like a homework dump. We are okay with helping you with your homework, but we need to know where you are stuck in coming up with the answer on your own. What have you tried? $\endgroup$ – mikeazo Oct 3 '17 at 19:06
  • $\begingroup$ I don't know where to begin, a sense of direction would be great. @mikeazo $\endgroup$ – kathy Oct 3 '17 at 19:16
  • 3
    $\begingroup$ I'm reading the question differently from @mikeazo . I assume that no Hawaiian dictionary or knowledge of frequency distribution in the Hawaiian language is available. It is still possible to eliminate those putative decrypts that violate the one stated rule in the Hawaiian language: "no two consecutive letters (in a word) can be constants, and all words end in a vowel". The task is to estimate how effective that is. It can be solved by a simulation or reasoning assimilating putative incorrect decrypts to uniformly random letters among the 12. $\endgroup$ – fgrieu Oct 3 '17 at 19:41
  • 1
    $\begingroup$ Hint: we can replace all constants by H and all vowels by A. After this, ciphertext "AAHA" can no be eliminated for it could be "A A HA", "A AHA", "AA HA", or "AAHA". But we can eliminate "AHHA" which can't be Hawaiian. $\endgroup$ – fgrieu Oct 3 '17 at 19:57
  • 1
    $\begingroup$ @kathy: think it through; why can't "AHHA" be Hawaiian? Are there other patterns that also can't be Hawaiian? Is there any simpler patterns that never show up in valid Hawaiian? $\endgroup$ – poncho Oct 4 '17 at 18:36
1
$\begingroup$

Let's assume that the incorrectly decrypted messages look like random sequences of letters. That assumption might not be exactly correct, but for most modern ciphers it should be pretty close. In any case, the mention of "random noise" in the assignment suggests that this is indeed the assumption that we're supposed to make.

According to the given rules of Hawaiian morphology, no word may contain two consonants in a row or end in a consonant. This implies that the correct plaintext can never contain two consonants in a row.

In an incorrect plaintext, the probability of each letter being a consonant is 7 out of 12. From this, you should be able to calculate (or at least approximate) the probability of two consonants appearing adjacent to each other in the incorrect plaintext as a function of its length.

Given this probability, you can then calculate the probability of all the $2^{50}-1$ incorrect plaintexts having at least one pair of adjacent consonants. Then pick some reasonably high target probability (say, 0.9999) and calculate the minimum plaintext length needed to meet it. (Of course, you really should give the full formula for the plaintext length needed to reject all the incorrect plaintexts with a given probability, so that the person reading your answer can choose a higher or lower target probability if they want.)

| improve this answer | |
$\endgroup$

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.