python - 移位以获得 128 位产品

Question

首先，我知道 Python 可以在不使用按位运算符的情况下很好地处理这个问题，因为第三行代码应该清楚。我最终试图在 C 中执行此操作以进行分配——在不支持 uint_128t 的体系结构上实现 RSA(因此代码中的 p、q 和 n 变量)；我只是更擅长使用 Python，并尝试使用它来理解。编辑:存储 total0(128 位)是它自己的问题，没有上述支持，但这个概念验证应该让我弄清楚其余部分。

我找到了 this archived magazine讨论在摩托罗拉 68000 CPU 上使用 64 位产品执行此操作，并尝试在 Python 中实现它，但加倍了。我的高 32 位正确，但其余 96 位不正确(好吧，最后 16 位也正确，但它们根本没有移位，所以这不足为奇)。

以防万一我在计算位时出现数学错误，我尝试了 for/for/for 循环的蛮力在范围 (0,81) 内运行 total1/total2/total3。不匹配。

p = 10259632476918722477
q = 17757547285565901767
n = p*q

big_mask =    0xffffffff
small_mask =      0xffff

p_lo = p & big_mask
p_hi = p >> 32
q_lo = q & big_mask
q_hi = q >> 32

p_lo_q_lo = p_lo * q_lo
p_lo_q_hi = p_lo * q_hi
p_hi_q_lo = p_hi * q_lo
p_hi_q_hi = p_hi * q_hi

p_lo_q_lo_UPPER = p_lo_q_lo >> 16
p_lo_q_lo_LOWER = p_lo_q_lo & small_mask
p_lo_q_hi_UPPER = p_lo_q_hi >> 16
p_lo_q_hi_LOWER = p_lo_q_hi & small_mask
p_hi_q_lo_UPPER = p_hi_q_lo >> 16
p_hi_q_lo_LOWER = p_hi_q_lo & small_mask
p_hi_q_hi_UPPER = p_hi_q_hi >> 16
p_hi_q_hi_LOWER = p_hi_q_hi & small_mask

# Original, incorrect implementation
#total0 = p_hi_q_hi_UPPER
#total1 = (p_lo_q_hi_UPPER + p_hi_q_lo_UPPER + p_hi_q_hi_LOWER)
#total2 = (p_lo_q_lo_UPPER + p_lo_q_hi_LOWER + p_hi_q_lo_LOWER)
#total3 = p_lo_q_lo_LOWER
#total = total0 << 80 | total1 << 33 | total2 << 14 | total3 << 0

# Corrected implementation
total0 = p_hi_q_hi_UPPER << 80
total1 = p_hi_q_hi_LOWER << 64
total2 = (p_lo_q_hi_UPPER + p_hi_q_lo_UPPER) << 48
total3 = (p_lo_q_hi_LOWER + p_hi_q_lo_LOWER) << 32
total4 = p_lo_q_lo_UPPER << 16
total5 = p_lo_q_lo_LOWER

total = total0 + total1 + total2 + total3 + total4 + total5

print("\n")
if (n==total):
  print("Match!")
else:
  print("No match.")
print("\n")
print("Actual:   " + str(n))
print("Computed: " + str(total))

print("\n")
# Strip '0b' off of the binary string so the list groupings display logically
hex_n = hex(n)[2:]
hex_total = hex(total)[2:]
print("Actual:   ", end="")
print("\t" + str([hex_n[i:i+4] for i in range(0, len(hex_n), 4)]))
print("Computed: ", end="")
print("\t" + str([hex_total[i:i+4] for i in range(0, len(hex_total), 4)]))

我认为将 total0 移动 80 位是因为它是一个 48 位数字，所以它应该有 80 个 0 向右填充。 total1 是 47 位，所以左移 33 (80-47)。 total2 是 44 位，所以左移 14 (47-33)。最后，保持 total3 不变，因为它是 LSDW。

Answer 1

我认为在最后创建 total 值时，您的类次金额不对。以下是我为各种中间值获得的偏移量:

p_lo         0
p_hi        32
q_lo         0
q_hi        32

p_lo_q_lo    0
p_lo_q_hi   32
p_hi_q_lo   32
p_hi_q_hi   64

p_lo_q_lo_UPPER    16
p_lo_q_lo_LOWER     0
p_lo_q_hi_UPPER    48
p_lo_q_hi_LOWER    32
p_hi_q_lo_UPPER    48
p_hi_q_lo_LOWER    32
p_hi_q_hi_UPPER    80
p_hi_q_hi_LOWER    64

对最终集合进行排序:

p_hi_q_hi_UPPER    80
p_hi_q_hi_LOWER    64
p_lo_q_hi_UPPER    48
p_hi_q_lo_UPPER    48
p_lo_q_hi_LOWER    32
p_hi_q_lo_LOWER    32
p_lo_q_lo_UPPER    16
p_lo_q_lo_LOWER     0

所以最终有 6 个不同的移位量，而不是 4 个。通过在末尾创建 6 个 total 变量，然后将它们与上面显示的移位量相加，应该很容易修复。