可交换矩阵

可交换矩阵（共4篇）

可交换矩阵 篇1

矩阵的乘法不满足交换律, 其原因有以下几点:

①AB有意义时, BA不一定有意义;

②AB与BA均有意义时, 阶数可能不相等;

③AB与BA均有意义, 且阶数相等时, 仍可能出现AB≠BA.

若AB=BA成立, 则称方阵A与B为可交换矩阵.设f (x) =amxm+am-1xm-1+…+a1x+a0, 系数a0, a1, …, am均为数域P中的交换数, A为P上的一个n阶方阵, 记

f (A) =amAm+am-1Am-1+…

+a1A+a0E.

容易看出:任何方阵A都与其伴随矩阵A*是可交换的, 且二者的乘积为|AI|n;对于任何方阵A, f (A) =a0Ap+a1Ap-1+…+apI与g (A) =b0Aq+b1Aq-1+…+bqI, 可交换.

定理1 设n阶方阵A, B满足条件A+B=AB, 则A, B可交换.

证明 由条件A+B=AB变形可得

-I=A-I+B-AB= (A-I) +B (I-A)

=- (A-I) (B-I) ,

即 (A-I) (B-I) =I.

所以A-I为可逆矩阵, 其逆矩阵为B-I, 有

(A-I) (B-I) = (B-I) (A-I) =I.

即 AB-A-B+I=BA-B-A+I.

从而可得AB=BA.

定理2 设A, B均为对称矩阵, 则A, B可交换的充要条件是AB为对称矩阵.

证明 设A, B均为对称矩阵, 由于AB=BA, 则

(AB) T=BTAT=BA=AB,

所以AB是对称的.

反之, 注意到 (AB) T=AB, 所以

AB= (AB) T=BTAT=BA.

因此, A, B可交换.

推论 设A为n阶对称矩阵, 则A, AT都可交换.

定理3 设A为对称矩阵, B为反对称矩阵, 则A, B可交换的充要条件是AB为反对称矩阵.

证明 设AT=A, BT=-B.

由于AB=BA, 所以

(AB) T=BTAT=-BA=- (AB) .

所以AB为反对称矩阵.

反之, 若AB为反对称矩阵, 则

- (AB) = (AB) T=BTAT=- (BA) .

从而AB=BA.

定理4 设A, B均为反对称矩阵, 则A, B可交换的充要条件是AB为对称矩阵.

证明 因A, B均为反对称矩阵, 故有AT=-A, BT=-A, 又因为A, B可交换, 故有AB=BA成立.从而

(AB) T=BTAT= (-B) (-A)

=BA=AB.

反之, 若AB为对称矩阵, 则

AB= (AB) T=BTAT

= (-B) (-A) =BA,

所以AB是可交换的.

定理5 若A, B为同阶可逆矩阵, 则A, B可交换的充要条件是A-1, B-1可交换.

证明 因AB=BA, 故有

B-1A-1= (AB) -1= (BA) -1=A-1B-1,

即 A-1, B-1是可交换的.

反之, 因A-1, B-1可交换, 故有

(BA) -1=A-1B-1=B-1A-1= (AB) -1,

两边求逆得到AB=BA.

推论 可逆矩阵A, B可交换的充要条件是 (AB) -1=A-1B-1.

定理6 若A, B均为n阶方阵, 则A, B可交换的充要条件是 (AB) T=ATBT.

证明 如果AB=BA, 那么

(AB) T= (BA) T=ATBT.

反之, 若 (AB) T=ATBT, 则

(AB) T=ATBT= (BA) T,

即 AB=BA.

定理7 设A, B可交换, 则以下结论成立:

(1) A2-B2= (A-B) (A+B)

= (A+B) (A-B) ;

(2) (A±B) 2=A2±2AB+B2;

(3) (AB) k=AkBk, ABm=BmA,

其中k, m分别为正整数;

(4) Am-Bm

= (A-B) (Am-1+Am-2B+…+Bm-1

= (Am-1+Am-2B+…+Bm-1)

(A-B) ;

$(5)(\mathit{A}+\mathit{B}){}^m={\displaystyle \sum _{k=0}^m\text{C}}{}_m^k\mathit{A}{}^{m-k}\mathit{B}{}^k.$

证明 (1) 因为

(A-B) (A+B) =A2+AB-BA-B2,

(A+B) (A-B) =A2-AB+BA-B2,

由已知AB=BA, 可得

A2-B2= (A-B) (A+B)

= (A+B) (A-B) .

(2) (A+B) 2= (A+B) (A+B)

=A2+AB+BA+B2,

由已知AB=BA, 可得

(A+B) 2=A2+2AB+B2.

同理可得

(A-B) 2=A2-2AB+B2.

(3) 由已知AB=BA, 可得

(AB) k=ABAB…AB=AABB…AB

=AA…AB…B=AkBk,

ABm=ABB…B=BAB…B=…

=BB…BA=BmA.

(4) 运用数学归纳法.

①当m=2时, 由 (1) , 等式成立, 即

A2-B2= (A-B) (A+B) .

②假设m=k-1时, 等式成立, 即有

Ak-1-Bk-1= (A-B) (Ak-2+Ak-3B+…+Bk-2) .

③则当m=k时, 由已知AB=BA, 有

Ak-Bk= (Ak-1-Bk-1) (A+B)

-Ak-1B+Bk-1A

= (A-B) (Ak-2+Ak-3B+…+Bk-2)

(A+B) -Ak-1B+Bk-1A

=Ak+Ak-1B+…+A2Bk-2-B2Ak-2

-B3Ak-3-…-Bk-Ak-1B+Bk-1A.

由性质4.1 (3) 有

Bk-1A=ABk-1, Ak-1B=BAk-1,

因此, 上式可转化为

Ak-Bk

=Ak+Ak-1B+…+A2Bk-2-B2Ak-2

-…-Bk-Ak-1B+Bk-1A

=Ak+Ak-1B+…+A2Bk-2+ABk-1

-BAk-1-B2Ak-2-B3Ak-3-…-Bk

=Ak-1 (A-B) +Ak-2B (A-B) +…

+Bk-1 (A-B)

= (A-B) (Ak-1+Ak-2B+…+Bk-1) .

即证得

Am-Bm= (A-B) (Am-1+Am-2B+…

+Bm-1) .

同理可证得

Am-Bm= (Am-1+Am-2B+…+Bm-1) (A-B) .

(5) 对m用数学归纳法同 (4) 即可得证.

定理8 矩阵A能与一切n阶矩阵可交换的充分必要条件是A为数量矩阵.

证明 若A与一切n阶矩阵可交换, 自然与对角线上元素互不相同的对角矩阵可交换, 由此可知A必为一对角矩阵.设

$\mathit{A}=\left(\begin{array}{cccc}d{}_1& & & \\ & d{}_2& & \\ & & \ddots & \\ & & & d{}_n\end{array}\right)$

,

取矩阵

$\mathit{B}=\left(\begin{array}{cccc}1& 1& \cdots & 1\\ 0& 0& \cdots & 0\\ ⋮& ⋮& \cdots & ⋮\\ 0& 0& \cdots & 0\end{array}\right)$

,

代入条件AB=BA, 得d1=d2=…=dn, 所以A是一个数量矩阵.

反之, 设A=aI, B为任一n阶矩阵, 则

AB= (aI) B=aB=Ba

= (BI) a=B (Ia) =BA.

摘要：从可交换矩阵的定义出发, 给出了可交换矩阵的一些性质和充要条件.

关键词：矩阵,交换,对称

参考文献

[1]刘仲奎, 杨永保, 程辉, 等.高等代数[M].北京:高等教育出版社, 2003.

[2]王晓易, 王庆生.线性代数学习辅导[M].北京:科学技术文献出版社, 2000.

可交换矩阵 篇2

关键词：矩阵,线性变换,可交换

一预备知识

一般情况下, 矩阵 (线性变换) 的乘法不满足交换律, 即AB≠BA (AB=BA) , 但是在某些特殊情况下, 矩阵 (线性变换) 乘法的交换律也可成立。

定义1:设A, B∈Cn×n, 如果AB=BA成立, 则称矩阵A, B可交换。

定义2:设V为线性空间, A, B为V上的线性变换, 如果AB=BA成立, 则称线性变换A, B可交换。

矩阵和线性变换的可交换性质是它们的特殊性质, 在某些问题上借助于矩阵和线性变换可交换的性质, 可以进一步得到许多相当好的结论。

二主要应用

例1, 设A, B都是n阶实对称正定矩阵, 则AB是实对称正定矩阵当且仅当AB=BA。

证:充分性:因为A, B都是实对称正定矩阵, 且AB=BA, 所以 (AB) T=BTAT=BA=AB, 即AB是实对称矩阵。另一方面, 存在实可逆矩阵C, D, 使A=CTC, B=DTD, 则AB=CTCDTD=D-1DCTCDTD=D-1[ (CDT) T (CDT) D], 因而AB相似于 (CDT) T (CDT) 。因为 (CDT) T (CDT) 正定, 所以AB的所有特征值皆为正数, 又AB实对称, 于是AB正定。

必要性:因为AB正定, 所以有可逆实矩阵P, 使得PTABP=E, 于是PTBTATP=PTBAP=E, 即PTABP=PTBAP, 左乘 (PT) -1, 右乘P-1得, AB=BA。

上例说明矩阵的可交换性在判断矩阵乘积是否正定时是一个很重要的条件, 如果缺少该条件, 则相关结论不一定成立。

例2, 设A与B均为n阶实对称正定矩阵, 且A-B也是正定阵。问C=A2-B2是否正定阵?是的话, 请证明, 否则, 举出反例。

一个错误的方法:A2-B2=A2+AB+AB-B2=A (A+B) + (A-B) B, 因为A与B均为n阶实对称正定矩阵, 则A+B为实对称正定阵。

又知A-B也是正定阵, 故A (A+B) 正定, (A-B) B正定。所以A (A+B) + (A-B) B正定, 即C=A2-B2正定。

[分析]该证明看起来似乎没有什么问题, 但仔细分析就会发现, 在证明过程中忽略了一个很重要的条件——矩阵乘积的可交换性, 即A和 (A+B) 及 (A-B) 和B是否可交换, 本质上就是A, B是否可交换, 所以该证明是错误的。实际上C=A2-B2不一定正定。

例3, 设A, B都是n维线性空间V的线性变换。证明:如果A的n个特征值互异, 则AB=BA的充要条件是A的特征向量也是B的特征向量。

证:设λ1, λ2, …, λn为A的全部特征值, 且λi≠λj (i≠j) , 属于λi的特征向量为αi (i=1, 2, …, n) 。因为属于不同特征值的特征向量线性无关, 故α1, α2, …, αn为V的一个基。

必要性:设AB=BA, 且A, B在基α1, α2, …, αn下的矩阵分别为A, B。则A (α1, …, αn) = (λ1α1, …, λnαn) = (α1, …, αn) A, 其中A=diag (λ1, …, λn) 。

由AB=BA得AB=BA。因为与对角元素彼此不同的对角矩阵可交换的矩阵只能是对角矩阵, 所以B=diag (μ1, …, μn) 。这时从B (α1, α2, …, αn) = (α1, α2, …, αn) B, 得到Bαi=μiαi (i=1, 2, …, n) 。

充分性:若A的特征向量也是B的特征向量, 则A (α1, α2, …, αn) = (α1, α2, …, αn) diag (λ1, …, λn) , B (α1, α2, …, αn) = (α1, α2, …, αn) diag (μ1, …, μn) 。

于是, A与B在基α1, …, αn下的矩阵A与B可换:

diag (λ1, …, λn) diag (μ1, …, μn) =diag (μ1, …, μn) diag (λ1, …, λn) , 即AB=BA, 因此AB=BA。

注:上述问题用矩阵语言描述, 即设A, B为n阶复矩阵, 且A有n个互不相同的特征值。则AB=BA⇔A, B有n个相同的线性无关特征向量⇔存在n阶可逆矩阵P, 使P-1AP与P-1BP同时为对角阵。

三结语

矩阵和线性变换的可交换性是高等代数学习过程中颇令教师和学生头疼的问题, 通过将可交换性在矩阵和线性变换之间的转换, 可以将问题化难为易, 帮助学生理解教学内容, 提高学习效果。

参考文献

[1]陈公宁.矩阵理论与应用[M].北京:科学出版社, 2007

[2]程云鹏.矩阵论[M].西安:西北工业大学出版社, 1999

酉矩阵在矩阵张量积交换中的应用 篇3

文献[1]利用正交矩阵实现了两个矩阵做张量积可交换的情况,文献[2]证明了交换后它们的数值半径依然相等的问题。在文献[1]的基础上,利用酉矩阵与相应的单位矩阵做张量积后所得酉矩阵实现了三个矩阵做张量积可任意交换的情形。进而推广到多个矩阵做张量积任意两个或多个相邻的非相邻的矩阵可交换,这是一个很漂亮的结论。它解决了文献[2]中多个矩阵做张量积进行倒序交换和有限个矩阵发生交换后数值半径仍然相等的问题。本文的相关定理的符号同于文献[1]和文献[2]。

1预备知识

定理1.1[1] 设A,B分别为m×m和n×n矩阵,则存在一个mn阶排列矩阵P使得

${\rm P}{}^{\text{Τ}}(A⨂B){\rm P}=B⨂A。$

定理1.2[1] 设矩阵A∈Mm×p,B∈Mp×s,C∈Mm×n,D∈Ms×q,则

$(A⨂B)(C⨂D)=(AC⨂BD)。$

定理1.3[2] 设A,B∈L(U),则数值半径

$r(A⨂B)=r(B⨂A)。$

2主要结论

首先详细介绍在复数域内三个矩阵做张量积利用酉矩阵实现任意交换的情况。

定理2.1 设A∈Mm×m,B∈Mp×p,C∈Mk×k那么存在一个mp阶的酉矩阵P使得

$({\rm P}{}^{\text{Τ}}⨂{\rm I}{}_k)(A⨂B⨂C)({\rm P}⨂{\rm I}{}_k)=B⨂A⨂C。$

证明 (PT⨂Ik)(A⨂B⨂C)(P⨂Ik)=

(PT(A⨂B)⨂IkC)(P⨂Ik)=

(PT(A⨂B)P)⨂(IkCIk)=B⨂A⨂C。

定理2.2 设A∈Mm×m,B∈Mp×p,C∈Mk×k那么存在一个pk阶的酉矩阵P使得

(Im⨂PT)(A⨂B⨂C)(Im⨂P)=A⨂C⨂B。

证明 (Im⨂PT)(A⨂B⨂C)(Im⨂P)=A⨂C⨂B=(ImA⨂PT(B⨂C))(Im⨂P)=

ImAIm⨂(PT(B⨂C)P)=A⨂C⨂B。

定理2.3 设A∈Mm×m,B∈Mp×p,C∈Mk×k,那么存在一个mk阶的酉矩阵P和mp阶酉矩阵Q使得

$\begin{array}{l}({\rm I}{}_p⨂{\rm P}{}^{\text{Τ}})(Q{}^{\text{Τ}}⨂{\rm I}{}_k)(A⨂B⨂C)\times \\ (Q⨂{\rm I}{}_k)({\rm I}{}_p⨂{\rm P})=B⨂C⨂A。\end{array}$

证明 由定理2.1和定理2.2可直接推得。

定理2.4 设A∈Mm×m,B∈Mp×p,C∈Mk×k,那么存在一个mk阶的酉矩阵P,mp阶酉矩阵Q和pk阶酉矩阵W使得

(WT⨂Im)(Ip⨂PT)(QT⨂Ik)(A⨂B⨂C)×

(Q⨂Ik)(Ip⨂P)(W⨂Im)=C⨂B⨂A。

证明 (WT⨂Im)(Ip⨂PT)(QT⨂Ik)×

(A⨂B⨂C)(Q⨂Ik)(Ip⨂P)(W⨂Im)=

(WT⨂Im)(Ip⨂PT)(QT(A⨂B)⨂IkC)×

(Q⨂Ik)(Ip⨂P)(W⨂Im)=

(WT⨂Im)(Ip⨂PT)(QT(A⨂B)Q⨂IkCIk)×

(Ip⨂P)(W⨂Im)=

(WT⨂Im)(Ip⨂PT)(B⨂A⨂C)(IP⨂P)×

(W⨂Im)=(WT⨂Im)(B⨂C⨂A)(W⨂Im)=

C⨂B⨂A。

定理2.5 设A∈Mm×m,B∈Mp×p,C∈Mk×k,那么存在一个mk阶的酉矩阵P,mp阶酉矩阵Q和pk阶酉矩阵W使得

(Ik⨂Q)(WT⨂Im)(Ip⨂PT)(QT⨂Ik)×

(A⨂B⨂C)×(Q⨂Ik)(Ip⨂P)(W⨂Im)(Ik⨂QT)=C⨂A⨂B。

证明 由定理2.2和定理2.4可直接证明。

有了上面这5个定理可以实现3个矩阵做张量积的任意转化。那么对于多个矩阵做张量积又是怎样的一种情况呢?下面的定理给出了相应回答。

定理2.6 设A1∈Mm1×m1,…,Ak∈Mmk×mk,那么存在一个mtmt+1阶的酉矩阵P使得

(Im1…mt-1⨂PT⨂Imt+2…mk)(A1⨂…⨂

At⨂At+1⨂…⨂Ak) (Im1…mt-1⨂P⨂Imt+2…mk)=

A1⨂…⨂At+1⨂At⨂…⨂Ak。

证明 (Im1…mt-1⨂PT⨂Imt+2…mk)(A1⨂…⨂

At⨂At+1⨂…⨂Ak)(Im1…mt-1⨂P⨂Imt+2…mk)=

((Im1…mt-1(A1⨂…⨂At-1))⨂((PT⨂Imt+2…mk)(At⨂At+1⨂…⨂Ak))) (In1…nt-1⨂P⨂Int+2…nk)=

((A1⨂…⨂At-1)⨂((PT⨂Imt+2…mk)(At⨂At+1⨂…⨂Ak))) (In1…nt-1⨂P⨂Int+2…nk)=

((A1⨂…⨂At-1)⨂((PT(At⨂At+1))⨂(Imt+2…mk(At+2⨂…⨂Ak))) (In1…nt-1⨂P⨂Int+2…nk)=

((A1⨂…⨂At-1)⨂((PT(At⨂At+1))⨂(At+2⨂…⨂Ak))(In1…nt-1⨂P⨂Int+2…nk)=

((A1⨂…⨂At-1)In1…nt-1)⨂((PT(At⨂At+1)⨂(At+2⨂…⨂Ak)(P⨂Int+2…nk)) =(A1⨂…⨂At-1)⨂((PT(At⨂At+1)P)⨂(At+2⨂…⨂Ak)=

(A1⨂…⨂At-1)⨂(At+1⨂At)⨂(At+2⨂…⨂Ak)=A1⨂…⨂At+1⨂At⨂…⨂Ak。

由此可以看出,既然可以实现相邻两个矩阵的交换,就可以实现任意两个非相邻矩阵的交换。因此可以有下述定理。

定理2.7 设A1∈Mm1×m1,…,Ak∈Mmk×mk,那么存在一个合适维数的酉矩阵P使得

$\begin{array}{l}{\rm P}{}^{\text{Τ}}(A{}_1⨂\cdots ⨂A{}_i\cdots ⨂A{}_t⨂\cdots ⨂A{}_k){\rm P}=\\ A{}_1⨂\cdots ⨂A{}_t\cdots ⨂A{}_i⨂\cdots ⨂A{}_k。\end{array}$

不仅可以实现任意两个的交换,也可以实现任意有限个的交换,满足这种交换的酉矩阵一定是存在的.并且经过交换后做张量积所得新矩阵与原矩阵是相似的,从而容易得出下面的定理。

定理2.8 设A1∈Mm1×m1,…,Ak∈Mmk×mk,那么存在一个合适维数的酉矩阵P使得

$\begin{array}{l}{\rm P}{}^{\text{Τ}}(A{}_1⨂A{}_2\cdots ⨂A{}_{k-1}⨂A{}_k){\rm P}=\\ A{}_k⨂A{}_{k-1}\cdots ⨂A{}_2⨂A{}_1。\end{array}$

定理2.9 经过交换后做张量积所得新矩阵与原矩阵有相同的特征值和特征向量,并且保持范数不变,行列式相等,迹相等,秩相等。

定理2.10 设A1∈Mm1×m1,…,Ak∈Mmk×mk,如果A1⨂A2…⨂Ak-1⨂Ak是酉(厄米特,正交,对称,幂等,正规)矩阵,那么交换后做张量积得到的矩阵仍然是酉(厄米特,正交,对称,幂等,正规)矩阵。

证明 酉矩阵,厄米特,正交,对称,幂等矩阵的情况可以由定理2.9和相关定义直接证明。正规矩阵的情况可以由文献[3]中的定理,A1⨂A2…⨂Ak-1⨂Ak是正规矩阵当且仅当每个Ai都是正规矩阵证明。

文献[2]指出数值半径r(A⨂B)=r(B⨂A)。现在利用定理2.8可以把矩阵个数进行推广。容易得下面的定理2.11。符号及对相应矩阵的定义同于文献[2]。

定理2.11 设A1,…,Ak∈L(U),并且都为方阵,那么

(1)r(A1⨂A2…⨂Ak-1⨂Ak)=r(Ak⨂Ak-1…⨂A2⨂A1)。

(2)r(A1⨂…⨂Ai…⨂At⨂…⨂Ak)=

r(A1⨂…⨂At…⨂Ai⨂…⨂Ak)。

证明(1) 由定理2.9知

r(Ak⨂Ak-1…⨂A2⨂A1)=r(PT(A1⨂A2…⨂Ak-1⨂Ak)P)=

$\underset{\left|x\right|=1}{{\displaystyle \sup }}\left|\left[{\rm P}{}^{\text{Τ}}(A{}_1⨂A{}_2\cdots ⨂A{}_{k-1}⨂A{}_k){\rm P}x,x\right]\right|=$

$\underset{\left|x\right|=1}{{\displaystyle \sup }}\left|\left[(A{}_1⨂A{}_2\cdots ⨂A{}_{k-1}⨂A{}_k){\rm P}x,{\rm P}x\right]\right|=$

$\underset{\left|y\right|=1}{{\displaystyle \sup }}\left|\left[(A{}_1⨂A{}_2\cdots ⨂A{}_{k-1}⨂A{}_k)y,y\right]\right|=$

r(A1⨂A2…⨂Ak-1⨂Ak)。

(2)利用定理2.7与(1)的证明类似,不再赘述。

参考文献

[1] 戴华.矩阵论.北京:科学出版社,2001

[2] Hou Qianmin.One ineguality and an equality on the numerical radius of matrix tensor product.Journal of Shanxi University (Nat Sci Ed),2007;30(3):312—314

可交换矩阵 篇4

网络技术,特别是基于互联网的工具的不断成熟与发展,传统的事务处理、商业活动以及政府服务等越来越通过网络实施,大大加快了社会信息化的发展,对计算机和网络系统的依赖性也越来越大,信息系统中的安全问题势必会影响到信息产业的应用和发展。要保证信息的安全性,一个有效的解决办法就是利用密码术。密码学是信息安全的基础和关键,利用密码技术,可以实现信息的保密性、完整性、认证性和抗抵赖性。密码协议是实现网络通信和网络体系、分布式系统和电子商务安全运行的核心组成部分,是安全系统的主要保障手段和工具,密钥交换是保密通信的前提和保证,是实施其他密码协议的关键,是公钥基础设施的基础。密钥交换协议,在密码学与信息安全领域具有很强的实际意义。

密码学中的一个核心问题是在有敌手控制的网络中如何实现安全可靠的通信,为了解决这个问题,实体之间必须共享一个密钥并利用现有的技术来实现安全通信。密钥交换协议就是这样一个机制,它允许两个或多个用户在开放的网络环境中通过协商,建立一个便于保密通信的会话密钥,从而实现安全通信。公钥密码学提供了密钥交换机制,产生了许多密钥交换算法,如Diffie-Hellman算法[1],ECMQV密钥交换算法[2]加密密钥交换算法[3]等。使用密钥交换协议,实现了不安全的信道上的密钥交换[4,5,6,7]。公钥密码学提供的密钥交换体制基于数论中的困难问题,比如离散对数问题[8],大整数的因子分解问题[9],椭圆曲线问题[10]等。这都需要大量的数学运算,而在有限的资源下实现起来比较困难。为了解决这个问题,人们提出了基于矩阵的密钥交换协议[11,12],利用矩阵,不需要选取大的素数,使用矩阵进行运算,能够有效提高运算效率,基于矩阵的密钥交换协议也成为了一个密钥交换的研究热点。随着对密钥交换协议不断地进行研究,对提出的协议进行分析,有的协议的缺陷已被找出并被攻破,因此,改进密钥交换协议,设计出更为安全的密钥交换协议具有重大意义。

2009年,lvarez等人提出了一种基于上三角矩阵幂乘运算的密钥交换方案[13],该方案避免了大素数的选取,使用矩阵进行运算,提高了运算效率。2013年,Kamal等人对lvarez等的方案进行了研究和分析,利用该方案中的公开参数,找出了该方案的不足之处,给出了一种可能的攻击方案[14]。本文通过对Kamal等人提出的攻击方案进行分析研究,利用矩阵多项式乘法的交换性,通过对矩阵进行多项式运算,改进lvarez等提出的密钥交换方案,改进后的方案可以有效抵抗Kamal等人提出的攻击,并对改进方案进行了可行性验证和安全性分析。

1 预备知识

1. 1 lvarez 等人的密钥交换方案简介[13]

lvarez等人提出了一种基于非交换的上三角矩阵上的密钥交换方案,下面回顾一下该方案。

定义1非交换矩阵群

其中,0: s×r的0矩阵; p: 一个素数; r,s∈N; Glr( Zp) : 模p剩余类下的r×r可逆矩阵; Gls( Zp) : 模p剩余类下的s×s可逆矩阵;Matr×s( Zp) : 模p剩余类下的r×s矩阵。

定义2若M∈Θ且h≥0 ,则:

其中:

定义3设:

为Θ中的两个元素M1、M2分别为m1、m2阶方阵。对于x,y∈N,定义:

lvarez等的密钥交换方案如下:

1) Alice和Bob共同协商一个素数p,以及矩阵M1,M2∈Θ,其中M1、M2分别为m1、m2阶方阵。

2) Alice随机选取两个整数l,m∈N,其中1≤l≤m1- 1,1≤m≤m2- 1; 并计算Alm,Blm,Clm,构造:

3) Alice将C发送给Bob。

4) Bob随机选取两个整数v,w∈N,其中1≤v≤m1- 1,1≤w≤m2- 1; 并计算Avw、Bvw、Cvw,构造:

5) Bob将D发送给Alice。

6) Alice和Bob的公钥分别为C和D。

7) Alice计算:

Ka为矩阵:

中r×s的上三角矩阵。

8) Bob计算:

Kb为矩阵:

中r×s的上三角矩阵。

经过该方案,Alice和Bob共享密钥K = Ka= Kb。

1. 2 对lvarez 等的密钥交换方案的攻击[14]

Kamal等人对lvarez等的方案进行了分析,并提出了攻击方案,下面回顾一下该攻击方案。

简化lvarez等的方案如下:

1) Alice和Bob共同协商一个素数p,以及两个矩阵M1,M2∈Θ。

2) Alice将公钥C = Ml1Mm2发送给Bob。

3) Bob将公钥D = Mv1Mw2发送给Alice。

4) Alice和Bob都计算M1l + vM2w + m,并提取它的上三角矩阵作为他们的共享密钥。

在下文中,我们将分析表明,通过传输信道上公开的矩阵C和D ,攻击者可以很容易地恢复出Alice和Bob所建立的共享密钥。

引理1取 ( r + s) × ( r + s) 的可逆矩阵W1、W2,使其满足:

可得:

攻击者通过公钥C,选取两个可逆矩阵W1、W2,使其满足引理1中的公式,即可得出Alice和Bob的共享密 钥,即为M1l + vM2w + m的上三角r×s的矩阵。

由lvarez等的方案,可知,攻击者可以窃听到的参数有:Alice和Bob共同协商的素数p,矩阵M1、M2,Alice发送给Bob的公钥C = M1lM2m,以及Bob发送给Alice的公钥D = M1vM2w。攻击者不能得到的参数有: Alice随机选取两个整数l、m ,Bob随机选取两个整数v,w∈N。

通过引理1,可知,攻击者不需知道Alice和Bob选取的私钥l、v、w、m,也不需要得到矩阵M1l、M1v、M2w、M2m,只要攻击者找出满足引理1中等式的矩阵W1和W2,即可恢复出Alice和Bob的共享密钥。

另外,通过引理1,我们不难看出,要想找出符合条件的矩阵W1、W2,必须得到Alice和Bob协商的矩阵M1、M2。针对这一特点,在下文中,我们设法对矩阵M1、M2进行加密,利用攻击者不能找到W1、W2这一思路,对lvarez等人的密钥交换方案进行改进。

2 改进的 lvarez 等人的密钥交换方案

Kamal等人提出的攻击方案中,攻击者通过公开的矩阵M1、M2、C、D,只需找出符合条件的W1、W2,就可得到Alice和Bob的共享密钥。针对Kamal等人的攻击方案中通过公开矩阵M1、M2,可找到符合条件的W1、W2这一特点,利用矩阵的多项式幂乘运算,对矩阵M1、M2进行多项式加密运算,改进lvarez等人的密钥交换方案。

引理2[15]对于非交换矩阵群Θ,若M∈Θ,有多项式f( x) 、g( x) 和k,l∈N ,则有:

定义4若f( M) ∈f( Θ) 且h≥0 ,则:

其中:

定义5

为f( Θ) 中的两个元素,f( M1) 、f( M2) 分别为m1、m2阶方阵。对于x,y∈N ,定义:

利用矩阵多项式的幂乘运算,对lvarez等人的密钥交换方案改进如下:

1) Alice和Bob共同协商一个素数p,具有大素数q个多项式的多项式库,以及矩阵M1,M2∈Θ,其中M1、M2分别为m1、m2阶方阵。

2) Alice随机选取两个整数l,m∈N,多项式库中的一个多项式f( x) ,其中1≤l≤m1- 1,1≤m≤m2- 1; 并计算f( Alm) 、f( Blm) 、f( Clm) ,构造:

3) Alice将f( C) 发送给Bob。

4) Bob随机选取两个整数v,w∈N,多项式库中的一个多项式g( x) ,其中1≤v≤m1- 1,1≤w≤m2- 1; 并计算g( Avw) 、g( Bvw) 、g( Cvw) ,构造:

5) Bob将g( D) 发送给Alice。

6) Alice和Bob的公钥分别为f( C) 和g( D) 。

7) Alice计算:

Ka为矩阵:

中r×s的上三角矩阵。

8) Bob计算:

Kb为矩阵:

中r×s的上三角矩阵。

则Ka= Kb即为Alice和Bob的共享密钥。

3 改进方案的安全性分析

3. 1 改进方案的可行性

引理3若:

证明:

显然,Ka= Kb,即Alice和Bob协商出共享密钥,改进的方案可行。

3. 2 改进方案的安全性

对改进后的方案进行分析,可知,攻击者通过窃听可以得到的参数有: Alice和Bob共同协商的素数p,具有q个多项式的多项式库,矩阵M1、M2,Alice发送给Bob的公钥f( C)=fl( M1) fm( M2) ,以及Bob发送给Alice的公钥g( D)=gv( M1) gw( M2) 。攻击者不能得到的参数有: Alice随机选取的一个多项式f( x) 以及两个整数l、m ,Bob随机选取的多项式一个g( x) 以及两个整数v,w∈N。

利用Kamal等人提出的攻击方案对改进后的方案进行攻击。根据Kamal等人所提出的攻击思路,结合引理1,可得引理4。

引理4攻击者需找到两个 ( r + s) × ( r + s) 的可逆矩阵W1、W2,使其满足下面的等式:

可得:

在引理1中,分别与矩阵W1、W2具有交换性的矩阵M1、M2是公开的; 而在引理4中,分别与矩阵W1、W2具有交换性的矩阵f( M1) 、f( M2) 是利用多项式运算对矩阵进行加密后的,该多项式的选取是参与者Alice随机选取的,并且未在信道上传输,是私密的。故攻击者不能够窃听到利用多项式加密后的矩阵f( M1) 、f( M2) 。

下面分析一下,攻击者通过公钥也不能得到参与者所选取的多项式。

改进后的方案基于解决离散对数问题的困难性假设,通过对M1、M2加入多项式运算并对加入多项式后的矩阵进行幂乘运算,能够有效地抵抗Kamal等人提出的攻击。攻击者能够截获公钥f( C) 、g( D) ,根据已知的矩阵M1、M2需要试图解决下面的等式:

要想解决上面的等式,攻击者需要试图找到两个多项式h1( x) 、h2( x) 以及α1,α2,β1,β2∈N ,使得:

显然,条件( 1) 容易被满足,由解决离散对数问题的困难性假设,攻击者不能得到Alice和Bob分别选取的多项式f( x) 、g( x) 。攻击者则需要试图通过穷举法试多项式的系数以满足条件( 2) ,公钥f( C) 、g( D) 的系数是由两个整数组成的集合,这就导致了蛮力攻击,故Kamal等人的攻击方案对改进方案是不可行的,即改进后的方案能够有效地抵抗Kamal等人的攻击方案。

4 结 语

对于非交换矩阵群Θ,若M1,M2∈Θ,有多项式f( x) 、g( x) ,则有: