使用 RSA 进行模乘会导致 Java 卡上出现错误

Question

你好，我正在做一个关于 Java Card 的项目，这意味着很多模乘法。我设法使用 RSA 密码系统在此平台上实现模乘，但它似乎适用于某些数字。

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

该代码适用于小数字但大数字失败

Answer 1

下面是一个非常简单的单元测试，其中包含您代码的（希望）工作变体：

package test.java.so;

import java.math.BigInteger;
import java.util.Random;

import javacard.framework.JCSystem;
import javacard.framework.Util;
import javacard.security.KeyBuilder;
import javacard.security.RSAPublicKey;
import javacardx.crypto.Cipher;

import org.apache.commons.lang3.ArrayUtils;
import org.bouncycastle.util.Arrays;
import org.junit.Assert;
import org.junit.Test;

import sutil.test.AbstractTest;

public class So36966764_Test extends AbstractTest {

    private static final int NUM_BITS = 1024;

    // Dummy
    static class Configuration {
        public static final short LENGTH_MODULUS = NUM_BITS/8;
        public static final short LENGTH_RSAOBJECT_MODULUS = LENGTH_MODULUS;
        public static final short TEMP_OFFSET_MODULUS = 0;
        public static final short TEMP_OFFSET_RESULT = LENGTH_MODULUS;
    }

    private byte[] tempBuffer = JCSystem.makeTransientByteArray((short)(Configuration.TEMP_OFFSET_RESULT+Configuration.LENGTH_MODULUS), JCSystem.CLEAR_ON_DESELECT);
    private byte[] eempromTempBuffer = new byte[Configuration.LENGTH_MODULUS]; // Why EEPROM?
    private RSAPublicKey mRsaPublicKekForSquare = (RSAPublicKey)KeyBuilder.buildKey(KeyBuilder.TYPE_RSA_PUBLIC, (short)NUM_BITS, false);
    private Cipher mRsaCipherForSquaring = Cipher.getInstance(Cipher.ALG_RSA_NOPAD, false);

    // Assuming xLength==yLength==LENGTH_MODULUS
    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, (short) (Configuration.LENGTH_RSAOBJECT_MODULUS-1),(byte)0x00);
        Util.arrayCopy(y,yOffset,eempromTempBuffer,(short)(Configuration.LENGTH_RSAOBJECT_MODULUS - yLength),yLength);

        // x+y
        if(add(x,xOffset,xLength, eempromTempBuffer, (short)0,Configuration.LENGTH_MODULUS)) {
            subtract(x,xOffset,xLength, tempBuffer, Configuration.TEMP_OFFSET_MODULUS, Configuration.LENGTH_MODULUS);
        }
        while(isGreater(x, xOffset, xLength, tempBuffer,Configuration.TEMP_OFFSET_MODULUS, Configuration.LENGTH_MODULUS)>0) {
            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 (subtract(x, xOffset, Configuration.LENGTH_MODULUS, tempBuffer, tempOutoffset,
                Configuration.LENGTH_MODULUS)) {
            add(x, xOffset, Configuration.LENGTH_MODULUS, tempBuffer,
                    Configuration.TEMP_OFFSET_MODULUS, Configuration.LENGTH_MODULUS);
        }

        /*WRONG OFFSET mRsaCipherForSquaring.doFinal(eempromTempBuffer, yOffset, Configuration.LENGTH_RSAOBJECT_MODULUS, eempromTempBuffer, yOffset); */
        mRsaCipherForSquaring.doFinal(eempromTempBuffer, (short)0, Configuration.LENGTH_RSAOBJECT_MODULUS, eempromTempBuffer, (short)0); //OK

        /*WRONG OFFSET if (subtract(x, xOffset, Configuration.LENGTH_MODULUS, eempromTempBuffer, yOffset,*/
        if (subtract(x, xOffset, Configuration.LENGTH_MODULUS, eempromTempBuffer, (short)0,Configuration.LENGTH_MODULUS)) {
            add(x, xOffset, Configuration.LENGTH_MODULUS, tempBuffer,
                    Configuration.TEMP_OFFSET_MODULUS, Configuration.LENGTH_MODULUS);
        }
        // ((x+y)^2 - x^2 -y^2)/2
        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)
    {
        // Beware: this part is not tested
        while(xLength>yLength) {
            if(x[xOffset++]!=0x00) {
                return 1; // x is greater
            }
            xLength--;
        }
        while(yLength>xLength) {
            if(y[yOffset++]!=0x00) {
                return -1; // y is greater
            }
            yLength--;
        }
        // Beware: this part is not tested END
        for(short i = 0; i < xLength; i++) {
            if (x[xOffset] != y[yOffset]) {
                short srcShort = (short)(x[xOffset]&(short)0xFF);
                short dstShort = (short)(y[yOffset]&(short)0xFF);
                return ( ((srcShort > dstShort) ? (byte)1 : (byte)-1));
            }
            xOffset++;
            yOffset++;
        }
        return 0;
    }

    private void modular_division_by_2(byte[] input, short inOffset, short inLength, byte[] modulus, short modulusOffset, short modulusLength) {
        short carry = 0;
        short digit_mask = 0xff;
        short digit_first_bit_mask = 0x80;
        short lastIndex = (short) (inOffset + inLength - 1);

        short i = inOffset;
        if ((byte) (input[lastIndex] & 0x01) != 0) {
            if (add(input, inOffset, inLength, modulus, modulusOffset,
                    modulusLength)) {
                carry = digit_first_bit_mask;
            }
        }

        for (; i <= lastIndex; i++) {
            if ((input[i] & 0x01) == 0) {
                input[i] = (byte) (((input[i] & digit_mask) >> 1) | carry);
                carry = 0;
            } else {
                input[i] = (byte) (((input[i] & digit_mask) >> 1) | carry);
                carry = digit_first_bit_mask;
            }
        }
    }

    @Test
    public void testModMultiply() {
        Random r = new Random(12345L);
        for(int iiii=0;iiii<10;iiii++) {
            BigInteger modulus = BigInteger.probablePrime(NUM_BITS, r);
            System.out.println(" M = " + modulus);
            byte[] modulusBytes = normalize(modulus.toByteArray());
            Util.arrayCopyNonAtomic(modulusBytes, (short)0, tempBuffer, Configuration.TEMP_OFFSET_MODULUS, Configuration.LENGTH_MODULUS);

            mRsaPublicKekForSquare.setModulus(modulusBytes, (short)0, (short)modulusBytes.length);
            mRsaPublicKekForSquare.setExponent(new byte[] {0x02}, (short)0, (short)1);

            for(int iii=0;iii<1000;iii++) {
                BigInteger x = new BigInteger(NUM_BITS, r).mod(modulus);
                System.out.println(" x = " + x);
                BigInteger y = new BigInteger(NUM_BITS, r).mod(modulus);
                System.out.println(" y = " + y);
                BigInteger accResult;
                {
                    byte[] xBytes = normalize(x.toByteArray());
                    byte[] yBytes = normalize(y.toByteArray());
                    byte[] accResultBytes = modMultiply(xBytes, (short)0, (short)xBytes.length, yBytes, (short)0, (short)yBytes.length, Configuration.TEMP_OFFSET_RESULT);
                    accResult = new BigInteger(1, accResultBytes);
                }
                System.out.println(" Qr = " + accResult);
                BigInteger realResult = x.multiply(y).mod(modulus);
                System.out.println(" Rr = " + realResult);
                Assert.assertEquals(realResult, accResult);
            }
        }
    }

    private byte[] normalize(byte[] xBytes) {
        if(xBytes.length<Configuration.LENGTH_MODULUS) {
            xBytes = ArrayUtils.addAll(new byte[Configuration.LENGTH_MODULUS-xBytes.length], xBytes);
        }
        if(xBytes.length>Configuration.LENGTH_MODULUS) {
            Assert.assertEquals(xBytes[0], 0x00);
            xBytes=Arrays.copyOfRange(xBytes, 1, xBytes.length);
        }
        return xBytes;
    }
}

（恕我直言）错了什么：

isGreater()方法——虽然可以使用减法来比较数字，但从最重要的字节开始比较相应的字节并停止比较更容易（也更快）在第一次不匹配时。（在减法的情况下，您需要完成减法和 return 最终结果的符号——您的原始代码首先以 "mismatch" 结束。）
x+y 溢出——您应该在上次编辑中保留加法溢出情况下的模数减法（即当 add() return 为真时） .
Offsets into eempromTempBuffer —— 在两个地方你使用了 yOffset 而应该使用 0（用 "WRONG OFFSET" 注释掉）。
将 Configuration.LENGTH_RSAOBJECT_MODULUS-1 转换为 byte 对于较大的模数长度值来说不是一个好主意

一些（随机）评论：

测试使用已经提到的jcardsim工作
代码假设 x 和 y 的长度都是 LENGTH_MODULUS （以及 LENGTH_RSAOBJECT_MODULUS 等于 LENGTH_MODULUS)
将eempromTempBuffer放在非易失性存储器中不是一个好主意
您的代码与 this code 非常相似，这很有趣
有关此主题的有趣读物是 here（第 4.2.3 节）。

祝你好运！

免责声明：我不是加密专家也不是数学家所以请验证我的想法

Answer 2

我通过更改更新代码下方发布的 multiplication.I 的数学公式设法解决了问题。

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

问题是对于某些相同数字 a 和 b 在 1024 位上的和 a+b 克服了 [=29= 的值 p ] 上面的代码我从 a+b 中减去 p 值以使 RSA functioning.But 这个东西在数学上是不正确的，因为 (a+b)^2 mod p 不同于 ((a+b) mod p)^2 mod p 。通过将公式从 ((x+y)^2 -x^2 -y^2)/2 更改为 (x^2 + y^2 - (x-y)^2)/2，我确信我永远不会溢出，因为 a-b 小于 p。基于我更改了将所有操作移动到 RAM 中的代码。

使用 RSA 进行模乘会导致 Java 卡上出现错误

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

java

cryptography

rsa

javacard