Renns' Blog

消息认证可以保护通信双方不受第三方攻击，但不能防止通信双方之间的攻击，例如 A、B间共享MAC密钥K，那么B可以产生任意消息并用K计算MAC，并声称该消息来自A A、B都可以否认自己曾发送过某消息，因为对方也可用密钥K伪造消息 因此在收发双方不能相互信任的情况下，就需要使用数字签名，数字签名必须具有以下特征 能验证签名者的身份 能检验被签消息内容的完整性 签名应能由第三方验证 ElGamal数字签名ElGamal算法首先选择大素数$q$及其原根$\alpha$ 用户A生成随机整数$1<X_A<q-1$，并计算$Y_A=\alpha^{X_A}\mod q$则A的私钥为$X_A$，公钥为${q,\alpha, Y_A}$ 若A要对消息M进行签名，则步骤如下 计算消息M的Hash值$m=H(M)$，满足$0\leq m\leq q-1$ 选择随机整数$1\leq K\leq q-1$满足$gcd(K,q-1)=1$ 计算$R=\alpha^K \mod q$ 计算$S=K^{-1}(m-X_AR)\mod(q-1)$，其中$K^{-1}$为$K$模$q-1$的逆 获得 ...

消息认证消息认证，即验证所收到的消息确实来自真正的发送方，而且消息未被篡改过 消息加密提供认证对于对称加密，理论上其可同时提供消息认证与消息保密性 例如密钥K仅由A、B共享，若A使用密钥K加密消息M并发送给B，则B可以相信消息来自于A，因为只有A能产生出可用K解密的密文 但上述推理其实隐含了一个假设：接收方容易对解密出的明文的可读性进行自动判断 显然实际中这个假设并不容易满足，若消息M是任意二进制序列，比如二进制文件或数字化的X射线等，则很难确定解密后的消息是合法明文还是无意义的位串 这个问题可以使用附加错误检测码来解决，也称为帧校验序列（FCS），但此处不展开说明 对于公钥加密，假设合法明文有易于判断的结构，则也可以同时提供消息认证与消息保密性 若A要给B发送消息M，则A依次用自己的私钥和B的公钥对M加密，就分别提供了认证与保密，前者是因为只有A的公钥才能解密出合法明文，后者是因为除B外没有人能用B的私钥解密 消息认证码消息认证码MAC又称密码校验和 MAC使用MAC函数产生，其输入是不定长消息和密钥，输出为固定长度的短数据块 例如A、B间共享密钥K，若A要向B发送消息M，则A计算$ ...

SHA-512总体结构SHA-512算法总体结构如图所示，后面我们会发现Hash码的每一位都是全部输入位的函数 其中输入消息最大长度为$2^{128}$位，输出为512位消息摘要，消息以1024位分组为单位处理 算法首先对输入进行填充使其长度模1024与896同余，注意即使输入已满足该条件也要填充，因此填充位数为1~1024，填充值以1开头，后续全为0 填充消息后，在消息后附加一个128位的无符号整数表示消息填充前的长度 此时消息的长度已经为1024的整数倍，将消息按1024位分组为$M_1,M_2,…,M_n$ 如图所示SHA加密的结构是安全Hash函数结构，可表示为 \begin{aligned} &H_0=IV\\ &H_i=SUM(F(M_i, H_{i-1}), H_{i-1}) \end{aligned}其中函数$F$产生512位输出，$SUM$函数（图中+号）将两个512位输入分别分成8个64位整数，再对应进行模$2^{64}$相加，最后消息摘要为$H_n$ 轮结构如图所示为SHA-512中模块$F$与$SUM$的具体结构 其中上一轮的结果$H_{i-1}$被分为8个 ...

密码学Hash及其应用Hash函数$H$可将不定长的数据块$M$作为输入，产生固定长度的Hash值$h=H(M)$一个好的Hash函数要求对于大的输入集合使用该函数，产生的结果均匀且看起来随机 在安全应用中使用的Hash函数称为密码学Hash函数，密码学Hash函数有如下几种应用 消息认证 当Hash函数用于提供消息认证功能时，Hash值通常称为消息摘要 假设A要给B发送消息M，则A计算Hash值$h=H(M)$并将$h$和消息一同发送B接收到消息后执行相同Hash计算，若Hash值结果不相同，则推断接受到的消息或Hash值遭到了篡改 消息认证中Hash值必须以安全得方式传输，否则会受到中间人攻击即攻击者截获消息和消息摘要，篡改消息并重新计算Hash值后再重新发送给接收人 一般的，消息认证是通过消息认证码MAC，即带密钥的Hash函数实现的 数字签名 Hash函数可以和公钥密码结合提供数字签名 假设假设A要给B发送消息M，则A用自己的私钥加密消息摘要，B则用A的公钥解密并验证消息摘要若消息M需要保密，则可以继续使用B的公钥对M和加密后的消息摘要进行加密 产生单向口令、构建PR ...

由于硬件提升和因子分解算法的发展不断威胁着RSA，最年来RSA密钥位数在不断增加而另一种公钥加密技术——椭圆曲线加密法ECC可以使用短得多的密钥获得与RSA相同的安全性 椭圆曲线基础实数域上的椭圆曲线椭圆曲线并不是椭圆，该名称只是因为其方程与计算椭圆周长的方程相似密码学中我们只考虑椭圆曲线的简化形式 y^2=x^3+ax+b除了方程所定义的点外，椭圆曲线还包含一个无穷远点（或称零点）$O$，他们共同组成点集$E(a,b)$ 若上述方程中的系数$a,b$满足 4a^3+27b^2\neq 0则可基于$E(a,b)$定义一个加群从几何角度定义椭圆曲线上的加法规则为：若椭圆曲线上三点在一条直线上，则它们的和为$O$ 根据该加法定义，$E(a,b)$满足如下条件 加法定义：设$P,Q$为曲线上两个不同点，他们的连线与椭圆曲线交于另一点$R$，则$P+Q=-R$可以证明$R$存在且唯一，除非连线在$P$（或$Q$）点与椭圆曲线相切，此时令$R=P$（或$R=Q$）此外若$P=Q$，则画出该点切线找到另一交点$R$，则$P+P=-R$ 单位元：$O$是$E(a,b)$的单位元。对于椭圆曲线上 ...

RSA原理RSA是最早提出并被广泛接受的公钥加密算法之一，其步骤如下 第一步，选择两个大素数$p,q$第二步，计算$n=pq$和$\phi(n)=(p-1)(q-1)$第三步，随机选择正整数$e<\phi(n)$满足$e$与$\phi(n)$互素第四步，计算$e$在模$\phi(n)$意义下的逆元$d$，即$ed\equiv 1(\mod \phi(n))$ 最后，公钥为${d,n}$，私钥为${e,n}$加密和解密过程分别为 $C=M^e \mod n$ 和 $M=C^d\mod n=M^{ed}\mod n$ 显然该算法要求$M<n$，应此实际应用中要将明文分组，每一分组转换成十进制数后要小于n RSA实现RSA的实现有很多计算上的问题需要考虑 首先是大素数$p,q$的选择问题，目前为止还没有有效的方法可以产生任意大素数一般的做法是随机选择一个期望位数的奇数，然后测试它是否为素数，若不是则继续随机 一般的确定性素性测试需要$O(\sqrt n)$进行试除，这样的复杂度并不能被接受基于概率性测试的Miller-Rabin算法是被广泛使用的素性检测算法算法原理和cpp实现可 ...

公钥密码学背景公钥密码学的提出是为了解决对称密码中最困难的两个问题： 密钥分配问题：通信双方要进行加密通信，必须通过一个安全信道共享密钥，然而这种安全信道在现实中难以实现其次对于有多个节点的通信网络，通常需要一个密钥分配中心管理密钥，否则整个系统保存的密钥数目会很大。然而公钥密码学提出者Diffie认为，要求用户与密钥分配中心共享密钥，那这些密钥分配中心的泄露也会使得一个不可破的密码体制毫无意义 数字签名问题：即能否设计一个方法对电子消息进行签名，确保消息出自某个特定的人 Diffie和Hellman二人针对上述问题提出了公钥密码学的概念，成为密码学发展的一个里程碑 公钥密码体制及其应用公钥密码体制中每个用户拥有两个密钥，分别为公钥和私钥，其中公钥是公开的，私钥是保密的 公钥密码的加密/解密算法满足可以用两个密钥中任何一个来加密，而另一个用来解密 根据这些特性，公钥密码体制可以分为三类应用： 消息的加密/解密 假设Alice要给Bob发送加密消息，且Bob产生了公钥$PU_b$和私钥$PR_b$Alice可以使用Bob的公钥$PU_b$对明文X加密，Bob则使用自己的私钥$PR ...

原根的定义首先引入数论中阶的定义 设$a\in Z, m\in N^+$，若$gcd(a,m)=1$，则称使得$a^n\equiv 1(\mod m)$成立的最小正整数$n$为$a$对膜$m$的阶 接下来是原根的定义 设$a\in Z, m\in N^+$，若$gcd(a,m)=1$，且$a$膜$m$的阶为$\varphi(m)$，则$a$为膜$m$的原根 原根的求解一般求解 定理1：若$m\notin {2,4}\bigcup{p^\alpha,2p^\alpha}$（其中p为奇素数，α为整数），则膜m不存在原根 由该定理，我们可以先求素数表，然后预处理出每个数是否有原根 定理2：膜m的原根数量级别为$O(m^{0.25})$ 定理3：若膜m存在原根，则其有$\varphi(\varphi(m))$个原根 假设我们已求得膜$m$的最小原根$g$，那么膜$m$的所有原根就是${g^k \ |\ gcd(k,\varphi(m)=1)}$所以我们可以直接从小到大枚举每个数判断其是否为膜m的原根先得到膜m的最小原根g，再求g的幂次方以求得所有原根 为判断g是否为膜m的原根，在 ...

欧几里得算法为方便后续扩展欧几里得的证明，这里简单回顾一下欧几里得算法的证明 假设欲求整数$a,b$的最大公因子$d=gcd(a,b)$ 使用带余除法，则b除a表示为 $a=qb+r,\ (0\leq r< b)$显然若$r=0$，则$gcd(a,b)=b$若$r\neq0$，因为 $d|a$ 且 $d|b$ ，所以一定有 $d|r$，接下来用反证法证明$gcd(b,r)=d$假设$gcd(b,r)=c$且$c>d$，则 $c|b$ 且 $c|(qb+r)=a$，与$gcd(a,b)=d$矛盾，因此$gcd(b,r)=d$ 综上即有欧几里得公式$gcd(a,b)=gcd(b,r)=gcd(b,a\mod b)$ 扩展欧几里得与ax+by=gcd(a,b)递归求解假设有 $ax+by=gcd(a,b)$ 和 $bx’+(a\mod b)y’=gcd(b,a\mod b)$ 成立则根据欧几里得公式有 $ax+by=bx’+(a\mod b)y’$将$a\mod b=a-\lfloor\frac{a}{b}\rfloor \times b$带入并整理得 $ax+by=ay’+b* ...

伪随机数产生的背景大量基于密码学的网络安全算法和协议都要使用二进制随机数 这些应用对随机数序列有两个要求 随机性：随机性可以用下面两个标准评价分布均匀性：序列中的位分布应是均匀的，即0、1出现的频率大致相等独立性：即序列中任何子序列不能由其他子序列推导出 不可预测性：即攻击者不能从先前的随机数推导出后面的随机数 随机数发生器可以分为真随机数发生器TRNG和伪随机数发生器PRNG TRNG把一个或多个很随机的源（例如键盘敲击的时间模式、鼠标移动等）作为输入，称为熵源，并转换为二进制序列输出一般而言，TRNG并不具有实用性，因为其有输出序列不可重现、效率较低等等缺点 而PRNG则选择一个固定值作为输入，称为种子，并用一个确定性的算法产生二进制序列输出 对随机性而言，要求PRNG尽管输出的位流是确定的但要“显示随机”然而并没有单个测试可以判定一个PRNG算法产生的输出的随机性，一般做法是设计一系列测试，如果该PRNG算法在多个测试上表现良好，则认为它满足要求对PRNG的随机性测试应该从如下几方面着手 均匀性：在序列的任何点，0或1出现的次数大约相等 可伸缩性：若序列是随机的，那么其中的 ...