最近一直在忙，都没能抽出时间来认认真真的学点东西，寒假去了一家圈子内比较有名的公司呆了几天学了点东西。从今天开始整理下自己所学到东西，也为这几天的学习做一个总结。

这一篇写的是密码学方向的内容，因为之前看WEB的东西看的更多所以每次碰到密码学方向的题目我其实挺懵的，这次机会正好补补基础。

古典密码

凯撒密码

凯撒密码也称为移位密码，加密时会根据偏移量进行相应的移位。对照表是26个英文字母，例如当偏移量为1时明文A经过加密后就变成了B。

在不知道偏移量的情况下我们可以进行爆破。偏移量取值范围为1~25。

乘法密码

乘法密码是替换密码的一种，加密时对已知明文进行编号，通过加密算法得到相应的位置表并且替换明文后得到密文。

设明文消息元素个数为n，密钥为k。
密钥k在选取的时候应满足两个条件：
（1）0<k<n  #可以用欧拉函数直接求得K的可取值数量
（2）k与n互素
设明文消息为M，消息元素为m;
则密文消息为C，密文元素为c=m*k mod n;
其解密过程如下：
首先要得到解密密钥，就是要求得加密密钥k模n的逆元；
具体求法为k *mod n=1;
然后计算m=c *mod n即可得到明文消息M。

解密时可以进行爆破，密钥有11种。

仿射密码

仿射密码为单表加密的一种，字母系统中所有字母都藉一简单数学方程加密，对应至数值，或转回字母。其仍有所有替代密码之弱处。所有字母皆借由方程(ax+b) mod (26)加密，b为移动大小。

密钥为gcd(a,b)一共是311种情况这里的明文全为字母。所以在破解时可以尝试暴力破解。

##判断是否与26互素
def isPN(a):
    for num in range(2,a):
        if 0==a%num and 0==26%num:
            return False
    return True

##求得逆元a_
def get_a_(a):
    i=1
    while (1!=(i*a)%26):
        i=i+1
    return i


##解密函数
def decodeMstr(mStr,a_,b):
    yStr=""
    for Char in mStr:
        if Char>='A' and Char<='Z':
            Int=ord(Char)-ord('A')
            Int=((Int-b+26)*a_)%26
            yStr=yStr+chr(Int+ord('A'))
        elif Char>='a' and Char<='z':
            Int=ord(Char)-ord('a')
            Int=((Int-b+26)*a_)%26
            yStr=yStr+chr(Int+ord('a'))
        else:
            yStr=yStr+Char
    return yStr

mStr="achjbnpdfherebjsw"
for a in range(1,25,2):
    if False==isPN(a):
        continue
    else:
        a_=get_a_(a)
    for b in range(-10,10):
        yStr=decodeMstr(mStr,a_,b)
        print(yStr,end="\t")
        print(a,b)

针对指定规则的简单代换密码，我们还可以采用词频分析的方法来进行破解，因为在现实情况中每个字母的使用频率是有很大的差异的。

在线工具：https://quipqiup.com/

维吉尼亚密码

维吉尼亚密码是使用一系列凯撒密码组成密码字母表的加密算法，属于多表密码的一种简单形式。这个密码号称是不可破解的密码，因为它密钥空间够大杜绝了普通计算机暴力破解的可能。

在破解时还是可以根据词频分析来尝试对密文进行破解

在线工具: https://www.guballa.de/vigenere-solver

在线工具: https://www.qqxiuzi.cn/bianma/weijiniyamima.php

现代密码

序列密码

序列密码也称为流密码，它是对称密码算法的一种。序列密码具有实现简单、便于硬件实施、加解密处理速度快、没有或只有有限的错误传播等特点。它模仿一次密码本的加密方式，但是密钥是伪随机的。伪随机的意思是实际上它并不能真正的随机出加密密钥，在实际加密中是利用密钥流产生器LFSR。

获取伪随机序列的常用方法是线性反馈移位寄存器。

分组密码

分组密码也可以称为块密码，将明文分成等长的块(如果位数不足则用0补齐)，然后对每一块进行加密操作。

DES加密

des对称加密，是一种比较传统的加密方式，其加密运算、解密运算使用的是同样的密钥，信息的发送者和信息的接收者在进行信息的传输与处理时，必须共同持有该密码（称为对称密码），是一种对称加密算法。

加密特点：分组长度为64比特；密钥长度为64比特（但只有56位有效）

AES加密

AES技术是一种对称的分组加密技术，使用128位分组加密数据，提供比WEP/TKIPS的RC4算法更高的加密强度。AES的加密码表和解密码表是分开的，并且支持子密钥加密，这种做法优于以前用一个特殊的密钥解密的做法。AES算法支持任意分组大小，初始时间快。特别是它具有的并行性可以有效地利用处理器资源。

加密特点：分组长度为128比特即16字节。而密钥长度为可选的，分别为128比特、192比特、256比特。

ECB工作模式

最简单的加密模式为电子密码本（Electronic Code Book, ECB）模式。需要加密的消息按照块密码的块大小被分为数个块，并对每个块进行独立加密。最后直接将密文串连起来。

CBC工作模式

1976年，IBM发明了密码分组链接（CBC，Cipher-block chaining）模式。在CBC模式中，每个明文块先与前一个密文块进行异或后，再进行加密。在这种方法中，每个密文块都依赖于它前面的所有明文块。同时，为了保证每条消息的唯一性，在第一个块中需要使用初始化向量。

加密特点：每个密文块都依赖于它前面的所有明文块，消除了明文统计特性。

填充攻击

Hash函数

哈希（Hash）函数也叫杂凑函数、散列函数，是将任意长度的消息 𝑚 转换成较短的、固定长度的哈希值 𝐻(𝑚) 的不需要密钥的不可逆的单向密码体制。

常见的HASH函数：MD5、SHA-1、SHA-256。

在Linux shadow文件的加密中域密码由三部分组成$id$salt$encrypted
ID为1时，采用MD5加密
ID为5时，采用SHA256加密
ID为6时，采用SHA512加密

常见的攻击方法暴力破解及彩虹币攻击(将所有已知的哈希值及明文存入数据库中)。彩虹表攻击在线地址 https://www.cmd5.com/

RSA加密

RSA公开密钥密码体制。所谓的公开密钥密码体制就是使用不同的加密密钥与解密密钥，是一种“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。RSA的安全性本质上是基于大数的因数分解，所以通过加密密钥来反推解密密钥在实际的情况中是行不通的。

密钥的生成：
1. 选择两个大素数 𝑝和𝑞,（𝑝≠𝑞，需要保密，步骤4以后建议销毁）
2. 计算𝑛=𝑝×𝑞，φ(𝑛) = (𝑝－1) × (𝑞－1)  #欧拉函数的计算
3. 选择整数 𝑒 满足 (φ(𝑛)，𝑒) = 1, 1 < 𝑒 <φ(𝑛)（一般取 65537）
4. 计算𝑑，使 𝑑 = 𝑒^-𝟏 𝑚𝑜𝑑 φ(𝑛),
   得到：公钥为{𝑒, 𝑛}； 私钥为{𝑑}
加密(用𝒆，𝒏)： 明文𝑀<𝑛， 密文𝐶 = 𝑀^𝑒(𝑚𝑜𝑑 𝑛)
解密(用𝒅，𝒏)： 密文𝐶， 明文 𝑀 = 𝐶^𝑑(𝑚𝑜𝑑 𝑛)

上面说过实际上RSA的安全性是基于大数的因数分解困难，在实际情况中我们可以利用工具暴力破解或者是利用在线工具查询已知大数的分解情况。

工具：yafu；在线工具：http://factordb.com/

总结

密码学分类

加密密钥是否相同？
- 加解密密钥相同 –> 对称密码
- 加解密密钥不同 –> 公钥密码(非对称密码)
- 无密钥 –> 哈希函数
安全性取决于？
- 加密算法的保密 –> 古典密码
- 取决于密钥的保密，算法公开 –> 现代密码

对密码学的攻击

暴力破解
统计分析
数学分析
侧信道攻击(物理方法)：

边信道攻击(side channel attack 简称SCA)，又称侧信道攻击:针对加密电子设备在运行过程中的时间消耗、功率消耗或电磁辐射之类的侧信道信息泄露而对加密设备进行攻击的方法被称为边信道攻击。这类新型攻击的有效性远高于密码分析的数学方法，因此给密码设备带来了严重的威胁。

练习题

凯撒相关

原题：

1	Jxyi yi oekh tqo.Jxyi yi oekh suburhqjyed., qdt jxu vbqw yi vv97v97t5t1ss32t9q5u62s2uu1t2v2s, ikrcyj myjx vbqw qdt {}

解密：

1 2	直接扔工具跑，位移16： this is your day.this is your celebration., and the flag is ff97f97d5d1cc32d9a5e62c2ee1d2f2c, submit with flag and {}

仿射密码

原题

1 2	achjbnpdfherebjsw hint: b=7

解密：

跑脚本，得到flag：flagisyouareright
##判断是否与26互素
def isPN(a):
    for num in range(2,a):
        if 0==a%num and 0==26%num:
            return False
    return True

##求得逆元a_
def get_a_(a):
    i=1
    while (1!=(i*a)%26):
        i=i+1
    return i


##解密函数
def decodeMstr(mStr,a_,b):
    yStr=""
    for Char in mStr:
        if Char>='A' and Char<='Z':
            Int=ord(Char)-ord('A')
            Int=((Int-b+26)*a_)%26
            yStr=yStr+chr(Int+ord('A'))
        elif Char>='a' and Char<='z':
            Int=ord(Char)-ord('a')
            Int=((Int-b+26)*a_)%26
            yStr=yStr+chr(Int+ord('a'))
        else:
            yStr=yStr+Char
    return yStr

mStr="achjbnpdfherebjsw"
for a in range(1,25,2):
    if False==isPN(a):
        continue
    else:
        a_=get_a_(a)
    for b in range(-10,10):
        yStr=decodeMstr(mStr,a_,b)
        print(yStr,end="\t")
        print(a,b)

DES

原题：

import pyDes
import base64
deskey = "********"
DES = pyDes.des(deskey)
DES.setMode('ECB')
DES.Kn = [
			[1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0],
			[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0], 
			[0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0],
			[1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1], 
			[0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1],
			[0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0],
			[0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0],
			[0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0],
			[0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0],
			[0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0],
			[0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1],
			[0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0],
			[1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0],
			[1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1],
			[1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1],
			[1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1]
		]
#cipher_list = base64.b64encode(DES.encrypt(mes))
cipher_list= "gAN5RT1XWKI0OyUayZj35SlKQ+if2PAJ"
#flag = mes+deskey

解题：

RSA

原题

from Crypto.Util.number import *
import gmpy2
import random
from flag import flag

p = getPrime(1024)
r = random.randint(2, 10)
e =65537
n=p**r
m=flag
assert(int(m.encode('hex'), 16) < n)
c = pow(int(m.encode('hex'), 16),e,n)
c=long_to_bytes(c)
print 'c =\n', c.encode('base64'),n


'''
c =
apxy3z3DgGnzaEedcUy3A49wAsqyyn9sqx6eYZL5iDrCq0Wjs8BOY2Ofza5wuaFigm32PVpO5jpu
Dgw9b6oX8KM2ZB9/dDmwQc7JKnAKhCQrIc1v9qt7iQbnTK0DTQj/xvQkz/IBeSjoWBmHOx4s0tDx
ZRAjOPui5wwAywNM3ynULEPczv+xN2v+6HBeoS2YuyfF5mq/pIAMPwZs+QpkuwxSbNQ6xPNP9Ox1
IeKz/41F7/D2fDsGB5CcFdAiQq+r95BhVeGzeaiQBpzwAXAPKIyO+fP6/M9XmpSJwjaMSiAUnksp
9KfVOXgEG9Z0FmxP6rgqPl0vU+rVeJ2RsTUYCSP8Vy+PD3PGwDDdUtNzvcEXKr2BKiNoOUxprBAt
yvcsmGqRLgDl1ZVgzSZ1U4MAmJ9x42mIU0XvolqaOCJZzaym1kJoBlw7/7+Nej4owEtan/c3TIkD
kr/gCenUD/8MSlvnfTUMGdQLkSht2BZiuiHxVVRVzY5ETG6v+w9AtDMC
4600616808891590817884946117009414083548013610469076381106568481948720521467073218024827360073980550620353792084520767372304347132535784875671026563160583598386773718586111034826555689602824563172463446924287072570386712719870348862904936370894695108302490867826094352072132696743116741635111860205049129717948520534270924834318704244999690532431941248905257880347561221151841978982240191397364038490250930604211256385925496658620755582058753376328583001312846508295319286941837220522563729215928111164274042890696771820759856790994461944209269732769269559257608440686713206622111649275898426040931301005711446055819707704086201357712959922814300067907536161841255533171805313149332383712997091780368142625499055149806043238057037400510197255364471685815004154357049874205884682322443391374020169114833722616851257895369648472048116320266548560787733764126281102645474252013714507014577620450816459153848279084910457288549191
'''

解题：

# Python 3.8
import base64
from libnum import n2s
p =
16631778300856146161980935433814936995552950080487778469613539444556283756439226
34783789967527660247694723110349300585359766249520227964497116507661553073595082
89724267180551758503427912271216717074610090283635131622612435152898135011648054
004511857955351506722712213877180074987292198905073222084609633471831
n = pow(p, 3)
phi_n = pow(p, 3)-pow(p, 2)
e = 65537
d = pow(e, -1, phi_n)
c =
"apxy3z3DgGnzaEedcUy3A49wAsqyyn9sqx6eYZL5iDrCq0Wjs8BOY2Ofza5wuaFigm32PVpO5jpuDgw
9b6oX8KM2ZB9/dDmwQc7JKnAKhCQrIc1v9qt7iQbnTK0DTQj/xvQkz/IBeSjoWBmHOx4s0tDxZRAjOPu
i5wwAywNM3ynULEPczv+xN2v+6HBeoS2YuyfF5mq/pIAMPwZs+QpkuwxSbNQ6xPNP9Ox1IeKz/41F7/D
2fDsGB5CcFdAiQq+r95BhVeGzeaiQBpzwAXAPKIyO+fP6/M9XmpSJwjaMSiAUnksp9KfVOXgEG9Z0Fmx
P6rgqPl0vU+rVeJ2RsTUYCSP8Vy+PD3PGwDDdUtNzvcEXKr2BKiNoOUxprBAtyvcsmGqRLgDl1ZVgzSZ
1U4MAmJ9x42mIU0XvolqaOCJZzaym1kJoBlw7/7+Nej4owEtan/c3TIkDkr/gCenUD/8MSlvnfTUMGdQ
LkSht2BZiuiHxVVRVzY5ETG6v+w9AtDMC"
c = int.from_bytes(base64.b64decode(c), byteorder='big')
m = pow(c, d, n)
print(n2s(m))

最短路径

原题：

以下是数行数据，每行第一个，第二个数字代表这条路的两个端点国家，第三个数字代表路途长度，最后一个字符串便是神秘代码。路在附件中~ 帮助救世主尼奥吧，他快被吓尿了。。。

1 2 100 FLAG{
2 3 87 AFQWE
2 4 57 ETKLS
2 5 50 WEIVK
2 6 51 AWEIW
3 7 94 QIECJF
3 8 78 QSXKE
3 9 85 QWEIH
4 13 54 WQOJF
4 14 47 KDNVE
4 15 98 QISNV
5 10 43 AEWJV
5 11 32 QWKXF
5 12 44 ASJVL
6 16 59 ASJXJ
6 17 92 QJXNV
6 18 39 SCJJF
6 23 99 SJVHF
7 19 99 WJCNF
8 20 96 SKCNG
9 20 86 SJXHF
10 21 60 SJJCH
11 21 57 SJHGG
12 22 47 SJCHF
14 10 55 EJFHG
16 17 59 ASJVH
18 12 53 SJFHG
18 24 93 SHFVG
21 22 33 SJFHB
19 25 88 ASHHF
20 25 96 SJVHG
22 25 23 SJVHJ
25 26 75 SDEV}

解题：

1
2
3

这是一道算法题，求最短路径。
由题最短路径的点为：1-2-5-12-22-25-26
FLAG{WEIVKSJCHFSJCHFSDEV}

Bu1'Blog

密码学基础

古典密码

凯撒密码

乘法密码

仿射密码

维吉尼亚密码

现代密码

序列密码

分组密码

DES加密

AES加密

ECB工作模式

CBC工作模式

填充攻击

Hash函数

RSA加密

总结

密码学分类

对密码学的攻击

练习题

凯撒相关

仿射密码

DES

RSA

最短路径