使用PowerShell内置加密提供程序生成2048位质数失败排查

为什么你的代码得到的不是质数？ #

你当前的代码把整个私钥Blob的所有字节直接拼接成一个BigInt，但这个Blob并非单个质数——它包含了RSA私钥的完整结构（头部标识、密钥长度、公钥指数、两个质数p/q以及其他私钥参数），所以拼接出来的数自然不是质数。

RSA私钥Blob的结构（参考微软文档翻译） #

RSA Schannel私钥Blob由两部分组成：

• BLOBHEADER（8字节）：包含Blob类型、版本、保留字段和密钥算法ID。
• RSAPRIVATEKEY结构体：
  • magic（4字节）：固定值0x32415352（小端格式，对应ASCII字符串"RSA2"），用于标识这是RSA2私钥Blob。
  • bitlen（4字节）：RSA密钥的总位数（比如2048）。
  • pubexp（4字节）：公钥指数（通常为65537，即0x10001）。
  • p（bitlen/8字节）：大端格式存储的质数p。
  • q（bitlen/8字节）：大端格式存储的质数q。
  • 后续还有dp、dq、iqmp等私钥参数，我们只需要提取p和q即可。

正确提取质数p和q的PowerShell代码 #

# 生成2048位RSA密钥对
$rsa = [System.Security.Cryptography.RSA]::Create(2048)
$format = [System.Security.Cryptography.CngKeyBlobFormat]::GenericPrivateBlob
$bytes = $rsa.Key.Export($format)

# 用内存流和二进制读取器解析Blob
$ms = [System.IO.MemoryStream]::new($bytes)
$br = [System.IO.BinaryReader]::new($ms)

try {
    # 跳过8字节的BLOBHEADER
    $br.ReadBytes(8) | Out-Null

    # 验证magic字段，确认是RSA2私钥Blob
    $magic = $br.ReadUInt32()
    if ($magic -ne 0x32415352) {
        throw "无效的RSA私钥Blob格式"
    }

    # 读取密钥位数和公钥指数
    $bitLength = $br.ReadUInt32()
    $pubExp = $br.ReadUInt32()
    $byteLength = $bitLength / 8

    # 读取质数p的字节（大端格式），转换为BigInt
    $pBytes = $br.ReadBytes($byteLength)
    $p = [System.Numerics.BigInteger]::new($pBytes, $true) # 指定大端字节序

    # 读取质数q的字节（大端格式），转换为BigInt
    $qBytes = $br.ReadBytes($byteLength)
    $q = [System.Numerics.BigInteger]::new($qBytes, $true)

    # 输出结果
    Write-Host "质数p：" $p
    Write-Host "质数q：" $q
}
finally {
    # 释放资源
    $br.Dispose()
    $ms.Dispose()
    $rsa.Dispose()
}

代码说明： #

• 使用BinaryReader按结构逐个读取Blob中的字段，避免直接拼接整个字节数组。
• 质数p和q在Blob中以大端字节序存储，创建BigInteger时指定isBigEndian为$true（需.NET Core 2.1+或.NET 5+支持，旧版本可手动反转字节数组后再创建BigInteger）。
• 最后释放相关资源，避免内存泄漏。

验证质数的方法 #

你可以用Rabin-Miller测试验证p和q是否为质数，简化版示例代码：

function Test-IsPrime {
    param([System.Numerics.BigInteger]$n)
    if ($n -le 1) { return $false }
    if ($n -le 3) { return $true }
    if ($n % 2 -eq 0) { return $false }

    # 将n-1分解为d*2^s
    $d = $n - 1
    $s = 0
    while ($d % 2 -eq 0) {
        $d /= 2
        $s++
    }

    # 测试多个底数提高准确性
    $bases = @(2,3,5,7,11)
    foreach ($a in $bases) {
        if ($a -ge $n) { continue }
        $x = [System.Numerics.BigInteger]::ModPow($a, $d, $n)
        if ($x -eq 1 -or $x -eq $n-1) { continue }
        for ($j=1; $j -lt $s; $j++) {
            $x = [System.Numerics.BigInteger]::ModPow($x, 2, $n)
            if ($x -eq $n-1) { break }
        }
        if ($x -ne $n-1) { return $false }
    }
    return $true
}

# 验证p和q
Write-Host "p是质数吗？" (Test-IsPrime $p)
Write-Host "q是质数吗？" (Test-IsPrime $q)

内容的提问来源于stack exchange，提问作者Carsten