SHA-1

SHA-1

概がい述じゅつ
设计者しゃ	美国びくに国家こっか安全あんぜん局きょく
首くび次じ发布	1993年ねん（SHA-0） 1995年ねん（SHA-1）
系列けいれつ	安全あんぜん散ち列れつ算法さんぽう家族かぞく
认证	FIPS PUB 180-4，CRYPTREC（监测）
密みつ码细节
摘要てきよう长度	160位い元もと
分ぶん组长度ど	512位い元もと
结构	Merkle–Damgård结构
重じゅう复回数すう	80
最さい佳けい公おおやけ开破やぶ解かい
2011年ねん，Marc Stevens的てき攻おさむ击，可か以通过复杂度260.3至いたり265.3的てき操作そうさ产生散ち列れつ碰撞。2017年ねん2月がつ23日にち，首しゅ次じ公おおやけ开碰撞。SHA-1容易ようい受到长度扩展攻おさむ击。

SHA-1（英語えいご：Secure Hash Algorithm 1，中ちゅう文名ぶんめい：安全あんぜん散ち列れつ算法さんぽう1）是ぜ一いち种密みつ码散列れつ函数かんすう，美国びくに国家こっか安全あんぜん局きょく设计，并由美国びくに國家こっか標準ひょうじゅん技術ぎじゅつ研究所けんきゅうじょ（NIST）发布为聯邦れんぽう資料しりょう處理しょり標準ひょうじゅん（FIPS）。SHA-1可か以生成せいせい一个被称为消息摘要的160位くらい（20字じ节）散ち列れつ值，散ち列れつ值通常つうじょう的てき呈てい现形式しき为40个十じゅう六ろく进制数かず。

2005年ねん，密みつ码分析ぶんせき人じん员发现了对SHA-1的てき有效ゆうこう攻おさむ击方法ほう，这表明ひょうめい该算法ほう可能かのう不ふ够安全あんぜん，不能ふのう继续使用しよう，自じ2010年ねん以来いらい，许多组织建けん议用SHA-2或あるSHA-3来らい替がえ换SHA-1。Microsoft、Google以及Mozilla都と宣布せんぷ，它们旗下きか的てき浏览器き将はた在ざい2017年ねん停止ていし接受せつじゅ使用しようSHA-1算法さんぽう签名的てきSSL证书。

2017年ねん2月がつ23日にち，CWI Amsterdam与あずかGoogle宣布せんぷ了りょう一いち个成功せいこう的てきSHA-1碰撞攻おさむ击，发布了りょう两份内容ないよう不同ふどう但ただしSHA-1散ち列れつ值相同どう的てきPDF文ぶん件けん作さく为概念がいねん证明。

2020年ねん，針はり對たいSHA-1的てき选择前ぜん缀冲突攻击已經けい實際じっさい可か行ぎょう。建議けんぎ盡つき可能かのう用ようSHA-2或あるSHA-3取と代がわSHA-1。

SHA-0和わSHA-1

SHA-1壓縮あっしゅく演算えんざん法ほう中ちゅう的てき一いち個こ迴圈。A, B, C, D和わE是ぜ這個state中ちゅう的てき32位い元もと文字もじ；F是ぜ會かい變化へんか的てき非ひ線せん性せい函數かんすう；<<<_n代表だいひょうbit向こう左ひだり循環じゅんかん移動いどうn個こ位置いち。n因いん操作そうさ而異。田た代表だいひょうmodulo 2³²之これ下か的てき加法かほう。K_t是ぜ一いち個こ常數じょうすう。W_t代表だいひょう经过拓つぶせ展てん后きさき的てき原文げんぶん。

最初さいしょ載の明あきら的てき演算えんざん法ほう於1993年ねん發はつ佈，稱しょう做安全ぜん雜ざつ湊みなと標準ひょうじゅん（Secure Hash Standard），FIPS PUB 180。這個版本はんぽん現在げんざい常つね被ひ稱しょう為ためSHA-0。它在發はつ佈之後ご很快就被NSA撤回てっかい，並なみ且由1995年ねん發はつ佈的修訂しゅうてい版本はんぽんFIPS PUB 180-1（通常つうじょう稱しょう為ためSHA-1）取と代だい。SHA-1和わSHA-0的てき演算えんざん法ほう只ただ在ざい壓縮あっしゅく函數かんすう的てき訊息轉換てんかん部ぶ份差了りょう一個位元的循環位移。根據こんきょNSA的てき說法せっぽう，它修正しゅうせい了りょう一個在原始演算法中會降低雜湊安全性的弱點。然しか而NSA並なみ沒ぼつ有ゆう提供ていきょう任にん何なん進しん一步的解釋或證明該弱點已被修正。而後SHA-0和わSHA-1的てき弱點じゃくてん相しょう繼ままし被ひ攻おさむ破やぶ，SHA-1似に乎是顯あらわ得とく比ひSHA-0有ゆう抵抗ていこう性せい，這多少たしょう證しょう實じつ了りょうNSA當初とうしょ修正しゅうせい演算えんざん法ほう以增進ぞうしん安全あんぜん性せい的てき聲明せいめい。

SHA-0和わSHA-1可か將しょう一いち個こ最大さいだい2⁶⁴位い元もと的てき訊息，轉換てんかん成なり一いち串くし160位い元もと的てき訊息摘要てきよう；其設計けい原理げんり相似そうじ於MIT教授きょうじゅRonald L. Rivest所ところ設計せっけい的てき密みつ碼學雜ざつ湊みなと演算えんざん法ほうMD4和わMD5。

SHA-0的てき破やぶ解かい

在ざいCRYPTO 98上じょう，兩りょう位い法ほう國こく研究けんきゅう者しゃ提出ていしゅつ一いち種しゅ對たいSHA-0的てき攻擊こうげき方式ほうしき：在ざい2⁶¹的てき計算けいさん複雜ふくざつ度ど之の內，就可以發現はつげん一いち次じ碰撞（即そく兩個りゃんこ不同ふどう的てき訊息對應たいおう到いた相あい同どう的てき訊息摘要てきよう）；這個數字すうじ小しょう於生なま日にち攻擊こうげき法ほう所ところ需的2⁸⁰，也就是ぜ說せつ，存在そんざい一いち種しゅ演算えんざん法ほう，使つかい其安全あんぜん性せい不ふ到いた一個理想的雜湊函數抵抗攻擊所應具備的計算複雜度。

2004年ねん時じ，Biham和かずChen也發現はつげん了りょうSHA-0的てき近似きんじ碰撞，也就是ぜ兩個りゃんこ訊息可か以雜湊みなと出いずる幾いく乎相同どう的てき數すう值；其中162位い元もと中有ちゅうう142位い元もと相しょう同どう。他た們也發現はつげん了りょうSHA-0的てき完かん整せい碰撞（相對そうたい於近似きんじ碰撞），將はた本來ほんらい需要じゅよう80次じ方かた的てき複雜ふくざつ度ど降くだ低てい到いた62次じ方かた。

2004年ねん8月がつ12日にち，Joux, Carribault, Lemuet和わJalby宣せん佈找到SHA-0演算えんざん法的ほうてき完かん整せい碰撞的てき方法ほうほう，這是歸納きのうChabaud和わJoux的てき攻擊こうげき所しょ完成かんせい的てき結果けっか。發現はつげん一個完整碰撞只需要2⁵¹的てき計算けいさん複雜ふくざつ度ど。他た們使用しよう的てき是ぜ一いち台だい有ゆう256顆Itanium2處理しょり器き的てき超ちょう級きゅう電腦でんのう，約やく耗80,000 CPU工こう時じ。

2004年ねん8月がつ17日にち，在ざいCRYPTO 2004的てきRump會議かいぎ上じょう，王おう小しょう雲くも，馮登國こく（Feng）、來き學がく嘉よしみ（Lai），和わ于紅波は（Yu）宣せん佈了攻擊こうげきMD5、SHA-0和わ其他雜ざつ湊みなと函數かんすう的てき初步しょほ結果けっか。他た們攻擊げきSHA-0的てき計算けいさん複雜ふくざつ度ど是ぜ2⁴⁰，這意味いみ的てき他た們的攻擊こうげき成果せいか比ひJoux還かえ有ゆう其他人たにん所しょ做的更さら好このみ。請參見みMD5安全あんぜん性せい。

2005年ねん二に月がつ，王おう小しょう雲くも和わ殷いん益えき群ぐん、于紅波は再度さいど發表はっぴょう了りょう對たいSHA-0破やぶ密みつ的てき演算えんざん法ほう，可か在ざい2³⁹的てき計算けいさん複雜ふくざつ度ど內就找到碰撞。

SHA-1的てき破やぶ解かい

鑒於SHA-0的てき破やぶ密みつ成果せいか，專せん家か們建議けんぎ那な些計劃利用りようSHA-1實み作さく密みつ碼系統的けいとうてき人じん們也應おう重おも新しん考慮こうりょ。在ざい2004年ねんCRYPTO會議かいぎ結果けっか公おおやけ佈之後ご，NIST即そく宣布せんぷ他た們將逐漸減少げんしょう使用しようSHA-1，改あらため以SHA-2取と而代之の。

2005年ねん，Rijmen和わOswald發表はっぴょう了りょう對たいSHA-1較弱版本はんぽん（53次じ的てき加か密みつ迴圈而非80次じ）的てき攻擊こうげき：在ざい2⁸⁰的てき計算けいさん複雜ふくざつ度ど之の內找到碰撞。

2005年ねん二に月がつ，王おう小しょう雲くも、殷いん益えき群ぐん及于紅波は發表はっぴょう了りょう對たい完かん整せい版ばんSHA-1的てき攻擊こうげき，只ただ需少於2⁶⁹的てき計算けいさん複雜ふくざつ度ど，就能找到一いち組くみ碰撞。（利用りよう生なま日にち攻擊こうげき法ほう找到碰撞需要じゅよう2⁸⁰的てき計算けいさん複雜ふくざつ度ど。）

這篇論文ろんぶん的てき作者さくしゃ們寫道どう；「我わが們的破やぶ密みつ分析ぶんせき是ぜ以對付づけSHA-0的てき差分さぶん攻擊こうげき、近似きんじ碰撞、多おお區く塊かたまり碰撞技術ぎじゅつ、以及從したがえMD5演算えんざん法ほう中ちゅう尋ひろ找碰撞的訊息更改こうかい技術ぎじゅつ為ため基礎きそ。沒ぼつ有ゆう這些強力きょうりょく的てき分析ぶんせき工具こうぐ，SHA-1就無法ほう破やぶ解かい。」此外，作者さくしゃ還かえ展示てんじ了りょう一いち次じ對たい58次じ加か密みつ迴圈SHA-1的てき破やぶ密みつ，在ざい2³³個こ單位たんい操作そうさ內就找到一いち組くみ碰撞。完かん整せい攻擊こうげき方法ほうほう的てき論文ろんぶん發表はっぴょう在ざい2005年ねん八はち月がつ的てきCRYPTO會議かいぎ中ちゅう。

殷いん益えき群ぐん在ざい一いち次じ面談めんだん中ちゅう如此陳述ちんじゅつ：「大だい致上來らい說せつ，我わが們找到了りょう兩個りゃんこ弱點じゃくてん：其一是前置處理不夠複雜；其二そのじ是ぜ前まえ20個こ迴圈中ちゅう的てき某ぼう些數學がく運算うんざん會かい造成ぞうせい不可ふか預あずか期き的てき安全あんぜん性せい問題もんだい。」

2005年ねん8月がつ17日にち的てきCRYPTO會議かいぎ尾お聲ごえ中ちゅう王おう小しょう雲くも、姚期智さとし、姚儲楓かえで再度さいど發表はっぴょう更さら有效ゆうこう率りつ的てきSHA-1攻擊こうげき法ほう，能のう在ざい2⁶³個こ計算けいさん複雜ふくざつ度ど內找到碰撞。

2006年ねん的てきCRYPTO會議かいぎ上じょう，Christian Rechberger和わChristophe De Cannière宣布せんぷ他た們能在ざい容よう許もと攻擊こうげき者しゃ決定けってい部分ぶぶん原げん訊息的てき條件じょうけん之の下した，找到SHA-1的てき一いち個こ碰撞。

在ざい密みつ碼學的てき學術がくじゅつ理論りろん中ちゅう，任にん何なん攻擊こうげき方式ほうしき，其計算けいさん複雜ふくざつ度ど若わか少しょう於暴力りょく搜さがせ尋ひろ法ほう所しょ需要じゅよう的てき計算けいさん複雜ふくざつ度ど，就能被ひ視し為ため針はり對たい該密碼系統けいとう的てき一種破密法；但ただし這並不ふ表示ひょうじ該破密みつ法ほう已やめ經けい可か以進入しんにゅう實際じっさい應用おうよう的てき階段かいだん。

就應用おうよう層そう面めん的てき考量こうりょう而言，一種新的破密法出現，暗示あんじ着ぎ將來しょうらい可能かのう會かい出現しゅつげん更さら有效ゆうこう率りつ、足あし以實用じつよう的てき改良かいりょう版本はんぽん。雖然這些實用じつよう的てき破やぶ密みつ法ほう版本はんぽん根本こんぽん還かえ沒ぼっ誕生たんじょう，但ただし確かく有ゆう必要ひつよう發展はってん更さら強的ごうてき雜ざつ湊みなと演算えんざん法ほう來らい取と代だい舊きゅう的てき演算えんざん法ほう。在ざい「碰撞」攻擊こうげき法ほう之の外そと，另有一いち種しゅ反譯はんやく攻擊こうげき法ほう（Pre-image attack），就是由よし雜ざつ湊みなと出いずる的てき字じ串くし反はん推原本げんぽん的てき訊息；反譯はんやく攻擊こうげき的てき嚴重げんじゅう性せい更さら在ざい碰撞攻擊こうげき之の上うえ，但ただし也更困難こんなん。在ざい許多きょた會かい應用おうよう到いた密みつ碼雜湊みなと的てき情じょう境さかい（如用戶ど密みつ碼的存そん放ひ、文ぶん件けん的てき數すう位い簽章等ひとし）中ちゅう，碰撞攻擊こうげき的てき影響えいきょう並なみ不ふ是ぜ很大。舉例來らい說せつ，一個攻擊者可能不會只想要偽造一份一模一樣的文件，而會想そう改造かいぞう原ばら來らい的てき文ぶん件けん，再さい附ふ上じょう合法ごうほう的てき簽章，來らい愚弄ぐろう持じ有ゆう公こう钥的驗けん證しょう者しゃ。另一方面ほうめん，如果可か以從密みつ文中ぶんちゅう反はん推未加か密みつ前まえ的てき使用しよう者しゃ密みつ碼，攻擊こうげき者しゃ就能利用りよう得え到いた的てき密みつ碼登入にゅう其他使用しよう者しゃ的てき帳とばり戶ど，而這種しゅ事ごと在ざい密みつ碼系統けいとう中ちゅう是ぜ不能ふのう被ひ允許いんきょ的てき。但ただし若わか存在そんざい反譯はんやく攻擊こうげき，只ただ要よう能のう得え到いた指定してい使用しよう者しゃ密みつ碼雜湊みなと過か後こう的てき字じ串くし（通常つうじょう存在そんざい影かげ檔中，而且可能かのう不ふ會かい透とおる露ろ原はら密ひそか碼資訊），就有可能かのう得え到いた該使用しよう者しゃ的てき密みつ碼。

2017年ねん2月がつ23日にち，Google公司こうし宣布せんぷ，他た们与CWI Amsterdam合作がっさく创建了りょう两个有ゆう着ぎ相しょう同どうSHA-1值但内容ないよう不同ふどう的てきPDF文ぶん件けん，这代表だいひょうSHA-1演算えんざん法ほう已やめ被ひ正式せいしき攻おさむ破やぶ。

2020年ねん，針はり對たいSHA-1的てき选择前ぜん缀冲突攻击已經けい實際じっさい可か行ぎょう。建議けんぎ盡つき可能かのう用ようSHA-2或あるSHA-3取と代がわSHA-1。在ざい數すう位い簽章領域りょういき，用よう更さら安全あんぜん的てきSHA-2或あるSHA-3替かえ換かわSHA-1已やめ經けい變へん得とく急迫きゅうはく。

SHA-1演算えんざん法ほう

以下いか是ぜSHA-1演算えんざん法ほう的てき伪代码：

Note: All variables are unsigned 32 bits and wrap modulo 232 when calculating

Initial variables:
h0 := 0x67452301
h1 := 0xEFCDAB89
h2 := 0x98BADCFE
h3 := 0x10325476
h4 := 0xC3D2E1F0

Pre-processing:
append the bit '1' to the message
append k bits '0', where k is the minimum number >= 0 such that the resulting message
    length (in bits) is congruent to 448(mod 512)
append length of message (before pre-processing), in bits, as 64-bit big-endian integer

Process the message in successive 512-bit chunks:
break message into 512-bit chunks
for each chunk
    break chunk into sixteen 32-bit big-endian words w[i], 0 ≤ i ≤ 15

    Extend the sixteen 32-bit words into eighty 32-bit words:
    for i from 16 to 79
        w[i] := (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1

    Initialize hash value for this chunk:
    a := h0
    b := h1
    c := h2
    d := h3
    e := h4

    Main loop:
    for i from 0 to 79
        if 0 ≤ i ≤ 19 then
            f := (b and c) or ((not b) and d)
            k := 0x5A827999
        else if 20 ≤ i ≤ 39
            f := b xor c xor d
            k := 0x6ED9EBA1
        else if 40 ≤ i ≤ 59
            f := (b and c) or (b and d) or(c and d)
            k := 0x8F1BBCDC
        else if 60 ≤ i ≤ 79
            f := b xor c xor d
            k := 0xCA62C1D6

        temp := (a leftrotate 5) + f + e + k + w[i]
        e := d
        d := c
        c := b leftrotate 30
        b := a
        a := temp

    Add this chunk's hash to result so far:
    h0 := h0 + a
    h1 := h1 + b
    h2 := h2 + c
    h3 := h3 + d
    h4 := h4 + e

Produce the final hash value (big-endian):
digest = hash = h0 append h1 append h2 append h3 append h4

上述じょうじゅつ關せき於f運算うんざん式しき列れつ於FIPS PUB 180-1中ちゅう，以下いか替がえ代だい運算うんざん式しき也許也能在ざい主要しゅよう迴圈裡うら計算けいさんf：

(0  ≤ i ≤ 19): f := d xor (b and (c xor d))         (alternative)
 
(40 ≤ i ≤ 59): f := (b and c) or (d and (b or c))   (alternative 1)
(40 ≤ i ≤ 59): f := (b and c) or (d and (b xor c))  (alternative 2)
(40 ≤ i ≤ 59): f := (b and c) + (d and (b xor c))   (alternative 3)

SHA-1示しめせ例れい

空文くうぶん的てき散ち列れつ为：

SHA-1("") 
= da39a3ee5e6b4b0d3255bfef95601890afd80709