Доброго времени суток, дорогие читатели и посетители! Сегодня небольшое погружение в мир криптографии и шифрования. Для меня эта область представляет некоторый интерес. А в целом, знать об этом нужно! В нашем цифровом веке без шифрования все уже давно бы рухнуло, ваша почта шифруется, ваши фото шифруются(в России вряд ли, но все же), ваши переписки тоже шифруются. В идеальном интернете шифроваться должно вообще все, особенно любая финансовая информация. Финансы защищены даже лучше, чем личная жизнь. В любом случае, сегодня полезно хотя бы примерно знать, как это все работает. Для начала, предлагаю посмотреть на мою реализацию самого простого из шифров. А там и до RSA доберемся, поехали!
Прежде чем продолжить чтение, обратите внимание на реализации других шифров
- Реализация и взлом шифра Цезаря;
- Реализация и взлом шифра простой перестановки;
- Реализация и взлом шифра гаммирования;
- Реализация и взлом шифра простой замены.
Шифр простого сдвига
Так же известен под названием «Шифр Цезаря». Это шифр простой подстановки, при шифровании каждый символ текста заменяется символом, находящимся на некотором постоянном расстоянии левее или правее в алфавите. Наглядно на картинке из вики:
Обратная процедура расшифровки выполняется аналогично.
Со взломом уже поинтереснее. Я реализовал частотный анализ для взлома шифра цезаря. В двух словах суть можно описать следующим образом. Необходимо сравнить частоты появления символов в шифре с эталонными. И на основе этого сделать вывод, в какую сторону был смещен алфавит. Я собираю все возможные сдвиги и беру в качестве результирующего самый часто встречающийся. Мой взлом отгадывает сдвиг почти со 100% вероятностью при достаточно больших текстах. Кстати, для тестов брал текст из библии вот здесь. По теории больше сказать нечего, сразу перейдем к реализации.
Реализация простого шифра сдвига на C++
C++ был выбран в качестве языка программирования по привычке. Во время написания программы, я понял, что проще было бы использовать интерпретируемый язык, например, Python. Но не бросать же дело на полпути?
Консольная программа, на вход принимает два файла, с открытым текстом и файл для шифра. Простенький интерфейс, код которого приведу в самом конце, спросит у нас нужное действие и вызовет соответствующую процедуру.
Используемые библиотеки
#include <iostream> #include <vector> #include <fstream> #include <algorithm>
Теперь к самому алгоритму.
Функция шифрования
Текст шифруется с помощью сдвигов по ascii таблице, отдельно обрабатываются случаи выхода за пределы таблицы. Пробелы и прочие символы пропускаются. Проверка на такой символ осуществляется с помощью функции bool checkChar(char c).
На вход: имя файла с открытым текстом, имя файла для шифра, значение смещения.
На выходе: ничего.
bool checkChar(char c) {
if(c == ' ' || c == '.' || c == ',' ||
c == '!' || c == '?' || c == ':' ||
c == ';') {
return true;
}
else {
return false;
}
}
void encrypt(string inFileName, string outFileName, int offset) {
ifstream inFile(inFileName.c_str());
//Считываем текст
vector<string> text;
while(true) {
string str;
inFile >> str;
if(inFile.eof()) {
break;
}
text.push_back(str);
}
inFile.close();
//Шифрование
vector<string> code;
for(unsigned int i = 0; i < text.size(); i++) {
string codeStr;
for(unsigned int j = 0; j < text[i].length(); j++) {
if(checkChar(text[i][j])) {
codeStr.push_back(text[i][j]);
}
else {
unsigned char symb = text[i][j] + offset;
//Если вылезли за таблицу
if(symb > 'z') {
symb = 'a' + (symb - 'z') - 1;
codeStr.push_back(symb);
}
else if(symb < 'a') {
symb = 'z' - ('a' - symb) + 1;
codeStr.push_back(symb);
}
else {
codeStr.push_back(symb);
}
}
}
code.push_back(codeStr);
}
//Записываем в файл
ofstream outFile(outFileName.c_str());
for(unsigned int i = 0; i < code.size(); i++) {
outFile << code[i] << endl;
}
outFile.close();
return;
}
Функция расшифровки
Шифр очень простой, поэтому расшифровка работает аналогично шифрованию. Символы сдвигаются обратно по алфавиту.
На вход: имя файла с шифром, имя файла для текста, значение смещения.
На выходе: ничего.
bool checkChar(char c) {
if(c == ' ' || c == '.' || c == ',' ||
c == '!' || c == '?' || c == ':' ||
c == ';') {
return true;
}
else {
return false;
}
}
void decrypt(string inFileName, string outFileName, int offset) {
ifstream inFile(inFileName.c_str());
//Считываем код
vector<string> code;
while(true) {
string str;
inFile >> str;
if(inFile.eof()) {
break;
}
code.push_back(str);
}
inFile.close();
//Дешифровка
vector<string> text;
for(unsigned int i = 0; i < code.size(); i++) {
string textStr;
for(unsigned int j = 0; j < code[i].length(); j++) {
if(checkChar(code[i][j])) {
textStr.push_back(code[i][j]);
}
else {
unsigned char symb = code[i][j] - offset;
//Если вылезли за таблицу
if(symb < 'a') {
symb = 'z' - ('a' - symb) + 1;
textStr.push_back(symb);
}
else if(symb > 'z') {
symb = 'a' + (symb - 'z') - 1;
textStr.push_back(symb);
}
else {
textStr.push_back(symb);
}
}
}
text.push_back(textStr);
}
//Записываем в файл
ofstream outFile(outFileName.c_str());
for(unsigned int i = 0; i < text.size(); i++) {
outFile << text[i] << endl;
}
outFile.close();
return;
}
Функция взлома
Добрались до интересного. Скажу сразу, чужих реализаций я не смотрел, писал по наитию, опираясь на статью из википедии. Получился неплохой результат. Как я уже говорил, в большинстве случаев, при большой длине текста, мой алгоритм угадывает смещение. Очень слабое место это переменная deff, которая отвечает за интервал, в который нужно попасть символу. И функция получилась очень уж громоздкой, у меня есть подозрения, что на Питоне можно было написать покороче. Но, в любом случае, она работает.
На вход: имя файла с шифром, имя файла для текста.
На выходе: ничего, программа определяет смещение(с которым был зашифрован текст) и совершает дешифровку.
#define ALPH_SIZE 26
void initFreq(vector<pair<char, double> > &F) {
/*источник: http://enghelp.ru/the_alphabet/687-chastota-vstrechaemosti-bukv.html */
F.push_back(make_pair('a', 8.17));
F.push_back(make_pair('b', 1.49));
F.push_back(make_pair('c', 2.78));
F.push_back(make_pair('d', 4.25));
F.push_back(make_pair('e', 12.70));
F.push_back(make_pair('f', 2.23));
F.push_back(make_pair('g', 2.02));
F.push_back(make_pair('h', 6.09));
F.push_back(make_pair('i', 6.97));
F.push_back(make_pair('j', 0.15));
F.push_back(make_pair('k', 0.77));
F.push_back(make_pair('l', 4.03));
F.push_back(make_pair('m', 2.41));
F.push_back(make_pair('n', 6.75));
F.push_back(make_pair('o', 7.51));
F.push_back(make_pair('p', 1.93));
F.push_back(make_pair('q', 0.10));
F.push_back(make_pair('r', 5.99));
F.push_back(make_pair('s', 6.33));
F.push_back(make_pair('t', 9.06));
F.push_back(make_pair('u', 2.76));
F.push_back(make_pair('v', 0.98));
F.push_back(make_pair('w', 2.36));
F.push_back(make_pair('x', 0.15));
F.push_back(make_pair('y', 1.97));
F.push_back(make_pair('z', 0.07));
return;
}
void hack(string inFileName, string outFileName) {
vector<pair<char, double> > standFreq;
initFreq(standFreq);
vector<pair<char, double> > currentFreq(ALPH_SIZE);
char symb = 'a';
for(unsigned int i = 0; i < ALPH_SIZE; i++) {
currentFreq[i].first = symb;
currentFreq[i].second = 0.0;
symb++;
}
ifstream inFile(inFileName.c_str());
//Считываем код
vector<string> code;
while(true) {
string str;
inFile >> str;
if(inFile.eof()) {
break;
}
code.push_back(str);
}
inFile.close();
//Посчитать частоту символов
//Всего символов
int symbCount = 0;
for(unsigned int i = 0; i < code.size(); i++) {
for(unsigned int j = 0; j < code[i].length(); j++) {
if(checkChar(code[i][j])) {
continue;
}
else {
symbCount++;
for(unsigned int k = 0; k < ALPH_SIZE; k++) {
if(code[i][j] == currentFreq[k].first) {
//Одновременно считать количество символов в тексте
currentFreq[k].second += 1.0;
break;
}
}
}
}
}
//Текущая частота каждого
for(unsigned int i = 0; i < ALPH_SIZE; i++) {
currentFreq[i].second = (currentFreq[i].second / symbCount) * 100.0;
}
//Сравнить со стандартной частотой
double deff = 0.25; //Допустимое отклонение
vector<int> slides;
for(unsigned int i = 0; i < ALPH_SIZE; i++) {
for(unsigned int j = 0; j < ALPH_SIZE; j++) {
if(currentFreq[i].second >= (standFreq[j].second - deff) &&
currentFreq[i].second <= (standFreq[j].second + deff)) {
//Запоминаем возможный сдвиг
slides.push_back(currentFreq[i].first - standFreq[j].first);
}
}
}
//Выбираем смещение
sort(slides.begin(), slides.end());
int count = 0;
int maxCount = count;
int slide = 0;
for(unsigned int i = 1; i < slides.size(); i++) {
if(slides[i-1] == slides[i]) {
count++;
}
else {
if(count > maxCount) {
maxCount = count;
slide = slides[i-1];
}
count = 0;
}
}
cout << "slide = " << slide << endl;
//Дешифровать с использованием найденного смещения
vector<string> text;
for(unsigned int i = 0; i < code.size(); i++) {
string textStr;
for(unsigned int j = 0; j < code[i].length(); j++) {
if(checkChar(code[i][j])) {
textStr.push_back(code[i][j]);
}
else {
unsigned char symb = code[i][j] - slide;
//Если вылезли за таблицу
if(symb < 'a') {
symb = 'z' - ('a' - symb) + 1;
textStr.push_back(symb);
}
else if(symb > 'z'){
symb = 'a' + (symb - 'z') - 1;
textStr.push_back(symb);
}
else {
textStr.push_back(symb);
}
}
}
text.push_back(textStr);
}
//Записываем в файл
ofstream outFile(outFileName.c_str());
for(unsigned int i = 0; i < text.size(); i++) {
outFile << text[i] << endl;
}
outFile.close();
return;
}
Интерфейс программы
Консольный. Команд всего четыре: encrypt, decrypt, hack, exit. Из названия легко угадывается действие. Интерфейс выглядит вот так:
Реализация:
int main() {
while(true) {
cout << "encrypt, decrypt, hack, exit:" << endl;
string action;
cin >> action;
if(action == "encrypt") {
cout << "input file:" << endl;
string inFileName;
cin >> inFileName;
cout << "output file:" << endl;
string outFileName;
cin >> outFileName;
cout << "offset:" << endl;
int offset;
cin >> offset;
encrypt(inFileName, outFileName, offset);
}
else if(action == "decrypt") {
cout << "input file:" << endl;
string inFileName;
cin >> inFileName;
cout << "output file:" << endl;
string outFileName;
cin >> outFileName;
cout << "offset:" << endl;
int offset;
cin >> offset;
decrypt(inFileName, outFileName, offset);
}
else if(action == "hack") {
cout << "input file:" << endl;
string inFileName;
cin >> inFileName;
cout << "output file:" << endl;
string outFileName;
cin >> outFileName;
hack(inFileName, outFileName);
}
else if(action == "exit") {
break;
}
else {
cout << "wrong action" << endl;
}
}
return 0;
}
Заключение
В заключении можно сказать, что это только начало. Я буду реализовывать и другие аогоритмы шифрования. От простых к более сложным. Возможно, однажды, я перейду на Python вместо C++. Интерпретируемый язык для шифрования подходит больше. На этом все, спасибо за внимание!