logo头像

Hacked By Swing

密码学救命稻草

前言

部分参考

哈希函数

定义和安全性

  • 定义:单向函数,固定长度

三种攻击由强到弱:

  • 原象攻击:得到了哈希函数的逆(给定一个哈希值,得到其原文)

  • 第二原象攻击:给定明文 \(M\) 找到 \(M'\) 使得 \(H(M') = H(M)\) ,也就是给了已知明文找到另一个明文具有相同的 hash

  • 碰撞:找到任意两个消息明文使得哈希值相同

比特安全性及其原理

比特安全性:攻破密码需要 \(2^n\) 次操作,那么比特安全性为 \(n\)

生日悖论:在 \(n\) 人中出现两人生日为同一天的概率大于 \(\frac{1}{2}\) 需要 \(n\) 最小为多少?

实际上比特安全性只需要出现碰撞的概率大于 \(\frac{1}{2}\) ,所以在哈希函数中,碰撞比特安全性为输出长度的 \(\frac{1}{2}\)

抗原象攻击的比特安全性与哈希值长度相同,抗第二原象的比特安全性就比较奇怪了,和明文的长度有关

常用哈希函数及其构造方式、哈希值长度和安全性

构造方式:

  • Merkle-Damgard: 把消息分块,对于每一个块都调用压缩函数(Compression Function) 进行压缩,以最终的压缩函数结果为哈希函数输出
  • Sponge: 分为吸收和挤压两个阶段,吸收阶段调用压缩函数然后每次与 padding 进行异或操作,经过反复的吸收之后,再通过挤压过程输出哈希值
  • MD 构造的问题:存在长度扩展攻击的可能
哈希函数 构造 哈希值长度 碰撞安全性(大多数是一半)
MD5 MD 128 bit 64
SHA1 MD 160 bit <80
SHA2 族 MD 名称上就是,比如 SHA-256 就是 256 bit \(\frac{n}{2}\)
RIPEMD-160 MD 160 bit 80
WhirlPool Miyaguchi-Preneel (不知道是个啥,所以估计应该不考吧) 512 没说,所以不知道
SM3 MD 256 bit 128
Sha3 族 Sponge 看名称,SHA3-224 就是 224 \(\frac{n}{2}\)

哈希函数应用

  • Key Deriving Functions :密钥生成
  • MAC:消息认证码
  • 在签名中生成定长摘要
  • 把教科书式公钥密码改为安全的加密方式
  • 构造伪随机数生成器

分组密码

对加密通信的攻击

  • 唯明文攻击:只有明文
  • 已知明文攻击:已经获取到了一些明文密文对,但是没有密钥,想要解密的密文不知道明文
  • 选择明文攻击:可以使用加密系统进行加密,也就是可以自己选择一些明文进行加密,然后得到密文,没有密钥
  • 选择密文攻击:可以任意构造一些密文进行解密
  • 选择文本攻击:选择明文攻击 + 选择密文攻击

分组密码的定义

对称密码,将明文分组进行加密,所以单次加密的长度是固定的(一个块)

两种典型构造

  • Feistel:右边的混入密钥(通过轮函数把密钥、右边的明文进行计算)和左边的异或,得到新的右边的内容,原来右边的内容放到左边不变,最后一轮不交换。解密和加密一样,把密钥顺序倒过来就行了。
  • SP:Substitution-Permutation,每一轮混入密钥,s-box 替换然后重新排列。最后一轮不进行重新排列,保证加密解密一致。

常用分组密码及其构造方式、密钥长度、安全性

分组密码 构造方式 密钥长度 安全性
DES Feistel 56 (8 字节,每字节有一个校验位)
3DES Feistel 56 * 3 112
SM4 非平衡 Feistel 128 ?
AES SP 128/192/256

分组密码的模式

  • ECB:不安全,直接分块直接加密,块与块之间的规律保留了下来
  • CBC:需要 IV ,每次加密之后和下一块异或,避免块之间的规律保留,加密不可并行,解密可以
  • CFB,OFB:不能并行,也不会不安全(主要是在校验位上存在一些优势,不管)
  • CTR:使用一个计数器规避掉块之间的规律,每个块和计数器加密后的明文异或,可以并行

序列密码

One-Time-Pad

密钥和明文等长,直接异或,完美密码,但是不可用

序列密码概念和分组密码区分

概念:使用伪随机数流作为密钥

和分组密码区分:(PPT 中没有明确)不需要分组,直接可以支持变长,对错误反应敏感(分组密码 CBC 模式中如果传输错误不容易处理)

MAC 和 AEAD

完整性及其对安全性的影响

完整性得不到保证可能导致传输过程中内容被中间人修改。

MAC 消息认证码算法定义

\(c = MAC(k, m)\) 其中 \(k\) 为 MAC 算法的密钥,\(m\) 为消息。

MAC 与加密类似,但是不可逆。

AEAD 的定义

AEAD 同时提供保密性以及完整性(认证)的加密系统。

(其实就是把加密过程和 MAC 过程一起考虑了,例如原来加密是由 AES 这类算法完成的,然后认证则是 MAC 算法,AEAD 就是一个算法两个都有)

分开的话,四种方案:

  • 先 hash 再加密
  • 先认证再加密
  • 先加密再认证
  • 独立加密和认证

然而四种都有问题,所以需要 AEAD

常用的 MAC 和 AEAD 模式

MAC :

  • HMAC:以哈希算法为核心,所以可以支持不同的哈希算法,比如 HMAC-SHA256 , HMAC-SM3
  • CMAC:和 CBC-MAC 有点关系,CBC-MAC 和分组密码的 CBC 有点关系,所以就跟分组密码有点关系,于是有 AES-128-CMAC ,SM4-CMAC 这种用法

AEAD 的模式:

  • GCM: CM 指 Ctr Mode 所以组合一下分组密码 AES-128-GCM/AES-256-GCM , SM4-GCM
  • CCM:Ctr + CBC-MAC
  • ChaCha20-Poly1305
  • OCB

密码分析

两种针对 s-box 的选择明文攻击。

差分密码分析

首先我们需要知道,异或其实就是加法,只不过是在不同群下的加法(mod \(2^n\) 的群),那么一次加密过程其实可以认为是:\(y = f(x + key)\)

其中 f 函数是 s-box 替换操作,加法是异或。

假设有两个输入 \(x_1\)\(x_2\) ,那么:

\(y_1 = f(x_1 + key)\)

\(y_2 = f(x_2 + key)\)

\(\Delta x = x_2 - x_1\)

\(\Delta y = f(\Delta x) = f(x_2 - x_1) = f(x_2 + key - (x_1 + key))\)

所以,如果以 \(\Delta x\) 作为 \(x\) 进行运算,得到的 \(\Delta y\) 的结果和 key 无关,也就是说,可以认为 \(\Delta x\ xor\ key = key\)

差分分析的思路就是,如果 \(\Delta y\)\(\Delta x\) 之间存在关系,他们自己又和 key 没有关系(这样的话,key 混入的过程不会影响其规律,排列是肯定不影响的),那么就可以去恢复一部分密钥,降低恢复的难度。

举例:当 \(\Delta x = 1\) 出现 \(\Delta y = 1\) 的可能性有 2 种,分别是 \(x_1 = 4, x_2 = 5\)\(x_1 = 6, x_2 = 7\),那么枚举 \(x_1\)\(x_2\) ,保证 \(\Delta x = 1\),对他们进行加密得到 \(y_1\)\(y_2\) 同时计算出 \(\Delta y\) ,如果出现了 \(\Delta y = 1\) 说明出现了 2 种情况中的一种,这样就说明现在的 \(x_1 + key\) 为 4 或者 5 ,\(x_1\) 已知(枚举的),key 的可能性就只有两种了,这样就可以降低枚举次数。

线性密码分析

和差分密码类似,不过使用了另外的规律:

将输入位置挑选一些(也就是让这些位为 1 其他为 0 )进行加法(异或),再将输出位置挑选一些进行加法操作,两者相等的关系称作线性关系。

在完美情况下,每一位都是独立随机的,那么概率应该每一位都是 \(\frac{1}{2}\) ,然后按照乘法原理乘起来。线性密码分析就是当这个概率不是完美的时候,利用这个概率来恢复密钥。

分析的思路就是找到输入和输出线性关系最强(概率最大)的一些输入位置和输出位置,然后,对密钥进行枚举操作(只需要枚举存在线性关系的那些位置的密钥,这样相比枚举所有密钥就少了许多),计算这个线性关系。

也就是对 \(y = f(x + key)\) 枚举 key ,对于每一个 key 都调整 x 的值得到一个统计。根据规律,\(y\) 一些位和 \(x + key\) 一些位的值各自和相等的时候出现的概率出现最大的时候就说明 key 是正确的了。(所以概率差距越大越好,这样最准确,大数定律)

公钥密码

单向函数和单向陷门函数的定义和实例

单向函数:正向计算容易,反向计算困难(实例:哈希函数)

单向陷门函数:正向计算容易,反向计算困难,但是如果有陷门信息,反向计算比较简单(实例:整数分解,离散对数问题)

群环域

见 PPT (或者 wiki ,都有详细定义)

简略版:

  • 群:一个操作(加法 or 乘法),一堆对象,封闭且有逆元,注意,群不要求可交换,可交换的为交换群(阿贝尔群)
  • 环:两个操作,其中的一个操作(加法)是交换群,乘法有幺元,满足结合律和分配律(乘法不是群,没有逆)
  • 域:两个都是交换群

公钥加密的定义

密钥空间 \(K\) ,明文空间 \(M\) ,密文空间 \(C\)

一个密钥 $k K $ 为一个元组 \((pk, sk)\) 其中 \(pk\) 为公钥,\(sk\) 为私钥。

加密:\(E_{pk} = M \rightarrow C\) 解密:\(D_{sk} = C \rightarrow M\)

满足:\(D_{sk}( E_{pk}(m)) = m\) 对任意 \(m \in M\) 成立

欧几里得算法和扩展欧几里得算法

欧几里得算法:\(gcd(a, b) = gcd(b, a\ mod\ b)\) 如果 \(a\ mod\ b = 0\) 那么 \(gcd(b, 0) = b\)

扩展欧几里得算法:计算 \(ax + by = gcd(a, b)\) 的解。

记号:\(gcd(a, b) = gcd(a', b') = gcd(b, a)\) 也就是 \(a' = b, b' = a\ mod\ b\)

思路:

  • \(a\ mod\ b = 0\) 时,\(gcd(a, 0) = ax + by\) ,显然,\(x = 1\)\(y\) 为任意值(\(b\) 为 0)
  • \(a\ mod\ b \neq 0\) 时,\(gcd(a, b) = gcd(a', b') = ax + by = a'x' + b'y'\) ,此时 \(b' = a\ mod\ b\) 所以 \(a = kb + b'\),代入,\((kb + b')x + by = a'x' + b'y' = b(kx + y) + b'x = a'(kx + y) + b'x\) ,所以 \(kx + y = x'\)\(x = y'\) ,再进行一步计算,得到 \(x = y', y = x' - ky'\) ,在计算欧几里得的时候是递归计算的,所以 \(x'\)\(y'\) 已经计算完了,那么就可以反推出 \(x\)\(y\) 直到整个计算过程完成,得到 \(x\)\(y\) 了。

Diffie-Hellman、ElGamel 加密

DH密钥交换:利用离散对数问题,即 \(g^x \equiv y\ (\\ mod\ p)\)

交换过程,双方分别随机选群内的一个元(即 \([1, p-1]\) 的一个数),得到 \(a\)\(b\) ,然后分别计算指数 \(g^a\)\(g^b\) ,进行密钥交换,由于双方分别有指数位,然后有对方的底数位,那么 \((g^a)^b = (g^b)^a = g^{ab}\) 就得到了公共的密钥,而中间人没有 \(a\)\(b\) ,只有 \(g^a\)\(g^b\) 无法得到 \(g^{ab}\)

ElGamel 加密以 DH 为基础:

参数大质数 \(p\) 和生成元 \(g\)

密钥(和 DH 类似):任意挑选 \([1, p-1]\) 的一个元素为私钥 \(d\) ,计算 \(y = g^d\ (\ mod\ p)\) 为公钥

加密:再挑选一个 \(r\) ,计算 \(c_1 = g^r\ (\ mod\ p)\) ,再计算 \(c_2 = m \times y^r\ (\\ mod\ p)\) 密文为 \((c_1, c_2)\)

解密:\(m = (c_1^d)^{-1} \times c_2(\ mod\ p)\)

椭圆曲线的定义和椭圆曲线算术:点加、倍点、点的标量乘法

椭圆曲线:\(y^2 = x^3 + Ax + B\)

点加:两点连线交椭圆曲线的第三点关于 x 轴的对称点

倍点:(倍加?)自己加自己,作切线交椭圆曲线的第三点关于 x 轴的对称点

点的标量乘法:连续点加 \(n\)

具体计算方法:

\(a = (x_1, y_1), b = (x_2, y_2)\)\(c = a + b\)

\(a \neq b\) 时,\(k = \frac{y_2 - y_1}{x_2 - x_1}\) (两点斜率),否则 \(k = \frac{3 x^2 + A}{2y}\) (两端求导除一下)

\(c = (k^2 - x_1 - x_2, k(x_1 - x_3) - y_1)\) (这个只能背了)

注意,如果是整数,那么公式中的除法就是乘逆,然后加法减法都模 \(p\) 就行了。

椭圆曲线困难问题 ECDLP

和 DLP 一样,只不过群内的元素变成了椭圆曲线整数时的点。

椭圆曲线密钥长度和比特安全性的关系

由于大步小步法,老样子,除以 2 。

素数和素性测试

素数、本元根(Primitive Roots)的定义

素数的定义:Emmm 看着办吧

本元根:整数模素数 \(p\) 得到的是一个域,域里边的乘法加法都是循环群(也就是一直乘一个数或是加一个数会算回来),本元根(应该也是生成元 generator )就是指这个数自己和自己相加/相乘可以得到整个群(mod p 内的所有元素)

费马小定理、欧拉公式

费马小定理: \(a^{p - 1} \equiv 1\ (\ mod\ p)\) 对模素数 p 内的任意数成立

欧拉公式(把费马小定理推广到合数): \(a^{\frac{(p - 1)(q - 1)}{gcd(p-1, q-1)}} \equiv 1\ (\ mod\ pq)\) 对任意 \(gcd(a, pq) = 1\) 成立(如果 \(gcd(a, pq) \neq 1\) 那么就为 0 了,所以最后这个情况也不用特殊记)

有个推论(和 RSA 原理有关,所以可以看看):\(a^x \equiv a^{x\ mod\ (p-1)(q-1)}\ (mod\ pq)\) ,证明方法可以把 \(x\ mod\ (p-1)(q-1)\) 写开(万能方法,遇事不绝就写开):\(x = k(p-1)(q-1)+r\) 然后算下去。

素数生成算法

有个素数理论可以得到素数的分布情况,大概意思就是还挺多的。那么找大素数的方法就是先生成一个不是偶数的大数(偶数肯定不是素数),然后用 MR 素数测试看是不是素数,由于还挺多的,所以一次不行多试几次就有了。

Miller-Rabin 素数测试

根据费马小定理,素数满足 \(a^{p-1} \equiv 1\ (mod\ p)\) 对于任意 \(a\) 成立,但是并不是满足这个要求的都是素数,所以再加一条 \(x^2 \equiv 1\ (\ mod\ p)\) 的解,在 p 是素数的情况下只有 1 和 -1 (也就是 p-1)(模素数才是一个群,见本原根那一节,合数不一定,群保证了只有一个幺元,也就是一个 1 ,但是不是群就说不好了,比如 mod 8 的时候,\(5^2 = 25 = 1\ (mod\ 8)\) 就多了一个 -1 出来)

所以,首先我们检查费马小定理的形式是不是满足,满足的时候还不够,接着得到一个序列,序列中 \(2^s\) 是能够整除 \(p-1\) 的最大的数,\(q\) 是一个任意奇数:

\(a^{p-1} = a^{2^s q}, a^{2^(s-1)q}, ..., a^q\)

这个序列中,每一个前面的数都是后一个数的平方,相当于每一步都是 \(x^2 = 1\),那么,第一个数一定为 1 (费马小定理),后面的数,要么全部为 1 ,要么第一个不是 1 的数是 -1 (也就是 p-1),像刚才 mod 8 )的情况就不是,我们得到了其中一个为 5 ,就说明不是素数)

如果通过了这个测试,差不多有 \(\frac{1}{4}\) 的概率不是素数,如果多测几次,概率就叠加了,于是就大概率得到一个素数。

具体实现的时候:

  1. 找一个 s 和 q 使得 \(p - 1 = 2^s q\) ,再随机从 1 到 p-1 选择一个 a
  2. 如果 \(a^q = 1\),那么通过测试
  3. 计算 \(a^{2^iq} = -1\) 对于 \(i = 0, .., s - 1\) 是否成立,成立则通过测试
  4. 否则未通过

其实就是倒着算。

RSA 算法

RSA 加密、RSA 签名

  1. 选择两个素数 p 和 q
  2. 计算 N = pq ,\(\phi(N) = (p-1)(q-1)\)
  3. 随机从 \([1, \phi(N)]\) 选择一个公钥指数 \(e\),要求 \(gcd(e, \phi(N)) = 1\)
  4. 计算私钥 \(d = e^{-1}\ mod\ \phi(N)\) ,用扩展欧几里得计算,即 \(ed + \phi(N)y = gcd(e, \phi(N)) = 1\) 的其中一个解

公钥:N 和 e 私钥:d

加密:\(c = m^e\ (\ mod\ N)\) 解密:\(m = c^d = m^{ed} = 1\ (mod\ N)\) 指数位 \(mod \phi(N)\) ,前面欧拉公式那有推论,所以才成立。

签名:RSA 的公钥指数和私钥是对等的!所以用私钥加密公钥解密和公钥加密私钥解密都可以,那么签名就是倒过来,用私钥加密,公钥解密,解密了看是不是和原文相等就可以验签了(注意,公钥加密的要求是公钥加密私钥解密)

为什么教科书 RSA 算法不安全?

教科书 RSA :没有加入填充方案,这个时候有很多攻击手法。比如广播攻击,在一个消息被不同但互质的公钥进行多次加密的时候,可以利用中国剩余定理然后开方得到密文(详情可以看我报告的PPT,broadcast attack 部分)

RSA 的填充方案

  • PKCS#1 v1.5 :不安全,存在解密 Oracle (可以看出解密是否正确,从而泄漏了信息)还有一些其他的攻击方法
  • PKCS#1 v2 OAEP:带有一定随机性的填充方案,可以比较好的避免广播攻击等。
  • PSS 编码:也是 PKCS#1 v2.1 的一部分

数字证书和 PKI

数字签名的概念和典型数字签名算法

数字签名:可以验证是谁签的名,不可以被其他人伪造(也就是只有他能签出这个签名来)

形式化一点,就是一个算法包括几个部分:密钥生成、签名、验签

密钥生成:得到公钥私钥 签名:利用私钥进行签名 验签:利用公钥对签名进行验证

和公钥加密相比,区别主要是公私钥反了,公钥加密里边是公钥进行加密,私钥解密,数字签名倒过来了。

典型算法:

  • RSA 签名(RSA-PSS,注意 padding)
  • Schnorr 签名:DSA 的前身
  • DSA 数字签名算法,椭圆曲线上的就是 ECDSA

RSA 签名前面说过了。

Schnorr:

基于离散对数问题,所以生成密钥的方法一样,选素数 \(p, g\) 再选一个 \(d \in {1, 2, ..., p-1}\),计算 \(y = g^d\),签名为了避免出现得到逆,还加入一个哈希函数 \(H\)

签名过程:选一个 \(r\) ,计算 \(c_1 = g^r\)\(e = H(r || M)\) (这个就相当于明文,但是签名最好不要有明文,所以加盐哈希一下),关键步骤是计算 \(c_2 = r - de\) ,签名为 (c_2, e) 验签过程:计算 \(H(g^c_2 y^e || M)\) 查看是否与 \(e\) 相等

我这里尽量保持符号和 ElGamel 中的符号一致(但是事实上差距还是很大,记忆量有点大)

DSA:

和之前又有一些区别,生成密钥过程包括:

  1. 选择素数 q ,选择素数 p 使得 p-1 是 q 的倍数
  2. 计算 \(g := h^{\frac{p - 1}{q}}\) g 不能是 1 ,如果是 1 重新算
  3. 选择 \(d \in {1, 2, ... q-1}\) 作为私钥
  4. 计算 \(y = g^{d}\) 作为公钥

签名过程:从 1 到 q-1 选择 \(r\) ,计算 \(c_1 = (g^r\ mod\ p)\ mod\ q\),如果为 0 ,重新找一个 r 。计算 \(c_2 = (r^{-1}(H(m) + d c_1)\) ,如果为 0 重新找 r ,\((c_1, c_2)\) 组成签名 验签过程:计算 \(w = c_2^{-1}\ mod\ q\),计算 \(u_1 = H(m)\times w\ mod\ q\)\(u_2 = c_1 \times w\ mod q\) 计算 \(v = (g^{u_1} y^{u_2}\ mod\ p)\ moq\ q\) 如果 v 和 \(c_1\) 相等则通过

(这两个签名太复杂了,就是一堆构造变形,而且和 ElGamel 相似但是容易弄混,根本记不住,不知道咋办,我反正是不背了)

数字证书、根证书、证书链、CA、PKI 的概念,通过浏览器观察网站的证书链,了解现实中证书的各个域,DV/EV/OV 的区别

(这一部分我完全不知道怎么复习,都背下来?完全不可能,学文科差不多)

数字证书:一段电子文档,包括公钥、一些相关信息和颁发者签名 根证书:证书链的根,验证的开始 证书链:从根证书开始,一个颁发给另一个,形成一个链,可以从根证书开始验证 CA:证书权威机构 Certification Authority ,一个公司或者组织负责验证证书的拥有者确实拥有某个实体,然后颁发证书 PKI:公钥基础建设,是一组由硬件、软件、参与者、管理政策与流程组成的基础架构,其目的在于创造、管理、分配、使用、存储以及撤销数字证书。

观察证书链。。。不知道咋复习

证书的域:

  • 版本
  • 序列号
  • 签名算法
  • 颁发者
  • 有效期
  • 客体:证书拥有者的可辨识名
  • 公钥
  • 扩展就不管了

DV/EV/OV 的区别:

  • DV:Domain Validation,验证拥有域名即可
  • OV:Organization Validation,需要身份权限的认证
  • EV:Extended Validation,也是身份全县认证,但是要求更高

浏览器里 url 栏里 https 的地方看不到公司名字的是 DV ,看的到的一般是 OV 或者 EV。

基于身份的密码定义、典型构造、应用以及和传统公钥密码/PKI 的区别

我基本放弃这一部分了。。。

身份就是指一个没有加密的任意的内容,比如一个任意的字符串(邮箱之类的),基于身份的密码就是利用一个公认的 PKG (Public Key Generator),PKG 发布一个主公钥,自己得到一个主私钥,每一方利用自己的身份从主公钥得到自己的私钥,然后向 PKG 要一个私钥。

典型构造:

不知道,又是一大堆构造,这个真没办法了。。

应用和区别:

  • 作为 PKI 的替代,不需要密钥和证书管理
  • 公钥过期机制
  • 解密密钥分发

数学困难问题

离散对数问题、EC 离散对数问题、整数分解问题、DH 问题、ECDH 问题、RSA 问题

前面基本已经有了

平滑数的概念及应用

平滑数:一个数被分解成质因数之后最大的质因数为 n 那么这个数就是 n-平滑的,一般来说平滑数就是指这个 n 比较小,那么这个时候这个数就比较容易被分解。

大步小步法和 Pohlig-Hellman 算法

这两种算法都是算离散对数问题的。

大步小步法:

计算 \(g^x = y\ (mod\ p)\),把 x 分开,写成 \(x = i\sqrt{p} + j\) ,之后:

\(g^x = g^{i\sqrt{p} + j} = g^{i\sqrt{p}} \times g^j = y\ (mod\ p)\)

\(g^j = y \times (g^{-\sqrt{p}})^i\)

这个时候 \(0 < i < \sqrt{p}, 0 < j < \sqrt{p}\) , 所以可以把 \(g^j\) 可能的值都算出来,然后再去找 \(i\) ,看不同的 \(i\) 是否会算出已经算好的 \(g^j\) ,这样就相当于用一些内存减少了运算时间。

Pohlig-Hellman:

前提:\(p - 1\) 是平滑的,那么 \(p - 1\) 很容易被分解,简单情况假设分解为 \(p - 1 = q_1 q_2\)

那么由费马小定理,\(g^{q_1 q_2} = 1\ (mod\ p)\) ,这个时候,把 \(g^x = y\ (mod\ p)\) 两边同时进行 \(q_1\) 次方运算,得到:

\(g^{x q_1} = y^{q_1}\ (mod\ p)\)

\(x_1 = x\ (mod\ q_2)\) 也就是 \(x = x_1 + k q_2\) ,那么 \(g^{x q_1} = g^{(x_1 + k q_2)q_1} = g^{x_1 q_1} g^{k q_1 q_2} = (g^{q_1})^{x_1} = y^{q_1}\ (mod\ p)\)

(遇事不绝就写开)

同理对 \(q_2\) 也来这么一发,就得到了两个式子:

\((g^{q_1})^{x_1} = y^{q_1}\ (mod\ p)\)

\((g^{q_2})^{x_2} = y^{q_2}\ (mod\ p)\)

其中 \(x_1\)\(x_2\) 都是更小的范围了,那么就可以分别把这两个求出来,然后由:

\(x_1 = x\ (mod\ q_2)\)

\(x_2 = x\ (mod\ q_1)\)

这个形式是符合中国剩余定理的形式的,所以可以用中国剩余定理求到 \(x\)

硬件安全

密码硬件安全等级 1 到 4 级的主要特征

FIPS 140-2:

  • 第一级:物理上没什么要求,算法至少得是经过验证的算法(常用的就差不多,意思就不能是自己发明的什么乱七八糟的),实例:个人电脑的加密板
  • 第二级:要求显示篡改证据,我理解就是如果被人物理搞了应该有明显痕迹可以看出来被改过,但是没有办法防止攻击者拿到想要的,只能事后。
  • 第三级:有了防护机制,我理解就是如果被人物理层次搞了,会直接归零掉,所以物理攻击比较难拿到有用的信息了。
  • 第四级:最强的,啥时候都不让攻破

测信道攻击的种类

  • 能量分析攻击
  • 电磁分析攻击
  • 错误攻击
  • DMA 攻击
  • 冷启动攻击

密文计算算法

一大堆概念

同态加密:同态是群论就有的概念,一个同态映射 f 满足 \(f(x + y) = f(x) + f(y)\) 且没有一一对应要求就是同态,如果一一对应就是 Isomorphism 。在这里 f 就是加密,所以就是加密之后进行运算和加密前进行运算一样,如果支持的是加法就是加法同态,乘法就是乘法同态。

基于属性的加密:就是加密之后,除了需要密钥还需要属性正确才可以进行正确解密

可搜索加密:加密之后可以建立索引进行搜索

秘密分享/秘密分割:加密之后,需要有多个人的密钥一起才能够进行解密

零知识证明:要证明自己有做什么事情的能力,但是又不真的做这个事情,比如要证明我拥有对某个大整数的分解,但是我又不能将这个分解告诉你,所以通过用他解决一些问题来让你知道

承诺:进行一个承诺保证一个值,但是又不让人知道这个值

隐私信息获取:想要从服务器获取一个信息,但是又不想让人知道获取的信息是什么,那么就可以获取一堆信息,其中包含真正的信息

不经意传输:在隐私信息获取的基础上,还不能获取到除了自己想获取的信息以外的别的信息

典型同态加密算法支持的密文计算能力

  • Goldwasser-Micali: 异或同态
  • Paillier: 加法同态
  • ElGamel: 乘法同态
  • EC-ElGamel: 加法同态
  • Boneh-Goh-Nissim: BGN,支持最高二次的多项式运算(加法乘法)