HASH函数编程

精品文档 1欢迎下载 上机三 HASH 函数编程 上机目的上机目的 熟悉 HASH 函数的基本原理和性质 通过编程 开源代码分析了解一种标准 HASH 算法的 运行原理 上机环境上机环境 1 硬件 PC 机一台 2 系统配置 操作系统 windows XP 以上 3 编程语言 C C C Java Python 上机内容及要求上机内容及要求 1 MD5 算法分析和实现 2 使用实例分析 备注 可借鉴网上相关算法的开源代码进行编程实现 编程语言不限 除了 MD5 算法 也可以选取 SHA 系列 HASH 算法 或其它任一种标准的 HASH 算法 进行研究 上机报告上机报告 实验过程 Python 遇到 Hash 内置的函数库就可以解决 但要是想理解算法与原理 还是要走一边流 程 Python hash 库的应用 importimport hashlib psw a a md5 hashlib md5 初始化摘要对象 md5 update psw encode utf 8 utf 8 使用 md5 算法计算 print md5 hexdigest 输出 16 进制字符串 精品文档 2欢迎下载 a 的 Hash 值对应 0cc175b9c0f1b6a831c399e269772661 让 a bujunjie 我的名字 hash 看来老师让我们分析分析源码吗 要分析源码首先搞一下 什么是 HASH 摘要算法是将信息压缩提取以作为数据指纹的算法 我们下载东西要确认下的 东西有没有下错下漏常用这种算法来做验证 在密码学中这是很多算法的基础 具体摘要算法是怎么样的 摘要算法又称哈希算法 散列算法 它通过一个函 数 把任意长度的数据转换为一个长度固定的数据串 通常用 16 进制的字符 串表示 还有一种应用场景是用来存储用户的密码 大明文密码存储在数据库里很不安 全 之前爆出很多知名网站将用户密码以明文存储 导致信息泄露 可以通过摘 要算法给密码加个密存储进去 这样要破解密码除了要知道密码本身 还得知 道生成最终摘要文本的算法才可以 也就相对安全多了 MD5 是输入不定长度信息 输出固定长度 128 bits 的算法 经过程序流程 生成 四个 32 位数据 最后联合起来成为一个 128 bits 散列 基本方式为 求余 取余 调整长度 与链接变量进行循环运算 得出结果 精品文档 3欢迎下载 摘 自 wiki 百科 Note All variables are unsigned 32 bits and wrap modulo 2 32 when calculating varvar int 64 r k r specifies the per round shift amounts r 0 15 7 12 17 22 7 12 17 22 7 12 17 22 7 12 17 22 r 16 31 5 9 14 20 5 9 14 20 5 9 14 20 5 9 14 20 r 32 47 4 11 16 23 4 11 16 23 4 11 16 23 4 11 16 23 r 48 63 6 10 15 21 6 10 15 21 6 10 15 21 6 10 15 21 Use binary integer part of the sines of integers as constants forfor i from 0 toto 63 k i floor abs sin i 1 2 32 精品文档 4欢迎下载 Initialize variables varvar int h0 0 x67452301 varvar int h1 0 xEFCDAB89 varvar int h2 0 x98BADCFE varvar int h3 0 x10325476 Pre processing append 1 bit toto message append 0 bits untiluntil message length inin bits 448 modmod 512 append bit length ofof message asas 64 bit little endian integer toto message Process the message in successive 512 bit chunks forfor each 512 bit chunk ofof message breakbreak chunk into sixteen 32 bit little endian words w i 0 i 15 Initialize hash value for this chunk varvar int a h0 varvar int b h1 varvar int c h2 varvar int d h3 Main loop forfor i from 0 toto 63 ifif 0 i 15 thenthen 精品文档 5欢迎下载 f b andand c oror notnot b andand d g i elseelse ifif 16 i 31 f d andand b oror notnot d andand c g 5 i 1 modmod 16 elseelse ifif 32 i 47 f b xorxor c xorxor d g 3 i 5 modmod 16 elseelse ifif 48 i 63 f c xorxor b oror notnot d g 7 i modmod 16 temp d d c c b b leftrotate a f k i w g r i b a temp Next i Add this chunk s hash to result so far h0 h0 a h1 h1 b h2 h2 c h3 h3 d 精品文档 6欢迎下载 EndEnd ForEach varvar int digest h0 append h1 append h2 append h3 expressed as little endian wiki 的伪代码 大概的意思就是经过 64 次运算 在经过 4 轮 然后将 32 位的加起来 codeing utf 8 引入math模块 因为要用到sin函数 importimport math 定义常量 用于初始化128位变量 注意字节顺序 文中的A 0 x01234567 这里低值存放低字节 即01 23 45 67 所以运算时A 0 x67452301 其他类似 这里用字符串的形势 是为了和hex函数的输出统一 hex 10 输出为 0 xA 注意结果为字符串 A 0 x67452301 0 x67452301 B 0 xefcdab89 0 xefcdab89 C 0 x98badcfe 0 x98badcfe D 0 x10325476 0 x10325476 定义每轮中用到的函数 L为循环左移 注意左移之后可能会超过32位 所以要和0 xffffffff做与运算 确保结果为32位 F lambdalambda x y z x y x z G lambdalambda x y z x z y z H lambdalambda x y z x y z I lambdalambda x y z y x z L lambdalambda x n x 32 n 0 xffffffff 定义每轮中循环左移的位数 这里用4个元组表示 用元组是因为速度比列表快 shi 1 7 12 17 22 4 shi 2 5 9 14 20 4 shi 3 4 11 16 23 4 shi 4 6 10 15 21 4 定义每轮中用到的M i 次序 m 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 m 2 1 6 11 0 5 10 15 4 9 14 3 8 13 2 7 12 精品文档 7欢迎下载 m 3 5 8 11 14 1 4 7 10 13 0 3 6 9 12 15 2 m 4 0 7 14 5 12 3 10 1 8 15 6 13 4 11 2 9 定义函数 用来产生常数T i 常数有可能超过32位 同样需要 0 xffffffff操作 注意返回的是十进 制的数 defdef T i result int 4294967296 abs math sin i 0 xffffffff returnreturn result 定义函数 用来将列表中的元素循环右移 原因是在每轮操作中 先运算A的值 然后是D C B 16轮 之后右恢复原来顺序 所以只要每次操作第一个元素即可 defdef shift shift list shift list shift list 3 shift list 0 shift list 1 shift list 2 returnreturn shift list 定义主要的函数 参数为当做种子的列表 每轮用到的F G H I 生成的M 以及循环左移的位数 该函数完成一轮运算 defdef fun fun list f m shi count 0 globalglobal Ti count 引入全局变量 T i 是从1到64循环的 whilewhile count 0 x67452301 defdef reverse hex hex str hex str hex str 2 hex str list forfor i inin range 0 len hex str 2 hex str list append hex str i i 2 hex str list reverse hex str result 0 x 0 x join hex str list returnreturn hex str result 显示结果函数 将最后运算的结果列表进行翻转 合并成字符串的操作 defdef show result f list result f list1 0 4 forfor i inin f list f list1 f list index i reverse hex i 2 result result f list1 f list index i returnreturn result 精品文档 9欢迎下载 程序主循环 whilewhile True abcd list A B C D Ti count 1 input m raw input msg msg 对每一个输入先添加一个 0 x80 即 10000000 ascii list map hex map ord input m msg lenth len ascii list 8 ascii list append 0 x80 0 x80 补充0 whilewhile len ascii list 8 64 512 0 ascii list append 0 x00 0 x00 最后64为存放消息长度 注意长度存放顺序低位在前 例如 消息为 a 则长度为 0 x0800000000000000 msg lenth 0 x hex msg lenth 2 msg lenth 0 x 0 x 0 x msg lenth 0 x rjust 16 0 0 msg lenth 0 x big order reverse hex msg lenth 0 x 2 msg lenth 0 x list forfor i inin range 0 len msg lenth 0 x big order 2 msg lenth 0 x list append 0 x 0 x msg lenth 0 x big order i i 2 ascii list extend msg lenth 0 x list printprint ascii list 对每个分组进行4轮运算 forfor i inin range 0 len ascii list 64 将最初128位种子存放在变量中 aa bb cc dd abcd list 根据顺序产生每轮M 列表 order 1 genM16 m 1 ascii list i order 2 genM16 m 2 ascii list i order 3 genM16 m 3 ascii list i order 4 genM16 m 4 ascii list i 精品文档 10欢迎下载 主要四轮运算 注意打印结果列表已经被进行过右移操作 abcd list fun abcd list F order 1 shi 1 printprint abcd list fun abcd list G order 2 shi 2 printprint abcd list fun abcd list H order 3 shi 3 printprint abcd list fun abcd list I order 4 shi 4 printprint 将最后输出与最初128位种子相加 注意 最初种子不能直接使用abcd list 0 等 因为 abcd list已经被改变 output a hex int abcd list 0 16 int aa 16 0 xffffffff 1 output b hex int