Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.62
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
#1

un XOR без ключа - C++

02.06.2011, 22:45. Просмотров 1653. Ответов 9
Метки нет (Все метки)

опять же по Страуструпу задание. написать прогу ксорящую текст с ключом, затем расшифровывающую данный ксоренный тескт с ключом. Но потом все слегка усложняется, надо написать прогу расшифровываюзую ксоренный тескт НЕ зная ключа. Страуструп дает подсказки - типа читайте "взломщики коднов страница такая то", далее столпы крипто пишут что это практически шифр виженера и вскрыватся ПК за секунды. Предлагается слелующий адгоритм - мы берем ксореный текст и делаем опять XOR c самим собой смещая постепенно относительно себя и считаем совпавшие байты. когад появятся всплески совпавших байт и их будет более не помню скольки процентов - мы нашли величину кратную длину ключа. ксорим шифр со смещением и освобождаемся от ключа - получаем шифрованный текст без ключа. ну а далее типа анализ....зная особенности избыточности языков например часто встречается буква е, там, а - подставляем буквы вместо символов с той же частотой. так вот. ЗАТЫК на участке поиска совпадений.
Разработал несколько вариантов смещений - это просто сдвиг на один символ и битовый сдвиг, поскольку так и не понял какое конкретно смещение имели ввиду столпы криптографии. прога шуршит, катае в файлы по 20 смещений 2х видов. Далее я смотрю файлы. и..... о ДА смещения есть, НО - поскольку я тот кто шифровал текст, то я и знаю длину ключа и тут ни фига не совпадает.всплески совпавших байт есть но они нестабильны, нет закономерности...Обращаюсь к экспертам. вы уже давно в мире С++, может приходилось вам успешно решить данную задачу?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.06.2011, 22:45     un XOR без ключа
Посмотрите здесь:

C++ Шифрование Xor'ом
C++ оператор XOR
xor, not C++
Оператор xor C++
Xor encrypt C++
C++ расшифровка текста без ключа
C++ быстрый xor
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
03.06.2011, 08:39     un XOR без ключа #2
Для расшифровки ксора без знания ключа, нужен валидатор результат попытки расшифорвки с предполагаемым клюм. При наличии такого валидатора просто пробуй все ключи подряд, пока не получишь валидный резульат, например, читабельный текст.
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
03.06.2011, 08:57  [ТС]     un XOR без ключа #3
позвольтес, но ведь это будет простой перебор. В книжках же напирают на интеллектуальтный анализ.

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

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

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

мы не берем случай когда ключ с ксором огромен, а случай когда ключ равен длине текста вообще считается неуязвимым без знания ключа. это мы не берем.
Тут столько народу опытного. понимаю, что на данную задачу - надо потратить время (на кой это делать?), но просто думал что может кому интересно и кто то тоже читал эти книги.
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
03.06.2011, 09:23     un XOR без ключа #4
Было:
8B 97 B6 D7 99 DA 8A D8 6C 9F A4 62 6F 4B E3 0E
F5 45 61 79 C9 CF 86 7A 90 64 EC D5 12 56 16 A5
05 5D D4 F4 C6 23 DD DD F9 78 CB CC 75 84 C7 AD
1E B7 A3 94 24 89 F0 C1 85 1B 69 78 43 2F C5 BB
74 37 90 22 04 52 9D 26 9C 38 9D 62 F0 E6 AD 72
5B 9C 6F E6 B1 19 0F F7 AA A6 AB 2B 35 5B 20 BF
50 9A 5C 52 91 09 6F A1 FC F4 1A A6 35 A1 29 FD
A6 94 40 69 76 79 3E 9E 28 56 1C AC A7 50 23 C6
32 F2 5E A8 D1 03 18 9E D5 AB 18 F7 F8 DF 77 81
F9 0E 9A 73 BC 05 09 70 48 F9 1E 5B 4B 7A 1E AF
51 E0 69 EA 10 37 B0 90 90 DC 43 81 85 E9 17 EA
92 15 EC 46 51 02 AA D6 21 A5 B6 D6 49 43 2E 65
95 8C 05 2A D3 5E 01 25 AC 91 44 B3 BB 49 F5 6E
3F C0 92 65 96 E4 91 A2 38 E3 F2 AD 72 72 D7 F9
B2 1D 4B C3 CF 69 65 AC E0 3F 94 4F E0 F6 B0 96
B8 A8 7F 87 F3 3A A4 64 6C 9D 9A 79 04 77 4C B6
, после ксорки с DE 46 A2 E4 стало
55 D1 14 33 47 9C 28 3C B2 D9 06 86 B1 0D 41 EA
2B 03 C3 9D 17 89 24 9E 4E 22 4E 31 CC 10 B4 41
DB 1B 76 10 18 65 7F 39 27 3E 69 28 AB C2 65 49
C0 F1 01 70 FA CF 52 25 5B 5D CB 9C 9D 69 67 5F
AA 71 32 C6 DA 14 3F C2 42 7E 3F 86 2E A0 0F 96
85 DA CD 02 6F 5F AD 13 74 E0 09 CF EB 1D 82 5B
8E DC FE B6 4F 4F CD 45 22 B2 B8 42 EB E7 8B 19
78 D2 E2 8D A8 3F 9C 7A F6 10 BE 48 79 16 81 22
EC B4 FC 4C 0F 45 BA 7A 0B ED BA 13 26 99 D5 65
27 48 38 97 62 43 AB 94 96 BF BC BF 95 3C BC 4B
8F A6 CB 0E CE 71 12 74 4E 9A E1 65 5B AF B5 0E
4C 53 4E A2 8F 44 08 32 FF E3 14 32 97 05 8C 81
4B CA A7 CE 0D 18 A3 C1 72 D7 E6 57 65 0F 57 8A
E1 86 30 81 48 A2 33 46 E6 A5 50 49 AC 34 75 1D
6C 5B E9 27 11 2F C7 48 3E 79 36 AB 3E B0 12 72
66 EE DD 63 2D 7C 06 80 B2 DB 38 9D DA 31 EE 52
, ксорим этот текст с собой со сдвигом на 4:
12 4D 3C 0F F5 45 2E BA 03 D4 47 6C 9A 0E 82 77
3C 8A E7 03 59 AB 6A AF 82 32 FA 70 17 0B C2 51
C3 7E 09 29 3F 5B 16 11 8C FC 0C 61 6B 33 64 39
3A 3E 53 55 A1 92 99 B9 C6 34 AC C3 37 18 55 99
70 65 0D 04 98 6A 00 44 6C DE 30 10 AB 7A C2 94
EA 85 60 11 1B BF A4 DC 9F FD 8B 94 65 C1 7C ED
C1 93 33 F3 6D FD 75 07 C9 55 33 5B 93 35 69 94
D0 ED 7E F7 5E 2F 22 32 8F 06 3F 6A 95 A2 7D 6E
E3 F1 46 36 04 A8 00 69 2D 74 6F 76 01 D1 ED F2
45 0B 93 03 F4 FC 17 2B 03 83 00 F4 1A 9A 77 45
41 D7 D9 7A 80 EB F3 11 15 35 54 6B 17 FC FB AC
C3 17 46 90 70 A7 1C 00 68 E6 98 B3 DC CF 2B 4F
46 D2 04 0F 7F CF 45 96 17 D8 B1 DD 84 89 67 0B
A9 24 03 C7 AE 07 63 0F 4A 91 25 54 C0 6F 9C 3A
7D 74 2E 6F 2F 56 F1 E3 00 C9 24 D9 58 5E CF 11
4B 92 DB E3 9F A7 3E 1D 68 EA D6 CF 51 A6 58 85
.

Добавлено через 13 минут
Найди как хоть один повтор через 4 символа! Повтор будет наблюдаться только в том случае, если через длину ключа повтоярются символы исходного текста. При длине ключа в 1 байт и в 1 символ анализ такой: гарантировно близко повторяемый символ - пробел. Перебираем повторяемые на роль пробела. Тогда, даже при неизвестной кодировке и невозможнсоти пямого вычисления ключа ксоркой с пробелом получаем предположительные длины слов. Однобуквенных слов относительно немного: только союзы и предлоги. Двухбуквенных тоже относительно мало и все они известны. Также мало и трёхбуквенных. Если даже учесть тире и числа, то всё равно вариантов не много, особенно односимвольных. Предполагая определённые буквы, можно их подставлять в отальнйо текст. Даже в духбуквенных они будут повторяться: слова "и" и "из"; "а", "за", и "да"; "о" и "он". Обрати внимание, что с этими буквами сочетаются не все другие буквы. Теперь подставляем их. Плюс можно юзить частотные таблицы языка. А если ключ длинее символа? Кроме перебора, пусть даже направленного, выриантов нет, иначе это вообще не шифр.
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
03.06.2011, 10:20  [ТС]     un XOR без ключа #5
хм....обоснованно. Мы не об одном и том же? если последовательно двигать шифротекст и ксорить с самим собой, мы должны будем рано или поздно натолкнуться на повторы (их будет более 6% по моему)
т.е. текст должен быть крупным - так пишут в книжках. ты насколько я понял доказал на данном примере обратное? что даже зная длину ключа и сместив на эту цифру шифротекст и ксорив с собой мы НЕ видим повторов?

Как ты делал смещение? просто по символам или битовый сдвиг?

Добавлено через 9 минут
по моему важный момент. не надо искать повторы с длиной через 4. надо просто искать повторы если они есть. то та величина на которую смещали кратна длине. т.е. во втором варианте то что помечено красным это не оно. надо вообще на предмет повторов кусок прогнать. я прав?
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
26.08.2011, 13:27  [ТС]     un XOR без ключа #6
Цитата Сообщение от AzaKendler Посмотреть сообщение
ни фига не совпадает
позднее я понял что считал эти совпадения не там. Страуструп дает непростые задания особенно непросты они для людей севших учить С++ с нуля. Пока вернуться недосуг к заданию. Но taras atavin считает что это все фигня что пишут и в результате нужен все равно тупой перебор. Хотя я согласен с ним. если при ксоре длина ключа равна длине текста - анализ невозможен.
fasked
Эксперт C++
4932 / 2512 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
26.08.2011, 13:42     un XOR без ключа #7
Цитата Сообщение от AzaKendler Посмотреть сообщение
надо просто искать повторы если они есть
Именно по смещению ключа, потому что разные символы открытого текста могут дать одинаковые символы в шифротексте, так как шифруются на разных символах ключа. (Слово "символ" в данном контексте условно).

Сейчас я попробую вкратце описать подобный "криптоанализ" :)
Допустим имеется открытый исходный текст:
Код
арозаупаланалапуазора
Допустим мы имеем ключ длиной в два символа (для простоты примера). В принципе нам не важно какой именно ключ и какой шифротекст будет после преобразования. Важно то, что определенные символызашифруются с повторами. Разобьем открытый текст на части, длины которых равны длине ключа.
Код
1     1   2  2  2  2    1     2
ар оз ау па ла на ла пу аз ор а
Цифрами отмечены те символы, которые в шифротексте будут одинаковыми. Хоть это и одна и та же буква. В шифротексте символ "а", помеченный 1-цей, будет отличаться от символа "а", помеченного 2-кой.

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

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include <string.h>
 
int main() {
    unsigned char buf[BUFSIZ] = "арозаупаланалапуазора";
    unsigned char key[BUFSIZ] = { 10, 45 };
    int i, j, keylen = strlen(key), buflen = strlen(buf);
 
    for (i = 0; i < buflen; i += keylen) {
        for (j = 0; j < keylen; ++j) {
            buf[i + j] ^= key[j];
        }
    }
 
    for (i = 0; i < buflen; ++i) {
        printf("%#2X%s", buf[i], (i + 1) % 2 ? " " : "\n");
    }
 
    return 0;
}
Код
0XDA 0X9D
0XDB 0XAD
0XDA 0X93
0XDA 0X9A
0XDA 0X9D
0XDB 0XAE
0XDA 0X92
0XDA 0X9D
0XDA 0X96
0XDA 0X9D
0XDA 0X90
0XDA 0X9D
0XDA 0X96
0XDA 0X9D
0XDA 0X92
0XDB 0XAE
0XDA 0X9D
0XDA 0X9A
0XDA 0X93
0XDB 0XAD
0XDA 0X9D
Посмотрите сколько значений 0xDA в первом стлбце и 0x9D во втором столбце - это все символы "а" в открытом тексте.
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
26.08.2011, 14:03  [ТС]     un XOR без ключа #8
fasked, мне стыдно призаться но явсе же сделаю ЭТО. Я смотрел повторы в текстовом файле а не в хекс редакторе тогда. Позже я понял это но к тому моменту выполнялись уже другие задания. А в это осталось только создать хранилище русских букв и алгоритм подстанова их в места повторов.Так что думаю ПК и правда способен быстро разксорить с приемлемой точностью при вменяемой длине ключа. Проделав все опреации по аналогии с вскрытием шифра виженера, теоретически можно получить ответ.
С форума добровольно уходить не собираюсь так что..давай я освоюсь немного в языке и мы сыграем в эту игру? Что скажешь? Шлем друг другу заксоренный текст и расшифровываем. сейчас я не готов. Я не осилил до конца даже книгу по стандарту от создателя.
easybudda
Эксперт С++
9412 / 5435 / 917
Регистрация: 25.07.2009
Сообщений: 10,428
26.08.2011, 16:58     un XOR без ключа #9
Цитата Сообщение от fasked Посмотреть сообщение
C
1
2
unsigned char key[BUFSIZ] = { 10, 45 }; 
int keylen = strlen(key); /*...*/
И чему же, интересно, это keylen равно будет?

...
Дошло! Остальная часть массива нулями инициализируется, всё правильно с этим.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.08.2011, 17:07     un XOR без ключа
Еще ссылки по теме:

XOR without XOR C++
XOR пароля C++
C++ XOR шифрование
C++ XOR шифрование
XOR Шифратор C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
fasked
Эксперт C++
4932 / 2512 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
26.08.2011, 17:07     un XOR без ключа #10
easybudda, да здесь и выход за границы массива может иметь место... главное, что пример достиг своей цели
Yandex
Объявления
26.08.2011, 17:07     un XOR без ключа
Ответ Создать тему
Опции темы

Текущее время: 01:58. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru