1
$\begingroup$

Basically, I need to find the probability that DES(p, k1) = DES(p, k2) = c

My guess is that probability = 1 / 2^64 since that's the total number of possible outputs, but honestly I have no clue about crypto. Thanks in advance for any help!

$\endgroup$
1
  • $\begingroup$ Welcome to Cryptography. Could you provide the origin of this question? $\endgroup$
    – kelalaka
    Oct 28, 2022 at 10:21

2 Answers 2

4
$\begingroup$

It depends on what you mean. There are $2^{56}$ different DES keys and so if $k_1$ and $k_2$ are both chosen uniformly and independently at random, then there is a $2^{-56}$ chance that they are the same key in which case $\mathrm{DES}(p,k_1)=\mathrm{DES}(p,k_2)$ independently of the choice of $p$. (With non-causal cases being a second-order effect).

If on the other hand $k_1$ and $k_2$ are distinct and $p$ is chosen uniformly at random then @kodlu's analysis holds.

However, if we choose distinct $k_1$ and $k_2$ then ask for the probability that there exists some $p$ such that $\mathrm{DES}(p,k_1)=\mathrm{DES}(p,k_2)$ is the probability that $\pi_{k_1}^{-1}(\pi_{k_2}(x))$ is not a derangement which is roughly $(1-1/e)$ (assuming that the DES operation is indistinguishable from a random permutation).

$\endgroup$
3
$\begingroup$

Let $DES(p,k)$ be modeled by the pseudorandom permutation $\pi_{k}:\{0,1\}^{64}\rightarrow \{0,1\}^{64}.$ Then $$ DES(p,k_1)=DES(p,k_2) \Leftrightarrow \pi_{k_2}^{-1}(\pi_{k_1}(p))=p. $$ Since $\pi_{k_2}^{-1}(\pi_{k_1}(\cdot))$ is itself a pseudorandom permutation. The probability that a given point $p$ is fixed by this permutation is $1/2^{64}$ which is the ratio $(n-1)!/n!$ with $n=2^{64}$ since there are $(n-1)!$ permutations on $n$ points which fix a given point.

$\endgroup$

Your Answer

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

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