The following code is an implementation of the RSA-Algorhythm. It uses Strife's UTF8ToUnicodeInteger (and back) functions and the code I found on http://www.nordwest.net/hgm/krypto/algo.htm with the RSA-implementation.
The speed is - well, kind of ok. It takes about 2 to 3 seconds to encode a text with about 70 characters. The decryption is slower and takes about 7 to 10 seconds.
I guess, this would be (kind of) ok to encrypt short messages to communicate between prims (let's say, to transfer a passphrase and some other stuff).
I didn't make it to encode longer stuff, since the goal was to make a secure communication for prims with short messages.
It seems that it's capable of doing the math with the whole Unicode set (thanks to Strife). At least, it worked quite well with «öäüé» and so on.
After compiling the script, it listens on channel 1. Say «keygen» to generate the public and secret key-pairs and says them with llOwnerSay().
After that, you can simply say a sentence on channel 1 - it will be encrypted and immediately decrypted.
I did have some weird results sometimes, depending on the keys that were generated. Sometimes, it just didn't work... Have to figure out where the problem is. If the decrypted part is not correct, just generate another keypair and try again.
ToDo:
Take the stuff apart so that the encryption and decryption part can be put into two prims which then will be able to communicate (preferably with a llDialog that lets the user say the public- and private key to the objects).
Implement a llDialog to provide a blue menu to a) generate the key-pairs and b) have them said to the owner.
-------------
Now go ahead and tell me, it's not secure at all...
[EDIT]
Added Strife's function for getting the bitlength of an integer (Thanks Strife!)
Changed the function RSA_decode to string manipulations so we don't run into lists which are too long (and, afaik, string manipulations are supposed to be faster than lists - are they?).
CODE
//===================================================//
// Combined Library //
// "Feb 4 2008", "08:38:13" //
// Copyright (C) 2004-2008, Strife Onizuka (cc-by) //
// http://creativecommons.org/licenses/by/3.0/ //
//===================================================//
//{
integer UTF8ToUnicodeInteger(string input)//LSLEditor Safe, LSO Safe
{
integer result = llBase64ToInteger(llStringToBase64(input = llGetSubString(input,0,0)));
if(result & 0x80000000){//multibyte, continuing to use base64 is impractical because it requires smart shifting.
integer end = (integer)("0x"+llGetSubString(input = (string)llParseString2List(llEscapeURL(input),(list)"%",[]),-8,-1));
integer begin = (integer)("0x"+llDeleteSubString(input,-8,-1));
return ( ( 0x0000003f & end ) |
(( 0x00003f00 & end) >> 2 ) |
(( 0x003f0000 & end) >> 4 ) |
(( 0x3f000000 & end) >> 6 ) |
(( 0x0000003f & begin) << 24) |
(( 0x00000100 & begin) << 22)
) & (0x7FFFFFFF >> (5 * ((integer)(llLog(~result) / 0.69314718055994530941723212145818) - 25)));
}
return result >> 24;
}
string UnicodeIntegerToUTF8(integer input)//LSLEditor Safe, LSO Safe
{
integer bytes = llCeil((llLog(input) / 0.69314718055994530941723212145818));
bytes = (input >= 0x80) * (bytes + ~(((1 << bytes) - input) > 0)) / 5;//adjust
string result = "%" + byte2hex((input >> (6 * bytes)) | ((0x3F80 >> bytes) << !bytes));
while (bytes)
result += "%" + byte2hex((((input >> (6 * (bytes = ~-bytes))) | 0x80) & 0xBF));
return llUnescapeURL(result);
}
string byte2hex(integer x)//LSLEditor Safe, LSO Safe
{//Helper function for use with unicode characters.
integer y = (x >> 4) & 0xF;
return llGetSubString(hexc, y, y) + llGetSubString(hexc, x & 0xF, x & 0xF);
}//This function would benefit greatly from the DUP opcode, it would remove 19 bytes.
string hexc="0123456789ABCDEF";
//} Combined Library
// *********************************************************
// RSA-Encryption/Decription
// Javascript-Code from http://www.nordwest.net/hgm/krypto/algo.htm
// LSL-Implementation by Haruki Watanabe
//
// *********************************************************
integer m;
integer e;
integer d;
integer BlkLen;
list PrimeNumbers = [101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157,
163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227];
integer randInt(integer n){
return (integer)llFrand(n + 1);
}
integer randIntBetween(integer min, integer max){
return min + randInt(max - min);
}
// Determine the BitLength of an Integer (Thanks to Strife Onizuka)
integer BitLength(integer value)
{
if(value & 0x80000000) return 32;//can't take the log of negatives
integer bits = llCeil((llLog(value) / 0.69314718055994530941723212145818));//ceil(log2(value))
return bits + (((1 << bits) - value) <= 0);//correct the log2
}
RSA_keys (integer P, integer Q) {
integer Phi = (P - 1)*(Q - 1);
m = P * Q;
e = PublicKey (Phi);
d = SecretKey (e, Phi);
}
integer PublicKey(integer Ph) {
integer akT = 0;
integer ee = 2;
while (akT != 1) {
ee = ee + 1;
akT = ggT(ee, Ph);
}
return ee;
}
integer ggT(integer m, integer n)
{
if (n==0)
return m;
else
return ggT(n, m%n);
}
integer SecretKey (integer ee, integer Phi) {
integer i = 0;
do {
i = i + 1;
} while ((i*Phi + 1)%ee != 0);
return (i*Phi + 1)/ee;
}
keygen_RSA(integer p, integer q) {
integer phi = (p - 1) * (q - 1);
m = p * q;
do{
e = PublicKey(phi);
} while (e < 1);
do{
d = SecretKey(e, phi);
} while(d < 1);
llOwnerSay("Public-Code: " + (string)e + ", " + (string)m);
llOwnerSay("Secret-Code: " + (string)d + ", " + (string)m);
}
RSA_keygen() {
integer P;
integer Q;
integer int1;
integer int2;
integer cPrimeNumbers = llGetListLength(PrimeNumbers);
// Generate the keypair */
int1 = randIntBetween(0, cPrimeNumbers);
int2 = randIntBetween(0, cPrimeNumbers);
P = llList2Integer(PrimeNumbers, int1);
Q = llList2Integer(PrimeNumbers, int2);
keygen_RSA(P, Q);
BlkLen = BitLength(m);
}
// RSA-Crypt
integer RSA_crypt (integer basis, integer exponent, integer modulus) {
integer sum = 0;
integer mask = 1;
integer ergebnis = 1;
while (sum < exponent) {
if ((exponent&mask) != 0) {
ergebnis = (ergebnis*basis) % modulus;
sum = sum + (exponent&mask);
}
basis = (basis*basis) % modulus;
mask = mask << 1;
}
return ergebnis;
}
string RSA_encode (string Klartext) {
string Chiffre = "";
integer KlLength = llStringLength(Klartext);
BlkLen = BitLength(m);
integer tmp;
integer i;
integer j;
while ((KlLength % llFloor((BlkLen - 1)/8)) != 0){
Klartext = Klartext + " ";
}
for (i=0; i < KlLength; i++) {
tmp = UTF8ToUnicodeInteger(llGetSubString(Klartext, i, i));
j = 1;
while (((j+1)*8) < BlkLen) {
tmp = tmp << 8;
tmp = tmp + UTF8ToUnicodeInteger(llGetSubString(Klartext, i + j, i + j));
j++;
}
if (j > 0) i = i + (j - 1);
Chiffre = Chiffre + " " + (string)RSA_crypt((integer)tmp, e, m);
}
return Chiffre;
}
string num_decode (integer Num) {
integer temp = Num;
string result = "";
Num = Num >> 8;
if (Num > 0){
result = num_decode(Num);
}
return result + UnicodeIntegerToUTF8(temp & 255);
}
// Decode the encrypted String
// Change from processing with a list to String-Manipulations
string RSA_decode (string Geheimtext) {
string Klartext = "";
integer Klarnum;
integer pos; // To find the spaces in the String
do{
pos = llSubStringIndex(Geheimtext, " ");
Klarnum = RSA_crypt((integer)llGetSubString(Geheimtext, 0, pos), d, m);
Klartext += num_decode(Klarnum);
Geheimtext = llGetSubString(Geheimtext, pos + 1, -1);
} while(pos != -1); // Until we found the last space in the string
return Klartext;
}
default*{
state_entry(){
llListen(1, "", llGetOwner(), "");
}
listen(integer channel, string name, key id, string message)
{
if(id == llGetOwner())
{
if(message == "keygen"){
RSA_keygen();
}
else
{
string cipher = RSA_encode(message);
llOwnerSay("cipher: " + cipher);
string decipher = RSA_decode(cipher);
llOwnerSay("decipher: " + decipher);
}
}
}
}
