字节数组的快速位移 - CMAC 子键

Question

我需要在 JavaCard.

中尽可能快地实现 16 字节数组的左移

我试过这段代码：

private static final void rotateLeft(final byte[] output, final byte[] input) {
         short carry = 0;
         short i = (short) 16;
         do {
             --i;
             carry = (short)((input[i] << 1) | carry);
             output[i] = (byte)carry;
             carry = (short)((carry >> 8) & 1);
         } while (i > 0);
}

有什么提高性能的想法吗？我正在考虑一些 Util.getShort(...) 和 Util.setShort(...) 魔法，但我没能让它比上面的实现更快地工作。

这是 CMAC 子密钥计算的一部分，不幸的是，它经常被执行。如果您知道一些更快的计算 CMAC 子密钥的方法（一个循环中的两个子密钥或类似的东西），请告诉我。

Answer 1

就速度而言，已知长度的硬编码版本是最快的（但很丑）。如果您需要移动多于一位，请确保相应地更新代码。

output[0] = (byte)((byte)(input[0] << 1) | (byte)((input[1] >> 7) & 1));
output[1] = (byte)((byte)(input[1] << 1) | (byte)((input[2] >> 7) & 1));
output[2] = (byte)((byte)(input[2] << 1) | (byte)((input[3] >> 7) & 1));
output[3] = (byte)((byte)(input[3] << 1) | (byte)((input[4] >> 7) & 1));
output[4] = (byte)((byte)(input[4] << 1) | (byte)((input[5] >> 7) & 1));
output[5] = (byte)((byte)(input[5] << 1) | (byte)((input[6] >> 7) & 1));
output[6] = (byte)((byte)(input[6] << 1) | (byte)((input[7] >> 7) & 1));
output[7] = (byte)((byte)(input[7] << 1) | (byte)((input[8] >> 7) & 1));
output[8] = (byte)((byte)(input[8] << 1) | (byte)((input[9] >> 7) & 1));
output[9] = (byte)((byte)(input[9] << 1) | (byte)((input[10] >> 7) & 1));
output[10] = (byte)((byte)(input[10] << 1) | (byte)((input[11] >> 7) & 1));
output[11] = (byte)((byte)(input[11] << 1) | (byte)((input[12] >> 7) & 1));
output[12] = (byte)((byte)(input[12] << 1) | (byte)((input[13] >> 7) & 1));
output[13] = (byte)((byte)(input[13] << 1) | (byte)((input[14] >> 7) & 1));
output[14] = (byte)((byte)(input[14] << 1) | (byte)((input[15] >> 7) & 1));
output[15] = (byte)(input[15] << 1);

并使用RAM字节数组！

Answer 2

当使用相同的密钥（即相同的 DESFire EV1 会话密钥）重复签名时，缓存 CMAC 子密钥可能会有所帮助。给定键的子键始终相同。

我认为 David 的回答可能会更快，如果它使用两个局部变量来缓存从输入数组的相同偏移量读取两次的值（根据我对 JCOP 的观察，即使对于瞬态数组，数组访问也非常昂贵).

编辑：我可以提供以下实现，它使用 short 进行 4 位右移（支持它的卡的 32 位 int 变体会更快）：

short pom=0; // X000 to be stored next
short pom2; // loaded value
short pom3; // 0XXX to be stored next
short curOffset=PARAMS_TRACK2_OFFSET;
while(curOffset<16) {
    pom2=Util.getShort(mem_PARAMS, curOffset);
    pom3=(short)(pom2>>>4);
    curOffset=Util.setShort(mem_RAM, curOffset, (short)(pom|pom3));
    pom=(short)(pom2<<12);
}

注意，此代码假定源和目标中的偏移量相同。

如果需要，您可以展开此循环并使用常量参数。

Answer 3

这是我能想到的旋转任意位数的最快算法（我旋转了 8 个字节的数组，您可以轻松地将其转换为移位 16）：

使用 EEPROM 为您的班次创建掩码 table。 Mask 只是从右边开始增加 1 的数量：

final static byte[] ROTL_MASK = {
    (byte) 0x00, //shift 0: 00000000 //this one is never used, we don't do shift 0.
    (byte) 0x01, //shift 1: 00000001
    (byte) 0x03, //shift 2: 00000011
    (byte) 0x07, //shift 3: 00000111
    (byte) 0x0F, //shift 4: 00001111
    (byte) 0x1F, //shift 5: 00011111
    (byte) 0x3F, //shift 6: 00111111
    (byte) 0x7F  //shift 7: 01111111
};

如果移位大于 8，则首先使用 Util.arrayCopyNonAtomic 快速交换字节：

final static byte BITS = 8;
//swap whole bytes:
Util.arrayCopyNonAtomic(in, (short) (shift/BITS), out, (short) 0, (short) (8-(shift/BITS)));
Util.arrayCopyNonAtomic(in, (short) 0, out, (short) (8-(shift/BITS)), (short) (shift/BITS));
shift %= BITS; //now we need to shift only up to 8 remaining bits

if (shift > 0) {
    //apply masks
    byte mask = ROTL_MASK[shift];
    byte comp = (byte) (8 - shift);

    //rotate using masks
    out[8] = in[0]; // out[8] is any auxiliary variable, careful with bounds!
    out[0] = (byte)((byte)(in[0] << shift) | (byte)((in[1] >> comp) & mask));
    out[1] = (byte)((byte)(in[1] << shift) | (byte)((in[2] >> comp) & mask));
    out[2] = (byte)((byte)(in[2] << shift) | (byte)((in[3] >> comp) & mask));
    out[3] = (byte)((byte)(in[3] << shift) | (byte)((in[4] >> comp) & mask));
    out[4] = (byte)((byte)(in[4] << shift) | (byte)((in[5] >> comp) & mask));
    out[5] = (byte)((byte)(in[5] << shift) | (byte)((in[6] >> comp) & mask));
    out[6] = (byte)((byte)(in[6] << shift) | (byte)((in[7] >> comp) & mask));
    out[7] = (byte)((byte)(in[7] << shift) | (byte)((in[8] >> comp) & mask));
}

您还可以删除 mask 变量并改用对 table 的直接引用。

事实证明，使用这种方式而不是简单地实现逐位旋转的速度提高了大约 450% - 500%。

字节数组的快速位移 - CMAC 子键

Fast bit shift of a byte array - CMAC subkeys

performance

cryptography

bit-manipulation

bit-shift

javacard