TWI408938B - Flexible multi - digit signature method - Google Patents

Description

具彈性之多重數位簽章方法

本發明是有關於一種數位簽章方法，特別是指一種具彈性可動態調整順序之多重數位簽章方法。

網路科技發達的時代，利用網路傳送待簽署文件以廣為被企業所使用，而一份待簽署文件往往可能需要多位成員共同簽署，因此，多重數位簽章的技術被開發出來以應用於此。

透過數位簽章的方式的確是一種可以提供相當方便、且節省紙張成本的有效且經濟的方式，但是在方便省錢之餘，對於一份待簽署的機密文件而言，網路傳輸卻始終存在著風險性，因此，如同中華民國專利公告號424371所發表的「在不安全通訊通道傳遞群體訊息時簽署群體簽章的方法」等相關研究成果或是專利紛紛被提出，企圖解決多重數位簽章技術的安全性問題，然而，該等技術卻依然伴隨著相當多的缺點，例如：中華民國專利公告號424371所提出之技術在進行多重數位簽署前需先完成廣播動作，此舉將會增加簽署成本，而且其公文傳遞的順序是固定的，較無法彈性應用於各種情況，此外，該技術的演算法複雜度為O (n )，在運算時間上仍有相當大的改善空間。

因此，本發明之目的，即在提供一種具彈性之多重數位簽章方法，適用於一具有一系統中心及多數個用戶端裝 置之網路系統，其包含下列步驟：組配該系統中心，以執行一系統金鑰產生程序並產生多數個系統公開金鑰；組配該系統中心，以接收N個用戶端裝置之簽章產生請求，且配合組配用戶端裝置以執行一第一多重數位簽章產生程序並得到一第一多重數位簽章，其中N>1，且用戶端裝置為N個發出簽章產生請求之用戶端裝置其中之一；組配用戶端裝置，以接收該多重數位簽章並執行一簽章驗證程序，以確認該多重數位簽章是否為一合法簽章；組配該系統中心與該用戶端裝置，以執行一多重數位簽章產生程序並產生一多重數位簽章，然後將該多重數位簽章送至下一個發出簽章產生請求之用戶端裝置；及組配下一個發出簽章產生請求之用戶端裝置重複執行該簽章驗證程序，並根據該簽章驗證程序之結果判斷是否執行該多重數位簽章產生程序，直到所有發出簽章產生請求之用戶端裝置皆產生對應之多重數位簽章；其中，該系統金鑰產生程序包括：組配該系統中心，以選取一第一系統公開金鑰p 、一第二系統公開金鑰q ，及該第三系統公開金鑰g ，其中，該第二系統公開金鑰q 可以被(p -1)整除之，且該第三系統公開金鑰係由該第一系統公開金鑰p 及該第二系統公開金鑰作一模數運算而得到；及組配該系統中心，以根據一用戶私密金鑰x _i 、該第一系統公開金鑰p ，及該第三系統公開金鑰g 計算出一第四系統公 開金鑰y _i 。

有關本發明之前述及其他技術內容、特點與功效，在以下配合參考圖式之一個較佳實施例的詳細說明中，將可清楚的呈現。

參閱圖1，本發明之具彈性之多重數位簽章方法之一較佳實施例，是適用於以一網路系統來實現。該網路系統包括多數個分別對應每一用戶之用戶端裝置8及一與該等用戶端裝置連接之系統中心9，而本實施例包含：一系統金鑰產生程序1、一第一多重數位簽章產生程序2、一簽章驗證程序3，及一多重數位簽章產生程序4。

當該網路系統建置完成之後，該系統中心9會執行該系統金鑰產生程序1以產生多數個系統公開金鑰，然後，當該系統中心9接收到第一個用戶n經由對應之用戶端裝置N 8發出簽章產生請求時，該系統中心9及該用戶端裝置N 8會共同執行該第一多重數位簽章產生程序2，直到一第一多重數位簽章SIG _N 產生之後，該用戶端裝置N 8經由網路送至下一個向該系統中心9發出簽章產生請求之用戶端裝置N+1 8，該用戶端裝置N+1 8接收到該第一多重數位簽章SIG _N 之後，將執行該簽章驗證程序3以驗證該第一多重數位簽章SIG _N 是否為合法的簽章，若是，則繼續執行該多重數位簽章產生程序4，若否，則中止本實施例之多重數位簽章方法，最後，當該第一多重數位簽章SIG _N 為合法的簽章時，該用戶端裝置N+1 8與該系統中心9共同執行該多重數位簽 章產生程序4以產生一對應之多重數位簽章SIG _{N +1} ，然後將該簽章SIG _{N +1} 送至下一個向該系統中心9發出簽章產生請求之用戶端裝置N+2 8，並由該用戶端裝置N+2 8重複執行該簽章驗證程序3及該多重數位簽章產生程序4，直到所有向該系統中心9發出簽章產生請求之用戶端裝置8皆完成產生對應之簽章。

以下將分別說明每一程序之執行步驟：

系統金鑰產生程序1

聯合參閱圖1、2，子步驟11是當該系統中心9選取二個大質數(Large prime integer)作為一第一系統公開金鑰p 及一第二系統公開金鑰q ，其中，該第二系統公開金鑰q 可以被(p -1)整除之。

子步驟12是該系統中心9選取一該第一系統公開金鑰p 之原根(primitive element)g 作為一第三系統公開金鑰，並根據方程式(F .1)計算出一第四系統公開金鑰：

其中，mod為一模數運算子，x _i 為一用戶私密金鑰，y _i 為該第四系統公開金鑰。

子步驟13是該系統中心9將該第一至第四系統公開金鑰公開，使得該網路系統上的每一用戶皆可經由對應之用戶端裝置8取得該等系統公開金鑰。

第一多重數位簽章產生程序2

聯合參閱圖1、3，當該系統中心9完成該系統金鑰產生程序1之後，當該系統中心9接收第一位用戶n經由對 應之用戶端裝置N 8所發出之簽章產生請求時，該系統中心9將執行該第一多重數位簽章產生程序2，執行步驟如下：子步驟21是該用戶端裝置N 8隨機選取一第一參數k1及一第二參數t ，並送至該系統中心9。

子步驟22是該系統中心9接收該第一參數k ₁ 及該第二參數t 之後，依據方程式(F .2)、(F .3)分別計算出一第一簽章元素r ₁ 及一第二簽章元素T ：

T ≡g ^t (modp ).....(F .3)

其中，mod為一模數運算子，p 為該第一系統公開金鑰，g 為該第三系統公開金鑰。

然後，該系統中心9將該第一簽章元素r ₁ 及該第二簽章元素T 送至該用戶端裝置N 8。

子步驟23是該用戶端裝置N 8隨機選取一第三簽章元素m ₁ 之後，根據方程式(F .4)計算出一第四簽章元素m 及一第五簽章元素s ₁ ：m ₁ +tT ≡x ₁ mr ₁ +k ₁ s ₁ (modq ).....(F .4)

其中，mod為一模數運算子，t 為該第二參數，T 為該第二簽章元素，x ₁ 為該用戶n之用戶私密金鑰，r ₁ 為該第一簽章元素，k ₁ 為該第一參數，q 為該第二系統公開金鑰。

子步驟24是該用戶端裝置N 8將一包括第一至第五簽章元素之第一多重數位簽章SIG _N =(r ₁ ,T ,m ₁ ,m ,s ₁ )經由網路傳送至下一個向該系統中心9發出簽章產生請求之用戶端裝置N+1 8。

簽章驗證程序3

聯合參閱圖1、4，當該用戶端裝置N+1 8接收到該用戶端裝置N 8所送出之第一多重數位簽章SIG _N 時，便會執行該簽章驗證程序3。

子步驟31是該用戶端裝置N+1 8根據方程式(F .5)以驗證該第一多重數位簽章SIG _N 或是其他多重數位簽章是否為一合法簽章：

其中，R ₀ =1、s ₀ =1、R ₁ ≡r ₁ (modp )。

若方程式(F .5)成立則該用戶端裝置N+1 8繼續執行該多重數位簽章產生程序4，若方程式(F .5)不成立則中止本實施例之多重數位簽章方法。

多重數位簽章產生程序4

聯合參閱圖1、5，子步驟41是該用戶端裝置N+1 8隨機選取一第一參數k _i (以下i 的數值範圍皆為i =1,2,...,N ,N +1,...)，並送至該系統中心9。

子步驟42是該系統中心9接收該第一參數k _i ，依據方程式(F .2)計算出一暫存簽章元素r _i ：

其中，mod為一模數運算子，p 為該第一系統公開金鑰，g 為該第三系統公開金鑰。

然後，該系統中心9將該暫存簽章元素r _i 送至該用戶端裝置N+1 8。

子步驟43是該用戶端裝置N+1 8隨機選取一第三參數之後，根據方程式(F .6)計算出一第四簽章元素m ：

其中，mod為一模數運算子，x _i 為該用戶n之用戶私密金鑰，r _i 為該暫存簽章元素，k _i 為該第一參數，q 為該第二系統公開金鑰。且一第一簽章元素R _i 及該第五簽章元素s _i 是根據方程式(F .6)中的R _{i -1} 、s _{i -1} ，以方程式(F .7)、(F .8)得到：R _i ≡R _{i -1} r _i (modp ).....(F .7)

s _i ≡r _i s _{i -1} (modq ).....(F .8)

子步驟44是該用戶端裝置N+1 8根據方程式(F .9)計算出一第三簽章元素m _i ：

其中，mod為一模數運算子，為該第三參數，r _i 為一暫存簽章元素，q 為該第二系統公開金鑰。

子步驟45是該用戶端裝置N+1 8將一包括該第一至第五簽章元素之多重數位簽章SIG _i =(R _i ,T ,m _i ,m ,s _i ),i =1,2,...N ,N +1,...

經由網路傳送至下一個向該系統中心9發出簽章產生請求之用戶端裝置N+2 8。

由上述可以發現，在本實施例中要實現一多重數位簽章方法時，並不需要事先進行一廣播動作以知會該網路系統上之所有用戶，同時，本實施例並無限定所有向該系統中心提出簽章產生需求之用戶端裝置之順序，因此，在不同的情況下，該系統中心可以彈性的調整該多重數位簽章之傳遞順序，也就是說，對於第N個用戶端裝置而言，其 下一個用戶端裝置N+1並不一定是其下一順位之用戶端裝置，該系統中心可以彈性決定將第N個用戶端裝置對應之多重數位簽章傳遞至網路中任一個向系統中心提出需求且尚未產生對應之多重數位簽章的用戶端裝置；最後，依照上述實施例可以發現，所有提出需求之用戶端裝置可依照該系統中新動態調整之順序產生對應之多重數位簽章，因此，本發明之演算法複雜度為O (1)，相較於先前技術而言可以大幅簡化多重數位簽章方法之執行運算成本，綜上所述，故確實能達成本發明之目的。

惟以上所述者，僅為本發明之較佳實施例而已，當不能以此限定本發明實施之範圍，即大凡依本發明申請專利範圍及發明說明內容所作之簡單的等效變化與修飾，皆仍屬本發明專利涵蓋之範圍內。

1‧‧‧系統金鑰產生程序

11~13‧‧‧子步驟

2‧‧‧第一多重數位簽章產生程序

21~24‧‧‧子步驟

3‧‧‧簽章驗證程序

31‧‧‧子步驟

4‧‧‧多重數位簽章產生程序

41~45‧‧‧子步驟

8‧‧‧用戶端裝置

9‧‧‧系統中心

圖1是本發明具彈性之多重數位簽章方法之流程圖；圖2是一系統金鑰產生程序之流程圖；圖3是一第一多重數位簽章產生程序之流程圖；圖4之一簽章驗證程序之流程圖；及圖5之一多重數位簽章產生程序之流程圖。

1‧‧‧系統金鑰產生程序

2‧‧‧第一多重數位簽章產生程序

3‧‧‧簽章驗證程序

4‧‧‧多重數位簽章產生程序

8‧‧‧用戶端裝置

9‧‧‧系統中心

Claims (14)

1. 一種具彈性之多重數位簽章方法，適用於一具有一系統中心及多數個用戶端裝置之網路系統，其包含下列步驟：組配該系統中心，以執行一系統金鑰產生程序並產生多數個系統公開金鑰；組配該系統中心，以接收N個用戶端裝置之簽章產生請求，且配合組配用戶端裝置i 以執行一第一多重數位簽章產生程序並得到一第一多重數位簽章，其中N>1，且用戶端裝置i 為N個發出簽章產生請求之用戶端裝置其中之一；組配用戶端裝置i +1，以接收該多重數位簽章並執行一簽章驗證程序，以確認該多重數位簽章是否為一合法簽章；組配該系統中心與該用戶端裝置i +1，以執行一多重數位簽章產生程序並產生一多重數位簽章，然後將該多重數位簽章送至下一個發出簽章產生請求之用戶端裝置；及組配下一個發出簽章產生請求之用戶端裝置重複執行該簽章驗證程序，並根據該簽章驗證程序之結果判斷是否執行該多重數位簽章產生程序，直到所有發出簽章產生請求之用戶端裝置皆產生對應之多重數位簽章；其中，該系統金鑰產生程序包括：組配該系統中心，以選取一第一系統公開金鑰p 、 一第二系統公開金鑰q ，及一第三系統公開金鑰g ，其中，該第二系統公開金鑰q 可以被(p -1)整除之，且該第三系統公開金鑰g 係由該第一系統公開金鑰p 及該第二系統公開金鑰q 作一模數運算而得到；及組配該系統中心，以根據一用戶私密金鑰x _i 、該第一系統公開金鑰p ，及該第三系統公開金鑰g 計算出一第四系統公開金鑰y _i 。
2. 依據申請專利範圍第1項所述之具彈性之多重數位簽章方法，其中，該系統金鑰產生程序還包括組配該系統中心，以公開該等系統公開金鑰於網路系統中。
3. 依據申請專利範圍第1項所述之具彈性之多重數位簽章方法，其中，該第四系統公開金鑰y _i 計算方式如下： 其中，mod為一模數運算子。
4. 依據申請專利範圍第1項所述之具彈性之多重數位簽章方法，其中，該第一多重數位簽章產生程序包括：組配該用戶端裝置i ，以隨機選取一第一參數k ₁ 及一第二參數t ，並送至該系統中心；組配該系統中心，以接收該第一參數k ₁ 及該第二參數t ，並根據該第一參數k ₁ 、該第二參數t 、該第一系統公開金鑰p 及該第三系統公開金鑰g ，分別計算出一第一簽章元素r ₁ 及一第二簽章元素T ；及組配該用戶端裝置i ，以接收該第一簽章元素r ₁ 及該第二簽章元素T 後，隨機選取一第三簽章元素m ₁ 之後，並 根據該第一參數k ₁ 、該第二參數t 、該第二系統公開金鑰q 、該第一簽章元素r ₁ 、該第二簽章元素T ，及該用戶端裝置i 之用戶私密金鑰x ₁ ，計算出一第四簽章元素m 及一第五簽章元素s ₁ 。
5. 依據申請專利範圍第4項所述之具彈性之多重數位簽章方法，其中，該第一多重數位簽章產生程序還包括組配該用戶端裝置i ，以將一包括第一至第五簽章元素之第一多重數位簽章送至下一個向該系統中心發出簽章產生請求之用戶端裝置i +1。
6. 依據申請專利範圍第4項所述之具彈性之多重數位簽章方法，其中，該第一簽章元素r ₁ 及該第二簽章元素T 計算方式如下： T ≡g ^t (modp )其中，mod為一模數運算子，p 為該第一系統公開金鑰，g 為該第三系統公開金鑰，k ₁ 為該第一參數，t 為該第二參數。
7. 依據申請專利範圍第4項所述之具彈性之多重數位簽章方法，其中，該第四簽章元素m 及該第五簽章元素s ₁ 計算方式如下：m ₁ +tT ≡x ₁ mr ₁ +k ₁ s ₁ (modq )其中，mod為一模數運算子，t 為該第二參數，T 為該第二簽章元素，x ₁ 為該用戶n之用戶私密金鑰，r ₁ 為該第一簽章元素，k ₁ 為該第一參數，q 為該第二系統公開金鑰 。
8. 依據申請專利範圍第1項所述之具彈性之多重數位簽章方法，其中，該簽章驗證程序為該用戶端裝置i +1根據下列方程式以驗證該多重數位簽章的合法性： 其中，R ₀ =1、s ₀ =1、R ₁ ≡r ₁ (modp )。
9. 依據申請專利範圍第1項所述之具彈性之多重數位簽章方法，其中，該多重數位簽章產生程序包括：該用戶端裝置i +1，以隨機選取一第一參數k _i ，並將其送至該系統中心；組配該系統中心，以接收該第一參數k _i ，並根據該第一系統公開金鑰p 、該第三系統公開金鑰g 以計算出一暫存簽章元素r _i ；組配該用戶端裝置i +1，以隨機選取一第三參數，並根據該用戶端裝置i +1之用戶私密金鑰x _i 、該暫存簽章元素r _i 、該第一參數k _i ，該第二系統公開金鑰q 計算出一第四簽章元素m ：組配該用戶端裝置i +1，計算出一第一簽章元素R _i 及該第五簽章元素s _i ；及組配該用戶端裝置i +1，根據該第三參數、該暫存簽章元素r _i 、該第二系統公開金鑰q ，以計算出一第三簽章元素m _i 。
10. 依據申請專利範圍第9項所述之具彈性之多重數位簽章方法，其中，該多重數位簽章產生程序還包括組配該用 戶端裝置i +1，以將一包括該第一至第五簽章元素之多重數位簽章送至下一個向該系統中心發出簽章產生請求之用戶端裝置。
11. 依據申請專利範圍第9項所述之具彈性之多重數位簽章方法，其中，該四簽章元素m 計算方式如下： 其中，mod為一模數運算子，x _i 為該用戶端裝置i +1之用戶私密金鑰，r _i 為該暫存簽章元素，k _i 為該第一參數，q 為該第二系統公開金鑰，i =1,2,...,N ,N +1,...。
12. 依據申請專利範圍第9項所述之具彈性之多重數位簽章方法，其中，該第一簽章元素R _i 計算方式如下：R _i ≡R _{i -1} r _i (modp )其中，mod為一模數運算子，r _i 為該暫存簽章元素，p 為該第一系統公開金鑰，i =1,2,...,N ,N +1,...。
13. 依據申請專利範圍第9項所述之具彈性之多重數位簽章方法，其中，該第五簽章元素s _i 計算方式如下：S _i ≡r _i s _{i -1} (modq )其中，mod為一模數運算子，r _i 為該暫存簽章元素，q 為該第二系統公開金鑰，i =1,2,...,N ,N +1,...。
14. 依據申請專利範圍第9項所述之具彈性之多重數位簽章方法，其中，該第三簽章元素m _i 計算方式如下： 其中，mod為一模數運算子，為該第三參數，r _i 為 該暫存簽章元素，q 為該第二系統公開金鑰。