(Untitled)

[gorkoff]

Не уверен, что с таким вопросом надо писать именно в это сообщество, но всё же...

Есть текст на русском языке, каждую букву заменили двумя цифрами в соответствии с её порядковым номером в алфавите (А - 01, Я -33). Под полученной строкой цифр записали другую строку, состоящую из некоторой периодической последовательности цифр (период не известен).

Comments

[roman_pro]

Некоторые слабости (возможно некритичные) заметны сразу:

* каждая нечётная цифра открытого текста может быть только 0,1,2,3 причём вероятность появления 3 достаточно мала (30,31,32,33). Отсюда следует возможность сокращения числа вариантов для перебора и возможность сузить пространство ключей:

для 1й цифры из примера:

т к ш
0+3=3
1+2=3
2+1=3
3+0=3

иными словами, ваш ключ начинается на 3,2,1 или 0, остальные варианты 1й цифры ключа невозможны. Причём можно оценить вероятность каждого варианта.
Для 3й цифры получаем:

т к ш
0+0=0
1+9=0
2+8=0
3+7=0

Т.е. либо 3я цифра ключа - 0, и тогда 2я буква открытого текста из набора "А-З"; либо 3я цифра ключа - 9,8,7. Остальные варианты отпадают.

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

* для больших объёмов осмысленного текста, можно воспользоваться частотным критерием появления пар цифр в открытом тексте.

* для осмысленного текста возможно отсечение невозможных соседних пар цифр, т.е. например использовать факт отсутствия удвоенных мягких знаков, etc.

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

0X - А,E,Ё
1X - И,О
2X - У
3X - Э,Ю,Я

Это первое что пришло на ум... возможно найдётся ещё чего, если покопать.

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

[gorkoff]

А вот за это спасибо.

[roman_pro]

Чуть-чуть проанализировал нечётные цифры. В примере - длина ключа - 22 цифры. Собственно, вот потенциальный ключ (каждая цифра заключена в квадратные скобки, [] -пустые квадратные скобки означают что анализ не производился, т.е. равносильно []=[0,1,2,3,4,5,6,7,8,9]):

[3,2][][9,8][][8][][1,0][][7][][8,7][][5,4][][4,3][][2][][5,4][][4,3][]

Иначе говоря, 5я цифра ключа - 8, 9я цифра ключа - 7. Для остальных нечётных осталось по 2 варианта

[gorkoff]

А откуда такая уверенность насчёт длины ключа?

[roman_pro]

Уверенности нет, но периодичность последовательности "на глаз" заметна, да и нестыковок вроде не вылезло пока. Будем считать что это предположение ;) Т.е. фразу выше следует читать как "Пока предполагаю, что длина ключа 22 цифры".

[gorkoff]

Я восхищаюсь вами. Два дня я смотрел на эту последовательность и нифига. А вам на глаз заметно...

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

[roman_pro]

Выписываем в столбик цифры шифртекста попарно. В квадратных скобках записываем возможные варианты для нечётных цифр ключа, на основании 1й цифры шифртекста в каждой паре. Алгоритм нахождения возможных комбинаций описывал выше. Дальше самое сложное - "на глаз" оценить повторяемость цифр в квадратных скобках по столбцам и вставить разрывы на границе последовательностей. Лично я зацепился за 3,9,9 в начале и 2,5,5 в конце. Попробовал разбить на группы по 11 строк, противоречий не вылезло. Затем, справа от скобок выписываем возможные цифры ключа, строя их пересечением с соответствующими наборами потенциальных цифр в каждой группе. Т.е. строки шифртекстов 38 и 51 имеют наборы [3,2,1,0] и [5,4,3,2] пересечением наборов являются те цифры, которые есть в обоих наборах. т.е. 3,2. Аналогично продолжаем отсекать двигаясь по остальным группам. В итоге в предпоследней группе (последняя - неполная) "выплывает" наиболее усечённое множество возможных нечётных цифр ключа. Результирующие множества выписаны для удобства внизу.

Собственно, простыня цифр:

38 [3,2,1,0] 3,2,1,0
03 [0,9,8,7] 0,9,8,7
95 [9,8,7,6] 9,8,7,6
36 [3,2,1,0] 3,2,1,0
99 [9,8,7,6] 9,8,7,6
84 [8,7,6,5] 8,7,6,5
55 [5,4,3,2] 5,4,3,2
53 [5,4,3,2] 5,4,3,2
22 [2,1,0,9] 2,1,0,9
65 [6,5,4,3] 6,5,4,3
69 [6,5,4,3] 6,5,4,3

51 [5,4,3,2] 3,2
90 [9,8,7,6] 9,8,7
97 [9,8,7,6] 9,8,7,6
25 [2,1,0,9] 2,1,0
07 [0,9,8,7] 9,8,7
06 [0,9,8,7] 9,8,7
65 [6,5,4,3] 5,4,3
68 [6,5,4,3] 5,4,3
54 [5,4,3,2] 2
59 [5,4,3,2] 5,4,3
67 [6,5,4,3] 6,5,4,3

41 [4,3,2,1] 3,2
99 [9,8,7,6] 9,8,7
97 [9,8,7,6] 9,8,7,6
21 [2,1,0,9] 2,1,0
78 [7,6,5,4] 7
99 [9,8,7,6] 9,8,7
69 [6,5,4,3] 5,4,3
47 [4,3,2,1] 4,3
52 [5,4,3,2] 2
77 [7,6,5,4] 5,4
58 [5,4,3,2] 5,4,3

58 [5,4,3,2] 3,2
15 [1,0,9,8] 9,8
91 [9,8,7,6] 9,8,7,6
28 [2,1,0,9] 2,1,0
80 [8,7,6,5] 7
86 [8,7,6,5] 8,7
69 [6,5,4,3] 5,4,3
59 [5,4,3,2] 4,3
47 [4,3,2,1] 2
67 [6,5,4,3] 5,4
60 [6,5,4,3] 5,4,3

43 [4,3,2,1] 3,2
01 [0,9,8,7] 9,8
88 [8,7,6,5] 8,7,6
23 [2,1,0,9] 2,1,0
70 [7,6,5,4] 7
92 [9,8,7,6] 8,7
79 [7,6,5,4] 5,4
49 [4,3,2,1] 4,3
27 [2,1,0,9] 2
77 [7,6,5,4] 5,4
40 [4,3,2,1] 4,3

54 [5,4,3,2] 3,2
14 [1,0,9,8] 9,8
12 [1,0,9,8] 8
16 [1,0,9,8] 1,0
76 [7,6,5,4] 7
92 [9,8,7,6] 8,7
65 [6,5,4,3] 5,4
51 [5,4,3,2] 4,3
53 [5,4,3,2] 2
77 [7,6,5,4] 5,4
53 [5,4,3,2] 4,3

41 [4,3,2,1] 3,2
03 [0,9,8,7] 9,8
02 [0,9,8,7] 8
21 [2,1,0,9] 1,0
85 [8,7,6,5] 7
95 [9,8,7,6] 8,7
69 [6,5,4,3] 5,4
52 [5,4,3,2] 4,3

=> [3,2]
=> [9,8]
=> [8]
=> [1,0]
=> [7]
=> [8,7]
=> [5,4]
=> [4,3]
=> [2]
=> [5,4]
=> [4,3]

[domage]

+1

[9000]

Не мешает ли вашим рассуждениям факт сложения номеров букв с непонятной последовательностью цифр?

[roman_pro]

Неа, не мешает :) Непонятная последовательность цифр вполне понятна и в народе зовётся ключом. К тому же в алгоритме ясно прописано как она используется, так что затруднений нет.

[9000]

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

Поясните, если не трудно, где я что упускаю?

[roman_pro]

Имея цифру шифртекста, соответствующую первой цифре номера буквы и зная, что она [первая цифра номера буквы] не превышает 3, получаем что у нас всего 4 возможных цифры ключа (вместо 10, если этот факт не брать во внимание), чтобы операция шифрования давала нужный шифртекст. Т.е. налицо сокращение неопределённости наших знаний о ключе. Далее, если узнать длину ключа, то может отказаться, что из шифртекстов, зашифрованных одной и той же цифрой ключа применение этого правила может дать слегка разные множества возможных цифр. Соответственно, реальная цифра ключа будет находиться в обоих множествах сразу, т.е. на их пересечении. Тем самым, ещё больше уменьшаем неопределённость знаний о ключе. Может оказаться, что в пересечении останется всего 1 элемент, это будет означать что мы нашли цифру ключа. Акелла конечно промахнулся с 22 цифрами ключа (их на деле только 11), но тем не менее, применение этого метода 2 цифры позволило вычислить, даже на такой ошибочной посылке.

[evilbot]

Хуясе мозг. :)

[roman_pro]

Да ладно ;)
Присоединяйся, коллективно вскроем это послание инопланетного разума.