1
$\begingroup$

On page 181 of Handbook of Applied Cryptography Chapter Five, it states the following:

The purpose of this test is to determine whether the number of occurrences of 00, 01, 10, and 11 as subsequences of s are approximately the same, as would be expected for a random sequence. Let $n_0$, $n_1$ denote the number of 0’s and 1’s in s, respectively, and let $n_{00}$,$n_{01}$,$n_{10}$,$n_{11}$ denote the number of occurrences of 00, 01, 10, 11 in s, respectively. Note that $n_{00} + n_{01} + n_{10} + n_{11} = (n − 1)$ since the subsequences are allowed to overlap. The statistic used is $$ X_2 = \frac{4}{n-1}(n_{00}^2+n_{01}^2+n_{10}^2+n_{11}^2)-\frac2n (n_0^2 +n_1^2) +1$$

Where does this statistic come from? I'm not entirely sure, and the book doesn't explain it's derivation. Normally, $ X=\frac{(Z-\mu)^2}{n^2}$ for Chi-Squared test ( if i recall correctly), but I don't see how this can result in the expression above. For each $n_{ij}$, the approximate value is $\frac{n_i+n_j-1}{4}$, and the expected value would be $\frac{n_i+n_j}2$, but how do we combine them in such a way that we get the expression for $X_2$?

If this belongs in Math, rather than Cryptography, I can happily delete and move it. I just figured since the question is cryptography related, it may receive better attention here.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

This is an interesting question. According to page 3-18 of available at NIST here it is a common mistake to think the variance statistic is a traditional chi squared statistic. It is not, due to dependence of the overlapping length 2 windows, so a differential statistic is used.

This statistic has been shown to converge to chi squared by I.J. Good, see the reference on the following page of the linked document, who was involved in the enigma decryption effort with Turing. Thus one must take at least a bitstring of 21 bits.

Here is the discussion

enter image description here

Improve this answer
$\endgroup$
7
  • $\begingroup$ May I inquire, what is the significance of $\frac{\text{Number of Possible Combinations of m-bits}}{\text{Total number of bits}}=\frac{2^m}n$? I would have expected it to be $\frac{2^m}{2^n}=2^{m-n}$, which combinatorics wise, would be the expected frequency? $\endgroup$
    – Shinaolord
    Apr 10, 2019 at 4:26
  • $\begingroup$ expected frequency of all $m$ bit patterns* $\endgroup$
    – Shinaolord
    Apr 10, 2019 at 4:32
  • $\begingroup$ Since there are $2^m$ $m-$ bit patterns but output string length is $n$, there are $n$ positions for the patterns to start (taken cyclically). If it wasn't cyclic it would have been $n-1$ starting position. $\endgroup$
    – kodlu
    Apr 10, 2019 at 5:06
  • $\begingroup$ So we divide $2^m$ by $n$, because for each $m$-bit pattern, it has a $\frac1n$ chance of starting at each position in the original string? $\endgroup$
    – Shinaolord
    Apr 10, 2019 at 5:07
  • $\begingroup$ yes that is correct $\endgroup$
    – kodlu
    Apr 10, 2019 at 5:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.