I also encountered this issue as part of upgrading from debian 9
(stretch) to debian 10 (buster).
At first, like the first reporter, I thought deleting and re-generating
/etc/nsd/nsd_server.pem persists the problem. However, if I also delete
/etc/nsd/nsd_server.key (which nsd-control-setup uses as a sort of
'cache') I can't reproduce. I suspect the first reporter hit the same
error. This means that it's probably the natural thing to do--can the
error message be improved to mention how to fix it?
I can't explain why the initial problem occurs, but I have some idea why
your reproduction didn't work.
My key was exactly 1.5K RSA bits, according to the output of 'sudo
openssl x509 -text -noout -in /etc/nsd/nsd_server.pem' -- not 3K bits.
The size switched from 1.5K to 3K in commit
cc589ae757cb34b5827faa9be92f8cc9a46877bd, which is part of nsd v4.1.2
RC2. I'm not sure how to check the _earliest_ version of a package in a
particular debian release, but at least the latest stretch version
includes the commit--meaning it probably can't be used to reproduce. To
reproduce you'll probably need to start from at least debian 8 (jessie),
which is before the key size change.