創作內容

18 GP

機密注意!伍德的密碼學時間 (2)

作者:伍德‧瓦懷特│2020-06-14 15:25:14│巴幣:134│人氣:438
  上期的伍德說數裡,我們帶大家簡單地理解密碼學究竟是什麼:只要你瀏覽網路,需要傳輸資料,就絕對逃不開密碼學。而將資料轉化為數字,而後傳輸加密的方式,可以大致分為對稱式加密非對稱式加密。兩者各有優缺點,要是需要複習的讀者可以直接參考上一篇

  本期我們要帶大家來看非對稱式加密中目前最受歡迎的模式之一:RSA加密法。真要說起來,其所使用的數學僅僅國中程度(當然,可以使用更難的定理簡化計算),目前在網路上相當普遍。此外,我們還會帶大家來看非對稱式加密中,如何解決「確認作者」的問題。簡而言之,當收到訊息時,我們要怎麼驗證此訊息沒有經過偽造:使用數位簽章(Digital Signature)讓寄件人簽名負責。

一、預備知識:關於模(Mod)
  在等等要提到的RSA加密法中,我們要使用一個簡單的數學觀念:(Mod)。不需要因為沒聽過就嚇到,它只是將我們從小學就學過的除法用另一種模式寫出來而已。所謂的模,簡而言之就是取餘數。在日常生活中我們很常只在意餘數,像是只在意過了幾天後是星期幾,就是只在意除以7的餘數。

  舉例來說,8、15、22除以7後都餘1,我們利用模的符號可以將其寫成:8 (mod 7)=15 (mod 7)=22 (mod 7)=1 (mod 7)。就這麼簡單。同理,4 (mod 3)=16 (mod 3)。

  這裡值得一提的是所謂「費馬小定理」。費馬(Fermat)是17世紀的數學家(雖然本業是律師),最為人所知的是「費馬最後定理(費馬大定理)」,要和ACG扯上關係的話,在《魔法少年賈修》裡被引用過。關於費馬大定理從提出到證明的數世紀歷史,基本上是可以出成一套書的,伍德在這裡不多提。它之所以傳奇是因為費馬當初在手稿中寫了一句「我想到一個絕妙的證明,但是因為這裡空白不夠,我沒地方寫。」結果所謂的絕妙證明拖到了1992年(很近,各位的父母應該都出生了)懷爾斯(Wiles)才完成,還使用了不少當初費馬時代根本沒有的觀念。

  扯遠了,我們給出費馬小定理:給定任何質數p,則對任何整數a,a^p (mod p)=a。其中a^p代表a的p次方。
  其中,要是a和p互質(最大公因數為1),我們可以改寫成a^(p-1) (mod p)=1。(粗略地看成兩篇同除a)

  這相當大程度地簡化計算。舉例來說,我們想算3^100 (mod 7)。因為7和3互質,我們從費馬小定理知道3^6 (mod 7)=1 (mod 7)。
  因此,3^100 (mod 7) = 3^6 * 3^6 * ... * 3^6 * 3^4 (mod 7) = 1*1*1...*81(mod 7)=4 (mod 7)。我們不需要把100次方真的算出來。

二、RSA加密法
  RSA加密法是由三位教授Ron Rivest、Adi Shamir、Leonard Adleman在1977年共同提出,是現今最常用的非對稱式加密系統之一。簡而言之,其所使用的概念是「將數字乘起來很簡單,但將數字質因數分解(運算)很難」。

  為了方便讀者,伍德把上次寫的非對稱式加密運作模式複製貼上。
  Alice和Bob各自有兩把鑰匙(總共4把;但等等我們會看到,只有兩把會用到)。其中一把用來上鎖所有人(包含偷聽的Eve)都知道,稱作公鑰(Public Key)。另一把用來解鎖,只有各自的主人知道,稱為私鑰(Private Key)。假設Alice想傳訊息給Bob,操作流程如下:
  (1) Alice取得Bob的公鑰,寫好訊息後使用Bob的公鑰加密,得到密文。(你也能想成使用Bob專用的鎖頭上鎖)
  (2) Bob取得密文,使用Bob的私鑰解密,得到原先訊息(明文)。(使用Bob的專用鑰匙開鎖)

  所以這裡的問題是,如何產生公鑰和私鑰。RSA是這麼做的。

  (1) 挑選兩個很大的質數:p、q。並且算出N=pq。
  (2) 計算r = (p-1)(q-1)。
  (3) 挑選e和d使得 ed (mod r)=1 (mod r)。
  (4) 將(N,e)當成公鑰送出、(N,d)當成私鑰保留

  實際上加解密的時候是這樣:假設Alice想傳遞訊息x給Bob。
  (1) Alice計算m (mod N) = x^e (mod N)
  (注意N、e是公鑰,大家都知道)
  (2) Bob得到m,計算 m^d (mod N)=x (mod N)
  (注意d是私鑰,只有收件者Bob自己知道)
  這裡使用了x^ed (mod N)=x。這是費馬小定理的推廣型(因為N不是質數,這裡伍德不細談)。

  那麼RSA安全在哪裡呢?要是Eve偷聽到m怎麼辦?答案很簡單:就讓Eve聽,反正她不知道怎麼把x給算出來
  Eve要是想算出x,只需要再知道d。而算出d目前所知最簡單的方式,是把r給算出來,透過 ed (mod r)=1 (mod r) 來解出d(注意e是公開的)。但是想把r=(p-1)(q-1)算出來,就必須要解出N=pq的p、q是誰。概念上很簡單,但實際上很難算出來。RSA就是透過算不出來,進而保障了資訊傳遞的安全性
  順帶一提,產生質數、驗證質數並不是那麼簡單的事情(這又能寫一期)。在運算法還沒成熟時,傳輸常常會卡住:那是因為系統正在產生p、q兩個質數。
  由於RSA在生活上應用太多了,不論是黑帽或白帽,自然會有想破解它的駭客。從數學家的角度來說,RSA難以破解,反映的是我們對質數仍然知之甚少。也因此,數論上每有對質數研究的突破,也算是對RSA的一次攻擊和反詰。

三、數位簽章(Digital Signature)
  本節我們要談的是這個問題:「我收到訊息了,但我怎麼知道訊息沒有被變造?
  因為公鑰為眾人所知,所有人想傳訊息給Bob時,都只需要使用Bob的公鑰。問題是,伍德也可以傳訊息給Bob,然後說自己是Alice。也就是說,Bob無法分辨寄件者是誰

  解決這個問題的方式意外地單純。前面我們說過用公鑰加密,用私鑰解密,但從數學來說是可以反過來的。我們可以如下操作:
  (1) Alice除了用Bob的公鑰加密訊息(訊息1),另外用Alice自己的私鑰加密訊息(訊息2)。
  (2) Bob收到訊息後,用Bob的私鑰解密訊息1,另外用Alice的公鑰解密訊息2。兩者一樣就表示訊息沒有被變造。
  沒錯,就這麼簡單。因為Alice的私鑰只有Alice自己知道,中間攻擊的Eve沒辦法做出訊息2。這種做法就像是Alice用自己的私鑰簽名負責一樣,專業術語稱為數位簽章(Digital Signature)。

  這裡有個實務操作上的小問題。我們傳輸了訊息1和訊息2,量是原先的兩倍。訊息少就算了,量要是大起來就很麻煩。實務上,訊息2是這麼做出來的:
  (1) 使用大家約定俗成的雜湊函數(Hash Function),將訊息的長度壓縮。常見的有SHA-1
  (順帶一提,伍德的密碼學老師曾經半開玩笑地說Hash Function應該翻譯為雜碎函數...)
  (2) 用Alice的私鑰加密壓縮後的訊息,把這當作訊息2寄出。
  (3) Bob解出訊息1後,使用同樣的雜湊函數壓縮訊息,再比對用Alice公鑰解出的訊息2。兩者應該都要是原始訊息經過雜湊函數壓縮的結果。要是一樣就沒事了。
  這裡又延伸出一個問題:我們比對的是壓縮的結果,而不是原始訊息。所以雜湊函數最重要的特性是A(原始)和B(變造)兩個訊息應該要壓縮出不同,甚至是差很多的結果

  本段懶人包:透過數位簽章,我們能解決確認寄件者的問題,或甚至是確保訊息沒被偽造

四、中間人攻擊和SSL憑證
  上一節談的是收件者擔心收到的文件是否被變造。本節我們要談反過來的問題:「Alice在寄件前必須要取得Bob的公鑰──那真的是Bob的公鑰嗎?」

  這裡延伸出一種攻擊技術:中間人攻擊(Man-in-the-middle Attack),操作法如下:
  (1) Alice想傳訊息給Bob,請Bob寄公鑰過來。中間人Eve發現這件事情。
  (2) Eve把自己的公鑰發給Alice。不知情的Alice將訊息加密後發出。
  (3) Eve用自己的私鑰解密,看到Alice的訊息
  (4) 事實上,Eve還可以在同一時間跟Bob要公鑰(注意,這時候還沒有訊息傳遞,沒有數位簽章)。將變造後的訊息傳給Bob。
  換句話說,雙方看到的訊息都經過中間人Eve之手。被看光也就算了,還有被變造的可能性。

  問題的癥結點在於Alice不能確定收到的公鑰真的是Bob的公鑰。常見的解決方式是所謂SSL協定。簡而言之,就是透過公正第三方保證安全。各位現在都是用https(看一下你的網址)連上巴哈姆特,這就代表連線是安全的。而在網址前的鎖頭(Chrome和Edge都有)也代表傳輸安全受公正第三方保障。如果你點開詳細資料,也能看到我們先前提到的SHA和公鑰等訊息。

五、結論
  本次我們談了非對稱式加密最重要的例子:RSA加密法,並談了可能的攻擊及解決方法。其中之一是不能確認寄件者,我們使用數位簽章解決。另一方面,我們透過SSL協定保障傳輸公鑰的正確性

  各位看到一半可能會認為傳輸資訊問題還真多。事實上確實是如此,想看秘密的人和看秘密的方法真的很多,也代表網路傳輸訊息危機四伏。即使伍德說得問題好像都有對策,實際上不見得如此,各位傳輸資料的時候還是不可不慎

  要是覺得本次內容有點複雜,也不用太氣餒。伍德第一次學的時候也不是很懂到底發生什麼事,反而是這次寫文章整理時,才比較懂背後的邏輯。要是各位多看幾次,能搞清楚一些密碼學的基礎知識的話,那伍德就太榮幸了。

  那麼我是伍德‧瓦懷特,我們下期伍德說數再見!
引用網址:https://home.gamer.com.tw/TrackBack.php?sn=4816203
All rights reserved. 版權所有,保留一切權利

相關創作

同標籤作品搜尋:伍德說數

留言共 5 篇留言

方天
謝謝老師,敬禮,下課!

06-14 15:50

伍德‧瓦懷特
叫我老師,那下禮拜要考試喔,記得回去複習(並沒有)
...現在學校還有在喊口令嗎(06-14 15:58
碧戥
看到這個我想起了資訊安全被當的那一年[e3]

06-14 15:51

伍德‧瓦懷特
在結論也有提到,我大一第一次學(選修課)的時候也不是很懂怎麼回事,真的是多看幾次及趁這次寫文章才理清邏輯。
不過數學系嘛,到最後考試還是偏重會算會證明用到的數學和演算法內容,倒是沒考太多實作的問題XD06-14 16:00
方天
我們矮人族還有喊口令,我們最尊師重道了,只是每次敬禮頭都會撞到桌子!

06-14 16:00

伍德‧瓦懷特
那是桌子設計不良的問題吧啊啊啊(欸)06-14 16:03
Norman
數論...

06-14 20:06

伍德‧瓦懷特
雖然RSA表面是數論,背後的費馬小定理等原理用抽象代數的群論解釋可能更方便直接。06-15 02:54
Jack
之前讀了一本書 碼書,有提到量子密碼學,利用量子力學特性傳遞鑰匙,由於量子隨機特性,監聽者也很難得到完整鑰匙資訊,監聽過程也會改變量子狀態導致事跡敗露,靠物理特性而不是計算困難來保護隱私。總之蠻推薦看這本書~

09-19 18:12

伍德‧瓦懷特
我學密碼學也是2013的事情(時間過好快...),那時量子密碼的技術不知道如何,現在應該建立起來了。
常覺得密碼學其實就是矛和盾的競賽,在攻擊和守備中持續發展呢。09-20 03:00
我要留言提醒:您尚未登入,請先登入再留言

18喜歡★e12344888 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:[達人專欄] 魔都妖探 ... 後一篇:[達人專欄] Math ...

追蹤私訊切換新版閱覽

作品資料夾

UFO012345678正在生活中掙扎的你
加油吧!!看更多我要大聲說59分前


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】