プログラミング > crypt関数の解説と実装


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

crypt関数の解説と実装


はるか昔にレポートで書いたものを少し修正したものです。間違い等あるかもしれません。



概要

Linuxでは、DESを使用したパスワード暗号化関数cryptが用意されている。 このレポートでは、まずそのcrypt関数の概要とアルゴリズムについて述べる。 また、crypt関数と同じ動作をする関数を一から実装し、その実行した結果を途中結果を 含め載せる。

crypt関数

Linuxでは、パスワードを暗号化するcryptという関数が用意されており、CやPerlなどから利用可能である。 crypt関数のCのプロトタイプ宣言は、

char *crypt(const char *key, const char *salt);

のようになっており、keyは、8文字以内のパスワード文字列、 saltは、出力をかき乱すのに使われる2文字の文字列であり、 その文字は[./0-9A-Za-z]の64文字中から選ばれなければならない。 また返り値は、暗号化された13文字のパスワード文字列である。 なお、この暗号化されたパスワード文字列は、[./0-9A-Za-z]の文字しか含まない。

crypt関数の使用例を、example.cに示す。 unistd.hをインクルードし、-lcryptでリンクすることで使用可能である。 あらかじめ保存されていた暗号化したパスワードと、入力パスワードを暗号化したものが 一致した場合にパスワードが一致したとするのが典型的な使用例である。

  • example.c
  1. #include <stdio.h>
  2. #include <unistd.h>
  3.  
  4. int main()
  5. {
  6. char crypted_password[] = "A1abcd80zC.2k"; // 保存されている暗号化パスワード
  7. // "futadaha"をsaltを"A1"で暗号化したもの
  8. char input_password[256];
  9.  
  10. scanf("%s", input_password);
  11.  
  12. if(strcmp(crypted_password, crypt(input_password, "A1")) == 0){
  13. // あらかじめ保存しておいた暗号化されたパスワードと
  14. // 入力パスワードを暗号化したものが一致すればOK
  15. printf("Password match.\n");
  16. }else{
  17. printf("Password not match.\n");
  18. }
  19. }

crypt関数は、Data Encryption Standard(DES)を 使用している。以下では、crypt関数のアルゴリズムを述べ、またDESについても簡単に 述べる。

Data Encryption Standard(DES)

DESは、64ビットの入力を64ビットの暗号文に暗号化する共通鍵ブロック暗号の アルゴリズムであり、鍵のビット長は56ビットになる。 DESの基本構造は、ファイステル暗号に基づいている。 ファイステル暗号は、ラウンド処理と呼ばれる暗号化の1ステップを何度も繰り返すように なっている。1回のステップには、暗号化関数と呼ばれる、"入力、鍵スケジュールと拡張関数 をもとにランダムに見えるビット列を生成する関数"が含まれる。 DESは、そのラウンド処理を16回繰り返すようになっている。

crypt関数のアルゴリズム

crypt関数は、以下のような手順で計算される。

  1. 引数で与えられたkey(64ビット)から鍵スケジュール作成に使われる鍵(56ビット)を作る
  2. その鍵から鍵スケジュール(16 x 48ビット)を作る
  3. 引数で与えられたsalt(16ビット)を使って、拡張関数を修正する(かき乱す)
  4. 初期入力をすべて0のビット列(64ビット)、鍵スケジュール、修正された拡張関数を使いDESを25回繰り返す
  5. DESの出力(64ビット)から11文字の文字列を作る。
  6. saltの2文字と上の11文字を連結した13文字を出力とする。

1.では、key8文字から下位7ビットをそれぞれ取り、56ビットの鍵が得られる。 2.は、DESで決められた鍵スケジュールである。 3.は、crypt関数独自の処理で、DESで決められている拡張関数をそのまま 使用するのではなく、修正して(かき乱して)使用する。具体的には、saltの各文字は [./0-9A-Za-z]の64文字文字に限られるため、まずそれを0から63の数値(6ビット)と見なす ('.'=0、'/'=1、'0'=2、'1'=3、'2'=4のように)。 そして得られた12ビットのビット列を順次走査し、 ビットが1であれば拡張関数で使われるテーブル中の値を入れ替える処理を行っている。 4.は、DESの暗号化部そのままである。 ただし、DESの暗号化を25回繰り返す。そのとき今の暗号化結果の出力を次の入力に順次使う。 25回目の暗号化結果を出力する。 5.は、最終的な出力文字列のための処理である。DESの出力64ビットを6ビット数値が11個 あるとみなし(6 $\times$ 11 = 66となるため、DESの出力64ビットの最後に0ビットを2個補う)、 その数値0から63を文字[./0-9A-Za-z]とする(0='.'、1='/'、2='0'、3='1'、4='2'のように)。 6.で、最終出力結果を作る。

cryptの実装と実行結果例

今回、Cを用いてcrypt関数と同じ動作をするmy_crypt関数を作成した。my_crypt関数に付随して 巡回左シフト、暗号化関数、DESなども同時に実装した。 ソースコードは、付録に記載した。

次に、実装した関数の実行結果を示す。keyは"futadaha"、saltは"A1"を用いた。 keyから作られた鍵スケジュールは、以下のようになった(16進数表示)。

K01:af f3 53 0a 85 89
K02:bf 73 5f 24 34 3a
K03:2f 57 d9 2d 18 62
K04:5f 59 fd 04 c8 72
K05:9f e9 d9 05 8c 54
K06:1f 6f af 89 84 d0
K07:fb 3d 8d 09 c6 05
K08:59 ae ed 1a 44 84
K09:f9 ac fc 10 38 36
K10:d4 ee ae 25 28 b0
K11:f2 bf 36 21 28 53
K12:ec be 67 27 80 16
K13:e3 f6 7e 05 05 c6
K14:ec d7 f2 0c 80 c5
K15:f6 db 7b 42 c4 c5
K16:ae db f3 60 b8 0a

また、saltで修正された拡張関数(暗号化関数で入力32ビットから48ビットに拡張するときに、 入力のどのビットをとるかを決める関数) のテーブル値は、以下のようになった(10進数表示)。

32 01 18 19 04 05 20 21 06 07 08 09 08 09 10 11 
12 13 12 13 14 15 16 17 16 17 02 03 20 21 04 05 
22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 01 

25回繰り返す、DESの各出力結果は以下のようになった(16進数表示)。

input:   00 00 00 00 00 00 00 00
output01:ad ef bb c4 31 0d 21 f0
output02:7d 2d bd 1b 2d 2b 95 36
output03:be fa 22 c4 02 4d bc 7d
output04:4e ec e1 8a 82 0a 96 88
output05:2f c5 8e 76 75 67 22 b0
output06:15 ff 48 09 28 58 f2 f1
output07:6e 61 cc f8 f5 94 25 78
output08:9e e6 88 1b b6 10 8a 44
output09:21 bb 04 de 53 ed f2 3d
output10:a6 40 ab b1 01 ed 5b 25
output11:6c 7f e4 c9 5c c7 83 26
output12:83 d8 cf 60 d2 d1 b6 1e
output13:5d b2 1b 48 06 4f 0c 1a
output14:16 02 77 dc 72 a0 f9 af
output15:75 41 19 3e 9c f9 8d 34
output16:36 0f ce 86 6f 62 60 5a
output17:50 fe b7 9a ab 22 dd 6f
output18:6c 5c e3 ec 2c d0 4e f4
output19:fb e1 75 7f d6 f1 00 86
output20:62 b9 65 56 46 07 08 64
output21:05 1e 41 f3 ee df f4 23
output22:09 00 57 6b 2c ff 9b a9
output23:8b bb a2 11 6f 6b 80 28
output24:fc 78 ca ae 71 a6 eb ef
output25:9a 7a 29 28 2f ce 00 4c

output25から、6ビットごとに区切り文字列化すると"abcd80zC.2k"となり、 saltと結合した最終結果は、"A1abcd80zC.2k"となった。 もとの文字列"futadaha"からは想像できない文字列が生成されることが確認できる。

終わりに

本レポートでは、cryptのアルゴリズムを述べ、その実装を行った。 また、実行結果についても例を使い記載した。

付録

my_crypt.cに今回実装した、crypt関数と同じ動作をするmy_crypt関数を示す。 ソースコード中の、PC1c、PC1d、shift、PC2c、PC2d、IP、S、P、IPInv、 Eは、別ファイルで定義してある定数テーブルである。

それらの値すべて、FIPSの資料に記載されている。

  • PC1cとPC1dは資料中でPermuted choice 1(PC-1)、
  • shiftはschedule of left shifts of the individual blocks、
  • PC2cとPC2dはPermuted choice 2(PC-2)、
  • IPはinitial permutation(IP)、
  • Sはprimitive functions(S_1,...S_8)、
  • Pはpermutation function(P)、
  • IPInvはinverse of the initial permutation(IP^-1)、
  • Eはfunction which takes a block of 32 bits as input and yields a block of 48 bits as output(E BIT-SELECTION TABLE)

である。

  • my_crypt.c
  1. #include <stdio.h>
  2. #include "table.h"
  3.  
  4. // デバッグ用のプリント
  5. void print_bit(char *x, int n)
  6. {
  7. int i, j;
  8.  
  9. for(i = 0; i < n; i++){
  10. unsigned char c = 0;
  11.  
  12. for(j = 0; j < 8; j++){
  13. c <<= 1;
  14. c |= x[8 * i + j];
  15. }
  16. printf("%02x ", c);
  17. }
  18. printf("\n");
  19. }
  20.  
  21. // 巡回左シフト
  22. void left_shift(char *v, char shift_n)
  23. {
  24. int i ,j;
  25. char t;
  26.  
  27. for(i = 0; i < shift_n; i++){
  28. t = v[0];
  29. for(j = 0; j < 28 - 1; j++){
  30. v[j] = v[j + 1];
  31. }
  32. v[27] = t;
  33. }
  34. }
  35.  
  36. // 暗号化関数
  37. void func(char R[32], char K[48], char E[48], char result[32])
  38. {
  39. int i;
  40. char ER[48], temp1[48], temp2[32];
  41.  
  42. // 1. 拡張関数を適用する
  43. for(i = 0; i < 48; i++){
  44. ER[i] = R[E[i] - 1];
  45. }
  46.  
  47. // 2. 鍵との排他的論理和
  48. for(i = 0; i < 48; i++){
  49. temp1[i] = ER[i] ^ K[i];
  50. }
  51.  
  52. // 3. S-Box
  53. for(i = 0; i < 8; i++){
  54. int t, k;
  55.  
  56. t = 6 * i;
  57. k = S[i][(temp1[t + 0] << 5) +
  58. (temp1[t + 1] << 3) +
  59. (temp1[t + 2] << 2) +
  60. (temp1[t + 3] << 1) +
  61. (temp1[t + 4] << 0) +
  62. (temp1[t + 5] << 4)];
  63. t = 4 * i;
  64. temp2[t + 0] = (k >> 3) & 1;
  65. temp2[t + 1] = (k >> 2) & 1;
  66. temp2[t + 2] = (k >> 1) & 1;
  67. temp2[t + 3] = (k >> 0) & 1;
  68. }
  69.  
  70. // 4. 転置を施す
  71. for(i = 0; i < 32; i++){
  72. result[i] = temp2[P[i] - 1];
  73. }
  74. }
  75.  
  76. // DES
  77. void des(char X[64], char Kn[16][48], char E[48])
  78. {
  79. int i, j;
  80. char L[32], R[32], concat[64];
  81.  
  82. // 1. 初期転置を作用させる
  83. for(i = 0; i < 32; i++){
  84. L[i] = X[IP[i] - 1];
  85. }
  86. for(i = 32; i < 64; i++){
  87. R[i - 32] = X[IP[i] - 1];
  88. }
  89.  
  90. // 2. 以下の暗号化を16回繰り返す
  91. for(i = 0; i < 16; i++){
  92. char tmp[32], f[32];
  93.  
  94. // 2-1. Rを一時領域に移す
  95. for(j = 0; j < 32; j++){
  96. tmp[j] = R[j];
  97. }
  98.  
  99. // 2-2. Rの暗号化関数を計算してLと排他的論理和
  100. func(R, Kn[i], E, f);
  101. for(j = 0; j < 32; j++){
  102. R[j] = L[j] ^ f[j];
  103. }
  104.  
  105. // 2-3. 一時領域に移していたLをRに移す
  106. for(j = 0; j < 32; j++){
  107. L[j] = tmp[j];
  108. }
  109. }
  110.  
  111. // 3. RLに初期転置の逆を施す
  112. for(i = 0; i < 32; i++){
  113. concat[i] = R[i];
  114. }
  115. for(i = 32; i < 64; i++){
  116. concat[i] = L[i - 32];
  117. }
  118. for(i = 0; i < 64; i++){
  119. X[i] = concat[IPInv[i] - 1];
  120. }
  121. }
  122.  
  123. // crypt関数の代替実装
  124. char *my_crypt(const char *key, const char *salt)
  125. {
  126. int i, j;
  127. char shifted_key[8] = {0};
  128. char key_bit[64] = {0};
  129. char C[28], D[28];
  130. char Kn[16][48]; // 鍵スケジュール
  131. char Emod[48];
  132. char X[64] = {0};
  133. char crypt_str[11 + 1];
  134. static char result_str[256];
  135.  
  136. // 1. 鍵スケジュール作成に使われる鍵を作る
  137. // 1-1. 引数keyを1ビット左シフトする
  138. for(i = 0; i < 8; i++){
  139. if(key[i] == 0) break;
  140. shifted_key[i] = (key[i] << 1);
  141. }
  142. // 1-2. ビットごとに分ける
  143. for(i = 0; i < 8; i++){
  144. for(j = 0; j < 8; j++){
  145. key_bit[i * 8 + j] = (shifted_key[i] >> (7 - j)) & 1;
  146. }
  147. }
  148.  
  149. // 2. 鍵スケジュールを作る
  150. // 2-1. 転置選択1を施す
  151. for(i = 0; i < 28; i++){
  152. C[i] = key_bit[PC1c[i] - 1];
  153. D[i] = key_bit[PC1d[i] - 1];
  154. }
  155. // 2-2. シフトと置換選択2を施し鍵スケジュールを作る
  156. for(i = 0; i < 16; i++){
  157. left_shift(C, shift[i]);
  158. left_shift(D, shift[i]);
  159. for(j = 0; j < 24; j++){
  160. Kn[i][j ] = C[PC2c[j] - 1];
  161. Kn[i][j + 24] = D[PC2d[j] - 28 - 1];
  162. }
  163. printf("K%02d: ", i + 1); print_bit(Kn[i], 6);
  164. }
  165.  
  166. // 3. saltを使って、拡張関数を修正する
  167. for(i = 0; i < 48; i++){
  168. Emod[i] = E[i];
  169. }
  170. for(i = 0; i < 2; i++){
  171. char c, k;
  172.  
  173. c = salt[i];
  174. if(c > 'Z') c -= 6;
  175. if(c > '9') c -= 7;
  176. c -= '.';
  177. for(j = 0; j < 6; j++){
  178. if((c >> j) & 01){ // ビットが立っていたら変更
  179. k = Emod[6 * i + j];
  180. Emod[6 * i + j] = Emod[6 * i + j + 24];
  181. Emod[6 * i + j + 24] = k;
  182. }
  183. }
  184. }
  185. printf("Emod: "); for(i = 0; i < 48; i++){printf("%2d ", Emod[i]);} printf("\n");
  186.  
  187. // 4. DESを25回繰り返す
  188. printf("input: "); print_bit(X, 8);
  189. for(i = 0; i < 25; i++){
  190. des(X, Kn, Emod);
  191. printf("output%02d: ", i + 1); print_bit(X, 8);
  192. }
  193.  
  194. // 5. ビットをASCII文字列にする
  195. for(i = 0; i < 11; i++){
  196. char c = 0;
  197.  
  198. for(j = 0; j < 6; j++){ // 6ビットごとに一つにする
  199. c <<= 1;
  200. if((6 * i + j) < 64) c |= X[6 * i + j];
  201. }
  202.  
  203. c += '.';
  204. if(c > '9') c+= 7;
  205. if(c > 'Z') c+= 6;
  206. crypt_str[i] = c;
  207. }
  208. crypt_str[11] = '\0';
  209.  
  210. sprintf(result_str, "%s%s", salt, crypt_str);
  211. printf("%s\n", result_str);
  212.  
  213. return result_str;
  214. }

参考