iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 9
0
Security

資安隨意分享的30天系列 第 9

Day9 - Twenty Years of Attacks on the RSA Cryptosystem

前言

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

正文

這次要分享的是這篇 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. 透過洩漏的部分質數來還原整個質數

總結

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

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


上一篇
Day8 - Integer Overflow/Underflow
下一篇
Day10 - How to Share a Secret
系列文
資安隨意分享的30天30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言