Network Working Group D. Eastlake, 3rd Request for Comments: 3174 Motorola Category: Informational P. Jones Cisco Systems September 2001 US Secure Hash Algorithm 1 (SHA1) Status of this Memo ＃　このメモの位置付け This memo provides information for the Internet community. It does ＃　このメモは、インターネット・コミュニティへ情報を提供する。 not specify an Internet standard of any kind. Distribution of this ＃　いかなる種類のインターネット標準も規定しない。 memo is unlimited. ＃　このメモの配布は無制限である。 Copyright Notice ＃　著作権掲示 Copyright (C) The Internet Society (2001). All Rights Reserved. Abstract ＃　要約 The purpose of this document is to make the SHA-1 (Secure Hash ＃　この文書の目的は、インターネット・コミュニティが Algorithm 1) hash algorithm conveniently available to the Internet ＃　SHA-1（Secure Hash Algorithm 1)ハッシュ・アルゴリズムを community. The United States of America has adopted the SHA-1 hash ＃　便利に利用できるようにすることにある。米国は連邦情報処理標準(FIPS)として algorithm described herein as a Federal Information Processing ＃　以下に記述するSHA-1ハッシュアルゴリズムを採用した。 Standard. Most of the text herein was taken by the authors from FIPS ＃　以下の文章の大半は（著者によって？）FIPS 180-1から採られている。 180-1. Only the C code implementation is "original". ＃　C言語による実装のみが「独自」のものである。 Acknowledgements ＃　謝辞 Most of the text herein was taken from [FIPS 180-1]. Only the C code ＃　以下の文章の大半は、FIPS 180-1から採られている。C言語による実装のみが implementation is "original" but its style is similar to the ＃　「独自」のものであるが、そのスタイル（？）は、先立って発行された previously published MD4 and MD5 RFCs [RFCs 1320, 1321]. ＃　MD4及びMD5のRFC（RFC 1320、1321）と同様である。 The SHA-1 is based on principles similar to those used by Professor ＃　SHA-1は、MD4メッセージ・ダイジェスト・アルゴリズムを設計する際に Ronald L. Rivest of MIT when designing the MD4 message digest ＃　MITのRonald L. Rivest教授によって利用されたものと同様の法則に基づき、 algorithm [MD4] and is modeled after that algorithm [RFC 1320]. ＃　後にそのアルゴリズム(RFC1320)を手本とした（？）。 Useful comments from the following, which have been incorporated ＃　以下の方々からの有用なコメント（既に本文に反映されている）に感謝する。 herein, are gratefully acknowledged: Tony Hansen Garrett Wollman Eastlake & Jones Informational [Page 1] RFC 3174 US Secure Hash Algorithm 1 (SHA1) September 2001 Table of Contents 1. Overview of Contents........................................... 2 ＃　概要 2. Definitions of Bit Strings and Integers........................ 3 ＃　ビット・ストリームと整数の定義 3. Operations on Words............................................ 3 ＃　ワード操作 4. Message Padding................................................ 4 ＃　メッセージ・パディング（メッセージの当て物） 5. Functions and Constants Used................................... 6 ＃　関数と定数 6. Computing the Message Digest................................... 6 ＃　メッセージ・ダイジェストの算出 6.1 Method 1...................................................... 6 ＃　操作1 6.2 Method 2...................................................... 7 ＃　操作2 7. C Code......................................................... 8 ＃　C言語による実装 7.1 .h file....................................................... 8 ＃　ヘッダファイル 7.2 .c file....................................................... 10 ＃　ソースファイル 7.3 Test Driver................................................... 18 ＃　テストドライバ 8. Security Considerations........................................ 20 ＃　セキュリティ上考慮されるべきこと References........................................................ 21 ＃　参考文献 Authors' Addresses................................................ 21 ＃　著者連絡先 Full Copyright Statement.......................................... 22 ＃　著作権全文提示 1. Overview of Contents ＃　概要 NOTE: The text below is mostly taken from [FIPS 180-1] and assertions ＃　注釈：以下の文章は大半がFIPS 180-1から採られており、 therein of the security of SHA-1 are made by the US Government, the ＃　the security of SHA-1（？）は米国政府、FIPS 180-1の著者により作成されている author of [FIPS 180-1], and not by the authors of this document. ＃　（この文書の著者によるものではない）という点について明記する。 This document specifies a Secure Hash Algorithm, SHA-1, for computing ＃　この文書では、メッセージ又はデータファイルを濃縮した表現を算出する、 a condensed representation of a message or a data file. When a ＃　SHA-1について述べる。 message of any length < 2^64 bits is input, the SHA-1 produces a ＃　2^64ビット未満の長さのメッセージが入力された時、SHA-1は 160-bit output called a message digest. The message digest can then, ＃　メッセージダイジェストと呼ばれる160ビットの出力を算出する。 for example, be input to a signature algorithm which generates or ＃　メッセージダイジェストは、例えば、メッセージへの署名を生成あるいは verifies the signature for the message. Signing the message digest ＃　確認するする署名アルゴリズムへの入力として使用することができる。 rather than the message often improves the efficiency of the process ＃　メッセージダイジェストを署名するよりはむしろ（？）、メッセージは ＃　しばしば処理効率を向上させる。なぜなら、メッセージダイジェストは通常、 because the message digest is usually much smaller in size than the ＃　メッセージそのものよりずっとサイズが小さいからである。 message. The same hash algorithm must be used by the verifier of a ＃　デジタル署名の確認には、デジタル署名の生成者によって使われたものと digital signature as was used by the creator of the digital ＃　同じハッシュ・アルゴリズムが使用されなければならない。 signature. Any change to the message in transit will, with very high ＃　転送中に起きた何らかのメッセージの変化は、非常に高い確率で probability, result in a different message digest, and the signature ＃　異なるメッセージ・ダイジェストを算出し、 will fail to verify. ＃　署名の確認は失敗するだろう。 The SHA-1 is called secure because it is computationally infeasible ＃　SHA-1は安全であると言われる。なぜなら、 to find a message which corresponds to a given message digest, or to ＃　与えられたメッセージ・ダイジェストに一致するメッセージが計算不能であり、 find two different messages which produce the same message digest. ＃　二つの異なるメッセージが同じメッセージ・ダイジェストを生成する ＃　ことがないためである。 Any change to a message in transit will, with very high probability, ＃　転送中に起きた何らかメッセージの変化は、非常に高い確率で result in a different message digest, and the signature will fail to ＃　異なるメッセージ・ダイジェストを算出し、署名の確認は失敗するだろう。 verify. Eastlake & Jones Informational [Page 2] RFC 3174 US Secure Hash Algorithm 1 (SHA1) September 2001 Section 2 below defines the terminology and functions used as ＃　続く第2章では、SHA-1を形作る積み木として利用される、 building blocks to form SHA-1. ＃　関数と用語を定義する。 2. Definitions of Bit Strings and Integers ＃　ビット・ストリームと整数の定義 The following terminology related to bit strings and integers will be ＃　ビット・ストリームと整数についての以下の用語が使用される（？）。 used: a. A hex digit is an element of the set {0, 1, ... , 9, A, ... , F}. ＃　16進数は、{0,1,...9,A,...F}の組み合わせから成る。 A hex digit is the representation of a 4-bit string. Examples: 7 ＃　16進数（の1桁）は、4ビット値を表現する。例：7 = 0111, A = 1010 = 0111, A = 1010. b. A word equals a 32-bit string which may be represented as a ＃　ワードは、8桁の16進数表記、つまり32ビット値に等しい。 sequence of 8 hex digits. To convert a word to 8 hex digits each ＃　ワードを、4ビット値毎の8桁の16進数に変換するには、 4-bit string is converted to its hex equivalent as described in ＃　上（a.のこと？）の記述と同等の16進数へ変換する。例： (a) above. Example: 1010 0001 0000 0011 1111 1110 0010 0011 = A103FE23. c. An integer between 0 and 2^32 - 1 inclusive may be represented as ＃　0から2^32-1に含まれる整数は、ワードで表記される。 a word. The least significant four bits of the integer are ＃　整数の最小の重要な（？）4ビットは、ワード表記の最も右側の16進数の桁として represented by the right-most hex digit of the word ＃　表記される。 representation. Example: the integer 291 = 2^8+2^5+2^1+2^0 = ＃　例：整数291（= 2^8+2^5+2^1+2^0 = 256+32+2+1）は、16進数のワード00000123 256+32+2+1 is represented by the hex word, 00000123. ＃　として表記される。 If z is an integer, 0 <= z < 2^64, then z = (2^32)x + y where 0 <= ＃　整数zが0 <= z < 2^64の時、0 <= x < 2^32かつ0 <= y < 2^32ならば、 x < 2^32 and 0 <= y < 2^32. Since x and y can be represented as ＃　z = (2^32)x + yである。xとyがそれぞれワードXとYで表記できるとき、 words X and Y, respectively, z can be represented as the pair of ＃　zはワードの組み合わせ(X,Y)として表記できる。 words (X,Y). d. block = 512-bit string. A block (e.g., B) may be represented as a ＃　ブロックは512ビット値である。ブロック（例えばB）は、16ワードで表記される。 sequence of 16 words. 3. Operations on Words ＃　ワード操作 The following logical operators will be applied to words: ＃　以下の論理操作がワードに適用される。 a. Bitwise logical word operations ＃　ビット単位の論理ワード操作 X AND Y = bitwise logical "and" of X and Y. ＃　X AND Y　= ビット単位の、XとYの論理積。 X OR Y = bitwise logical "inclusive-or" of X and Y. ＃　X OR Y　= ビット単位の、XとYの論理和。 X XOR Y = bitwise logical "exclusive-or" of X and Y. ＃　X OR Y　= ビット単位の、XとYの排他的論理和。 NOT X = bitwise logical "complement" of X. ＃　X OR Y　= ビット単位の、Xの否定。 Eastlake & Jones Informational [Page 3] RFC 3174 US Secure Hash Algorithm 1 (SHA1) September 2001 Example: ＃　例： 01101100101110011101001001111011 XOR 01100101110000010110100110110111 -------------------------------- = 00001001011110001011101111001100 b. The operation X + Y is defined as follows: words X and Y ＃　操作X+Yは、以下のように定義される： represent integers x and y, where 0 <= x < 2^32 and 0 <= y < 2^32. ＃　0 <= x < 2^32かつ0 <= y < 2^32の時、ワード値XとYは整数xとyを表す。 For positive integers n and m, let n mod m be the remainder upon ＃　正の整数nとmにおいて、n mod mは n / mの剰余とする。 dividing n by m. Compute ＃　z = (x + y) mod 2^32を計算する。 z = (x + y) mod 2^32. Then 0 <= z < 2^32. Convert z to a word, Z, and define Z = X + ＃　そのとき、0 <= z < 2^32である。zをワード値Zに変換し、 Y. ＃　Z = X + Yと定義する。 c. The circular left shift operation S^n(X), where X is a word and n ＃　Xをワード値、nを0 <= n < 32の整数としたときの循環左シフト操作 S^n(X)は、 is an integer with 0 <= n < 32, is defined by ＃　次のように定義される。 S^n(X) = (X << n) OR (X >> 32-n). In the above, X << n is obtained as follows: discard the left-most ＃　上で、X << nは次のようにして得られる：Xの左側nビットを捨て、 n bits of X and then pad the result with n zeroes on the right ＃　その結果の右側をn個のゼロビットを当てる。 (the result will still be 32 bits). X >> n is obtained by ＃　（結果は32ビットのままである）。X >> nは、 discarding the right-most n bits of X and then padding the result ＃　Xの右側nビットを捨て、その結果の左側にn個のゼロビットを with n zeroes on the left. Thus S^n(X) is equivalent to a ＃　当てることで得られる。これで、S^n(X)は circular shift of X by n positions to the left. ＃　Xのnビット循環左シフトと同等になる。 4. Message Padding ＃　メッセージ・パディング（メッセージの当て物） SHA-1 is used to compute a message digest for a message or data file ＃　SHA-1は、入力されたメッセージ又はデータファイルのメッセージ・ダイジェストを that is provided as input. The message or data file should be ＃　算出するのに使用される。メッセージ又はデータファイルは、 considered to be a bit string. The length of the message is the ＃　ビット・ストリングと見なされるべきである。メッセージの長さは、 number of bits in the message (the empty message has length 0). If ＃　メッセージのビット数である（空のメッセージは、長さ0となる）。もし、 the number of bits in a message is a multiple of 8, for compactness ＃　メッセージのビット数が8の倍数であれば、単純に、 we can represent the message in hex. The purpose of message padding ＃　メッセージを16進数で表記することができる。メッセージ・パディングの目的は、 is to make the total length of a padded message a multiple of 512. ＃　当て物されたメッセージの全体の長さを、512の倍数にすることにある。 SHA-1 sequentially processes blocks of 512 bits when computing the ＃　メッセージ・ダイジェストを計算するとき、SHA-1は512ビットのブロックを message digest. The following specifies how this padding shall be ＃　順次処理する。以下に述べるパディングが実行される。 performed. As a summary, a "1" followed by m "0"s followed by a 64- ＃　要約すると、512 * nの長さの、当て物されたメッセージを生成するため、 bit integer are appended to the end of the message to produce a ＃　"1"、複数の"0"、64ビットの整数が padded message of length 512 * n. The 64-bit integer is the length ＃　メッセージの後ろに追加される。64ビットの整数は、 of the original message. The padded message is then processed by the ＃　元のメッセージの長さである。当て物されたメッセージは、 SHA-1 as n 512-bit blocks. ＃　512ビット長のブロックとしてSHA-1に処理される。 Eastlake & Jones Informational [Page 4] RFC 3174 US Secure Hash Algorithm 1 (SHA1) September 2001 Suppose a message has length l < 2^64. Before it is input to the ＃　メッセージは、2^64未満の長さlであるとする。SHA-1に入力される前に、 SHA-1, the message is padded on the right as follows: ＃　メッセージは以下のようにして右側に当て物をされる： a. "1" is appended. Example: if the original message is "01010000", ＃　"1"が追加される。例：元のメッセージが"01010000"であれば、 this is padded to "010100001". ＃　"010100001"となる。 b. "0"s are appended. The number of "0"s will depend on the original ＃　複数の"0"が追加される。"0"の数は、元のメッセージの長さに依存する。 length of the message. The last 64 bits of the last 512-bit block ＃　最後の512ビットブロックのそのまた最後の64ビットは、 are reserved ＃　元のメッセージの長さlのために for the length l of the original message. ＃　予約されている。 Example: Suppose the original message is the bit string ＃　例：元のメッセージを、次のビット・ストリングとする。 01100001 01100010 01100011 01100100 01100101. After step (a) this gives ＃　ステップaの後は次のようになる。 01100001 01100010 01100011 01100100 01100101 1. Since l = 40, the number of bits in the above is 41 and 407 "0"s ＃　lが40の時、上のビット数は41であり、407個の"0"が are appended, making the total now 448. This gives (in hex) ＃　追加され、全部で448になる。これは（16進数表記で）次のようになる。 61626364 65800000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000. c. Obtain the 2-word representation of l, the number of bits in the ＃　元のメッセージのビット数であるlの、2ワード表現を得る。 original message. If l < 2^32 then the first word is all zeroes. ＃　もしl < 2^32であれば、最初のワードはすべてゼロになる。 Append these two words to the padded message. ＃　当て物されたメッセージに、その2ワードを追加する。 Example: Suppose the original message is as in (b). Then l = 40 ＃　例：元のメッセージを(b)節のものとする。l = 40である (note that l is computed before any padding). The two-word ＃　（lは当て物をする前に計算することに注意）。40の2ワード表記は representation of 40 is hex 00000000 00000028. Hence the final ＃　16進数で00000000 00000028である。その結果、最終的に padded message is hex ＃　当て物されたメッセージは16進数で次のようになる。 61626364 65800000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000028. The padded message will contain 16 * n words for some n > 0. ＃　当て物されたメッセージは、16 * n個のワードに分割できる（n > 0とする）。 The padded message is regarded as a sequence of n blocks M(1) , ＃　当て物されたメッセージは、n個のブロックMの並びと見なされる。 M(2), first characters (or bits) of the message. ＃　（？？？） Eastlake & Jones Informational [Page 5] RFC 3174 US Secure Hash Algorithm 1 (SHA1) September 2001 5. Functions and Constants Used ＃　関数と定数 A sequence of logical functions f(0), f(1),..., f(79) is used in ＃　SHA-1では、f(0), f(1),..., f(79)の関数の並び（？）が使用される。 SHA-1. Each f(t), 0 <= t <= 79, operates on three 32-bit words B, C, ＃　それぞれのf(t)（0 <= t <= 79とする）は、B、C、Dの3つの32ビットのワードを D and produces a 32-bit word as output. f(t;B,C,D) is defined as ＃　操作し、出力として32ビットのワードを生成する。f(t;B,C,D)は、 follows: for words B, C, D, ＃　以下のように定義される：ワード値B、C、Dにおいて、 f(t;B,C,D) = (B AND C) OR ((NOT B) AND D) ( 0 <= t <= 19) f(t;B,C,D) = B XOR C XOR D (20 <= t <= 39) f(t;B,C,D) = (B AND C) OR (B AND D) OR (C AND D) (40 <= t <= 59) f(t;B,C,D) = B XOR C XOR D (60 <= t <= 79). A sequence of constant words K(0), K(1), ... , K(79) is used in the ＃　SHA-1では、ワード定数列K(0), K(1), ... , K(79)を使用する。 SHA-1. In hex these are given by ＃　それらは、16進数で次のようになる。 K(t) = 5A827999 ( 0 <= t <= 19) K(t) = 6ED9EBA1 (20 <= t <= 39) K(t) = 8F1BBCDC (40 <= t <= 59) K(t) = CA62C1D6 (60 <= t <= 79). 6. Computing the Message Digest ＃　メッセージ・ダイジェストの算出 The methods given in 6.1 and 6.2 below yield the same message digest. ＃　同じメッセージ・ダイジェストを生成する、6.1、6.2の操作が与えられる。 Although using method 2 saves sixty-four 32-bit words of storage, it ＃　しかし、操作2を使用する場合は64個の32ビットワードを保存するため、 is likely to lengthen execution time due to the increased complexity ＃　ステップ(c)で{ W[t] }のアドレス計算の複雑さが増加し、 of the address computations for the { W[t] } in step (c). There are ＃　実行時間が長くなる。 other computation methods which give identical results. ＃　他にも同様の結果を返す計算法は存在する。 6.1 Method 1 ＃　操作1 The message digest is computed using the message padded as described ＃　メッセージ・ダイジェストは、4章の記述よる当て物をされたメッセージを使って in section 4. The computation is described using two buffers, each ＃　計算される。計算は、5つの32ビットワードから成る2組のバッファと、 consisting of five 32-bit words, and a sequence of eighty 32-bit ＃　80個の32ビットワードの数列を使用するように記述される。 words. The words of the first 5-word buffer are labeled A,B,C,D,E. ＃　はじめの5つのワードバッファは、A、B、C、D、Eと名づけられる。 The words of the second 5-word buffer are labeled H0, H1, H2, H3, H4. ＃　次の5つのワードバッファは、H0、H1、H2、H3、H4と名づけられる。 The words of the 80-word sequence are labeled W(0), W(1),..., W(79). ＃　80個のワード数列は、W(0)、W(1)、……W(79)と名づけられる。 A single word buffer TEMP is also employed. ＃　更に1つのワードバッファTEMPも使用される。 To generate the message digest, the 16-word blocks M(1), M(2),..., ＃　メッセージ・ダイジェストを生成する際、4章で定義された16ワード単位の M(n) defined in section 4 are processed in order. The processing of ＃　ブロックM(1)、M(2)……M(n)が、順番に処理される。それぞれのM(i)の処理は each M(i) involves 80 steps. ＃　80の段階が含まれる。 Eastlake & Jones Informational [Page 6] RFC 3174 US Secure Hash Algorithm 1 (SHA1) September 2001 Before processing any blocks, the H's are initialized as follows: in ＃　ブロックを処理する前に、バッファHは（16進数表記で）次のように初期化される： hex, H0 = 67452301 H1 = EFCDAB89 H2 = 98BADCFE H3 = 10325476 H4 = C3D2E1F0. Now M(1), M(2), ... , M(n) are processed. To process M(i), we ＃　（？） proceed as follows: ＃　M(i)を処理するために、以下の処理を行う： a. Divide M(i) into 16 words W(0), W(1), ... , W(15), where W(0) ＃　M(i)を16個のワードW(0), W(1), ... , W(15)に分割する。 is the left-most word. ＃　W(0)は最も左側のワードである。 b. For t = 16 to 79 let ＃　tが16から79までの間で、次の計算を行う。 W(t) = S^1(W(t-3) XOR W(t-8) XOR W(t-14) XOR W(t-16)). c. Let A = H0, B = H1, C = H2, D = H3, E = H4. ＃　この計算を行う。 d. For t = 0 to 79 do ＃　tが0から79の間で、次の計算を行う。 TEMP = S^5(A) + f(t;B,C,D) + E + W(t) + K(t); E = D; D = C; C = S^30(B); B = A; A = TEMP; e. Let H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4 + E. ＃　この計算を行う。 After processing M(n), the message digest is the 160-bit string ＃　M(n)を処理した後、メッセージダイジェストは次の5つのワードで表記された represented by the 5 words ＃　160ビット・ストリングである。 H0 H1 H2 H3 H4. 6.2 Method 2 ＃　操作2 The method above assumes that the sequence W(0), ... , W(79) is ＃　（？？？）数列W(0), ... , W(79)は、 implemented as an array of eighty 32-bit words. This is efficient ＃　80個の32ビット・ワードの配列として実現されている。これは、 from the standpoint of minimization of execution time, since the ＃　ステップ(b)のW(t-3), ... ,W(t-16)のアドレスが簡単に求められるため、 addresses of W(t-3), ... ,W(t-16) in step (b) are easily computed. ＃　実行時間の最小化という見地からして有効である。 If space is at a premium, an alternative is to regard { W(t) } as a ＃　もしメモリ空間が貴重であれば、他の手段として、 ＃　{ W(t) }を循環キューと見なし、 Eastlake & Jones Informational [Page 7] RFC 3174 US Secure Hash Algorithm 1 (SHA1) September 2001 circular queue, which may be implemented using an array of sixteen ＃　16個の32ビット・ワード配列W[0], ... W[15]を使って実装してもよい。 32-bit words W[0], ... W[15]. In this case, in hex let ＃　この場合は、16進数でMASK = 0000000Fとする。 MASK = 0000000F. Then processing of M(i) is as follows: ＃　このときのM(i)の処理は、以下のようになる： a. Divide M(i) into 16 words W[0], ... , W[15], where W[0] is the ＃　M(i)を16個のワードW[0], ... , W[15]に分割する。 left-most word. ＃　W(0)は最も左側のワードである。 b. Let A = H0, B = H1, C = H2, D = H3, E = H4. ＃　この計算を行う。 c. For t = 0 to 79 do ＃　tが0から79の間で、次の計算を行う。 s = t AND MASK; if (t >= 16) W[s] = S^1(W[(s + 13) AND MASK] XOR W[(s + 8) AND MASK] XOR W[(s + 2) AND MASK] XOR W[s]); TEMP = S^5(A) + f(t;B,C,D) + E + W[s] + K(t); E = D; D = C; C = S^30(B); B = A; A = TEMP; d. Let H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4 + E. ＃　この計算を行う。 7. C Code ＃　C言語による実装 Below is a demonstration implementation of SHA-1 in C. Section 7.1 ＃　以下は、C言語によるSHA-1の実装の実例である。 contains the header file, 7.2 the C code, and 7.3 a test driver. ＃　7.1節はヘッダファイル、7.2節はCのコード、7.3節はテストドライバである。 7.1 .h file ＃　ヘッダファイル /* * sha1.h * * Description: * This is the header file for code which implements the Secure * Hashing Algorithm 1 as defined in FIPS PUB 180-1 published * April 17, 1995. * * Many of the variable names in this code, especially the * single character names, were used because those were the names * used in the publication. * * Please read the file sha1.c for more information. * */ Eastlake & Jones Informational [Page 8] RFC 3174 US Secure Hash Algorithm 1 (SHA1) September 2001 #ifndef _SHA1_H_ #define _SHA1_H_ #include /* * If you do not have the ISO standard stdint.h header file, then you * must typdef the following: * name meaning * uint32_t unsigned 32 bit integer * uint8_t unsigned 8 bit integer (i.e., unsigned char) * int_least16_t integer of >= 16 bits * */ #ifndef _SHA_enum_ #define _SHA_enum_ enum { shaSuccess = 0, shaNull, /* Null pointer parameter */ shaInputTooLong, /* input data too long */ shaStateError /* called Input after Result */ }; #endif #define SHA1HashSize 20 /* * This structure will hold context information for the SHA-1 * hashing operation */ typedef struct SHA1Context { uint32_t Intermediate_Hash[SHA1HashSize/4]; /* Message Digest */ uint32_t Length_Low; /* Message length in bits */ uint32_t Length_High; /* Message length in bits */ /* Index into message block array */ int_least16_t Message_Block_Index; uint8_t Message_Block[64]; /* 512-bit message blocks */ int Computed; /* Is the digest computed? */ int Corrupted; /* Is the message digest corrupted? */ } SHA1Context; /* * Function Prototypes */ Eastlake & Jones Informational [Page 9] RFC 3174 US Secure Hash Algorithm 1 (SHA1) September 2001 int SHA1Reset( SHA1Context *); int SHA1Input( SHA1Context *, const uint8_t *, unsigned int); int SHA1Result( SHA1Context *, uint8_t Message_Digest[SHA1HashSize]); #endif 7.2 .c file ＃　ソースファイル /* * sha1.c * * Description: * This file implements the Secure Hashing Algorithm 1 as * defined in FIPS PUB 180-1 published April 17, 1995. * * The SHA-1, produces a 160-bit message digest for a given * data stream. It should take about 2**n steps to find a * message with the same digest as a given message and * 2**(n/2) to find any two messages with the same digest, * when n is the digest size in bits. Therefore, this * algorithm can serve as a means of providing a * "fingerprint" for a message. * * Portability Issues: * SHA-1 is defined in terms of 32-bit "words". This code * uses (included via "sha1.h" to define 32 and 8 * bit unsigned integer types. If your C compiler does not * support 32 bit unsigned integers, this code is not * appropriate. * * Caveats: * SHA-1 is designed to work with messages less than 2^64 bits * long. Although SHA-1 allows a message digest to be generated * for messages of any number of bits less than 2^64, this * implementation only works with messages with a length that is * a multiple of the size of an 8-bit character. * */ Eastlake & Jones Informational [Page 10] RFC 3174 US Secure Hash Algorithm 1 (SHA1) September 2001 #include "sha1.h" /* * Define the SHA1 circular left shift macro */ #define SHA1CircularShift(bits,word) \ (((word) << (bits)) | ((word) >> (32-(bits)))) /* Local Function Prototyptes */ void SHA1PadMessage(SHA1Context *); void SHA1ProcessMessageBlock(SHA1Context *); /* * SHA1Reset * * Description: * This function will initialize the SHA1Context in preparation * for computing a new SHA1 message digest. * * Parameters: * context: [in/out] * The context to reset. * * Returns: * sha Error Code. * */ int SHA1Reset(SHA1Context *context) { if (!context) { return shaNull; } context->Length_Low = 0; context->Length_High = 0; context->Message_Block_Index = 0; context->Intermediate_Hash[0] = 0x67452301; context->Intermediate_Hash[1] = 0xEFCDAB89; context->Intermediate_Hash[2] = 0x98BADCFE; context->Intermediate_Hash[3] = 0x10325476; context->Intermediate_Hash[4] = 0xC3D2E1F0; context->Computed = 0; context->Corrupted = 0; Eastlake & Jones Informational [Page 11] RFC 3174 US Secure Hash Algorithm 1 (SHA1) September 2001 return shaSuccess; } /* * SHA1Result * * Description: * This function will return the 160-bit message digest into the * Message_Digest array provided by the caller. * NOTE: The first octet of hash is stored in the 0th element, * the last octet of hash in the 19th element. * * Parameters: * context: [in/out] * The context to use to calculate the SHA-1 hash. * Message_Digest: [out] * Where the digest is returned. * * Returns: * sha Error Code. * */ int SHA1Result( SHA1Context *context, uint8_t Message_Digest[SHA1HashSize]) { int i; if (!context || !Message_Digest) { return shaNull; } if (context->Corrupted) { return context->Corrupted; } if (!context->Computed) { SHA1PadMessage(context); for(i=0; i<64; ++i) { /* message may be sensitive, clear it out */ context->Message_Block[i] = 0; } context->Length_Low = 0; /* and clear length */ context->Length_High = 0; context->Computed = 1; Eastlake & Jones Informational [Page 12] RFC 3174 US Secure Hash Algorithm 1 (SHA1) September 2001 } for(i = 0; i < SHA1HashSize; ++i) { Message_Digest[i] = context->Intermediate_Hash[i>>2] >> 8 * ( 3 - ( i & 0x03 ) ); } return shaSuccess; } /* * SHA1Input * * Description: * This function accepts an array of octets as the next portion * of the message. * * Parameters: * context: [in/out] * The SHA context to update * message_array: [in] * An array of characters representing the next portion of * the message. * length: [in] * The length of the message in message_array * * Returns: * sha Error Code. * */ int SHA1Input( SHA1Context *context, const uint8_t *message_array, unsigned length) { if (!length) { return shaSuccess; } if (!context || !message_array) { return shaNull; } if (context->Computed) { context->Corrupted = shaStateError; Eastlake & Jones Informational [Page 13] RFC 3174 US Secure Hash Algorithm 1 (SHA1) September 2001 return shaStateError; } if (context->Corrupted) { return context->Corrupted; } while(length-- && !context->Corrupted) { context->Message_Block[context->Message_Block_Index++] = (*message_array & 0xFF); context->Length_Low += 8; if (context->Length_Low == 0) { context->Length_High++; if (context->Length_High == 0) { /* Message is too long */ context->Corrupted = 1; } } if (context->Message_Block_Index == 64) { SHA1ProcessMessageBlock(context); } message_array++; } return shaSuccess; } /* * SHA1ProcessMessageBlock * * Description: * This function will process the next 512 bits of the message * stored in the Message_Block array. * * Parameters: * None. * * Returns: * Nothing. * * Comments: Eastlake & Jones Informational [Page 14] RFC 3174 US Secure Hash Algorithm 1 (SHA1) September 2001 * Many of the variable names in this code, especially the * single character names, were used because those were the * names used in the publication. * * */ void SHA1ProcessMessageBlock(SHA1Context *context) { const uint32_t K[] = { /* Constants defined in SHA-1 */ 0x5A827999, 0x6ED9EBA1, 0x8F1BBCDC, 0xCA62C1D6 }; int t; /* Loop counter */ uint32_t temp; /* Temporary word value */ uint32_t W[80]; /* Word sequence */ uint32_t A, B, C, D, E; /* Word buffers */ /* * Initialize the first 16 words in the array W */ for(t = 0; t < 16; t++) { W[t] = context->Message_Block[t * 4] << 24; W[t] |= context->Message_Block[t * 4 + 1] << 16; W[t] |= context->Message_Block[t * 4 + 2] << 8; W[t] |= context->Message_Block[t * 4 + 3]; } for(t = 16; t < 80; t++) { W[t] = SHA1CircularShift(1,W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16]); } A = context->Intermediate_Hash[0]; B = context->Intermediate_Hash[1]; C = context->Intermediate_Hash[2]; D = context->Intermediate_Hash[3]; E = context->Intermediate_Hash[4]; for(t = 0; t < 20; t++) { temp = SHA1CircularShift(5,A) + ((B & C) | ((~B) & D)) + E + W[t] + K[0]; E = D; D = C; C = SHA1CircularShift(30,B); Eastlake & Jones Informational [Page 15] RFC 3174 US Secure Hash Algorithm 1 (SHA1) September 2001 B = A; A = temp; } for(t = 20; t < 40; t++) { temp = SHA1CircularShift(5,A) + (B ^ C ^ D) + E + W[t] + K[1]; E = D; D = C; C = SHA1CircularShift(30,B); B = A; A = temp; } for(t = 40; t < 60; t++) { temp = SHA1CircularShift(5,A) + ((B & C) | (B & D) | (C & D)) + E + W[t] + K[2]; E = D; D = C; C = SHA1CircularShift(30,B); B = A; A = temp; } for(t = 60; t < 80; t++) { temp = SHA1CircularShift(5,A) + (B ^ C ^ D) + E + W[t] + K[3]; E = D; D = C; C = SHA1CircularShift(30,B); B = A; A = temp; } context->Intermediate_Hash[0] += A; context->Intermediate_Hash[1] += B; context->Intermediate_Hash[2] += C; context->Intermediate_Hash[3] += D; context->Intermediate_Hash[4] += E; context->Message_Block_Index = 0; } /* * SHA1PadMessage * Eastlake & Jones Informational [Page 16] RFC 3174 US Secure Hash Algorithm 1 (SHA1) September 2001 * Description: * According to the standard, the message must be padded to an even * 512 bits. The first padding bit must be a '1'. The last 64 * bits represent the length of the original message. All bits in * between should be 0. This function will pad the message * according to those rules by filling the Message_Block array * accordingly. It will also call the ProcessMessageBlock function * provided appropriately. When it returns, it can be assumed that * the message digest has been computed. * * Parameters: * context: [in/out] * The context to pad * ProcessMessageBlock: [in] * The appropriate SHA*ProcessMessageBlock function * Returns: * Nothing. * */ void SHA1PadMessage(SHA1Context *context) { /* * Check to see if the current message block is too small to hold * the initial padding bits and length. If so, we will pad the * block, process it, and then continue padding into a second * block. */ if (context->Message_Block_Index > 55) { context->Message_Block[context->Message_Block_Index++] = 0x80; while(context->Message_Block_Index < 64) { context->Message_Block[context->Message_Block_Index++] = 0; } SHA1ProcessMessageBlock(context); while(context->Message_Block_Index < 56) { context->Message_Block[context->Message_Block_Index++] = 0; } } else { context->Message_Block[context->Message_Block_Index++] = 0x80; while(context->Message_Block_Index < 56) { Eastlake & Jones Informational [Page 17] RFC 3174 US Secure Hash Algorithm 1 (SHA1) September 2001 context->Message_Block[context->Message_Block_Index++] = 0; } } /* * Store the message length as the last 8 octets */ context->Message_Block[56] = context->Length_High >> 24; context->Message_Block[57] = context->Length_High >> 16; context->Message_Block[58] = context->Length_High >> 8; context->Message_Block[59] = context->Length_High; context->Message_Block[60] = context->Length_Low >> 24; context->Message_Block[61] = context->Length_Low >> 16; context->Message_Block[62] = context->Length_Low >> 8; context->Message_Block[63] = context->Length_Low; SHA1ProcessMessageBlock(context); } 7.3 Test Driver ＃　テストドライバ The following code is a main program test driver to exercise the code in sha1.c. /* * sha1test.c * * Description: * This file will exercise the SHA-1 code performing the three * tests documented in FIPS PUB 180-1 plus one which calls * SHA1Input with an exact multiple of 512 bits, plus a few * error test checks. * * Portability Issues: * None. * */ #include #include #include #include "sha1.h" /* * Define patterns for testing */ #define TEST1 "abc" #define TEST2a "abcdbcdecdefdefgefghfghighijhi" Eastlake & Jones Informational [Page 18] RFC 3174 US Secure Hash Algorithm 1 (SHA1) September 2001 #define TEST2b "jkijkljklmklmnlmnomnopnopq" #define TEST2 TEST2a TEST2b #define TEST3 "a" #define TEST4a "01234567012345670123456701234567" #define TEST4b "01234567012345670123456701234567" /* an exact multiple of 512 bits */ #define TEST4 TEST4a TEST4b char *testarray[4] = { TEST1, TEST2, TEST3, TEST4 }; long int repeatcount[4] = { 1, 1, 1000000, 10 }; char *resultarray[4] = { "A9 99 3E 36 47 06 81 6A BA 3E 25 71 78 50 C2 6C 9C D0 D8 9D", "84 98 3E 44 1C 3B D2 6E BA AE 4A A1 F9 51 29 E5 E5 46 70 F1", "34 AA 97 3C D4 C4 DA A4 F6 1E EB 2B DB AD 27 31 65 34 01 6F", "DE A3 56 A2 CD DD 90 C7 A7 EC ED C5 EB B5 63 93 4F 46 04 52" }; int main() { SHA1Context sha; int i, j, err; uint8_t Message_Digest[20]; /* * Perform SHA-1 tests */ for(j = 0; j < 4; ++j) { printf( "\nTest %d: %d, '%s'\n", j+1, repeatcount[j], testarray[j]); err = SHA1Reset(&sha); if (err) { fprintf(stderr, "SHA1Reset Error %d.\n", err ); break; /* out of for j loop */ } for(i = 0; i < repeatcount[j]; ++i) { Eastlake & Jones Informational [Page 19] RFC 3174 US Secure Hash Algorithm 1 (SHA1) September 2001 err = SHA1Input(&sha, (const unsigned char *) testarray[j], strlen(testarray[j])); if (err) { fprintf(stderr, "SHA1Input Error %d.\n", err ); break; /* out of for i loop */ } } err = SHA1Result(&sha, Message_Digest); if (err) { fprintf(stderr, "SHA1Result Error %d, could not compute message digest.\n", err ); } else { printf("\t"); for(i = 0; i < 20 ; ++i) { printf("%02X ", Message_Digest[i]); } printf("\n"); } printf("Should match:\n"); printf("\t%s\n", resultarray[j]); } /* Test some error returns */ err = SHA1Input(&sha,(const unsigned char *) testarray[1], 1); printf ("\nError %d. Should be %d.\n", err, shaStateError ); err = SHA1Reset(0); printf ("\nError %d. Should be %d.\n", err, shaNull ); return 0; } 8. Security Considerations ＃　セキュリティ上考慮されるべきこと This document is intended to provide convenient open source access by ＃　この文書は、インターネット・コミュニティによる、 the Internet community to the United States of America Federal ＃　米国・連邦情報処理標準・SHA-1[FIPS180-1]への Information Processing Standard Secure Hash Function SHA-1 [FIPS ＃　オープンソースな（？）アクセスのための便宜を図ることを意図する。 180-1]. No independent assertion of the security of this hash ＃　何らかの特別な用途に対する、このハッシュ関数のセキュリティについての、 function by the authors for any particular use is intended. ＃　著者による独立した（？）主張は意図しない。 Eastlake & Jones Informational [Page 20] RFC 3174 US Secure Hash Algorithm 1 (SHA1) September 2001 References ＃　参考文献 [FIPS 180-1] "Secure Hash Standard", United States of American, National Institute of Science and Technology, Federal Information Processing Standard (FIPS) 180-1, April 1993. [MD4] "The MD4 Message Digest Algorithm," Advances in Cryptology - CRYPTO '90 Proceedings, Springer-Verlag, 1991, pp. 303-311. [RFC 1320] Rivest, R., "The MD4 Message-Digest Algorithm", RFC 1320, April 1992. [RFC 1321] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, April 1992. [RFC 1750] Eastlake, D., Crocker, S. and J. Schiller, "Randomness Requirements for Security", RFC 1750, December 1994. Authors' Addresses ＃　著者連絡先 Donald E. Eastlake, 3rd Motorola 155 Beaver Street Milford, MA 01757 USA Phone: +1 508-634-2066 (h) +1 508-261-5434 (w) Fax: +1 508-261-4777 EMail: Donald.Eastlake@motorola.com Paul E. Jones Cisco Systems, Inc. 7025 Kit Creek Road Research Triangle Park, NC 27709 USA Phone: +1 919 392 6948 EMail: paulej@packetizer.com Eastlake & Jones Informational [Page 21] RFC 3174 US Secure Hash Algorithm 1 (SHA1) September 2001 Full Copyright Statement ＃　著作権全文提示 Copyright (C) The Internet Society (2001). All Rights Reserved. This document and translations of it may be copied and furnished to ＃　本文書とその翻訳は、複製および他に提供することができる。 others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this ＃　また、この文書に論評や説明を加えたり、その実装を補助するものは、 ＃　上記の著作権表示およびこ の節を付加していれば、 ＃　全体あるいは一部であっても一切の制約を課されることなく ＃　作成、複製、 発表、配布できる。 ただし、 document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of ＃　この文書自体に対して、著作権表示やインターネットソサエティ ＃　もしくは他のインターネット関 連団体への参照を取り除くなどの ＃　変更を加えてはならない。 developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. ＃　インターネット標準化過程で定義されている著作権のための手続きに従って、 ＃　インターネット標準を 開発するために必要な場合や、 ＃　RFC を英語以外の言語に翻訳する必要がある場合はそのかぎり でない。 The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. ＃　上記の制限は永続的なものであり、インターネットソサエティもしくは ＃　その継承者や譲渡者によって取 り消されることはない。 This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. ＃　本文書とここに含まれた情報は「無保証」で提供され、 ＃　インターネットソサエティおよび IETF はす べての保証を ＃　明示的にも暗黙的にもおこなわない。 ＃　その中には、この情報がいかなる権利も侵害していないという保証や、 ＃　商用利用および特定 目的における適合性への保証が含まれる。 Acknowledgement ＃　謝辞 Funding for the RFC Editor function is currently provided by the Internet Society. ＃　RFC編集作業のための資金は現在、the Internet Societyより提供されている。 Eastlake & Jones Informational [Page 22]