Доброго времени суток, дорогие читатели! Недавно вышла статья про реализацию шифра Цезаря и его взлом. В конце я пообещал, что буду реализовывать и другие шифры. И вот мой выбор пал на перестановочный шифр. Но появилась проблема, для взлома понадобился список запрещенных биграмм в английском языке. После упорного и безрезультатного поиска, я решил поступить, как настоящий программист и составить эту таблицу самостоятельно.
Идея такая: взять достаточно большой литературный текст на английском языке и вычленить из него все возможные биграммы, обязательно с пробелами. Сравнить их со списком всех биграмм языка и найти запрещенные, которые ни разу не встретились в литературном тексте. Для этой задачи я выбрал язык программирования Python, так как хотелось сделать быстро и не заморачиваться с эклипсом и прочими радостями компилируемых языков. Вот, что у меня получилось, поехали!
Анализируемый текст
Первое, что пришло в голову это взять библию в качестве исходного текста. Кажется, именно ее анализируют статисты всего мира. Однако я столкнулся со следующими проблемами: очень много сокращений и спецсимволов. Специальные символы программно убрать не составило труда, а вот с сокращениями возникла проблема, из-за них портится статистика биграм. Кроме того, текст получился обрезанный, много абзацев из одного символа и прочие радости.
Помучившись пару часов с библией, я решил взять текст одной из своих любимых книг. «Крестный отец» подошел отлично, достаточно объемный текст, без излишеств спецсимволов. И самое главное — это полностью художественный, литературный текст, восхитительный кандидат. Эта книга настолько мне нравится, что я вставил фото из одноименного фильма! Однажды я напишу свою рецензию на крестного отца, а сейчас самое время перейти к алгоритму.
Мой алгоритм поиска запрещенных биграмм
Поиск реализуется в три шага:
Первый шаг
Открываем файл с текстом и обрабатываем его: убираем цифры, все спецсимволы и знаки препинания. Я создаю новый файл, дабы не портить первоисточник, ведь я наверняка буду перечитывать его не один раз. Время работы напрямую зависит от размера текста, но в целом пробегаемся быстро. Больше времени уходит на перезапись файла.
Исходный код на python
#определяет, является ли символ спецсимволом def checkSymb(symb): badSymbols = ['”' ,'“', '*', ')', '(', '\t', '¶', '–', ',', '.', ':', ';', '`', '-', '!', '&', '?', '_', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'] for s in badSymbols: if symb == s: return True else: return False def processFile(fileName): file = open(fileName, 'r') text = [] for line in file: text.append(list(line.lower())) file.close() #Убрать все спец символы, кроме пробелов и перевода строки, и цифры for i in range(len(text)): for j in range(len(text[i])-1): if checkSymb(text[i][j]) == True: text[i][j] = '' newFileName = fileName + 'New' file = open(newFileName, 'w') for line in text: file.write(''.join(line)) file.close() return newFileName
Второй шаг
Открываем новый файл и бежим по всем строкам, забиваем массив всех встречающихся сочетаний двух символов, включая сочетания с пробелом. Именно ради них это программа была написана.
Исходный код на Python
def findAllBigrammsInFile(fileName): file = open(fileName, 'r') text = [] for line in file: text.append(list(line)) file.close() allBigrammsInText = [] for i in range(len(text)): for j in range(1, len(text[i])-1): allBigrammsInText.append(text[i][j-1] + text[i][j]) return allBigrammsInText
Третий шаг
Быстренько составляем список вообще всех биграмм латинского алфавита и сравниваем его со списком биграмм текста. Находим индексы биграмм, которые встречались в литературном тексте и методом исключения получаем те, которые ни разу не были встречены.
Исходный код на python
def getAllBigramms(): allBigramms = [] for num in range(ord('a'), ord('z')+1, 1): for secondNum in range(ord('a'), ord('z')+1, 1): allBigramms.append(chr(num) + chr(secondNum)) for num in range(ord('a'), ord('z')+1, 1): allBigramms.append(chr(num) + ' ') allBigramms.append(' ' + chr(num)) return allBigramms #------------------------------------ #MAIN newFileName = processFile('godfather') allBigrammsInText = findAllBigrammsInFile(newFileName) allBigramms = getAllBigramms() indexesOfGoodBigramms = [] for i in range(len(allBigramms)): for j in range(len(allBigrammsInText)): if allBigramms[i] == allBigrammsInText[j]: indexesOfGoodBigramms.append(i) break badBigramms = [] for i in range(len(allBigramms)): flag = True for j in range(len(indexesOfGoodBigramms)): if i == indexesOfGoodBigramms[j]: flag = False break if flag == True: badBigramms.append(allBigramms[i]) file = open('badBigramms', 'w') file.write(str(badBigramms)) file.close()
Список запрещенных биграмм
Вот, что у меня получилось при анализе текста «Крестный отец»:
['aa', 'bc', 'bf', 'bh', 'bk', 'bn', 'bp', 'bq', 'bw', 'bx', 'bz', 'cb', 'cf', 'cg', 'cj', 'cm', 'cv', 'cw', 'dx', 'dz', 'fk', 'fp', 'fq', 'fv', 'fx', 'fz', 'gb', 'gj', 'gk', 'gp', 'gq', 'gv', 'gx', 'gz', 'hg', 'hj', 'hk', 'hp', 'hq', 'hv', 'hx', 'hz', 'iw', 'jb', 'jc', 'jd', 'jf', 'jg', 'jh', 'jj', 'jk', 'jl', 'jm', 'jn', 'jp', 'jq', 'jr', 'js', 'jt', 'jv', 'jw', 'jx', 'jy', 'jz', 'kk', 'kq', 'kv', 'kx', 'kz', 'lj', 'lq', 'lx', 'lz', 'md', 'mj', 'mk', 'mq', 'mv', 'mw', 'mx', 'mz', 'pc', 'pf', 'pj', 'pq', 'pv', 'px', 'pz', 'qa', 'qb', 'qc', 'qd', 'qe', 'qf', 'qg', 'qh', 'qi', 'qj', 'qk', 'ql', 'qm', 'qn', 'qo', 'qp', 'qq', 'qr', 'qs', 'qt', 'qv', 'qw', 'qx', 'qy', 'qz', 'rj', 'rq', 'rx', 'sv', 'sx', 'sz', 'tj', 'tq', 'tv', 'tx', 'uj', 'uq', 'uu', 'uw', 'vb', 'vc', 'vd', 'vf', 'vg', 'vh', 'vj', 'vk', 'vl', 'vm', 'vn', 'vp', 'vq', 'vt', 'vv', 'vw', 'vx', 'vz', 'wq', 'wv', 'wx', 'wz', 'xd', 'xf', 'xg', 'xj', 'xk', 'xl', 'xn', 'xr', 'xs', 'xv', 'xx', 'xz', 'yj', 'yk', 'yq', 'yx', 'zb', 'zc', 'zd', 'zf', 'zh', 'zj', 'zk', 'zm', 'zn', 'zp', 'zq', 'zr', 'zs', 'zt', 'zv', 'zw', 'zx', 'q ']
Заключение
Чисто теоретически, получился список биграмм, которые не встречаются в литературном тексте. Для большей уверенности стоит взять несколько романов разных авторов и проанализировать их вместе. Да, это займет больше времени, но зато уверенности прибавится. Перед реализацией перестановочного шифра я так и сделаю.
Я готов приступать ко взлому перестановочного шифра. Это совсем не такая легкая задача, как мне показалось на первый взгляд. И большой минус в том, что я использую собственноручно составленный список запрещенных биграмм, он не дает совершенно никаких гарантий. Но не смотря на это, я все же попытаюсь, спасибо за внимание!