We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [permutation]

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

Filter by
Sorted by
Tagged with
1
vote
2answers
131 views

Total password count, given length and pool size

First, if my password is exactly 8 characters long, derived from a pool of 95 characters, then is the total amount of passwords I can create simply $95^8$ ...
2
votes
1answer
635 views

Pseudo-random permutation of a range

I have this set: {0,1,2,3,...,15}. I would like to create a pseudo-random permutation from elements of this set, for example ...
0
votes
1answer
104 views

Can a random permutation be restored / decrypted?

Say you have a 1,000,000 random bytes file and you split it into 1000 x (1000 bytes) pieces. You then pick two random pieces and swap them writing down the position of the pieces (eg. swapped piece ...
3
votes
1answer
153 views

How to generate a permutation of n numbers using secret sharing scheme?

Consider $n$ parties having their private inputs $s_1,\cdots,s_n$. How can they compute a public function $f(s_1,\cdots,s_n)= \pi$, where $\pi$ is a permutation of numbers between $1,\cdots,n$, using ...
4
votes
1answer
139 views

Mathematical structure for Sbox

Recently, when I studied the permutation cipher, I saw a matrices structure which is same as permutation cipher. This method was so simple and interesting for me. Let $m$ be $n$-bit plain text and $P=...
2
votes
2answers
578 views

Apply a permutation cipher by hand

I did the following problem from the book "Cryptography Theory and Practice" as I am doing some self-study. Problem: a) Suppose that $\pi$ is the following permutations of the set $\lbrace 1,\dots,8 ...
1
vote
1answer
296 views

What is the importance of $f_k$ in a feistel network being a permutation

I was doing some cryptography exercises, one of which was an example of a feistel network. It said that the function $f_k$ was a permutation for all k but didn't explain why that makes a difference. ...
1
vote
1answer
585 views

substitution-permutation network construction

I want to understand more about substitution-permutation network, if we modify it instead of carrying out the key-mixing, substitution, and permutation steps in alternating order for r rounds, the ...
2
votes
1answer
534 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 ...
4
votes
2answers
12k views

How to solve Columnar Transposition Cipher without a key

I have been given a 77 character message for decryption, but no matter where I look all the Columnar Transposition scripts out there are all requiring of a key. I believe the number of columns to be 7,...
1
vote
1answer
85 views

Permutations coming from RSA

The RSA algorithm can be used to generate a permutation. Given two prime numbers $p$ and $q$, the key length is $n=pq$. If $a$ is the private key, then $b$ is the public key, where $ab \equiv 1 \...
2
votes
1answer
164 views

Inverse single element permutations

Let's say we have a set of ordered elements $D=[x_1,x_2,x_3,x_4,x_5]$. We apply a random permutation on them with a $PRP=P_k: P_k(D)=D'=[x_3,x_2,x_5,x_1,x_4]$ My question is: can the owner of the key ...
6
votes
2answers
602 views

Can we exchange the permutation of a sponge construction?

Part of a sponge construction (like SHA3 uses) is a fixed permutation $p$; which is clearly not one-way. Could we, theoretically, exchange the permutation $p$ with any other permutation? What basic ...
4
votes
1answer
127 views

Using a round function intended for an SP network in a Feistel network?

If I use the round function from a secure SP network (such as AES) and use it in a Feistel netwok, is this a good starting point for the second cipher? My thought is "yes" because: it already has ...
3
votes
1answer
631 views

How does Feistel cipher create diffusion between blocks?

From what I've read about Feistel ciphers, I can understand that within each block, there is both confusion and diffusion. But it is unclear to me how a Feistel cipher permutates among blocks of data. ...
1
vote
1answer
504 views

Differences between OWP and OWF and their IND-CPA security

I am learning about one way permutations and one way functions and am not sure of the differences if there are any. Also in the random oracle model are they both IND-CPA secure?
13
votes
4answers
3k views

Why is the permutation in AES (and other ciphers) not random or key-dependent?

If the permutation in AES (or other ciphers) were randomly generated or dependent on the key, would it not be stronger against differential attacks? If this is so, then might we need fewer rounds for ...
0
votes
0answers
119 views

Permuted Hash Table

Suppose we have a hash table, $HT$, consisting of $100$ bins.The hash table uses a hash function $H$ that is public. We all know that given value $a$ we can compute the address in the hash by $H(a)=j$...
3
votes
1answer
508 views

How do substution-permutation networks work?

I understand what's going on in higher level. But i don't understand what's really going on in page 3 and 4 of this slide. Specifically, How S0 and S1 is used? What goes in what goes out? How ...
0
votes
0answers
56 views

When we use permutation and random long sting to hide a message

This question is modified version of this: Can we use merely permutation to hide a message? I have an English name $m=m_1 || m_2 ||..||m_{30}$. I pick a random string $d=d_1 ||..||d_{70}$ I mix ...
-1
votes
1answer
105 views

Can we use merely permutation to hide a message?

This question is related to this: When all shares of a secret are given to adversary as a permuted matrix I think the below question is a simplified version of that. Assume we have a 40-bit ...
4
votes
1answer
212 views

When all shares of a secret are given to adversary as a permuted matrix

Suppose we have a secret $\sigma$. The secret comes from a universe in which the elements are not necessarily distributed uniformly. We split $\sigma$ into $n$ shares $[\sigma_1,...,\sigma_n]$ (...
3
votes
1answer
365 views

Periodic One Way Function

Is there any notion of a periodic OWF? I.e. an OWF $f$ that on every input $x$ in its domain it holds that $f(f(f\ldots f(x))\ldots )=x$ when $f$ applied many times, each time on the previous output....
2
votes
1answer
281 views

Provable security of cryptographic hash functions

I am working on the following exercise question: Consider the following construction of a “keyed” hash function from Katz & Lindell (ex. 7.22 (1st ed.)/ 8.21(2nd ed.)). Gen : On input $1^n$...
3
votes
2answers
4k 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 ...
10
votes
1answer
360 views

Santa Claus' secret permutation

This December, $N$ friends play secret santa: they select a random permutation $\sigma$ of $N$ (without fixed point). For Santa Claus, everyone has to bring a gift to the next person in the ...
3
votes
1answer
88 views

Permuting Small Sized Set in Practice

Imagine we have a set $S$ of $m$ elements and we wants to permutes the set elements. Thus the original position of each element should be unknown after permuting. If we define a permutation function ...
2
votes
0answers
141 views

Does the encryption algorithm DES perform random permutations? If so how is information not lost?

Before round 1 begins, all 64 bits of an incoming message and all 56 bits of the secret key are separately permuted (shuffled) My question is this : Is the shuffling of the bits performed randomly? ...
1
vote
2answers
127 views

Negilible Function $\frac{1}{n!}$

Is $\frac{1}{n!}$ a negligible function where $n$ is a security parameter? Application: I have a vector of n>100 elements. I permute it and give it to an adversary. The adversary can break it if it ...
2
votes
1answer
168 views

Permuted vectors

Consider we have two vectors $v_1, v_2$ of size $n$, and each vector contains $n$ elements. We permute the vectors as: $\pi (k_1,v_1), \pi (k_2,v_2)$. Where $\pi (k_i,v)$ denotes a permutation of a ...
1
vote
1answer
394 views

Why is a Feistel network not a type of substitution-permutation network?

I understand what substitution-permutation networks look like. I understand what Feistel networks and Feistel-like networks look like. A Feistel network or a Feistel-like network features substitution ...
1
vote
0answers
148 views

common ways / methods to try to break a SP network

I have a very little cryptography background (but a relatively solid maths background) so my below question is very general. Basically I have been given a SP network with an output to reverse. I ...
0
votes
1answer
90 views

One-one correspondance complete function

I am reading the paper by John B. Kam and Georges I. Davida (1979) titled Structured Design of Substitution-Permutation Encryption Networks. On page 749 it reads ...
2
votes
0answers
101 views

Permutation parity after cycle-walking

Let $E$ be a random even permutation of the set $\{0\dots n-1\}$. We construct a permutation $P$ of the set $\{0\dots m-1\}$, for some $m\le n$, using cycle-walking; that is, computing $P(x)$ is as ...
2
votes
1answer
209 views

Random Permutation polynomial

I need to know, please: (1) Is there anyway to pick uniformly at random permutation polynomial in a field of prime order? (2) Are there many permutation polynomials in a field? (3) In a finite ...
1
vote
1answer
231 views

Is AES's parity key-dependent?

Is the parity of the permutation of the set $\{0,1\}^{128}$, defined by AES encryption for a certain fixed key, dependent on this key? DES, and any pure Feistel cipher, has even parity for any key. ...
4
votes
1answer
505 views

How secure is bit level permutation?

Could anyone explain how secure is bit level permutation? What is the most serious threat against the security of this kind of cipher?
1
vote
1answer
2k views

What benefits do substitution boxes and permutation boxes offer in DES?

I understand that with more encryption rounds the more complex the ciphertext becomes due to multiple substitutions and permutations. What I don't understand is the purpose of these features. I am ...
1
vote
0answers
90 views

Forward pseudorandom permutation [closed]

Please consider the following scenario: The user A and B use their keys, K1 and K2 respectively. Each client have a vector of elements. Each client separately permutes his vector using his key and ...
18
votes
2answers
6k views

Shannon confusion and diffusion concept

I read the document(not the whole document) from Shannon where he speaks about the concepts of confusion and diffusion. I read in many places(not in the document but around the internet) that ...
5
votes
1answer
671 views

Is it possible to generate a secure permutation F over 32-bit integers even if F(0) … F(n) is public knowledge?

I'm currently interested in the problem of generating random-looking URLs from sequential database IDs, like how they do it in link shorteners. One way to do this is to encrypt the sequential database ...
3
votes
1answer
612 views

Simple proof that shows AES is not a uniform permutation on any n-bit string?

Is there a simple proof that shows AES is not a uniform permutation on any $n$-bit string? Since I'm just starting with crypto, I'd like to see a simple yet elegant proof for the said property. ...
3
votes
1answer
590 views

Revealing random bit permutation

I am new in cryptography. I want to determine the complexity of revealing a random bit permutation which is used as block cipher for plaintexts (bitstrings of length n). An adversary catches different ...
1
vote
2answers
533 views

Correct way to read a given permutation cipher?

In some literature I am reading – where they are explaining the permutation cipher – they have two examples, which encrypt a small block of text. But they seem to contradict each other: First ...
2
votes
1answer
554 views

Security of permutation cipher

I would like to understand how secure the permutation cipher is. I would specifically like to understand the following concrete setup: If the alphabet is $L = \{0,1,\dots , 255\}$ and $\sigma_1, \...
9
votes
1answer
1k views

Block cipher and parity of permutation

Can anyone explain the following text passage to me? Most real-world block ciphers build even permutations, because it's hard to build odd ones using small operations (32 bit) on larger (128 ...
3
votes
1answer
357 views

derangements and permutations in cryptography

Given a partial key for a mono-alphabetic substitution cipher (missing 11 letters), calculate the number $N$ of possible keys, given that no plaintext letter can be mapped to itself. Ordinarily, ...
1
vote
1answer
724 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,...
0
votes
3answers
346 views

Question on RSA trapdoor permutation

You plan to use a public-key cryptosystem based on the RSA trapdoor permutation in three different real-life applications, in which the attacker has, respectively, only one of the following resources: ...
5
votes
4answers
667 views

Get permutations from password

Are there any "good" ways to get a permutation from a password/pass-phrase? If one, for example, wanted to get a permutation of letters from a password, how might one do that in a smart way? I would ...