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 A1 and A2 each of 512 bits and B1 and B2 each of perhaps 20 bits.
Bi is incremented until it is relatively prime to Ai.
The two arithmetic sequences, Ai + Bi*ji, are each searched for primes.
(See routine ‘scan’ Here.)
The search results in values for ji, 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 j0 coded conveniently somehow, then with the following
the private key can be reproduced in milliseconds.
Without the j0, minutes will be required for subsequent retrieval of the private key.
- the original entropy
- the low 32 bits of the public 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 2100 * (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.
- 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.
- 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 1019 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
108 sec / (economic lifetime),
105 gates / $,
109 binary ops / sec / gate,
109 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.