http://www14.ocn.ne.jp/~bkclass/
B class impostor of information technology...
  
 
トップソフトウェアドキュメント免責事項連絡カンパ告知
 
  < 前の頁上の頁次の頁 >  
 
[プライバシーポリシー]

SHA-1の計算方法

SHA-1は認証やデジタル署名などに使用されるハッシュ関数です。 そのアルゴリズムが規定されているRFC3174の補足説明です。

注意事項

以降の説明は次の条件で行っています。

  • 1バイトは8ビットとする。
  • 1ワードは4バイト(32ビット)とする。
  • 理解しやすくするためバイト単位で説明をする。
  • C言語を対象にして説明をする。
  • longは4バイトの整数の変数とする。
  • unsigned longは4バイトの符号なし整数の変数とする。

概略

アルゴリズムは4つのステップでなりたっています。

ステップ1. メッセージの拡張
算出対象のメッセージを切りのいい長さまで拡張します。
ステップ2. 使用関数と使用定数の定義
計算に使用する関数と定数を準備します。
ステップ3. メッセージダイジェストの計算
64バイト毎にSHA-1の値を算出します。
ステップ4. 出力
結果を出力します。

アルゴリズム

SHA-1は以下の方法で算出します。

ステップ1. メッセージの拡張

算出対象のメッセージを切りのいい長さまで拡張します。

パディング

【引用】
SHA-1は、入力として提供されるメッセージまたはデータファイルのメッセージダイジェストを計算するために使用される。 メッセージまたはデータファイルは、bit 文字列と見なされる。 メッセージ長は、メッセージの bit 数（空メッセージは長さ 0）である。 メッセージの bit 数が 8 の倍数であれば、簡便さのためメッセージを 16 進数で表す。 メッセージに対してはパディングを行うが、その目的は、パディングを行った後のメッセージ長が 512 の倍数になるようにすることである。 SHA-1では、メッセージダイジェストを計算する際に、512bit のブロックごとに処理を行う。 以下では、このパディングがどのように行われるかについて記述する。 簡単に述べると、1つの"1"を付加し、その後にm個の"0"を付加して、 最後に 64bit の整数を付加することで、メッセージ長を 512 * n とする。 この 64 bit 整数というのは、オリジナルメッセージの長さである。 パディングの行われたメッセージは、その後 n 個の 512bit ブロックとして解釈され、SHA-1 により処理される。

バイト数が64の倍数となるようにメッセージを拡張します。 拡張は元のメッセージの末尾に0x80、それ以降に0x00のデータをm個、最後に8バイトの数値を付加して行われます。 その最後に追加する8バイトの整数値は、元のメッセージのビット数です。
SHA-1の計算は拡張したメッセージを64バイト毎に分割して行います。

【引用】
あるメッセージの長さ l が、l < 2^64 であるとする。 これを SHA-1 に入力する前に、 メッセージはその右側に対して以下のようなパディングを行う。

a. 1個の"1"を付加する。 例：オリジナルメッセージが"01010000"であるとき、パディングされたメッセージは"010100001"である。

b. "0"を付加する。 付加する"0"の個数はオリジナルメッセージの長さに依存する。 最後の 512bit ブロックにおける最後の 64bit は、オリジナルメッセージの長さ l を格納するために予約されている。 例：オリジナルメッセージが以下のようなbit 文字列であったとき、

    01100001 01100010 01100011 01100100 01100101

ステップ(a)の処理を行うと、以下のようになる。

    01100001 01100010 01100011 01100100 01100101 1

l = 40 であるため、上記の bit 数は 41 bit であり、407個の"0"が付加されて 448 bit とされる。 したがって、16進数で 次のようになる。

    61626364 65800000 00000000 00000000
    00000000 00000000 00000000 00000000
    00000000 00000000 00000000 00000000
    00000000 00000000

例えば“abcde”という5バイトの文字列の場合には、まず0x80の1バイトが足されます。 その後に全体の長さが56バイト(64-8)になるように、0x00が50バイト足されます。

[拡大]

拡張は必ず行われます。これは元のメッセージ長を64で割った際のあまりがちょうど56であった場合でも拡張されるということです。メッセージ長が56バイトならば120バイトに、120バイトなら184バイトに拡張されます。

最小で1バイト(0x80の1バイト)、最大で64バイトのデータが付加されて拡張されます。

ビット長の付加

【引用】
c. オリジナルメッセージの bit 数 l を 2 ワードで表記する。 l < 2^32 であれば、最初のワードはすべて 0 になる。 これらの 2 ワードをメッセージに付加する。 例：オリジナルメッセージが（b）と同じである場合、l = 40 となる （ l はパディングを行う前に計算することに注意）。 40 を 2 ワード表記すると16進数で 00000000 00000028 となる。 それゆえパディング処理により最終的に得られるメッセージは、16進数で次のようになる。

    61626364 65800000 00000000 00000000
    00000000 00000000 00000000 00000000
    00000000 00000000 00000000 00000000
    00000000 00000000 00000000 00000028

次に、元のメッセージのビット数を8バイトの整数値にしてその上位バイトから順に足します。 (この時にビット数がunsigned long {符号なし4バイトの整数値}に収まるのなら、上位4バイトはすべて0x00になります)
このビット長の付加でメッセージの大きさが64の倍数となります。

[拡大]

例えば“abcde”というメッセージの場合には、そのビット長40を付加します。

[拡大]

※ メッセージの拡張手順をまとめると以下のようになります。

  1. 1バイトのデータ(0x80)を足す。(必須)
  2. メッセージのバイト数を64で割った余りが56となるように0x00を足す。
  3. 元のメッセージのビット数を8バイトの整数値にしてその上位バイトから順に足す。(必須)

ステップ2. 使用関数と使用定数の定義

計算に使用する関数と定数を準備します。

関数の準備

【引用】
SHA-1 では、論理関数のシーケンス f(0), f(1),..., f(79) を使用する。 それぞれの f(t), 0 <= t <= 79 では、3 つの 32bit ワード B, C, D を処理し 1つの 32bit ワードを出力する。 ワード B, C, D に対し、f(t;B,C,D) を以下のように定義する。 
  f(t;B,C,D) = (B AND C) OR ((NOT B) AND D)         ( 0 <= t <= 19)
  f(t;B,C,D) = B XOR C XOR D                        (20 <= t <= 39)
  f(t;B,C,D) = (B AND C) OR (B AND D) OR (C AND D)  (40 <= t <= 59)
  f(t;B,C,D) = B XOR C XOR D                        (60 <= t <= 79)

SHA-1は80回の演算を行って求めますが、その際に使用する関数を準備します。 各関数はunsigned longのB, C, Dを引数にとり、以下のように定義します。

/* 関数1： 0〜19回目の演算で使用 */
unsigned long f00(unsigned long B, unsigned long C, unsigned long D) {
    return (B & C) | ((~B) & D);
}

/* 関数2：20〜39回目の演算で使用 */
unsigned long f20(unsigned long B, unsigned long C, unsigned long D) {
    return B ^ C ^ D;
}

/* 関数3：40〜59回目の演算で使用 */
unsigned long f40(unsigned long B, unsigned long C, unsigned long D) {
    return (B & C) | (B & D) | (C & D);
}

/* 関数4：60〜79回目の演算で使用 */
unsigned long f60(unsigned long B, unsigned long C, unsigned long D) {
    return B ^ C ^ D;
}

定数の準備

【引用】
SHA-1では、定数ワードのシーケンス K(0), K(1), ... , K(79) を使用する。 それぞれは、16 進表記で以下のように定義される。 
  K(t) = 5A827999  ( 0 <= t <= 19)
  K(t) = 6ED9EBA1  (20 <= t <= 39)
  K(t) = 8F1BBCDC  (40 <= t <= 59)
  K(t) = CA62C1D6  (60 <= t <= 79)

算出時にはunsigned long の配列定数 K[] が使用されます。 その配列は以下のように定義されます。

const unsigned long K[] = {
    0x5A827999,    /*  0〜19回目の演算で使用 */
    0x6ED9EBA1,    /* 20〜39回目の演算で使用 */
    0x8F1BBCDC,    /* 40〜59回目の演算で使用 */
    0xCA62C1D6     /* 60〜79回目の演算で使用 */
};

ステップ3. メッセージダイジェストの計算

64バイト毎にSHA-1の値を算出します。

【引用】
以下の 6.1 と 6.2 で示されている 2 つの方法は、どちらも同じダイジェスト値を出力する。 方法 2 は方法 1 に比べ、32bit ワード 64 個分の記憶域を使用しなくて済むが、ステップ c におけるそれぞれの W[t] のアドレス計算が複雑であるため実行時間が長くなるようである。 同じ結果を出力する他の計算方法も存在する。

計算方法は複数ありますが、ここでは方法1と方法2の二つを紹介します。 方法1は代表的な方法で、方法2はメモリ使用量を抑える事ができるが計算時間が多少長くなるような方法です。

方法1

【引用】
メッセージダイジェストは、4 章で示されているメッセージパディングを使用して計算する。

複数ある計算方法のうちの代表的なものです。 この方法では、ステップ1で拡張したメッセージを使用して計算します。

変数の準備
計算に使用する変数を準備します。
算出処理
SHA-1の値を算出します。

方法1：変数の準備

【引用】
計算に際して 2 つのバッファを使用する。 それぞれのバッファは 32bit ワード 5 つ分で構成されている。 さらに 32 bit ワード 80 個分のワードシーケンスを 1 つ使用する。 1 つの 5 ワードバッファにおけるそれぞれのワードを A,B,C,D,E とする。 もうひとつの 5 ワードバッファにおけるそれぞれのワードを H0, H1, H2, H3, H4 とする。 80 ワードシーケンスにおけるそれぞれのワードは W(0), W(1),..., W(79) とする。 そして 1 ワードのバッファ TEMP を使用する。

(中略)

ワードブロックを処理する前に、それぞれの H を以下のように初期化する（16 進で表記している）。 
  H0 = 67452301
  H1 = EFCDAB89
  H2 = 98BADCFE
  H3 = 10325476
  H4 = C3D2E1F0

計算に使用する変数を準備します。

unsigned long A, B, C, D, E;
unsigned long H0 = 0x67452301;
unsigned long H1 = 0xEFCDAB89;
unsigned long H2 = 0x98BADCFE;
unsigned long H3 = 0x10325476;
unsigned long H4 = 0xC3D2E1F0;
unsigned long W[80];
unsigned long TEMP;

方法1：算出処理

【引用】
そして M(1), M(2), ... , M(n) の計算を行う。 M(i)の処理を以下のように行う。

算出はステップ1で拡張したメッセージを64バイト毎のブロックに分割して行います。

ブロック毎の演算

各ブロックにa〜eの5段階で処理を行い、SHA-1の値を算出します。

方法1-a
【引用】
a. M(i)を、16個のワード W(0), W(1), ... , W(15) に分割する。ここで W(0) は 最上位ワードである。

ステップ1で拡張したメッセージを64バイト毎に分割して、配列W[0]〜W[15]にセットします。

int t;                   /* ループ変数 */
unsigned char *block;    /* 拡張したメッセージへのポインタ */

/* 拡張したメッセージへのポインタをblockにセット */
……

/* 配列W[0]〜W[15]に値セット */
for (t = 0; t < 16; t++) {
    W[t]  = block[t*4  ] << 24;
    W[t] |= block[t*4+1] << 16;
    W[t] |= block[t*4+2] <<  8;
    W[t] |= block[t*4+3];
}
[拡大]
方法1-b
【引用】
b. 16から79までのtに対して、以下の計算を行う。
W(t) = S^1(W(t-3) XOR W(t-8) XOR W(t-14) XOR W(t-16))

配列W[16]〜W[79]に以下のようにして値をセットします。

/* unsigned long値の各ビットを循環してシフトするマクロ */
#define SHA1CircularShift(bits,word) \
            (((word) << (bits)) | ((word) >> (32-(bits))))

int t;    /* ループ変数 */

/* 配列W[16]〜W[79]に値セット */
for (t = 16; t < 80; t++) {
    W[t] = SHA1CircularShift(1, W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16]);
}
方法1-c
【引用】
c. A, B, C, D, E をそれぞれ、A = H0, B = H1, C = H2, D = H3, E = H4 とする。

変数A, B, C, D, Eのそれぞれに、H0, H1, H2, H3, H4の値をセットします。

A = H0;
B = H1;
C = H2;
D = H3;
E = H4;
方法1-d
【引用】
d. 0から79までのtに対して、以下の計算を行う。 
  TEMP = S^5(A) + f(t;B,C,D) + E + W(t) + K(t);
  E = D; D = C; C = S^30(B); B = A; A = TEMP;

それぞれの変数・関数を用いて以下の計算を行います。

注意 関数f00, f20, f40, f60と配列定数K[]はステップ2で定義しています。 
/* unsigned long値の各ビットを循環してシフトするマクロ */
#define SHA1CircularShift(bits,word) \
            (((word) << (bits)) | ((word) >> (32-(bits))))

int t;    /* ループ変数 */

/* 0〜19回目の演算 */
for (t = 0; t < 20; t++) {
    TEMP = SHA1CircularShift(5, A) + f00(B, C, D) + E + W[t] + K[0];
    E = D;
    D = C;
    C = SHA1CircularShift(30, B);
    B = A;
    A = TEMP;
}

/* 20〜39回目の演算 */
for (t = 20; t < 40; t++) {
    TEMP = SHA1CircularShift(5, A) + f20(B, C, D) + E + W[t] + K[1];
    E = D;
    D = C;
    C = SHA1CircularShift(30, B);
    B = A;
    A = TEMP;
}

/* 40〜59回目の演算 */
for (t = 40; t < 60; t++) {
    TEMP = SHA1CircularShift(5, A) + f40(B, C, D) + E + W[t] + K[2];
    E = D;
    D = C;
    C = SHA1CircularShift(30, B);
    B = A;
    A = TEMP;
}

/* 60〜79回目の演算 */
for (t = 60; t < 80; t++) {
    TEMP = SHA1CircularShift(5, A) + f60(B, C, D) + E + W[t] + K[3];
    E = D;
    D = C;
    C = SHA1CircularShift(30, B);
    B = A;
    A = TEMP;
}
方法1-e
【引用】
e. HO, H1, H2, H3, H4 をそれぞれ、H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4 + E とする。

HO, H1, H2, H3, H4にA, B, C, D, Eを加算します。

H0 += A;
H1 += B;
H2 += C;
H3 += D;
H4 += E;

方法2

2つ目の方法です。方法1と比べるとメモリの使用をおさえる事ができますが実行時間が長くなります。

ブロック毎の演算

各ブロックにa〜dの4段階で処理を行い、SHA-1の値を算出します。

方法2-a
【引用】
a. M(i)を、16個のワード W(0), W(1), ... , W(15) に分割する。ここで W(0) は 最上位ワードである。

ステップ1で拡張したメッセージを64バイト毎に分割して、配列W[0]〜W[15]にセットします。

int t;                   /* ループ変数 */
unsigned char *block;    /* 拡張したメッセージへのポインタ */

/* 拡張したメッセージへのポインタをblockにセット */
……

/* 配列W[0]〜W[15]に値セット */
for (t = 0; t < 16; t++) {
    W[t]  = block[t*4  ] << 24;
    W[t] |= block[t*4+1] << 16;
    W[t] |= block[t*4+2] <<  8;
    W[t] |= block[t*4+3];
}
[拡大]
方法2-b
【引用】
b. A, B, C, D, E をそれぞれ、A = H0, B = H1, C = H2, D = H3, E = H4 とする。

変数A, B, C, D, Eのそれぞれに、H0, H1, H2, H3, H4の値をセットします。

A = H0;
B = H1;
C = H2;
D = H3;
E = H4;
方法2-c
【引用】
c. 0 から 79 までの t に対して、以下の計算を行う。 
  s = t AND MASK;
  if (t >= 16) W[s] = S^1(W[(s + 13) AND MASK] XOR W[(s + 8) AND MASK]
                             XOR W[(s + 2) AND MASK] XOR W[s]);
  TEMP = S^5(A) + f(t;B,C,D) + E + W[s] + K(t);
  E = D; D = C; C = S^30(B); B = A; A = TEMP;

それぞれの変数・関数を用いて以下の計算を行います。

注意 関数f00, f20, f40, f60と配列定数K[]はステップ2で定義しています。 
/* unsigned long値の各ビットを循環してシフトするマクロ */
#define SHA1CircularShift(bits,word) \
            (((word) << (bits)) | ((word) >> (32-(bits))))

int t;                                    /* ループ変数   */
unsigned long s;                          /* 演算用ワーク */
const unsigned long MASK = 0x0000000f;    /* 演算用マスク */

/* 0〜15回目の演算 */
for (t = 0; t < 16; t++) {
    s = t & MASK;
    TEMP = SHA1CircularShift(5, A) + f00(B, C, D) + E + W[s] + K[0];
    E = D;
    D = C;
    C = SHA1CircularShift(30, B);
    B = A;
    A = TEMP;
}

/* 16〜19回目の演算 */
for (t = 16; t < 20; t++) {
    s = t & MASK;
    W[s] = SHA1CircularShift(1,   W[(s+13) & MASK] ^ W[(s+8) & MASK]
                                ^ W[(s+2) & MASK] ^ W[s]);
    TEMP = SHA1CircularShift(5, A) + f00(B, C, D) + E + W[s] + K[0];
    E = D;
    D = C;
    C = SHA1CircularShift(30, B);
    B = A;
    A = TEMP;
}

/* 20〜39回目の演算 */
for (t = 20; t < 40; t++) {
    s = t & MASK;
    W[s] = SHA1CircularShift(1,   W[(s+13) & MASK] ^ W[(s+8) & MASK]
                                ^ W[(s+2) & MASK] ^ W[s]);
    TEMP = SHA1CircularShift(5, A) + f20(B, C, D) + E + W[s] + K[1];
    E = D;
    D = C;
    C = SHA1CircularShift(30, B);
    B = A;
    A = TEMP;
}

/* 40〜59回目の演算 */
for (t = 40; t < 60; t++) {
    s = t & MASK;
    W[s] = SHA1CircularShift(1,   W[(s+13) & MASK] ^ W[(s+8) & MASK]
                                ^ W[(s+2) & MASK] ^ W[s]);
    TEMP = SHA1CircularShift(5, A) + f40(B, C, D) + E + W[s] + K[2];
    E = D;
    D = C;
    C = SHA1CircularShift(30, B);
    B = A;
    A = TEMP;
}

/* 60〜79回目の演算 */
for (t = 60; t < 80; t++) {
    s = t & MASK;
    W[s] = SHA1CircularShift(1,   W[(s+13) & MASK] ^ W[(s+8) & MASK]
                                ^ W[(s+2) & MASK] ^ W[s]);
    TEMP = SHA1CircularShift(5, A) + f60(B, C, D) + E + W[s] + K[3];
    E = D;
    D = C;
    C = SHA1CircularShift(30, B);
    B = A;
    A = TEMP;
}
方法2-d
【引用】
d. HO, H1, H2, H3, H4 をそれぞれ、H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4 + E とする。

HO, H1, H2, H3, H4にA, B, C, D, Eを加算します。

H0 += A;
H1 += B;
H2 += C;
H3 += D;
H4 += E;

ステップ4. 出力

結果を出力します。

【引用】
M(n)の処理を行うと、メッセージダイジェストは、以下の5ワードで表される 160bit の 文字列として得られる。 
  H0 H1 H2 H3 H4

H0, H1, H2, H3, H4にSHA-1の値が格納されています。 出力する場合には各変数の上位バイトから順に16進数で行います。

[拡大]

サンプルプログラム

RFC3174のサンプル

RFC3174にはサンプルプログラムが付記されています。 サンプルプログラムを実行すると、決められたメッセージ(文字列)のSHA-1の値を算出して表示します。

ソースファイル：
sha1_src.zip (クリックでSkyDriveへ移動します)
5KB  MD5：09f82b0e928548327cf7d6c9e5cad57b
Windows版実行ファイル：
sha1_exe.zip (クリックでSkyDriveへ移動します)
16KB  MD5：8cafb94a4fdf0a7d247714427936b538

ソースファイルをコンパイルする際には、以下のようにします。

% gcc sha1test.c sha1.c -osha1

C:\> cl sha1test.c sha1.c -osha1

注意 プログラムではstdlint.hを使用しています。 このヘッダーが無いシステム上でコンパイルするには次のように各ファイルを修正してください。
  1. sha1.hを編集し、“#include <stdint.h>”の行を削除する。
  2. sha1.hにuint32_t, uint8_t, int_least16_tの定義を追加する。
    typedef unsigned long uint32_t;
typedef unsigned char uint8_t;
typedef short int_least16_t;
  3. sha1test.cを編集し、“#include <stdint.h>”の行を削除する。

雑記

（感想はMD5とほぼ同じです）

正直に言って専門家でないと良くわかりません。 RFC3174もいかにもな感じでわかりにくいです。 英語版Wikipediaが比較的簡単ですが、これで理解できない場合には手を出さない方が良いと思われます。

多くの言語では標準で関数（メソッド）が用意されていますので、それを利用するのが正解でしょう。 やはり自前で、という場合でもRFC3174のサンプルの流用で事足ります。

SHAは比較的安全だと言われていますが、それはビット長が大きいものです。 できる限りSHA-224より長いものを利用しましょう。

参考資料

  
  < 前の頁上の頁次の頁 >  
  Copyright © 1998-2012 m,KATO. | Web template created with doTemplate.