现代密码学的标志是什么?_密码学考试题库

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

离散数学, 线性代数与概率论三门课程中的主要数学记号及其含义 ?
现代密码学是一门什么样的学科 ?
$\LaTeX$ 的基本用法与常见数学符号命令有哪些 ?

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

符号风格

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

斜体表示: 如 $x, m, n$ , $X, Y, Z$ 等斜体形式通常用于表示变量 (variable), 如第 $i$ 个正整数是 $n$ ; 如果遇到斜体加粗, 则一般表示的是某个随机变量或随机样本.
正体表示: 如 $\mathsf{X},\mathsf{Y}$ 等正体形式通常用于表示矩阵或某种变换 (transform).
花体表示: $\mathcal{E}$ , $\mathcal{X}$ 等花体形式通常表示集合概念, 因此有时会有 $x\in \mathcal{X}$ .
空心表示: $\mathbb{R}$ , $\mathbb{Q}$ 等空心形式通常表示空间, 域等, 这些符号表示的范围通常是比花体和正体表示都要大的.
$\LaTeX$ 特殊字体: 在实际的论文写作中，某些特殊符号或者术语样式需要用到 $\LaTeX$ 中的各类字体样式命令，常见命令如 \textit, \textsf, \texttt, \mathsf等。更多信息可以参阅刘海洋老师的《LaTeX入门》第二章.

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

主要符号总结

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

运算符

二运算符

名称	符号	含义	$\LaTeX$ 命令	使用情景
异或	$\oplus$	01串 (或两数) 之间的异或操作	`\oplus`	One Time Pad
连接	$∣∣$	顺序连接两个串	`\|\|`	将两个串拼接后输入一个算法
组合作用	$\circ$	两个函数作用的”组合”	`\circ`	密码理论分析, 白盒密码，同态
代数运算	$\cdot$ , $+$	(模) 乘, (模) 加	`\cdot, +`	代数运算, RSA等公钥密码算法
移位	$<<, >>$	将一个数的二进制向左或向右移动若干位	`<<,>>`	各类算法(如MD5, SM4)的底层运算

概率与取样

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

名称	符号	含义	$\LaTeX$ 命令	使用情景
采样	$\leftarrow$	从某一集合中采样出某个样本	`\leftarrow`	生成某一素进行后续操作
随机采样	$\stackrel{\$}{\leftarrow}$	从某一集合中随机采样出某个样本	`\stackrel{\$}{\leftarrow}`	生成随机数
概率	$\mathrm{Pr}$	计算某一事件的概率	`\mathrm{Pr}`	衡量可证明安全中的各类事件发生的概率
集合	$\left\{\cdots\right\}$	离散数学中集合的概念	`\left\{\cdots\right\}`	各类密码算法与协议
概率分布	$\sim$	变量服从概率分布	`\sim`	基于格的算法与困难问题中的变量分布特征
可忽略概率	$\epsilon$	在安全参数 $\lambda$ 的多项式级别下的极小量	`\varepsilon`	可证明安全的敌手优势说明
期望	$E$	计算某一随机变量或者分布的数学期望	`E`	基于格的算法证明中的相关计算

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

常用记号

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

算法记号

对称密码算法

名称	符号	含义	$\LaTeX$ 命令	使用情景
密钥	$K$	对称密码算法的密钥	`K`	对称密码算法中双方共享一密钥
密钥生成	$\mathrm{Gen}(1^{\lambda})$	根据安全参数 $\lambda$ 生成算法密钥	`\mathrm{Gen}(1^{\lambda})`	许多对称密码算法的第一步
加密	$\mathsf{Enc}$	将明文加密为密文	`\mathsf{Enc}`	对称加密算法的主要步骤
解密	$\mathsf{Dec}$	将密文解密为明文	`\mathsf{Dec}`	对称加密算法的主要步骤
消息认证码生成	$\mathsf{Mac}$	根据对称密钥生成某条消息对应的消息认证码	`\mathsf{Mac}`	HMAC等MAC算法
消息认证码验证	$\mathsf{Vrfy}$	根据对称密钥验证某个消息认证码是否正确	`\mathsf{Vrfy}`	HMAC等MAC算法

公钥密码算法

名称	符号	含义	$\LaTeX$ 命令	使用情景
公钥	$\mathsf{Pk}$	可公开的密钥	`\mathsf{Pk}`	公钥算法, PKI等
私钥	$\mathsf{Sk}$	与公钥对应的需要秘密保存的私钥	`\mathsf{Sk}`	公钥算法
密钥生成	$\mathsf{Gen}(1^{\lambda})$	根据安全参数 $\lambda$ 生成一对公私钥	`\mathsf{Gen}(1^{\lambda})`	公钥算法
公钥加密	$\mathsf{Enc}(\mathsf{Pk}, \cdot)$	计算某一事件的概率	`\mathrm{Pr}`	加密只有私钥拥有方才能解密的信息
私钥解密	$\mathsf{Dec}(\mathsf{Sk}, \cdot)$	离散数学中集合的概念	`\left\{\cdots\right\}`	略
私钥签名	$\mathsf{Sign}(\mathsf{Sk}, \cdot)$	在安全参数 $\lambda$ 的多项式级别下的极小量	`\varepsilon`	可证明安全的敌手优势说明
公钥验签	$\mathsf{Vrfy}(\mathsf{Pk}, \cdot)$	在安全参数 $\lambda$ 的多项式级别下的极小量	`\varepsilon`	略
采样函数	$\mathsf{Samp}$	均匀选取集合中的素	`\mathsf{Samp}`	单向置换
逆置换	$\mathsf{Inv}$	拥有陷门信息后的高效逆置换算法	`\mathsf{Inv}`	基于陷门置换的公钥加密

值得一提的是, 公钥算法发展至今有很多种类, 也有很多高阶方案, 如门限加密, 秘密共享, 同态加密, 可搜索加密和函数加密等等. 不同的高阶方案也衍生出了各自的算法符号范式, 诸如 $\mathsf{Trap}$ , $\mathsf{Index}$ 等等. 由于这些零散记号和方案本身的特点紧密相关, 并非是公钥方案的共性操作. 故此处就不作进一步介绍.

密码学哈希

名称	符号	含义	$\LaTeX$ 命令	使用情景
计算哈希摘要	$H$	从某一集合中采样出某个样本	`\leftarrow`	生成某一素进行后续操作
带密钥的哈希	$\cdot)$ , $H_{K}(\cdot)$	从某一集合中随机采样出某个样本	`H(K, \cdot), H_{K}(\cdot)`	HMAC

模糊提取器

名称	符号	含义	$\LaTeX$ 命令
初始化	$\mathsf{init}(1^{\lambda})$	生成公开模糊提取器的公开参数 $\mathsf{pp}$	`\mathsf{init}(1^{\lambda})`
生成字符串	$\mathsf{Gen}(\mathsf{pp,w;r})$	根据 $\mathsf{pp}$ ,素 $\mathsf{w}$ 与随机性 $\mathsf{r}$ 生成字符串 $R$ 与公开的帮助字符串 $P$	`\mathsf{Gen}(\mathsf{pp,w;r})`
提取字符串	$\mathsf{Rep}(\mathsf{pp,w\prime;}P)$	根据 $\mathsf{pp}$ ,相近素 $\mathsf{w\prime}$ 与帮助字符串 $P$ 还原字符串 $R$	`\mathsf{Rep}(\mathsf{pp,w\prime;}P)`

哈希证明系统

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

名称	符号	含义	$\LaTeX$ 命令
生成哈希密钥	$\mathsf{HashKG}(\mathsf{pp})$	根据语言系统的参数 $\mathsf{pp}$ 生成哈希密钥 $hk$	`\mathsf{HashKG}(\mathsf{pp})`
派生投影密钥	$\mathsf{ProjKG}(hk,\mathsf{pp},x)$	根据语言 $x$ , $\mathsf{pp}$ 与哈希密钥 $hk$ 派生出投影密钥 $h p$	`\mathsf{ProjKG}(hk,\mathsf{pp},x)`
计算哈希	$\mathsf{Hash}(hk,\mathsf{pp},x)$	根据语言 $x$ , $\mathsf{pp}$ 与哈希密钥 $hk$ 计算哈希值 $H$	`\mathsf{Hash}(hk,\mathsf{pp},x)`
计算投影哈希	$\mathsf{ProjHash}(hp,\mathsf{pp},x,w)$	根据语言 $x$ , $\mathsf{pp}$ 与派生密钥 $h p$ 和一个证据 $w$ 计算出投影哈希值 $p H$	`\mathsf{ProjHash}(hp,\mathsf{pp},x,w)`

可证明安全记号

名称	符号	含义	$\LaTeX$ 命令	使用情景
敌手	$\mathcal{A}$	可证明安全中试图解决攻破方案的假想攻击者	`\mathcal{A}`	$\mathcal{A}$ 尝试攻破加密算法的不可区分性
挑战者	$\mathcal{C}$	可证明安全中试图解决困难问题的挑战者	`\mathcal{C}`	$\mathcal{C}$ 尝试解决大整数分解问题
Oracle	$\mathcal{O}$	经抽象后的证明过程中可被查询的预言机	`\mathcal{O}`	算法的加解密部分被抽象为了 $\mathcal{O}$ 供 $\mathcal{A}$ 或 $\mathcal{C}$ 提交明密文查询
标志	$\mathsf{bad}$	用来指示证明过程中某些事件的发生	`\mathsf{bad}`	当加密得到的密文产生了碰撞时, 是一个 $\mathsf{bad}$ 事件
证明游戏	$\mathsf{Game}$	为安全性证明定义的挑战者与敌手的交互模型	`\mathsf{Game}`	定义 $\mathcal{A}$ 与 $\mathcal{O}$ 的若干次选择明文查询是一个 $\mathsf{Game}$

其他常用符号

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

名称	符号	含义	$\LaTeX$ 命令	使用情景
字符串长度	$∣ s ∣$	得到字符串 $s$ 的长度	`\left\|s\right\|`	密码算法输入
全0字符串	$0^{n}$	$n$ -bit 长的全0字符串	`0^{n}`	略
全1字符串	$1^{n}$	$n$ -bit 长的全1字符串	`1^{n}`	略
字符串分块	$s\|\|_{l}$	将字符串 $s$ 分为 $l$ 块, 每块长度为 $\lceil \frac{\|s\|}{l} \rceil$ bit	`\|\|s\|\|_{l}`	对分组算法中的每一块进行加解密

量子密码算法符号

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

注意, 量子密码算法都是在一个或若干个希尔伯特空间 ( $\mathcal{H}$ ) 中的, 此时算法的状态会被抽象为一个 $\mathcal{H}$ 中的状态矢量 $\psi$ , 因此这部分的操作与符号有些和线性代数也是通用的.

名称	符号	含义	$\LaTeX$ 命令
右矢	$\|\psi \rangle$	可理解为线性空间中的某个向量	`\| \psi \rangle`
左矢	$\langle \psi \|$	某个右矢对应的共轭矢量	`\langle \psi \|`
矢量间的内积	$\langle a \| b \rangle$	两矢量间进行内积运算	`\langle a \| b \rangle`
矢量间的外积	$\|a\rangle \langle b \|$	两矢量间进行外积运算	`\|a\rangle \langle b \|`
张量积	$\otimes$	希尔伯特空间的张量积, 如 $\mathcal{H_{1}}\otimes \mathcal{H_{2}}$ 形成一个组合系统	`\otimes`
共轭转置	$U^{\dag}$	矩阵的共轭转置, 被用来描述 $\mathcal{H}$ 上的幺正变换	`U^{\dag}`
概率坍缩	$\|\langle a \| \psi \rangle\|^{2}$	经过某一量子系统变换后, 从叠加态 $\psi$ 观测到状态 $a$ 的概率	`\|\langle a \| \psi \rangle\|^{2}`
状态叠加	$\sum \|a_{i}\rangle$	将若干个状态 $\|a_{i}\rangle$ 进行叠加得到叠加态	`\sum \|a_{i}\rangle`
量子Oracle变换	$\mathbf{O}\|x\rangle$	在量子Oracle中对矢量 $\|x\rangle$ 进行变换得到 $\|x+O(x)\rangle$	`\mathbf{O}\|x\rangle`

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

LaTeX宏包 cryptocode 的使用

cryptocode是一个专门为了密码学研究者提供的 $\LaTeX$ 宏包, 而且这一宏包已经默认加入了texlive2022中, 使用时无需额外安装, 只需要\usepackage[your_options]{cryptocode}就能引入. 而且这个宏包的文档非常全面, 基本可以做到即查即用. 这里就拾人牙慧, 简单介绍几个最常用的命令.

常用符号

上文提到的很多运算符号, 其实已经都在cryptocode中封装好了, 尤其是一些呈现方式简单, 但 $\LaTeX$ 命令复杂的运算, 可以用cryptocode提供的更容易记忆和使用的短命令.

名称	cryptocode命令	等价 $\LaTeX$ 命令
随机采样	`\sample`	`\leftarrow`
标志	`\bad`	`\mathsf{bad}`
0-1集合	`\bin`	`\left\{0, 1\right\}`
概率	`\prob`	`\mathsf{Pr}`
敌手优势	`\advantage`	`\mathsf{Adv}`
密钥生成	`\kgen`	`\mathsf{KGen}`

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

算法

在密码学论文中, 除了那些常见符号外, 还会需要用 $\LaTeX$ 的algorithm环境呈现算法方案. 而在cryptocode中则可以直接用procedureblock, 效果如下图所示.

而对应的 $\LaTeX$ 代码也更为简洁, 无需像原来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 时, 我们常常需要借助 $\mathsf{bad}$ 等符号标注出一个game里有利于敌手的那些事件. 要表达这样一件事, 一般需借助table环境以及一些文本样式命令. 然而, cryptocode也提供了这方面的封装, 如下图所示.

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

密码协议

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

而在cryptocode中，可以同样使用procedureblock命令与缩进指令 (tabbing) \>方便地通呈现一个密码协议，如下图所示。

总结

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

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