密码学

密码学(Crypto)

概述

密码学(Cryptography)，是由希腊单词kryptos与graphin派生得到的，它包括密码编码学和密码分析学

  • 密码编码学：对信息的编码，实现对信息的隐秘
  • 密码分析学：破译加密信息和伪造信息

现代信息安全的基本要求：

  • 信息的保密性：防止信息泄漏给未经授权的人（加密解密技术）
  • 信息的完整性：防止信息被未经授权的篡改（消息认证码，数字签名）
  • 认证性：保证信息来自正确的发送者（消息认证码，数字签名）
  • 不可否认性：保证发送者不能否认他们已发送的消息（数字签名）

术语

  • 明文和密文

    • 明文(P)：又称消息，指尚未隐藏或被加密的信息；明文的集合成为明文信息空间(SP)
    • 密文(C)：被加密后的消息；密文构成的集合成为密文信息空间(SC)

  • 密钥

    • 密钥(K)：明文到密文的转换由一些特定的函数完成，控制这些函数的参数成为密钥，一般是用户实现选定的字符或数字序列
    • 密钥空间(SK)：密钥构成的集合称为密钥空间
    • 密钥量：密钥空间中不同的密钥的个数称为密钥量，用来衡量一个密码体制的安全性

  • 加密与解密

    • 加密：把明文P从SP对应到SC的变换，记为\(E_k：S_p\rightarrow S_c\)，则明文与密文的关系可以表示为\(C=E_k(P)\)
    • 解密：把密文C从SC对应到SP的变换，记为\(D_k: S_c\rightarrow S_p\)，则\(P=D_k(C)=D_k(E_k(P))\)

古典密码

简介

古典密码指的是1976年以前的密码算法，主要是使用手工、纯机械或电子机械等方式进行加密，大多数是对有意义的文字进行加密，使用在军事机密和外交领域，它加解密过程简单，一般用手工或机械就可以完成。它的计算强度小，数据安全性基于算法的安全性，因此算法必须要保密。

密码体制

  • 单表代替密码
  • 多表代替密码
  • 置换密码

单表代替密码

棋盘密码

Polybius密码

将明文加密为两两组合的数字，如下图，

加密与解密

每一个字母对应一个两位数\(\overline{ab}\)，a为该字母在表中的行号，b为该字母在表中的列号，

例如对于明文 “I love China”，可以得到密文序列 "23 43 24 52 23 51 41 23 54 31"；相反地，已知密文序列也可以通过查表获得明文。

在线工具

点击此处进入在线工具

ADFGX密码

ADFGX加密与Polybius加密类似，只是将 1,2,3,4,5改为 ADFGX

移位密码

移位密码是通过将明文中所使用的字母按照一定的字数进行平移来加密，其中最早出现的是著名的凯撒密码

凯撒密码
简介

凯撒密码是一种替换加密的技术，明文中的字母带字母表上向后（或向前）按照一个固定的偏移量偏移后被替换成密文如下图，

（图片来源与网络）

但凯撒密码很容易被破解（可以分别尝试偏移0~25暴力破解），因此凯撒密码多被当作其它更为复杂的加密算法的一个步骤。

传说中凯撒使用的是 key=3的移位密钥，经过推广，凯撒密码可以便宜其它任何整数位，根据偏移量不同，存在特定的凯撒密码名称

  • Avocat:偏移量为10
  • ROT13:偏移量为13
  • Cassis:偏移量为-5
  • Cassette:偏移量为-6
在线工具

点击此处进入在线工具

移位密码
加密
  • 假设英文字母与26个整数的对应关系如下，
  • 设明文为 “CHINA”，密钥为 6，加密过程如下
  1. 将明文映射到\(Z_{26}\)，得到整数序列：02 07 08 13 00
  2. 将数字加上 key=6，结果mod26运算，得到 08 13 14 19 06
  3. 再根据表格转换为英文字母，得到密文为 INOTG
解密
  • 密文是 INOTG，转换为数字序列 08 13 14 19 06
  • 数字减 key=6，mod26运算得到序列 08 13 14 19 06
  • 将结果转化为明文 CHINA

仿射密码

  • 仿射密码是一种替换密码，明文和密文是一一对应的字母

  • 加密函数：\(E_{key}=(k_1x+k_2)mod26\)，\(k_1\)与26互质，\(k_2\)是随机数

    1. 假设需要加密的明文为 CHINA，转换为数字序列为 2,7,8,13,0
    2. \(k_1\)可能的取值有 1,3,5,7,9,11,15,17,19,21,23,25，暂定\(k_1=7,k_2=13\)
    3. 使用加密函数\(E_{key}=(7x+13)mod26\)对明文数字序列加密，得到数字序列 1,10,17,0,13
    4. 得到密文 BKRAN

  • 解密函数：\(D_{key}=k^{-1}(y-k_2)mod26\)

    1. 首先将密文 BKRAN转换为数字序列 1,10,17,0,13
    2. 计算\(7\)的乘法逆元为\(15\)
    3. 代入解密公式\(D_{key}=15*(y-13)mod26\)，得到明文序列 2,7,8,13,0
    4. 查表后得到明文为 CHINA

    \(k^{-1}\)表示\(k\)在\(Z_{26}\)中的乘法逆元，即\((kk^{-1})mod26=1\)

// 计算一个数在$Z_{26}$中的乘法逆元
# include "stdio.h"
# include "stdlib.h"

int main()
{
    int x = 0;
    printf("请输入一个数字:");
    scanf("%d", &x);
    for (int i = 0; i < 100; ++i)
    {
        if ((x*i) %26 == 1)
        {
            printf("%d\n", i);
            break;
        }
    }

    system("pause");
    return 0;
}

多表代换密码

维吉尼亚密码

维吉尼亚密码表可以看作是由一系列偏移量不同的一位密码组成，密码表的大小是\(26*26\)，第一行是\(A\rightarrow Z\)的顺序，第二行是\(key=1\)的移位密码，以此类推，最后一行是\(key=25\)的移位密码。

加密与解密
  1. 假设明文为 CHINESE，关键词为 FLAG，重复关键词得到密钥 FLAGFLA
  2. 逐个字母分析，密钥对应行号，明文对应列号，例如\(F\)和\(C\)对应\(H\)，则\(C\)的密文为\(H\)，以此类推，得到完整密文为 HSITJDE；通过相反的方法可以根据密钥和密文退出明文。

在维吉尼亚密码体制中，密钥不同，同一个明文字母可以被映射到不同的密文字母，体现出多表代换密码优势，解决了明文中单字母出现的频率与密文中相同的问题。

置换密码

置换密码是根据一定的规则重新排列明文，以打破明文的结构特性，明文中的字符不变，只是位置和次序发生改变。

加密

  1. 明文为 informationsecurityisimportant
  2. 设置密钥为 351264
  3. 密钥长度为6，将明文6位一组分成5组：inform ations ecurit yisimp ortant
  4. 将5组明文分成5行，每行有6列
3 5 1 2 6 4
i n f o r m
a t i o n s
e c u r i t
y i s i m p
o r t a n t
  1. 按照新的123456的顺序逐行获取密文 foimnrioastnuretcisiypimtaotrn

解密

  1. 已知密文 foimnr ioastn uretci siypim taotrn，按顺序排成6列
1 2 3 4 5 6
f o i m n r
i o a s t n
u r e t c i
s i y p i m
t a o t r n
  1. 已知密钥 351264，得到解密顺序
3 5 1 2 6 4
i n f o r m
a t i o n s
e c u r i t
y i s i m p
o r t a n t
  1. 按照解密顺序得到明文 informationsecurityisimportant

现代密码与散列函数

与古典密码不同，现代密码的数据安全基于密钥和算法公开。

“一切秘密寓于密钥”：攻击者即使知道了密码系统中所用的算法，也无法通过解惑的密文推算出明文或密钥。密码体制的所有秘密寓于密钥当中，这就要求公开的加密算法非常健壮

散列函数

散列函数算法是一种将任意长度的消息亚索到某一固定长度的算法总称。

  • 优点

    1. 雪崩效应：散列函数对于源数据的更改具有极高的敏感性，即使是\(1bit\)的更改都会对最终的散列值造成很大改变。
    2. 安全性高，逆向计算的难度远大于正向计算的难度。

. 缺点

  1. 单向算法：散列函数是指是一种压缩映射，即多对一的映射，散列值的空间(密文空间)远小于输入的空间(明文空间)，而且不同的输入法可能会散列称相同的输出，因此不可能从散列值唯一确定输入值。

MD算法

  • 用途

    • 一致性验证：确保信息传输完全已知，以防止被篡改

      • 无论多大的数据，经过算法运算之后都是固定长度。结果使用32个16进制数连成的字符串显示\(128bit\)的二进制串

    • 数字签名

    • 安全访问认证：用于操作系统的登陆认证

      • 创建密码：输入密码\(\rightarrow\)对密码进行MD5\(\rightarrow\)储存密码的MD5值
      • 验证密码：输入密码\rightarrow对密码进行MD5\(\rightarrow\)对比储存的MD5值

系统在不知道用户密码明码的情况下就可以确定用户登录系统的合法性，避免用户的密码被有权限的管理员知道，可以有效防止密码泄漏

eg:忘记密码 ：通过验证后一般是重设密码而不会显示原密码，因为该网站只有原密码的散列值

  • 处理步骤

    1. 数据填充，追加数据长度

      1. 计算填充长度：设消息长度为\(K\)，填充的目标是满足\(K mod 512=448\)
      2. 填充：在原文后面填充，第一位是1，其余为0

    2. 添加消息长度：在结尾补充原消息的长度(用来储存的长度为\(64bit\)(512-448))

    3. 分组循环变换

      1. 设置初始值，MD5的散列值长度为128位，按每32位分成一组，共4组

      2. 这四组的结果是由4个初始值\(A/B/C/D\)经过多轮(轮数由输入的信息长度决定)不断演变得到。官方实现中\(A=0x01234567,B=0x89ABCDEF,C=0xFEDCBA98,D=0x76543210\)

    4. 循环运算

      1. 在第一步中，处理后的明文长度是512的整数倍，按每512位一份分成16等份，命名为\(M0-M15\)，每一份长度为32

      2. 每16次循环，都会交替用到\(M0-M15\)，当16个子分组处理完成时，就完成了一次循环变换。\(MD5\)的数据分组一共需要进行四轮循环变换，64次子循环

      3. \(K_i\)是一个常量，且64次子循环中的常量不同

      4. <<\(s\)位，其中\(a=b+((a+X(b,c,d)+Mj+Ki)<<

        • FF(a,b,c,d,Mj,Si,Ki)：0~16次
        • GG(a,b,c,d,Mj,Si,Ki)：17~23次
        • HH(a,b,c,d,Mj,Si,Ki)：33~48次
        • II(a,b,c,d,Mj,Si,Ki)：49~64次

图中绿色框代表四中官方定义的非线性函数

  • F(X,Y,Z) = (X&Y) | ((~X)&Z)
  • G(X,Y,Z) = (X&Z) | (Y & (~Z))
  • H(X,Y,Z) = XYZ
  • I(X,Y,Z) = Y^(X | (~Z))

SHA算法

简介

SHA算法是一个密码散列函数族

安全性
  • SHA可以产生独特的散列，当两个不同的值或文件产生了相同的散列，就会发生碰撞。只有在不发生碰转时，才能保证数字签名的安全性
  • MD5的摘要长度为\(128bit\)，SHA的摘要长度为160bit，多出\(32bit\)一位这不同明文的碰撞几率降低了\(2^{32}\)倍
应用

SSL行业选择SHA作为数字签名的散列算法

对称加密算法

概述

  • 加密和解密使用同一个密钥的加密方式。

  • 优点：计算量小，速度快，适合对大量数据进行加密

  • 缺点：

    • 不能保证密钥安全的传递
    • 密钥数量逐渐增多，管理代价高

  • 应用

    • 流密码：加密和解密双方使用相同伪随机加密数据流作为密钥，明文数据每次与密钥数据流顺次对应加密，得到密文数据流，主要应用在对链路的实时加密 中。
    • 分组密码：将明文数字序列，划分成长度为 n 的组，每组分别在密钥的控制下变换成等长的输出数字（简称密文数字）序列，主要应用在网络包交换加密 过程中。

非对称加密（公开密钥密码体制）

结合上图，分析非对称加密的过程

  1. Alice有明文X；
  2. Bob随即生成一对密钥，一个作为公钥c，另一个作为私钥d；
  3. Bob将公钥发送给Alice，即使Eve在中间窃听到公钥c也没关系
  4. Alice利用公钥c将明文X加密得到密文c(X)
  5. Alice将密文c(X)传输给Bob，即使Eve在中间窃听到密文c(X)也没关系
  6. Bob用私钥d对密文c(X)解密的d(c(x))，得到明文X

Eve没有私钥d，因此无法得知明文X

科普—Alice与Bob

出自布鲁斯·施奈尔所著的《应用密码学》，Alice、Bob—在密码学中是最基本的两位代用人物，其次是Eve。通例上，Alice希望把一条讯息传送给Bob。

  • Carol/Charlie—通讯中的第三位参加者。
  • Dave—通讯中的第四位参加者。
  • Eve—一位偷听者，但行为通常是被动的。他拥有偷听的技术，但不会中途篡改传送的讯息。
  • Isaac—互联网服务提供者。
  • Ivan—发行人，使用于商业密码学中。
  • Justin—是司法机关。
  • Mallory—一位恶意攻击者，与Eve不同的是，Mallory会篡改传送的讯息。对付马洛里所需的信息安全技术比对Eve的高出很多。
  • Matilda—商人，用于电子商务。
  • Oscar—敌人，通常与Mallory一样。
  • Pat/Peggy—证明者，Victor—验证者：两人会证实一项事件是否有实际进行，多使用于零知识证明。
  • Plod—执法官员。
  • 史蒂夫（Steve）代指隐写术（Steganography）。
  • Trent—一位可信赖的仲裁人，中立的第三者，根据存在的协议而判断。
  • Trudy—侵入者，等同马洛里。
  • Walter—看守人，根据已存在的协议而保护Alice和Bob。
  • Zoe—安全协议中的最后参与者。

RSA密码

  • 欧拉函数：任意给定正整数n，计算小于等于n的正整数中有多少个与n互质

    1. \(n=1,\phi(n)=1\)
    2. \(n\)是质数,\(\phi(n) = n-1\)
    3. \(n=p^k,\phi(n) = p^k-p^{k-1}\)
    4. \(n = pq\)，且\(p,q\)互质，\(\phi(n) = (p-1)(q-1)\)

  • 欧拉定理：若\(a\)与\(n\)互质，则\(a^{\phi(n)} = 1(mod n)\)

  • 模反元素：\(ab=1(mod n)\)

  • RSA密钥生成算法

    1. 选择两个不相等的质数\(p = 11和q = 17\)
    2. 计算\(n=pq = 187\)，\(n\)的长度就是密钥的长度\(n = 187 = 10111011_{(2)}\)，即密钥长度是8（实际上，RSA的密钥一般是1024位）
    3. 根据欧拉函数\(\phi(n) = 160\)
    4. 在\((1,\phi(n))\)随机选择一个整数e，且e与\(\phi(n)\)互质，例如\(e = 27\)
    5. 设\(e\)对于\(\phi(n)\)的模反元素是\(d\)， \(ed = 1(mod (\phi(n)))\),即\(ed-1 = k\phi(n)\)
    6. 解二元一次方程\(27d-1 = 160k\)，一组整数解为\(d=43,k=11\)（辗转相除法）
解法如下：
27d-160k = 1;
160/27 = 5......25
27/25 = 1......2
25/2 = 12......1
则有
27d-160k = 1 
= 25-2*12 
= 25-(27-25*1)*12 = 25*(-11)-27*12
= (160-5*27)*(-11)-27*12 = 43*27-160*11
得到一组解d=43,k=11

编码

\(Unicode\)编码

简介

\(Unicode\)编码为每种语言的每个字符设定了统一并且唯一的二进制编码，以满足跨平台、跨语言地进行文本处理的要求。特征就是\u加4为16进制数

\(Base 64\)编码

简介

Base64不是加密算法，而是一种 将二进制转换为文本的编码方式。它是包括小写字母\(a\rightarrow z\)、大写字母\(A\rightarrow Z\)、数字\(0\rightarrow 9\)、符号"\(+\)"、"\(/\)"一共64个字符的字符集(加密过程中很可能用到"\(=\)"补位)。任何符号都可以转换成这个字符集中的字符，这个转换过程就叫做\(Base64\)编码。

编码与解码

\(2^6=64\)，因此 6\(bit\) 为一个\(Base64\)的单元。编码时，首先将字符串（图片等）转换成二进制序列，然后按 \(6bit\) 为一组，分成若干组，但是又可能到最后不够3个字节，只能用2个\(Base64\)字符表示1个字节或者3个\(Base64\)字符表示2个字节，在低位用0补足，这样就构成一个新的二进制序列，最后根据\(Base64\)索引表中的值找到对应的字符。具体过程如下，

  • 恰好字符数是3的倍数，如下图，得到 TeX的\(Base64\)编码结果为 VGVY。
  • 转换到最后不够3个字节，在二进制为的低位用\(“0”\)补位，其余用\(“=”\)补位，这并不影响以后的解码，而且可以推断只有在Base64字符串的最后才有可能出现1个或2个\(“=”\)，如下图，得到 T的\(Base64\)编码结果为 VA，Te的\(Base64\)编码结果为 VGU。

\(Base64\)索引表

（图片来源于网络）

在线工具

点击此处进入在线工具：

密码破解

  • 穷举攻击（暴力破解）：对密码逐个推算，用于破解弱口令和压缩包密码
  • 频度分析：对各个字母和字母组合进行拼读分析，利用统计结果推测密码,针对移位密码、代换密码和仿射密码体制

具体题目见CTF专区Crypto部分

  • 附频度分析图

（图片来源与网络）

CTF

相关

XCTF---easyjni的WriteUp

Youngter-drive(BUUCTF)

CTF入门学习3->Web通信基础

ctfshow web入门信息收集

Bugku CTF练习题---MISC---telnet

XCTF练习题---MISC---就在其中

XCTF练习题---MISC---normal_png

XCTF练习题---CRYPTO---wtc_rsa_bbq

bcloud_bctf_2016(house of force)

bcloud_bctf_2016(house of force)

BUU-CTF[CISCN2019 华东南赛区]Web11

BUUCTF-[CISCN2019 华东南赛区]Web4

标签