🦋 🤴🏻 👆🏻 データハッシュの新しい標準であるKeccak 🙎🏿 👆🏻 💅🏿

読者の皆さん、こんにちは。

おそらくあなたの多くは、新しいSHA-3標準を採用するために、NISTがハッシュ関数間の競争を数年間行ってきたことをおそらく知っています。そして今年、この賞はそのヒーローを見つけました。新しい標準が安全に採用されました。

さて、この標準は既に採用されているので、それが何であるかを見る時です。

そして、静かな土曜日の夜、私はブラウザgoogle.comで開かれた~~マニュアルで~~自分自身を~~カバー~~したので、私の小さな研究を始めました。

前戯

224,256,384および512ビットの可変出力長を持つKeccakハッシュ関数が新しい標準として選択されました。ケッカックの中心にあるのは、スポンジ（スポンジ、上の画像と同じ）と呼ばれるデザインです。

この設計は次のように表すことができます。

図からわかるように、スキームは2つの段階で構成されています。

吸収する元のメッセージMは、マルチラウンド順列fを経ます。
スクイージング（リリース）。順列の結果として生じるZ値の出力。

注意深い読者は、図の文字rとcに気付いたに違いありません。前もって陰謀を明らかにすることはしません。これらの変数の値を変えることで、まったく異なるハッシュ関数が得られるとだけ言っておきましょう。したがって、SHA-512では、r = 576、c = 1024をこれらの値として選択する必要があります。

さらに詳細に？

そのため、上で述べたように、KeccakアルゴリズムはSpongeコンストラクトに基づいています。つまり、ハッシュを取得するには、次の簡単なアクションを実行する必要があります。

元のメッセージMを取得し、rの長さの倍数に追加します。追加規則は、その単純さに魅了されます。式の形式では、M = M || 0x01 || 0x00 || .. || 0x00 || 0x80のように表すことができます。または、ロシア語では、1バイトがメッセージに追加され、必要な数のゼロが追加され、このアンサンブル全体が0x80の値でバイトを完成させます。

UPD：上記のすべては、複数のバイトが追加された場合にのみ適用されます。ただし、1バイトのみを追加する必要がある場合は、0x81のみを追加すれば十分です。尊敬されているOverQuantumの警戒のおかげで、間違いが明らかになりました。そしてさらに以前、fdsc habrayuzerは同じことについて話しました。サンドボックスの投稿は気づかれていませんでしたが、今では正義が勝利しました。したがって、これを念頭に置いてコードを書き換える必要があります！
次に、長さrビットの各ブロックM _{iに対して} 、次を実行します。
初期状態Sのセットの最初のrビットを使用したモジュロ2加算。関数が開始する前に、Sのすべての要素はゼロになります。
結果のデータに関数fをN回適用します。ブロックM _{i + 1}の初期状態のセットSは、ブロックM _iの最後のラウンドの結果になります。
すべてのブロックM _iが終了したら、最終結果を取得してハッシュ値として返します。

とにかく、何も明確ではありません！

さて、今では、 ~~ブラックジャックと売春婦の~~コードと説明を含むアルゴリズムの全体が~~詳しく~~説明されています。

しかし、まず、秘密のベールをはがして、パラメーターrとcが必要な理由を教えてください。

このため、Keccakハッシュ関数は、ユーザーが事前定義関数b = {f-25、f-50、f-100、fのセットから各ブロックM _iに使用する置換関数fを選択できるように実装されていると言わなければなりません。 -200、f-400、f-800、f-1600}。

実装で、たとえばf-800関数を使用するには、等式r + c = 800が満たされるように、そのようなrとcを選択する必要があります。

さらに、rとcの値を変更することにより、ハッシュ関数のラウンド数を変更します。なぜならこれらの数は、式n = 12 + 2lで計算されます。ここで、2 ^l =（b / 25）です。したがって、b = 1600の場合、ラウンド数は24です。

ただし、ユーザーは作成者が実装に提案する機能を選択する権利を持っていますが、SHA-3標準として受け入れられるのはKeccak-1600機能のみであり、作成者はそれのみを使用することを強くお勧めします。そのため、著者はさまざまな長さのハッシュの主な値として次のパラメーターを選択しました。

SHA-224：r = 1156、c = 448（結果の最初の28バイトを返す）

SHA-256：r = 1088、c = 512（結果の最初の32バイトを返す）

SHA-384：r = 832、c = 768（最初の48バイトの結果を返す）

SHA-512：r = 576、c = 1024（最初の64バイトの結果を返す）

コードはどこにありますか？

そして、これらすべての説明の後、すでにアルゴリズムの擬似コードに直接行くことができます。

吸収段階は、次の関数として表すことができます。

Keccak-f[b](A) { forall i in 0…nr-1 A = Round[b](A, RC[i]) return A }

ここで、bは選択された関数の値です（デフォルトは1600）。また、Round（）関数は、各ラウンドに適用される擬似ランダム順列です。ラウンド数nrは、rとcの値から計算されます。

各ラウンドで実行される操作は次の機能です。

 Round[b](A,RC) { θ step for(int x=0; x<5; x++) C[x] = A[x,0] xor A[x,1] xor A[x,2] xor A[x,3] xor A[x,4]; for(int x=0; x<5; x++) D[x] = C[x-1] xor rot(C[x+1],1); for(int x=0; x<5; x++) A[x,y] = A[x,y] xor D[x]; ρ and π steps for(int x=0; x<5; x++) for(int y=0; y<5; y++) B[y,2*x+3*y] = rot(A[x,y], r[x,y]); χ step for(int x=0; x<5; x++) for(int y=0; y<5; y++) A[x,y] = B[x,y] xor ((not B[x+1,y]) and B[x+2,y]); ι step A[0,0] = A[0,0] xor RC return A }

これは4つのステップで構成され、各ステップで受信データに対して一連の論理演算が実行されます。

ここで、関数rot（X、n）は、要素Xのn位置による巡回シフトを示します。

配列r []は、各ラウンドでシフトするバイト数を示す事前定義された値のセットです。この配列のすべての要素の値は、次の表に示されています。

RC配列は、事前定義された定数のセットです。

Keccak関数自体は次のとおりです。

 Keccak[r,c](M) { Initialization and padding for(int x=0; x<5; x++) for(int y=0; y<5; y++) S[x,y] = 0; P = M || 0x01 || 0x00 || … || 0x00; P = P xor (0x00 || … || 0x00 || 0x80); //Absorbing phase forall block Pi in P for(int x=0; x<5; x++) for(int y=0; y<5; y++) S[x,y] = S[x,y] xor Pi[x+5*y]; S = Keccak-f[r+c](S); //Squeezing phase Z = empty string; do { for(int x=0; x<5; x++) for(int y=0; y<5; y++) if((x+5y)<r/w) Z = Z || S[x,y]; S = Keccak-f[r+c](S) } while output is requested return Z; }

Absorbigステップでは、値のハッシュが計算されます。

そして、スクイージング段階で、必要なハッシュ長に達するまで結果を出力します。

ネタバレの下で、これらすべてのアクションを実装するC＃で書かれた小さなクラス

 public class Keccack { // ,   24 //   ι private ulong[] RC ={0x0000000000000001, 0x0000000000008082, 0x800000000000808A, 0x8000000080008000, 0x000000000000808B, 0x0000000080000001, 0x8000000080008081, 0x8000000000008009, 0x000000000000008A, 0x0000000000000088, 0x0000000080008009, 0x000000008000000A, 0x000000008000808B, 0x800000000000008B, 0x8000000000008089, 0x8000000000008003, 0x8000000000008002, 0x8000000000000080, 0x000000000000800A, 0x800000008000000A, 0x8000000080008081, 0x8000000000008080, 0x0000000080000001, 0x8000000080008008}; // ,       θ private int[,] r = {{0, 36, 3, 41, 18} , {1, 44, 10, 45, 2} , {62, 6, 43, 15, 61} , {28, 55, 25, 21, 56} , {27, 20, 39, 8, 14} }; private int w, l, n; //     b=1600 public Keccack(int b) { w = b / 25; l = (Convert.ToInt32(Math.Log(w, 2))); n = 12 + 2 * l; } //   x  n  private ulong rot(ulong x, int n) { n = n % w; return (((x << n) | (x >> (w - n)))); } private ulong[,] roundB(ulong[,] A, ulong RC) { ulong[] C = new ulong[5]; ulong[] D = new ulong[5]; ulong[,] B = new ulong[5, 5]; // θ for (int i = 0; i < 5; i++) C[i] = A[i, 0] ^ A[i, 1] ^ A[i, 2] ^ A[i, 3] ^ A[i, 4]; for (int i = 0; i < 5; i++) D[i] = C[(i + 4) % 5] ^ rot(C[(i + 1) % 5], 1); for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) A[i, j] = A[i, j] ^ D[i]; // ρ  π for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) B[j, (2 * i + 3 * j) % 5] = rot(A[i, j], r[i, j]); // χ for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) A[i, j] = B[i, j] ^ ((~B[(i + 1) % 5, j]) & B[(i + 2) % 5, j]); // ι A[0, 0] = A[0, 0] ^ RC; return A; } private ulong[,] Keccackf(ulong[,] A) { for (int i = 0; i < n; i++) A = roundB(A, RC[i]); return A; } //  16-    r-      64-  private ulong[][] padding(string M, int r) { int size = 0; //     r M = M + "01"; while (((M.Length / 2) * 8 % r) != ((r - 8))) { M = M + "00"; } ; M = M + "80"; //     b-   size = (((M.Length / 2) * 8) / r); //   64-  ulong[][] arrayM = new ulong[size][]; arrayM[0] = new ulong[1600 / w]; string temp = ""; int count = 0; int j = 0; int i = 0; //     64-  foreach (char ch in M) { if (j > (r/w-1)) { j = 0; i++; arrayM[i] = new ulong[1600 / w]; } count++; if ((count * 4 % w) == 0) { arrayM[i][j] = Convert.ToUInt64(M.Substring((count - w / 4), w / 4), 16); temp = ToReverseHexString(arrayM[i][j]); arrayM[i][j] = Convert.ToUInt64(temp, 16); j++; } } return arrayM; } private string ToReverseHexString(ulong S) { string temp = BitConverter.ToString(BitConverter.GetBytes(S).ToArray()).Replace("-", ""); return temp; } private string ToHexString(ulong S) { string temp = BitConverter.ToString(BitConverter.GetBytes(S).Reverse().ToArray()).Replace("-", ""); return temp; } // public string GetHash(string M, int r, int c, int d) { //    S=0 ulong[,] S = new ulong[5, 5]; for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) S[i, j] = 0; ulong[][] P = padding(M, r); // P     Pi, //        64-  foreach (ulong[] Pi in P) { for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) if((i + j * 5)<(r/w)) S[i, j] = S[i, j] ^ Pi[i + j * 5]; Keccackf(S); } string Z = ""; //    ,      do { for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) if ((5*i + j) < (r / w)) Z = Z + ToReverseHexString(S[j, i]); Keccackf(S); } while (Z.Length < d*2); return Z.Substring(0, d * 2); } }

ここからソースをダウンロードできます。

PSこの記事のすべての資料とイラストは、公式のKeccakハッシュ関数のWebサイトで見つかりました。

UPD： fshpは、新しい標準の主な機能に関するロシア語の説明へのリンクを親切に共有しました。

UPD2：記事を公開した後、Admiralというニックネームを持つ読者からメールで連絡がありました。彼は、文字列操作を使用しない、より最適化されたコードを提案しました。

提督リーダーの実装

 using System; using System.Linq; using System.Collections.Generic; class Program { /*const */ static private Byte InstanceNumber = 6; /*const */ static private UInt16[] b_array = { 25, 50, 100, 200, 400, 800, 1600 }; //permutation_width /*const */ static private Byte matrixSize = 5 * 5; /*const */ static private Byte[] w_array = { 1, 2, 4, 8, 16, 32, 64 }; //b / 25; /*const */ static private Byte[] l_array = { 0, 1, 2, 3, 4, 5, 6 }; //log(static_cast<float>(m_w)) / log(2.0F) /*const */ static private Byte[] n_array = { 12, 14, 16, 18, 20, 22, 24 }; //12 + 2 * l -> number_of_permutation /*const */ static private Byte[,] r = { {0, 36, 3, 41, 18}, {1, 44, 10, 45, 2}, {62, 6, 43, 15, 61}, {28, 55, 25, 21, 56}, {27, 20, 39, 8, 14} }; /*const */ static private UInt64[] RC = {//24 by w_array[KeccakInstanceCount - 1] (for 1600), for less please use less in w_array 0x0000000000000001, 0x0000000000008082, 0x800000000000808A, 0x8000000080008000, 0x000000000000808B, 0x0000000080000001, 0x8000000080008081, 0x8000000000008009, 0x000000000000008A, 0x0000000000000088, 0x0000000080008009, 0x000000008000000A, 0x000000008000808B, 0x800000000000008B, 0x8000000000008089, 0x8000000000008003, 0x8000000000008002, 0x8000000000000080, 0x000000000000800A, 0x800000008000000A, 0x8000000080008081, 0x8000000000008080, 0x0000000080000001, 0x8000000080008008 }; static private UInt64[,] B = new UInt64[5, 5]; static private UInt64[] C = new UInt64[5]; static private UInt64[] D = new UInt64[5]; /*const*/ static public UInt16[] rate_array = { 576, 832, 1024, 1088, 1152, 1216, 1280, 1344, 1408 }; /*const*/ static public UInt16[] capacity_array = { 1024, 768, 576, 512, 448, 384, 320, 256, 192 }; public enum SHA3 { SHA512 = 0, SHA384, SHA256 = 3, SHA224 }; static private UInt64[,] Keccak_f(UInt64[,] A) { for(Byte i = 0; i < n_array[InstanceNumber]; i++) A = Round(A, RC[i]); return A; } static private UInt64[,] Round(UInt64[,] A, UInt64 RC_i) { Byte i, j; //theta step for (i = 0; i < 5; i++) C[i] = A[i,0] ^ A[i,1] ^ A[i,2] ^ A[i,3] ^ A[i,4]; for (i = 0; i < 5; i++) D[i] = C[(i + 4) % 5] ^ ROT(C[(i + 1) % 5], 1, w_array[InstanceNumber]); for (i = 0; i < 5; i++) for (j = 0; j < 5; j++) A[i,j] = A[i,j] ^ D[i]; //rho and pi steps for (i = 0; i < 5; i++) for (j = 0; j < 5; j++) B[j,(2 * i + 3 * j) % 5] = ROT(A[i,j], r[i,j], w_array[InstanceNumber]); //chi step for (i = 0; i < 5; i++) for (j = 0; j < 5; j++) A[i,j] = B[i,j] ^ ((~B[(i + 1) % 5,j]) & B[(i + 2) % 5,j]); //iota step A[0,0] = A[0,0] ^ RC_i; return A; } static private UInt64 ROT(UInt64 x, Byte n, Byte w) { return ((x << (n % w)) | (x >> (w - (n % w)))); } static private Byte[] Keccak(UInt16 rate, UInt16 capacity, List<Byte> Message) { //Padding Message.Add(0x01); UInt16 min = (UInt16)((rate - 8) / 8); UInt16 n = (UInt16)Math.Truncate((Double)(Message.Count / min)); UInt32 messageFullCount = 0; if (n < 2) { messageFullCount = min; } else { messageFullCount = (UInt32)(n * min + (n - 1)); } UInt32 delta = (UInt32)(messageFullCount - Message.Count); if ((Message.Count + delta) > UInt16.MaxValue - 1) throw (new Exception("Message might be too large")); /*Byte[] byteArrayToAdd = new Byte[delta]; Message.AddRange(byteArrayToAdd);*/ while (delta > 0) { Message.Add(0x00); delta--; } if ((Message.Count * 8 % rate) != (rate - 8)) throw (new Exception("Length was incorect calculated")); Message.Add(0x80); /*const*/ Int32 size = (Message.Count * 8) / rate; UInt64[] P = new UInt64[size * matrixSize]; Int32 xF = 0, count = 0; Byte i = 0, j = 0; for(xF = 0; xF < Message.Count; xF++) { if (j > (rate / w_array[InstanceNumber] - 1)) { j = 0; i++; } count++; if ((count * 8 % w_array[InstanceNumber]) == 0) { P[size * i + j] = ReverseEightBytesAndToUInt64( Message.GetRange(count - w_array[InstanceNumber] / 8, 8).ToArray() ); j++; } } //Initialization UInt64 [,]S = new UInt64[5,5]; for(i = 0; i < 5; i++) for(j = 0; j < 5; j++) S[i,j] = 0; //Absorting phase for(xF = 0; xF < size; xF++) { for(i = 0; i < 5; i++) for(j = 0; j < 5; j++) if ((i + j * 5) < (rate / w_array[InstanceNumber])) { S[i, j] = S[i, j] ^ P[size * xF + i + j * 5]; } Keccak_f(S); } //Squeezing phaze Byte a = 0; Byte d_max = (Byte)(capacity / (2 * 8)); List<Byte> retHash = new List<Byte>(d_max); for( ; ; ) { for(i = 0; i < 5; i++) for(j = 0; j < 5; j++) if((5 * i + j) < (rate / w_array[InstanceNumber])) { if(a >= d_max) i = j = 5; else { retHash.AddRange(FromUInt64ToReverseEightBytes(S[j, i])); a = (Byte)retHash.Count; } } if(a >= d_max) break; Keccak_f(S); } return retHash.GetRange(0, d_max).ToArray(); } static private UInt64 ReverseEightBytesAndToUInt64(Byte[] bVal) { UInt64 ulVal = 0L; for (Byte i = 8, j = 0; i > 0; i--) { ulVal += (UInt64)((bVal[i - 1] & 0xF0) >> 4) * (UInt64)Math.Pow(16.0F, 15 - (j++)); ulVal += (UInt64)(bVal[i - 1] & 0x0F) * (UInt64)Math.Pow(16.0F, 15 - (j++)); } return ulVal; } static private Byte[] FromUInt64ToReverseEightBytes(UInt64 ulVal) { Byte[] bVal = new Byte[8]; Byte a = 0; do { bVal[a] = (Byte)((ulVal % 16) * 1); ulVal = ulVal / 16; bVal[a] += (Byte)((ulVal % 16) * 16); a++; } while (15 < (ulVal = ulVal / 16)); while (a < 8) { bVal[a++] = (Byte)ulVal; ulVal = 0; } return bVal; } static void Main(String[] args) { if (args.Length < 1) return; List<Byte> MessageB; String message = string.Copy(args[0]); MessageB = strToByteList(message); String hash_224 = ByteArrayToString(Keccak(rate_array[(Byte)SHA3.SHA224], capacity_array[(Byte)SHA3.SHA224], MessageB)); MessageB = strToByteList(message); String hash_256 = ByteArrayToString(Keccak(rate_array[(Byte)SHA3.SHA256], capacity_array[(Byte)SHA3.SHA256], MessageB)); MessageB = strToByteList(message); String hash_384 = ByteArrayToString(Keccak(rate_array[(Byte)SHA3.SHA384], capacity_array[(Byte)SHA3.SHA384], MessageB)); MessageB = strToByteList(message); String hash_512 = ByteArrayToString(Keccak(rate_array[(Byte)SHA3.SHA512], capacity_array[(Byte)SHA3.SHA512], MessageB)); Console.WriteLine("Message: " + message + "\r\n" + "Hash_224: " + hash_224 + "\r\n" + "Hash_256: " + hash_256 + "\r\n" + "Hash_384: " + hash_384 + "\r\n" + "Hash_512: " + hash_512 + "\r\n"); } static List<Byte> strToByteList(String str) { List<Byte> ret = new List<byte>(str.Length); foreach(char ch in str) { ret.Add((Byte)ch); } return ret; } static public String ByteArrayToString(Byte[] b) { System.Text.StringBuilder sb = new System.Text.StringBuilder(16); for (Int32 i = 0; i < Math.Min(b.Length, Int32.MaxValue - 1); i++) sb.Append(String.Format("{0:X2}", b[i])); return sb.ToString(); } }

データハッシュの新しい標準であるKeccak

前戯

さらに詳細に？

とにかく、何も明確ではありません！

コードはどこにありますか？

More articles: