密码学

对称加密算法

对称密码包括分组密码与序列密码。分组密码代表算法有AES,DES/3DES,RC4等,序列密码代表算法有A51。

非对称加密算法

非对称加密算法的安全性往往需要根据数学问题来保障,目前主要是基于大整数因数分解与离散对数,椭圆曲线等经典数学难题。

大整数分解难题:给定两个大素数,计算它们的乘积非常容易,但是将它们的乘积分解因式非常困难。

离散对数难题:设p是素数,是一个本原元,。已知,求满足的整数,并且n是唯一的,称为有限域上的离散对数问题,记

代表算法:

  • RSA:利用对大数进行质因子分解的困难性
  • Diffle-Hellman密钥交换:利用离散对数求解困难性
  • ElGamal:利用模运算下离散对数求解困难性
  • 椭圆曲线算法(ECC):利用对椭圆曲线上特定点进行特殊乘法逆运算计算(离散对数)困难性

以下进行详细介绍。

RSA公钥密码体制

利用大数因数分解困难

  • 选取大素数p和q,并秘密保存;
  • 计算,其中公开n,秘密保存
  • 随机选取正整数,使得。e作为加密密钥公开;
  • 解同余式,得到d作为解密密钥,秘密保存;
  • 加密:对明文,计算,得密文c;
  • 解密:对密文,计算,得明文m。

Diffle-Hellman密钥交换

利用离散对数求解困难

  • Alice和Bob协商一个有限循环群G和它的一个生成元g;
  • Alice随机选择自然数a并将发送给Bob;
  • Bob随机选择自然数b并将发送给Alice;
  • Alice计算;
  • Bob计算;
  • 这样Alice和Bob就同时协商出群元素,用来共享秘密。

ELGamal公钥密码体制

利用模运算上离散对数求解困难

  • 选取大素数p,是一个本原元,p和公开;
  • 随机选取整数,解同余式,得到作为加密密钥公开,d作为解密密钥,秘密保存;
  • 明文空间为,密文空间为;
  • 加密:对任意明文,秘密随机选取一个整数,计算得密文
  • 解密:对任意明文,计算得明文m。

一般的,只要选取适当的素数p,在有限域上的离散对数问题是难解的。在上述中,由求解d,就是求解离散对数。

ECC椭圆曲线密码

  1. ECC的主要特点:

    • 比其他方法(如RSA)使用更小的密钥。

      签名算法有RSA、DSA、ECC(椭圆曲线数字签名算法ECDSA)等。前两者因为秘钥长度和性能的关系,现在使用越来越少,例如常见的RSA2048,秘钥长度就达到了2048bit,也就是2KB大小,在一些嵌入式场合消耗比较大,而ECC只需要224bit,因此比特币在保证数据安全性基础的算法选择上选择了ECC。

    • 可以定义群之间的双线性映射,基于Weil对或Tate对。

  2. ECC也就是椭圆曲线密码学,在使用ECC进行数字签名的时候,需要构造一条曲线,也可以选择标准曲线,诸如:prime256v1、secp256r1、nistp256、secp256k1等等。比特币使用的是secp256k1,也就是比特币选择的加密曲线,秘钥长度256bit,也就是32字节。

  3. 过程

    • 用户A选定一条椭圆曲线,并取椭圆曲线上一点,作为基点
    • 用户A选择一个私有密钥,并生成公开密钥
    • 用户A将和点传给用户B
    • 用户B接到信息后 ,将待传输的明文编码到上一点,并产生一个随机整数
    • 用户B计算点
    • 用户B将传给用户A
    • 用户A接到信息后,计算,结果就是点。因为,再对点M进行解码就可以得到明文。

    在这个加密通信中,是公开的,是私密的,因为通过求解或通过求解都是困难的,因此无法窃取明文信息。

  4. 拓展

双线性映射(Bilinear Pairing)

  1. 利用椭圆曲线上离散对数求解困难,可以从超奇异椭圆曲线中的Weil和Tate配对中得到。常用来构造零知识证明,基于身份的加密等。缺点是加解密操作的实现比其他机制花费的时间长。

  2. 定义

    是由生成的循环加法群,其阶为素数q,是一个阶为q的循环乘法群。双线性映射是指具有如下性质的映射

    • 双线性:对所有的
    • 非退化:存在一个,满足
    • 可计算:对,存在一个有效的算法计算
  3. 拓展

    详见此处

关于HTTPs

在传统的HTTPs加密通信中,公钥的验证是通过CA进行的,即向CA注册时,能够拿到由CA签名加密的公钥,这样别人拿到后用CA的公钥解密即可验证其身份。

具体来说,A与B通信,首先A向B发送自己的公钥,B通过CA验证A公钥的真实性,然后用A的公钥加密B的公钥和通信时使用的密钥,发给B,B用自己的私钥解开就拿到了通信密钥,之后即可通过通信密钥进行对称加密实现通信。原理图如下:

区块链中也依然存在CA实现公钥身份证明,若要去掉CA这个中心呢,设想公钥是否可以用区块链来实现公开透明共识,然后发现有人写了一篇专利,主要步骤如下:

  1. 用户向代理节点申请将公钥托管在区块链中,用户向代理节点发送请求,请求在一定时间内将公钥存储在区块链网络中的权利,代理节点在通过申请后,生成一对临时的公钥私钥对以及用户的ID,代理节点将临时公钥、用户ID、用户托管的起止时间、代理节点的ID、签名算法以及信息类型标志打包成一个信息包,利用代理节点的公钥签名后发布到网络中,代理节点将密钥对信息以及用户ID发送给请求的用户,用户在信息被区块链确认之后,发布自己的公钥;
  2. 用户生成公钥私钥对,并生成公钥信息,将自己的公钥信息广播到区块链网络中用户在生成自己的密钥之后,将密钥的生效时间段、用户ID、签名算法以及信息类型标志封装成附加信息附在生成的公钥之后,生成完整的公钥信息,用户对完整的公钥信息进行签名,签名所使用的私钥为存在于区块链中的有效公钥信息对应的私钥,使得收到信息的节点能够对公钥信息进行验证;
  3. 节点对收到的公钥信息进行验证,加入本地缓存当节点从网络中收到一条公钥信息时,通过附加信息中存储的签名者ID查找到用户存储于区块链中的公钥信息;通过验证签名的方式证明信息由用户自身生成;在信息通过签名验证后,节点会将公钥信息存储入本地缓存中,同时转发用户的公钥信息;
  4. 节点在生成或收到一个新的区块后,开始进行下一个区块的生成节点…
    详见此处

其他密码学算法

哈希算法

如比特币中使用了SHA256,RipeMDk1和Base58。

差分隐私(Differential Privacy, DP)

  1. 核心思想:对于差别只有一条记录的两个数据集,查询它们获得相同值得概率非常接近。即攻击者无法通过计算统计信息获得数据集中单个记录信息。

  2. 实现方案:在查询结果中加入随机性,常用方法是在结果上加满足某种分布的噪音。

    • 法一:Laplace机制—在查询结果中加入Laplace分布的噪音,适合于数值型输出;
    • 法二:指数机制—在查询结果中用指数分布来调整概率,适用于非数值型输出。
  3. 缺点:对背景知识假设过强,需在查询中加入大量的随机化,导致数据的可用性急剧下降。

    • 数据库小时,查询误差极大;
    • 数据库大时,非DP的传统方法(k-anonymity, I-diversity)也能基本保证privacy,同时查询误差极小。
  4. 应用:

    • 一般和访问权限控制以及信息流向分析(Information Flow Analysis)用来做统计分析型数据库的隐私保障;
    • PATE框架:有效保护隐私训练数据。详见此处
  5. 小结:

    差分隐私(DP):降低隐私预算—-> 噪声聚合机制—-> 共识度↑ + 噪声↑

    共识度高,加入噪声不会影响统计结果的正确性。

    噪声过多,会影响结果的可用性。可训练新的推断模型投入使用(PATE框架的student模型)。

同态加密(Homomorphic Encryption)

  1. 核心思想:加密运算和代数运算可以交换顺序的加密方案。
  2. 内容:E(x)为加密算法,若 x op y = z,则E(x) op E(y) = E(z)
  3. 实现方案:
    • 部分同态加密:
      • ELGamal公钥加密算法—乘法同态性
      • Paillier公钥加密算法—加法同态性
      • RSA公钥加密算法—乘法同态性
      • Benaloh—加法同态性
      • Goldwasser-Micali—异或同态性
    • 全同态加密:
      • BGN:BonehGod-Nissim,同时对加法和乘法同态,可进行任意次加法同态运算,只能做一次乘法同态运算。可使用HElib库实现
      • Gentry算法:可使用FHE-CODE实现
  4. 意义:数据处理权和数据所有权分离,使企业可以在防止自身数据泄露的同时,利用云服务的算力。

零知识证明(Zero-Knowledge Proof)

  1. 核心思想:证明信息正确性而不暴露信息。
  2. 在计算机领域,一般将原始问题映射为NP问题,验证者只要验证证明者给出的NP问题的解即可,无需将计算结果的算法暴露出来。
  3. 应用:Zcash,Super-ZK等

基于属性加密(Homomorphic Encryption)

详见此处

可验证随机函数(Verifiable Random Function,VRF)

主要是哈希算法+非对称加密+零知识证明,其中零知识证明通过双线性对构造。详见此处

量子密码学

  1. 在量子计算模型下,经典数论假设的大整数分解和计算有限域/椭圆曲线上的离散对数问题都存在多项式时间(PPT)的量子算法。
  2. 后量子密码系统常见数学技巧:
    • 杂凑函数,多变量方程—构造签名方案
    • 纠错码—构造加密方案
    • 格密码
    • 超奇异椭圆曲线同源问题—密钥交换和签名方案的构造

其他隐私保护方案

通道(Channels)

通道内的交易都不是在链上

混合器(Mixes)

  1. 核心内容:中心处理器(混合器)混合交易的来源与去向,使无法追溯。

  2. 举个栗子:

    初始状态:A->B:10¥,C->D:10¥

    混合后: A->B:2¥,C->B:8¥,A->D:8¥;C->D:2¥

  3. 用途:

    • 抵抗Sybil攻击(女巫攻击,即攻击者创建多个账户达到攻击的目的)
    • 保护隐私的投票

环签名(Ring Signature)

拥有一组群签名中任意一个签名的签署权。

门限签名(Threshold Signature)