中國剩余定理CRT、高斯算法和RSA低加密指數(shù)廣播攻擊

這篇討論一下中國剩余定理(Chinese Remainder Theorem),高斯算法(Gauss's algorithm)解決同步線性同余(simultaneous linear congruences)的問題拉庵、簡單的方法去解決小模數(shù)(small moduli)同余扶平、RSA低加密指數(shù)廣播攻擊的原理(theorem to break the RSA algorithm when someone sends the same encrypted message to three recipients using the same exponent of e=3塔嬉，又叫Johan Hastad廣播攻擊)

中國剩余定理 The Chinese Theorem

定理：有整數(shù) $n_1,n_2,\cdots,n_r$ ， $gcd(n_i,n_j)=1谍失，且 i\neq j$ ，那么線性同余系統(tǒng)

$x\equiv c_1 (mod \ n_1)$

$x\equiv c_2 (mod \ n_2)$

$x\equiv c_3 (mod \ n_3)$

$\cdots$

$x\equiv c_r (mod \ n_r)$

定理說有唯一解莹汤，并不是說如何去求解快鱼。這個通常使用高斯算法(Gauss's algorithm)。中國剩余定理更多的時候是用在對RSA算法進行提速纲岭。

中國剩余定理在《孫子算經(jīng)》中的問題是：今有物不知其數(shù)抹竹，三三數(shù)之剩二，五五數(shù)之剩三止潮，七七數(shù)之剩二窃判，問物幾何？在現(xiàn)代數(shù)論種我們把它寫成解同余問題喇闸。

$x \equiv 2 (mod \ 3)$

$x \equiv 3 (mod \ 5)$

$x \equiv 2 (mod \ 7)$

高斯算法 Gauss's algorithm

算法：有 $N=n_1 n_2 \cdots n_r$ 那么

$x \equiv c_1 N_1 d_1 + c_2 N_2 d_2 + \cdots + c_r N_r dr (mod \ N)$

$N_i = N/n_i 和 d_i \equiv N_i^{-1}(mod \ n_i)$

《孫子算經(jīng)》的例子

《孫子算經(jīng)》上面原始的中國剩余定理的題目有：

$n_1=3,n_2=5,n_3=7$

$N=n_1n_2n_3 = 3 \times 5 \times 7 = 105$

$c_1 = 2, c_2 = 3, c_3 = 2$

$N_1 = N/n_1 = 105 \div 3 = 35 \ 所以 d_1=35^{-1} (mod \ 3) = 2$

$N_2 = N/n_2 = 105 \div 5 = 21 \ 所以 d_2= 21……{-1}(mod \ 5) = 1$

$N_3 = N/n_3 = 105 \div 7 = 15 \ 所以 d_3= 15^{-1}(mod \ 7) = 1 \ 因此$

$x=(2 \times 35 \times 2)+(3 \times 21 \times 1)+(2 \times 15 \times 1)= 233 \equiv 23 (mod \ 105)$

低加密指數(shù)廣播攻擊RSA Johan Hastad attack

Alice發(fā)送您相同的RSA加密消息m給三個接收方袄琳，使用了不同的模數(shù) $n_1,n_2,n_3$ 询件，這些模數(shù)互質(zhì)，但是他們使用了相同的指數(shù) $e=3$ 唆樊。Eve恢復(fù)出了密文值 $c_1,c_2,c_3$ 并且知道三個接收方的公鑰 $(n, e=3)$ 宛琅。Eve是否可以在不分解模數(shù)的情況下，恢復(fù)出消息逗旁？

可以嘿辟。Eve使用高斯算法可以找到解x，在 $0 \le x \lt n_1 n_2 n_3$ 范圍內(nèi)片效，

$x \equiv c_1 (mod \ n1)$

$x \equiv c_2 (mod \ n2)$

$x \equiv c_3 (mod \ n3)$

我們知道 $m^3 \lt n_1 n_2 n_3$ 红伦，因此可以得到， $x=m^3$ , $m$ 可以通過簡單的對整數(shù) $x$ 求立方根恢復(fù)出來堤舒。

例子

有三個接收方的公鑰 $(87,3),(115,3)和(187,3)$ 色建，我們知道 $e=3$ 并且

$n_1=29 \times 3 = 87, n_2=23 \times 5= 115, n_3=17*11=187$
（實際使用中，會使用更大的N舌缤，不可以分解）

Alice使用RSA算法加密消息 $m=10$ 給三個接收方箕戳，如下：

$c_1=10^3 mod \ 87 = 43;c_2=10^3 mod \ 115=80;c_3= 10^3 mod \ 187=65$

這三個密文值 $c_1,c_2,c_3$ 被中間人Eve攔截，Eve知道公鑰 $(n_i, e)$ 国撵。她可以使用高斯算法如下：

$N=n_1 n_2 n_3 = 87 \times 115 \times 187 = 1870935$

$N_1 = N/n_1 = 115 \times 187 = 21505; d_1= 20505^{-1}(mod \ 87) = 49$

$N_2 = N/n_2 = 87 \times 187 = 16269; d_2 = 16269^{-1} (mod \ 115)=49$

$N_3 = N/n_3 = 87 \times 115 = 10005; d_3 = 10005^{-1}(mod \ 187) = 2$

$x \equiv c_1 N_1 d_1 + c_2 N_2 d_2 +c_3 N_3 d_3 (mod N)$

$x = (43 \times 21505 \times 49) + (80 \times 16269 \times 49) + (65 \times 10005 \times 2) = 110386165 \equiv 1000 (mod \ 1870935)$

所以明文消息 $m$ 是1000的立方根陵吸， $m=10$ 。所以Eve不需要對模數(shù)進行分解就可以恢復(fù)出明文消息介牙。

如何防止以上的攻擊

1. 使用大指數(shù)壮虫，比如65537(0x10001)。這樣使用上面的攻擊方法將會變得很困難环础。
1. 添加一些隨機比特到消息中囚似，至少64比特。確保每次消息加密都添加了不同的隨機數(shù)线得。這種加鹽的方法也可以防止許多其他的攻擊饶唤。顯然，接收方也需要知道如何在解密后去除填充的隨機數(shù)贯钩。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末募狂，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子角雷，更是在濱河造成了極大的恐慌祸穷，老刑警劉巖，帶你破解...
沈念sama閱讀 222,183評論 6贊 516
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件勺三，死亡現(xiàn)場離奇詭異雷滚，居然都是意外死亡，警方通過查閱死者的電腦和手機吗坚，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 94,850評論 3贊 399
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門揭措，熙熙樓的掌柜王于貴愁眉苦臉地迎上來胯舷，“玉大人，你說我怎么就攤上這事绊含∩Ｋ唬” “怎么了？”我有些...
開封第一講書人閱讀 168,766評論 0贊 361
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵躬充，是天一觀的道長逃顶。經(jīng)常有香客問我，道長充甚，這世上最難降的妖魔是什么以政？我笑而不...
開封第一講書人閱讀 59,854評論 1贊 299
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮伴找，結(jié)果婚禮上盈蛮，老公的妹妹穿的比我還像新娘。我一直安慰自己技矮，他們只是感情好抖誉，可當(dāng)我...
茶點故事閱讀 68,871評論 6贊 398
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著衰倦，像睡著了一般袒炉。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上樊零，一...
開封第一講書人閱讀 52,457評論 1贊 311
城市分裂傳說
那天我磁，我揣著相機與錄音，去河邊找鬼驻襟。笑死夺艰，一個胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的沉衣。我是一名探鬼主播郁副，決...
沈念sama閱讀 40,999評論 3贊 422
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼厢蒜！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起烹植，我...
開封第一講書人閱讀 39,914評論 0贊 277
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤斑鸦，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后草雕，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體巷屿，經(jīng)...
沈念sama閱讀 46,465評論 1贊 319
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 38,543評論 3贊 342
?白月光啟示錄
正文我和宋清朗相戀三年墩虹，在試婚紗的時候發(fā)現(xiàn)自己被綠了嘱巾。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片憨琳。...
茶點故事閱讀 40,675評論 1贊 353
活死人
序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖旬昭，靈堂內(nèi)的尸體忽然破棺而出篙螟，到底是詐尸還是另有隱情，我是刑警寧澤问拘，帶...
沈念sama閱讀 36,354評論 5贊 351
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布遍略，位于F島的核電站，受9級特大地震影響骤坐，放射性物質(zhì)發(fā)生泄漏绪杏。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點故事閱讀 42,029評論 3贊 335
男人毒藥：我在死后第九天來索命
文/蒙蒙一纽绍、第九天我趴在偏房一處隱蔽的房頂上張望蕾久。院中可真熱鬧，春花似錦拌夏、人聲如沸僧著。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,514評論 0贊 25
一樁弒父案辖佣，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽霹抛。三九已至，卻和暖如春卷谈，著一層夾襖步出監(jiān)牢的瞬間杯拐，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 33,616評論 1贊 274
情欲美人皮
我被黑心中介騙來泰國打工世蔗，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留端逼，地道東北人。一個月前我還...
沈念sama閱讀 49,091評論 3贊 378
代替公主和親
正文我出身青樓污淋，卻偏偏與公主長得像顶滩，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子寸爆，可洞房花燭夜當(dāng)晚...
茶點故事閱讀 45,685評論 2贊 360