使用RSA进行模乘会导致Java卡出错 [英] Using RSA for modulo-multiplication leads to error on Java Card
问题描述
您好,我正在开发一个Java卡项目,这意味着很多模乘法。我设法使用RSA密码系统在这个平台上实现一个模乘法,但它似乎适用于某些数字。
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
推荐答案
我设法通过更改乘法的数学公式来解决问题。我在更新的代码下面发布。
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;
}
< a 和 b
在1024位上的总和 a + b
克服值<$ c在上面的代码中,我从 a + b
减去 p $ c $这个东西在数学上是不正确的,因为
(a + b)^ 2 mod p
不同于 ((a + b)mod p)^ 2 mod p
。通过将公式从((x + y)^ 2 -x ^ 2 -y ^ 2)/ 2
更改为(x ^ 2 + y ^ 2 - (xy)^ 2)/ 2
我肯定我永远不会溢出,因为 ab
小于 p
。根据上面的链接,我更改了该代码移动RAM中的所有操作。
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.
这篇关于使用RSA进行模乘会导致Java卡出错的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!