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.