The Pluto Scarab「Hash Functions」をPowerShellから再利用
前置き
薦めるに薦められないサイトがあって。
読みやすそうなサイトでしょう? でも上のキャプチャ、クリックして訪れてみた人はわかると思いますが、Wayback Machine ですよ、これ。残念なことに今やこんなことに：
このサイトにはね、お世話になったのです。昔、少人数のユーザしか利用しない「ユーザ登録制アプリケーション」を作ったときに、ユーザIDに利用するのに「32ビットの質の良いハッシュ関数はないか?」と探っていて見つけたの。で、最近気付いたのですけど、Wikipedia の Jenkins Hash ページ：
あ、The Pluto Scarab の検証が再利用されてるのかな? と思って。(リファレンスに言及がないので違うかもしれない。)
C# 環境持ってませんが
さて、本題はここから。
Hash Functionsの検証は、全て C# です、と。でね、アタシ、今の割と買ったばかりの PC には Visual Studio そのものを入れてない。入れる準備だけはしてるけどね、入れてません。こういうの、結構あるのですね。やりたいことそのものズバリの答えが C#、みたいな。その場合にね、「移植してやれ」というのはアリだけど、移植するからには、元のコードで動かないと厳しい。机上だけでの移植は、地獄だ。なんとか PowerShell だけで出来ないかなぁ、と、PowerShell に本気出そうかと思ったその日から考えていた。(そのときに考えてたのがまさにこの The Pluto Scarab。)
でだ。「PowerShell からスクリーンキャプチャ出来ねぇかなぁ?」と思って見つたこれ：
のソースコードを眺めてちょっと驚いてしまった：
Take-ScreenShot.ps1の抜粋
1 # C# code
2 $code = @'
3 using System;
4 using System.Runtime.InteropServices;
5 using System.Drawing;
6 using System.Drawing.Imaging;
7 namespace ScreenShotDemo
8 {
9 /// <summary>
10 /// Provides functions to capture the entire screen, or a particular window, and save it to a file.
11 /// </summary>
12 public class ScreenCapture
13 {
14 /// <summary>
15 /// Creates an Image object containing a screen shot the active window
16 /// </summary>
17 /// <returns></returns>
18 public Image CaptureActiveWindow()
19 {
20 return CaptureWindow( User32.GetForegroundWindow() );
21 }
22 /// <summary>
23 /// Creates an Image object containing a screen shot of the entire desktop
24 /// </summary>
25 /// <returns></returns>
26 public Image CaptureScreen()
27 {
28 return CaptureWindow( User32.GetDesktopWindow() );
29 }
30 /// <summary>
31 /// Creates an Image object containing a screen shot of a specific window
32 /// </summary>
33 /// <param name="handle">The handle to the window. (In windows forms, this is obtained by the Handle property)</param>
34 /// <returns></returns>
35 private Image CaptureWindow(IntPtr handle)
36 {
37 // get te hDC of the target window
38 IntPtr hdcSrc = User32.GetWindowDC(handle);
39 // get the size
40 User32.RECT windowRect = new User32.RECT();
41 User32.GetWindowRect(handle,ref windowRect);
42 int width = windowRect.right - windowRect.left;
43 int height = windowRect.bottom - windowRect.top;
44 // create a device context we can copy to
45 IntPtr hdcDest = GDI32.CreateCompatibleDC(hdcSrc);
46 // create a bitmap we can copy it to,
47 // using GetDeviceCaps to get the width/height
48 IntPtr hBitmap = GDI32.CreateCompatibleBitmap(hdcSrc,width,height);
49 // select the bitmap object
50 IntPtr hOld = GDI32.SelectObject(hdcDest,hBitmap);
51 // bitblt over
52 GDI32.BitBlt(hdcDest,0,0,width,height,hdcSrc,0,0,GDI32.SRCCOPY);
53 // restore selection
54 GDI32.SelectObject(hdcDest,hOld);
55 // clean up
56 GDI32.DeleteDC(hdcDest);
57 User32.ReleaseDC(handle,hdcSrc);
58 // get a .NET image object for it
59 Image img = Image.FromHbitmap(hBitmap);
60 // free up the Bitmap object
61 GDI32.DeleteObject(hBitmap);
62 return img;
63 }
64 /// <summary>
65 /// Captures a screen shot of the active window, and saves it to a file
66 /// </summary>
67 /// <param name="filename"></param>
68 /// <param name="format"></param>
69 public void CaptureActiveWindowToFile(string filename, ImageFormat format)
70 {
71 Image img = CaptureActiveWindow();
72 img.Save(filename,format);
73 }
74 /// <summary>
75 /// Captures a screen shot of the entire desktop, and saves it to a file
76 /// </summary>
77 /// <param name="filename"></param>
78 /// <param name="format"></param>
79 public void CaptureScreenToFile(string filename, ImageFormat format)
80 {
81 Image img = CaptureScreen();
82 img.Save(filename,format);
83 }
84
85 /// <summary>
86 /// Helper class containing Gdi32 API functions
87 /// </summary>
88 private class GDI32
89 {
90
91 public const int SRCCOPY = 0x00CC0020; // BitBlt dwRop parameter
92 [DllImport("gdi32.dll")]
93 public static extern bool BitBlt(IntPtr hObject,int nXDest,int nYDest,
94 int nWidth,int nHeight,IntPtr hObjectSource,
95 int nXSrc,int nYSrc,int dwRop);
96 [DllImport("gdi32.dll")]
97 public static extern IntPtr CreateCompatibleBitmap(IntPtr hDC,int nWidth,
98 int nHeight);
99 [DllImport("gdi32.dll")]
100 public static extern IntPtr CreateCompatibleDC(IntPtr hDC);
101 [DllImport("gdi32.dll")]
102 public static extern bool DeleteDC(IntPtr hDC);
103 [DllImport("gdi32.dll")]
104 public static extern bool DeleteObject(IntPtr hObject);
105 [DllImport("gdi32.dll")]
106 public static extern IntPtr SelectObject(IntPtr hDC,IntPtr hObject);
107 }
108
109 /// <summary>
110 /// Helper class containing User32 API functions
111 /// </summary>
112 private class User32
113 {
114 [StructLayout(LayoutKind.Sequential)]
115 public struct RECT
116 {
117 public int left;
118 public int top;
119 public int right;
120 public int bottom;
121 }
122 [DllImport("user32.dll")]
123 public static extern IntPtr GetDesktopWindow();
124 [DllImport("user32.dll")]
125 public static extern IntPtr GetWindowDC(IntPtr hWnd);
126 [DllImport("user32.dll")]
127 public static extern IntPtr ReleaseDC(IntPtr hWnd,IntPtr hDC);
128 [DllImport("user32.dll")]
129 public static extern IntPtr GetWindowRect(IntPtr hWnd,ref RECT rect);
130 [DllImport("user32.dll")]
131 public static extern IntPtr GetForegroundWindow();
132 }
133 }
134 }
135 '@
136 #User Add-Type to import the code
137 add-type $code -ReferencedAssemblies 'System.Windows.Forms','System.Drawing'
138 #Create the object for the Function
139 $capture = New-Object ScreenShotDemo.ScreenCapture
ううん??? これ、C# をダイレクトに使ってない?
実はこれを動かすのにまだ成功できていないんだけど、「C# をそのまま動かせる」ことに興味津々になってしまった。
ここに辿り着いた後で改めて調べなおしてみると、結構これについて触れている人がいた：
どうにも「あまり用途なさそう」とか「C# から PowerShell を呼び出すことは良くありますが」とか、ちがくね、とは思うけど、それは最後に触れるとして。今は Hash Functions の検証プログラムを動かすことに専念。
オリジナルの検証プログラムはここにあります。で、public じゃなかったものを public にしたりとか多少 C# コードも触りつつこんなんなりました：
hash.ps1
1 $cs = @'
2 using System;
3 using System.Security.Cryptography;
4 using System.Drawing;
5
6 public class Rand : System.Random
7 {
8 RandomNumberGenerator rng = new RNGCryptoServiceProvider();
9 byte[] b = new byte[4];
10
11 protected override double Sample()
12 {
13 rng.GetBytes(b);
14 uint u = BitConverter.ToUInt32(b, 0);
15 return u / (uint.MaxValue + 1.0);
16 }
17 }
18
19 public class ConsoleApp
20 {
21 static Rand rand = new Rand();
22
23 [STAThread]
24 public static void Main(string[] args)
25 {
26 HashFunction hf = new SBoxHash();
27 AvalancheTest(hf);
28 BitCorrelationTest(hf);
29 BucketTest(hf);
30 Console.Write("\r\n>");
31 Console.ReadLine();
32 }
33
34 private static void GenerateSBox()
35 {
36 byte[] b = new byte[4];
37 for (int i = 0; i < 256; i++)
38 {
39 rand.NextBytes(b);
40 uint s = BitConverter.ToUInt32(b, 0);
41 Console.Write("0x{0:X8}, ", s);
42 if (i % 4 == 3)
43 Console.WriteLine();
44 }
45 }
46
47 static void BitCorrelationTest(HashFunction hf)
48 {
49 int[,] H = new int[32, 32];
50 for (int i=0; i<10000; i++)
51 {
52 byte[] key = null;
53 switch (rand.Next(3))
54 {
55 case 0:
56 key = HashFunction.GetUniformKey();
57 break;
58 case 1:
59 key = HashFunction.GetTextKey();
60 break;
61 case 2:
62 key = HashFunction.GetSparseKey();
63 break;
64 }
65 uint hash = hf.ComputeHash(key);
66 for (int j=0; j<32; j++)
67 for (int k=0; k<32; k++)
68 {
69 if (((hash & (1U << j)) != 0) == ((hash & (1U << k)) != 0))
70 H[j, k]++;
71 else
72 H[j, k]--;
73 }
74 }
75
76 using (Bitmap bmp = new Bitmap(255, 255))
77 using (Graphics g = Graphics.FromImage(bmp))
78 {
79 g.DrawLine(Pens.Black, 63, 0, 63, 255);
80 g.DrawLine(Pens.Black, 127, 0, 127, 255);
81 g.DrawLine(Pens.Black, 191, 0, 191, 255);
82 g.DrawLine(Pens.Black, 0, 63, 255, 63);
83 g.DrawLine(Pens.Black, 0, 127, 255, 127);
84 g.DrawLine(Pens.Black, 0, 191, 255, 191);
85 for (int j=0; j<32; j++)
86 for (int k=0; k<32; k++)
87 {
88 Brush br;
89 if (H[j,k]<-233)
90 br = Brushes.Red;
91 else if (H[j,k]<-199)
92 br = Brushes.Orange;
93 else if (H[j,k]<199)
94 br = Brushes.LightGray;
95 else if (H[j,k]>233)
96 br = Brushes.GreenYellow;
97 else
98 br = Brushes.YellowGreen;
99 g.FillRectangle(br, 8*j + 1, 8*k + 1, 5, 5);
100 }
101 bmp.Save(hf.ToString() + "-bits.gif");
102 }
103 }
104
105 static int[,] matrix;
106
107 static void InitMatrix(int width)
108 {
109 matrix = new int[width, 32];
110 }
111
112 static void Tally(HashFunction hf, byte[] key)
113 {
114 uint h0 = hf.ComputeHash(key);
115 if (key.Length <= 6)
116 {
117 for (int i=0; i<key.Length; i++)
118 for (int j=0; j<8; j++)
119 {
120 key[i] ^= (byte) (1 << j);
121 uint h1 = hf.ComputeHash(key) ^ h0;
122 key[i] ^= (byte) (1 << j);
123 int x = i*8 + j;
124 for (int y=0; y<32; y++)
125 {
126 if ((h1 & 1) != 0)
127 matrix[x, y]++;
128 h1 >>= 1;
129 }
130 }
131 }
132 else
133 {
134 for (int j=0; j<8; j++)
135 {
136 key[0] ^= (byte) (1 << j);
137 uint h1 = hf.ComputeHash(key) ^ h0;
138 key[0] ^= (byte) (1 << j);
139 for (int y=0; y<32; y++)
140 {
141 if ((h1 & 1) != 0)
142 matrix[j, y]++;
143 h1 >>= 1;
144 }
145 key[key.Length - 1] ^= (byte) (1 << j);
146 h1 = hf.ComputeHash(key) ^ h0;
147 key[key.Length - 1] ^= (byte) (1 << j);
148 for (int y=0; y<32; y++)
149 {
150 if ((h1 & 1) != 0)
151 matrix[j + 8, y]++;
152 h1 >>= 1;
153 }
154 }
155 }
156 }
157
158 static void RenderMatrix(Graphics g, uint trials)
159 {
160 int sc = 8;
161 uint o3 = trials / 3;
162 uint t3 = trials * 2 / 3;
163 for (int x=0; x<matrix.GetLength(0); x++)
164 for (int y=0; y<matrix.GetLength(1); y++)
165 {
166 Brush br;
167 if (matrix[x, y] == 0 || matrix[x, y] == trials)
168 br = Brushes.Red;
169 else if (matrix[x, y] < o3 || matrix[x, y] > t3)
170 br = Brushes.Orange;
171 else
172 br = Brushes.Green;
173 g.FillRectangle(br, sc * (matrix.GetLength(1) - 1 - y) + 1, sc * x + 1, sc - 3, sc - 3);
174 }
175 }
176
177 static void AvalancheTest(HashFunction hf)
178 {
179 int sc = 8;
180
181 Console.WriteLine("\r\n{0}", hf);
182
183 Console.WriteLine("\r\nTwo-octet keys");
184 using (Bitmap bmp = new Bitmap(32 * sc - 1, 16 * sc - 1))
185 using (Graphics g = Graphics.FromImage(bmp))
186 {
187 g.DrawLine(Pens.Black, 8*sc-1, 0, 8*sc-1, 16*sc-1);
188 g.DrawLine(Pens.Black, 16*sc-1, 0, 16*sc-1, 16*sc-1);
189 g.DrawLine(Pens.Black, 24*sc-1, 0, 24*sc-1, 16*sc-1);
190 InitMatrix(16);
191 byte[] key = new byte[2];
192 for (int i=0; i<65536; i++)
193 {
194 key[0] = (byte) (i & 0xFF);
195 key[1] = (byte) (i >> 8);
196 Tally(hf, key);
197 }
198 RenderMatrix(g, 65536);
199 bmp.Save(hf.ToString() + "-2.gif");
200 }
201
202 RandomNumberGenerator rng = new RNGCryptoServiceProvider();
203 Console.WriteLine("Four-octet keys");
204 using (Bitmap bmp = new Bitmap(32 * sc - 1, 32 * sc - 1))
205 using (Graphics g = Graphics.FromImage(bmp))
206 {
207 g.DrawLine(Pens.Black, 8 * sc - 1, 0, 8 * sc - 1, 32 * sc - 1);
208 g.DrawLine(Pens.Black, 16 * sc - 1, 0, 16 * sc - 1, 32 * sc - 1);
209 g.DrawLine(Pens.Black, 24 * sc - 1, 0, 24 * sc - 1, 32 * sc - 1);
210 InitMatrix(32);
211 byte[] key = new byte[4];
212 uint trials = 32768;
213 for (int i = 0; i < trials; i++)
214 {
215 rng.GetBytes(key);
216 Tally(hf, key);
217 }
218 RenderMatrix(g, trials);
219 bmp.Save(hf.ToString() + "-4.gif");
220 }
221
222 Console.WriteLine("Five-octet keys");
223 using (Bitmap bmp = new Bitmap(32 * sc - 1, 40 * sc - 1))
224 using (Graphics g = Graphics.FromImage(bmp))
225 {
226 g.DrawLine(Pens.Black, 8 * sc - 1, 0, 8 * sc - 1, 40 * sc - 1);
227 g.DrawLine(Pens.Black, 16 * sc - 1, 0, 16 * sc - 1, 40 * sc - 1);
228 g.DrawLine(Pens.Black, 24 * sc - 1, 0, 24 * sc - 1, 40 * sc - 1);
229 InitMatrix(40);
230 byte[] key = new byte[5];
231 uint trials = 32768;
232 for (int i = 0; i < trials; i++)
233 {
234 rng.GetBytes(key);
235 Tally(hf, key);
236 }
237 RenderMatrix(g, trials);
238 bmp.Save(hf.ToString() + "-5.gif");
239 }
240
241 Console.WriteLine("Three-octet keys");
242 using (Bitmap bmp = new Bitmap(32 * sc - 1, 24 * sc - 1))
243 using (Graphics g = Graphics.FromImage(bmp))
244 {
245 g.DrawLine(Pens.Black, 8 * sc - 1, 0, 8 * sc - 1, 24 * sc - 1);
246 g.DrawLine(Pens.Black, 16 * sc - 1, 0, 16 * sc - 1, 24 * sc - 1);
247 g.DrawLine(Pens.Black, 24 * sc - 1, 0, 24 * sc - 1, 24 * sc - 1);
248 InitMatrix(40);
249 byte[] key = new byte[3];
250 uint trials = 32768;
251 for (int i = 0; i < trials; i++)
252 {
253 rng.GetBytes(key);
254 Tally(hf, key);
255 }
256 RenderMatrix(g, trials);
257 bmp.Save(hf.ToString() + "-3.gif");
258 }
259
260 rng = new RNGCryptoServiceProvider();
261 Console.WriteLine("256-octet keys");
262 using (Bitmap bmp = new Bitmap(32 * sc - 1, 16 * sc - 1))
263 using (Graphics g = Graphics.FromImage(bmp))
264 {
265 g.DrawLine(Pens.Black, 8*sc-1, 0, 8*sc-1, 16*sc-1);
266 g.DrawLine(Pens.Black, 16*sc-1, 0, 16*sc-1, 16*sc-1);
267 g.DrawLine(Pens.Black, 24*sc-1, 0, 24*sc-1, 16*sc-1);
268 InitMatrix(16);
269 byte[] key = new byte[256];
270 uint trials = 32768;
271 for (int i=0; i<trials; i++)
272 {
273 rng.GetBytes(key);
274 Tally(hf, key);
275 }
276 RenderMatrix(g, trials);
277 bmp.Save(hf.ToString() + "-256.gif");
278 }
279 }
280
281 static void BucketTest(HashFunction hf)
282 {
283 GetRandomKey[] keyfunc = {
284 new GetRandomKey(HashFunction.GetUniformKey),
285 new GetRandomKey(HashFunction.GetTextKey),
286 new GetRandomKey(HashFunction.GetSparseKey),
287 };
288
289 Console.WriteLine("\r\n{0}", hf);
290 Console.WriteLine("\r\n Uniform keys Text keys Sparse keys");
291 Console.WriteLine("\r\nBits Lower Upper Lower Upper Lower Upper");
292 for (int bits=1; bits<=16; bits++)
293 {
294 Console.Write("{0,2} ", bits);
295 foreach (GetRandomKey getKey in keyfunc)
296 {
297 Console.Write(" ");
298 uint mask = (1U << bits) - 1U;
299 int E = 100;
300 for (int lsb=0; lsb<32; lsb += 32-bits)
301 {
302 if (hf is FNV)
303 {
304 if (lsb == 0)
305 hf = new FNV(bits);
306 else
307 hf = new FNV();
308 }
309 int[] buckets = new int[1 << bits];
310 int n = E * buckets.Length;
311 for (int i=0; i<n; i++)
312 {
313 byte[] key = getKey();
314 uint hash = hf.ComputeHash(key);
315 uint bucket = (hash >> lsb) & mask;
316 buckets[bucket]++;
317 }
318 double X = 0.0;
319 double p;
320 for (int i=0; i<buckets.Length; i++)
321 {
322 double err = buckets[i] - E;
323 X += err * err / E;
324 p = buckets[i] / (double)n;
325 }
326 p = ChiSq(X, buckets.Length - 1);
327 Console.Write(" {0:0.000}", p);
328 }
329 }
330 Console.WriteLine();
331 }
332 }
333
334 static double ChiSq(double x, int n)
335 {
336 double q, t, p;
337 int k, a;
338
339 if (n == 1 && x > 1000)
340 return 0.0;
341
342 if (x > 1000 || n > 1000)
343 {
344 q = ChiSq((x - n) * (x - n) / (2 * n), 1) / 2;
345 if (x > n)
346 return q;
347 else
348 return 1 - q;
349 }
350
351 p = Math.Exp(-0.5 * x);
352 if ((n % 2) == 1)
353 {
354 p *= Math.Sqrt(2 * x / Math.PI);
355 }
356
357 k = n;
358 while (k >= 2)
359 {
360 p *= x / k;
361 k -= 2;
362 }
363
364 t = p;
365 q = -1;
366 a = n;
367 while (q != p)
368 {
369 a += 2;
370 t *= x /a;
371 q = p;
372 p += t;
373 }
374 if (p > 1)
375 p = 1;
376
377 return 1 - p;
378 }
379 }
380
381 public delegate byte[] GetRandomKey();
382
383 public abstract class HashFunction
384 {
385 static RandomNumberGenerator rng = new RNGCryptoServiceProvider();
386 static byte[] b = new byte[4];
387
388 public abstract uint ComputeHash(byte[] data);
389
390 private static int GetRandomLength()
391 {
392 rng.GetBytes(b);
393 uint s = BitConverter.ToUInt32(b, 0);
394 double x = 1 - s / (uint.MaxValue + 1.0);
395 return (int) Math.Floor(Math.Sqrt(-800.0 * Math.Log(x)));
396 }
397
398 public static byte[] GetUniformKey()
399 {
400 // with 8 bits/byte we need at least two octets
401 int length = GetRandomLength() + 2;
402 byte[] key = new byte[length];
403 rng.GetBytes(key);
404 return key;
405 }
406
407 public static byte[] GetTextKey()
408 {
409 // with 4.34 bits/byte we need at least 4 octets
410 int length = GetRandomLength() + 4;
411 byte[] key = new byte[length];
412 rng.GetBytes(key);
413 for (int i=0; i<length; i++)
414 key[i] = (byte) (65 + (key[i] * key[i] * 26) / 65026);
415 return key;
416 }
417
418 public static byte[] GetSparseKey()
419 {
420 // with 3 bits/byte we need at least 6 octets
421 int length = GetRandomLength() + 6;
422 byte[] key = new byte[length];
423 rng.GetBytes(key);
424 for (int i=0; i<length; i++)
425 key[i] = (byte)(1 << (key[i] & 7));
426 return key;
427 }
428 }
429
430 public class SimpleHash : HashFunction
431 {
432 public override uint ComputeHash(byte[] data)
433 {
434 uint hash = 1;
435 foreach (byte b in data)
436 hash = (hash + b) * 0x50003;
437 return hash;
438 }
439 }
440
441 public class FakeHash : HashFunction
442 {
443 RandomNumberGenerator rng = new RNGCryptoServiceProvider();
444 byte[] b = new byte[4];
445
446 public override uint ComputeHash(byte[] data)
447 {
448 rng.GetBytes(b);
449 return (uint) (b[0] + 256U * b[1] + 65536U * b[2] + 16777216U * b[3]);
450 }
451 }
452
453 public class FNV : HashFunction
454 {
455 int shift;
456 uint mask;
457
458 public FNV()
459 {
460 shift = 0;
461 mask = 0xFFFFFFFF;
462 }
463
464 public FNV(int bits)
465 {
466 shift = 32 - bits;
467 mask = (1U << shift) - 1U;
468 }
469
470 public override uint ComputeHash(byte[] data)
471 {
472 uint hash = 2166136261;
473 foreach (byte b in data)
474 hash = (hash * 16777619) ^ b;
475 if (shift == 0)
476 return hash;
477 else
478 return (hash ^ (hash >> shift)) & mask;
479 }
480 }
481
482 public class ModifiedFNV : HashFunction
483 {
484 public override uint ComputeHash(byte[] data)
485 {
486 const uint p = 16777619;
487 uint hash = 2166136261;
488 foreach (byte b in data)
489 hash = (hash ^ b) * p;
490 hash += hash << 13;
491 hash ^= hash >> 7;
492 hash += hash << 3;
493 hash ^= hash >> 17;
494 hash += hash << 5;
495 return hash;
496 }
497 }
498
499 public class Jenkins96 : HashFunction
500 {
501 uint a, b, c;
502
503 void Mix()
504 {
505 a -= b; a -= c; a ^= (c>>13);
506 b -= c; b -= a; b ^= (a<<8);
507 c -= a; c -= b; c ^= (b>>13);
508 a -= b; a -= c; a ^= (c>>12);
509 b -= c; b -= a; b ^= (a<<16);
510 c -= a; c -= b; c ^= (b>>5);
511 a -= b; a -= c; a ^= (c>>3);
512 b -= c; b -= a; b ^= (a<<10);
513 c -= a; c -= b; c ^= (b>>15);
514 }
515
516 public override uint ComputeHash(byte[] data)
517 {
518 int len = data.Length;
519 a = b = 0x9e3779b9;
520 c = 0;
521 int i = 0;
522 while (i + 12 <= len)
523 {
524 a += (uint)data[i++] |
525 ((uint)data[i++] << 8) |
526 ((uint)data[i++] << 16) |
527 ((uint)data[i++] << 24);
528 b += (uint)data[i++] |
529 ((uint)data[i++] << 8) |
530 ((uint)data[i++] << 16) |
531 ((uint)data[i++] << 24);
532 c += (uint)data[i++] |
533 ((uint)data[i++] << 8) |
534 ((uint)data[i++] << 16) |
535 ((uint)data[i++] << 24);
536 Mix();
537 }
538 c += (uint) len;
539 if (i < len)
540 a += data[i++];
541 if (i < len)
542 a += (uint)data[i++] << 8;
543 if (i < len)
544 a += (uint)data[i++] << 16;
545 if (i < len)
546 a += (uint)data[i++] << 24;
547 if (i < len)
548 b += (uint)data[i++];
549 if (i < len)
550 b += (uint)data[i++] << 8;
551 if (i < len)
552 b += (uint)data[i++] << 16;
553 if (i < len)
554 b += (uint)data[i++] << 24;
555 if (i < len)
556 c += (uint)data[i++] << 8;
557 if (i < len)
558 c += (uint)data[i++] << 16;
559 if (i < len)
560 c += (uint)data[i++] << 24;
561 Mix();
562 return c;
563 }
564 }
565
566 public class Jenkins32 : HashFunction
567 {
568 uint key;
569
570 void Mix()
571 {
572 key += (key << 12);
573 key ^= (key >> 22);
574 key += (key << 4);
575 key ^= (key >> 9);
576 key += (key << 10);
577 key ^= (key >> 2);
578 key += (key << 7);
579 key ^= (key >> 12);
580 }
581
582 public override uint ComputeHash(byte[] data)
583 {
584 key = 1;
585 foreach (byte b in data)
586 {
587 key += b;
588 Mix();
589 }
590 return key;
591 }
592 }
593
594 public class SHA1Hash : HashFunction
595 {
596 SHA1 sha = SHA1.Create();
597
598 public override uint ComputeHash(byte[] data)
599 {
600 byte[] hash = sha.ComputeHash(data);
601 return BitConverter.ToUInt32(hash, 0);
602 }
603 }
604
605
606 public class MD : HashFunction
607 {
608 MD5 md5 = MD5.Create();
609
610 public override uint ComputeHash(byte[] data)
611 {
612 byte[] hash = md5.ComputeHash(data);
613 return BitConverter.ToUInt32(hash, 0);
614 }
615 }
616
617 public class Cheater : HashFunction
618 {
619 public override uint ComputeHash(byte[] data)
620 {
621 byte[] b = new byte[4];
622 int i = 0;
623 while (i < 4 && i < data.Length)
624 {
625 b[i] ^= data[i];
626 i++;
627 }
628 while (i < 4)
629 {
630 b[i] ^= data[i % data.Length];
631 i++;
632 }
633 return BitConverter.ToUInt32(b, 0);
634 }
635 }
636
637 public class JenkinsOneAtATime : HashFunction
638 {
639 public override uint ComputeHash(byte[] data)
640 {
641 uint hash = 0;
642 foreach (byte b in data)
643 {
644 hash += b;
645 hash += (hash << 10); // 10
646 hash ^= (hash >> 6); // 6
647 }
648 hash += (hash << 3); // 3
649 hash ^= (hash >> 11); // 11
650 hash += (hash << 15); // 15
651 return hash;
652 }
653 }
654
655 public class FletcherChecksum : HashFunction
656 {
657 public override uint ComputeHash(byte[] data)
658 {
659 uint hash = 0;
660 uint sum = 0;
661 foreach (byte b in data)
662 {
663 sum += b;
664 hash += sum;
665 }
666 return hash;
667 }
668 }
669
670 public class CRC32 : HashFunction
671 {
672 uint[] tab;
673
674 public CRC32()
675 {
676 Init(0x04c11db7);
677 }
678
679 public CRC32(uint poly)
680 {
681 Init(poly);
682 }
683
684 void Init(uint poly)
685 {
686 tab = new uint[256];
687 for (uint i=0; i<256; i++)
688 {
689 uint t = i;
690 for (int j=0; j<8; j++)
691 if ((t & 1) == 0)
692 t >>= 1;
693 else
694 t = (t >> 1) ^ poly;
695 tab[i] = t;
696 }
697 }
698
699 public override uint ComputeHash(byte[] data)
700 {
701 uint hash = 0xFFFFFFFF;
702 foreach (byte b in data)
703 hash = (hash << 8) ^ tab[b ^ (hash >> 24)];
704 return ~hash;
705 }
706 }
707
708 public class SBoxHash : HashFunction
709 {
710 uint[] sbox = new uint[] {
711 0xF53E1837, 0x5F14C86B, 0x9EE3964C, 0xFA796D53,
712 0x32223FC3, 0x4D82BC98, 0xA0C7FA62, 0x63E2C982,
713 0x24994A5B, 0x1ECE7BEE, 0x292B38EF, 0xD5CD4E56,
714 0x514F4303, 0x7BE12B83, 0x7192F195, 0x82DC7300,
715 0x084380B4, 0x480B55D3, 0x5F430471, 0x13F75991,
716 0x3F9CF22C, 0x2FE0907A, 0xFD8E1E69, 0x7B1D5DE8,
717 0xD575A85C, 0xAD01C50A, 0x7EE00737, 0x3CE981E8,
718 0x0E447EFA, 0x23089DD6, 0xB59F149F, 0x13600EC7,
719 0xE802C8E6, 0x670921E4, 0x7207EFF0, 0xE74761B0,
720 0x69035234, 0xBFA40F19, 0xF63651A0, 0x29E64C26,
721 0x1F98CCA7, 0xD957007E, 0xE71DDC75, 0x3E729595,
722 0x7580B7CC, 0xD7FAF60B, 0x92484323, 0xA44113EB,
723 0xE4CBDE08, 0x346827C9, 0x3CF32AFA, 0x0B29BCF1,
724 0x6E29F7DF, 0xB01E71CB, 0x3BFBC0D1, 0x62EDC5B8,
725 0xB7DE789A, 0xA4748EC9, 0xE17A4C4F, 0x67E5BD03,
726 0xF3B33D1A, 0x97D8D3E9, 0x09121BC0, 0x347B2D2C,
727 0x79A1913C, 0x504172DE, 0x7F1F8483, 0x13AC3CF6,
728 0x7A2094DB, 0xC778FA12, 0xADF7469F, 0x21786B7B,
729 0x71A445D0, 0xA8896C1B, 0x656F62FB, 0x83A059B3,
730 0x972DFE6E, 0x4122000C, 0x97D9DA19, 0x17D5947B,
731 0xB1AFFD0C, 0x6EF83B97, 0xAF7F780B, 0x4613138A,
732 0x7C3E73A6, 0xCF15E03D, 0x41576322, 0x672DF292,
733 0xB658588D, 0x33EBEFA9, 0x938CBF06, 0x06B67381,
734 0x07F192C6, 0x2BDA5855, 0x348EE0E8, 0x19DBB6E3,
735 0x3222184B, 0xB69D5DBA, 0x7E760B88, 0xAF4D8154,
736 0x007A51AD, 0x35112500, 0xC9CD2D7D, 0x4F4FB761,
737 0x694772E3, 0x694C8351, 0x4A7E3AF5, 0x67D65CE1,
738 0x9287DE92, 0x2518DB3C, 0x8CB4EC06, 0xD154D38F,
739 0xE19A26BB, 0x295EE439, 0xC50A1104, 0x2153C6A7,
740 0x82366656, 0x0713BC2F, 0x6462215A, 0x21D9BFCE,
741 0xBA8EACE6, 0xAE2DF4C1, 0x2A8D5E80, 0x3F7E52D1,
742 0x29359399, 0xFEA1D19C, 0x18879313, 0x455AFA81,
743 0xFADFE838, 0x62609838, 0xD1028839, 0x0736E92F,
744 0x3BCA22A3, 0x1485B08A, 0x2DA7900B, 0x852C156D,
745 0xE8F24803, 0x00078472, 0x13F0D332, 0x2ACFD0CF,
746 0x5F747F5C, 0x87BB1E2F, 0xA7EFCB63, 0x23F432F0,
747 0xE6CE7C5C, 0x1F954EF6, 0xB609C91B, 0x3B4571BF,
748 0xEED17DC0, 0xE556CDA0, 0xA7846A8D, 0xFF105F94,
749 0x52B7CCDE, 0x0E33E801, 0x664455EA, 0xF2C70414,
750 0x73E7B486, 0x8F830661, 0x8B59E826, 0xBB8AEDCA,
751 0xF3D70AB9, 0xD739F2B9, 0x4A04C34A, 0x88D0F089,
752 0xE02191A2, 0xD89D9C78, 0x192C2749, 0xFC43A78F,
753 0x0AAC88CB, 0x9438D42D, 0x9E280F7A, 0x36063802,
754 0x38E8D018, 0x1C42A9CB, 0x92AAFF6C, 0xA24820C5,
755 0x007F077F, 0xCE5BC543, 0x69668D58, 0x10D6FF74,
756 0xBE00F621, 0x21300BBE, 0x2E9E8F46, 0x5ACEA629,
757 0xFA1F86C7, 0x52F206B8, 0x3EDF1A75, 0x6DA8D843,
758 0xCF719928, 0x73E3891F, 0xB4B95DD6, 0xB2A42D27,
759 0xEDA20BBF, 0x1A58DBDF, 0xA449AD03, 0x6DDEF22B,
760 0x900531E6, 0x3D3BFF35, 0x5B24ABA2, 0x472B3E4C,
761 0x387F2D75, 0x4D8DBA36, 0x71CB5641, 0xE3473F3F,
762 0xF6CD4B7F, 0xBF7D1428, 0x344B64D0, 0xC5CDFCB6,
763 0xFE2E0182, 0x2C37A673, 0xDE4EB7A3, 0x63FDC933,
764 0x01DC4063, 0x611F3571, 0xD167BFAF, 0x4496596F,
765 0x3DEE0689, 0xD8704910, 0x7052A114, 0x068C9EC5,
766 0x75D0E766, 0x4D54CC20, 0xB44ECDE2, 0x4ABC653E,
767 0x2C550A21, 0x1A52C0DB, 0xCFED03D0, 0x119BAFE2,
768 0x876A6133, 0xBC232088, 0x435BA1B2, 0xAE99BBFA,
769 0xBB4F08E4, 0xA62B5F49, 0x1DA4B695, 0x336B84DE,
770 0xDC813D31, 0x00C134FB, 0x397A98E6, 0x151F0E64,
771 0xD9EB3E69, 0xD3C7DF60, 0xD2F2C336, 0x2DDD067B,
772 0xBD122835, 0xB0B3BD3A, 0xB0D54E46, 0x8641F1E4,
773 0xA0B38F96, 0x51D39199, 0x37A6AD75, 0xDF84EE41,
774 0x3C034CBA, 0xACDA62FC, 0x11923B8B, 0x45EF170A,
775 };
776
777 public override uint ComputeHash(byte[] data)
778 {
779 uint hash = 0;
780 foreach (byte b in data)
781 {
782 hash ^= sbox[b];
783 hash *= 3;
784 }
785 return hash;
786 }
787 }
788 '@
789
790 $assemblies = (
791 #"System",
792 #"System.Security.Cryptography",
793 "System.Drawing"
794 )
795 Add-Type -ReferencedAssemblies $assemblies -TypeDefinition $cs -Language CSharp
796 [ConsoleApp]::Main("")
長いけれど、「スクリプト」たる部分は最後の8行くらいだけなのね。残りは全部 C# そのもの。
動かしてみた：
1 me@host: ~$ /C/WINDOWS/SysWOW64/WindowsPowerShell/v1.0/powershell ./h.ps1
2
3 SBoxHash
4
5 Two-octet keys
6 Four-octet keys
7 Five-octet keys
8 Three-octet keys
9 256-octet keys
10
11 SBoxHash
12
13 Uniform keys Text keys Sparse keys
14
15 Bits Lower Upper Lower Upper Lower Upper
16 1 0.258 0.034 0.777 0.322 0.480 0.888
17 2 0.457 0.936 0.272 0.628 0.167 0.701
18 3 0.496 0.136 0.157 0.233 0.619 0.889
19 4 0.927 0.365 0.826 0.194 0.046 0.879
20 5 0.611 0.185 0.119 0.873 0.360 0.900
21 6 0.195 0.639 0.647 0.008 0.914 0.328
22 7 0.421 0.775 0.844 0.036 0.685 0.595
23 8 0.309 0.270 0.298 0.900 0.589 0.541
24 9 0.350 0.507 0.200 0.579 0.687 0.159
25 10 0.457 0.601 0.447 0.870 0.758 0.596
26 11 0.221 0.516 0.755 0.629 0.501 0.526
27 12 0.042 0.787 0.197 0.025 0.718 0.363
28 13 0.180 0.031 0.277 0.296 0.666 0.680
29 14 0.950 0.482 0.857 0.672 0.161 0.285
30 15 0.194 0.972 0.566 0.377 0.149 0.051
31 16 0.077 0.559 0.797 0.806 0.504 0.858
SBoxHashだけが動くような Main になってるので SBoxHash のだけが動きます。んで、Wikipedia で見えてるような「Avalanche behavior」の絵が、gif で出来上がります：
うんうん、これはいい。
用途ないことなんかあるもんか
その壱。どんだけ C# 資産があると思ってる? 面白いもん、いっぱいあんぞ。それを、C# 環境がないから諦めるなんか勿体無い。
その弐。C# 環境持っていても。Python や Ruby で開発しやすいのはなぜか? それは、「対話的に即結果を確認出来るから」であろう? それを C# で出来る、とは考えない? (多分これ、VB も出来ると思う。)
その参。C# から PowerShell を「気軽に」呼ぶなよ。C# に限らないが、「スクリプトじゃない言語」で書くからには、性能などを考えてそうしてるんではないの。開発コスト削減で、かつ、実用に問題が出ないならいいけどさ、よくいるんだ、だから Python は遅くてダメだ! と、プロセスの exec だらけのコードを書いといて dis る子たちが。(実際に見たことがあります。馬鹿じゃねーの、と思ったけれど、「馬鹿じゃねーの」ってツッコミが案の定入ってました。) Unix 系の fork/exec は比較的安価ですけどそれでもオーバヘッドは高くて、Windows のそれは悲劇的なほどにオーバヘッド高いです(Unix系の10倍くらい)。だから出来るだけ同じ言語内で閉じるようにして、どうしてもという場合だけ他プロセスを呼び出す、とするのがセオリー。
 |
 |
 |
