PowerShell: Implementing the RSA algorithm (PowerRSA)

Article
1/17/2024

https://msdnshared.blob.core.windows.net/media/2016/05/0640_NinjaAwardTinyGold.pngGold Award Winner

Preamble

Based on this very good article (http://www.di-mgt.com.au/rsa_alg.html), you can implement an RSA algorithm.

Download

The code : https://github.com/giMini/PowerRSA

Caution
Caution : Don't use it in production ;-) For the demo, you can encrypt directly the data, in the real world, you have to encrypt the symmetric key (which you exchange between Sender and Recipient) that will encrypt the data.

Introduction

The RSA algorithm was created by Ron Rivest, Adi Shamir and Len Adleman in 1977.

The main idea behind RSA is the secure way of exchanging key with a public channel of communication.

It has become the most widely used public key cryptography algorithm in the world.

Generate the keys

How it works

For length k required of 2048 bits

generate a big (128 bytes) random number p and check if it is a Prime number with the Miller-Rabin algorithm
generate a big (128 bytes) random number q and check if it is a Prime number with the Miller-Rabin algorithm
compute n (modulus) which is p * q
compute φ (PHI of n) which is (p-1)*(q-1)
choose the value 65537 which 10001 in Hex for e Exponent Public Key
compute d which is the Exponent Private Key using the Extended Euclidean algorithm

Steps in the code

Generate a big random Prime number

I call the function Get-RandomPrimeNumber and store the result in a Big Integer variable. The parameter Length help us to get a Prime number of the desired length (e.g.: 0x80 = 128 bytes = 1024 bits)

[BigInt]$p = Get-RandomPrimeNumber -Length $Length

function Get-RandomPrimeNumber {

[CmdletBinding()]

Param (

[UInt32] $Length

)

$prime = $false

for(!$prime) {

$CryptoRNGBytes = Get-RandomByte -Method CryptoRNG -Length $Length

$generated = ""

foreach($cryptoRNGByte in $CryptoRNGBytes) {

$generated += $cryptoRNGByte

}

[BigInt]$generatedPrime = $generated

$prime = Is-PrimeRabinMiller $generatedPrime 40

if($prime -eq $true) {

Break

}

return $generatedPrime

}

First, the program calls the function Get-RandomByte which returns an array of random bytes.

From that, we try to know if this random big number is a Prime. To do that, the function Is-PrimeRabinMiller is called.

The result of this probabilistic function is True when the number is a Prime and False if it is not.

We loop until we get a True from this Is-PrimeRabinMiller function.

The Miller-Rabin test is described here : https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

A thing to know about this Miller-Rabin function is the following line :

[BigInt]$x = ([BigInt]::ModPow($a,$d,$source))

We used the Modular Arithmetic, https://en.wikipedia.org/wiki/Modular_arithmetic, which is much more effective than computing:

x = a^d (mod source)

or in PowerShell:

[BigInt]$x = ([BigInt]::Pow($a,$d) % $source)

Compute the modulus

The RSA key length in bits is called the modulus which is n. So when you talk about the RSA length key, you talk about the modulus.

It is a very easy calculation :

[BigInt]$n = $p * $q

The length of the modulus will be **k, **where k is the addition of p length and q length. If you want a modulus of 1024 bits, you need a 64 bytes p (512 bits) and a 64 bytes **q **(512 bits).

Compute φ

You need φ to calculate d (d being the private key).

[[BigInt]$PHI = ($p-1)*($q-1)

Choose e

I finally use the value 65537 for e after reading this:

In practice, common choices for e are 3, 5, 17, 257 and 65537 (216+1). These particular values are chosen because they are primes and make the modular exponentiation operation faster, having only two bits of value 1. Aside: These five numbers are the first five Fermat numbers, referred to as F0 to F4, where Fx=2^(2^x)+1. Just be careful, these first five Fermat numbers are prime ("Fermat primes"), but the numbers F5 and above are not prime. For example, F5 = 4294967297 = 641 × 6700417. The usual choice for e is F4 = 65537 = 0x10001. Also, having chosen e, it is simpler to test whether gcd(e, p-1)=1 and gcd(e, q-1)=1 while generating and testing the primes in step 1. Values of p or q that fail this test can be rejected there and then.

But if you want to calculate a value for e, you could do this (in summary, find the greatest common divisor for e and φ):

function Get-GCD {

[CmdletBinding()]

Param (

[Int32] $a,

[Int32] $b

)

while ($a -ne $b) {

if ($a -gt $b) {

$a = $a - $b

}

else {

$b = $b - $a

}

return $a;

}

$GCD1 = 0

$e = 0

while ($GCD1 -ne 1) {

$compteur = 0

while ($compteur -eq 0) {

if(($p -lt $e) -and ($q -lt $e) -and ($e -lt $phiOfN)){

$compteur = 1

}

$e = $e + 1

}

$GCD1 = Get-GCD $e $phiOfN

if($GCD1 -ne 1) {

$e = $e + 1

}

Compute d

To compute the value for d, I have to use the Extended Euclidean algorithm, which is also known as the modular inverse operation.

Here we call the Get-ExtendedEuclide function for $e and $PHI calculated values and we store the result in a Big Integer variable.

[BigInt]$d = Get-ExtendedEuclide $e $PHI

The Get-ExtendedEuclide function is written as follows:

function Get-ExtendedEuclide($e, $PHI) {

$u = @(1,0,$PHI)

$v = @(0,1,$e)

while ($v[2] -ne 0) {

$q = $u[2] / $v[2]

$temp1 = $u[0] - $q * $v[0]

$temp2 = $u[1] - $q * $v[1]

$temp3 = $u[2] - $q * $v[2]

$u[0] = $v[0]

$u[1] = $v[1]

$u[2] = $v[2]

$v[0] = $temp1

$v[1] = $temp2

$v[2] = $temp3

}

if ($u[1] -lt 0) {return ($u[1] + $PHI)}

else {return ($u[1])}

}

If you want to understand how this algorithm works, you can watch this video : https://www.youtube.com/watch?v=hB34-GSDT3k

You can also Bruteforce it, but it is much slower. A Bruteforce implementation could look like this:

$d = 0

$compteur = 0

while ($compteur -eq 0) {

if(((($e * $d) % $phiOfN) -eq 1) -and ($p -lt $d) -and ($q -lt $d) -and ($d -lt $phiOfN)) {

$compteur = 1

}

$d = $d + 1

}

$d = $d - 1

How to use it

To generate the Modulus, the private key and the public key, enter this command:

.\PowerRSA.ps1 -Method GenKeys

PowerRSA will generate the necessary keys:

PS F:\Crypto> .\PowerRSA.ps1 -Method GenKeys

Keys generating...

Keys saved in F:\Crypto\

and save them in a folder:

https://4.bp.blogspot.com/-xVka2D0Qnfo/VrYV3PwrorI/AAAAAAAACYw/8t16ljwcoEw/s1600/keys.PNG

Example of the Modulus generated:

https://4.bp.blogspot.com/-G6cuxRa0gyE/VrYWIZdmdEI/AAAAAAAACY4/0T44AS56sM4/s400/modulus.PNG

The program allows to generate a 1024-bit, 2048-bit or 4096-bit key length.

To generate a 2048-bit key:

.\PowerRSA.ps1 -Method GenKeys -KeyType 2048-bit

Encrypt data

How it works

With the public key (which is composed of the Modulus and the Public Exponent), I encrypt the data string provided.

To encrypt it and for each character:

I transform character into an integer representation
I generate a Random Padding
I concatenate the integer character representation with the random padding = m
I encrypt the concatenation result by computing c = m^e % n where c is the encrypted character, m = the concatenate integer character with random padding, e = the public Exponent key and n = the Modulus. I do this calculation with the help of Modular Arithmetic (ModPow in PowerShell)

Steps in the code

First, I get the integer for the character to encrypt:

$asciiCode = [int]$character[-0]

I create a random padding before encrypting data to avoid statistical attack on text:

$CryptoRNGBytes = Get-RandomByte -Method CryptoRNG -Length 0x12

[string]$randomPadding = ""

foreach($c in $CryptoRNGBytes) {

$randomPadding += $c

}

I concatenate the ASCII Code and the random padding:

[BigInt]$asciiCode = "$($asciiCode)00005$randomPadding

I encrypt the character data by computing c = m^e mod n with the help of Modular Arithmetic:

$cryptCharacter = ([BigInt]::ModPow($asciiCode,$exponentInt,$modulusInt))

How to use it

To encrypt data using PowerRSA, enter this command (with your generated Modulus and Public Key):

.\PowerRSA.ps1 -Method Enc -Exponent F:\Crypto\PublicKey -Modulus F:\Crypto\Modulus

Then, enter the data string to encrypt:

Enter message to encrypt: Hi! I'm an encrypted data string

PowerRSA will encrypt data:

PS F:\Crypto> .\PowerRSA.ps1 -Method Enc -Exponent F:\Crypto\PublicKey -Modulus F:\Crypto\Modulus

Enter message to encrypt: Hi! I'm an encrypted data string :-)

Data saved in F:\Crypto\

and save it in a folder:

https://1.bp.blogspot.com/-tXYORcEbj4Y/VrYbRAjYI9I/AAAAAAAACZM/AsIkkbZ6wHM/s1600/data.PNG

Encrypted data looks like this:

https://2.bp.blogspot.com/-QwjVuflQkG4/VrYbfsWTVcI/AAAAAAAACZU/Yibc47mdqzU/s320/dataencrypted.PNG

Decrypt data

How it works

With the private key (which is composed of the Modulus and the Private Exponent), I decrypt the data string provided.

I decrypt the encoded string by computing m = c^d % n (I used Modular Arithmetic)
I remove the random padding
I transform the integer into its character representation

Steps in the code

For each block (which is a character):

foreach ($b in $block) {

Get the Integer value of the block:

$b = [BigInt]::Parse($b,([System.Globalization.NumberStyles]::HexNumber));

Decrypt the block:

[BigInt]$asciiCode = ([BigInt]::ModPow($b,$d,$n))

Remove the random padding:

$asciiCodeSplitted = $asciiCode -split "00005"

[int]$asciiCodeSplittedInteger = $asciiCodeSplitted[0]

Construct the result String:

$string = $string + $([char]$asciiCodeSplittedInteger)

How to use it

To decrypt data using PowerRSA, enter this command:

.\PowerRSA.ps1 -Method Dec -Data F:\Crypto\Data -ExponentF:\Crypto\PrivateKey -Modulus F:\Crypto\Modulus

PowerRSA will decrypt the data:

PS F:\Crypto> .\PowerRSA.ps1 -Method Dec -Data F:\Crypto\Data -Exponent F:\Crypto\PrivateKey -Modulus F:\Crypto\Modulus

Hi! I'm an encrypted data string :-)

Conclusion

We now have an implementation of RSA algorithm proving -if this was still necessary- the power of PowerShell :-)

Share via

PowerShell: Implementing the RSA algorithm (PowerRSA)

Preamble

Download

Introduction

Generate the keys

How it works

Steps in the code

Generate a big random Prime number

Compute the modulus

Compute φ

Choose e

Compute d

How to use it

Encrypt data

How it works

Steps in the code

How to use it

Decrypt data

How it works

How to use it

Conclusion

See Also

Additional resources