Skip to content

Instantly share code, notes, and snippets.

@Forst
Created March 27, 2019 11:30
Show Gist options
  • Save Forst/d3731729807c182fc4eacabaae81b56d to your computer and use it in GitHub Desktop.
Save Forst/d3731729807c182fc4eacabaae81b56d to your computer and use it in GitHub Desktop.
Домашняя работа по криптографии, Московский политех
#!/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')
Мой дядя самых честных правил Когда не в шутку занемог Он уважать себя заставил И лучше выдумать не мог Его пример другим наука Но Боже мой какая скука С больным сидеть и день и ночь Не отходя ни шагу прочь Какое низкое коварство Полуживого забавлять Ему подушки поправлять Печально подносить лекарство Вздыхать и думать про себя Когда же чёрт возьмет тебя Так думал молодой повеса Летя в пыли на почтовых Всевышней волею Зевеса Наследник всех своих родных Друзья Людмилы и Руслана С героем моего романа Без предисловий сей же час Позвольте познакомить вас
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment