竞赛评卷的分配问题.doc

公平的竞赛评卷系统模型
摘要
(略)
关键词:简单二次加密算法 DES 算法加密
装箱法离散整数规划模型
问题重述:(略)
模型假设:
:基于本题采用简单二次加密算法,使其具有优良的保密性能,并基于DES的保密效果提出更好的加密方案
,来自各个学校的评委之间不会彼此影响,即不会因为评委间的交流对评卷的公证性造成影响。
,对于评委“只允许”的要求给与满足,对于评委的“要求评…”视为软要求,在满足其他条件的情况下尽量满足。
:每个评委工作量差别很小,即评卷数量基本一致,每个评委评阅的试卷尽量广泛(卷子来自学校数目尽量多)。
,即被编入一个题组(便于管理,也减少了评委的工作难度)。
,由于试卷按密码发放到不同题组,所以满足试卷发放的随机性,进一步保证公平性。
模块一试卷号的加密与解密
DES 算法的加密过程:
DES 使用 56 位密钥对 64 位数据块进行加密, 需要进行 16轮编码。在每轮编码时, 一个 48 位的密钥值由 56 位的完整密钥通过置换得来,每轮编码过程中,64位数据及每轮密钥被输入一个称为S的盒中, 由一个压码函数对数位进行编码。另外, 在每轮编码开始、过后以及每轮之间, 64 位数据被以一种特别的方式置换, 打乱数位顺序。在每一步处理中都要从 56 位的主密钥中得出一个唯一的轮次密钥。最后, 输入的 64 位原始数据被转换成 64 位看起来被完全打乱了的输出数据, 但可以用解密算法将其转换成输入时的状态。
DES 加密过程如下图所示:
图1
除了DES,用于数据加密的还有MD5加密算法(产生一个唯一的数字签名,仅用于加密)。从这两种主流的加密算法来看,加密的基本思路为:通过一个不可逆的函数变换,最终得到从明码映射而来的密码。而加密的关键在于函数的选择,或者说是变换的复杂度。
从前面的分析可知,加密的效果由两方面因素决定:(1)加密策略,如果加密策略不对外部公开,那么外部只有破解了这种策略才能破译,而破解的难度取决于加密策略的选择。(2)密钥的长度和复杂性。所谓密钥是指解密时参与运算要用到的一个特定的数据。

考虑到本系统要处理的加密数据仅是一个4位的数码,DES等加密算法并不适合处理如此短的数据加密,而且当数据长度很小时,DES也不能起到很好的加密效果,因此我们需要用一个简单的但无法通过部分数据得出公式的加密程式。
简单二次加密算法
本算法用到的两个加密函数:
(A):
对于数码A:abcd,将c换为(c+d)模10,将b换为(b+c)模10,依次进行,最后将d换为(d+a)模10。
(A,K)
K是加密者选定的与A等长的数码。输出结果为对A与K按位异或的结果。
所谓二次加密就是用前面提到的第一个函数生成一个中间码,然后再用第二个函数生成密码。这样一个映射不是可以用简单的解析形式表示出来的,从几个对应的明码和密码中是无法找出其中的规律,进而破译的。综上,在不公开加密算法的前提下可以起到很好的加密效果,完全可以满足系统需求。(后附算法源代码)

从前述的简单加密模型中可以看出,在不知道加密策略的情况下,只能通过穷举法对数据进行破译,对于本系统的4位数码来说破译概率为1/10000。然而一旦加密策略被公开或是有人得知加密策略,密码只剩一层保护,即由加密者选定的数码K,此时仍只能穷举K值,破译率仍为1/10000。在这种情况下如果一份对应的明码与密码被得知,则K值可被得到,密码将没有任何保护,密码的破译率为1。
现在提出的算法解决如何在加密策略和部分明码对应密码被窃取后,其他密码仍不会被破译。
前面已经提到DES算法并不适合简单的4位数码的加密,由于数码只有4位,密钥K的长度也只能为4位。此时K的穷举空间只有2的4次方,显然这是很脆弱的。
因此,提出下面的加密算法。
掩码Y(长度64位,每位取值为0或1),密钥K(长度64位,每位取值0或1),数据明码D(4位数码),密码M(64位数码)。
掩码Y的作用是决定某位数据是否有效,即解密时通过掩码将无效位屏蔽掉。显然这里的Y应该有4位为1,其他位为0。
对于明码D,通过掩码Y对无效位填充随机数码,得到64位码DY。
对DY进行DES加密,K为密钥,最终得到一个64的密码。
解密时按密钥K和掩码Y对密码进行解密得到原明码。
此加密算法基于DES,因此它的加密效果也更好,理论上破译可能很小,目前还只能通过计算机穷举,而DES实际密钥长度为