软考密码学（一）

作者: river_li | 来源:发表于2019-05-21 00:00 被阅读0次

软考密码学（一）
软考密码学（二）
几种古典密码代码实现
软考
软考
软考
软考各级别考试难度对比
软考记录
软考体会
软考（信管）

更多文章欢迎访问个人博客/备用链接;

概念

基本目标

保密性
完整性
可用性

关于密码学的保密性，常用的保密技术包括：

防侦收
防辐射
数据加密
物理保密

针对密码学的攻击

穷举攻击
数学分析攻击
基于物理的攻击
仅知密文攻击
已知明文攻击
选择明文攻击 CPA
选择密文攻击 CCA

我国的密码

做到好多相关题目，经常分不清，因此专门整理一下

SM4

2006年公布的用于无线局域网的SM4密码算法

是一个分组密码，数据分组长度128bits，密钥长度128bits

加密和密钥拓展均有32轮

加密解密算法结构相同，只是轮密钥顺序不同

ZUC

ZUC即祖冲之算法

用于移动通信3GPP的加密和验证

是一个同步流密码

整体结构分为三层:

上层为定义在素域 $GF(2^{31}-1)$ 上的先行反馈移位寄存器
中层为比特重组
下层为非线性函数F

其本质上是一种非线性序列产生器

SM3

SM3是2010年国家发布的安全杂凑算法

每一组也是512bit

SM2

SM2是国家2010年发布的椭圆曲线公钥密码算法，商用密码体系中用来替代RSA

古典密码

置换密码
代替密码
代数密码

以上三个类型的典型例子是：凯撒密码、维吉尼亚密码、Vernam密码

针对古典密码的破译，常用方法为：穷举分析、统计分析

Vernam密码就是简单的用密钥异或明文得到密文

当密钥长度与明文长度相等时，Vernam密码是理论上无法破译的

（与之相对的概念为计算上无法破译)

分组密码

DES

Len(Key)=64 bits
Len(M)=64 bits
Len(C)=64 bits

def DES(M,Key):
    (L0,R0)=IP(M)
    //IP
    K=SubKeyGen(Key)
    // K=16*56 bits
    //子密钥生成
    
    for i=0 to 16:
        Li=Ri-1
        Ri=Li xor f(Ri-1,Ki)
    
    swap(L16,R16)
    //16轮后左右部分要交换
    C=RIP(L16,R16)
    //逆IP置换
    return C

def SubKeyGen(Key):
    K0=switch_choose1(Key)
    // K0 = 56 bits
    // (C0,D0) = K0
    //选择置换一
    //目的是用64位的Key生成56位的K0
    
    for i=0 to 16:
        Ci+1=MovLeft(Ci)
        Di+1=MoveLeft(Di)
        Ki+1=Switch_Choose2(Ci+1,Di+1)
        //选择置换二
        //两个28位组合成一个56位的子密钥K
    return K
    
def f(R,K):
    // R is 32 bits
    // K is 56 bits
    result=E(R)
    //选择运算，输入32位，输出48位
    result=xor(result,K)
    result = S(result)
    //S盒运算
    //48位分成6*8
    //每一个6位 拆成1+4+1
    //对于每个S盒 输入6位输出4位
    
    result = P(result)
    //置换运算，作用是扩散混淆
    return result

DES的安全问题：

密钥太短 $2^{56}$ 对于现在的计算力不是太难，可以穷举
存在弱密钥

DES中存在一些密钥K，使得子密钥k1=k2=....=k16

注意：对于抗穷举攻击，2DES的效果与DES是一样的，只能使用3DES

2DES在穷举时的复杂度是 $2^{56} \times 2$

设已知明文M和密文C

穷举 $2^{56}$ 个密钥，保存其对M加密的结果以及对C解密的结果

只需要遍历数据库找到两者的交集即可

AES

AES主要由轮函数构成，即S盒变换、行移位和列混淆、圈密钥加组成

Round(State,RoundKey){
    ByteSub(State);
    //S盒
    ShiftRow(State);
    MixColumn(State);
    AddRoundKey(State,RoundKey);
}

AES不是对合运算，因此解密与加密不是同样的结构

解密的算法应该是将轮函数的逆运算

分组密码工作模式

ECB 电码本模式

直接分组加密，最简单

PCB 明密文链接模式

$C_i=E(M_i \oplus M_{i-1} \oplus C_{i-1},K)$

CBC 密文链接模式

$C_i = E(M_i \oplus C_{i-1},K)$

CFB 密文反馈模式

分组密码作为一个系列密码产生器使用

需要一个寄存器R的初始状态 $I_0$ ,和一个密钥K

K加密R后输出低s位，与明文异或后反馈给右移的R

OFB 输出反馈模式

这个也是将分组密码作为一个系列密码产生器使用

需要一个寄存器R的初始状态 $I_0$ ,和一个密钥K

用K将R加密，最右侧的s位作为序列密码密钥输出

这个结果也是R左移后空缺的内容

CTR 计数器模式

加密过程：
$O_i=E(T_i,K)\\ C_i=M_i \oplus O_i$
其中T是一个计数序列

序列密码

线性移位寄存器序列

这部分好复杂，而且很重要，之后补充

RC4

RC4目前已经被证明不安全，但是曾经使用十分的广泛

是一种十分简单易实现的算法

分为KSA和PRGA两部分

ksa:
    for i from 0 to 255:
        S[i]:=i
    endfor

    j:=0
    for i from 0 to 255:
        j:=(j + S[i] + key[i mod keylength]) mod 256
        swap values of S[i] and S[j]
    endfor

prga:
    j:=0
    i:=0
    while GeneratingOutput:
        i:=(i + 1) mod 256
        j:=(j + S[i]) mod 256
        swap values of S[i] and S[j]
        K:=S[ ( S[i] + S[j] )mod 256]
        output K
    endwhile

最终得到的K即为输出的序列

Hash

概念

hash函数满足的性质

单向性给定h，找到x使得H(x)=h不可行
抗弱碰撞性已知x,求y使得H(x)=H(y)是不可行的
抗强碰撞性找到任何H(x)=H(y)是不可行的

以上说的不可行均是计算上的

对于hash函数，有一种特别的攻击，生日攻击：

$p=1.2 \sqrt{n}$

含义为n个数中存在两个数相等的概率超过1/2的概率

这种攻击会导致复杂度直接指数除以二

Birthday Paradox

SHA

输入小于 $2^{64}$ 位，输出160位的摘要

对输入按512分组，以分组为单位处理

算法步骤：

填充报文
初始化缓冲区
执行算法主循环（核心是压缩函数）
输出

公钥密码

概念

如果一个函数 $y=f(x)$ ，且f具有陷门，满足

对于给定的x，计算出y很容易
对于给定的y，计算出x很困难，但是如果掌握陷门计算x就很容易

这个函数是单向陷门函数

实际中找到了的单向性足够的函数由：

有限域上的离散对数问题
大合数的因式分解

公钥加密的几个方式：

保证数据的秘密性

a. $C=E(M,K_{eB})$

b. $M=D(C,K_{dB})$
保证数据的真实性

a. $C=D(M,K_{dA})$

b. $M=E(C,K_{eA})$
同时保证秘密性和真实性

a. $S=D(M,K_{dA})$

$C=E(S,K_{eB})$

b. $S=D(C,K_{dB})$

$M=E(S,K_{eA})$

以上均为a发送给b的情况

$K_d$ 为私钥， $K_e$ 为公钥

RSA

选择两个大素数p、q
公开 $n=p \times q$
计算 $\varphi(n)=(p-1)(q-1)$
随机选取 $1<e<\varphi(n)$ 且 $(e,\varphi(n))=1$ ,公开e
$ed=== 1 \quad mod \quad \varphi(n)$ 求d
加密时 $C=M^e \quad mod \quad n$
解密时 $M=C^d \quad mod \quad n$

实际使用时RSA不能单独使用，必须经过Hash，否则可能会出现如下情况：

$M^e = C$

$M = M_1 * M_2$

Then
$M_1^e * M_2^e =C$
And we can get
$C_1 = M_1^e$

$C_2 = M_2^e$

another two messages

And when Decryption:
$C^d = M$

$C^d = C_1^d *C_2^d$

$C_1^d =M1$

$C_2^d = M2$

So when Encrypting, must use hash function
$y = Hash(M)$
because
$Hash(M_1) *Hash(M_2) \not= Hash(M)$

ElGamal

与RSA相对,ElGamal是基于离散对数问题的公钥密码

首先需要随机选一个大素数p，要求p-1由大素数因子

再选择一个模p的本原元a，公开p和a

密钥生成

用户随机选一个数d作为私钥

计算 $y===a^d \quad mod \quad p$ ,作为公钥

加密

随机取一个k

计算

$U=y^k \quad mod \quad p$

$C_1=a^k\quad mod\quad p$

$C_2=UM \quad mod \quad p$

$(C_1,C_2)$ 作为密文
解密

计算 $V=C_1^d \quad mod \quad p$

计算 $M=C_2 \times V^{-1}\quad mod\quad p$

ECC

椭圆曲线密码密钥短、签名短、软件实现规模小、硬件实现电路省电

$设p是大于3的素数，且4a^3+27b^2 \ne 0\quad mod \quad p,则\\ y^2=x^3+ax+b，为GF(p)上的椭圆曲线$

160位长度的ECC相当于1024位的RSA安全效果

写在最后

本文禁止转载，仅供个人学习交流

软考密码学（一）
更多文章欢迎访问个人博客/备用链接; 概念基本目标保密性完整性可用性关于密码学的保密性，常用的保密技术包...
软考密码学（二）
密码学应用更多内容请访问我的博客数字签名完善的签名需要满足三个条件：签名者事后不能抵赖任何其他人不能伪造...
几种古典密码代码实现
最近在备考软考信息安全工程师，学习到密码学部分，为了记忆更加深刻，将已经掌握并且觉得比较有趣的密码算法用Pytho...
软考
1.软件设计师 1.参考1 2.信息系统项目管理师
软考
软考全称计算机技术与软件专业技术资格（水平）考试，软考既是职业资格考试，又是职称资格考试。软考是一个神奇又特别的...
软考
为期一周的软考结束了。从上个月报名，，到今天考试，自己加起来的准备时间大概有一周。先是看教学视频，花了一大半时...
软考各级别考试难度对比
从软考历年的合格率来看，软考的通过率并不是很高，这可能跟软考报名没有设很高的门槛也是有一定关系的。由于软考向社会...
软考记录
软考的全称是计算机技术与软件专业技术资格（水平）考试。考试分为 5 个专业类别 1 计算机软件 2 计算机网络 ...
软考体会
上大学的时候，从来没想过要考什么计算机方面的证书。毕业后，参加工作的几年来来，却突然想考一下国内的软考的高级软件架...
软考（信管）
至于证书有啥作用，大家可以自行百度。这边主要分享下我的备考经验。说起初衷，主要觉得上下班路上时间太长了，然后平时在...