Slashdot Mirror
Encryption by Hand?
Arachn1d writes "A question for all those slashdot math-geeks out there: What's the simplest, but most secure encryption algorithm you can devise or provide a link to that can be carried out with nothing but a pen, some paper and a calculator? Bonus points for any public-key cryptography solutions!" Bruce Schneier developed an encryption algorithm designed to be performed with a deck of cards, but it's rather slow to do for fun. Well, you did say "a calculator", and if we assume a programmable calculator your options probably expand quite a bit...
I think Knapsack is a simple system to do by "hand" if you know modular arith / number theory (to calculate the inverse modular operation). Plus it meets your public key "bonus."
It's not the most unbreakable code in the world, but better than ROT13 or even poly alphebetic cyphers (think Kasiski for breaking ploy's).
Wheeeee
2) If you are going to be hand writing the messages as well, you may want to use out of band information (letter shapes, mispellings (with & without crossing out, etc.), line breaks, etc.) to either carry information or make it appear that you have hidden information & thus confuse the issue.
3) Split the message (e.g. every third word, etc.) in interesting ways.
4) Play Simon-says; send messages that say things you might have said, but that your recipient knows to ignore because they lack some feature.
Etc., etc. The list is pretty long, and success mostly depends on doing Odd Things the Bad Guys don't expect, and avoiding the Dumb Things that they will see right through.
Weren't you ever twelve?
-- MarkusQ
You don't have to use ASCII, just start with a number mapping that conveys the information you need. Maybe 1-26 for letters and a few more for space, punctuation, etc.
Then pull the top number off your pad, add your code number, write that down. Tedious but not difficult, and your friend just does the same thing in reverse to decode.
Plus it's unbreakable, so long as no one gets a hold of your pad and you never reuse it.
--
I don't want to rule the world... I just want to be in charge of mayonnaise.
you dont need a calculator, you just create your own 'hash' table. Like a = f, b = g, etc, or you can do a random thing and map a = g, b= d, etc.. All you need is a peice of paper and a pencil.
Only 'flamers' flame!
If you allow the addition of dice, say a d20 ...
Setup by the sender:
- Generate a one-time pad by rolling the d20
and writing down the 1's digits (d20 face value
mod 10).
- Transmit the one-time pad in a secure fashion
(use somebody's public key suggestion, hand carry, etc.)
Setup by the receiver:To encrypt:
To decrypt:
Encrypt example:
Decrypt example:
And yes, the devil in the details is in the secure transmission of the one-time pad (step 2 of sender setup). Key management is never easy. Storage and transmission of one-time pads is one of the reason why this form of crypto is not a realistic choice for most applications. However if you have some way to transmit the one-time pad ahead of time, say visiting the sender ahead of time and dropping off the one-time pad it is not a bad choice.
chongo (was here)
Search the literature - what was used before the mechanical systems of WW-II?
These were the strongest ciphers that could be used in an era before mechanical assistance (and you could even simulate the Engima machine with pen and paper!), so they satisfy two of your requirements. But you won't find asymmetrical ciphers from that era.
However, you can find some ciphers far stronger than the simple rotor engines others are suggesting.
For every complex problem there is an answer that is clear, simple, and wrong. -- H L Mencken
What about ciphersaber?
These numbers, which are probably random, are not crytographically secure precisely because it's in a book you can find in the library.
An attacker can easily find out which book you are using from quite a small portion of plaintext and thus reveal all messages past and future.
One Time Pad relies on the utmost security of the key, and the fact that it's only used once (for any purpose).
Make even shorter URLs - 8LN.org
... had a system that relied on a deck of cards, and figured in the plot. The scheme was designed by Bruce Schneier, and described in great detail in an appendix. The system looked quite difficult in practice.
Even better, if you can get them: a pair of twenty sided quantum-entangled dice. That way, both sender and receiver can extend the pad at need, just by rolling up more numbers.
The only tricky part is reading the dice without looking at them. There are several ways to do this, but none of them actually work in practice and at least one of them is suspected of causing space-time errosion (& thus you will need to file an Environmental Impact Statement, including the plain text of the message being sent, thus reducing the utility of the system).
Another problem is keeping the dice cold. They have to be kept very, very cold, and of course this is very very expensive (C = A*exp(K-T)+B*N, where C is cost, K is Boltzman's constant, T is the temp., A and B are arbitrary constants related to local tax laws, and N is undefined).
But the main advantage of using quantum dice is that it would be too nerdly for words (at least three equations would be required) and you could probably get your picture in some magazine, wearing a white lab coat with coloured lights hitting you from odd angles.
-- MarkusQ
P.S. The original post was sound, but if you buy any of this post, I have a startup I'm trying to fund...
Seriously. You can run AES by hand; and given a few sheets (and an hour of setup time) for precomputed tables, you can get the time down to half an hour per block.
Of course, making sure you don't make any mistakes along the way is rather critical, so I'd suggest spending another half an hour to verify your cryptotext.
Tarsnap: Online backups for the truly paranoid
It's pretty obvious that you can use vector sizes different from 256. For example, you can do RC4-52 with a deck of cards face up on a table (4 rows of 13 so you have to do arithmetic in your head mod 13 and 4 on the cards and suits--you figure out the details). Or you can do RC4-99 (9x11 grid) or maybe RC4-100 (10x10 grid) with pencil, paper, and eraser.
Then as several people mentioned, there's always the one-time pad. If you want to encrypt just one or two very short messages (total a few dozen characters or less), one innocuous way to carry the pad is as a wad of cash (I mean just a normal quantity of $1 and $5 bills in your wallet, not a suspicious roll of $50's and $100's). Use the serial numbers as the pad and spend the bills when you're done with them.
Forget public key. Public key cryptography in any known form is impossible without a programmable device. The calculations are just too cumbersome to do by hand. Anyway, public key probably isn't too useful in this situation. Public key solves the "n**2 problem" when a bunch of independent mutually distrustful peers are all trying to talk to each other--you only need one secret per person, instead of n**2 different secrets. For pencil and paper ciphers you're probably only communicating with trusted peers, so a shared secret is ok.
Of course if you have even a crude programmable device like a pocket organizer (even some of the ones much less fancy than a Palm Pilot) or a Java-enabled cellular phone, you can run all the usual computer cryptography algorithms on it.
To avoid the embarassment of being caught with code books, an old method was to take an obscure out of print book, then refer to a letter by page, paragraph, word, then position in the word. The trick is not to repeat a reference, and to change the book you use frequently. Russian spies in England in the 60s (for example the "Lonsdales") used this trick. If you control the channel the message is sent by (for example, dead-letter drops), and if you use other codes in the source (for example, code names for contacts), you can make your own cold-war communications system.
"Well, put a stake in my heart and drag me into sunlight."
They used a table like this:
8 BCDFGJKLMP
9 QRUVWXYZ/.
The common letters in the first line are encoded as the single digits 0..7. The less common letters are encoded as the double digits 80..99.
This has two advantages. It provides some compression of the text and it eliminates any simple one-to-one correspondence between letters and pairs of digits.
Example:
SLASHDOT
S = 6
L = 87
A = 2
S = 6
H = 7
D = 82
O = 3
T = 1
6 87 2 6 7 82 3 1
68726 78231
Mea navis aericumbens anguillis abundat
Yes and No. I did leave out details. Consider this revised proof:
Definition: Interesting Numbers - numbers that have a name or a special property that describes them. Examples: Primes, telephone numbers, population of some town, etc...
Theorem: All Natural Numbers are interesting.
Proof: Assume that not all natural numbers are interesting. This implies there exists an uninteresting natural number or a set of uninteresting natural numbers. Now, we must only prove that this set is indeed interesting.
Method One:
Basis: By the well ordering principle there exists a minimum value in this set. Because this number can be described as the minimum value in the set of ALL uninteresting numbers that means there is a description of this number and thus it is somewhat interesting and does not belong in this set.
We can inductively show numbers in the set are interesting. Not that each is now the minimum uninteresting, rather the ith member of the uninteresting set, thus making it interesting.
Method Two:
Just state that being the member of a set for which there is a descritption makes all numbers in that set interesting (since they were just described). I do not really like this method however since it makes the entire proof un-elegantly trivial. To prove all numbers interesting we can just define two sets: the set of all numbers equal to 2, and those that are no equal to two. Maybe we need to argue that the cardinality of a set should not be 1 or 0 but then we can just make a set of all numbers greater than 1 and less than 4, and all numbers that aren't. Then there's the "interesting" issue of making two sets of equal size that partition the universe: even and odd numbers. It is easily shown that all natural numbers are either even or odd, and being odd or even is arguably interesting, thus all natural numbers are interesting. Then again, I'm babbling on about a truely meaningless property of numbers that I just use in an intro class to talk about simple proofs and WOP and induction, etc...
As for your barber problem, if you introduce a second barber they can each cut each other's hair, and thus begins the old joke about the small town with two barbers, one having nice hair, the other having horrible - which do you go to?
Wheeeee
Pretty much any other key based one is doomed
Ok, I'll grant you that yes, on the basis of other algs, finding the key (ie guessing) will produce the answer. However, you need to be careful when you use the concept of "pretty much" and then go on stating how something is not secure due to the inherent key guessing restrictions. Although I can't say there is one point or another that you make that I completely disagree with, it's probably just ambiguities in the language that erk me. Ok, yes, you can guess all the keys, but if you do not know what alg. I used (you do need to know what to stick your keys and the cipher text into, right?) your time to break my code grows - and it grows very large. Especially if I take a known alg. and alter it in a way that does not introduce some flaw, let's say I alter the SBoxes in DES to just as secure sets - now you have to know what alg. I used and what alterations I used. Then, how do you know when your brute force spits out the right answer? I could have sent the message: "SNaRFt" to my friends who happen to know that this means they need to attack at 1:21PM EDT. Presumably you will stumble upon key / alg. combos that will produce just as meaningful (to you) plain texts.
Yes, given enough time you can try all keys (within a finite length) and I guess you can try every SBox combo in DES (within a finite range of values) but how much time are we talking for just this set? Let alone the fact that you don't know if maybe I just used regular blowfish, or AES, or whatever.
Are Blowfish, AES, DES, whatever unbreakable? Heck no. But does that mean that even given a year you could break a particular code of mine? How about infinite time and the obvious issues shared with one time pads that you are not sure which possible plain text is the right one - can you ever say for sure you've cracked it?
Basic idea: is it theoretically possible to break something? Yup. Might the sun go nova before you get done? Pretty much. Would you even know when you got it? Hard to say.
Wheeeee
In WW2 and the 60's, breaking book codes was difficult but not impossible. Today, if the attacker has the text of your book in a computer (he doesn't have to know which book it is, he just needs a big library of online books that includes yours), book codes are probably quite weak.
Stage 5 of Simon Singh's cipher challenge was also a book code. It turned out to be possibly the hardest of all 10 stages. But even though the message was just a few dozen characters long (and turned out to be written in Spanish), several people managed to solve it.
Yes, the idea is the person at the other end has the list of serial numbers. In all these examples the purpose of encrypting it is to send it to another person, not to store the info so you can decode it yourself later. Sorry about any confusion.
Bruce Schneier's Solitaire algorithm (the one that uses a deck of cards) also has no known breaks, though it turns out to not have all the properties that the designer had hoped for.
With computers everywhere these days, pen and paper ciphers are mostly just an intellectual challenge. Still, the subject comes up on sci.crypt regularly. It figures into Neal Stephenson's Cryptonomicon if that's of any interest.
Of course, the proper way to encode the key
would be on something like Fruit Roll-Ups (TM),
which are like paper but edible. That way, both you and the recipient could eat the key after using it.
Cryptograpy has never been so delicious!!!
The Codebreakers, by David Kahn, is the standard reference on historical ciphers, btw. That's the first place to look if you want to know how those old systems worked.
The closest thing anyone has found to weaknesses in RC4 are "distinguishing attacks". If you have a gigabyte or so of RC4 output, you can statistically show that it's not actual random data (you can distinguish RC4 from a true random number source). However, that's a long way from being able to break the algorithm.
On the other hand, I can't...
I will not delve deeply into set-theory here. But what you remember from your classes about a class versus a set is true. A class C is defined as: C = {x | x has property P }
On the other hand, with the use of Zermelo-Fraenkels axiom number 4 from standard ZF-set-theory, the following is a completely ok way to define a set: S = {x | (x is element of T) and (x has property P) }, whenever T is a well-defined set.
In both definitions above, it is of course important that the property P is something we can express in a formal language, otherwise it is impossible to even in theory tell wether something is part of a set (note that it is ok for P to be very hard to compute, but it should at least be possible to express P in a formal language).
In the barber paradox, you have the set of all people: P. Populations are usually finite, so this set can be listed by enumeration, and is thus well-defined. Then you have the set of all people shaving themselves: S. And the set of all people not shaving themselves P\S. And we have the set B of all people shaved by the barber. All of those sets are well-defined. Now, you introduce the assumption that B=P\S. This leads to a contradiction, thus the assumption is wrong, the barber cannot possibly shave everyone who doesn't shave themselves. It is not a paradox, it is a simple proof (reductio ad absurdum), and there is no need to involve heavy set-theoretic stuff.
On the other hand, in the "interesting numbers" theorem, we have the set N of naturals. We define a subset I of "interesting" numbers. The trouble with I is that the "interesting"-property is not something we can express in a formal language. Thus I is not a well-defined set. Wrongly, we continue developing the proof under the false assumption that I is well-defined. Since our intention is to prove that I=N, it is natural to assume the opposite (not I=N), and in this case the well-ordering property of N gives us that there is a least number n in N, but not in I. Given our completely unformal definition of "interesting" above, it seems perfectly ok to say that n is "interesting". But if n is "interesting" then it must be in I. This is again a contradictory result, and thus we must conclude that not not I=N, which most people who aren't anal intuitionists, agree to mean the same thing as I=N.
But just to clear up: B=P\S is not a definition of a set. It is a statement in logic, it can be either true or false.
The old definition of set's were equal to todays classes. I don't know why we need classes, but I'm sure real mathematicians use them for some sort of thing (real mathematicians don't worry much about foundations, only logicians (and thus computer scientists) do).
The meaning of a self-referential set involves a set with itself as a member. Such as "the set of all sets", "the set only having itself as member", or anything in between. Of course, "the set of all sets except itself" is equally troublesome, since the complement would be self-referential. (And in those days, the complement of a set really meant that, it was not taken with respect to another well-defined set, but to a universal set including every set).
Your definition of the set I (either a prime, or the smallest number not in I is however legal, as the property of being prime or being the smallest number not (already) in I), is certainly expressible in a formal system. It is almost comparable to a standard recursive definition, e.g. where you define a binary tree to be either an empty tree, or a node with two subtrees named "left" and "right". If you reformulate that definition as one defining the set of all binary trees it looks almost (but maybe not completely) as "weird". And upon inspection this definition of I is certainly simple enough. If you are used to inductive proofs, it is immediately obvious that I=N.
The current popular reformulation of sets (ZF-axioms) doesn't involve classes. I don't know what real mathematicians need classes for, but it's most likely something, otherwise they wouldn't be needed.
Subtracting sets (e.g) P\S doesn't involve any big problems. The problems shows only up if you involve negations of sets without a clearly defined universe of discourse. If you allow this universe to be the set of all sets, then you are in trouble. Because it could include such sets itself, and so on. It might be the case that classes were introduced just for this purpose, to allow people to do it anyway, but without destroying the foundation of mathematics, which is built on top of sets.
Yes, I don't like your definition of I. I agree that it is troublesome. The easy way out is to declare it meaningless (since you cannot define something in terms of itself (circular definitions)), or to reformulate it as an inductive definition. And in a typical formal system of notation (logic), you would be forced to do this choice.
Either way, the proof that all naturals are interesting, revolves around the non-formal definition of I. You can define it in a completely informal way (my way), in a way that is not meaningful (your way), in a way that is questionable (my reinterpretation of your way), and so on...
I don't think there is anything deep or fishy here. Circular definitions are certainly meaningless, but my reinterpretation clearly shows one of the deficiensies of the human brain. In an attempt to try to understand something that didn't make sense, I reformulated it in another way that perhaps could make sense (although highly doubtful), instead of pointing out the obvious fault that it was a circular definition. (And as most circular definitions of this kind, when trying to interpret it anyway, you would either reach everything N, or nothing (bottom)).
To say that sets can be constructed from classes is just a reformulation of saying that they can be formulated from other sets, and a property. So to me, it doesn't add any value. But I am not a set-theorist, and maybe classes really add something useful. Or maybe they are just a convenient notational device. Or maybe neither.