Домашняя работа по криптографии, Московский политех

crypto.py

#!/usr/bin/env python3

from abc import ABC, abstractmethod
from hashlib import sha256
from math import ceil
from secrets import token_bytes, randbits, randbelow


def bit(value, index):
    return (value & (2**index)) >> index


def bip(value, length):
    return bin(value)[2:].rjust(length, '0')


def hed(value, length):
    return hex(value)[2:].rjust(length * 2, '0')


class Cipher(ABC):
    """Абстрактный класс, задающий основные методы шифрования и расшифрования."""

    def __init__(self, key):
        key = self._normalize_key(key)
        self.key = key

    @classmethod
    def _normalize_key(cls, key):
        return key

    @abstractmethod
    def encrypt(self, data):
        ...

    @abstractmethod
    def decrypt(self, data):
        ...


class ShiftCipher(Cipher, ABC):
    """Абстрактный класс, реализующий сдвиговые шифры общего вида."""

    alphabets = (
        '0123456789',
        'abcdefghijklmnopqrstuvwxyz',
        'абвгдеёжзийклмнопрстуфхцчшщъыьэюя',
    )

    @classmethod
    def _normalize_key(cls, key):
        key = super()._normalize_key(key)
        key = int(key)
        return key

    def _update_shift(self, index_old, index_new, direction):
        pass

    def _encrypt(self, data, direction):
        output = ''

        for index, character in enumerate(data):
            isupper = character.isupper()
            character = character.lower()

            alphabet = None
            for a in self.alphabets:
                if character in a:
                    alphabet = a
                    break

            if alphabet is None:
                output += character
                continue

            index_old = alphabet.index(character)
            index_new = (index_old + self._key) % len(alphabet)
            self._update_shift(index_old, index_new, direction)

            character_new = alphabet[index_new]
            if isupper:
                character_new = character_new.upper()

            output += character_new

        return output

    def encrypt(self, data):
        self._key = self.key
        return self._encrypt(data, 1)

    def decrypt(self, data):
        self._key = -self.key
        return self._encrypt(data, -1)


class AutokeyCipher(ShiftCipher):
    """Реализует шифр Виженера с автоключом длиной 1."""

    def _update_shift(self, index_old, index_new, direction):
        if direction > 0:
            self._key = index_old
        elif direction < 0:
            self._key = -index_new


class PlayfairCipher(Cipher):
    """Реализует шифр Плейфера."""

    alphabet = 'абвгдежзиклмнопрстуфхцчшщьыэюя'
    rare_letter = 'ь'
    row_count = 5
    column_count = len(alphabet) // row_count
    replacement = str.maketrans('ёйъ', 'еиь')

    def __init__(self, key):
        if self.column_count * self.row_count != len(self.alphabet):
            raise Exception('Неверно задан рабочий алфавит.')

        if self.rare_letter not in self.alphabet:
            raise Exception(f'Редкая буква "{self.rare_letter}" не содержится в рабочем алфавите.')

        super().__init__(key)

    @classmethod
    def _normalize_key(cls, key: str):
        key = key.lower().translate(cls.replacement)
        normalized = ''

        for letter in key:
            if letter in normalized:
                continue
            elif letter in cls.alphabet:
                normalized += letter
            else:
                raise ValueError(f'Символ ключа "{letter}" не поддерживается рабочим алфавитом.')

        for letter in cls.alphabet:
            if letter not in normalized:
                normalized += letter

        return normalized

    def _l2p(self, letter):
        letter = letter.lower()

        if letter not in self.key:
            raise ValueError('Указанная буква не принадлежит ключу.')

        output = divmod(self.key.index(letter), self.column_count)
        return output

    def _p2l(self, row, column):
        if row >= self.row_count:
            raise ValueError(f'Указанная строка {row} больше количества строк ключа {self.row_count}.')
        if column >= self.column_count:
            raise ValueError(f'Указанный столбец {column} больше количества столбцов ключа {self.column_count}.')

        letter = self.key[row * self.column_count + column]
        return letter

    def _encrypt(self, data, direction):
        data = data.lower().translate(self.replacement)
        data = ''.join((letter for letter in data if letter in self.alphabet))

        output = ''

        i = 0
        while i < len(data):
            b = data[i:i+2]

            if len(b) == 1:
                b += self.rare_letter

            if b[0] == b[1] and b[0] != self.rare_letter:
                data = data[:i+1] + self.rare_letter + data[i+1:]
                b = data[i:i+2]

            i += 2

            p1, p2 = self._l2p(b[0]), self._l2p(b[1])

            if p1[0] == p2[0]:
                l1 = self._p2l(p1[0], (p1[1] + direction) % self.column_count)
                l2 = self._p2l(p2[0], (p2[1] + direction) % self.column_count)
            elif p1[1] == p2[1]:
                l1 = self._p2l((p1[0] + direction) % self.row_count, p1[1])
                l2 = self._p2l((p2[0] + direction) % self.row_count, p2[1])
            else:
                l1 = self._p2l(p1[0], p2[1])
                l2 = self._p2l(p2[0], p1[1])

            output += l1 + l2

        return output

    def encrypt(self, data):
        return self._encrypt(data, 1)

    def decrypt(self, data):
        return self._encrypt(data, -1)


class VerticalCipher(Cipher):
    @classmethod
    def _normalize_key(cls, key):
        key = super()._normalize_key(key)
        key = int(key)
        return key

    def encrypt(self, data):
        data = data.replace(' ', '').lower()

        step1 = ''
        is_odd_row = False

        for row in range(0, len(data), self.key):
            if is_odd_row:
                word = data[row + self.key - 1:row - 1:-1]
                word = word.rjust(self.key, ' ')
            else:
                word = data[row:row + self.key]
                word = word.ljust(self.key, ' ')

            step1 += word
            is_odd_row = not is_odd_row

        step2 = ''
        row_count = len(step1) // self.key
        is_odd_col = False

        for col in range(self.key - 1, -1, -1):
            if is_odd_col:
                r = range(row_count - 1, -1, -1)
            else:
                r = range(row_count)

            for row in r:
                step2 += step1[row * self.key + col]

            is_odd_col = not is_odd_col

        step2 = step2.replace(' ', '')

        return step2

    def decrypt(self, data):
        row_count = ceil(len(data) / self.key)
        remainder = self.key - len(data) % self.key

        is_odd_col = (self.key % 2 == 1)

        step1 = ''

        if len(data) % self.key == 0:
            step1 = data
        else:
            if row_count % 2 == 0:
                i = len(data)

                while i > 0:
                    offset = row_count - 1 if remainder > 0 else row_count
                    word = data[i-offset:i]

                    if is_odd_col:
                        word = word.ljust(row_count, ' ')
                    else:
                        word = word.rjust(row_count, ' ')

                    i -= offset
                    step1 = word + step1
                    is_odd_col = not is_odd_col

                    if remainder > 0:
                        remainder -= 1

            else:
                i = 0

                while i < len(data):
                    offset = row_count - 1 if remainder > 0 else row_count
                    word = data[i:i+offset]

                    if is_odd_col:
                        word = word.ljust(row_count, ' ')
                    else:
                        word = word.rjust(row_count, ' ')

                    i += offset
                    step1 += word
                    is_odd_col = not is_odd_col

                    if remainder > 0:
                        remainder -= 1

        step2 = ''
        for col in range(self.key):
            row = step1[col * row_count:(col + 1) * row_count]

            if col % 2 == 1:
                row = row[::-1]

            step2 += row

        step3 = ''
        is_odd_row = False
        for row in range(row_count):
            if is_odd_row:
                r = range(self.key)
            else:
                r = range(self.key - 1, -1, -1)

            for col in r:
                step3 += step2[col * row_count + row]

            is_odd_row = not is_odd_row

        return step3


class OneTimePadCipher(Cipher):
    def encrypt(self, data):
        out = bytearray()

        for i in range(len(data)):
            out.append(data[i] ^ self.key[i])

        return bytes(out)

    def decrypt(self, data):
        return self.encrypt(data)


class StreamA51Cipher(Cipher):
    @classmethod
    def _normalize_key(cls, key):
        key = super()._normalize_key(key)
        key = int(key) & 0xffffffffffffffff
        return key

    def encrypt(self, data):
        r1 = self.key & (2**19 - 1)
        r2 = (self.key & (2**22 - 1) << 19) >> 19
        r3 = (self.key & (2**23 - 1) << 41) >> 41

        output = bytearray()

        for byte in data:
            key = 0

            for i in range(8):
                x = bit(r1, 8)
                y = bit(r2, 10)
                z = bit(r3, 10)
                f = (x & y) | (x & z) | (y & z)

                if x == f:
                    b = bit(r1, 18) ^ bit(r1, 17) ^ bit(r1, 16) ^ bit(r1, 13)
                    r1 = (r1 << 1) & (2**19 - 1)
                    r1 |= b

                if y == f:
                    b = bit(r2, 21) ^ bit(r2, 20)
                    r2 = (r2 << 1) & (2**22 - 1)
                    r2 |= b

                if z == f:
                    b = bit(r3, 22) ^ bit(r3, 21) ^ bit(r3, 20) ^ bit(r3, 7)
                    r3 = (r3 << 1) & (2**23 - 1)
                    r3 |= b

                keybit = bit(r1, 18) ^ bit(r2, 21) ^ bit(r3, 22)
                key |= keybit << i

            output.append(byte ^ key)

        return bytes(output)

    def decrypt(self, data):
        return self.encrypt(data)


class BlockKuznechikCipher(Cipher):
    BLOCK_LENGTH = 16

    pi = (
        252, 238, 221, 17, 207, 110, 49, 22, 251, 196, 250, 218, 35, 197, 4, 77,
        233, 119, 240, 219, 147, 46, 153, 186, 23, 54, 241, 187, 20, 205, 95, 193,
        249, 24, 101, 90, 226, 92, 239, 33, 129, 28, 60, 66, 139, 1, 142, 79,
        5, 132, 2, 174, 227, 106, 143, 160, 6, 11, 237, 152, 127, 212, 211, 31,
        235, 52, 44, 81, 234, 200, 72, 171, 242, 42, 104, 162, 253, 58, 206, 204,
        181, 112, 14, 86, 8, 12, 118, 18, 191, 114, 19, 71, 156, 183, 93, 135,
        21, 161, 150, 41, 16, 123, 154, 199, 243, 145, 120, 111, 157, 158, 178, 177,
        50, 117, 25, 61, 255, 53, 138, 126, 109, 84, 198, 128, 195, 189, 13, 87,
        223, 245, 36, 169, 62, 168, 67, 201, 215, 121, 214, 246, 124, 34, 185, 3,
        224, 15, 236, 222, 122, 148, 176, 188, 220, 232, 40, 80, 78, 51, 10, 74,
        167, 151, 96, 115, 30, 0, 98, 68, 26, 184, 56, 130, 100, 159, 38, 65,
        173, 69, 70, 146, 39, 94, 85, 47, 140, 163, 165, 125, 105, 213, 149, 59,
        7, 88, 179, 64, 134, 172, 29, 247, 48, 55, 107, 228, 136, 217, 231, 137,
        225, 27, 131, 73, 76, 63, 248, 254, 141, 83, 170, 144, 202, 216, 133, 97,
        32, 113, 103, 164, 45, 43, 9, 91, 203, 155, 37, 208, 190, 229, 108, 82,
        89, 166, 116, 210, 230, 244, 180, 192, 209, 102, 175, 194, 57, 75, 99, 182
    )

    lc = (148, 32, 133, 16, 194, 192, 1, 251, 1, 192, 194, 16, 133, 32, 148, 1)

    @staticmethod
    def _gfmul(p1, p2):
        p = 0
        while p2:
            if p2 & 1:
                p ^= p1
            p1 <<= 1
            if p1 & 0x100:
                p1 ^= 0xc3
            p2 >>= 1
        return p & 0xff

    @staticmethod
    def X(k, a):
        return bytearray((k[i] ^ a[i] for i in range(len(a))))

    @classmethod
    def S(cls, a):
        return bytearray((cls.pi[b] for b in a))

    @classmethod
    def Sinv(cls, a):
        return bytearray((cls.pi.index(b) for b in a))

    @classmethod
    def l(cls, a):
        out = 0
        for i in range(len(a)):
            out ^= cls._gfmul(cls.lc[i], a[i])
        return out

    @classmethod
    def R(cls, a):
        output = bytearray([cls.l(a)]) + a[:15]
        return output

    @classmethod
    def Rinv(cls, a):
        rev = a[1:] + bytearray([a[0]])
        output = a[1:] + bytearray([cls.l(rev)])
        return output

    @classmethod
    def L(cls, a):
        for _ in range(16):
            a = cls.R(a)
        return a

    @classmethod
    def Linv(cls, a):
        for _ in range(16):
            a = cls.Rinv(a)
        return a

    @classmethod
    def LSX(cls, k, a):
        return cls.L(cls.S(cls.X(k, a)))

    @classmethod
    def SinvLinvX(cls, k, a):
        return cls.Sinv(cls.Linv(cls.X(k, a)))

    @classmethod
    def F(cls, k, a1, a0):
        return cls.X(cls.LSX(k, a1), a0), a1

    def __init__(self, key):
        super().__init__(key)

        self.K = [
            key[:16],
            key[16:]
        ]

        for i in range(1, 5):
            result = self.K[(i-1)*2], self.K[(i-1)*2+1]
            for offset in range(8):
                result = self.F(self.C[8*(i-1)+offset], *result)
            self.K.extend(result)

    def E(self, block):
        for i in range(9):
            block = self.LSX(self.K[i], block)
        block = self.X(self.K[9], block)
        return block

    def D(self, block):
        for i in range(9, 0, -1):
            block = self.SinvLinvX(self.K[i], block)
        block = self.X(self.K[0], block)
        return block

    @classmethod
    def pad(cls, data):
        padlen = cls.BLOCK_LENGTH - (len(data) % cls.BLOCK_LENGTH)
        data += bytearray([padlen] * padlen)
        return data

    @classmethod
    def unpad(cls, data):
        padlen = data[-1]
        if padlen > cls.BLOCK_LENGTH or data[-padlen:] != bytearray([padlen] * padlen):
            raise ValueError('Неверный пэддинг.')
        return data[:-padlen]

    def encrypt(self, data):
        data = self.pad(data)

        ct = bytearray(token_bytes(self.BLOCK_LENGTH))

        for i in range(0, len(data), self.BLOCK_LENGTH):
            x = self.X(data[i:i+self.BLOCK_LENGTH], ct[i:i+self.BLOCK_LENGTH])
            ct += self.E(x)

        return ct

    def decrypt(self, data):
        pt = bytearray()

        for i in range(self.BLOCK_LENGTH, len(data), self.BLOCK_LENGTH):
            x = self.D(data[i:i+self.BLOCK_LENGTH])
            pt += self.X(x, data[i-self.BLOCK_LENGTH:i])

        return self.unpad(pt)


BlockKuznechikCipher.C = tuple((
    BlockKuznechikCipher.L(bytearray.fromhex(hex(i + 1)[2:].rjust(32, '0')))
    for i in range(32)
))

##########

with open('text.txt', 'r') as f:
    test_plaintext = f.read().strip()
    test_plainbytes = test_plaintext.encode()

ciphers = (
    ('А. Шифр Цезаря', ShiftCipher, test_plaintext, 7),
    ('B. Шифр Виженера с автоключом', AutokeyCipher, test_plaintext, 7),
    ('C. Шифр Плейфера', PlayfairCipher, test_plaintext, 'пушкин'),
    ('D. Шифр маршрутной перестановки', VerticalCipher, test_plaintext, 7),
    ('E. Одноразовый блокнот Шеннона', OneTimePadCipher, test_plainbytes, token_bytes(len(test_plainbytes))),
    ('F. Поточный шифр A5/1', StreamA51Cipher, test_plainbytes, randbits(64)),
    ('G. Блочный шифр Кузнечик', BlockKuznechikCipher, test_plainbytes, token_bytes(32))
)


def display(x, is_plain=False):
    out = x

    if isinstance(x, bytes) or isinstance(x, bytearray):
        if is_plain:
            out = x.decode()
        else:
            out = x.hex()

    return out


for name, cipher, plaintext, ckey in ciphers:
    print(f'\033[1;7m {name.upper()} \033[0m')

    print(f'Исход: \033[93m{display(plaintext, True)}\033[0m')

    c = cipher(ckey)
    dckey = display(ckey)
    dkey = display(c.key)
    if dckey == dkey:
        print(f'Ключ:  {dckey}')
    else:
        print(f'Ключ:  {dckey} \033[2m({dkey})\033[0m')

    enc = c.encrypt(plaintext)
    print(f'Шифр:  \033[96m{display(enc)}\033[0m')

    dec = c.decrypt(enc)
    print(f'Текст: \033[92m{display(dec, True)}\033[0m')


##########


# RSA

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('Модульная инверсия не существует.')
    else:
        return x % m


print(f'\033[1;7m H. RSA (ЦИФРОВАЯ ПОДПИСЬ) \033[0m')
# Небезопасные простые числа выше 2^128
p = 340282366920938463463374607431768211507
q = 340282366920938463463374607431768211537
n = p * q
phi = (p - 1) * (q - 1)
e = 65537
d = modinv(e, phi)

hashsum = sha256().hexdigest()
sig = pow(int(hashsum, 16), d, n)
ver = pow(sig, e, n)

print(f'Исход: {test_plaintext}')
print(f'Ключ:  {hed(p, 16)}, {hex(q)[2:]}')
print(f'Хеш:   \033[93m{hashsum}\033[0m')
print(f'Подп:  \033[96m{hed(sig, 32)}\033[0m')
print(f'Пров:  \033[92m{hed(ver, 32)}\033[0m')


##########

print(f'\033[1;7m J. DH (ОБМЕН КЛЮЧАМИ) \033[0m')

g = 3
print(f'Ген:   {g}')
n = 0xfaec9a0e08ffa6c80622b6d7294cc2490b18e8c76781ce5eeebc062f1343c4db
print(f'Модул: {n}')

secret_a = randbelow(n)
print(f'a сек: \033[93m{secret_a}\033[0m')
secret_b = randbelow(n)
print(f'b сек: \033[93m{secret_b}\033[0m')

A = pow(g, secret_a, n)
print(f'A:     \033[96m{A}\033[0m')
B = pow(g, secret_b, n)
print(f'B:     \033[96m{B}\033[0m')

AB = pow(B, secret_a, n)
print(f's=AB:  \033[92m{AB}\033[0m')
BA = pow(A, secret_b, n)
print(f's=BA:  \033[92m{BA}\033[0m')

text.txt

Мой дядя самых честных правил Когда не в шутку занемог Он уважать себя заставил И лучше выдумать не мог Его пример другим наука Но Боже мой какая скука С больным сидеть и день и ночь Не отходя ни шагу прочь Какое низкое коварство Полуживого забавлять Ему подушки поправлять Печально подносить лекарство Вздыхать и думать про себя Когда же чёрт возьмет тебя Так думал молодой повеса Летя в пыли на почтовых Всевышней волею Зевеса Наследник всех своих родных Друзья Людмилы и Руслана С героем моего романа Без предисловий сей же час Позвольте познакомить вас