How to generate a large prime via cryptography provider?

Question

I want to generate a 2048-bit prime number via the buildin cryptography provider in Powershell. This is the code I have so far, but testing the result via Rabin-Miller Test is telling me, that the number is NOT prime. What is wrong here?

$rsa = [System.Security.Cryptography.RSA]::Create(2048)
$format = [System.Security.Cryptography.CngKeyBlobFormat]::GenericPrivateBlob
$bytes = $rsa.Key.Export($format)

[bigint]$prime = 0
foreach($b in $bytes) {$prime = ($prime -shl 8) + $b}
$prime

This link tells me, that the BLOB should contain both RSA primes, but for any reason I am not able to get that info as expected: https://learn.microsoft.com/en-us/windows/win32/seccrypto/rsa-schannel-key-blobs#private-key-blobs

Answer 1

Finally I solved it after digging a bit deeper into the generic BLOB-format. The learning point here is the fact, that a 4096 RSA key includes two 2048-bit primes. One is on the last 256 bytes in the BLOB and the other prime is in the 256 bytes in front of that.

Here is the working code:

# generating two random 2048-bit PRIME numbers:

cls
$rsa = [System.Security.Cryptography.RSA]::Create(4096)
$key = $rsa.Key.Export('PRIVATEBLOB')
$len = $key.Length

$Pb = [byte[]]::new(256+1)
[array]::Copy($key, $len-512, $Pb, 1, 256)
[array]::Reverse($Pb)
$P = [bigint]$Pb
write-host $P

# optionally same for the second prime in the BLOB:
$Qb = [byte[]]::new(256+1)
[array]::Copy($key, $len-256, $Qb, 1, 256)
[array]::Reverse($Qb)
$Q = [bigint]$Qb
write-host $Q

# optionally here the Test-Function:
function Is-PrimeRabinMiller ([BigInt] $Source, [int] $Iterate)  {
    if ($source -eq 2 -or $source -eq 3) {return $true}
    if (($source -band 1) -eq 0) {return $false}

    [BigInt]$d = $source - 1;
    $s = 0;
    while (($d -band 1) -eq 0) {$d = $d -shr 1; $s++;}

    if ($source.ToByteArray().Length -gt 255) {
        $sourceLength = 255
    }
    else {
        $sourceLength = $source.ToByteArray().Length
    }

    $rngProv = [System.Security.Cryptography.RNGCryptoServiceProvider]::Create()
    [Byte[]] $bytes = $sourceLength 

    [BigInt]$a = 0
    foreach ($i in 1..$iterate) {          
        do {
            $rngProv.GetBytes($bytes)
            $a = [BigInt]$bytes            
        } while (($a -lt 2) -or ($a -ge ($source - 2)))                              
     
        [BigInt]$x = ([BigInt]::ModPow($a,$d,$source))
        if ($x -eq 1 -or ($x -eq $source-1)) {continue}

        foreach ($j in 1..($s-1)) {            
            $x = [BigInt]::ModPow($x, 2, $source)
            if ($x -eq 1) {return $false}
            if ($x -eq $source-1) {break}
        }
        return $false
    }
    return $true
}

if (Is-PrimeRabinMiller $P 42) {"P is prime!"}
if (Is-PrimeRabinMiller $Q 42) {"Q is prime!"}

Also I created a small function based on the above findings, that generates a random large prime numer:

function get-RandomPrime {
    Param (
        [parameter(Mandatory=$true)]
        [ValidateRange(256, 8192)]
        [ValidateScript({$_ % 8 -eq 0})]
        [int]$bitLength
    )
    $rsa = [System.Security.Cryptography.RSA]::Create($bitLength*2)
    $key = $rsa.Key.Export('PRIVATEBLOB')
    $len = $key.Length

    $byteLength = [int]$bitLength/8
    $bytes = [byte[]]::new($byteLength+1)
    [array]::Copy($key, $len-$byteLength, $bytes, 1, $byteLength)
    [array]::Reverse($bytes)
    [bigint]$bytes
}
$prime = get-RandomPrime -bitLength 2048
write-host "`nprime (DEC):" $prime
write-host "`nprime (HEX):" $prime.ToString('X2').SubString(1)