Playfair Hillclimbing трещины

Я пишу сценарий Python для взлома шифра playfair, только с зашифрованным текстом. Сначала я генерирую около 30-100 ключей дешифрования и запускаю их в зашифрованном виде, ранжируя каждый из них по частотам орграфа. К следующему "поколению" / итерации я копирую те, у которых лучший результат. Затем они видоизменяются (буквы меняются местами в сетке 5x5) и снова добавляются к следующей итерации, которая ранжируется снова, и так далее.

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

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

РЕДАКТИРОВАТЬ: образец зашифрованного текста в соответствии с запросом (ключ: пример playfair)

['p', 'l', 'a', 'y', 'f']
['i', 'r', 'e', 'x', 'm']
['b', 'c', 'd', 'g', 'h']
['k', 'n', 'o', 'q', 's']
['t', 'u', 'v', 'w', 'z']

как эль-уль-ви-не узк qk dm kz qe ca qe tb qc pv zb md nv om lo gv qo od er qc zg pv vk ov или iw zg ro nz ge ro af yp qe zi lo rk pr ad xl dl ix cl qr rk dq vu sa zb xv qe ho dm dn ok eb xe do bm iz kd de as kv ef kc rd lv om dm vy km ur et xe aq zb xe tx om rt gh rk hc fg mk py dr qo af zs xv nv ac DF Ad DLYR do БМЭФ вечера ZS Lo Ceyl Ai CaNV CA FY Wi-Fi Ne TX ZB Bm Kn Ul Bn Ar км от ФоКо Ро До Gp Ло KV ДМ мл Ке Зи Лок рк пр Ad XL TX ZB ле нв Занимаешься своими делами, не обращаешь внимания, не обращаю внимания на то, что я делаю тебя, как ты думаешь. пу ад хл нл эр нв кз кн о г у г дф пб уз фо я ау дк ву ло гд экс айп бп ап хв йф нв вк пз дм вк во вк пр кз ро

Источник

2 ответа

Алгоритмы Hillclimbing, применяемые к криптографии, работают следующим образом:

  1. Создайте ключ наугад (алфавит из 25 символов в случайном наборе) и определите свою пригодность с помощью набранных цифр. Назовите это "родитель"
  2. Внесите некоторые изменения в родительский элемент, чтобы получить "дочерний" ключ (случайные перестановки в таблице ключей 5x5 не так уж и плохи) и измерьте его пригодность с помощью функции оценки орграфов.
  3. Если ребенок более здоров, чем родитель, сделайте его новым родителем и откажитесь от старого
  4. Вернитесь к (2), если только за последние 1000 изменений нет улучшений; в этом случае вернитесь к (1)

Это способ избежать блокировки в локальном максимуме функции оценки орграфов.

Если вы хотите получить лучшие результаты, чем Hillclimbing, вы должны разработать алгоритм имитации отжига. Также функция оценки, основанная на триграммах или 4 граммах, имеет меньше локальных максимумов. Если вы хотите взломать его быстрее, вы бы перешли с Python на C/C++.

Алгоритмы HillClimbing и Simulated Annealing могут использоваться для взлома шифров Playfair, а также всех других шифров на основе сетки 5*5, а также простых шифров замещения и шифров Vigenere.

С шифром Playfair важно то, что он слабый: все круговые горизонтальные или вертикальные перестановки сетки 5x5 являются эквивалентным ключом. Таким образом, сходимость алгоритмов для этого шифра быстрее.

Чтобы сделать родительский алфавит, используйте следующее:

alpha='ABCDEFGHIKLMNOPQRSTUVWXYZ'
used=[0]*25;parent=['']*25
for i in range(25):
    j=randrange(25)
    while used[j]:j=randrange(25)
    parent[i]=alpha[j];used[j]=1

Функция расшифровки playfair:

def DEplayfair(a,key):
l=[];order={}
for k in range(25):order[key[k]]=k
for i in range(0,len(a),2):
    ord1=order[a[i]]
    raw1=ord1//5
    col1=ord1%5
    ord2=order[a[i+1]]
    raw2=ord2//5
    col2=ord2%5
    if raw1==raw2:
        l.append(key[5*raw1 + (col1 + 4)%5])
        l.append(key[5*raw2 + (col2 + 4)%5])
    elif col1==col2:
        l.append(key[col1 + 5*((raw1 + 4)%5)])
        l.append(key[col2 + 5*((raw2 + 4)%5)])
    else:
        l.append(key[5*raw1 + col2])
        l.append(key[5*raw2 + col1])
return ''.join(l)

Для алгоритмов SA вы можете найти основные принципы SA в: http://en.wikipedia.org/wiki/Simulated_annealing

Шифр Playfair использовался береговой охраной США во время Второй мировой войны, и существует известный исторический шифр Playfair: http://practicalcryptography.com/ciphers/playfair-cipher/

PS: Имя главного героя в вашем примере с шифром Playfair - Алиса.

Источник

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

  1. Поколение 0 - это случайные ключи.
  2. Выберите n ключей с наивысшим рейтингом, остальные умрут.
  3. Скрестить выживших между собой. Низкий процент мутирует при рекомбинации.
  4. Промыть и повторить.

Рекомбинация может выглядеть так:

  1. Родители A и B, и они производят потомство.
  2. Для каждого потомства выберите 0 <= x <= y < 25 (возможно, с ограничением y - x > c). Ключ потомка - A[:x] + B[x:y] + A[y:].
Источник
Другие вопросы по тегам