Как вычислить модульную мультипликативную инверсию для аффинного шифра

Это невозможно (в общем случае для аффинного шифра см. обновление ниже). Именно поэтому модульная работа так часто используется в алгоритмах безопасности - она ​​необратима. Но почему бы нам не попробовать?

result = (k1 * input + k2) % 27 (*1)

Возьмем первую букву:

result = (7 * 8 + 5) % 27 = 7

Это классно. Теперь, потому что мы сказали, что:

result = (k1 * input + k2) % 27

также верно следующее:

k1 * input + k2 = 27 * div + result (*2)

где

div = (k1 * input + k2) / 27 (integral division)

Это вполне очевидно (если a % b = c, то a = b*n + c, где n — результат целочисленного деления a/b).

Вы знаете значения k1 (что равно 7), k2 (5) и результат (7). Итак, когда мы помещаем эти значения в (*2), мы получаем следующее:

7 * input + 5 = 27 * div + 7 //You need to solve this

Как вы можете видеть, это невозможно решить, потому что вам нужно знать также результат целочисленного деления - переводя это на язык вашей функции, вам нужно значение

numberback / 27

что неизвестно. Итак, ответ таков: вы не можете отменить результаты своей функции, используя только вывод, который она возвращает.

** ОБНОВИТЬ **

Я слишком сосредоточился на заголовке вопроса, поэтому ответ выше не совсем правильный. Решил не удалять, однако, а написать обновление.

Таким образом, ответ для вашего конкретного случая (аффинный шифр): ДА, вы можете обратить его вспять.

Как вы можете видеть в вики, функция дешифрования для аффинного шифра для следующей функции шифрования:

E(input) = a*input + b mod m

определяется как:

D(enc) = a^-1 * (enc - b) mod m

Единственной возможной проблемой здесь может быть вычисление a^-1, которое является модульно-мультипликативным обратным.

Прочитайте об этом на wiki, я приведу только пример.

В вашем случае a = k1 = 7 и m = 27. Итак:

7^-1 = p mod 27
7p = 1 mod 27

Другими словами, вам нужно найти p, который удовлетворяет следующему: 7p % 27 = 1. p можно вычислить с помощью расширенного алгоритма Евклида, и я вычислил его равным 4 (4 * 7 = 28, 28 % 27 = 1).

Проверьте, можете ли вы сейчас расшифровать ваш вывод:

E(8) = 7*8 + 5 mod 27 = 7

D(7) = 4 * (7 - 5) mod 27 = 8

Надеюсь, это поможет :)

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

В вашем случае это будет:

m = 27; // letters in your alphabet
k1 = 7; // coprime with m
k2 = 5; // no reqs here, just that a value above 27 is the same as mod 27 of that value

int Encrypt(int letter) {
  return ((letter * k1) + k2) % m;
}

int Decrypt(int letter) {
  return ((letter - k2) * modInverse(k1, m)) % m;
}

Tuple<int, Tuple<int, int>> extendedEuclid(int a, int b)
{
  int x = 1, y = 0;
  int xLast = 0, yLast = 1;
  int q, r, m, n;
  while (a != 0)
  {
    q = b / a;
    r = b % a;
    m = xLast - q * x;
    n = yLast - q * y;
    xLast = x; yLast = y;
    x = m; y = n;
    b = a; a = r;
  }
  return new Tuple<int, Tuple<int, int>>(b, new Tuple<int, int>(xLast, yLast));
}

int modInverse(int a, int m)
{
  return (extendedEuclid(a, m).Item2.Item1 + m) % m;
}

Реализация ModInverse взята с http://comeoncodeon.wordpress.com/2011/10/09/modular-multiplicative-inverse/.

Я создал программу, которая расскажет модульную инверсию чего-то. Я позволю тебе использовать его. Он размещен ниже.

# Cryptomath Module


def gcf(a, b):
    # Return the GCD of a & b using Euclid's Algorithm
    while a != 0:
        a, b = b % a, a
    return b


def findModInverse(a, m):
    # Return the modular inverse of a % m, which is
    # the number x such that a*x % m = 1

    if gcf(a, m) != 1:
        return None # No mode inverese if a & m aren't relatively prime

    # Calculate using the Extended Euclidean Algorithm:
    u1, u2, u3 = 1, 0, a
    v1, v2, v3 = 0, 1, m
    while v3 != 0:
        q = u3 // v3 # // is the integer division operator
        v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q *
v3), v1, v2, v3
    return u1 % m

Примечание. Модульная инверсия находится с использованием расширенного алгоритма Евклида. Вот запись об этом в Википедии: http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm .

Примечание. Это необходимо импортировать как модуль для использования. Надеюсь, поможет.