Remembering Private Keys

To Remember a Private Key

Public key crypto deals in large numbers which are conceptually “remembered” by parties holding those keys. In practice these numbers are so large that probably no one actually remembers their key but instead keeps the key in a computer protected with a pass phrase. Elliptic crypto keys are smaller but still scarcely memorable. Here is a scheme to remember about 100 bits of random information from preexisting memories instead of having to form new memories. If these memories are very likely to be private then the algorithm may produce a private key that is sufficiently secret. What ever your private noise, here is how to use it to generate a private RSA key.

To produce a 1024 bits RSA private key requires the prospective owner to produce and remember information (entropy) of around 100 bits. If your noise is text in some natural language, append your Social Security Number, not because it is a good secret but because it thwarts dictionary attacks. This information is hashed to produce numbers A₁ and A₂ each of 512 bits and B₁ and B₂ each of perhaps 20 bits. B_i is incremented until it is relatively prime to A_i. The two arithmetic sequences, A_i + B_i*j_i, are each searched for primes. (See routine ‘scan’ Here.) The search results in values for j_i, each about 10 bits long. This produces the private key from which the public key may be derived. If the new owner is willing and able to remember j₀ coded conveniently somehow, then with the following

the original entropy
j₀
the low 32 bits of the public key

the private key can be reproduced in milliseconds. Without the j₀, minutes will be required for subsequent retrieval of the private key.

A brute force attack on the key must presumably search the space of hash values, or search some statistically appropriate space of natural language. If the owner has indeed provided adequate entropy this will require 2¹⁰⁰ * (several seconds) of normal computer time by either method.

There is no direct analog to remember public keys, but they need less protection. Remembering part of the public key’s fingerprint serves much of the purpose.

Advantages:

The scheme is deterministic so that two implementations of the scheme can be employed and the output compared to ensure that your secret was indeed computed by the publicly reviewed standard, baring collusion between the two implementations. This overcomes the danger of deficient random number generators which are extremely difficult to detect.
Contrasted with pass phrase protected keys in computer files, there is no need to return to the same computer to use your private key. Any computer that you trust and that is equipped with the standard software is able to use your remembered key.

Disadvantages:

There is a substantial risk in the quality of entropy provided by the user. There is no adequate programmable test to assure the quality of the owner’s entropy, but there are tests that will warn of some unsafe uses. The scheme requires that the owner have a realistic intuition about the entropy that he provides. This requires some intuitive grasp of information theory.
An institution with a large budget and a charter to break these keys could precompute 10¹⁹ private keys and index them by public key ID. This would amortize the cost over many breaks. This would crack many keys but fail for well chosen secret phrases. I assume a budget of 10⁸ dollars, 10⁸ sec / (economic lifetime), 10⁵ gates / $, 10⁹ binary ops / sec / gate, 10⁹ binary ops to test a prime, 100 tests / found prime.
The hardware to perform the creation or recreation of the private key would have to be confined or otherwise trusted to forget your private key and the material used to create it.

Some progress