Large random prime numbers, or any randomly selected number satisfying a predicate, can be encoded compactly by simply providing the seed to the pseudorandom number generator used to sample for it.
This provides a way to compactly store, or memorize, private keys (perhaps engraved onto small jewelry). We need a standardized protocol for re-deriving private keys from a seed. Unfortunately, this can't be extended to encoding RSA public keys or Diffie-Hellman because it would divulge the private key.
It is rather disorienting that, in some situations, 128 bits is effectively indistinguishable from infinity.
4 comments :
Also the random number might not have been generated by a seeded algorithmic PRNG, but might instead have been produced from some "true entropy" of some sort.
Or it might have been generated by an algorithmic PRNG which has a seed just as long as the random number itself (e.g. 128 bits) (or even longer!), so the seed representation is not more compact.
Yes, one could use fancier random number sources that you suggest, but the subtle point I was trying to make is that such fanciness is "effectively" no "better" than a 128-bit stream cipher, so one might as well forego the fancy entropy source and just use the stream cipher.
...after which point, the 128-bit seed (plus the specification of the predicate) is enough to describe anything subsequently generated from the random stream, though it might be considerable computation to replicate.
...and then that tradeoff, space versus time, is the real point.
Post a Comment