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.
Contents
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; }
RSADecodeKeygen
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); } }
RSADecodeStream
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); d = RSADecodeKeygen(e, 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)); s2 = RSADecodeStream(ia, d, n); 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.
Comments
Sixpack_Shambler: Hmmmm....I've tried this code out and when I decrypt a string I don't even have to use the decrypt string to decrypt it, I just converted every signgle byte in the encrypted array to big string and it came out as EXACTLY the same string as what I put in :/
El Muerte: then you didn't pick correct prime numbers. I've improved the implementation, it can now encrypt up to 23bits, thus allowing a window size of 2 bytes.
UsAaR33: Do you think it would be possible to perhaps rewrite some math algorithms? With structures and some funky overloading, you could probably use much higher bit encryption. Right now, you can factor out the private key in seconds...
El Muerte: both me and PJMODOS once started on an BigInt implementation, but neither of use ever finished it (at least not ebough to have all required operators). But it should be possible to create a BigInt type, but it won't be as nice\fast as a C or Pascal implementation (w.r.t. normal execution time in unrealscript).