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

Дешифрование - C++

Восстановить пароль Регистрация
 
milvus
0 / 0 / 0
Регистрация: 14.11.2012
Сообщений: 35
15.11.2013, 09:19     Дешифрование #1
У Страуструпа есть такие упражнения

Кликните здесь для просмотра всего текста
11. (*2) Напишите шифрующую программу, которая читает символы из cin и пишет их в cout в
зашифрованном виде. Можно использовать следующий простой метод шифрации: для символа s
зашифрованное представление получается в результате операции s^key[i], где key - массив
символов, передаваемый в командной строке. Символы из массива key используются в
циклическом порядке, пока не будет прочитан весь входной поток. Первоначальный текст
получается повторным применением той же операции с теми же элементами key. Если массив key
не задан (или задана пустая строка), шифрация не происходит.
12. (*3) Напишите программу, которая помогает дешифрировать текст, зашифрованный описанным
выше способом, когда ключ (т.е. массив key) неизвестен. Подсказка: см. D Kahn "The Codebreakers",
Macmillan, 1967, New York, стр. 207-213.

первое я сделал, а вот найти перевод книги не вышло, подскажите какой алгоритм есть для дешифрования без ключа?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
kpoxaa
70 / 31 / 1
Регистрация: 03.08.2012
Сообщений: 446
15.11.2013, 10:55     Дешифрование #2
Если что найдешь, отпиши здесь пожалуйста. Интересно...

Добавлено через 2 минуты
[cut]Вот тут идем какие-то предлагают в коментах
milvus
0 / 0 / 0
Регистрация: 14.11.2012
Сообщений: 35
15.11.2013, 22:46  [ТС]     Дешифрование #3
А я хотел по быстренькому сделать и читать дальше((
Я так понял что самый реальный для меня вариант это тоже как по той ссылке искать ключ методом подбора по одному символу добавляя в ключ, и сравнивая получившееся со словарем часто встречающихся слов из 5000 слов, самые удачные варианты показывать пользователю, и если он видит в результате смысл - то поиск закончен иначе продолжаем перебор вариантов ключей
Неужели нет чего нибудь более технологичного?
nefton
44 / 20 / 5
Регистрация: 28.02.2013
Сообщений: 184
16.11.2013, 01:03     Дешифрование #4
зависит от размера текста. Применимы ли статистические данные. Если текст большой - то можно подбирать длинну ключа и его элементы не перебором - а чтоб количество букв и пробелов приближалось к среднестатистичскому.
Тоесть допустим длинна N. Заполняем случайно key[]. Оптимизируем key[i] из соображений максимальной схожести текста. (вероятность встретить пробел к примеру или гласную). И так оптимизируем по очереди.
Очень скоро (наоченьмного быстрее перебора) найдём чтото похожее.

Добавлено через 11 минут
кстати, всё намного проще. Текстом является лишь по сути 24 буквы. А вот результатом операции ^ случайный байт. 0-255. Так что если key[i] выдаёт хоть гдето например символ ↨↑♀☼ или подобное - фтопку!

Добавлено через 2 минуты
п.с. Как Бьярн Страуструп в своём задании предполагает проверить насколько эффективна "помощь" программы?
milvus
0 / 0 / 0
Регистрация: 14.11.2012
Сообщений: 35
23.11.2013, 12:01  [ТС]     Дешифрование #5
Возникло два вопроса:
1) при кодировании английского текста с исп. английского ключа иногда получаются спец символы, и файл в который я записываю результат заканчивается раньше конца исходного текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void code(ifstream &src, ofstream &result, const char * kodeTable){
 
    size_t codeStackSize = strlen(kodeTable);
    int i = 0;
    char ch;
 
    while ( src.good() ) {
        src.get(ch);
        if (src.good())
            result << (ch^kodeTable[i%codeStackSize]);
                i++;
    }
 
}
Добавлено через 1 час 2 минуты
2) Я пытаюсь подобрать слово по частоте пробелов (любому другому символу)
Проблема в том что если кодовое слово нужной длинны (находится индексом совпадения) но случайное, обычные символы в декодированном тексте вообще не попадаются, и соответственно нет критерия для подбора ключевого слова по отдельной букве, можно только долбить случайную подстановку слова до тех пор пока не появится хоть один пробел?7
nefton
44 / 20 / 5
Регистрация: 28.02.2013
Сообщений: 184
24.11.2013, 15:32     Дешифрование #6
сформулируй из чего может состоять текст и кодовое слово.
да, если символ в тексте и кодовом слове одинаковый - то результатом ^ будет 0;
эту проблемку можно решить думаю если файл открыть бинарно, и в начале файла писать 4 байта uint32_t длинну файла. Либо чтоб множества символов текста и кодового слова не пересекались. (например текст маленькими, кодовое слово большими) (или на 128 смести вперёд кодовое слово)

Добавлено через 4 часа 9 минут
Писал писал.. что не получается даже кодировать файл по нормальному
вот что есть (неправильно!):
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
#include <iostream>
#include <cstdint>
#include <fstream>
#include <string>
 
 
using namespace std;
 
bool IsValid(uint8_t _char);
bool IsValidFile(uint8_t* file, int filesize, uint8_t* key, int key_size);
bool IsValidKeyUnit(uint8_t* file, int filesize, uint8_t* key, int key_size, int key_unit);
 
void Print(uint8_t* file, int filesize, uint8_t* key, int key_size);
 
int main(){
 
    fstream input_file;
    fstream output_file;
    uint8_t char_buff;
    string vibor;
    string filename;
    
 
    string to_do_option;
    cout<<"encode/decode: ";
    cin>>to_do_option;
 
    string input_key;
    if (to_do_option == "encode"){
        
        cout<<"choose input file: ";
        cin>>filename;
        input_file.open(filename.c_str(), fstream::in);
        if(!input_file) cout<<"error open input file\n";
        
        cout<<"choose output file: ";
        filename = "";
        cin>>filename;
        output_file.open(filename.c_str(), fstream::out|fstream::trunc);
        if(!output_file) cout<<"error open output file\n";
        
        cout<<"input key for coding: ";
        cin>>input_key;
        
        
        int key_index = 0;
        
        while (input_file.good()){
            char_buff = input_file.get();
            if (!IsValid(char_buff)) continue;
            char_buff ^= input_key[key_index];
            output_file<<(char)(char_buff);
            key_index++;
            if (key_index >= input_key.size()) key_index = 0;
        }
        cout<<"encoding completed\n";
    }
 
    if (to_do_option == "decode"){
 
        cout<<"choose input file: ";
        cin>>filename;
        input_file.open(filename.c_str(), fstream::in);
        if(!input_file) cout<<"error open input file\n";
 
        string in;
        while (input_file.good()){
            char_buff = input_file.get();
            in += char_buff;
        }
 
        
        int file_size = in.size();
        uint8_t* Memory_file = new uint8_t[in.size()];
        for (int i = 0; i < in.size(); i++) Memory_file[i] = in[i];
        
        for (int key_size = 1; key_size < 10; key_size++){
            cout<<"Key sise to try: "<<key_size<<endl;
 
            uint8_t* key = new uint8_t[key_size]; 
            bool is_valid_key = 0;
            
            for (int i = 0; i<key_size; i++) key[i] = 0;
            
    _continue:
            
            bool is_est_chto_dvigat_flag = 0;
            bool is_max_key_flag = 0;
            int key_index = 0;
 
            while (!is_max_key_flag){
                is_est_chto_dvigat_flag = 0;
                //Двигаем по очереди разряды вверх
                if (!IsValidKeyUnit(Memory_file, file_size, key, key_size, key_index)){
                    if (key[key_index] < 255) key[key_index]++;
                    is_est_chto_dvigat_flag = 1;
                }
    
                key_index++;
                if (key_index >= key_size) key_index = 0;
                
                //Проверяем не дошли ли до максимума
                is_max_key_flag = 1;
                for (int i = 0; i<key_size; ++i){
                    if (key[i] < 255){
                        is_max_key_flag = 0;
                        break;
                    }
                }
 
                //Проверяем не получился ли файл
                if (IsValidFile(Memory_file, file_size, key, key_size)){
                    Print(Memory_file, file_size, key, key_size);
                    cout<<"Prodolzit perebor? (1/0) ";
                    cin>>vibor;
                    if (vibor == "1") {
                        //Продолжаем перебор... както????????
                        //НЕВЕРНЫЙ ПОДХОД
                    
                            
                        goto _continue;
                    }
                }
            }
            
            
 
            delete key;
 
            cout<<"Perebor key razmerom "<<key_size<<" okonchen\n";
 
 
        }
 
    }
            
    cout<<"input anithing to end: ";
    cin>>vibor;
 
    return 0;
}
 
 
bool inline IsValid(uint8_t _char){
 
    if ((_char >= 32)&&(_char <= 126)) return 1;
    if (_char == 13) return 1; //<CR> конец строки
    if (_char == 10) return 1; //<LF>
    if (_char == 9) return 1; //<TAB> табуляция
    return 0;
}
 
bool IsValidFile(uint8_t* file, int filesize, uint8_t* key, int key_size){
 
    int key_index = 0;
    for (int file_index = 0; file_index < filesize-1; ++file_index){
        if (!IsValid(file[file_index]^key[key_index])) return 0;
        key_index++;
        if (key_index >= key_size) key_index = 0;
    }
    return 1;
}
bool IsValidKeyUnit(uint8_t* file, int filesize, uint8_t* key, int key_size, int key_unit){
        
    for (int file_index = key_unit; file_index < filesize-1; file_index+=key_size){
        if (!IsValid(file[file_index]^key[key_unit])) return 0;
    }
    return 1;
}
 
 
 
 
void Print(uint8_t* file, int filesize, uint8_t* key, int key_size){
 
    cout<<"Key: ";
    for (int i = 0; i<key_size; i++) cout<<key[i];
    
    cout<<"\nEncripted file:n";
    int key_index = 0;
    for (int file_index = 0; file_index < filesize; ++file_index){
        cout<<(char)(file[file_index]^key[key_index]);
        key_index++;
        if (key_index >= key_size) key_index = 0;
    }
    cout<<"\n-------------------------------------\n";
}
Но я понял зато как надо верно его расшифровывать.
1. Допустим ключь размером N (к примеру 10)
2. Для каждого элемента ключа определяются возможные значения
3. Как то перебираем все комбинации этих возможных значений (рекурсия, но я не программист и это для меня сложно )
milvus
0 / 0 / 0
Регистрация: 14.11.2012
Сообщений: 35
24.11.2013, 21:47  [ТС]     Дешифрование #7
Поделюсь тогда и я результатом, не знаю на сколько у меня грамотный подход
суть в том что длинну ключа мы определяем более-менее устойчиво
потом просто берем случайный ключь, проверяем результат посимвольно, если абракадабра то сразу генерим новый ключь, если нет то считаем все пробели и оцениваем их частоту, если она близка к теоретической - ключь найден
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
//code and decode if exist key
void code(ifstream &src, ofstream &result, const char * kodeTable){
 
    size_t codeStackSize = strlen(kodeTable);
    int i = 0;
    char ch;
 
    while ( src.good() ) {
        src.get(ch);
        if (src.good())
            result << (char)(ch^kodeTable[i%codeStackSize]);
        i++;
    }
}
 
//find key and decode
void decode(ifstream &src, ofstream &result){
    const int size_buf = 50000;
    const int max_key_size = 15;
//  const int iter_num = 1000000000;
    char buffer_src[size_buf];
    char buffer[size_buf];
    char ch;
    int frec_table[max_key_size];
 
    //READ FILE
    char * p = buffer_src;
    char * pp = buffer;
    while ( src.good() ) {
        src.get(ch);
        if (src.good()){
            *p++ = ch;
            *pp++ = ch;
        }
    }
    *= '\0';
    *pp = '\0';
    int text_size = strlen(buffer_src);
 
    //DETERM LENGTH OF KEY WORD
    for (int i=0; i<max_key_size; i++){
        //left cycle shift of string!
        ch = buffer[0];//char go to end of new buffer
        for (int j=0; j<text_size-1; j++){
            buffer[j] = buffer[j+1];
        }
        buffer[text_size-1] = ch;
        buffer[text_size] = '\0';
 
        //CALCULATE frec of ecuality src txt and shifted txt
        frec_table[i]=0;
        for (int j=0; j<text_size; j++){
            if (buffer[j] == buffer_src[j])
                frec_table[i]++; 
        }
        result << "frec[" << i+1 << "]=" << frec_table[i] << endl; 
    }
 
    //FIND local maximum
    int key_len = 0;
    float epsilon = 1.99f;
    if ( frec_table[1]*epsilon < frec_table[0]){
        key_len = 1;
    } else {
        for (int i=1; i<max_key_size; i++){
            if ( frec_table[i+1] > frec_table[i]*epsilon){
                key_len = i+2;
                break;
            }
        }
    }
    result << "size of text = " << text_size << endl; 
    result << "calc key len = " << key_len << endl; 
    cout << "size of text = " << text_size << endl;
    cout << "calc key len = " << key_len << endl; 
 
//  cout << (int)'А' << ' ' << (int)'Я' << ' ' << (int)'а' << ' ' << (int)'я' << endl;
//  cout << (int)'A' << ' ' << (int)'Z' << ' ' << (int)'a' << ' ' << (int)'z' << endl;
//  cout << (int)' ' << ' ' << (int)'\t' << ' ' << (int)'\n' << ' ' << (int)'\v' << endl;
 
    //FIND KEY! (FROM FREC OF ' ' = 0.178609)
    char key[max_key_size];
    char key_tmp[max_key_size];
        key_tmp[0] = '\0';
    float sp_frec = 0.178609f;
    //maching key
    srand(time(NULL));
    int mach_count=0;
    float delta=0;
    float delta_min=1;
 
//  for (int i = 0; i<iter_num; i++){
    long int i = 0;
    while (delta_min > 0.01f){
        if (i%(iter_num/100) == (iter_num/100-1))
            cout << i/(iter_num/100) + 1 << '%' << endl;
 
        //INIT KEY
        for (int key_i = 0; key_i < key_len ; key_i++){
            key[key_i] = rand()%64 + 'А';
        }
        key[key_len] = '\0';
        mach_count=0;
        //DECODE WITH CURRENT KEY
        for (int j=0; j<text_size-1; j++){
            buffer[j] = buffer_src[j]^key[j%key_len];
            //IF IN TEXT INCORRECT SYMBOL
            if (    (buffer[j] < -111 & buffer[j] != -123)
            ||  (buffer[j] > -105 & buffer[j] < 9) 
            ||  (buffer[j] > 12 & buffer[j] < 32) 
            ||  (buffer[j] > 126) ){
                mach_count = 0;
                break;
            }
            if (buffer[j] == ' ')
                mach_count++;
        }
        //Exam result
        if (mach_count != 0)
            delta = sp_frec - (mach_count*1.0f)/(text_size*1.0f);
        else
            delta = 1;
        if (delta<0) delta = -delta;
        if (delta_min > delta) {
            delta_min = delta;
            strcpy(key_tmp, key);
            result << "key = " << key_tmp << ' ' << mach_count << ' ' << i << ' ' << delta << endl;
        }
        i++;
    }
 
    result << "RES key = " << key_tmp << endl;
    cout << "RES key = " << key_tmp << endl;
 
    //DECODE WITH TRUE KEY
    for (int j=0; j<text_size-1; j++){
        result << (char)(buffer_src[j]^key_tmp[j%key_len]);
    }
}
Знаю что плохо с размером массивов намутил, но пока главное принцип,
ключевое слово из 3 букв ищет в среднем за 10-100 тыс случ итераций
а вот уже с 4 буквами не всегда хватает и миллиарда итераций
из 6 букв не находил вообще ни разу

Добавлено через 6 часов 4 минуты
Есть идеи как повысить эффективность алгоритма? Я так понял есть возможность статистически определять не только длину ключа но и наиболее вероятные буквы в ключе, может кто подскажет как?
nefton
44 / 20 / 5
Регистрация: 28.02.2013
Сообщений: 184
25.11.2013, 12:42     Дешифрование #8
Я ж написал. Первое что надо для решения ЛЮБОЙ задачи - формализовать. Опиши конкретно входящий текст и ключь. Если текст сравнительно большой (скажем 100 ключей) и там только разумные буквы, цыфры и препинания то я оцениваю возможности в 20 значный ключь за секунду.
milvus
0 / 0 / 0
Регистрация: 14.11.2012
Сообщений: 35
25.11.2013, 23:13  [ТС]     Дешифрование #9
текст у меня для примера в 15 тыс символов, английские буквы заглавные и строчные и знаки препинания, плюс всякие тире и значки троеточия есть, ключь из русских букв, чтобы не получался символ 0,
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.11.2013, 23:30     Дешифрование
Еще ссылки по теме:

XOR шифрование/дешифрование C++
C++ Шифрование/Дешифрование
C++ Шифрование / дешифрование методом Цезаря

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

Или воспользуйтесь поиском по форуму:
ssXXss
263 / 185 / 10
Регистрация: 15.01.2011
Сообщений: 668
25.11.2013, 23:30     Дешифрование #10
посмотрите Практическая криптография Алгоритмы и их программирование А.В.Аграновский и Прикладная криптография 2-е издание Брюс Шнайер протоколы ,алгоритмы и исходные тексты на языке с. там куча примеров. и в сети найти можно.

Yandex
Объявления
25.11.2013, 23:30     Дешифрование
Ответ Создать тему
Опции темы

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