问题描述
您好,我正在研究 Java Card 上的一个项目,这意味着很多模乘.我设法在这个平台上使用 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
克服了值 p
的模数.在上面的代码中,我从 a+b
中减去 p
值以使 RSA 正常工作.但这不是数学上的东西正确,因为 (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 Card 出错的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持跟版网!