Атака на многоалфавитный шифр простой замены

#криптография #дискретная_математика #криптоаналитика

Как расшифровать текст, зашифрованный с использованием многоалфавитного шифра простой
замены? Вкратце о том что это за шифр: ключ состоит из n алфавитов, каждая i-ая буква
открытого текста заменяется по (i-1)%keyLenght + 1 алфавиту. Шифр по сути представляет
из себя обобщенный шифр Виженера.
Длину ключа я определил. А вот как теперь подобрать ключ я не знаю.
    

Ответы

Ответ 1

Я пока не нашел полного решения, но нащупал некое направление, по которому можно
пробовать идти. И так, с начала определяем длину ключа например по методу, предложенному
автором вопроса (@Asem) в комментариях, т.е. методом индекса совпадений

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

0: t=>14.268, h=>9.348, d=>8.364, u=>8.364, l=>8.364, s=>7.38, j=>6.396, a=>4.92,
z=>4.428, x=>3.936, e=>3.444, r=>2.952, k=>2.952, w=>2.46, y=>2.46, m=>2.46, c=>2.46,
n=>1.968, p=>1.476, f=>0.492, i=>0.492, b=>0.492, o=>0.492,
1: s=>13.776, a=>8.364, n=>8.364, j=>7.38, g=>7.38, t=>7.38, y=>6.888, h=>6.396,
p=>4.92, k=>4.428, v=>4.428, e=>3.444, q=>3.444, i=>2.952, c=>2.46, w=>1.968, f=>1.476,
m=>1.476, l=>0.984, z=>0.984, o=>0.984,
2: t=>12.3,   n=>10.332, c=>9.84, w=>9.348, q=>7.872, k=>6.396, y=>5.904, a=>4.428,
h=>4.428, v=>4.428, s=>4.428, f=>3.936, r=>2.952, l=>2.952, x=>2.46, g=>1.968, m=>1.968,
j=>1.476, b=>0.984, d=>0.492, i=>0.492, p=>0.492,
3: t=>9.84,   m=>9.348, g=>8.856, p=>8.364, q=>8.364, i=>7.872, r=>6.396, k=>6.396,
x=>4.428, s=>4.428, f=>3.444, z=>3.444, j=>2.952, n=>2.952, w=>2.46, e=>2.46, c=>2.46,
d=>1.968, l=>1.476, u=>0.984, v=>0.492, o=>0.492,


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

     Минимум      Максимум         Минимум 4    Максимум 4
  A: 4.545        11.916        A: 0.982        16.216
  B: 0.368        4.176         B: 0.491        5.405
  C: 0.614        5.651         C: 0.491        8.353
  D: 1.474        7.739         D: 0.491        11.302
  E: 6.756        16.461        E: 5.405        21.621
  F: 0.368        4.545         F: 0.491        6.879
  G: 0.491        4.668         G: 0.491        5.896
  H: 1.719        10.319        H: 0.491        13.267
  I: 3.316        9.828         I: 1.474        13.759
  J: 0.122        1.228         J: 0.491        1.965
  K: 0.122        3.439         K: 0.491        4.422
  L: 1.105        7.739         L: 0.491        9.828
  M: 0.737        5.159         M: 0.491        8.353
  N: 3.808        10.81         N: 1.965        12.285
  O: 4.299        12.407        O: 2.457        15.724
  P: 0.122        5.282         P: 0.491        5.405
  Q: 0.122        1.474         Q: 0.491        1.474
  R: 2.702        8.845         R: 1.474        12.776
  S: 3.194        10.073        S: 0.982        12.285
  T: 4.299        13.022        T: 0.982        16.216
  U: 0.737        6.019         U: 0.491        8.845
  V: 0.122        3.316         V: 0.491        3.931
  W: 0.491        5.282         W: 0.491        7.371
  X: 0.122        1.105         X: 0.491        2.457
  Y: 0.245        6.388         Y: 0.491        7.371
  Z: 0.122        1.597         Z: 0.491        1.965


В колонках "Минимум/Максимум 4" я посчитал частоты, если брать каждую 4ю букву блока.
К сожалению они имеют еще большие отклонения от реальности и в некоторых случаях возможно
придется ориентироваться на них.

Далее подстановкой самых частых по нашему разумению букв замечаем места в шифротексте,
где близко расположено несколько букв с повторами. А так же повторяющиеся комбинации
символов. Для выбранного участка готовим регулярное выражение, которое учитывает во
первых повтор букв, во вторых на месте букв перечисляем класс символов из всех букв,
которые могли бы подойти по частоте. Например буква t из третьего (последнего, при
нумерации с 0) словаря, с частотой 9.84 может быть представлена [ETAONIHS]. Таким образом
для участка шифротекста tzzstmtgtmt (первая буква в позиции 2го словаря) у меня получилась
следующая регулярка (в ней нарочно оставлены маленькие буквы шифротекста, что бы можно
было быстро увидеть правильность выбора участка). Большими буквами обозначаем ожидаемые
символы в открытом тексте, так потом удобнее для замены.

(?[tETAO])
[zONIHSRDLUWCMGFYPBK]
(?[zTAONIHSRDLUWCMGFYPBK])
(?[sET])
\g{t2}
(?[mETAONIHS])
(?[tE])
[gTAONIHSRDL]
\g{t2}
\g{m3}
\g{t0}


Имена групп захвата и соответствующие ссылки идут по букве шифротекста и номеру словаря.
К сожалению регулярка упрощенная и не контролирует, что одна буква алфавита в пределах
одного словаря, соответствует строго одной букве словаря. Этот контроль я реализовывал
позже в скрипте. Прогоняем полученную регулярку по реальному тексту большого объема
(я использовал 2Mb склеенных в один текст только из букв английских рассказов) и находим
попадающие под нее места:

TBUTTHENTHE
THATTHEOTHE
TIMETHENTHE
TOGETHERTHE
TSATTHEOTHE
TWHETHERTHE


Собственно когда я писал эту регулярку я как раз хотел понять, на сколько жизнеспособна
моя идея расшифровки tmt как THE. Просто эта комбинация с одной стороны часто встречалась,
с другой, в данном месте два раза THE стоят слишком близко и мне было интересно на
сколько это реально. Далее по шифротексту есть еще одно место с нагромождением тех
же букв, его я проверял скрипте по другой регулярке с подстановкой букв найденных первой.
В итоге для второй точки нашлись предположения только для случая если в первом случае
была комбинация TWHETHERTHE. Если бы набор текстов был больше, возможно нашлось бы
что то еще.

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

Минимизация булевых функций (получение МДНФ)

#cpp #алгоритм #дискретная_математика #булева_алгебра

Ещё в прошлом году у меня был курс дискретной математики, и с её основами я знаком.
Мне бы хотелось, что бы вы помогли мне с написанием алгоритма получения ДНФ, и объяснения
того, как из ДНФ перейти в МДНФ. 

Я ищу любой пример реализации этой задачи, не обязательно на C++. Главное, что бы
был понятен алгоритм получения ДНФ и МДНФ. Было бы здорово, если бы вы развёрнуто прокомментировали
алгоритм (что на входе, что на выходе, и т.д.).

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

Ответы

Ответ 1

Посмотрите вот этот проект. Если ссылка со временем окажется битой - гуглите 
Quine-McCluskey minimizer.

Задача о триангуляции многоугольника

#алгоритм #pascal #freepascal #дискретная_математика

Задан многоугольник координатами своих вершин вдоль обхода его контура. Требуется
указать множество непересекающихся во внутренних точках диагоналей, разбивающих многоугольник
на треугольники.
Вход: файл input.txt, , в первой строке которого записано число N – количество вершин
многоугольника, потом в N строках пары целых чисел – координат вершин многоугольника
в порядке обхода контура.
Ограничения: 4 ≤ N ≤ 200; каждая координата от -10000 до 10000.
Выход: файл output.txt, в первой строке которого должно быть число k, указывающее
необходимое число диагоналей. В последующих k строках должно быть по два натуральных
числа – номер начальной и конечной вершины соответствующей диагонали.
Дополнительные ограничения: диагонали должны лежать строго внутри многоугольника
(все точки диагонали, за исключением концов, являются внутренними точками многоугольника).

Пример:
input.txt 
5
1 1
2 5
5 5
5 1
2 2

output.txt
2
2 5
3 5


Мое решение: 


Количество диагоналей равно (количество вершин - 3)


Соединяем все точки от (2) до (количество вершин - 2) с последней точкой; если прямая
между соединяемой и последней точкой лежит вне многоугольника (многоугольник невыпуклый),
то берем следующую точку и соединяем
 ее с некоторыми (какими?) точками.


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

Ответы

Ответ 1

Если число вершин <= 3 разбиение закончено
Выбраем первую вершину как текущую (N)
Если из неё нельзя провести диагональ внутри многоугольника к точке N+2, то теущей
становится следующая и т.д. по кольцу. Думаю можно доказать, что этот цикл не бесконечен. 
"Отрезаем" треугольник от многоугольника, вершин становится на одну меньше за счёт
исключения вершины N+1.
Переходим к пункту 1


Наверно удобно использовать связный список.

Определение проходит ли диагональ внутри многоугольника.

Заранее определим в каком направлении задан многоугольник - по или против часовой
стрелки. Далее если треугольник N N+1 N+2 обходится в противоположном направлении,
значит наша диагональ снаружи - не подходит.
В противном случае возможен ещё вариант когда диагональ оказывается снаружи полностью
или частично по вине других внутренних углов, это проверяется далее.

Для точек N+3 и N-1 нужно проверить, чтобы эти углы при этих вершинах были больше
чем соответствующие углы отрезаемого треугольника. Т.е. вершина лежит по другую сторону
от диагонали относительно вершины N+1, либо угол при вершине больше развёрнутого. (См.
на картинке для вершины 2 угол 2-3-1 больше чем 2-3-4, или 4 и 2 находятся по одну
сторону от диагонали 3-1, поэтому диагональ 3-1 не подходит. Для вершины 8 она с вершиной
6 по одну сторону диагонали 7-1, но угол 7 больше развёрнутого, поэтому это не мешает,
вершина подходит.)

Для оставшихся сторон нужно проверить не пересекают ли они данную диагональ. (Например
на рисунке сторона 6-7 пересекает диагональ 4-2. Точка пересечения прямых принадлежит
отрезку.) Тут четыре стороны проверять не нужно: это стороны при вершине и соседние к ним.

Определение направления обхода многоугольника

Проводим из одной вершины A1 вектора ко всем остальным A1->A2, A1->A3, ... A1->AN.
Считаем сумму N-1 векторных произведений соседних векторов по порядку, нас интереует
только координата z. Эта сумма по модулю равна удвоенной площади фигуры, а знак указывает
направление обхода.

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

Иллюстрация к случаям рассмотренным в алгоритме.


Ответ 2

Классический алгоритм решения этой задачи заключается в выполнении двух этапов


Декомпозиция исходного многоугольника на монотонные многоугольники. Эта задача аккуратно
решается алгоритмом сканирующей прямой.
Триангуляция каждого монотонного многоугольника. Это делается несложным алгоритмом
триангуляции.


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

Задача о триангуляции многоугольника

Задан многоугольник координатами своих вершин вдоль обхода его контура. Требуется указать множество непересекающихся во внутренних точках диагоналей, разбивающих многоугольник на треугольники. Вход: файл input.txt, , в первой строке которого записано число N – количество вершин многоугольника, потом в N строках пары целых чисел – координат вершин многоугольника в порядке обхода контура. Ограничения: 4 ≤ N ≤ 200; каждая координата от -10000 до 10000 Выход: файл output.txt, в первой строке которого должно быть число k, указывающее необходимое число диагоналей. В последующих k строках должно быть по два натуральных числа – номер начальной и конечной вершины соответствующей диагонали. Дополнительные ограничения: диагонали должны лежать строго внутри многоугольника (все точки диагонали, за исключением концов, являются внутренними точками многоугольника). Пример: input.txt 5 1 1 2 5 5 5 5 1 2 2
output.txt 2 2 5 3 5 Мое решение: Количество диагоналей равно (количество вершин - 3) Соединяем все точки от (2) до (количество вершин - 2) с последней точкой; если прямая между соединяемой и последней точкой лежит вне многоугольника (многоугольник невыпуклый), то берем следующую точку и соединяем ее с некоторыми (какими?) точками. Помогите, пожалуйста, все это реализовать или подскажите, как проверить принадлежность прямой (или точки) многоугольнику и какие точки соединять, если многоугольник является невыпуклым.

Ответ

Если число вершин <= 3 разбиение закончено Выбраем первую вершину как текущую (N) Если из неё нельзя провести диагональ внутри многоугольника к точке N+2, то теущей становится следующая и т.д. по кольцу. Думаю можно доказать, что этот цикл не бесконечен. "Отрезаем" треугольник от многоугольника, вершин становится на одну меньше за счёт исключения вершины N+1. Переходим к пункту 1
Наверно удобно использовать связный список.
Определение проходит ли диагональ внутри многоугольника.
Заранее определим в каком направлении задан многоугольник - по или против часовой стрелки. Далее если треугольник N N+1 N+2 обходится в противоположном направлении, значит наша диагональ снаружи - не подходит. В противном случае возможен ещё вариант когда диагональ оказывается снаружи полностью или частично по вине других внутренних углов, это проверяется далее.
Для точек N+3 и N-1 нужно проверить, чтобы эти углы при этих вершинах были больше чем соответствующие углы отрезаемого треугольника. Т.е. вершина лежит по другую сторону от диагонали относительно вершины N+1, либо угол при вершине больше развёрнутого. (См. на картинке для вершины 2 угол 2-3-1 больше чем 2-3-4, или 4 и 2 находятся по одну сторону от диагонали 3-1, поэтому диагональ 3-1 не подходит. Для вершины 8 она с вершиной 6 по одну сторону диагонали 7-1, но угол 7 больше развёрнутого, поэтому это не мешает, вершина подходит.)
Для оставшихся сторон нужно проверить не пересекают ли они данную диагональ. (Например на рисунке сторона 6-7 пересекает диагональ 4-2. Точка пересечения прямых принадлежит отрезку.) Тут четыре стороны проверять не нужно: это стороны при вершине и соседние к ним.
Определение направления обхода многоугольника
Проводим из одной вершины A1 вектора ко всем остальным A1->A2, A1->A3, ... A1->AN. Считаем сумму N-1 векторных произведений соседних векторов по порядку, нас интереует только координата z. Эта сумма по модулю равна удвоенной площади фигуры, а знак указывает направление обхода.
Оптимизация от @AnT: Для того, чтобы определить направление обхода многоугольника достаточно вычислить векторное произведение сторон инцидентных с нижней-левой вершиной (минимальный x среди минимальных y). Делать это во всех вершинах (т.е. считать полную площадь) нет никакой необходимости.
Иллюстрация к случаям рассмотренным в алгоритме.