Brute forcing Cardan grille

Having a "rotating" square Cardan Grill with sides long n cells, how could i determinate the cost of a brute-force attack? How many configurations should be considered to perform an exhaustive search?

EDIT FOR MORE DETAIL:

This was an exam question so these are all the information given to me, but i think i can suppose that the grille has $(n^2)/4$ holes, the plaintext has $n^2$ letters, letters are not visible in more than one orientation and the grille have to be rotated 4 times.

-

An obvious upper bound is $2^{n^2}$, but it's hard to say anything more specific without knowing more details about the system. For example, do you know how many holes the grille has? And may a given letter in the message be visible through the grille in more than one orientation? (If yes, that means you have to strike out letters you've already used when decoding a message.) – Ilmari Karonen Apr 10 '12 at 22:53
Please provide more details (rotating, parameters, etc.). – Iceberg Hotspot Apr 11 '12 at 4:38
thanks for the comment. I added more details, hoping that they are useful. – dciriello Apr 11 '12 at 6:56

1 Answer

With the extra information you've provided, there are $4^{\left\lfloor \frac{n^2}{4} \right\rfloor}$ possible grilles to consider.

Specifically, consider an $n \times n$ grille with just one hole, and make a mark on the paper through that hole with the grille in each orientation. If you do that, you'll see that there will always be exactly four marked positions on the paper, placed symmetrically around the center (unless $n$ is odd and the hole is in the middle of the grille, in which case all marks will be in the same position).

Clearly, with the grille in its original orientation, exactly one of these four positions must have a hole: if two or more of them had holes, the same letters would show through all of them, and if none of them had holes, the letters in those positions would not be visible in any orientation (contradicting the claim that the plaintext has $n^2$ letters).

(Incidentally, if the requirement that no letters are visible in more than one orientation is taken strictly, it means that the center position cannot have a hole for odd $n$, meaning that the plaintext length for odd $n$ can be at most $n^2-1$. So we must either relax one of the requirements or rule out odd $n$.)

Each grille has $n^2$ positions (including the center position for odd $n$) and thus $\left\lfloor \frac{n^2}{4} \right\rfloor$ of these 4-position cycles. (The floor is there for odd $n$; if $n$ in even, $n^2$ is divisible by 4.) Assuming maximal plaintext length, each of these cycles must contain a hole (and, as shown above, cannot contain more than one hole).

By symmetry, each of these holes can be in any of the four positions within their respective cycle. Thus, we have $\left\lfloor \frac{n^2}{4} \right\rfloor$ independent choices, with four options for each choices, giving us a total of $4^{\left\lfloor \frac{n^2}{4} \right\rfloor}$ possible sets of choices.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 19, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9367585778236389, "perplexity_flag": "middle"}