加密系统中协商弱密钥的方法

摘要

一种允许两个站间加密通信的方法,这两个站可用加密算法工作,加密算法采纳具有不同值的工作因素的加密密钥,该方法包含:在第1确定步骤中,确定不同值中较低的一个;提供具有第1工作因素值的原始加密密钥:将第1工作因素值与在确定步骤中确定的较低一个工作因素值进行比较;当在比较步骤中第1工作因素值大于确定步骤中确定的较低一个工作因素值时,执行下面步骤:对原始加密密钥执行第1散列函数以产生第1输出,从第1输出导出第1中间密钥,第1中间密钥的工作因素值不大于确定步骤中确定的不同工作因素值中较低的一个值;对第l中间密钥执行散列函数以产生第2输出,从第2输出导出最终加密密钥,最终加密密钥的工作因素值不大于确定步骤中确定的不同工作因素值中较低的一个值;使用该最终加密密钥在这两个站间进行加密通信;当在比较步骤中发现第1工作因素值不大于确定步骤中确定的较低一个工作因素值时,使用该原始加密密钥在这两个站间进行加密通信。

说明书

发明背景

本发明涉及无线通信信号的加密，尤其涉及具有不同加密要求的系统间的通信。以数字数据形式经无线通信系统和/或英特网发送消息已成常事。

两种普通类型的加密术是保密密钥加密术和公开密钥加密术。在保密密钥加密术中，从发送端发送到预定接收端的常称为“明文”的消息使用保密密钥加密，而接收端使用同样的保密密钥对常称为“密文”或“密码报文”的加密消息进行解密。只有该保密密钥可用来加密和解密，而企图用其它密钥解密该消息将注定失败。一种广泛应用的保密密钥系统是数据加密标准(DES)，它采用56比特密钥和8比特非密钥的奇偶校验比特。DES作为美国联邦信息处理标准已于1977年公开。

本发明实质上是针对保密密钥密码术。

给定加密系统提供的保密程度取决于该系统的强度或工作因素，它们一般用密钥的比特数来恒量。

工作因素是以比特为单位的数，它是基本解密操作必须执行的最大数的以2为底的对数。这种解密操作就是使用不同的试用密钥可靠地确定哪个试用密钥对应于加密时使用的实际密钥。例如，DES算法给密钥提供2⁵⁶可能的值，因而其工作因素为56比特。本领域已知，任何试用密钥都可以是正确密钥(correct key)。因此，一般在少于2⁵⁶次试用后就会找到该正确密钥。平均而言，将在大约一半试用密钥值测试后能找到该正确密钥。但是公用实践是将工作因素建立在可能密钥值的最大数上，这对比较不同工作因素提供了有效的基础。

于是，在一个保密密钥加密系统中，一个密钥例如3字节长，由24比特组成，通过试用所有2²⁴个可能的密钥直到获得可理解的明文为止，这样能相当容易地破译该密钥。这种技术是一种称为“强力破译”或“穷举密码分析”形式。密钥的比特数越大，它的强度越强。至今人们认为，用于加密算法的例如一个128比特的密钥，至少采用强力方法将完全不能破译。

一个加密密钥的工作因素可以或不可以小于该密钥的物理大小。但是，工作因素不能大于该密钥的物理大小。这是由于工作因素仅仅取决于该密钥中保密信息量。如果增加不保密的信息来加大加密密钥的物理大小，它的工作因素不加大。

另一类破译依靠对该明文的部分消息的预先知识或设定的预先知识。例如，可以知道电子邮件消息总是包含如节头(section heading)等某些节段。寻求截取和解密这样消息的人可用各个可能的密钥预先计算确定该已知节段的加密形式并将各密钥的结果及密钥本身存放在表中。然后，当截取消息时，从该表中找到已知的上下文的加密部分，产生正确密钥。这种技术称为预计算破译。

预计算破译使得截取的消息即便当加密密钥有高工作因素也能相当快和省钱地被解密，但是利用撒“盐(salt)”能阻止这种破译，下面将会详细描述这一点。

另一方面，利用强力方法解密截取消息所需的时间和花费实质上取决于加密密钥的工作因素。然而在某些情况下，必须使用减少工作因素的密钥。例如，美国法律允许出口有限密钥长度的密码术算法或产品。例如，某种算法，如果限定为40比特密钥长度，目前可以出口。此外，某些外国国家的法律将密钥长度设定了上限。

本发明概述

本发明目的在于促进具有不同工作因素的用户或站间的通信。

本发明的更具体的目的在于在两个站之间建立工作因素，这两个具有各自不同工作因素能力的站能使用所建立的工作因素使两站间能通信。

按照本发明，通过允许两个站间加密通信的方法可获得上面和其它目的，这两个站可用加密算法工作，该加密算法可采纳具有各自不同值的工作因素的加密密钥，该方法包含：

在第1确定步骤中，确定不同工作因素值中较低的一个；

提供具有第1工作因素值的原始加密密钥：

将该第1工作因素值与在所述确定步骤中确定的较低一个工作因素进行比较；

当在该比较步骤中发现第1工作因素值大于所述确定步骤中确定的所述较低一个工作因素值时，执行下面步骤：

对所述原始加密密钥执行散列函数以产生第1输出，从该第1输出导出第1中间密钥，该第1中间密钥的工作因素值不大于所述确定步骤中确定的不同工作因素值中较低一个值；

对该第1中间密钥执行散列函数以产生第2输出，从该第2输出导出最终加密密钥，该最终加密密钥的工作因素值不大于所述确定步骤中确定的不同工作因素值中较低一个值；

使用该最终加密密钥在这两个站间进行加密通信；和

当在该比较步骤中发现第1工作因素值不大于所述确定步骤中确定的所述较低一个工作因素值时，使用该原始加密密钥在这两个站间进行加密通信。

按照本发明，通过允许两个站间加密通信的方法可获得本发明的进一步的目的，这两个站的每一个可用加密算法工作，该加密算法可采纳具有给定工作因素值的加密密钥，该方法包含：

提供具有第1工作因素值的原始加密密钥，该第1工作因素值小于各站能采纳的加密密钥的所述给定工作因素值；

对包含原始加密密钥的第1字执行散列函数以产生中间密钥，从该中间密钥导出修正后的中间密钥，该修正后的中间密钥的工作因素值对预先计算破译具有比第1工作因素值有更大抗译力而不大于各站能采纳的加密密钥的给定工作因素值；

对包含修正后的中间加密密钥的第2字执行散列函数以产生第2中间密钥，从该第2中间密钥导出最终加密密钥，该最终加密密钥具有与第1中间密钥的工作因素值相等的工作因素值；和

使用最终加密密钥在这两个站间进行加密通信。

几幅附图的概述

图1为能按照本发明方法工作的通信系统的方框图。

图2为说明本发明方法一实施例的编程流程图。

本发明的详细说明

图1示出可应用本发明的移动站通信系统的基本构成。该系统包含多个移动站，各移动站实质上由CPU2、存储器4和无线接口6组成。所有数据处理和信号处理按照该领域中常规原理由CPU2控制。存储器4储存移动系统需要的数据，包括加密密钥、“盐(salt)”和其它系统操作所需的数据。该数据可以响应接口6接收到的信号永久性地存储在存储器中或写入存储器中。接口6执行发送和接收无线通信所需操作。

该系统进一步包含连接移动站控制器10的基站8。移动站控制器10与主网络(home network)12通信，该主网络12其中之一包含鉴别中心14。控制器10可通过无线链路、专用线路或通信网络耦连到网络12。图1所示全部结构组成是该领域中已知的，本发明已知工作间的基本差别在于数据加密发送和授权接收站接收后解密数据的方法。

下面描述本发明方法的一个例子。在蜂窝网中基站和移动站间出现通信时可执行该方法。

实施本发明方法需输入下面4项：

密钥K，具有给定的工作因素W_K，如上所述，它对某些应用可能太强(strong)。移动站的密钥K也是鉴别中心知道的，它可通过电话交换网发送到基站，该基站的发送设定为保密，使得在该两站是知道的。这可以是如北美IS-41移动电话系统中使用的长期密钥(long term key)、从这样的长期密钥导出的临时密钥(temporary key)、或如在欧洲GSM系统中发送的临时密钥；该密钥能被基础加密算法(underlying encryption algorithm)采纳的以比特为单位的字长L_c；该基础加密算法可以是上面提到的DES算法(此时，L_c为56比特)，或任何其它保密密钥算法；

整数W_B，表示某选定基站设备允许的最大工作因素。在基站与移动站间设置通信期间该整数将在某时刻从选定基站发送到移动站，或它能从某些其它信息，如协议标识符、协议版本号等导出，当移动站进入基站覆盖区时，这些信息按照本领域中已知的过程事先从基站发送到移动站；

整数W_m，表示该移动站允许的最大工作因素。它可以在制造时存入该移动站，或可在此后编程进入该移动站，但受到这样的限制，即该编程试图设置W_m的值大于该移动站中已编程的值时，该编程将被拒绝；和

数据项(data item)，为该基站和移动站两者所知，但对于能截取两站间通信的其它方事先不知道，并且能以只让授权方知道的时刻和方法变化。它被称为“盐(salt)”S，用来防止利用预先计算的查找表识别该密钥。该“盐”S，如可以是移动站的设备电子系列号或鉴别过程期间使用的RAND值，或它们的串联。引证一个例子，移动站的电子系列号一般在呼叫开始时发送，并且双方都知道。对某个特定电话，它不随时间变化，但从试图解密来自不同人们的通信的破译者方面看，它是变化的，所以破译者一般不能预先计算确定。该破译者顶多能预先计算确定一个或多个特定电话，但不能截取其它电话通信；和

单向函数H，其特性是很难反转。换句话说，对于函数y＝H(x)的任何输出都不可能从输出值y执行计算确定输入值，或者找到产生同一输出值的两个输入值。该输出y通常称为散列，而H通常称为散列函数。变化强度的散列函数是已知的并可作为商品购得。

IS-41标准设备中存在这样的一种散列函数，称为CAVE。可选择的是，保密散列标准(FIPS 180-1)指定也能使用的函数SHA-1。散列函数的输入可有任意长度。散列函数的输出设定为具有比特数L_h，至少有表示各W_m、W_b和L_c的比特数那么大。

本发明的一实施例由下面步骤组成，这些步骤图示在图2的流程图中，并在可能出现数据交换前在移动站和基站中执行：

步骤1

目标工作因素W_t设置成等于移动站的工作因素W_m；

步骤2

将基站的工作因素W_b与W_m作比较；如果比较表明W_b小于或等于W_m，那么将W_t设置得等于W_b。要不然W_t保持步骤1中设置的值；

步骤3

如果目标工作因素W_t大于或等于加密算法L_c可接纳的密钥的长度，则至少密钥K的最低有效的L_c比特直接用于对发送进行加密，并省略下面的步骤。如果W_t小于L_c，则执行下面的步骤，产生新的加密密钥。

步骤4

具有工作因素W_k的密钥K与“盐”S相连，并且产生的字作为输入用于单向函数H。产生的输出是具有长度L_h，但仍然只是工作因素W_b的中间密钥K’，这是因为假定没有授权而截取和解密消息的人知道该“盐”S。

步骤5

通过将K’中最高有效的(L_h-W_t)比特设定为0，将K’修改成只包含有意义的W_t比特，其中，W_t具有步骤1和2中产生的值。与K’相关的工作因素现在减少到W_t比特。

步骤6

步骤5中修改后的密钥K’与“盐”S相串连，所产生的字作为输入用于单向函数H以形成输出值K_out。

步骤7

K_out的最低有效的L_c比特用作加密密钥K”。

步骤4到7同时在两站中执行。

在上面描述的过程中，密钥K”可以有比W_t的比特数长的比特数，但是，由于在步骤5中修改密钥K’，故密钥K”只有工作因素W_t，它不大于W_k或W_h。由于在该计算中使用了“盐”S，所以预先计算破译要作更大的努力，并且必须为表准备更大的存储容量。这种努力和存储容量对应于L_c或W_t+L_s中较小的工作因素。

在上面描述的过程中，还设定在步骤4和6中使用相同的单向函数H，在实践中通常这样做。但是，也可以在步骤4中使用第1单向函数，而在步骤6中使用与第1单向函数不同的第2单向函数。

按照上面描述的方法的具体例子，初始按照本领域中传统方法产生的密钥K具有工作因素W_k等于64比特。利用具有32比特长度的“盐”S。在该例中，W_m为64比特的值，W_b为40比特的值。因此，在步骤1中，W_t先设置成64比特，然后在步骤2将其设置成40比特。

在该例中，DES是具有密钥长L_c为56比特的基础加密算法，使得在步骤3中找到W_t小于W_c。因此，进行到步骤4时，产生长度L_h的K’，这里等于160比特。

在步骤5，该K’的120比特最高有效比特设置成零，使得产生的修改后的密钥K’的有意义的比特为40比特，因此工作因素W_t为40比特。

步骤6中执行的处理产生具有长度160比特的输出值K_out。由于基础加密算法容纳的密钥长度为56比特，因此K_out中56比特最低有效比特用作加密密钥。

按照本发明另一实施例，加密密钥能变换为长密钥。两站必须能使用相同的加密算法，具有该算法可接纳的密钥的相同长度。如果该密钥长度大于当局可接纳的长度，则上面描述的协商确保工作因素适当地受到限制。例如，可要求使用密码算法能接纳长度大于初始提供的密钥的长度的密钥。在这种情况下，本发明的方法可用来产生同样工作因素的密钥。虽然这种更长因素能通过穷举搜索加以破译，该穷举搜索不长于破译原始密钥所需长度，但是任何预先计算结果的企图，因“盐”的参与而要求更长的计算和更大容量的存储。

本发明上述实施例的方法只要求通过将W_t设置为W_b、W_m和W_k中最小的那个来改变本发明第1描述实施例中步骤1和2。

上面描述涉及建立的加密密钥仅与两方相关。然而在特定的环境中，可能出现虽然在过程中的任何给定点，交换只发生在各方中的两方之间，但是加密密钥的计算可能涉及2个以上的各方。例如，可能出现从美国出口基站8或移动站控制器10，结果对它的工作因素存在某种限制。还可能出现移动站2-6在法国应用，对工作因素构成更大的限制。在这种情况下，本发明方法借助有鉴别中心14而能实施，当与控制器10通信时，使得受法国法律的限制影响较小。然而，移动站2-6可能有更强的限制，通过与控制器10交互时出现这种限制。尤其是，步骤1-3在主网络与访问网络间执行，使得W_b达到一个可接受的值。该值将由移动站和基站使用。

上面的描述虽然涉及本发明的特定实施例，但应当看到在不脱离本发明精神实质范围内可作种种修改。因此，所附权利要求书用来涵盖落入本发明真正范围内的这种修改。

因此，当前揭示的实施例只是说明性的而不是限定，所附权利要求书(而不是前面所作的说明)表明本发明的范围，因此，落入权利要求书等价含义和范围内的所有变化均涵盖在其中。