typodupeerror

## Encryption by Hand?77

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...
This discussion has been archived. No new comments can be posted.

## Encryption by Hand?

• #### Knapsack (Score:2, Informative)

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).
• #### update... (Score:1)

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.
• #### Use a code book! (Score:5, Insightful)

on Saturday March 30, 2002 @08:06PM (#3256952) Journal
1) Use a code book. Something with a concordence is good, though if you have the book in flat text you can easily make a concordence. Then you could write "fungal:17" to mean "staple" if "staple" (the word you intended) occured N words after (for some pre-agreed N) the seventeenth occurance of "fungal". There are a number of cute ways you could encode seventeen, and it's relatively easy to make N vary as well. Since this is "security through obscurity" you might as well have fun with it.

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

• #### Just use a one-time pad... (Score:2)

it's perfect for this sort of use.

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.

• #### Re:Just use a one-time pad... (Score:2, Interesting)

Prior to the availability of decent true and pseduo random number generators, a large number of books were published that contain strings of random numbers -- simply because creating such data was hard to do. Most decent universities, probably every single land grant university surely, will have such books. I know we do here. They've been long forgotten, but are an excellent source of truly random data. No need to do all the futzing around, just pull some data from the books.
• #### Don't do that!! (Score:3, Insightful)

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).
• #### Re:Just use a one-time pad... (Score:1, Funny)

by Anonymous Coward

No need to do all the futzing around, just pull some data from the books.

Nothing like a one-time pad that you can use over and over again... Hey, wait a second...

• #### Re:Just use a one-time pad... (Score:2)

Actually, the gov't (to the best of my knowledge, still does) use atmospheric noise. The other option would be SGI's Lava Lamp based RNG. They had a whack of Lava Lamps, would take digital photos, and automagically convert the bitmap into random numbers.
• #### Re:Just use a one-time pad... (Score:2)

I've also heard of people using radioactive decay for properly decent random data -- a la Hotbits. [fourmilab.ch] Apparently the Pentium III and P4 include a truly random number generator. I was impressed by this, but I'm not sure how the hell one uses it. It seems that most software still used pseduo generators. I suppose it takes additional work to call upon this feature. Here's what Intel said in a press release:
"Present software pseudo-random number generators still have a pattern that a very sensitive code breaker can ultimately detect and break the encrypted message."
• #### Intel RNG (Score:1)

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.
• #### OTP printed on a fruit roll-up (Score:2, Funny)

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!!!
• #### an alphabet wheel (Score:2)

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.
• #### Re:an alphabet wheel (Score:2)

Except that the original question asked for the "simplest, but most secure" algorithm. A simple monoalphabetic substitution cipher like you suggest is horrendously weak. The code puzzles in the newspaper are often harder than that.
• #### Re:an alphabet wheel (Score:1)

How about you take this idea, and then rotate the code you use. For example, the first letter is the key telling you which encryption to start with, say its T. So for that letter A is T, B is U, so on. Then the next letter / word, A is U, B is V, yadda yadda yadda. Keep that up and no one will care enough to figure it out (or decode it for that matter)
• #### ROTrandom (Score:1)

Use a random number generator that only uses a seed number. Use it to generate numbers that are used for how many steps the rotate the character around the wheel. The four secrets that need to be protected are the random number generator algorithm, seed number, character set sequence, and calculator make and model.

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.

• #### do-it-yourself one time pad (Score:5, Informative)

on Saturday March 30, 2002 @08:51PM (#3257233) Homepage Journal
For a non-public key stream cipher:

If you allow the addition of dice, say a d20 ...

Setup by the sender:

1. Generate a one-time pad by rolling the d20 and writing down the 1's digits (d20 face value mod 10).
2. Transmit the one-time pad in a secure fashion (use somebody's public key suggestion, hand carry, etc.)
Setup by the receiver:
1. Receive the one-time pad from the sender.
2. Store in a secure place.

To encrypt:

1. Convert each plaintext symbol into an alphabet of 100 values (00 thru 99).
2. For each plaintext digit, remove a digit from the one-time pad and transmit the sum mod 10.
3. Destroy the used digits of the one-time pad.

To decrypt:

1. Receive the cipher text from the sender.
2. For each digit in the cipher, remove the next digit from the one-time pad and subtract mod 10, from the cipher digit.
3. Convert the result, pairwise, (00 thru 99 alphabet) into plaintext symbols.
4. Destroy the used digits of the one-time pad.

Encrypt example:

1. Plaintext: Hello
2. One-time: 9690367034
3. Alphabet: 0730373740
4. Transmit: 9320630774

Decrypt example:

1. Receive Ciphertext: 9320630774
2. Receive One-time: 9690367034
3. Subtract mod 10: 0730373740
4. Convert to text: Hello

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.

• #### Re:do-it-yourself one time pad (Score:2)

I ask this as an honest question, just wondering if there's something I'm missing... why not a d10? Also, if you can reduce your alphabet to 20 letters (text is remarkably readable with w transmitted as uu, k and c collapsed, etc) you can avoid the modulus entirely. Just thoughts.
• #### Re:do-it-yourself one time pad (Score:2)

There is no such thing as a d10.

The thing about dice that makes them work is that they are Platonic solids, so that all the faces and vertices are shaped the same. If you had a 10-faced solid, some of its faces would have to be different shapes.
• #### Re:do-it-yourself one time pad (Score:2)

There is no such thing as a d10.

Really? Well, in the off chance that you're not joking, I provide you with this link [chessex.com], which has pictures of mroe than a few. Now, to my mind (looking at a few of the d10's that I have) the various faces do look the same, so I'm not sure where you're coming from.

• #### Re:do-it-yourself one time pad (Score:2)

Oh, I see.

I was wrong, then - a die does not have to be a Platonic solid. On a d10, the corners are not all identical (the top and bottom are very obtuse angles) but this just means they're more likely to stay in whatever half of the die is up when it hits the table. Since that should be random anyway, the die works.

Thanks for pointing that out. d10s look neat.
• #### Re:do-it-yourself one time pad (Score:2)

There are also platonic-solid d10's available; they are 20 sided, but list each number twice.

you can make one yourself semi-trivially by taking a standard D20 and striking out the high digit whenever present :)

• #### Re:do-it-yourself one time pad (Score:2, Interesting)

Actually one time pads where used a lot by the government (English, American, etc) a few years ago.

Typically you have a person sitting at a bingo roller thingy... who pulls out letters at random.
These random letters are then written down on a big peice of paper as a one time pad.

A copy of this is given to the person who needs to send data, and a copy is given to the reciever.

The person doing the encoding takes another peice of paper and every three lines writes the pad down. (Maybe the paper with the pad it self had two lines between each pad sequance... I dont remember hehehe)

On the second line is the message...

on the third line, you do a bit of addition mod(26) (Actually I believe they left out a few letters to make the msg easier to read...)

The person then writes their message under the pad sequence. So you might have something like this:

a=1, b=2, c=3...

(note, I am just hitting keys, replace with a real random sequance)

ahfxd adbgf ewefg hzqdf wrhwd wrghl
thisi sthem essag etobe sentx xxxxx
upoqm txjls jpxgp mtffk pwv........

so
a + t = 1 + 20 = 21 = u
h + h = 8 + 8 = 16 = p
etc etc

Urgh... my ride is here so I have to take off... but you get the idea. I might have mad a few mistakes in this post because I did the entire thing in a bit of a hurry.

A good (and really fun) book to read is Cryptonomicon. Its based in two timelines and during the story it talks a lot about cryptography. Quite a good book.

Anyways, sorry I could not finish the post. Good luck
• #### Even better, use a Q20 (Score:4, Funny)

on Sunday March 31, 2002 @12:00AM (#3257984) Journal

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

• #### Re:Even better, use a Q20 (Score:2)

I mod you +1 Funny in the slashdot moderation system of my mind. Too bad that's too long for a .sig.
• #### Soviet Encoding Technique (Score:2)

The Russians used a clever technique to convert text into numbers before encrypting with the OTP.

They used a table like this:

..0123456789
..ETAOINSH
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

• #### Search the literature (Score:2)

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.
• #### Re:Search the literature (Score:2, Interesting)

One of the most popular pre-WWII ciphers was the Playfair Cipher [carleton.edu]. Very simple, just know the code word of the day.
• #### Not such a good plan (Score:2)

The ciphers used before WW2 were in general pretty weak. We could deploy better ones now, just because we understand the subject better.

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.

• #### It'd be difficult, but... (Score:2, Interesting)

What about ciphersaber [gurus.com]?
• #### Gödel Incompleteness Theorem (Score:1)

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 [wikipedia.com] 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]
• #### Re:Gödel Incompleteness Theorem (Score:1)

Therefore all Natural numbers are interesting.

How interesting.

• #### Re:Gödel Incompleteness Theorem (Score:1)

Okay, now I am a complete math geek, I am reply on slashdot to point out a possible flaw in a math joke...

You seem to be using one of the standard proofs for math induction. Or using math induction implicitly. Lets say n is the where the only interesting property it has is that is it is the smallest non-interesting number. Now you move onto m where n This is a known problem with set theory, and why classes were invented. No I don't know the difference. But basically you have constructed a self referential set, which of is the common source of logical consistance issues. This is very similar to the barber problem. The barber shaves all people who don't shave themselves. Well, if the barber doesn't shave himself implies he shaves himself. ( A implies not A. The pain the horror... cats and dogs living together.... choas and madness). I know there is a resolution to the issue, but I have never read up on it.

And for my next trick I will prove to you it is in your best interest to give me all your money.

• #### Re:Gödel Incompleteness Theorem (Score:1)

I know there is a resolution to the issue, but I have never read up on it.

Simple. The barber's razor dies before he gets to himself.

• #### Re:Gödel Incompleteness Theorem (Score:2)

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?
• #### Re:Gödel Incompleteness Theorem (Score:1)

Method still one is self referential. Although it is getting closer I suppose. The i'th element in the set moves, because you shift the elements out of it and into the other set as you start to execute the definition of the two. It is precisely the barber problem, on a slightly different twist.

The second one is while not exactly referential, is well useless. The Universial set has a description, which makes the definition of "interesting" pretty much useless. Because all numbers must be in it. This is like the idea that you should be able to do all geometric proves by replacing the words "point", "line" with the words "beer", and "chair". And the proves to work. The problem replace the word "interesting" which isn't very well defined, and replace it with "uninteresting" and the prove works just as well. Replace it with "not a number" and it works. Sorta like the quote about a "rose by any other name is still a rose".

Among other problems, the definition of "interesting" leaves something to be desired. It literally is meaningless in this context. There is no definition of interesting that isn't self referential yet.

• #### Re:Gödel Incompleteness Theorem (Score:1)

which is why (like I said earlier) it has no use other than 5 fleeting seconds in an intro class - which is much much shorter than we have spent discussing the minutia
• #### Re:Gödel Incompleteness Theorem (Score:1)

If the minutia isn't right, the math is wrong... See Godel's Incompleteness Theorem.

There are lots of things that look right in mathematics but aren't. Try doing the integral using rectacular cordniates to figure the area of the circle. Comes out 4 * pi * pi * r * r. If I remember correctly. It doesn't work, because that minutia isn't correct. Ahh, to harken back to the days of my real number analysis.

I promise no more replies

• #### Re:Gödel Incompleteness Theorem (Score:2)

No, the proof as it is stated is valid. While self-referential sets can be troublesome, that is not the problem here. The problem is of course the loosely defined notion of "interesting numbers". And in that regard, the conclusion that all naturals are "interesting" is not really surprising. I'm sure a real mathematician like Ramanujan [wolfram.com] would quickly find an interesting property to any natural, such as: 478394739274019283740192837409128376354342

On the other hand, I can't...

• #### Re:Gödel Incompleteness Theorem (Score:1)

Nope, they invented a whole new kind of object to solve the problem. You refer to classes not to sets when constructing a set. You do not refer to a when constructing a set. Don't make me dig up my Abstract Algebra reference, it always makes my head hurt. It causes mathimatical inconsistancies if you allow self referential sets. So they aren't allowed. If you allow self referential sets, it is easy to prove that you should give me all your money, and that the square root of two should be not only rational but a whole number.

And yes interesting is a very poorly defined term too. That is part of the problem.

KIrby

• #### Re:Gödel Incompleteness Theorem (Score:2)

Except that this set of interesting numbers is not self-referential. It is a proper subset of the naturals, and therefore cannot include itself. And the same can be said about the barber paradox.

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 [fau.edu], agree to mean the same thing as I=N.

• #### Re:Gödel Incompleteness Theorem (Score:1)

Pretty clear you know more set theory then I do. I didn't introduce the assumption B=P\S, that is the definition of the set (I know it isn't a well defined set). I had been taught in the past that this was a simplified form of the problems that forced the construction of classes, and that whole realm of theory about sets. Basically, it was that sort of construction that lead people to figure out the problems with it. Similarly to the fact that essentially Godel's Incompleteness Theorem revoles around roughtly the statment:

This statement if false.

They use to have a version set theory way back when, and it did not involve classes, and nothing in the definitions said that the barber's paradox wasn't a set. It isn't a paradox now, but it use to be one. It was a set by the former mathematical definitions. It was in fact a set that contained a contradition. You know how contraditions bother mathematicians so they went and constructed a new version of set theory, so it couldn't contain such problems. And there was much rejoicing in the land of the set theory gods. I don't have any books on set theory from the 1800's so I can't really double check that.

I mean self-referential, in the sense, that once you decide the state of an object, that affects the state the object is in. That is a problem with the barbers problem. I suppose recursive-like or some other adjective would have been more appropriate. Essentially there is a feedback loop in all of the definitions. The nature of the problem changes after each iteration of the definition, which is the problem.

I just assumed the definition of Interesting is x is a member of I if x is a member of the primes or x is the smallest number not in I.

Hence self referential. All this is what they taught me in College, Dr. Konvolina vould be proud I remembered all that.

Kirby

• #### Re:Gödel Incompleteness Theorem (Score:2)

I am certainly no set-theorist either, so you should probably ask Dr. Konvolina again about these things if it becomes unclear (or the horror: I've been wrong). But I have worked for at least a year with logic and formal systems, and mostly found out that those people who actually make progress there, are way smarter than me...

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.

• #### Re:Gödel Incompleteness Theorem (Score:1)

Okay, I am a sucker...

And we are incredibly off topic, but it is interesting...

B=P\S is currently a statement in logic. The english description of it, formerly was a "set". Prior to the current classes based definitions you could have stated the set of all sets, and other such nasties. The use of classes was to allow to define useful sets that do useful things and have them have known properties. The former formulations of sets allowed things like the set of all sets, the formulations including classes don't. Classes were introduced, specifically to allow you to construct the set in a well defined manner. They allow you to formally state that the set of all sets isn't well defined, and isn't a set. Prior to that, it would have been a legitimate set to use. This avoids lots of issues.

There is one significant difference between my definition of I, and the standard binary tree. The binary tree doesn't refers to unknown parts that aren't based on other parts of itself (actually your definition doesn't explicitly state that, but it would be a graph not a tree then).

Is 4 in I or not? Well yes it is. Is 6, not on the first iteration. Would be on the second. But if 6 is in there, then then 4 shouldn't be ( it isn't prime and you claim 6 is the smallest number not in there). Attempting to apply the definition inductively doesn't make sense. If 6 is in, then 4 shouldn't be.

The definition isn't an infinite intersection where you define I sub k to be I sub k - 1 plus the smallest element not in I sub k - 1. Let I be I sub infinity. I sub 1 is the set of all primes. Okay that is a fine set, and not at all confusing.

Now of course I just moved from informal to formal on you, and then claim you're legitimate observation isn't right. Just not quite what I was getting at. To me the original definition I gave for I is similar to the set of all sets with the nature of problems it provides. While constructing it, it would change a bit on you. I don't like that. It isn't very handy. Now all this might be exactly what you meant by a formal definition. Just attempting to use induction on the original definition doesn't make sense at all to me. This uses recursion in the construction, and so it is fine by me. Splitting a hair, I know, but that is what a lot of mathematics is all about.

It isn't clear to me that if 6 is included that 4 should be with the original definition, it's not a prime, and 6 is supposedly the smallest element not in I. Definitions which move are odd. Which makes it similar to the problems with the barber problem. There is nothing about a tree that has that sort of issue. A tree's definition is independent of it. Just because a 4 is over there in the tree, doesn't induce a 6 in this part of the tree. That is what I find odd.

Interesting discussion. Don't use the math background very often.

• #### Re:Gödel Incompleteness Theorem (Score:2)

No: B is already defined. P\S is already defined, it contains all the elements of P except those that are in S. Saying that the two sets are equal is not a set, it is an equation. An equation is a statement of logic, and can be either true or false.

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

• #### Re:Gödel Incompleteness Theorem (Score:1)

See, here section 2.3. The describe the original drive for classes. From what I can gather in a quick reading. A class can be a something that isn't a legal set. That is fine, in fact they have a special name, proper class. So you can have classes that behave badely, but the sets constructed from them behave well. If only human offspring worked that way...

Axiomatic set Theory [www.ltn.lv]

• #### Re:Gödel Incompleteness Theorem (Score:2)

Thanks for the link, but unfortunately it didn't clear much up. I think we both knew that a class was a (ill-behaved) extension of set. Now, what I was wondering about was for what reason they existed in the first place. If they only have historical value, then it seems kind of stupid to keep them around. ZF-theory doesn't seem to need them, and almost all of mathematics can be reformulated in ZF-theory.

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.

• #### Why? (Score:1)

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...
• #### Re:Why? (Score:1)

Nothing so interesting - I was reading a document on an algorithm [dogma.net] that allows you to order the text such that it can be restored to it's original order - however, having it more sorted increases compression ratios dramatically. It occurred to me "hey, you could to this by hand", and it got me thinking on secure encryption by hand...
• #### Characters in spy novels always want to do this (Score:2)

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.
• #### Cryptonomicon ... (Score:2)

... 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.
• #### Matrix Encryption (Score:1)

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?
• #### Re:Matrix Encryption (Score:1)

This is a Hill cipher.
C = AP (mod 26)

P = A^(-1)C (mod 26)

where A is an n*n matrix with inverse A^(-1), P and C are n element vectors consisting of plaintext and ciphertext characters respectively, and gcd(det A, 26) = 1.

It's more difficult to break than say a Vigenere or Caesar cipher since the value of the cipher characters depends on the character(s) next to it in the plaintext. But it's nowhere near unbreakable with small n.

• #### AES (Score:2)

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.
• #### Do you want it to be secure if so, none exist (Score:1)

A one time pad might possibly be an example of the only shot at a secure example. Pretty much any other key based one is doomed. If you can do it in with pen and paper in a reasonable period of time, I can brute force the entire key space in no time flat. This is why they rate security systems in terms of time. If you want it to be secure, it had better be computationally time consuming, or I will just try all the keys and be done with the problem.

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.

• #### Re:Do you want it to be secure if so, none exist (Score:2)

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.
• #### Re:Do you want it to be secure if so, none exist (Score:1)

I agree with Bruce Schiner's assessment. It isn't secure if you're relying the the encryption algorithm to be secret. When I say secure I don't mean in some petty practical sense. I spent entirely too much time in theory based math classes.

The other issue with the "SNaRFt" example, is that well, either there are a finite set of choices that are only in human heads, which makes it nearly impossible to break. It also is a heck of a lot less useful. I can't say do it at 10:30PM unless there is some mechanism to translate SNaRFt into times, or that happens to be one of the finite set that a human can remember. While the mechanism you're talking about is sneaky and sly. Just ask the Germans and the Japanesse about how well sly works. They did both during World War II.

I'd much rather have an algorithm that is inheriently strong. So strong that I can give you plain text and ciphered text sets using the key I plan on using to transmit that I don't want you to read. As many as you'd like. I can give you the algorithm to go from the plain text -> cipher text. Then give you the mathmatical proof that it is strong, and describe all the known variations of the algorithm and the known weakness of the algorithms. Describe the key generation, and describe the set of weak keys. Then I can give you the schematics for hardware based encryption/decryption for it.

After doing all that, I want to be able to still have you have to be lucky to get it early in the keyspace search, otherwise the heat death of the Universe will happen first. Then and only then would I feel secure.

If you want to break those other schemes you describe. Hire a good looking woman or man to be a double agent, to sleep with somebody on the other end. You can find a surprising amount of information out that way. Capture and beat up the guy who knows what the algorithm is. Then the rest is trivial. Hire 10,000 really smart math people to be smarter then either you or I to work on it. I belive that is roughly the US gov't approach with the NSA.

• #### Pen and paper methods can be secure (Score:2)

For example, almost all SSL web browsing is secured by RC4-256 encryption and there are no known breaks for that. You could do RC4-256 with pen and paper (well, pencil and paper and eraser) pretty straightforwardly, though RC4-100 might be easier (and possibly less secure, though again there are no known useful breaks).

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.

• #### Re:Pen and paper methods can be secure (Score:1)

Not breakable, maybe but that doesn't mean they are secure. RSA doesn't have any breaks with using a 2-bit key either, it just so happens, I have to decrypt 4 times and I will have the original plain text. It just so happens that I can brute force the entire keyspace in very little time, but I didn't find a backdoor. I didn't apply some kind of cipher analysis on it, but I got the plain text all the same. dnetc, isn't attempting to break RC5 by some cryptographic attack. It is instead attempting to brute force the keys by by trying all of them. If you can do the encryption, and more importantly the decryption by hand, a computer can do it probably 5-20 orders of magnitude faster then you can.

I am not familiar with the Solitare algorithm, I haven't ever read up on it. All the encryption schemes I have seen so far have a function D which takes the cipher text, and something other parameter to decrypt. If that other parameter is finite, plain text can be found, it is only a matter of time. I know D, I have cipher text. Bruce Schneier claims you aren't secure if you have to hide D. If you have to hide the cipher text, you might as well send it in the clear. If you use that same parameter repeatedly, like say in Public Key encryption, then I can break it over and over again, paying the time penalty once hence people want to make the penalty incredibly high buy using very large key spaces. If you use a one-time pad, I have to use that pently everytime I want to break your encryption so it is harder.

Hmm, and I thought RC4 did have problems. I'll have to go ask about that.

• #### RC4 (Score:2)

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.
• #### RC4 (Score:3, Insightful)

on Sunday March 31, 2002 @06:06AM (#3259355)
Check the RC4 algorithm, which normally is done on a 256-element vector so we'll call it RC4-256.

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.

• #### Re:RC4 (Score:2)

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.

Which is a nice, secure approach as long as you don't want to decrypt the messages afterwards... =)

It's important to remember that there have to be two copies of a one-time pad in order for it to work: one copy encrypts the message, the other copy decrypts it.

• #### one-time pad (Score:2)

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.
• #### Do it the Russian way... (Score:3, Informative)

on Sunday March 31, 2002 @06:56AM (#3259520) Homepage
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.
• #### That system is still breakable (Score:2)

That's called a book code and it's still breakable, because different letters in the words in a book aren't randomly distributed. See Kahn's "The Codebreakers" for more info on how to break these systems. Ken Follett's spy novel "The Key To Rebecca" is also about breaking such a code.

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 [simonsingh.com] 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.

#### Related LinksTop of the: day, week, month.

You know, Callahan's is a peaceable bar, but if you ask that dog what his favorite formatter is, and he says "roff! roff!", well, I'll just have to...

Working...