Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1634490
  • 博文数量: 124
  • 博客积分: 4078
  • 博客等级: 中校
  • 技术积分: 3943
  • 用 户 组: 普通用户
  • 注册时间: 2010-07-21 11:28
个人简介

新博客:http://sparkandshine.net/

文章分类

全部博文(124)

分类: 系统运维

2011-07-26 20:21:29

摘要:

  本文结合代码讲述了中兴捧月杯密码传情中的密码策略,包括密码策略约束条件分析、密码策略设计、5种编码介绍,最后附源代码。


  参加了中兴通讯第三届"中兴捧月"杯校园程序设计大赛,后来因项目原因,小组讨论一致决定放弃这个比赛。我主要负责密码策略分析与实现,原本可以在没提交作品之前整理上来,结果去了趟长沙,回来忙了一段时间的项目。直到现在才整理:-(

一、题目理解

    题目下载,点这里 中兴捧月_密码传情_题目.doc   整个题目旨在编写一款聊天软件,并对数据加解密。题目涉及到编解码要求,主要有两句:

(1) 编码与解码的每一步结果,将可以调试输出

(2)设计中需要分析策略中各种编码方法的约束条件。最大策略设计为不超过8次编码,加密最后两步必须为手机编码和摩尔斯编码

    做完之后,回过头来发现其实挺简单的,因为编码/解码仅仅涉及到字符串一一映射,主要是对字符串的一些操作:-)

2.1 每一步编解码可调试输出

    这句话我的理解是,每一步编码/解码需要单独实现。而不能通过分析几种编码内在联系,一次性完成几步编码过程。比如加密策略采取倒序、栅栏、QWE、栅栏、QWE、手机、摩尔斯,可以分析这几步编码内在关系(因为是一一对应),得到更简单的映射关系,这就使得每一步编解码无法调试输出。

2.2 策略约束条件

    纵观这5种编解码,所涉及到字符串可分为三类:字母(a~z)、数学(0~9)、由*-组成的字符串(记为:*-)。具体转化如下(以加密为例,解密类似,箭头反向即可):

  1. 字母、数字、*- —倒叙—> 字母、数字、*-
  2. 字母、数字、*- —栅栏—> 字母、数字、*-
  3. 字母 —QWE—> 字母
  4. 字母 —手机—> 数字
  5. 数字 —Morse—> *-

    转化为状态转化图如下:(花絮,我最开始想到的是用图论建模,行不通,后来考虑到有状态转换,于是作成状态转换图)



上图是用visio软件作的,下载源文件点这里 状态转换图.rar  

二、总体设计
2.1 加密策略
    因为加密过程最后两步已指定为手机和摩尔斯,再由上图1的状态转换可以得出,前面的策略只能在倒叙、栅栏、QWE进行排列(选择手机码或者摩尔斯码就回不去了,当然也可以只采用这两种编码)。
    我的思路,是在客户端做六个下拉框(因为题目要求最多只能8次编码,减去指定2种),每个下拉框有:倒叙、栅栏、QWE、不选。如此,我从客户端获得编码字符串代号,比如rfq,即表示编码过程为倒叙、栅栏、QWE、手机、摩尔斯。加密策略部分源代码如下:
  1. //Encryption
  2. //policy 最后两步是手机编码、Morse码,policy无须包括cm
  3. int encryption(char *dst, char *src, char *policy, int rows)
  4. {
  5.     char c_cf; //code function
  6.     char *middleStr = (char *)malloc(sizeof(char)*BUFFERSIZE);

  7.     while ((c_cf=*policy++) != '\0')
  8.     {
  9.         strcpy(middleStr, dst);
  10.         switch(c_cf)
  11.         {
  12.             case 'r':
  13.                 cf_reverse(dst,middleStr);
  14.                 break;
  15.             case 'f':
  16.                 cf_fence(dst, middleStr, rows);
  17.                 break;
  18.             case 'q':
  19.                 cf_qwe(dst, middleStr);
  20.                 break;
  21.             default:
  22.                  break;
  23.         }
  24.     }
  25.     //cellphone & morse coding are default at the end of policy
  26.     strcpy(middleStr, dst);
  27.     cf_cellphone(dst, middleStr);
  28.     strcpy(middleStr, dst);
  29.     cf_morse(dst, middleStr);

  30.     free(middleStr);
  31.     return OK;
  32. }
2.2 解密策略
与加密策略思路分析是一样的,解密策略部分代码如下:
  1. //Decryption 输入解码的顺序的字符串
  2. //解码前两步默认是Morse、手机,policy无须包括mc
  3. int decryption(char *dst, char *src, char *policy, int rows)
  4. {
  5.     char c_cf; //code function
  6.     char *middleStr = (char *)malloc(sizeof(char)*BUFFERSIZE);
  7.     
  8.     //cellphone & morse decoding are default at the begin of policy
  9.     dcf_morse(dst, src);
  10.     strcpy(middleStr, dst);
  11.     dcf_cellphone(dst, middleStr);

  12.     while ((c_cf=*policy++) != '\0')
  13.     {
  14.         strcpy(middleStr, dst);
  15.         switch(c_cf)
  16.         {
  17.             case 'r':
  18.                 cf_reverse(dst,middleStr);
  19.                 break;
  20.             case 'f':
  21.                 dcf_fence(dst, middleStr, rows);
  22.                 break;
  23.             case 'q':
  24.                 dcf_qwe(dst, middleStr);
  25.                 break;
  26.             default:
  27.                 break;
  28.         }
  29.     }

  30.     free(middleStr);
  31.     return OK;
  32. }
2.3 测试结果
    以题目给出的“iloveyoutoo”作为验证,以“zhongxingpengyue”作为测试例子,采用加密策略为rfqcm,即倒叙、栅栏、QWE、手机、摩尔斯,结果如下:
  1. ***zhongxingpengyue test based on rfqcm encryption policy***
  2. zhongxingpengyue
  3. ___***_____******___***__***__****_**___***__***__**___**___***__***__****_***______***______****______***_______****____*******_____****___****_*_____*****____

  4. ***zhongxingpengyue test based on rfqcm decryption policy test***
  5. ___***_____******___***__***__****_**___***__***__**___**___***__***__****_***______***______****______***_______****____*******_____****___****_*_____*****____
  6. zhongxingpengyue

三、编解码
    这部分主要介绍各个编码的加/解密,本来是想结合源代码,无奈的是工程目录下code_function.c文件损坏(其他文件正常,我现在都不知道为什么会这样),加之,我没有备份。事实上也不难,主要涉及到字符串的操作。code_function.c主要实现下列函数:
  1. /********外部函数*******/
  2. extern int cf_reverse(char *dst, const char *src); //字符串倒序
  3. extern int cf_fence(char *dst, const char *src, int rows); //栅栏密码 把明文分成N组,而后将每组第i个字符连接
  4. extern int dcf_fence(char *dst, const char *src, int rows); //栅栏密码 将密方分成N行,按列取第i个字符
  5. extern int cf_qwe(char *dst, const char *src); //QWE键盘密码 qwe_c --> qwe_dc eg.a-->q
  6. extern int dcf_qwe(char *dst, const char *src); //QWE键盘密码 qwe_dc --> qwe_c eg.q-->e
  7. extern int cf_cellphone(char *dst, const char *src); //手机按键码表 字符-->数学 eg.g-->41
  8. extern int dcf_cellphone(char *dst, const char *src); //手机按键码表 数字-->字符 eg.41-->g
  9. extern int cf_morse(char *dst, const char *src); //MORSE码 字符类型数字-->Morse码
  10. extern int dcf_morse(char *dst, const char *src);//MORSE码 Morse码-->字符类型数字
3.1 倒叙
3.2 栅栏码
    加密过程,可以这么理解,将明文划分成m个一组(称m排栅栏),得到n组,排列成二维数组m*n,按列存取该数组即得到密文。
    解密过程类似,将密文分成m个一组(称m排栅栏),得到n组,排列成二维数组m*n,按列存取该数组即得到明文。
3.3 QWE码
QWE码也叫键盘编码,其对应关系如下:
  1. 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码*/
  2. 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     /*字母表*/
3.4 手机编码
    如下图所示,2~9分别对应于字母表若干字母,比如5对应字母jkl。想一下你发短信是如何输入字母k的,切换到字母输入模式,按两下5键,即输入字母k。手机编码就是这样的,51表示按一下5键得到字母k,52表示按两下5键得到字母k,53表示按三下5键得到字母l。其他的类推,从而得到手机编码与字母的映射表。
图2 手机键盘[1]
3.5 摩尔斯编码
Morse码,0~9每个数字对应一个由5个*或者-组成的字符串,直接看常量定义:
  1. #define MORSE_CODE_0 "_____"
  2. #define MORSE_CODE_1 "*____"
  3. #define MORSE_CODE_2 "**___"
  4. #define MORSE_CODE_3 "***__"
  5. #define MORSE_CODE_4 "****_"
  6. #define MORSE_CODE_5 "*****"
  7. #define MORSE_CODE_6 "_****"
  8. #define MORSE_CODE_7 "__***"
  9. #define MORSE_CODE_8 "___**"
  10. #define MORSE_CODE_9 "____*"

四、源代码
我是在Ubuntu 9.10下开发的,源代码 ztepc_passwdPolicy_jelline.rar ,但存在如下问题:
(1) 里面一个文件code_funtion.c损坏了,几乎是乱码(但不影响总体阅读)
(2) 只能处理小写字符
(3) 测试不充分,还有不少BUG


解压后文件列表如下:
文件列表:
code_function.c  -----------------5种编码加解密实现(无奈,该文件损坏)
code_function.h  -----------------定义了一些常量,对于于code_function.c
code_function_test ---------------单步加解密测试用例可执行文件
code_function_test.c -------------单步加解密测试用例实现
code_function_test_result --------单步加解密测试用例测试结果
Makefile -------------------------makefile文件
passwdPolicy.c -------------------密码组合策略实现
passwdPolicy.h -------------------密码组合策略头文件
passwdPolicy_test ----------------密码组合策略测试用例可执行文件
passwdPolicy_test.c --------------密码组合策略测试用例实现
passwdPolicy_test_result ---------密码组合策略测试用例测试结果


参考资料:
[1] 图片来源北方IT网
阅读(3423) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~