作者znmkhxrw (QQ)
看板Math
標題[其他] 沒有雜湊函數的數位簽章
時間Sat Apr 16 03:32:02 2022
想請問在 [
不考慮計算量跟速度] 下
如果直接對整個訊息做只有非對稱加密的數位簽章 會有被竄改然後不被發覺的可能性嗎?
我覺得沒有, 即雜湊函數只是讓計算量降低而已, 推論請見下:
假設我使用的非對稱加密是RSA,
公鑰是K = (N, e), 私鑰是k =(N, d), 其中公鑰是傳送者, 接受者, 竄改者都看得到,
私鑰只有傳送者看得到
今天我有訊息m跟用k加密的訊息m_k, 傳送數對(m, m_k)出去
接著有竄改者攔截到訊息後把m改成M, 改傳送(M, X)過去, 但是他瞞不過接受端的人啊..
.因為:
1. 若X=m_k, 接受者用K把m_k解密後得到m, 就發現m不等於M, 因此認定M無效
2. 若X=亂碼, 接受者用K把亂碼解密也是亂碼當然不等於m, 因此認定M無效
3. 若X=M_k, 接受者是可以把M_k解密後得到M, 然後得到誤導後的資訊M=M, 但是X=M_k相
當於他要
破解RSA去得到私鑰k, 這當作不可能
因此我認為雜湊函數在
確認是正確訊息上是不需要的
查了很多中英文關鍵字沒找到類似的, 我純粹好奇任何一個算法一定都有其必然理由, 少
了之後會有什麼影響, 多了是為了什麼好處之類的...
所以數位簽證的雜湊函數是:
(1) 同時降低計算量與確認訊息正確性
(2) 只有降低計算量
(1)或(2)對我來說差很多所以想釐清XD
謝謝幫忙~
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.102.225.191 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1650051124.A.8FA.html
※ 編輯: znmkhxrw (59.102.225.191 臺灣), 04/16/2022 03:33:19
1F：→ int0x80 : 跟傳整個m_k相比 的確在正確性上不會比較安全04/16 03:58
2F：→ int0x80 : 畢竟雜湊函數是公開的 只要有能力造一組合法(M,X)04/16 04:00
3F：→ int0x80 : 就能造出合法的用雜湊的簽章04/16 04:02
4F：推 AndyLee76 : 的確hash不是必要，這點在維基上有寫04/16 09:11
5F：→ AndyLee76 : 只是hash內容遠小於原文，在計算加密上比較快04/16 09:15
謝樓上i, A大分享
6F：推 ilway25 : 估狗 why hash before signing 有很多回答04/16 09:51
7F：推 ilway25 : 例如有可能可以偽造簽名，維基 Existential forger04/16 09:56
8F：→ ilway25 : y04/16 09:56
謝謝關鍵字, 我是查digital signature without hash, 我再試試看你的關鍵字
另外wiki講的hash有三個功能, efficiency, compatibility, integrity
前兩者是實務問題不論, 他在integrity那邊講說如果直接加密原文, 那分的多段可能被
竄改者刪除或是換順序
但是這樣的話接受者在解密後也會發現跟一起送來的正確訊息m有出入, 或是跟誤導的錯
誤訊息M不合, 不管哪種case接受者都會認為是無效簽名
不過existential forger應該就是有辦法矇騙過去, 我再看看, 謝謝
9F：→ int0x80 : 睡醒突然發現昨天講錯了抱歉 造的出合法(M,M_k)不代04/16 10:42
※ 編輯: znmkhxrw (114.137.187.125 臺灣), 04/16/2022 10:54:31
10F：→ int0x80 : 表能造出加密的hash(M) 04/16 10:45
11F：推 LPH66 : 這裡的 integrity 應該是指這種狀況:04/17 01:11
12F：→ LPH66 : 現代的加密函數都是所謂區塊加密, 會把訊息切成固定04/17 01:12
13F：→ LPH66 : 長度個別加密, 那我想要竄改的話我只要把對應區塊04/17 01:13
14F：→ LPH66 : 給換成我造的東西就好 (注意是一起換, 接收方不可能 04/17 01:13
15F：→ LPH66 : 知道訊息當中哪些是正確的) 04/17 01:14
16F：→ LPH66 : 上面提的 Existential Forgery 也是一樣道理04/17 01:17
17F：→ LPH66 : 接收方不知道什麼是正確訊息, 所以可以造一個我要的04/17 01:17
18F：→ LPH66 : 簽章出來, 其訊息可以任意指定 04/17 01:17
19F：→ LPH66 : 至於什麼時候有可能接收方不知道正確訊息04/17 01:19
20F：→ LPH66 : 一個例子可能是某些通訊協定中有加密 nonce 的過程04/17 01:19
21F：→ LPH66 : 既然是 nonce 那所有組合都是合法訊息04/17 01:20
謝謝L大分享, 我之後查閱existential forgery後, 發現他是只要竄改者能夠產生出一組
合法的(message, signature)就算是有existential forgery, 其中message
不一定要有意
義
我一開始覺得怪的點在於, 今天如果數位簽章是採用標準的RSA但是沒有用hash, 雖然竄
改者可以造出一堆合法的(m, s), 但是m幾乎是亂碼, 這樣接受者接受到後也會認為無意
義, 這樣的話好像沒有防的必要了
也就是說, existential forgery單純定義在有存在合法的竄改者產生的(m, s)的話, 確
實無hash的標準RSA當數位簽章會有問題
但是如果竄改者要
任意的偽造合法且
有意義的訊息(M, s), 那沒hash的RSA也夠防止這點
發生了, 因為要任意造有意義的訊息M, 必須存在s滿足
M = s^e (mod N), 然後再吧(M, s
)送出去, 但是對於任何M要找到s滿足綠色的條件式, 應該是不好找甚至不存在吧...
※ 編輯: znmkhxrw (123.240.192.135 臺灣), 04/17/2022 01:55:33
22F：推 LPH66 : 「有意義的訊息」這個想法是個誤區 04/17 17:18
23F：→ LPH66 : 我上面有提到的狀況就有提到是存在一些狀況 04/17 17:18
24F：→ LPH66 : 任何訊息都是有意義的訊息 04/17 17:19
25F：→ LPH66 : (例如我上面提的對 nonce 簽章以產生協定資料等) 04/17 17:19
26F：→ LPH66 : 在這層意義上, 使用 hash 的意義才正是要試著把 04/17 17:21
27F：→ LPH66 : 「任何訊息都有意義」這個條件給打破 04/17 17:22
28F：→ LPH66 : 藉由其中一部份資料的相關性來製造出能夠拒絕的狀況04/17 17:23
了解了, 確實有些情況下任何訊息都是有意義的, 而如果要嚴格定義何謂有意義的, hash
在這邊就幫的上忙, 換言之hash好像幫忙定義出何謂有意義的訊息, 好聰明!
謝謝回答~
※ 編輯: znmkhxrw (123.240.192.135 臺灣), 04/17/2022 18:11:18