[發(fā)明專利]基于矩陣經(jīng)典分解問題的公鑰密碼體制

無效

• 申請?zhí)枺?/td>: 02129332.5
• 申請日: 2002-09-02
• 公開（公告）號: CN1396741A
• 公開（公告）日: 2003-02-12
• 發(fā)明（設(shè)計）人: 鄭建德
• 申請（專利權(quán)）人: 鄭建德
• 主分類號: H04L9/30
• 分類號: H04L9/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

??????????????????????一、技術(shù)領(lǐng)域

本發(fā)明屬于信息安全領(lǐng)域，特別涉及到一種基于矩陣經(jīng)典分解的公鑰密碼體制。

??????????????????????二、背景技術(shù)

公鑰密碼體制的出現(xiàn)已有26年，但至今國際上通用的主要公鑰密碼體制只有兩大類，一類是基于因數(shù)分解問題(IFP)的公鑰密碼體制，其算法定義在一個整數(shù)環(huán)Z_n上(如RSA和Rabin)；另一類是基于離散對數(shù)問題(DLP)的公鑰密碼體制，其算法定義在一個Galois域GF(p)上(如ElGamal)。以上所述的幾種公鑰密碼體制都在美國等國家獲得過專利(如RSA的專利號為4-405-829)。隨著計算技術(shù)和代數(shù)數(shù)論的發(fā)展，這兩類公鑰密碼體制的安全性都受到日益增大的威脅。近年來，人們利用定義在整數(shù)環(huán)或整數(shù)域上的橢圓曲線建立了與這兩類公鑰密碼體制相似的新的公鑰密碼體制，它們被統(tǒng)稱為橢圓曲線密碼體制。其中比較有應(yīng)用價值的是基于橢圓曲線離散對數(shù)問題(EDLP)的公鑰密碼體制。引入橢圓曲線是否能夠從根本上提高公鑰密碼體制的安全性是目前人們?nèi)栽谘芯康囊粋€問題，但已經(jīng)有人發(fā)現(xiàn)至少在理論上基于EDLP的公鑰密碼體制和基于DLP、IFP的公鑰密碼體制一樣有可能被采用量子算法的攻擊所破解。我們也不能排除這樣一種可能性：即經(jīng)過幾十年的分析研究，實際上已經(jīng)有人找到破解基于IFP、DLP(包括EDLP)的公鑰密碼體制的有效方法，但這個事實被少數(shù)人或少數(shù)國家所隱瞞。因此，研究新的公鑰密碼體制在信息安全領(lǐng)域的實踐中具有重大意義。

?????????????????????三、發(fā)明內(nèi)容

本發(fā)明需要解決的技術(shù)問題是打破現(xiàn)有主要公鑰密碼體制都是基于IFP或DLP，包括EDLP的局限性，研究出一種全新的實用的公鑰密碼體制。本發(fā)明的目的，是利用高階矩陣經(jīng)典分解問題的復(fù)雜性來實現(xiàn)的，其特征是：

(a)信息加密采用的是如下的多維陷門單向函數(shù)：

f(k₁，k₂，…k_r)＝(k₁A^r-1+k₂A^r-2…+k_rI)²b₁+(k₁A^r-1+k₂A^r-2…+k_rI)b₂???(1)其中A是一個根據(jù)公鑰算出的r×r矩陣，b₁和b₂是兩個任選的r維常數(shù)向量，r＞4；

(b)函數(shù)f(k₁，k₂，…k_r)的單向性由矩陣A的經(jīng)典分解問題(即通過相似變換將其化為對角型的問題)的難度來保障；

(c)對函數(shù)f(k₁，k₂，…k_r)求逆的陷門由矩陣A的特征值或特征向量提供。

本發(fā)明的有益效果是為信息安全實踐提供一種全新的公鑰密碼體制，它對于威脅現(xiàn)有公鑰密碼體制安全的一些攻擊方法具有更強(qiáng)的抵御能力。

???????????????????????四、附圖說明

圖一是本發(fā)明的實施流程圖。

????????????????????五、具體實施方式

以下結(jié)合附圖，對本發(fā)明的具體實施，包括設(shè)計算法、制作密鑰、建立陷門單向函數(shù)、加密以及解密過程進(jìn)行詳細(xì)的說明。(一)設(shè)計算法

如附圖所示，設(shè)計算法是實施本發(fā)明的第一步，它包括如下兩個內(nèi)容：

1.設(shè)計算法的定義域，并定義相應(yīng)的加法和乘法運(yùn)算。建議算法的定義域取為實數(shù)域，并采用普通的加法和乘法，乘法計算的實際操作過程中可按四舍五入的規(guī)則保留一定的小數(shù)位數(shù)。

2.設(shè)計各參數(shù)和加、解密計算中各種數(shù)據(jù)的取值范圍。定義域取為實數(shù)域時，還要確定各中間數(shù)據(jù)和計算結(jié)果應(yīng)保留的小數(shù)位數(shù)。小數(shù)位數(shù)的選擇應(yīng)使多余的小數(shù)尾數(shù)得以及時舍棄以節(jié)省計算資源，同時保證計算結(jié)果中數(shù)據(jù)有效位的正確性。(二)制作密鑰

制作密鑰是實施本發(fā)明的第二步，它包括選取私鑰和計算公鑰兩個內(nèi)容：

1.根據(jù)第一步的設(shè)計，選取r個適當(dāng)?shù)恼龑崝?shù)λ₁，λ₂…λ_r作為私鑰，其中r＞4。要求構(gòu)成私鑰的這些數(shù)各不相同。