2
$\begingroup$

Monoalphabetic substitution cipher consists of applying a one letter shift in each letter of plain text. So if $p = p_1 \ldots p_r$ is plain text then encrypted text is $e = q_1 \ldots q_r$ where each $q_i = p_i + k$ where $k$ is the key (the shift). This cipher is vulnerable using freqüency letters in alphabet.

The Vigenère cipher improves that using a multiletter key. Now the key is $k = k_1 \ldots k_s$ and each symbol of encrypted text is $q_i = p_i + k_i$. According to "Introduction to Modern Cryptography" by Katz and Lindell, this is vulnerable by Kasiski's method.

My question is if Kasiski's method or any other method make this vulnerable if we extend the Vigenère cipher to another cipher with any function $f$ which add to $q_i$. That is. $q_i = p_i + f(i)$. [Shift cipher has $f$ constant ($f(i) = k$) and Vigenère has $f$ periodic.]

Do you have references where I could find some information about this

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I don't know if I had to post this entry in Crypto because it's about cryptography but I need academic references. $\endgroup$
    – somenxavier
    Commented Jul 29, 2020 at 17:40

1 Answer 1

Reset to default
6
$\begingroup$

Suppose that I create a list of intgers $(a_1,a_2,a_3,\dots)$, where the $0\le a_i<26$ are chosen randomly, e.g., using quantum effects or micro-temperature changes. Then I share the list with you, and we use it for the cipher you've explained, setting $f(i)=a_i$. The net effect is that we're using a one-time pad, so that's secure. On the other hand, the function $f(i)=0$ is obviously quite insecure! So your question is really more about what functions can be detected via statistical analysis of transcripts, and as such, is probably too broad to have a satisfactory answer.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Can you give me some references about that "The net effect is that we're using a one-time pad, so that's secure"? $\endgroup$
    – somenxavier
    Commented Jul 30, 2020 at 9:27
  • $\begingroup$ For being concrete, what about quadratic function: $f(x) = ax^2 + bx + c$ $\endgroup$
    – somenxavier
    Commented Jul 30, 2020 at 9:28
  • 2
    $\begingroup$ I don't know a reference, but isn't it obvious that it's a one-time pad? If you replace $\mathbb Z/26\mathbb Z$ with $\mathbb Z/2\mathbb Z$, then you get exactly the usual one-time pad where each bit of the message is XOR'd with the corresponding bit of the random list of bits. As for the concrete example that $f$ is an unknown quadratic polynomial, that's a great question, but comes back down to a Vigenere, since the sequence $\{f(i)\bmod26:i\ge1\}$ is eventually periodic. It's an example of a dynamical system over $\mathbb Z/26\mathbb Z$. So some version of Kasiski should work. $\endgroup$
    – Joe Silverman
    Commented Jul 30, 2020 at 10:30
  • $\begingroup$ OK. I have an educated guess: if $f$ is eventually non-periodic, then cipher is not vulnerable to Kasiski's method or frequency analysis. Eg. decimal expansion of $\sqrt{p}$ with base 26 where $p$ is prime. $\endgroup$
    – somenxavier
    Commented Jul 30, 2020 at 21:29
  • 1
    $\begingroup$ Sounds reasonable, although since $p$ is your secret key, it would need to be quite large. And probably you'd want to take the part of the base 26 expansion starting after the decimal point, i.e., the expansion of the $\sqrt{p}-\lfloor\sqrt p\rfloor$. $\endgroup$
    – Joe Silverman
    Commented Jul 30, 2020 at 22:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .