# Can any asymmetric algorithms work with only a key-sized amount of randomness?

With 397 rolls of a fair 6-sided die (not my favorite use of time, but certainly not infeasible), I could generate more than 1024 random bits. Could I use those bits to generate a keypair that could then be used in encryption without ever touching a (p)rng again?

• Once you have 100 to 200 bits of entropy you can generate unlimited amounts of secure pseudo random data. So 100-200 dice rolls should be enough. Oct 9, 2013 at 8:13

There are two points:

1. Key pair generation: this is a process by which an object with some mathematical structure is randomly selected. Structure depends on the used algorithm; for instance, with RSA, you need two big prime integers.

The generic method is to use your initial entropy as a seed for a PRNG, and then use the PRNG for all the random choices in the key pair generation algorithm. To fit all your die rolls in such a seed, simply hash them all together. As a rule of thumb, you only need 128 bits of entropy (provided that the PRNG is cryptographically strong), so 50 rolls are enough. More don't harm, in case the die is not as fair-sided as initially assumed.

1. Key usage: some usages of asymmetric cryptography require randomness. In particular, asymmetric encryption inherently requires some random padding, because deterministic asymmetric encryption could be subject to exhaustive search on the message itself (asymmetric encryption uses the public key, which is public, so everybody can encrypt messages and see if the result matches a given encrypted output). You could get away without random padding if the message to encrypt is already strongly random, but that does not solve the problem; it just moves it around. To operate without randomness, you may use the following:
• For signatures, use a deterministic signature algorithm. RSA with PKCS#1 v1.5 is deterministic (but not the newer "PSS" padding scheme). For DSA (and ECDSA), the algorithm as specified by FIPS 186-4 requires good randomness for each signature, but a compatible deterministic variant can be defined.

• Since asymmetric encryption requires randomness, you may replace it with static Diffie-Hellman. System A and system B both own a DH key pair, in the same group (the same curve for ECDH). Whenever A and B want to talk together, they use as shared secret the value resulting from DH, using their two key pairs. This implies that A and B will always end up with the same shared secret. This has some extra issues to take care about: there is no Perfect Forward Secrecy, replay attacks may apply...

Generally speaking, cryptographic life without randomness is harsh. A lot of algorithms and protocols require some randomness (e.g. symmetric encryption in CBC mode should have a random IV). You can have "sufficiently good" randomness in a given system as long as you have a secret key, and either state or a non-repeating public value (e.g. a clock, but beware of resets). Indeed, if you have a counter, then you can encrypt the successive counter values with a block cipher (AES comes to mind) and this will be a good PRNG; a non-repeating value known to everybody (such as the current time) can serve as a substitute for the counter.

If a system has no state to update, and no source of randomness, then it is intrinsically rewindable: boot it up, then send the same inputs as previously, and you will get the same output. This is what it means, when we say that a computer is a deterministic system. Replay attacks are the main worry here.

Assuming your dice is fair, each dice roll yields around 2.585 bits of entropy. You could use this to generate strong key-material.

Generating asymmetric keys is however a mathematical process. Both RSA and DSA key generation involve selecting primes. So you can't approach the process with a huge random number in hand and expect to be able to use it as-is.

There are opportunities to 'mix in' your high-entropy dice-material during the key generation process, namely when selecting your primes and encryption exponent in RSA, or when selecting the primes or private secret in DSA.

You would not need to generate so much however, a 1024 bit RSA key holds around 80 bits of entropy;

the security available with a 1024-bit key using asymmetric RSA is considered approximately equal in security to an 80-bit key in a symmetric algorithm

So you would only need 80 bits of entropy to generate a 1024 bit RSA key. That is to say, that if you consumed as much randomness as possible during every stage of key generation, you would find that you had used up around 80 bits of dice-material by the time you had finished generation.

• Beware that 80 bits of initial entropy are sufficient only if the PRNG used to extend these 80 bits into the random choices for RSA key pair generation, is cryptographically strong. In fact you will need a lot more than 80 bits of (pseudo-)randomness for RSA key pair, but an 80-bit seed will be good enough IF expanded with something strong (e.g. HMAC-DRBG). Oct 9, 2013 at 11:17