密碼學

資訊學院的30堂課-密碼學

發行量超過一千六百萬張、號稱「絕對不可能被破解」的台北悠遊卡，不敗神話破滅！
前一陣子悠遊卡被破解的新聞，大家應該都還有印象吧。crypto1是悠遊卡所使用的加
密演算法則，居然在維基百科就有連結，而且開宗明義說，幾乎是沒有保護狀態。原來
讀取我們的悠遊卡，跟讀取我們數位相機拍出來的照片，保護等級一個是沒有保護狀
態，一個是幾乎是完全沒有保護狀態("the security of this cipher is ... close
to zero")。到底crypto1演算法哪裡錯了？或者我們教的密碼學哪裡錯了？
其實google的PageRank並無法去篩選文章的正確性，常見google把錯誤的文章放在搜尋
的第一位，比如: 你用RSA去咕台灣網頁的第一頁，他是一篇錯誤很多的文章，繁體中
文第一個連結，http://www.mathland.idv.tw/life/rsa576.htm，雖然RSA的演算法難
度基於質因數分解，但跟網站說的完全不同，RSA其中一支public key開宗明義說了由
兩個質數相乘而成,所以不是質數!!!

The RSA algorithm works as follows: take two large primes, p and q, and
compute their product
n = pq; n is called the modulus

不過這個網頁高懸在google search繁體中文第一位超過一年。RSA相關的連結很多，而
且這是屬於數論與演算法的範疇，我就曾經在演算法這門課Implement過RSA的
Project，只是，寫過的人都知道，實作一個基本的RSA加解密並不難，難的是如何使用
長整數，程式語言32位元長的整數或者64位元的整數都不足以提供足夠的保護，我當時
還很笨的去Implement超長整數的四則運算，很顯然的我的程式有bug，而且沒有適當處
理逸位問題，經過時空的演進，現在要在常見的軟體平台找到超超超長整數的函式庫，
已經不是難事，而且效能還不錯。而crypto1演算法的致命錯誤就在於???金鑰太短。

MIFARE Classic是近年來最廣泛被使用的非接觸式智慧卡，應用在門禁、大眾運輸工
具、電子錢包等系統上。MIFARE Classic上密碼保護機制與結構已被發表在許多的論文
上。在本論文中我們提出各式各樣在MIFARE Classic攻擊實作的經驗。我們實作兩類的
攻擊:一是假造讀卡機、二是側錄合法的交易。第一類的攻擊在兩天內利用NVIDIA高速
運算顯示卡上實作密鑰的窮舉搜尋法與隨機數和連認證的漏洞離線的破解卡片上所有的
金鑰。第二類是針對MIFARE Classic加解密器: CRYPTO-1上攻擊方法的改進。經過我們
的改進，攻擊者不僅可以破解自己的卡同時也能破解別人的卡。我們所實作的攻擊徹底
讓MIFARE Classic的密碼保護失去效用，讓未經授權的攻擊者能任意更改卡片上資料，
如同沒有任何保護的記憶卡。更進一步，我們提出有關防止目前已知的攻擊的建議，而
此防禦機制加強對卡片資料的防護並加強後端清算機制的效率。
http://ndltd.ncl.edu.tw/cgi-bin/gs32/gsweb.cgi/login?o=dnclcdr&s=id=%22098NT
U05442107%22.&searchmode=basic

http://www.rsa.com/rsalabs/faq/files/rsalabs_faq41.pdf