Since when can the government patent its work? I thought that works produced by government agencies could not be copyrighted or patented.

No. The patent on the digital signature algorithm, the basis of the new digital signature standard, for example, is held by NIST.