字节数组的快速位移 - 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子密钥的方法（在一个循环中计算两个子密钥或类似的东西），请告诉我。

- vojta

---

我了解JavaCard是解释执行的。如果是这样，那么我建议您查看生成的字节码，并考虑可用指令集进行优化。例如，我怀疑int比short更可取，并且展开循环可能会为您赢得一些周期。除此之外，我认为您将会执行不止一个扩展精度算术运算，因此最好尽早切换到更宽的整数以实现更快的处理，并在最后将其转换回8位数组。 - doynax

@doynax，在JavaCard中没有int或long...你只有byte和short。 - vojta

@doynax 是的，JavaCard 真是个噩梦。谢谢，我会好好学习我的字节码。 - vojta

失去循环肯定会使它更快。你提前知道有16个字节。 :-) - Shuckey

我已经创建了多个实现来相对快速地执行任何类型的旋转在这里。它还能够原地旋转数组（而且不需要临时数组），这是相当棘手的。底部的64位实现可以非常容易地扩展到128位，只需在用于获取byteRot变量的掩码左侧添加一个位集即可。 - Maarten Bodewes

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字节数组！

- David

---

谢谢！不过我认为你使用了太多的强制类型转换...你可以只对最终结果进行转换，并尽可能保持int类型... - vojta

仅供参考：令人惊讶的是，即使涉及低级汇编指令，展开循环通常也不是最快的。 - Anton Samsonov

@AntonSamsonov 这怎么可能？ - vojta

这是因为先进的乱序执行和分支预测，两者都从向后跳转中获益，特别是如果循环入口对齐在缓存行边界上并且主体不是很大，因为CPU不需要再次分析您的代码。这可能会变得更加复杂，如Java和.Net等HLVM，其中一些可识别模式可能会转换为最佳本机指令（SSE等），而手动展开的代码可能会被保留。因此，在确切的目标平台上进行适当的基准测试之前，不应进行任何判断。 - Anton Samsonov

@AntonSamsonov，你期望在Java Card上有多少复杂的乱序执行和分支预测？除非可以证明普通循环比展开循环更快，否则我会完全忽略你的评论。顺便说一句，我并不是说David的实现一定非常快 - 通常情况下，你要避免不必要的数组访问，但这里显然不是这种情况 - 每个字节位置都被访问了两次！！！ - Maarten Bodewes

Answer 2

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

使用EEPROM创建一个掩码表来进行位移。掩码只是从右侧逐渐增加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变量，直接使用对表格的引用。

与位旋转的天真实现相比，使用这种方法证明速度提高了约450％ - 500％。

- MiragePV

Answer 3

当使用相同的密钥（即相同的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);
}

注意，此代码假设源和目标具有相同的偏移量。

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

- vlp