Python-сообщество

tmvpsingle · Дек. 11, 2014 17:10:50

Доброго времени суток всем.
У меня возникла проблема, надеюсь кто-нибудь поможет её решить.

В академических целях (самообучение) я решил реализовать алгоритм шифрования RC5. Не могу реализовать операции “>>> <<<” циклического побитового сдвига. Эта операция выполняется во время перемешивания словарных ключей и во время собственно шифрования/дешифрования.
Перед тем как спросить тут я пытался найти реализацию этого алгоритма на чистом Питоне, а также реализацию циклических сдвигов в других языках. Натыкался на информацию, что реализация циклического побитового сдвига на Питоне будет отличаться от других реализаций из-за отсутствия целочисленного переполнения. В подтверждении этому я переписал несколько примеров с С и С++, но все они либо работали с ошибками, либо вообще не работали. Например:
Си.

unsigned long __cdecl _lrotl (
    unsigned long val,
    int shift
    )
{
    shift &= 0x1f;
    val = (val>>(0x20 - shift)) | (val << shift);
    return val;
}

Джава.

int a;
a = 0x12345678;
int shift = 8; // сдвиг в битах
a = (a>>(32 - shift)) | a << 8;// цикло сдвиг влево на 8 бит
System.out.println(Integer.toHexString(a));
a = 0x12345678;
a = a>>(shift) | (a << (32 - shift));// цикло сдвиг вправо на 8 бит
System.out.println(Integer.toHexString(a));

Си.

int rol(int a, int n)

{
int t1, t2;
n = n % (sizeof(a)*8); // нормализуем n
t1 = a << n; // двигаем а вправо на n бит, теряя старшие биты
t2 = a >> (sizeof(a)*8 - n); // перегоняем старшие биты в младшие
return t1 | t2; // объединяем старшие и младшие биты
}
int ror(int a, int n)
{
int t1, t2;
n = n % (sizeof(a)*8); // нормализуем n
t1 = a >> n; // двигаем а влево на n бит, теряя младшие биты
t2 = a << (sizeof(a)*8 - n); // перегоняем младшие биты в старшие
return t1 | t2; // объединяем старшие и младшие биты
}

Последний пример вообще не понятен мне. Зачем тут используется встроенная функция определения размера объекта, который он занимает в памяти? Обычно для целого числа это 4 байта. И зачем эти байты умножать на 8? Это же не биты. Вообще, какая разница сколько объект занимает места в памяти, главное какова его битовая разрядность (разве нет?). Ведь циклический сдвиг это математическая операция.

Также где-то находил библиотеку на Питоне для подобных целей, но размер этой библиотеки такой, что лишает смысла в её: импорте и использовании, вычленения реализации.

Может кто-нибудь показать мне реализацию подобных функций? Желательно универсальную (т.е. можно использовать для 16, 32, 64 бит и т.д.).

P.S. В качестве тестового примера взял следующие переменные для RC5. Количество раундов - 12, размер блока - 32. Ключ “Пробный ключ 484847129425” (в кодировке utf-8).

Байтовый ключ [208, 159, 209, 128, 208, 190, 208, 177, 208, 189, 209, 139, 208, 185, 32, 208, 186, 208, 187, 209, 142, 209, 135, 32, 52, 56, 52, 56, 52, 55, 49, 50, 57, 52, 50, 53, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Массив слов [3500134784, 3502166193, 3502100875, 3501793488, 3134241745, 2396096288, 876098616, 876032306, 959722037, 0, 0, 0]
Таблица расширенных ключей [2654435769, 5308871538, 7963307307, 10617743076, 13272178845, 15926614614, 18581050383, 21235486152, 23889921921, 26544357690, 29198793459, 31853229228, 34507664997, 37162100766, 39816536535, 42470972304, 45125408073, 47779843842, 50434279611, 53088715380, 55743151149, 58397586918, 61052022687, 63706458456, 66360894225, 69015329994]

py.user.next · Дек. 12, 2014 01:17:51

tmvpsingle
Последний пример вообще не понятен мне. Зачем тут используется встроенная функция определения размера объекта, который он занимает в памяти? Обычно для целого числа это 4 байта.

Я встречал и 64-битный int. А по стандарту он не ограничен, главное, чтобы он не был короче short int и не был длиннее long int.

Неправильно в том примере только то (в плане языка), что он работает со знаковыми целыми. При сдвиге вправо знак числа остаётся неопределённым (по стандарту). Поэтому, имея изначально отрицательное число, при сдвиге вправо он может получить либо отрицательное, либо положительное (зависит от реализации). Чтобы этого не было делают unsigned, как в самом первом примере.

А в первом примере __cdecl надо убрать, так как это часть не от языка, а от компилятора. И размер у него зафиксирован, тогда как размер может быть произвольным.

tmvpsingle
Не могу реализовать операции “>>> <<<” циклического побитового сдвига.

Сначала запиши вызов функции, которой у тебя ещё нет.

x = rotate_right(12345, 5)

Когда запишешь, поймёшь, как её нужно сделать.

Начинай с прототипа
один

def rotate_left(num, n)

второй

def rotate_right(num, n)

Нужно понять, что он принимает на вход и выдаёт на выход.

Дальше пишешь тело функции, не отступая от полученного объявления.

В питоне для представления целых чисел используется длинная арифметика, поэтому правая граница известна, а левая - нет.

Но есть метод:

>>> (-12345).bit_length()
14
>>> (12345).bit_length()
14
>>> (-1234512345123451234512345).bit_length()
81
>>> (1234512345123451234512345).bit_length()
81
>>>

Вот на нём можешь основать перемещение.

Отредактировано py.user.next (Дек. 12, 2014 01:38:52)

saw_tooth · Дек. 12, 2014 13:06:48

не знаю видел ли, но сброшу

http://www.cyberforum.ru/python/thread693325.html

Вообще, куда быстрее найти реализацию на С и прямо просто переписать на Питоне, с использованием простых строенных функций типа len() и << >>.

Я когда делал протокол обмена данными, именно по такому способу делал реализацию CRC16 суммы с 0x8005 полиномом.

Python-сообщество

Уведомления

#1 Дек. 11, 2014 17:10:50

Циклический побитовый сдвиг. Алгоритм RC5.

#2 Дек. 12, 2014 01:17:51

Циклический побитовый сдвиг. Алгоритм RC5.

#3 Дек. 12, 2014 13:06:48

Циклический побитовый сдвиг. Алгоритм RC5.

Board footer