Drago Drago - 6 months ago 29
Java Question

Using RSA for modulo-multiplication leads to error on Java Card

Hello I'm working on a project on Java Card which implies a lot of modulo-multiplication. I managed to implement an modulo-multiplication on this platform using RSA cryptosystem but it seems to work for certain numbers.

public byte[] modMultiply(byte[] x, short xOffset, short xLength, byte[] y,
short yOffset, short yLength, short tempOutoffset) {

//copy x value to temporary rambuffer
Util.arrayCopy(x, xOffset, tempBuffer, tempOutoffset, xLength);


// copy the y value to match th size of rsa_object
Util.arrayFillNonAtomic(eempromTempBuffer, (short)0, (byte) (Configuration.LENGTH_RSAOBJECT_MODULUS-1),(byte)0x00);
Util.arrayCopy(y,yOffset,eempromTempBuffer,(short)(Configuration.LENGTH_RSAOBJECT_MODULUS - yLength),yLength);

// x+y
if (JBigInteger.add(x,xOffset,xLength, eempromTempBuffer,
(short)0,Configuration.LENGTH_MODULUS)) ;
if(this.isGreater(x, xOffset, xLength, tempBuffer,Configuration.TEMP_OFFSET_MODULUS, Configuration.LENGTH_MODULUS)>0)
{
JBigInteger.subtract(x,xOffset,xLength, tempBuffer,
Configuration.TEMP_OFFSET_MODULUS, Configuration.LENGTH_MODULUS);
}

//(x+y)2
mRsaCipherForSquaring.init(mRsaPublicKekForSquare, Cipher.MODE_ENCRYPT);

mRsaCipherForSquaring.doFinal(x, xOffset, Configuration.LENGTH_RSAOBJECT_MODULUS, x,
xOffset); // OK

mRsaCipherForSquaring.doFinal(tempBuffer, tempOutoffset, Configuration.LENGTH_RSAOBJECT_MODULUS, tempBuffer, tempOutoffset); // OK


if (JBigInteger.subtract(x, xOffset, Configuration.LENGTH_MODULUS, tempBuffer, tempOutoffset,
Configuration.LENGTH_MODULUS)) {
JBigInteger.add(x, xOffset, Configuration.LENGTH_MODULUS, tempBuffer,
Configuration.TEMP_OFFSET_MODULUS, Configuration.LENGTH_MODULUS);
}

mRsaCipherForSquaring.doFinal(eempromTempBuffer, yOffset, Configuration.LENGTH_RSAOBJECT_MODULUS, eempromTempBuffer, yOffset); //OK


if (JBigInteger.subtract(x, xOffset, Configuration.LENGTH_MODULUS, eempromTempBuffer, yOffset,
Configuration.LENGTH_MODULUS)) {

JBigInteger.add(x, xOffset, Configuration.LENGTH_MODULUS, tempBuffer,
Configuration.TEMP_OFFSET_MODULUS, Configuration.LENGTH_MODULUS);

}
// ((x+y)^2 - x^2 -y^2)/2
JBigInteger.modular_division_by_2(x, xOffset,Configuration. LENGTH_MODULUS, tempBuffer, Configuration.TEMP_OFFSET_MODULUS, Configuration.LENGTH_MODULUS);
return x;
}


public static boolean add(byte[] x, short xOffset, short xLength, byte[] y,
short yOffset, short yLength) {
short digit_mask = 0xff;
short digit_len = 0x08;
short result = 0;
short i = (short) (xLength + xOffset - 1);
short j = (short) (yLength + yOffset - 1);

for (; i >= xOffset; i--, j--) {
result = (short) (result + (short) (x[i] & digit_mask) + (short) (y[j] & digit_mask));

x[i] = (byte) (result & digit_mask);
result = (short) ((result >> digit_len) & digit_mask);
}
while (result > 0 && i >= xOffset) {
result = (short) (result + (short) (x[i] & digit_mask));
x[i] = (byte) (result & digit_mask);
result = (short) ((result >> digit_len) & digit_mask);
i--;
}

return result != 0;
}
public static boolean subtract(byte[] x, short xOffset, short xLength, byte[] y,
short yOffset, short yLength) {
short digit_mask = 0xff;
short i = (short) (xLength + xOffset - 1);
short j = (short) (yLength + yOffset - 1);
short carry = 0;
short subtraction_result = 0;

for (; i >= xOffset && j >= yOffset; i--, j--) {
subtraction_result = (short) ((x[i] & digit_mask)
- (y[j] & digit_mask) - carry);
x[i] = (byte) (subtraction_result & digit_mask);
carry = (short) (subtraction_result < 0 ? 1 : 0);
}
for (; i >= xOffset && carry > 0; i--) {
if (x[i] != 0)
carry = 0;
x[i] -= 1;
}

return carry > 0;
}



public short isGreater(byte[] x,short xOffset,short xLength,byte[] y ,short yOffset,short yLength)
{
if(xLength > yLength)
return (short)1;
if(xLength < yLength)
return (short)(-1);
short digit_mask = 0xff;
short digit_len = 0x08;
short result = 0;
short i = (short) (xLength + xOffset - 1);
short j = (short) (yLength + yOffset - 1);

for (; i >= xOffset; i--, j--) {
result = (short) (result + (short) (x[i] & digit_mask) - (short) (y[j] & digit_mask));
if(result > 0)
return (short)1;
if(result < 0)
return (short)-1;
}
return 0;
}


The code works well for little number but fails on bigger one

Answer

I managed to solve the problem by changing the mathematical formula of multiplication.I posted below the updated code.

private byte[] multiply(byte[] x, short xOffset, short xLength, byte[] y,
        short yOffset, short yLength,short tempOutoffset)
{
    normalize();
    //copy x value to temporary rambuffer
    Util.arrayFillNonAtomic(tempBuffer, tempOutoffset,(short) (Configuration.LENGTH_RSAOBJECT_MODULUS+tempOutoffset),(byte)0x00);
    Util.arrayCopy(x, xOffset, tempBuffer, (short)(Configuration.LENGTH_RSAOBJECT_MODULUS - xLength), xLength);

    // copy the y value to match th size of rsa_object
    Util.arrayFillNonAtomic(ram_y, IConsts.OFFSET_START, (short) (Configuration.LENGTH_RSAOBJECT_MODULUS-1),(byte)0x00);
    Util.arrayCopy(y,yOffset,ram_y,(short)(Configuration.LENGTH_RSAOBJECT_MODULUS - yLength),yLength);

    Util.arrayFillNonAtomic(ram_y_prime, IConsts.OFFSET_START, (short) (Configuration.LENGTH_RSAOBJECT_MODULUS-1),(byte)0x00);
    Util.arrayCopy(y,yOffset,ram_y_prime,(short)(Configuration.LENGTH_RSAOBJECT_MODULUS - yLength),yLength);

    Util.arrayFillNonAtomic(ram_x, IConsts.OFFSET_START, (short) (Configuration.LENGTH_RSAOBJECT_MODULUS-1),(byte)0x00);
    Util.arrayCopy(x,xOffset,ram_x,(short)(Configuration.LENGTH_RSAOBJECT_MODULUS - xLength),xLength);

    // if x>y
    if(this.isGreater(ram_x, IConsts.OFFSET_START, Configuration.LENGTH_RSAOBJECT_MODULUS, ram_y,IConsts.OFFSET_START, Configuration.LENGTH_MODULUS)>0)
    {

        // x <- x-y
        JBigInteger.subtract(ram_x,IConsts.OFFSET_START,Configuration.LENGTH_RSAOBJECT_MODULUS, ram_y,
                IConsts.OFFSET_START, Configuration.LENGTH_RSAOBJECT_MODULUS);
    }
    else
    {

        // y <- y-x
        JBigInteger.subtract(ram_y_prime,IConsts.OFFSET_START,Configuration.LENGTH_RSAOBJECT_MODULUS, ram_x,
                IConsts.OFFSET_START, Configuration.LENGTH_MODULUS);
         // ramy stores the (y-x) values copy value to ram_x
        Util.arrayCopy(ram_y_prime, IConsts.OFFSET_START,ram_x,IConsts.OFFSET_START,Configuration.LENGTH_RSAOBJECT_MODULUS);

    }

        //|x-y|2
        mRsaCipherForSquaring.init(mRsaPublicKekForSquare, Cipher.MODE_ENCRYPT);
        mRsaCipherForSquaring.doFinal(ram_x, IConsts.OFFSET_START, Configuration.LENGTH_RSAOBJECT_MODULUS, ram_x,
                IConsts.OFFSET_START); // OK

        // x^2
        mRsaCipherForSquaring.doFinal(tempBuffer, tempOutoffset, Configuration.LENGTH_RSAOBJECT_MODULUS, tempBuffer, tempOutoffset); // OK

        // y^2
        mRsaCipherForSquaring.doFinal(ram_y,IConsts.OFFSET_START, Configuration.LENGTH_RSAOBJECT_MODULUS, ram_y,IConsts.OFFSET_START); //OK 



        if (JBigInteger.add(ram_y, IConsts.OFFSET_START, Configuration.LENGTH_MODULUS, tempBuffer, tempOutoffset,
                Configuration.LENGTH_MODULUS)) {
              // y^2 + x^2 
            JBigInteger.subtract(ram_y, IConsts.OFFSET_START, Configuration.LENGTH_MODULUS, tempBuffer,
                    Configuration.TEMP_OFFSET_MODULUS, Configuration.LENGTH_MODULUS);
        } 


        //  x^2 + y^2
        if (JBigInteger.subtract(ram_y, IConsts.OFFSET_START, Configuration.LENGTH_MODULUS, ram_x, IConsts.OFFSET_START,
                Configuration.LENGTH_MODULUS)) {

            JBigInteger.add(ram_y, IConsts.OFFSET_START, Configuration.LENGTH_MODULUS, tempBuffer,
                    Configuration.TEMP_OFFSET_MODULUS, Configuration.LENGTH_MODULUS);
    }
    // (x^2 + y^2 - (x-y)^2)/2
   JBigInteger.modular_division_by_2(ram_y, IConsts.OFFSET_START,Configuration. LENGTH_MODULUS, tempBuffer, Configuration.TEMP_OFFSET_MODULUS, Configuration.LENGTH_MODULUS);
   return ram_y;
}

The problem was that for some numbers for same numbers a and b on 1024 bits the sum a+b overcome the value p of the modulus.In above code I subtract from a+b the p value in order to make the RSA functioning.But this thing is not mathematically correct because (a+b)^2 mod p is different from ((a+b) mod p)^2 mod p . By changing the formula from ((x+y)^2 -x^2 -y^2)/2 to (x^2 + y^2 - (x-y)^2)/2 I was sure I will never have overflow because a-b is smaller than p. Based on link above I changed the code moving all the operations in RAM.

Comments