(Untitled)

[gorkoff]

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

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

Comments

[vilgeforce]

А вопрос в чем?

Если требуется восстановить исходный текст без ключа - это, думаю, малореально: по сумме нельзя восстановить слагаемые.

[gorkoff]

Вот и я так думаю.

[borzig]

для верности эту строку надо хешировать

[domage]

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

[gorkoff]

Спасибо. Всё что мне говорят в сообществе просто подтверждает мои собственные мысли на эту тему.

[9000]

+1
при малой длине ключа и большом тексте есть шанс подобрать длину и победить статистикой встречаемости букв + словарём. если наоборот - безнадёжно, хотя не исключён теоретически и вариант false positive :)

[stiver_rus]

>>Ну при знании ключа строка восстанавливается однозначно, что радует.

Это с какой же радости? Читайте внимательнее: букв 33, а делим на 10.

Вот тут http://community.livejournal.com/ru_algorithms/70933.html вполне прилично ответили.

[lamed]

Эта штука называется "Шифр Вижинера". Вскрывается дифференциальным криптоанализом. Если длина периода небольшая, можно просто их перебрать и частотным методом попробовать вскрыть для каждой длины.

[gorkoff]

Знаю про Вижинера. Читал. Но там нет остатка од деления на 10.

[9000]

Поскольку букв всего 33, вариантов остатков от деления немного, есть шанс просто перебрать все комбинации.

[lamed]

Есть. Там сложение по основанию системы счисления. Какая система счисления - не важно.

Я ведь правильно понял: складываются по модулю 10 цифры, а не числа, состоящие из двух цифр? Значит, все правильно.

Кстати, в данном случае в алгоритме есть слабина: первая цифра номера буквы может быть только от 0 до 3, что дает дополнительную информацию о ключе.

[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 раз), потому как, после начала следующего периода нечётные цифры ключа "лягут" на чётные цифры открытого текста

[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]

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