Криптоалгоритм без передачи ключа. Как найти вторые ключи α и β?

Question

Есть задача - Пусть абоненты А и В выбрали простое число р=23 и каждый их них независимо от другого выбрал числа a=5 и b=7 соответственно. Пусть абонент А отправляет сообщение m=17 абоненту В.

Найти вторые ключи α и β.
Вычислить значения m1, m2, m3, m4.

Со вторым пунктом разобрался, не понял как именно найти вторые ключи. Ползал по интернету и нашёл, что ответом являются числа 9 и 19 для α и β соответственно. Есть формулы для их нахождения -

а∙α ≡ 1(mod φ(р)), 0 < α < p-1

b∙β ≡ 1(mod φ(р)), 0 < β < p-1

Так же есть формулы для значений m1, m2, m3, m4 -

m1 ≡ m^a (mod p), 0 < m1 < p

m2 ≡ m1^b (mod p), 0 < m2 < p

m3 ≡ m2^α (mod p), 0 < m3 < p

m4 ≡ m3^β (mod p), 0 < m4 < p

Как можно реализовать нахождение ключей α и β на Python?

Ниже представлен код, который у меня получился на Python для второго пункта.

def find_enc_message(m, a, b, alpha, beta, p):
    m1 = pow(m, a, p)
    m2 = pow(m1, b, p)
    m3 = pow(m2, alpha, p)
    m4 = pow(m3, beta, p)
    return m4


print(find_enc_message(17, 5, 7, 9, 19, 23))

Answer 1

У Вас α и β - это обратные по модулю числа (вики).

Для нахождения их в python есть два способа:

Для Python 3.8+

y = pow(x, -1, p) # x*y = 1 (mod p)

Для Python 3.7 и более ранние версии

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

Источник

БЛОГ НА HUSL

Криптоалгоритм без передачи ключа. Как найти вторые ключи α и β?

Ответы (1 шт):