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...
rot13!!!
translate topic with your friendly local IRC bot
Sig you!
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
Well, I should clarify, you *can* work through DES, blowfish, etc... by hand (provided you have S-Boxes as needed) but I found it terribly time consuming when I had to do that in some proofs. I was kind of assuming you were thinking of a decent balance between security and getting done before the message contents are useless.
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!
Can it be broken, yes. Coose the random number generator carefully exploiting artifacts unique to the calculator's internal calculation methods and it can easily get quite dificult to crack.
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?
I'm just curious, but, what is the use for this? Are you in prison trying to reach your attorney? Are you in an oppressive, 3rd world dictatorship? Are you in school trying to pass notes? Again, just curious...
"I assumed blithely that there were no elves out there in the darkness"
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
Indeed. We should confiscate any technology that may aid or abet terrorists. Please turn any sharp objects, flammable objects, objects capable of use in transmitting information, and while we are at it, please gouge out your own eyes, drive an icepick into your throat then hack off your limbs to prevent the use of handwriting or sign language..
Then again, you could probably lick someone in morse code. Probably simplest if you just shot yourself.
There are about two categories of response to this: simple algorhithms which can be performed by hand, which would be exceedingly easy to break for an experienced cryptanalyst, and one-time pads, which is a painfully obvious methodology to anyone over the age of eight. I doubt a discussion of cryptographic parlor tricks is going to enlighten a terrorist.
Poster's Sig:
I have a theory it's impossible to prove anything, but I can't prove it.
Check out Gödel Incompleteness Theorem in your quest. I don't know if you were proving that anything interesting was unsolvable, but if you weren't then you're proof is by that nature interesting, and thus is unsolvable. This follows similar to the proof that all Natural numbers are interesting:
Consider numbers like prime numbers to be interesting, and any other number you like (maybe your favorite lucky number). Then, by the Well Ordering Principle there exists a minimum number that is un-interesting. This fact alone it atleast somewhat interesting, thus this number is now interesting. Thus there exists another number...
Therefore all Natural numbers are interesting.
[X]
Wheeeee
... 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...
I picked this technique up from my high-school precalc teacher. Convert the message to some sort of number(a=1, b=2) possibly applying a shift or substitution cipher first if you feel like it. Create the necessary number of 2x2 matrices and multiply them all by a key. Result is 2x2 matrices with the ciphertext. Convert this back to letters and your set. I can't remember if there was a single 2x2 as the key or if there were multiple ones. He claimed it was unbreakable, what are your thoughts?
I doubt a discussion of cryptographic parlor tricks is going to enlighten a terrorist.
YHBT. YHL. HAND.
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
A one time pad with or some other secret knowledge where the security isn't in the difficulty of the computations to just brute force everything. However, if you have a secure way to give the ontime pad, it is probably easier to give the message in the first place unless you're sending an agent into the field.
Actually lots of PK methods are "easy" to do by hand with primes that are small (thus small key size). I have done it on pen and paper before with a calculator handy. Not secure, but educational, which is my guess for your desire to use it.
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
At least after this assignment is due, tell us what mark we got.
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.
The Intel RNG is in the 8xx series chipsets, not in the processor. You don't get it if you use a VIA or SiS chipset with an Intel processor.