Deterministically generate RSA private keys with custom io.Reader using Go

php editor Baicao will introduce how to use Go language to deterministically generate RSA private keys through custom io.Reader interface. RSA is an asymmetric encryption algorithm commonly used for data encryption and digital signatures. When generating an RSA private key, we usually need to obtain random numbers from a random source, but sometimes we need to generate a deterministic private key according to specific rules. This article will explain in detail how to implement a custom io.Reader interface and use this interface to generate a deterministic RSA private key. By reading this article, you will learn this useful technique to give your cryptographic applications more flexibility and control.

Question content

For reasons that are probably best left unanswered, I need to generate unlimited rsa public/private keys. Note that this isn't used for anything highly secure, so please don't tell me not to do it, and yes, I know it's not ideal. What I mean by "infinite" is that I need an unknown number of them (billions to trillions) and creating them before using them is impossible.

Since this consumes infinite space and takes infinite time to generate, I need to do this at runtime.

However, I also need to have the same key pair for a given input. This means I need to deterministically recreate the rsa key based on the input.

I use go, usually you create the key using the following command,

k, err := rsa.generatekey(rand.reader, 2048)

Of course, the problem is that rand.reader is served by crypto/rand, so it cannot be seeded.

I thought it would be possible to provide my own reader implementation to achieve my goal. I looked at the source code for generatekey and noticed that it was looking for prime numbers, so I implemented my own reader so that I could control the "random" prime numbers returned, allowing me to generate the same if needed The key,

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
}

Then I can call generate key like this

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

It compiles but crashes at runtime due to a zero pointer. I'm pretty happy with go, but the implementation of rsa is beyond my understanding. Looking for better ways to achieve this, or looking for what I need to do to make it work for my readers.

Note that my only hard requirement here is to be able to generate the same key for a given input, using rsa.generatekey or a compatible replacement. The input can be literally anything as long as I get the same key as the output.

Here is a go playground link showing where I am currently https://go.dev/play/p/jd1naopr5ad

Workaround

read Method did not perform the expected operation. It does not pad the input p byte slice with random bytes. If you look at the unix implementation of the crypto/rand.read method, it passes a slice of input bytes to another reader. So basically 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
}

This is the link to the playground .

renew

As erwin mentioned in his answer, there is a function called maybereadrand which has a 50% chance of reading 1 byte from the rand reader, making the function unique Certainty. But you can solve it by adding an if statement in the read method: if the length of the input slice is 1, ignore everything and return. Otherwise, provide prime numbers to the input slice:

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 create 2 keys and they are both equal. p>

The above is the detailed content of Deterministically generate RSA private keys with custom io.Reader using Go. For more information, please follow other related articles on the PHP Chinese website!