1

I am currently studying the most widely known encryption algorithms and methodologies. For practice purposes, I want to implement everything from ECB to RSA as some kind of a C crypto library.
How would I generate a secure key in a C program (I know, that writing a crypto library on my own is not secure at all but I just want to learn basic principles from key generating to key exchanging to encryption mechanisms).
How could I approach the problem of implementing an algorithm for a secure key generation? Which main issues need to be considered to reach an at least mediocre key security?

  • Given that you want to write a C library, I assume that interoperability is some concern. As such, relying on /dev/urandom is not really recommended, as it may not exist on some systems (e.g. MS Windows). – MechMK1 Nov 12 '19 at 11:55
1

Most block ciphers want a totally random string of bytes as the key. So read the key from /dev/random dd if=/dev/urandom count=1 bs=256 (or whatever cryptographic RNG you have easy access to).

For ciphers other than block ciphers, for example RSA or ECDHE (on curves other than ed25519), keys are not just random bytes and in fact have a lot of mathematical structure inside them. These algorithms have complicated key generation routines, so you'll need to go find the specification for the algorithm you're trying to implement. These keygen algorithms have been tested by many mathematicians over the years, and as long as you follow them exactly, you should get a secure key.

For example, Wikipedia describes the general RSA keygen algorithm here, but I'm struggling to find an original source technical spec. Maybe that's because what I want is the PKCS#1 spec, which is pay-walled by the RSA company?

https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Key_generation

  • Hmm, I feel unsure about this because whenever I google something related to encryption methodologies I always read smth like "plain rsa is insecure, needs padding" or "sidechannel attacks can screw this or that up" and I wonder how to handle these insecurities. Also i.e., as stated here, /dev/urandom is actually not recommended to be used for long term cryptographic keys. So could you imagine different ways on how to securely generate keys? Or where I could find good resources on how to really do similar things? – Lavair Nov 11 '19 at 23:30
  • Not OP, but can I use random bytes as key for ed25519? Like, could I manually read some random bytes of correct length, encode them correctly, and then say "Here, this is my ed25519 private key" and generate a public key from it? – ig-dev Nov 12 '19 at 0:16
  • @Lavair Your question was about generating private keys. Padding has nothing to do with private key generation. Sidechannel attacks could, I guess, apply to keygen, but usually they apply to signing / encryption / decryption operations. In your link, right below the warning is this text: "whether it applies or not largely depends on the system's status and purpose. For example, ..whether the system has just booted up, or the kernel has had time to gather entropy and fill the entropy pool". There is a huge debate about /dev/random vs /dev/urandom which it out of scope for this question :P – Mike Ounsworth Nov 12 '19 at 0:34
  • 1
    @ig-dev I'm not an expert on the internals of ed25519, but according to wikipedia: _"An EdDSA private key is a b {\displaystyle b} b-bit string k {\displaystyle k} k which should be chosen uniformly at random. The corresponding public key is ..." So yes, any random bit string of the correct length is a valid ed25519 private key. – Mike Ounsworth Nov 12 '19 at 0:44
  • @Lavair For most platforms /dev/urandom is about as good as you are going to get to produce long term cryptographic keys (unless you have access to a trusted hardware random number generator device). – Martin Bonner supports Monica Nov 12 '19 at 10:05
1

If you're just asking "how do I create a cryptographically secure PRNG?", that's an interesting problem because the difficulty in a secure PRNG is largely a matter of its entropy source(s). Given sufficiently good input entropy, it's relatively easy (using existing primitives) to create a pseudo-random function where the internal state cannot be derived from the outputs, nor the past or future outputs predicted - every stream cipher is just a CSPRNG, and a simple implemention would be a function that uses a secure hash, returns part of the digest, and updates its internal state using the rest - but that precondition is almost never a "given".

Absent some sort of hardware RNG based on processes we cannot predict, entropy is usually collected from as many different hard-to-predict events as possible, so that even if one or a few sources are controlled by an adversary, that adversary won't have access to the others. A few simple examples of this: power source fluctuations, network traffic, user input hardware interrupts, thermal sensors. Taking all these sources of entropy and "mixing" them (such that even if multiple sources are completely attacker controlled, the overall value is not) create a high-quality entropy source can be done a few different ways; you can see the algorithms used in open-source CSPRNGs such as the one in the Linux kernel (which drives /dev/[u]random).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.