プログラミング/crypt関数の解説と実装 - futada wiki

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

crypt関数の解説と実装

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

概要
crypt関数
Data Encryption Standard(DES)
crypt関数のアルゴリズム
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

#include <stdio.h>
#include <unistd.h>
 
int main()
{
    char crypted_password[] = "A1abcd80zC.2k"; // 保存されている暗号化パスワード
                                               // "futadaha"をsaltを"A1"で暗号化したもの
    char input_password[256];
 
    scanf("%s", input_password);
 
    if(strcmp(crypted_password, crypt(input_password, "A1")) == 0){
        // あらかじめ保存しておいた暗号化されたパスワードと
        // 入力パスワードを暗号化したものが一致すればＯＫ
        printf("Password match.\n");
    }else{
        printf("Password not match.\n");
    }
}

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

Data Encryption Standard(DES)

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

crypt関数のアルゴリズム

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

引数で与えられたkey(64ビット)から鍵スケジュール作成に使われる鍵(56ビット)を作る
その鍵から鍵スケジュール(16 x 48ビット)を作る
引数で与えられたsalt(16ビット)を使って、拡張関数を修正する(かき乱す)
初期入力をすべて0のビット列(64ビット)、鍵スケジュール、修正された拡張関数を使いDESを25回繰り返す
DESの出力(64ビット)から11文字の文字列を作る。
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

#include <stdio.h>
#include "table.h"
 
// デバッグ用のプリント
void print_bit(char *x, int n)
{
    int i, j;
 
    for(i = 0; i < n; i++){
        unsigned char c = 0;
 
        for(j = 0; j < 8; j++){
            c <<= 1;
            c |= x[8 * i + j];
        }
        printf("%02x ", c);
    }
    printf("\n");
}
 
// 巡回左シフト
void left_shift(char *v, char shift_n)
{
    int i ,j;
    char t;
 
    for(i = 0; i < shift_n; i++){
        t = v[0];
        for(j = 0; j < 28 - 1; j++){
            v[j] = v[j + 1];
        }
        v[27] = t;
    }
}
 
// 暗号化関数
void func(char R[32], char K[48], char E[48], char result[32])
{
    int i;
    char ER[48], temp1[48], temp2[32];
 
    // 1. 拡張関数を適用する
    for(i = 0; i < 48; i++){
        ER[i] = R[E[i] - 1];
    }
 
    // 2. 鍵との排他的論理和
    for(i = 0; i < 48; i++){
        temp1[i] = ER[i] ^ K[i];
    }
 
    // 3. S-Box
    for(i = 0; i < 8; i++){
        int t, k;
 
        t = 6 * i;
        k = S[i][(temp1[t + 0] << 5) +
                 (temp1[t + 1] << 3) +
                 (temp1[t + 2] << 2) +
                 (temp1[t + 3] << 1) +
                 (temp1[t + 4] << 0) +
                 (temp1[t + 5] << 4)];
        t = 4 * i;
        temp2[t + 0] = (k >> 3) & 1;
        temp2[t + 1] = (k >> 2) & 1;
        temp2[t + 2] = (k >> 1) & 1;
        temp2[t + 3] = (k >> 0) & 1;
    }
 
    // 4. 転置を施す
    for(i = 0; i < 32; i++){
        result[i] = temp2[P[i] - 1];
    }
}
 
// DES
void des(char X[64], char Kn[16][48], char E[48])
{
    int i, j;
    char L[32], R[32], concat[64];
 
    // 1. 初期転置を作用させる
    for(i = 0; i < 32; i++){
        L[i] = X[IP[i] - 1];
    }
    for(i = 32; i < 64; i++){
        R[i - 32] = X[IP[i] - 1];
    }
 
    // 2. 以下の暗号化を16回繰り返す
    for(i = 0; i < 16; i++){
        char tmp[32], f[32];
 
        // 2-1. Rを一時領域に移す
        for(j = 0; j < 32; j++){
            tmp[j] = R[j];
        }
 
        // 2-2. Rの暗号化関数を計算してLと排他的論理和
        func(R, Kn[i], E, f);
        for(j = 0; j < 32; j++){
            R[j] = L[j] ^ f[j];
        }
 
        // 2-3. 一時領域に移していたLをRに移す
        for(j = 0; j < 32; j++){
            L[j] = tmp[j];
        }
    }
 
    // 3. RLに初期転置の逆を施す
    for(i = 0; i < 32; i++){
        concat[i] = R[i];
    }
    for(i = 32; i < 64; i++){
        concat[i] = L[i - 32];
    }
    for(i = 0; i < 64; i++){
        X[i] = concat[IPInv[i] - 1];
    }
}
 
// crypt関数の代替実装
char *my_crypt(const char *key, const char *salt)
{
    int i, j;
    char shifted_key[8] = {0};
    char key_bit[64] = {0};
    char C[28], D[28];
    char Kn[16][48]; // 鍵スケジュール
    char Emod[48];
    char X[64] = {0};
    char crypt_str[11 + 1];
    static char result_str[256];
 
    // 1. 鍵スケジュール作成に使われる鍵を作る
    // 1-1. 引数keyを1ビット左シフトする
    for(i = 0; i < 8; i++){
        if(key[i] == 0) break;
        shifted_key[i] = (key[i] << 1);
    }
    // 1-2. ビットごとに分ける
    for(i = 0; i < 8; i++){
        for(j = 0; j < 8; j++){
            key_bit[i * 8 + j] = (shifted_key[i] >> (7 - j)) & 1;
        }
    }
 
    // 2. 鍵スケジュールを作る
    // 2-1. 転置選択1を施す
    for(i = 0; i < 28; i++){
        C[i] = key_bit[PC1c[i] - 1];
        D[i] = key_bit[PC1d[i] - 1];
    }
    // 2-2. シフトと置換選択2を施し鍵スケジュールを作る
    for(i = 0; i < 16; i++){
        left_shift(C, shift[i]);
        left_shift(D, shift[i]);
        for(j = 0; j < 24; j++){
            Kn[i][j     ] = C[PC2c[j]      - 1];
            Kn[i][j + 24] = D[PC2d[j] - 28 - 1];
        }
        printf("K%02d: ", i + 1); print_bit(Kn[i], 6);
    }
 
    // 3. saltを使って、拡張関数を修正する
    for(i = 0; i < 48; i++){
        Emod[i] = E[i];
    }
    for(i = 0; i < 2; i++){
        char c, k;
 
        c = salt[i];
        if(c > 'Z') c -= 6;
        if(c > '9') c -= 7;
        c -= '.';
        for(j = 0; j < 6; j++){
            if((c >> j) & 01){ // ビットが立っていたら変更
                k = Emod[6 * i + j];
                Emod[6 * i + j] = Emod[6 * i + j + 24];
                Emod[6 * i + j + 24] = k;
            }
         }
    }
    printf("Emod: "); for(i = 0; i < 48; i++){printf("%2d ", Emod[i]);} printf("\n");
 
    // 4. DESを25回繰り返す
    printf("input:    "); print_bit(X, 8);
    for(i = 0; i < 25; i++){
        des(X, Kn, Emod);
        printf("output%02d: ", i + 1); print_bit(X, 8);
    }
 
    // 5. ビットをASCII文字列にする
    for(i = 0; i < 11; i++){
        char c = 0;
 
        for(j = 0; j < 6; j++){ // 6ビットごとに一つにする
            c <<= 1;
            if((6 * i + j) < 64) c |= X[6 * i + j];
        }
 
        c += '.';
        if(c > '9') c+= 7;
        if(c > 'Z') c+= 6;
        crypt_str[i] = c;
    }
    crypt_str[11] = '\0';
 
    sprintf(result_str, "%s%s", salt, crypt_str);
    printf("%s\n", result_str);
 
    return result_str;
}

参考

http://ruffnex.oc.to/kenji/xrea/crypt.txt
- このページを大いに参考にしてます

「crypt関数の解説と実装」をウィキ内検索

最終更新：2010年01月17日 00:32

futada wiki

メニュー

更新履歴