Using Go deterministicly generate RSA Private Key with custom io.Reader

For reasons probably best left unanswered I need to generate infinite RSA public/private keys. Note this is not being used for anything highly secure, so please don't tell me not to do this, yes I know its not ideal. By "infinite" I mean I need a unknown number of them think billions to trillions, and creating them before being used is not possible.

Since this would consume infinite space and take infinite time to generate I need to do it at runtime.

However I also need to have for a given input the same key pair. This means I need to deterministically recreate the RSA key given the input.

I am using Go and normally you create keys using the following,

k, err := rsa.GenerateKey(rand.Reader, 2048)

Of course the catch is that rand.Reader is supplied by crypto/rand and as such there is no way to seed this.

I thought that it would be possible to provide my own reader implementation to achieve my goal. I looked through the source of GenerateKey and noted that it is looking for prime numbers, so I implemented my own reader, such that I could control the "random" primes returned, allowing me to generate the same key when required,

type Reader struct {
	data   []byte
	sum    int
	primes []int
}

func NewReader(toRead string) *Reader {
	primes := sieveOfEratosthenes(10_000_000)
	return &Reader{[]byte(toRead), 0, primes}
}

func (r *Reader) Read(p []byte) (n int, err error) {
	r.sum = r.sum + 1

	if r.sum >= 100_000 {
		return r.primes[rand.Intn(len(r.primes))], io.EOF
	}

	return r.primes[rand.Intn(len(r.primes))], nil
}

func sieveOfEratosthenes(N int) (primes []int) {
	b := make([]bool, N)
	for i := 2; i < N; i++ {
		if b[i] == true {
			continue
		}
		primes = append(primes, i)
		for k := i * i; k < N; k += i {
			b[k] = true
		}
	}
	return
}

I can then call into generate key like so

k, err := rsa.GenerateKey(NewReader(""), 2048)

Which compiles, but crashes at runtime due to nil pointers. I am fairly comfortable with Go, but the implementation of RSA for this is beyond my understanding. Looking for either a better way to achieve this, or perhaps what I need to do to get my reader working.

Note, the only hard requirement's I have here are being able to generate the same key for a given input, and use rsa.GenerateKey or a drop in compatible replacement. The input can be anything really, so long as I get the same key as the output.

Here is a Go playground link demonstrating where I am currently https://go.dev/play/p/jd1nAoPR5aD

The Read method is not doing what is expected. It does not fill the input p byte slice with random bytes. If you look at the implementation for Unix of crypto/rand.Read method, it passes the input byte slice into another reader. So basically you what you need to fill the byte slice with random numbers. For example:

func (r *Reader) Read(p []byte) (n int, err error) {
        i := 0
        b := p

        for i < len(b) {
                if len(b) < 4 {
                        b[0] = 7
                        b = b[1:]
                } else {
                        binary.LittleEndian.PutUint32(b, uint32(rand.Intn(len(r.primes))))
                        b = b[4:]
                }
        }

        return len(p), nil
}

Here is the link to playground.

UPD

As mentioned in the answer by Erwin, there is a function called MaybeReadRand that with 50% chance read 1 byte from rand reader to make this function nondeterministic. But you can get around by adding if statement in Read method: if length of the input slice is 1, then ignore everything and return. Otherwise, feed the input slice with prime numbers:

func (r *Reader) Read(p []byte) (n int, err error) {
	i := 0
	b := p

	if len(p) == 1 {
		println("maybeReadRand")
		return 1, nil
	}

	for i < len(b) {
		if len(b) < 4 {
			b[0] = 7
			b = b[1:]
		} else {
			binary.LittleEndian.PutUint32(b, uint32(r.primes[r.i]))
			r.i++
			b = b[4:]
		}
	}

	return len(p), nil
}

In this snippet I am creating 2 keys, and both of them are equal.

Someone posted an answer here, and I was about to award it to them as it got me the final piece I needed to resolve the question.

In short, I didn't read how the read was being called properly and I needed to populate the input slice. Changing the read to the below,

func (r *Reader) Read(p []byte) (n int, err error) {
	i := 0
	b := p

	for i < len(b) {
		if len(b) < 4 {
			b[0] = 7
			b = b[1:]
		} else {
			binary.LittleEndian.PutUint32(b, uint32(rand.Intn(len(r.primes))))
			b = b[4:]
		}
	}

	return len(p), nil
}

resolves the crashes, and since it is now using math/rand I can set the seed for the list of primes allowing me to ensure it is deterministic. Everything solved without needing anything from 3rd parties. Excellent.

To whoever posted that, if you post again I will award you the accepted answer.

You have made a strange assumption. rand.Reader returns completely random data. It doesn't return prime numbers. rsa.GenerateKey uses the data internally to come up with -very probable- prime numbers. But it doesn't depend on any particular pattern in the reader. In fact, it prefers there to be no pattern (and "being a prime number" is definitely a pattern)

Sure, you're free to feed rsa.GenerateKeym, or excerpts from Shakespeare's works, but rsa.GenerateKey is not going to make use of the fact that it is.

So running a sieve of Eratosthenes is a waste of time (literally).

If rsa.GenerateKey allowed you to deterministically generate keys, then you could directly generate bytes using a pseudo-random number generator that uses a seed, directly.

But, that's not the case. Look at the source code, line 287 of rsa.go:

func GenerateMultiPrimeKey(random io.Reader, nprimes int, bits int) (*PrivateKey, error) {
	randutil.MaybeReadByte(random) // <------- this line here is the important one

The function GenerateMultiPrimeKey is directly invoked by GenerateKey.

Now what does randutil.MaybeReadByte do? The documentation is clear:

> MaybeReadByte reads a single byte from r with ~50% probability. This
> is used to ensure that callers do not depend on non-guaranteed
> behaviour, e.g. assuming that rsa.GenerateKey is deterministic w.r.t.
> a given random stream.

In short, it ensures that it is not possible to deterministically generate a particular RSA key.

If you still needed to do that, you would need to copy the source code of GenerateMultiPrimeKey to your own library, and remove the line randutil.MaybeReadByte. Or you'd need to rethink what your requirement really is, a level higher than you're currently thinking, and see if there is a different way to achieve your requirement. (Have a look at the "XY problem")

If you need a deterministic-random io.Reader, here's how to do it with the standard library

import (
	"io"
	"math/rand"
)

func main() {
	const seed = 1
	var myRand = rand.New(rand.NewSource(seed))
}

rand.NewSource creates a deterministic seeded random source, and rand.New wraps it to create a more featureful *Rand object, which includes an implementation of io.Reader.

You can also reset the *Rand by calling myRand.Seed(seed).