Bitshifts, чтобы получить 128-битный продукт - PullRequest
Новая
       9

Bitshifts, чтобы получить 128-битный продукт

1 голос
/ 23 июня 2019

Во-первых, я знаю, что Python обрабатывает этот штраф без использования побитовых операторов, как должно проясниться в третьей строке кода. В конечном итоге я пытаюсь сделать это в C для назначения - реализовать RSA (следовательно, переменные p, q и n в коде) на архитектуре, которая не поддерживает uint_128t; Я просто лучше с Python, и пытаюсь использовать его, чтобы понять. РЕДАКТИРОВАТЬ: Хранение total0 (128 бит) является собственной проблемой без указанной поддержки, но это доказательство концепции должно позволить мне выяснить остальное.

Я нашел этот архивированный журнал , обсуждающий это с 64-битными продуктами на процессоре Motorola 68000, и попытался реализовать это в Python, но удвоил его. Я правильно понял верхние 32 бита, но остальные 96 неверны (ну, последние 16 тоже правильные, но они вообще не сдвинуты, так что это не удивительно).

На всякий случай, когда у меня возникла математическая ошибка при подсчете битов, я попытался использовать грубую силу для цикла / for / for, чтобы выполнить total1 / total2 / total3 в диапазоне (0,81). Нет совпадений. 

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)]))

Моя мысль о смещении итогового 0 на 80 бит заключается в том, что это 48-битное число, поэтому оно должно иметь 80 нулей, дополняющих его вправо. total1 составляет 47 бит, поэтому сдвиг влево на 33 (80-47). total2 составляет 44 бита, поэтому сдвиг влево на 14 (47-33). Наконец, оставьте total3 как есть, так как это LSDW.

1 Ответ

3 голосов
/ 23 июня 2019

Я думаю, что ваши значения смены отключены при создании значений 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 переменных в конце и добавив их с величинами сдвига, показанными выше.

...