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

[jeffceth]

do-it-yourself encryption

Really don't know where to put this, so thought I'd ask all the fine folks here and see if I get a response. One of the curses of being widely read is that sometimes you remember the subject but neither content nor location of something you read once and would really like to find out where it can be found again. I know I've read several 'schemes' for doing encryption(high security, no kiddy stuff, the kind it takes a wealthy adversary centuries to crack) in your head or with a few notes on a piece of paper(which if compromised mean nothing cryptanalytically) but cannot find it anywhere. Any of this ring a bell for someone who can provide a url or summary?

The kind of stuff I'm looking for is probably symmetric(tho assymetric would be great and can require any kind of printout or out-of-mind assistance as long as nothing is given away cryptanalytically on any of it.

If anyone remembers anything like this I'd love to hear about it.

 

[jeffceth]

Really don't know where to put this, so thought I'd ask all the fine folks here and see if I get a response. One of the curses of being widely read is that sometimes you remember the subject but neither content nor location of something you read once and would really like to find out where it can be found again. I know I've read several 'schemes' for doing encryption(high security, no kiddy stuff, the kind it takes a wealthy adversary centuries to crack) in your head or with a few notes on a piece of paper(which if compromised mean nothing cryptanalytically) but cannot find it anywhere. Any of this ring a bell for someone who can provide a url or summary?

The kind of stuff I'm looking for is probably symmetric(tho assymetric would be great and can require any kind of printout or out-of-mind assistance as long as nothing is given away cryptanalytically on any of it.

If anyone remembers anything like this I'd love to hear about it.

 

[Gokul43201]

Even a simple multialphabetic substitution cipher becomes virtually uncrackable if the length of the key is comparable to the length of the plaintext.

I remember seeing a little Javascript tool somewhere that let's you enter the plaintext/ciphertext and a password (which serves as a pseudo-random key generating seed). The code generates a key that is as long as the text and encrypts it using that key. You can decrypt ciphertext at the same site, if you have the password.

 

[selfAdjoint]

Colonel Abel, the soviet spy who was arrested back during the Cold War, had a one time pad and some simple rules for using it, involving if I recall, an old Russian folk tune. The "unbreakable" feature was the (pseudo)-random sequence of numbers, which he had to carry with him.

I believe a public key system of fairly good resistance could be based on two large prime numbers which hopefully you could memorize and then do a memorized algorithm on with a calculator.

 

[gnomedt]

Rot-13 is usually enough for most. ;-)

 

[jeffceth]

lol!

 

[chroot]

I've never heard of any such thing. At their heart, most ciphers very complicated "bit shuffling," which could not be done in your head. I'm not saying such a thing could not exist, but I'm pretty well read in cryptography, and I've never heard of it.

- Warren

 

[chroot]

On second thought, perhaps you're referring to the Solitaire cipher, which was called Pontifex in Neal Stephenson's Cryptonomicon. This cipher can be done with playing cards, but is definitely not "the kind it takes a wealthy adversary centuries to crack."

http://en.wikipedia.org/wiki/Solitaire_(cipher)

- Warren

 

[jeffceth]

thanks, gokul, but I think a multialphabetic substitution cipher of decent security would require a prohibitively long shared key for most messages and is, of course, not reusable.

The javascript tools are handy, but fall well within the 'insecure if environment is compomised' zone. if the password is being typed into a computer in unencrypted form, then an environment breach would trivially shatter the security.

one time pads you have to carry with you again leave you dead in the water if physically compromised, and tend to be way too long to memorise. It took me several days to memorise the first 100 digits of pi, so a decent one-time pad would probably be quite the herculean effort.

the reason I don't think an asymetric system is practical is that to be reasonably secure the calculations would have to be too large to do in your head, and in an environment-compromised situation any calculations of that type done on a calculator are cryptanalytically vulnerable.

I don't mean to sound too negative, guys. I really appreciate you taking the time to try and help.

If it helps jog any memories, I think one of the systems allowed for certain things to be written down on a napkin or paper but if the paper was compromised the system was still secure.

 

[jeffceth]

thanks, chroot. I'm familiar with the solitaire scheme and how insecure it is. the scheme(s) I seem to recall had nothing to do with a pack of cards. If it helps jog anyone's memories, I'm pretty sure at least one of the schemes allowed for some things to be written on a piece of paper to help with the calculation, but if the paper was compromised it was not cryptanalytically helpful.

 

[chroot]

I honestly don't see how such a system could even exist. If you write down intermediate figures in the course of performing an encryption, how on Earth could they not be cryptanalytically useful? They indicate, in some respect, the state of the "state machine" in your head.

As I said, even the Solitaire cipher uses a rather complex "bit shuffling" scheme, with real cards, by its numerous cuts and counts. Every other "secure" cryptosystem I have ever seen uses some form of bit shuffling -- and bit shuffling is particularly hard to do in one's head.

I'm interested in learning about such a cipher, if it really exists -- but is there any chance you have just misread something, or perhaps mistook some fictional work for factual?

- Warren

 

[Irresistible_Force]

You mean you don't want to use something like a 384 bit encryption
biometric flash drive?

 

[jeffceth]

exactly. the idea is that the core part of encryption happens inside your head. the method doesn't have to be easy to remember, but the process has to be able to be done as if you were sitting in the same room with an adversary.

 

[jeffceth]

I'm hoping not, but anything's possible.

 

[Irresistible_Force]

You need to encrypt notes on the discussion taking place or like large blocks of data in written form?

 

[chroot]

And really, if such a cipher existed, I don't know why anyone would use anything else! The largest pitfall in almost all realistic cryptographic applications is key security -- if anyone can steal your laptop, they can get your key, and render the inherent mathematical security of your cryptosystem irrelevant. It's almost always easier to break into someone's house, point a gun at them, and take their computer than it is to break a modern cipher.

If you really could do secure cryptography in your head, with an algorithm strong enough that the computing hardware of major governments could not break it for centuries, then key security issues evaporate. The key is only stored in your head, and with the exception of torture and Star Treak brain scanners, no one can get it.

Why would anyone use any other kind of cryptography if such a "killer app" existed?

- Warren

 

[chroot]

Admin note: Two threads with idential original posts have been merged into this thread. My apologies for any conversation that's difficult to follow!

- Warren

 

[Irresistible_Force]

What about this?
Make up your own shorthand note taking system, then assign three digit number codes for every word you may likely need (that's 999 words). Every second use of the same word increments the number by a fourth/fifth digit. Third use next increment and so on. Unusual words could be substituted for with common words that make sense to you, like metal, box, fire, could mean tank.

They have ten tanks. (Shorthand= %= they , *=10 , @,#,$=metal,box,fire)

It, them, they, he/she etc. = % converts to 3951
[have can be assumed and left out]
ten = * = 7861
@=metal = 3541
#=box =7561
$=fire =2931

39517861354175612931

Don't account for spaces, punctuation, common words that can be
assumed. Instead of Incrementing by 1 , you could also go with a 4 digit
number to begin with, and assign two or three numeric values to each shorthand
word and just use them randomly, because they mean the same thing to you.

What do you think? Not uncrackable, but fairly effective with just your brain to work with.
You could also change the proper english usage to something like ten,metal-box-fire,they.
Try to crack this one :273197312391!

 

[chroot]

What do you think? Not uncrackable, but fairly effective with just your brain to work with.

It would probably take a cryptanalyst no more than a half dozen of these messages to crack it completely. In fact, it isn't even a cryptosystem at all, it's just a shorthand, and offers absolutely no mathematical security at all.

The original poster is talking about cryptography that major governments could not crack; this kind of "real-world" cryptography requires expert-level training to design.

- Warren

 

[Irresistible_Force]

It would probably take a cryptanalyst no more than a half dozen of these messages to crack it completely. In fact, it isn't even a cryptosystem at all, it's just a shorthand, and offers absolutely no mathematical security at all.

The original poster is talking about cryptography that major governments could not crack; this kind of "real-world" cryptography requires expert-level training to design.

- Warren

'Cryptosytem' is not a word. So, you're right.
If you're saying it isn't a cryptographic system , then you're wrong.

cryp·tog·ra·phy
1.The process or skill of communicating in or deciphering secret writings or ciphers.
2.Secret writing.

There is no 'real world' cryptography that only major governments could not crack, which is why we change keys quite frequently. If there were, you most certainly could not do it in your head.

I was only offering a suggestion to the poster of something that could be done in his head. The most secure encryptions are the ones that are unknown to any but the owner. He didn't say he would be sending messages back and forth, he said it had to be done in front of the adversary, without giving anything away.

BTW, I am a cryptologic technician (maintenance) for the Navy, so although not up to the 'expert level of training' you refer to. I am certainly
qualified to offer a suggestion.

 

[Curious3141]

'Cryptosytem' is not a word.

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

It is a word. It's a portmanteau of "cryptographic" & "system".

 

[Irresistible_Force]

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

It is a word. It's a portmanteau of "cryptographic" & "system".

Dictionary.com says it's not.
And, from your link on 'Wikipedia' in which anyone can write stuff up :
In this meaning, the term cryptosystem is used as shorthand for "cryptographic system". A cryptographic system is any computer system that involves cryptography
Still, not a word. As I said. Neither is Cryptonet, not to be confused with kryptonite, which, BTW is a word.

 

[shmoe]

Dictionary.com says it's not.

Dictionary.com doesn't include all scientific or field specific terminology. You can find "cryptosystem" all over the literature. Try searching for "cryptosytem" in MathSciNet, I had 454 hits with "cryptosystem" somewhere in the title.

 

[chroot]

'Cryptosytem' is not a word. So, you're right.
If you're saying it isn't a cryptographic system , then you're wrong.

Of course it's a word. Have you ever, say, read a book on cryptography?

There is no 'real world' cryptography that only major governments could not crack, which is why we change keys quite frequently.

While it is possible that NSA already has cracked every modern cryptosystem, most mathematicians believe that at least a few existing cryptosystems have no corresponding cryptoanalytic vulnerabilities, meaning the only known attack is brute-force. These algorithms use keyspaces so large that the mean time to find a key with existing computing hardware is longer than the age of the universe. Of course, this doesn't mean the key won't be found in thirty seconds, but it's highly unlikely. It's also possible that Uncle Sam has alien quantum-computer technology, but, again, it's highly unlikely.

If there were, you most certainly could not do it in your head.

However, this is exactly what the original poster asked for.

The most secure encryptions are the ones that are unknown to any but the owner.

This is quite likely the dumbest thing you've said in this thread -- even dumber, perhaps, than suggesting that cryptosystem is not a word. Point of fact, the most secure ciphers are those that are publicly scrutinized by tens of thousands of professionals, and corrected so that they contain no "bugs" that could be used for cryptanalytic attack. An algorithm that is known to contain no flaws is one whose security depends only on the key. If no one has your key, such an algorithm provides no opportunity for attack, other than brute-force.

The kind of security you're advocating, commonly called security through obscurity, is an almost sure-fire way to fail.

The likelihood that any non-expert would be able to single-handedly design a cipher which could withstand an attack by, say, the NSA is vanishingly small. The likelihood that your algorithm contains obvious, glaring flaws is enormous. Even if you never tell anyone your algorithm, the likelihood that these glaring flaws will be found and exploited by simple ciphertext analysis is very high.

BTW, I am a cryptologic technician (maintenance) for the Navy, so although not up to the 'expert level of training' you refer to. I am certainly
qualified to offer a suggestion.

Shall we be honest? The comments you have made in this thread indicate you know virtually nothing about cryptography. You don't even know the vocabulary, or the major conclusions. I don't care if you work for the Navy, swapping boards out of computers used for cryptography or whatever -- you're definitely not qualified to develop secure cryptosystems. (Nor, for that matter, am I.) Sorry to burst your bubble.

- Warren

 

[Irresistible_Force]

Of course it's a word. Have you ever, say, read a book on cryptography? Yes, I have. You want me to Fedex them to you?
The point was, just because a term is used colloquially among a group of people does not make it a word by definition. Hootnanny is not a word, but I'm sure a lot of people know what it means. I was pointing out the fact that earlier you insinuated that I was offering a dumb idea to the orginal poster, even though you were not using correct terminology yourself.
While it is possible that NSA already has cracked every modern cryptosystem, most mathematicians believe that at least a few existing cryptosystems have no corresponding cryptoanalytic vulnerabilities, meaning the only known attack is brute-force. These algorithms use keyspaces so large that the mean time to find a key with existing computing hardware is longer than the age of the universe. Of course, this doesn't mean the key won't be found in thirty seconds, but it's highly unlikely. It's also possible that Uncle Sam has alien quantum-computer technology, but, again, it's highly unlikely.
Again, you offer no solution to the question posed by the original poster, You merely reiterate the fact that any cipher of quality must have complex keys generated by algorithms. Duh! At least I offered a suggestion that might help the poster remember the original reference he was seaching for. What have you done to assist the poster? Nothing. You state the obvious and then pick on the only person that even offered to help.


However, this is exactly what the original poster asked for.
Still not seeing how your solution (or lack of one) has helped the poster at all. Your only picking apart my statemenst like someone who can't let go of Debate Club habits.


This is quite likely the dumbest thing you've said in this thread -- even dumber, perhaps, than suggesting that cryptosystem is not a word. You are wrong. I can splice two words together whenever I want, they still don't become a word just becaus of it's colloquial use. Additionally, do you really feel so threatened that you have to resort to calling me 'Dumb'? I've plainly admitted that I am no professional cryptographer, though I am sure my credentials in that area suffice to allow me to offer a suggestion in a public forum. Point of fact, the most secure ciphers are those that are publicly scrutinized by tens of thousands of professionals, and corrected so that they contain no "bugs" that could be used for cryptanalytic attack. An algorithm that is known to contain no flaws is one whose security depends only on the key. If no one has your key, such an algorithm provides no opportunity for attack, other than brute-force.

The kind of security you're advocating, commonly called security through obscurity, is an almost sure-fire way to fail.
Depending on his application. The poster merely said 'Adversary' in the same room. Given enough time, ANY cipher can be broken, like you pointed out. But the for the application suggested, I imagined him in a room with some other person that he did not want to view his writings. Perhaps he was thinking of encrypted crib notes for one of his classes? We never got that much information from him. But based on what he DID say, at least I offered a suggestion. Not you. You can only spend your time criticizing others, only illuminating the fact that you have no tact and are not a people person at all. I just hope you are not a teacher somewhere, I would feel badly for your students.
The likelihood that any non-expert would be able to single-handedly design a cipher which could withstand an attack by, say, the NSA is vanishingly small. The likelihood that your algorithm contains obvious, glaring flaws is enormous. Even if you never tell anyone your algorithm, the likelihood that these glaring flaws will be found and exploited by simple ciphertext analysis is very high.Again, he never said the cipher had to withstand NSA scrutiny. He plainly said 'Adversary'.



Shall we be honest? The comments you have made in this thread indicate you know virtually nothing about cryptography. You don't even know the vocabulary, or the major conclusions. I don't care if you work for the Navy, swapping boards out of computers used for cryptography or whatever -- you're definitely not qualified to develop secure cryptosystems. (Nor, for that matter, am I.) Sorry to burst your bubble.
I am well aware of the vocabulary, I just chose your colloquialism to make a point. At the moment I am serving a tour as a Naval Instructor for the Cryptologic Maintenance Technician course. This is where we teach them the job. I wasn't even attempting to develop a secure cryptographic system. I'd need an engineering degree for that. I was offering the suggestion of a cipher that the original poster could do in his head, to keep an 'Adversary' in the same room from reading what he was writing. What did you offer? Nothing, save personal attacks against the only person even offering a suggestion. Do you feel so inadequate that you have to pick on other people to make yourself feel smarter or better than everyone else? My IQ is 132, so , I am no Dummy as you insinuated. Neither am I a genius however, between the two of us, only I offered a useful suggestion to the original poster.
- Warren

I will not waste any more time or effort to reply to you. I will only feel as though I have to defend myself even further from someone who has not even bothered to produce any credentials as to his expertise in the matter other than personal attacks and hot air. I thought I had found an enlightened forum here in Physics Forums. I guess I was wrong.
-click-

 

[chroot]

You've got to be kidding me, kid.

The point was, just because a term is used colloquially among a group of people does not make it a word by definition. Hootnanny is not a word, but I'm sure a lot of people know what it means. I was pointing out the fact that earlier you insinuated that I was offering a dumb idea to the orginal poster, even though you were not using correct terminology yourself.

1) Hootenanny is a word. You just didn't spell it correctly.

2) The word "cryptosystem" is also a word, one used by virtually everyone in the field of cryptography. How on Earth is it not "correct terminology?" As has been pointed out, many hundreds of papers have been published with the word "cryptosystem" in their titles. The most popular books in the field -- which you claim to have read -- use the word hundreds of times each. The fact that you didn't know the word is just additional testament to your laughable ignorance of the entire topic of cryptography. Why don't you just stop while you're ahead?!

3) Your attempt to discredit me by attacking my use of a word indicates that you really just have nothing more useful to say about my arguments.

You merely reiterate the fact that any cipher of quality must have complex keys generated by algorithms.

I never said that at all. Work on your reading comprehension.

I just hope you are not a teacher somewhere, I would feel badly for your students.

I just hope you're not a student somewhere, I would feel badly for your teachers!

I just chose your colloquialism to make a point

What point was that, exactly? The point that you have no idea what you're talking about? What you just did is the equivalent of walking into a room full of neurosurgeons and trying to one-up them by telling them the word subfornical is not in the dictionary, and thus isn't a word. Who the hell cares what you think is or is not a word? Again, your ignorance of this extremely common term just illuminates your level of understanding.

I have to defend myself even further from someone who has not even bothered to produce any credentials as to his expertise in the matter other than personal attacks and hot air.

I wasn't the one who started busting out credentials, kiddo. My statements stand on their own; I don't have to explain to anyone that I repair Navy computers () to try to prove I know what I'm talking about. If you're interested in credentials, however, I have a BSEE from Virginia Tech, am nearly done with an MSEE at Stanford, and am a senior integrated circuit designer at a Nasdaq 100 corporation in Silicon Valley.

I thought I had found an enlightened forum here in Physics Forums. I guess I was wrong.

Don't let the door hit you on your...

- warren

 

[ATruePyRo]

I liked the topic, although this thread has likely gone the way of the dinosaurs

I think that there is a strong recreational component to the practice of mental cryptography. It can be made quite mathematical, however it's truthfully just heaps of mental algebra. Nothing too fancy that I know of can be put to work in realistic, reliable mental cryptographic algorithms -- this makes sense as the heart of any cryptographic system is based on computation and calculus or high order exponential/modulus mental gymnastics seem trivial when passing notes among friends.

Obscuring a message can be easy, either through encoding or processes of enciphering. Encoding could be used to turn known symbols into coded symbols via some agreed upon translation system. This too can be algorithmic if the original message could be converted into numerical forms. While this may seem to be a difficult proposition for words, letters can be mentally represented numerically and manipulated as if in an ordinal system. Friends of mine will sometimes use a different number base to encode messages, I call the system Base 3.

Base 3 method for coding messages:
--first, an overview - there are 26 letters in the alphabet and a space character required to communicate messages at the word level without punctuation. In Base 3, three symbols (represented here as 0,1,2) can be grouped in blocks of threes (000, 001, 002, 010, ...) to represent all numbers from 000 to 222 with an astounding range of (you guessed it) 27 values. Allow 000 to represent a space, it seems easy enough to remember because it is effectively NULL. 'A' is 001 and 'Z' is 222. Go to town with it, you'll develop your own mnemonics and mental automata quickly takes over to make the process painless.

Primary benefit of Base 3: fun
Secondary benefit of Base 3: It functions as a data set and computationally-based mnemonic system for retaining information on the value attributed to letters in the english alphabet. "m is the middle of the alphabet, its base 3 representation is 111, 1*(3^2)+1*(3^1)+1*(3^0) is 9+3+1 or 13. therefore m is the 13th letter and m=13." or "If r is 200 in base 3, then 9*2 is 18 so r = 18."

The possibilities are finite (there are 26 letters, complete knowledge of base 3 takes minutes to acquire, hours (at most) to attain some reasonable degree of proficiency.).

Suggested system for mental cryptography:
Implement a polyalphabetic cipher, even a few characters produces results that Edgar Alan Poe would have found troubling.

I've protected a few notes in my journal with a coded key. I used a 4 digit composite number, say 1918, which can be easily factored as 2*7*137, and concatenated the digits to form 27137 and sequentially iterated through the digits (allowing the pattern to repeat throughout the duration of the message) to additively translate every character in my message.

"A MESSAGE" thus becomes "C TFVZCNF" (I applied, +"2 7137271").

Thus, 1918 can be used to decode the message if received by a compatriot.
(Protecting individual privacy is a patriotic act and a constitutional right!)

Let's send the message to a hypothetical friend and consider the thought process:
"C TFVZCNF" ... let's see, 1918 ... that's 2*959, and 959 is 910+49 or (130+7)*7, so 2*7*137 is 1918, which gives 27137 as my key! Now, C-2, A. T-7, that's 20-7 or 13 and 13=M. F-1 is E. V-3 is 22-3 or 19, 19 is 201 in base 3, which is S, therefore 19=S. Z-7 is 26-7 is 19, so S. C-2 is A (again). N-7 is 14-7, which is 7 which is G. F-1 is E. That spells "A MESSAGE" I just received "A MESSAGE" from my friend protected by a polyalphabetic key encoded by the number 1918!

Unfortunately with the above system, the range of possible values the key can translate the original message is confined to 0-9 unless new rules are applied. The above system was intended as a proof of concept, namely polyalphabetic (or vigenere) ciphers can be done mentally, I hope this message is received by at least one person who finds this post meaningful.

This was written as a stream of consciousness, and I hope any errata lingering in what I have written will be forgiven.

Regards,
James

 

[CRGreathouse]

I think it was Neal Stephenson's Cryptonomicon that had a modestly secure cryptosystem using playing cards explained in an appendix. A videotape of you 'shuffling' the cards would break the system, but the cards themselves (which carry the ciphertext at the end) could be found without compromising the system.

Of course a deck of cards has only 225 bits of entropy, so I guess it depends on how much information you need to convey. That might be 45 characters without compression -- and doing compression, even simple compression, in your head would be tough.

 

[chroot]

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.

- Warren

 

[ATruePyRo]

I appreciate the responses and was surprised by their rapidity. I am human and fallible, so please forgive any errors in judgment or knowledge. Mental cryptography is something of which I'd like to improve. I hope this post is both useful and appropriate.

Side note: Neal Stephenson is one of my favorite authors. I highly enjoyed Snowcrash, Interface and Cryptonomicon and I am yearning to read Diamond Age.

--back to ciphers-- (particularly as they apply to mental cryptography.)
''WARNING'' I speculate.

It's really all about keys. For a moment, let's consider an isolated cipher that is equal in length or shorter than an arbitrary, private key. All messages protected by the cipher would be completely obscured by the possible entropy of the private key.

E.g., given a 20 character message and a 30 character key produced using ideally randomized symbols. Assuming that each symbol represents a number which can be applied to the original message via additive or subtractive process, the effective values of each symbol fall within the range 0 through 25 (via mod 26). The effective length of the key is 20 because the effect of the key's entropy beyond the length of the message isn't present. I recognize that the conditions are constrained in this hypothetical, but I think these constraints are suited to best describe my message to the forum.

When I've encountered cryptoanalysis in my reading, frequency analysis and index of coincidence rely on natural biases in letter frequencies and combinations which are language dependent. Therefore, systems that detract from the natural quality of the original message could possibly be employed to help thwart these types of attacks. A scrambling algorithm could effect index of coincidence analysis on its own, however without further effort frequency analysis wouldn't necessarily be effected. (It would presumably be more difficult to apply frequency analysis on enciphered text that is scrambled.)

An enciphered message that undergoes data compression is both enciphered and encoded, and if a compressed, enciphered message were found and treated as a simple polyalphabetic cipher then encryption would probably be curiously difficult to break. As an arbitrary, made-up metaphor, you could liken it to searching for birds by digging up gopher holes. All the work trying to break the cipher would lead you away from meaningful decryption which would first involve decompression (and thus decoding/formatting to allow the iterative application of the cipher key).

The strength of a cryptographic system does not have to rely on sheer complexity if the situation can be reasonably controlled. If a highly randomized key can be selected for limited use, say on an assignment infiltrating the den of an adversary, then as previously described, a simple cipher can completely obscure the original message up through the length of the key with increasing vulnerability as the key is allowed to cycle. Frequency analysis of data is only possible with keys that are relatively small in comparison to the length of the data.

Overlaying a combination of keys with relative-prime lengths could create an effectively much larger key using less information. The resulting key will contain patterns I find reminiscent of auditory beat-phenomena created when differing tones are superimposed, however a cipher's strength in protecting finite data does not increase linearly with the length of the key used to protect it so the key-inflation effect might provide increased support.

I think that an ideal cryptosystem should best fit the scenario in which it is needed; this is seemingly relevant in mental cryptography where computational resources are limited. There really shouldn't be a one-size-fits-all solution because any truly secure system involves an unrealistic amount of complexity and human humility must be taken into account. If you wish, blame God for the limitations of man. I think that a pragmatic system would have to be devised to mediate the computation process, 'humanizing' the computation by applying heuristics in order to exploit the necessary complexity required for cryptographic security.

In the limit, the most pragmatic means of securing the information could very well be the use of charm, stealth and unmarked manilla envelopes which never leave the carrier's sight. Secrets can't always be guarded by ciphers. 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.

 

[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.