Profiling rsa.GenerateKey >113 bytes

[Nathan Vander Wilt]

I'm hitting some sort of wall generating useful RSA keys with Go's rsa library. Requesting a key with length of 114 bits or more causes my process to (essentially) hang.

import ("fmt"; "crypto/rsa"; "os")

func main() {
rand, _ := os.Open("/dev/random", os.O_RDONLY, 0)

{
privKey, _ := rsa.GenerateKey(rand, 113)
fmt.Printf("P & Q: %v & %v\n", privKey.P, privKey.Q)
}
{
privKey, _ := rsa.GenerateKey(rand, 114)
fmt.Printf("P & Q: %v & %v\n", privKey.P, privKey.Q)
}
}

How can I go about troubleshooting this? What are people using to profile and debug Go code?

thanks,
-natevw

[Russ Cox]

>        rand, _ := os.Open("/dev/random", os.O_RDONLY, 0)

I think your program is blocking because you are
running the system out of random data. Typically
/dev/urandom is used for things like this.

> How can I go about troubleshooting this?
> What are people using to profile and debug Go code?

You can get a stack trace by doing kill -ABRT pid.
That's about as good as it gets right now.

Russ

[Nathan Vander Wilt]

On Dec 23, 2009, at 8:55 AM, Russ Cox wrote:
>> rand, _ := os.Open("/dev/random", os.O_RDONLY, 0)
>
> I think your program is blocking because you are
> running the system out of random data. Typically
> /dev/urandom is used for things like this.

That was my initial thought, but while it hangs I was still able to cat from /dev/random. I've changed my code to use /dev/urandom for compatibility, but on OS X /dev/random uses the Yarrow algorithm and is non-blocking as well.

I meant to include in my original post that I'm using GOARCH=amd64, GOOS=darwin and have since tested it with GOARCH=386 as well.

>> How can I go about troubleshooting this?
>> What are people using to profile and debug Go code?
>
> You can get a stack trace by doing kill -ABRT pid.
> That's about as good as it gets right now.

Though my sample size is fairly small, most traces have been within big·divNN. When I tried compiling for GOARCH=386 instead, rsa.GenerateKey for bits > =114 completes in a much more reasonable time. Is there perhaps a performance bug in the big package under amd64? I would have expected large number calculations to be faster with 64- rather than 32-bit instructions available.

thanks,
-natevw

[Charlie]

Looks like a boundary condition issue in randomN (pkg/big/nat.go)
replace:
bitLengthOfMSW := uint(n % _W)
with:
bitLengthOfMSW := uint(n % _W)
if bitLengthOfMSW == 0 {
bitLengthOfMSW = _W;
}
assuming n!=0
(ow. will return 0 with n = 64 on 64bit arch, n = 32 on 32 arch...
Note: Problem occurs on 8g with bits= 112/2.)

Charlie