CODEWITHSUNDEEP
encryptioncryptographyrsapublic-key-encryption
Alireza Kazeminia
Alireza Kazeminia

Reputation: 75

Generating a public/private key pair using an initial key

I'm looking for a method that enables a user to generate a pair of public/private keys using an initial key provided to him/her. I don't know if this is called hierarchical key generation or multilevel key generation or something else. It's not important for the higher level key to be able to decrypt the data of the lower level I just need the pair to be be generated using another key.

I have a seen some articles but they're all just theoretical. Is there a way to achieve this for RSA?

Upvotes: 5

Views: 4959

Answers (1)

SquareRootOfTwentyThree
SquareRootOfTwentyThree

Reputation: 7766

It is pretty easy actually.

The algorithm for generating an RSA key pair boils down to finding a set of big, prime numbers, that fulfil some algebraical properties and that are of appropriate size. If you need a 2048 bit RSA key, you will typically look for 2 prime number, each having a a rough length of 1024 bits.

The process of finding a prime number is trial-and-error: you randomly pick an integer of appropriate size, and test if it is prime. If it is not, you retry.

In the real world, the random generator that drives the algorithm is a deterministic PRNG which is seeded with a secret of appropriate entropy (e.g. 128 bits of true randomness).

In your case, the PRNG seed can be derived from a user secret or even from another key (provided it is secret of course). Derivation should be performed with a salted KDF like HKDF, PBKDF2, etc.

You don't specify which crypto library you use: whatever it is, you must be clear on how it draw randomness and how to define the seed of the PRNG.

Example (in Python 2.x):

from Crypto.PublicKey import RSA
from Crypto.Hash import HMAC
from struct import pack

# The first key could also be read from a file
first_key = RSA.generate(2048)

# Here we encode the first key into bytes and in a platform-independent format.
# The actual format is not important (PKCS#1 in this case), but it must
# include the private key.
encoded_first_key = first_key.exportKey('DER')

seed_128 = HMAC.new(encoded_first_key + b"Application: 2nd key derivation").digest()

class PRNG(object):

  def __init__(self, seed):
    self.index = 0
    self.seed = seed
    self.buffer = b""

  def __call__(self, n):
    while len(self.buffer) < n:
        self.buffer += HMAC.new(self.seed +
                                pack("<I", self.index)).digest()
        self.index += 1
    result, self.buffer = self.buffer[:n], self.buffer[n:]
    return result

second_key = RSA.generate(2048, randfunc=PRNG(seed_128))

The drawbacks to keep in mind are that:

  1. the derived key will get compromised as soon as the first key is compromised.
  2. the derived key cannot be stronger than the first key (as in, the algorithm does not magically generate entropy. If the secret key or passphrase is short, you end up with a weak derived key.

Upvotes: 7

Related Questions