補題：ＳＨＡ−１アルゴリズムを方程式にする

初期seedから日時を求める無謀な挑戦 - Plus Le Toolのための補題。
使う記号の定義は[id:plusletool:20130427:p2]参照。

アルゴリズムは手順（過程）を記述したものであり、方程式は関係（結果）を記述したものである。
それらは記述の仕方が異なるので、詳しく議論するにはどちらかに統一するのがよい。
ここではアルゴリズムを方程式に書き換えることにする。

まずＳＨＡ−１アルゴリズムがどのように記述されているか見てみよう。
次のコードはＣ＃で書かれたＳＨＡ−１アルゴリズムである。

using System;
using System.Collections.Generic;
using System.Text;

namespace Test {
	public class MySha1 {
		public byte[] ComputeHash(byte[] msg) {
			if( msg == null ) {
				throw new ArgumentNullException();
			} else if( msg.Length <= 0 ) {
				throw new ArgumentException();
			}

			long lengthMsg = msg.LongLength;
			long lengthBlk = ( ( ( lengthMsg + 8 ) >> 6 ) + 1 ) << 6;

			// メッセージデータを拡張
			byte[] blocks = new byte[lengthBlk];
			for( long i=0;i<lengthMsg;i++ ) {
				blocks[i] = msg[i];
			}
			blocks[lengthMsg] = 0x80;
			for( long i=lengthMsg+1;i<lengthBlk-8;i++ ) {
				blocks[i] = 0;
			}
			ulong len = (ulong)( lengthMsg * 8 );
			blocks[lengthBlk-8] = (byte)( ( len>>56 ) & 0xff );
			blocks[lengthBlk-7] = (byte)( ( len>>48 ) & 0xff );
			blocks[lengthBlk-6] = (byte)( ( len>>40 ) & 0xff );
			blocks[lengthBlk-5] = (byte)( ( len>>32 ) & 0xff );
			blocks[lengthBlk-4] = (byte)( ( len>>24 ) & 0xff );
			blocks[lengthBlk-3] = (byte)( ( len>>16 ) & 0xff );
			blocks[lengthBlk-2] = (byte)( ( len>> 8 ) & 0xff );
			blocks[lengthBlk-1] = (byte)( ( len     ) & 0xff );

			// ハッシュ化メインループ
			uint h0 = 0x67452301;
			uint h1 = 0xEFCDAB89;
			uint h2 = 0x98BADCFE;
			uint h3 = 0x10325476;
			uint h4 = 0xC3D2E1F0;
			uint[] words = new uint[80];
			for( long indexBlk=0;indexBlk<lengthBlk; ) {
				// ワードの初期化
				for( int i=0;i<16;i++ ) {
					words[i]  = ( (uint)blocks[indexBlk++] )<<24;
					words[i] |= ( (uint)blocks[indexBlk++] )<<16;
					words[i] |= ( (uint)blocks[indexBlk++] )<< 8;
					words[i] |= ( (uint)blocks[indexBlk++] );
				}
				for( int i=16;i<80;i++ ) {
					words[i] = CircularShiftLeft(words[i-3] ^ words[i-8] ^ words[i-14] ^ words[i-16],1);
				}

				// ハッシュなう
				uint a = h0;
				uint b = h1;
				uint c = h2;
				uint d = h3;
				uint e = h4;
				for( int t=0;t<80;t++ ) {
					uint tmp = CircularShiftLeft(a,5) + F(t,b,c,d) + e + words[t] + K(t);
					e = d;
					d = c;
					c = CircularShiftLeft(b,30);
					b = a;
					a = tmp;
				}
				h0 += a;
				h1 += b;
				h2 += c;
				h3 += d;
				h4 += e;
			}

			// ハッシュ値
			byte[] hash = new byte[20];
			hash[00] = (byte)( h0>>24 );
			hash[01] = (byte)( h0>>16 );
			hash[02] = (byte)( h0>> 8 );
			hash[03] = (byte)( h0     );
			hash[04] = (byte)( h1>>24 );
			hash[05] = (byte)( h1>>16 );
			hash[06] = (byte)( h1>> 8 );
			hash[07] = (byte)( h1     );
			hash[08] = (byte)( h2>>24 );
			hash[09] = (byte)( h2>>16 );
			hash[10] = (byte)( h2>> 8 );
			hash[11] = (byte)( h2     );
			hash[12] = (byte)( h3>>24 );
			hash[13] = (byte)( h3>>16 );
			hash[14] = (byte)( h3>> 8 );
			hash[15] = (byte)( h3     );
			hash[16] = (byte)( h4>>24 );
			hash[17] = (byte)( h4>>16 );
			hash[18] = (byte)( h4>> 8 );
			hash[19] = (byte)( h4     );

			return hash;
		}
		private uint CircularShiftLeft(uint target,int size) {
			return ( target << size ) | ( target >> (32-size) );
		}
		private uint F(int t,uint x,uint y,uint z) {
			if( t < 0 ) {
				throw new ArgumentOutOfRangeException();
			} else if( t < 20 ) {
				return ( x & y ) | ( ( ~x ) & z );
			} else if( t < 40 ) {
				return x ^ y ^ z;
			} else if( t < 60 ) {
				return ( x & y ) | ( x & z ) | ( y & z );
			} else if( t < 80 ) {
				return x ^ y ^ z;
			} else {
				throw new ArgumentOutOfRangeException();
			}
		}
		private uint K(int t) {
			if( t < 0 ) {
				throw new ArgumentOutOfRangeException();
			} else if( t < 20 ) {
				return 0x5A827999;
			} else if( t < 40 ) {
				return 0x6ED9EBA1;
			} else if( t < 60 ) {
				return 0x8F1BBCDC;
			} else if( t < 80 ) {
				return 0xCA62C1D6;
			} else {
				throw new ArgumentOutOfRangeException();
			}
		}

	}
}

割と適当に書いたから細かいところは各自調べて（
高速化とかまったく考えてないし、そもそもＳＨＡ−１でハッシュ化したいだけなら自作するまでもなくSystem.Security.Cryptography.SHA1を使えばいい話なので、最適化とか必要ないよねってことで。

いらないだろうけど動作確認用のプログラムも一応貼っておく。

using System;
using System.Collections.Generic;
using System.Text;

namespace Test {
	class Program {
		private static readonly MySha1 mySha1 = new MySha1();
		private static readonly System.Security.Cryptography.SHA1 sha1 = System.Security.Cryptography.SHA1Managed.Create();

		static void Main(string[] args) {
			Random rand = new Random();

			// メッセージデータを乱数列で初期化
			int msgLength = rand.Next(1000);
			byte[] msg = new byte[msgLength];
			rand.NextBytes(msg);

			// ハッシュ化
			byte[] value1 = mySha1.ComputeHash(msg);
			byte[] value2 = sha1.ComputeHash(msg);

			// 比較
			if( value1.Length == value2.Length ) {
				int length = value1.Length;
				bool b = true;
				for( int i=0;i<length;i++ ) {
					Console.WriteLine("{0:d2}: {1:x2} {2:x2}",i,value1[i],value2[i]);
					if( value1[i] != value2[i] ) {
						b = false;
					}
				}
				if( b ) {
					Console.WriteLine("value1 == value2");
				} else {
					Console.WriteLine("value1 != value2");
				}
			} else {
				Console.WriteLine("value1.Length != value2.Length");
			}

			Console.WriteLine("fin.");
			return;
		}

	}
}

とりあえずこのプログラムでＳＨＡ−１のアルゴリズムを簡単に見てみよう。
最初にメッセージデータ msg を拡張し、その値で blocks を初期化している。
メッセージデータの拡張によって追加されるデータ内容は、元のメッセージデータ msg のbyteサイズのみに依存して決まる。
この時追加されるデータは、拡張後のメッセージデータ（blocks）のbyte数が「元のメッセージデータ（msg）のbyte数に8を足した値より大きい64の倍数のうち最小の値」になるように追加される。
初期seed計算の場合、メッセージデータ（msg）のbyteサイズは52byteで固定なので、追加されるデータは「0x80,00,00,00,00,00,00,00,00,00,01,a0」の12byteで固定であり、したがって拡張後のデータ（blocks）のサイズも必ず64byteになる。
よって初期seed計算の場合に限るなら、本来のメッセージデータ（msg）ではなく拡張後のメッセージデータ（blocks）ＳＨＡ−１への入力値だったとみなすと後の考察に都合がいい。
初期seedから日時を求める無謀な挑戦 - Plus Le Toolの最初の表はその考え方に基いて書いてあり、この表のbyte欄が拡張後のメッセージデータ（blocks）である。

次に、ソース中の「ハッシュ化メインループ」において

for( long indexBlk=0;indexBlk<lengthBlk; ) {
	// 中略
	// （ blocks の64byteずつのループ）
	// （ words の初期化）
}

のループがあるが、先程も述べたように初期seed計算においては blocks のサイズは64byteなので、実際のループ回数は１回だけである（１回だけなのに「ループ」というのかというツッコミはおいといて）。
よってbyte配列 blocks をビッグエンディアンでuint型配列にしたものが words （の最初の16項）であり、これを使ってハッシュ値を計算している。

あるいはめんどうなのでいっそのこと、この words （の最初の16項）を初期seed計算の入力値と考えてもいいかもしれない。
そのように考えた場合、上記プログラムのメソッド部分は次のように書き換えられる。

public byte[] ComputeHash(uint[] w) {
	// ハッシュ化メインループ
	uint h0 = 0x67452301;
	uint h1 = 0xEFCDAB89;
	uint h2 = 0x98BADCFE;
	uint h3 = 0x10325476;
	uint h4 = 0xC3D2E1F0;
	uint[] words = new uint[80];
	{
		// ワードの初期化
		for( int i=0;i<16;i++ ) {
			words[i] = w[i];
		}
		for( int i=16;i<80;i++ ) {
			words[i] = CircularShiftLeft(words[i-3] ^ words[i-8] ^ words[i-14] ^ words[i-16],1);
		}

		// ハッシュなう
		uint a = h0;
		uint b = h1;
		uint c = h2;
		uint d = h3;
		uint e = h4;
		for( int t=0;t<80;t++ ) {
			uint tmp = CircularShiftLeft(a,5) + F(t,b,c,d) + e + words[t] + K(t);
			e = d;
			d = c;
			c = CircularShiftLeft(b,30);
			b = a;
			a = tmp;
		}
		h0 += a;
		h1 += b;
		h2 += c;
		h3 += d;
		h4 += e;
	}

	// ハッシュ値
	byte[] hash = new byte[20];
	hash[00] = (byte)( h0>>24 );
	//       :
	//       : （中略）
	//       :
	hash[19] = (byte)( h4     );

	return hash;
}

これを見ると、計算らしい計算をしているのは２ヶ所しかないことが分かる。
１つ目はこの部分。

for( int i=0;i<16;i++ ) {
	words[i] = w[i];
}
for( int i=16;i<80;i++ ) {
	words[i] = CircularShiftLeft(words[i-3] ^ words[i-8] ^ words[i-14] ^ words[i-16],1);
}

これを数学的に記述すると、次のようになる。

（＊１）

（※ words[i] は32bit（uint型）整数なので、今までの記法にあわせて大文字で とした。）
（＊１）をbit単位の式で記述し直すと、次のようになる。

（＊２）

（※ は の第bitである。）
この漸化式は「 〜 は 〜 の（法２のもとでの）線形変換によって求められる」と読むこともできる。
つまり、 〜 は 〜 の関数であり、しかもその関数の形は具体的には 〜 の（排他的論理和による）一次式で表されるということである。
一次式だから２次以上の項を含まないので、 〜 の一次式から簡単に 〜 を求められる（ただし解がある場合に限る）。
（なんかちょっと違う気がするけど……まぁ細かいことは後でちゃんと考えることにする。今回のメインはこっちじゃなくて次の部分なんだから。）

２つ目はこの部分。（初期値とか後処理部分は省略した。）

for( int t=0;t<80;t++ ) {
	uint tmp = CircularShiftLeft(a,5) + F(t,b,c,d) + e + words[t] + K(t);
	e = d;
	d = c;
	c = CircularShiftLeft(b,30);
	b = a;
	a = tmp;
}

これを数学的に記述すると次のようになる。

（＊３）

この（＊３）には無駄に文字が多いので少し減らしてみようか。
漸化式の第２〜５式より、次のことが言える。

（＊４）

これを漸化式の第１式に代入すれば次のようになる。

（＊５）

初項を次のようにおけば、（＊５）は で成り立つ。

（＊６）

整理すると、次のようになる。

（＊７）

もう少し詳しく見てみようか。
先述のプログラムによると、関数 および定数 は次のように表されるのだった。

（＊８）

（＊９）

これらを使うと、（＊７）の漸化式部分は次のように書き換えられる。

（＊10）

この式から、 は の関数であると言える。
（もう少し細かいことを言えば、 は の関数である。）

これでＳＨＡ−１アルゴリズムを漸化式で表すことができたので、ここからはこの漸化式を解いて方程式の形にしようと思う。
今回の場合は後ろから見ていくのがよさそうだ。
先述のプログラムによると、次の 〜 を順に並べたものがＳＨＡ−１のハッシュ値だった。

（＊11）

そして をつなげた値を初期seedとして使っているのだった。
とりあえず初期seedの上位32bitを 、下位32bitを と置いておく。

（＊12）

， は式変形時には値不明の変数として扱う必要があるが、実行時には既知の値として計算できる（つまりこれらは媒介変数である）。
一方 はただの計算過程で出てくるだけの文字で、最終的にはこれらは消去されることになる文字である。
文字を消去する最も単純な方法は「代入」なので、代入しやすいように（＊12）を について解く（と言っても定数項を移項するだけだが）。

（＊13）

ここで１つ注意しなければならない。
（＊12）は加算のオーバーフローによる第33bitを切り捨てており、実際には法 のもとに成立する式である。
よって（＊13）も同様に、法 のもとに成立すると考えられる。

（＊14）

もっとも、（＊14）をプログラムに戻せばオーバーフロー分は自動的に切り捨てられるのだから、わざわざ法を強調しなくてもいいのではないかという考え方もある。
よって以下、めんどうなので法 を適時省略して書くことにする。
めんどうついでに、（＊14）の右辺に新しい文字を割り当てておこうか。

（＊15）

また、（＊11）に戻るが、 が初期seedとして使われる一方、 は使わずに捨てられる値だった。

（＊11）再掲

よって は任意の値でよいので、 も任意の値でよい。
（∵「定数を（法 のもとに）算術加算する」「定数bitだけ循環シフトする」演算はいずれも全単射な演算であるので、 と 、 と 、 と はそれぞれ全単射（一対一対応）の関係にあるため。）
これも上と同様に、適当に新しい文字を割り当てておこう。

（＊16）

（＊15）（＊16）をまとめておく。

（＊17）

次に、 を後ろから順に消去していくことを考える。
まずは（＊10）を について解いておこう。

（＊10）再掲

（＊18）

（＊18）で、 の場合の式は次のようになる。

（＊19）

（＊19）に（＊17）を代入することで次式を得る。

（＊20）

本当はこの式をさらにbit単位に分解して記述したいところなのだが、算術和演算を含むためそう簡単にはいかない。
とはいえ、 の各bit が ， ， ， ， ， の関数であることは分かった。

次に、（＊18）において の場合は次のようになる。

（＊21）

（＊21）に（＊17）（＊20）を代入することで次式を得る。

（＊22）

括弧がひどいことになってるし式もかなり見づらくなってきてるけど、そこはどうでもいい。
重要なのは、 の各bit が ， ， ， ， ， ， の関数であるということだ。

同様に繰り返していけば、最終的に 〜 を ， ， ， ， ， 〜 の式で表すことができる。

（＊23）

【注意】
……このあたりで先に断っておくと、この式でピンと来た人はこの先を読まない方がいいかもしれない。
というのは、式（＊23）が具体的な式の形を表しておらず、よってここから先は抽象的な方法論でしか議論できないからだ。
実際、この方程式を解こうとすると「シャノン展開」と言う名の総当り計算をすることになり、現実的な計算量や計算時間をはるかに超えるだろうことは目に見えている。
進められるところまでは一応このまま続けるが、本来は（＊10）か（＊18）をbit単位の式に書きなおして議論するべきなのに難しいのでやむを得ず別の方法で進めている、ということを頭の片隅にでも置いて読んでいただければと思う。

（＊７）より、 〜 は定数だった。

（＊７）再掲

よって（＊23）の定数項 を移項して関数の中に含めてしまい、次のように再定義する。

（＊24）

一応排他的論理和で移項したけど、もしかしたら普通に減算で移行した方が計算が簡単になるかもしれない。
その辺りは実際の関数の形が分からないことには何ともいえないので後で考えるしかない。

さて（＊24）の５本の方程式は、bit単位で記述しなおせば32×５＝160本の（ブール関数の）方程式になる。

（＊25）

補題：任意のブール方程式の解き方 - Plus Le Toolの（＊15）〜（＊17）あたりで書いたように、ブール関数の連立方程式は次のようにして１つの方程式にしてしまうのがポイントだった。

補題：任意のブール方程式の解き方 - Plus Le Toolより抜粋

[id:plusletool:20130514:p1]（＊15）再掲

ところで、次の2つは同値である。

[id:plusletool:20130514:p1]（＊16）再掲

• かつ かつ …… かつ
• 

よって を次のように定義すれば、（＊15）は の形の1本の方程式にすることができる。

[id:plusletool:20130514:p1]（＊17）再掲

これを使って（＊25）を１つの方程式にしてしまおう。

（＊26）

（＊２）より、 〜 は 〜 の関数（一次式）である。

（＊２）再掲

具体的にどんな式かはまだ分からないが、とりあえず式が既知のものとして扱い（＊26）に代入すれば、 〜 を消去できる。

（＊27）

ところで、初期seedから日時を求める無謀な挑戦 - Plus Le Toolにも書いたように、512個の変数 〜 のうち53個が未知変数、240個が媒介変数、残りの219個が定数だった。
未知変数を 、媒介変数を 、定数を と命名し直すことにしよう。
ついでに を 、 を と再命名しよう。
ついでのついでに引数の順序も並べ替えておこう。
そのまたついでに定数 は値を代入して計算してしまおう。
……えーっと、こんなもんでいいかな？　これで（＊27）は次のようになる。少しは見やすくなったかな？

（＊28）

（＊28）において、左辺を についてシャノン展開する。

（＊29）

この各係数 は媒介変数 と任意変数 の関数である。
この値が０になる時、それを満たす の組み合わせが方程式（＊28）の解である。
よって、この係数が０になるような の組み合わせを探すことになる。

（＊30）

（＊30）において、左辺を についてシャノン展開する。

（＊31）

この各係数 は媒介変数 の関数なので、計算実行時には既知定数となっている。
これらのうち１つでも０であれば、（＊30）が解を持つので、元の方程式（＊28）も解を持つことになる。
よって係数 の値をすべて調べればいい。

……などと考えていたのでは、いくら時間とメモリがあっても解にはたどりつけないだろう。
なぜなら、係数 は 個もあるからだ。
係数の値は1bitだから単純に１係数あたり1bitぶんの記憶領域が必要と仮定しても、全部で約 テラバイト必要になる。
かなり速く見積もって１秒間に１億個の係数の値を計算できたとしても、約 兆年必要になる。
あー……うん。無理だね。

シャノン展開というのは理論上可能ということを示すには便利だけど、やってることは総当り代入計算と変わらないから実戦的な用途には向いてないんだよなぁ。
やっぱり実際の式の形を見てヒューマリスティックに解くしかないのかなぁ。
本当は（＊30）をちゃんとbit単位の式で記述してから議論したいんだけど、無理っぽいし……うーん。
もしかしたらうまいことプログラム書けばできるのかもしれないけど、これもメモリ足りるのかなぁ。
せめて（＊19）だけでも（欲を言えば（＊10）か（＊18）も）bit単位で記述できれば、話が変わってきそうな気がするのに。……残念。