# Tag Info

7

Most encryption algorithm use a specific number of the same (or similar) group of operations. As example, AES consists of 4 different operations: SubBytes, ShiftRows, MixColumns and AddRoundKey. AES-128 (AES with a key of 128 bits) uses all this operations 10 times in 10 rounds. Well, not exactly. The last round doesn't have the MixColumns step. It would add ...

2

This answer addresses Cases 1 and 2 from the question to provide a baseline, leaving Case 3 (which is the one I'm most interested in), unresolved. Case 1, Zero Increment In this case we'll consider a simple Lehmer-style LCG (a.k.a. an MCG), with a seed $s_1$, multiplier $a$ and $b$ bits of state and $r$ bits returned. The modulus $M = 2^b$, and the ...

2

The rotational cryptanalysis considers applying the transformation $E$ to both $X$ and $\overrightarrow{X}$, where $$\overrightarrow{(x_1, x_2,x_3,\ldots, x_n)} = (x_{r+1},x_{r+2},\ldots, x_n, x_1,\ldots, x_r)$$ for some integer $r$. You know that $\overrightarrow{X} \oplus \overrightarrow{Y} = \overrightarrow{X\oplus Y}$ always, and  \overrightarrow{X} ...

1

What you are describing is One-Time-Pad encryption, and yes it does have perfect secrecy. Note that for any ciphertext $y$ there is exactly one key $k'$ for each possible plaintext $x'$ so that $E_k(x') = y$. So if you choose the key uniformly at random the ciphertext gives no information on the plaintext, because any plaintext is equally likely.

1

So we have $k+1$ matrices $M_0, M_1, \ldots, M_k \in \mathbb{K}^{n\times{}n}$. We are trying to find weights $\mu_1, \dots, \mu_k$ such that the rank of the weighted sum of matrices is smaller than or equal to some target rank: $\mathsf{rank}(-M_0 + \sum_{i=1}^k\mu_iM_i) \leq r$. The Courtois and Goubin strategy is to select $m$ random vectors ...

1

The set of bijections from the set of words over an alphabet to itself is countable, therefore it is possible to guess the correct cipher in finite time. But you can never be sure you found the right one, since you can "decrypt" literally any plaintext from a given ciphertext without further constraints.

1

Putting some of my comments into writing. This is less than an answer but too much for a comment. In the comments I had claimed to apply SMT to solve case 1 - this is false, I was mistaken. I have had cases 2 and 3 running SMT (boolector, Z3, CVC4, yices) for some time without success. The closest thing to success is the identification of seeds that ...

1

This is a work-in-progress, mostly trying to address Case 3 in the question, since the problem of Case 2 is dealt with in another answer, and has been thoroughly researched: Jacques Stern: Secret linear congruential generators are not cryptographically secure, in proceedings of the 28th Annual Symposium on the Foundations of Computer Science, 1987 (try a ...

Only top voted, non community-wiki answers of a minimum length are eligible