循环小数在序列加密中的应用 - 夏冰加密软件技术博客

序列加密是用数字密码对数字信息序列逐个比特进行加密的体制。这种加密体制算法简单，保密性好，是目前常用的一种加密体制。下面我就给大家介绍一种一种采用循环小数来生成密码序列，它具有算法简单、序列多变、保密性好、抗破译能力强等特点。

一、序列加密的基本原理

序列加密是对数字信息序列进行加密的，我们把加密前的数字信息序列叫做明文，把加密后的数字信息序列叫做密文，把加密时用的密码序列叫做密码。于是加密过程就可由以下表达式给出：

明文序列：P0,P1,P2,P3.....Pn

密码序列：C0,C1,C2,C3.....Cr(r≥n)

密文序列：So,S1,S2,S3……、Sn

这里有关系式：

Si=Pi+Ci(i=0、1、2、……n)

其中+表示可以是代数运算也可以是逻辑运算。上述关系式反映了序列加密的基本原理。

破译攻击者需要知道的是明文序列一Pi(i=0，1，2，……，n)．

但明文序列是不公开发送的,而公开发送的只能是密文序列Si=(i=0,1,2,...n)，故破译攻击者直接截获的只能是密文序列。要想通过已截获的密文序列来获取所需要的明文序列,就必须千方百计地获得密码序列Ci=(i=1,2,...r)。因此破译攻击者就要采用各种破译分析手段去获取密码序列。由此可见，密码序列的构成是保密性能优劣的关键。为了保证密码序列的保密性能，密码设计者必须满足以下三条基本要求：

1、密码空间必须足够广阔。

2、密码构造必须足够复杂。

3、密码更换必须足够频繁。

这三条非常重要。因为密码空间越广阔，穷举攻击越困难密码构造越复杂，技术破译越不易密码更换越频繁，破译者就难以找出密码的规律。

二、有关循环小数的几个定理

前面提到过，密码序列可以用各种方式来生成，例如利用某一随机数列、某一函数、某一多次用余式等等。本文介绍一种利用循环小数来生成密码序列。为了对循环小数的性质有一个明确的概念，首先给出了有关循环小数的几个定理：

定理1十进制中任意质数P(10)，换算成r进制数P(r)后，则P(r)在r进制中仍然是质数。

定理2在r进制中，a/b (a<b)能化成纯循环小数的必要和充分条件是在分母b内根本不含r的因数。

定理3在r进制中，若(b．r)=1，则a/b(a<b)化成小数后，其循环节的位数等h的必要和充分条件是h能使rh三l (mod b)成立的最小正整数。

定理4在r进制中，若r是质数P的一个元根，则以P为分母的真分数化成小数后，其循环节位数是h=φ（P) =P-1；否则是h一①(P)——g，而glq> cP)。

其中①(P)是数论中的Euler函数。

定理5若P为质数，h是使rh-l (mod p)的最小正整数。k是使rh—l (mod pk)的最大正整数，则以Pa为分母的既约真分数的循环节的位数为：

h．当Q≤k时；

hPa-k，当a>k时。

定理6 若b的标准分解式为b—P{-P2z……P备，则以b为分母的既约真分数化成r进制的小数后，其循环节的位数是：

h={hi．h2，h3，……，h。）

其中h．是满足rh1=l (mod P})的最小正整数(i=1，2，3．……，n)。

根据上述定理可知，在十进制中除2和5两个质数外，以任意一个质数（包括它的幂）作分母的真分数以及任意几个质数的积（包括它们幂的积）作分母的既约真分数都可以化成纯循环小数。另外，以质数P为分母的真分数化成循环小数后，共可获得P-l种循环小数序列即1/P，2/P．……，(P-I)/P。这样就满足了第一条要求：密码空间必须足够广阔。

用循环小数来生成密码序列，其构造是多变的，因为它运算简便，可以做到每发送一则信息，更换一个密码序列，而不象随机密码序列那样，必须存储在存储器中，应用一段时间后再更换。这样就满足了第一条和第三条要求密码构造必须足够复杂和密码更换必须足够频繁。

三、以循环小数来生成密码序列

根据上述六个有关循环小数的定理，我们可以适当选择真分数，来生成任意长度的密码序列。为了简明扼要，我们以3/113为例来生成电报通讯的密码序列。

为了提高计算速度，我们给出了使计算机每做一次除法便可求出4位商的、用BASIC语言编写的、在PC-1500计算机上实现了的计算程序：

10 : P=113 : Q=3 : R=IE4 :
LPRINT k3/113=";
20 : FOR I=O T0 28
30 : T—INT (Q * R/P)
40 : IF I=o LET B=T/R :
GOT0 60
50 : B=T
60 : s=o *R-T *P
70 : o—s
80 : LPRINT B
90 : NEXT I
IOO : ENiD
计算打印结果 :
3/113=0. 0265
4867 _2566 _3716 _81-tl
5929 _2035 _3982 _3008
8495 _5752 _2123 _8938
0530 _9734 _5132 _7433
6283 _1858 _1070 _7964
6017 _6991 _1504 _4217
7876 _1061 _9469 _0256

这个电报通信密码序列长度只有28个汉字，只作为简要例子而已。如果需要较长的密码序列周期，可选用较大的质数，例如选择质数99901作分母，它的循环节位数有99900位。
还可根据定理5选择113s—1442897作分母，其循环节位数是1430028。若以它作为电报通信的密码序列，其序列周期长度为357507个汉字．足够对一部长篇小说稿件进行加密了。若
序列周期还不够长，可以综合运用上述各个定理。使循环节位数根据需要任意加长。

此种方法也可以生成二进制密码序列，用于数据通讯和数字通讯，也可用于数据俘储保密。将十进制数转换成二进制密码序列有多种方法，现举出以下三种：

第一种方法是将十进制的循环小数逐位转换成二进制数。

例如 _ 3/113=o．0265 4867 2566……，进行逐位转换有：0=0000.2= 0010，6=—0110, 5= 0101，4=0100, 8= 1000，6-0110，7= 0111．……；

第二种方法是多位进行转换，即每次取若干位数，将其转换成二进制数。

例如：3/113=0. 0265 4867 2566-----，进行4位转换有0265- 100001001, 4867—1001100000011,……；

第三种方法是直接将3/113中的分子分母分别转换成二进制11/1110001，然后直接求商。

采用多种十进制和二进制转换方式可以增强密文的抗破译能力。

四、抗破译能力的初步分析

从上面谈到的利用循环小数生成的密码序列具备了保密的三个条件：

1、由于质数是无限的，加之其积和幂，其密码空间是足够广阔的。

2、由于不同的分数，其循环小数的序列是截然不同的，相同的分母而分子不同的分数，其循环小数的序列也是不同的。

例如：