Министерство транспорта Российской Федерации
Федеральное агентство железнодорожного транспорта
Федеральное государственное бюджетное образовательное учреждение
высшего образования
«Дальневосточный государственный университет путей сообщения»
Кафедра «Вычислительная техника и компьютерная графика»
Криптоанализ потоковых и простейших блочных
шифров
Лабораторная работа
По дисциплине «Защита информации»
ЛР.[Link].03.БО941САП
Студент__________________________________24.12.24______________ Б. В. Рощупкин
Доцент_______________________________________24.12.24__________ Е. В. Данилова
Хабаровск 2024
Цель: ознакомиться, изучить криптоанализ потоковых и простейших блочных
шифров, научиться реализовывать его на языке программирования Python.
Криптоанализ потоковых и простейших блочных шифров
Криптоанализ — это процесс изучения и взлома шифров с целью восстановления
исходного текста без знания ключа. Рассмотрим два простых типа шифров: потоковые
шифры и простейшие блочные шифры, а также методы их криптоанализа.
Потоковые шифры
Потоковые шифры шифруют данные по одному символу или биту за раз, используя
последовательность ключей, которая обычно генерируется псевдослучайным образом.
Основные характеристики:
Гибкость: Подходят для шифрования потоков данных, таких как сетевые передачи.
Скорость: Быстрее блочных шифров при обработке больших объемов данных.
Безопасность: Зависит от качества генератора ключей. При повторении ключевых
последовательностей шифр становится уязвимым.
Пример: XOR-шифр, где каждый символ открытого текста комбинируется с
соответствующим символом ключа с помощью операции XOR.
Криптоанализ:
Атаки с повторяющимся ключом: Если ключ повторяется, можно использовать
частотный анализ для восстановления ключа.
Известный открытый текст: Зная часть исходного текста, можно вычислить часть
или весь ключ.
Простейшие блочные шифры
Блочные шифры работают с фиксированными блоками данных (например, 2 или 4
символа) и используют ключевую матрицу или алгоритм для преобразования каждого
блока. Рассмотрим два примера:
1. Шифр Цезаря
o Описание: Симметричный шифр сдвига, где каждый символ текста сдвигается на
фиксированное количество позиций в алфавите.
o Простота: Очень простой и легко реализуемый.
o Недостатки: Ограниченное количество ключей (размер алфавита), подвержен
частотному анализу.
2. Шифр Хилла
o Описание: Блочный шифр, использующий линейные преобразования через
матрицу ключа. Каждый блок текста представляется как вектор чисел, умножается
на ключевую матрицу и преобразуется обратно в текст.
o Сложность: Более сложный, требует матричных операций и инверсии матрицы по
модулю.
o Безопасность: Сложнее взломать по сравнению с шифром Цезаря, но всё ещё
уязвим при наличии достаточного объёма известного открытого текста.
Криптоанализ:
Шифр Цезаря:
o Брутфорс: Перебор всех возможных сдвигов и проверка полученного текста.
Шифр Хилла:
o Атака с известным открытым текстом: Если известны соответствия между
открытым и зашифрованным текстом, можно составить систему уравнений для
восстановления ключевой матрицы.
o Требования: Необходимо знать достаточное количество пар открытый-
зашифрованный текст, чтобы решить систему уравнений.
o Сложности: Требуется, чтобы матрица открытого текста была обратимой по
модулю размера алфавита. Если матрица необратима, криптоанализ затрудняется.
Шифр Хилла — это блочный шифр, использующий линейные преобразования через
матрицу ключа. Для криптоанализа этого шифра используется атака с известным
открытым текстом (known-plaintext attack), при которой известны пары открытого и
зашифрованного текста.
Как Работает Криптоанализ Хилла:
1. Необходимые Данные:
o Зашифрованный текст: Текст, который был зашифрован с использованием
шифра Хилла.
o Известный открытый текст: Часть или весь текст до шифрования,
соответствующая части зашифрованного текста.
2. Преобразование Текста в Векторы:
o Текст разбивается на блоки фиксированного размера (например, 2 символа
для матрицы 2x2).
o Каждый символ преобразуется в числовое значение на основе позиции в
алфавите.
3. Составление Системы Уравнений:
o Используя пары блоков открытого и зашифрованного текста, формируется
система линейных уравнений, позволяющая вычислить матрицу ключа.
o Для матрицы 2x2 требуется как минимум две пары блоков для составления
полной системы уравнений.
4. Восстановление Ключевой Матрицы:
o Инвертируемость Матрицы: Для успешного восстановления ключа
матрица, сформированная из известных блоков открытого текста, должна
быть обратимой по модулю длины алфавита (32 для русского алфавита без
"Ё").
o Если матрица обратима, вычисляется обратная матрица, и на основе неё
восстанавливается ключевая матрица.
o Проверка Корректности: Полученная ключевая матрица проверяется на
остальных блоках текста для подтверждения её правильности.
5. Обработка Необратимых Матриц:
o В случае, если первая попытка восстановления матрицы PPP из известных
блоков открытого текста оказывается необратимой, программа перебирает
другие возможные пары блоков из известного текста.
o Это увеличивает шансы на успешное восстановление ключа, поскольку не
все пары блоков приводят к необратимой матрице.
6. Вывод Результатов:
o Если ключевая матрица успешно восстановлена, программа выводит её и
расшифровывает весь зашифрованный текст.
o Если восстановление не удалось (например, из-за отсутствия обратимой
матрицы), выводится соответствующее сообщение.
Код для реализации криптоанализа
Листинг 1 – Код реализации криптоанализа Цезаря и Хилла
import numpy as np
# -------------------- Шифр Цезаря --------------------
def caesar_cipher_russian(text, key, decrypt=False):
result = ""
alphabet_lower = 'абвгдежзийклмнопрстуфхцчшщъыьэюя'
alphabet_upper = 'АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ'
len_alphabet = len(alphabet_lower)
# Если текст содержит цифры, выведем сообщение об ошибке
if any([Link]() for char in text):
return 'Ошибка: Текст не должен содержать цифры!'
# Для дешифровки сдвиг должен быть отрицательным
if decrypt:
key = -key
for char in text:
if char in alphabet_lower:
new_index = (alphabet_lower.index(char) + key) % len_alphabet
result += alphabet_lower[new_index]
elif char in alphabet_upper:
new_index = (alphabet_upper.index(char) + key) % len_alphabet
result += alphabet_upper[new_index]
else:
result += char
return result
# Функция для криптоанализа шифра Цезаря
def cryptanalysis_caesar(text):
alphabet = 'абвгдежзийклмнопрстуфхцчшщъыьэюя'
frequency_order = 'оеинат' # Примерный порядок частот русских букв
len_alphabet = len(alphabet)
steps = 0
best_shift = 0
max_matches = -1
for shift in range(len_alphabet):
steps += 1
decrypted = caesar_cipher_russian(text, shift, decrypt=True)
# Простая оценка: сколько самых частотных букв содержится в тексте
matches = sum([Link](char) for char in frequency_order)
if matches > max_matches:
max_matches = matches
best_shift = shift
# Расшифровка с найденным сдвигом
cracked_text = caesar_cipher_russian(text, best_shift, decrypt=True)
return cracked_text, best_shift, steps
# -------------------- Шифр Хилла --------------------
# Определяем русский алфавит (без 'Ё')
alphabet = 'АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ'
alphabet_len = len(alphabet)
# Функция для преобразования текста в числовые векторы
def text_to_vectors(text, block_size=2):
text = [Link]().replace(' ', '')
if len(text) % block_size != 0:
text += 'А' * (block_size - len(text) % block_size)
vectors = [[[Link](text[i]), [Link](text[i + 1])] for i in range(0, len(text),
block_size)]
return vectors
# Функция для преобразования числовых векторов в текст
def vectors_to_text(vectors):
return ''.join(alphabet[num] for vector in vectors for num in vector)
# Функция для нахождения обратной матрицы по модулю (только для 2x2 матриц)
def mod_inv_matrix_2x2(matrix, mod):
a, b = matrix[0]
c, d = matrix[1]
det = (a * d - b * c) % mod
det_inv = mod_inverse(det, mod)
if det_inv is None:
raise ValueError("Обратной матрицы не существует.")
# Инвертируем матрицу вручную
inv_matrix = [
[(d * det_inv) % mod, (-b * det_inv) % mod],
[(-c * det_inv) % mod, (a * det_inv) % mod]
]
return [Link](inv_matrix)
# Функция для нахождения обратного числа по модулю
def mod_inverse(a, m):
a=a%m
for x in range(1, m):
if (a * x) % m == 1:
return x
return None
# Функция шифрования и расшифрования текста шифром Хилла
def hill_cipher(text, key_matrix, mode='шифровать'):
vectors = text_to_vectors(text, block_size=key_matrix.shape[0])
key_matrix = [Link](key_matrix)
result = []
if mode == 'расшифровать':
try:
key_matrix = mod_inv_matrix_2x2(key_matrix, alphabet_len)
except ValueError as e:
raise ValueError(f"Невозможно расшифровать: {e}")
for vector in vectors:
vector = [Link](vector)
new_vector = [Link](key_matrix, vector) % alphabet_len
new_vector = new_vector.astype(int)
[Link](new_vector)
return vectors_to_text(result)
# Функция для ввода ключевой матрицы с клавиатуры
def input_key_matrix():
while True:
try:
n = int(input("Введите размер ключевой матрицы (например, 2 для матрицы 2x2): "))
if n <= 0:
raise ValueError("Размер матрицы должен быть положительным числом.")
if n != 2:
print("На данный момент поддерживается только матрица 2x2.")
continue
break
except ValueError as e:
print(f"Ошибка ввода: {e}. Попробуйте снова.")
key_matrix = []
print(f"Введите элементы ключевой матрицы {n}x{n} (по строкам, элементы разделяйте
пробелами):")
for i in range(n):
while True:
try:
row = list(map(int, input(f"Строка {i + 1}: ").split()))
if len(row) != n:
raise ValueError(f"Ошибка: ожидается {n} элементов в строке.")
key_matrix.append(row)
break
except ValueError as e:
print(f"Ошибка ввода: {e}. Попробуйте снова.")
return [Link](key_matrix)
# Функция для криптоанализа шифра Хилла (для 2x2 матрицы и известного открытого текста)
def cryptanalysis_hill(cipher_text, known_plaintext):
block_size = 2
vectors_cipher = text_to_vectors(cipher_text, block_size)
vectors_plain = text_to_vectors(known_plaintext, block_size)
if len(vectors_cipher) < 2 or len(vectors_plain) < 2:
print("Недостаточно данных для криптоанализа.")
return None, None, 0
# Перебираем все возможные пары двух блоков из известного открытого текста
for i in range(len(vectors_plain) - 1):
for j in range(len(vectors_cipher) - 1):
P = [Link](vectors_plain[i:i + 2]).T # 2x2
C = [Link](vectors_cipher[j:j + 2]).T # 2x2
try:
P_inv = mod_inv_matrix_2x2(P, alphabet_len)
except ValueError:
continue # Переходим к следующей паре
# Ключевая матрица K = C * P_inv mod alphabet_len
K = [Link](C, P_inv) % alphabet_len
K = [Link](int)
# Проверка ключевой матрицы на всех блоках
valid = True
for k in range(len(vectors_plain)):
P_block = [Link](vectors_plain[k]).T
C_block = [Link](vectors_cipher[k]).T
C_computed = [Link](K, P_block) % alphabet_len
C_computed = C_computed.astype(int)
if not np.array_equal(C_computed, C_block):
valid = False
break
if valid:
steps = (i + 1) * (j + 1) + len(vectors_plain)
return K, vectors_cipher, steps
print("Криптоанализ не удался.")
return None, None, 0
# Основная функция
def main():
while True:
# Выбор действия
action = input("Выберите действие: (1) Шифр Цезаря (2) Шифр Хилла (3) Выйти: ").strip()
if action not in ('1', '2', '3'):
print("Неверный выбор. Попробуйте снова.")
continue
if action == '3':
print("Выход из программы.")
break
if action == '1':
# Шифр Цезаря
text = input("Введите текст для шифрования/дешифрования на русском: ")
key = int(input("Введите ключ: "))
mode = input("Вы хотите зашифровать или расшифровать текст?: ").lower()
if mode == 'зашифровать':
encrypted_text = caesar_cipher_russian(text, key)
print("Зашифрованный текст:", encrypted_text)
elif mode == 'расшифровать':
decrypted_text = caesar_cipher_russian(text, key, decrypt=True)
print("Дешифрованный текст:", decrypted_text)
else:
print("Неправильный выбор режима!")
continue
# Криптоанализ
print("\nНачинаем криптоанализ шифра Цезаря...")
# Используем зашифрованный текст для дешифровки
cracked_text, found_shift, steps = cryptanalysis_caesar(encrypted_text if mode ==
'зашифровать' else text)
print(f"Криптоанализ завершен за {steps} шагов.")
# print(f"Найденный сдвиг: {found_shift}")
print(f"Расшифрованный текст: {cracked_text}\n")
elif action == '2':
# Шифр Хилла
sub_action = input("Выберите действие: (1) Шифровать (2) Расшифровать (3)
Криптоанализ: ").strip()
if sub_action not in ('1', '2', '3'):
print("Неверный выбор. Попробуйте снова.")
continue
if sub_action in ('1', '2'):
# Ввод ключевой матрицы
key_matrix = input_key_matrix()
# Ввод текста
text = input("Введите текст (используйте только буквы русского алфавита): ").upper()
# Проверка размера матрицы
block_size = key_matrix.shape[0]
if block_size > len(text):
print("Ошибка: размер ключевой матрицы больше длины текста.")
continue
if sub_action == '1':
# Шифрование
encrypted_text = hill_cipher(text, key_matrix, mode='шифровать')
print('Зашифрованный текст:', encrypted_text)
elif sub_action == '2':
# Расшифрование
try:
decrypted_text = hill_cipher(text, key_matrix, mode='расшифровать')
print('Расшифрованный текст:', decrypted_text)
except ValueError as e:
print(f"Ошибка: {e}")
elif sub_action == '3':
# Криптоанализ шифра Хилла
cipher_text = input("Введите зашифрованный текст для криптоанализа: ").upper()
known_plaintext = input("Введите известный открытый текст (должен быть не менее 2
блоков): ").upper()
if len(known_plaintext) < 4:
print(
"Ошибка: известный открытый текст должен содержать как минимум 4 символа
(2 блока по 2 символа).")
continue
print("\nНачинаем криптоанализ шифра Хилла...")
key_matrix, vectors_cipher, steps = cryptanalysis_hill(cipher_text, known_plaintext)
if key_matrix is not None:
print(f"Криптоанализ завершен за {steps} шагов.")
print("Найденная ключевая матрица:")
print(key_matrix)
# Дополнительно можно попытаться расшифровать весь текст
try:
decrypted_text = hill_cipher(cipher_text, key_matrix, mode='расшифровать')
print('Расшифрованный текст:', decrypted_text)
except ValueError as e:
print(f"Ошибка при расшифровке: {e}")
else:
print("Криптоанализ не удался.\n")
if __name__ == "__main__":
main()
Результаты работы программы
Листинг 2 – Результат работы криптоанализа
/usr/local/bin/python3.12 /Users/bogdanroshchupkin/Downloads/kirill_caps/[Link]
Выберите действие: (1) Шифр Цезаря (2) Шифр Хилла (3) Выйти: 1
Введите текст для шифрования/дешифрования на русском: рощупкин
Введите ключ: 3
Вы хотите зашифровать или расшифровать текст?: зашифровать
Зашифрованный текст: усьцтнлр
Начинаем криптоанализ шифра Цезаря...
Криптоанализ завершен за 32 шагов.
Расшифрованный текст: рощупкин
Выберите действие: (1) Шифр Цезаря (2) Шифр Хилла (3) Выйти: 2
Выберите действие: (1) Шифровать (2) Расшифровать (3) Криптоанализ: 1
Введите размер ключевой матрицы (например, 2 для матрицы 2x2): 2
Введите элементы ключевой матрицы 2x2 (по строкам, элементы разделяйте пробелами):
Строка 1: 3 6
Строка 2: 4 11
Введите текст (используйте только буквы русского алфавита): богдан
Зашифрованный текст: ЧЮБШОП
Выберите действие: (1) Шифр Цезаря (2) Шифр Хилла (3) Выйти: 2
Выберите действие: (1) Шифровать (2) Расшифровать (3) Криптоанализ: 2
Введите размер ключевой матрицы (например, 2 для матрицы 2x2): 2
Введите элементы ключевой матрицы 2x2 (по строкам, элементы разделяйте пробелами):
Строка 1: 3 6
Строка 2: 4 11
Введите текст (используйте только буквы русского алфавита): ЧЮБШОП
Расшифрованный текст: БОГДАН
Выберите действие: (1) Шифр Цезаря (2) Шифр Хилла (3) Выйти: 2
Выберите действие: (1) Шифровать (2) Расшифровать (3) Криптоанализ: 3
Введите зашифрованный текст для криптоанализа: ЧЮБШОП
Введите известный открытый текст (должен быть не менее 2 блоков): богдан
Начинаем криптоанализ шифра Хилла...
Криптоанализ завершен за 7 шагов.
Найденная ключевая матрица:
[[ 3 6]
[ 4 11]]
Расшифрованный текст: БОГДАН
Выберите действие: (1) Шифр Цезаря (2) Шифр Хилла (3) Выйти: 3
Выход из программы.
Process finished with exit code 0
Вывод: в ходе лабораторной работы было изучено и реализован
криптоанализ потоковых и простейших блочных шифров.