16
I thought about this and have done a bit of research, and the answer is no.
The problem is the gap between the difficulty of factorisation versus prime generation isn't really large enough at the scale of primes/moduli we can work with.
By 1588 the largest prime discovered was 524287, thanks to Pietro Cataldi. This was a prime generated by a single person's ...
13
There are techniques for doing online surveys on sensitive subjects. They don't follow the approach you outlined, but here's a sketch of how they work.
Suppose we want to survey people to determine how many people have ever seriously considered suicide (say), but we suspect many people might be unwilling to answer honestly because of the stigma associated ...
11
"Strong enough" is a broad term. Some things that you need to keep in mind are entropy size and cryptanalysis. "Strong ciphers" are ciphers that have shown to have enough entropy to withstand practical attacks over time from public scrutiny.
With that said, the Solitaire cipher has a keyspace of roughly 238 bits. By comparison, many SSL keys on the internet ...
9
This requirement is a killer:
The paper (or any medium other than the brain) must not at any time contain data that leaks information about the plaintext.
Almost any security proof for a hash assumes an adversary only gets to see digests, not any mid-state. Mid-state has not had enough confusion and diffusion, so it leaks information.
This means that ...
9
One option would be to get them to select a one-time MAC of the form:
$mac(m,k_0, k_1) = (k_0 \times m + k_1) \mod p$
You would select $p$ to be something like 29. $k_0$ and $k_1$ would be chosen at random from the values 0-29. $k_0$ has the additional restriction that it can't be 0.
You can aid the computation by giving them a 29x29 matrix of all ...
8
Of course, it strongly depends on what exactly you mean when writing “casual person”. The cipher algorithm works similar to a shift cipher. As long as the attacker does not know the original order of the cards (of one or more decks of cards), then the cipher should be close to being unbreakable for a “casual person” – assuming that that casual person is ...
7
You are not likely to find such a construction. One problem you will run in to is that of size: In order to be secure against brute force search with Grover's algorithm, you will need to use at least 200 bits of secret material. And that assumes you are content with a security level of $2^{100}$.
This is equal to 25 random bytes or a 60 digit long decimal ...
7
Probably the easiest way to do finite field multiplication by hand is using discrete logarithm and antilogarithm tables. For example, here's a pair of such tables for the AES field (using 3 as the base), generated using this Python code:
log| _0 _1 _2 _3 _4 _5 _6 _7 _8 _9 _A _B _C _D _E _F
---+------------------------------------------------
0_ | -- 00 19 ...
6
Check out Manuel Blum's human computable hash function. He calls it HCMU for Human Computable Machine Unbreakable.
He claims you have to spend an hour memorizing the technique and then you can apply the has function in about 20 seconds without even using pencil and paper.
The memorization required is to remember a random mapping of each letter of the ...
6
I still don't understand your desire for a hash, especially considering (as already stated at other places in this forum) that you don't gain any entropy by subjecting a PW
to a deterministic function like a hash. So, when decrypting your ciphertext, you will be as secure with a H(key) as with (key), thus you might as well just memorize a good long ...
5
You can try NSA's CryptoKids page (archived here). It's been around for some years and the ciphers have varying difficulty so you might at least get some ideas.
Alternatively you can use plain XOR encryption with a twist: Encrypt multiple consecutive letters with the same character. For example, if $|m|=n$ then $|k|=n/4$ and do $c_i,...c_{i+4}=k_i \oplus ...
5
Perhaps you could do something with Visual Cryptography.
Maybe something like:
Gather a few low-resolution images (symbols or short text phrases), perhaps a few more images than you have kids
Use visual cryptography to split each image into 2 random-looking images, and print each random-looking image on its own piece of transparency paper
Shuffle the pile ...
5
Any set of $N$ distinguishable objects can be permuted in $N!$ different ways, thus giving you the ability to represent $N!$ different keys, resulting in a representable keylength of $\log_2(N!)$ bits. For $52$ distinguishable playing cards, this would be $\approx 225$ bits.
However with the additional property, that each object can have two distinguishable ...
4
You could challenge them to devise low-tech, physical zero-knowledge proofs (of knowledge) for games like "Where's Waldo?" and Sudoku, then show them some methods that really work and why. I've done this before with high school CS students and they seemed to really like it.
For "Where's Waldo?" one can prepare a large sheet of paper (at least twice as big ...
4
How about using something similar to Zobrist hashing and generate the look-up table by coin flips?
Let's say you want to commit to a 64-bit integer and you are able to deliver the look-up table in person and later communicate a 256-bit hash.
Flip the coin 256 x 64 times, with 2 seconds / flip it takes 9.1 hours so you might not want to do it every day :) ...
4
I don't think RC4-based constructs were mentioned yet, it would be fairly trivial to implement with a deck or two of playing cards or self-made cards. It has only modular sums and swaps, and only two state variables i and j :)
It is known to be weak but shouldn't be crackable without a calculator.
Edit: Yes, the message would be used to seed the cipher and ...
4
No, there aren't any cryptographic hash functions like this. I'm pretty confident you're not going to find one. I have yet to see a white-box secure hash function that remains secure against dedicated attack, let alone one that you can implement securely on pencil and paper. Since this is a practical problem, I suggest finding another solution -- like ...
4
A Michael Kjörling notes, what you basically have is a monographic substitution cipher. These are generally easy to crack using frequence analysis; for example, if we know that the underlying text is in English, we can be fairly sure that the two most frequently occurring symbols correspond to the letters T and E (and that any symbol that occurs unusually ...
4
The question relates to the amount of information that can be encoded within a standard pack of cards. The cards can be face up or face down. It is reasonable to assume therefore that they can also be rotated as in reality, who arranges a deck so that all the hearts are the right way up?
You would have to decide out of band what the interpretation of the ...
4
Assuming that
we can encode information with:
the order of the cards;
which face is up;
rotation of cards by 180° as clearly distinguishable on a standard deck of cards as pictured below, that is for 7 of tile, and ace, 3, 5, 6, 7, 8, 9 of clover, heart, and spade;
that when "carrying" a deck of cards:
we keep the cards together so that relative ...
3
I'm answering to this a bit with "tongue in cheek" attitude because I like the question. Thanks d33tah. I try to make a few useful points. Maybe somebody contributes more via comments.
The term RSA in itself is ambiguous. I've assumed that entire RSA as defined in PKCS#1 + key generation stuff from FIPS 186-4 was known back then (maybe they also knew DSA ...
3
You’ll likely have to do your own analysis.
First of all, most of existing literature focuses either on asymptotic speed or specific implementations (such as in the case of hardware based encryption). Neither of which will be very useful to your pen-and-paper scenario.
Second of all, coming up with your own “similar system” implies it is a “new” system and ...
2
You can implement a linear feedback shift register using nothing but a series of coins. Define 1 to be heads, 0 for tails. Line them up in to a series 128 coins in length. Then follow the algorithm exactly as you would on a computer.
From this basic generator, you can construct a self-shrunk generator. Self-shrinking generators have somewhat suspect ...
2
I'm not sure how secure this is (posting here will probably reduce its security at least a little), or whether it would necessarily even be called a hash function, but in terms of input/output (keyboard keys), memory (I think about 3 chunks beyond the piece being manipulated at a time), speed (a couple minutes to produce around 8-16 characters), materials (...
2
Many of the beginner explanations use very simple examples:
like this
It is still hard to factorize a small number by hand, compared to other operations. There is definitely a size of prime numbers where hand computation is still feasible, but hand factorizing isn't. Would you, for instance, even armed with a list of primes, be able to quickly tell me what ...
2
I don't think doing this by hand is the right way to do this. Pencil and paper systems are unreliable because humans just aren't as good at being robots as, well, robots! Most of the work in computing a secure MAC is hugely monotonous and a single mistake, anywhere during the process, could completely destroy any security you thought you had.
If your ...
2
It depends on the time you want to spend. But most likely, there is nothing with reasonable efficiency. For arithmetic operations, humans are really bad compared to computers, and the difference is at least a factor of $10.000.000$ (very very rough guess, probably even 1+ additional zeros there).
So, since you have to assume that the attacker has access to ...
2
The main difference between what you want an example for (digital signatures) and secure communication is this: the roles of the public and private keys are reversed.
Also, the content being encrypted is different. For secure communication, the entire message is encrypted. For digital signatures, the message format is irrelevant; you are trying to prove ...
2
Every classical cipher can be used without a computer's assistance; while simple mechanical ciphers can fall into the "classical cipher" category, in general classical ciphers are pen-and-paper ciphers, almost all of which are more secure than your "press the key to the right of the real one." Vigenere, for instance, has flaws; however, it is much more ...
Only top voted, non community-wiki answers of a minimum length are eligible
