# RSA

R.S.A. stands for Rivest, Shamir and Adleman - the three cryptographers who invented this public key cryptosystem.

For information about RSA encryption check the related documents section below

## Code

### PowerMod

Support function to calculate `C^D mod N`. Because float signification you can't just use `C**D%N`

```static final function int PowerMod(int C, int D, int N)
{
local int f, g, j;
if ( D % 2 == 0)
{
G = 1;
for (j = 1; j <= D/2; j++)
{
F = (C*C) % N;
G = (F*G) % N;
}
}
else {
G = C;
for (j = 1; j <= D/2; j++)
{
F = (C*C) % N;
G = (F*G) % N;
}
}
return g;
}```

### _RSAGCD

A private function to calculate the Greatest Common Divider, this is use to calculate the encryption key

```static final private function int _RSAGCD(int e, int PHI)
{
local int great, a;
if (e > PHI)
{
while (e%PHI != 0)
{
a = e%PHI;
e = PHI;
PHI = a;
}
great = PHI;
}
else {
while (PHI%e != 0)
{
a = PHI%e;
PHI = e;
e = a;
}
great = e;
}
return great;
}```

### RSAPublicKeygen

This method will calculate the encryption key E from the prime numbers you supply.

P and Q have to be prime and unequal. N=P*Q and must be large enough to contain all possible values you need to encrypt..

```static final function int RSAPublicKeygen(int p, int q)
{
local int PHI, E, great;
PHI = (p-1)*(q-1);
great = 0;
E = 2;
while (great != 1)
{
E = E+1;
great = _RSAGCD(E, PHI);
}
return E;
}```

### RSAPrivateKeygen

This will calculate the decrypt key D for the corresponding encrypt key

Use the same P and Q as you did with the encrypt key

```static final function int RSAPrivateKeygen(int E, int p, int q)
{
local int PHI, u1, u2, u3, v1, v2, v3, t1, t2, t3, z;
PHI = (p-1)*(q-1);
u1 = 1;
u2 = 0;
u3 = PHI;
v1 = 0;
v2 = 1;
v3 = E;
while (v3 != 0)
{
z = u3/v3;
t1 = u1-z*v1;
t2 = u2-z*v2;
t3 = u3-z*v3;
u1 = v1;
u2 = v2;
u3 = v3;
v1 = t1;
v2 = t2;
v3 = t3;
}
if (u2 < 0)
{
return u2 + PHI;
}
else {
return u2;
}
}```

### RSAEncode

This will encode the string using the keys E and N `(=P*Q)`. the output will be stored in the int array data2.

```static final function RSAEncode(coerce string data, int E, int N, out array<int> data2)
{
local int i, c;
data2.length = len(data);
for (i = 0; i < len(data); i++)
{
c = Asc(Mid(data,i,1));
data2[i] = PowerMod(c,E,N);
}
}```

This will decrypt the array data to the correct string value.

```static final function string RSADecode(array<int> data, int D, int N)
{
local int i, j, G, F, C;
local string result;
for (i = 0; i < data.length; i++)
{
c = data[i];
result = result\$chr(PowerMod(c,D,N));
}
return result;
}```

## Example usage

Here's an example, we used the primes 19 and 23, this is more then enough to carry all characters used. And the end s1 and s2 will be equal. (note, these RSA methods have been implemented into WUtils)

```  local string s1,s2;
local int p,q,n,e,d;
local array<int> ia;

p = 19;
q = 23;
n = p*q;
e = class'wMath'.static.RSAPublicKeygen(p, q);
d = class'wMath'.static.RSAPrivateKeygen(e, p, q);

log("p="\$p@"q="\$q@"n="\$n@"e="\$e@"d="\$d);
s1 = "0123456789ABCDEFGHIJKLMNOPQRST";
log(s1);
class'wMath'.static.RSAEncode(s1, e, n, ia);
log(s2);```

This will output:

``` p=19 q=23 n=437 e=5 d=317
0123456789ABCDEFGHIJKLMNOPQRST
0123456789ABCDEFGHIJKLMNOPQRST```

Note that I left in the values of `p` and `q` in the above example. You should remove the usage of `p` and `q` when you no longer need them. When you have decided what `p` and `q` to use calculate the `n`, `e` and `d` values and use them in the rest of your code.