[其他] 沒有雜湊函數的數位簽章

[znmkhxrw (QQ)]

想請問在 [不考慮計算量跟速度] 下
如果直接對整個訊息做只有非對稱加密的數位簽章 會有被竄改然後不被發覺的可能性嗎?


我覺得沒有, 即雜湊函數只是讓計算量降低而已, 推論請見下:

假設我使用的非對稱加密是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://www.ptt.cc/bbs/Math/M.1650051124.A.8FA.html
※ 編輯: znmkhxrw (59.102.225.191 臺灣), 04/16/2022 03:33:19
→ int0x80     : 跟傳整個m_k相比 的確在正確性上不會比較安全
→ int0x80     : 畢竟雜湊函數是公開的 只要有能力造一組合法(M,X)
→ int0x80     : 就能造出合法的用雜湊的簽章
推 AndyLee76   : 的確hash不是必要，這點在維基上有寫
→ AndyLee76   : 只是hash內容遠小於原文，在計算加密上比較快
謝樓上i, A大分享

推 ilway25     : 估狗 why hash before signing 有很多回答
推 ilway25     : 例如有可能可以偽造簽名，維基 Existential forger
→ ilway25     : y
謝謝關鍵字, 我是查digital signature without hash, 我再試試看你的關鍵字

另外wiki講的hash有三個功能, efficiency, compatibility, integrity

前兩者是實務問題不論, 他在integrity那邊講說如果直接加密原文, 那分的多段可能被
竄改者刪除或是換順序

但是這樣的話接受者在解密後也會發現跟一起送來的正確訊息m有出入, 或是跟誤導的錯
誤訊息M不合, 不管哪種case接受者都會認為是無效簽名

不過existential forger應該就是有辦法矇騙過去, 我再看看, 謝謝

→ int0x80     : 睡醒突然發現昨天講錯了抱歉 造的出合法(M,M_k)不代
※ 編輯: znmkhxrw (114.137.187.125 臺灣), 04/16/2022 10:54:31
→ int0x80     : 表能造出加密的hash(M)
推 LPH66       : 這裡的 integrity 應該是指這種狀況:
→ LPH66       : 現代的加密函數都是所謂區塊加密, 會把訊息切成固定
→ LPH66       : 長度個別加密, 那我想要竄改的話我只要把對應區塊
→ LPH66       : 給換成我造的東西就好 (注意是一起換, 接收方不可能
→ LPH66       : 知道訊息當中哪些是正確的)
→ LPH66       : 上面提的 Existential Forgery 也是一樣道理
→ LPH66       : 接收方不知道什麼是正確訊息, 所以可以造一個我要的
→ LPH66       : 簽章出來, 其訊息可以任意指定
→ LPH66       : 至於什麼時候有可能接收方不知道正確訊息
→ LPH66       : 一個例子可能是某些通訊協定中有加密 nonce 的過程
→ LPH66       : 既然是 nonce 那所有組合都是合法訊息
謝謝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
推 LPH66       : 「有意義的訊息」這個想法是個誤區
→ LPH66       : 我上面有提到的狀況就有提到是存在一些狀況
→ LPH66       : 任何訊息都是有意義的訊息
→ LPH66       : (例如我上面提的對 nonce 簽章以產生協定資料等)
→ LPH66       : 在這層意義上, 使用 hash 的意義才正是要試著把
→ LPH66       : 「任何訊息都有意義」這個條件給打破
→ LPH66       : 藉由其中一部份資料的相關性來製造出能夠拒絕的狀況
了解了, 確實有些情況下任何訊息都是有意義的, 而如果要嚴格定義何謂有意義的, hash
在這邊就幫的上忙, 換言之hash好像幫忙定義出何謂有意義的訊息, 好聰明!

謝謝回答~
※ 編輯: znmkhxrw (123.240.192.135 臺灣), 04/17/2022 18:11:18