[ crypt() アルゴリズム解析 ] 動作確認は基本的には Linux + gcc で行っていますが crypt2.c に関しては Windows + Borland C++ Compiler でも動作確認済みです。 >> [ 0x01 ] crypt()とは？ 例えば以下のプログラムを実行してみる。 crypt.pl ------------------------------------------------------------------------------ #!/usr/bin/perl $str = crypt( $ARGV[0], $ARGV[1] ); print $str . "\n"; ------------------------------------------------------------------------------ crypt]$ chmod 755 crypt.pl crypt]$ ./crypt.pl bbbbbbbb aa aaZbwOjboVU62 crypt]$ C で書くと以下だ。 crypt.c ------------------------------------------------------------------------------ #include #include int main(int argc, char *argv[]) { if(argc < 3){ fprintf(stderr, "%s [string] [salt]\n",argv[0]); exit(1); } printf("%s\n", crypt(argv[1], argv[2])); return 0; } ------------------------------------------------------------------------------ crypt]$ gcc -Wall crypt.c -lcrypt crypt]$ ./a.out bbbbbbbb aa aaZbwOjboVU62 crypt]$ 意味不明な文字列が出力されます。これは"bbbbbbbb"という文字列を暗号化し た文字列ということです。ではどういう仕組みで暗号化されたのか？それをこ れから調べるわけですが、基本的にはDESの暗号化アルゴリズムを使用してい ます。crypt関数についてはソースコードもネット上に落ちてますので探して みて下さい。(例えばgoogleで"crypt3.c"で検索してみるとか)私は http://packetstorm.icx.fr/crypt/applied-crypto/crypt3.cからDLしました。 >> [ 0x02 ] 処理の概要 crypt関数の第一引数を str(8bytes) 、第二引数を salt(2bytes) とします。 ポイントは4つあります。1つ目はstr(8bytes)を平文ではなく共通鍵と考えて DES暗号化アルゴリズムの共通鍵の生成の処理に渡します。それにより内部鍵 が生成されます。str は平文ではなく鍵として使用されるのです。では何が平 文として使用されるのかというと、それはただの 0 の羅列です。64ビット分 0 の羅列が平文として使用されるのです。2つ目は salt の使用方法です。 salt はどこで使用されるのかというと拡大型転置(E)を変更するために使用さ れます。crypt()では salt により拡大型転置(E)は少し変更されて使用されま す。3つ目にDES暗号化は25回行われます。最後にcrypt関数は暗号化後も文字 列として出力しなければなりません。なのでその変換の処理が加わっています。 では実際に処理の内容を追っていきます。 ちなみにこれは私がこの文章用に独自に書いたものなので本当のcrypt()とは ソースコードの書き方が違います。(もちろん出力結果は同じですが)私が googleから検索して貰って来た crypt3.c は違いました。crypt()の説明用に 解りやすくしようと変更した結果こうなりました（笑）こっちの方が解りやす いと思います,多分。興味があれば crypt3.c もよんでみてください。 では始まり始まり〜 >> [ 0x03 ] crypt()解析 ソースコードは↓にアップしました。 http://ruffnex.oc.to/kenji/src/crypt2.c http://ruffnex.oc.to/kenji/src/des.h ここからはこのソースを元に解説していきます。 --- crypt2.c --- #include #include #include "des.h" //#define DEBUG void debug(char *data, unsigned short size, char *str) { #ifdef DEBUG int i; printf("%s = ", str); for(i=0; i < size; i++){ printf("%d", data[i]); } printf("\n"); #endif } これはデバッグ時に使用するので基本的には無視して構いません。defineもコ メントアウトしてるし。des.h はDES暗号化アルゴリズムの転置処理などなど の配列を定義しているヘッダファイルです。詳しくは詳解DESアルゴリズムを みてください。 int main(int argc, char *argv[]) { char block[66],dmy_block[64], KS[16][48], preS[48]; char C[28], D[28], L[32], R[32], DMY[32], E[48], f[32]; char *str, *salt, iobuf[16]; int i, j, k, t, m; char c; if(argc < 3){ fprintf(stderr, "%s [string] [salt]\n", argv[0]); exit(1); } /* 引数確保 */ str = argv[1]; salt = argv[2]; for(i=0; i < 66; i++) block[i] = 0; ここまでは初期化などなどの処理です。特に問題無いかと思います。 /* 内部鍵生成 */ /* 1,9,17...ビット目を無視する */ for(i=0; *str && i < 64; str++){ for(j=0; j < 7; j++, i++) block[i] = ((*str)>>(6-j)) & 01; i++; } まず str つまり文字列(64)を1ビットずつ取得していきます。ただし1,9,17 ビット目は無視します。(これはDESとはちょっと違いますが)その残りの56ビ ットを縮約型転置にかけます。もちろんblockの8の倍数ビット目は(配列でい うと7,15,23...(8*n-1))当然すべて 0 になっています。詳しく説明すると 1 0 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 1 1 1 0 0 1 0 1 0 0 1 0 1 という64ビットの文字列があり1,9,17...ビット目を消します。つまり一番左 の一列を消します。そしてそれぞれの行の後に 0 を付加します。 0 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 この64ビット配列を縮約型転置PC1にいれて56ビットの配列を求めています。 これはDESアルゴリズムとは多少の違いがあります。DESアルゴリズムでは64ビッ トの鍵をそのまま縮約型転置PC1にいれてましたが(結果DESでは8の倍数ビット 目が削除されていた)crypt()では1,9,17...ビット目が削除されることになっ ています。 /* 縮約型転置 PC1 */ for(i=0; i < 28; i++){ C[i] = block[PC1_C[i]-1]; D[i] = block[PC1_D[i]-1]; } for(i=0; i < 16; i++){ /* 循環シフト */ for(k=0; k < shift[i]; k++){ t = C[0]; for(j=0; j < 28-1; j++) C[j] = C[j+1]; C[27] = t; t = D[0]; for(j=0; j < 28-1; j++) D[j] = D[j+1]; D[27] = t; } /*縮約型転置 PC2 */ for(j=0; j < 24; j++){ KS[i][j] = C[PC2_C[j]-1]; KS[i][j+24] = D[PC2_D[j]-28-1]; } } /* 内部鍵生成完了！ */ 内部鍵生成の処理はDES暗号化を引き継いでいます。ただし最初に述べたよう に鍵には str が利用されています。 /* 拡大型転置 E をコピー */ for(i=0; i < 48; i++) E[i] = e2[i]; /* salt による 拡大型転置の変更 */ for(i=0; i < 2; i++){ c = *salt++; iobuf[i] = c; if(c > 'Z') c -= 6; if(c > '9') c -= 7; c -= '.'; for(j=0; j < 6; j++){ if((c >> j) & 01){ k = E[6*i+j]; E[6*i+j] = E[6*i+j+24]; E[6*i+j+24] = k; } } } ここがすこし違うところです。拡大型転置(E)をコピーしています。for文の中 はまずsaltの一文字をとりだしiobufにいれています。iobufとは最終的に出力 する暗号化後の文字列を格納する配列なのでiobufの最初の2バイトはsaltで埋 めときます。そして c を if で判定してますが、これはASCIIコードを見なが らソースを解析すれば一目瞭然でしょう。 ASCIIコード (2E 〜 7A) ./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz ~~~~~~~ ~~~~~~ このアンダーバーが引かれているところを省いて考えたいので、9 より大きい なら -7 さらに Z より大きいなら -6 をすれば、ちょうどcrypt()が使用する 文字の羅列を作ることができるということです。そして最後に'.'を減算して るので結果的には'.'を 0 として 0....63 の数字でcrypt()が扱う文字を表す ことができるというわけです。 ./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz そしてシフトした値が 1 だったならば拡大転置(E)を変更する。という処理を 行っています。これが salt の利用方法だったわけです。 for(i=0; i < 66; i++) block[i] = 0; 暗号化開始直前に blockをゼロに初期化しています。 平文に相当するデータは 0 なのです。 /* 暗号化開始 */ for(m=0; m < 25; m++){ おいおい、なんでここに 25 回ループさせる命令があるんだよ。ということで すが、crypt() はDES暗号化アルゴリズムを 25回 繰り返します。トリプルDES の比じゃないです。なんたって25回ですから（笑）まぁおそらく暗号化対象の データがちいさいのでこのくらいやっても全然処理的にだいじょぶなのでって ことだろうと私は思っています。 /* 初期転置 */ for(i=0; i < 32; i++) L[i] = block[IP[i]-1]; for(i=32; i < 64; i++) R[i-32] = block[IP[i]-1]; /* 16段の暗号化オペレーション */ for(i=0; i < 16; i++){ for(j=0; j < 32; j++) DMY[j] = R[j]; /* 内部鍵との排他的論理和 */ for(j=0; j < 48; j++) preS[j] = R[E[j]-1] ^ KS[i][j]; /* S BOX */ for(j=0; j < 8; j++){ t = 6*j; k = S[j][(preS[t+0]<<5)+ (preS[t+1]<<3)+ (preS[t+2]<<2)+ (preS[t+3]<<1)+ (preS[t+4]<<0)+ (preS[t+5]<<4)]; t = 4*j; f[t+0] = (k>>3)&01; f[t+1] = (k>>2)&01; f[t+2] = (k>>1)&01; f[t+3] = (k>>0)&01; } /* 転置 P を行ったあとの 排他的論理和 */ for(j=0; j < 32; j++) R[j] = L[j] ^ f[P[j]-1]; for(j=0; j < 32; j++) L[j] = DMY[j]; } for(i=0; i < 32; i++){ t = L[i]; L[i] = R[i]; R[i] = t; } for(i=0; i < 32; i++) dmy_block[i] = L[i]; for(i=32; i < 64; i++) dmy_block[i] = R[i-32]; /* 最終転置 */ for(i=0; i < 64; i++) block[i] = dmy_block[FP[i]-1]; } ここまでもDESと変わりありません。25回繰り返す以外はちゃんとDES暗号化ア ルゴリズムと同じです。ちゃんとというのもおかしいですが...(^^; for(i=0; i < 11; i++){ c = 0; for(j=0; j < 6; j++){ c <<= 1; c |= block[6*i+j]; } c += '.'; if(c > '9') c += 7; if(c > 'Z') c += 6; iobuf[i+2] = c; } block配列の中にはいっているビット列を文字列に復元する処理です。左に1シ フトしてblockとの or ですが c は必ず 0 なので結果的に block のビット列 を1ビットずつ c にいれていることになります。なぜ 6ビットなのかというと ./0123...............xyzがちょうど 64個 であり、0..63 までで表せるから ということです。(もはや説明はいらんかったかもしれんですけど)そして iobufにあらかじめ salt が入っているのでその後から文字列を追加していき それを出力して終了。ということです。 iobuf[i+2] = '\0'; printf("%s\n", iobuf); return 0; } 以上で終了です。 今回はソースコードをアップしてるので、ここには載せません。 End. written by kenji aiko 2003/10/08 2003/10/13 一部修正 2003/10/17 ソースコードのリンク先を変更 2003/11/06 ソースコードを Windows + BCC に対応 Copyright (C) 2003 kenji aiko All Rights Reserved