Format Preserving Encyption question I've got a theorical question from an exercise. 
Here it is:

--- Exercise beginning ---

There are ways to convert a block cypher onto an FPE. One of them is the following: 

Let $E_{k}$ a cryptographic primitive with size n. 

$FPE_k(x)$ a cryptographic primitive with $P = C = {0,1,..., m-1} $ with $m &lt; 2^n$

The pseudo-code looks like this

fpe = x
do {
     x = fpe
     fpe = Ek(x)
} while(fpe &gt;= m)


It could be interesting to use this functions to create cupon codes. 
For example, if we consider cupons as numbers of 20 digits, we could generate 10000 cupons encoding numbers from 0 to 9999.

--- Exercise ending ---

Now my questions are:

1) I do get that encoding numbers from 0 to 9999 you get 10000 possible encodings, what I don't get is that how to you get 20 digit encodings?
As far as I understand with FPE you always get the same length so if you encode numbers from 0 to 9999 you'd get ciphers between the same values. 

2) The exercise asks what is the probability of an attacker to generate a valid cupon?
Not sure if I am correct about this, but let me give it my best.


I do get that encoding numbers from 0 to 9999 you get 10000 possible encodings, what I don't get is that how to you get 20 digit encodings? As far as I understand with FPE you always get the same length so if you encode numbers from 0 to 9999 you'd get ciphers between the same values.


It seems that the problem assumes that all numbers are written as 20-digit nature numbers. So for the number 45 you might have '00000000000000000045'. This keeps all of your numbers in the same size and format. It also means that the output space is quite large (10^20).


The exercise asks what is the probability of an attacker to generate a valid cupon?


Well, the attacker doesn't know the values of the input numbers (and the input coupon numbers don't necessarily need to be 0 through 9,999, rather, they can be any 10,000 numbers in the space. So that means that the attacker will likely have to try a random input number and then check with the server if the coupon has value. As there are 10,000 valid coupons (10^4) and a space of 10^20, we can simply divide to get 10^4/10^20. So 1/10^16 chance of hitting a valid coupon code.

Hope that answers your questions.