task3.py - master - ku11ch/Lab_5

task3.py
295 строк14 KB
ku11ch
upload files
25 ноя 2025, 17:07
25 ноя 2025, 17:07fe7c66c
from math import ceil


def columnar_order_from_key(key: str):
    """
    Возвращает порядок столбцов (список индексов) для столбцовой перестановки.
    При одинаковых буквах ключа сохраняется порядок их появления (stable).
    Пример: key="SECRET" -> порядок [4,1,5,2,0,3] (примерный)
    """
    # Создаем список пар (char, original_index)
    pairs = [(ch, i) for i, ch in enumerate(key)]
    # Сортируем по букве, при равенстве — по исходному индексу (stable)
    sorted_pairs = sorted(pairs, key=lambda x: (x[0], x[1]))
    # Возвращаем для каждой позиции исходного индекса его ранк в отсортированном ключе
    order = [None] * len(key)
    for rank, (ch, orig_idx) in enumerate(sorted_pairs):
        order[orig_idx] = rank
    return order  # length == len(key)


def columnar_encrypt(plaintext: str, key: str):
    """
    Шифрование столбцовой перестановкой.
    Заполняем матрицу построчно, читаем столбцы по возрастанию рангов key.
    Неалфавитные символы сохраняются (в данном варианте мы удалим их только пробелы по примеру).
    """
    # Очистка: можно сохранить пробелы/знаки - но обычно их убирают. Тут убираем только пробелы.
    text = plaintext.replace(" ", "")
    n_cols = len(key)
    n_rows = ceil(len(text) / n_cols)
    # pad with 'X' (можно выбрать любой символ)
    pad_len = n_rows * n_cols - len(text)
    text_padded = text + ("X" * pad_len)

    # Заполним матрицу построчно
    matrix = []
    idx = 0
    for r in range(n_rows):
        row = []
        for c in range(n_cols):
            row.append(text_padded[idx])
            idx += 1
        matrix.append(row)

    order = columnar_order_from_key(key)
    # Сортируем индексы столбцов по рангу: для чтения в порядке 0..n_cols-1 находим столбцы с этим ранком
    ciphertext = []
    for rank in range(n_cols):
        for col_idx, col_rank in enumerate(order):
            if col_rank == rank:
                # прочитать столбец сверху вниз
                for r in range(n_rows):
                    ciphertext.append(matrix[r][col_idx])
                break

    return "".join(ciphertext)


def columnar_decrypt(ciphertext: str, key: str):
    """
    Дешифрование столбцовой перестановкой.
    Исходный алгоритм: зная размеры (rows, cols) и порядок столбцов, заполняем столбцы в порядке рангов,
    затем читаем матрицу построчно.
    """
    n_cols = len(key)
    n_rows = ceil(len(ciphertext) / n_cols)
    total = n_rows * n_cols
    # предполагаем, что ciphertext длина == total (т.е. padding присутствует)
    # Если нет — обработаем укороченно (но здесь предполагаем полный блок)
    order = columnar_order_from_key(key)
    # создаём пустую матрицу
    matrix = [[''] * n_cols for _ in range(n_rows)]

    idx = 0
    # Для рангов от 0..n_cols-1 найти столбец с этим рангом и заполнить его сверху вниз
    for rank in range(n_cols):
        for col_idx, col_rank in enumerate(order):
            if col_rank == rank:
                for r in range(n_rows):
                    if idx < len(ciphertext):
                        matrix[r][col_idx] = ciphertext[idx]
                        idx += 1
                break

    # прочитаем построчно
    plaintext_padded = []
    for r in range(n_rows):
        for c in range(n_cols):
            plaintext_padded.append(matrix[r][c])

    plaintext = "".join(plaintext_padded)
    # убрать возможный padding 'X' справа
    plaintext = plaintext.rstrip('X')
    return plaintext


# ---------------------------
# Fleissner / Cardan grille (Решетка Флейснера)
# ---------------------------
def rotate_matrix_cw(mat):
    """Поворот квадратной матрицы по часовой на 90 градусов."""
    n = len(mat)
    return [[mat[n - c - 1][r] for c in range(n)] for r in range(n)]


def apply_grille_encrypt(plaintext: str, grille_mask: list, k: int, pad_char='X'):
    """
    Шифрование с помощью решетки Флейснера.
    grille_mask — квадратная матрица k x k из 0/1, где 1 — отверстие (куда пишем).
    Алгоритм:
      - Текст вписывается по отверстиям решетки, затем решетка поворачивается CW, и т.д. (4 раза),
      - после заполнения всех клеток (k*k) берем результат (обычно читают столбцами/строками).
    Примечание: количество отверстий * 4 должно равняться k*k (или отверстия покрывают каждую клетку при 4 поворотах).
    """
    # подготовка текста
    text = plaintext.replace(" ", "")
    n = k
    total_cells = n * n
    # дополняем до total_cells
    if len(text) < total_cells:
        text = text + pad_char * (total_cells - len(text))
    elif len(text) > total_cells:
        raise ValueError("Длина текста больше, чем размер квадрата grille (k*k). Увеличьте k или сократите текст.")

    # Инициализация пустой матрицы размера k x k
    big_square = [[''] * n for _ in range(n)]
    mask = [row[:] for row in grille_mask]  # копия
    idx = 0
    for rotation in range(4):
        for i in range(n):
            for j in range(n):
                if mask[i][j] == 1:
                    if big_square[i][j] != '':
                        # если уже заполнено — это означает, что маска и повороты не корректны
                        raise ValueError("Некорректная маска: ячейка заполняется повторно.")
                    big_square[i][j] = text[idx]
                    idx += 1
        # Повернуть маску по часовой
        mask = rotate_matrix_cw(mask)

    # После четырёх поворотов все клетки должны быть заполнены
    # Собираем шифротекст — обычно по столбцам (как в описании) или построчно; возьмём по столбцам.
    ciphertext = []
    for c in range(n):
        for r in range(n):
            ciphertext.append(big_square[r][c])
    return "".join(ciphertext)


def apply_grille_decrypt(ciphertext: str, grille_mask: list, k: int):
    """
    Дешифрование решётки Флейснера.
    Получаем квадрат k x k, заполняем его по столбцам (как шифрование собирало),
    затем читаем по маске и поворотам отверстий последовательность символов => исходный текст.
    """
    n = k
    total = n * n
    if len(ciphertext) != total:
        raise ValueError("Длина шифротекста должна равняться k*k")

    # заполнить квадрат по столбцам (как в encrypt)
    big_square = [[''] * n for _ in range(n)]
    idx = 0
    for c in range(n):
        for r in range(n):
            big_square[r][c] = ciphertext[idx]
            idx += 1

    # теперь, применяя маску и повороты, считываем текст
    mask = [row[:] for row in grille_mask]
    recovered = []
    for rotation in range(4):
        for i in range(n):
            for j in range(n):
                if mask[i][j] == 1:
                    recovered.append(big_square[i][j])
        mask = rotate_matrix_cw(mask)

    return "".join(recovered)


# Удобная помощь: генерация маски из заданных позиций отверстий
def build_grille_from_positions(positions, k):
    """
    positions: список (i,j) координат отверстий для начальной ориентации (0-index).
    k: размер решётки.
    Возвращает k x k матрицу 0/1.
    """
    mask = [[0] * k for _ in range(k)]
    for (i, j) in positions:
        mask[i][j] = 1
    return mask


# ---------------------------
# Шифр Виженера (русский)
# ---------------------------
def vigenere_cipher_ru(text: str, key: str, mode='encrypt'):
    """
    Виженер для русского алфавита (33 буквы, включая Ё).
    mode: 'encrypt' или 'decrypt'
    Неалфавитные символы сохраняются; регистр сохраняется.
    """
    # Алфавит 33 буквы (включая Ё)
    ALPHABET = "АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ"
    N = len(ALPHABET)  # 33

    # Преобразуем ключ в сдвиги
    key_shifts = []
    for ch in key.upper():
        if ch in ALPHABET:
            key_shifts.append(ALPHABET.index(ch))
    if not key_shifts:
        raise ValueError("Ключ должен содержать буквы русского алфавита (включая Ё при необходимости).")

    result = []
    key_idx = 0
    for ch in text:
        up = ch.upper()
        if up in ALPHABET:
            p = ALPHABET.index(up)
            k_shift = key_shifts[key_idx % len(key_shifts)]
            if mode == 'encrypt':
                c = (p + k_shift) % N
                out = ALPHABET[c]
            elif mode == 'decrypt':
                p_idx = p
                # here p is index of C (cipher) when decrypting; compute original plaintext index
                orig = (p_idx - k_shift) % N
                out = ALPHABET[orig]
            else:
                raise ValueError("mode must be 'encrypt' or 'decrypt'")
            # восстановим регистр
            if ch.islower():
                result.append(out.lower())
            else:
                result.append(out)
            key_idx += 1
        else:
            result.append(ch)
    return "".join(result)



if __name__ == "__main__":


    # 1) Columnar Transposition — пример
    pt = "нельзянедооцениватьпротивника"  # пример из методички (убраны пробелы)
    key_col = "пароль"  # пример пароля
    print("Columnar Transposition пример")
    print("Открытый:", pt)
    ct_col = columnar_encrypt(pt, key_col)
    print("Зашифровано:", ct_col)
    dt_col = columnar_decrypt(ct_col, key_col)
    print("Дешифровано:", dt_col)
    assert dt_col == pt
    print("Columnar: OK\n")

    # 2) Виженер (русский) — тест (сквозная проверка)
    text_vig = "криптографиясерьезнаянаука"
    key_vig = "математика"
    print("Виженер пример")
    enc_vig = vigenere_cipher_ru(text_vig, key_vig, mode='encrypt')
    dec_vig = vigenere_cipher_ru(enc_vig, key_vig, mode='decrypt')
    print("Открытый:", text_vig)
    print("Зашифровано:", enc_vig)
    print("Дешифровано:", dec_vig)
    assert dec_vig == text_vig
    print("Vigenere RU: OK\n")

    # 3) Fleissner grille — пример
    # Для демонстрации используем k=4 (4x4).
    # Выберем такие отверстия, чтобы при 4 поворотах перекрывать все 16 клеток.
    # Пример простой корректной маски (один из возможных):
    # позиции отверстий (i,j) начальной ориентации:
    positions = [(0, 0), (1, 2), (2, 1), (3, 3)]
    k = 4
    grille = build_grille_from_positions(positions, k)
    # Текст длиной k*k = 16
    pt_grille = "договорподписалиXX"  # если надо, дополним X
    pt_grille = pt_grille.replace(" ", "")
    pt_grille = pt_grille[:k * k].ljust(k * k, 'X')  # точная длина
    print("Решетка Флейснера пример")
    print("Открытый:", pt_grille)
    try:
        ct_grille = apply_grille_encrypt(pt_grille, grille, k, pad_char='X')
        dt_grille = apply_grille_decrypt(ct_grille, grille, k)
        print("Зашифровано:", ct_grille)
        print("Дешифровано:", dt_grille)
        assert dt_grille == pt_grille
        print("Grille: OK\n")
    except ValueError as e:
        print("Ошибка при работе с решёткой:", e)
        print("Попробуйте изменить positions / k так, чтобы отверстия и повороты покрывали весь квадрат.\n")