91115/11116 !

by

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:

8+\frac{1}{5+\frac{1}{12+\frac{1}{12+\frac{1}{15}}}}.

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

8+\frac{1}{5+\frac{1}{12+\frac{1}{\frac{181}{15}}}} and then 8+\frac{1}{5+\frac{1}{12+\frac{15}{181}}}

all the way to \frac{91115}{11116}.

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 \frac{2358}{169} (or the longer \frac{536341314626}{38440072317}).

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.

Tags: ,

3 Responses to “91115/11116 !”

  1. Barry Leiba Says:

    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

  2. TwoPi Says:

    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 2^8 3^5 5^{12} 7^{12} 11^{15}, 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.

  3. Jason Dyer Says:

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: