驗證實體真實性或消息完整性的方法、系統、設備的製作方法

2023-07-22 09:42:51 5

專利名稱：驗證實體真實性或消息完整性的方法、系統、設備的製作方法
技術領域：
本發明涉及驗證實體真實性和/或消息的完整性和/或真實性的方法，系統，和設備。
發明人為Louis Guillou和JeanJacques Quisquater的專利EP 0 311470 B1描述了這種方法。此後將通過術語″GQ專利″或″GQ方法″表示他們的專利成果。此後術語″GQ2″，或″GQ2發明″或″GQ2技術″將被用來描述本發明。
根據GQ方法，一個被稱為″委託機構″的實體為各個被稱為″見證者″的實體分配一個身份並且計算其RSA籤名。在定製過程中，委託機構為見證者指定一個身份和籤名。其後，見證者聲明″這是我的身份；我知道該身份的RSA籤名″。見證者在不出示這個籤名的情況下證明他知道其身份的RSA籤名。通過委託機構分配的RSA公開鑑別密鑰，一個被稱為″控制者″的實體在沒有獲得其中的知識的情況下確定RSA籤名對應於所聲明的身份。使用GQ方法的機制在″不傳送知識″的情況下運行。根據GQ方法，見證者不知道委託機構為大量身份籤署的RSA私有密鑰。
上述GQ技術利用了RSA技術。然而雖然RSA技術嚴重依賴模數n的因數分解，但正如在針對實現RSA技術的各種數字籤名標準的所謂″乘法攻擊″中可以看到的，這種依賴的不具等效性，並且實際上差別很大。
GQ2技術有雙重目標一方面，是改進RSA技術的性能特性，另一方面是避免RSA技術的固有問題。有關GQ2私有密鑰的知識相當於有關模數n的因數分解的知識。任何對三元組GQ2的攻擊均導致對模數n的因數分解此時存在等效性。使用GQ2技術減少了籤名或自認證實體以及控制者實體的工作負載。通過在安全和性能方面對因數分解問題的良好使用，GQ2技術避免了RSA技術的缺點。
GQ方法實現了包括512位或更多位數的數值取模計算。這些計算涉及具有基本相同的長度、高到以216+1為指數的冪的數值。但是尤其是在銀行卡領域中，現有的微電子基礎設施均使用沒有算術協處理器的可自編程單片微處理器。涉及諸如GQ方法的方法中產生的多個算術應用的工作負載所需要的計算時間在某些情況下為使用銀行卡支付其購買的客戶帶來不便。回顧以往，當試圖增加支付卡的安全性時，銀行機構提出了一個特別難以解決的問題。事實上，必須研究兩個明顯矛盾的問題一方面，通過使用更加冗長和獨特的密鑰增加安全性，另一方面，防止工作負載為用戶帶來過長的計算時間。由於還有必要考慮到現有基礎設施和現有微處理器部件，這個問題變得尤其尖銳。
GQ2技術的目標是提供一個能夠解決這個問題並且仍然增加了安全性的解決方案。
方法更具體地，本發明涉及一個為控制者實體驗證下列內容的方法-一個實體的真實性和/或-與這個實體相關的消息M的完整性。
通過所有或部分下列參數或這些參數的派生參數完成這個證明-m對私有數值Q1，Q2，…Qm和公開數值G1，G2，…Gm(m大於或等於1)，-由上述f個素數p1，p2，…pf(f大於或等於2)的乘積構成的一個公開模數n，上述模數，上述私有和公開數值有以下類型的關係Gi.Qiv{1 mod n或Gi{Qivmod n其中v表示一個上述類型的公開指數v＝2k其中k是大於1的安全參數，上述m個公開數值Gi是少於f個素數p1，p2，…pf的m個基數g1，g2，…gm的平方gi2；通過滿足下面的條件產生上述f個素數p1，p2，…pf和/或上述m個基數g1，g2，…gm。第一條件根據第一條件，各個等式xv{gi2mod n在以n為模的整數環中有x的解。
第二條件根據第二條件，在Gi{Qivmod n成立的情況下，在通過把Qi提高成以n為模以k-1為秩的乘方獲得的m個數值qi中有一個qi不同於±gi(即有一個非無效解)。
根據第二條件，在Gi.Qiv{1 mod n成立的情況下，在通過把Qi模n的反置提高成以n為模以k-1為秩的乘方獲得的m個數值qi中有一個qi不同於±gi(即有一個非無效解)。
這裡應當注意，根據當前的符號表示，±gi表示數量gi和n-gi。第三條件根據第三條件，在2m個等式中間x2{gimod n(2)x2{-gimod n (3)其中至少有一個在以n為模的整數環中有x的解。
上述方法在下面定義的步驟中實現了被稱作見證者的實體。上述見證者實體具有f個素數pi和/或m個基數gi和/或素數的中國餘數的參數和/或公開模數n和/或m個私有數值Qi和/或私有數值Qi與公開指數v的f.m個分量Qi，j(Qi，j{Qimod pj)。
見證者計算以n為模數的整數環中的質問(commitment)R。通過以下操作計算各個質問-執行下列類型的運算R{rvmod n其中r是一個隨機數值並且0＜r＜n，-或
**通過執行下列類型的運算Ri{rivmod pi其中ri是一個與素數pi相關的隨機數值，其中0＜ri＜pi，各個ri屬於一個隨機數值集合{r1，r2，…rf}，**接著使用中國餘數方法。
見證者接收一或多個質問(challenge)d。每個質問d包括m個被稱作基本質問的整數di。根據各個質問d，見證者通過執行以下類型的運算計算一個應答D，-或者通過執行下列類型的運算D{r.Q1d1.Q2d2.…Qmdmmod n-或者**通過執行下列類型的運算Di{ri.Qi，1d1.Qi，2d2.…Qi，mdmmod pi**接著使用中國餘數方法。
該方法使得應答D的數量與質問d和確認R一樣多。每給數值R，d，D均構成一個被表示成{R，d，D}的三元組。證明一個實體的真實性的實例在一個實施例的第一變型中，基於本發明的方法被用來向一個被稱為控制者的實體證明一個被稱為證明者的實體的真實性。上述證明者實體包括見證者。上述證明者和控制者實體執行下列步驟·步驟1涉及確認R的操作每次見證者使用上述過程計算各個確認R。證明者向控制者發送所有或部分確認R。
·步驟2涉及質問d的操作在接收所有或部分確認R之後，控制者產生數量等於確認R的數量的質問d並且向證明者發送質問d。
·步驟3涉及應答D的操作見證者使用上述過程根據質問d計算應答D。
·步驟4涉及檢查的操作證明者向控制者發送各個應答D。第一種情況證明者已經發送一部分確認R如果證明者已經發送一部分確認R，則控制者在具有m個公開數值G1，G2，…Gm的情況下根據各個質問d和各個應答D計算一個重構確認R′，這個重構確認R′滿足以下類型的關係R′{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R′{Dv/G1d1.G2d2.…Gmdm.mod n.
控制者確定各個重構的確認R′還原出已經發送過來的所有或部分確認R。第二種情況證明者已經全部發送確認R如果證明者已經發送全部確認R，則控制者在具有m個公開數值G1，G2，…Gm的情況下確定各個確認R滿足以下類型的關係R′{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R′{Dv/G1d1.G2d2.…Gmdm.mod n.證明消息的完整性的案例在一個實施例的能夠與其第一變型配合使用的第二變型中，基於本發明的方法被用來為被稱為控制者實體的實體證明與被稱為證明者實體的實體相關的消息M的完整性。上述證明者實體包括見證者。
上述證明者和控制者實體執行下列步驟·步驟1涉及確認R的操作每次見證者使用上述過程計算各個確認R。
·步驟2涉及質問d的操作證明者使用一個散列函數h計算至少一個令牌T，其中散列函數的參數包括消息M和所有或部分確認R。證明者向控制者發送令牌T。在接收令牌T之後，控制者產生數量等於確認R的數量的質問d並且向證明者發送質問d。
·步驟3涉及應答D的操作見證者使用上述過程根據質問d計算應答D。
·步驟4涉及檢查的操作證明者向控制者發送各個應答D。控制者在具有m個公開數值G1，G2，…Gm的情況下根據各個質問d和各個應答D計算一個重構確認R′，這個重構確認R′滿足以下類型的關係R′{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R′{Dv/G1d1.G2d2.…Gmdm.mod n.
接著控制者使用一個散列函數h重構令牌T′，其中散列函數的參數包括消息M和所有或部分重構確認R′。接著控制者確定令牌T′與發送的令牌T相同。消息的數字籤名及其真實性證明在基於本發明的一個實施例的能夠與前面兩個實施例配合使用的第三變型中，基於本發明的方法被用來通過一個被稱為籤名實體的實體產生消息M的數字籤名。上述籤名實體包含見證者。籤名運算上述籤名實體執行籤名運算以便獲得包括以下內容的已籤名消息-消息M，-質問d和/或確認R，-應答D。
上述籤名實體通過實現下列步驟執行籤名運算步驟1涉及確認R的操作每次見證者使用上述過程計算各個確認R。
步驟2涉及質問d的操作籤名實體使用一個散列函數h獲得一個二進位序列，上述散列函數的參數包括消息M和各個確認R。籤名實體從這個二進位序列中提取其數量等於確認R的數量的質問d。
*步驟3涉及應答D的操作見證者使用上述過程根據質問d計算應答D。檢查運算為了驗證消息M的真實性，一個被稱作控制者的實體檢查已籤名消息。具有已籤名消息的上述控制者實體通過執行如下步驟來完成檢查運算，在控制者具有確認R，質問d，應答D的情況下如果控制者具有確認R，質問d，應答D，則控制者確定確認R，質問d和應答D滿足以下類型的關係R{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R{Dv/G1d1.G2d2.…Gmdm.mod n.
接著控制者確定消息M，質問d和確認R滿足散列函數d＝h(消息，R)在控制者具有質問d和應答D的情況下如果控制者具有質問d和應答D，控制者根據各個質問d和各個應答D重構滿足以下類型的關係的確認R′R′{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R′{Dv/G1d1.G2d2.…Gmdm.mod n.
接著控制者確定消息M和質問d滿足散列函數D＝h(消息，R′)在控制者具有確認R和應答D的情況下如果控制者具有確認R和應答D，則控制者使用散列函數並且重構d′d＇＝h(消息，R).
接著控制者設備確定確認R，質問d′和應答D滿足以下類型的關係R{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R{Dv/G1d1.G2d2.…Gmdm.mod n.系統本發明還涉及被用來向控制者伺服器驗證下列內容的系統-一個實體的真實性和/或-與這個實體相關的消息M的完整性。
通過所有或部分下列參數或這些參數的派生參數完成這個證明-m對私有數值Q1，Q2，…Qm和公開數值G1，G2，…Gm(m大於或等於1)，-由上述f個素數p1，p2，…pf(f大於或等於2)的乘積構成的一個公開模數n，上述模數，上述私有和公開數值有以下類型的關係Gi.Qiv{1 mod n或Gi{Qivmod n其中v表示一個下述類型的公開指數v＝2k其中k是大於1的安全參數，上述m個公開數值Gi是少於f個素數p1，p2，…pf的m個不同基數g1，g2，…gm的平方gi2；產生上述f個素數p1，p2，…pf和/或上述m個基數g1，g2，…gm以滿足下面的條件。第一條件根據第一條件，各個等式xv{gi2mod n(1)
可以被以n為模的整數環中的x求解。第二條件根據第二條件，在Gi{Qivmod n成立的情況下，在通過把Qi提高成以n為模以k-1為秩的乘方獲得的m個數值qi中有一個qi不同於±gi(即有一個非無效解)。
根據第二條件，在Gi.Qiv{1 mod n成立的情況下，在通過把Qi模n的反置提高成以n為模以k-1為秩的乘方獲得的m個數值qi中有一個qi不同於±gi(即有一個非無效解)。
這裡應當指出，根據當前的符號表示，±gi表示數量gi和n-gi。第三條件根據第三條件，在2m個等式中間x2{gimod n(2)x2{gimod n(3)其中至少有一個可以被以n為模的整數環中的x求解。
上述系統包括一個見證者設備，尤其是被包含在諸如基於微處理器的銀行卡形式的漫遊對象中的設備。見證者設備包括一個存儲器區段，上述存儲器區段包含f個素數pi和/或素數的中國餘數的參數和/或公開模數n和/或m個私有數值Qi和/或私有數值Qi與公開指數v的f.m個分量Qi，j(Qi，j{Qimod pj}。見證者設備還包括-隨機數值產品裝置，此後被稱作見證者設備的隨機數值產生裝置，-計算裝置，此後被稱作見證者設備計算確認R的裝置。
計算裝置使得能夠計算以n為模數的整數環中的確認R。通過以下方式計算各個確認執行下列類型的運算R{rvmod n其中r是隨機數產生裝置產生的隨機數值，並且0＜r＜n；或者執行下列類型的運算Ri{rivmod pi其中ri是一個與素數pi相關的隨機數值，其中0＜ri＜pi，各個ri屬於一個由隨機數值產生裝置產生的隨機數值集合{r1，r2，…rf}，並且接著使用中國餘數方法。
見證者設備還包括-接收裝置，此後被稱作接收見證者設備的質問d的裝置，上述接收裝置接收一或多個質問d；每個質問d均包括m個此後被稱作基本質問的整數di。
-計算裝置，此後被稱作計算見證者設備的應答D的裝置，上述計算根據各個質問d計算以下類型的應答D完成下列類型的運算D{r.Q1d1.Q2d2.…Qmdmmod n或者，完成下列類型的運算Di{ri.Qi，1d1.Qi，2d2.…Qi，mdmmod pi並且接著使用中國餘數方法。
見證者設備還包括發送一或多個確認R和一或多個應答D的發送裝置。應答D的數量與質問d和確認R一樣多，其中每組數值R，d，D構成一個被表示成{R，d，D}的三元組。證明一個實體的真實性的實例在實施例的第一變型中，基於本發明的系統被用來向一個被稱為控制者的實體證明一個被稱為證明者的實體的真實性。
上述系統包括一個與證明者實體相關的證明者設備。上述證明者設備通過互連裝置與見證者設備互連。尤其可以採取漫遊對象中的邏輯微電路的形式，例如基於微處理器的銀行卡中的微處理器的形式。
上述系統還包括一個與控制者實體相關的控制者設備。上述控制者設備尤其可以採取終端或遠程伺服器的形式。上述控制者設備包括連接裝置以便通過電子、電磁、光學或聲學方式，尤其是通過計算機通信網絡連接到證明者設備。
上述系統被用來執行下列步驟步驟1涉及確認R的操作每次見證者設備的計算確認R的裝置使用上述過程計算各個確認R。見證者設備包括通過互連裝置向證明者設備發送所有或部分確認R的發送裝置，此後被稱作見證者設備的發送裝置。證明者設備還包括通過連接裝置向控制者設備發送所有或部分確認R的發送裝置，此後被稱作證明者的發送裝置。步驟2涉及質問d的操作控制者設備包括質問產生裝置，該裝置在接收所有或部分確認R之後產生數量等於確認R的數量的質問d。控制者設備還包括通過連接裝置向證明者發送所有或部分質問d的發送裝置，此後被稱作控制者的發送裝置。*步驟3涉及應答D的操作接收見證者設備的質問的裝置通過互連裝置接收來自證明者設備的各個質問d。見證者設備計算應答D的裝置使用上述過程根據質問d計算應答D。*步驟4涉及檢查的操作證明者的發送裝置向控制者發送各個應答D。控制者設備還包括-計算裝置，此後被稱作控制者設備的計算裝置，-比較裝置，此後被稱作控制者設備的比較裝置。第一種情況證明者已經發送一部分確認R如果證明者的發送裝置已經發送一部分確認R，則控制者的計算裝置在具有m個公開數值G1，G2，…Gm的情況下根據各個質問d和各個應答D計算一個重構確認R′，這個重構確認R′滿足以下類型的關係R′{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R′{Dv/G1d1.G2d2.…Gmdm.mod n.
控制者設備的比較裝置將各個重構確認R′與接收的所有或部分確認R進行比較。第二種情況證明者已經全部發送確認R如果證明者的發送計算裝置已經發送全部確認R，則控制者設備的計算裝置和比較裝置在具有m個公開數值G1，G2，…Gm的情況下確定各個確認R滿足以下類型的關係R{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R{Dv/G1d1.G2d2.…Gmdm.mod n.證明消息的完整性的實例在一個能夠與第一變型實施例配合使用的第二變型實施例中，基於本發明的系統被用來向一個被稱為控制者的實體證明與一個被稱為證明者的實體相關的消息M的完整性。上述系統包括與證明者實體相關的證明者設備。上述證明者設備通過互連裝置與見證者設備互連。尤其可以採取漫遊對象中的邏輯微電路的形式，例如採取基於微處理器的銀行卡中的微處理器的形式。上述系統還包括一個與控制者實體相關的控制者設備。上述控制者設備尤其可以採取終端或遠程伺服器的形式。上述控制者設備包括連接裝置以便通過電子、電磁、光學或聲學方式，尤其是通過數據處理通信網絡連接到證明者設備。
上述系統被用來執行下列步驟步驟1涉及確認R的操作每次見證者設備的計算確認R的裝置使用上述過程計算各個確認R。見證者設備具有通過互連裝置向證明者設備發送所有或部分確認R的發送裝置，此後被稱作見證者設備的發送裝置。步驟2涉及質問d的操作證明者設備包括計算裝置，此後被稱作證明者的計算裝置，計算裝置使用一個散列函數h計算至少一個令牌T，其中散列函數的參數包括消息M和所有或部分確認R。證明者設備還包括通過連接裝置向控制者設備發送各個令牌T的發送裝置，此後被稱為證明者設備的發送裝置。控制者設備還具有質問產生裝置，該裝置在接收令牌T之後產生數量等於確認R的數量的質問d。控制者設備還具有通過連接裝置向證明者發送所有或部分質問d的發送裝置，此後被稱作控制者的發送裝置。*步驟3涉及應答D的操作接收見證者設備的質問的裝置通過互連裝置接收來自證明者設備的各個質問d。見證者設備計算應答D的裝置使用上述過程根據質問d計算應答D。*步驟4涉及檢查的操作證明者的發送裝置向控制者發送各個應答D。控制者設備還包括計算裝置，此後被稱作控制者設備的計算裝置，上述計算裝置在具有m個公開數值G1，G2，…Gm的情況下首先根據各個質問d和各個應答D計算一個重構確認R′，這個重構確認R′滿足以下類型的關係R′{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R′{Dv/G1d1.G2d2.…Gmdm.mod n.
接著使用一個散列函數h計算一個令牌T′，其中散列函數的參數包括消息M和所有或部分重構確認R′，控制者設備還具有將計算的令牌T′與接收的令牌T相比較的比較裝置，此後被稱為控制者設備的比較裝置。消息的數字籤名及其真實性證明在一個基於本發明的實施例的能夠與前兩個實施例中的一個和/或另一個配合使用的第三變型中，基於本發明的系統被用來證明一個被稱作籤名實體的實體對一個此後被稱為籤名消息的消息M實施的數字籤名。
已籤名消息包括-消息M，-質問d和/或確認R，-應答D。籤名運算上述系統包括與籤名實體相關的籤名設備。上述籤名設備通過互連裝置與見證者設備互連，並且尤其可以具有漫遊對象中邏輯微電路的形式，例如具有基於微處理器的銀行卡中微處理器的形式。
上述系統被用來執行下列步驟步驟1涉及確認R的操作每次見證者設備的計算確認R的裝置使用上述過程計算各個確認R。見證者設備包括通過互連裝置向籤名設備發送所有或部分確認R的發送裝置，此後被稱作見證者設備的發送裝置。步驟2涉及質問d的操作籤名設備包括計算裝置，此後被稱作籤名設備的計算裝置，上述計算裝置使用一個散列函數h計算一個二進位序列並且從這個二進位序列中提取出數量等於確認R的數量的質問d，其中散列函數的參數包括消息M和所有或部分確認R。*步驟3涉及應答D的操作見證者設備接收質問d的裝置通過互連裝置接收來自籤名設備的各個質問d。見證者設備計算應答D的裝置使用上述過程根據質問d計算應答D。見證者設備包括通過互連裝置向籤名設備發送應答D的發送裝置，此後被稱作見證者設備的發送裝置。檢查運算為了驗證消息M的真實性，一個被稱作控制者的實體檢查已籤名消息。
上述系統還包括一個與控制者實體相關的控制者設備。上述控制者設備尤其可以採取終端或遠程伺服器的形式。上述控制者設備包括連接裝置以便通過電子、電磁、光學或聲學方式，尤其是通過計算機通信網絡連接到籤名設備。
上述與籤名實體相關的籤名設備包括通過連接裝置向控制者設備發送已籤名消息的發送裝置，此後被稱為籤名設備的發送裝置。因而控制者設備具有一個包括以下內容的已籤名消息-消息M，-質問d和/或確認R，-應答D。
控制者設備包括-計算裝置，此後被稱作控制者設備的計算裝置，-比較裝置，此後被稱作控制者設備的比較裝置。在控制者設備具有確認R，質問d，應答D的情況下如果控制者設備具有確認R，質問d，應答D，則控制者設備的計算和比較裝置確定確認R，質問d和應答D滿足以下類型的關係R{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R{Dv/G1d1.G2d2.…Gmdm.mod n.
接著控制者設備的計算和比較裝置確定消息M，質問d和確認R滿足散列函數d＝h(消息，R)在控制者設備具有質問d和應答D的情況下如果控制者重構具有質問d和應答D，控制者的計算裝置根據各個質問d和各個應答D重構滿足以下類型的關係的確認R′R′{G1d1.G2d2.…Gmdm.Dvmod n
或以下類型的關係R′{Dv/G1d1.G2d2.…Gmdm.mod n.
接著控制者設備的計算和比較裝置確定消息M和質問d滿足散列函數d＝h(消息，R′)在控制者具有確認R和應答D的情況下如果控制者設備具有確認R和應答D，則控制者設備的計算裝置使用散列函數並且以下面方式計算出d′d＇＝h(消息，R)接著控制者設備的計算和比較裝置確定消息M，質問d′和確認R滿足以下關係R{G1d＇1.G2d′2.…Gmd′m.Dvmod n或以下類型的關係R{Dv/G1d＇1.G2d＇2.…Gmd′m.mod n.終端設備本發明還涉及與一個實體相關的終端設備。終端設備尤其可以採取漫遊對象的形式，例如基於微處理器的銀行卡中的微處理器的形式，終端設備被用來為控制者設備驗證下列內容-一個實體的真實性和/或-與這個實體相關的消息M的完整性。
通過所有或部分下列參數或這些參數的派生參數完成這個證明-m對私有數值Q1，Q2，…Qm和公開數值G1，G2，…Gm(m大於或等於1)，-由上述f個素數p1，p2，…pf(f大於或等於2)的乘積構成的一個公開模數n。
上述模數，上述私有和公開數值有以下類型的關係Gi.Qiv{1 mod n或Gi{Qivmod n
其中v表示一個下述類型的公開指數v＝2k其中k是大於1的安全參數。
上述m個公開數值Gi是少於f個素數p1，p2，…pf的m個不同基數g1，g2，…gm的平方gi2；產生上述f個素數p1，p2，…pf和/或上述m個基數g1，g2，…gm以滿足下面的條件。第一條件根據第一條件，各個等式xv{gi2mod n(1)可以被以n為模的整數環中的x求解。第二條件根據第二條件，在Gi{Qivmod n成立的情況下，在通過把Qi提高成以n為模以k-1為秩的乘方獲得的m個數值qi中有一個qi不同於±gi(即有一個非無效解)。
根據第二條件，在Gi.Qiv{1 mod n成立的情況下，在通過把Qi模n的反置提高成以n為模以k-1為秩的乘方獲得的m個數值Qiv中有一個Qiv不同於±gi(即有一個非無效解)。
這裡應當指出，根據當前的符號表示，±gi表示數量gi和n-gi。第三條件根據第三條件，在2m個等式中間x2{gimod n(2)x2{gimod n(3)其中至少有一個可以被以n為模的整數環中的x求解。
上述終端設備包括一個見證者設備，上述見證者設備包括一個存儲器區段，上述存儲器區段包含f個素數pi和/或素數的中國餘數的參數和/或公開模數n和/或m個私有數值Qi和/或私有數值Qi與公開指數v的f.m個分量Qi，j(Qi，j{Qimod pj}見證者設備還包括-隨機數值產品裝置，此後被稱作見證者設備的隨機數值產生裝置，-計算裝置，此後被稱作計算見證者設備的確認R的裝置，上述計算裝置計算見證者設備在以n為模的整數環中的確認R。
通過以下方式計算各個確認執行下列類型的運算R{rvmod n其中r是隨機數值產生裝置產生的隨機數值，並且0＜r＜n。
或者，執行下列類型的運算Ri{rivmod pi其中ri是一個與素數pi相關的隨機數值，其中0＜ri＜pi，各個ri屬於一個由隨機數值產生裝置產生的隨機數值集合{r1，r2，…rf}，並且接著使用中國餘數方法。
見證者設備還包括-接收裝置，此後被稱作接收見證者設備的質問d的裝置，上述接收裝置接收一或多個質問d，每個質問d均包括m個此後被稱作基本質問的整數di。
-計算裝置，此後被稱作計算見證者設備的應答D的裝置，上述計算根據各個質問d計算一個應答D，或者通過執行下列類型的運算D{r.Q1d1.Q2d2.…Qmdmmod n或者通過執行下列類型的運算Di{ri.Qi，1d1.Qi，2d2.…Qi，mdmmod pi並且接著使用中國餘數方法。
上述見證者設備還包括發送一或多個確認R和一或多個應答D的發送裝置。應答D的數量與質問d和確認R一樣多，其中每組數值R，d，D構成一個被表示成{R，d，D}的三元組。證明一個實體的真實性的實例在一個第一實施例變型中，基於本發明的終端設備被用來向一個被稱作控制者的實體證明一個被稱作證明者的實體的真實性。
上述終端設備包括與證明者實體相關的證明者設備。上述證明者設備通過互連裝置與見證者設備互連。尤其可以採取漫遊對象中的邏輯微電路的形式，例如基於微處理器的銀行卡中的微處理器的形式。
上述證明者設備還包括連接裝置以便通過電子、電磁、光學或聲學方式，尤其是通過數據處理通信網絡連接到與控制者實體相關的控制者設備。上述控制者設備尤其可以採取終端或遠程伺服器的形式。
上述終端設備被用來執行下列步驟*步驟1涉及確認R的操作每次見證者設備的計算確認R的裝置使用上述過程計算各個確認R。
見證者設備具有通過互連裝置向證明者設備發送所有或部分確認R的發送裝置，此後被稱作見證者設備的發送裝置。證明者設備還具有通過連接裝置向控制者設備發送所有或部分確認R的發送裝置，此後被稱作證明者的發送裝置*步驟2和3涉及質問d的操作，涉及應答D的操作見證者設備接收質問d的裝置通過控制者設備和證明者設備之間的連接裝置和證明者設備與見證者設備之間的互連裝置接收來自控制者設備的各個質問d。見證者設備計算應答D的裝置使用上述過程根據質問d計算應答D。*步驟4涉及檢查的操作證明者的發送裝置向執行檢查的控制者設備發送各個應答D。證明消息的完整性的實例在一個能夠與第一實施例配合使用的第二實施例變型中，基於本發明的終端設備被用來向一個被稱為控制者的實體證明與一個被稱為證明者的實體相關的消息M的完整性。使上述終端設備包括一個與證明者實體相關的證明者設備，上述證明者設備通過互連裝置與見證者設備連接。尤其可以採取漫遊對象中的邏輯微電路的形式，例如基於微處理器的銀行卡中的微處理器的形式。上述證明者設備包括連接裝置以便通過電子、電磁、光學或聲學方式，尤其是通過數據處理通信網絡連接到與控制者實體相關的控制者設備。上述控制者設備尤其可以採取終端或遠程伺服器的形式。
上述終端設備被用來執行下列步驟步驟1涉及確認R的操作每次見證者設備的計算確認R的裝置使用上述過程計算各個確認R。見證者設備具有通過互連裝置向證明者設備發送所有或部分確認R的發送裝置，此後被稱作見證者設備的發送裝置。
步驟2和3涉及質問d的操作，涉及應答D的操作證明者設備包括計算裝置，此後被稱作證明者的計算裝置，計算裝置使用一個散列函數h計算至少一個令牌T，其中散列函數的參數包括消息M和所有或部分確認R。證明者設備還具有通過連接裝置向控制者設備發送各個令牌T的發送裝置，此後被稱為證明者設備的發送裝置。
上述控制者設備在接收令牌T之後產生數量等於確認R的數量的質問d見證者設備接收質問d的裝置通過控制者設備和證明者設備之間的連接裝置和證明者設備與見證者設備之間的互連裝置接收來自控制者設備的各個質問d。見證者設備計算應答D的裝置使用上述過程根據質問d計算應答D。
*步驟4涉及檢查的操作證明者的發送裝置向進行檢查的控制者發送各個應答D。消息的數字籤名及其真實性證明在一個能夠與前兩個實施例中的任意一個配合使用的第三實施例變型中，基於本發明的終端設備被用來通過一個被稱作籤名實體的實體產生對一個此後被稱為籤名消息的消息M的數字籤名。
已籤名消息包括-消息M，-質問d和/或確認R，-應答D。
上述終端設備包括與籤名實體相關的籤名設備。上述籤名設備通過互連裝置與見證者設備互連。尤其可以採取漫遊對象中的邏輯微電路的形式，例如基於微處理器的銀行卡中的微處理器的形式。上述籤名設備包括連接裝置以便通過電子、電磁、光學或聲學方式，尤其是通過數據處理通信網絡連接到與控制者實體相關的控制者設備。上述控制者設備尤其可以採取終端或遠程伺服器的形式。籤名運算上述終端設備被用來執行下列步驟*步驟1涉及確認R的操作每次見證者設備的計算確認R的裝置使用上述過程計算各個確認R。見證者設備包括通過互連裝置向籤名設備發送所有或部分確認R的發送裝置，此後被稱作見證者設備的發送裝置。
*步驟2涉及質問d的操作籤名設備包括計算裝置。此後被稱作籤名設備的計算裝置。上述計算裝置使用一個散列函數h計算一個二進位序列並且從這個二進位序列中提取出數量等於確認R的數量的質問d，其中散列函數的參數包括消息M和所有或部分確認R。
*步驟3涉及應答D的操作接收質問d的裝置通過互連裝置接收來自籤名設備的各個質問d。見證者設備計算應答D的裝置使用上述過程根據質問d計算應答D。見證者設備包括通過互連裝置向籤名設備發送應答D的發送裝置，此後被稱作見證者設備的發送裝置。控制者設備本發明也涉及一個控制者設備。控制者設備尤其可以採取與控制者實體相關的終端或遠程伺服器的形式。控制者設備被用來檢查以下內容-一個實體的真實性和/或-與這個實體相關的消息M的完整性。
通過所有或部分下列參數或這些參數的派生參數完成這個證明-m對公開數值G1，G2，…Gm(m大於或等於1)，-由上述f個素數p1，p2，…pf(f大於或等於2)的乘積構成的一個對於控制者設備和相關控制者實體是未知數的公開模數n。
上述模數，上述私有和公開數值有以下類型的關係Gi…Qiv{1 mod n或Gi{Qivmod n其中v表示一個下述類型的公開指數v＝2k其中k是大於1的安全參數。
上述m個公開數值Gi是少於f個素數p1，p2，…pf的m個不同基數g1，g2，…gm的平方gi2；產生上述f個素數p1，p2，…pf和/或上述m個基數g1，g2，…gm以滿足下面的條件。第一條件根據第一條件，各個等式xv{gi2mod n(1)可以被以n為模的整數環中的x求解。第二條件根據第二條件，在Gi{Qivmod n成立的情況下，在通過把Qi提高成以n為模以k-1為秩的乘方獲得的m個數值qi中有一個qi不同於±gi(即有一個非無效解)。
根據第二條件，在Gi…Qiv{1 mod n成立的情況下，在通過把Qi模n的反置提高成以n為模以k-1為秩的乘方獲得的m個數值qi中有一個qi不同於±gi(即有一個非無效解)。
這裡應當指出，根據當前的符號表示，±gi表示數量gi和n-gi。第三條件根據第三條件，在2m個等式中間x2{gimod n (2)x2{gimod n (3)其中至少有一個可以被以n為模的整數環中的x求解。證明一個實體的真實性的實例在一個第一實施例變型中，基於本發明的控制者設備被用來證明一個被稱作證明者的實體和一個被稱作控制者的實體的真實性。
上述證明者設備包括連接裝置以便通過電子、電磁、光學或聲學方式，尤其是通過數據處理通信網絡連接到與證明者實體相關的證明者設備。
上述控制者設備被用來執行下列步驟步驟1和2涉及確認R的操作，涉及質問d的操作上述控制者設備還具有通過連接裝置接收所有或部分來自證明者設備的確認R的裝置。
控制者設備包括質問產生裝置，該裝置在接收所有或部分確認R之後產生數量等於確認R各個數量的各個質問d，其中各個質問d均包括m個此後被稱作基本質問的整數di。
控制者設備還包括通過連接裝置向證明者發送所有或部分質問d的發送裝置，此後被稱作控制者的發送裝置。
*步驟3和4涉及應答D的操作，涉及檢查的操作控制者設備還包括-通過連接裝置接收來自證明者設備的應答D的裝置，
-計算裝置，此後被稱作控制者設備的計算裝置，-比較裝置，此後被稱作控制者設備的比較裝置。第一種情況證明者已經發送一部分確認R如果證明者的接收裝置已經接收一部分確認R，則控制者設備的計算裝置在具有m個公開數值G1，G2，…Gm的情況下根據各個質問d和各個應答D計算一個重構確認R′，這個重構確認R′滿足以下類型的關係R′{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R′{Dv/G1d1.G2d2.…Gmdm.mod n.
控制者設備的比較裝置將各個重構確認R′與接收的所有或部分確認R進行比較。第二種情況證明者已經全部發送確認R如果證明者的發送計算裝置已經接收全部確認R，則控制者設備的計算裝置和比較裝置在具有m個公開數值G1，G2，…Gm的情況下確定各個確認R滿足以下類型的關係R′{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R′{Dv/G1d1.G2d2.…Gmdm.mod n.證明消息的完整性的實例在一個能夠與第一實施例配合使用的第二實施例變型中，基於本發明的控制者設備被用來證明與一個被稱為證明者的實體相關的消息M的完整性。
上述證明者設備包括連接裝置以便通過電子、電磁、光學或聲學方式，尤其是通過數據處理通信網絡連接到與證明者實體相關的證明者設備。
上述控制者設備被用來執行下列步驟
*步驟1和2涉及確認R的操作，涉及質問d的操作上述控制者設備具有通過連接裝置接收來自證明者設備的令牌T的裝置。控制者設備具有質問產生裝置，該裝置在接收令牌T之後產生數量等於確認R的數量的質問d，其中各個質問d均包括m個此後被稱作基本質問的整數di。控制者設備還具有通過連接裝置向證明者發送所有或部分質問d的發送裝置，此後被稱作控制者的發送裝置。
*步驟3和4涉及應答D的操作，涉及檢查的操作上述控制者設備還包括通過連接裝置接收來自證明者設備的應答D的裝置。上述控制者設備還包括計算裝置，此後被稱作控制者設備的計算裝置，上述計算裝置在具有m個公開數值G1，G2，…Gm的情況下首先根據各個質問d和各個應答D計算一個重構確認R′，這個重構確認R′滿足以下類型的關係R′{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R′{Dv/G1d1.G2d2.…Gmdm.mod n.
接著使用一個散列函數h計算一個令牌T′，其中散列函數的參數包括消息M和所有或部分重構確認R′。
控制者設備還具有將計算的令牌T′與接收的令牌T相比較的比較裝置，此後被稱作控制者設備的比較裝置。消息的數字籤名及其真實性證明在一個能夠與前兩個實施例中的一個或另一個配合使用的第三實施例變型中，通過利用一個被稱作控制者的實體檢查一個籤名消息，基於本發明的控制者設備被用來證明消息M的真實性。
通過一個與具有散列函數h(消息，R)的籤名實體相關的籤名設備發送的籤名消息包括-消息M，-質問d和/或確認R，-應答D。檢查運算上述籤名設備包括連接裝置以便通過電子，電磁，光學或聲學方式，尤其是通過數據處理通信網絡連接到與籤名實體相關的籤名設備。上述控制者設備通過連接裝置從籤名設備接收籤名消息。
控制者設備包括-計算裝置，此後被稱作控制者設備的計算裝置，-比較裝置，此後被稱作控制者設備的比較裝置。
*在控制者設備具有確認R，質問d，應答D的情況下如果控制者設備具有確認R，質問d，應答D，則控制者設備的計算和比較裝置確定確認R，質問d和應答D滿足以下類型的關係R{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R{Dv/G1d1.G2d2.…Gmdm.mod n.
接著控制者設備的計算和比較裝置確定消息M，質問d和確認R滿足散列函數d＝h(消息，R)*在控制者設備具有質問d和應答D的情況下如果控制者設備具有質問d和應答D，控制者設備的計算裝置可以根據各個質問d和各個應答D計算出滿足以下類型的關係的確認R′R′{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R′{Dv/G1d1.G2d2.…Gmdm.mod n.
接著控制者設備的計算和比較裝置確定消息M和質問d滿足散列函數d＝h(消息，R′)在控制者設備具有確認R和應答D的情況下
如果控制者設備具有確認R和應答D，則控制者設備的計算裝置使用散列函數並且以下面方式計算出d′d′＝h(消息，R)接著控制者設備的計算和比較裝置確定消息M，質問d′和確認R滿足以下關係R{G1d′1.G2d′2.…Gmd′m.Dvmod n或以下類型的關係R{Dv/G1d′1.G2d′2.…Gmd′m.mod n.對本發明的描述GQ方法的目標是對實體、消息和消息的數字籤名一起進行動態認證。這些都屬於″不傳送知識″的方法。一個實體證明其知道一個或若干個私有數值。另一個實體進行檢查；該實體知道對應的公開數值。證明實體希望在不出示私有數值的情況下得到檢查實體的信任以便根據需要以任意多次使用上述私有數值。
各個GQ方法均依賴於一個由秘密的大素數組成的公開模數。一個公開指數v和一個公開模數n共同構成一個驗證密鑰v，n，即″提高到模數n的v次冪″，並且通過一個或若干個類型相同的通用等式直接實現Gi{Qivmod n或反置GixQiv{1 mod n。該類型對檢查實體而不是證明實體內部的計算操作有影響；事實上安全分析混淆了兩個類型。與一個公開數值G和一個私有數值Q關聯的各個通用等式共同構成一對數值{G，Q}。總之，各個GQ方法針對相同密鑰v，n實現了一或若干對數值{G，Q}。
GQ方法的一個被稱作GQ1的經典版本使用了RSA數字籤名機制。驗證密鑰v，n是一個RSA公開密鑰，其中奇指數v最好是一個素數。各個GQ1方法通常使用單獨一對數值{G，Q}根據一個屬於RSA數字籤名技術不可分割的部分的格式機制通過鑑別數據推斷出公開數值G。私有數值Q或其反置模數n是鑑別數據的一個RSA籤名。證明實體出示有關其自身鑑別數據的RSA籤名的知識並且無論使用多少次這個證明不會暴露籤名，從而保守了秘密。
GQ1方法通常實現兩個級別的密鑰為一個對實體進行授權的機構保留RSA私有籤名密鑰，其中上述實體通過鑑別數據區分彼此。這種機制被稱作″基於身份″的機制。因而，晶片卡的一個發射器使用其用於各個卡的發射的RSA私有密鑰計算一個被記錄成卡中的各種私有密鑰的私有數值Q；或者一個計算機網絡上的客戶端在進入各個會話時使用其RSA私有密鑰計算一個在會話期間會被當成客戶端的短期私有密鑰的私有數值Q。證明實體，晶片卡或客戶端在會話期間知道其鑑別數據的RSA籤名；它們不知道在密鑰層次上處於更高一級的RSA私有密鑰。但是，在一個機構的層次上使用一個768位模數通過GQ1方法對實體進行動態認證所需的工作負載與在各個實體的層次上使用一個512位模數和三個素數通過RSA對實體進行動態認證的工作負載幾乎相同，這允許證明實體在計算各個素數乘積的取模結果之前通過計算各個素數的取模結果來使用中國餘數技術。
然而，一個機構和受信實體之間的密鑰層次並不是必須的。可以通過一個屬於證明實體的模數使用GQ1方法，這使得能夠使用中國餘數技術減少證明實體的工作負載，並且不根本改變檢查實體的工作負載，另外一個證明實體層次上的模數可以比一個機構層次上的模數更短，例如512位比768位。
當實體知道其自身模數的素數時，為何要使用RSA數字籤名機制？GO方法的另一個被稱作基本GQ2的版本直接處理模數n的因數分解問題。在這種情況下″直接″意味著″不需要RSA籤名″。GQ2的目標是減少證明實體和檢查實體的工作負載。證明實體出示有關其自身模數的分解的知識並且這個證明不暴露分解，，從而保守了秘密，所以能夠根據需要被經常使用。GQ2協議的安全性等價於模數的因數分解的安全性。
各個證明實體具有其自身的模數n。各個GQ2機制實現了一個參數k，即一個大於1的較小數值，從而固定一個公開指數v＝2k和一或若干對數值{G1，Q1}到{Gm，Qm}。各個公開數值Gi是一個大於1並且被稱作″基數″的較小數值gi的平方。所有證明實體均可以使用相同的公開數值G1到Gm。模數n的因數分解和私有數值Q1到Qm，n則在密鑰層次中處於相同的層次上。通過兩個必要和充分條件定義各組基本GQ2密鑰-對於各個基數，兩個等式x2{±gimod n在以n為模的整數環中均不具有x的解，即數值±gi是兩個n為模的的非二次餘數。
-對於各個基數，等式xv{gi2mod n在以n為模的整數環中具有x的解，其中V＝2k。私有數值Qi或其反置模數n是這些解中的任意一個。
考慮第二條件，為了使數值±gi是兩個以n為模的非二次餘數，模數n必須包括至少兩個恆等於3(mod4)的素數，但gi的勒讓德符號則不同於此。因此，由其中最多僅有一個恆等於3(mod4)的素數組成的任意模數不允許建立一組基本GQ2密鑰，這特許素數恆等於3(mod4)。因而通過隨機取出大素數，顯然只有一半恆等於3(mod4)並且另一半恆等於1(mod4)。結果，許多在使用的RSA模型不能建立一組基本GQ2密鑰。
我們這裡介紹克服這種限制以便能夠針對任意模數，尤其是任意RSA模數使用GQ2技術的通用化GQ密鑰集合它們取決於兩個必要充分原則。
第一原則還原了第二基本GQ2條件-對於各個基數g1到gm，等式xv{gi2mod n在以n為模的整數環中具有x的解，其中V＝2k。
由於私有數值Q或其反置模數n是等式的一個解，以n為模的連續k-1次乘方將其轉換成一個數值qi，數值qi是以n為模的整數環中的Gi的平方根。根據數值qi是等於兩個數值gi或n-gi中的一個，還是不同於兩個數值gi和n-gi，可以確定其是否無效解。當數值qi是非無效解時，整除qi2-gi2的n不整除qi-gi或qi+gi。因而任意非無效數值q均暴露了模數n的一個分解。
n＝pgcd(n，qi-gi)xpgcd(n，qi+gi)第二原則加寬了第一基本GQ2條件
-在數值q1至qm中至少有一個數值qi是非無效解。
應當注意，如果存在一個數值q+並且數值±gi是以n為模的整數環中的兩個非二次餘數，則數值qi肯定是非無效解。因而基本GQ2密鑰集合肯定是通用化GQ2密鑰集合的一部分，這使得能夠使用任意的模數，即對於任意的大素數成分，無論是恆等於3(mod4)還是恆等於1(mod4)，其中至少有兩個是不同的。另一方面，許多通用化GQ2密鑰集合不是基本GQ2密鑰集合。各個通用化GQ2密鑰集合基於下面情況中的一種-當2xm個數值±g1到±gm全部是非二次餘數時，這是一個基本GQ2密鑰集合。
-當在2xm個數值±g1到±gm中至少有一個二次餘數時，這不是一個補充GQ2密鑰集合，所知的是一個補充GQ2密鑰集合。
本發明涉及補充GQ2密鑰集合，根據定義這些通用化GQ2密鑰集合不是基本GQ2密鑰集合。除了前面兩個原則之外，這種集合必須滿足第三個原則。
-在2xm個數值±g1到±gm中有至少一個二次餘數。
為了評估問題和理解我們提供的解決方案，即本發明，我們首先分析一個非無效數值q暴露的模數n的分解，並且接著回顧中國餘數技術，和伽羅瓦域CG(p)中有關秩的概念；並且接著研究CG(p)中的″開方」函數和CG(p)中對二次餘數″求平方根」的函數；最後分析上述三個原則的適用性。對模數分解的分析就象模數n被分解成f個素數p1到pf那樣，以n為模的整數環被分解成f個伽羅瓦域CG(p1)到CG(pf)。在每個域中有兩個單平方根，即±1。在整數環中，有2f個單平方根。各個私有數值Q1到Qm均定義了一個數值i=qi/gi(modn)]]>，該數值是整數環的2f個單平方根中的一個；即n分割 當qi是無效數值時，即當i=1]]>時，n分割Δi-1或Δi+1並且 不暴露模數n的分解。
當qi是非無效數值時，即當 時，n不分割Δi-1或Δi+1並且暴露了一個通過各個域中的 值得到的分解，n=pgcd(n,i-1)xpgcd(n,i+1)]]>一方面是分割 的素數，另一方面是分割 的素數。
數值q的乘法合成的規則檢查。兩個數值{q1，q2}給出了一個複合數q1×q2(mod n)。
-當q1是非無效數值並且q2是無效數值時，複合數q1×q2(mod n)是非無效數值；它暴露了與q1相同的分解。
-當q1和q2是非無效數值並且1=2]]>時，複合數q1×q2(mod n)是無效數值；它不暴露任何分解。
-當q1和q2是非無效數值並且12]]>時，複合數q1×q2(mod n)是非無效數值；它暴露了一個第三分解。
三個數值{q1，q2，q3}提供了四個複合數{q1×q2，q1×q3，q2×q3，q1×q2×q3(mod n)}，總共有7個數值；因而m個數值提供2m-m-1個複合數並且總共有2m-1個數。
現在我們考慮一個通用化GQ2密鑰集合，其中包括i個基數g1到gi和i個私有數值Q1到Qi，從而提供i個數值q1到qi和i個均屬於單根的數值 到 。我們通過一個提供數值qi+1和根 的私有數值Qi+1嘗試考慮另一個基數gi+1。
*總共2i+1-1個數值包括下面各個情況下的所有非無效數值。
-根 是無效數值並且至少一個根 至 是非無效數值。
-根 是非無效數值並且在2xi個根 至 中出現。
*如果根 是非無效數值並且沒有在2xi個根 到 中出現，則出現qi+1的各個複合數均是非無效數值。
因此，當在m個數值q1到qm中至少有一個是非無效數值，則總共2m-1個數值中有超過一半的數值是非無效數值。
根據定義，當2l-l-1個對應的複合數均是非無效數值時，稱l＜f個非無效數值{q1，q2，…ql}相對於模數n是獨立的，即總共2l-1個數值均是非無效數值。因而這2l-1個數值中的每一個數值均暴露了模數n的一個不同分解。
-當f個素數不同時，模數n有2f-1-1個分解。因而如果f-1個數值q是獨立的，則在2f-1-1個分解和總共2f-1-1個包括f-1個獨立數值和2f-1-f個對應複合數的數值之間存在一個雙-單義(bi-univocal)對應關係。
*中國餘數對於兩個數值a和b，0＜a＜b，其間的素數，和兩個從0到a-1的數值Xa和從0到b-1的數值Xb；涉及確定0到axb-1中的唯一數值使得Xa{X(mod a)並且Xb{X(mod b)。數值x{{b(mod a)}-1(mod a)是中國餘數參數。以下是基本中國餘數操作x{Xb(mod a)y＝Xa-x；如果y為負數，用y+a替代yz{axy(mod a)X＝zxb+Xb最初X＝中國餘數(Xa，Xb)當按照升序從最小的p1到最大的pf排列f個素數時，中國餘數參數如下所示(比素數少1，即f-1)-第一個參數是x{(p2(mod p1))-1(mod p1)。
-第二個參數是E{(p1×p2(mod p3))-1(mod p3)。
-第i個參數是O{(p1×…pi-1(mod pi))-1(mod pi)。
-依此類推在f-1個基本操作中，根據f個分量X1到Xf，Xj從0到pj-1構成的任意集合產生一個從0到n-1的數值-一個具有第一參數的第一結果(mod p1×p2)，-一個具有第二參數的第二結果(mod p1×p2×p3)，-一個具有最後參數的最後結果(mod p1×p2×…pf)。
最初指定素數p1到pf，以n為模的整數環中的各個元素具有兩個等價的表示-f個數值X1到Xf，一個素數分量Xj{X(mod pj)，
-一個從0到n-1的數值X，X＝中國餘數(X1，X2，…Xf)。
CG(p)中數值的秩-令p為一個奇素數並且a是一個小於p的數值，即0＜a＜p。根據定義，a相對於p的秩是由{xi＝a；則對於iτ1，xi+1{aυxi(mod p)}定義的序列{X}的周期。通過應用費馬定理，我們得到xi+p{apυxi{aυxi{xi+1(mod p)。因而數值a相對於素數p的秩是p-1或p-1的一個除數。
例如，當(p-1)/2是一個奇素數p′時，伽羅瓦域CG(p)包含秩為1的數值即1，一個秩為2的數值即-1，p′-1個秩為p′的數值和p′-1個秩為2υp＇＝p-1的數值。在CG(p)中，任何秩為p-1的數值均是一個「生成器」。如此稱呼的原因是，CG(p)中一個生成器的連續次冪，即序列{X}中下標為1到p′-1的項值構成CG(p)的所有非零元素的一個排列。
令y是CG(p)的一個生成器。根據i和p-1求數值y′(mod y)的秩。當i與p-1互素時，這個秩為p-1。當i整除p-1時，秩為(p-1)/i。總之，秩為(p-1)/lgcd(p-1，i)(lgcd＝最大公約數)。
根據定義，歐拉函數M(n)是小於n並且與n互素的數的數量。在CG(p)中，有M(p-1)個生成器。
為了說明，秩有助於理解RSA的基礎。模數n是f個素數p-1到p-f的乘積，其中fτ2。對於從p1到pf的各個素數pi，公共指數e應當與pi-1互素。現在，密鑰e，pj觀察CG(pj)的元素的秩它排列CG(pj)的元素；存在一個儘可能小的數值dj，使得p-1整除eυdj-1。密鑰dj，pj反置CG(pj)的元素的排列。這f個分別處於各個域CG(p1)到CG(pf)中的排列被公開密鑰e，n概括出的RSA排列表示成以n為模的整數環。存在一個通常儘可能小的數值d，使得(p1-，p2-1，…pf-1)的最小公倍數(scm)整除dυe-1。對於從p1到pf的各個素數pj，存在dj{d(mod pj-1)。被公開密鑰e，n概括的RSA排列被私有密鑰d，n反置。
CG(p)中的乘方-定義一個數值t使得p-1可被2t整除但不可被2t-1整除。各個大素數均出現在一個並且唯一一個類目中t＝1，t＝2，t＝3，t＝4，等等。如果考慮足夠多的連續素數，大約2個中有一個出現在第一類目中，其中p與3(mod 4)同餘，4個中有一個出現在第二類目中，其中p與5(mod 8)同餘，8個中有一個出現在第三類目中，其中p與9(mod 16)同餘，16個中有一個出現在第四類目中，其中p與17(mod 32)同餘，等等；平均起來，2t個中有一個出現在第n類目中，其中p與2t+1(mod 2t+1)同餘。
由於數值x和p-x在CG(p)中有相同的乘方，密鑰2，p不排列CG(p)。CG(p)中的函數「求乘方」可以被表示成一個定向圖，其中域內的各個非零元素有其位置。根據各個元素的秩的奇偶性將圖的結構分析成分支和圓圈。
-設置零元素。這個為0。不為沒有被其它元素涉及到的零元素定義秩；零元素被隔離。
-設置單元元素。這個為1，唯一秩為1的元素。CG(p)中所有一的根均位於涉及1的分支內。令y是CG(p)的除二次餘數之外的任何餘數；密鑰p-1)/2t，p將y變換成-1的第2t-1次原根，原根被表示成b；因而我們具有y(p-1)/2{-1(mod p)。因而在CG(p)中，b的指數為1到2t-1的各個冪是一的2t-1個不等於1的根它們構成涉及1的分支。
-具有偶數秩的任何元素的乘方是另一個秩被2整除的元素。因而各個具有偶數秩的元素被放到一個分支中；各個分支包含一個可被2整除但不可被4整除的秩數，接著，如果tτ2，包含2個可被4整除但不可被8整除的秩數，如果t，3，包含4個可被8整除但不可被16整除的秩數，如果t，4，包含8個可被16整除但不可被32整除的秩數，等等。所有分支類似於涉及1的分支；各個分支的2t-1個葉子是非二次餘數；每個分支包含2t-1個元素並且涉及一個具有奇數秩的元素；存在(p-1)/2t個均具有相同長度t的分支。
-除單位元素之外具有奇數秩的任何元素的乘方是另一個具有相同秩的元素。密鑰2，p排列(p-1)/2t個具有奇數秩的元素構成的集合。排列被分解成排列圓圈。圓圈的數量取決於(p-1)/2t的分解。對於(p-1)/2t的各個除數p′，存在一個包含M(p′)個具有秩p′的元素。回憶一下，根據定義，歐拉函數M(p′)是小於p′並且與p′互素的數值的數量。例如，當p′等於(p-1)/2t時，互素，p′-1個以p′為秩的數值構成一個大的排列圓圈。


圖1A-1D分別針對p與3(mod 4)同餘，p與5(mod 8)同餘，p與9(mod 16)同餘和p與17(mod 32)同餘圖解了一個圖段。
-白圓圈表示分支中的葉子；這些是非二次餘數。
-灰圓圈表示分支中的結點；這些是具有偶數秩的二次元素。
-圓圈中的結點被表示成黑圓圈；這些是具有偶數秩的二次元素。
CG(p)中的平方根-已知a是CG(p)的一個二次餘數，看看如何計算等式x2{a(mod p)，即CG(p)中「求平方根」的一個解。當然，有許多種得到相同結果的方式；可以參考Henri Cohen的著作，計算代數理論教程，31-36頁，大學生數學系列教材138卷(GTM)138，Springer，Berlin 1993年出版。
數值s＝(p-1+2t)/2t+1提供一個密鑰s，p)，即(p+1)/4，p，當p與3(mod 4)同餘時，(p+3)/8，p，當p與5(mod 8)同餘時，(p+7)/16，p，當p與9(mod 16)同餘時，(p+15)/32，p，當p與17(mod 32)同餘時，等等。
-密鑰s，p將一個圓圈的任何元素變換成圓圈中前面的元素。當a具有偶數秩時，是具有奇數秩的解，表示成w。在CG(p)中，w2/a等於a至(2υ(p-1+2t)/＜2t+1)-1＝(p-1)/2t的冪。另一個解具有偶數秩；即p-w。
-通常，密鑰s，p將一個第一逼近中的任何二次餘數變換成一個稱作r的解。由於a是一個二次餘數，密鑰2t-1，p當然將r2/a變換成1。為了逼近a的平方根，取r2/a(mod p)的2t-2次冪以便得到+1或-1。如果結果為+1則新逼近的餘數為r，否則如果結果為-1則餘數為bυr(mod p)，已知p表示域CG(p)中1的任何2t次原根。因而密鑰2t-2，p將新逼近變換成1。如果必要也可以通過使用密鑰2t-3，p並且乘以b2(mod p)來進行逼近，等等。
下面的算法對等待求解。它使用前面定義的數值a，b，p，r和t和兩個變量c表示連續校正，w表示連續逼近。在算法開始時，c＝b並且w＝r。在計算結束時，兩個解是w和p-w。
對於從t-2到1的i，重複下列序列-對數值w3/a(mod p)應用密鑰2t，p以獲得+1或-1。
-當得到-1時用wυc(mod p)取代w。
-用c2(mod p)取代c。
原理的可用性-根據定義我們指出當等式xΘ{g2(mod p)在域CG(x)內有x的解時參數k，基數g和素數p是兼容的，其中指數Θ為2k。數值k和g較小但大於1。數值p是大素數。
-當t＝1，即p{3(mod 4)時，等式有兩個解。
-當t＝2，即p{5(mod 8)時，根據g相對於p的勒讓德符號，如果(g～p)＝+1則等式有4個解，如果(g～p)＝-1則等式沒有任何解。
-當t＞2，即p{1(mod 8)時，令數值u使得2u整除公開數值G＝g2相對於p的秩並且使得2u+1不整除這個秩；因而u等於從0到t-1的數值中的一個。如果u＞0並且k+u＞t則等式沒有解；如果k+uδt則等式有2k個解；如果u＝0並且k＞t則有2t個解。
因而根據G是在圓圈內還是在一個分支內的適當位置上，存在兩種兼容性。
-當G在圓圈內，即u＝0時，無論k的值如何，在圓圈內有一個具有奇數秩的解並且存在具有偶數秩並且散布在Δ＝min(k，t)個涉及圓圈的連續分支內的解，即2Δ個解。圖2A圖解了這種情況，其中kτt＝3，即一個與9(mod 16)同餘的素數，這表明u＝0。
-當G位於一個分支內一個適當位置上，即u＞0並且u+kδt時，存在2k個均具有偶數秩並且位於分支內的解。圖2B圖解了這種情況。
指定一個參數k，因而根據t的值是小於k還是大於或等於k，存在兩種素數。
一對於任何素數pj，例如t＜k，各個Gi應當位於圓圈內，並且在涉及Gi的分支內沒有解。定義一個數值 ，根據gi還是-gi位於圓圈內該數值為+1或-1。對於m個數值 到 而言這是沒有選擇的。圖3A圖解了t＜k的情況Gi位於一個圓圈內，其中一個素數pj與9(mod16)同餘，即u＝0，t＝3並且k＞3。
-對於任何使得tτk的素數pj，各個Gi應當使得u+kδt，即或者在一個圓圈內並且u＝0，或者在一個分支的適當位置上並且1δuδt-k。定義一個數值 ，根據Qi，j位於圖中涉及gi還是-gi的部分內該數值為+1或-1。對於m個數值 到 中各個數值而言存在一個選擇；可以單獨將各個數值 從一個值切換成另一個值。圖3B圖解了tτk的情況Gi位於一個圓圈內，其中一個素數pj與17(mod 32)同佘，即u＝1，t＝4並且k＝3。
由f個分量{i,1i,1f]]>構成的各個集合是CG(pj)中1的平方根。根據f個分量是否相等，這個根是無效解或非無效解。接著規定f個分量構成的集合是否固定，這表明數值qi是否無效數值。因而當一個數值qi是非無效數值時，由f個分量{i,1i,1f}]]>構成的集合概括了模數的分解。因而可以在計算私有分量Qi，j之前測試原則。
-當一個公開數值Gi位於針對素數pj的圓圈內時，根據gi還是-gi位於圓圈內數值 為+1或-1。當pj{3(mod 4)時，這是一個勒讓德符號i,j=(gi~pj).]]>-當一個公開數值Gi位於一個針對素數pj的分支內適當位置上時，通過計算私有分量Qi，可以確定為 指定的值。
密鑰集合的產生-指定一個參數k，存在兩個策略。
-生成器均需要f個素數以便確定m個基數。檢查第一素數2，3，5，7，…以評估其與f個大素數p1到pf中每個素數的兼容性。儘管g＝2不與p{5(mod 8)兼容，但2可以進入一個基數的成分內。實際上，當兩個數值位於一個分支內的一個位置上時，由於平方使圓圈更接近，所以其乘積更接近圓圈。因而通過組成單獨考慮均不適當的數值可以獲得一個基數。
-或者，生成器需要m個基數和模數的特徵，使得一個位長(例如512，768，1024，1536，2048)和若干個連續到1的位具有強權重(例如1，8，16，24，32)以便確定fτ2個素數。表示成G1，G2，…Gm的基數通常出現在第一素數2，3，5，7，11…中間，或者是第一素數的組合。除非專門指出，這些是前m個素數G1＝2，G2＝3，G3＝5，G4＝7，…。注意p{5(mod 8)不與G＝2兼容。模數n將是f個具有接近長度，即為被f整除的模數分配的長度的素數的乘積。
第一原則-參數k，各個素數p1到pf和從g1到gm的各個基數應當兼容。定義一個數值h，使得2h整除g相對於p的秩，但2h+1不整除這個秩。為了計算數值h，下面過程使用勒讓德符號(g～p)和一個數值b，CG(p)中1的第2t次原根。
-如果(g～p)＝+1並且t＝1，返回″h＝0″。
-如果(g～p)＝+1並且t＞1，對G應用密鑰(p-1+2t)/2t+1，p到以便獲得一個被稱作w的結果。
-如果w＝+g，返回″h＝0″。
-如果w＝p-g，返回″h＝1″。
-否則，將c設置到b並且針對從t-1到2的i，-對w/g(mod p)應用密鑰2i，p以便獲得ρ1，-如果-1，將h設置成i並且用wυc(mod p)替換w，-用c2(mod p)替換c。
-返回″從2到t-1的h數值″。
-如果(g～p)＝-1，返回″h＝t″。
已知當u＞0並且k+u＞t時k，g和p不兼容；當h＝0或1時，無論k的數值如何它們均是兼容的，並且在k+hδt+1時相等。
第二原則-下面三個過程對應於第二原則的不同實現。在某些實現中，第二原則可以被加強到要求各個數值q1到qm均不是無效數值的程度。接著均衡基數的作用；無論是否均衡第二原則均對方案在安全性方面的某些表現有影響。最終，當在m個數值{q1…qm}中存在f＞2個不同素數時，需要有至少一個含有f-1個獨立數值的子集。
三個過程使用mδf個被定義如下的數值Γi，j。
-當pi滿足t＜k，i從1到m時，i,j=i,j]]>，即+1，如果hi，j＝0，和-1，如果hi，j＝1。
-當pi滿足tδk，i從1到m時，Γi，j＝0，這意味著可以根據第二原則選擇 到 一個第一過程確定至少一個集合{Γi，1…Γi，f)是可變的或零，即至少一個數值q1到qm是非無效數值，或者可以被選定成非無效數值。
-對於從1到m的i和從1到f的j，-如果Γi，j＝0或ζΓi，j，返回″成功″。
-返回″失敗″。
一個第二過程確定各個集合{Γi，1…Γi，f}是可變的或零，即各個數值q1到qm是非無效數值，或者可以被選定成非無效數值。
-對於從1到m的i，-對於從1到f的j，-如果Γi，j＝0或ζΓi，j，則跳到i的下一個數值，-返回″失敗″。
-返回″成功″。
一個第三過程確定，對於每對素數pj1和pj2，並且1δj1δj2δf，存在至少一個集合{Γi，1…Γi，f}，其中Γi，j1是零或不同於Γi，j2。當m小於f-1時顯然會失敗。當在m個數值{q1…qm}中成功時，對於f個素數，需要有至少一個含有f-1個獨立數值的集合。
-對於從1到f-1的j1和從j1+1到f的j2，-對於從1到m的i，-如果Γi，j1＝0或ζΓi，j2，則跳到j1和j2的下一個數值，
-返回″失敗″。
-返回″成功″。
當一個過程失敗時，GQ2密鑰集合的生成器遵循從兩個可能策略中為其選定的策略-改變m個基數中的一個並且保留f個素數，-改變f個素數中的一個並且保留m個基數。
第三原則-下面過程確定通用化GQ2密鑰的集合在生成或已經生成時屬於-一個基本GQ2密鑰集合，即2υm個數值ρg1到ρgm均是非二次餘數，或者-一個補充GQ2密鑰集合，即在2υm個數值ρg1到ρgm中間至少存在一個二次餘數。
該過程使用兩個勒讓德符號(gi～pj)和(-gi～pj)，其中i從1到m而j從1到f。
-對於從1到m的i，-對於從1到f的j，-如果(gi～pj)＝-1，則跳到i的下一個數值。
-返回″補充GQ2密鑰集合″。
-對於從1到f的j，-如果(gi～pj)＝-1，則跳到i的下一個數值。
-返回″補充GK2密鑰集合″。
-返回″基本GK2密鑰集合″。
私有分量-對於一個直接類型的等式xΘ{gi2(mod pj)，下面的計算產生私有分量Qi，j的所有可能數值。兩個最簡單和最常見的情況，即t＝1和t＝2，後面有更加複雜的情況，即t＞2。
對於t＝1，即pj{3(mod 4)，密鑰(pj+1)/4，pj提CG(pj)中任意二次餘數的二次平方根。據此，導出一個數值sj{((pj+1)/4)k(mod(pj-1)/2)，該數值提供一個密鑰sj，pj，該密鑰將Gi轉換成w{Gisj(mod pj)。Qi，j等於n或pj-n。
對於t＝2，即pj{5(mod 8)，密鑰(pj+3)/8，pj為CG(pj)中具有奇數秩的元素提供具有奇數秩的平方根。據此，導出一個數值sj{(pj+3)/8)k(mod(p1-1)/4)，該數值提供一個密鑰sj，pj，該密鑰將Gi轉換成w{Gisj(mod pj)。注意，由於2是CG(pj)中的一個非二次餘數，所以z{2(Pj-1)/4(mod pj)是-1的平方根。Qi，j或者等於w或pj-w，或者等於w』{wυz(mod pj)或pj-w』。
對於pj{2t+1(mod 2t+1)和t＝2，密鑰(pj-1+2t)/2t+1，pj為任意具有奇數秩的元素提供具有奇數秩的平方根。k，g和p之間的兼容測試指定h的數值，u的下一個數值。
-當Gi位於圓圈內(u＝0，無論k有何數值)時，建立一個數值sj{((pj-1+2t)/2t+1)k(mod(pj-1)/2t)。密鑰Sj，pj將Gi轉換成具有奇數秩的解w{Gisj(mod pj)。在min(k，t)個涉及圓圈的連續分支，即在A個分支內分布有具有偶數秩的解。Qi，j等於w和CG(pj)中1的任意第2Δ次根的乘積。
-當Gj位於分支(u＞0，u+kδt)中一個適用位置上時，所有的解均和Gj位於相同的分支上，即一個涉及表示數值Gi的第2u次冪的圓圈的分支。產生一個數值sj{((pj-1+2t)/2t+1)k+u(mod(pj-1)/2t)。
密鑰sj，pj將Gi的第2u次冪轉換成具有奇數秩的數值w。w和CG(pj)中1的第2k+u次原根的乘積的集合包括2k個Qi，j數值。
當pi使得tτk時，由於數值bj是CG(pj)中1的第2t次原根，CG(pj)中bj的第2t-u次冪存在；這是1的第2k次原根。通過使Qi，j與1的一個第2k次原根相乘可以交換數 的值。
對於一個反置類型的等式1{xΘυgi2(mod pj)，足夠用密鑰sj，pj中的((pj-1)/2t)-sj替換數值sj，這相當於反置CG(pj)中Qi，j的值。具有兩個與5(mod 8)同餘的素數的密鑰集合的例子P1＝E6C83BF428689AF8C35E07EDD06F9B39A659829A58B79CD894C435C95F32BF25P2＝11BF8A68A0817BFCC00F15731C8B70CEF9204A34133A0DEF862829B2EEA74873Dn＝P1υP2＝FFFF8263434F173D0F2E76B32D904F56F4A5A6A50008C43D32B650E9AB9AAD2EB713D4F9A97C4DBDA3828A3954F296458D5F42C0126F5BD6B05478BE0A80ED1
這裡是最前面的素數的勒讓德符號。
(2～p1)=-1；(3～p1)=l；(S～p1)=+l；(7～p1)=l；(11～p1)=+1；(13～p1)=-l；(17～p1)=+l；在CG(p1)中，-5，-11和17的秩為奇數。
(2～p2)=-1；(3～p2)=+1；(5～p2)=+1；(7～p2)=+1；(11～p2)=+1；(13～p2)=-1；(17～p2)=1；在CG(p2)中，3，-5，7和11的秩為奇數．CarmichaeI函數是O(n)＝scm((p1-1)/4，(p2-1)/4)．O(n)＝33331A13DA43IUA5CFD617BD6F834311642121543334F40C3D57A9C8SS8555D5BDAA2EF6AEDl789E3794F51A65A1837239818FA980F618627D8C7ElD8499C1Bk＝9，數值S{O(n)-((1+O(n))/2)9(mod O(n))被用作私有指數以便使用反置類型的通用等式。
ζ＝01E66577BC997CAC273671E187A35EFD25373ABC9FE6770E74446CICCEF2C72AF6E89DOBE277CC6165F1007187AC58028BD2416D4CC1121E7A7A886AEl86BB480數值2，3，7，13和17不適於作為基數。
密鑰 ，n將gI=5轉換成一個私有數值Ql，Q1不說明任何因數分解。實際上在兩個域中，-5均在一個圓圈上。
Q1＝818C23AF3DE333FAECE88A71C4591A70553F91D6CODD5538EC0FlF2AAF909BDAD49lFD8BF13F18E3DA3774CCE19D0097BC4BD47C5D6EOE7EBF6D89FE3DC5176C密鑰 ，n將g2=11轉換成一個私有數值Q2，Q2說明了一個因數分解。實際上，11在兩個域中處於不同的位置上。
Q2=25F9AFDFl77993BE8652CE6E2C728AF31B6D66154D3935AC535196B07Cl9080DC962E4E86ACF40D01FDC454F256S4S4F29l0050DA052089EEC96A187DEB92CCA7密鑰 ，n將g3=2l=3v7轉換成一個私有數值Q3，Q3說明了一個因數分解。
Q2=78A8A2F3IJFEB4A5233BC05541AF78684C2406415EAlDD67D18A0459A1254121E95D5CAD8A1FE3ECFE0685C96CC7EE86167D9953283A9686BF9D93CAF8DF46AF0密鑰 ，n將g4=26=2u13轉換成一個私有數值Q4，Q4說明了一個因數分解。
Q2=6F1748A6280A200C38824A34C939F97DD2941DAD30030E4818738C62BF8C673731514D1978AF5655FE493D659514A6CE897AB76C01E50B5488C5DADl2332ES還可以通過兩個素數，中國餘數的參數和八個私有分量表示私有密鑰。△{(p2(modp1))-1(modp1)=ADE4E7787113F5FDEAC589AAE825D649E06692D15FBF0DF737B115DC4D012FDlDQ1，1{Q1(modp1)=7751AEE918A8F5CE44AD73D613A4F465E06C6F9AF4D229949C74DD6C18D76FAFQ1，2{Q1(modp2)=A9EB5FA182A981AA64CF88C382923DB64376F5FD46152C08EEB6114F3187665FQ2，1{Q2(modp1)=D5A7D33C5FB75AI)33F2FIlE88202748957FA34004ABB2C2AClCA3F5320C5A9049Q2，2{Q2(modp2))=76C9F5EFD066C73A2B5CE97S8DB512DFC011F585AF7DA8D39A961CC876F2DD8FQ3，1{Q3(mop1)＝2FEC0DC2DCA5BA7290B27BC8CC85C938A514B8F5CFD55820A174FB5E6DF7B883Q3，2{Q3(modp2)＝010D488E6B0A38A1CC406CEE0D55DE59013389D8549DE493413F34604A160C1369Q4，1{Q4(modp1)＝A2B32026B6F82B6959566FADD9517DB8ED8524652145EE159DF3DC0C61FE3617Q4，2{Q4(modp2)＝011A3BB9B607F0BD71BBE25F52B305C224899E5F1F8CDC2FE0D8F9FF62B3C9860F私有密鑰GQ2的多態-私有密鑰GQ2的不同可能表示被證明均是等價的它們均相當於知道模數n的因數分解，即實際的GK2私有密鑰。GQ2私有密鑰的表示對證明實體內部而不是審查實體內部的計算進程有影響。這裡是GQ2私有密鑰的三個可能的主要表示。1)GQ私有密鑰的傳統表示是存儲m個私有數值Qi和公開檢查Θ，n；對於GQ2方案，這種表示與下面兩個競爭。2)就工作負載而言的最優表示是存儲參數k，f個素數pj，mυf個私有分量Qij和中國餘數的F-1個參數。3)就私有密鑰尺寸而言的最優表示在於存儲參數k，m個基數gi和f個素數pj，接著在開始使用時確定m個私有數值Qi和模數n以便其等價於第一種表示，或者確定mυf個私有分量Qi，j和中國餘數的f-1個參數以便等價於第二種表示。
由於動態認證機制或數字籤名機制的安全性等價於知道模數的因數分解，對於GQ2方案，不能簡單使用相同模數區分兩個實體。通常，各個證明實體具有其自身的GQ2模數。然而可以規定具有四個素數的GQ2模數，一個實體知道其中的兩個素數，而另一個實體知道其它兩個素數。
動態認證-動態認證機制向一個被稱為控制者的實體證明另一個被稱為證明者的實體的真實性以及可能相關的消息M的真實性，使得控制者可以確定實際上正與證明者交涉，並且確定其自身和證明者正在說及相同的消息M。相關消息M是可選的，這意味著它可以為空。
動態認證機制是一個四操作序列一個確認操作，一個質問操作，一個應答操作和一個檢查操作。證明者完成確認和應答操作。控制者完成質問和審查操作。
在證明者內，可以隔離一個見證者以便隔離證明者的最敏感參數和功能，即確認和應答的產生。見證者具有參數k和GQ2私有密鑰，即根據上述三種表示對模數進行的因數分解ξf個素數和m個基數，ξmυf個私有分量，f個素數和F-1個中國餘數參數，ξm個私有數值和模數n。
見證者可以對應於一個具體的實施例，例如ξ一個與共同構成證明者的PC相連的晶片卡，或ξ在PC內特別保護的程序，或ξ在晶片卡內特別保護的程序。如此隔離的見證者類似於籤名實體內部定義的見證者。在每次執行機制時，見證者產生一或多個確認R，並且接著對一樣多的質問d產生一樣多的應答D。各個集合{R，d，D}構成一個GQ2三元組。
除了包括見證者之外，證明者在必要時還具有一個散列函數和一個消息M。
控制者具有模數n，模數n來自一個公開密鑰目錄，甚至來自一個公開密鑰證書；在必要時還具有相同的散列函數和一個消息M′。證明者可以將GQ2公開參數，即數值k，m和g1到gm提供給控制者。控制者能夠根據任何質問d和任何應答D重構確認R′。參數k和m為控制者提供信息。除非專門指出，m個從g1到gm的基數是頭m個素數。各個質問d應當包含m個被表示成d1到dm的基本質問每個基數一個基本質問。從d1到dm的各個基本質問是從0到2k-1-1的一個數值(未使用Θ/2到Θ-1中的數值)。通常各個質問被編碼成m乘k-1個位(而不是m乘k個位)。例如，對於k＝5和m＝4個基數5，11，21和26，各個質問包含16位，其中通過4個四位字節發送這16位。當可能的(k-1)υm個質問有同等概率時，數值(k-1)υm確定各個GQ2三元組帶來的安全性一個根據定義不知道模數n的因數分解的冒名頂替者在2(k-1)υm次償試中只有一次成功機會。當(k-1)υm來自於15至20時，一個三元組足夠合理保證動態認證。為了實現任何層次的安全性，可以並行產生三元組；也可以順序產生它們即重複機制。
1)涉及確認的操作包括下列運算。
當見證者不使用中國餘數時，該見證者具有參數k，從Q1到Qm的m個私有數值和模數n；該見證者以隨機和秘密的方式選擇一或多個隨機數值r(0＜r＜n)；接著通過接連k次連續平方(mod n)運算將各個隨機數值r轉換成確認R。
R{rΘ(modn)這裡是一個具有前面無中國餘數的密鑰集合的例子。r＝5E94B894AC24AF843131F437C1B1797EF562CFA53AB8AD426C1AC016F1C89CFDA13120719477C3E2FB4B4566088E10EF9C010E8F09C60D981512198126091996R6BBF9FFA5D509778D0F93AE074D36A07D95FFC38F70C8D7E3300EBF234FA0BC20A95152A8FB73DE81FAEE5BF4FD3EB7F5EE3E36D7068D083EF7C93F6FDDF673A當見證者使用中國餘數時，見證者具有參數k，從p1到pf的頭f個素數，f-1個中國餘數參數和muf個私有分量Qi，j；見證者以隨機和秘密的方式中抽出一或多個包括f個隨機數的集合各個集合針對每個素數pi(0＜ri＜pi)包含一個隨機數值ri；接著通過k次連續平方(mod pi)運算將各個隨機數值ri轉換成一個確認分量Ri。
Ri{riΘ(modpi)對於包括f個確認分量的各個集合，見證者根據中國餘數技術建立一個確認。確認的數量與隨機數集合一樣多。
R＝中國餘數(R1，R2，…Rf)這裡是一個具有前面的密鑰集合和中國餘數的例子。
r1＝5C6D37F0E97083C8D120719475E080BBBF9F7392F11F3E244FDF0204E84D8CAER1＝3ddf516ee3945cb86d20d9c49e0da4d42281d07a76074dd4fe20c5c7c5e205df66r2＝AC8F85034AC78112071947C457225E908E83A2621B0154ED15DBFCB9A4915AC3R2＝01168CEC0F661EAA15157C2C287C6A5B34EE28F8EB4D8D340858079BCAE4ECB016R＝Chinese remainders(R1，R2)＝0AE51D90CB4FDC3DC757C56E063C9ED86BE153B71FC65F47C123C27F082BC3DD15273D4A923804718573F2F05E991487D17DAE0AAB7DF0D0FFA23E0FE59F95F0在兩種情況下，證明者向控制者發送所有或部分確認R，或發送一個散列碼H，其中通過雜湊各個確認R和一個消息M來獲得上述散列碼H。
2)涉及質問的操作包括隨機抽出一或多個均由m個基本質問d1，d2，…，dm構成的質問d；各個基本質問di均是0到Θ/2-1中的一個數值。
d＝d1d2…dm這裡是一個針對兩個例子的質問，即k＝5和m＝4。
d1＝1011＝11＝『B』；d2＝0011＝3；d3＝0110＝6；d4＝1001＝9，d＝d1‖d2‖d3‖d4＝1011001101101001＝B369控制者向證明者發送各個質問d。
3)應答操作包含下列運算。
當見證者不使用中國餘數時，見證者具有參數k，從Q1到Qm的m個私有數值和模數n；見證者使用通過確認操作得到的各個隨機數r和基於基本質問的私有數值計算一或多個應答D。
D{riυQid1νQ2d2υ…Qmdm(modpi)這裡是無中國餘數的例子的延續。
D＝027E6E808425BF2B401FD00B15B642B1A8453BE8070D86C0A7870E6C1940F7A6996C2D871EBE611812532AC5875E0E116CC8BA648FD8E86BE0B2ABCC3CCBBBE4當見證者使用中國餘數時，見證者具有參數k，f個從p1到pf的素數，f-1個中國餘數參數和muf個私有分量Qi，j；見證者使用通過確認操作得到的各個隨機數集合計算一或多個包含f個應答分量的集合；對於每個素數，各個應答分量集合均包含一個分量。
D{riυQ1，id1υQ2，id2υ…Qm，idm(modpi)針對各個應答分量集合，見證者根據中國餘數技術建立一個應答。應答的數量與質問一樣多。
D＝中國餘數(D1，D2，…Df)這裡是無中國餘數的例子的延續。
D1＝riνQ1，1d1υQ2，1d2υQ3，1d3υQ4，1d4(modp1)C71F86F6FD8F955E2EE434BFA7706E38E5E715375BC2CD2029A4BD572A9EDEE6D2＝r2υQ1，1d1υQ2，2d2υQ3，2d3υQ4，2d4(modp2)0BE022F4A20523F98E9F5DBEC0E10887902F3AA48C864A6C354693AD0B59D85E90CE7EA43CB8EA89ABDD0C814FB72ADE74F02FE6F098ABB98C8577A660B9CFCEAECB93BE1BCC356811BF12DD667E2270134C9073B9418CA5EBF5191218D3FDB3在兩種情況下，證明者均向控制者發送各個應答D。
4)檢查操作包括檢查各個三元組{R，d，D}滿足下面針對非零數值的等式。
等式或在恢復各個確認時沒有確認一定為零。
等式可選地，控制者接著通過雜湊各個恢復的確認R′和消息M′計算一個散列碼H′。當控制者因而檢索到在第一確認操作結束時接收的內容，即所有或部分確認R或散列碼H時，動態認證成功。
例如，一系列基本運算將應答D轉換成一個確認R′。該操作序列包括被k-1個基數除法或基數乘法(mode n)分隔的k個平方(mod n)。對於在第i個平方和第i+1個平方之間執行的第i個除法或乘法，基本質問d1的第i個位指示是否必須使用g1，基本質問d2的第i個位指示是否1必須使用g2，…，基本質問dm的第i個位指示是否必須使用gm。
這裡是無中國餘數的例子的結束。
D＝027E6E808425BF2B401FD00B15B642B1A8453BE8070D86C0A7870E6C1940F7A6996C2D871EBE611812532AC5875E0E116CC8BA648FD8E86BE0B2ABCC3CCBBBE4計算平方模n88BA681DD641D37D7A7D9818D0DBEA82174073997C6C32F7FCAB30380C4C6229B0706D1AF6EBD8461771C31B4243C2F0376CAF5DCEB644F098FAF3B1EB49B39乘以5乘26＝130，即′82′模n6ECABA65A91C22431C413E4EC7C7B39FDE14C9782C94FD6EA3CAAD7AFE192B94400C1113CB8DBC45619595D263C1067D3D0A840FDE008B415028AB3520A6AD49D計算平方模n0236D25049A5217B13818B39AFB009E4D7D52B17486EBF844D64CF75C4F652031041328B29EBF0829D54E3BD17DAD218174A01E6E3AA650C6FD62CC274426607乘以21，即′15 ′模n2E7F40960A8BBF1899A06BBB6970CFC5B47C88E8F115B5DA594504A92834BA405559256A705ABAB6E7F6AE82F4F33BF9E91227F0ACFA4A052C91ABF389725E93計算平方模nB802171179648AD687E672D3A32640E2493BA2E82D5DC87DBA2B2CC0325E7A71C50E8AE002E299EF868DD3FB916EBCBC0C5569B53D42DAD49C956D8572E1285B0乘以5乘11乘21＝1155，即′483′模n3305560276310DEFEC1337EB5BB5810336FDB28E91B350D485B09188E0C4F1D67E68E9590DB7F9F39C22BDB4533013625011248A8DC417C667B419D27CB11F72計算平方模n8871C494081ABD1AEB8656C38B9BAAB57DBA72A4BD4EF9029ECBFFF540E55138C9F22923963151FD0753145DF70CE22E9D019990E41DB6104005EEB7B1170559乘以5乘11乘26＝1430，即′596′模n4FF5EEACDF794563BB09A17045ECFFF88F5136C7FBC825BC50C計算平方模n6BBF9FFA5D509778D0F93AE074D36A07D95FFC38F70C8D7E3300EBF234FA0BC20A95152A8FB73DE81FAEE5BF4FD3EB7F5EE3E36D7068D083EF7C93F6FDDF673A檢索到確認r。認證成功。
這裡是有中國餘數的例子的結束。
D＝90CE7EA43CB8EA89ABDD0C814FB72ADE74F02FE6F098ABB98C8577A660B9CFCEAECB93BE1BCC356811BF12DD667E2270134C9073B9418CA5EBF5191218D3FDB3計算平方模n770192532E9CED554A8690B88F16D013010C903172B266C1133B136EBE3EB5F13B170DD41F4ABE14736ADD3A70DFA43121B6FC5560CDD4B4845395763C792A68乘以5乘26＝130，即′82′模n6EE9BEF9E52713004971ABB9FBC31145318E2A703C8A2FB3E144E7786397CD8D1910E70EA86262DB771AD1565303AD6E4CC6E90AE3646B461D3521420E240FD4計算平方模nD984D9A8E80002C4D0329FF97D7AD163D8EA98F6AF8FE2B2160B2126CBBDFC734E39F2C9A39983A426486BC477F20ED2CA59E664C23CA0E04E84F2F0AD65340乘以21，即′15′模nD7DD7516383F78944F2C90116E1BEE0CCDC8D7CEC5D7D1795ED33BFE8623DB3D2E5B6C5F62A56A2DF4845A94F32BF3CAC360C7782B5941924BB4BE91F86BD85F計算平方模nDD34020DD0804C0757F29A0CBBD7B46A1BAF949214F74FDFE021B626ADAFBAB5C3F1602095DA39D70270938AE362F2DAE0B914855310C75BCA328A4B2643DCCDF乘以5乘11乘21＝1155，即′483′模n038EF55B4C826D189C6A48EFDD9DADBD2B63A7D675A0587C8559618EA2D83DF552D24EAF6BE983FB4AFB3DE7D4D2545190F1B1F946D327A4E9CA258C73A98F57計算平方模nD1232F50E30BC6B7365CC2712E5CAE079E47B971DA03185B33E918EE6E99252DB3573CC87C604B327E5B20C7AB920FDF142A8909DBBA1C04A6227FF18241C9FE乘以5乘11乘26＝1430，即′596′模n3CC768F12AEDFCD4662892B9174A21D1F0DD9127A54AB63C984019BED9BF88247EF4CCB56D71E0FA30CFB0FF28B7CE45556F744C1FD751BFBCA040DC9CBAB744計算平方模n0AE51D90CB4FDC3DC757C56E063C9ED86BE153B71FC65F47C123C27F082BC3DD15273D4A923804718573F2F05E991487D17DAE0AAB7DF0D0FFA23E0FE59F95F0正確檢索到確認r。認證成功。數字籤名數字籤名機制允許一個被稱作籤名實體的實體產生已籤名消息並且允許一個被稱作控制者的實體確定已籤名消息。消息M是任意的二進位序列可以為空。通過向消息M加入一個籤名附錄對消息M籤名，籤名附錄包括一或多個確認和/或質問，以及對應的應答。
控制者具有模數n，模數n來自一個公開密鑰目錄，甚至來自一個公開密鑰證書；它也具有相同的散列函數。證明者可以將GQ2公開參數，即數量k，m和g1到gm提供給控制者，例如通過把它們放在籤名附錄中。
數值k和m為控制者提供信息。一方面，從d1到dm的各個基本質問是0到2k-1-1中的一個數值(未使用Θ/2到Θ-1中的數值)。另一方面，各個質問d應當包含m個被表示成d1到dm的基本質問，其中基本質問和基數一樣多。並且，除非專門指出，m個從g1到gm的基數是頭m個素數。在(k-1)υm等於15至20的情況下，可以用四個並行產生的GQ2三元組籤名；在(k-1)υm等於60或更大數值的情況下，可以僅用一個GQ2三元組籤名。例如，對於k＝9和m＝8，只有一個GQ2三元組便足夠了；各個質問包含八個字節並且基數為2，3，5，7，11，13，17和19。
籤名運算是由三個操作構成的操作序列一個確認操作，一個質問操作和一個應答操作。各個操作產生一或多個GQ2三元組，其中每個三元組包括一個確認r(ζ0)，一個由m個基本質問d1，d2，…，dm構成的質問d，和一個應答D(ζ0)。
籤名實體具有一個散列函數，參數k和GQ2私有密鑰，即基於上述三種表示中的一種的模數n因數分解。在籤名實體內部，可以通過隔離執行確認和應答操作的見證者來隔離證明者的最敏感功能和參數。為了計算確認和應答，見證者具有參數k和GQ2私有密鑰，即基於上述三種表示中的一種的模數n因數分解。如此隔離的見證者類似於證明者內部定義的見證者。它可以對應於一個具體實施例，例如ζ一個與共同構成籤名實體的PC連接的晶片卡，ζ或PC內部特別保護的程序，ζ或晶片卡內部特別保護的程序。
1)涉及確認的操作包括下列運算。
當見證者具有從Q1到Qm的m個私有數值和模數n時，該見證者以隨機和秘密的方式選擇一或多個隨機數值r(0＜r＜n)；接著通過接連k次連續自乘(mod n)運算將各個隨機數值r轉換成一個確認R。
R{rΘ(modn)當見證者具有從p1到pf的f個素數和mυf個私有分量Qi，j時，該見證者以隨機和秘密的方式抽出一或多個包含f個隨機數值的集合各個集合針對每個素數pi(0＜ri＜pi)均具有一個隨機數值ri；接著通過k次連續自乘(mod pi)運算將各個隨機數值ri轉換成一個確認分量Ri。
Ri{riΘ(modpi)對於包括f個確認分量的各個集合，見證者根據中國餘數技術建立一個確認。確認的數量與隨機數集合一樣多。
r{中國餘數(R1，R2，…Rf)2)質問操作包括雜湊所有確認r和要籤名的消息M以獲得一個被籤名實體用來構成一或多個均包括m個基本質問的質問的散列碼；各個基本質問的取值範圍為0到Θ/2-1；例如對於k＝9和m＝8，各個質問包含八個字節。質問的數量與確認一樣多。
d＝d1，d2，…，dm，即從雜湊(M，R)結果中提取的數值3)應答操作包含下列運算。
當見證者具有從Q1到Qm的m個私有數值和模數n時，見證者使用通過確認操作得到的各個隨機數r和基於基本質問的私有數值計算一或多個應答D。
X{Q1d1vQ2d2v…Qmdm(mod n)D{rυX(modn)當見證者具有f個從pi到pf的素數和muf個私有分量Qi，j時，見證者使用通過確認操作得到的各個隨機數值集合計算一或多個由f個應答分量構成的集合各個應答分量集合針對每個素數均包括一個分量。
X{Q1，id1υQ2，id2υ…Qm，idm(modpi)Di{riυXi(modpi)針對各個應答分量集合，見證者根據中國餘數技術建立一個應答。應答的數量與質問一樣多。
D中國餘數(D1，D2，…Df)籤名實體通過加入一個籤名附錄對消息M進行籤名，籤名附錄包括
-各個GQ2三元組，即各個確認R，各個質問d和各個應答D，-或各個確認R和各個對應的應答D，-或各個質問d和各個對應的應答D。
根據籤名附錄的內容運行驗證運算。區分三種情況。
如果附錄包括一或多個三元組，檢查運算包含兩個時序無關緊要的獨立過程。若且唯若下面兩個條件被滿足時控制者才接受籤名消息。
首先，各個三元組必須是一致的(必須滿足一個下面類型的適當關係)和可接受的(必須在非零數值上進行比較)。
等式(mod n)否則R(mod n)例如，通過一個基本運算序列轉換應答D被k-1個基數乘法或除法運算(mod n)分隔的k個平方(mod n)。對於在第i個平方和第i+1個平方之間執行的第i個乘法或除法，基本質問d1的第i個位指示是否有必要使用g1，基本質問d2的第i個位指示是否有必要使用g2，…，基本質問dm的第i個位指示是否有必要使用gm。因而有必要檢索籤名附錄中出現的各個確認R。
此外，一或多個三元組必須與消息M關聯起來。通過雜湊所有確認R和一個M，獲得一個散列碼，其中必須根據上述散列碼恢復出各個質問d。
d＝d1，d2，…，dm，與從雜湊(M，R)結果中提取的數值相同。
如果附錄中沒有質問，則檢查運算開始通過雜湊所有確認R和消息M重構一或多個質問d′。
d＝d′1，d′2，…，d′m，即從雜湊(M，R)結果中提取的數值。
接著，若且唯若各個三元組是一致的(滿足一個下面類型的適當關係)和可接受的(在非零數值上進行比較)，控制者才接受籤名消息。
等式(mod n)否則R(mod n)如果附錄中沒有確認，則檢查運算開始根據下列兩個公式中的一個適當的公式重構一或多個確認R′。重新建立的確認不應當為零。
等式(mod n)否則R(mod n)接著，控制者必須雜湊所有確認R′和消息M以便重構各個質問d。
d＝d1，d2，…，dm，與從雜湊(M，R′)結果中提取的數值相同。
若且唯若各個重構的質問與附錄中的對應質問相同時控制者才接受籤名消息。
權利要求
1.用於向一個控制者實體證明以下內容的方法，-一個實體的真實性和/或-與這個實體相關的消息M的完整性，這種證明是通過所有或部分下列參數或這些參數的派生參數而進行的-m對私有數值Q1，Q2，…Qm和公開數值G1，G2，…Gm(m大於或等於1)，-由上述f個素數p1，p2，…pf(f大於或等於2)的乘積構成的一個公開模數n，上述模數，上述私有和公開數值具有下面類型的關係Gi.{Qiv.mod n or G1.{Qiv.mod n其中v表示一個具有以下形式的公開指數v＝2k其中k是大於1的安全參數；上述m個公開數值Gi是小於f個素數p1，p2，…pm的m個不同基數g1，g2，…gm的平方gi2；上述素數p1，p2，…pf和/或上述m個基數g1，g2，…gm是這樣產生的，即使得以下條件得到了滿足第一條件等式xv{gi2modn(1)中的每一個可以被以n為模的整數環中的x求解；第二條件如果Gi{Qivmod n成立，在通過以n為模把Qi乘方k-1次獲得的m個數值qi中有一個qi不同於±gi(即是一個非無效解)，如果Gi.Qiv{1 mod n成立，在通過以n為模把Qi的反置乘方k-1次獲得的m個數值qi中有一個qi不同於±gi(即是一個非無效解)；第三條件2m等式中的至少一個x2{gimod n(2)x2{-gimod n(3)可以被以n為模的整數環中的x求解；上述方法在下面步驟中實現一個被稱作見證者的實體，上述見證者實體具有f個素數pi和/或m個基數gi和/或素數的中國餘數的參數和/或公開模數n和/或m個私有數值Qi和/或私有數值Qi與公開指數v的f.m個分量Qi，j(Qi，j{Qimod pj)；-見證者計算以n為模數的整數環中的確認R；通過以下方式計算各個確認通過執行下列類型的運算R{rvmod n其中r是一個隨機數值並且0＜r＜n，或通過執行下列類型的運算Ri{rivmod pi其中ri是一個與素數Pi相關的隨機數值，從而使0＜ri＜Pi，各個ri屬於一個隨機數值集合{r1，r2，…rf}接著通過使用中國餘數方法，-見證者接收一或多個質問d；每個質問d包括m個被稱作基本質問的整數di；根據各個質問d，見證者通過執行以下類型的運算計算一個應答DD{r.Q1d1.Q2d2…Qmdmmod n或通過執行下列類型的運算Di{ri.Qi，1d1.Qi，2d2…Qi，mdmmod pi接著使用中國餘數方法；上述方法使得應答D的數量與質問d和確認R一樣多，其中每組數值R，d，D構成一個被表示成{R，d，D}的三元組。
2.如權利要求1所述的方法，上述方法被用來向一個被稱為控制者的實體證明一個被稱為證明者的實體的真實性，上述證明者實體包括見證者；上述證明者和控制者實體執行下列步驟步驟1涉及確認R的操作-每次見證者使用如權利要求1所述的過程計算各個確認R，證明者向控制者發送所有或部分確認E，步驟2涉及質問d的操作-在接收所有或部分確認R之後，控制者產生數量等於確認R的數量的質問d並且向證明者發送質問d，*步驟3涉及應答D的操作-見證者使用如權利要求1所述的過程根據質問d計算應答D，*步驟4涉及檢查的操作-證明者向控制者發送各個應答D，在證明者發送一部分確認R的情況下如果證明者已經發送一部分確認R，則控制者在具有m個公開數值G1，G2，…Gm的情況下根據各個質問d和各個應答D計算一個重構確認R′，這個重構確認R′滿足以下類型的關係R＇1{G1di.G2d2.…Gmdm.Dvmod n或以下類型的關係R′{Dv/G1d1.G2d2.…Gmdm.mod n控制者確定各個重構的確認R′還原出已經發送過來的所有或部分確認R，在證明者已經全部發送確認R的情況下如果證明者已經發送全部確認R，則控制者在具有m個公開數值G1，G2，…Gm的情況下確定各個確認R滿足以下類型的關係R′{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R′{Dv/G1d1.G2d2.…Gmdm.mod n
3.如權利要求1所述的方法，上述方法被用來向一個被稱為控制者的實體證明與一個被稱為證明者的實體相關的消息M的真實性，上述證明者實體包括見證者；上述證明者和控制者實體執行下列步驟*步驟1涉及確認R的操作-每次見證者使用如權利要求1所述的過程計算各個確認R，*步驟2涉及質問d的操作-證明者使用一個散列函數h計算至少一個令牌T，其中散列函數的參數包括消息M和所有或部分確認R，-證明者向控制者發送令牌T，-在接收令牌T之後，控制者產生數量等於確認R的數量的質問d並且向證明者發送質問d，*步驟3涉及應答D的操作-見證者使用如權利要求1所述的過程根據質問d計算應答D，*步驟4涉及檢查的操作-證明者向控制者發送各個應答D，-控制者在具有m個公開數值G1，G2，…Gm的情況下根據各個質問d和各個應答D計算一個重構確認R′，這個重構確認R′滿足以下類型的關係R′{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R′{Dv/G1d1.G2d2.…Gmdm.mod n-接著控制者使用一個散列函數h重構令牌T′，其中散列函數的參數包括消息M和所有或部分重構確認R′，-接著控制者確定令牌T′與發送的令牌T相同。
4.如權利要求1所述的方法，上述方法被用來通過一個被稱為籤名實體的實體產生一個消息M的數字籤名，上述籤名實體包括見證者；籤名運算上述籤名實體執行籤名運算以便獲得包括以下內容的已籤名消息-消息M，-質問d和/或確認R，-應答D；上述籤名實體通過實現下列步驟執行籤名運算*步驟1涉及確認R的操作-每次見證者使用如權利要求1所述的過程計算各個確認R，*步驟2涉及質問d的操作籤名實體使用一個散列函數h獲得一個二進位序列，上述散列函數的參數包括消息M和各個確認R，-籤名實體從這個二進位序列中提取其數量等於確認R的數量的質問d，*步驟3涉及應答D的操作-見證者使用如權利要求1所述的過程根據質問d計算應答D。
5.如權利要求4所述的方法，上述方法被用來通過使用一個被稱作控制者的實體檢查籤名消息來證明消息M的真實性；檢查運算上述具有已籤名消息的上述控制者實體通過執行如下步驟來完成檢查運算在控制者具有確認R，質問d，應答D的情況下，如果控制者具有確認R，質問d，應答D，控制者確定確認R，質問d和應答D滿足以下類型的關係R{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R{Dv/G1d1.G2d2.…Gmdm.mod n控制者確定消息M，質問d和確認R滿足散列函數d＝h(消息，R)在控制者具有質問d和應答D的情況下如果控制者具有質問d，應答D，控制者根據各個質問d和各個應答D重構滿足下列關係的確認R′R′{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R′{Dv/G1d1.G2d2.…Gmdm.mod n控制者確定消息M和質問d滿足散列函數d＝h(消息，R1)在控制者具有確認R和應答D的情況下如果控制者具有確認R，應答D，控制者使用散列函數並且重構d′d′＝h(消息，R)控制者設備確定確認R，質問d′和應答D滿足以下類型的關係R{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R{Dv/G1d1.G2d2.…Gmdm.mod n
6.被用來向一個控制者伺服器證明以下內容的系統，-一個實體的真實性和/或-與這個實體相關的消息M的完整性，通過所有或部分下列參數或這些參數的派生參數完成這個證明-m對私有數值Q1，Q2，…Qm和公開數值G1，G2，…Gm(m大於或等於1)，-由上述f個素數p1，p2，…pf(f大於或等於2)的乘積構成的一個公開模數n，上述模數，上述私有和公開數值具有下面類型的關係Gi.Qiv{1.mod n or Gi{Qivmod n；其中v表示一個具有以下形式的公開指數v＝2k其中k是大於1的安全參數；上述m個公開數值Gi是小於f個素數p1，p2，…pf的m個不同基數g1，g2，…gm的平方gi2；上述f個素數p1，p2，…pf和/或上述m個基數g1，g2，…gm的產生使得以下條件得到滿足第一條件各個等式xv{gi2mod n(1)可以被以n為模的整數環中的x求解；第二條件如果Gi{Qivmod n成立，在通過以n為模把Qi乘方k-1次獲得的m個數值qi中有一個qi不同於±gi(即是一個非無效解)。如果Gi.Qiv{1 mod n成立，在通過以n為模把Qi的反置乘方k-1次獲得的m個數值qi中有一個qi不同於±gi(即是一個非無效解)第三條件2m等式中的至少一個x2{gimod n(2)x2{-gimod n(3)可以被以n為模的整數環中的x求解；上述系統包括一個見證者設備，尤其是採取諸如基於微處理器的銀行卡的形式的漫遊對象中的見證者設備，見證者設備包括-一個存儲器區段，其中包含f個素數pi和/或m個基數gi和/或素數的中國餘數的參數和/或公開模數n和/或m個私有數值Qi和/或私有數值Qi與公開指數v的f.m個分量Qi，j(Qi，j{Qimod pj)；上述見證者設備還包括-隨機數值產品裝置，此後被稱作見證者設備的隨機數值產生裝置，-計算裝置，此後被稱作計算見證者設備的確認R的裝置，上述計算裝置計算以n為模的整數環中的確認R；通過以下方式計算各個確認通過執行下列類型的運算Ri{rvmod n其中r是隨機數值產生裝置產生的隨機數值，並且0＜r＜n；或者，執行下列類型的運算Ri{rivmod pi其中ri是一個與素數pi相關的隨機數值，其中0＜ri＜pi，各個ri屬於一個由隨機數產生裝置產生的隨機數值集合{r1，r2，…rf}，並且接著使用中國餘數方法；上述見證者設備還包括-接收裝置，此後被稱作接收見證者設備的質問的裝置，上述接收裝置接收一或多個質問di；每個質問di包括m個此後被稱作基本質問的整數di；-計算裝置，此後被稱作計算見證者設備的應答D的裝置，上述計算根據各個質問d計算一個應答D，通過執行下列類型的運算D{r.Q1d1.Q2d2…Qmdmmod n或者通過執行下列類型的運算D{r.Qi，1d1.Qi，2d2…Qi，mdmmod pi並且接著使用中國餘數方法。-發送一或多個確認R和一或多個應答D的發送裝置；應答D的數量與質問d和確認R和一或多個，其中每組數值R，d，D構成一個被表示成{R，d，D}的三元組。
7.如權利要求6所述的系統，該系統被用來證明一個被稱作證明者的實體和一個被稱作控制者的實體的真實性，上述系統包括-一個與證明者實體相關的證明者設備，上述證明者設備通過互連裝置與見證者設備互連，並且能夠具有漫遊對象中邏輯微電路的形式，例如具有基於微處理器的銀行卡中的微處理器的形式，-一個與控制者實體相關的控制者設備，上述控制者設備具有終端或遠程伺服器的形式；上述控制者設備包括以電子，電磁光學或聲學方式，尤其是通過數據處理通信網絡連接到證明者設備的連接裝置；上述系統允許執行下列步驟步驟1涉及確認R的操作每次見證者設備的計算確認R的裝置使用如權利要求1所述的過程計算各個確認R，見證者設備具有通過互連裝置向證明者設備發送所有或部分確認R的發送裝置，此後被稱作見證者設備的發送裝置，證明者設備設備還具有通過連接裝置向控制者設備發送所有或部分確認R的發送裝置，此後被稱作證明者設備的發送裝置；*步驟2涉及質問d的操作控制者設備包括質問產生裝置，該裝置在接收所有或部分確認R之後產生數量等於確認R的數量的質問d，控制者設備還具有通過連接裝置向證明者發送所有或部分質問d的發送裝置，此後被稱作控制者的發送裝置，*步驟3涉及應答D的操作接收見證者設備的質問d的裝置通過互連裝置接收來自證明者設備的各個質問d，見證者設備計算應答D的裝置使用如權利要求1所述的過程根據質問d計算應答D，*步驟4涉及檢查的操作證明者的發送裝置向控制者發送各個應答D。控制者設備還包括-計算裝置，此後被稱作控制者設備的計算裝置，-比較裝置，此後被稱作控制者設備的比較裝置，在證明者發送一部分確認R的情況下如果證明者的發送裝置已經發送一部分確認R，則控制者的計算裝置在具有m個公開數值G1，G2，…Gm的情況下根據各個質問d和各個應答D計算一個重構確認R′，這個重構確認R′滿足以下類型的關係R′{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R′{Dv/G1d1.G2d2.…Gmdm.mod n控制者設備的比較裝置將各個重構確認R′與接收的所有或部分確認R進行比較，在控制者已經全部發送確認R的情況下如果證明者的發送計算裝置已經發送全部確認R，則控制者設備的計算裝置和比較裝置在具有m個公開數值G1，G2，…Gm的情況下確定各個確認R滿足以下類型的關係R{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R{Dv/G1d1.G2d2.…Gmdm.mod n
8.如權利要求6所述的系統，上述系統被用來向一個被稱為控制者的實體證明與一個被稱為證明者的實體相關的消息M的完整性，上述系統包括-一個與證明者實體相關的證明者設備，上述證明者設備通過互連裝置與見證者設備互連，並且能夠具有漫遊對象中邏輯微電路的形式，例如具有基於微處理器的銀行卡中的微處理器的形式，-一個與控制者實體相關的控制者設備，上述控制者設備具有終端或遠程伺服器的形式，上述控制者設備包括以電子，電磁光學或聲學方式，尤其是通過數據處理通信網絡連接到證明者設備的連接裝置；上述系統允許執行下列步驟*步驟1涉及確認R的操作每次見證者設備的計算確認R的裝置使用如權利要求1所述的過程計算各個確認R，-見證者設備具有通過互連裝置向證明者設備發送所有或部分確認R的發送裝置，此後被稱作見證者設備的發送裝置，*步驟2涉及質問d的操作證明者設備包括計算裝置，此後被稱作證明者的計算裝置，計算裝置使用一個散列函數h計算至少一個令牌T，其中散列函數的參數包括消息M和所有或部分確認R，證明者設備還具有通過連接裝置向控制者設備發送各個令牌T的發送裝置，此後被稱為證明者設備的發送裝置，控制者設備還具有質問產生裝置，該裝置在接收令牌T之後產生數量等於確認R的數量的質問d，控制者設備還具有通過連接裝置向證明者發送所有或部分質問d的發送裝置，此後被稱作控制者的發送裝置；*步驟3涉及應答D的操作接收見證者設備的質問d的裝置通過互連裝置接收來自證明者設備的各個質問d，見證者設備計算應答D的裝置使用如權利要求1所述的過程根據質問d計算應答D，*步驟4涉及檢查的操作證明者的發送裝置向控制者發送各個應答D，控制者設備還包括計算裝置，此後被稱作控制者設備的計算裝置，上述計算裝置在具有m個公開數值G1，G2，…Gm的情況下根據各個質問d和各個應答D首先計算一個重構確認R′，這個重構確認R′滿足以下類型的關係R′{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R′{Dv/G1d1.G2d2.…Gmdm.mod n接著使用一個散列函數h計算一個令牌T′，其中散列函數的參數包括消息M和所有或部分重構確認R′，控制者設備還具有將計算的令牌T′與接收的令牌T相比較的比較裝置，此後被稱為控制者設備的比較裝置。
9.如權利要求6所述的系統，上述系統被用來通過一個被稱作籤名實體的實體產生一個此後被稱為籤名消息的消息M的數字籤名；已籤名消息包括-消息M，-質問d和/或確認R，-應答D；籤名運算上述系統包括一個與籤名實體相關的籤名設備，上述籤名設備通過互連裝置與見證者設備互連並且可以具有漫遊對象中邏輯微電路的形式，例如基於微處理器的銀行卡中微處理器的形式，上述系統允許執行下列步驟*步驟1涉及確認R的操作每次見證者設備的計算確認R的裝置使用如權利要求1所述的過程計算各個確認R，見證者設備具有通過互連裝置向籤名設備發送所有或部分確認R的發送裝置，此後被稱作見證者設備的發送裝置，*步驟2涉及質問d的操作籤名設備包括計算裝置，此後被稱作籤名設備的計算裝置，上述計算裝置使用一個散列函數h計算一個二進位序列並且從這個二進位序列中提取出數量等於確認R的數量的質問d，其中散列函數的參數包括消息M和所有或部分確認R，*步驟3涉及應答D的操作接收質問d的裝置通過互連裝置接收來自籤名設備的各個質問d，見證者設備計算應答D的裝置使用如權利要求1所述的過程根據質問d計算應答D，見證者設備包括通過互連裝置向籤名設備發送應答D的發送裝置，此後被稱作見證者設備的發送裝置。
10.如權利要求9所述的系統，上述系統被用來通過使用一個被稱作控制者的實體檢查籤名消息來證明消息M的真實性；檢查運算上述系統包括一個與控制者實體相關的控制者設備，上述控制者設備具有終端或遠程伺服器的形式，上述控制者設備包括以電子，電磁光學或聲學方式，尤其是通過數據處理通信網絡連接到籤名設備的連接裝置；上述與籤名實體相關的籤名設備包括通過連接裝置向控制者設備發送已籤名消息的發送裝置，此後被稱為籤名設備的發送裝置，因而控制者設備具有一個包括以下內容的已籤名消息-消息M，-質問d和/或確認R，-應答D；控制者設備包括-計算裝置，此後被稱作控制者設備的計算裝置，-比較裝置，此後被稱作控制者設備的比較裝置在控制者設備具有確認R，質問d，應答D的情況下如果控制者具有確認R，質問d，應答D，控制者設備的計算和比較裝置確定消息M，質問d和確認R滿足以下關係R{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R{Dv/G1d1.G2d2.…Gmdm.mod n控制者設備的計算和比較裝置確定消息M，質問d和確認R滿足散列函數d＝h(消息，R)在控制者設備具有質問d和應答D的情況下如果控制者設備具有質問d，應答D，控制者設備的計算裝置根據各個質問d和各個應答D計算滿足以下類型關係的確認R』R{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R{Dv/G1d1.G2d2.…Gmdm.mod n控制者設備的計算和比較裝置確定消息M和質問d滿足散列函數d＝h(消息，R』)在控制者設備具有確認R和應答D的情況下如果控制者設備具有確認R，應答D，控制者設備的計算裝置使用散列函數並且計算d′，使得d』＝h(消息，R)控制者設備的計算和比較裝置確定消息M，質問d′和確認R滿足以下關係R{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R{Dv/G1d1.G2d2.…Gmdm.mod n
11.與一個實體相關、被用來向一個控制者設備證明以下內容的終端設備，上述終端設備具有漫遊對象的形式，例如基於微處理器的銀行卡中的微處理器的形式-一個實體的真實性和/或-與這個實體相關的消息M的完整性；通過所有或部分下列參數或這些參數的派生參數完成這個證明-m對私有數值Q1，Q2，…Qm和公開數值G1，G2，…Gm(m大於或等於1)，-由上述f個素數p1，p2，…pf(f大於或等於2)的乘積構成的一個公開模數n，上述模數，上述私有和公開數值具有下面類型的關係Gi.Qiv{1 mod n或Gi{Qivmod n；其中v表示一個具有以下形式的公開指數v＝2k其中k是大於1的安全參數；上述m個公開數值Gi是少於f個素數p1，p2，…pf的m個基數g1，g2，…gm的平方gi2；產生上述f個素數p1，p2，…pf和/或上述m個基數g1，g2，…gm以滿足下面的條件第一條件各個等式xvgi2mod n(1)均不能被以n為模的整數環中的x求解。第二條件如果Gi{Qivmod n成立，在通過以n為模把Qi乘方k-1次獲得的m個數值qi中有一個qi不同於±gi(即是一個非無效解)，如果Gi.Qiv{1 mod n成立，在通過以n為模把Qi的反置乘方k-1次獲得的m個數值qi中有一個qi不同於±gi(即是一個非無效解)；第三條件2m等式中的至少一個x2{gimod n(2)x2{-gimod n(3)可以被以n為模的整數環中的x求解；上述終端設備包括一個見證者設備，上述見證者設備包括-一個存儲器區段，其中包含f個素數pi和/或m個基數gi和/或素數的中國餘數的參數和/或公開模數n和/或m個私有數值Qi和/或私有數值Qi與公開指數v的f.m個分量Qi，j(Qi，j{Qimod pj)；上述見證者設備還包括-隨機數值產品裝置，此後被稱作見證者設備的隨機數值產生裝置，-計算裝置，此後被稱作計算見證者設備的確認R的裝置，上述計算裝置計算以n為模的整數環中的確認R；通過以下方式計算各個確認通過執行下列類型的運算R{rvmod n其中r是隨機數值產生裝置產生的隨機數值，並且0＜r＜n。或者通過執行下列類型的運算Ri{rivmod pi其中ri是一個與素數pi相關的隨機數值，其中0＜ri＜Pi，各個ri屬於一個由隨機數產生裝置產生的隨機數值集合{r1，r2，…rf}，並且接著使用中國餘數方法；上述見證者設備還包括-接收裝置，此後被稱作接收見證者設備的質問的裝置，上述接收裝置接收一或多個質問di；每個質問di包括m個此後被稱作基本質問的整數di；-計算裝置，此後被稱作計算見證者設備的應答D的裝置，上述計算根據各個質問d計算一個應答D，通過執行下列類型的運算D{r.Q1d1.Q2d2…Qmdmmod n或者通過執行下列類型的運算D{r.Qi，1d1.Qi，2d2…Qi，mdmmod pi並且接著使用中國餘數方法-發送一或多個確認R和一或多個應答D的發送裝置；應答D的數量與質問d和確認R和一或多個，其中每組數值R，d，D構成一個被表示成{R，d，D}的三元組。
12.如權利要求11所述的終端設備，該終端設備被用來向一個被稱作控制者的實體證明一個被稱作證明者的實體的真實性；上述終端設備包括一個與證明者實體相關的證明者設備，上述證明者設備通過互連裝置與見證者設備互連並且尤其可以具有漫遊對象中邏輯微電路的形式，例如基於微處理器的銀行卡中微處理器的形式，上述證明者設備還包括以電子，電磁光學或聲學方式，尤其是通過數據處理通信網絡連接到與控制者實體相關的控制者設備的連接裝置，上述控制者設備尤其具有終端或遠程伺服器的形式；上述終端設備允許執行下列步驟*步驟1涉及確認R的操作每次見證者設備的計算確認R的裝置使用如權利要求1所述的過程計算各個確認R，-見證者設備具有通過互連裝置向證明者設備發送所有或部分確認R的發送裝置，此後被稱作見證者設備的發送裝置，證明者設備還具有通過連接裝置向控制者設備發送所有或部分確認R的發送裝置，此後被稱作證明者的發送裝置；*步驟2和3涉及質問d的操作，涉及應答D的操作見證者設備接收質問d的裝置通過控制者設備和證明者設備之間的連接裝置和證明者設備與見證者設備之間的互連裝置接收來自控制者設備的各個質問d，見證者設備計算應答D的裝置使用如權利要求1所述的過程根據質問d計算應答D，*步驟4涉及檢查的操作證明者的發送裝置向進行檢查的控制者發送各個應答D。
13.如權利要求11所述的終端設備，上述終端設備被用來向一個被稱為控制者的實體證明與一個被稱為證明者的實體相關的消息M的完整性，上述終端設備包括一個與證明者實體相關的證明者設備，上述證明者設備通過互連裝置與見證者設備互連並且尤其可以具有漫遊對象中邏輯微電路的形式，例如基於微處理器的銀行卡中微處理器的形式，上述證明者設備包括以電子，電磁光學或聲學方式，尤其是通過數據處理通信網絡連接到與控制者實體相關的控制者設備的連接裝置，上述控制者設備尤其具有終端或遠程伺服器的形式；上述終端設備被用來執行下列步驟*步驟1涉及確認R的操作每次見證者設備的計算確認R的裝置使用如權利要求1所述的過程計算各個確認R；見證者設備具有通過互連裝置向證明者設備發送所有或部分確認R的發送裝置，此後被稱作見證者設備的發送裝置，*步驟2和3涉及質問d的操作，涉及應答D的操作證明者設備包括計算裝置，此後被稱作證明者的計算裝置，計算裝置使用一個散列函數h計算至少一個令牌T，其中散列函數的參數包括消息M和所有或部分確認R，證明者設備還具有通過連接裝置向控制者設備發送各個令牌T的發送裝置，此後被稱為證明者設備的發送裝置，(在接收令牌T之後，上述控制者設備產生數量與確認R相同的質問d)，見證者設備接收質問d的裝置通過控制者設備和證明者設備之間的連接裝置和證明者設備與見證者設備之間的互連裝置接收來自控制者設備的各個質問d，見證者設備計算應答D的裝置使用如權利要求1所述的過程根據質問d計算應答D，*步驟4涉及檢查的操作證明者的發送裝置向執行檢查的控制者設備發送各個應答D。
14.如權利要求11所述的終端設備，上述終端設備被用來通過一個被稱作籤名實體的實體產生一個此後被稱為籤名消息的消息M的數字籤名；已籤名消息包括-消息M，-質問d和/或確認R，-應答D；上述終端設備包括一個與籤名實體相關的籤名設備，上述籤名設備通過互連裝置與見證者設備互連並且尤其可以具有漫遊對象中邏輯微電路的形式，例如基於微處理器的銀行卡中微處理器的形式，上述籤名設備包括以電子，電磁光學或聲學方式，尤其是通過數據處理通信網絡連接到與控制者實體相關的控制者設備的連接裝置，上述控制者設備尤其具有終端或遠程伺服器的形式；籤名運算上述終端設備被用來執行下列步驟*步驟1涉及確認R的操作每次見證者設備的計算確認R的裝置使用如權利要求1所述的過程計算各個確認R，見證者具有通過互連裝置向籤名設備發送所有或部分確認R的發送裝置，此後被稱作見證者設備的發送裝置，*步驟2涉及質問d的操作籤名設備包括計算裝置，此後被稱作籤名設備的計算裝置，上述計算裝置使用一個散列函數h計算一個二進位序列並且從這個二進位序列中提取出數量等於確認R的數量的質問d，其中散列函數的參數包括消息M和所有或部分確認R，*步驟3涉及應答D的操作見證者設備接收質問d的裝置通過互連裝置接收來自籤名設備的各個質問d，見證者設備計算應答D的裝置使用如權利要求1所述的過程根據質問d計算應答D，見證者設備包括通過互連裝置向籤名設備發送應答D的發送裝置，此後被稱作見證者設備的發送裝置。
15.被用來證明以下內容的控制者設備，上述控制者設備尤其具有與控制者實體相關的終端或遠程伺服器的形式-一個實體的真實性和/或-與這個實體相關的消息M的完整性；通過所有或部分下列參數或這些參數的派生參數完成這個證明-m對公開數值G1，G2，…Gm(m大於或等於1)，-由上述f個素數p1，p2，…pf(f大於或等於2)的乘積構成的一個對於控制者設備和相關控制者實體是未知數的公開模數n；上述模數，上述私有和公開數值具有下面類型的關係Gi.Qiv{1.mod n或Gi{Qivmod n；其中v表示一個具有以下形式的公開指數v＝2k其中k是大於1的安全參數；其中Qi是一個控制者設備未知並且與公開數值Gi相關的私有數值；上述m個公開數值Gi是小於f個素數p1，p2，…pf的m個不同基數g1，g2，…gm的平方gi2；產生上述f個素數p1，p2，…pf和/或上述m個基數g1，g2，…gm以滿足下面的條件第一條件各個等式xvgi2mod n(1)均不能被以n為模的整數環中的x求解第二條件如果Gi{Qivmod n成立，在通過以n為模把Qi乘方k-1次獲得的m個數值qi中有一個qi不同於±gi(即是一個非無效解)。如果Gi.Qiv{1 mod n成立，在通過以n為模把Qi的反置乘方k-1次獲得的m個數值qi中有一個qi不同於±gi(即是一個非無效解)；第三條件2m等式中的至少一個x2{gimod n(2)x2{-gimod n(3)可以被以n為模的整數環中的x求解。
16.如權利要求15所述的控制者設備，該控制者設備被用來向一個被稱作控制者的實體證明一個被稱作證明者的實體的真實性；上述控制者設備包括以電子，電磁光學或聲學方式，尤其是通過數據處理通信網絡連接到與證明者實體相關的證明者設備的連接裝置；上述控制者設備被用來執行下列步驟*步驟1和2涉及確認R的操作，涉及質問d的操作上述控制者設備還具有通過連接裝置接收來自證明者設備的所有或部分確認R的裝置，控制者設備具有質問產生裝置，該裝置在接收所有或部分確認R之後產生數量等於確認R的數量的質問d，每個質問d包括m個此後被稱作基本質問的整數di；控制者設備還具有通過連接裝置向證明者發送所有或部分質問d的發送裝置，此後被稱作控制者的發送裝置；*步驟3和4涉及應答的操作，涉及檢查的操作上述控制者設備還包括-通過連接裝置接收來自證明者設備的應答D的裝置，-計算裝置，此後被稱作控制者設備的計算裝置，-比較裝置，此後被稱作控制者設備的比較裝置，在證明者發送一部分確認R的情況下如果證明者的接收裝置已經接收一部分確認R，則控制者設備的計算裝置在具有m個公開數值G1，G2，…Gm的情況下根據各個質問d和各個應答D計算一個重構確認R′，這個重構確認R′滿足以下類型的關係R』{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R』{Dv/G1d1.G2d2.…Gmdm.mod n控制者設備的比較裝置將各個重構確認R′與接收的所有或部分確認R進行比較，在證明者已經全部發送確認R的情況下如果證明者的發送計算裝置已經接收全部確認R，則控制者設備的計算裝置和比較裝置在具有m個公開數值G1，G2，…Gm的情況下確定各個確認R滿足以下類型的關係R{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R{Dv/G1d1.G2d2.…Gmdm.mod n
17.如權利要求15所述的控制者設備，該控制者設備被用來證明與一個被稱作證明者的實體相關的消息M的完整性，上述控制者設備包括以電子，電磁光學或聲學方式，尤其是通過數據處理通信網絡連接到與證明者實體相關的證明者設備的連接裝置，上述控制者設備允許執行下列步驟*步驟1和2涉及確認R的操作，涉及質問d的操作上述控制者設備還具有通過連接裝置接收來自證明者設備的令牌T的裝置，控制者設備具有質問產生裝置，該裝置在接收令牌T之後產生數量等於確認R的數量的質問d，各個質問d包括m個此後被稱作基本質問的整數；控制者設備設備還具有通過連接裝置向證明者發送所有或部分質問d的發送裝置，此後被稱作控制者設備的發送裝置；*步驟3和4涉及應答D的操作，涉及檢查的操作上述控制者設備還包括-通過連接裝置接收來自證明者設備的應答D的裝置，-計算裝置，此後被稱作控制者設備的計算裝置，上述計算裝置在具有m個公開數值G1，G2，…Gm的情況下首先根據各個質問d和各個應答D計算計算一個重構確認R′，這個重構確認R′滿足以下類型的關係R』{G1d1.G2d2.…Gmdm.Dvmod n；或以下類型的關係R』{Dv/G1d1.G2d2.…Gmdm.mod n接著使用一個散列函數h計算一個令牌T′，其中散列函數的參數包括消息M和所有或部分重構確認R′，控制者設備還包括-將令牌T＇與接收的令牌T相比較的比較裝置，此後被稱作控制者設備的比較裝置。
18.如權利要求15所述的控制者設備，上述控制者設備被用來通過使用一個被稱作控制者的實體檢查籤名消息來證明消息M的真實性；通過一個與具有散列函數h(消息，R)的籤名實體相關的籤名設備發送的籤名消息包括-消息M，-質問d和/或確認R，-應答D；檢查運算上述籤名設備包括以電子，電磁光學或聲學方式，尤其是通過數據處理通信網絡連接到一個與控制者實體相關的籤名設備的連接裝置，上述控制者設備已經通過連接裝置從籤名設備接收了已籤名消息，控制者設備包括-計算裝置，此後被稱作控制者設備的計算裝置，-比較裝置，此後被稱作控制者設備的比較裝置，在控制者設備具有確認R，質問d，應答D的情況下如果控制者具有確認R，質問d，應答D，控制者設備的計算和比較裝置確定消息M，質問d和確認R滿足以下關係R{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R{Dv/G1d1.G2d2.…Gmdm.mod n控制者設備的計算和比較裝置確定消息M和質問d滿足散列函數d＝h(消息，R)在控制者設備具有確認R和應答D的情況下如果控制者設備具有確認R，應答D，控制者設備的計算裝置使用散列函數並且計算d′，使得d』＝h(消息，R』)控制者設備的計算和比較裝置確定消息M，質問d′和確認R滿足以下關係R{G1d1.G2d2.…Gmdm.Dvmod n或以下類型的關係R{Dv/G1d1.G2d2.…Gmdm.mod n
全文摘要
本發明涉及一個通過以下數值進行證明的方法m(≥1)對私有數值Q
文檔編號H04L9/32GK1433609SQ00817730
公開日2003年7月30日 申請日期2000年9月29日 優先權日1999年10月1日
發明者路易斯·吉盧, 讓-雅克·吉斯卡特 申請人:法國電信公司, 法國電視傳播公司, 馬思·裡茲克