用於數字籤名以及認證的系統及方法

2023-04-27 20:52:31 1

專利名稱：用於數字籤名以及認證的系統及方法
技術領域：
本發明涉及即使是受到很大限制的計算能力，或者即使完全沒有計算單元，也可以利用公開密鑰加密系統來安全地對裝置或數字內容的籤名進行認證的方法以及裝置。
背景技術：
認證是為了取締盜版行為、未認證的複製或偽造，所以承擔重要的作用。例如，還可以在對護照的所有者進行認證或者以反偽造為目的的、內置了可無線通信的晶片的安全的護照中採用該認證，在此，認證用晶片對製造物的出處進行認證。並且，受到著作權保護的數字媒體為了防止盜版行為等未認證行為，
包含作為DRM (digital right managements)而公知的認證用令牌。結果，支持這些認證的設備(CD、 DVD、存儲卡、其他相同的存儲裝置)經常具備認證機制。最後，認證還有效用於防止竟爭者對產品進行逆向工程，並且對於低價格大量生產也有用。例如，為了防止使用由竟爭者製造的再填充用(refill)器材或偽造的墨盒(cartridge),可以在印表機墨盒中安裝認證用晶片。
認證由被認證裝置(prover)將用於對其進行確定的證據提示給認證裝置(verifier)的協議構成。通常，認證裝置傳送只有被認證裝置可以解決的請求(挑戰challenge),在該請求依照對稱密鑰加密法時，糹皮認證裝置和認證裝置共有公共的保密密鑰，與此相對，在公開密鑰加密法的情況下，只有被認證裝置具有保密密鑰，並且，任何認證裝置都可以確認"企查)由被認證裝置提供的請求的解。
期待在不久的將來把RFID晶片用作認證的手段，但是在現有技術中僅用於記錄標籤信息、即利用無線發送來不加密地淨皮發送的固有的ID號碼。因此，可以接收發送頻率的任何人都獲知該標籤信息，之後可以製作其複製品(clone )。利用基於對稱密鑰加密法的協議，可以對被認證裝置和認證裝置的通信進行加密，所以是更好的解決方式。但是，由於保密密鑰由被認證裝置和認證裝置所共有，所以在認證裝置不可靠或失去信用時，可能會發生ID欺詐。
並且，在幾乎所有情況下，一個認證裝置必須認證多個被認證裝置，因此一旦 一個認證裝置失去信用時，全部的保密密鑰都被公開，然後，全部被認證裝置 也同樣失去信用。並且，在反偽造系統的範圍內，認證裝置不是認證個別的產
品，而應該能夠認證整個產品線。在產品線由數百萬個單元(unit)構成時， 存儲全部的密鑰是過分的。此時，乍一看，代替對各個單元具備一個保密密鑰 而對於全線具備一個密鑰是更好的主意。但是，如果不幸唯一一個單元變得危 險，則產品的全線的信用變得危險。
取而代之，公開密鑰密碼系統，特別是數字籤名可以用於認證的目的。認 證裝置將隨機的消息發送給使用其保密密鑰在消息中簽名的被認證裝置。並 且，認證裝置可以不使用保密密鑰而僅使用被認證裝置的公開密鑰認證籤名， 由此可以確認被認證裝置的來歷。在基於公開密鑰加密法的認證系統中，認證 裝置不知道被認證裝置的保密密鑰，所以具有認證裝置無法偽裝成被認證裝置 的優點。並且，通過使用公開密鑰勤出設施，可以容易地進行產品線的認證。 即，被認證裝置在請求中進行數字籤名，然後與其公開密鑰一同由認證中心裝 置(certificate authority )進行籤名，提供包含了被認證裝置的保密密鑰的數字 籤名的用於被認證裝置的公開密鑰的證書。因此，認證裝置為了確認被認證裝 置的來歷，可以認證雙方的籤名。該方法不僅除去了向不存儲個別單元的公開 密鑰、而必須存儲用於證明的認證手段(例如，用於全部產品線的單一的公開 密鑰，該公開密鑰從製造公司取得)的認證裝置的存儲請求，還包含簡單的取 消機構。在某個被認證裝置的保密密鑰的信用喪失時，可以向全部認證裝置中 設置的黑名單內發送該神皮認證裝置的公開密鑰。
以公開密鑰加密法以及數字籤名為J^出的認證系統具有以下問題。即，為 了構成數字籤名，被認證裝置必須具有某種運算能力。在最典型的數字籤名的 方案中要求相當強的運算能力。但是，從認證機制看也許有用的多個平臺不具 有強大的運算單元，更何況經常完全不具有運算單元，即它們是純粹的存儲單 元。例如，CD、 DVD、 SD卡或其他存儲卡等可拆裝的存儲介質不具備CPU， 僅由存儲器構成。因此，該平臺無法從以公開密鑰加密法為基礎的認證方法中 獲得利益。在專利文獻1中公開了 ，利用具有熔絲、只可寫一次的(read-once)陣列， 無需在被認證裝置一側進行運算來實現認證的發明。但是，在該文獻的發明中， 為了證明由確認裝置提供的應答，要求在認證裝置中存儲保密密鑰，所以基本 上成為對稱密鑰認證協議。
專利文獻1美國專利第5,032,708號
非專利文獻17一7:y卜 7乇7、 、乂亇S—/k 7"f、一 「如何Cl L T&^t自身^証明卞3力、；特定及t/署名問題^0実用的解決」CRYPTO 1986 : 186-19非專利文獻2少少夕^C. ，/k:7「認証S^fc:y、乂夕/P署名」CRYPTO 1989 : 218-238

發明內容
因此，本發明的目的以及優點在於，除了在上述專利中記載的發明的目的 以及優點之外，不對確認裝置一側要求任何運算單元地提供公開密鑰的認證或 數字籤名的機制。通過考慮以下的記載以及附圖，其它目的以及優點將會變得 明確。
被認證裝置(prover)具備存儲有保密數據的特別的存儲單元、即所謂的 只讀一次存儲單元。該單元存儲的數據由陣列狀配置的幾個對(Ui, Di)構成， 在此，僅可以讀出(取出)各對內的兩個要素中的一方。在讀出了對(Ui， Dj)的一個要素之後，從存儲器中刪除該整個對。
除了只讀一次存儲器(read once memory)之外，被認證裝置還具備其他 的存儲單元，該其他的存儲單元存儲用於對被認證裝置的公開密鑰證明對(Ui， D。的認證數據。在該單元上，被認證裝置存儲其公開密鑰和其證書。在數字 數據中進行了籤名時，或者在應答了認證協議中的請求時，被認證裝置表明幾 個對中的一方的要素Uj或Di,伴隨該讀出進行破壞。按照籤名或請求的比特 來選擇被表明的要素。並且，被認證裝置提供用於被表明的要素的認證數據。
被表明的要素Ui或Di對於被認證裝置的公開密鑰進行認證，然後，因為 公開密鑰被進行了驗證，所以被驗證裝置確實可以僅通過表明數據然後進行傳 輸(取出)來不進行任何運算地證明自己或者對數據進行籤名。結果，通過該 存儲單元，根據情況通過簡單的存儲控制器，被驗證裝置可以利用強大的公開
8密鑰加密技術，該公開密鑰加密技術可以用於實現認證、或數字籤名的生成、
或7>開密鑰的認_汪。


圖l表示本發明的認證系統的硬體結構。 圖2表示本發明的被認證裝置的硬體結構。
圖3表示本發明的認證裝置的硬體結構。 圖4是表示本發明的認證系統中的認證協議的流程的流程圖。 圖5是表示本發明的認證系統中的初始化的流程的流程圖。 圖6是表示本發明的認證系統中的籤名生成流程的流程圖。 圖7是表示本發明的認證系統中的籤名認證流程的流程圖。 圖8表示本發明的認證系統的應用例子。
圖9表示作為本發明第二實施例的、將認證系統用於印表機墨盒的認證系 統時的硬體結構。
圖IO表示上述系統中的只讀一次陣列的硬體結構。
圖11表示作為本發明第三實施例的、用於存儲卡上的數字內容的DRM 的硬體結構。
圖12表示作為本發明第四實施例的反偽造系統的硬體結構。 符號說明
101被認證裝置；121認證裝置；141認證中心裝置；161網絡；102、 122、 142輸入輸出接口； 103隻讀一次存儲單元；105ROM單元；106RWM單元； 131、 151存儲單元；132運算單元
具體實施例方式
以下，參照附圖詳細說明本發明的實施方式。 (實施例1 )
首先，作為實施例l，以下說明基於僅有存儲器的平臺的公開密鑰認證、 以及用於數字籤名的系統。
在該第一實施例中，系統由通過網絡連接的至少3個獨立要素構成，即， 由至少一個被認證裝置(prover)、至少一個認證裝置(verifier)、以及認證中 心裝置(Certificate Authority)構成。認證中心裝置的作用是，啟動在被認i正裝置的存儲器內存儲的數據，發行用於被認證裝置的證書。除此之外，認證中 心裝置維持已失去信用的認-i正裝置的黑名單，並且將黑名單定期地向全部認^正 裝置傳輸。
在該系統中，通過利用7>開密鑰基礎設施(public-key infrastructure),可 以通過任何認證裝置來認證任何被確認裝置。該系統具有以下3個參數安全 性參數[n]，其是應該由被認證裝置進行籤名的請求(challenge)的大小；可用 性參數[p]，其是可以由被認證裝置進行籤名的籤名的數量；散列函數[H]及其 輸出大小[h]。
首先，參照圖1對認證系統進行詳細說明。
該系統是僅有存儲器的平臺，由至少一個被認證裝置(prover) 101、至少 一個認證裝置(verifier) 121、以及認證中心裝置(Certificate Authority) 141 構成。^皮i人證裝置101、認證裝置121以及認證中心裝置141通過網絡161相 連接。#:認證裝置101由輸入輸出接口 102、只讀一次存儲單元(read-once memory unit) 103、只讀存儲單元(read-only memory unit) 105、以及讀寫存 儲單元(read-write memory unit) 106構成。認證裝置121具備輸入輸出接口 122、運算單元132以及存儲單元(memory unit) 131。認證中心裝置141具 備輸入輸出接口 142、運算單元(computation units ) 152以及存儲單元(memory unit) 151。
淨皮認證裝置101和認證裝置121可以從事認證協議，在此，認證裝置121 向被認證裝置101發送隨機的請求(randomchallenge) 164,然後，被認證裝 置IOI通過請求的數字籤名163進行應答。在籤名正確時認證成功。認證中心 裝置141的作用是通過初始化數據(initialization data) 162存滿被認證裝置 101的存儲單元，並且發行被認證裝置101的公開密鑰的證書。此外，該認證 中心裝置141維持已失去信用的公開密鑰的黑名單126，將該黑名單發送給與 網絡161連接的全部認證裝置121。
然後，參照圖2對被認證裝置進行詳細說明。
被認證裝置101不具有任何CPU,由存儲單元103、 105、 106和輸入輸 出接口 102構成。該只讀一次存儲單元103存儲有p個保密陣列104,即A。， ， Ap.,，在此，在一個陣列中存儲的數據只能用於一個認證。結果，被認證裝置101隻能進行有限次數、即p次的認證。各保密陣列104由h比特的2n個數 據塊UQ. LU、 D。 . 構成。只讀存儲單元105通過陣列的指數(0 < i 《p-l)、數據塊的指數(0《j<n-l)、以及數據塊的行(D或U)來尋址。
在讀出陣列Ai內的某個數據塊Uj時，將數據塊Ui向輸入輸出接口 102發 送，然後刪除Uj和Uj兩者。同樣地，在讀出Dj時，刪除Uj和Uj兩者，因此， 正如只讀一次存儲器(read-once memory)的名稱那樣，其存儲器內容隨著讀 出而^皮石皮i不。
被認證裝置101具備讀寫存儲單元(read-write memory unit) 106,該讀寫 存儲單元106將計數器107與為了選擇活動(active)陣列所使用的指數(0 《Kp-l)—同存儲在內部。陣列Ai用於一個認證，並且在完全刪除其數據之 後，計數器107的值通過i+l進行更新。
最後，被認證裝置101具備只讀存儲單元105，在此，數據可以沒有任何 限制地自由訪問。該只讀存儲單元105存儲有唯一 (uniquely)確定被認證 裝置101的確定號碼112、被認證裝置101的公開密鑰108、由認證中心裝置 141發行的用於公開密鑰108的證書109、包含2p-l個數據塊(^ ) 的數據樹110、以及p個加密陣列111 (即Co . Cp.,)。各加密陣列含有2n 個數據塊(UQ ... Un.,以及Dq ... Dn.i),其中，來自加密陣列Q的一個數 據塊(Uj或Dj)對應於通過散列函數H進行了加密的、來自陣列Ai的數據塊 (Uj或Dj)，即Ci[Dj]=H (Ai[Dj]) and Ci[Uj]=H (Ai[Uj])。例如，散列函數H 是MD5，即可以是與認證裝置121的散列函數相同的散列函數。加密陣列111 以及數據樹110也可用於，通過後面說明的機制來證明來自只讀一次存儲器 103內的保密陣列104的數據塊是被認證裝置101的7>開密鑰108。
然後，參照圖3對認證裝置121和認證中心裝置141進行說明。
認證裝置121具備若干運算單元，即CPU128，並且如果可能還具備能夠 為了任意大小的輸入X來運算散列值(H( X))的加密用協處理器(coprocessor) 129。例如，該散列函數可以是公知的MD5，或者也可以是其他任何散列函數。 此外，在此留意散列函數具有將任意長的輸入數據映射為h比特的固定長的輸 出的功能。在為MD5時，散列輸出大小為128比特。除此之外，認證裝置還 具備用於生成隨機請求164的隨機數生成器130。
ii認證裝置121還具備用於經由通信網絡161與被認證裝置101、認證中心 裝置141或者其他裝置進行通信的輸入輸出接口 122。最後，認證裝置121具 備存儲單元，即用於暫時存儲數據的易失性存儲器123、以及在存儲程序127 的同時還存儲認證中心裝置141的公開密鑰125和黑名單126的非易失性存儲 器124。黑名單包含已知失去信用的全部的公開密鑰，並且通過在軟體的更新 中傳送新的黑名單的認證中心裝置141被更新。
認證中心裝置141基本上具備與認證裝置121相同的若干構成要素，即 輸入輸出接口 142、 CPU148、用於運算散列值149的協處理器、隨機數生成 器150、用於存儲認證中心裝置的公開密鑰125和黑名單126以及程序147的 非易失性存儲器144、以及易失性存儲器143。除此之外，認證中心裝置141 還可以在非易失性存儲器144內存^l其私有密鑰(private key) 146,並且還具 備用於生成數字籤名以及證書的運算用協處理器153。認證中心裝置141的作 用是在生成用於被認證裝置的保密陣列104的初始化數據134的同時，還生 成加密陣列111和樹數據110。除此之外，認證中心裝置141還可以發行被認 證裝置的公開密鑰108的證書。最後，認證中心裝置141根據全部失去信用的 公開密鑰來維持黑名單126。即，為了防止失去信用的晶片進行認證，在認證 裝置121的軟體的更新中，向全部認證裝置121傳輸其黑名單126。
然後，參照圖4對認證協議進行詳細說明。
被認證裝置101，通過在步驟S211中向認證裝置121發送的認證請求， 可以開始認證協議，在該認證請求中包含被認證裝置的公開密鑰108、證書 109、計數器值107以及ID112。計數器(值)對應於未使用的陣列Ai的指數。
然後，在步驟S221中，認證裝置121確認公開密鑰108是否存在於失去 信用的密鑰的黑名單126中，當該公開密鑰存在於黑名單內時，認證失敗。如 果公開密鑰不在黑名單內，則認證裝置121在步驟222中對證書進行認證。該 證書包含由認證中心裝置141籤名的、被認證裝置的公開密鑰108的數字籤名。 在證書無效時，認證失敗。在證書有效時，認證裝置121發送隨機的n比特的 消息164。該消息是認證協議的請求(challenge),並且必須由被認證裝置101 進行籤名。
之後，被認證裝置101通過訪問陣列A104內的數據塊來對請求進行籤名，在此的[i]是在步驟211中發送的計數器(計數值)，[Uo或D]取決於請求的[O] 比特，或D!]取決於請求的[l]比特，並且，這種情況直到[n-l]比特也是相 同的。除此之外，^皮認證裝置101向公開密鑰108發送來自對應的加密的數 據塊的加密的陣列Cjlll;以及來自證明來自陣列Ajl04的數據塊的數據樹110 的要素。通過^皮i^i正裝置101向認證裝置121發送的籤名163由陣列Ai和C;、 以及來自樹數據的數據塊構成。
當接收到籤名時，認證裝置121在步驟241中使用來自Ci的加密數據塊 和樹數據，來檢查來自陣列Ai的數據塊對於公開密鑰108進行了認證，由此 認證籤名。如果籤名無效則認證失敗，另一方面，如果籤名有效則認證成功。 最後，在步驟253中，認證裝置121寫入協議的日誌，該協議的日誌包含認 證結果(成功或失敗)、認證裝置的公開密鑰、以及由被認證裝置101利用的 指數。
然後，參照圖5對存儲器的初始化進行詳細說明。
在使用前，被認證裝置101的存儲單元必須通過恰當的數據進行初始化， 即，只讀一次存儲單元103在其保密陣列Ajl04內存儲保密的數據塊，加密陣 列111存儲保密數據塊的加密後的值，樹110由與散列函數H成對組合的加 密的數據塊、以及根據與某個固有的ID號碼組合的樹T!的根(root:參照圖 8)運算出的公開密鑰108構成。被認證裝置101基本上由存儲單元構成，無 法通過其自身的初始化來執行所要求的運算，取而代之，全部運算由認證中心 裝置141在外部執行。通過認證中心裝置141運算的初始化數據134僅通過網 絡161發送給被認證裝置101,並且存儲在被認證裝置的存儲單元中。
最初，在步驟301 322中，輸入籤名數p和消息長n，保密陣列104通過 隨機數據塊(random data block)被初始化。即，通過利用了隨機數生成器單 元(random number generator unit) 150的認證中心裝置141生成的隨機數來填 充塊Aj [Uo]和Aj [Do],並且同樣地直到Ai [LU]、 Ai [D^]為止。之後，通過 由散列函數處理過的保密塊來填充加密陣列111的對應的塊，成為Q [UQ]=H (A; [U0] )、 Ci [D0]= H (A; [D0])，並且，同樣地使用散列函數單元149,成為
Ci[Un+H (Ai[Un-,])、 Ci隊,]-H (Ai隊,])。當再次進行敘述時，這些運 算由認證中心裝置141來執行。即， 一旦準備了全部的塊數據，就經由網絡161從認證中心裝置向被認證裝置101傳輸。
在填充了保密陣列104和加密陣列111之後，必須對樹數據進行初始化。 最初，樹的p個葉Tp . , T2p.,由認證中心裝置141準備，並且使各葉與一個 加密的陣列相關聯。更詳細地說，在步驟S332中，將加密的陣列Ci內存儲的 2n個數據塊連成鏈狀，並且由散列函數模塊149進行處理。Ti+P=H( C; [Uo] || Q [Do] II Ci則II Ci [D,] If ... Cj [Un.,] II Cj [D"])，在此，X||Y表示兩個比特流的 鏈。現在，當準備了樹的葉Tp . . . T2l>1時，樹的剩餘節點可以在步驟342中 進行運算。實際上，樹內剩餘節點可以通過對該節點的兩個子節點進行散列 (hashing)來簡單地運算。即，節點Tj具有兩個子節點T2i和T2w，因此，塊 Ti的值由散列函數模塊149來運算,成為H ( T2i|| T2i+1 )。但是，這樣的樹的準 備不便於之後生成認證用令牌，因此，交換樹塊的全部的對，即，在步驟352
中，T2i通過T2i+l來置換，並且T2i+l通過T2i來置換。 一旦處理了全部的樹
塊，就將它們經由網絡161從認證中心裝置141傳輸給被認證裝置101。
然後，在步驟353中，根據樹1^的根和唯一確定4皮認證裝置101的確定 (ID)號碼112來運算被認證裝置101的公開密鑰108。例如，該ID號碼可 以是產品ID，或者在被認證裝置101存儲有某個數字內容時，也可以設為該 數字內容的比特值。無論在哪個情況下，公開密鑰都被定義為H (T川ID),並 且存儲在只讀存儲單元105內。之後，認證中心裝置141發行公開密鑰108 的證書109(步驟354)，該證書包含該公開密鑰的數字籤名，被發送到被認證 裝置101。證書109被存儲在只讀存儲單元105內。最後，將讀寫存儲單元106 內的計數器107初始化為"0(零)"。
然後，參照圖6對籤名的生成進行詳細說明。
在認證處理中，在步驟231 (參照圖4)中留意由被認i正裝置101生成隨 機請求164的籤名163。以下，說明如何生成該認證。隨機請求由n個比特(m-(m0. mn.,) 2)構成，並且，經由網絡161從認證裝置121被發送到被認證 裝置101。在接收到請求後，被認證裝置101表明計數器107的值(在圖4 中由"i，，表示)。該計數器對保密陣列Ai中的一個以及對應的加密的陣列Cj 進行初始化。然後，掃描請求m的比特mj,然後，在步驟421-424中生成2n 個籤名塊，即So，o, So'.'Sj，o、 Sj，, . Sw，o、 Sn.u。在此，從保密陣列Aj104、
14或加密的陣列Cilll的一方中取出各籤名塊。為了生成("取出")該籤名，被
認證裝置101僅從這些陣列104以及111中選擇數據，然後僅表明該數據，不 需要任何的運算。更詳細地說在消息比特mj為O時，在步驟422中，籤名 塊(Sj,o， Sj,i)成為(Ai[Uj]， Ai[Dj]),在消息比特mj為1時，在步驟423中， 籤名塊(Sj，o, Sj，,)成為(Ci[Uj]， Ai[Dj])。在兩個步驟422和423中，留意只 將Aj[Uj]以及Ai[Dj]的一方傳輸給籤名163內。但是，根據只讀一次存儲器103 的特性，它們兩者都^皮破壞。本技術(發明)的特點是對於一個消息比特，表 明唯一的保密數據塊，即，在籤名後保密數據塊的一方仍處於保密，因此， Ai[Uj]或Ai[Dj〗中的任意一方以及籤名不會被偽造。
在選擇了用於(Sj,o, Sj,!)的值後，必須從樹表110中選4奪log2(p)個塊， 在此，所謂log2 (p)是指取整(四捨五入)為最接近的整數的、籤名數p對 於2的對數(logarithm in base 2 )。應選擇的最初的樹塊在步驟432中是設為 j-p+i的P。-Tj，然後，直到選擇log2 (p)個樹塊為止，j反覆被分離為兩個。 最後，在步驟433中，將籤名(S0，0, ..,， S^,p P0,….P,。g2(p)-!) 163經由網 絡向認證裝置121發送。
然後，參照圖7對籤名的認證進行詳細說明。
在運算完隨機請求164的籤名後，被認證裝置101向認證裝置121回復籤 名163。在該時刻，在步驟241 (參照圖4)中，認證裝置121必須認證n比 特的請求(m= (m。….mn-i) 2) 164的籤名(S0，0, . .， S^," P0， ..., P!。g2 (p) -。163。以下，對如何認證該籤名進行說明。
在輸入籤名(S。,q， . .， Sn.U, P。，…，P^2(pM)(步驟521)後，首先，
在步驟522和523中，認證裝置121再次運算(re-compute )加密的陣列QUI 的全部的數據塊，在此，"i"是在步驟211中的認證協議的開始時向認證裝置 發送的計數器107(的值)。更詳細地說，掃描請求比特mQ ' mn小然後， 如果mj為零(0 )，則在步驟522中，使用散列函數模塊129作為H ( Sj，o )來 運算C，j，o,在此，對C，j, i賦予籤名塊Sj,!。實際上，如果請求比特mj為零(O), 則在步驟422中簽名塊Sj, o和％ ,分別作為Ai[Uj]以及Q[Dj]被選擇。因此， 如果在步驟231中由^皮認證裝置正確地生成，則C，j.o應等於Ci[Uj], C，j,,應 等於C,[Uj]。同樣，如果請求比特mj為1,則向C，j，o複製籤名塊Sj,o,並且在C，j,,中設定H (Sjj )。
當準備了全部的對(C，j,0, C，j，,)時，在步驟531中，運算樹數據塊T，。 實際上，使全部的C，j,b的值連成鏈，然後在步驟531中通過散列函數H129進 行散列(hash:細分)。T，=H (C,o，ollC,oH』…UCVu)。
如果在步驟231中由認證裝置正確地生成了籤名，則T，的值應該與來自 樹數據110的樹塊的值、即在籤名的生成中在步驟432 (參照圖6)中選擇出 的Po的兄弟(sibling )—致。因此，該節點為了運算樹110中的親節點(parent node),可以和籤名塊P。組合。更詳細地說，在步驟532中，計數器"i，，被設 定為"i+p"，在此，在步驟211中與公開密鑰、證書一起從被認證裝置104接 收計數器"i" 107的值。如果"i，，為偶數，則在步驟552中，使用散列函數 模塊129將T，更新為H(T，HPo),另一方面，如果為奇數，則在步驟553中將 T，更新為H (PollT，)。此外，在正確地生成了籤名時，T，應包含還作為籤名塊 Pj的兄弟的之前的T，和Po的親節點。然後，對於P,， P2，， P,。g2(p-,)也重複 進行同樣的步驟，並且，在重複完之後，T，的值應該與某個樹數據塊的值一致， 每次接近根一個等級(圖8的根T,)。最後，T，包含根T,的值，然後，在步驟 555中，被認證裝置101的公開密鑰108可以通過運算H (T， ||ID )再次進行 運算，在此，ID是被認證裝置101的確定號碼112。如果公開密鑰與運算H (T，IIID)的結果一致，則籤名在步驟562中被接受，另一方面，如果不一致， 則在步驟563中被拒絕。
然後，參照圖8對上述認證系統中的數據結構的一例進行詳細說明。
圖8表示在籤名了 p=128個籤名、並且請求具有n=4比特的情況下如何組 織數據。存在128個保密陣列AQ， ...， A127,以及128個對應的加密的陣列 C0， ，.， C127。各陣列具有8個數據塊Uo、 U,、 U2、 U3以及D。、 Dp D2、 D3， 並且，具有Ci [Uj]= H ( Aj [Uj])以及同樣具有Cj [Dj]= H ( Aj [Dj])。當把在數 據初始化中使用的散列函數設為MD5時，h=128,各數據比特也同樣具有128 個比特。
樹數據110的葉T128 . . ■ T255最初如下進行運算。
T128+i=H ( Ci [U0〗|i Ci [D0] II Cj則II Ci [D,] ||Q , Q [D2] || [U3] || Ci [D3])20
例如，T154=H ( C26 [U0〗|i C26 [D0] II C26 [Ui] II C26 [D,] ||C26 [U2]|| C26 [D2] || C26 [U3] II C26 [D3])。
然後，進行將親節點細分(hashing)為兩個子節點的運算，即，進行Tr H (T2i||T2i+1)。例如，成為T77=H (T154||T155)。但是，在運算了樹內的全部 的節點後，為了從丁255到T,促進生成籤名，每次交換兩個節點，即，將T2和
T3交換，將丁4和T5交換，以下也相同地進行交換。最後，交換Tt54和T,55。
在存在由128比特構成的8個數據塊的同時，還存在128個保密陣列，因 此，只讀一次存儲單元103具有16千字節的容量。同樣地，在存在由128比 特構成的8個凝:據塊的同時還存在128個加密的陣列，並且，存在由128比特 構成的255個樹節點，因此，為了存儲這些要素，只讀存儲單元105需要20 千字節。但是，除此之外，只讀存儲單元105還必須存儲公開密鑰108和其證 書109。
此外，對籤名的生成進行說明。當把計數器107設定為26時，為了生成 籤名，陣列八26和(:26成為活動的(ActiveX例如，使針對籤名的4比特的請 求為m-( 1001 )2。最初的比特為"1",因此，對應的籤名塊為C26[U0]， A26[D0]。 第二比特為"0",所以對應的籤名塊為C26[U!], A,],以下也相同。最後， 籤名請求(1001) 2的最初的部分成為(So,o， So，,， Si,o， S,，p S2,0, S2,p S3,0,
) = (C26[U0],A26[D0]， A26[U。A6[D,]， A26[U2],C26[D2], C26[U3]，A26[D3])。
然後，為了對公開密鑰認證籤名的最初的塊，必須選擇來自樹的節點。應 該選擇的最初的節點為T155=H (C26 [UQ] II .. II C26 [D3])的兄弟節點， P0=TP+26=T154。下一個節點為作為節點丁155和丁154的親節點的T76的兄弟， PfT154/2=T77。重複進行該步驟直到P^T2為止。
然後，對籤名的認證進行說明。認證裝置121最初接收公開密鑰108、以 及在本例中i=26的計數器值107。接收籤名(S。，Q,， Sv),認證裝置121 利用散列函凝3莫塊129再次運算來自加密的陣列C26的全部數據塊。最初的請 求比特為"1"，所以認證裝置121運算(C，。,。， CV) = (So,o, H (S(u))。由 於第二請求比特為"0"，所以認證裝置121運算(d，o, C，u) = (H (S^)， Su),以下也相同。在處理了全部的請求比特之後，認證裝置121得到以下的 陣歹寸(C，o,o，C，o，i， C，i，o,C，i,i， C,2,o,C，2，1, C，3,0,C，3，1 )=( S。，o,H( So，i )， H( Si,o ),Si,i，
17H ( S2，0) ,S2，1， S3，0,H ( S3，1))。
在沒有由被認證裝置101正確地生成籤名的情況下，該陣列應該具有與加密的陣列C26相同的數據塊。實際上，可知(So,o， So,!) = (C26[UG]， A26[D0])，因此，成為(CV C，o,J = (C26[U0]， H (A26[D0])) = (C26[U0]， C26[D0])。
對於其他籤名塊也進行同樣的觀測。認證裝置121可以再運算加密的陣列，但認證裝置121沒有方法從被認證裝置101得知加密的陣列的確與最初加密的陣列相同、或者加密的陣列為真的(authentic)。因此，認證裝置121為了對於公開密鑰108認證加密的陣列，使用剩餘的籤名塊，即樹塊。
最初，認證裝置121使用散列函數模塊129運算丁，=11((:，0，0，(:，0,1,(:，1,,(:，1,1,
C，2，o，C，2,。
C，3，Q,C，w )。如果正確地生成了籤名，則T，應該與樹節點T,55相同
(留意丁154和T。5在數據初始化階段被進行了交換)。認i正裝置121在此將P0和T，組合，即，最初將計數器"i"設定為"i+p-154"。因為"i=154，，，所以認證裝置121通過散列函數模塊129運算T，=H (T， II Po )。實際上，如果正確地生成籤名，則T，= T,55以及Pf T154,因此，T4皮更新後的值應該為親節點T76。然後，將"i"除以2,成為"i-77"。因為"i=77"為奇數，所以成為T，-H
(PJT，)。如果再次正確地生成籤名，則T，被更新後的值應該為親節點丁39。在利用了到P6為止的全部樹塊之後，如果籤名正確，則認證裝置121應運算了樹的根，即"T，=Tr，。然後，認證裝置121僅確認H (T，IIID)是否與公開密鑰108的值一致。
最後，對該結構的安全性進行討論。對於一個消息比特mj，對應的籤名部分為Ai[Uj], Q[Dj]或Ci[Uj], Ai[Dj]。在雙方的情況下，保密塊Aj[Uj]， Ai[Dj]被破壞，因此，它們的一方仍未表明，所以仍然處於保密。結果，為此需要得知沒有表明的保密塊，所以不會對不同的消息比特進行籤名。作為一例，如果消息比特為mj=0,則針對mj=l的籤名的偽造，例如像Ci[Dj]=H (Ai[D」])那樣，暗示了發現Ai[Dj]。但是，該任務例如被稱為Y-H(X)，該Y-H(X)發現與某個被賦予的Y相對應的原像(pre-image) X,由於散列函數的特性，
這是不可能實現的。
作為不同的途徑，還可以嘗試注入對於樹的根Tt進行認證的保密陣列A;此時，樹的下部與真的樹不同，例如，T，i+pTi+p，但是在某個點，兩個樹具有相同的根，所以相同。這對於某個節點的指數"j"為(T， 2j， T，2j+1 ) ( T2j，T2j+)，但是暗示了 T，廣Tj，在此，為Tj^H(T2jllT2jw)以及T，H(T，2jllTV！)。例如，H (X) =H (X，)那樣的值X, X，被稱為衝突(collisions),並且，根據散列函數的特性，不可能發現該沖突。因此，偽造籤名的唯一途徑是，觀察真的被驗證裝置101和認證裝置121之間的相互作用，然後從4皮認證裝置101收集籤名。然後，在從事於認證協議時，如果為相同的計數器值"i"則認證裝置121與真的被認證裝置101的情況相同地，發送相同的請求，偽造者可以使用對應的收集到的籤名。結果，偽造籤名的概率為l/2n，在此，"n"為安全性的參數。如果對於請求大小n=20，則該;慨率為100萬次中1次以下的程度。
此外，本發明的範圍不限於以上所述的實施例。例如，可用性參數p或籤名的數量、或者安全性參數n或請求的大小等系統參數可以取任何恰當的整數值。為了高安全性的系統，n必須變大，典型地為121比特以上，這對於被認證裝置101要求大的容量。為了使認證系統輕量化，例如可以像8比特那樣選擇較小的n,此時，作為偽造者偽造籤名的概率具有1/256，這從智慧卡上通過PIN碼提供的安全性來看也不是非常不合理，在某種狀況下可以允許。
此外，對於散列函數可以任意地選擇，即，可以是具有128比特的輸出大小的MD5、或SHA1、或其他任何的散列函數。
被認證裝置101的存儲單元可以通過幾種方法來實施。更嚴密地說，存儲單元105包含讀寫存儲器(read-write memory),可以是任何類型的存儲器。因此，可以通過ROM、 PROM、 EEPROM或閃速存儲器(flash memory)或者任何存儲器輔助單元來實施。關於只讀一次存儲單元103,例如可以是上述專利文獻l記載的熔絲底座(flisebase)的真正的只讀一次存儲器，或者可以是FeRAM存儲器或其他任何只讀一次存儲器，並且其功能例如可以通過作為閃速存儲器的EEPROM和通過寫入來刪除內容的存儲控制器構成的、標準的存儲單元來實現(仿真)。
最後，將上述的認證系統變更為生成消息164,通過被認證裝置101進行籤名，然後由認證裝置121進行認證的數字籤名系統，對於本領域的技術人員來說應該是簡單的。(實施例2 )然後，參照圖9對作為本發明實施例2的用於印表機墨盒的認證系統進行詳細i兌明。
該系統由認證者晶片121和被認證者晶片101構成。在本實施例中，在印表機中安裝有認證者晶片121，另一方面，在墨盒中安裝有被認證者晶片101。正規的墨盒可以在商店購得，此外，由竟爭者製造的偽造的墨盒或再填充器材(refill kit)也相同。因此，為了禁止使用偽造的墨盒，合法的墨盒必須對印表機進行認證，並且，必須只能使用為了避免再填充而限制的次數。
墨盒101和印表機121直接接觸，可以經由直接連接901交換數據。交換的數據例如可以是墨水等級(ink level)的檢查等、與通常的印表機功能有關的數據，但是也可以是與包含請求164或籤名163的認證數據有關的數據。
印表機121例如經由USB這樣的電纜902與個人計算機911連接。在個人計算機911中，例如在安裝了 USB、 LAN連接器、存儲單元913、運算單元914或者幾個周邊設備或單元的同時，還安裝了輸入輸出接口 912。經由電纜902,個人計算機911還可以發送與印刷請求或通常的印表機功能有關的任何數據，並且還可以提出黑名單126。實際上，個人計算機911經由網際網路與認證中心裝置(Certificate Authority)連接，認證中心裝置將固件或軟體的更新版本經由個人計算機911發送給印表機121,並且，同時還可以發送更新後的黑名單。
認證中心裝置141是與網際網路903連接的WEB伺服器，由印表機公司來運營。與最初的實施例的情況不同，在認證中心裝置141和墨盒101之間沒有持久性的直接連接，因此，無法從遠方執行數據的初始化。取而代之，墨盒的存儲單元103、 105以及106在製造墨盒時進行初始化。此時，將墨盒與認證中心裝置141物理連接，或者，為了避免將多個墨盒的保密陣列104洩露的安全性侵害，可以向不與網際網路連接的專用計算機連接。
印表機121和墨盒101是自主的，並且可以不訪問外部任何網絡地執行認證，特別是印表機121不需要向網際網路903或認證中心裝置141持久性地直接連接。僅通過使用在本地存儲的認證中心裝置141的公開密鑰125，印表機121可以通過在上述實施例1中記載的認證機制來認證合法的墨盒。可以按照印表機公司的安全性策略，以定期的時間間隔來執行認證。例如，可以在每次請求
20列印時、啟動時(bootingtime)或者每天進行認證。關於認證失敗時印表機如何處理，也根據印表機公司的安全性策略來決定。作為一種可能，還考慮印表機拒絕列印請求數分鐘。因此，即使安全參數不是非常高，例如，即使是n-8比特的請求，實際上成為1/256的偽造概率，但如果使印表機在認證失敗時成為空轉(idling)大約1分鐘的狀態，則在使用偽造的墨盒時，其可用性受到大幅損害。
在該實施例2中，安全性參數對於消息大小為n=8比特，散列函數為輸出大小h=128比特的MD5，籤名數量為p=1024個。
此時，只讀一次存儲器存儲用於保密陣列104的大約260千字節的數據，與此相對，只讀存儲器需要用於加密陣列111的260千字節和用於樹數據110的32千字節。公開密鑰108正是一個散列值，因此為16位元組，證書可以是1024比特的RSA籤名，因此為128位元組，並且，ID112是通過4位元組編碼的產品編號。對只讀存儲器要求總共300千字節以下的容量。最後，計數器107是用於計數到1024的計數器，佔用讀寫存儲器的2位元組。
只讀一次存儲單元103將在後面對其進行詳細討論，只讀存儲單元105作為PROM來實施，讀寫存儲單元106作為EEPROM來實施。關於輸入輸出接口 102,是由串行數據輸入輸出針921、供電針922、接地針923以及時鐘針924構成的單純的連接器。
然後，參照圖IO對只讀一次陣列進行詳細說明。
存儲保密數據塊Uj以及Dj的保密陣列Ajl04是認證機制的核心部分。一對陣列(Uj， Dj)只使用一次，數據在被訪問後刪除。在本實施例2中，該只讀一次存儲器通過熔絲1021來實現，更詳細地說， 一個熔絲存儲有一個數據比特。熔絲具有兩個狀態，即與比特值"0"對應的熔融狀態和與比特值"1"對應的非熔融狀態。除此之外，當電流流過熔絲時，熔絲熔融，然後，對應的比特值被不可恢復地設定為"0"。
此外，對保密陣列104進行詳細說明。各陣列Ai具有兩個輸入信號，即8比特的請求164和時鐘信號931。各陣列還具有作為一個輸出的、籤名163的一部分。8-計數計數器1002進行從"0"向"8"的計數，其輸出控制復用器1001和解復用器1003。復用器1001根據計數器1002的值選擇8個請求比特中的一個，例如根據"1"選擇請求的比特"1"。解復用器1003按照計數器
1002的值，將輸入Vcc信號1005向128比特的存儲元件(cell) 1011 U0， ，U7中的一個，並且向128比特的存儲元件1012 D0，， D7中的一個傳播。例如，根據"1"將Vcc向U!和D!傳播。各存儲元件Uj或Dj存儲128比特，並且，包含128個熔絲1021,熔融狀態的熔絲存儲比特值"0",另一方面，非熔融狀態的熔絲存儲比特值"1"。
留意計數器1002啟動存儲元件Uj內的一個、和存儲元件Dj內的一個。兩個存儲元件將它們的128比特的存儲器內容向復用器1004傳輸。留意計數器1002還選擇請求比特mj的一個。將該請求比特的值向復用器1004傳輸，用於選擇Uj或Dj中的某一方，如果請求比特為mji,則籤名的一部分為Uj，並且，如果請求比特為m^1，則籤名的一部分為Dj。
然後，對一個存儲元件U1011進行記載，但其他的元件也基本相同。如果計數器1002為"0 (零)"，則將輸入Vcc傳輸給全部的作為關斷開關進行動作的128個電晶體1022。如果對於某一個電晶體對應的熔絲1021熔融，則電阻1023左右側的電壓非零。即，反相器1024的右側具有與比特值"0"對應的電壓"0"。
另一方面，如果熔絲1021沒有熔融，則電阻1023的右側與接地信號連接，該電阻的右側的電壓成為零(0)。即，反相器1024的右側具有與比特值"1"對應的電壓Vcc。但是，此時，電流通過熔絲1021，在某個時間後使熔絲熔融，然後，對應的比特數據被無法恢復地設定為零(0)。即，數據在對其進行訪問後始終被刪除。
如果最初沒有將輸入Vcc通過解復用器1003向128個電晶體傳輸，則它們全部作為接通開關進行動作，並且，全部電晶體的右側的電壓成為零(0),因此，存儲元件Uo直到由解復用器1003啟動為止，不傳輸其存儲器內容。
但是，本發明的範圍並不限於上述實施例，特別是還可以作為用於其他應用的同樣的系統來使用。例如，在第二實施例中記載的認證系統還可以用於認證更換部件的 一致性(compliance )。作為典型的例子是用於膝上型電腦的電池，
損壞膝上型電腦的經驗。通過利用在此記載的認證系統，膝上型電腦的製造者可以對適合於產品並且可以安全使用的膝上型電腦用電池發行數字證書。並且，當然，在此記載的認證系統也可以根據不同的安全性或可用性參數、不同
的散列函數、以及通過不同的存儲器支援(memory supports )來實施。(實施例3 )
然後，作為本發明的實施例3，對用於存儲卡上的數字內容的DRM進行說明。
即，在該第三實施例中，表示了本發明可以如何用於保護在存儲器支援上、特別是在SD卡等由閃速存儲器構成的存儲卡上存儲的數字內容。在默認狀態下，無法根據存儲器的類型來支援該只讀一次訪問(僅一次的讀出訪問)，所以必須通過簡單的存儲控制裝置來實現該功能，即，在讀出了某個特定的存儲器區段時，破壞該讀出的內容。
作為該第三實施例，以下參照圖11對用於視頻遊戲控制臺和視頻遊戲的例子進4於詳細i兌明。
在該第三實施例中，被認證裝置是在其上裝有軟體、典型地裝有視頻遊戲1126的存儲卡。該視頻遊戲1126可以由認證裝置、即視頻遊戲控制臺121來執行。視頻遊戲與控制臺直接連接1101,存儲卡具有包含數據針1121、供電針1122、時鐘針1123、以及接地針1124的幾個針。向閃速存儲器部1127的訪問由控制訪問權的存儲控制器1125管理，即，存儲有加密的陣列、樹數據、公開密鑰以及證書的存儲器區段105具有只能讀出的(read-only:只讀訪問)功能，存儲有計數器的存儲器區段106具有讀出/寫入(read/write:讀寫訪問)功能，並且，存儲有保密陣列的存儲器區段103具有僅一次讀出(read-once:只讀一次訪問)功能，並且，在讀出保密陣列之後通過存儲控制裝置1125刪除。並且，存儲控制器1125如圖4所記載的那樣，還執行籤名的生成(signaturegeneration) 231。與上述的實施例相同，為了對請求進行籤名而進行訪問，然後，根據情況需要刪除存儲器。
在視頻遊戲控制臺中具備通常的周邊設備以及包含運算單元132和存儲單元131的單元。輸入輸出接口例如通過利用WiFi接口來控制與視頻遊戲存儲卡101的連接，並且控制與網際網路1103的連接。該控制臺的主要目的是執行在存儲卡101上存儲的遊戲軟體1126。認證中心裝置141是由視頻遊戲公司管理的WEB伺服器。該WEB服務 器可以發行用於被允許在控制臺121上運行的視頻遊戲的證書，並且維持失去 信用、以及其保密陣列被黑客披露的特定存儲卡110的公開密鑰的黑名單126。 控制臺121不進行向網際網路1103的持久性的連接，而是有時為了軟體或固件 的更新而訪問網際網路。此時，將黑名單126向通過認證中心裝置141連接的全 部控制臺121進行傳輸。
當把視頻遊戲存儲卡101插入控制臺121中時，將遊戲數據1126向控制 臺傳輸。在該情況下中，遊戲數據1126還是存儲卡101的確定手段ID112。 存儲卡101的公開密鑰被規定為H(T川ID)，所以遊戲數據可以由視頻遊戲控 制臺121來認證。本發明的目的在於防止由控制臺執行沒有認證的軟體，根據 籤名數據163，可以根據在實施例1中記載的認證協議的結果來確定是否可以 執行遊戲數據1126。在該結果為在認證協議中失敗時，病毒或非法的複製等 具有惡意的代碼無法在視頻遊戲控制臺上執行。並且，由視頻遊戲公司管理的 認證中心裝置141,對於作為可以開發出能夠在控制臺121上運行的視頻遊戲 的第三方的遊戲提供商，可以不向該第三方表明認證中心裝置的私有密鑰146 地發出證書。
在該第三實施例中，安全性參數對於請求的大小為n=32比特，因此，偽 造籤名的概率為相對於四百萬或其以上大約1次。在認證數次失敗時，控制臺 應該按照視頻遊戲公司的安全策略進行反應。例如，可以將存儲卡的公開密鑰 108加入到黑名單126中，並且，為了更新其他控制臺的黑名單，可以向認證 中心裝置141發送通知。可用性參數;陂選4奪為p=65,536,由此， 一個特定的-見 頻遊戲可以運行65,536次。最後，散列函數為h=128比特的MD5。此時，在 只讀一次存儲器區段103中需要67兆字節的容量，在只讀存儲器區段105中 需要69兆字節的容量，並且在讀寫存儲器區段106中需要2位元組的容量。
此外，本發明的範圍不限於上述實施例，可以簡單地通過不同的參數、例 如SHA1這樣的不同的散列函數、或者例如EEPROM或其他類型的存儲器來 實現同樣的功能。並且，在實施例3中記載的系統還可以容易地用於其他目的， 特別是根據該系統，例如可以對電影或音樂等任何類型的數字內容進行數字籤 名。並且，認證裝置121並不限定為可攜式音頻播放器、行動電話或個人計算
24機，還可以通過任何類型的電子設備實現。 (實施例4 )
最後，以下詳細說明將本發明用於基於RFID晶片的反偽造系統的實施例4。
現有的RFID標籤不安裝加密模塊，因此不足以用於認證或反偽造。不在 該平臺上執行加密算法主要有兩個理由。首先，最初，為了用於加密需要消耗 大量的能量，另一方面，被動的標籤即使是非常低的電力設定也進行動作。第 二，幾乎所有RFID標籤僅具備存儲器，為了儘可能低地維持製造成本，不具 備運算單元。
在該第四實施例中表示了如何取得在實施例1中所述的認證機制的優點， 即，如何通過通常實現只讀一次訪問(read -once access)功能的FeRAM存"f諸 器來實現只讀一次存儲單元(read-once memory unit )。
首先，以下參照圖12對反偽造系統進行詳細說明。
對於名牌物品或高價產品來說，偽造成為最大的爭論焦點，在此，加密或 數字籤名確實可以有所幫助。所謂該第四實施例的典型的情況是海關的管理， 在此，為了檢查具備RJFID晶片的可疑的項目，海關人員使用RFID閱讀器 (RFID reader) 121。 RFID晶片與認證協議聯合工作，認證項目的可靠性，對 此，偽造的產品在其自身證明失敗時被檢測出。RFID晶片由檢查項目的製造 者(以下稱為公司)製造，並進行初始化。公司起到認證中心的作用，並對海 關人員發行認證中心的公開密鑰125,但是，例如在閱讀器121被惡意的用戶 佔據等情況下，為了避免信息的洩露，保密地保存認證中心的私有密鑰146。
RFID晶片101由公司安裝在所製造的產品上，該晶片具備天線1201、以 及可以捕捉規定頻率的無線電波，並且利用磁感應將無線電波轉換為電信號的 轉發器(transponder) 1202。由轉發器轉換的電信號傳輸來自閱讀器121的信 息，同時還由晶片101作為電源來使用。通過對接收到的信號進行後向散射， 轉發器1202和天線1201可以將數據回復給閱讀器121。因此，閱讀器121和 RFID晶片101使用近距離通信技術，通過無線網絡相連接。
存儲控制器1203控制向由FeRAM (Ferromagnetic Random Access Memory )實現的存儲部1204的訪問。FeRAM本來是只讀一次存儲器(read-oncememory),其數據與實施例3的情況不同，由於讀出而4皮破壞，所以存儲控制 器1203不需要表明地刪除數據。因此，存儲控制器的作用僅是實現存儲控制， 並且執行圖6所示的籤名生成步驟。在此再次說明，所謂籤名就是選擇l丈據， 不需要進行任何運算。
FeRAM是具備類似閃速存儲器的特性的非易失性存儲器，並且具有幾個 優點。即，低功耗，並且寫入/刪除循環(write/erase cycles )的次數多。FeRAM 目前在幾個RFID的應用中使用。FeRAM單元1204至少具有3個存儲器區段。 只讀區段(read-only segment) 105存儲有ID112、公開密鑰108及其證書109、 樹數據110、以及加密的陣列111 。讀寫區段(read-write segment )106存儲有 計數器107，並且只讀一次區段(read-once segment) 103存儲有保密陣列104。 從其性質上看，FeRAM為只讀一次(read-once),所以不需要任何用於實現存 儲器區段103的只讀一次特性(read-once functionality)的機制。但是，在只 讀區段105和只讀一次區4史106中存儲的數據通過讀出被破壞，所以必須通過 在存儲控制器1203內實現的機制來再生(refresh)數據。
晶片101和閱讀器121如圖4所示，可以執行認證協議，在此，閱讀器 121向晶片101發送隨機的請求164,晶片通過請求的籤名163來應答。作為 閱讀器，可以是具備用於與RFID晶片101進行通信，並且在失敗時顯示認證 協議的結果以使海關人員可以採取恰當的應對措施的近距離通信技術的 PDA。並且，為了獲得包含失去信用的產品的公開密鑰的、由公司更新的黑名 單126,閱讀器可以定期向網際網路1212連接。但是，在閱讀器為可移動(mobile) 時，並不一定持續向網際網路連接，因此，晶片101和閱讀器121之間的認證協 議，可以不受到任何外部千擾，或者不向網際網路1212連接地執行。
在該第四方式中，安全性參數對於請求的大小選擇為n=16比特，並且， 作為可用性參數為p-256個的籤名。因此， 一個產品在其壽命內最多可以認證 256次。並且，只能以l/216=l/65，536這樣的可以忽略的概率偽造籤名。對於 散列函數使用SHAl,因此散列輸出大小為h=160比特，由此，需要用於ReRAM 單元1204的330千字節的容量。
本發明的範圍不限於上述的實施例，上述的系統並不限於電子護照，還可 以用於產品的跟蹤(product tracking)、電子錢包(electronic wallets )或者電子月票(electronic commuter pass)等其他情況。也可以使用不同的散列函數或 實現。
2權利要求
1. 一種加密系統，其用於在不具備強大的運算單元或者完全不具有運算單元的平臺中生成數字籤名，其特徵在於，具有(a)用於接收輸入消息的第1單元；(b)用於存儲保密數據的第1存儲部；(c)用於存儲加密後的數據、認證數據以及公開密鑰的第2存儲部；(d)存儲了計數器的第3存儲部；以及(e)用於發送所述輸入消息的數字籤名的第2單元，所述數字籤名具備從所述保密數據中取出的數據，並且具備所述加密後的數據以及認證數據。
2. 根據權利要求1所述的加密系統，其特徵在於， 所述保密數據由多個保密陣列構成，所述保密陣列存^f諸多個保密數據塊，並且所述保密數據塊成對地構成，在所述對的狀態下只有一個所述保密數據塊 可以訪問，並且通過讀出所述對內的要素破壞兩個保密數據。
3. 根據權利要求1所述的加密系統，其特徵在於，所述第1存儲部是熔絲陣列，並且通過訪問所述第1存儲部熔化規定數量 的熔絲。
4. 根據權利要求2所述的加密系統，其特徵在於，還具有存儲控制器，所述存儲控制器通過訪問所述第1存儲部消除規定數 量的所述保密數據塊。
5. 根據權利要求4所述的加密系統，其特徵在於， 所述第1存儲部是閃速存儲單元。
6. 根據權利要求4所述的加密系統，其特徵在於， 所述第1存儲部是EEPROM存儲單元。
7. 根據權利要求4所述的加密系統，其特徵在於， 所述第1存儲部是FeRAM存儲單元。
8. 根據權利要求2所述的加密系統，其特徵在於，所述加密後的數據由多個加密後的陣列構成，該加密後的陣列存儲有多個加密後的數據塊，並且所述加密後的數據塊存儲來自通過加密處理單元加密後的所述保密陣列的所述保密數據塊。
9. 根據權利要求8所述的加密系統，其特徵在於，所述加密處理單元是散列函數單元。
10. 根據權利要求9所述的加密系統，其特徵在於，所述認證數據構成為存儲了多個節點的樹狀的結構，所述樹的葉子存儲有由所述散列函數單元進一步加密後的節點，並且，所述樹內的親節點存儲有由所述散列函數單元加密後的規定數量的子節點，在此從所述樹的根導出所述公開密鑰。
11. 一種爿^開密鑰i人-i正系統，其特徵在於，具有(a) 所述權利要求1所述的加密系統；以及(b) 認證部，該認證部具有(1) 用於生成隨機數消息的隨機數生成單元；(2) 用於發送所述隨機數消息的第l單元；(3 )用於接收數字籤名的第2單元；以及(4)用於認證所述數字籤名的第3單元，所述加密系統生成所述消息的數字籤名，並且當正確地認證所述數字籤名時，由所述認證單元來證明。
12. —種用於生成數字籤名的數字籤名生成方法，其具備以下的步驟(a) 提供用於存儲保密數據、加密後的數據、認證數據以及公開密鑰的單元；(b) 接收輸入消息；(c) 從所述保密數據中取出保密數據塊；(d) 從所述加密後的數據中取出加密後的塊；(e) 從所述認證數據中取出認證數據塊；(f) 更新計數器；(g )發送所述輸入消息的數字籤名，該數字籤名生成方法的特徵在於，所述數字籤名具有所述取出的保密數據塊、所述取出的加密後的數據塊、以及所述耳又出的i人證數據塊。
13. 根據權利要求12所述的方法，其特徵在於，取出所述保密數據塊的步驟還具有以下步驟(a) 消除所述取出的保密數據塊；(b) 對應於各個取出的保密數據塊，至少消除一個其他的保密數據塊。
14. 根據權利要求12所述的方法，其特徵在於，取出所述保密數據塊的步驟還具有以下步驟(a) 對所述輸入消息的1比特進行掃描；(b) 訪問所述保密數據內的保密數據塊的對；(c) 如果所述比特為0則表明所述對中的一個保密 居，如果所述比特為1則表明該對中的另一個保密數據；(d) 消除所述保密數據的所述對；(e) 對於所述輸入消息的全部比特重複上述的步驟，由此，所述數字籤名包含有被表明的保密數據塊。
15. 才艮據權利要求12所述的方法，其特徵在於，通過使用加密函數從所述保密數據中對全部的保密數據塊進行加密，由此對所述加密後的數據進行初始化。
16. 根據權利要求15所述的方法，其特徵在於，所述加密函數是散列函數。
17. 根據權利要求16所述的方法，其特徵在於，所述認證的初始化包含以下步驟(a) 通過使用所述散列函數對規定數量的加密後的數據塊執行散列，運算葉節點；(b) 通過對在所述上一步驟中運算出的規定數量的節點扭i行散列，運算至少一個新的節點；(c) 重複進行上述的步驟(b)，直到剩餘一個節點為止，由此，從通過所述初始化方法運算出的最後的節點導出了所述數字籤名方法的公開密鑰。
18. —種公開密鑰認證方法，其特徵在於，具有以下的步驟(a) 生成隨機的消息；(b) 通過所述權利要求12所述的方法生成所述隨機消息的數字籤名；(c) 對所述數字籤名進行認證，由此，在正確地認證了所述數字籤名時，認證成功。
全文摘要
本發明提供用於在僅有存儲器的結構中進行認證和數字籤名的系統及方法，其具備只讀一次存儲單元，其存儲有由於讀出使內容被破壞的數據的保密陣列；以及通常的存儲器，其存儲有加密陣列、對於單一的公開密鑰證明加密陣列的樹數據、以及由認證中心裝置發行的公開密鑰的證書，這些存儲器結構向被認證者裝置發送該公開密鑰和證書，在只讀一次存儲單元內，從保密陣列接收通過要素被籤名的請求。認證系統為了檢查從只讀一次存儲器表明的數據是否可靠，對其進行加密後將其結果與加密陣列的一個數據進行比較，並且，利用樹數據來確認加密陣列是否對於公開密鑰進行證明。最後，認證者裝置使用證書檢查公開密鑰是否可靠。
文檔編號H04L9/32GK101488856SQ20081017710
公開日2009年7月22日 申請日期2008年12月5日 優先權日2008年1月17日
發明者卡米爾·維堯姆, 埃裡克·達爾門, 桶屋勝幸 申請人:株式會社日立製作所