Continued Fraction Cryptography
In this quick post, we take a look at the mathematics behind basic cryptography and how to implement basic cryptography using Mathematica.
Join the DZone community and get the full member experience.
Join For FreeEvery 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
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
Published at DZone with permission of John Cook, DZone MVB. See the original article here.
Opinions expressed by DZone contributors are their own.
Comments