ハッシュ関数をつくってみた (適当
今回は、MD5, SHA-1 などのハッシュ関数と呼ばれるものを作ってみました。
ハッシュ関数の詳細はググってください。
今回作ったものは、適当なのであまりいい特性ではないかもしれません。
コード↓
#include <iostream> #include <cstring> #include <fstream> using namespace std; const int BIT = 8; const int prime[BIT] = { 11, 13, 17, 19, 23, 29, 31, 37}; class HD { private: public: int hash(char [], int, unsigned int[]); int shash(char []); void operator = (char *ch) { shash(ch); } char str[33]; }; int HD::hash(char word1[],int wordsz1, unsigned int data[]) { unsigned int i=0, j=0, k = 2166136261, l = 0, data2[BIT] = {0}; char word[32] = { 0 }; unsigned long A, B, C, D, E, F, G, H; memset(data,0,BIT); for(l = 0; l < 2; l++) { for(i = 0; i < BIT; i++) { word[i % 32] |= k << 2; word[i % 32] += word1[i]; word[i % 32] ^= word1[i] * k; } } for(i = 0; word1[i] != 0; i++) { k = (k * 16777931) + word1[i] + word[i % 32]; data[i % BIT] += k; } for(i = 0; i < BIT; i++) { k = (k * 16777931) + data[i]; data[i] ^= prime[i] * k; data[i] &= prime[i] + k; data[i] += prime[i]; data[i] += (data[i] & k) ^ ~k; } data2[0] = data[0]; A = data2[7]; data2[1] = data[1]; B = data2[0]; data2[2] = data[2]; C = data2[1]; data2[3] = data[3]; D = data2[2]; data2[4] = data[4]; E = data2[3]; data2[5] = data[5]; F = data2[4]; data2[6] = data[6]; G = data2[5]; data2[7] = data[7]; H = data2[6]; memset(data, 0, BIT); for(j = 0; j < 64; j++) { A = (A = A ^ H * ~k) * (A = A ^ (k * A) ^ ~H); B = (B = B ^ G * ~k) * (B = B ^ (k * B) ^ ~G); C = (C = C ^ F * ~k) * (C = C ^ (k * C) ^ ~F); D = (D = D ^ E * ~k) * (D = D ^ (k * D) ^ ~E); E = (E = E ^ D * ~k) * (E = E ^ (k * E) ^ ~D); F = (F = F ^ C * ~k) * (F = F ^ (k * F) ^ ~C); G = (G = G ^ B * ~k) * (G = G ^ (k * G) ^ ~B); H = (H = H ^ A * ~k) * (H = H ^ (k * H) ^ ~A); A = ((A = A ^ (A * (A % k))) % (k * A)) ^ (k + H) ^ (~A); B = ((B = B ^ (B * (B % k))) % (k * B)) ^ (k + G) ^ (~B); C = ((C = C ^ (C * (C % k))) % (k * C)) ^ (k + F) ^ (~C); D = ((D = D ^ (D * (D % k))) % (k * D)) ^ (k + E) ^ (~D); E = ((E = E ^ (E * (E % k))) % (k * E)) ^ (k + D) ^ (~E); F = ((F = F ^ (F * (F % k))) % (k * F)) ^ (k + C) ^ (~F); G = ((G = G ^ (G * (G % k))) % (k * G)) ^ (k + B) ^ (~G); H = ((H = H ^ (H * (H % k))) % (k * H)) ^ (k + A) ^ (~H); data2[0] = A; A = data2[7]; data2[1] = B; B = data2[0]; data2[2] = C; C = data2[1]; data2[3] = D; D = data2[2]; data2[4] = E; E = data2[3]; data2[5] = F; F = data2[4]; data2[6] = G; G = data2[5]; data2[7] = H; H = data2[6]; } { data[0] = A; data[1] = B; data[2] = C; data[3] = D; data[4] = E; data[5] = F; data[6] = G; data[7] = H; } for(i = 0; i < BIT; i++) { data[i] %= 65535; if(data[i] < 0) data[i] = -data[i]; } return 0; } int HD::shash(char word[]) { unsigned int data[BIT] = { 0 },i = 0, wordsz = 0; wordsz = (unsigned int)strlen(word); hash(word,wordsz,data); memset(str, 0, 33); for(i = 0; i < BIT; i++) { sprintf(str, "%s%04x", str, data[i]); } return 0; } int main() { HD hash;// Hash Digest object hash = ""; cout << hash.str << endl; hash = "The quick brown fox jumps lazy dog";// ハッシュ化したい文字列を代入 (operator =) cout << hash.str << endl;// HD::str はハッシュ後の文字列(char str[33]) }
暗号化してみる
最近、暗号化にはまりまくっていますww
暗号化アルゴリズムには、公開鍵と共通鍵がありますが今回は共通鍵です。
公開鍵が登場するまで、暗号化は共通鍵でした。
今回は、少々まともな暗号化アルゴリズムを考えてみます。
で、たぶんシーザーよりは強い暗号化アルゴリズムができました。
名前は、ストリーム暗号を使ったので、SEA ( Stream Encrypt Algorithm ) です。(かっこいいww)
以下コードです。が、あくまでお遊び用に使ってくださいww
#include <iostream> #include <cstdio> #include <cstdlib> using namespace std; class SEA { public: int encrypt(int *, int, char *, int); int decrypt(int *, int, char *, int); int encryptx(int , char*, int); int decryptx(int , char*, int); int encfile(char*, int, FILE *); int decfile(char*, int, char *, FILE *); }; inline int SEA::encryptx(int num,char key[],int keysz) { int i=num,k,*onkey,out=0,onkeysz,keynum=0,onk = 0; onkeysz = (keysz > 20) ? 20 : keysz; onkey = (int *)calloc(keysz, sizeof(int)); for(k=0; k < onkeysz; k++)onkey[k] = (int)key[k]; for(k=0; k < onkeysz - 1; k++) { onkey[k] ^= onkey[onkeysz - k - 1]; onkey[k] <<= 3; } for( k=0; k < onkeysz; k++) { i = i ^ (onkey[k] * 4); } for( k=0; k < onkeysz; k++) { i ^= onkey[k] + (onkey[k] >> 1) * (onkey[k] % 103); keynum %= onkey[k] + 31; onk += onkey[k]; } i *= (keynum + 7); out = i; return out; } inline int SEA::decryptx(int num,char key[],int keysz) { int i = num; int k = 0,*onkey,out=0,onkeysz,keynum = 0,onk = 0; onkeysz = (keysz > 20) ? 20 : keysz; onkey = (int *)calloc(keysz, sizeof(int)); for(k=0; k < onkeysz; k++) onkey[k] = (int)key[k]; for(k=0; k < onkeysz - 1; k++) { onkey[k] ^= onkey[onkeysz - k - 1]; onkey[k] <<= 3; } keynum = 0; for( k=0; k < onkeysz; k++) { keynum %= onkey[k] + 31; onk += onkey[k]; } i /= (keynum + 7); for( k=0; k < onkeysz; k++) i ^= onkey[k] + (onkey[k] >> 1) * (onkey[k] % 103); for( k=0; k < onkeysz; k++) i = i ^ (onkey[k] * 4); out = i; return out; } inline int SEA::encrypt(int *tl,int tlsz,char *key,int keysz) { int i=0; for( i=0; i<tlsz; i++) tl[i] = encryptx(tl[i],key,keysz); return 0; } inline int SEA::decrypt(int *tl,int tlsz,char *key,int keysz) { int i=0; for( i=0; i<tlsz; i++) tl[i] = decryptx(tl[i],key,keysz); return 0; } int SEA::encfile(char *key,int keysz,FILE *fr) { int *tl; char*out; int i=0,m=0,n=0,fsz=0; FILE *fw; fw = fopen("sea.sea","wb+"); { fseek(fr,0,2); fsz = ftell(fr); fseek(fr,0,0); tl = new int [fsz](); out= new char[fsz](); } { fread(out,sizeof(char),fsz,fr); for(i=0; i < fsz; i++) tl[i] = out[i]; i=0; } encrypt(tl,fsz,key,keysz);//暗号化 fwrite(tl,sizeof(int),fsz,fw); delete[] tl; delete[] out; fclose(fw); return 0; } inline int SEA::decfile(char *key, int keysz, char *filename, FILE *fp) { int *tl; char*out; int i=0,m=0,n=0,fsz=0; FILE *fw; if(!(fw=fopen(filename,"wb+"))) return -1; {//ファイルサイズ取得 & 配列確保 ブロック fseek(fp,0,2); fsz = ftell(fp)/4; tl = new int[fsz](); out= new char[fsz](); fseek(fp,0,0); } fread(tl,sizeof(int),fsz,fp); decrypt(tl,fsz,key,keysz); for(i=0; i<fsz; i++) out[i] = tl[i]; fwrite(out,sizeof(char),fsz,fw); delete[] tl; delete[] out; fclose(fw); return 0; } int main(int argc,char *argv[]) { // 暗号化対象 int table1 = 65; int table2[3] = {12,34,567}; int k = 0; // 暗号化用キー char key[20] = "keyword"; // SEA Object SEA sea; // 表示 cout << "table1 : " << table1 << endl; cout << "table2 : " << table2[0] << " " << table2[1] << " " << table2[2] << endl; // 暗号化 cout << "Encrypt table1 : " << (k = sea.encryptx(table1, key, 20)) << endl; // 配列の暗号化 sea.encrypt(table2,3,key,20); cout << "table2 : " << table2[0] << " " << table2[1] << " " << table2[2] << endl; // 復号化 cout << "Decrypt table1 : " << sea.decryptx(k, key, 20) << endl; // 配列の復号化 sea.decrypt(table2, 3, key, 20); cout << "table2 : " << table2[0] << " " << table2[1] << " " << table2[2] << endl; return 0; }
こんな感じです。 コードがスパゲッティですいません...
クラスの説明
// SEA class public: // encrypt関数 : 配列の暗号化 int encrypt( int *, // 暗号化対象配列 int, // 配列サイズ char *,// 復号化 & 暗号化キー int // 復号化 & 暗号化キーサイズ ); // 戻り値 : 0 // decrypt関数 : 配列の復号化 int decrypt( int *, // 復号化対象配列 int, // 配列サイズ char *,// 復号化 & 暗号化用キー int // 復号化 & 暗号化用キーサイズ ); // 戻り値 : 0 // encryptx関数 : 整数の暗号化 int encryptx( int , // 暗号化対象整数 char*,// 復号化 & 暗号化用キー int // 復号化 & 暗号化用キーサイズ ); // 戻り値 : 暗号化後整数 signed int // decryptx関数 : 整数の復号化 int decryptx( int , // 復号化対象整数 char*,// 復号化 & 暗号化用キー int // 復号化 & 暗号化用キーサイズ ); // 戻り値 : 復号化後整数 signed int // encfile関数 : ファイルを暗号化 出力ファイル名は常に sea.sea int encfile( char*, // 復号化 & 暗号化用キー int, // 復号化 & 暗号化用キーサイズ FILE * // 暗号化対象ファイルポインタ 読み込みモード ); // 戻り値 : 0 // decfile関数 : ファイルを復号化 int decfile( char*, // 復号化 & 暗号化用キー int, // 復号化 & 暗号化用キーサイズ char *,// 復号化後ファイル名 FILE * // 復号化対象ファイルポインタ 読み込みモード ); // 戻り値 : 0
著作権フリーです。コードを改変してもかまいません。
暗号化って楽しいですね^^b まだ、しばらく暗号化について考えそうです。
それでは^^
色々な乱数
暗号について調べているうちに、乱数が必要になったのでしらべてみました。
乱数とは、5,2,7,3,7,9... のように次の数が予測できないバラバラな数。ですが、
コンピューターで乱数を得るときは、よっぽどのことがない限り、擬似乱数という計算によって
得られる乱数を使います。(計算によって得るので、予測ができる)
擬似乱数には周期があり、しばらく使っていると、また同じ数列が出てきてしまうことがあります。
この周期が長いほどいいといわれています。
ガイガーカウンタとかがあれば真の乱数が得られますけどね^^
ということで、C/C++ C# などで使えそうな擬似乱数アルゴリズムをまとめました。
・stdlib rand()
C/C++ 標準ヘッダのstdlib(cstdlib)内の rand()関数 です。
0...RAND_MAX までの乱数を返します。
アルゴリズムは線形合同法なので、周期が短いのが欠点です。(2^32 ぐらい)
・C# System.Random.Next()
System.Random 内の Next()関数です。
C/C++ のrand() よりは多少いいものの、満足のいくものではありません。
どんなアルゴリズムを使っているかは、わかりませんでした。(ググってくださいww)
・メルセンヌ・ツイスター(MT)
自分の知っている中でもっとも周期の長い、メルセンヌ・ツイスター。
何と周期が 2^19937 - 1 もあります。
ほぼ、無限大です。(Mersenne Twister: A random number generator (since 1997/10))
・XorShift
意外と知られていない? XorShift。その名の通り、XOR と SHIFT を使います。
周期も 2^128 - 1 と長く、いい感じです。(計算速度も速い)
・M系列
M系列という物もあります。メルセンヌ・ツイスターも中核部分はこれです。
面白そうなので、コードを探していたら Wikipedia に載っていました。(線形帰還シフトレジスタ - Wikipedia)
#include <iostream> using namespace std; // Wikipedia にあったものを少し改造 unsigned Mrand(int Max)//Max 最高値 { static unsigned int lfsr = ( 1 >> 1) ^ ( -(1 & 1u) & 0xd0000001u); if(lfsr != 1) { lfsr = (lfsr >> 1) ^ ( -(lfsr & 1u) & 0xd0000001u); } return lfsr % Max; } int main(void) { int i=0; while(i<10000) { cout << Mrand(100) << endl; i++; } return 0; }
乱数って面白いですね。今度、乱数のクラスを作ろうと思います。
それでは^^
RSA暗号 C++
参考にさせてもらったのは、このページ(RSA暗号で遊んでみる - ser1zw's blog)の
C#で書かれた実装例です。ありがとうございます。
で、これをC++に移植しました↓
#include <cstdio> #include <cstdlib> #include <cmath> #include <conio.h> #include <cstring> #include <iostream> #define P (__int64 )12671 #define Q (__int64 )1009 #define E (__int64 )6553 using namespace std; class RSA { private: __int64 getl(__int64 p,__int64 q); __int64 getd(__int64 p,__int64 q,__int64 e); public: __int64 Ec(__int64 ec, __int64 e, __int64 n); __int64 Dc(__int64 ec,__int64 p,__int64 q,__int64 e); }; __int64 RSA::Ec(__int64 ee, __int64 e, __int64 n) { __int64 result = 1; __int64 pown = ee; while (e > 0) { if((e & 1) > 0) result = (result * pown) % n; pown = (pown * pown) % n; e >>= 1; } return result; } __int64 RSA::getl(__int64 p,__int64 q) { __int64 t; __int64 m = p*q; while (p % q != 0) { t = q; q = p % q; p = t; } return m / q; } __int64 RSA::getd(__int64 p,__int64 q,__int64 e) { __int64 lcm = getl(p-1,q-1); int x1 = 1, y1 = 0, z1 = lcm; int x2 = 0, y2 = 1, z2 = e; int x3, y3, z3; int a = 1; while(z2 > 0) { a = (__int64 )(z1 / z2); x3 = x1 - a * x2; y3 = y1 - a * y2; z3 = z1 - a * z2; x1 = x2; y1 = y2; z1 = z2; x2 = x3; y2 = y3; z2 = z3; } return (x1 > y1) ? x1 : y1; } __int64 RSA::Dc(__int64 ee,__int64 p,__int64 q,__int64 e) { return Ec(ee,getd(p,q,e),p*q); } int main(void) { int key = 13;//暗号化対象 RSA rsa; cout << "key -> " << key << endl; cout << "暗号-> " << (key = rsa.Ec(key,E,P*Q)) << endl; cout << "復号-> " << rsa.Dc(key,P,Q,E) << endl; return 0; }
ちょっと変数名が変わったり、新しい関数ができていたりしますが、
__int64 RSA::Ec( __int64 ee,// 暗号化対象 __int64 e, // e __int64 n) // p * q __int64 RSA::Dc( __int64 ee,// 復号化対象 __int64 p,// p __int64 q,// q __int64 e)// e
という風になっています。
RSA暗号が理解できないと難しいですが、
pとqは大きな素数
eはp-1とq-1の最小公倍数とおたがいに素な数
だったと思います。
あと、このコードは Visual C++ でコンパイルしたので64bit 整数は __int64 となっています。
他の環境でコンパイルするときは、unsigned long long にしたほうがいいと思います。
また、変なところがあったら教えていただけると光栄です。