# Questions tagged [permutation]

A way, esp. one of several possible variations, in which a set or number of things can be ordered or arranged.

145 questions
Filter by
Sorted by
Tagged with
55 views

### Test the randomness of a random permutations, that was generated without Fisher-Yates?

Overview of the problem Before this gets immediately flagged as duplicate, I'm not interested in testing the Fisher-Yates shuffle for randomness, since this can simply be done by testing the ...
534 views

### How strong is XooDoo vs AES?

What is Gimli, and how does XooDoo compare to symmetric ciphers such as AES or ChaCha? I am looking at this library, called charm. Interesting paper here. I also ...
86 views

### How can I determine the number of times I have to reapply the Scytale until the original plaintext comes back?

Given "①②③④⑤⑥⑦⑧⑨⑩⑪⑫" as plain text and a 4 rows Scytale inscription with 3 as the length of the longest row, the original plaintext is back after 5 runs: ①④⑦⑩②⑤⑧⑪③⑥⑨⑫ ①⑩⑧⑥④②⑪⑨⑦⑤③⑫ ①⑥⑪⑤⑩④⑨③⑧②⑦...
81 views

### How should I assign a letter at random to another?

For my first ever project in Python, I wanted to code a cipher to encrypt simple messages ( no spaces or lower case to avoid that extra hassle for now ). My idea was to either: Choose a letter of ...
16 views

### calculating the branch number/ active bundles of a cipher

I have read the papers Wide Trail Strategy and Wide Trail Design Strategy for Binary MixColumns. These papers describe the need for a good linear transformation in a cipher, a provable mechanism to ...
108 views

50 views

### collision resistance with added permutation

Suppose we have an $n$ bit ciphertext $c$ protected by a $k$ bit $MAC$, with $k < n$. Generally, we expect collisions after $O(2^{k/2})$ ciphertext/MAC pairs are seen. Consider the following ...
244 views

### Is this permutation secure?

Let vector ${\bf d} \in \{ \pm 1 \}^n$ be the message we want to send. In my system, ${\bf d}$ is multiplied by an $n \times n$ Fourier matrix ${\bf F}$, as follows $${\bf x} = {\bf F} {\bf d}$$ ...
61 views

### Proving that RSA encryption function with non-square free modulus is not a permutation

Here is a backgroung for the question on hand. While studying RSA I came up to the question about what happens if $p$ and $q$ involved in modulus computation are not actually primes? There is already ...
55 views

### Shuffling: Purpose and formal definition

To my understanding, shuffling means simply to permute the elements in vector $\mathbf{v}$ pseudorandomly, using a PRP $\pi (\mathrm{seed},\mathbf{v})$. A secure PRP should yield a permutation ...
72 views

### One way permutation and its inverse

Is the following statement correct? Let $F$ be a OWP. Then the inverse $F^{-1}$ of $F$ is also a OWP.
72 views

### Provably secure way of expanding permutations

Gimli is a 384-bit permutation that makes use of an internal 96-bit permutation which works on columns. Every 4 rounds starting from the 1st a "small swap" is performed and every 4 rounds ...
884 views

### Proving RSA is a permutation

I am trying to prove that RSA is a permutation. All I can find is places where it is stated that it is a permutation because the function is bijective. I know that it is, but would like to see a ...
283 views

### Permutation for which an inverse is a hard problem

Is it possible to construct (even if we don't know how) a permutation for which an inverse must exist but is difficult to find (brute force required)? The one way permutation contains no hidden ...
131 views

### What is different between a hash function and permutations with repeats

Are secure hash function outputs different from permutation sets of the same length and value? If yes please explain how they appear differently. For example, MD5 would produce ...
56 views

### Is it possible to compute permutations of a sequence of bytes by using exactly one pseudo-random number?

Suppose I have a certain sequence of bytes, for example 0102F4829hex, and I can pick from a pseudo-random number generator exactly one number. Is it possible, by using exactly one pseudo-random number ...
56 views

### An insecure signature with message recovery, Dan Boneh

Someone can help me to resolve this questions from the book of Dan Boneh (University of Standford)
164 views

### If you iterate a cryptographic permutation long enough will you map the input to itself?

Given a cryptographic permutation $\{0,1\}^n \rightarrow \{0,1\}^n$ does it follow that after some number of iterations you must eventually map the input to itself?
64 views

### Permutation of first $k$ prime powers as a one-way function?

Let $a_1$ through $a_k$ be some permutation of the first $k$ primes. Let $n \in [1,k!]$ be a parameter specifying the exact ordering by taking the $n$th permutation in a sorted list or by some other ...
81 views

### Is there an efficient algorithm that allows to obtain a uniform distribution of all possible $4$-bit permutations from a single keyless $4$-bit S-Box?

Let $S$ denote a keyless permutation that operates on $4$-bit inputs and returns $4$-bit outputs (that is, $S$ is a $4$-bit S-Box). In this question, $x_0$ denotes an arbitrary bitstring that ends ...
192 views

### Is there a method to encrypt relations in between values of a cyclic value set and generate values out of this set with pseudo RNG? (all at user PC)

Is there a pseudo RNG and function $f$ with 1.) The RNG produces a value $v_0$ out of $N$ different values (set $S$). 2.) Independent of the RNG the function $f$ generates $v_{i+1}=f(v_i)$ ...
177 views

### Sponge with PRF instead of PRP

In most uses of Sponge mode of operations such as SHA3 and many of the round-2 candidates in the NIST lightweight cryptography project, the underlaying primitive is a cryptographic permutation - that ...
93 views

### Iterated AES encryption under a fixed key

Is it right that repeated AES encryption under the same key will eventually lead back to the original plaintext? The reasoning is that AES acts like a reversible permutation of the blocks, the ...
76 views

### memory-hard KDF that's just a giant permutation?

Why aren't there memory-hard KDF functions that simply build a 1GB permutation and permute it? Then hash the 1GB result. For example, use a hash function (unfixed output mode) on the key+salt and use ...
2k views

### How to check whether the permutation is random or not

Imagine that my friend gives me the permutation $\pi$. He pretends that the permutation was generated completely random. I'm suspicious and worried, because the permutation (for instance) looks like: ...
234 views

### modified substitution permutation networks

I have a model of substitution permutation networks, modified as follows: instead of iterating $n$ times a round(each of which is composed of the key mixing phase, substitution S-BOX) and ...
62 views

### Question about the definition of Associative Pseudorandom Permutation [closed]

In question about associative pseudo-random permutation the definition uses: $f(k_1, f(k_2, m)) = f(f(k_1, k_2), m)$ What is defined by that? No luck with google so far. As far as I know a ...
285 views

### How are the four 8-bit permutation tables of Present cipher calculated?

the fast implementation of present cipher for 8-bit register uses four 8-bit lookups tables for permutation. Table 3 & 2 are : ...
104 views

### What is the intuition behind the strength of unstructured symmetric cryptography?

Consider a single round of a cryptographic permutation, what is so special about it that lacking some bits of information that either get mixed into it as a subkey or omitted at the end (sponge ...
1k views

### No of keys used in Triple DES Algorithm

I am studying Triple DES. I have got two basic questions. One, why are we following a sequence like encrypt(decrypt(encrypt)); what is the problem using a sequence encrypt(encrypt(encrypt))? Second,...
446 views

### Randomness Testing

Let say I have three sequences: S1 = {1,2,3,4,5,6,7,8,9,10} S2 = {3,7,1,9,4,10,5,8,6,2} S3 = {8,3,10,2,6,7,1,5,9,4} i.e. S2 and S3 are just the permutations of S1. Is there any method to check how ...
103 views

### From the product of two permutation matrices raised to the same power, is it easy to find the power?

Let $A$ and $B$ be two public permutation matrices. If $r$ is a secret power of large number, can we easily find $r$ from $A^rB^r$?
137 views

### Is Permutation conjugate problem hard?

Let $x$,$y$,$z$ be permutations. Then public key is $z=xyx^{−1}$ and $y$. Is permutation conjugate search problem easy? if yes, how to find $x$ from $z$ and $y$? Let be a is Alice's secret key as ...
157 views

### What can be said about the self-power map on groups based on DLP?

Introduction I've been playing with group representation theory some time, concretely representing groups as permutation groups (Cayley's theorem), where the group $G$ has an embedding into the ...
59 views

### AES: Why ShiftRows() before MixColumns()? [duplicate]

In above picture you can see a AES state array over 2 rounds through the S- and P-Boxes of AES. It's taken from here and intends to show how 2 rounds of transformation are necessary to achieve full ...
91 views

### Is a random permutation “hiding”?

Let's say I tell you $G: \mathbb{F} \rightarrow \mathbb{F}$ is a random permutation (some finite field). Does that mean: $G$ is one-way, so that if I give you $G(x)$, it is infeasible to determine ...
45 views

### Proving at most one affine permutation mapping $x$ to $u$ and $y$ to $v$ with $x,y \in \mathbb{Z}_n$ and $\gcd(x−y,n) = 1$

Suppose that $x,y \in \mathbb{Z}_n$ with $\gcd(x−y,n) = 1$. Prove that for any $u,v \in \mathbb{Z}_n$ there is at most one affine permutation mapping $x$ to $u$ and $y$ to $v$.
806 views

### Number of combinations required to brute force

I am trying to encrypt a password in a program. Here is the process: Let us assume that I have a string $p$ ($n$ characters long) which contains the password. Now the program reverse the string and ...
5k views

### DES: How to find the Inverse of the Initial Permutation?

I am doing a DES problem by hand and I want to know how you calculate the inverse of the initial permutation. I know what the permutation is, but how do you find it based off the given initial ...
802 views

### DES: how does Richard Outerbridge's Initial Permutation operate?

I know how initial permutation works, but I've never heard of this part. People say it's Richard Outerbridge's initial permutation and that it's faster than usual IP (initial permutation) and simple. ...
Question: If a cipher’s key size is $k$ bits and its block size is $b$ bits, how many possible keys are there, how many possible plaintext blocks are there, and how many possible ciphertext blocks are ...