数字签名

烟草的香味

发布于 2020-06-01 11:06:04

7270

发布于 2020-06-01 11:06:04

文章被收录于专栏：烟草的香味烟草的香味

概述

还记得之前在介绍HTTPS的时候提到过的数字签名吗?

忘了?? 来, 复习一下. 揭开HTTPS的神秘面纱

其中用到了非对称加密算法, 此算法分为公钥和私钥, 一个加密, 只能用另一个进行解密.

第一次看到非对称加密算法的时候, 说实话我有些懵逼, 实在是想不到为何会有如此神奇的算法? 你就好比有一个函数, 通过 x, 能够计算得出 f(x), 但是根据 f(x), 算不出 x. 到这我还能够理解, 很多函数都存在多个解. 但是你又告诉我, 根据 f(x)和 n, 就能够算出 x??这么神奇的么? 让我不得不想着看看它到底是个什么东东... 简单看了看之后发现, 数学果然是个神奇的东西.

让我们尝试还原数字签名的发展.

人工签名时代

提到了签名, 首先想到的就是每个人的签名了. 在以前. 如果小王给你打了个欠条, 为了防止到时候他赖账, 就会要求他在欠条上签字, 这样到时候如果他赖账, 你就可以拿着欠条以理服人.

但是, 就怕你遇到的是一个无赖, 到时候你拿着欠条去找他, 他说这不是他签的字, 怎么办? 你当然可以要求他现场签一个, 然后比对二者是否相同. 但是他也完全可以现场签一个不同的字出来. 这就比较尴尬了. 这时就需要一个中立的组织来保存每个人的签字, 到时如果他想抵赖, 就到公证处, 将他签名的存根拿出来进行比对. 孰是孰非, 立竿见影. 同时你看到签名, 就可以确认这张欠条确实出自小王的手笔.

工业化时代

步入工业化时代了, 以前的人工签名应该要摒弃了, 毕竟模仿一个人的字体并不是什么难事. 在工业化时代, 我们假设每个人都有一把属于自己的锁和钥匙, 每个人都不同, 并且这把锁装有人体识别器, 只有它的拥有者才能将它锁上.

好, 这个时候, 如果小王又借你的钱, 他再给你打欠条. 不用他在欠条上签字了, 只要将欠条放到一个箱子里, 然后让小王用自己的锁锁上就行了, 因为只有小王可以锁上自己的这把锁. 等到他又赖账的时候, 你就让小王用自己的钥匙把箱子打开, 只要能打开, 就说明这是他的锁. 但是, 他还是可以自己造一把假钥匙, 然后拿出来尝试开锁, 当然打不开了. 真是个无赖, 也罢, 再来一个公证处, 他保存着所有用户的钥匙, 只要到公证处取出小王的钥匙就行了, 谁也别想赖账.

同时因为用小王的钥匙将锁打开了, 那就必然是小王的锁. 而每个人的锁只有自己能锁上, 说明箱子里的欠条必然是小王放进去的.

数字化时代

终于来到了数字化时代. 也要引出数字签名了, 数字签名和上面上锁的思路基本一致.

既然是数字化, 那所有数据都是数字咯. 小王又借你钱了, 这次他打的欠条就是数字9(为了方便取了个简单的数). 现在要对这个数字进行签名了, 也就是刚才的上锁操作. 签名后的数字必须是只有小王才能算出来. 如何实现呢?

还记得之前在介绍迪菲-赫尔曼算法的时候, 介绍过的钟运算嘛? 来来来, 再复习一下: 密钥交换算法: 迪菲-赫尔曼算法

上锁操作

小王选择自己的一个私人数字: 7, 以及自己的钟大小: 23.

签名数字就是: 7*9%23=17.

之前在介绍钟算的时候就提到过了, 这种算法很容易被暴力破解, 被人算出这个私人数字, 别急, 很快你就能看到熟悉的指数对数了. 还有, 别忘了签名的用户, 不光要上锁, 还要有钥匙能够把锁打开.

开锁操作

当然, 如果将小王的私人数字7给你, 你就可以对其进行解锁. 但是, 这也就意味着你也可以上锁啊. 当前需要只有小王才能完成上锁的操作, 其他人不可以.

这个时候就需要一个很巧妙的数字, 也就是上面的钥匙. 这个数字就是10. 不要问我10是怎么来的, 在这里我是脚本跑出来的, 但是有算法, 咱不懂.

来, 一段计算公钥的 Python 代码, 暴力计算, 钟大小不要太大哦, 自己测试用用就行.

def get_public_key(clock_count: int, private_key: int) -> int:
    """
    计算出用户的公钥
    :param clock_count: 用户的钟大小
    :param private_key: 用户的私钥
    """
    # 遍历每一个数字, 判断是否是公钥
    for public_key in range(1, clock_count):
        is_public_key = True
        # 遍历所有数字结果, 判断是否每一个都相同
        for j in range(1, clock_count):
            # 签名信息
            sign = j * private_key % clock_count
            # 解锁信息
            tmp_j = sign * public_key % clock_count
            if tmp_j != j:
                is_public_key = False
                break
        if is_public_key:
            return public_key
    return 0

开始开锁, 用小王的钥匙开锁: 10*17%23=9. 拿到了上锁的信息. 这个时候, 你就可以确定, 这条信息确确实实是小王发给你的. 当然, 和之前一样, 也需要一个公证处来保存小王的公开数字和钟大小.

你以为到这就完了么? 没有, 这个乘法并不是最终版本, 因为公式的简单性, 只要写个程序暴力破解, 就可以拿到一个人的私钥. 而这, 也就没有安全性可言了.