密码第六、七周_arth(q)

密码第六、七周

单向散列函数继续学习

哈希函数 y=h(x) ：
保证数据完整性
电子签名等认证方案的关键技术

应用：
检测消息完整性
提高数字签名的速度

Bitcoin
Proof of Work

哈希函数的属性
基本属性：
压缩性:应用于任意大小的数据块，产生定长的输出
有效性：对于给定的消息x，计算h(x)是容易的。
安全属性：


三种属性的强弱关系：
防 抗碰撞性 则防 抗原像和抗第二原像
攻 抗原像或抗第二原像 则攻 抗碰撞

哈希函数的通用攻击方法：
碰撞攻击：打破抗碰撞性。
生日攻击：

长度扩展攻击：
填充后产生的哈希函数与没有填充的相同

Multiple collisions:
将某些词（t处）进行同义词替换
可构造2^t种消息

特殊方法：针对不同的杂凑算法有不同的攻击方法。

哈希表：
封闭寻址法
开放寻址法

彩虹表攻击
常用密码的哈希值——>查找表
哈希加盐（一定程度上抵御彩虹表攻击）
盐：密码中加入的随机字符串
密文后加上盐，再计算哈希值。

应用：数据检索，密码保存，文件对比，数字签名，MAC，数字指纹

参考
【密码学03｜哈希函数】https://www.bilibili.com/video/BV1oY41197g4?vd_source=77e1fe7a7419fa7dbd62746624c75975

题

BJDCTF2020-编码与调制
hint: 曼彻斯特编码
曼彻斯特编码(Manchester)又称裂相码、同步码、相位编码，是一种用电平跳变来表示1或0的编码方法，其变化规则很简单，即每个码元均用两个不同相位的电平信号表示，也就是一个周期的方波，但0码和1码的相位正好相反。由于曼彻斯特码在每个时钟位都必须有一次变化，因此，其编码的效率仅可达到50%左右。

用Python脚本实现曼切斯特解码

import re

#十六进制转二进制
x="2559659965656A9A65656996696965A6695669A9695A699569666A5A6A6569666A59695A69AA696569666AA6"
b=bin(int(x,16))[2:]
print(b)
c=""

#曼切斯特编码解码
for i in re.findall(r".{2}","10010101011001011001011001100101100101011001010110101010011010011001010110010101101001100101100110100101101001011001011010011001101001010101100110100110101001011010010101101001101001100101010110100101100110011010100101101001101010011001010110100101100110011010100101100101101001010110100110100110101010011010010110010101101001011001100110101010100110"):
    if (i=="10"):
        c+="1"
    if (i=="01"):
        c+="0"
print(c)

#二进制转十六进制
c16=hex(int(c,2))[2:]
print(c16)

#十六进制转字符串
import libnum

flag=libnum.n2s(int(c16,16))
print(flag)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

妈呀，完了
一串二进制数字，转字符串
https://gchq.github.io/CyberChef/

妈呀—>玛雅，玛雅预言：20121221
AES密文特征与base64相似，但是需要注意AES几种不同的加密模式，以及引入了密钥
https://the-x.cn/cryptography/Aes.aspx

BJDCTF2020_easyrsa
题目

from Crypto.Util.number import getPrime,bytes_to_long
from sympy import Derivative
from fractions import Fraction
from secret import flag

p=getPrime(1024)
q=getPrime(1024)
e=65537
n=p*q
z=Fraction(1,Derivative(arctan(p),p))-Fraction(1,Derivative(arth(q),q))
m=bytes_to_long(flag)
c=pow(m,e,n)
print(c,z,n)
'''
output:
7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035
32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482
15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441

'''
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

现在的问题在于求得p.q
题目中只有

z=Fraction(1,Derivative(arctan(p),p))-Fraction(1,Derivative(arth(q),q))
1

一段与基本的RSA加密不同，需要理解这行代码的具体含义

arctan(p):反正切函数
arth(q):反双曲正切函数
Derivative():求导数
Derivative(arctan(p),p):求反正切函数在p点的导数
Fraction(x,y): x/y
1
2
3
4
5

关于Fraction函数：
1.接受一个参数，表示一个浮点数或字符串
2.接受两个参数，表示两数分别作分子分母相除
1
2
3

所以在这里对这个式子进行化简
$$Derivative(arctan(p),p)=\frac{1}{p^2+1}$$
$$Derivative(arth(q),q)=\frac{1}{1-q^2}$$
最终得到
$$Z=p^2+q^2$$

根据z的值可以求得p,q
$$Z=p^2+q^2=(p+q{)}^2-2pq=(p-q{)}^2+2pq$$
exp

import gmpy2
from Crypto.Util.number import *

c = 7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035
z = 32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482
n = 15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441

x = gmpy2.iroot(z + 2 * n, 2)[0]#元组解包
y = gmpy2.iroot(z - 2 * n, 2)[0]
e = 65537
p = (x + y) // 2
q = x - p
d = gmpy2.invert(e, (p - 1) * (q - 1))
print(long_to_bytes(pow(c, d, n)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14

也可以在线分解n得到p,q
套个普通的RSA脚本解密
exp

import libnum
import gmpy2

c =7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035
p =105909195259921349656664570904199242969110902804477734660927330311460997899731622163728968380757294196277263615386525795293086103142131020215128282050307177125962302515483190468569376643751587606016315185736245896434947691528567696271911398179288329609207435393579332931583829355558784305002360873458907029141
q =144564833334456076455156647979862690498796694770100520405218930055633597500009574663803955456004439398699669751249623406199542605271188909145969364476344963078599240058180033000440459281558347909876143313940657252737586803051935392596519226965519859474501391969755712097119163926672753588797180811711004203301
e =65537
n =15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441

phi_n=(p-1)*(q-1)
d=gmpy2.invert(e,phi_n)
m=pow(c,d,n)
print(m)
print(libnum.n2s(int(m)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14

我的木头啊
栅栏密码

'''
遍历所有可能的栏数，并得到加/解密结果
'''
s = 'c6_I_@t216MG_0q_Uf673JTYYzBXs{31QJmTTg=hw63XZFZiHho5GzE}'
factors = [fac for fac in range(2, len(s)) if len(s)%fac == 0] #取得密文长度的所有因数
for fac in factors:
    flag = ''
    for i in range(fac): #按一定的步长取几组字符，并连接起来，这里组数就等于步长数
        flag += s[i::fac]
    print(str(fac)+'栏：'+flag)

1
2
3
4
5
6
7
8
9
10
11

W型

'''
若知道栏数，则使用decode解密，若不知道，则使用crack_cipher遍历所有可能性
'''
def generate_w(string, n):
    '''将字符排列成w型'''
    array = [['.']*len(string) for i in range(n)] #生成初始矩阵
    row = 0
    upflag = False
    for col in range(len(string)): #在矩阵上按w型画出string
        array[row][col] = string[col]
        if row == n-1:
            upflag = True
        if row == 0:
            upflag = False
        if upflag:
            row -= 1
        else:
            row += 1
    return array

def encode(string, n):
    '''加密'''
    array = generate_w(string, n)
    msg = []
    for row in range(n): #将每行的字符连起来
        for col in range(len(string)):
            if array[row][col] != '.':
                msg.append(array[row][col])
    return array, msg

def decode(string, n):
    '''解密'''
    array = generate_w(string, n)
    sub = 0
    for row in range(n): #将w型字符按行的顺序依次替换为string
        for col in range(len(string)):
            if array[row][col] != '.':
                array[row][col] = string[sub]
                sub += 1
    msg = []
    for col in range(len(string)): #以列的顺序依次连接各字符
        for row in range(n):
            if array[row][col] != '.':
                msg.append(array[row][col])
    return array, msg

def crack_cipher(string):
    '''破解密码'''
    for n in range(2,len(string)): #遍历所有可能的栏数
        print(str(n)+'栏：'+''.join(decode(string, n)[1]))

if __name__ == "__main__":
    string = "c6_I_@t216MG_0q_Uf673JTYYzBXs{31QJmTTg=hw63XZFZiHho5GzE}"
    
    # n = 5 #栏数

    #若不知道栏数，则遍历所有可能
    crack_cipher(string)

    #若知道栏数
    # array,msg = decode(string, n)
    # # array,msg = encode(string, n)
    # for i in array: print(i)
    # print(''.join(msg))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

再加上base系列解密

年CTF_初一
Rabbit加密——高速流密码
特点：
1.26个英文字母构成
2.以U2FsdGVkX1开头
3.可能有=结尾。
http://www.jsons.cn/rabbitencrypt/
猜测密钥为2023
初五
http://cangjie.quchacha.com/

justshow
题目只给出了

hlcgoyfsjqknyifnpd:bcdefghijklmnopqrstuvwxyza
1

从冒号后面一段可以看出密文有经过移位一位的操作
复位后为

gkbfnxeripjmxhemoc:abcdefghijklmnopqrstuvwxyz
1

那么猜测冒号隔开的前面一段应该才是密文，后面一段或许是密钥。
这段密文只有小写字母，没有啥特殊字符
经过网上查找，是一个playfair密码
playfair密码
特点：密文为小写字母，且字母数一定为偶数
http://www.atoolbox.net/Tool.php?Id=912
加密方式：
1.编制密文表
2.明文两两分组
明文个数为奇数个：缺补，最后一个明文字母的后面补上其下一位字母
明文分组后同一组字母相同：同插，相同的字母中间插入其下一位字母
3.移位替换
若一组中的两个字母在同一行，对应密文是紧靠那两个字母右端的字母。
若在同一列，对应密文是紧靠下方的字母。
若不在同一行，不在同一列，则是由两个字母确定的矩形的反对角的字母。

解密就是逆向过程。

the dancing man

对照

伏羲六十四卦

打开得到一个加密脚本和一个文件，文件中给出密文和b=7
看密文与算卦相关，百度一下伏羲六十四卦

这个卦象与二进制相关，可以尝试将它转化为二进制。

s='升随临损巽睽颐萃小过讼艮颐小过震蛊屯未济中孚艮困恒晋升损蛊萃蛊未济巽解艮贲未济观豫损蛊晋噬嗑晋旅解大畜困未济随蒙升解睽未济井困未济旅萃未济震蒙未济师涣归妹大有'
dic={'坤': '000000', '剥': '000001', '比': '000010', '观': '000011', '豫': '000100', '晋': '000101', '萃': '000110', '否': '000111', '谦': '001000', '艮': '001001', '蹇': '001010', '渐': '001011', '小过': '001100', '旅': '001101', '咸': '001110', '遁': '001111', '师': '010000', '蒙': '010001', '坎': '010010', '涣': '010011', '解': '010100', '未济': '010101', '困': '010110', '讼': '010111', '升': '011000', '蛊': '011001', '井': '011010', '巽': '011011', '恒': '011100', '鼎': '011101', '大过': '011110', '姤': '011111', '复': '100000', '颐': '100001', '屯': '100010', '益': '100011', '震': '100100', '噬嗑': '100101', '随': '100110', '无妄': '100111', '明夷': '101000', '贲': '101001', '既济': '101010', '家人': '101011', '丰': '101100', '离': '101101', '革': '101110', '同人': '101111', '临': '110000', '损': '110001', '节': '110010', '中孚': '110011', '归妹': '110100', '睽': '110101', '兑': '110110', '履': '110111', '泰': '111000', '大畜': '111001', '需': '111010', '小畜': '111011', '大壮': '111100', '大有': '111101', '夬': '111110', '乾': '111111'}
li=[]
k=0
for i in range(len(s)):
    if k ==1:
        k=0
        continue
    try:
        li.append(dic[s[i]])
    except:
        t=''
        t=t+s[i]+s[i+1]
        li.append(dic[t])
        k=1
ss=''.join(li)
print(ss)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

二进制转字符串

enc=''
for i in range(0,len(ss),8):
    enc+=chr(eval('0b'+ss[i:i+8]))
print(enc)
1
2
3
4

结果是

bl1oXF1ra2FbW2VpV1dfUmBiT11dYE5NVVdXSUZYSFVDUA==
1

两个==，尝试base64解密

import base64
x=base64.b64decode(enc).decode()
print(x)
1
2
3

得到

n]h\]kka[[eiWW_R`bO]]`NMUWWIFXHUCP
1

看来还是需要看看题目给出的加密脚本

# -- coding:UTF-8 --
from secret import flag

def encrpyt5():
    enc=''
    for i in flag:
        enc+=chr((a*(ord(i)-97)+b)%26+97) #b=7
    return(enc)

def encrypt4():
    temp=''
    offset=5
    for i in range(len(enc)):
        temp+=chr(ord(enc[i])-offset-i)
    return(temp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

逆过程解密

exp

#decrypt4
def decrypt4(enc):
    temp=''
    offset=5
    for i in range(len(enc)):
        temp+=chr(ord(enc[i])+offset+i)#减变加
    return temp
#decrypt5
def decrypt5(flag):
	#爆破a
    for a in range(1,200):
        enc = ''
        for i in flag:
        	#爆破k
            for k in range(200):
                 if (ord(i) - 97 - 7+26*k)%a==0:
                    enc+= chr((ord(i) - 97 - 7 + 26 * k) // a + 97)
                    break
        print(enc)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

飞鸽传书
一大段密文，=，base64一次

MWIwOGFmMjc2ZGJjNzU5MzI3MWY0ZWU2MTYyODkzMjQlMEFlMmFlM2EyMzUwNzQzYzUxNmNkYTQxMjQ5OWJhM2JlOSUwQWJkZTUyY2IzMWRlMzNlNDYyNDVlMDVmYmRiZDZmYjI0JTBBZTIzZTAwYmUzOWQzNmYzNDYyZTU3NmE2N2E3ZjkxOTklMEExOGM3OTI4NWI1MTRjNjNmYzkwMzVlM2Y5MjBhZTQ3NyUwQWRhNDRkZDE5MmRlZmQxYmU3OWY2M2MzNTBkMjkyMGNmJTBBNDI1MWM0YzY0OWM3ZDJmODYzMjdlZmRlMjM5OTJmYTclMEFhYWU3YjJkNDgyMzgyYWFhZDc1ZmRlNjRkZjhmZjg2ZiUwQTI5NmY3ZmZjMmU0NTQ1ZGM3NzkyMDUwY2ViNGE4NzExJTBBNjEwN2FjMWE1NWYxZTBmZWNiN2RkYjYwZmIzYmYxMDklMEFhZWMyMzMzMzIxZDczMDAwMTYxNjgyZDNjNGViYzAwOSUwQTUwMDViM2JmMDAwNTBiZjRmN2U0M2FjMzNhMDQ1NGI4JTBB
1

还是有大写字母有小写字母有数字，尝试再来一次base64

1b08af276dbc7593271f4ee616289324%0Ae2ae3a2350743c516cda412499ba3be9%0Abde52cb31de33e46245e05fbdbd6fb24%0Ae23e00be39d36f3462e576a67a7f9199%0A18c79285b514c63fc9035e3f920ae477%0Ada44dd192defd1be79f63c350d2920cf%0A4251c4c649c7d2f86327efde23992fa7%0Aaae7b2d482382aaad75fde64df8ff86f%0A296f7ffc2e4545dc7792050ceb4a8711%0A6107ac1a55f1e0fecb7ddb60fb3bf109%0Aaec2333321d73000161682d3c4ebc009%0A5005b3bf00050bf4f7e43ac33a0454b8%0A
1

这次不太一样了，看到了很多%0，应该是一种编码方式，找了一下

http://www.jsons.cn/urlencode/
解码得到

1b08af276dbc7593271f4ee616289324
e2ae3a2350743c516cda412499ba3be9
bde52cb31de33e46245e05fbdbd6fb24
e23e00be39d36f3462e576a67a7f9199
18c79285b514c63fc9035e3f920ae477
da44dd192defd1be79f63c350d2920cf
4251c4c649c7d2f86327efde23992fa7
aae7b2d482382aaad75fde64df8ff86f
296f7ffc2e4545dc7792050ceb4a8711
6107ac1a55f1e0fecb7ddb60fb3bf109
aec2333321d73000161682d3c4ebc009
5005b3bf00050bf4f7e43ac33a0454b8
1
2
3
4
5
6
7
8
9
10
11
12

八组32位密文，数字加小写字母
神奇的MD5
http://www.ttmd5.com/

一封信

有关Emoji的加密：
base100, http://www.atoolbox.net/Tool.php?Id=936
emoji-aes,需要密钥 https://emoji-aes.miaotony.xyz/
codemoji, 需要密钥 https://learning.mozilla.org/codemoji/#/encrypt
Emoji表情符号编码/解码, http://www.atoolbox.net/Tool.php?Id=937

这道题是emoji-aes，密钥是题目上提示的mooncake