One of my favorite encryption techniques isn’t really an encryption at all: it fails in the basic sense that if you know the method of encryption, you can easily decrypt the message. But it does reduce every message to a fraction, and I like that. I can envision entire conversations consisting of phrases like “73/9”. Here’s how it works. You start by replacing each letter with a number: say, A=1, B=2,…,Z=26, and perhaps (space)=27, plus whatever punctuation that you want. Then you write your message as a continued fraction (that is, a nested fraction where each numerator is 1). For example, to write “HELLO” you’d let H=8, E=5, L=12, L=12, and O=15 and write:

.

Then you’d simplify it before sending it. For example, the fraction above simplifies to:

and then

all the way to .

To decrypt, use division to write the fraction as a continued fraction (keeping in mind that words that end in “A” will turn out to be ambiguous unless you develop a way around it). Want to have some fun? Try decrypting (or the longer ).

*I don’t know if the guy in the painting by Lesser Ury is really a spy, but I kind of think he looks like one.*

### Like this:

Like Loading...

*Related*

Tags: continued fraction, encryption

This entry was posted on October 13, 2008 at 5:42 pm and is filed under Miscellaneous. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

October 13, 2008 at 10:53 pm |

Right, a handy code for some math-oriented kids to play with. Of course, one can vary the mapping between alphabet and numbers, to make it “harder” (but it still just amounts to a substitution cipher once you sort out the division code). And avoiding mapping 1 should take care of the ambiguity problem.

Here’s a simple REXX program to do the decoding:

/* Decode Xi’s cipher

Enter the numerator and the denominator of the code.

*/

numeric digits 30

parse arg a b

alpha = “ABCDEFGHIJKLMNOPQRSTUVWXYZ ”

msg = “”

do while b > 0

q = a % b

r = a // b

msg = msg || substr(alpha, q, 1)

a = b

b = r

end

say msg

Used:

> xxcode 536341314626 38440072317

MATH IS FUN

October 14, 2008 at 9:04 am |

Godel’s proof of the incompleteness of formal arithmetic hinged in part on the ability to encode sequences of symbols as integers, along with a proof that various logical properties become number theoretic (such as, “is this string of symbols a well-formed formuila?”, or “is this string of symbols a valid proof”?).

Godel’s encoding involves prime powers. Adapted to your “HELLO” example (and using your mapping of the alphabet to the integers), it would lead to the integer , which is a 39 digit integer.

One can prove Godel’s result using the partial fraction encoding rather than the prime power encoding; the one advantage to doing so is that the arithmetic remains simple enough to illustrate by hand for small examples, while Godel’s scheme becomes unmanageable almost immediately.

I can almost imagine two people exchanging fractions as a way to communicate; I can’t imagine folk working with the expansion of “MATH IS FUN” in the prime power encoding.

October 14, 2008 at 1:20 pm |

I am curious if continued fractions could be used for a real cryptographic system. Not simple continued fractions with only 1s in the numerators, but the kind that allows arbitrary numerators.