wiz.code

Visual Basic 2005でのコーディング

やろうと思えば関数ひとつで変換!もできると思いますが、かなり面倒なのでちゃんとクラスを作ります。 クラス名はSHA256でよいでしょう。 (ページが長くなるのでXml部分は省略しています。)

[ SHA256.vb ]
Public Class SHA256

End Class

定数

まずは、定数を用意します。 今回使う定数は、先ほどの定数Kと整数のビット数を表す「w」です。 定数kは符号なし32bit値(UInt32又はUInteger)として宣言します。 定数wは用意しなくてもかまいません。 FIPSでは定数wを計算に使用しているので用意しただけです。

[ SHA256.vb ]
Public Class SHA256

    ' ブロックの回転処理に使用する定数
    Private intK As UInt32() = { _
    &H428A2F98UI, &H71374491UI, &HB5C0FBCFUI, &HE9B5DBA5UI, _
    &H3956C25BUI, &H59F111F1UI, &H923F82A4UI, &HAB1C5ED5UI, _
    &HD807AA98UI, &H12835B01UI, &H243185BEUI, &H550C7DC3UI, _
    &H72BE5D74UI, &H80DEB1FEUI, &H9BDC06A7UI, &HC19BF174UI, _
    &HE49B69C1UI, &HEFBE4786UI, &HFC19DC6UI, &H240CA1CCUI, _
    &H2DE92C6FUI, &H4A7484AAUI, &H5CB0A9DCUI, &H76F988DAUI, _
    &H983E5152UI, &HA831C66DUI, &HB00327C8UI, &HBF597FC7UI, _
    &HC6E00BF3UI, &HD5A79147UI, &H6CA6351UI, &H14292967UI, _
    &H27B70A85UI, &H2E1B2138UI, &H4D2C6DFCUI, &H53380D13UI, _
    &H650A7354UI, &H766A0ABBUI, &H81C2C92EUI, &H92722C85UI, _
    &HA2BFE8A1UI, &HA81A664BUI, &HC24B8B70UI, &HC76C51A3UI, _
    &HD192E819UI, &HD6990624UI, &HF40E3585UI, &H106AA070UI, _
    &H19A4C116UI, &H1E376C08UI, &H2748774CUI, &H34B0BCB5UI, _
    &H391C0CB3UI, &H4ED8AA4AUI, &H5B9CCA4FUI, &H682E6FF3UI, _
    &H748F82EEUI, &H78A5636FUI, &H84C87814UI, &H8CC70208UI, _
    &H90BEFFFAUI, &HA4506CEBUI, &HBEF9A3F7UI, &HC67178F2UI}

    ' 1ワードあたりのビット数
    Private Const w As Integer = 32

End Class

ビットシフト・ビット回転関数

次にハッシュ計算に必要な演算関数を用意します。 いくつかはあらかじめ.NETで用意されてはいますが、ここでは出来る限りFIPSの数式に従えるように既存の演算子も関数化していきます。 まずはビット系演算です。さすがにXorはそのまま使って構いませんが、FIPSではビットシフトをSHR/SHL※、ビット回転をROTR/ROTL※と定義しているので、この名前の関数を作ります。 符号付き整数ではビット演算がうまく出来ないことがあるので、すべて「符号なし32bit値(UInt32 又は UInteger)」を使います。

※ SHA-256ではSHLとROTLを使用しません。なので書かなくてもOKです。
[ SHA256.vb ]
Public Class SHA256

    ' 右ビットシフト(SHift Right)
    Private Function SHR(ByVal v As UInt32, ByVal n As Integer) As UInt32
        Return v >> n
    End Function

    ' 左ビットシフト(SHift Left)
    Private Function SHL(ByVal v As UInt32, ByVal n As Integer) As UInt32
        Return v << n
    End Function

    ' 右ビット回転(ROTate Right)
    Private Function ROTR(ByVal v As UInt32, ByVal n As Integer) As UInt32
        Return (v >> n) Or (v << w - n)
    End Function

    ' 左ビット回転(ROTate Left)
    Private Function ROTL(ByVal v As UInt32, ByVal n As Integer) As UInt32
        Return (v << n) Or (v >> w - n)
    End Function

End Class

Visual Basic 6.0/VBScript/VBA/ASP(.NETを除く)等にはビットシフトも符号なし32bit値もないので、このあたりは自力でコーディングする必要があります。

オーバーフロー回避加算関数

もうひとつ演算関数を作ります。 ハッシュ計算では加算処理を使用しますが、桁あふれ(オーバーフロー)した分はすべて破棄されます。 ただ、普通に加算してしまうと当然のごとくオーバーフローが発生してしまうので、オーバーフローを起こさない加算関数を用意します。 それがこちら。

[ SHA256.vb ]
Public Class SHA256

    ' オーバーフローを回避して複数の値を加算
    Private Function SafeAdd(ByVal ParamArray Values As UInt32()) As UInt32
        Dim intReturn As UInt32 = Values(0)

            For i As Integer = 1 To Values.GetUpperBound(0)
                intReturn = ((intReturn And &H7FFFFFFFUI) + (Values(i) And &H7FFFFFFFUI)) Xor _
                            (intReturn And &H80000000UI) Xor (Values(i) And &H80000000UI)
            Next

        Return intReturn
    End Function
End Class

引数をParamArrayで指定しているので、加算したい値をいくつでも指定できます。 オーバーフローの回避方法はいくつかありますが、上記のコードでは1回の計算でオーバーフロー回避加算をしています。 原理は加算回路を知っている方ならすぐに分かると思います。 (オーバーフロー回避加算の原理についは、このページの最後で解説します。)

これで基本的な演算関数がそろいました。

ハッシュ計算用関数

次にハッシュ計算用の関数を用意します。 SHA-256では、6つの関数をハッシュ計算に使用します。 これらの計算式はFIPS 180-2 4.1.2 SHA-256 Functionsに掲載されています。 どの関数もビットシフトやビット回転等のビット演算しか行っていないので、ここではオーバーフローを意識する必要はありません。

[ SHA256.vb ]
Public Class SHA256

    ' Ch
    Private Function Ch(ByVal x As UInt32, ByVal y As UInt32, ByVal z As UInt32) As UInt32
        Return (x And y) Xor ((Not x) And z)
    End Function

    ' Maj
    Private Function Maj(ByVal x As UInt32, ByVal y As UInt32, ByVal z As UInt32) As UInt32
        Return (x And y) Xor (x And z) Xor (y And z)
    End Function

    ' シグマA0(Σ0)
    Private Function SigmaA0(ByVal x As UInt32) As UInt32
        Return ROTR(x, 2) Xor ROTR(x, 13) Xor ROTR(x, 22)
    End Function

    ' シグマA1(Σ1)
    Private Function SigmaA1(ByVal x As UInt32) As UInt32
        Return ROTR(x, 6) Xor ROTR(x, 11) Xor ROTR(x, 25)
    End Function

    ' シグマB0(σ0)
    Private Function SigmaB0(ByVal x As UInt32) As UInt32
        Return ROTR(x, 7) Xor ROTR(x, 18) Xor SHR(x, 3)
    End Function

    ' シグマB1(σ1)
    Private Function SigmaB1(ByVal x As UInt32) As UInt32
        Return ROTR(x, 17) Xor ROTR(x, 19) Xor SHR(x, 10)
    End Function

End Class

FIPSではシグマ関数を大文字(Σ)・小文字(σ)で分ていますが、VBでは大文字・小文字を区別できないのでA/Bとしました。 シグマBの中で呼ばれているSHRはビットシフト演算子に置き換えても構いません。 SHRを呼び出すのはここしかないので、置き換えたらSHRは消しちゃっても大丈夫です。 つまり、ROTRだけあればいいぢゃん、というオチ。

以上で演算やハッシュ計算に使う関数の用意は終わりました。 ここからハッシュ計算の中枢処理を組み立てていきます。

オーバーフロー回避加算の原理

符号なし32bit値 x, y の2項を加算する場合、最上位ビットだけマスクをかけてしまえばオーバーフローが発生することはありません。 ですので、まずそれぞれの最上位ビットをAnd演算子で除外して加算した値zを求めます。

z = (x And &h7FFFFFFFUI) + (y And &h7FFFFFFFUI)

次に、x, y, zの3項の最上位ビットを加算するのですが、x, y, zのうち2つ以上に最上位ビットがある場合はオーバーフローします。 ここで、x, y, zのそれぞれの最上位ビットとそれらを加算した場合のパターンを見てみましょう。 なお、桁上がりした分は削除しています。

A = x + y + z (オーバーフローは破棄)
    (1) (2) (3) (4) (5) (6) (7) (8)
x    0   1   0   1   0   1   0   1
y    0   0   1   1   0   0   1   1
z  + 0   0   0   0   1   1   1   1
-----------------------------------
A    0   1   1   0   1   0   0   1

この8パターンが考えられます。 ここからの考え方は二通りあります。

考え方1.(1)~(4)と(5)~(8)のzと解Aに注目する

    (1) (2) (3) (4) | (5) (6) (7) (8)
z    0   0   0   0  |  1   1   1   1
--------------------|----------------
A    0   1   1   0  |  1   0   0   1

(1)~(4)の解Aと(5)~(8)の解Aは、完全に逆転しています。 また、zに注目すると(1)~(4)は0、(5)~(8)は1となっており「zの値によって解Aのビットが反転した」と見ることが出来ます。 つまり、(x + y)の解をzの値で反転するように仕組めばよいわけです。 ビットの反転はXor演算で出来ますので、(x + y) Xor z と考えることが出来ます。

a = x + y (オーバーフローは破棄)
A = a Xor z
     (1) (2) (3) (4) (5) (6) (7) (8)
x     0   1   0   1   0   1   0   1
y   + 0   0   1   1   0   0   1   1
------------------------------------
a     0   1   1   0   0   1   1   0
z Xor 0   0   0   0   1   1   1   1
------------------------------------
A     0   1   1   0   1   0   0   1

次に、(1)~(2)と(3)~(4)の解aに注目します。 こちらも先ほどと同様に、yの値によってxの値が反転しています。 つまりここも、x Xor y と置き換えることが出来ます。 (5)~(8)についてxとyは同じパターンなので、同じくx Xor y で表せます。

a = x Xor y
A = a Xor z
     (1) (2) (3) (4) (5) (6) (7) (8)
x     0   1   0   1   0   1   0   1
y Xor 0   0   1   1   0   0   1   1
------------------------------------
a     0   1   1   0   0   1   1   0
z Xor 0   0   0   0   1   1   1   1
------------------------------------
A     0   1   1   0   1   0   0   1

最後に、aを「x Xor y」に置き換えて「x Xor y Xor z」とすれば、(1)~(8)のすべてのパターンに当てはまる式が完成します。

A = x Xor y Xor z
     (1) (2) (3) (4) (5) (6) (7) (8)
x     0   1   0   1   0   1   0   1
y     0   0   1   1   0   0   1   1
z Xor 0   0   0   0   1   1   1   1
------------------------------------
A     0   1   1   0   1   0   0   1

考え方2.x, y, z それぞれの「1」の出現数に注目する

A = x + y + z (オーバーフローは破棄)
    (1) (2) (3) (4) (5) (6) (7) (8)
x    0   1   0   1   0   1   0   1
y    0   0   1   1   0   0   1   1
z  + 0   0   0   0   1   1   1   1
-----------------------------------
A    0   1   1   0   1   0   0   1
-----------------------------------
N    0   1   1   2   1   2   2   3

上記の式にある「N」は、各パターンにおける「1」の出現回数を表しています。 見て解るとおり、Nが偶数の時はA=0、Nが奇数の時はA=1となっています。 このことから、1が遇数回出現したら解Aは0、1が奇数解出現したら解Aは1となります。 これはそのままXor演算の性質であるので「x Xor y Xor z」を導き出すことが出来ます。

上記を踏まえて加算処理

実際には、最上位ビットに対してこの処理を行うので、計算式は次のようになります。 さらに、さきほど求めたZは加算します。 zの最上位ビットはx, yとのXor演算で使っているので、ここでは下位31bitだけを加算します。

z = (x And &h7FFFFFFFUI) + (y And &h7FFFFFFFUI)
A = (x And &h80000000UI) Xor (y And &h80000000UI) Xor (z And &h80000000UI) + (z And &h7FFFFFFFUI)

    (x And &h80000000UI)
Xor (y And &h80000000UI)
Xor (z And &h80000000UI)
  + (z And &h7FFFFFFFUI)
------------------------
     A

今度は、zの扱いに注目します。 zは、最上位ビットと下位31bitの演算を別々に行っていますが、これをまとめて次のように置き換えることができます。

A = (x And &h80000000UI) Xor (y And &h80000000UI) Xor z

    (x And &h80000000UI)
Xor (y And &h80000000UI)
Xor (z And &hFFFFFFFFUI)
------------------------
     A

Xorは前の項のビットが0の場合は、後ろの項の値がそのまま解となります。 前の項、つまり
(x And &h80000000UI) Xor (y And &h80000000UI)は、最上位ビットしか処理していないので、結果としてzの下位31bitはそのままの形で解となります。 あとは、zをx, yから求める式に置き換えれば、1回の計算でオーバーフロー回避加算が可能になります。

A = (x And &h80000000UI) Xor (y And &h80000000UI) Xor
                   ((x And &h7FFFFFFFUI) + (y And &h7FFFFFFFUI))

ちなみに、この方法は「符号なし整数値」でしか使えません。 「符号つき整数」で行うと(x + y)の時点でオーバーフローする場合があります。 「符号なし」であれば8bit/16bit/32bit/64bitの各整数型で同じように計算できます。