I'm a doctor, not a mechanic

# Legacy:RSA

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

For information about RSA encryption see Wikipedia:RSA and the related documents section below.

## Code

This code uses integers, integers are 32bit in UnrealScript. Because of this the encryption as shown in the document isn't very secure. The improved code can have encryption up to 23bit, the previous implementation was limited to 13bits.

Using floats is not an option because they will lose signification at a certain point.

This code can be used under the terms of the ZLib/LibPNG license:

```Copyright (c) 2004 Michiel Hendriks & UnrealWiki Contributers
http://wiki.beyondunreal.com/edit/Legacy:RSA

This software is provided 'as-is', without any express or implied
warranty. In no event will the authors be held liable for any damages
arising from the use of this software.

Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it
freely, subject to the following restrictions:

1. The origin of this software must not be misrepresented; you must not
claim that you wrote the original software. If you use this software
in a product, an acknowledgment in the product documentation would be
appreciated but is not required.

2. Altered source versions must be plainly marked as such, and must not be
misrepresented as being the original software.

3. This notice may not be removed or altered from any source
distribution.
```

### PowerMod

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

```static final function int PowerMod(int C, int D, int N)
{
local int p;
c = mod(c, n);
if (c < 0) c += n;
p = 1;
while (d >= 1)
{
if ((d & 1) == 1) p = mulmod(c, p, n);
c = mulmod(c, c, n);
d = d / 2;
}
return p;
}

static final function int mulmod(int C, int D, int N)
{
local int p;
c = mod(c, n);
if (c < 0) c += n;
p = 0;
while (d >= 1)
{
if ((d & 1) == 1) p = mod(c + p, n);
c = mod(c * 2, n);
d = d / 2;
}
return p;
}

/**
* int precision modulo function.
* Like the % operator, this function returns a negative result for negative a.
*/
static final function int mod(int a, int n)
{
return a - (a / n) * n;
}```

### _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 (mod(e, PHI) != 0)
{
a = mod(e, PHI);
e = PHI;
PHI = a;
}
great = PHI;
}
else {
while (mod(PHI, e) != 0)
{
a = mod(PHI, e);
PHI = e;
e = a;
}
great = e;
}
return great;
}```

### RSAEncodeKeygen

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++;
great = _RSAGCD(E, PHI);
}
return E;
}```

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;
}
}```

### NumBits

This will return the number of bits used in an integer.

```static final function int NumBits(int sample)
{
local int bits;
bits = 0;
while (sample > 0)
{
sample = sample >>> 1;
bits++;
}
return bits;
}```

### RSAEncodeStream

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

It will automactially adjust to window size according to the size of N. When N is more than 15 bits two characters will put in a single integer.

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

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

It will automactially adjust to window size according to the size of N.

```static final function string RSADecodeStream(array<int> data, int D, int N)
{
local int i, c, window;
local string result;
window = NumBits(N)/8;
for (i = 0; i < data.length; i++)
{
c = PowerMod(data[i],D,N);
if (window > 3) result \$= chr((c & 0xff000000) >> 24);
if (window > 2) result \$= chr((c & 0x00ff0000) >> 16);
if (window > 1) result \$= chr((c & 0x0000ff00) >> 8);
result \$= chr((c & 0x000000ff));
}
return result;
}```

## Example usage

Here's an example that creates the keys, encrypts and decrypts and checks if they're equal. It will also print the encrypted data.

```function bool EncTest(int p, int q, string testData)
{
local string s2;
local int n,e,d;
local array<int> ia;

n = p*q;

if (NumBits(N) < 8)
{
warn("Not enough bits for encrypting the data");
return false;
}

e = RSAEncodeKeygen(p, q);

log("p="\$p@"q="\$q@"n="\$n@"e="\$e@"d="\$d@"bits="\$NumBits(N));

log("Source:"\$chr(9)\$chr(9)@testData);
RSAEncodeStream(testData, e, n, ia);
log("Encrypted:"\$chr(9)@printByteArray(ia));
log("Decrypted:"\$chr(9)@s2);

return s2 == testData;
}```

When called with `EncTest(2851, 2927, "012345 hello world")` it will output:

```p=2851 q=2927 n=8344877 e=13 d=2565877 bits=23
Source:          012345 hello world
Encrypted:       001075070001d062007efb6800542d6800471922003fc53e00692eae005a3a310074b044
Decrypted:       012345 hello world
```

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.