点击上方蓝色字体，关注我们
在生活中，我们经常要用到手机支付。手机支付是如何保证安全的呢？这就涉及到数字签名了。
为了解释数字签名，我们首先来研究一个问题：生日。
1生日碰撞
在一个班级里，我们偶尔会发现生日相同的同学。如果以前没有注意，现在也可以做实验：在一个几十人的微信群里，大家挨个报上自己的生日，看看有没有生日相同的？
也许有同学会想：这个概率太低了。一年有365天，如果群里有50个人，最多只能填满全年的1/7，两个人生日在同一天的概率太低了。
事实真的如此吗？
这是一个著名的问题，称为生日碰撞。它的结果令许多人惊奇：只要班里有23个人，有生日相同的概率就超过50%。如果有50个人，有生日相同的概率就超过97%。
我们来解释一下原因。我们令P表示所有人的生日都不在同一天的概率，那么1-P就是至少有两人生日在同一天的概率。为了方便起见，我们暂时不算闰年的2月29日。
如果只有一个人：无论这个人生日在哪一天，都不会有人与他生日相同。或者说：他的生日有365种可能，生日不相同的可能也是365种，所以生日不同的概率为
如果有两个人，那么第一个人的生日在365天中的任意一天，第二个人生日不能与第一个人相同，只有364种选择，第二个人不与第一个人撞车的概率为364/365。因此两人生日不同的概率为
如果有3个人，那么第一个人的生日在365天中的任意一天，第二个人的生日不能与第一个人相同，有364种选择，第二个人不与第一个人撞车的概率364/365。第三个人的生日不能与前两个人相同，只有363种选择，不与前两个人撞车的概率为363/365。这样，三个人生日都不相同的概率为
……
按照这种方法，我们可以计算出如果有n个人（n≤365）时，所有人生日都不同的概率为：
我们可以列一张表，并把“存在生日相同的人”的概率1-P同时列出
我们会发现：随着人数的增加，生日彼此不同的概率急速下降，有相同生日的概率逐渐增加。我们也可以画出一张图表示这个趋势：
我们会发现：只要人数超过23个，有相同生日的人概率就超过了50%。如果人数超过50个，发生生日碰撞的概率就非常接近于1了。是不是与直觉不太相同？
2哈希函数
那么，这个问题在生活中有什么应用呢？这就涉及到与我们日常生活息息相关的问题了：信息安全。
比如：当我们用手机支付购买一件商品的时候，手机会向服务器发出请求。此时面临两个问题：
第一，支付系统中枢怎么确认这个请求是账号使用者发出的，而不是被人冒充的？
第二，支付系统如何保证在同意了这笔请求后，使用者不会抵赖？
在这个问题上，数字签名就开始发挥作用了。数字签名可以配合加密系统，完成上述工作。
数字签名比较通用的算法是哈希函数。所谓哈希函数，是指将一串代码映射到一个比较短的代码上。它有两个特点：第一是位数固定，即无论原代码是多少位，哈希值的位数都一样多。第二是单向性，即从原代码推导出哈希值很容易，但是哈希值反推出原代码几乎是不可能的。
这非常像一个人和他的生日。无论这个人名字多长，生日的位数都是固定的。而且，已知一个人，求出他的生日很容易；给出一个生日，问这个人是谁几乎是不肯能的。
3数字签名
利用这个原理，就可以进行数字签名了。
首先，进行通讯的双方A和B有一对公钥、私钥对，私钥在发送方A手中，可以对信息进行加密。公钥是公开的，任何人都可以获得，用于解密。首先发送方计算信息的哈希函数，然后用私钥进行加密。然后，信息发送方A将加密后的信息和数字签名发送给接收方B，接收方B就可以对信息和签名进行解密，并验证这个解密后的数字签名和信息是否符合哈希函数。如果符合，就说明信息来源于发送方，并且没有被篡改。
说通俗一点：比如我们要派一个人张三到某地执行任务，会把张三的生日写在一个该有封印的信封里，随着张三一起派到目的地。接收方看到张三后会查验张三的生日，同时将封印的信封打开，检查张三的生日是否与信封里写的生日相同。如果相同，就接收张三。
如果中途张三被敌人抓住，派了李四冒充张三。敌人没有办法把李四的生日装进信封里，因为信封的封印只有我们发送方才有。所以只能让李四带着张三原来的信封到达目的地。接收方查验李四的生日，再打开信封对比，发现李四的生日与信封里的不同，从而拒绝李四。
这里，张三就是信息，生日就是哈希值，封印就是私钥。
4哈希碰撞
看到这，有同学会问：为什么不找一个与张三生日相同的人来冒充张三呢？是的，这就是数字签名的风险：如果两段信息的哈希值是相同的，那么接收者就会误以为信息是无误的，从而接收篡改后的信息，这个现象叫做哈希碰撞。
哈希碰撞就像生日碰撞一样，如果哈希值只有365种可能，那么只要有23段信息就有50%以上的概率出现相同的哈希值。
不过幸好，哈希值是单向算法，也就是说发生生日碰撞只能凭运气，我们无法知道到底哪个信息会和我们要发送的信息发生碰撞，就像我们要挑选一个与张三生日相同的人，而且这个人还能够执行特殊的人物，是很困难的。只要哈希值有足够多的位数，还是可以保证信息的安全。
在我们每一次扫码支付的过程中，计算机系统都帮我们完成了加密、签名等一系列过程。计算机科学本质上就是一门用电路实现的数学过程，所有的计算机科学家都是数学家，由于这些科学家的努力，才能让我们的生活越来越方便。
更多阅读
李老师直播课堂2018暑假课表已发布 四位名师带你学好数理化
李永乐
李永乐老师：北京大学物理与经济双学士，清华大学电子工程硕士；北京市中学物理教师/物理竞赛教练。从教十年，培养清华北大学生200余人，国际奥赛、亚洲奥赛、国家奥赛金牌十余名。
扫二维码，关注公众号
↙↙↙点击下方“阅读原文”，进入李老师直播课网站。
继续阅读
阅读原文