@ch3sh1r blogs.

Класс Text

2012-03-11T00:00:00+00:00

Вы видите перед собой вольный перевод курса за авторством Jeffrey Dege. Это значит, что все права на текст принадлежат автору, а в ошибках, скорее всего, стоит винить переводчика.

Содержание

Введение
Python
Криптография
Класс Text
Класс Encryption
Криптоанализ I - Ряд Цифр
Криптоанализ II - Хитрость
Криптоанализ III - Точность
Создание программ

Программировать будем от конца к началу, то есть с целью сломать Monome-Dinome мы сначала напишем программу для шифрования открытого текста. Затем напишем программу для расшифрования по известному ключу.

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

И только завершив с шифровкой/расшифровкой, мы приступим к методам идентификации номеров строк и перевода шифротекста к легко взламываему виду.

Первый объект

Наконец-то мы переходим от разглагольствований к программированию. Для начала нам понадобится кусочек открытого текста, например вот такой: “As soon as we started programming, we found to our surprise that it wasn’t as easy to get programs right as we had thought. Debugging had to be discovered. I can remember the exact instant when I realized that a large part of my life from then on was going to be spent in finding mistakes in my own programs.” Maurice Wilkes, конструктор EDSAC, 1949.

Запускайте свой интерпретатор и присвойте переменной plaintext эту цитату:

Python 2.4.3 (#1, Jan 21 2009, 01:10:13) 
[GCC 4.1.2 20071124 (Red Hat 4.1.2-42)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> plaintext = '''As soon as we started programming, we found to our surprise that it wasn't
as easy to get programs right as we had thought.  Debugging had to be
discovered.  I can remember the exact instant when I realized that a large
part of my life from then on was going to be spent in finding mistakes in
my own programs.'''
>>> print plaintext
As soon as we started programming, we found to our surprise that it wasn't
as easy to get programs right as we had thought.  Debugging had to be
discovered.  I can remember the exact instant when I realized that a large
part of my life from then on was going to be spent in finding mistakes in
my own programs.
>>>

Маленькое отступление. Автор и далее с успехом продолжает использовать интерпретатор напрямую. Мы же, как дети более светлого времени, воспользуемся достижениями мысли человеческой. А именно, перейдем на использование замены стандартного Python shell’а — iPython. На повествование это никак не повлияет, но даст нам всякие фишки вроде доступной истории команд и автокомплита по коду (а при желании и многие другие). Итак,

>> ipython
Python 2.7.2+ (default, Oct  4 2011, 20:03:08) 
Type "copyright", "credits" or "license" for more information.

IPython 0.10.2 -- An enhanced Interactive Python.
?         -> Introduction and overview of IPython's features.
%quickref -> Quick reference.
help      -> Python's own help system.
object?   -> Details about 'object'. ?object also works, ?? prints more.

In [1]: plaintext = '''As soon as we started programming, we found to our surprise that it wasn't
   ...:     as easy to get programs right as we had thought.  Debugging had to be
   ...:     discovered.  I can remember the exact instant when I realized that a large
   ...:     part of my life from then on was going to be spent in finding mistakes in
   ...:     my own programs.'''

In [2]: print plaintext
As soon as we started programming, we found to our surprise that it wasn't
    as easy to get programs right as we had thought.  Debugging had to be
    discovered.  I can remember the exact instant when I realized that a large
    part of my life from then on was going to be spent in finding mistakes in
    my own programs.

Как и в большинстве других языков программирования, в Python кавычки использованы для объявления строк. Но есть один нюанс — кавычки бывают двух типов. Тройные кавычки (''' и """) используются для строк, содержащих символ новой строки \n.

Так вот, наш открытый текст содержится в объекте строкового типа с именем plaintext. Теперь можно работать с этой строкой средствами Python, например привести к верхнему регистру или посчитать длину:

In [3]: print plaintext.upper()
AS SOON AS WE STARTED PROGRAMMING, WE FOUND TO OUR SURPRISE THAT IT WASN'T
    AS EASY TO GET PROGRAMS RIGHT AS WE HAD THOUGHT.  DEBUGGING HAD TO BE
    DISCOVERED.  I CAN REMEMBER THE EXACT INSTANT WHEN I REALIZED THAT A LARGE
    PART OF MY LIFE FROM THEN ON WAS GOING TO BE SPENT IN FINDING MISTAKES IN
    MY OWN PROGRAMS.

In [4]: len(plaintext)
Out[4]: 326

Это конечно хорошо, но наш plaintext не является строкой в интуитивном смысле. Разумеется в скором времени мы будем оперировать им как строкой, но сейчас необходима другая абстракция, способная вместить операции не принадлежащие к классу строковых. Попробуем определить класс Text, в который наша “нестрока” будет вписываться.

Обратите внимание — класс назван Text а не Plaintext, о котором идет речь. Это осмысленное действие — на данном этапе нет причин разделять эти понятия. А привлечение новых сущностей без необходимости часто приводит к серьезным ошибкам.

Итак, наш первый класс:

In [5]: class Text:
   ...:     def __init__(self, text):
   ...:         self.text = text
   ...:         
   ...:         

In [6]: pt = Text(plaintext)

In [7]: pt
Out[7]: <__main__.Text instance at 0x98a29ac>

In [8]: print pt.text
As soon as we started programming, we found to our surprise that it wasn't
    as easy to get programs right as we had thought.  Debugging had to be
    discovered.  I can remember the exact instant when I realized that a large
    part of my life from then on was going to be spent in finding mistakes in
    my own programs.

Класс — это контейнер для данных и методов работы с этими данными. Наш Text состоит из переменной text и метода __init__(). __init__() — кодовое слово языка Python, это функция выполняющаяся при инициализации объекта. То есть конструкция pt = Text(plaintext) присваивает переменной text класса pt значение переменной plaintext.

А нужна вся это объектная ориентированность для возможности на лету конструировать много объектов со схожими свойствами:

In [9]: pt2 = Text("Another text")

In [10]: pt2.text
Out[10]: 'Another text'

In [11]: print pt.text
As soon as we started programming, we found to our surprise that it wasn't
    as easy to get programs right as we had thought.  Debugging had to be
    discovered.  I can remember the exact instant when I realized that a large
    part of my life from then on was going to be spent in finding mistakes in
    part of my life from then on was going to be spent in finding mistakes in
    my own programs.

Но эти объекты существуют только в памяти интерпретатора и превратятся в историю сразу после выхода. Если же нам необходимо использовать их и в дальнейшем — стоит оформить их в модуль.

Первый модуль

Модуль — это текстовый файл, содержащий код Python. Большая часть этого файла — описание классов/функций, и лишь маленький кусочек — инструкции по работе с ними. Чтобы создать модуль, откроем любимый текстовый редактор и запишем следущее:

class Text:
    def __init__(self, text):
        self.text = text

Теперь сохраняем все это под именем crypto.py в той же директории из которой запускаем iPython. Отныне командой from crypto import * мы возвращаем все наши объекты к жизни:

In [1]: from crypto import *

In [2]: pt = Text("This is a text")

In [3]: print pt.text
This is a text

Осталось заметить, что такой метод импорта расходится с Дао Python, в котором пространства имен провозглашаются неплохой идеей (я вполне серьезен, попробуйте дать интерпретатору команду import this). Правильнее поступать так:

In [1]: import crypto

In [2]: pt = crypto.Text("This is another text")

In [3]: print pt.text
This is another text

Загрузка из файла

Теперь нет необходимости перепечатывать определение нашего класса при каждом запуске интерпретатора. Хочется что-то похожее сделать и с открытым текстом. Было бы неплохо хранить его в файле и считывать при необходимости. Для претворения этого плана в жизнь файл crypto.py должен выглядеть как то так:

class Text:
    def __init__(self, filename):
        self.text = ""

    def load(self, filename):
        fp = open(filename)
        self.text = fp.read()
        fp.close

    def __str__(self):
        return self.text

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

Запишем исследуемую цитату в файл, назовем его plain.txt и опробуем на нем новый модуль:

In [4]: reload(crypto)
Out[4]: <module 'crypto' from 'crypto.pyc'>

In [5]: pt = crypto.Text("plain.txt")

In [6]: print pt
As soon as we started programming, we found to our surprise that it wasn't
as easy to get programs right as we had thought.  Debugging had to be
discovered.  I can remember the exact instant when I realized that a large
part of my life from then on was going to be spent in finding mistakes in
my own programs.

Форматирование вывода

Изучаемый открытый текст содержит символы, часть которых никак не меняется при шифровании. Пробелы, пунктуация, escape-символы нам не интересны — значит в процессе исследования их следует отбросить. Кое-какие методы работы со строками нам уже известны, так напишем же с их помощью функцию конвертирования текста в необходимую форму:

class Text:
    def __init__(self, filename):
        self.load(filename)

    def load(self, filename):
        fp = open(filename)
        self.rawtext = fp.read()
        fp.close
        self.text = self.convert(self.rawtext)

    def convert(self, txt):
        rval = ""
        for c in txt.upper():
            if c.isalpha():
                rval += c
        return rval

    def __str__(self):
        return self.text

Теперь метод __str__() возвращает все буквы из текста в верхнем регистре:

In [7]: reload(crypto)
Out[7]: <module 'crypto' from 'crypto.pyc'>

In [8]: pt = crypto.Text("plain.txt")

In [9]: print pt
ASSOONASWESTARTEDPROGRAMMINGWEFOUNDTOOURSURPRISETHATITWASNTASEASYTOGETPROGRAMSRIGHTASWEHADTHOUGHTDEBUGGINGHADTOBEDISCOVEREDICANREMEMBERTHEEXACTINSTANTWHENIREALIZEDTHATALARGEPARTOFMYLIFEFROMTHENONWASGOINGTOBESPENTINFINDINGMISTAKESINMYOWNPROGRAMS

С этим уже можно работать. Осталось только чуть-чуть подкорректировать вывод так, чтобы одновременно не мешало действиям алгоритма и не резало глаз человека. Пусть __str__() печатает группами по пять символов, по двенадцать групп в строку:

def __str__(self):
    rval = ""
    pos = 0
    for c in self.text:
        rval += c
        pos += 1
        if pos % 60 == 0:
            rval += '\n'
        elif pos % 5 == 0:
            rval += " "
    return rval

Компактно и внушает уважение наблюдателям.

In [10]: reload(crypto)
Out[10]: <module 'crypto' from 'crypto.pyc'>

In [11]: pt = crypto.Text("plain.txt")

In [12]: print pt
ASSOO NASWE START EDPRO GRAMM INGWE FOUND TOOUR SURPR ISETH ATITW ASNTA
SEASY TOGET PROGR AMSRI GHTAS WEHAD THOUG HTDEB UGGIN GHADT OBEDI SCOVE
REDIC ANREM EMBER THEEX ACTIN STANT WHENI REALI ZEDTH ATALA RGEPA RTOFM
YLIFE FROMT HENON WASGO INGTO BESPE NTINF INDIN GMIST AKESI NMYOW NPROG
RAMS

Первая программа

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

Такое можно проделать и с нашим crypto.py, правда он пока не способен на внятные самостоятельные действия. По вызову он просто создает описанные классы и отключается. Вроде бы осталось только описать необходимые действия, но тогда они будут выполняться каждый раз как мы импортируем программу в качестве модуля. Чтобы такого не происходило, введем в использование еще парочку кодовых слов Python:

if __name__ == "__main__":
    txt = Text('plain.txt')
    txt.load('plain.txt')
    print txt

Переменная __main__ принимает значение "__name__" только когда файл исполняется интерпретатором. Это и позволяет использовать написанные программы как библиотеки а библиотеки как программы.

>> python crypto.py
ASSOO NASWE START EDPRO GRAMM INGWE FOUND TOOUR SURPR ISETH ATITW ASNTA
SEASY TOGET PROGR AMSRI GHTAS WEHAD THOUG HTDEB UGGIN GHADT OBEDI SCOVE
REDIC ANREM EMBER THEEX ACTIN STANT WHENI REALI ZEDTH ATALA RGEPA RTOFM
YLIFE FROMT HENON WASGO INGTO BESPE NTINF INDIN GMIST AKESI NMYOW NPROG
RAMS
>>

И добавим очевидное — пусть имя обрабатываемого файла передается как параметр:

#!/usr/bin/env python
import sys

#...тут все без изменений...

if __name__ == "__main__":
    if len(sys.argv) == 2:
        txt = Text(sys.argv[1])
    else:
        print "Usage: crypto.py <filename>"
        sys.exit(1)
    print txt

Итак, всего два нововведения. Во-первых, мы добавили юниксовый “shebang” комментарий, который и позволяет в Unix запускать программу не передавая ее интерпретатору напрямую. Для Windows это не обязательно. Там решающим фактором становится расширение, и файл оканчивающийся на .py будет автоматически передан интерпретатору.

Во-вторых, импортирован модуль sys. Это стандартный модуль который поставляется с каждой установкой Python. Он содержит функции и переменные для создания интерфейса по работе с операционной системой. В нашем случае, он использован для получения аргументов командной строки при запуске нашей программы и для выхода при получении незапланированных аргументов. Переменная sys.argv указывает на массив строк, нулевой элемент которого — имя запущенной программы, а первый содержит единственный в нашем случае аргумент.

>> python ./crypto.py
Usage: crypto.py <filename>
>> python crypto.py plain.txt 
ASSOO NASWE START EDPRO GRAMM INGWE FOUND TOOUR SURPR ISETH ATITW ASNTA
SEASY TOGET PROGR AMSRI GHTAS WEHAD THOUG HTDEB UGGIN GHADT OBEDI SCOVE
REDIC ANREM EMBER THEEX ACTIN STANT WHENI REALI ZEDTH ATALA RGEPA RTOFM
YLIFE FROMT HENON WASGO INGTO BESPE NTINF INDIN GMIST AKESI NMYOW NPROG
RAMS
>>

Криптография

2012-03-10T00:00:00+00:00

Вы видите перед собой вольный перевод курса за авторством Jeffrey Dege. Это значит, что все права на текст принадлежат автору, а в ошибках, скорее всего, стоит винить переводчика.

Содержание

Введение
Python
Криптография
Класс Text
Класс Encryption
Криптоанализ I - Ряд Цифр
Криптоанализ II - Хитрость
Криптоанализ III - Точность
Создание программ

Предполагается, что вы и без этого курса понимаете основы и ориентируетесь в терминологии криптографии. Например, знаете о частотном анализе и понимаете метод его применения для взлома шифра простой подстановки. Если таких знаний нет — стоит сначала почитать что-нибудь из перечисленного в следующем параграфе.

Литература

В сети не так много обучающих крптографии материалов хорошего качества, как для Python:

Cryptanalyzing the Simple Substitution Cipher, из John Savard “A Cryptographic Compendium”
Cracking The Substitution Cipher, из Simon Singh “The Code Book”
Lecture 1, из Lanaki Classical Cryptography Course

Для начинающих программистов Mike Cowan написал курс по использованию Python в криптографических целях:

Learning to program in python for novice programmers and cipher enthusiasts.

Если вы никогда ранее не программировали, то этот курс — неплохой повод начать. Он (в смысле курс) начинает с введения простейших понятий языков программирования, а в конце приводит к созданию программы для решения многих шифров простой подстановки. И, под конец, упомянем несколько готовых решений для анализа шифров подстановки:

Шифр Monome-Dinome

Для демонстрации криптоаналитических способностей Python нам потребуется шифр. Будем использовать Monome-Dinome от Американской Ассоциации Криптограмм (или American Cryptogram Association, далее по тексту ACA). Это такой шифры, в которых знак исходного текста иногда заменяются знаком, а иногда парой знаков (то есть замена моно- и биграммами). Самым знаменитым в этом классе является Straddling Checkerboard. Основная идея состоит в попытке скрыть информацию о частоте с целью усложнить взлом. Ни один из таких шифров нельзя назвать сильным, а Monome-Dinome к тому же содержит в себе уязвимость, которая позволяет взломать его довольно просто .

Ключом является перемешанный алфавит, записанный в матрицу 3х8, столбцы
которой нумеруются случайным образом восемью однозначными числами, два оставшихся числа приписываются двум последним строкам. Первая строка остается ненумерованной. Пример:

. 6 2 7 0 4 8 3 9
. P B N E C O R D
5 Q I F U S G V T
1 H X A K Y L M Z

Процесс шифрования прост. Каждая буква открытого текста располагается где-то в таблице. Если она в первой строке — заменяем ее номером столбца. Если нет — заменяем парой (номер столбца, номер строки).

Тогда, в нашем примере буква P шифруется как 6, а буква Q как 56. Текст ATTACK AT DAWN превратится в 17 59 59 17 4 10 17 59 9 17 53 7, или в 17595 91741 01759 91753 7, если записать группами из 5 цифр. Заметьте, что буква W воспринимается как синоним к V и шифруется как 53.

Плюс такой замены в размытой связи между открытым текстом и шифротекстом. По цифре в шифротексте невозможно определить — является ли она букву или входит в пару с правой или левой цифрой. А очевидная слабость Monome-Dinome от ACA в том, что цифры из номера строки никогда не появятся в номере столбца, и наоборот. Это создает легко узнаваемые статистические шаблоны. А обнаружение подобного шаблона однозначно ведет к компроментации шифротекста. Другие шифры с подобным методом замены, в том числе и Straddling Chessboard, лишены этого недостатка. Например, в такой:

. 6 2 7 5 0 4 8 1 3 9
. P B N . E C O . R D
5 Q F J U S G V T I W
1 H X A K Y L M Z . .

решетке цифры 1 и 5 встречаются как в номерах строк, так и в номерах столбцов. И при этом они не могут появиться в одиночку, всегда участвуя в паре.

Приобретя дополнительную сложность, в сердцевине шифр Monome-Dinome является обычным шифром простой подстановки. Но как только взломщик узнает о природе этой дополнительной сложности, он без труда сможет свести задачу взлома Monome-Dinome к задаче взлома простой подстановки, которую достаточно просто решить. Эта техника — отбрасывание слоев сложности до сведения к простой абстракции — является основой для большого числа методов криптоанализа более сложных шифров. А шифр Monome-Dinome от ACA — легкая мишень для такой методики, из-за чего он и выбран в качестве примера.

Python

2012-03-05T00:00:00+00:00

Вы видите перед собой вольный перевод курса за авторством Jeffrey Dege. Это значит, что все права на текст принадлежат автору, а в ошибках, скорее всего, стоит винить переводчика.

Содержание

Введение
Python
Криптография
Класс Text
Класс Encryption
Криптоанализ I - Ряд Цифр
Криптоанализ II - Хитрость
Криптоанализ III - Точность
Создание программ

Python — скриптовый язык. На практике, это во-первых значит что он интерпретируем Во-вторых что язык заточен для быстрой автоматизации “бытовых” программистских задач. История Unix пестрит такими языками: от Bourne Shell к AWK и затем к PERL или TCL. Есть сикриптовые языки и на других платформах: JCL и REXX для мейнфреймах IBM, AppleScript на Macintosh, PowerShell на Windows и другие.

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

Литература

Повторюсь, этот курс не концентрируется на базовых основах языка Python. Если вы не знакомы с этим языком, стоит посмотреть специальные курсы, многие из которых доступны в сети. Jeffrey советует такие:

Swaroop C H “A Byte of Python”
Allen B. Downey “Think Python, How to think like a Computer Scientist”

От себя добавлю “Dive into Python”, частично переведенный на русский и “Язык программирования Python”, в создании которого участвовал Гвидо ван Россум, создатель языка.

Три способа запуска кода

Напечатать в интерпретаторе
Сохранить в файл и передать интерпретатору
Сохранить в файл и вызвать сохраненное из другой программы

Первый способ — могучая способность Python’а и многих других интерпретируемых языков. В миру это приятная возможность выдрать кусок кода и рассмотреть под лупой как он работает (или не работает, да).

Второй очевиден — как только мы добились от кода необходимых результатов, мы его сохраняем и затем запускаем раз за разом.

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

Большинство компилируемых языков предлагают последние два способа и ни один первый (это можно смело утверждать, не смотря на техническую возможность некоторых IDE для компилируемых языков отлаживать код по кускам). Большинство же интерпретируемых языков умеют только первые два, и лишь некоторые третий. Python покрывает все три и в довесок позволяет использовать сохраненный код не только как приложение или библиотеку, но и вызвать его из интерпретатора. Что, кстати, мы и будем заниматься в этом курсе.

Введение

2012-03-02T00:00:00+00:00

Вы видите перед собой вольный перевод курса за авторством Jeffrey Dege. Это значит, что все права на текст принадлежат автору, а в ошибках, скорее всего, стоит винить переводчика.

Содержание

Введение
Python
Криптография
Класс Text
Класс Encryption
Криптоанализ I - Ряд Цифр
Криптоанализ II - Хитрость
Криптоанализ III - Точность
Создание программ

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

(y/n) Ничего не слышали о программировании
(y/n) В первый раз видите слова язык программирования и Python в одном словосочетании
(y/n) Никогда не пробовали взломать шифр простой подстановки

Если что-то из этого подходит под ваше описание — стоит попробовать почитать другие работы, подробно освещающие эти вопросы. С другой стороны, если вы уже читали что-то подобное, с помощью Питона способны вывести на экран Hello world и любой другой наборы символов, подобрали пару подстановок — возможно здесь найдется что-нибудь интересное.

Базовая идея курса состоит в том, что создание программ-кирпичиков для решения собственных задач и программирование для решения задач чужих — две большие разницы. Если зайти издалека, задача Серьезного Программиста — создание бензопилы достаточно безопасной для семилетнего ребенка и одновременно пригодной для решения повседневных задач сурового лесоруба.

Говорят, существует такая околоюниксовая поговорка: «Единственная необходимая ошибка — сегфолт» (имеется в виду Segmentation fault: core dumped). Такой способ обработки ошибок отрицательно влияет на психику и моральное состояние пользователей, что, с одной стороны, довольно забавно, но и обременительно с другой. Создание интуитивного интерфейса и вытекающая из этого проблема качественной обработки ошибок — задачи подчас более сложные чем описание алгоритма программы. Очевидно и гибкость итогового продукта страдает от такого подхода.

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

Пару десятков лет назад, когда большинство пользователей были программистами, книги компьютерной тематики писались именно с уклоном в эту сторону. Unix придуман и воплощен как средство повышения продуктивности программистов. Серьезные труды по исследованию подобных концепций написаны командой исследователей из Bell Labs, создателей упомянутого unix’а:

The Unix Programming Environment (Brian W. Kernighan and Rob Pike. Prentice Hall, Inc., 1984.)
Software Tools (Brian W. Kernighan amd P. J. Plauger, Addison-Wesley, 1976.)
Programming Pearls (Jon Bentley, Addison-Wesley, 1986.)

Да и после этого не мало копий сломано в дискуссиях. А программирование тем временем стало массовой сферой, сконцентрировавшейся на написании приложений для пользователей.