单向函数及应用

密码

定义

单向函数

给定任意两个集合X和Y。 函数f：X　Y 称为单向的，如果对每一个x属于X，很容易计算出函数f(x)的值，而对大多数y属于Y， 要确定满足y=f(x)的x是计算上困难的(假设至少有这样一个x存在)。注意，不能将单向函数的概念与数学意义上的不可逆函数的概念混同，因为单向函数可能是一个数学意义上可逆或者一对一的函数，而一个不可逆函数却不一定是单向函数。
即满足下列两条件：
① 对于所有属于 f 定义域的任一 x ，可以很容易计算 f( x ) = y；
② 对于几乎所有属于 f 值域的任一 y ，则在计算上不可能求出 x 使得 y = f( x )；

举几个例子：
1. 高阶多项式 令 f 为一 n 阶多项式，且 y = f( x ) = x^n + a[n-1] x^(n-1) + … + a[1]x + a[0] mod p。给出a[0]，a[1]， …，a[n-1]，p 及x，欲求 y ，只需最多n个乘法及n-1个加法。因为 y = f( x) = (...(x + a[n-1]) x + a[n-2])x + a[n-3]) x + ... +a[1]) x + a[0] mod p。此即为有名的Honer's Rule。但若已给a[0]，a[1]， …，a[n-1]及y，欲求出 f( x )的 x，则至少需要n^2((log[2]p)^2)次乘法，当n及p很大时，可知由y求x，比由x求y难上许多。
2. 求离散对数 （mod为求余运算）令素数p满足p-1含有另一大素因子q（即q整除p-1）及一整数g，1 已给一整数x，欲求y = g^x mod p，最多只需要『log[2]x』+ w(x) - 1个乘法。其中『a』表示高斯符号，即比a小的最大整数。如a = 3.14，则『a』= 3。w( x) 表示x用二进制表示法中所有1的个数。例如 x=15=1111[2]，则g^15=(((1*g)^2*g)^2*g)^2*g mod p。只需要3+4-1=6次乘法。但若已给p，g 及y 欲求x ，此问题称为求离散对数问题。现今已知最快的方法需要L（p）=exp(ln p (ln( ln p ))^(1/2))次运算。求离散对数为几千年来数学界一直无法突破的难题。当 p = 512时，L(p)约为2^256≈ 10^77。欲由y求出x,则为计算机上不可能。

散列函数

一般的线性表，树中，记录在结构中的相对位置是随机的，即和记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上，查找的效率依赖于查找过程中所进行的比较次数。 理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。
散列（Hashing）通过散列函数将要检索的项与索引（散列，散列值）关联起来，生成一种便于搜索的数据结构（散列表）。

常见应用

MD5（Message Digest Algorithm 5）：是RSA数据安全公司开发的一种单向散列算法，MD5被广泛使用，可以用来把不同长度的数据块进行暗码运算成一个128位的数值。

SHA（Secure Hash Algorithm）这是一种较新的散列算法，可以对任意长度的数据运算生成一个160位的数值。

MAC（Message Authentication Code）：消息认证代码，是一种使用密钥的单向函数，可以用它们在系统上或用户之间认证文件或消息。HMAC（用于消息认证的密钥散列法）就是这种函数的一个例子。

CRC（Cyclic Redundancy Check）：循环冗余校验码，CRC校验由于实现简单，检错能力强，被广泛使用在各种数据校验应用中。占用系统资源少，用软硬件均能实现，是进行数据传输差错检测地一种很好的手段（CRC 并不是严格意义上的散列算法，但它的作用与散列算法大致相同，所以归于此类）。

实现

Python中内置的hashlib模块提供了MD5和SHA1等摘要算法

import hashlib
#MD5是最常见的摘要算法，速度很快，生成结果是固定的128 bit字节,通常用一个32位的16进制字符串表示。
md5 = hashlib.md5()
md5.update('how to use md5 in python hashlib?'.encode('utf-8'))
print(md5.hexdigest())
#d26a53750bc40b38b65a520292f69306
#SHA1的结果是160 bit字节，通常用一个40位的16进制字符串表示。
sha1 = hashlib.sha1()
sha1.update('how to use sha1 in python hashlib'.encode('utf-8'))
print(sha1.hexdigest())

使用这种方法在用户密码管理时能去的很好的效果，如果在数据库中用加密后的密文保存密码，假设数据库被窃取后也能保证用户的安全；同样，在验证用户登录时密码是否匹配也可以直接采用加密值进行匹配。

例子

验证密码

import hashlib
db = {
    'michael': 'e10adc3949ba59abbe56e057f20f883e',
    'bob': '878ef96e86145580c38c87f0410ad153',
    'alice': '99b1c2188db85afee403b1536010c2c9'
}
def login(user,password):
    md5 = hashlib.md5()
    md5.update(password.encode('utf-8'))
    pw_md5 = md5.hexdigest()
    if pw_md5 == db[user]:
        print('Ture')
    else:
        print('False')

加盐处理

import hashlib
db = {}
def register(user, password):
    safe_password = password + user + 'the-Salt'
    md5 = hashlib.md5()
    md5.update(safe_password.encode('utf-8'))
    get_md5 = md5.hexdigest()
    db[user] = get_md5
def login(user,password):
    safe_password = password + user + 'the-Salt'
    md5 = hashlib.md5()
    md5.update(safe_password.encode('utf-8'))
    pw_md5 = md5.hexdigest()
    if pw_md5 == db[user]:
        print('Ture')
    else:
        print('False')   

参考文章：
http://www.cfca.com.cn/20150811/101230827.html
https://www.liaoxuefeng.com/wiki/0014316089557264a6b348958f449949df42a6d3a2e542c000/0014319556588648dd1fb0047a34d0c945ee33e8f4c90cc000