国密SM9标识密码算法数理原理

国密SM9标识密码算法推出好多年了，只是大概看过一些介绍，从来没有仔细研究，现在看到的频率越来越多，决定对照规范好好学习一下。国密SM9标识密码算法由国密局的密码行业标准GM/T 0044-2016《SM9标识密码算法》公布，这个标准共分五个部分：

第1部分：总则
第2部分：数字签名算法
第3部分：密钥交换协议
第4部分：密钥封装机制和公钥加密算法
第5部分：参数定义

Adi Shamir(RSA中的S)在1984年提出了标识密码（Identity-Based Cryptography）的概念，在标识密码系统中，用户的私钥由密钥生成中心（KGC）根据主密钥和用户标识计算得出，用户的公钥由用户标识唯一确定，从而不需要第三方保证其公钥的真实性。与基于证书的公钥密码系统相比，标识密码系统中的密钥股那里环节可以得到适当简化

定义

标识 identity

可以唯一确定一个实体身份的信息。标识应有实体无法否认的信息组成，如实体可以识别的名称、电子邮箱、身份证号码、电话号码等。

主密钥 master key

处于标识密码密钥分层最顶层的密钥，包括主私钥和主公钥，其中主公钥公开，主私钥由KGC秘密保存。<u>KGC用主私钥和用户的标识生成用户的私钥</u>。在标识密码中，主私钥一般由KGC通过随机数发生器产生，主公钥由主私钥结合系统参数产生。

签名系统的主密钥与加密系统的主密钥不同。数字签名算法属于签名系统，其主密钥为签名主密钥，密钥交换协议、密钥分装机制和公钥加密算法属于加密系统，其主密钥为加密主密钥。

密钥生成中心 key generation center;KGC

在SM9标识密码中，负责选择系统参数、生成主密钥并产生用户私钥的可信机构。

有限域和椭圆曲线

有限域

概述

域由一个非空集合F和两中运算共同组成，这两种运算分别为加法（用+表示）和乘法（用 $\cdot$ 表示），并满足下列算数特性：

a) (F, + )对于加法运算构成加法交换群，单位元用0表示。
b) (F, $\cdot$ )对于乘法运算构成乘法交换群，单位元用1表示。
c) 分配律成立：对于所有的 $a,b,c \in F$ ,都有 $(a+b) \cdot c = a \cdot c + b \cdot c$ 。

若集合F是有限集合，则称域为有限域。有限域的元素个数称为有限域的阶。

素域 $F_p$

阶位素数的有限域是素域。

设p是一个素数，则整数模p的全体余数的集合 ${0,1,2, \cdots ,p-1}$ 关于模p的加法和乘法构成一个p阶素域，用符号 $F_p$ 表示。

$F_p$ 具有如下性质：

a) 加法单位元是0
b) 乘法单位元是1
c) 域元素的加法是整数的模p加法，即若 $a,b\in F_p$ ,则 $a+b=(a+b) mod\ p$
d) 域元素的乘法是整数的模p乘法，即若 $a,b\in F_p$ ,则 $a \cdot b=(a \cdot b) mod\ p$

有限域 $F_{q^m}$

设q是一个素数或者素数方幂， $f(x)$ 是多项式环 $F_q[x]$ 上的一个m(m>1)次不可约多项式（称为约化多项式或域多项式），商环 $F_q[x]/(f(x))$ 是含 $q^m$ 个元素的有限域（记为 $F_{q^m}$ ），称 $F_{q^m}$ 是有限域 $F_q$ 的扩域，域 $F_q$ 为域 $F_{q^m}$ 的子域，m为扩张次数。 $F_{q^m}$ 可以看成 $F_q$ 上的m维向量空间。 $F_{q^m}$ 的每一个元可以唯一地写成 $\alpha_0\beta_0+\alpha_1\beta_1+\cdots+\alpha_{m-1}\beta_{m-1}$ ，其中 $\alpha_i \in F_q$ ，而 $\beta_0,\beta_1,\cdots,\beta_{m-1}$ 是向量空间 $F_{q^m}$ 在 $F_q$ 上的一组基。

$F_{q^m}$ 中的元素可以用多项式基或正规基表示。在商密规范中，一般 $F_{q^m}$ 中的元素均采用多项式基表示。

不可约多项式 $f(x)$ 可取为首一的多项式 $f(x)=x^m+f_{m-1}x^{m-1}+\cdots+f_2x^2+f_1x+f_0$ （其中 $f_i \in F_q,i=0,1,\cdots,m-1$ ）， $F_{q^m}$ 中的元素由多项式环 $F_q[x]$ 中所有次数低于m多项式构成。多项式集合 $\{ x^{m-1},x^{m-2},\cdots,x,1\}$ 是 $F_{q^m}$ 在 $F_q$ 上的一组基，称为多项式的基。域 $F_{q^m}$ 上的任意一个元素 $a(x)=a_{m-x}x^{m-1}+a_{m-2}x^{m-2}+\cdots +a_1x+a_0$ 在 $F_q$ 上的系数恰好构成了一个m维向量，用 $a=(a_{m-1},a_{m-2},\cdots,a_1,a_0)$ 表示，其中分量 $a_i \in F_q,i=0,1,\cdots,m-1$ 。
$F_{q^m}$ 具有如下性质：

a) 零元0用m维向量 $(0,\cdots,0,0)$ 表示
b) 乘法单位元1用m维向量 $(0,\cdots,0,1)$ 表示
c) 两个域元素的加法为向量加法，各个分量用域 $F_q$ 的加法
d) 域元素a和b的乘法定义如下：设a和b对应的 $F_q$ 上多项式为a(x)和b(x)，则 $a\cdot b$ 定义为多项式 $(a(x)\cdot b(x) mod \ f(x))$ 对应的向量
e) 逆元：设a对应的 $F_q$ 上的多项式为a(x),a的逆元 $a^{-1}$ 对应的 $F_q$ 上多项式为 $a^{-1}(x)$ ，那么有 $a(x)\cdot a^{-1}(x)\equiv 1 \ mod \ f(x)$ 。

有限域上的椭圆曲线

有限域 $F_{q^m}(m\ge 1)$ 上的椭圆曲线是由点组成的集合。在仿射坐标系下，椭圆曲线上点P（非无穷远点）用满足一定方程的两个域元素 $x_P$ 和 $y_P$ 表示， $x_P,y_P$ 分别称为点P的x坐标和y坐标，并记 $P=(x_P,y_P)$ 。

定义在 $F_{p^m}$ 上的椭圆曲线方程为：

$y^2 = x^3+ax+b, a,b \in F_{p^m}, 且 4a^3+27b^2\ne 0 \ \cdots \ \cdots \ \cdots 1$

椭圆曲线 $E(F_{p^m})$ 定义为：

$E(F_{p^m})=\{ (x,y) |x,y \in F_{p^m},且满足方程(1)\}\cup \{O\} ,其中O是无穷远点$

椭圆曲线 $E(F_{p^m})$ 上的点的数目用 $\# E(F_{p^m})$ 表示，称为椭圆曲线 $E(F_{p^m})$ 的阶。

商密SM9规范中规定素数 $p>2^{191}$

设E和E'是定义在 $F_q$ 上的椭圆曲线，如果存在一个同构映射 $\phi_d:E'(F_{q^d})\to E(F_{q^d})$ ，其中d是使映射存在的最小整数，则称E'为E的d次扭曲线。当 $p \ge 5$ 时，d的取值又3种情况：

a) $若a=0,b\ne 0,那么d=6, E':y^2 = x^3 + \beta b,\phi_6 : E' \to E: (x,y)\mapsto(\beta^{-1/3}x,\beta^{-1/2}y);$
b) $若b=0,a\ne 0, 那么d=4, E':y^2=x^3+\beta ax,\phi_4:E' \to E:(x,y) \mapsto (\beta^{-1/2}x,\beta^{-3/4}y);$
c) $若a\ne 0,b\ne 0,那么d=2,E':y^2=x^3+\beta^2 ax+ \beta^3 b,\phi_2:E' \to E:(x,y) \mapsto(\beta^{-1}x,\beta^{-3/2}y).$

椭圆曲线群

椭圆曲线 $E(F_{p^m})(m\ge 1)$ 上的点按照下面的加法运算规则，构成一个交换群：

a) $O+O=O$
b) $\forall P=(x,y) \in E (F_{p^m}) \backslash \{ O \}, P+O=O+P=P$
c) $\forall P=(x,y) \in E (F_{p^m}) \backslash \{ O \}, P的逆元素-P=(x,-y),P+(-P)=O$
d) $两个非互逆的不同点相加的规则：$

$设P_1=(x_1,y_1) \in E(F_{p^m}) \backslash \{ O\}, P_2=(x_2,y_2) \in E(F_{p^m})\backslash \{O\},且x_1 \ne x_2,$

$设P_3=(x_3,y_3)=P_1+P_2,则$

$\begin{cases} x_3 = \lambda^2 - x_1 - x_2, \\ y_3 = \lambda (x_1 - x_3) - y_1, \end{cases}$

其中

$\lambda = \frac {y_2-y_1}{x_2-x_1};$
e) 倍点规则：
$设P_1=(x_1,y_1) \in E(F_{p^m}) \backslash \{O\}, 且y_1 \ne 0,P_3=(x_3,y_3)=P_1+P_1$ ,

则

$\begin{cases} x_3 = \lambda^2-2x_1, \\ y_3 = \lambda (x_1 - x_3) - y_1, \end{cases}$
其中
$\lambda = \frac {3x_1^2 + a}{2y_1}.$

椭圆曲线多倍点运算

椭圆曲线上同一个点的重复相加称为该点的多倍点运算。设u式一个正整数，P是椭圆曲线上的点，其u倍点
$Q=[u]P= \begin{matrix} \underbrace{ P+P+\cdots+P } \\ u个 \end{matrix} .$

多倍点运算可以扩展到0倍点运算和负数倍点运算： $[0]P=O,[-u]P=[u](-P)$ .

椭圆曲线子群上点的验证

输入：定义 $F_{q^m}$ 上（q为奇素数， $m \ge 1$ ）椭圆曲线方程的参数a、b，椭圆曲线 $E(F_{q^m})$ 上的子群G的阶N， $F_{q^m}$ 上的一堆元素(X,y)。

输出：若(x,y)是群G中的元素，则输出有效，否则输出无效。

a) 在 $F_{q^m}$ 上验证（x,y）是否满足椭圆曲线方程 $y^2 = x^3+ax+b$
b) 令Q=(x,y)，验证[N]Q=O

若以上任何一项验证失败，则输出无效，否则输出有效

离散对数问题

双线性对及安全曲线

双线性对

安全性

嵌入次数及安全曲线

系统参数的验证

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,456评论 5赞 477
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,370评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,337评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,583评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,596评论 5赞 365
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,572评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,936评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,595评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,850评论 1赞 297
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,601评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,685评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,371评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,951评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,934评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,167评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 43,636评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,411评论 2赞 342