（已完结）应用密码学笔记

简称为“大网安数”。

密码学概述

现代密码学四性：机密性，完整性，鉴别和不可抵赖性。

三个时期为：古典密码（算法保密），近代密码（密钥保密）和现代密码时期。

对密码系统的攻击：唯密文攻击，已知明文攻击，选择明文攻击，选择密文攻击。

Kerckhoffs原则：安全性只取决于密钥的保密，而不是算法。否则是“受限制的密码算法”。

安全性分类：无条件安全性，计算安全性，可证明安全性。

密码算法的功能：加密，杂凑，数字签名，身份鉴别，密钥协商。

私钥用于签名，公钥用于验证。

作业（p14）：

1-1，1-2，1-4，1-6，1-7

古典密码

单表替代密码

Caesar

仿射密码

密钥短语密码

把密钥放在最前面，剩余字母排在密钥后作为替换表。

缺点

词频分析。

多表替代密码

Vigenere

Hill

其中与为列向量，为加密矩阵。

优缺点：

• 对抗唯密文攻击，密钥空间大。
• 易受已知明文攻击与选择明文攻击。

OTP (Vernam)

不能重复使用密钥，理论上不可破译。

playfair

密钥字母去重，放在前面，剩下字母接上，i/j 一起占一个空，排成5*5的矩阵。

对明文两两分组（记为p1 p2），如果：

• 如果在同一行，那么密文就是明文靠右的字母。（最右的右边就是左边第一个）
• 如果在同一列，那么密文就是明文靠下的字母。（同理）
• 如果都不是，那么取另一个对角线作为密文，原文与对应密文的行相同。
• 如果相同（或剩一个），则在中间（右边）插一个约定的字母x。

链式密码算法

利用一个明文加密的结果作为下一个明文加密密钥。

缺点：误码扩散。

置换密码

周期置换

密钥规定了位置的置换。

属于Hill的特例，即属于线性变换的密码。

列置换密码

把明文按行填入矩阵，密钥规定以列读取的顺序。

转轮机密码

不考。

作业：

2.1 2.4 2.5 2.7 2.8 2.10 2.11 2.13 2.14 2.15

分组密码

设计原则

• 扩散原则：明文每一位影响密文尽可能多的位，密文每一位被尽可能多的明文影响。
• 混乱原则：敌手获得明文和密文也无法求出密钥的任意信息。
• 软件设计：使用子块和简单的运算。
• 硬件实现：尽量使用规则的结构。

若 则是幂等密码体制，如仿射密码、置换密码等。

迭代密码体制必须是非幂等的。

典型结构

• SPN结构：扩散更快速，但是加密和解密不相似。
• Feistel结构：加密解密相似，扩散慢一些（至少需要两轮才能改变输入的每一位）。

DES（重点）

• 安全性完全依赖于密钥保密。

• 密钥长度 64 位（8 位用于奇偶校验）

步骤：

• 明文IP置换。
• 的扩展得到：把分成块，每块记为到，然后前面加上前一块的，后面加上后一块的.
• 对加上校验位（8的倍数），通过得到C[0]和D[0]，左移一位得到C[1]和D[1]，通过PC-2得到位.
• 盒变换：不同的块是不同的盒，取 到 作为盒的行，作为盒的列（大端序），查表得到的值作为密钥块。（重点）
• 盒变换。
• 与异或以后得到，便完成了一轮迭代。
• 经过 16 次迭代后再经过一次IP逆置换。

优点：

• 加密解密结构相同。
• 强度高。

互补对称性证明：

对于函数，有

从而轮函数，进而

设为左右块对换，，从而加密函数

改进：三重DES。

分组密码的工作模式

• ECB：每块明文加密成相应的密码块，最后不足64 bit的部分用随机串补全。（本身是一种大的单字母替换）
• CBC（常用）：当前明文块在加密之前要与前面的密文块进行异或，需严格保密初始向量。
• CFB：按比分组小得多的单位进行加密，密文依赖于前面所有明文。
• OFB：在块内部进行反馈。（易受篡改）
• CTR：可并行、预处理，可产生较好的伪随机数序列。

如何选择：

• 安全性
• 高效性
• 功能

AES（重点）

数学基础

有限域 的乘法：略。

x乘：由于 AES 选取的模数为 0x11b，即，当乘数高位为0时，相当于左移；反之相当于左移并异或0x1b.

叉乘：指中两个四次式相乘，模数为。可以通过矩阵乘法简化过程，具体而言，对于多项式与，乘积为：

其中项与项的点乘就是的乘法（使用x乘），加法就是异或。

步骤

密钥128位。

• 字节代换：查表。
• 行移位：第行循环左移字节。
• 列混淆（重点）：对每一列进行叉乘，固定为3112H.
• 轮密钥加：按列与轮密钥进行异或。

总过程：

AddRoundKey()

for i from 1 to 9:
  SubBytes()
  ShiftRows()
  MixColumns()
  AddRoundKey()

SubBytes()
ShiftRows()
MixColumns()

其它对称加密

• IDEA (分组64bit, 密钥长度128bit, 非feistel结构)
• RC6 (分组128bit, 密钥长度128,192,256bit, feistel)
• SM4 (分组128bit，密钥长度128bit, 非对称feistel)

非对称加密

对称的缺点

• 系统开放性差（如何传递密钥）
• 密钥管理困难，个设备有个密钥。
• 数字签名问题。

公钥的特点

• 公钥管理方便，开放性好
• 加解密计算代价较大

公钥的作用

• 常规密钥分发与协商
• 数字签名
• 加密解密（效率较低且不宜直接使用）

RSA

具体过程：略

用CRT实现RSA的快速计算

例：计算，其中，为互异素数，为密钥。

解：分别用欧拉定理计算和的值，然后用CRT计算即可。

Miller-Rabin

费马小定理是模数为素数的必要条件。

二次探测定理：若是奇素数，则的解只有或.

伪代码：

# false rate: 1 - 4^(-s)
def WITNESS(a, n):
  if pow(a, n-1, n) != 1:
    return FALSE
  else while n % 2 == 0:
    n /= 2
    if pow(a, n-1, n) != 1 or -1:
      return FALSE
  return TRUE

for i from 1 to s:
  if WITNESS(integers[i], n) == FALSE
    return NOT_PRIME
return PRIME

ElGamal

description

系统参数：.

选取私钥，公钥为

加密：

• 选取随机数

解密：

feature

• 非确定性的（依赖于k）
• 密文空间大于明文空间

ECC

SM2也使用了椭圆曲线密码体制

实数域上的椭圆曲线

可记为，简称为

若共线，则定义加法单位元，对曲线上任意一点有

易得加法逆元与本身的轴互为相反数

因此可得加法的定义：做过的直线交于，则为，由加法可以类比倍加的定义（此处省略）。可以证明，这种加法满足交换律和结合律。

从代数角度而言，为直线斜率，若重合则

有限域上的椭圆曲线

重点，不考。

可记为，简称为

可以证明，有限域上的椭圆曲线关于运算 + 构成循环群。

加法的定义把对应坐标模 即可，倍加类似。

例：求中点的个数：

答：一共有13个（不要忘了点！）

椭圆曲线上的ElGamal

记为满足的最小整数.

ECDLP: 已知，求的是困难的。

类似于离散对数(DLP)问题，可以把点加类比于模乘，倍加类比于方幂。

系统参数：，基点（其阶为）。

密钥生成：选取私钥，公钥为

加密：

• 将明文消息映射到点
• 选取随机数

解密：

• 对逆映射得到

Menezes-Vanstone

主要解决将明文映射到的问题

系统参数：，基点（其阶为）。

密钥生成：选取私钥，公钥为

加密：

• 选取随机数

解密：

• （注意到，故）
• 由得到

例：设中基点为，密钥，明文为，随机数，计算密文。

解：计算公钥

故密文为

代码实现（晚上写作业时搞的）

# ECC en&decrypt in GF(p)
# 4/24/2023 junyu33
import gmpy2
a = 1
b = 6
p = 11
G = [2, 7]
d_A = 5
def Add(A: list, B: list) -> list:
    lamb = 0
    if A == B:
        lamb = (3*A[0]*A[0]+a)*gmpy2.invert(2*A[1], p) % p
    else:
        lamb = (B[1]-A[1])*gmpy2.invert(B[0]-A[0], p) % p
    s = (lamb**2 - A[0] - B[0]) % p
    t = (lamb*(A[0]-s) - A[1]) % p
    return [s,t]

def Mult(X: list, t: int) -> list:
    R = X
    t = t - 1
    while t:
        if t & 1:
            R = Add(R, X)
        X = Add(X, X)
        t >>= 1
    return R

def enc(M: list, G: list, k: int):
    c_1 = Mult(G, k)
    P_A = Mult(G, d_A)
    Y = Mult(P_A, k)
    c_2 = Y[0] * M[0] % p
    c_3 = Y[1] * M[1] % p
    print(c_1, c_2, c_3)

def dec(c_1: list, c_2: int, c_3: int):
    Y = Mult(c_1, d_A)
    z_1 = Y[0]
    z_2 = Y[1]
    m_1 = c_2 * gmpy2.invert(z_1, p) % p
    m_2 = c_3 * gmpy2.invert(z_2, p) % p
    print(m_1, m_2)

enc([7,9],G,3)

哈希

SHA-1（已被破解）

big-endian

2**64-1 -> 160 bit

steps

• 填充：origin + 1000...000(长度448-len%512) + len
• 初始MD缓存：A=67452301 B=EFCDAB89 C=98BADCFE D=10325476 E=C3D2E1F0
• 以512bit为一组处理信息：A,B,C,D,E←[(A<<5)+ft(B,C,D)+E+Wt+Kt],A,(B<<30),C,D，共80轮循环，这里：
  • 是逻辑函数，分别为(b&c)|(b&d) b^c^d (b&c)|(b&d)|(c&d) b^c^d;
  • 为子明文分组W[t]，每项32位，前16项就是原文512bit的对应，之后的项为(W[t-16]^W[t-14]^W[t-8]^W[t-3])<<1，共80项;
  • 为固定常数（），分别为5A827999 6ED9EBA1 8F1BBCDC CA62C1D6
  • 最开始20轮循环取1，然后20轮取2，以此类推。
• 将原先的A,B,C,D,E与最后得到的A',B',C',D',E'相加得到新一轮的缓存，处理完所有明文后得到的缓存就是SHA-1值。

生日攻击

如果消息空间的大小为，那么大概随机选择个消息，就有一半的概率产生碰撞。

SM3

国内商用密码 Hash 函数。

分组 512 bit，输出 256 bit。

智能电表，TPM2.0

消息鉴别

消息鉴别码（Message Authentication Code, MAC）的分类：

• 加密技术
• 散列函数
• HMAC算法（带密钥的单向散列函数）

数字签名

RSA

发送者使用进行签名。

接收者使用进行验证。

ElGamal

初始化：

签名变换：

• 选取随机数，与互素
• 签名：
  • ，其中为单向散列函数。
  • 发送
• 验证：
  • 计算
  • 计算与，若相等则签名有效。

注意不能被泄露，加密部分同理。

DSA

公开，是的素因子，

随机选取作为私钥，公钥

签名变换：

• 签名：
  • 选取
  • 发送
• 验证：
  • ，若则签名成功。

ECDSA

为系统参数。

随机选取作为私钥，作为公钥。

• 签名：
  • 选择随机数
  • 发送
• 验证：
  • ，若则接受签名。

特殊签名

• 不可否认签名
• 盲数字签名
• 群签名

密钥管理技术

Diffie-Hellman (非对称，只能用于两个用户的密钥交换)

系统参数：

• Alice 选取不公开的，计算
• Bob 选取不公开的，计算
• 双方交换，
• Alice 计算
• Bob 计算

显然以上两个值相等，密钥协商完成。

易受中间人攻击。

Shamir 门限方案

系统参数：

秘密：

因此可构造出秘密多项式：

密钥分发者根据每个人的密钥计算出的值，各自分发给他们。

由拉格朗日插值，只有任意取个人才能还原出秘密多项式（重构），过程如下：

特别的，当时，可以计算出秘密的值：

不足：

• 门限值固定
• 秘密分发者知道参与者的shadow
• 不能防止秘密分发者和参与者的欺诈

身份鉴别技术

概念，威胁，攻击手段

质询——响应身份鉴别：

• 额外通信代价
• 只能防止声称者的重放，不能防止验证者的重放攻击：双向鉴别、时间戳。

S/Key OTP 身份鉴别：

• 可防止重放攻击
• 不能防止小数攻击（截取服务器的种子和迭代值，修改较小迭代值发给用户，截获用户口令，计算较大迭代值）
• 缺乏完整性保护机制

零知识证明协议

设，假设 Alice 知道 的因子，如果 Alice 想告诉 Bob 她知道但不具体告诉 Bob 因子是什么，可以执行以下步骤：

• Bob 随机选取，计算，并将 告诉 Alice
• Alice 计算 ，并将 告诉 Bob
• Bob 验证 是否成立。
• 重复多次都能成功就代表 Alice 确实知道 的因子

理论基础是计算 的难度等价于对 进行因式分解。

kerberos 身份鉴别

采用对称密钥体制，由可信第三方提供鉴别服务。

通过票据（ticket）给通信双方分发共享密钥。

安全通信

伪代码：

发送方：

# send.py
# Example usage:
with open("public_key_B.pem", "rb") as f:
  public_key_B = RSA.import_key(f.read())

with open('data', 'rb') as f:
  data = f.read()

# Party A encrypts the data and signs it
ciphertext = encrypt(data, key)
signature = sign(data, private_key_A)

# Party A encrypts the key using the public key of party B
encrypted_key = encrypt_key(key, public_key_B)

with open('encrypted_key', 'wb') as f:
  f.write(encrypted_key)

with open('ciphertext', 'wb') as f:
  f.write(ciphertext)

with open('signature', 'wb') as f:
  f.write(signature)

with open('public_key_A.pem', 'wb') as f:
  f.write(public_key_A.export_key('PEM'))

接收方

# receive.py
with open('public_key_A.pem', 'rb') as f:
  public_key_A = RSA.import_key(f.read())
with open('encrypted_key', 'rb') as f:
  encrypted_key = f.read()

with open('signature', 'rb') as f:
  signature = f.read()

with open('ciphertext', 'rb') as f:
  ciphertext = f.read()

# Party B decrypts the key and uses it to decrypt the data
key = decrypt_key(encrypted_key, private_key_B)
decrypted_data = decrypt(ciphertext, key)
with open('decrypted_data', 'wb') as f:
  f.write(decrypted_data)

# Party B verifies the signature of party A
is_valid = verify_signature(decrypted_data, signature, public_key_A)

if is_valid:
  print("The signature is valid")
else:
  print("The signature is not valid")

序列密码基础

又称流密码，属于对称密码体制，适合硬件实现。

分类

• 同步序列密码：记忆元件状态独立于明文或密文，无错误传播，有同步要求。
• 自同步序列密码：密钥流的产生与密文有关，有限错误传播，自同步。

LFSR

注意是高位移向低位，就是输出，的值为下一个.

性质完全由反馈函数决定。级LFSR周期.

基于LFSR的序列密码生成器有：

• Geffe生成器
• 钟控生成器
• 交错停走式生成器

RC4

两个算法：密钥调度算法KSA、伪随机数生成算法PRGA。