Welcome to the Second Life Forums Archive

These forums are CLOSED. Please visit the new forums HERE

RSA Cryptography

Moose Pegler
Registered User
Join date: 22 Apr 2006
Posts: 33
10-31-2006 02:23
Here's a script that does RSA ("public key";) cryptography. The modular exponentiation function can be used for other public key schemes.

It's seriously slow so I'm hoping that the optimizers out there will tune it up.

Enjoy!

Cheers, Moose

CODE

//
// RSA Cryptography for LSL
//
// Moose Pegler, October 31, 2006
//
// "It's not how well the dog sings, it's that the dog sings at all."

// A BigNum is a list: LeastSignificantDigit ... MostSignificantDigit Width

integer DIGITLOGBITS = 4;
integer DIGITLOGMASK = 0x0F;
integer DIGITBITS = 16;
integer DIGITMASK = 0xFFFF;
integer OVERFLOWMASK = 0xFFFF0000;
integer DIGITMSBIT = 0x00008000;
integer SIGNBIT = 0x80000000;
integer WIDTHDIGIT = 5;

integer shiftLength;

//list SetDigit(list a, integer n, integer value);
//list SetDigit2(list a, integer n, integer value1, integer value2);
//integer GetDigit(list a, integer n);
//list SetWidth(list a, integer width);
//integer GetWidth(list a);

//list BigNumZero(integer width);
//list BigNumFromInt(integer value);
//integer BigNumBitIsSet(list a, integer bitIndex);
//integer BigNumNumSignificantDigits(list a);
//integer BigNumUCompare(list a, list b);
//list BigNumUShiftRight(list operand, integer shiftSize, integer operandLength);
//list BigNumUShiftLeft(list operand, integer shiftSize, integer operandLength);
//list BigNumMod(list a, list p);
//list BigNumSub(list a, list b);
//integer BigNumEstimateQuotientDigit(integer u2, integer u1, integer u0, integer v1, integer v0);
//list BigNumDivide(list a, list p, integer qorr);
//integer BigNumNi0(integer n);
//list BigNumMod(list a, list p);
//list BigNumModMult(list a, list b1, list n, integer ni0);
//list BigNumModExp(list a, list b, list n, integer ni0);

//integer unsigned_divide(integer dividend, integer divisor);
//integer greater_than(integer a, integer b);

//integer encrypt(integer plaintext, integer privateKey, integer modulus);
//integer decrypt(integer cryptogram, integer publicKey, integer modulus);

integer p=167;
integer q=347;
integer modulus = 57949;
integer publickey = 40097;
integer privatekey = 25533;

//integer p=5483;
//integer q=2819;
//integer modulus = 15456577;
//integer publickey = 4780727;
//integer privatekey = 12951387;

integer encrypt(integer plaintext, integer privateKey, integer modulus)
{
list n;
list m;
list d;
list c;

n = BigNumFromInt(modulus);
d = BigNumFromInt(privateKey);
m = BigNumFromInt(plaintext);

c = BigNumModExp(m, d, n, BigNumNi0(modulus));

return (GetDigit(c, 1)<<DIGITBITS) | GetDigit(c, 0);
}

integer decrypt(integer cryptogram, integer publicKey, integer modulus)
{
list n;
list m;
list e;
list c;

n = BigNumFromInt(modulus);
e = BigNumFromInt(publicKey);
c = BigNumFromInt(cryptogram);

m = BigNumModExp(c, e, n, BigNumNi0(modulus));

return GetDigit(m, 1)<<DIGITBITS | GetDigit(m, 0);
}

list SetDigit(list a, integer n, integer value)
{
return llListReplaceList(a, [value & DIGITMASK], n, n);
}

list SetDigit2(list a, integer n, integer value1, integer value2)
{
return llListReplaceList(a, [value1 & DIGITMASK, value2 & DIGITMASK], n, n+1);
}

integer GetDigit(list a, integer n)
{
return llList2Integer(a, n) & DIGITMASK;
}

list SetWidth(list a, integer width)
{
return llListReplaceList(a, [width & DIGITMASK], WIDTHDIGIT, WIDTHDIGIT);
}

integer GetWidth(list a)
{
return llList2Integer(a, WIDTHDIGIT);
}

list BigNumModExp(list a, list b, list n, integer ni0)
{
integer w;
integer counter = 0;
integer stage = 0;
list t;

t = BigNumFromInt(0);

while(TRUE)
{
if(stage == 0)
{
// Set counter to the most significant exponent bit that is non-zero.
w = GetWidth(b);
for (counter = (w * DIGITBITS) - 1; counter >= 0; --counter)
{
if (BigNumBitIsSet(b, counter))
jump break;
}
@break;
if (!BigNumBitIsSet(b, counter))
{
return BigNumFromInt(1);
}

t = a;
if (counter == 0)
{
stage = 2;
}
else
{
--counter;
++stage;
}
}
else if (stage == 1)
{

t = BigNumModMult(t, t, n, ni0);
if (BigNumBitIsSet(b, counter))
{
// Exponent bit is set, multiply by a
t = BigNumModMult(t, a, n, ni0);
}
if ( counter > 0 )
{
--counter;
}
else
{
++stage;
}
}
else if (stage == 2)
{
jump done;
}
}
@done;
return t;
}

integer BigNumNi0(integer n)
{
integer temp;
integer y;
integer x;
integer ti;
integer mmi;
integer i;

x = n;
y = 1;
ti = 2;
mmi = 3;
for (i = 1; i < DIGITBITS; i++)
{
temp = (x*y) & DIGITMASK;
temp = temp & mmi;
if (ti < temp)
{
y = (y + ti) & DIGITMASK;
}
ti = (ti << 1) & DIGITMASK;
mmi = (( mmi << 1 ) | 0x1) & DIGITMASK;
}

// ni0 = -y mod 2**w
y = (y ^ DIGITMASK);
y = (y + 1) & DIGITMASK;

return y;
}

// Koc, C.K., T. Acar, B. S. Kaliski, "Analyzing and Comparing Montgomery
// Multiplication Algorithms, IEEE Micro, 16 (3), June, 1996, pp. 26-33.
// Algorithm is the Coarse Operand Integration Scanning (COIS)
list BigNumModMult(list a, list b1, list n, integer ni0)
{
integer temp;
integer carry_or_borrow;
integer m;
integer s;
integer i;
integer j;
integer w;
list amNum;
list tNum;
list bNum;

w = GetWidth(n);
amNum = BigNumZero(2*w);
for (i = 0; i < w; i++)
{
amNum = SetDigit(amNum, i + w, GetDigit(a, i));
}

amNum = BigNumMod(amNum, n);

s = GetWidth(amNum);

tNum = BigNumZero(s);
bNum = BigNumZero(s);
w = GetWidth(b1);
for (i = 0; i < w; i++)
{
bNum = SetDigit(bNum, i, GetDigit(b1, i));
}
for (i = 0; i < s; i++)
{
carry_or_borrow = 0;
m = GetDigit(bNum, i);
for (j = 0; j < s; j++)
{
temp = GetDigit(tNum, j) + GetDigit(amNum, j) * m + carry_or_borrow;
tNum = SetDigit(tNum, j, temp);
carry_or_borrow = (temp>>DIGITBITS) & DIGITMASK;
}

temp = GetDigit(tNum, s) + carry_or_borrow;
carry_or_borrow = (temp>>DIGITBITS) & DIGITMASK;
tNum = SetDigit2(tNum, s, temp, carry_or_borrow);

m = (GetDigit(tNum, 0) * ni0) & DIGITMASK;
temp = GetDigit(tNum, 0) + m * GetDigit(n, 0);
carry_or_borrow = (temp>>DIGITBITS) & DIGITMASK;

for (j = 1; j < s; j++)
{
temp = GetDigit(tNum, j) + m * GetDigit(n, j) + carry_or_borrow;
tNum = SetDigit(tNum, j - 1, temp);
carry_or_borrow = (temp>>DIGITBITS) & DIGITMASK;
}
temp = GetDigit(tNum, s) + carry_or_borrow;
carry_or_borrow = (temp>>DIGITBITS) & DIGITMASK;
tNum = SetDigit2(tNum, s - 1, temp, GetDigit(tNum, s + 1) + carry_or_borrow);
}

carry_or_borrow = 0;
for (j = 0; j <= s; j++)
{
temp = GetDigit(tNum, j) - GetDigit(n, j) - carry_or_borrow;
amNum = SetDigit(amNum, j, temp);
carry_or_borrow = (temp >> DIGITBITS) & DIGITMASK;
if (carry_or_borrow != 0)
carry_or_borrow = 1;
}

if (carry_or_borrow == 0)
{
return amNum;
}
else
{
return tNum;
}
}

list BigNumMod(list a, list p)
{
return BigNumDivide(a, p, FALSE);
}

// Kunth, D., The Art of Computer Programming, VOLUME 2, Seminumerical Algorithms, 2nd Edition
// Algorithm D, Section 4.3.1 p272-273.
list BigNumDivide(list dividend1, list divisor1, integer qorr)
{
integer i;
integer temp;
integer overflow;
integer shiftSize = 0;
integer divisorLen;
integer dividendLen;
integer counter;
integer numDigitsLeft;
integer msword;
integer q;
integer dsor0;
integer dsor1;
integer remainderLen;
integer quotientLen;
integer w;
list dividend;
list divisor;
list quotient;
list remainder;

if ((BigNumNumSignificantDigits(divisor1) == 1) && (GetDigit(divisor1, 0) == 0))
{
// Divide by zero error.
return dividend1;
}

if (BigNumUCompare(divisor1, dividend1) > 0)
{
if(qorr == 1)
return BigNumFromInt(0);
else
return dividend1;
}

quotient = BigNumFromInt(0);
remainder = BigNumFromInt(0);

dividend = dividend1;
divisor = divisor1;

divisorLen = BigNumNumSignificantDigits(divisor);
dividendLen = BigNumNumSignificantDigits(dividend);

// Normalize the divisor so that the most significant bit of most significant digit is set.
msword = GetDigit(divisor, divisorLen - 1);
while ((msword & DIGITMSBIT) == 0)
{
msword = msword << 1;
shiftSize++;
}

// Ensure that divisor is at least 2 digits
if (divisorLen == 1)
shiftSize += DIGITBITS;

if (shiftSize > 0)
{
divisor = BigNumUShiftLeft(divisor, shiftSize, divisorLen);
divisorLen = shiftLength;
dividend = BigNumUShiftLeft(dividend, shiftSize, dividendLen);
dividendLen = shiftLength;
}

remainderLen = divisorLen;

numDigitsLeft = dividendLen - divisorLen;
remainder = SetWidth(remainder, GetWidth(divisor1));
for (counter = 0; counter < divisorLen; ++counter)
{
remainder = SetDigit(remainder, counter, GetDigit(dividend, counter + numDigitsLeft));
}
remainderLen = divisorLen;

quotient = SetWidth(quotient, GetWidth(dividend1));

quotientLen = 1;

dsor0 = GetDigit(divisor, divisorLen - 2);
dsor1 = GetDigit(divisor, divisorLen - 1);

while(TRUE)
{
while ((remainderLen < divisorLen) && numDigitsLeft > 0)
{
quotient = BigNumUShiftLeft(quotient, DIGITBITS, quotientLen);
quotientLen = shiftLength;
remainder = BigNumUShiftLeft(remainder, DIGITBITS, remainderLen);
remainderLen = shiftLength;
// Insert new least significant digit.
remainder = SetDigit(remainder, 0, GetDigit(dividend, numDigitsLeft - 1));
numDigitsLeft--;
}
// Ensure that the remainder < divisor.
if (BigNumUCompare(divisor, remainder) <= 0)
{
remainder = BigNumSub(remainder, divisor);
remainderLen = BigNumNumSignificantDigits(remainder);
quotient = SetDigit(quotient, 0, GetDigit(quotient, 0)+1);
jump continue;
}
if (numDigitsLeft == 0)
jump next;

quotient = BigNumUShiftLeft(quotient, DIGITBITS, quotientLen);
quotientLen = shiftLength;
remainder = BigNumUShiftLeft(remainder, DIGITBITS, remainderLen);
remainderLen = shiftLength;
// Insert new least significant digit.
remainder = SetDigit(remainder, 0, GetDigit(dividend, numDigitsLeft - 1));
numDigitsLeft--;
// Heart of the algorithm; estimate next term of quotient
q = BigNumEstimateQuotientDigit(GetDigit(remainder, remainderLen - 1),
GetDigit(remainder, remainderLen - 2),
GetDigit(remainder, remainderLen - 3), dsor1, dsor0);
overflow = 0;
w = GetWidth(remainder) + 1;
for (i = 0; i <= w; i++)
{
temp = q * GetDigit(divisor, i) + overflow;
overflow = (temp & OVERFLOWMASK)>>DIGITBITS;
if (GetDigit(remainder, i) < (temp & DIGITMASK))
++overflow;
remainder = SetDigit(remainder, i, (GetDigit(remainder, i) - (temp & DIGITMASK)) & DIGITMASK);
}
counter = 2;
remainderLen = BigNumNumSignificantDigits(remainder);
quotient = SetDigit(quotient, 0, q);

@continue;
}

@next;
if (shiftSize > 0)
{
remainder = BigNumUShiftRight(remainder, shiftSize, remainderLen);
}

if(qorr)
{
return quotient;
}
else
{
return remainder;
}
}

integer BigNumEstimateQuotientDigit(integer u2, integer u1, integer u0, integer v1, integer v0)
{
integer r0;
integer u;
integer r;
integer p;
integer q0v0;
integer U1;
integer q0;

u = (u2 << (DIGITBITS)) | u1;

if(u >= 0)
{
q0 = u / v1;
}
else
{
q0 = unsigned_divide(u, v1);
}

p = q0 * v1;

if (q0 > DIGITMASK)
{
return DIGITMASK;
}

r = u - p;

r0 = (r & DIGITMASK);
U1 = (r0 << DIGITBITS) | u0;
q0v0 = q0 * v0;

while (greater_than(q0v0, U1))
{
q0--;
r += v1;
if ( r > DIGITMASK )
jump done;
r0 = (r & DIGITMASK);
U1 = (r0 << DIGITBITS) | u0;
q0v0 = q0 * v0;
}

@done;
return q0 & DIGITMASK;
}

// Special case of subtraction for BigNumDivide
// a and b non-negative and a > b
list BigNumSub(list a, list b)
{
integer temp;
integer overflow;
integer i;
integer w;
integer length;
list t;

t = BigNumFromInt(0);

length = GetWidth(a) - GetWidth(b);
overflow = 0;
if (length == 0)
{
w = GetWidth(a);
for (i = 0; i <= w; i++)
{
temp = GetDigit(a,i) - GetDigit(b, i) - overflow;
t = SetDigit(t, i, temp);
if(temp & OVERFLOWMASK)
overflow = 1;
else
overflow = 0;
}
}
else if (length > 0)
{
w = GetWidth(b);
for (i = 0; i <= w; i++)
{
temp = GetDigit(a,i) - GetDigit(b, i) - overflow;
t = SetDigit(t, i, temp);
if(temp & OVERFLOWMASK)
overflow = 1;
else
overflow = 0;
}
}

return t;
}

list BigNumUShiftRight(list operand, integer shiftSize, integer operandLength)
{
integer i;
integer j;
integer length;
integer w;
integer wordShifts;
integer carry;
integer temp;
list value;

if (shiftSize == 0)
return operand;

wordShifts = (shiftSize / DIGITBITS);

length = (operandLength - wordShifts);
shiftSize %= DIGITBITS;

value = operand;

// Do word shifts
if (wordShifts > 0)
{
for (j = 0; j < length; j++)
value = SetDigit(value, j, GetDigit(operand, j + wordShifts));
}

// Zero out the digits above the new most significant digit
w = GetWidth(operand);
for (j = length; j < w; j++)
value = SetDigit(value, j, 0);

// Do bit shifts
if (shiftSize > 0)
{
carry = 0;
for (i = (integer )(length - 1); i >= 0; i--)
{
temp = (carry | (GetDigit(value, i) >> shiftSize)) & DIGITMASK;
carry = (GetDigit(value, i) << (DIGITBITS - shiftSize));
value = SetDigit(value, i, temp);
}
}

if(GetDigit(value, length - 1) > 0)
shiftLength = length;
else
shiftLength = length - 1;

return value;
}

list BigNumUShiftLeft(list operand, integer shiftSize, integer operandLength)
{
integer wordShifts;
integer i;
integer j;
integer length;
integer carry;
integer temp;
list value;

if (shiftSize == 0 || (operandLength == 1 && GetDigit(operand, 0) == 0))
return operand;

wordShifts = (shiftSize / DIGITBITS);
length = (operandLength + wordShifts);
shiftSize %= DIGITBITS;

value = operand;

// Do word shifts
if (wordShifts> 0)
{
for (j = (length - 1); j >= wordShifts; j--)
value = SetDigit(value, j, GetDigit(value, j - wordShifts));
for (j = 0; j < wordShifts; j++)
value = SetDigit(value, j, 0);
}

// Do bit shifts
if (shiftSize > 0)
{
carry = 0;
for (i = wordShifts; i < length; i++)
{
temp = (carry | (GetDigit(value, i) << shiftSize)) & DIGITMASK;
carry = (GetDigit(value, i) >> (DIGITBITS - shiftSize)) & DIGITMASK;
value = SetDigit(value, i, temp);
}
value = SetDigit(value, i, carry);
if(carry > 0)
shiftLength = i + 1;
else
shiftLength = i;
}
else
shiftLength = length;

return value;
}

integer BigNumUCompare(list a, list b)
{
integer i;
integer aLen;
integer bLen;
integer aD;
integer bD;

aLen = BigNumNumSignificantDigits(a);
bLen = BigNumNumSignificantDigits(b);

if (aLen != bLen)
{
if(aLen > bLen)
return 1;
else
return -1;
}

for (i = aLen - 1; i >= 0; i--)
{
aD = GetDigit(a, i);
bD = GetDigit(b, i);
if (aD != bD)
{
if(aD > bD)
return 1;
else
return -1;
}
}

return 0;
}

integer BigNumNumSignificantDigits(list a)
{
integer i;

for (i = GetWidth(a) - 1; i > 0; i--)
{
if (GetDigit(a, i) > 0)
{
return(i + 1);
}
}

return 1;
}

integer BigNumBitIsSet(list a, integer bitIndex)
{
integer temp;
integer value;

if (bitIndex >= (DIGITBITS * (1 + GetWidth(a))) )
{
return FALSE;
}

temp = (bitIndex >> DIGITLOGBITS);
value = GetDigit(a,temp);
temp = (bitIndex & DIGITLOGMASK);

if ((value & (1 << temp)) != 0)
return TRUE;
else
return FALSE;
}

list BigNumFromInt(integer value)
{
list bignum;

bignum = [value & DIGITMASK,(value & OVERFLOWMASK)>>DIGITBITS,0,0,0,2];

return bignum;
}

list BigNumZero(integer width)
{
// Make sure this matches with WIDTHDIGIT
return [0,0,0,0,0,width];
}

integer unsigned_divide(integer dividend, integer divisor)
{
integer t;
integer num_bits;
integer q;
integer bit;
integer d;
integer i;
integer remainder = 0;
integer quotient = 0;

if (divisor == 0)
return 0;

if (divisor == dividend)
{
quotient = 1;
}

num_bits = 32;

while (remainder < divisor)
{
bit = ((dividend & 0x80000000) >> 31) & 0x00000001;
remainder = (remainder << 1) | bit;
d = dividend;
dividend = dividend << 1;
num_bits--;
}

dividend = d;
remainder = remainder >> 1;
num_bits++;

for (i = 0; i < num_bits; i++)
{
bit = (dividend & 0x80000000) >> 31;
remainder = (remainder << 1) | bit;
t = remainder - divisor;
q = !((t & 0x80000000) >> 31);
dividend = dividend << 1;
quotient = (quotient << 1) | q;
if (q)
remainder = t;
}

return quotient;
}

integer greater_than(integer a, integer b)
{
integer sign = 0x80000000;

if((a & sign) != (b & sign))
{
if(a & sign)
return TRUE;
else
return FALSE;
}
a = a & ~sign;
b = b & ~sign;

return (a > b);
}

default
{
state_entry()
{
integer c;
integer m;

m = 1000;
c = encrypt(m, privatekey, modulus);
llSay(0, "The encryption of "+(string)m+" is "+(string)c);
m = decrypt(c, publickey, modulus);
llSay(0, "The decryption of "+(string)c+" is "+(string)m);
}
}
Nada Epoch
The Librarian
Join date: 4 Nov 2002
Posts: 1,423
Discussion Thread
11-02-2006 13:43
/54/8c/146901/1.html
_____________________
i've got nothing. ;)