Как сравнить гистограммы?
Захотелось попробовать расшифровать шифр из «Жангады» Жюля Верна. Там был текст из 252 букв: message = 'СГУЧПВЭЛЛЗЙРТЕПНЛНФГИНБОРГЙУГЛЧДКОТХЖГУУМЗДХРЪСГСЮДТПЪАРВЙГГИЩВЧЭЕЦСТУЖВСЕВХАХЯФБЬБЕТФЗСЭФТХЖЗБЗЪГФБЩИХХРИПЖТЗВТЖЙТГОЙБНТФФЕОИХТТЕГИИОКЗПТФЛЕУГСФИПТЬМОФОКСХМГБТЖФЫГУЧОЮНФНШЗГЭЛЛШРУДЕНКОЛГГНСБКССЕУПНФЦЕЕЕГГСЖНОЕЫИОНРСИТКЦЬЕДБУБТЕТЛОТБФЦСБЮЙПМПЗТЖПТУФКДГ' и N-значное число, задававшее кольцевые сдвиги. В романе шифр описывался как принципиально невзламываемый из-за большой вычислительной сложности, но к моменту публикации его уже научились вскрывать. Для этого берут срезы (или какой принят термин?) message[0::N], message[1::N] … message[N-1::N], для каждого строят гистограмму вероятностей букв и сравнивают с эталонной, насколько нужно сдвинуть.
Вопрос: как это сравнение гистограмм реализовать программно?
Я попробовал сравнивать суммы квадратов разностей, перебирая сдвиги для каждой длины ключа, и это позволило найти сдвиги, угадав длину ключа. Но для разных длин ключа сравнивать эти суммы напрямую нельзя — наименьшая сумма вышла для 1-значного ключа. Как их сравнивать?
Для определённости — код:
message = 'СГУЧПВЭЛЛЗЙРТЕПНЛНФГИНБОРГЙУГЛЧДКОТХЖГУУМЗДХРЪСГСЮДТПЪАРВЙГГИЩВЧЭЕЦСТУЖВСЕВХАХЯФБЬБЕТФЗСЭФТХЖЗБЗЪГФБЩИХХРИПЖТЗВТЖЙТГОЙБНТФФЕОИХТТЕГИИОКЗПТФЛЕУГСФИПТЬМОФОКСХМГБТЖФЫГУЧОЮНФНШЗГЭЛЛШРУДЕНКОЛГГНСБКССЕУПНФЦЕЕЕГГСЖНОЕЫИОНРСИТКЦЬЕДБУБТЕТЛОТБФЦСБЮЙПМПЗТЖПТУФКДГ'
alph32 = 'АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ'
def rln32(letter):
'''Номер буквы 32-буквенного русского алфавита.'''
return alph32.index(letter);
def letter_frequencies(text):
'''Частоты букв в тексте.'''
return [ text.count(letter) / len(text) for letter in alph32 ]
etalon = letter_frequencies(sample_text) # эталонная гистограмма вероятностей букв
def shiftmatch(a1, a2, shift):
'''Сумма квадратов разностей элементов списков для сдвига shift.'''
return sum((val - a2[ (pos + shift) % 32 ])**2 for pos, val in enumerate(a1))
for razr in range(1,13): # длина ключа
shifts = [0] * razr
for place in range(razr): # позиция в ключе
probs = letter_frequencies(message[place::razr]) # гистограмма для позиции
match = [ shiftmatch(etalon, probs, s)*100 for s in range(32) ]
mm = min(match)
shifts[place] = match.index(mm);
print(razr, place, shifts[place], mm, sep = '\t');
print(''.join(alph32[(rln32(l) - shifts[p % razr]) % 32] for p,l in enumerate(message)))
Для 6-значного ключа скрипт подобрал верное значение [4, 3, 2, 5, 1, 3], но как численно обосновать, что ключ 6-разрядный?
