【philippica】萌萌噠弱受RSA和強攻wiener

01-25

RSA作為一種吃瓜群眾最為耳熟能詳的公鑰加密演算法，其本身的思想以及構造方法也是非常簡單的。我將嘗試著盡量用通俗易懂的語言來描述這件本來就很簡單的事。

什麼時候需要公鑰加密？想像這樣一個場景，一堆情侶，每天早上alice站在東邊的山頭，bob找在西邊的山頭，隔著大山用擴音喇叭說著羞羞臉的情話。這時候兩座山之間的山谷中總會坐著一個吃瓜群眾philippica,聽著兩個人的小秘密。alice和bob當然不喜歡被他聽到他們的情話，於是機智的alice就大聲的說:"bob,以後每次說話我們都把說的字母按著字母表順序往後數8個字母，也就是用凱撒密碼移動8位，這樣philippica就不知道我們在說什麼了！"

接著bob想說：「I love u」,他按著字母表abcd的順序把字母移動了8位，變成了q twdm c，然後他大聲地喊出了這些字母，只見alice拿出小本將凱撒密碼解開後熱淚迎眶，一對情侶淚眼朦朧，在看山谷里的吃瓜八卦者philippica,它也聽到了alice說凱撒密碼移動8位，於是他放下西瓜，也拿出了筆記本算了一下，然後露出了意味深長的笑容，接著繼續吃瓜。

「這根本不起任何作用，我們說的任何加密方式philippica也會聽到，他只要用聽到的密鑰解開我們的密碼，那我們做啥都是徒勞的。」bob絕望的說。

alice說：「沒關係，我們有rsa，現在我告訴你一組公鑰(3233, 17) 你現在腦子裡想一個0～25的數字作為凱撒密碼的移動位數，假設這個數字是m，那麼你現在把 $m_{}^{17}$ Mod 3233這個結果告訴我。」

bob覺得現在的alice很6,所以他選擇移動位數為6,他會快速冪的方法，所以很快就把6^17 mod 3233的結果算了出來結果是824,他大聲喊出了這個數字。

alice聽到後很開心，她這裡有一組私鑰：（3233,2753），她用類似的方法計算824^2753 mod 3233,結果發現是6！於是她很開心的和bob用密鑰是6的凱撒說情話了。

再看pilippica這邊，他也知道rsa密碼的流程,也聽到了兩人報的數字，他知道Bob想了一個數字m，並且m^17 mod 3233 = 824，可他沒有高效的方法去解這個方程，只能看著alice和Bob媚眼傳情，共訴情話而自己在一邊鬱悶的吃瓜了。

因此rsa的本質就是找這麼三個數，(e, d, n)使得對於任意的數字（在這裡是指明文）m，(m^e)^d mod n = m,接著把(e, n)公開作為公鑰，自己留著d，別人把要加密的數自乘e次後mod n，告訴自己，自己只要把發來的結果再自乘d次mod n就是原來的明文了。

---------------------------------------------以下內容需要一些數論基礎-------------------------------

那如何找這個三個數呢，rsa給出了很簡介的步驟，首先現要找到兩個超大的素數p,q。這裡p,q如此之大以至於即使線性的歐拉篩也肯定篩個十天半個月才能找到了，所以一般的方法是隨機生成一段超大區間的奇數（為啥是奇數？因為大於2的偶數絕對不可能是素數），然後挨個檢測每個奇數是否是素數，判素數通常用米勒羅賓等演算法，全都不是素數就重新生成一段區間，事實上rsa演算法最消耗時間的就是找素數這個環節了。

找到兩個素數p,q後把它們相乘，就是三元組(e,d,n)中的n了，也就是n = q * p;接著計算n的歐拉函數φ(n),我們知道φ(n)的含義是小於n中與n互質的數的個數，並且對於n = q * p, 它的歐拉函數的值就是(p - 1) * (q - 1),所以接下來e的選取就是1到(p - 1) * (q - 1)中和(p - 1) * (q - 1)互質的數中的任何一個，而e隨便選了，d也就定下來了，是e在mod φ(n)下的逆元，換句話說，e * d mod φ(n) = 1,利用擴展歐幾里德演算法，我們可以很容易的求出d，這樣我們就輕鬆的把e , d , n求了出來。

簡單的證明一下這樣選取的(e,d,n)對於任何m,滿足(m^e)^d mod n = m吧：

因為 e * d mod φ(n) = 1

即存在整數c使得e * d = φ(n) * c + 1

那麼 $(m^{e}) ^{d}equiv m^{ed}equiv m^{phi (n) * c + 1}equiv m * (m^{phi (n)})^{c}$ MOD n

那麼由歐拉定理很快就能得到右邊的這坨等於1

即 $(m^{e}) ^{d}equiv m$ MOD n

QED

---------------------------------------------以上內容需要一些數論基礎-------------------------------

rsa思想很簡單,它的安全性在於對於大整數分解的困難（當然，rsa的安全性略小於它），想要直接暴力破解rsa或許等到量子計算機的出現可以解決(shor演算法)，但是如果你參數選擇的不對，豬隊友神仙都保不住你，在上文中我們知道，我們要在1～φ(n)中隨便找個和φ(n)互素的數，如果這個數選的不當，那麼這個rsa的安全性很有可能沒你想像的那麼安全，wiener發現了，如果d非常小的時候，在小於n^(1/4)/3時，wiener攻擊能夠奏效！

在說wiener"s attack之前，先介紹下連分數，對於任意一個數都能展開成連分數，

如果你嘗試做一遍你會發現，在你對一個分數展開成連分數的時候，事實上就是在對分子分母不斷做輾轉相除法，因此你很快得出一個結論：對於任意有理數(兩個整數的比)的連分數永遠是有限的。這很簡單，對於兩個數輾轉相除，最終會停在兩個數的最大公約數上，對於無理數也能連分數展開，例如著名的無理數π，e，無理數連分數展開是無限的。

對於連分數，我們觀察每一個分母，它後面加的那一項都小於1,所以相比ai是一個非常小的數，如果我們把第i個分母后面的分數全部略去，我們稱這個分數為這個連分數第i個漸進分數，顯然i越大離x越接近，並且由於約去了分母前n-1個漸進分數都是小於x的。比如祖沖之發現圓周率的疏率和密率22 / 7與355 / 113 就是π連分數展開的兩個漸進分數。

介紹完連分數，我們回來看RSA，首先N = pq; φ(n) = pq - (p + q) + 1 = N - (p + q) + 1

可以發現由於p,q非常大，pq是遠大於p+q的，因此φ(n)約等於N

上面我們知道e d對於φ(n)互為逆元，因此我們可以列出式子:ed-1=k*φ(n)

這個式子非常重要我們將它變個型，兩邊同除以d*φ(n)可以得到：

$frac{e}{phi (n)} -frac{k}{d} =frac{1}{dphi (n)}$

由於φ(n)約等於N，上式我們可以寫成 $frac{e}{N} -frac{k}{d} =frac{1}{dphi (n)}$

顯然d*φ(n)是一個很大的數，因此可以說e/N 略大於k/d

為啥要這麼寫呢，因為e和N是我們是知道的，公鑰中給我們的，所以我們計算出e/N後，比它略小的k/d怎麼出來呢，計算e/N的連分數展開，依次算出這個分數每一個漸進分數，由於e/N 略大於k/d，wiener證明了，該攻擊能精確的覆蓋k/d

我們來舉個例子，現在有一個rsa, e = 42667, N = 64741,我們來求。第一步，我們把分數e/N連分數展開，以此求出每一個漸進分數：0，1, 1/2, 2/3 ....

我們用1/2舉例子，現在我們說，k/d=1/2非常可能成立，假設它成立，我們把k=1,d=2代入上面的ed-1=k*φ(n)中（為何原來比值相等的可以直接把分子分母分別帶進去？想一想為什麼），顯然e,d,k都有了，φ(n)也就有了，我們知道φ(n)有啥用呢？我們知道 φ(n) = pq - (p + q) + 1 = N - (p + q) + 1，N = pq作為公鑰我們是知道的，所以知道了φ(n) 我們只要算出N- φ(n)+1就是(p + q)的值，好回到初三，現在知道了pq,和p+q的值，我們如何快速求出p和q的值呢？很簡單，利用偉大定理，我們可以輕鬆構造出方程x^2 - (p + q)*x + pq = 0,這個方程的兩個根就是我們要求的p,q,至此rsa中所有的參數都被我們求了出來，讓我們乾杯！

順手把wiener attack的演算法寫了一遍

import math# Return the continued fractions expansions of x / ydef continuedFraction(x, y): ret = [] while y: ret.append(x / y) x, y = y, x % y return retdef expand(ctnf): _ctnf = ctnf _ctnf.reverse() numerator = 0 denominator = 1 for x in _ctnf: numerator, denominator = denominator, x * denominator + numerator return (numerator, denominator) # Return the list of n progressive fraction def progressiveFraction(x, y): cfe = continuedFraction(x, y) cfeL = len(cfe) ret = [] for i in xrange(1, cfeL): ret.append(expand(cfe[0 : i])) return ret # Solve the equation: ax^2 +bx + c = 0def solve(a, b, c): par = math.sqrt(b * b - 4 * a * c) return (-b + par) / (2 * a), (-b - par) / (2 * a)def wienerAttack(e, n): res = progressiveFraction(e, n) for (d, k) in res: if k == 0 : continue if (e * d - 1) % k != 0:continue phi = (e * d - 1) / k p, q = solve(1, n - phi + 1, n) if p * q == n: print "find it" returnwienerAttack(17993, 90581)

reference：

https://en.wikipedia.org/wiki/RSA_(cryptosystem)