Как составить алгоритм шифрования

Каждый человек, который пользуется компьютером или смартфоном, ежедневно сталкивается с криптографией: начиная от работы в интернете по протоколу HTTPS и заканчивая печально известными вирусами-шифровальщиками. Однако далеко не все понимают, как работает криптография. Давайте попробуем в этом разобраться на конкретных примерах.

Википедия гласит:

Криптогра́фия (от др.-греч. κρυπτός — скрытый и γράφω — пишу) — наука о методах обеспечения конфиденциальности (невозможности прочтения информации посторонним), целостности данных (невозможности незаметного изменения информации), аутентификации (проверки подлинности авторства или иных свойств объекта), а также невозможности отказа от авторства.

Одним из разделов криптографии является наука о шифровании. В процессе шифрования происходит обратимое изменение информации с помощью некоего секрета, что делает информацию недоступной для тех, кто секретом не владеет. Базовые принципы шифрования мы и рассмотрим в этой статье.

Симметричное шифрование

Предположим, что сторона А хочет передать стороне Б секретную информацию. Стоп. А, Б — это всё некрасиво и неудобно. Именно поэтому в криптографии принято называть стороны обмена информацией именами Алиса (Alice) и Боб (Bob).

Итак, как Алиса может передать сообщение, чтобы никто, кроме Боба, не смог прочесть его? Необходимо как-то изменить эти данные по заранее согласованному с Бобом алгоритму. Простейшим способом реализации такой задачи является подстановочный шифр — алгоритм, при котором каждая буква сообщения заменяется на другую букву. Например, вместо первой буквы алфавита («А») Боб c Алисой будут использовать третью («В»), вместо второй («Б») — четвертую («Г») и так далее.

В этом случае алгоритмом шифрования является сдвиг букв алфавита, а ключом — цифра 2 (сдвиг на две позиции). Любой, кто знает алгоритм и ключ, сможет расшифровать сообщение Алисы. Кстати, попробуйте и вы расшифровать это сообщение — стретвоокуф. Вам поможет простой пример на Python 3:

# -*- coding: utf-8 -*-

ALPHA = u'абвгдеёжзийклмнопрстуфхцчшщьъэюя'
 
def encode(text, step):
    return text.translate(
        str.maketrans(ALPHA, ALPHA[step:] + ALPHA[:step]))
 
def decode(text, step):
    return text.translate(
        str.maketrans(ALPHA[step:] + ALPHA[:step], ALPHA))

Такие алгоритмы шифрования, при которых Алиса и Боб должны заранее придумать и согласовать одинаковый секрет, называются симметричными, а рассмотренный пример является самым простым алгоритмом этой группы и называется шифром Цезаря. Он считается небезопасным, и его не рекомендуется использовать. Наиболее популярными и достаточно криптостойкими симметричными алгоритмами являются 3DES и AES.

Асимметричное шифрование

Но что же делать, если Алиса и Боб находятся далеко друг от друга и не могут договориться об использовании одинакового секрета, поскольку есть некая Ева (от англ. eavesdropper — подслушивающий), которая так и хочет узнать тайны Алисы и Боба? В этом случае Боб может отправить Алисе замок, ключ от которого есть только у него. Алиса положит письмо в коробку и запрёт её на этот замок. Теперь ни Алиса, ни Ева не смогут открыть коробку и прочесть письмо.

Аналогичный подход используется в асиметричном шифровании, которое также называют криптосистемой с открытым ключом. В примере с Алисой и Бобом секретным ключом Боба будет ключ от замка, а публичным ключом условно можно назвать сам замок. Отправка Алисе замка — это алгоритм согласования ключей.

Наиболее популярным алгоритмом шифрования с открытым ключом является RSA. Вот как выглядит его реализация на языке Python с использованием библиотеки RSA:

# -*- coding: utf-8 -*-
  
import rsa

#Боб формирует публичный и секретный ключ

(bob_pub, bob_priv) = rsa.newkeys(512)

#Алиса формирует сообщение Бобу и кодирует его в UTF8, 
#поскольку RSA работает только с байтами
message = 'hello Bob!'.encode('utf8')

#Алиса шифрует сообщение публичным ключом Боба
crypto = rsa.encrypt(message, bob_pub)

#Боб расшифровывает сообщение своим секретным ключом
message = rsa.decrypt(crypto, bob_priv)
print(message.decode('utf8'))

Более подробно с алгоритмом RSA можно ознакомиться в другой нашей статье.

Стоит также отметить, что асиметричные алгоритмы работают медленнее, чем симметричные, и очень часто встречается схема, когда по асимметричному алгоритму шифруется симметричный секрет и дальнейший обмен сообщениями происходит по симметричному алгоритму.

Заключение

В этой статье мы рассмотрели лишь один из разделов криптографии — шифрование. Если тема вас заинтересовала, следите за нашими дальнейшими публикациями, а также посмотрите подборку с материалами по криптографии.

Время на прочтение
5 мин

Количество просмотров 90K

Немного о проекте

Мне, лично, давно была интересна тема шифрования информации, однако, каждый раз погрузившись в эту тему, я осознавал насколько это сложно и понял, что лучше начать с чего-то более простого. Я, лично, планирую написать некоторое количество статей на эту тему, в которых я покажу вам различные алгоритмы шифрования и их реализацию в Python, продемонстрирую и разберу свой проект, созданный в этом направлении. Итак, начнем.

---

Для начала, я бы хотел рассказать вам какие уже известные алгоритмы мы рассмотрим, в моих статьях. Список вам представлен ниже:

• Шифр Цезаря

• Шифр Виженера

• Шифр замены

• Омофонический шифр

• RSA шифрование

Шифр Цезаря

Итак, после небольшого введения в цикл, я предлагаю все-таки перейти к основной теме сегодняшней статьи, а именно к Шифру Цезаря.

Что это такое?

Шифр Цезаря – это простой тип подстановочного шифра, где каждая буква обычного текста заменяется буквой с фиксированным числом позиций вниз по алфавиту. Принцип его действия можно увидеть в следующей иллюстрации:

Какими особенностями он обладает?

У Шифра Цезаря, как у алгоритма шифрования, я могу выделить две основные особенности. Первая особенность – это простота и доступность метода шифрования, который, возможно поможет вам погрузится в эту тему, вторая особенность – это, собственно говоря, сам метод шифрования.

Программная реализация

В интернете существует огромное множество уроков, связанных с криптографией в питоне, однако, я написал максимально простой и интуитивно понятный код, структуру которого я вам продемонстрирую.

Начнем, пожалуй, с создания алфавита. Для этого вы можете скопировать приведенную ниже строку или написать все руками.

alfavit =  'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZАБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯАБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ'
# Создаем алфавит

Далее, нам нужно обозначить программе шаг, то есть смещение при шифровании. Так, например, если мы напишем букву “а” в сообщении, тот при шаге “2”, программа выведет нам букву “в”.

Итак, создаем переменную smeshenie, которая будет вручную задаваться пользователем, и message, куда будет помещаться наше сообщение, и, с помощью метода upper(), возводим все символы в нашем сообщении в верхний регистр, чтобы у нас не было ошибок. Потом создаем просто пустую переменную itog, куда мы буем выводить зашифрованное сообщение. Для этого пишем следующее:

smeshenie = int(input('Шаг шифровки: '))    #Создаем переменную с шагом шифровки
message = input("Сообщение для шифровки: ").upper()    #создаем переменнную, куда запишем наше сообщение
itog = ''    #создаем переменную для вывода итогового сообщения

Итак, теперь переходим к самому алгоритму шифровки. Первым делом создаем циклfor, где мы определим место букв, задействованных в сообщении, в нашем списке alfavit, после чего определяем их новые места (далее я постараюсь насытить код с пояснениями):

for i in message:
    mesto = alfavit.find(i)    #Вычисляем места символов в списке
    new_mesto = mesto + smeshenie    #Сдвигаем символы на указанный в переменной smeshenie шаг

Далее, мы создаем внутри нашего цикла условие if , в нем мы записываем в список itog мы записываем наше сообщение уже в зашифрованном виде и выводим его:

for i in message:
    mesto = alfavit.find(i)
    new_mesto = mesto + smeshenie
    if i in alfavit:
        itog += alfavit[new_mesto]  # Задаем значения в итог
    else:
        itog += i
print (itog)

Модернизация

Вот мы и написали программу, однако она имеет очень большой недостаток: “При использовании последних букв(русских), программа выведет вам английские буквы. Давайте это исправим.

Для начала создадим переменную lang, в которой будем задавать язык нашего шифра, а так же разделим английский и русский алфавиты.

alfavit_EU =  'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'
alfavit_RU = 'АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯАБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ'
smeshenie = int(input('Шаг шифровки: '))
message = input("Сообщение для шифровки: ").upper()
itog = ''
lang = input('Выберите язык RU/EU: ')   #Добавляем возможность выбора языка

Теперь нам надо создать условие, которое проверит выбранный язык и применит его, то есть обратится к нужному нам алфавиту. Для этого пишем само условие и добавляем алгоритм шифрования, с помощью которого будет выполнено шифрование:

if lang == 'RU':
    for i in message:
        mesto = alfavit_RU.find(i)   # Алгоритм для шифрования сообщения на русском 
        new_mesto = mesto + smeshenie
        if i in alfavit_RU:
            itog += alfavit_RU[new_mesto]
        else:
            itog += i
else:
    for i in message:
        mesto = alfavit_EU.find(i)		# Алгоритм для шифрования сообщения на английском 
        new_mesto = mesto + smeshenie
        if i in alfavit_EU:
            itog += alfavit_EU[new_mesto]
        else:
            itog += i

Дешифровка сообщения

Возможно это прозвучит несколько смешно, но мы смогли только зашифровать сообщение, а насчет его дешифровки мы особо не задумывались, но теперь дело дошло и до неё.

По сути, дешифровка – это алгоритм обратный шифровке. Давайте немного переделаем наш код (итоговый вид вы можете увидеть выше).

Для начала, я предлагаю сделать “косметическую” часть нашей переделки. Для этого перемещаемся в самое начало кода:

alfavit =  'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZАБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯАБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ'
smeshenie = int(input('Шаг шифровки: '))
message = input("Сообщение для ДЕшифровки: ").upper()    #заменяем слово шифровка, на дешифровка
itog = ''

Остальное можно оставить так же, но если у вас есть желание, то можете поменять названия переменных.

По большому счету, самые ‘большие’ изменения у нас произойдут в той части кода, где у нас находится алгоритм, где нам нужно просто поменять знак “+” на знак “-“. Итак, переходим к самому циклу:

if lang == 'RU':
    for i in message:
        mesto = alfavit_RU.find(i)    
        new_mesto = mesto + smeshenie    # Меняем знак + на знак -
        if i in alfavit_RU:
            itog += alfavit_RU[new_mesto]
        else:
            itog += i
else:
    for i in message:
        mesto = alfavit_EU.find(i)		 # Меняем знак + на знак - 
        new_mesto = mesto + smeshenie
        if i in alfavit_EU:
            itog += alfavit_EU[new_mesto]
        else:
            itog += i

Итоговый вид программы

Итак, вот мы и написали простейшую программу для шифрования методом Цезаря. Ниже я размещу общий вид программы без моих комментариев, чтобы вы еще раз смогли сравнить свою программу с моей:

alfavit_EU =  'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'
alfavit_RU = 'АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯАБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ'
smeshenie = int(input('Шаг шифровки: '))
message = input("Сообщение для ДЕшифровки: ").upper()
itog = ''
lang = input('Выберите язык RU/EU: ')
if lang == 'RU':
    for i in message:
        mesto = alfavit_RU.find(i)
        new_mesto = mesto + smeshenie
        if i in alfavit_RU:
            itog += alfavit_RU[new_mesto]
        else:
            itog += i
else:
    for i in message:
        mesto = alfavit_EU.find(i)
        new_mesto = mesto + smeshenie
        if i in alfavit_EU:
            itog += alfavit_EU[new_mesto]
        else:
            itog += i
print (itog)

Итог

Вы успешно написали алгоритм шифровки и дешифровки сообщения на Python с помощью метода Цезаря. В следующей статье мы с вами рассмотрим Шифр Виженера, а также разберем его реализацию на Python, а пока я предлагаю вам написать в комментариях варианты модернизации программы(код или просо предложения и пожелания). Я обязательно учту ваше мнение.



Человечество за всю свою историю никогда не развивалось так быстро, как в новейшем времени. Если раньше компьютер могла купить только крупная компания, то сейчас его может позволить себе каждый. Вместе с компьютером в жизнь людей прочно вошел интернет, с помощью которого стало возможным передавать информацию по всему земному шару в считанные секунды. Однако такие возможности имеют свои минусы, и самым главным из них является проблема информационной безопасности.

Ключевые слова:



шифрование, информационная безопасность, защита информации, алгоритм AOCRYPT.

1. 
   
   Решение проблемы защиты данных. Алгоритмы шифрования
   
   

Данные в сети могут быть украдены злоумышленниками и использованы в неблагоприятных целях. Некоторые вредоносные программы могут просто занимать место на диске и замедлять ОС, а другие перезаписывать MBR (загрузочная область диска) своим кодом и при перезапуске компьютера стирать данные с дисков (например, VineMEMZ). Во избежание запуска трояна — вредоносной программы, маскирующейся под любую другую, используется криптографическая функция SHA-256, MD5 и др. Результат функции является уникальным для каждого файла, поэтому, зная проверочную сумму оригинала, можно сразу понять о принадлежности данного файла к вредоносному ПО. Кроме того, многие криптографические алгоритмы были реализованы на компьютере, что позволило зашифровывать информацию с помощью сгенерированного ключа, который невозможно подобрать, ведь на это могут уйти десятки лет (например, RSA-2048).

Все алгоритмы шифрования делятся на две группы: симметричные и ассиметричные. Для симметричных алгоритмов нужен один и тот же ключ для кодирования и декодирования информации, а для ассиметричных — разные. Если алгоритм не поддается взлому в течение пяти лет — значит он может использоваться для защиты секретной информации. Ниже приведены одни из надежных и распространенных криптографических алгоритмов:

—

AES

внастоящее время является федеральным стандартом шифрования США. Используется вариант шифра с размером блока 128 бит.

—

Blowfish

— сложная схема выработки ключа существенно затрудняет атаку на алгоритм методом перебора, однако делает его непригодным для использования в системах, где ключ часто меняется, и на каждом ключе шифруется небольшие по объему данные. Алгоритм подходит для систем, в которых на одном и том же ключе шифруются большие массивы данных.

—

RSA

— алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел. Стала первой системой, пригодной и для шифрования, и для цифровой подписи. Алгоритм используется в большом числе криптографических приложений, включая PGP, S/MIME, TLS/SSL, IPSEC/IKE и других.

Принцип работы всех криптографических алгоритмов одинаков: генерируется ключ, в соответствии с которым по установленному алгоритму изменяются данные и записываются в зашифрованный файл. Однако применение криптографических алгоритмов разное. Автором разработан собственный симметричный алгоритм (AOCRYPT) и программа-шифровальщик (AOCRYPT0R) на языке программирования C++.

Рассмотрим более подробно принципы работы двух наиболее популярных алгоритмов — BlowFish и RSA.

Алгоритм шифрования BLOWFISH






.



Blowfish — криптографический алгоритм, реализующий блочное симметричное шифрование с переменной длиной ключа. Разработан Брюсом Шнайером в 1993 году. Выполнен на простых и быстрых операциях: XOR, подстановка, сложение. Является незапатентованным и свободно распространяемым. По заявлению автора, критериями проектирования Blowfish были: скорость (шифрование на 32-битных процессорах происходит за 26 тактов); простота (за счёт использования простых операций, уменьшающих вероятность ошибки реализации алгоритма); компактность (возможность работать в менее, чем 5 Кбайт памяти); настраиваемая безопасность (изменяемая длина ключа).

Алгоритм разделён на этапы.

1. Инициализация массивов P и S при помощи секретного ключа K

— Инициализация фиксированной строкой, состоящей из шестнадцатеричных цифр мантиссы числа пи.

— Производится операция XOR над P_1 с первыми 32 битами ключа K, над P_2 со вторыми 32-битами и так далее. Если ключ K короче, то он накладывается циклически.

1. Шифрование ключей и таблиц замен

— Алгоритм шифрования 64-битного блока, используя инициализированные ключи P_1 — P_18 и таблицу замен S_1 — S_4, шифрует 64 битную нулевую (0x0000000000000000) строку. Результат записывается в P_1, P_2.

— P_1 и P_2 шифруются изменёнными значениями ключей и таблиц замен. Результат записывается в P_3 и P_4.

— Шифрование продолжается до изменения всех ключей P_1 — P_18 и таблиц замен S_1 — S_4.

1. Шифрование текста полученными ключами и F(x), с предварительным разбиением на блоки по 64 бита. Если невозможно разбить начальный текст точно на блоки по 64 бита, используются различные режимы шифрования для построения сообщения, состоящего из целого числа блоков. Суммарная требуемая память 4168 байт.

Дешифрование происходит аналогично, только P_1 — P_18 применяются в обратном порядке.

Алгоритм шифрования RSA



(аббревиатура от фамилий Rivest, Shamir и Adleman) — криптографический алгоритм с открытым ключом. Принцип работы алгоритма представлен на схеме ниже.

Рис. 1. Схема работы RSA (шифрование и дешифрование)

Предположим, Боб хочет послать Алисе сообщение m. Сообщениями являются целые числа в интервале от 0 до n-1, т. е. m принадлежит Zn.

1. Алгоритм шифрования:

— Взять открытый ключ (e, n) Алисы

— Взять открытый текст m

— Зашифровать сообщение с использованием открытого ключа Алисы:

— C = E(m) = me mod n

1. Алгоритм дешифрования:

— Принять зашифрованное сообщение c

— Взять свой закрытый ключ (d, n)

— Применить закрытый ключ для расшифрования сообщения:

— m = D(c) = cd mod n

Данная схема на практике не используется по причине того, что она не является надёжной. Функция E(m) является детерминированной — при одних и тех же значениях входных параметров выдаёт одинаковый результат. В настоящее время используется смешанный алгоритм шифрования, в котором сначала шифруется сеансовый ключ, а потом уже с его помощью участники шифруют свои сообщения симметричными системами. После завершения сеанса сеансовый ключ, как правило, уничтожается.

Рис. 2. Алгоритм шифрования сеансового ключа

1. 
   
   Разработка алгоритма
   
   
   
   
   AOCRYPT
   
   

Создание программного обеспечения на основе разрабатываемого алгоритма AOCRYPT произведено на языке C++ в среде Code::Blocks — это свободная кроссплатформенная среда разработки. Code::Blocks использует библиотеку wxWidgets. Имея открытую архитектуру, может масштабироваться за счёт подключаемых модулей. Code::Blocks разрабатывается для Windows, Linux и Mac OS X. Среду можно собрать из исходников практически под любую Unix-подобную систему, например FreeBSD, PC-BSD.

Принцип работы






AOCRYPT

Самый простой способ зашифровать данные — это просто инвертировать каждый байт файла, то есть:


новое значение = 255








— оригинальное значение.


Данный алгоритм является самым простым и небезопасным способом шифрования. Для надежного шифрования нужно сгенерировать ключ, но создавать его с помощью функции srand() крайне небезопасно в криптографии, потому что данная функция создает предсказуемые значения ключа. Безопаснее будет использовать специальные библиотеки, но самым безопасным вариантом является генерация ключа, связанная с человеческим фактором. Человек может вводить данные с помощью клавиатуры и мыши. Создавать ключ с помощью ввода с клавиатуры займет много времени, а с мышью проще и «неповторимей», т. к. сдвиг на 1–2 пикселя повлияет на результат. Ниже приведен алгоритм генерации ключа (max = 512 байт — размер ключа):

Рис. 3. Алгоритм генерации ключа

Итак, ключ готов! Пусть файл шифруется по данному алгоритму:

новое значение = ключ [




i




] + оригинальное значение

Такой способ обеспечивает более высокую безопасность, но зная тип зашифрованного файла, можно сразу определить первые значения ключа. Например, каждое выполняемое приложение ОС Windows и некоторые для MSDOS начинаются с MZ — инициалов Марка Збиковски. Подставив значения в формулу выше и решив простое уравнение, можно определить два значения ключа, а так как каждые 512 байт будут шифроваться одними и теми же числами, то можно расшифровать часть значений после инициалов.

Рис. 4. Заголовок.exe файла (обведен в синий прямоугольник)

Было решено разбить ключ на две части по 256 байт. Пусть первая часть будет отвечать за числа, с которыми производят действия, а вторая — за сами действия, причем первые 4 бита — номер действия, а вторые — номер дополнительного числа в ряду. Теперь с каждым байтом файла будут производиться действия, в которых будут принимать участие 2 байта ключа.

Первое число = ключ [




i




]

Второе число = ключ [номер доп. числа в








строке из 16 байт]

новое значение = оригинальное значение ± результат действия

Данный алгоритм является еще более надежным, чем предыдущие версии AOCRYPT, но если файл имеет данные, которые повторяются каждые 256 байт, то злоумышленник может сразу догадаться, что файл имеет повторяющееся фрагменты. Заключительный этап разработки AOCRYPT — добавление сдвига действий на 4 бита каждые 256 байт данных. Конечный алгоритм шифрования данных приведен ниже. В программе использованы следующие переменные:

— ac — массив номеров доп. чисел и действий над ними

— f — номер элемента ключа; d — номер действия или доп. числа

— oddnum — доп. число

— sec — номер действия; shft — сдвиг (в 4 бит)

— fdata — данные файла; fsize — размер файла

Рис. 5. Конечный вариант алгоритма шифрования

1. 
   
   Разработка программного обеспечения
   
   
   
   
   AOCRYPT
   
   
   
   
   0
   
   
   
   
   R
   
   

Для создания графического интерфейса использован Windows API –набор базовых функций интерфейсов программирования приложений операционных систем семейств Microsoft Windows, который предоставляет прямой способ взаимодействия приложений пользователя с операционной системой Windows. Windows API представляет собой множество функций, структур данных и числовых констант, следующих соглашениям языка Си. В то же время конвенция вызова функций отличается от cdecl, принятой для языка C: Windows API использует stdcall (winapi). Для облегчения переноса на другие платформы программ, написанных с опорой на Windows API, разработана библиотека Wine.

Wine — свободное программное обеспечение, позволяющее пользователям UNIX-подобных операционных систем исполнять 16-, 32- и 64- битные приложения без наличия при этом установленной Microsoft Windows. Wine также предоставляет программистам библиотеку программ Winelib, при помощи которой они могут компилировать Windows-приложения для портирования их в UNIX-подобные операционные системы. Название W. I. N.E. — рекурсивный акроним и расшифровывается «Wine Is Not an Emulator» — «W. I. N.E. — это не эмулятор». Имеется в виду, что Wine это не эмулятор компьютера или виртуальная машина, как, например, qemu, VirtualBox и другие подобные им. С помощью Wine данная программа может свободно работать на ОС Linux и MacOS.

В интерфейсе программы использованы следующие элементы: кнопки, поля для отображения локации файла на диске. Соответственно, при нажатии кнопки

Browse

создается диалог выбора файла, кнопки

Process

файл шифруется или расшифровывается, кнопки

Quit

программа завершает работу. Также в интерфейс добавлен логотип разработчика, рамки, музыкальное сопровождение. Все это было сжато в 50.0Кб, что обеспечивает быстрое скачивание и эксплуатацию данного ПО.

Рис. 6. Графический интерфейс программы Aocrypt0r

При разработке программного обеспечения были решены следующие проблемы. Во-первых, во время работы программы было замечено сильное мерцание всех элементов окна. Это было обусловлено тем, что видеокарта отрисовывала большее число кадров в секунду, чем мог отрисовать монитор. Окно программы вырисовается следующим образом: сначала происходит полное заполнение всего белым цветом, а потом начинают отображаться элементы. Так, мерцание происходило из-за того, что на экран выводились моменты, когда все окно было закрашено белым цветом. Для решения проблемы использован алгоритм вертикальной синхронизации — двойная буферизация. Для этого изображение, отрисованное видеокартой, подаётся не сразу на экран, а в специальный буфер (область памяти). Как только монитор отрисует следующий кадр, содержимое этого буфера передаётся на монитор, а в буфер пишется следующий кадр. С технической точки зрения это реализованно как смена указателя на первичный буфер (тот, из которого изображение поступает на монитор): два буфера меняются местами, и, пока изображение из нового буфера выводится на экран, следующий кадр пишется в старый буфер. Затем эта операция повторяется.

Логотип SATAGAX был сжат с помощью


собственного алгоритма




imagecom




-256.


Формат поддерживает до 255 цветов. Первые два слова — размеры изображения в пикселях, затем идет байт, отвечающий за количество цветов в палитре, затем данные самой палитры в формате RGB, потом номера цветов в соответствии с палитрой. Если есть повторяющееся подряд цвета, то ставится сигнальный байт 0, затем количество повторений цвета и номер цвета в палитре. Это очень эффективно сжимает простые изображения, в отличие от BMP. Так в формате BMP логотип весит 126.0Кб, PNG: 25.2Кб, imagecom-256: 53.0Кб. Но, если PNG фактически больше наподдаётся сжатию, то изображения imagcom-256 очень хорошо сжимаются, и после сжатия, например, в zip архив, размер становится равным 25.3Кб. Программа распаковывает данные в память в формате BGRA, а затем создает в памяти 24-х битное BMP изображение и выводит его на экран с помощью команды:

StretchDIBits


(


hdcmem


, 0, 0,


xres


,


yres


, 0, 0,


xres


,


yres


,


logodata


, &


info


,


DIB


_


RGB


_


COLORS


,


SRCCOPY


);

xres, yres — размеры изображения, logodata — данные, info — заголовок BMP изображения в памяти.

Алгоритм работает следующим образом. Пусть существует некоторое изображение. В начале оно конвертируется в изображение с палитрой на 255 цветов, затем imagecom-256 создает и записывает в файл палитру изображения. Далее imagecom-256 считывает цвет каждого пикселя изображения и сравнивает его с цветом в палитре. Если цвета совпадают, то в файл записывается номер соответствующего цвета в палитре.

Одним из критериев при создании программного обеспечения был минимальный размер (до 50 кБ). На свободное после разработки основной части программы интерфейса место была добавлена фоновая трекерная музыка. Размер аудио файла — 12.0Кб. Для сравнения: WAV файл всего в 2 секунды весит целых 1.5Мб! Трекерная (модульная) музыка — музыка, созданная на компьютере при помощи программы-«трекера» (в данном случае Fasttracker II), представляющей собой специализированный музыкальный редактор. Музыка формата XM занимает очень маленькие объемы из-за принципа хранения данных в виде номеров нот, команд и 8-ми битных WAV семплов. Для проигрывания XM формата использована библиотека UFMOD, разработанную на ассемблере.

Заключение

Таким образом, и алгоритм, и программное обеспечение для шифрования были успешно созданы, но это далеко не предел возможностей криптографии. Программа-шифровальщик имеет общий размер, равный 50.0Кб, что делает ее портативной и удобной в использовании. Кроме того, с помощью ПО Wine стал возможен запуск данной программы не только на ОС Windows, но и на Linux и MacOS! Ключ алгоритма имеет размер в 512 байт, а также зависимость выполняемых операций от ключа, что делает взлом перебором практически невозможным в настоящее время. В целом, любая программа-шифровальщик представляет собой несложное, но мощное приложение, превращающее файлы в массив данных, который можно декодировать только при наличии ключа. Данный алгоритм может применятся как для электронных подписей, так и для шифрования файлов или архивов. Способен работать с большими объемами информации, для чего и был предназначен.

Сравнение кодировок приведено ниже (1-исходный файл, 2-инвертирование, 3-aocrypt + 4-ключ)

Рис. 7. Сравнение кодировок

В стадии разработки находится отдельная операционная система, загружающееся с внешнего устройства и работающая в 16-ти битном незащищенном режиме, что позволяет использовать драйвера BIOS и неограниченно изменять любые данные на жестких дисках. Данная ОС позволит зашифровывать целые диски с помощью алгоритма AOCRYPT, который будет совершенствоваться, если будут обнаружены серьезные уязвимости. Шифрование дисков целиком не только не даст загрузить систему и просмотреть файлы, но и просмотреть файлы на диске, подключив его к другому устройству. Так, работа над проектом еще не завершена, и в будущем есть множество перспектив его развития.

Разработанное программное обеспечение Aocrypt0r 1.02e находится в свободном доступе по ссылке: http://satagax.com/data/aocrypt0r1.02e.zip Альтернативная ссылка:

https://drive.google.com/uc?export=download&id=146XmbIRZwHj6gF7mGPg-xa8nSt1aIvjl).

Исходный код алгоритма сжатия изображений imagecom-256 доступен по ссылке: https://github.com/aolvos/imagecom-256

Литература:

1. Баричев, С. Г. Основы современной криптографии. — М.: СИНТЕГ, 2011.

2. Фергюсон Н.. Практическая криптография. — М.: Диалектика, 2004.

3. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы. — М.: Триумф, 2002.

4. Интернет-энциклопедия «Википедия». RSA. MZ. Blowfish [Электронный ресурс]. URL: https://ru.Wikipedia.org/wiki/RSA; https://ru.wikipedia.org/wiki/MZ; https://ru.wikipedia.org/wiki/Blowfish

5. Официальный сайт UFMOD [Электронный ресурс]. URL: https://ufmod.sourceforge.io/ind_ru.htm

6. Портал stackoverflow.com [Электронный ресурс]. URL: https://ru.stackoverflow.com/

7. Портал rohos.ru [Электронный ресурс]. URL: http://www.rohos.ru/help/crypto_algorithms

Алгоритмы шифрования

Эта первая практическая работа, которая посвящена базовым конструкциям языка Python. Также в этой работе описан общий подход к выполнению заданий.

Все исходники к работам можно найти в шаблоне репозитория курса. Если вы еще не настроили рабочее окружение, то перейдите в раздел «Настройка рабочего окружения».

Прежде чем приступить к выполнению работы

Перед тем как начать выполнять задания не забудьте перейти в рабочую директорию и активировать ваше виртуальное окружение:

$ gocs102 && cd homework01
$ workon cs102

При выполнении работ мы будем придерживаться простого подхода к ветвлению под названием GitHub flow (есть и другие подходы, например, gitflow). Приступая к новой практической работе создавайте ветку с именем этой работы:

(cs102) $ git checkout -b homework01 master
Switched to a new branch 'homework01'

Чтобы отобразить список локальных веток можно воспользоваться командой git branch:

(cs102) $ git branch
* homework01
  master

Символ * указывает на какой ветке вы находитесь. Для переключения между ветками используйте команду git checkout имя_ветки.

Шифр Цезаря

Шифр Цезаря является одним из самых простых методов шифрования. Для кодирования сообщения все буквы алфавита сдвигают на три символа вперед:

A -> D, B -> E, C -> F, и так далее

Сдвиг трёх последних букв алфавита:

Используя шифр Цезаря, слово PYTHON будет закодировано следующим образом:

Вам необходимо написать тело для следующих двух функций в файле caesar.py:

def encrypt_caesar(plaintext: str, shift: int = 3) -> str:
    """
    Encrypts plaintext using a Caesar cipher.

    >>> encrypt_caesar("PYTHON")
    'SBWKRQ'
    >>> encrypt_caesar("python")
    'sbwkrq'
    >>> encrypt_caesar("Python3.6")
    'Sbwkrq3.6'
    >>> encrypt_caesar("")
    ''
    """
    ciphertext = ""
    # PUT YOUR CODE HERE
    return ciphertext


def decrypt_caesar(ciphertext: str, shift: int = 3) -> str:
    """
    Decrypts a ciphertext using a Caesar cipher.

    >>> decrypt_caesar("SBWKRQ")
    'PYTHON'
    >>> decrypt_caesar("sbwkrq")
    'python'
    >>> decrypt_caesar("Sbwkrq3.6")
    'Python3.6'
    >>> decrypt_caesar("")
    ''
    """
    plaintext = ""
    # PUT YOUR CODE HERE
    return plaintext

Обратите внимание, что вторым аргументом функции является сдвиг (shift), например, при сдвиге равном нулю сообщение останется без изменений (A -> A, B -> B, ...).

Hint

Воспользуйтесь встроенными функциями ord() и chr(). Функция ord() позволяет получить код указанного символа, а chr() работает наоборот – возвращает символ по его коду.

Info

О кодировках можно почитать тут и тут.

В результате переменные ciphertext и plaintext должны содержать зашифрованное и расшифрованное сообщения соответственно.

Проверить работу функций можно с помощью примеров, приведенных в доктестах (текст внутри функции, который заключен в тройные кавычки и похож на работу с интерпретатором в интерактивном режиме). Запустить доктесты можно с помощью следующей команды (при условии, что файл с программой называется caesar.py):

(cs102) $ python -m doctest -v caesar.py

Доктесты обычно играют роль примеров и не используются в качестве полноценного фреймворка для автоматического тестирования. Поэтому мы будем использовать стандартную библиотеку unittest для тестирования наших приложений (наиболее популярной альтернативой является pytest). Для запуска тестов можно воспользоваться следующей командой:

(cs102) $ python -m unittest -v tests.test_caesar

или для запуска всех тестов:

(cs102) $ python -m unittest discover

Также обратите свое внимание на официальное руководство по стилю pep8 (некоторые пояснения по оформлению кода можно найти здесь).

Если вы добились успешного прохождения тестов, не забудьте сделать коммит, который зафиксирует ваши изменения, например:

(cs102) $ git add homework01/caesar.py
(cs102) $ git commit -m "Реализована функция encrypt_caesar()"

и аналогично:

(cs102) $ git add homework01/caesar.py
(cs102) $ git commit -m "Реализована функция decrypt_caesar()"

Note

Вы можете воспользоваться приложением Source Tree для наглядного отслеживания вносимых изменений.

Также не забывайте периодически отправлять ваши изменения на сервер:

(cs102) $ git push origin homework01

В качестве дополнительного упражнения вам предлагается реализовать алгоритм взлома шифра Цезаря, основанный на использовании словаря. Функция caesar_breaker должна вернуть наиболее подходящий сдвиг для зашифрованного сообщения:

def caesar_breaker(ciphertext: str, dictionary: tp.Set[str]) -> int:
    """
    >>> d = {"python", "java", "ruby"}
    >>> caesar_breaker("python", d)
    0
    >>> caesar_breaker("sbwkrq", d)
    3
    """
    best_shift = 0
    # PUT YOUR CODE HERE
    return best_shift

Шифр Виженера

Шифр Виженера очень похож на шифр Цезаря, за тем исключением, что каждый символ сообщения сдвигается на определяемое ключом значение. Ключ – это слово, каждый символ которого указывает на сколько позиций должен быть сдвинут соответствующий символ в шифруемом сообщении. Так, A означает сдвиг на 0 символов, B на 1 и т.д.

Если длина ключа меньше длины слова, подлежащего шифрованию, то ключ повторяется необходимое число раз, например:

Простой текст: ATTACKATDAWN
Ключ: LEMONLEMONLE
Зашифрованный текст: LXFOPVEFRNHR

Ваша задача написать тело для следующих двух функций в файле vigenere.py так, чтобы переменные ciphertext и plaintext содержали зашифрованное и расшифрованное сообщения соответственно:

def encrypt_vigenere(plaintext: str, keyword: str) -> str:
    """
    Encrypts plaintext using a Vigenere cipher.

    >>> encrypt_vigenere("PYTHON", "A")
    'PYTHON'
    >>> encrypt_vigenere("python", "a")
    'python'
    >>> encrypt_vigenere("ATTACKATDAWN", "LEMON")
    'LXFOPVEFRNHR'
    """
    ciphertext = ""
    # PUT YOUR CODE HERE
    return ciphertext


def decrypt_vigenere(ciphertext: str, keyword: str) -> str:
    """
    Decrypts a ciphertext using a Vigenere cipher.

    >>> decrypt_vigenere("PYTHON", "A")
    'PYTHON'
    >>> decrypt_vigenere("python", "a")
    'python'
    >>> decrypt_vigenere("LXFOPVEFRNHR", "LEMON")
    'ATTACKATDAWN'
    """
    plaintext = ""
    # PUT YOUR CODE HERE
    return plaintext

Note

Обратите внимание, что символы A и a в ключе не оказывают никакого влияния на шифруемое сообщение. Если же в качестве ключа мы будем использовать C или c, то получим шифр Цезаря.

По окончании работы над каждой функцией не забудьте запустить тесты и сделать соответствующие коммиты, как в примере с шифром Цезаря.

RSA шифрование

Одним из современных методов шифрования является алгоритм шифрования RSA, названный так по первым буквам фамилий его авторов (Rivest, Shamir и Adleman).

Мы не будем вдаваться в подробности работы этого алгоритма, но следующего объяснения должно быть достаточно для понимания принципов шифрования с открытым ключом:

Quote

Show your kid a padlock. This is a kind of lock that locks when you click it (i.e it doesn’t require a key) but requires the key to open the lock.

So, I can send these padlocks to all my friends who want to communicate with me. I will send them only the lock but will keep the key with me.

My friends can write me messages, put it in a box, lock it with my padlock (by clicking it) and send it to me, even over high risk networks. If the box is intercepted, it’s contents will not be compromised since I still have the key with me.

When the box reaches me, I can open my padlock with my key and read the contents. This way, I can send padlocks (public keys) to people outside which they can use to lock boxes (encrypt messages) without being in danger of the contents being compromised as the padlock key (the private key) is always with me and never exchanged over the network.

Работу алгоритма можно разбить на три шага:

1. Генерация ключей
2. Шифрование
3. Расшифровка

От вас в этом задании требуется выполнить только шаг генерации ключей, остальные два шага уже представлены в шаблоне работы.

На этапе генерации создаётся два ключа: открытый (public key, с помощью которого кто угодно может зашифровать сообщение и отправить его нам) и закрытый (private key, с помощью которого мы будем расшифровать полученные сообщения). Для генерации пары ключей необходимо выбрать два простых числа p и q. Мы предоставим пользователю возможность выбирать эти числа. От вас требуется написать тело функции is_prime(n), которая проверяет число на простоту:

def is_prime(n: int) -> bool:
    """
    >>> is_prime(2)
    True
    >>> is_prime(11)
    True
    >>> is_prime(8)
    False
    """
    # PUT YOUR CODE HERE
    pass

Если вы закончили работу над функцией is_prime(n), то запустите тесты и сделайте коммит:

(cs102) $ git commit -am "Реализована функция is_prime(n)"

Info

Для фиксации изменений мы использовали команду git commit -am, которая является аналогом последовательности команд git add . и git commit -m.

После того как были выбраны два простых числа требуется найти их произведение n = p * q:

def generate_keypair(p: int, q: int) -> Tuple[Tuple[int, int], Tuple[int, int]]:
    if not (is_prime(p) and is_prime(q)):
        raise ValueError('Both numbers must be prime.')
    elif p == q:
        raise ValueError('p and q cannot be equal')

    # n = pq
    # PUT YOUR CODE HERE

    # phi = (p-1)(q-1)
    # PUT YOUR CODE HERE

    # Choose an integer e such that e and phi(n) are coprime
    e = random.randrange(1, phi)

    # Use Euclid's Algorithm to verify that e and phi(n) are comprime
    g = gcd(e, phi)
    while g != 1:
        e = random.randrange(1, phi)
        g = gcd(e, phi)

    # Use Extended Euclid's Algorithm to generate the private key
    d = multiplicative_inverse(e, phi)
    # Return public and private keypair
    # Public key is (e, n) and private key is (d, n)
    return ((e, n), (d, n))

Затем вычисляется функция Эйлера по формуе:

Далее выбирается число e, отвечающее следующим критериям:

• e — простое;
• e < phi;
• e взаимно простое с phi.

Определить, являются ли числа взаимно простыми можно с помощью алгоритма Евклида. Для этого необходимо вычислить наибольший общий делитель (НОД) и проверить равен ли он единице. На этом этапе вашей задачей является реализация данного алгоритма:

def gcd(a: int, b: int) -> int:
    """
    >>> gcd(12, 15)
    3
    >>> gcd(3, 7)
    1
    """
    # PUT YOUR CODE HERE
    pass

Не забудьте зафиксировать реализацию функции gcd(a, b):

(cs102) $ git commit -am "Реализована функция поиска НОД"

Заключительным этапом на шаге генерации ключей является вычисление d такого что d * e mod phi = 1. Для его вычисления используется расширенный (обобщенный) алгоритм Евклида (см. стр. 23 этого учебного пособия с подробными объяснениями).

def multiplicative_inverse(e: int, phi: int) -> int:
    """
    >>> multiplicative_inverse(7, 40)
    23
    """
    # PUT YOUR CODE HERE
    pass

Таким образом, полученные пары (e,n) и (d,n) являются открытым и закрытым ключами соответственно.

Снова запустите тесты и зафиксируйте изменения:

(cs102) git commit -am "Реализованы функции multiplicative_inverse() и generate_keypair()"

После выполнения всех заданий

После выполнения всех заданий отправьте изменения на сервер:

(cs102) $ git push origin homework01

Затем создайте пул-реквест либо с поммощью веб-формы, либо с помощью gh, как это было описано в предыдущей работе. Не забудьте проверить, что нет ошибок при выполнении шагов на вкладке Checks. Сообщите Коннору, что вы готовы к код ревью:

Если ваш пул-реквест был одобрен, то примените изменения к мастер-ветке (Merge pull request), удалите ветку homework01 как в репозитории так и локально:

(cs102) $ git checkout master
(cs102) $ git branch -d homework01

Наконец получите изменения для локальной мастер-ветки с сервера:

---

Последнее обновление: 25 октября 2020 г.