Поля Галуа GF(2^8)

Question

Поля Галуа GF(2^8)

Рейтинг: 2Ответов: 2Опубликовано: 23.09.2014

В чем ошибка при умножении в поле Галуа GF(2^8).
Пример: 57*83=x^7+x^6+1.

57 из HEX в BIN (1010111)  
83 из HEX в BIN (10000011)

Соответственно представим, как:

(1+x+x2+x4+x6)(1+x+x7)

т.к у 57 на позициях x3 и x5 стоят нули, то мы их не записываем, по тому же принципу записали 83.

(x6+x4+x2+x+1)(x7+x+1)=x13+x11+x9+x8+/x7/+/x7/+x5+x3+/x2/+/x/+x6+x4+/x2/+/x/+1 = 
x13+x11+x9+x8+x5+x3+x6+x4+1

(Т.к. в ответе есть одинаковые значения, то мы избавимся от них, помечены /)

Теперь посчитаем:

x13+x11+x9+x8+x6+x5+x4+x3+1 mod (x8+x4+x3+x+1)

где x8+x4+x3+x+1 - это предельное значение в Поле Галуа по 2^8, которое мы не можем превысить.

Запишем все в BIN:

10101101111001 mod (100011011)

То есть

11129 mod 283 = 92

Правильный ответ: x7+x6+1, то есть 11000001 = 193.

У меня получилось 92.

Объясните, в чем моя ошибка, может быть, деление mod происходит совсем иначе?

шифрование полином

Источник: Stack Overflow на русском

Answer 1

▲ 3

Это сообщение первое в выдаче поиска по запросу "Галуа", поэтому добавлю сюда код для умножения в поле Галуа GF(2^8):

def gf_mul(a, b, modulo):
    """
    Умножение двух многочленов в поле GF(2^8).
    
    Многочлены представлены в виде целых чисел,
    где каждый бит соответствует коэффициенту при соответствующей 
    степени x.
    Например, многочлен x^7 + x^5 + 1 будет представлен как 0b10010001 
    или в 0x91.
    """
    result = 0
    for _ in range(8):
        if b == 0:
            break
        if b & 1:
            result ^= a  # Добавляем a к результату
        hi_bit_set = a & 0x80  # Проверяем, есть ли в многочлене a член x^7
        a <<= 1  # Умножаем a на x
        if hi_bit_set: 
            # Если был член x^7, то после умножения на x старший член стал x^8, 
              и многочлен нужно редуцировать
            a ^= modulo # Редуцируем по модулю неприводимого многочлена
        a &= 0xFF  # Отбрасываем старшие биты, которые появились 
                   # в результате редукции
        b >>= 1  # Делим многочлен b на x
    return result

def poly(n: int) -> str:
    """
    Преобразует число в строку многочлена.
    Например, 0b10010001 будет преобразовано в "x^7 + x^5 + 1".
    """
    if n == 0:
        return "0"
    
    terms = []
    for i in reversed(range(n.bit_length())):
        if n & (1 << i):
            if i == 0:
                terms.append("1")
            elif i == 1:
                terms.append("x")
            else:
                terms.append(f"x^{i}")
    return " + ".join(terms)

Вычисление для вопроса ТС

modulo = 0x11B  # Неприводимый многочлен для GF(2^8)
print("неприводимый многочлен:",poly(modulo))

a = 0x57
print("a = ", poly(a))  

b = 0x83
print("b = ", poly(b))

c = gf_mul(a, b, modulo=modulo)
print("a * b = ", poly(c))

print(f"{hex(a)} * {hex(b)} = {hex(c)}")
print(f"{a} * {b} = {c}")

Итого:

неприводимый многочлен: x^8 + x^4 + x^3 + x + 1
a =  x^6 + x^4 + x^2 + x + 1
b =  x^7 + x + 1
a * b =  x^7 + x^6 + 1
0x57 * 0x83 = 0xc1
87 * 131 = 193

Answer 2

▲ 2

Хм, я удивился что за месяц никто не ответил. Да, ты был прав, деление идет в полях Галуа не совсем так как обычное. Если делить так же в столбик, то нужно вместо вычитания каждый раз использовать операцию xor ( если одинаковые то нолик, если разные то единица ). Пример как решить на картинке. И если еще будут вопросы по полям Галуа спрашивай, я их неплохо знаю. пример решения.

Поля Галуа GF(2^8)

Ответы