2014 dxdy logo

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

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




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


19/12/10
1546
В сабжевой задаче, похоже, используется, всё таки, полный алфавит, либо алфавит без буквы Й. Так как в шифротексте и Е и Ё присутствуют одновременно.

 Профиль  
                  
 
 Re: Шифр
Сообщение12.10.2013, 15:33 


05/09/12
2587
Думал уже над этим, но это только предположение. Может автор задач узнал, что в русском языке есть буква Ё, начал еЁ вовсю применять при написании посланий, а алфавит не заменил и она остаЁтся как есть, как пробелы и знаки препинания.

 Профиль  
                  
 
 Re: Шифр
Сообщение12.10.2013, 15:58 


30/03/12
130
Индекс совпадений говорит в пользу полиалфавитного шифра с тремя алфавитами, код на питоне:
Код:
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 


30/03/12
130
Это полиалфавитный шифр, причём одной букве шифротекста может соответствовать несколько букв открытого текста(не помню каким термином такие буквы шифротекста называют). Период три, вот частичная расшифровка:
Цитата:
интересно, хватит разгадывающему текста для построения статистики, или нет. по прежнему, в качестве ответа будет ключевое слово. чтобы не нарушать традицию, это будет слово "с(на)лрв(ит)н(на)". правда шифр уже сложнее - это и не шифр виженера, а просто какой-то абстрактный полиалфавитный шифр с периодом три.

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

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

 Профиль  
                  
 
 Re: Шифр
Сообщение14.10.2013, 00:05 


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

 Профиль  
                  
 
 Re: Шифр
Сообщение14.10.2013, 00:28 


30/03/12
130
_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 


05/09/12
2587
Моя ошибка была в том, что я не проводил частотный анализ. Хотя дошел до того, что это полиалфавитный шифр, но я пытался подобрать аналитическую закономерность нахождения замен, пытаясь "угадать" отдельные слова и выражения, а потом увидеть закономерности (типа афинного полиалфавитного и т.п.). Не исключал и варианта, что это какой-нибудь двойной или тройной шифр типа Атбаша с последующей парной перестановкой и сверху полированный Цезарем. И без частотного анализа опираться я мог только на предположения, что именно написано в каждой фразе, хотя бы структурно. И вот здесь, конечно, вводные слова с запятыми и дефис-не дефис сильно меняют дело...

 Профиль  
                  
 
 Re: Шифр
Сообщение14.10.2013, 02:09 


30/03/12
130
_Ivana в сообщении #774866 писал(а):
Моя ошибка была в том, что я не проводил частотный анализ.

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

 Профиль  
                  
 
 Re: Шифр
Сообщение16.10.2013, 08:30 


16/10/13
11
Бред.

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


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

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

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

 Профиль  
                  
 
 Re: Шифр
Сообщение16.10.2013, 09:12 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Motx в сообщении #775781 писал(а):
При такой длине ШТ с ошибками в каждом слове вы хотели расшифровать?

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

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

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

 Профиль  
                  
 
 Re: Шифр
Сообщение16.10.2013, 09:59 


16/10/13
11
: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 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Motx в сообщении #775792 писал(а):
Уважаемый учите матчасть

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

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

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


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

 Профиль  
                  
 
 Re: Шифр
Сообщение16.10.2013, 10:47 


16/10/13
11
Шифрование должно не зависить от данных, все современные шифры раобают с бинарной строкой, и не важно текст это или программа, или рисунок.

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

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

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

 Профиль  
                  
 
 Re: Шифр
Сообщение16.10.2013, 10:57 
Заслуженный участник
Аватара пользователя


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

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

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

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

 Профиль  
                  
 
 Re: Шифр
Сообщение16.10.2013, 11:01 


16/10/13
11
Для учебных задач иногда допускают что е=ё, и=й, ъ=ь, но НИКОГДА в=с, т=н, а=о и т. д.

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


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 56 ]  На страницу Пред.  1, 2, 3, 4  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group