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:
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 
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: continued fraction, encryption
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.