Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
4
Help us understand the problem. What is going on with this article?
@keitashot

SHA-3に関するまとめ

More than 3 years have passed since last update.

SHA-3とは

一方向ハッシュ関数の一種、KECCAKというアルゴリズムが用いられており、ビットコインをはじめ様々なブロックチェーンで用いられている。生成するビット列の長さに応じてSHA3-224,SHA3-256,SHA3-384,SHA3-512といった規格が定義されている。

一方向ハッシュ関数とは

任意長のメッセージを入力すると固定長のハッシュ値を返す関数であるハッシュ関数の一種。ハッシュ値から元のメッセージを推測できない、異なるメッセージに対しては異なるハッシュ値が対応するという特徴を持つ。改竄の検出や電子署名などに用いられている。

衝突

異なるメッセージが同一のハッシュ値を持つことを衝突と呼ぶ。この衝突は必ず起こるので、一方向ハッシュ関数は衝突を見つけることが事実上不可能である必要がある。衝突の見つけにくさを衝突耐性と呼ぶ。衝突耐性にはあるメッセージと同じハッシュ値を持つメッセージの見つけにくさである弱衝突耐性とハッシュ値が一致する二つのメッセージの見つけにくさである強衝突耐性がある。

xor

バイト列同士の足し算。0+0=0,0+1=1,1+0=1,1+1=0。

KECCAK

  • スポンジ構造

スポンジ.PNG

KECCAKでは上図のようなスポンジ構造が用いられている。吸収フェーズと搾出フェーズに分かれており、r+cの長さの内部状態を持つ。メッセージMはpadにてパディング(rで割り切れるように足りないバイト列を足す)を施され長さrの入力ブロックi(1,2,3,,,)に分割される。そして入力ブロックが尽きるまで1から順に長さrの内部状態とxor、関数fによる処理を繰り返す(図では左から順に入力ブロック1,2,3,4が入力として使われる、また長さcの部分は入力の影響を受けない)。搾出フェーズでは長さrの内部状態を出力iとして出力、関数fによる処理を出力iの合計長が出力Zの固定長に達するまで繰り返して結合する。

  • 内部状態と関数f

Keccak-f-State.png

KECCAKはr+cビットの内部状態を持つが、それは上図のような5*5*(r+c)/25の立方体が集合した直方体として扱われている。
1ビットが一つの立方体である。関数fはこの直方体に対して決められた操作(足したり入れ替えたり)を行うことに相当する。

参考

4
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
4
Help us understand the problem. What is going on with this article?