Занимательная криптография

← →
Сергей М. © (2012-04-11 15:03) [0]

В результате двойного последовательного шифрования некоего текста с использованием некоей заведомо неизвестной шифр-решетки Кардано 8х8 получена дословно след.матрица:

в р и е а ь и Л
р е е ы п ы п а
о с н л х а л Н
ы н ф и о о п т
е р г ь р д г ц
Р е ф й и с ж д
О а и т и с ж д
н о л и х р е и

Задача : найти текст исходного сообщения.

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

А вы как думаете ?

← →
БарЛог © (2012-04-11 15:11) [1]

в р и е а ь и Л
р е е ы п ы п а
о с н л х а л Н
ы н ф и о о п т
е р г ь р д г ц
Р е ф й и с ж д
О а и т и с ж д
н о л и х р е и

← →
Kerk © (2012-04-11 17:42) [2]

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

← →
KilkennyCat © (2012-04-11 19:49) [3]

Если заглавные буквы не просто так...

← →
Сергей М. © (2012-04-11 20:04) [4]

> Если заглавные буквы не просто так...

Меня вот тоже сей факт застеснял ..

← →
KilkennyCat © (2012-04-11 20:12) [5]

Меня смущает факт двойной перестановки. учитывая, что решетка одна и та же (а даже и разные), скорее всего, расшифровка будет за один раз, но другой решеткой.

← →
Сергей М. © (2012-04-11 21:14) [6]

> но другой решеткой

По условиям решетка одна и та же ..

← →
oldman © (2012-04-11 21:26) [7]

> Если заглавные буквы не просто так...

Тогда где знаки препинания? Хотя бы точка?

← →
Inovet © (2012-04-11 21:30) [8]

> [7] oldman © (11.04.12 21:26)
> Тогда где знаки препинания? Хотя бы точка?

зпт тчк

← →
Сергей М. © (2012-04-12 09:24) [9]

> зпт тчк

И такое ведь не исключено ..

← →
oldman © (2012-04-12 09:52) [10]

http://www.cyberforum.ru/cpp-beginners/thread339793.html
:)

← →
Сергей М. © (2012-04-12 10:22) [11]

> oldman © (12.04.12 09:52) [10]

Ценнейшее обсуждение)

← →
oldman © (2012-04-12 10:32) [12]

> Задача : найти текст исходного сообщения.
>
> Полагаю что при данной вводной без перебора всех возможных
> решеток с последующим привлечением лингвоанализатора к результатам
> декодирования для каждой из решеток не обойтись.

Ответов может быть несколько. )))

> Например, врядли в сообщении могут идти буквы "фй"

"штоф йода"

← →
KilkennyCat © (2012-04-12 10:33) [13]

кайф Йоды

← →
Inovet © (2012-04-12 10:40) [14]

> [10] oldman © (12.04.12 09:52)
> http://www.cyberforum.ru/cpp-beginners/thread339793.html

У меня ФФ поперхнулся и странным стал, по Alt+F4 закрыл, так как в заголовке кнопок не было. Потм нормально стал есть. Что это было? Вчера у меня Silverlight с обновлениями установился, может он чего проинициализировал.

← →
oldman © (2012-04-12 11:28) [15]

шифр-решетка Кардано для квадратных матриц вообще забавная штука.
наложив решетку на матрицу получаем ПЕРВУЮ часть фразы,
повернув решетку на 90 градусов - ВТОРУЮ... и т.д.
используя и зеркальную решетку фраза может состоять из ВОСЬМИ фрагментов

← →
AV © (2012-04-12 12:10) [16]

> Полагаю что при данной вводной без перебора всех возможных
> решеток с последующим привлечением лингвоанализатора к результатам
> декодирования для каждой из решеток не обойтись.
>
> А вы как думаете ?

так же

← →
brother © (2012-04-12 12:13) [17]

> У меня ФФ поперхнулся и странным стал

не подтверждаю, все гуд...

Комментарий модератора silent_1991 Больше подобным образом названия тем не выделяем!

моэет это?

← →
Сергей М. © (2012-04-12 12:19) [18]

> используя и зеркальную решетку фраза может состоять из ВОСЬМИ
> фрагментов

это если решетка с 8-ю дырками.

а с 16-ю дырками речь о зеркальном ее использовании речь идти не может и исходное сообщение может состоять не более чем из 4-х фрагментов.

Для иллюстрации - фрагмент кода для генерации уникальной 16-дырочной решетки из 4-х миллиардов возможных при матрице 8x8:

const MatrixSize = 8; type TMask = array[0..15] of Integer; // тип для описания индексов дырок в матирице const BaseMask: TMask = (1,2,3,4,5,6,7,10,11,12,13,14,19,20,21,28); RotVectors: array[1..MatrixSize*MatrixSize, 0..3] of Integer = ((1,8,64,57),(2,16,63,49),(3,24,62,41),(4,32,61,33), (5,40,60,25),(6,48,59,17),(7,56,58,9),(8,64,57,1), (9,7,56,58),(10,15,55,50),(11,23,54,42),(12,31,53,34), (13,39,52,26),(14,47,51,18),(15,55,50,10),(16,63,49,2), (17,6,48,59),(18,14,47,51),(19,22,46,43),(20,30,45,35), (21,38,44,27),(22,46,43,19),(23,54,42,11),(24,62,41,3), (25,5,40,60),(26,13,39,52),(27,21,38,44),(28,29,37,36), (29,37,36,28),(30,45,35,20),(31,53,34,12),(32,61,33,4), (33,4,32,61),(34,12,31,53),(35,20,30,45),(36,28,29,37), (37,36,28,29),(38,44,27,21),(39,52,26,13),(40,60,25,5), (41,3,24,62),(42,11,23,54),(43,19,22,46),(44,27,21,38), (45,35,20,30),(46,43,19,22),(47,51,18,14),(48,59,17,6), (49,2,16,63),(50,10,15,55),(51,18,14,47),(52,26,13,39), (53,34,12,31),(54,42,11,23),(55,50,10,15),(56,58,9,7), (57,1,8,64),(58,9,7,56),(59,17,6,48),(60,25,5,40), (61,33,4,32),(62,41,3,24),(63,49,2,16),(64,57,1,8)); procedure QuickSort(var Mask: TMask; L, R: Integer); var I, J: Integer; P, T: Integer; begin repeat I := L; J := R; P := Mask[(L + R) shr 1]; repeat while Mask[I] < P do Inc(I); while Mask[J] > P do Dec(J); if I <= J then begin T := Mask[I]; Mask[I] := Mask[J]; Mask[J] := T; Inc(I); Dec(J); end; until I > J; if L < J then QuickSort(Mask, L, J); L := I; until I >= R; end; // генерация уникальной маски // Id - индекс уникальной маски, записываемой в Mask procedure BuildMask(var Mask: TMask; Id: DWord); var i: Integer; begin i := 0; repeat Mask[i] := RotVectors[BaseMask[i], Id and 3]; Id := Id shr 2; Inc(i) until i > High(Mask); QuickSort(Mask, 0, High(Mask)) end; // однократное вращение маски на 90 град. по час.стрелке procedure RotateMask(var Mask: TMask); var i: Integer; begin i := 0; repeat Mask[i] := RotVectors[Mask[i], 1]; Inc(i) until i > High(Mask); QuickSort(Mask, 0, High(Mask)) end; // вывод маски в текст.виде function MaskToStr(var Mask: TMask): String; var i,r: Integer; begin Result := ""; for i := 0 to High(Mask) do begin if i > 0 then Result := Result + ","; Result := Result + IntToStr(Mask[i]); end; end;

← →
Inovet © (2012-04-12 12:24) [19]

> [17] brother © (12.04.12 12:13)
> моэет это?

Не знаю, после нормально стало.

← →
oldman © (2012-04-12 12:29) [20]

> это если решетка с 8-ю дырками.

не факт...
нигде не сказано, что искомая фраза состоит из 64 символов.
на решетке может быть 4 дырки, но поворачивать надо всего 3 раза.
12 букв. остальные генерируются случайно.
зависит от инструкции к кодированию.

← →
Сергей М. © (2012-04-12 12:45) [21]

> oldman © (12.04.12 12:29) [20]

цитирую вводную дословно:

Для зашифрования текста шифром «Поворотная решетка» из бумажного квадрата размером 8на8 клеток изготавливают трафарет. Вырезанные клетки выбирают так , что при наложении трафарета на лист бумаги того же размера четырьмя возможными способами каждая клетка листа «открывается» ровно один раз. Первые 16 букв текста сообщения вписываются в прорези трафарета (по одной в каждую), потом трафарет поворачивается на 90 градусов, вписываются следующие 16 букв и т.д.Для повышения сложности шифра процедуру зашифрования провели дважды. Найдите текст исходного сообщения.

← →
Сергей М. © (2012-04-12 12:48) [22]

и ниже прилагается 5 различных образцов матриц 8x8, заполненных символами из набора ["A".."Я", "а".."я"]

первую из 5-ти я процитировал в топикстарте

← →
oldman © (2012-04-12 12:57) [23]

Я знаю первую букву!!!
Это Л.

При условии, что заглавные буквы не просто так. И что в искомой фразе 64 символа.

← →
oldman © (2012-04-12 13:00) [24]

> что при наложении трафарета на лист бумаги того же размера
> четырьмя возможными способами каждая клетка листа «открывается»
> ровно один раз

Количество вариантов уменьшается...
Для каждого отверстия всего 4 возможных положения.
Всего то 4^16 вариантов.

← →
Inovet © (2012-04-12 13:01) [25]

> [23] oldman © (12.04.12 12:57)
> Это Л.

Т.е. в решётке в первом ряду единственная дырка в углу?

← →
oldman © (2012-04-12 13:03) [26]

> Inovet © (12.04.12 13:01) [25]

видимо да

← →
Сергей М. © (2012-04-12 13:05) [27]

> oldman © (12.04.12 12:57) [23]
>
> Я знаю первую букву!!!
> Это Л.

"Ленина помнят рассветы и вёсны" ?)))

> При условии, что заглавные буквы не просто так

А нет такого условия как видишь)
Мож не просто так, а мож и для запутывания вражеской разведки)

> И что в искомой фразе 64 символа

Ну а сколько же еще , если не 64 ?
Даже если меньше - значит недостающие были каким-то образом выбраны для дополнения до 64.

← →
oldman © (2012-04-12 13:07) [28]

)))
а если еще в алгоритм запихать правила языка типа "жи"-"ши"...
)))

← →
oldman © (2012-04-12 13:08) [29]

> а мож и для запутывания вражеской разведки)

Вражеская разведка давно пользуется E-mail и не парится )))

← →
Сергей М. © (2012-04-12 13:18) [30]

> а если еще в алгоритм запихать правила языка типа "жи"-"ши".
> ..

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

← →
AV © (2012-04-12 16:42) [31]

> Для повышения сложности шифра процедуру зашифрования провели
> дважды

не понял. Как это?
Пусть имеем фразу word: string = "QWERT..", length(word) = 64
зашифровали сеткой, получили матрицу
M:array[0..7][0..7] of char =
Q А V Р S ..
...

как второй раз зашифровать?

← →
AV © (2012-04-12 16:54) [32]

а..
или получили тогда
word: string = "QАVРS..", length(word) = 64
обходя матрицу лево-право, верх-низ

а это слово опять зашифровали сеткой..

так?

← →
Сергей М. © (2012-04-12 16:54) [33]

> как второй раз зашифровать?

подготавливаемая к повторному шифрованию строка последовательно слева направо заполняется символами из матрицы по правилу:

word[i] := M[(i - 1) div 8, (i - 1) mod 8]

← →
Сергей М. © (2012-04-12 16:55) [34]

> так?

ну судя по вводной именно так дело и было)

← →
Inovet © (2012-04-12 18:19) [35]

> [34] Сергей М. © (12.04.12 16:55)
> ну судя по вводной именно так дело и было)

Интересно, а это реально повышает стойкость? Как-то сомнительно.

← →
Sha © (2012-04-12 19:35) [36]

> Сергей М.

Я правильно понял, что процедура преобразования текста следующая:
- написали текст в решетку 8х8
- наложили трафарет с 16 дырками
- выписали 16 открытых букв в 2 строчки по 8 букв
- повернули трафарет на 90 градусов по часовой стрелке
- выписали 16 открытых букв в следующие 2 строчки по 8 букв
- повернули трафарет на 90 градусов по часовой стрелке
- выписали 16 открытых букв в следующие 2 строчки по 8 букв
- повернули трафарет на 90 градусов по часовой стрелке
- выписали 16 открытых букв в следующие 2 строчки по 8 букв
- с 8-ю получившимися строчками по 8 букв повторили описанную процедуру
- в результате получена решетка из [1]

← →
Сергей М. © (2012-04-12 20:15) [37]

> Sha © (12.04.12 19:35) [36]

Я понимаю вводную так:

1. Есть исх.строка S текста из 64 символов в вышепроцитированном диапазоне.

2. На подготовленную "пустую" матрицу M приложен Кардано-трафарет X с 16-ю дырками. В каждую из дырок слева направо сверху вниз вписаны символы 1..16 исх.строки.

3. Трафарет повернут на 90 град по часовой, в "дырки" вписаны символы 17..32 исх.строки.

4. Трафарет повернут на 90 град по часовой, в "дырки" вписаны символы 17..32 исх.строки.

5. Трафарет повернут на 90 град по часовой, в "дырки" вписаны символы 33..48 исх.строки.

6. Трафарет повернут на 90 град по часовой, в "дырки" вписаны символы 49..64 исх.строки.

------------------------------------------------------------------

7. Из полученной матрицы М сформирована строка S1 из 64 символов, полученная посимвольным чтением элементов матрицы в порядке обхода по строкам/столбцам сверху вниз и слева направо соответсвенно.

8. Строка S1 подвергнута преобразованиям с 2 по 6.

9. Результат преобразований в п.8 представлен во вводной.

← →
Сергей М. © (2012-04-12 20:15) [38]

> - в результате получена решетка из [1]
>

Похоже что так)

← →
Сергей М. © (2012-04-12 20:19) [39]

> в вышепроцитированном диапазоне

Имелось ввиду : что вижу - то и пою)
Символы вых.матрицы именно в этом диапазоне, если не синдром мартышки к старости.

← →
Сергей М. © (2012-04-12 20:21) [40]

> 3. Трафарет повернут на 90 град по часовой, в "дырки" вписаны
> символы 17..32 исх.строки.

зарапортовался-закопипастился)))
это не считается, ессно..

← →
Сергей М. © (2012-04-12 20:24) [41]

Собссно а что там думать ?

В [18] я привел рабочую заготовочку для сокращения времени на эксперименты заинтересовавшиися сей занимательной хренью)

← →
Sha © (2012-04-12 20:25) [42]

Ясно.
Получается, в [36] описано обратное преобразование.

Тогда просто в лоб [36] с учетом того,
что в тексте не должно быть подряд 4 гласных или 6 согласных.

← →
Sha © (2012-04-12 20:33) [43]

Для ускорения можно массово отсечь плохие варианты, крутя только центр 6х6

← →
Sha © (2012-04-12 20:37) [44]

И еще )
При двойном преобразовании буква либо остается на месте,
либо отражается центрально-симметрично.

← →
Sha © (2012-04-12 20:39) [45]

Ошибся.

← →
Сергей М. © (2012-04-12 20:45) [46]

> не должно быть подряд 4 гласных или 6 согласных

Так точно, сэр)
Это первое что мне как и тебе пришло в голову..

← →
Сергей М. © (2012-04-12 20:47) [47]

Но !
Опять же в предположении что в исх.тексте нет бредятины.

← →
Sha © (2012-04-12 21:10) [48]

А иначе любое решение подойдет.

← →
han_malign (2012-04-13 08:46) [49]

> 7. Из полученной матрицы М сформирована строка S1 из 64
> символов, полученная посимвольным чтением элементов матрицы
> в порядке обхода по строкам/столбцам сверху вниз и слева
> направо соответсвенно.
>
> 8. Строка S1 подвергнута преобразованиям с 2 по 6.
>
> 9. Результат преобразований в п.8 представлен во вводной.

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

← →
han_malign (2012-04-13 09:14) [50]

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

← →
han_malign (2012-04-13 09:29) [51]

З.Ы. И слов содержащих "х" и "ф", в словаре тоже не особо много(в словаре Даля - 2809 и 828)

← →
Сергей М. © (2012-04-13 09:54) [52]

Опять же - судя по

> потом трафарет поворачивается на 90 градусов

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

← →
Сергей М. © (2012-04-13 10:10) [53]

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

← →
Сергей М. © (2012-04-13 10:18) [54]

И примерно столько же фрагмент "родина"

← →
Сергей М. © (2012-04-13 10:22) [55]

"россии", "родны" очень много

похоже на какую-то патриотическую лабуду)

> [55] Сергей М. © (13.04.12 10:22)
> похоже на какую-то патриотическую лабуду)

За использование шифров и за шифрование Родины - расттрел 2 раза.

но "ленин" пока бьет все рекорды - не менее чем раз 100 встречается)

> han_malign (13.04.12 09:14) [50]
> т.к. 64! - это не вариант

В нашем случае подстановок не больше 4^16=2^32, т.к.
1. все дырки после 0..3 вращений покрывают первый квадрант
2. при возведении в квадрат возможно? совпадение подстановок

А может там Ленин

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

Тэк-с .. Вождь, похоже, не при делах)

в р и е а ь и Л
р е е ы п ы п а
о с н л х а л Н
ы н ф и о о п т
е р г ь р д г ц
Р е ф й и с ж д
О а и т и с ж д
н о л и х р е и

Дело движется к нечто похожему на "Ленинград - город России на Неве. Он ...."

← →
аноним (2012-04-16 07:59) [64]

Скорее всего без брутфоса в руки, плюс n времени и словарика слов дело не обойдется. Причем взаимотнешение со словариком строить по проценту совпадений... Дальше делать выводы

← →
btfra (2012-04-17 02:11) [65]

11111110 00000001 00000000 00000000
01111100 00000011 00000000 10000000
00111000 00000111 00000000 11000000
00010000 00001111 00000000 11100000
00000000 00000111 00001000 11110000
00000000 00000011 00011100 11100000
00000000 00000001 00111110 11000000
00000000 00000000 01111111 10000000

← →
btframework (2012-04-17 02:12) [66]

Вот решетка удовлетворяющая условию задачи
11111110 00000001 00000000 00000000
01111100 00000011 00000000 10000000
00111000 00000111 00000000 11000000
00010000 00001111 00000000 11100000
00000000 00000111 00001000 11110000
00000000 00000011 00011100 11100000
00000000 00000001 00111110 11000000
00000000 00000000 01111111 10000000
(здесь она повернута 4 раза). 1 - дырка, 0 - нет дырки

← →
btframework (2012-04-17 02:15) [67]

ее же можно и в зеркальном отражении. т.е. всего 8 вариантов начальной решетки.

> [66] btframework (17.04.12 02:12)
> Вот решетка удовлетворяющая условию задачи

И какой текст зашифрован в исходм сообщении?

> btframework (17.04.12 02:12) [66]
>
> Вот решетка удовлетворяющая условию задачи

Не болтай ерундой)

точно с тем же успехом еще 4 млрд решеток будут удовлетворять условию)

← →
btf (2012-04-18 02:40) [71]

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

> btf (18.04.12 02:40) [71]

> Так что куча решеток отсеивается

Так никто и не возражает.
А оставшихся после "отсеивания" - 4 млрд)

> [72] Сергей М. © (18.04.12 09:15)
> оставшихся после "отсеивания" - 4 млрд)

Если каждый житель Земли попробует одну решётку, то шифр будет разгадан за 1 ход.

> [73] Inovet © (18.04.12 09:23)
> > [72] Сергей М. © (18.04.12 09:15)
> > оставшихся после "отсеивания" - 4 млрд)
>
> Если каждый житель Земли попробует одну решётку, то шифр
> будет разгадан за 1 ход.

Осталось только распределить решётки между ними.

← →
Очень злой (2012-04-22 20:56) [75]

нет их там,
видно же, что одно слово всего

> нет их там

Не исключено что извращенный разум кодера перед кодированием заменил пробелы на от балды выбранные буквы)

ну, значит, их нет

← →
Очень Злой (2012-04-24 12:12) [79]

>
> Не исключено что извращенный разум кодера перед кодированием
> заменил пробелы на от балды выбранные буквы)

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

Занимательная криптография Найти похожие ветки