Project Euler 59

各文字はそれぞれ一意のコードに割り当てられている. よく使われる標準としてASCII (American Standard Code for Information Interchange) がある. ASCIIでは, 大文字A = 65, アスタリスク (*) = 42, 小文字k = 107というふうに割り当てられている.

モダンな暗号化の方法として, テキストファイルの各バイトをASCIIに変換し, 秘密鍵から計算された値とXORを取るという手法がある. XOR関数の良い点は, 暗号化に用いたのと同じ暗号化鍵でXORを取ると平文を復号できる点である. 65 XOR 42 = 107であり, 107 XOR 42 = 65である.

破られない暗号化のためには, 鍵は平文と同じ長さのランダムなバイト列でなければならない. ユーザーは暗号文と暗号化鍵を別々の場所に保存する必要がある. また, もし一方が失われると, 暗号文を復号することは不可能になる.

悲しいかな, この手法はほとんどのユーザーにとって非現実的である. そこで, 鍵の変わりにパスワードを用いる手法が用いられる. パスワードが平文より短ければ (よくあることだが), パスワードは鍵として繰り返し用いられる. この手法では, 安全性を保つために十分長いパスワードを用いる必要があるが, 記憶するためにはある程度短くないといけない.

この問題での課題は簡単になっている. 暗号化鍵は3文字の小文字である. cipher1.txtは暗号化されたASCIIのコードを含んでいる. また, 平文はよく用いられる英単語を含んでいる. この暗号文を復号し, 平文のASCIIでの値の和を求めよ.

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2059

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
using namespace std;

vector<string> split(const string& str, const string& delimiter) {
    // delimiter(2 文字以上も可) を空白に置換
    string item(str);    
    for(unsigned pos = item.find(delimiter); pos != string::npos; pos = item.find(delimiter, pos)) {
        item.replace(pos, delimiter.size(), " ");
    }
    // 分解
    stringstream buf(item);

    // 読み取り
    vector<string> result;
    while(buf >> item) {
        result.push_back(item);
    }

    return result;
}

string stringxor(string v, int* a){
	string ret;
	
	for(int i=0 ; i<(signed)v.size() ; i++){
		ret += v[i]^a[i%3];
	}

	return ret;
}

bool stringsearch(string s, string target){
	for(int i=0 ; i<(signed)s.length()-3 ; i++){
		if(s.substr(i,target.size())==target) return true;
	}
	return false;
}

int main(){
	ifstream ifs("dat059.txt");
	string elem;
	ifs >> elem;

	vector<string> dat = split(elem, ",");
	string datc;

	for(int i=0 ; i<dat.size() ; i++){
		datc += atoi(dat[i].c_str());
	}

	int cc[3];
	string str;

	for(int i=97 ; i<=122 ; i++){
		cc[0] = i;
		for(int j=97 ; j<=122 ; j++){
			cc[1] = j;
			for(int k=97 ; k<=122 ; k++){
				cc[2] = k;
				str = stringxor(datc, cc);

				if(stringsearch(str," can ")){
					cout << str << endl;
					int sum=0;

					for(int i=0 ; i<str.size() ; i++){
						sum += str[i];
					}
					cout << sum << endl;
				}
			}
		}
	}
}

split関数はこちらを参考にさせていただきました。