基表变量伪随机序列和杂凑函数的制作方法
专利名称：基表变量伪随机序列和杂凑函数的制作方法
技术领域：
密码学对称密钥加密，杂凑函数
背景介绍 1).用于加密的基表变量伪随机序列BTS BTS基表变量循环体是以变量取代MD5中固定字表，IV，以及消息输入子块，融入 了加密密钥K进行运算的循环体，输出大周期伪随机序列。它利用并增强了 MD5随机性又 具有庞大周期，不依赖于任何预置的IV，因而BTS既可以获得MD5的输出随机性，在计算安 全性基础上又可以随意设置IV，用同一个密钥K下组织多个独立循环体，从而可进行大规 模并行运算，为加密提供高速和安全的伪随机序列。
2).用于杂凑的基表杂凑函数BTH 将明文的每一个分组块512比特当作BTS的加密密钥，作4轮16步的运算，寄存 器变量abed的4个第16步输出的128位，即hp^h^^级联构成这个明文块的256位杂 凑值；以每个第16步时abcd和连续多个运算过程中的查表变量值为下一轮(第四轮的状 态为下一个明文块的)的初始IV。以多层查表变量取代了 MD5或SHA的固定字表以及IV 设置，并定义为下一轮的初始IV，独特的BTH在预防自由起始端攻击，生日攻击等各类攻击 时，比通常的杂凑函数更具有优良的抗碰撞特性。
发明内容
1.基表变量序列BTS 1. 1建立一个公开固定的基础表 我们以所有不同的单节字为基元，随机乱序排列成总共长度为256B的固定序列 表"PBS"， 将PBS基础表放在连续的物理内存中，它是只读顺序表，因而，对于此表上的任意 一个数据单 元，都可以随机读取。 实际建立独立的2个PBS基础表，"PS"和"QS" 用P(t)来表示在PS上查表获得单字节基元，t为对应基元的地址； 用Q(t)来表示在QS上查表获得单字节基元，t为对应基元的地址； 要求PS和QS上的基元分布随机均匀，且对于任意一个t(O《t《255)，有
P(t) # Q(t) 1.2定义基元项& 密钥K为144比特长，拆分为16比特的子密钥K。， Kn， &，， K8
Ri是由四个8比特基元P(tJ， P(t2i)， Q(tu)， Q(t2i)串接构成的32比特字& = P (t ) P (t2i) Q (tu) Q (t2i)是以16位子密钥产生的32位的特定字，可排除规律的特殊的比特 排列，例如& # 0 1. 3利用MD5形式，主寄存器运算器变量ABCD 和MD5 —样，由4个32比特的寄存器A， B， C， D组成的累加器，a， b， c， d代表这4个寄存器变量组成abcd，进行运算并存储运算结果)。 初始化后，输入Ri及其他输入项，每轮进行9步的移位和累加运算，输出128比特。
1. 4基表变量序列BTS算法(以下所有加法为模加，"一"表示同时赋值，"<<<"为循环左移。) 初始化abcd = N。 R—丄=N" R—2 = N2， R—3 = N3， R—4 = N4， R—4 = N5，常量W = N6其
中N。，NpN2，N3，N4，Ns，N6 为6个给定的32比特常量，N。为给定的128比特常量
整型变量i，j步数i(0《i《8)，设定最大轮数j^。
每一轮共9步，每一步输入&获得&后，输入为abcd， &， R卜5
对于j轮，第i步0《i《8(0《j《jmax) (1)第j轮第i步开始时，abed记为(abed) t。」，abed中32比特的b顺序写为4个 8比特的Sl， s2和Ql， q2，子密钥16比特&写为2个8比特的Ku， K2i
t = qu+i+j+Ku (8位模加)
t2i = q2i+i+j+K2i (8位模加)
I j = P (tu) P (t2i) Q (t ) Q (t2i) b = b+(R卜4。 j <<< (i+l)+W) <<< (Slmod32)(加法为32位模加) a = a+(ProcessPi(b， c， d)+Ri。 j+b) <<< (s2mod32) (ProcessPi (b， c， d)为处理
P函数，见后)(加法为32位模加) (a， b， c， d) — (d， a， b， c)(同时赋值)此时abed即为(abed) i+1。 j (2)(abcd)8。」为j轮的y」， j+1轮的初始化令(abcd)。。 j+1 = (abcd)8。」； (R—5,j+1， R—4, j+1R—" R—3,j+1， R—2,j+1， R—一(R" R5,j R6,j R7,」R8,j);(同时赋值) j = o时，获得y。， l《j起输出Y,; y。
yv y」为输出序列 j+l，进入下轮 ......， 直至j = j^，结束 2.基表变量循环体构造的杂凑函数BTH 将明文的一个512分组当作基表变量循环体的密钥K，把基表变量循环体稍作改 动，就可以构成一个新杂凑函数BTH。进行MD强化后，明文总共m个512位分组，我们用 K^，……Kj，……，Km来表示各个分组 每个分组为512比特，依次拆为32比特的&。」其中0《i《15， 1《j《m
每个明文分组进行4轮，各16步的运算，每轮的第16步的(abcd)w输出128比特， 分别记为hph2，h3，h4^，h2串接成256比特，hj |h2， I I为级联符号，@表示位异或，<<<表 示循环左移，一表示同时赋值。Hj= ( (h II h2) @ (h3 II h4) ) @Hj—L为256比特 当j = m时，最终的Hm为整个明文的杂凑值。预定义H。值杂凑时的&定义
第i步，abed中32比特的b顺序写为4个8比特的Ql， q2， q3， q4明文分组Kj的第 i+1个32比特的ki。 j拆为8比特的ku， k2i， k3i， k4i
t = q,i+j+ku (8位模加)
t2i = q2+i+j+k2i (8位模加) t3i = q3+i+j+k3i (8位模加) t4i = q4+i+j+k4i (8位模加)
其中ri = P(tli)P(t2i)Q(t3i)Q(t4i) (1)第j分组第n轮第i步开始时，(1《n《4) Rin = k卜Ln (P (t") P (t2i) Q (t3i) Q (t4i)) b = b+ (1\+W) < < < (qimod32); (T" T2， T3， T4， T5) — (T2， T3， T4， T5， RLn <<< (i+1))此为(1\， T2， T3， T4， T5)Ln a = a+(ProcessPi(b， c， d)+Ri n+b) <<< (q2mod32) (a， b， c， d) — (d， a， b， c)此为(abcd)i n (2)n+l轮的初始化 (abed) o n+1 = (abed) 15 n ; (1\， T2， T3， T4， T5)0.n+1 = (1\， T2， T3， T4， T5)15.n 即n轮最后一步abed和1\， T2， T3， T4， T5的状态，为n+1轮的初始状态。 hn = (abcd)15 n n = n+l，…，直到n = 4时，得到h4 H尸((ht II h2) (h3 II h4) ) 1 (3) j+1分组的初始状态(i = 0， n = 1)为j分组最后一轮最后一步(i = 15， n =4)的状态 (abed) oj j+1 = (abed) 15 4」 (1\， T2， T3， T4， T5)0.Lj+1 = (1\， T2， T3， T4， T5)15.4.j j = j + l， ......， —直到j二m，求出Hm
具体实施例方式
以所有不同的单节字为基元，随机乱序排列成总共长度为256B的固定序列表 "PBS，， 建立独立的2个PBS基础表，"PS "和"QS " 用P (t)来表示在PS上查表获得单字节基元，t为对应基元的地址； 用Q (t)来表示在QS上查表获得单字节基元，t为对应基元的地址； 要求PS和QS上的基元分布随机均匀，且对于任意一个t(O《t《255)，有
P(t) # Q(t) 定义HHHNe为6个给定的32比特常量，N。为给定的128比特常量。 设置4个32比特的寄存器A， B， C， D组成的累加器，a， b， c， d代表这4个寄存器 变量组成abcd，进行运算并存储运算结果。设置辅助的5个寄存器变量1\， T2， T3， T4， 1~5，每 个为32比特.定义一个32比特的固定字W。
所有加法为模加，"一"表示同时赋值，"<<<"为循环左移，"@ "表示对应位异
或，所有变量为整形变量。 1)对于基表变量序列BTS 密钥K为144比特长，拆分为16比特的子密钥K。， &， …，K8初始化时，1\
=Np T2 = N2， T3N3， T4 = N4， T5 = ^，常量W = N6(abcd)。 = N。变量i， j 步数i (0《i《8)，设定最大轮数J隨。 每一轮共9步，每一步输入&获得&后，输入为abcd， &， 1\算法 对于j轮，第i步0《i《8 (0《j《jmax) (1)第j轮第i步开始时，abed记为(abed) t。」，abed中32比特的b顺序写为4个 8比特的Sl， s2和Ql， q2，子密钥16比特&写为2个8比特的Ku， K2i t = qu+i+j+Ku (8位模加) t2i = q2i+i+j+K2i (8位模加) 定义Ri是由四个8比特基元P(tJ，P(t2i)，Qaj，Q(t2i)串接构成的32比特字 I j = p au) p a2i) q a ) q a2i) b = b+0\+W) <<< (Slmod32);(加法为32位模加) (1\， T2， T3， T4， T5) — (T2， T3， T4， T5， Ri= j <<< (i+1))此为0\， T2， T3， T4， T5)i。」 a = a+(ProcessPi(b， c， d)+Ri。」+b) <<< (s2mod32) (ProcessP丄(b， c， d)为处理 P函数，见后) (a， b， c， d) — (d， a， b， c)(同时赋值)此时abed即为(abed) i+1。 j (2)j + l轮的初始化 (abcd)o。 j+1 = (abcd)8。」，(1\， T2， T3， T4， T5)0。 j+1 = (1\， T2， T3， T4， T5)8。」 即j轮最后一步abed和1\， T2， T3， T4， T5的状态，为j+1轮的初始状态。 (3)(abcd)8。』.为j轮的y」， j = o时，获得y。，1《j起输出Y,二 y。ey,Yj为输出序列 j+l，进入下轮 ......， 直至j二Jm^，结束 (4)ProcessPi(b， c， d)处理P函数 i = 0，1，2时:ProcessPi = (bANDc)0R((N0Tb)AND(d)) i = 3，4，5时:ProcessPi = (bANDd)OR(cAND(N0Td)) i = 6，7，8，时ProcessPi = bX0RcX0Rd 2).基表变量循环体构造的杂凑函数BTH 将明文分成每个为512比特的分组，并进行MD强化 原明文长度x，在明文后添加b比特(添加第一个比特为l，后面接着添加b-l个 O)，使得添加后的长度x+b = 512m-64(m是正整数)b《512，若x = 512m-64，则b = 512。 最后的明文块b比特后再加上64位长度值xmod264。这样明文总共m个512位分组，我们 用&，1(2，……Kj，……，Km来表示各个分组 每个分组为512比特，依次拆为32比特的l j其中0《i《15， 1《j《m 每个明文分组进行4轮，各16步的运算，每轮的第16步的(abcd)^输出128比特，分别记为^，}12，113，114 h」|h2表示h!， h2串接成256比特，h3| |h4表示h3， h4串接成256比特，"| | "为级 :@ "表示对应比特位异或运算 H尸(II h2) (h31| h4) )Hj—i为256比特
当j 二m时，最终的Hm为整个明文的杂凑值。预定义^值，设置5个辅助的寄存
联符号，' 0115] :0116]
器变量
:01"] :oi 18]
0119] 0120]
步，abed中32比特的b顺序写为4个8比特的Ql， q2， q3， q4明文分组K」的第i+l个32比 特的b。 j拆为8比特的k ， k2i， k3i， k4i q,i+j+ku (8位模加) (8位模加) (8位模加) (8位模加)
定义ri是由四个8比特基元Paj，P(t2i)，Q(t3i)，Q(t4i)串接构成的32比特字
I\， T2， T3， T4， Ts，每个为32比特。定义变量i， j，n， (1)初始化设置以及杂凑时的&定义 第一个明文块首轮第一步(j = 0， n = 0， i = 0) 初始化:1\ = N丄，T2 = N2， T3 = N3， T4 = N4， T5
Ns，常量W = N6(abcd)。 = N。第i
0121] 0122] 0123] 0124] :0125] :0126] :0127]
q3+i+j+k3
R,=r. k.
0128] (2)算法
0129] (i)对于第j分组第n轮第i步(1《n《4，0《i《8) 0130] = k，—'』0 (P(tu)P(t2i)Q(t3i)Q(t4i))
0131] b = b+(l\+W) <<< (qimod32);
0132] (1\， T2， T3， T4， T5) — (T2，T3，T4，T.5，Ri.n〈《(i+l))此为(T丄，T2， T3， T4， T5) Ln
0133] a = a+(ProcessPi(b， c， (D+D) <<< (q2mod32)
0134] (a， b， c， d) — (d， a， b， c)此为(abed) i. n
0135] (ii) (abcd)0n+1 = (abcd)15n;
0136] (1\， T2， T3， T4， T5)0.n+1 = (1\， T2， T3， T4， T5)15.n
:0137] 即n+l轮的初始状态为n轮最后一步abed和1\， T2， T3， T4， T5的状态。
:0138] hn = (abcd)15n
0139] 直到n = 4时，分别得到h" h2， h3， h4
0140] H尸((h,llh》 (h3||h4) ) Hi—,
0141] (iii) j+1分组的初始状态(i = 0， n = 1)为j分组最后一轮最后一步(i = 15， =4)的状态:
0142] (abcd)ai.j+1 二 (abed) i5.4.」
0143] (1\， T2， T3， T4， T5)。.Lj+1 = (1\， T2， T3， T4， T5)15.4.j
0144] j = j + l，
0145] ......，
7
—直到j二m，求出Hm (iv)ProcessPi(b， c， d)同MD5 n = 1时，ProcessPi(b， c， d)= n = 2时，ProcessPi(b， c， d)= n = 3时，ProcessPi(b， c， d)= n = 4时，ProcessPi(b， c， d)=
(bANDc)OR((NOTb)AND(b)) (bANDd) OR(cAND(NOTd)) bXORcXORd cXOR(bOR(丽d))。
权利要求
获取一种伪随机序列的方法----基表变量伪随机序列BTS循环体BTS运用了MD5杂凑函数的结构，直接采用了其非线性运算处理P函数。与MD5不同的是，BTS是一个使用密钥K创建大周期伪随机系列的循环，其特征为(1)建立了2个基础序列表PS，QS，将密钥K拆为有序的16位子密钥K0，K1，…，Ki，逐个逐步获得对应查表变量R0，R1，R2，…，Ri(Ri＝P(t1i)P(t2i)Q(t1i)Q(t2i))，以多层查表变量替代MD5结构中固定字表，消息子块，作为每一步输入。(2)设立辅助存储变量T1，T2，T3，T4，T5依次存储连续的查表变量值。每轮输出为最后一步abcd值，第一轮最后一步abcd定义为y0，同时，最后一步时的abcd值和T1，T2，T3，T4，T5值为下一轮的初始IV。(3)从第二轮开始输出序列，对于j轮输出序列为(或)，而不直接给出yj。(4)并行运算方法使用同一密钥K而将初始的T1，T2，T3，T4，T5，W值，(abcd)0值任意设置，以获得多个不同的独立循环体，每个独立循环体只需要初始设置互不相同，就可以在同一K下，同时输出独立的伪随机序列。F2008101566730C0000011.tif,F2008101566730C0000012.tif
2. —种新杂凑函数一基表变量杂凑函数BTHBTH采用了 MD5的基本结构添加比特MD强化，将明文分为512比特分组，采用了 MD5 处理P函数，寄存器abed结构，每个消息块512比特经过4轮，每轮16步运算。但BTH与 MD5不同，其特征为(1) BTH把每个消息子块当作BTS中密钥K来处理，每一步是采用BTS循环体的多层查 表变量来替代MD5的固定字表，消息子块作为输入。(2) BTH采用了辅助变量1\， T2， T3， T4， T5。每轮的每一步，输入不同层次的查表变量，每 轮的最后一步时输出的abcd值hn二 (abcd)^(n为轮数，l《n《4)以及1\， T2， T3， T4， T5 同时作为下一轮(或下一个明文块的首轮)的初始IV。(3) 输出杂凑值是256位H7.= (II h2)(ha II h4) ) 。
全文摘要
(1)基表变量伪随机序列BTS预建基表，把144位的密钥K依次拆分为16比特的子密钥Ki(0≤i≤8)，每轮的每一步以查表变量取代MD5中固定字和消息子块进行运算，每轮abcd第9步的128位，作为伪随机序列输出。BTS具有MD5的随机性并具有庞大周期，可用同一个密钥K组织多个独立循环体，进行大规模并行运算。(2)基表变量杂凑函数BTH将明文的每一个分组块512比特当作BTS的加密密钥，作4轮16步的运算，每轮第16步abcd输出的128位即h1，h2，h3，h4级联构成这个明文块的256位杂凑值；以每个第16步时abcd和多个查表变量值为下一轮(第四轮的状态为下一个明文块的第一轮)的初始IV。BTH在预防各类攻击时更强大，更具有抗强碰撞的特性。
文档编号G09C1/02GK101727772SQ20081015667
公开日2010年6月9日 申请日期2008年10月15日 优先权日2008年10月15日
发明者姚锡根 申请人:姚锡根
技术领域：
密码学对称密钥加密，杂凑函数
背景介绍 1).用于加密的基表变量伪随机序列BTS BTS基表变量循环体是以变量取代MD5中固定字表，IV，以及消息输入子块，融入 了加密密钥K进行运算的循环体，输出大周期伪随机序列。它利用并增强了 MD5随机性又 具有庞大周期，不依赖于任何预置的IV，因而BTS既可以获得MD5的输出随机性，在计算安 全性基础上又可以随意设置IV，用同一个密钥K下组织多个独立循环体，从而可进行大规 模并行运算，为加密提供高速和安全的伪随机序列。
2).用于杂凑的基表杂凑函数BTH 将明文的每一个分组块512比特当作BTS的加密密钥，作4轮16步的运算，寄存 器变量abed的4个第16步输出的128位，即hp^h^^级联构成这个明文块的256位杂 凑值；以每个第16步时abcd和连续多个运算过程中的查表变量值为下一轮(第四轮的状 态为下一个明文块的)的初始IV。以多层查表变量取代了 MD5或SHA的固定字表以及IV 设置，并定义为下一轮的初始IV，独特的BTH在预防自由起始端攻击，生日攻击等各类攻击 时，比通常的杂凑函数更具有优良的抗碰撞特性。
发明内容
1.基表变量序列BTS 1. 1建立一个公开固定的基础表 我们以所有不同的单节字为基元，随机乱序排列成总共长度为256B的固定序列 表"PBS"， 将PBS基础表放在连续的物理内存中，它是只读顺序表，因而，对于此表上的任意 一个数据单 元，都可以随机读取。 实际建立独立的2个PBS基础表，"PS"和"QS" 用P(t)来表示在PS上查表获得单字节基元，t为对应基元的地址； 用Q(t)来表示在QS上查表获得单字节基元，t为对应基元的地址； 要求PS和QS上的基元分布随机均匀，且对于任意一个t(O《t《255)，有
P(t) # Q(t) 1.2定义基元项& 密钥K为144比特长，拆分为16比特的子密钥K。， Kn， &，， K8
Ri是由四个8比特基元P(tJ， P(t2i)， Q(tu)， Q(t2i)串接构成的32比特字& = P (t ) P (t2i) Q (tu) Q (t2i)是以16位子密钥产生的32位的特定字，可排除规律的特殊的比特 排列，例如& # 0 1. 3利用MD5形式，主寄存器运算器变量ABCD 和MD5 —样，由4个32比特的寄存器A， B， C， D组成的累加器，a， b， c， d代表这4个寄存器变量组成abcd，进行运算并存储运算结果)。 初始化后，输入Ri及其他输入项，每轮进行9步的移位和累加运算，输出128比特。
1. 4基表变量序列BTS算法(以下所有加法为模加，"一"表示同时赋值，"<<<"为循环左移。) 初始化abcd = N。 R—丄=N" R—2 = N2， R—3 = N3， R—4 = N4， R—4 = N5，常量W = N6其
中N。，NpN2，N3，N4，Ns，N6 为6个给定的32比特常量，N。为给定的128比特常量
整型变量i，j步数i(0《i《8)，设定最大轮数j^。
每一轮共9步，每一步输入&获得&后，输入为abcd， &， R卜5
对于j轮，第i步0《i《8(0《j《jmax) (1)第j轮第i步开始时，abed记为(abed) t。」，abed中32比特的b顺序写为4个 8比特的Sl， s2和Ql， q2，子密钥16比特&写为2个8比特的Ku， K2i
t = qu+i+j+Ku (8位模加)
t2i = q2i+i+j+K2i (8位模加)
I j = P (tu) P (t2i) Q (t ) Q (t2i) b = b+(R卜4。 j <<< (i+l)+W) <<< (Slmod32)(加法为32位模加) a = a+(ProcessPi(b， c， d)+Ri。 j+b) <<< (s2mod32) (ProcessPi (b， c， d)为处理
P函数，见后)(加法为32位模加) (a， b， c， d) — (d， a， b， c)(同时赋值)此时abed即为(abed) i+1。 j (2)(abcd)8。」为j轮的y」， j+1轮的初始化令(abcd)。。 j+1 = (abcd)8。」； (R—5,j+1， R—4, j+1R—" R—3,j+1， R—2,j+1， R—一(R" R5,j R6,j R7,」R8,j);(同时赋值) j = o时，获得y。， l《j起输出Y,; y。
yv y」为输出序列 j+l，进入下轮 ......， 直至j = j^，结束 2.基表变量循环体构造的杂凑函数BTH 将明文的一个512分组当作基表变量循环体的密钥K，把基表变量循环体稍作改 动，就可以构成一个新杂凑函数BTH。进行MD强化后，明文总共m个512位分组，我们用 K^，……Kj，……，Km来表示各个分组 每个分组为512比特，依次拆为32比特的&。」其中0《i《15， 1《j《m
每个明文分组进行4轮，各16步的运算，每轮的第16步的(abcd)w输出128比特， 分别记为hph2，h3，h4^，h2串接成256比特，hj |h2， I I为级联符号，@表示位异或，<<<表 示循环左移，一表示同时赋值。Hj= ( (h II h2) @ (h3 II h4) ) @Hj—L为256比特 当j = m时，最终的Hm为整个明文的杂凑值。预定义H。值杂凑时的&定义
第i步，abed中32比特的b顺序写为4个8比特的Ql， q2， q3， q4明文分组Kj的第 i+1个32比特的ki。 j拆为8比特的ku， k2i， k3i， k4i
t = q,i+j+ku (8位模加)
t2i = q2+i+j+k2i (8位模加) t3i = q3+i+j+k3i (8位模加) t4i = q4+i+j+k4i (8位模加)
其中ri = P(tli)P(t2i)Q(t3i)Q(t4i) (1)第j分组第n轮第i步开始时，(1《n《4) Rin = k卜Ln (P (t") P (t2i) Q (t3i) Q (t4i)) b = b+ (1\+W) < < < (qimod32); (T" T2， T3， T4， T5) — (T2， T3， T4， T5， RLn <<< (i+1))此为(1\， T2， T3， T4， T5)Ln a = a+(ProcessPi(b， c， d)+Ri n+b) <<< (q2mod32) (a， b， c， d) — (d， a， b， c)此为(abcd)i n (2)n+l轮的初始化 (abed) o n+1 = (abed) 15 n ; (1\， T2， T3， T4， T5)0.n+1 = (1\， T2， T3， T4， T5)15.n 即n轮最后一步abed和1\， T2， T3， T4， T5的状态，为n+1轮的初始状态。 hn = (abcd)15 n n = n+l，…，直到n = 4时，得到h4 H尸((ht II h2) (h3 II h4) ) 1 (3) j+1分组的初始状态(i = 0， n = 1)为j分组最后一轮最后一步(i = 15， n =4)的状态 (abed) oj j+1 = (abed) 15 4」 (1\， T2， T3， T4， T5)0.Lj+1 = (1\， T2， T3， T4， T5)15.4.j j = j + l， ......， —直到j二m，求出Hm
具体实施例方式
以所有不同的单节字为基元，随机乱序排列成总共长度为256B的固定序列表 "PBS，， 建立独立的2个PBS基础表，"PS "和"QS " 用P (t)来表示在PS上查表获得单字节基元，t为对应基元的地址； 用Q (t)来表示在QS上查表获得单字节基元，t为对应基元的地址； 要求PS和QS上的基元分布随机均匀，且对于任意一个t(O《t《255)，有
P(t) # Q(t) 定义HHHNe为6个给定的32比特常量，N。为给定的128比特常量。 设置4个32比特的寄存器A， B， C， D组成的累加器，a， b， c， d代表这4个寄存器 变量组成abcd，进行运算并存储运算结果。设置辅助的5个寄存器变量1\， T2， T3， T4， 1~5，每 个为32比特.定义一个32比特的固定字W。
所有加法为模加，"一"表示同时赋值，"<<<"为循环左移，"@ "表示对应位异
或，所有变量为整形变量。 1)对于基表变量序列BTS 密钥K为144比特长，拆分为16比特的子密钥K。， &， …，K8初始化时，1\
=Np T2 = N2， T3N3， T4 = N4， T5 = ^，常量W = N6(abcd)。 = N。变量i， j 步数i (0《i《8)，设定最大轮数J隨。 每一轮共9步，每一步输入&获得&后，输入为abcd， &， 1\算法 对于j轮，第i步0《i《8 (0《j《jmax) (1)第j轮第i步开始时，abed记为(abed) t。」，abed中32比特的b顺序写为4个 8比特的Sl， s2和Ql， q2，子密钥16比特&写为2个8比特的Ku， K2i t = qu+i+j+Ku (8位模加) t2i = q2i+i+j+K2i (8位模加) 定义Ri是由四个8比特基元P(tJ，P(t2i)，Qaj，Q(t2i)串接构成的32比特字 I j = p au) p a2i) q a ) q a2i) b = b+0\+W) <<< (Slmod32);(加法为32位模加) (1\， T2， T3， T4， T5) — (T2， T3， T4， T5， Ri= j <<< (i+1))此为0\， T2， T3， T4， T5)i。」 a = a+(ProcessPi(b， c， d)+Ri。」+b) <<< (s2mod32) (ProcessP丄(b， c， d)为处理 P函数，见后) (a， b， c， d) — (d， a， b， c)(同时赋值)此时abed即为(abed) i+1。 j (2)j + l轮的初始化 (abcd)o。 j+1 = (abcd)8。」，(1\， T2， T3， T4， T5)0。 j+1 = (1\， T2， T3， T4， T5)8。」 即j轮最后一步abed和1\， T2， T3， T4， T5的状态，为j+1轮的初始状态。 (3)(abcd)8。』.为j轮的y」， j = o时，获得y。，1《j起输出Y,二 y。ey,Yj为输出序列 j+l，进入下轮 ......， 直至j二Jm^，结束 (4)ProcessPi(b， c， d)处理P函数 i = 0，1，2时:ProcessPi = (bANDc)0R((N0Tb)AND(d)) i = 3，4，5时:ProcessPi = (bANDd)OR(cAND(N0Td)) i = 6，7，8，时ProcessPi = bX0RcX0Rd 2).基表变量循环体构造的杂凑函数BTH 将明文分成每个为512比特的分组，并进行MD强化 原明文长度x，在明文后添加b比特(添加第一个比特为l，后面接着添加b-l个 O)，使得添加后的长度x+b = 512m-64(m是正整数)b《512，若x = 512m-64，则b = 512。 最后的明文块b比特后再加上64位长度值xmod264。这样明文总共m个512位分组，我们 用&，1(2，……Kj，……，Km来表示各个分组 每个分组为512比特，依次拆为32比特的l j其中0《i《15， 1《j《m 每个明文分组进行4轮，各16步的运算，每轮的第16步的(abcd)^输出128比特，分别记为^，}12，113，114 h」|h2表示h!， h2串接成256比特，h3| |h4表示h3， h4串接成256比特，"| | "为级 :@ "表示对应比特位异或运算 H尸(II h2) (h31| h4) )Hj—i为256比特
当j 二m时，最终的Hm为整个明文的杂凑值。预定义^值，设置5个辅助的寄存
联符号，' 0115] :0116]
器变量
:01"] :oi 18]
0119] 0120]
步，abed中32比特的b顺序写为4个8比特的Ql， q2， q3， q4明文分组K」的第i+l个32比 特的b。 j拆为8比特的k ， k2i， k3i， k4i q,i+j+ku (8位模加) (8位模加) (8位模加) (8位模加)
定义ri是由四个8比特基元Paj，P(t2i)，Q(t3i)，Q(t4i)串接构成的32比特字
I\， T2， T3， T4， Ts，每个为32比特。定义变量i， j，n， (1)初始化设置以及杂凑时的&定义 第一个明文块首轮第一步(j = 0， n = 0， i = 0) 初始化:1\ = N丄，T2 = N2， T3 = N3， T4 = N4， T5
Ns，常量W = N6(abcd)。 = N。第i
0121] 0122] 0123] 0124] :0125] :0126] :0127]
q3+i+j+k3
R,=r. k.
0128] (2)算法
0129] (i)对于第j分组第n轮第i步(1《n《4，0《i《8) 0130] = k，—'』0 (P(tu)P(t2i)Q(t3i)Q(t4i))
0131] b = b+(l\+W) <<< (qimod32);
0132] (1\， T2， T3， T4， T5) — (T2，T3，T4，T.5，Ri.n〈《(i+l))此为(T丄，T2， T3， T4， T5) Ln
0133] a = a+(ProcessPi(b， c， (D+D) <<< (q2mod32)
0134] (a， b， c， d) — (d， a， b， c)此为(abed) i. n
0135] (ii) (abcd)0n+1 = (abcd)15n;
0136] (1\， T2， T3， T4， T5)0.n+1 = (1\， T2， T3， T4， T5)15.n
:0137] 即n+l轮的初始状态为n轮最后一步abed和1\， T2， T3， T4， T5的状态。
:0138] hn = (abcd)15n
0139] 直到n = 4时，分别得到h" h2， h3， h4
0140] H尸((h,llh》 (h3||h4) ) Hi—,
0141] (iii) j+1分组的初始状态(i = 0， n = 1)为j分组最后一轮最后一步(i = 15， =4)的状态:
0142] (abcd)ai.j+1 二 (abed) i5.4.」
0143] (1\， T2， T3， T4， T5)。.Lj+1 = (1\， T2， T3， T4， T5)15.4.j
0144] j = j + l，
0145] ......，
7
—直到j二m，求出Hm (iv)ProcessPi(b， c， d)同MD5 n = 1时，ProcessPi(b， c， d)= n = 2时，ProcessPi(b， c， d)= n = 3时，ProcessPi(b， c， d)= n = 4时，ProcessPi(b， c， d)=
(bANDc)OR((NOTb)AND(b)) (bANDd) OR(cAND(NOTd)) bXORcXORd cXOR(bOR(丽d))。
权利要求
获取一种伪随机序列的方法----基表变量伪随机序列BTS循环体BTS运用了MD5杂凑函数的结构，直接采用了其非线性运算处理P函数。与MD5不同的是，BTS是一个使用密钥K创建大周期伪随机系列的循环，其特征为(1)建立了2个基础序列表PS，QS，将密钥K拆为有序的16位子密钥K0，K1，…，Ki，逐个逐步获得对应查表变量R0，R1，R2，…，Ri(Ri＝P(t1i)P(t2i)Q(t1i)Q(t2i))，以多层查表变量替代MD5结构中固定字表，消息子块，作为每一步输入。(2)设立辅助存储变量T1，T2，T3，T4，T5依次存储连续的查表变量值。每轮输出为最后一步abcd值，第一轮最后一步abcd定义为y0，同时，最后一步时的abcd值和T1，T2，T3，T4，T5值为下一轮的初始IV。(3)从第二轮开始输出序列，对于j轮输出序列为(或)，而不直接给出yj。(4)并行运算方法使用同一密钥K而将初始的T1，T2，T3，T4，T5，W值，(abcd)0值任意设置，以获得多个不同的独立循环体，每个独立循环体只需要初始设置互不相同，就可以在同一K下，同时输出独立的伪随机序列。F2008101566730C0000011.tif,F2008101566730C0000012.tif
2. —种新杂凑函数一基表变量杂凑函数BTHBTH采用了 MD5的基本结构添加比特MD强化，将明文分为512比特分组，采用了 MD5 处理P函数，寄存器abed结构，每个消息块512比特经过4轮，每轮16步运算。但BTH与 MD5不同，其特征为(1) BTH把每个消息子块当作BTS中密钥K来处理，每一步是采用BTS循环体的多层查 表变量来替代MD5的固定字表，消息子块作为输入。(2) BTH采用了辅助变量1\， T2， T3， T4， T5。每轮的每一步，输入不同层次的查表变量，每 轮的最后一步时输出的abcd值hn二 (abcd)^(n为轮数，l《n《4)以及1\， T2， T3， T4， T5 同时作为下一轮(或下一个明文块的首轮)的初始IV。(3) 输出杂凑值是256位H7.= (II h2)(ha II h4) ) 。
全文摘要
(1)基表变量伪随机序列BTS预建基表，把144位的密钥K依次拆分为16比特的子密钥Ki(0≤i≤8)，每轮的每一步以查表变量取代MD5中固定字和消息子块进行运算，每轮abcd第9步的128位，作为伪随机序列输出。BTS具有MD5的随机性并具有庞大周期，可用同一个密钥K组织多个独立循环体，进行大规模并行运算。(2)基表变量杂凑函数BTH将明文的每一个分组块512比特当作BTS的加密密钥，作4轮16步的运算，每轮第16步abcd输出的128位即h1，h2，h3，h4级联构成这个明文块的256位杂凑值；以每个第16步时abcd和多个查表变量值为下一轮(第四轮的状态为下一个明文块的第一轮)的初始IV。BTH在预防各类攻击时更强大，更具有抗强碰撞的特性。
文档编号G09C1/02GK101727772SQ20081015667
公开日2010年6月9日 申请日期2008年10月15日 优先权日2008年10月15日
发明者姚锡根 申请人:姚锡根
最新回复(0)