I'll let you know how this turns out. Wish me luck!

[mgb_phys]

This is about the simplest strong encryption tool, I don't think you could run the algorithm in your head, but you can probably memorise the code.

http://en.wikipedia.org/wiki/Tiny_Encryption_Algorithm

 

[CRGreathouse]

CRGreathouse,

As has already been mentioned in this thread, the Solitaire algorithm (called Pontifex in Cryptonomicon) is nowhere near secure enough to thwart major governments.

Ah, sorry, I missed where it was mentioned.

I agree that the algorithm is not secure enough to meet the requirements of the thread, but I thought that it might have been what the OP had read about so I wanted to mention it.

 

[CRGreathouse]

I don't believe there's a realizable mental cryptosystem strong enough to consistently protect against cryptoanalysis backed by the military budget of a motivated country.

Well, let's consider what a large country might be able to do to brute-force any code, assuming they haven't found a special weakness. If the EFF can crack DES (56 bits) in two days, then a government should be able to brute-force 60 to 80 bit keys in a day, with budgets around ten million dollars (60 bits) to hundreds of billions of dollars (80 bits). If the information needs to remain secret for a year, that's another 8 bits. Kick in a few bits for safety (in case of a minor keyspace reduction break) and you need 90 bits, minimum, to be safe from a major government.

So the first step to a mental cryptosystem is finding a way to remember and work with a key at least 90 bits long.

 

[ATruePyRo]

(wrote this up minutes before lecture; trying to run with presented ideas - characters -> bits information isn't very meaningful to me in a simple polyalphabetic cipher.)

Heuristic: group the cipher key into blocks of 5 letters- 40 characters requires eight 5-character blocks. While doing the cipher, note the lengths of each word and track block placement by adding the word length to last block placement value and taking mod 5. Keeping track of the block placement values could make it easier to keep track of where you are in the key while enciphering mentally. If you lose track of your placement mid-word, the block placement value could be used to get you back on track instead of having to recount everything.

If an error occurs while enciphering, there are two likely possibilities. The first of the likely possibilities is that an individual letter may be incorrectly converted to its ciphertext. The second likely possibility is that the person creating the ciphertext may have shifted the key placement; hopefully the block placement value will allow the shift to maintain some regularity, e.g., suppose you are decrypting (bare with me) a [7-letter word and are on the 3rd letter], from memory you know the current and upcoming blocks are RIJND AELCR YPTOG and that [you started on the 2nd character of the RIJND block]. The correct character to apply as a cipher key is N (value: +14), but you made a mistake and thought you were already using AELCR. You recognize the 4th ((2+3)-1) character of your block is C and continue on your merry way having skipped the 5 intervening characters NDAEL (N obviously included). Fortunately this can be fixed at the decoding phase without too much trouble and importantly doesn't effect the strength of the cipher. When the 7 letter word is finished, you would still observe that (2+7) mod 5 = 4 is the starting position in the continuing block.

On to memorization:
It takes hours (who would sit around memorizing pi for days??) to memorize a couple hundred digits of pi- a sequence of digits that serve no practical purpose in man's memory beyond perhaps 9 digits. My point is that a lot of people know plenty of digits of pi despite the inherent randomness of the digits.

Strictly relying on memorized strings of numbers could be worked into some sort of mental cryptosystem- however there are some considerations to make. Speaking strictly numerically, grouping the digits would seemingly offer a fairly easy solution to increasing the range at which a cipher can effect text. The process, as consistent with previous descriptions, would be an additive mental operation, but first between the grouped digits and secondly as the sum is applied to the text as a member of the crypto-key. Through cursory reasoning result in a problem as you can expect an inherent bias for the pairs to sum to 10. While 10 would be the most probable sum with 9% of all pairings yielding this value, followed by 9 and 11 then 8 and 12, etc. 0 and 18 occur the least frequently only once out of 100 blocks. This is sensible because the only way to sum to 0 with two digits is (0,0), and 18 also can only be reached by pairing (9,9). All other values 2-17 have at least two possible pairings, with 10 having the most through (1,9),(2,8),(3,7),(4,6),(5,5),(6,4),(7,3),(8,2) and (9,1). This would seemingly be a flaw in the strength of the cipher if the process were numerically based on this method. Although I'm not quite certain as to how much trouble that sort of thing would really cause as the key itself would still prove useful in lighthearted applications (of the sort my postings have predominantly intended). If you already have 200 digits of pi memorized, that can serve as a 100-character key!

Other methods can mediate the storage and retrieval of key-information; the pontifex method exploits a common deck of cards as such a medium. However, if people demonstrate the ability to retain accurate memories of numerical sequences (or otherwise), why not exploit this in a mental cryptographic system?

The memorization of non-numeric sequences could help avoid the aforementioned numerical bias (to 10) by increasing the number of values stored in each symbol - pairing would thus be unnecessary.

Heuristic idea #2: As 3rd graders memorize times-tables, the memorization of a substitution chart corresponding to each letter could help exploit rote memory and reduce overall cognitive load during mental enciphering. Practicing monoalphabetic ciphers would probably be a good way to learn because effectively each character in a key functions as a switch into a different monoalphabetic cipher (fortunately, there are only 25 monoalphabetic ciphers that produce unique ciphertext).

Getting accustomed to applying the monoalphabetic cipher mentally is easy for letters along the extrema of the range, if "A" is given as a key and represents a translation of 1 position, "A" onto "A" is always "B", "A" onto "D" is always "E", "A" onto "Z" is always "A". If all the letters can be learned this way then a sequence can be ciphered without much computation, just mental substitution. The "key" would be switching gears, treating your mind as a Turing machine and switching machine states dependent on the current symbol reached as one iteratively moves through the mental 'tape'-recording of a random sequence of letters. Furthermore, while developing the mental codes for automatic retrieval, conversion to numerical representations and a little quick algebra consistently works and is always an option as a mental checksum.

As for a long key, people (myself included) often pick up various >>useless<< alphanumeric sequences, e-mail accounts, phone numbers, microsoft windows (egh) serials. Memorization of sequences is often less an issue of memory limitations as it is a limit of motivation. The memorization of several hundred randomized characters with regular blocking seems a bit excessive however well within human capacity. I think a Vigenere cipher exploiting a memorized key of sufficient length could be effectively utilized in a mental cryptosystem. This is perhaps overly simplistic. Are there any other suggestions for going about an applied mental cryptosystem? Feel free to critique what I've written. Personally, I'm much more interested in simple ciphers that I could use when passing notes among friends, strictly for the hell of it, but I suppose if security were an issue the system could effectively be extended by more dramatic means.

EDIT: I tried mentally ciphering a sentence using a memorized 25-character key. I used my laptop's XP serial which I remember (for no good reason, i run slackware12) and considered all letters as numbers, went through the arithmetic mentally and managed to write out my message without showing work. Maintaining awareness of the key and the original message wasn't as difficult as one might suppose, there is a minimal amount of information that one is required to keep in focus to accomplish a simple cipher task as I have described. Maybe the use of a more sophisticated system could provide more security but the methods should be designed to function reasonably under limited human-attentional resources.

 

[ATruePyRo]

I have fixed several errors contained in my last post.
-James

As for learning the placement of letters in the alphabet... I've found Base 3 is a pretty handy system. I mentioned it on my first posting here (page 2) and it's surprisingly convenient.

(Base 3, XYZ) -> (Decimal, 9X+3Y+Z)

_ 000 I 100 R 200
A 001 J 101 S 201
B 002 K 102 T 202
C 010 L 110 U 210
D 011 M 111 V 211
E 012 N 112 W 212
F 020 O 120 X 220
G 021 P 121 Y 221
H 022 Q 122 Z 222

Example: 'Base3 in action'
111 012 201 201 001 021 012 201 000 001 200 012
000 012 001 201 221 000 100 112 000 002 001 201
012 000 202 022 200 012 012 000 001 112 011 000
100 202 000 010 001 112 000 022 012 110 121 000
221 120 210 000 110 012 001 200 112 000 202 022
012 000 112 210 111 012 200 100 010 001 110 000
211 001 110 210 012 201 000 001 201 201 120 010
100 001 202 012 011 000 212 100 202 022 000 012
001 010 022 000 110 012 202 202 012 200 000 000

in Base10,
13 05 19 19 01 07 05 19 00 01 18 05
00 05 01 19 25 00 09 14 00 02 01 19
05 00 20 08 18 05 05 00 01 14 04 00
09 20 00 03 01 14 00 08 05 12 16 00
25 15 21 00 12 05 01 18 14 00 20 08
05 00 14 21 13 05 18 09 03 01 12 00
22 01 12 21 05 19 00 01 19 19 15 03
09 01 20 05 04 00 23 09 20 08 00 05
01 03 08 00 12 05 20 20 05 18 00 00

Converted back to alphabetical symbols,
messages are
easy in bas
e three and
it can help you learn th
e numerical
values assoc
iated with e
ach letter

"messages are easy in base three and it can help you learn the numerical values associated with each letter "

I know the system doesn't offer any cipher protection, but it is really easy to learn and I've found it useful as a mnemonic when doing arithmetical operations on alphabetical symbols. 3 qubits are all it takes to hold the entire alphabet and a space character, which makes Base3 a particularly neat system to work with when encoding text. Observing that the 13th letter of a 26 letter alphabet is smack dab in the 'm'iddle is priceless. (M=111, Z=222)

I have no clue if anyone will find this remotely interesting, but I've done the work outlining the process anyway. Hope it's enjoyed.

 

[laddiebuck]

Just interjecting

Well, let's consider what a large country might be able to do to brute-force any code, assuming they haven't found a special weakness. If the EFF can crack DES (56 bits) in two days, then a government should be able to brute-force 60 to 80 bit keys in a day, with budgets around ten million dollars (60 bits) to hundreds of billions of dollars (80 bits). If the information needs to remain secret for a year, that's another 8 bits. Kick in a few bits for safety (in case of a minor keyspace reduction break) and you need 90 bits, minimum, to be safe from a major government.

So the first step to a mental cryptosystem is finding a way to remember and work with a key at least 90 bits long.

I just felt I could interject for a moment here -- I'm very interested in the original question -- to note that 90 bits of ASCII is just over 11 letters, and memorising passwords of over 12 characters is not a problem for the typical computer user. Even considering that only 40 or so characters are used -- let's assume 5 bits of real information -- only 18 characters need to be memorised. So key length is not really a problem.

 

[CRGreathouse]

For me, at least, memorizing and manipulating an 18-character password of random letters and symbols (26 letters, 6 other symbols) would not be easy. It's hard enough for businesses to enforce strong 8 to 12 character passwords, which are still fairly far from random. This is twice that length and fully random. (If you're allowed to use less-than-random keys, you need to increase the length to ensure that the entropy stays high enough.)

 

[laddiebuck]

True, but given the original question's high goals, we may at least set the bar a little bit higher than for any ordinary problem. It's not /that/ difficult. You could easily invent a mnemonic for your password, a little ditty or rhyme, as long as you choose the password randomly first, and fit the ditty to it afterward.

When this question was asked on Slashdot, by the way, the most reasonable method proposed was RC4.
http://ask.slashdot.org/article.pl?sid=02/03/30/1927236
http://en.wikipedia.org/wiki/RC4

I'll work through some instances of RC4 and Tiny and post the results here later unless I forget. I don't think either has the property that they can't be broken based on the intermediate state, but as another poster pointed out, that may be impossible (without some "hardware", which may be no more than a paper abacus or pack of cards, of course). In any case, they are a start.

 

[NickAlger]

I have been thinking about this as well, and I think RC4 would be feasible given a few months of training. The key to performing the encryption at speed in your mind will be memorizing huge tables of precomputed operations.

 

[laddiebuck]

Hmm, promising! I plan to see how much effort I can save if I write out some key tables (mind I haven't thought much about the actual feasibility, so I'm just writing down my general ideas). Including the full algorithm and generic tables next to my ciphertext is no security risk, and no inconvenience.