3
$\begingroup$

Is it possible to use FPE to encrypt names and language words like 'Bob' 'the' 'tree', in order to preserve both length and format (like keeping characters within a certain range like A-Z a-z)

The only way I can think of at the moment is to reduce each character to it's decimal value and encrypt that. But that doesn't seem very secure (wouldn't each character map to exactly the same value each time?)

$\endgroup$
3
$\begingroup$

The obvious way to FPE strings of $N$ characters of [A-Za-z] is to treat the string as a base-52 value (with each character being a digit, say, A=0, B=1, ..., y=50, z=51); do a base conversion of that to an integer between 0 and $52^N-1$; use a standard FPE technique to encrypt that value into another integer between 0 and $52^N-1$, and do a base conversion back into a string of $N$ characters of [A-Za-z].

Because you're encrypting the string as a whole, you don't have the data leakage you would have if you encrypted each character individually.

$\endgroup$
  • 1
    $\begingroup$ Exactly. The formal name for this construction is rank-then-encipher, and was first treated in Bellare et al.'s paper on the subject: link $\endgroup$ – pg1989 Mar 2 '15 at 19:52
  • 1
    $\begingroup$ Interestingly, this technique can be extended to build permutations over regular languages and context-free grammars: link $\endgroup$ – pg1989 Mar 2 '15 at 19:54
  • $\begingroup$ I'm not sure I see how this is better, it seems like you are encrypting each character individually anyway, just as an integer. $\endgroup$ – erotavlas Apr 29 '15 at 20:08
  • 1
    $\begingroup$ @erotavlas: nope. Consider the case where we encrypt the strings "ABC" and "ABD". "ABC" is translated into the integer 54, while "ABD" is translated into the integer 55. Those integers are both encrypted as integers between 0 and 140607 (and the mapping acts as if were chosen randomly); 54 might encrypt as 31415, while 55 might encrypt as 27182. So, 31415 would translate back into "LgH", while 27182 would translate into "KCm". So, by changing one character, all three characters of the ciphertext are affected. $\endgroup$ – poncho Apr 29 '15 at 20:14
  • 1
    $\begingroup$ @erotavlas: review en.wikipedia.org/wiki/Positional_notation ; this is base-52 $\endgroup$ – poncho Apr 29 '15 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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