A data processing system is provided that includes applications, databases, encryption engines, and decryption engines. Encryption and decryption engines may be used to perform format-preserving encryption on data strings stored in a database. Applications may be used to embed information in data strings. Information may be embedded by using a character set that is larger than a character set being used by a data string. A data string may be converted into a larger character set, analogous to converting a number from a lower base to higher base. Such a conversion may shorten a data string, allowing information to be embedded as appended characters.