竞赛评卷地分配问的题目.doc

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