How to start a classical cryptanalysis on a Substitution + Shift cipher? [closed]

Question

i was thinked about problem of Cyrpto.

At first glance, it looks like a simple classic password problem, but there are a lot of difficulties to think about the way the two encryption schemes are mixed.

The process is as follows. First, create a substitution table for 26 alphabets.

Second, we select two key values for the shift cipher.

For example, the substitution table looks like this, and the key value of shift cipher is (3,7).

Original..  : A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 
Substitution: N E O B F M D Q V P U A W R I K Y J C S Z L G T X H 

Plain Text : "APPLE"

first, The letter corresponding to 'A' is N.

cipher : APPLE --> NPPLE

second, Shift key 3 shifts the shift table to the right, and then maps the table.

Original..  : A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 
shift table : T X H N E O B F M D Q V P U A W R I K Y J C S Z L G 

cipher : APPLE --> NPPLE --> NWPLE

third, Shift key 7 shifts the shift table to the right, and then maps the table.

Original..  : A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 
shift table : Y J C S Z L G T X H N E O B F M D Q V P U A W R I K  

cipher : APPLE --> NPPLE --> NWPLE --> NWMLE

forth, Shift key 3 shifts the shift table to the right, and then maps the table.

Original..  : A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 
shift table : R I K Y J C S Z L G T X H N E O B F M D Q V P U A W  

cipher : APPLE --> NPPLE --> NWPLE --> NWMLE --> NWMXE

forth, Shift key 7 shifts the shift table to the right, and then maps the table.

Original..  : A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 
shift table : D Q V P U A W R I K Y J C S Z L G T X H N E O B F M 

cipher : APPLE --> NPPLE --> NWPLE --> NWMLE --> NWMXE --> NWMXU

The resulting encrypted string is : 'APPLE' result cipher is 'NWMXU'.

I tried to use the matrix, and I tried to perform the frequency analysis after the offset calculation for 26 ^ 2 cases (676) because I thought that the shift range exceeded the rotation range of 26 is meaningless in the shift operation anyway.

However, it has never been solved easily. I would appreciate it if you could give me some advice.

Answer 1

Reminder: Analyzing schemes is off topic on crypto.SE. This question will therefore be likely to be closed soon.

Your scheme can be summarized by:
pick a S-box $\sigma$ and two keys $(k_1, k_2)$ and do:

for i in 0 .. len(message) do
  c[i] = σ(m[i])
  if i & 1:
    σ >>> k2
  else
    σ >>> k1
return c

This is broken by frequency analysis with a sufficiently long message:

• Find $n$ such that $n \times (k_1 + k_2) \equiv 0 \pmod{26}$.
• Remark that every $n \times (k_1 + k_2)$, a character you encrypted with the same key, thus frequency analysis will work.

Worth to be noted:

• this is equivalent to a alphabetic Vigenère Cipher with a long key.
• modern cryptanalysis (CPA & CCA) breaks this with a 26 chosen plaintext and 1 chosen ciphertext. See bellow.

Query messages:

AA B C D E F .. Z  

$\alpha\beta$ These will give the $\sigma$ table.
Assuming that AA is encrypted by αβ query a decryption for the ciphertext: $xαβ$ (prepend a random character). Drop the first character decrypted, the following letters will correspond to the shift distances $k_1$ and $k_2$.

In your example, the query would be:
E(AA) = NT
and
D(XNT) = YDH
leading to
D $\implies k_1 = 3$,
H $\implies k_2 = 7$.