青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

woaidongmao

文章均收錄自他人博客,但不喜標(biāo)題前加-[轉(zhuǎn)貼],因其丑陋,見(jiàn)諒!~
隨筆 - 1469, 文章 - 0, 評(píng)論 - 661, 引用 - 0
數(shù)據(jù)加載中……

數(shù)據(jù)校驗(yàn)雜談——CRC,MD5和SHA-1原理、實(shí)現(xiàn)及其破解

  數(shù)據(jù)校驗(yàn)是計(jì)算機(jī)發(fā)展至今的至關(guān)重要的部分。但是它一般作為底層、后臺(tái)或者內(nèi)置模塊出現(xiàn),因而即使對(duì)于多數(shù)成天在計(jì)算機(jī)網(wǎng)絡(luò)里飄蕩的人來(lái)也說(shuō)并不十分了解。前段時(shí)間由于特殊原因深入學(xué)習(xí)了一下MD5,后面接著學(xué)習(xí)了SHA-1和CRC32,我發(fā)覺(jué)網(wǎng)絡(luò)上的資料并不多,尤其是中文的資料大概就那么兩三個(gè)版本。小奀在這里根據(jù)我的學(xué)習(xí)體會(huì)整體的淺談(掃盲級(jí)/入門(mén)初級(jí))一下這幾種在目前主要使用的數(shù)據(jù)校驗(yàn)算法,不當(dāng)之處請(qǐng)高人指正。
當(dāng)前最常用的三個(gè)數(shù)據(jù)校驗(yàn)算法CRC、MD5和SHA-1當(dāng)中,強(qiáng)度(這個(gè)強(qiáng)度是相對(duì)于被破解的困難程度來(lái)說(shuō)的)以CRC最弱,而SHA-1最強(qiáng)。其實(shí)三個(gè)算法的原理和實(shí)現(xiàn)都很簡(jiǎn)單(CRC優(yōu)化的算法可能比較費(fèi)解),下面依次講起,并對(duì)各算法的當(dāng)前破解情況進(jìn)行了介紹,在相應(yīng)之處列有比較詳細(xì)的參考文檔。

CRC
CRC是什么?CRC的全稱(chēng)是Cyclic Redundancy Checksum,即“循環(huán)冗余校驗(yàn)碼”。簡(jiǎn)單的說(shuō)它是一種利用二進(jìn)制的多項(xiàng)式除法來(lái)取得數(shù)據(jù)的校驗(yàn)和的方法。
CRC有什么用?目前主要使用在哪些地方?一如其名,CRC對(duì)數(shù)據(jù)的處理結(jié)果是取得一個(gè)校驗(yàn)碼,在數(shù)據(jù)傳輸?shù)那昂蠓謩e計(jì)算一次,然后進(jìn)行比較就可以發(fā)現(xiàn)是否有錯(cuò)誤發(fā)生。打一個(gè)不是很恰當(dāng)?shù)谋确?,你乘?chē)前檢查了一下錢(qián)包,里面有N張RMB,下車(chē)的時(shí)候你再檢查一次,如果不是N張RMB的話你就會(huì)應(yīng)該意識(shí)到出問(wèn)題了(不過(guò)這種情況下一般是會(huì)減少吧),但如果還是N張RMB的時(shí)候是否能保證沒(méi)有出問(wèn)題了呢——很不幸,不一定,有可能被人家換了幾張小額的給你,或者換了假幣給你,這就類(lèi)似于后邊要講到的“CRC碰撞”。CRC廣泛應(yīng)用于以太網(wǎng)的數(shù)據(jù)包檢查,PNG,以及我們常用的壓縮軟件(PKZIP, Zlib,WinRAR……)等。
CRC原理是什么?原理其實(shí)非常簡(jiǎn)單,就是二進(jìn)制的多項(xiàng)式除法。在后面的參考文檔里有不厭其煩的描述,當(dāng)需要更詳細(xì)的講解時(shí)建議你參考這些列出的文檔。在這里我只簡(jiǎn)單的說(shuō)說(shuō)我在學(xué)習(xí)過(guò)程中覺(jué)得比較重要的幾點(diǎn):
1.這個(gè)二進(jìn)制除法的沒(méi)有優(yōu)化的偽代碼大概可以這樣寫(xiě)(設(shè)除數(shù)有P個(gè)bits):
{
任命余數(shù)r = 被除數(shù)的前(P-1)位;
while(被除數(shù)還有剩余bit沒(méi)有補(bǔ)入到r中)
{
補(bǔ)入一個(gè)bit到r中;
r = 補(bǔ)位后的r作為被除數(shù) 除以 除數(shù) 所得的余數(shù);
}
哈哈,這回完了吧。就是你了,拿起小r就可以跑了;
}
看看吧,是不是覺(jué)得很熟悉?的確,跟我們年輕時(shí)學(xué)過(guò)的一模一樣。
2.二進(jìn)制的多項(xiàng)式除法這個(gè)東東跟我們小學(xué)學(xué)過(guò)的普通的十進(jìn)制運(yùn)算沒(méi)有多大差別,簡(jiǎn)單的來(lái)說(shuō)就是不考慮進(jìn)位退位就可以了,記住這個(gè)很重要。那么不夠減的時(shí)候怎么辦呢?直接把本來(lái)是0的位看作2就可以了。
3.二進(jìn)制的多項(xiàng)式除法運(yùn)算中,對(duì)于有T個(gè)bit位的被除數(shù)除以有P個(gè)bit位的除數(shù),應(yīng)該除多少次才能得到余數(shù)呢?如果除數(shù)的高位為1時(shí),應(yīng)該做(T +1-P)次運(yùn)算(如果T+1<P,那么為0次)。有的人可能會(huì)反駁說(shuō)CRC的實(shí)作代碼中是(T-P)次,其實(shí)問(wèn)題在于那里使用的除數(shù)是把最高位去掉了的。
4.關(guān)于除數(shù)多項(xiàng)式Poly(以下簡(jiǎn)稱(chēng)Poly)。我曾經(jīng)看過(guò)一篇中文文檔中說(shuō),“不要問(wèn)我為什么Poly的最高位和最低位都是 1,因?yàn)檫@是規(guī)定”。規(guī)定當(dāng)然是規(guī)定,但是做出這種規(guī)定也應(yīng)當(dāng)是有原因的吧?根據(jù)我的個(gè)人理解(當(dāng)然,也許這是錯(cuò)誤的理解),首先最高位必須為1,這個(gè) bit位在英文文檔中稱(chēng)為"Active" bit,為什么呢?如果Poly最高位不是1那么除法無(wú)法進(jìn)行下去而得到有我們所需要的位數(shù)的余數(shù)(當(dāng)Poly最高位為0而被除數(shù)高位為1時(shí)無(wú)法抵消)。而低位為什么也必須為1呢?在有的使用場(chǎng)合是把CRC的Poly和被除數(shù)都做了反射之后再進(jìn)行的,這種情況下低位反射成了高位,基于前面同樣的理由,所以必須保持最低位也為1。
5.關(guān)于查表算法,查表法的主要目的是提高運(yùn)算速度。下面以最常用的CRC32為例。查表法的方案也不同,最長(zhǎng)采用的是按照字節(jié)(8位)生成碼表。這里對(duì)應(yīng)前面所述的最原始的除法方案進(jìn)行講述,即沒(méi)有反射,并把字節(jié)中的高位作為被除數(shù)的高位。
對(duì)于喜歡證明結(jié)論的人,或者可以按照如下的思路進(jìn)行:
在進(jìn)行除法的過(guò)程中,當(dāng)寄存器移出一個(gè)字節(jié)的時(shí)候,最終對(duì)余數(shù)的影響相當(dāng)于其后的四個(gè)字節(jié)異或上某一個(gè)值(設(shè)這個(gè)值為y),設(shè)移出值為x時(shí)對(duì)應(yīng)的y為f (x),那么這個(gè)f映射是一個(gè)雙射,這很容易證明。因?yàn)檫@個(gè)映射是一系列異或操作的疊加,而異或運(yùn)算滿(mǎn)足交換律和結(jié)合律。那么當(dāng)y后面的四個(gè)字節(jié)全為0 時(shí),可以推出余數(shù)值為:r = y^0 = f(x)^0 = f(x)。利用這個(gè)關(guān)系,對(duì)每個(gè)x值算出對(duì)應(yīng)的r,并記錄在以x值為下標(biāo)的數(shù)組中,就得到了f映射在x定義域上的所有值。而這個(gè)數(shù)組就是查表法所使用的碼表。
顯然,這個(gè)f映射是提高效率的關(guān)鍵,它相當(dāng)于有“預(yù)見(jiàn)性”的進(jìn)行一個(gè)字節(jié)的除法運(yùn)算。當(dāng)然也很容易想到可以有其他位數(shù)的查表算法,比如16位、32位等。而且如果你了解了以上的算法,你應(yīng)該可以想到兩點(diǎn)(以16位為例):前面256個(gè)元素和8位的應(yīng)該完全一致;16位的碼表可以通過(guò)類(lèi)似的按照位進(jìn)行運(yùn)算的方法得到,同樣也可以對(duì)8位的已經(jīng)運(yùn)算出的碼表進(jìn)行運(yùn)算得到,把一個(gè)字節(jié)看成一個(gè)“位”就行。
CRC的碰撞是什么東東?怎么產(chǎn)生的?CRC“碰撞”實(shí)際上是不同的源數(shù)據(jù)可能對(duì)應(yīng)同一個(gè)CRC值的沖突現(xiàn)象。根據(jù)前面的討論,可以把CRC看成一個(gè)從無(wú)限定義域映射到2的 32次方空間的一個(gè)單向函數(shù),很明顯這個(gè)映射是“多對(duì)一”的。這種現(xiàn)象類(lèi)似于中國(guó)目前的男女比率失調(diào)狀況,根據(jù)某甲某乙們預(yù)計(jì)的結(jié)果,到2020年,中國(guó)會(huì)有幾千萬(wàn)的男光棍出現(xiàn)——為啥乜?其實(shí)簡(jiǎn)單的說(shuō)就是供映射的目標(biāo)空間不夠大,在這種情況下如果保證每個(gè)人都不做光棍的話,那么除了從外國(guó)(當(dāng)然也可以是外星球)大力引進(jìn)適齡女子外,就只能多男共事一妻了^_^(各位兄弟們,你今天汗了嗎?)。
CRC被破解了么?是的。實(shí)際上要從CRC結(jié)果逆向找回?cái)?shù)據(jù)源幾乎是不可行的,因?yàn)檫@是個(gè)一對(duì)多的映射,因此所謂的“破解”一般指找到一個(gè)產(chǎn)生相同CRC結(jié)果的數(shù)據(jù),但無(wú)法判斷這個(gè)找到的數(shù)據(jù)和源數(shù)據(jù)的異同(除非有上下文等信息)。CRC是一個(gè)相對(duì)簡(jiǎn)單的數(shù)據(jù)校驗(yàn)算法,從理論上我們得知只要提供比映射的目標(biāo)空間的值的個(gè)數(shù)(CRC32是2的32次方個(gè))更多的互不相同的源數(shù)據(jù)時(shí),就一定會(huì)出現(xiàn)CRC碰撞。實(shí)際上破解CRC是有規(guī)可循的,看雪論壇上有一篇文章做了理論推導(dǎo)并提供了程序下載,有興趣的請(qǐng)參考后面列出的參考文檔。

CRC 參考文檔
1. CRC圣經(jīng)(注:這是我所找到的一份最全的英文文檔,很多其他的英文文檔以及幾乎目前的所有中文文檔都是這份文檔的衍生品,我稱(chēng)其為“CRC圣經(jīng)”實(shí)在是一點(diǎn)都不為過(guò))
2. CSDN文章(這是CSDN上選自http://blog.csdn.net/chensheng913/ 的文章,基本上是CRC圣經(jīng)的節(jié)選翻譯+讀書(shū)筆記)
3. 老羅的繽紛天地:原理篇+實(shí)踐篇(注:老羅其實(shí)沒(méi)有老,文章非常好:-),這里另外還有匯編代碼)
4. RFC3309 中的講述
5. PNG中用到的CRC的實(shí)作代碼
6. Koders上的實(shí)作代碼(注:在此MHASH模塊中包含了CRC和本文中另外所提到的MD5和SHA-1,非常值得一看)
7. 看雪論壇上的破解文章

源地址未知。

posted on 2008-07-08 12:08 肥仔 閱讀(3355) 評(píng)論(0)  編輯 收藏 引用 所屬分類(lèi): C++ 基礎(chǔ)

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            99成人免费视频| 性欧美1819性猛交| 亚洲视频www| 日韩一级大片在线| 亚洲国产三级在线| 亚洲精品一线二线三线无人区| 红杏aⅴ成人免费视频| 一区二区三区在线不卡| 在线精品视频一区二区| 在线观看亚洲| 亚洲免费成人av电影| 一区二区日韩精品| 亚洲线精品一区二区三区八戒| 亚洲在线成人精品| 欧美在线一二三区| 久热精品视频在线观看| 免费欧美在线| 一本久道久久综合狠狠爱| 亚洲小视频在线| 久久久91精品国产| 欧美日韩国产成人在线91| 国产精品美女xx| 在线成人黄色| 亚洲欧美国产三级| 欧美jizzhd精品欧美喷水| 亚洲激情视频网| 一区二区精品国产| 久久国产婷婷国产香蕉| 欧美久久精品午夜青青大伊人| 国产精品欧美经典| 亚洲欧洲精品一区二区三区| 欧美亚洲日本国产| 亚洲精品一区二区三区不| 亚洲免费av观看| 久久乐国产精品| 亚洲免费电影在线观看| 亚洲国产精品va在线看黑人| 国产亚洲激情| 影音先锋日韩资源| 亚洲激情视频网站| 久久中文字幕导航| 欧美激情自拍| 欧美一区二区三区视频免费| 黄色免费成人| 国产精品大片wwwwww| 国产精品白丝jk黑袜喷水| 久久精品最新地址| 欧美性猛交xxxx免费看久久久| 久久综合给合久久狠狠色| 猛干欧美女孩| 亚洲欧美精品伊人久久| 国产一区二区精品久久99| 亚洲精品一区二区三区不| 久久精品国产一区二区三区| 99精品欧美| 欧美激情第3页| 在线观看国产日韩| 欧美中文字幕视频| 亚洲欧美日韩久久精品| 欧美四级在线| 一区二区三区四区五区精品视频| 免费不卡视频| 韩国成人理伦片免费播放| 久久久久久久网站| 亚洲欧美另类在线观看| 欧美日韩中文精品| 亚洲精品一区二区三区av| 久久综合九色| 久久久久久久一区二区三区| 国产一区激情| 久久婷婷成人综合色| 欧美亚洲一区二区在线| 国产日本欧美一区二区三区在线 | 久久久久**毛片大全| 国产麻豆午夜三级精品| 欧美在线亚洲| 国产欧美在线播放| 久久久成人网| 久久亚洲精品一区二区| 在线成人国产| 亚洲大胆人体视频| 亚洲国产精品久久久久久女王| 久久精彩视频| 久久久噜噜噜久久人人看| 亚洲三级影院| 一区二区欧美在线| 国产亚洲免费的视频看| 六十路精品视频| 欧美精品一区二区三区久久久竹菊| 99综合精品| 午夜影院日韩| 亚洲精品国产精品国自产观看浪潮 | 欧美在线免费看| 欧美日韩一区二区精品| 99国产精品| 亚洲精品综合精品自拍| 男女av一区三区二区色多| 亚洲第一在线视频| 欧美高清视频一二三区| 牛牛国产精品| 日韩视频精品在线| 日韩午夜激情| 国产精品日韩欧美一区二区| 亚洲欧美日韩在线| 午夜亚洲伦理| 久久久精品动漫| 最近中文字幕日韩精品| 欧美激情视频网站| 日韩一级黄色av| 国产精品激情电影| 久久精品动漫| 久久亚洲私人国产精品va媚药 | 久久精品国产清高在天天线 | 欧美一区二区黄色| 亚洲欧美一区在线| 久久久7777| 亚洲欧美怡红院| 欧美精品亚洲一区二区在线播放| 欧美在线一二三区| 最近看过的日韩成人| 久久香蕉国产线看观看网| 亚洲视频欧洲视频| 米奇777超碰欧美日韩亚洲| 亚洲欧美日韩天堂| 欧美在线日韩在线| 欧美日韩精品免费看 | 一区二区亚洲| 亚洲一区二区av电影| 日韩一级大片在线| 欧美1区3d| 美女视频黄 久久| 国产一区二区日韩精品| 一本不卡影院| 亚洲片在线资源| 美女被久久久| 另类尿喷潮videofree| 国产一区二区三区的电影| 亚洲新中文字幕| 亚洲一区三区在线观看| 欧美另类综合| 亚洲精品专区| 在线一区日本视频| 欧美精品精品一区| 亚洲伦理精品| 亚洲天堂男人| 国产精品爱啪在线线免费观看| 99热免费精品| 亚洲桃花岛网站| 国产精品久久77777| 亚洲永久网站| 久久九九电影| 亚洲高清123| 欧美国产日本韩| 亚洲人体偷拍| 亚洲欧美中文在线视频| 国产精品一区二区久久| 午夜在线播放视频欧美| 久久精品中文字幕一区| 在线成人小视频| 欧美国产精品v| 日韩小视频在线观看专区| 亚洲欧美精品在线观看| 国模叶桐国产精品一区| 久久亚洲色图| 一本到12不卡视频在线dvd| 欧美一级免费视频| 在线 亚洲欧美在线综合一区| 欧美激情一区二区三区在线视频观看| 亚洲人www| 亚洲欧美日韩视频二区| 影音国产精品| 99精品免费视频| 久久久亚洲精品一区二区三区 | 国产午夜精品美女视频明星a级| 久久本道综合色狠狠五月| 欧美激情 亚洲a∨综合| 亚洲一区二区三区高清不卡| 国产欧美日韩一区二区三区在线| 久久精品国产999大香线蕉| 亚洲高清视频一区二区| 亚洲欧美成人一区二区在线电影 | 一区二区欧美在线| 国产日韩av一区二区| 免费看的黄色欧美网站| 亚洲一区观看| 亚洲激情国产精品| 久久―日本道色综合久久| 一本色道久久综合亚洲二区三区| 国产欧美精品久久| 国产精品99久久久久久宅男| 国内精品久久久久影院色| 欧美国产视频在线| 久久成人av少妇免费| 日韩午夜在线| 亚洲高清资源综合久久精品| 午夜精品久久久久久久男人的天堂| 1204国产成人精品视频| 国产欧美一区二区精品仙草咪| 欧美高清在线视频| 久久久久久久一区二区|