Blind Signature (盲簽名)
Jing (mqJing@gmail.com)
(this picture was taken from here.)
不知道內容, 那要怎麼放數位簽章呢? 不知道你對解答是否有興趣? 我可是對此非常有興趣! (因為上過密碼學的課, 早就知道有 Blind Signature 這東西. 可是我從來沒搞懂過.)
應用範圍:
想想看要如何讓大家相信, 這個訊息是你本人發出的? 一般的做法是在你的信件內容, 附加一個親筆簽名. 認識你的人, 看到你的簽名就知道這封信是由你本人發送的 (當然, 自古以來就有人模仿別人的簽名, 這裡我們不討論這個問題).
在數位的世界裡, 你無法用筆簽在數位內容上. 所以直接在數位內容上做以密碼學為基礎的數字轉換, 把轉換出來的數值當作文件的簽名, 也就普遍應用在各項的數位內容上. 例如: 很多 Android PAD 廠商, 在系統 image 都有經過數位簽章的加簽. 當載入系統時也就可以檢查 image 是否為偽造的.
所以每個人所發出的訊息或數位內容, 都必須要取得合法或經由機關的認證, 才能讓大家相信這個訊息的來源與用途. 在牽涉到實際的社會活動時(例如: 投票, 抽獎, 通知), 受到主辦單位認證的訊息. 就很重要了.
現在就以投票當實際的例子來說明. 投票是一種普遍的社會活動, 為了防止造假的選票影響公平性, 選票一定要選委會發出的選票才算數. 所以你在領取選票時, 都會被再三檢驗這張選票的目的就在這裡. 這完全符合上面提到的 [受主辦單位認證的訊息].
回到電子選舉應用, 如果你想用電腦或網路來作社會活動時, 要達到 [受主辦單位認證的訊息]. 一般就是使用數位簽章的觀念. 來對要傳輸的訊息作sign 的工作. 例如: 你可以用 md5 對你的訊息算出一個簽章數字, 然後再把訊息與 md5 value 送出去. 任何人都可以藉由這個 hash value 驗證訊息是否被修改過 [1]. 但是若牽涉到無記名投票時, 就會有問題了.
電子無記名投票的意思是: 簽證單位在進行民眾投票內容的簽章時, 無法知道/也不可以知道訊息的內容. 因為如果知道民眾投票的內容, 那認證單位不就知道我投給張三了嗎? 所以幫我簽章的單位, 不可以知道我的票投給誰.
這是一個有趣的問題. 不知道內容, 那要怎麼放數位簽章呢?
不知道你對解答是否有興趣? 我可是對此非常有興趣. 因為上過密碼學的課, 早就知道有 Blind Signature 這東西. 可是我從來沒搞懂過 …. (所以 … 關心本質是很重要的. 如果在乎的是收穫的話. 已經花了時間聽課, 卻沒有搞懂這段時間他教的東西, 那很明確的就是浪費時間. 當然, 如果不在乎上課的內容, 那應該不要浪費時間繼續聽課, 你應該去做自己想要累積的事).
回到正題.
票證單位不應該知道每個人的投票內容, 但又必須要讓每個人在合法的選票上圈選. 匿名投票的需求, 票證單位不應該知道每個人投票的內容.下面是解決方案:
問題定義: 進行數位簽章的單位, 不能知道 message 的內容
主要的創意核心:
簽章單位不一定要對 message 簽章, 使用者送給簽證單位要簽證的 message, 可以是經過修改的. 並且在使用者端可以 inverser 回來即可
作法如下:
Step 1: 交付選票給認證單位簽章. (以證明我的選票 m是合法的)
投票人依照公開格式, 對一張選票 m 圈選喜歡的人物, 搭配使用者自己的密碼 亂數R, 利用 選委會的 public key e 加密後, 傳給選委會.
(因為選委會不知道使用者密碼R 為何, 所以選委會知道投票的人, 但是無法得知投票的人選誰)
Step 2: 選委會將使用者的選票, 進行簽署的動作
選委會利用 private key d, 進行數位簽章的運算, 並將數位憑證 T'發還給投票人. 這麼做的目的是稍候投票人可以藉由 T'產生選票的數位簽章 T, 任何人就可以核對選票的合法性了. 數位憑證 T'的作法如下, 只有一個算式.
Step 3: 取出對選票 m的數位簽章
因為剛剛送給選委會簽章的東西, 是包過一個密碼 random R 的 message, 所以我們要拆解T',以取得來自選委會對我選票 m的簽章 T.
作法如下:
驗證選票的部分 (m,T)
使用者, 可以利用選委會的 public key e, 進行驗證數位簽章 T 所計算出來的m 值, 是不是與自己剛剛送給委員會的 m一樣.
因此, 就完成了 Blind Signature 的主要工作. (選委會因為不知 R, 所以無法得知投票內容m, 投票者可以藉由 選委會的 public key e, 驗證該簽章與選票 message 緊密結合).
投票與計票
這部分我們將在下次說明.
投票
拿到選票與不可修改的憑證後, 現在要開始投票了. 投票的人, 透過 anonymous channel 對投票箱, 進行投票 (m,T)
計票
計票單位可以使用 Paillier Cryptosystem[3] 針對已經加密過後的選票, 進行計票.
基本投票需求:
- 只有合法者才能投票
- 一人一票
- 除了投票者本人之外, 沒有其他人可以知道個別選票的內容
- 無法由開出來的選票, 追蹤到投票人
- 能夠驗證每一張選票都被累計到最後結果
Enjoy!
by Jing.
References
- 井民全觀點, “[Java] 如何使用數位簽章的功能? --- MessageDigest, “http://mqjing.blogspot.com/2008/07/java-messagedigest.html
- 賴溪松, 韓亮 and 張真誠 , “近代密碼學及其應用”, p.p. 21-2
- http://web.mit.edu/6.857/OldStuff/Fall02/handouts/L15-voting.pdf
- Bruce Schneier, “Applied Cryptography: Protocols, Algorithms and Source Code in C” Second Edition.