密码学原理精解【4】

$Z_{256}下的希尔密码$

概述

m ≥ 2 为正整数，表示 m 维向量空间 P 和 C 分别是原文和密文 P = C = ( Z 256 ) m K = { 定义在 Z 256 上的 m × m 的可逆矩阵 } 加解密 : z 256 上的加密： e K ( x ) = x K z 256 上的解密： d K ( y ) = y K − 1 m\ge 2为正整数，表示m维向量空间 \\P和C分别是原文和密文 \\P=C=(Z_{256})^m \\K=\{定义在Z_{256}上的m \times m的可逆矩阵\} \\加解密: \\z_{256}上的 加密：e_K(x)=xK \\z_{256}上的解密：d_K(y)=yK^{-1} m≥2为正整数，表示m维向量空间P和C分别是原文和密文P=C=(Z256​)mK={定义在Z256​上的m×m的可逆矩阵}加解密:z256​上的加密：eK​(x)=xKz256​上的解密：dK​(y)=yK−1

example

K密钥选择

• K的形式
  取m=3，需要选择一个K（密钥）满足$k在Z_{256}下可逆。即：gcd(\mid K\mid ,26)=1$。
  具体原理见密码学原理精解【3】
  K的形式如下面矩阵所示：
  $$K=\left[\begin{array}{ccc}{K}_{11}& K_{12}& K_{13}\\ K_{21}& K_{22}& K_{23}\\ K_{31}& K_{32}& K_{33}\end{array}\right]$$
• 计算K
  使用Julia完成计算(也可使用C++完成)
  1、定义K

julia> k=rand(0:255,3,3)
3×3 Matrix{Int64}:
 180  191   64
 128  120   63
 139   27  168

2、选择K，计算det(k)。

using LinearAlgebra
k=rand(0:255,3,3)
dk=det(k)
while abs(dk)<1.0 || abs(dk-trunc(Int,dk))>0.0
    global k
    global dk
	k=rand(0:255,3,3)
	dk=det(k)
	sleep(1)
	println("try again")
end
dk=dk % 256 	
if dk<0 
	dk=256+dk
end
println(k)
println(dk)

julia> include("e:/learn/learn1.jl")
try again
try again
[55 174 63; 47 135 200; 231 179 148]
200.0

3.保证K可逆。

using LinearAlgebra
isOk=false
k=rand(0:255,3,3)
dk=det(k)
println("trying")
while gcd(trunc(Int,dk),256)!=1 || abs(dk)<1.0 ||abs(trunc(Int,dk)-dk)>0.000001
	global k
	global dk
	k=rand(0:255,3,3)
	dk=det(k)
	dk=dk % 256 	
	if dk<0 
		dk=256+dk
	end
	print(".")	
	sleep(1)
end
println("I found out!")
println(k)
println(dk)

julia> include("e:/learn/learn1.jl")
trying
...I found out!
[16 91 215; 171 253 50; 8 186 121]
121.0

julia> include("e:/learn/learn1.jl")
trying
........I found out!
[109 138 25; 62 128 229; 19 253 224]
207.0

在此，我们取K=
$$K=\left[\begin{array}{ccc}16& 91& 215\\ 171& 253& 50\\ 8& 186& 121\end{array}\right]$$

$|K{|}^{-1}$

$$\begin{gathered} |k|=det|k| \\ |k{|}^{-1}=121^{-1}=201 \end{gathered}$$

julia> for i in range(1,256)
         if (121*i) % 256==1
           println(i)
           println(121*i)
           break
         end
       end

201
24321

$K^{\ast }$

• 下面是在$Z_{26}$下的运算。

using LinearAlgebra
k=[10 5 12 ;3 14 21;8 9 11]
adjoint_k=[0 0 0;0 0 0;0 0 0]
for i in range(1,3)
	index_i=[1,2,3]
	deleteat!(index_i,i)
	for j in range(1,3)
		global k
		index_j=[1,2,3]
		deleteat!(index_j,j)		
		print([index_i,index_j],"=")
		println(k[index_i,index_j])
		a_ij=(-1)^(i+j)*round(Int,det(k[index_i,index_j]))
		a_ij=a_ij % 26
		if a_ij <0 
			a_ij=26+a_ij
		end
		adjoint_k[j,i]=a_ij
	end
end
println(adjoint_k)

julia> include("e:/learn/learn1.jl")
[[2, 3], [2, 3]]=[14 21; 9 11]
[[2, 3], [1, 3]]=[3 21; 8 11]
[[2, 3], [1, 2]]=[3 14; 8 9]
[[1, 3], [2, 3]]=[5 12; 9 11]
[[1, 3], [1, 3]]=[10 12; 8 11]
[[1, 3], [1, 2]]=[10 5; 8 9]
[[1, 2], [2, 3]]=[5 12; 14 21]
[[1, 2], [1, 3]]=[10 12; 3 21]
[[1, 2], [1, 2]]=[10 5; 3 14]
[17 1 15; 5 14 8; 19 2 21]

• $Z_{256}$下的运算
  我们本次要用到的是模256，所以上面程序改下

using LinearAlgebra
k=[16 91 215; 171 253 50; 8 186 121]
adjoint_k=[0 0 0;0 0 0;0 0 0]
for i in range(1,3)
	index_i=[1,2,3]
	deleteat!(index_i,i)
	for j in range(1,3)
		global k
		index_j=[1,2,3]
		deleteat!(index_j,j)		
		print([index_i,index_j],"=")
		println(k[index_i,index_j])
		a_ij=(-1)^(i+j)*round(Int,det(k[index_i,index_j]))
		a_ij=a_ij % 256
		if a_ij <0 
			a_ij=256+a_ij
		end
		adjoint_k[j,i]=a_ij
	end
end
println(adjoint_k)

julia> include("e:/learn/learn1.jl")
[[2, 3], [2, 3]]=[253 50; 186 121]
[[2, 3], [1, 3]]=[171 50; 8 121]
[[2, 3], [1, 2]]=[171 253; 8 186]
[[1, 3], [2, 3]]=[91 215; 186 121]
[[1, 3], [1, 3]]=[16 215; 8 121]
[[1, 3], [1, 2]]=[16 91; 8 186]
[[1, 2], [2, 3]]=[91 215; 253 50]
[[1, 2], [1, 3]]=[16 215; 171 50]
[[1, 2], [1, 2]]=[16 91; 171 253]
[65 51 75; 189 216 125; 86 56 7]

$K^{-1}$

$$K^{-1}=|K{|}^{-1}{K}^{\ast }=201\ast K^{\ast }=?$$

K*=[65 51 75; 189 216 125; 86 56 7]

using LinearAlgebra
adjoint_k=[65 51 75; 189 216 125; 86 56 7]
k=201*adjoint_k
for i in range(1,3)
	for j in range(1,3)
		a_ij=k[i,j] % 256
		if a_ij <0 
			a_ij=256+a_ij
		end
		adjoint_k[j,i]=a_ij
	end
end
println(adjoint_k)

julia> include("e:/learn/learn1.jl")
[9 11 227; 101 152 37; 134 248 127]

现在K和K的逆都已经计算完毕，下一步可以完成加密计算了，我们用C++实现（未完待续）