Строка к BigNum и обратно (в Ruby), чтобы разрешить циклический сдвиг

В качестве личной задачи я пытаюсь реализовать блочный шифр SIMON на Ruby. У меня возникают некоторые проблемы с поиском наилучшего способа работы с данными. Полный код, связанный с этим вопросом, находится по адресу: https://github.com/Rami114/Personal/blob/master/Simon/Simon.rb

SIMON требует операций XOR, сдвига и циклического сдвига, последняя из которых вынуждает меня работать с BigNums, чтобы я мог выполнять циклический сдвиг влево с помощью математики, а не более сложный/медленный двойной цикл на байтовых массивах.

Есть ли лучший способ преобразовать строку в BigNum и обратно.

String -> BigNum (где N равно 64, а pt — строка открытого текста)

 pt = pt.chars.each_slice(N/8).map {|x| x.join.unpack('b*')[0].to_i(2)}.to_a

Поэтому я разбиваю строку на отдельные символы, разбиваю на массивы размером N (размер слова в SIMON) и распаковываю каждый набор в BigNum. Кажется, это работает нормально, и я могу преобразовать его обратно.

Теперь мой код SIMON в настоящее время не работает, но я думаю/надеюсь, что это больше математика, а не код. Обратное преобразование (где ct — массив больших чисел, представляющих зашифрованный текст):

ct.map { |x| [x.to_s(2).rjust(128,'0')].pack('b*') }.join

Кажется, мне нужно выровнять строку по правому краю, поскольку большие числа имеют неопределенную ширину, поэтому у меня нет начальных нулей. К сожалению, пакет требует, чтобы определенный with имел разумный вывод.

Является ли это допустимым методом преобразования? Есть ли способ лучше? Я не уверен ни в том, ни в другом, и надеюсь, что кто-то здесь может помочь.

E: Для @torimus реализация кругового сдвига, которую я использую (из ссылки выше)

def self.lcs (bytes, block_size, shift)
  ((bytes << shift) | (bytes >> (block_size - shift))) & ((1<< block_size)-1)
end

ruby cryptography bignum bit-manipulation
person Ben Pottier    schedule 22.07.2013    source источник
comment
Должно ли это быть .rjust(64,'0') во втором списке, или заполнение дополнительными нулями (которое я получаю, запуская строку из 64 символов через обе ваши строки кода) является частью алгоритма шифрования?   -  person Neil Slater    schedule 22.07.2013
comment
Что касается операции ротации битов, может пригодиться следующий SO answer.   -  person Torimus    schedule 22.07.2013
comment
@NeilSlater rjust имеет 128 бит, потому что раунды SIMON работают с двумя словами размером N вместе, чтобы сформировать 128-битный блок.   -  person Ben Pottier    schedule 22.07.2013
comment
@Torimus Добавлен код циклического сдвига, который я использую в исходном вопросе. Он использует тот же механизм, что и в ваших ответах на ссылки (спасибо), но немного более гибко, чтобы учесть различную ширину.   -  person Ben Pottier    schedule 22.07.2013
comment
Это альтернатива вашей первой строке: pt.scan( /.{#{N/8}}/ ).map { |x| x.unpack('b*')[0].to_i(2) }.to_a. Это позволяет избежать создания, а затем присоединения к временному массиву за счет использования простого регулярного выражения - я не думаю, что это большое улучшение (или обязательно улучшение), хотя я ожидаю, что это будет немного быстрее, поэтому, возможно, стоит сравнить   -  person Neil Slater    schedule 22.07.2013
comment
Заметил некоторые проблемы на моем этапе key_expansion. Я собираюсь сделать это медленно и сначала написать на C (что намного проще), а затем убедиться, что каждый компонент работает по очереди.   -  person Ben Pottier    schedule 23.07.2013

Ответы (1)


arrow_upward
0
arrow_downward

Если бы вы были в равной степени довольны unpack('B*') с первыми двоичными числами msb (что вполне могло бы быть, если вся ваша обработка циклическая), то вы также могли бы использовать .unpack('Q>') вместо .unpack('B*')[0].to_i(2) для генерации pt:

pt = "qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM1234567890!@"

# Your version (with 'B' == msb first) for comparison:
pt_nums = pt.chars.each_slice(N/8).map {|x| x.join.unpack('B*')[0].to_i(2)}.to_a
=> [8176115190769218921, 8030025283835160424, 7668342063789995618, 7957105551900562521,
  6145530372635706438, 5136437062280042563, 6215616529169527604, 3834312847369707840]

# unpack to 64-bit unsigned integers directly
pt_nums =  pt.unpack('Q>8')
=> [8176115190769218921, 8030025283835160424, 7668342063789995618, 7957105551900562521, 
  6145530372635706438, 5136437062280042563, 6215616529169527604, 3834312847369707840]

Нет родной 128-битной упаковки/распаковки для возврата в другом направлении, но вы также можете использовать Fixnum для решения этой проблемы:

split128 = 1 << 64
ct = pt # Just to show round-trip
ct.map { |x| [ x / split128, x % split128 ].pack('Q>2') }.join

=> "\x00\x00\x00\x00\x00\x00\x00\x00qwertyui . . . " # truncated

Это позволяет избежать многих временных этапов вашего кода, но за счет использования другого байтового кодирования - я недостаточно знаю SIMON, чтобы комментировать, можно ли это адаптировать к вашим потребностям.

person Neil Slater    schedule 22.07.2013
comment
Обратите внимание, что в первой версии была ошибка, точка разделения 1 << 64, а не 65, как изначально было написано. - person Neil Slater; 22.07.2013