前言

一直都沒時間好好讀論文，現在開始慢慢追進度...

正文

這次要分享的是這篇 20年來的rsa 攻擊研究

這篇論文好像是 2001 年寫的，距今其實也蠻久了但很經典這樣

Introduction

這邊文章是簡單介紹一下什麼是 rsa ，其實這邊可以直接跳去看維基百科就好

或者其實市面上密碼學的書都有寫很多，這裡就不贅述了

分解大數攻擊

因為 rsa 是建立在很難分解大數的問題上，如果可以分解的話，就可以攻擊 rsa。

那這邊文章就是在介紹分解 n 下的攻擊

這邊額外推薦兩個

1. factordb.com
2. yafu

一個是網站，可以幫你分解數字，另一個是抓在本地運行的軟體，大概跑個 256-bits 大小數字都還在可接受的時間範圍內

Elementary attack

這邊再講一些比較基本古老的攻擊

Common Modulus

這邊說的是 n 的廣播上的問題，也就是當大家的公鑰中， N 都是相同的情況下，會有的問題

情境是:

alice 公鑰(N, e1)
bob   公鑰(N, e2)

bob 可以利用自己的 e2 和私鑰去分解 N ，這樣有了 p, q 可以算出phi(N) 來求 Alice 的私鑰

Blinding

這個是說，假設 Bob 的公鑰是 (N,e) ，私鑰是 d ，而攻擊者 Eve 想要 Bob 幫她對 M 這個明文做簽名

當然這邊 Bob 拒絕

那這邊 Eve 可能隨機選一個小於 N 的數字 r ，並且計算 M'

M' = r^e * M (mod N)

然後 Eve 請 Bob 對 M' 做簽名，那假設這邊 Bob 是同意的，所以得到 M' 的簽名:

S' = pow(M', e, N)

那可以透過 S' 去算 S

S = S' / r (mod N)

這個 S 就是本來 Eve 想要 Bob 對 M 做的簽名，證明如下

S^e = S'^e / r^e = (M')^ed / r^e = M' / r^e = M (mod N)

Low Private Exponent

Wiener attack ，使用條件是私鑰要小於 N 的三分之一的四分之一次方，原理是連分數

可以透過 Wiener attack 求出 phi(N) ，那有 phi(N) 就可以求出私鑰，有私鑰就可解密

Low Public Exponent

Coppersmith's Theorem 這個先跳過@@

Hastad's Broadcast Attack

這是一個利用中國剩餘定理的攻擊，就是剛好場景符合中國剩餘定理的使用條件

所以把數學式寫好，直接 crt 解這樣

Franklin-Reiter Related Message Attack

這是當兩個明文存在一個線性的關係時，可以使用的攻擊

Partial key exposure attack

這種攻擊有三種:

1. 透過洩漏的部分明文來還原整個明文
2. 透過洩漏的部分私鑰來還原整個私鑰
3. 透過洩漏的部分質數來還原整個質數

總結

本來是想寫個詳細一點，但好像又會涉及很多數學@@

之後如果有空再分篇論文寫好了