Continued fraction cryptography

Every rational number can be expanded into a continued fraction with positive integer coefficients. And the process can be reversed: given a sequence of positive integers, you can make them the coefficients in a continued fraction and reduce it to a simple fraction.

In 1954, Arthur Porges published a one-page article pointing out that continued fractions could be used to create a cipher. To encrypt your cleartext, convert it to a list of integers, use them as continued fraction coefficients, and report the resulting fraction. To decrypt, expand the fraction into a continued fraction and convert the coefficients back to text.

We can implement this in Mathematica as follows:

    
encode[text_] := FromContinuedFraction[ ToCharacterCode[ text ]]
decode[frac_] := FromCharacterCode[ ContinuedFraction[ frac ]]

So, for example, suppose we want to encrypt “adobe.” If we convert each letter to its ASCII code we get {97, 100, 111, 98, 101}. When we make these numbers coefficients in a continued fraction we get

\mathrm{

which reduces to 10661292093 / 109898899.

This isn’t a secure encryption scheme by any means, but it’s a cute one. It’s more of an encoding scheme, a (non-secret) way to convert a string of numbers into a pair of numbers.

Related posts

[1] Arthur Porges. A Continued Fraction Cipher. The American Mathematical Monthly, Vol. 59, No. 4 (Apr., 1952), p. 236

3 thoughts on “Continued fraction cryptography

  1. You could easily make it a shared key encryption system though by multiplying the fraction by some secret (rational) number.

    Unfortunately, the continued fraction expansion of the resulting number would probably have some numbers outside of the range of the input plaintext characters. It feels like it would be hard to use that to find the secret rational, but maybe not.

    You could even encode a secret pass phrase this way to come up with the secret rational.

  2. If one used multiple rounds of continued fraction transformations with a shift cipher, substitutions and a multiplier that is pre-shared you could obtain secrecy. For example you obtain the ASCII letters/numbers, shift/substitute per cipher, transform into the new continued fraction ratio, and then multiply by a rational ratio as stated above. Then for the following rounds, you expand the new ratio into a simple continued fraction, shift per cipher, and multiply. Rinse and repeat. Doing multiple rounds of this securely obfuscates the continued fraction expansion that would not be so if you only did one round of transformations. I’m to I’m going to write a proof of value. Thank you for the inspiration. I’ll be sharing the secret with a Diffie-Hellman KE.

  3. Patrick Stein, you could factor the numerator and denominator of the resulting fraction and get a very reduced set of combinations for which factors produce the secret and which the message.

Leave a Reply

Your email address will not be published. Required fields are marked *