我們又在搞事了。 最近和幾位老師吹牛討論密碼學(xué)小白研究生入門的培養(yǎng)問(wèn)題。如何準(zhǔn)備1000道小白問(wèn)題幫助學(xué)生入門（別期待哈，我們計(jì)劃退休的時(shí)候才弄好，而且沒(méi)有答案）。 今天，我們發(fā)現(xiàn)一個(gè)看似簡(jiǎn)單的入門問(wèn)題，收到的答案卻是五花八門。放在這里，讓大家圍觀下，感受下密碼學(xué)的入門門檻?！“讋裢宋膮?。 各位道友，不可取笑以下的每一個(gè)答案哦。不然，我咒你每天出門忘記拉褲鏈，和臥報(bào)主編一樣。每一個(gè)答案的背后都是一位道友的成長(zhǎng)史，有人還在煉氣期，而有人已筑基……

問(wèn)題

：

如何從“對(duì)用戶好，對(duì)敵人狠”解釋:?敵人破解公鑰對(duì)應(yīng)的私鑰時(shí)，我們要求其時(shí)間復(fù)雜度和公鑰的長(zhǎng)度呈指數(shù)級(jí)關(guān)系，而不是線性級(jí)或 多項(xiàng)式級(jí)的關(guān)系？

答案

：對(duì)用戶好：計(jì)算的方式簡(jiǎn)單（相比多項(xiàng)式），從私鑰得到公鑰只需要很小的簡(jiǎn)單的輸入（私鑰），經(jīng)過(guò)指數(shù)計(jì)算，就可以得到很大的復(fù)雜的結(jié)果（公鑰）。用戶在持有保存時(shí)開(kāi)銷少。 對(duì)敵人狠：計(jì)算困難（逆運(yùn)算），從公鑰破解獲取私鑰，是指數(shù)的逆運(yùn)算，需要大量的運(yùn)算嘗試，計(jì)算很大的復(fù)雜的數(shù)，然后才能獲得結(jié)果。敵人在持有保存時(shí)開(kāi)銷多。

答案

：在用戶的角度，為了用戶方便，產(chǎn)生私鑰的過(guò)程應(yīng)該是容易的，所花費(fèi)的時(shí)間不多，是線性或者多項(xiàng)式級(jí)別的，即對(duì)用戶好，而在敵人的角度，為了保護(hù)私鑰不會(huì)被輕易泄露，破解公鑰對(duì)應(yīng)的私鑰的過(guò)程是困難的，所花費(fèi)的時(shí)間要超過(guò)敵人所能承受的極限，是指數(shù)級(jí)別的，即對(duì)敵人狠。

答案

：呈指數(shù)級(jí)關(guān)系，意味著敵人破解私鑰的難度大，即“對(duì)敵人狠”，這樣才能保證方案的安全性

答案

： 敵人破解公鑰對(duì)應(yīng)私鑰是沒(méi)有簡(jiǎn)單解法或者不存在，但對(duì)于用戶獲得私鑰是簡(jiǎn)單的，具有單向性。

答案

：“對(duì)用戶好，對(duì)敵人狠”就是用戶可以方便地使用公鑰和私鑰進(jìn)行加解密，而敵人則需要花費(fèi)大量的時(shí)間和計(jì)算資源去攻破私鑰。因此，敵人破解公鑰對(duì)應(yīng)的私鑰時(shí)要求時(shí)間復(fù)雜度和公鑰的長(zhǎng)度呈指數(shù)級(jí)關(guān)系，而不是線性級(jí)或多項(xiàng)式級(jí)的關(guān)系。這樣的話，隨著公鑰長(zhǎng)度的增加，敵人所需的計(jì)算量就會(huì)呈現(xiàn)爆炸性地增長(zhǎng)，攻破私鑰的難度也就大幅增加。

答案

： 首先一個(gè)用戶是否惡意的判別是，這個(gè)用戶是否遵守算法規(guī)則，不遵守規(guī)則的用戶就應(yīng)定義為惡意用戶，也可直接定義為敵手，那么我們?nèi)?gòu)造一個(gè)算法的時(shí)候就應(yīng)該考慮到惡意敵手的存在，那么此算法就應(yīng)該能抵御敵手的任何形式的攻擊。 以敵手根據(jù)正常用戶的公鑰計(jì)算對(duì)應(yīng)私鑰這類攻擊為例: 首先我們要清楚，我們避免不了任何一個(gè)用戶都成為敵手的可能，因此，應(yīng)該可以說(shuō)是，對(duì)任何不懷好意的人來(lái)說(shuō)，僅僅由公鑰計(jì)算私鑰必須是困難的，這樣才能保證算法的安全性。 然后，對(duì)于敵手由公鑰計(jì)算私鑰的困難程度來(lái)說(shuō)，指數(shù)級(jí)時(shí)間復(fù)雜度是最耗時(shí)的，而除此之外的時(shí)間復(fù)雜度對(duì)敵手來(lái)說(shuō)，可以在相比較之下較短的時(shí)間內(nèi)算出私鑰。 因此，對(duì)于由公鑰推出私鑰來(lái)說(shuō)，這對(duì)用戶是友好的，因?yàn)橛脩粲凶约核借€，對(duì)敵手是提防的，提防的手段就是使敵手由公鑰計(jì)算私鑰的時(shí)間復(fù)雜度為指數(shù)級(jí)。

答案

: 對(duì)用戶好，對(duì)敵人狠，直白的理解就是，敵人很難從公鑰計(jì)算出私鑰。它的要求是：隨著公鑰長(zhǎng)度的增加，從公鑰求解出私鑰的時(shí)間復(fù)雜度是指數(shù)級(jí)的，其難度高于線性或者多項(xiàng)式。

答案

：”對(duì)用戶好“是指方案在計(jì)算、通信、存儲(chǔ)等方面的開(kāi)銷較小 ”對(duì)敵人狠“是指敵人攻破方案的難度較大，即方案的安全性較高。通常認(rèn)為敵人攻破方案的時(shí)間復(fù)雜度與公鑰的長(zhǎng)度呈指數(shù)級(jí)關(guān)系時(shí)，難度較大，而呈線性級(jí)或多項(xiàng)式級(jí)的關(guān)系時(shí)，難度較小。因此，為了保證”對(duì)敵人狠“，要求其攻破方案的時(shí)間復(fù)雜度和公鑰的長(zhǎng)度呈指數(shù)級(jí)關(guān)系

答案

：離散對(duì)數(shù)不就是這樣嗎？已知g^x，求x, 沒(méi)有辦法，只能窮舉。復(fù)雜度就是與群元素長(zhǎng)度的指數(shù)？

答案

: 沒(méi)有Google，直覺(jué)上我是這么理解的。因?yàn)槔碚撋瞎€長(zhǎng)度越長(zhǎng)越安全，但是同時(shí)帶來(lái)的問(wèn)題是，公鑰越長(zhǎng)，通信代價(jià)越高。所以我們需要增加公鑰長(zhǎng)度時(shí)，敵人破解的難度指數(shù)增加。這樣一樣，“對(duì)用戶好，對(duì)敵人狠”。

答案

：因?yàn)槿绻麛橙似平馑借€所需要的時(shí)間復(fù)雜度和公鑰的長(zhǎng)度成線性級(jí)或 多項(xiàng)式級(jí)的關(guān)系的話，那么為了保證私鑰的安全，公鑰長(zhǎng)度就要設(shè)置的特別長(zhǎng)，這樣顯然對(duì)用戶不友好。而且，我們也很難利用敵人破解私鑰來(lái)解決數(shù)學(xué)困難問(wèn)題，這也方便了敵人，對(duì)敵人“不夠狠”。 站在實(shí)際應(yīng)用的角度，公鑰的長(zhǎng)度是有限的，如果攻破私鑰的時(shí)間復(fù)雜度與公鑰長(zhǎng)度的線性或多項(xiàng)式關(guān)系，那么為了為了保證私鑰的安全，公鑰長(zhǎng)度可能就得呈指數(shù)級(jí)增長(zhǎng)，這樣顯然對(duì)用戶不友好。 站在安全歸約的角度，我們將一個(gè)密碼學(xué)方案歸約到某個(gè)問(wèn)題上，通常是為了證明破解該方案不比解決該問(wèn)題簡(jiǎn)單。而在實(shí)際的方案設(shè)計(jì)中，大多數(shù)方案都會(huì)將都會(huì)將底層困難假設(shè)嵌入在由公鑰計(jì)算私鑰中。 在歸約時(shí)，simulator希望能夠利用敵手對(duì)方案的攻擊來(lái)獲取困難問(wèn)題的解，也就是說(shuō)，simulator希望利用一個(gè)擁有無(wú)限計(jì)算力的敵手來(lái)破解一個(gè)自己無(wú)法解決的問(wèn)題。如果破解公鑰對(duì)應(yīng)的私鑰僅僅呈線性級(jí)或多項(xiàng)式級(jí)的關(guān)系的話，那么就意味著，該方案所依賴的底層困難問(wèn)題可以通過(guò)增加有限計(jì)算資源的方式讓simulator自己解決，從而浪費(fèi)了利用敵手的機(jī)會(huì)，對(duì)敵手來(lái)說(shuō)不夠狠。