Множества ключей шифрования и расшифрования совпадают.

Для начала необходимо определиться, какие ключи могут быть использованы для шифрования сообщения. Для этого необходимо найти все числа a, которые будут взаимно простыми с m=30, то есть НОД(a, 30) = 1, a < 30. Напишем функцию, которая возвращает все подходящие числа (листинг 3.1-1). Воспользуемся алгоритмом Евклида по вычислению НОД.

 

Листинг 3.2-1 – Функция получения массива чисел, взаимнопростых с m, на языке программирования Python

##

# поиск НОД для 2-х чисел

#   a - первое число

#   b - второе число

# RETURN

#   вычисленный НОД

##

def NOD(a: int, b: int):

  while a != 0 and b != 0:

    if a > b:

      a = a % b

    else:

      b = b % a

  return a + b

 

Для получения массива ключей при m = 30 необходимо воспользоваться функцией getKeys() (листинг 3.2-2).

 

Листинг 3.2-2 – Получение массива ключей для m = 30 на языке программирования Python.

## Получение массива ключей

# PARAMS

#         число m (int)

#         ключи должны быть взаимно простым с ним

# RETURN

#         массив ключей (vector)

##

def getKeys(m: int):

  keys = []

  # цикл от 1 до m

  for i in range(1,m):

    # если НОД(очередное число, m) == 1,

    # то добавляем очередное число в массив ключей

    if NOD(i, m) == 1:

      keys.append(i)

  # возвращаем результат

  return keys;

 

 

m = 30

keys = getKeys(m)

print(keys)

 

Результат выполнения программы:

[1, 7, 11, 13, 17, 19, 23, 29]

Всего таких ключей – 8.

 

Дальше возможно 2 варианта:

1) Перебирать комбинации из 3-х ключей на примере шифрования символа точки ‘.’

2) Перебирать комбинации из 3-х обратных ключей (a^-1), которые будут из этого же множества ключей (листинг 3.1-2) и перебирать их комбинации для расшифрования последнего символа сообщения, пока не получим символ точки ‘.’. После этого искать (подбирать или вычислить) используемые ключи шифрования.

 

Воспользуемся вторым вариантом, поскольку для расшифрования используются ключи из того же множества, что и ключи шифрования. В программе необходимо перебрать все возможные тройки ключей, использование которых при расшифровании перехваченного сообщения дает текст, заканчивающийся на символ точки “.”. Всего возможно 8*8*8 = 512 таких комбинаций, перебор которых выполнится достаточно быстро. Пример реализации такой программы на языке программирования Python приведен в листинге 3.2-3.

 

Листинг 3.2-3 – Пример реализации программы перебора ключей для расшифрования сообщения до получения символа точки ‘.’ в конце на языке программирования Python

# размер алфавита

m = 30

# АЛФАВИТ

ALPHA = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J',

         'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',

         'U', 'V', 'W', 'X', 'Y', 'Z', '.', ',', ' ', '-']

 

## Получение индекса символа алфавита ALPHA

# PARAMS

#   c - символ (char)

# RETURN

#   индекс символа (int)

#   ИЛИ

#   -1 - если символ не найден

##

def getIndex(c: str):

  for i in range(len(ALPHA)):

    if ALPHA[i] == c[0] :

      return i

  # если ошибка

  return -1

 

## Расшифрование символа с использованием ключей a,b,m

# PARAMS

#   index - индекс зашифрованного символа (int)

#   a - ключ расшифрования 1-я часть (int)

#   b - ключ расшифрования 2-я часть (int)

#   m - модуль для расшифрования (int)

# RETURN

#   индекс расшифрованного символа (int)

##

def decipher(index: int, a: int, b: int, m: int):

  res = (a * (index - b)) % m

  return res

 

## Расшифрование сообщения (string) с использованием ключей a,b,m

# PARAMS

#   msg - зашифрованное сообщение (string)

#   a - ключ расшифрования 1-я часть (int)

#   b - ключ расшифрования 2-я часть (int)

#   m - модуль для шифрования (int)

# RETURN

#   зашифрованное сообщение (string)

##

def decipherText(msg: str, a: int, b: int, m: int):

  res = ""

  cindex = 0

  index = 0

  # цикл по каждому символу зашифрованной строки

  for i in range(len(msg)):

    # получение индекса очередного символа

    cindex = getIndex(msg[i])

    # если индекс символа найден - расшифровываем его

    if cindex != -1:

      # расшифрование символа

      index = decipher(cindex, a, b, m)

      # добавление расшифрованного символа к строке результата

      res = res + ALPHA[index]

  return res

 

## main()

b = 5 # ключ 2-я часть

# получение массива ключей для m = 30

keys = getKeys(m)

print(keys)

 

ctext = 'ZSS-V,BR-C,-ROED' # зашифрованное сообщение

symbol = '.'       # искомый символ после расшифрования ('.')

symbolIndex = getIndex(symbol)  # индекс исходного символа (26)

ctext1 = ''

ctext2 = ''

 

# перебор 1-го ключа

for key1 in keys:

  # перебор 2-го ключа

  for key2 in keys:

    # перебор 3-го ключа

    for key3 in keys:

      # расшифрование на 3-м ключе (key3)

      ctext2 = decipherText(ctext, key3, b, m)

      # расшифрование на 2-м ключе (key2)

      ctext1 = decipherText(ctext2, key2, b, m)

      # расшифрование на 1-м ключе (key1)

      text = decipherText(ctext1, key1, b, m)

      # проверка последнего символа

      if text[-1] == symbol:

        # вывод на экран ключей и результат расшифрования

        print("keys: (" + str(key1) + "," + str(key2) + "," + str(key3) +

               "): " + text)

 

Результатом выполнения данной программы будет следующее:

keys: (11,1,7): KLLSCOWYSJOSYDN.

keys: (11,1,17): ALL COME TO END.

keys: (11,7,1): KLLSCOWYSJOSYDN.

keys: (11,7,11): ALL COME TO END.

...

 

В результате получается 32 комбинации, из которых 16 дает фразу «ALL COME TO END.». Эта фраза и есть исходное сообщение. Осталось подобрать исходные ключи, которые использовались для шифрования с учетом правила их выбора. Это возможно решить двумя способами:

1) Подбирать ключи шифрования для фразы «ALL COME TO END.».

2) Вычислить ключи шифрования, зная ключи расшифрования.

 

Воспользуемся вторым способом. Для вычисления ключа шифрования (a) из ключа расшифрования (a^-1) необходимо найти число a, что

a * a^-1 = 1 mod m, НОД(a, m) = 1.

Очевидно, что множество ключей шифрования и расшифрования совпадает. Найти ключи шифрования, зная ключи расшифрования можно с использованием программы. Пример программы поиска обратных чисел приведен в листинге 3.2-4.

 

Листинг 3.2-4 – Пример реализации программы поиска обратных ключей на языке программирования Python.

## Получение обратных ключей

# PARAMS

#   key - ключ, для которого ищется обратный (int)

#   keys - массив ключей ([])

#   m - модуль для шифрования (int)

# RETURN

#   массив обратных ключей (того же размера, что и keys)

##

def getBackKey(key: int, keys: [], m: int):

  # для ключа key перебор ключей (i) и проверка на обратность

  for i in keys:

      if (key * i) % m == 1:

        return i

 

## main()

b = 5 # ключ 2-я часть

# получение массива ключей для m = 30

keys = getKeys(m)

# вывод на экран ключей

for i in keys:

  print(str(i) + " - " + str(getBackKey(i,keys,m)))

 

В результате работы программа выдает следующее:

1 - 1

7 - 13

11 - 11

13 - 7

17 - 23

19 - 19

23 - 17

29 - 29

В первом столбце содержатся ключи шифрования/расшифрования, во втором – ключи расшифрования/шифрования.

Осталось выполнить следующее:

1) Для каждой комбинации ключей расшифрования, дающих фразу «ALL COME TO END.», найти ключи шифрования.

2) Для найденных ключей шифрования проверить условие:

«ключ a равен номеру первого зашифрованного символа сообщения, полученного после применения шифрования. Если номер первого зашифрованного символа не является взаимно простым к m, то в качестве ключа a берется ближайшее большее число, удовлетворяющее правилу. Если такого числа нет (например, номер символа равен 30), то в качестве ключа используется значение 1».

 

Для этого можно усовершенствовать программу из листинга 3.2-3, добавив необходимый код в цикл поиска ключей расшифрования. Пример модифицированного цикла представлен в листинге 3.2-5.

 

Листинг 3.2-5 – Пример реализации программы перебора ключей для расшифрования с проверкой условия на обратные ключи шифрования на языке программирования Python

# перебор 1-го ключа

for key1 in keys:

  # перебор 2-го ключа

  for key2 in keys:

    # перебор 3-го ключа

    for key3 in keys:

      # расшифрование на 3-м ключе (key3)

      ctext2 = decipherText(ctext, key3, b, m)

      # расшифрование на 2-м ключе (key2)

      ctext1 = decipherText(ctext2, key2, b, m)

      # расшифрование на 1-м ключе (key1)

      text = decipherText(ctext1, key1, b, m)

      # проверка последнего символа

      if text[-1] == symbol:

        #получение обратного ключа

        bkey3 = getBackKey(key3,keys,m)

        bkey2 = getBackKey(key2,keys,m)

        bkey1 = getBackKey(key1,keys,m)

        # проверка условия на ключи

        if bkey2 >= getIndex(ctext1[0]) \ # 2-й ключ больше зашифрованного

                                          # первым ключом 1-го символа

        and bkey3 >= getIndex(ctext2[0]): # 3-й ключ больше зашифрованного

                                          # вторым ключом 1-го символа

           # вывод на экран ключей и результат расшифрования

           print("CipherKey1: " + str(bkey1) + ", ctext1[0]: " + str(getIndex(ctext1[0])))

           print("CipherKey2: " + str(bkey2) + ", ctext2[0]: " + str(getIndex(ctext2[0])))

           print("CipherKey3: " + str(bkey3) + ", ctext3[0]: " + str(getIndex(ctext[0])))

           print("--------")

 

Результат выполнения программы:

ALL COME TO END.

CipherKey1: 11, ctext1[0]: 5

CipherKey2: 7, ctext2[0]: 10

CipherKey3: 29, ctext3[0]: 25

--------

…

ALL COME TO END.

CipherKey1: 23, ctext1[0]: 5

CipherKey2: 7, ctext2[0]: 10

CipherKey3: 23, ctext3[0]: 25

--------

…

ALL COME TO END.

CipherKey1: 29, ctext1[0]: 5

CipherKey2: 7, ctext2[0]: 10

CipherKey3: 11, ctext3[0]: 25

--------

ALL COME TO END.

CipherKey1: 29, ctext1[0]: 5

CipherKey2: 19, ctext2[0]: 10

CipherKey3: 23, ctext3[0]: 25

--------

 

Из полученных вариантов подходит только (29,7,1), поскольку второй ключ 7 – первое простое число после 5 (первый зашифрованный символ), а 11 – первое простое число после 10. Остальные варианты не подходят: в тройке (11,7,29): 29 – не первое простое число после 10. аналогично в тройке (29,19,23): 19 – не первое простое число после 5.

ALL COME TO END. Ключи: a1 = 29, a2 = 7, a3 = 11.