密码传情之密码机制

Jelline 发表于 2011-12-22 08:54

摘要：　　本文结合代码讲述了中兴捧月杯密码传情中的密码策略，包括密码策略约束条件分析、密码策略设计、5种编码介绍，最后附源代码。 　　参加了中兴通讯第三届"中兴捧月"杯校园程序设计大赛，后来因项目原因，小组讨论一致决定放弃这个比赛。我主要负责密码策略分析与实现，原本可以在没提交作品之前整理上来，结果去了趟长沙，回来忙了一段时间的项目。直到现在才整理:-(一、题目理解    题目下载，点这里<a href=".http://blog.chinaunix.net/attachment/attach/91/12/80/039112803eba7f9f9c5257d052e71d48016d805b8.doc" target="_blank" target="_blank"><img border="0" align="absmiddle" src="/blog/image/attachicons/msoffice.gif"> 中兴捧月_密码传情_题目.doc </a>  整个题目旨在编写一款聊天软件，并对数据加解密。题目涉及到编解码要求，主要有两句：(1) 编码与解码的每一步结果，将可以调试输出

(2)设计中需要分析策略中各种编码方法的约束条件。最大策略设计为不超过8次编码，加密最后两步必须为手机编码和摩尔斯编码    做完之后，回过头来发现其实挺简单的，因为编码/解码仅仅涉及到字符串一一映射，主要是对字符串的一些操作:-)

2.1 每一步编解码可调试输出    这句话我的理解是，每一步编码/解码需要单独实现。而不能通过分析几种编码内在联系，一次性完成几步编码过程。比如加密策略采取倒序、栅栏、QWE、栅栏、QWE、手机、摩尔斯，可以分析这几步编码内在关系(因为是一一对应)，得到更简单的映射关系，这就使得每一步编解码无法调试输出。2.2 策略约束条件    纵观这5种编解码，所涉及到字符串可分为三类：字母(a~z)、数学(0~9)、由*-组成的字符串(记为：*-)。具体转化如下(以加密为例，解密类似，箭头反向即可)：<div id="codeText" class="codeText"><ol style="margin:0 1px 0 0;padding:5px 0;" start="1" class="dp-css"><li style="text-align: center;">字母、数字、*-—倒叙—> 字母、数字、*-</li><li style="text-align: center;">
字母、数字、*-—栅栏—> 字母、数字、*-</li><li style="text-align: center;">
字母—QWE—> 字母</li><li style="text-align: center;">
字母—手机—> 数字</li><li style="text-align: center;">
数字 —Morse—> *-</li></ol></div>    转化为状态转化图如下：(花絮，我最开始想到的是用图论建模，行不通，后来考虑到有状态转换，于是作成状态转换图)<a href="http://blog.chinaunix.net/attachment/201108/12/9112803_13131554929D9g.jpg" target="_blank" target="_blank"><img src="http://blog.chinaunix.net/attachment/201108/12/9112803_13131554929D9g.jpg" .load="imgResize(this, 650);" border="0" ;=""></a><div> </div><div> </div><div>上图是用visio软件作的，下载源文件点这里<a href=".http://blog.chinaunix.net/attachment/attach/91/12/80/039112803c797868c38a04a31cdb8feee9e3c0044.rar" target="_blank" target="_blank"><img border="0" align="absmiddle" src="/blog/image/attachicons/rar.gif"> 状态转换图.rar </a> </div><div> </div><div>二、总体设计</div><div>2.1 加密策略</div><div>    因为加密过程最后两步已指定为手机和摩尔斯，再由上图1的状态转换可以得出，前面的策略只能在倒叙、栅栏、QWE进行排列(选择手机码或者摩尔斯码就回不去了，当然也可以只采用这两种编码)。</div><div>    我的思路，是在客户端做六个下拉框(因为题目要求最多只能8次编码，减去指定2种)，每个下拉框有：倒叙、栅栏、QWE、不选。如此，我从客户端获得编码字符串代号，比如rfq，即表示编码过程为倒叙、栅栏、QWE、手机、摩尔斯。加密策略部分源代码如下：</div><div><div id="codeText" class="codeText"><ol style="margin:0 1px 0 0;padding:5px 0;" start="1" class="dp-css"><li>//Encryption </li><li>
//policy 最后两步是手机编码、Morse码，policy无须包括cm </li><li>
int encryption(char *dst, char *src, char *policy, int rows) </li><li>
{ </li><li>
    char c_cf; //code function </li><li>
    char *middleStr = (char *)malloc(sizeof(char)*BUFFERSIZE); </li><li> </li><li>
    while ((c_cf=*policy++) != '\0') </li><li>
    { </li><li>
        strcpy(middleStr, dst); </li><li>
        switch(c_cf) </li><li>
        { </li><li>
            case 'r': </li><li>
                cf_reverse(dst,middleStr); </li><li>
                break; </li><li>
            case 'f': </li><li>
                cf_fence(dst, middleStr, rows); </li><li>
                break; </li><li>
            case 'q': </li><li>
                cf_qwe(dst, middleStr); </li><li>
                break; </li><li>
            default: </li><li>                 break; </li><li>
        } </li><li>
    } </li><li>
    //cellphone & morse coding are default at the end of policy </li><li>
    strcpy(middleStr, dst); </li><li>
    cf_cellphone(dst, middleStr); </li><li>
    strcpy(middleStr, dst); </li><li>
    cf_morse(dst, middleStr); </li><li>
 </li><li>
    free(middleStr); </li><li>
    return OK; </li><li>
}</li></ol></div></div><div>2.2 解密策略</div><div>与加密策略思路分析是一样的，解密策略部分代码如下：</div><div><div id="codeText" class="codeText"><ol style="margin:0 1px 0 0;padding:5px 0;" start="1" class="dp-css"><li>//Decryption 输入解码的顺序的字符串 </li><li>
//解码前两步默认是Morse、手机，policy无须包括mc </li><li>
int decryption(char *dst, char *src, char *policy, int rows) </li><li>
{ </li><li>
    char c_cf; //code function </li><li>
    char *middleStr = (char *)malloc(sizeof(char)*BUFFERSIZE); </li><li>
     </li><li>
    //cellphone & morse decoding are default at the begin of policy </li><li>
    dcf_morse(dst, src); </li><li>
    strcpy(middleStr, dst); </li><li>
    dcf_cellphone(dst, middleStr); </li><li>
 </li><li>
    while ((c_cf=*policy++) != '\0') </li><li>
    { </li><li>
        strcpy(middleStr, dst); </li><li>
        switch(c_cf) </li><li>
        { </li><li>
            case 'r': </li><li>
                cf_reverse(dst,middleStr); </li><li>
                break; </li><li>
            case 'f': </li><li>
                dcf_fence(dst, middleStr, rows); </li><li>
                break; </li><li>
            case 'q': </li><li>
                dcf_qwe(dst, middleStr); </li><li>
                break; </li><li>
            default: </li><li>                break;</li><li>
        } </li><li>
    } </li><li>
 </li><li>
    free(middleStr); </li><li>
    return OK; </li><li>
}</li></ol></div></div><div>2.3 测试结果</div><div>    以题目给出的“iloveyoutoo”作为验证，以“zhongxingpengyue”作为测试例子，采用加密策略为rfqcm，即倒叙、栅栏、QWE、手机、摩尔斯，结果如下：</div><div><div id="codeText" class="codeText"><ol style="margin:0 1px 0 0;padding:5px 0;" start="1" class="dp-css"><li>***zhongxingpengyue test based on rfqcm encryption policy***</li><li>
zhongxingpengyue </li><li>
___***_____******___***__***__****_**___***__***__**___**___***__***__****_***______***______****______***_______****____*******_____****___****_*_____*****____</li><li> </li><li>
***zhongxingpengyue test based on rfqcm decryption policy test***</li><li>
___***_____******___***__***__****_**___***__***__**___**___***__***__****_***______***______****______***_______****____*******_____****___****_*_____*****____</li><li>
zhongxingpengyue</li></ol></div></div><div> </div><div>三、编解码</div><div>    这部分主要介绍各个编码的加/解密，本来是想结合源代码，无奈的是工程目录下code_function.c文件损坏(其他文件正常，我现在都不知道为什么会这样)，加之，我没有备份。事实上也不难，主要涉及到字符串的操作。code_function.c主要实现下列函数：</div><div><div id="codeText" class="codeText"><ol style="margin:0 1px 0 0;padding:5px 0;" start="1" class="dp-css"><li>/********外部函数*******/ </li><li>
extern int cf_reverse(char *dst, const char *src); //字符串倒序 </li><li>
extern int cf_fence(char *dst, const char *src, int rows); //栅栏密码把明文分成N组，而后将每组第i个字符连接 </li><li>
extern int dcf_fence(char *dst, const char *src, int rows); //栅栏密码将密方分成N行，按列取第i个字符 </li><li>
extern int cf_qwe(char *dst, const char *src); //QWE键盘密码qwe_c --> qwe_dc eg.a-->q </li><li>
extern int dcf_qwe(char *dst, const char *src); //QWE键盘密码 qwe_dc --> qwe_c eg.q-->e </li><li>
extern int cf_cellphone(char *dst, const char *src); //手机按键码表字符-->数学 eg.g-->41 </li><li>
extern int dcf_cellphone(char *dst, const char *src); //手机按键码表数字-->字符 eg.41-->g </li><li>
extern int cf_morse(char *dst, const char *src); //MORSE码字符类型数字-->Morse码 </li><li>
extern int dcf_morse(char *dst, const char *src);//MORSE码 Morse码-->字符类型数字</li></ol></div></div><div>3.1 倒叙</div><div>3.2 栅栏码</div><div>    加密过程，可以这么理解，将明文划分成m个一组(称m排栅栏)，得到n组，排列成二维数组m*n，按列存取该数组即得到密文。</div><div>    解密过程类似，将密文分成m个一组(称m排栅栏)，得到n组，排列成二维数组m*n，按列存取该数组即得到明文。</div><div>3.3 QWE码</div><div>QWE码也叫键盘编码，其对应关系如下：</div><div><div id="codeText" class="codeText"><ol style="margin:0 1px 0 0;padding:5px 0;" start="1" class="dp-css"><li>Q W E R T Y U I O P A S D F G H J K L Z X C V B N M     /*QWE码*/ </li><li>
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z     /*字母表*/</li></ol></div></div><div>3.4 手机编码</div><div><div>    如下图所示，2～9分别对应于字母表若干字母，比如5对应字母jkl。想一下你发短信是如何输入字母k的，切换到字母输入模式，按两下5键，即输入字母k。手机编码就是这样的，51表示按一下5键得到字母k，52表示按两下5键得到字母k，53表示按三下5键得到字母l。其他的类推，从而得到手机编码与字母的映射表。</div></div><div style="text-align: center;"><a href="http://blog.chinaunix.net/attachment/201108/19/9112803_1313753836YXD9.jpg" target="_blank" target="_blank"><img src="http://blog.chinaunix.net/attachment/201108/19/9112803_1313753836YXD9.jpg" .load="imgResize(this, 650);" border="0" ;=""></a></div><div style="text-align: center;">图2 手机键盘</div><div>3.5 摩尔斯编码</div><div>Morse码，0～9每个数字对应一个由5个*或者-组成的字符串，直接看常量定义：</div><div><div id="codeText" class="codeText"><ol style="margin:0 1px 0 0;padding:5px 0;" start="1" class="dp-css"><li>#define MORSE_CODE_0 "_____" </li><li>
#define MORSE_CODE_1 "*____" </li><li>
#define MORSE_CODE_2 "**___" </li><li>
#define MORSE_CODE_3 "***__" </li><li>
#define MORSE_CODE_4 "****_" </li><li>
#define MORSE_CODE_5 "*****" </li><li>
#define MORSE_CODE_6 "_****" </li><li>
#define MORSE_CODE_7 "__***" </li><li>
#define MORSE_CODE_8 "___**" </li><li>
#define MORSE_CODE_9 "____*"</li></ol></div></div><div> </div><div>四、源代码</div><div>我是在Ubuntu 9.10下开发的，源代码<a href=".http://blog.chinaunix.net/attachment/attach/91/12/80/0391128037f787d5ed659b28dbdac0f8cde552f28.rar" target="_blank" target="_blank"><img border="0" align="absmiddle" src="/blog/image/attachicons/rar.gif"> ztepc_passwdPolicy_jelline.rar </a>，但存在如下问题：</div><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><div>(1) 里面一个文件code_funtion.c损坏了，几乎是乱码(但不影响总体阅读)</div><div>(2) 只能处理小写字符</div><div>(3) 测试不充分，还有不少BUG</div></blockquote><div> </div><div> </div><div>解压后文件列表如下：</div><div><div>文件列表：</div></div><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><div>code_function.c  -----------------5种编码加解密实现(无奈，该文件损坏)</div></div></blockquote><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><div>code_function.h  -----------------定义了一些常量，对于于code_function.c</div><div>code_function_test ---------------单步加解密测试用例可执行文件</div><div>code_function_test.c -------------单步加解密测试用例实现</div><div>code_function_test_result --------单步加解密测试用例测试结果</div><div>Makefile -------------------------makefile文件</div><div>passwdPolicy.c -------------------密码组合策略实现</div><div>passwdPolicy.h -------------------密码组合策略头文件</div><div>passwdPolicy_test ----------------密码组合策略测试用例可执行文件</div><div>passwdPolicy_test.c --------------密码组合策略测试用例实现</div><div>passwdPolicy_test_result ---------密码组合策略测试用例测试结果</div></blockquote><div> </div><div> </div><div>参考资料：</div><div> 图片来源北方IT网</div>

页: [1]

Chinaunix's Archiver

密码传情之密码机制