Assume that source elements of length k are mapped in some uniform fashion into
ID: 3628182 • Letter: A
Question
Assume that source elements of length k are mapped in some uniform fashion into a target elements of length p. If each digit can take on one of r values, then the number of source elements is rk and the number of target elements is the smaller number rp. A particular source element xi is mapped to a particular target element yj.
a. What is the probability that the correct source element can be selected by an adversary on one try?
b. What is the probability that a different source element xk ( xi xk) that results in the same target element, yj, could be produced by an adversary?
c. What is the probability that the correct target element can be produced by an adversary on one try?
Explanation / Answer
Length of source elements=k<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />
Length of target elements=p
Number of source elements is rk
Number of target elements is rp
a) Probability that the correct source element can be selected by an adversary on one try is 1/rk
b) Each element in the rp target elements can be mapped to by rk/rp = rk-p target elements.
Number of target elements is rk-p
Number of source elements is rk-p-1
Probability of selecting on of these is (rk-p-1)/rk.
c) Probability that the correct target element can be produced by an adversary on one try is 1/rp