從自然數開始,一直講明白了RSA 非對稱式加密的細節。
前不久Jason 同學邀請複旦大學數學系的梅同學給希望了解Web3 的朋友們上了5 節硬核的數學課。從自然數開始,一直講明白了RSA 非對稱式加密的細節。我再回顧一下,嘗試解釋這個其實還挺複雜的事兒。
(前方數學預警,但是我保證努力限制在小學數學知識範圍以內)
大數無法分解
3 * 7 算出21 容易嗎?容易。反過來,21 是哪兩個數的乘積?也不難,但肯定比算3 * 7 麻煩。
同理967 * 379 = 366493 容易。反過來,366493 是哪兩個數乘積?難多了。
隨著乘積的不斷變大,算乘法的難度略微增大,算是這個數是由哪兩個數相乘的難度陡峭的增加。
一個一百位數字的數和一百位數字的數相乘,手工算不容易,但對計算機來說不難,結果是一個大約兩百位數字的數字。
反過來,把這個200 位的數字分解?基本上現在能想到的辦法就是近似於一個一個的試。別說算乘法了,光從一數到80 位的數字,按照現在的計算水平,就要消耗掉一個中等恆星幣一生的能量了。所以,簡單結論是,超級大的數字做分解不可能。
就利用這個簡單的原理,加上聽起來故弄玄虛的歐拉定理,就是一個精妙絕倫的RSA 加密貨幣算法。
n 進制取個位
這個東西的數學名稱叫「取模」,就是算「一個數除以n 以後的餘數是幾」。
不過我們不用這個名字。我自己發明的一個混雜了數學和計算機的概念,叫做n 進制取個位。比如n = 8,八進制下只取個位,超過的十、百、千位數就直接扔掉,那麼15 這個數本來八進制就是17,只取個位,就是7。所以,我們規定,15 在八進制個位模式下,就等於7。同樣,23,31 等,在8 進制取個位下,都等於7。這個「等於」,不是絕對數字的相等,而是經過了n 進制取個位,我們用≡表示這種特殊的等於(正規說法叫做「模n 同餘」,可以忽略)。
這樣,如果n 是4 萬公里的話,數字的世界變成像地球一樣,是一個循環。在赤道上可以向東走1 萬公里,和向西走3 萬公里結果是一樣的,甚至向西走7 萬,11 萬,15 萬公里的終點是一樣的,就是一圈一圈的轉就是了。所以4 萬進制取個位, 1 萬≡-7 萬≡ -11 萬≡ -15 萬。注意,畢竟走7 萬公里和走11 萬公里不相等( =),但是在地球赤道上走,他們的效果相等(≡)。
例子:比如在20進制取個位下,3 * 7的結果就是1(本來是21,結果走過頭了, 又繞回來,回到了1 )。
連著乘兩個數就是它本身
這有啥用呢?神奇的事情在於,在20 進制取個位下,任何數乘以3 再乘以7,就相當於乘以1,就是這個數本身
比如12 * 3= 36 ;36 % 20 =16;16 * 7= 112; 112 % 20 =12
變回原來了。神奇嗎?
在20 進制取個位下,你把一個數乘以3,我不用除以3,而是繼續乘以7 ,就是原來那個數。不僅僅是7,我把乘3 的數字乘以67,127,或者187。 。 。 。它都會回到原來那個數,只是轉的圈數多了些。
這就使得,如果兩個數在一個n 進制取個位下乘積為1,這兩個數不就是一個很好的加密和解密的工具嗎?
比如數字大一點,在366492 進制取個位下,任何數乘以967 得到的數再乘以379,就是它本身。
公鑰和密鑰
如果我把e = 967當做公鑰,d = 379當做密鑰,我只需要告訴別人(e = 967,n = 366492)這兩個數字,別人乘積以後交給我,我再乘以d ,然後。 。 。 。
不過有一個小問題,如果給出了(e =967, n = 366492)這兩個數,別人除以e 不就得到了我的秘鑰d 嗎?畢竟,你可以算乘法,別人就可以算除法,而且難度差不多。我們把這個辦法成為露餡兒加密貨幣法。
接下來要做的事情,就是想辦法把這自己的密鑰藏起來,讓別人拿到n 進制數,還有公鑰e,沒有辦法算出我的密鑰,但是依然可以用e 加密貨幣,我可以用私鑰d 解密不就好了?
歐拉定理
我們引入φ(n) 。它的定義可厲害了,是「小於n的正整數中和n互質的數的個數」。這個定義忽略就好,只要知道,如果n 是兩個素數p, q 的乘積的話,φ(n) = (p-1)(q-1)。
歐拉發現了一個驚天大秘密,居然在n 進制取個位下,如果m 和n 互為質數,m 的φ(n) 次方居然等於1:
m ^φ(n)≡1
兩邊都取k 次方:
m ^(k *φ(n))≡1
兩邊都乘以m :
m ^(k *φ(n) + 1)≡m
k *φ(n) + 1是啥意思?就是這是一個「除以φ(n) 餘數為1 」的數字。也就是說,只要找到e*d 這兩個數,使得他們的乘積除以φ(n)餘數為1 就好。這個好找,有一個叫做輾轉相除法的方法,不過這裡先略過。我們一般常常把e 固定的設為65537,然後就可以找到一個滿足的d。
最後,也就是最驚豔的一步,如果我們能夠找到這樣的e, d,我們把e和n告訴整個世界,讓他們在n 進制取個位下,把要加密的數字m取e次方發給我,我對這個數再進行d 次方,我就能得到m。
(m^ e) ^d≡m
重新梳理
到現在大家應該已經無一例外的暈厥了。這很正常。我們再理一下就清楚了。
就是說,如果我能無論用什麼方法,找到一個進制n,在這個n 進制取個位下,能夠找到兩個數字e 和d,e 公開給整個世界,d 留給自己,同時還能讓任何數字m 的e 次方的d 次方還等於原來這個m,加密貨幣解密算法不就成立了嗎?就跟最早我說的那個乘以一個數,再乘以另一個數,總等於原來的數字一樣?
但露餡兒加密貨幣法兩個乘法的算法的明顯的漏洞在於,e 和n 給出了,d 也就給出了。
在這個新的算法中,e 給出了。 n 給出了,但e * d≡1 的進制,不是簡單地n,而是和n 同源,但是不同的φ(n)。正因為進制改了,所以也不能用露餡兒加密貨幣法裡面的兩次乘法,而藉用歐拉的驚天發現,做了兩次冪運算。
從n能不能算出來φ(n)呢?如果有能力分解n 當然φ(n)唾手可得,把兩個因子各自減一再乘起來就好。
但是從n 能不能輕易地找到p 和q 呢?根據最早的大數不可分解,要想找到100 個太陽燒掉都不夠用,p 和q 好像是腳手架,算出來n,算出來φ(n) 就扔掉了。那麼φ(n)就是一個秘密。如果φ(n)是個秘密,有了e 也找不到d。
所以,整個算法是無比精巧的安全。
舉例子
我們找兩個腳手架數字:p = 2, q = 7,算出n = 2 * 7 =14,φ(n)=(2 – 1) * (7 – 1) =6。那兩個腳手架數字p, q 在算出n 和φ(n) 後就退休了。找在6 進制取個位下,e * d≡1 好辦,e = 5, d = 11 就行( 5 * 11 = 55 =6* 9 + 1≡1)。
這樣,公佈給全世界的數字就是(e = 5, n = 14),保留給自己的就是d = 11。 φ(n) 千萬也不能告訴任何人。 φ(n)就如同總統,n 如同他的影子。世界只能看到他的影子,看不到總統本人。好在影子在世間行走不怕暗殺,總統躲在防空洞裡是安全的。
我們來試一下,在14進制個位模式下,如果要傳遞的數字m =2,別人把m ^ e 算出來,就是2 ^5 =32= 2 *14+ 4≡4
現在,4 就可以大大咧咧的在互聯網上隨便傳輸了。只有我知道有一個秘密是11 。我拿到以後,算4 的11 次方,4 ^ 11≡4,194,304 % 14≡2,不就是別人要給我的那個數字嗎?前提是,我們認為別人從n = 14 無法分解成2 * 7,否則就全露餡了。
14 肉眼可以看出等於2 * 7。
這個數n:
8244510028552846134424811607219563842568185165403993284663167926323062664016599954791570992777758342053528270976182274842613932440401371500161580348160559
是 p
91119631364788082429447973540947485602743197897334544190979096251936625222447
乘以 q
90480063462359689383464046547151387793654963394705182576062449707683914045697
計算機眼也看不出來。 p 和q 如同兩位門神,死死的守住了獲取它們後面的秘密的入口。但是從p,q 算出φ(n),以及e,d,卻都是舉手之勞。
如果知道n 的組成是p,q,我們按照上面的算法可以選出來e 和d:
65537
2545549238258797954286678713888152865623498585866759298032549597771444725977268190722532488574321463855938811396613702406984581214587037347197409962813953
也就是說,這個遊戲,任何人要把一個數字m 傳給我,只需要在n 進制取個位下,對它進行65537 次冪(m ^ 65537),我再把它進行d 次冪,我就拿回了原來的數字。
這個精巧的算法,就是RSA 加密貨幣算法。
希望有人能夠看明白。我真的是盡力了。
原文標題:《用吃奶的勁試著解釋加密貨幣算法的數學原理》
撰文:王建碩
來源:ForesightNews
資訊來源:由0x資訊採集自互聯網。版權歸作者“ForesightNews”所有,未經許可,不得轉載