2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Шифр
Сообщение12.10.2013, 15:29 
Аватара пользователя
В сабжевой задаче, похоже, используется, всё таки, полный алфавит, либо алфавит без буквы Й. Так как в шифротексте и Е и Ё присутствуют одновременно.

 
 
 
 Re: Шифр
Сообщение12.10.2013, 15:33 
Думал уже над этим, но это только предположение. Может автор задач узнал, что в русском языке есть буква Ё, начал еЁ вовсю применять при написании посланий, а алфавит не заменил и она остаЁтся как есть, как пробелы и знаки препинания.

 
 
 
 Re: Шифр
Сообщение12.10.2013, 15:58 
Индекс совпадений говорит в пользу полиалфавитного шифра с тремя алфавитами, код на питоне:
Код:
import re
chiper = 'ЩЭАШЬШОЭШ, ПЭМЫЛА ЗЪОЗЪЪУЭМУЖШПЕ АШСКЫЪ ЪЪБ РЕЦАЗПШСЛЗ ОЛМЫЛКЫЛРЩ, ЛБЩ ЭШЫ. ДШ ХЬШЦЭШПЕ, Б ДЪУШЦАББ ШЫЭШЫЪ ЬХФШЫ СБУНШБПШ ОУШБП. УЫПЬУ ЭШ СЪФХНМЫИ АЗЪЪЩОЁУ, ЭАЕ ФЕНБА ОУШБП "КСУФБЛНС". ДФСЭЪС НЁФЬ ЕЦБ КЪПЮСБШ - ДЛШ Щ ЭШ ЕЛЩЗ ЭЁЦБНШЬМ, С ДФЕЦАЕ СМДПС-ЫП МВЦАЗЪРЫЭЁФ ДШЪЛМЪСМБЛАСЩС ЕЛЩЗ Ц РШЬЁЕФШП ЛФЩ.'
alpha = [chr(x+ord('А')) for x in range(6)]+['Ё']+[chr(x+ord('А')) for x in range(6,32)]

chiper = re.sub('[^А-ЯЁ]', '', chiper)

def CoincidentIndex(text):
   frequency = [0 for x in range(32)]
   n = 0
   for ch in text:
      try:
         frequency[alpha.index(ch)]+=1
         n += 1
      except ValueError:
         pass
   ret = 0
   for x in frequency:
      ret += x*(x-1)/n/(n-1)
   return ret

for x in range(1,14):
   s = 0
   for y in range(x):
      s += CoincidentIndex(chiper[y::x])
   print(x, '->', s/x)

вывод:
Цитата:
1 -> 0.0461445051608986
2 -> 0.045657769949871294
3 -> 0.08575981130181672
4 -> 0.04549180327868853
5 -> 0.045578231292517014
6 -> 0.08347925786950178
7 -> 0.047648150169158576
8 -> 0.04303856136447905
9 -> 0.0848821959933071
10 -> 0.04623188405797101
11 -> 0.04438512738907996
12 -> 0.08567251461988305
13 -> 0.044587335609007434

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

 
 
 
 Re: Шифр
Сообщение13.10.2013, 23:49 
Это полиалфавитный шифр, причём одной букве шифротекста может соответствовать несколько букв открытого текста(не помню каким термином такие буквы шифротекста называют). Период три, вот частичная расшифровка:
Цитата:
интересно, хватит разгадывающему текста для построения статистики, или нет. по прежнему, в качестве ответа будет ключевое слово. чтобы не нарушать традицию, это будет слово "с(на)лрв(ит)н(на)". правда шифр уже сложнее - это и не шифр виженера, а просто какой-то абстрактный полиалфавитный шифр с периодом три.

Т.е. я так и не угадал секретное слово, но это явно из-за того что не знаю о какой традиции речь :) .
Ключи:
Код:
{'С': ['н', 'а'], 'У': ['ю', 'ы'], 'Ф': ['й', 'ф'], 'Х':['у', 'п'], 'Ц': ['ж'], 'Ш': ['е'], 'Щ': ['и'], 'Ъ': ['л'], 'Ы': ['т'], 'Б': ['в'], 'В': ['б'], 'Д': ['к', 'э'], 'Е': ['ш', 'о'], 'З': ['р', 'г'], 'Н': ['д'], 'О': ['с'], 'П': ['х', 'м']}
{'С': ['к', 'ф'], 'У': ['л'], 'Ф':['д', 'б'], 'Ц': ['с'], 'Щ': ['ы'], 'Ъ': ['а'], 'Ь': ['р'], 'Э': ['в', 'н', 'э'], 'Б': ['е', 'я'], 'Д': ['п'], 'Е': ['у'], 'Ж': ['щ'], 'И': ['ь'], 'Л': ['и', 'т'], 'Н': ['ч', 'ш'], 'О': ['ц'], 'П': ['о']}
{'Р': ['к', 'п'], 'С': ['й'], 'У': ['ч'], 'Ф': ['р'], 'Ш': ['о', 'е'], 'Щ':['ф'], 'Ъ': ['д'], 'Ь': ['б'], 'Ю': ['ж'], 'А': ['т'], 'Б': ['л', 'в'], 'Е': ['у'], 'З': ['я'], 'К': ['с'], 'М': ['а'], 'Н': ['н'], 'О': ['з'], 'Ё': ['ы', 'и']}

В принципе всткрывается довольно быстро, главное подходящий скрипт написать, а слова легко угадывались. Частотный анализ оказалось сложно провести - из-за малого объёма текста биграммы малоинформативны, а монограммы искажены многозначностью ключа.

 
 
 
 Re: Шифр
Сообщение14.10.2013, 00:05 
Euler7 в сообщении #774835 писал(а):
по прежнему,
Я четверть головы напряг на попытке расшифровки, и безуспешно. По моему мнению, прогнал все трехбуквенные ключи по Виженеру и много чего еще... Но, честно говоря, был неприятно удивлен, увидев в тексте сабжевое выражение без дефиса и отделенное запятой! Запятая перед "или нет" также имхо более чем сомнительна... Я просто не ожидал от человека текста, где делается явное различие между тире и дефисом, таких ляпов!.... Хорошо хоть слово
Euler7 в сообщении #774835 писал(а):
какой-то
(или деривативы типа когда-то и т.п.), массово всеми угаданное, написано в исходном тексте правильно....
ЗЫ вконтакте у автора задач появились ссылки на обсуждение на форумах, в т.ч. и на dxdy. И одно время висел коммент про "троллирующие посты на форумах", который потом исчез. Но имхо не грех и потроллить.
ЗЗЫ Euler7, спасибо, спасли от бессонной ночи :)

 
 
 
 Re: Шифр
Сообщение14.10.2013, 00:28 
_Ivana в сообщении #774840 писал(а):
Я четверть головы напряг на попытке расшифровки, и безуспешно. По моему мнению, прогнал все трехбуквенные ключи по Виженеру и много чего еще... Но, честно говоря, был неприятно удивлен, увидев в тексте сабжевое выражение без дефиса и отделенное запятой! Запятая перед "или нет" также имхо более чем сомнительна... Я просто не ожидал от человека текста, где делается явное различие между тире и дефисом, таких ляпов!....

Ну дефис там сильно упростил бы дело, я это слово только в самом конце угадал, вот вся последовательность угадывания(выдрано из кода):
Код:
change('СМДПСЫП', 'какойто')
change('ОУШБП', 'слово')
change('СБУНШБПШ', 'ключевое')
change('ШЫЭШЫЪ', 'ответа')
change('ДШЪЛМЪСМБЛАСЩС', 'полиалфавитный')
change('ЕЛЩЗ', 'шифр')
change('ДЪУШЦАББ', 'качестве')
change('ОЛМЫЛКЫЛРЩ', 'статистики')
change('ПЭМЫЛА', 'хватит')
change('ЩЭАШЬШОЭШ', 'интересно')
change('УЫПЬУ', 'чтобы')
change('МВЦАЗЪРЫЭЁФ', 'абстрактный')
change('ЪЪБ', 'для')
change('РЕЦАЗПШСЛЗ', 'построения')
change('ЭЁЦБНШЬМ', 'виженера')
change('ЬХФШЫ', 'будет')
change('СЪФХНМЫИ', 'нарушать')
change('АЗЪЪЩОЁУ', 'традицию')
change('ЭАЕ', 'это')
change('ФЕНБА', 'будет')
change('НЁФЬ', 'шифр')
change('КЪПЮСБШ', 'сложнее')
change('ДЛШ', 'это')
change('РШЬЁЕФШП', 'периодом')
change('ХЬШЦЭШПЕ', 'прежнему')
change('ЗЪОЗЪЪУЭМУЖШПЕ', 'разгадывающему')

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

 
 
 
 Re: Шифр
Сообщение14.10.2013, 01:22 
Моя ошибка была в том, что я не проводил частотный анализ. Хотя дошел до того, что это полиалфавитный шифр, но я пытался подобрать аналитическую закономерность нахождения замен, пытаясь "угадать" отдельные слова и выражения, а потом увидеть закономерности (типа афинного полиалфавитного и т.п.). Не исключал и варианта, что это какой-нибудь двойной или тройной шифр типа Атбаша с последующей парной перестановкой и сверху полированный Цезарем. И без частотного анализа опираться я мог только на предположения, что именно написано в каждой фразе, хотя бы структурно. И вот здесь, конечно, вводные слова с запятыми и дефис-не дефис сильно меняют дело...

 
 
 
 Re: Шифр
Сообщение14.10.2013, 02:09 
_Ivana в сообщении #774866 писал(а):
Моя ошибка была в том, что я не проводил частотный анализ.

Я пытался его провести, но толком ничего не получилось. Мне кажется главное тут постоянно иметь перед глазами частично расшифрованный текст в разных форматах, т.е. задача скорее на программирование чем на криптоанализ. Ещё помог pymorphy2, который хорошо отсеивал невалидные слова, устраняя(уменьшая) неоднозначности. Им же можно частично открытые слова подбирать, если 3-4 букв не хватает, то вполне можно полным перебором получить список всех возможных слов. Я долго надеялся вскрыть шифр в автоматическом режиме, но сейчас думаю что это слишком сложно.

 
 
 
 Re: Шифр
Сообщение16.10.2013, 08:30 
Бред.

Для полиалфавиного шифра:
Код:
алф1.      алф.2     алф.3
Щ- и        Э - н      А - т
Ш - е       Ь - р      Ш - е<
О -  с      Э - н<     Ш, - о<
П -  х      Э - в<     М - а
Ы -  т      Л -  и     А - т


2 слова - 2 ошибки.

При такой длине ШТ с ошибками в каждом слове вы хотели расшифровать?

Автор просто смеется над всеми вами.

 
 
 
 Re: Шифр
Сообщение16.10.2013, 09:12 
Аватара пользователя
Motx в сообщении #775781 писал(а):
При такой длине ШТ с ошибками в каждом слове вы хотели расшифровать?

Однако, шифр оказался взломанным.

Да и в чём Вы увидели ошибку?
Никто не гарантировал, что для открытого текста и шифротекста будет использоваться один и тот же алфавит, в частности, что мощности этих алфавитов будут равны.

Уже в примере с шифром Цезаря автор задачи использовал для шифротекста алфавит мощности 31 (Е,Ё ->Е; И,Й->И). Можно было предположить, что в сабжевой задаче этот приём будет только усилен.

 
 
 
 Re: Шифр
Сообщение16.10.2013, 09:59 
:facepalm:
Уважаемый учите матчасть - ключевое слово "полиалфавитный шифр"

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

В полиалфавитном шифре используються несколько алфавитов ( поли- много).
Каждый из которых является шифром простой замены - и в нем действуют правила для таких шифров, а именно
при А=x B=y,
если x<>y то обязательно A<>B.

Если
$ с i = (p i + k i) mod (L) $
для
і=1 - шифр Цезаря
i>1 - шифр Виженера
i= длине сообщения, - одноразовый шифр блокнот.

Если нету правила - каждый алфавит независимый и не зависит от ключевого слова , но алфавиты зависят от позиции буквы - получим общий случай полиалфавитного шифра.
И в любом случае будут выполнятся условия для одного алфавита.

А то что придумал автор - бредятина чистой воды.


Иначе получится бред с вашим "шифром":

вместо
легендарная деВятая рота
получится
легендарная деСятая рота

Неоднозначно? Усилено? - О, да. Толку то? :facepalm:

 
 
 
 Re: Шифр
Сообщение16.10.2013, 10:38 
Аватара пользователя
Motx в сообщении #775792 писал(а):
Уважаемый учите матчасть

Воспользуйтесь этим советом, изучите $\TeX$ и перепишите все свои формулы в соответствии с правилами форума.
Motx в сообщении #775792 писал(а):
В общем случае - в любом шифре должны быть четкие правила -
иначе зашифровав ехе-шник, после расшифровки он никогда не будет работать.

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

Способ применённый автором задачи является одним из таких методов.
Шифрование текста происходит однозначно. Дешифровка, в подавляющем большинстве случаев, также будет однозначной ввиду существующей избыточности естественного текста.
Motx в сообщении #775792 писал(а):
вместо
легендарная деВятая рота
получится
легендарная деСятая рота


Троллите, Уважаемый, Ваш пример не имеет отношения к рассматриваемой задаче.

 
 
 
 Re: Шифр
Сообщение16.10.2013, 10:47 
Шифрование должно не зависить от данных, все современные шифры раобают с бинарной строкой, и не важно текст это или программа, или рисунок.

Пример как имеет оношение, если в шифре знак Х может быть и В и С и Щ, тогда при расшифровке получится неоднозначность деВять<>деСять?

Получат в штабе армии такое шифрсообщение - и вместо подкрепления легендарной девятой роте, которая бедная несет потери в Кандагаре,пошлют подкрепление десятой роте которая пинает на границе.

Повышение стойкости через проблеммы при расшифровке - вот где бредятина этого "шифра"

 
 
 
 Re: Шифр
Сообщение16.10.2013, 10:57 
Аватара пользователя
Motx в сообщении #775792 писал(а):
Каждый из которых является шифром простой замены - и в нем действуют правила для таких шифров, а именно
при А=x B=y,
если x<>y то обязательно A<>B.

С чего Вы взяли?
Выше приведён пример задачи того же автора с шифром Цезаря где $e(\text{И})= e(\text{Й})$, хотя $\text{Й}\ne\text{И}$

Motx в сообщении #775814 писал(а):
все современные шифры раобают с бинарной строкой, и не важно текст это или программа, или рисунок.

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

 
 
 
 Re: Шифр
Сообщение16.10.2013, 11:01 
Для учебных задач иногда допускают что е=ё, и=й, ъ=ь, но НИКОГДА в=с, т=н, а=о и т. д.

Похоже автор
Код:
слышал звон, да не знает, где он


Если задача учебная и нужно было расшифровать текст с ошибками - так должно быть указано.

 
 
 [ Сообщений: 56 ]  На страницу Пред.  1, 2, 3, 4  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group