现代密码学常用符号总结

本文将总结现代密码学 (Modern Cryptography) 中的常见数学符号, 了解以下预备知识可以极大增加本文的阅读体验:

离散数学, 线性代数与概率论三门课程中的主要数学记号及其含义 ?

现代密码学是一门什么样的学科 ?

LaTeX \LaTeX LATE​X的基本用法与常见数学符号命令有哪些 ?

在阅读密码学相关的论文时会遇到各类符号, 即使有的论文命名法和符号风格不同, 但在符号使用规律上基本都保持一致. 因此, 本文将持续性地总结记录现代密码学中的常见符号和表示法, 方便查阅参考, 并还会结合

LaTeX

\LaTeX

LATE​X相关命令给出示例和一些实用技巧.

符号风格

密码学中涉及符号的风格与使用规范遵循一般的数学公式表示规范, 而这些规定通常是约定俗成的. 具体而言有:

斜体表示: 如 x , m , n x,m,n x,m,n, X , Y , Z X, Y, Z X,Y,Z等斜体形式通常用于表示变量 (variable), 如第 i i i个正整数是 n n n; 如果遇到斜体加粗, 则一般表示的是某个随机变量或随机样本.

正体表示: 如 X , Y \mathsf{X},\mathsf{Y} X,Y等正体形式通常用于表示矩阵或某种变换 (transform).

花体表示: E \mathcal{E} E, X \mathcal{X} X等花体形式通常表示集合概念, 因此有时会有 x ∈ X x\in \mathcal{X} x∈X.

空心表示: R \mathbb{R} R, Q \mathbb{Q} Q等空心形式通常表示空间, 域等, 这些符号表示的范围通常是比花体和正体表示都要大的.

LaTeX \LaTeX LATE​X特殊字体: 在实际的论文写作中，某些特殊符号或者术语样式需要用到 LaTeX \LaTeX LATE​X中的各类字体样式命令，常见命令如 ```\textit```, ```\textsf```, ```\texttt```, ```\mathsf```等。 更多信息可以参阅刘海洋老师的《LaTeX入门》第二章.

在了解上述常见符号风格后, 即使在论文中遇到没见过而且作者似乎也没解释的记号, 也可以通过记号的书写风格来结合上下文推测这一记号的大致特点.

主要符号总结

下面我们将从三个方面总结现代密码学中的主要符号, 首先就是最基础也是最常见的各种运算符了.

运算符

二元运算符

名称符号含义

LaTeX

\LaTeX

LATE​X命令使用情景异或

⊕

\oplus

⊕01串 (或两数) 之间的异或操作

\oplus

One Time Pad连接

∣

∣

||

∣∣顺序连接两个串

||

将两个串拼接后输入一个算法组合作用

∘

\circ

∘两个函数作用的"组合"

\circ

密码理论分析, 白盒密码， 同态代数运算

⋅

\cdot

⋅,

+

+

+(模) 乘, (模) 加

\cdot, +

代数运算, RSA等公钥密码算法移位

<

<

,

>

>

<<,>>

<<,>>将一个数的二进制向左或向右移动若干位

<<,>>

各类算法(如MD5, SM4)的底层运算

概率与取样

在现代密码学涉及的基础知识中, 概率论是很重要的一环. 在密码算法的可证明安全中, 概率论与随机过程的相关知识更是充当了核心角色. 因此,虽然有些符号并非运算符, 但为了方便也将在本处一并进行介绍.名称符号含义

LaTeX

\LaTeX

LATE​X命令使用情景采样

←

\leftarrow

←从某一集合中采样出某个样本

\leftarrow

生成某一元素进行后续操作随机采样

←

$

\stackrel{\$}{\leftarrow}

←$从某一集合中随机采样出某个样本

\stackrel{\$}{\leftarrow}

生成随机数概率

P

r

\mathrm{Pr}

Pr计算某一事件的概率

\mathrm{Pr}

衡量可证明安全中的各类事件发生的概率集合

{

⋯

}

\left\{\cdots\right\}

{⋯}离散数学中集合的概念

\left\{\cdots\right\}

各类密码算法与协议概率分布

∼

\sim

∼变量服从概率分布

\sim

基于格的算法与困难问题中的变量分布特征可忽略概率

ϵ

\epsilon

ϵ在安全参数

λ

\lambda

λ的多项式级别下的极小量

\varepsilon

可证明安全的敌手优势说明期望

E

E

E计算某一随机变量或者分布的数学期望

E

基于格的算法证明中的相关计算当然, 在数学中还有很多其他常见的二元运算符 (例如线性代数, 抽象代数中的一大堆记号), 此处我们只介绍密码学中常用的符号及其在密码学中的用途. 如其他需要补充说明, 欢迎分享你的建议 !

常用记号

除了常用的运算符外, 在阅读各类密码学的论文时, 最令人头疼的想必是各类繁杂的数学记号了. 但好在各个记号在不同论文中的写法基本都是统一的, 只是花样众多, 令人眼烦, 我们通常只需要在第一次遇见的时候记住就可以了.

算法记号

对称密码算法

名称符号含义

LaTeX

\LaTeX

LATE​X命令使用情景密钥

K

K

K对称密码算法的密钥

K

对称密码算法中双方共享一密钥密钥生成

G

e

n

(

1

λ

)

\mathrm{Gen}(1^{\lambda})

Gen(1λ)根据安全参数

λ

\lambda

λ生成算法密钥

\mathrm{Gen}(1^{\lambda})

许多对称密码算法的第一步加密

E

n

c

\mathsf{Enc}

Enc将明文加密为密文

\mathsf{Enc}

对称加密算法的主要步骤解密

D

e

c

\mathsf{Dec}

Dec将密文解密为明文

\mathsf{Dec}

对称加密算法的主要步骤消息认证码生成

M

a

c

\mathsf{Mac}

Mac根据对称密钥生成某条消息对应的消息认证码

\mathsf{Mac}

HMAC等MAC算法消息认证码验证

V

r

f

y

\mathsf{Vrfy}

Vrfy根据对称密钥验证某个消息认证码是否正确

\mathsf{Vrfy}

HMAC等MAC算法

公钥密码算法

名称符号含义

LaTeX

\LaTeX

LATE​X命令使用情景公钥

P

k

\mathsf{Pk}

Pk可公开的密钥

\mathsf{Pk}

公钥算法, PKI等私钥

S

k

\mathsf{Sk}

Sk与公钥对应的需要秘密保存的私钥

\mathsf{Sk}

公钥算法密钥生成

G

e

n

(

1

λ

)

\mathsf{Gen}(1^{\lambda})

Gen(1λ)根据安全参数

λ

\lambda

λ生成一对公私钥

\mathsf{Gen}(1^{\lambda})

公钥算法公钥加密

E

n

c

(

P

k

,

⋅

)

\mathsf{Enc}(\mathsf{Pk}, \cdot)

Enc(Pk,⋅)计算某一事件的概率

\mathrm{Pr}

加密只有私钥拥有方才能解密的信息私钥解密

D

e

c

(

S

k

,

⋅

)

\mathsf{Dec}(\mathsf{Sk}, \cdot)

Dec(Sk,⋅)离散数学中集合的概念

\left\{\cdots\right\}

略私钥签名

S

i

g

n

(

S

k

,

⋅

)

\mathsf{Sign}(\mathsf{Sk}, \cdot)

Sign(Sk,⋅)在安全参数

λ

\lambda

λ的多项式级别下的极小量

\varepsilon

可证明安全的敌手优势说明公钥验签

V

r

f

y

(

P

k

,

⋅

)

\mathsf{Vrfy}(\mathsf{Pk}, \cdot)

Vrfy(Pk,⋅)在安全参数

λ

\lambda

λ的多项式级别下的极小量

\varepsilon

略采样函数

S

a

m

p

\mathsf{Samp}

Samp均匀选取集合中的元素

\mathsf{Samp}

单向置换逆置换

I

n

v

\mathsf{Inv}

Inv拥有陷门信息后的高效逆置换算法

\mathsf{Inv}

基于陷门置换的公钥加密值得一提的是, 公钥算法发展至今有很多种类, 也有很多高阶方案, 如门限加密, 秘密共享, 同态加密, 可搜索加密和函数加密等等. 不同的高阶方案也衍生出了各自的算法符号范式, 诸如

T

r

a

p

\mathsf{Trap}

Trap,

I

n

d

e

x

\mathsf{Index}

Index等等. 由于这些零散记号和方案本身的特点紧密相关, 并非是公钥方案的共性操作. 故此处就不作进一步介绍.

密码学哈希

名称符号含义

LaTeX

\LaTeX

LATE​X命令使用情景计算哈希摘要

H

H

H从某一集合中采样出某个样本

\leftarrow

生成某一元素进行后续操作带密钥的哈希

H

(

K

,

⋅

)

H(K, \cdot)

H(K,⋅),

H

K

(

⋅

)

H_{K}(\cdot)

HK​(⋅)从某一集合中随机采样出某个样本

H(K, \cdot), H_{K}(\cdot)

HMAC

模糊提取器

名称符号含义

LaTeX

\LaTeX

LATE​X命令初始化

i

n

i

t

(

1

λ

)

\mathsf{init}(1^{\lambda})

init(1λ)生成公开模糊提取器的公开参数

p

p

\mathsf{pp}

pp

\mathsf{init}(1^{\lambda})

生成字符串

G

e

n

(

p

p

,

w

;

r

)

\mathsf{Gen}(\mathsf{pp,w;r})

Gen(pp,w;r)根据

p

p

\mathsf{pp}

pp,元素

w

\mathsf{w}

w与随机性

r

\mathsf{r}

r生成字符串

R

R

R与公开的帮助字符串

P

P

P

\mathsf{Gen}(\mathsf{pp,w;r})

提取字符串

R

e

p

(

p

p

,

w

′

;

P

)

\mathsf{Rep}(\mathsf{pp,w\prime;}P)

Rep(pp,w′;P)根据

p

p

\mathsf{pp}

pp,相近元素

w

′

\mathsf{w\prime}

w′与帮助字符串

P

P

P还原字符串

R

R

R

\mathsf{Rep}(\mathsf{pp,w\prime;}P)

哈希证明系统

一般的哈希证明系统通常是一个非交互的零知识系统, 此处主要指的是Smooth Projective Hash Proof System (SPHFs)名称符号含义

LaTeX

\LaTeX

LATE​X命令生成哈希密钥

H

a

s

h

K

G

(

p

p

)

\mathsf{HashKG}(\mathsf{pp})

HashKG(pp)根据语言系统的参数

p

p

\mathsf{pp}

pp生成哈希密钥

h

k

hk

hk

\mathsf{HashKG}(\mathsf{pp})

派生投影密钥

P

r

o

j

K

G

(

h

k

,

p

p

,

x

)

\mathsf{ProjKG}(hk,\mathsf{pp},x)

ProjKG(hk,pp,x)根据语言

x

x

x,

p

p

\mathsf{pp}

pp与哈希密钥

h

k

hk

hk派生出投影密钥

h

p

hp

hp

\mathsf{ProjKG}(hk,\mathsf{pp},x)

计算哈希

H

a

s

h

(

h

k

,

p

p

,

x

)

\mathsf{Hash}(hk,\mathsf{pp},x)

Hash(hk,pp,x)根据语言

x

x

x,

p

p

\mathsf{pp}

pp与哈希密钥

h

k

hk

hk计算哈希值

H

H

H

\mathsf{Hash}(hk,\mathsf{pp},x)

计算投影哈希

P

r

o

j

H

a

s

h

(

h

p

,

p

p

,

x

,

w

)

\mathsf{ProjHash}(hp,\mathsf{pp},x,w)

ProjHash(hp,pp,x,w)根据语言

x

x

x,

p

p

\mathsf{pp}

pp与派生密钥

h

p

hp

hp和一个证据

w

w

w计算出投影哈希值

p

H

pH

pH

\mathsf{ProjHash}(hp,\mathsf{pp},x,w)

可证明安全记号

名称符号含义

LaTeX

\LaTeX

LATE​X命令使用情景敌手

A

\mathcal{A}

A可证明安全中试图解决攻破方案的假想攻击者

\mathcal{A}

A

\mathcal{A}

A 尝试攻破加密算法的不可区分性挑战者

C

\mathcal{C}

C可证明安全中试图解决困难问题的挑战者

\mathcal{C}

C

\mathcal{C}

C 尝试解决大整数分解问题Oracle

O

\mathcal{O}

O经抽象后的证明过程中可被查询的预言机

\mathcal{O}

算法的加解密部分被抽象为了

O

\mathcal{O}

O供

A

\mathcal{A}

A或

C

\mathcal{C}

C提交明密文查询标志

b

a

d

\mathsf{bad}

bad用来指示证明过程中某些事件的发生

\mathsf{bad}

当加密得到的密文产生了碰撞时, 是一个

b

a

d

\mathsf{bad}

bad事件证明游戏

G

a

m

e

\mathsf{Game}

Game为安全性证明定义的挑战者与敌手的交互模型

\mathsf{Game}

定义

A

\mathcal{A}

A与

O

\mathcal{O}

O的若干次选择明文查询是一个

G

a

m

e

\mathsf{Game}

Game

其他常用符号

在密码算法中还有一些常用的符号, 如对字符串数据的一些操作. 如有其他常用符号也欢迎大家补充.名称符号含义

LaTeX

\LaTeX

LATE​X命令使用情景字符串长度

∣

s

∣

|s|

∣s∣得到字符串

s

s

s的长度

\left|s\right|

密码算法输入全0字符串

0

n

0^{n}

0n

n

n

n-bit 长的全0字符串

0^{n}

略全1字符串

1

n

1^{n}

1n

n

n

n-bit 长的全1字符串

1^{n}

略字符串分块

∣

∣

s

∣

∣

l

||s||_{l}

∣∣s∣∣l​将字符串

s

s

s分为

l

l

l块, 每块长度为

⌈

∣

s

∣

l

⌉

\lceil \frac{|s|}{l} \rceil

⌈l∣s∣​⌉ bit

||s||_{l}

对分组算法中的每一块进行加解密

量子密码算法符号

在量子密码算法中会涉及很多量子力学的操作与符号, 而这些符号其实都遵循着狄拉克记号法, 也就是所谓的Bra-ket notation. 不过在我们第一次遇到量子密码算法时, 看到这些符号依然会头大, 下面初步总结了一些常用记号方便检索.

注意, 量子密码算法都是在一个或若干个希尔伯特空间 (

H

\mathcal{H}

H) 中的, 此时算法的状态会被抽象为一个

H

\mathcal{H}

H中的状态矢量

ψ

\psi

ψ, 因此这部分的操作与符号有些和线性代数也是通用的.

名称符号含义

LaTeX

\LaTeX

LATE​X命令右矢

∣

ψ

⟩

|\psi \rangle

∣ψ⟩可理解为线性空间中的某个向量

| \psi \rangle

左矢

⟨

ψ

∣

\langle \psi |

⟨ψ∣某个右矢对应的共轭矢量

\langle \psi |

矢量间的内积

⟨

a

∣

b

⟩

\langle a | b \rangle

⟨a∣b⟩两矢量间进行内积运算

\langle a | b \rangle

矢量间的外积

∣

a

⟩

⟨

b

∣

|a\rangle \langle b |

∣a⟩⟨b∣两矢量间进行外积运算

|a\rangle \langle b |

张量积

⊗

\otimes

⊗希尔伯特空间的张量积, 如

H

1

⊗

H

2

\mathcal{H_{1}}\otimes \mathcal{H_{2}}

H1​⊗H2​形成一个组合系统

\otimes

共轭转置

U

†

U^{\dag}

U†矩阵的共轭转置, 被用来描述

H

\mathcal{H}

H上的幺正变换

U^{\dag}

概率坍缩

∣

⟨

a

∣

ψ

⟩

∣

2

|\langle a | \psi \rangle|^{2}

∣⟨a∣ψ⟩∣2经过某一量子系统变换后, 从叠加态

ψ

\psi

ψ观测到状态

a

a

a的概率

|\langle a | \psi \rangle|^{2}

状态叠加

∑

∣

a

i

⟩

\sum |a_{i}\rangle

∑∣ai​⟩将若干个状态

∣

a

i

⟩

|a_{i}\rangle

∣ai​⟩进行叠加得到叠加态

\sum |a_{i}\rangle

量子Oracle变换

O

∣

x

⟩

\mathbf{O}|x\rangle

O∣x⟩在量子Oracle中对矢量

∣

x

⟩

|x\rangle

∣x⟩进行变换得到

∣

x

+

O

(

x

)

⟩

|x+O(x)\rangle

∣x+O(x)⟩

\mathbf{O}|x\rangle

由于我对量子力学的相关概念也不是非常熟悉, 上述记号如有错误欢迎大家指出, 也欢迎大家补充其他常见的量子密码方案记号.

LaTeX宏包 cryptocode 的使用

cryptocode是一个专门为了密码学研究者提供的

LaTeX

\LaTeX

LATE​X宏包, 而且这一宏包已经默认加入了texlive2022中, 使用时无需额外安装, 只需要

\usepackage[your_options]{cryptocode}

就能引入. 而且这个宏包的文档非常全面, 基本可以做到即查即用. 这里就拾人牙慧, 简单介绍几个最常用的命令.

常用符号

上文提到的很多运算符号, 其实已经都在cryptocode中封装好了, 尤其是一些呈现方式简单, 但

LaTeX

\LaTeX

LATE​X命令复杂的运算, 可以用cryptocode提供的更容易记忆和使用的短命令.

名称cryptocode命令等价

LaTeX

\LaTeX

LATE​X命令随机采样

\sample

\leftarrow

标志

\bad

\mathsf{bad}

0-1集合

\bin

\left\{0, 1\right\}

概率

\prob

\mathsf{Pr}

敌手优势

\advantage

\mathsf{Adv}

密钥生成

\kgen

\mathsf{KGen}

上述这些符号只是cryptocode封装的很小一部分, 官方说明文档中会有更多描述.

算法

在密码学论文中, 除了那些常见符号外, 还会需要用

LaTeX

\LaTeX

LATE​X的

algorithm

环境呈现算法方案. 而在cryptocode中则可以直接用

procedureblock

, 效果如下图所示.

而对应的

LaTeX

\LaTeX

LATE​X代码也更为简洁, 无需像原来

algorithm

包那样写过多不必要的关键字.

\procedureblock {$\indcpa_\enc^\adv(\secpar)$}{

b \sample \ bin \\

(\pk, \sk) \sample \kgen(\secparam) \\

(m_0, m_1) \sample \adv(\secparam ,\pk, c)\\

c \sample \enc(\pk ,m_b)\\

b' \sample \adv(\secparam, \pk, c)\\

\pcreturn b = b’

}

Game-based 安全证明

一篇理论密码方案论文的核心就是它的安全性证明了, 而在写一些game-based proof 时, 我们常常需要借助

b

a

d

\mathsf{bad}

bad 等符号标注出一个game里有利于敌手的那些事件. 要表达这样一件事, 一般需借助

table

环境以及一些文本样式命令. 然而, cryptocode也提供了这方面的封装, 如下图所示.

此外, 除了最基本的这种game-based proof外, 它还提供了game hopping, reduction等的命令封装, 这能极大地减少密码学研究者在撰写论文时的麻烦.

密码协议

在密码学中还有很多协议（Protocol）相关的工作，而对于我个人而言，通过drawio等工具画协议图还是有些繁琐了，而且如果数学公式较多的话在校对和排版上都存在着不少缺陷; 而原生tikz的作图效果很漂亮，但学习和使用成本太高。

而在cryptocode中，可以同样使用

procedureblock

命令与缩进指令 (tabbing)

\>

方便地通呈现一个密码协议，如下图所示。

总结

本文总结了传统密码学与量子密码方案中的常见记号与对应的

LaTeX

\LaTeX

LATE​X代码, 以缓解记忆密码学论文中繁琐符号含义所带来的烦躁心情🤡. 本文内容也将会动态更新, 在后续的学习过程中会不断添加新遇到的各类记号, 也欢迎大家分享和指正. 文章所在的专栏 包括了其他密码学相关的文章, 欢迎阅读并给出意见! 最后以一句歌词作为结束.

“你让任务如期完成并划下记号, 现在或悠悠闲闲带爱子散步” ——李克勤《再见穿梭机》