From 4.1 Representation of Character Strings of the NIST SP 800 38G Rev 1 draft spec that was mentioned in the comments:
The data inputs and outputs to the FF1 and FF3-1 encryption 286 and decryption functions must be finite sequences of numerals, i.e., numeral strings. If the data to be encrypted is formatted in an alphabet that is not already the set of base radix numerals, then each character must be represented by a distinct numeral in order to apply FF1 or FF3-1.
...
The choice and implementation of a one-to-one correspondence between a given alphabet and the set of base radix numerals that represents the alphabet is outside the scope of this publication.
This is not that clear yet, but very basically you need to canonically map your input data to a range [0, N), and back again during both encryption and decryption. This mapping is outside the scope, as it is of course specific to the data input specification.
If your data consists of multiple ranges then things get a bit more tricky. Very basically you first order the data (usually left to right), then you determine the base for each separate set of input ranges. Then the value in the range is created by multiplying the input range with the lower end bases.
I'll first show you how these $\text{encode}$ and $\text{decode}$ functions would work:
Let's say that the input ranges are for a digit - excluding zero - followed by a character in the uppercase ABC, i.e. [1-9][A-Z]
. The base of the digits - excluding zero - is $9$, the base of the alphabet is of course $26$.
Now let's try to calculate the value for 7Z
. If you follow these rules then the value you get is $6 \cdot 26 + 25 = 181$, where $6$ is the index of 7
in $[1, 9]$, $26$ is the base (the count of characters) in the ABC and $25$ is the index of Z
in that ABC.
To map it back, you first perform $181 \bmod 26$, which should give you $25$ again, which gives you Z
after de-indexing. Then you divide: $\big\lceil 181 / 26 \big\rceil$, and get back $6$ which is the index of 7
in the range $[1, 9]$.
Now we need to include encryption and decryption:
You can now perform FF1 or FF3 on the result, $181$ and get a different value. You can simply use the rules to encode this to your required representation.
So say that you have $\text{encode}(\text{"7Z"}) = 181$ and $\text{enc}_k(181) = 26$, then this will give you
$\text{decode}(26) = "1A"$ which you can store. Then you reverse like this: $\text{decode}(\text{dec}_k(\text{encode}(\text{"1A"}))) = "7Z"$. The encode and decode parameters are specific to [1-9][A-Z]
.
Above tricks can easily be extended to any format for which the ranges are clear, and - when coded correctly - only multiplication & addition for are needed for encoding and only divide-with-remainder is needed for decoding. The encoding/decoding should take less than a microsecond when implemented correctly (for relatively small input sizes, for which FPE is commonly used).