tyc的小窝
0%

密码学

Posted on Edited on

古典密码

1.猪圈密码（buu萌哒哒的八戒）

2.MD5

（1）buu获得权限的第一步Administrator:500:806EDC27AA52E314AAD3B435B51404EE:F4AD50F57683D4260DFD48AA351A17A8:::

将F4AD50F57683D4260DFD48AA351A17A8MD5解密即可

（2）丢失的MD5

题目中给的代码

1
2
3
4
5
6
7
8
9
import hashlib   
for i in range(32,127):
    for j in range(32,127):
        for k in range(32,127):
            m=hashlib.md5()
            m.update('TASC'+chr(i)+'O3RJMV'+chr(j)+'WDJKX'+chr(k)+'ZM')
            des=m.hexdigest()
            if 'e9032' in des and 'da' in des and '911513' in des:
                print des

修改后的代码

1
2
3
4
5
6
7
8
9
10
11
import hashlib
for i in range(32,127)：
	for j in range(32,127)：
		for k in range(32,127)：
			m = hashlib.md5()
			s = 'TASC' + chr(i) + 'O3RJMV' +chr(j) +'WDJKX' +chr(k) + 'ZM'
			m.update(s.encode("utf8"))
			des = m.hexdigest()
			if 'e9032' in des and 'da' in des and '911513' in des:
				print(des)
				break

2.栅栏密码

特征U2开头需要密钥，一种流加密
把要加密的明文分成N个一组，然后把每组的第一个字连起来，形成一段无规律的话。
不过栅栏密码本身有一个潜规则，就是组成栅栏的字母一般不会太多。
参考
加密原理
举例：
n = 7, m = 2
假设明文为：have a good night
加密过程如下：
将其去掉空格：haveagoodnight
分成7组：ha ve ag oo dn ig ht
ha
ve
ag
oo
dn
ig
ht
按照竖排来组合，则它的栅栏密码为：hvaodihaegongt
解密过程如下：
先将其分为2组：hvaodih aegongt
hvaodih
aegongt
然后按照每组按次序取一个进行重新组合：ha ve ag oo dn ig ht
拼起来即可：haveagoodnight
添加上必需的空格即可：have a good night

3.中文电码

606046152623600817831216121621196386

中文电码采用了四位阿拉伯数字作代号，
从0001到9999按四位数顺序排列，用四位数字表示最多一万个汉字、字母和符号。
汉字先按部首，后按笔划排列。
字母和符号放到电码表的最尾。
后来由于一万个汉字不足以应付户籍管理的要求，又有第二字面汉字的出现。
在香港，两个字面都采用同一编码，由输入员人手选择字面；
在台湾，第二字面的汉字会在开首补上“1”字，变成5个数字的编码。

现代密码

rsa

rsa算法简介

RSA是公钥密码体制，是一种使用不同加密密钥与解密密钥的解密方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
选择两个大素数p和q，计算出模数N = p*q
计算φ(n) = （p-1) * (q-1)即N的欧拉函数，然后选择一个e(1<e<φ(n)),且e和φ(n)互素

取e的模反数为d（逆元），计算方法：e * d ≡ 1(mod φ(n))

对明文进行加密： c = m^e%N
c = pow(m,e,N),得到c即为密文

对密文c进行解密 ：m = c^d%N
m = pow(c,d,N),得到的m即为明文

其中：
	p 和 q ：大整数N的两个因子
	N      ：大整数N，我们称之为模数
	e 和 d ：互为模反的两个指数
	c 和 m ：分别是密文和明文，这里一般指的是一个十进制的数

rsa算法原理

欧拉函数φ(n)

欧拉函数φ(n)的定义是小于n的自然数中与n互质的数的个数

任何一个素数p的欧拉函数就是 p-1

欧拉定理

若n,a为正整数，且n,a互质，gcd（n,a）= 1 , 则:a^φ(n)≡1 mod n

费马小定理

模运算
模运算与基本四则运算有些相似，但是除法除外。其规则如下：

(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
a ^ b % p = ((a % p) ^ b) % p
结合律
((a + b) % p + c) = (a + (b + c) % p) % p
((a * b) % p * c) = (a * (b * c) % p) % p
交换律
(a + b) % p = (b + a) % p
(a * b) % p = (b * a) % p
分配律
(a + b) % p = (a % p + b % p) % p
((a + b) % p * c) % p = ((a * c) % p + (b * c) % p
重要定理
若 a ≡ b (mod p)，则对于任意的 c，都有(a + c) ≡ (b + c) (mod p)
若 a ≡ b (mod p)，则对于任意的 c，都有(a * c) ≡ (b * c) (mod p)
若 a ≡ b (mod p)，c ≡ d (mod p)，则
(a + c) ≡ (b + d) (mod p)
(a - c) ≡ (b - d) (mod p)
(a * c) ≡ (b * d) (mod p)
(a / c) ≡ (b / d) (mod p)
逆元
a mod p的逆元便是可以使 a * a’ mod p = 1 的最小a’。

推导过程

式1：c=m^e%N
式2：m=c^d%N

将式1带入式2 得 m = (m ^ e % N ) ^ d % N

需要证明：m == ( m ^ e % N ) ^ d % N

(m^e%N)^d%N

=> (m^e)^d%N #模运算 a ^ b % p = ((a % p) ^ b) % p

m^(e*d)%N #幂的乘方，底数不变，指数相乘
将 e * d ≡ 1 (mod φ(N)) 即 e * d = K * φ(N) + 1，K为任意正整数，代入得：

=> (m^(K*φ(N)+1))%N

=> (m^(K*φ(N)*m^1)%N # 同底数相乘，指数相加

=> (m^(K*φ(N)*m)%N

=> ((m^φ(N)^K%N*m)%N # 幂的乘方，底数不变，指数相乘

=> ((m^φ(N)^K%N*m%N)%N # (a * b) % p = (a % p * b % p) % p

=> ((m^φ(N)%N)^K%N*m%N)%N # a ^ b % p = ((a % p) ^ b) % p

=> (1^K%N*m%N)%N # 根据欧拉定理：a^φ(n)≡1 mod n 即 a^φ(n) mod n = 1

=> (m%N)%N # 1^K%N=1

=> (m%N)%N

=> (m%N)^1%N

=> (m^1)%N # a ^ b % p = ((a % p) ^ b) % p

=> m%N

m #因为 m < N

Crypto.PublicKey模块公私钥读取与生成

公钥生成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.PublicKey import RSA

p= 787228223375328491232514653709
q= 814212346998672554509751911073
n= 640970939378021470187479083920100737340912672709639557619757
d= 590103645243332826117029128695341159496883001869370080307201
e= 65537


rsa_components = (n, e)
keypair = RSA.construct(rsa_components)
with open('pubckey.pem', 'wb') as f :
    f.write(keypair.exportKey())


私钥生成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.PublicKey import RSA

p= 787228223375328491232514653709
q= 814212346998672554509751911073
n= 640970939378021470187479083920100737340912672709639557619757
d= 590103645243332826117029128695341159496883001869370080307201
e= 65537


rsa_components = (n,e,d,p,q)
keypair = RSA.construct(rsa_components)
with open('private1.pem', 'wb') as f :
    f.write(keypair.exportKey())


公钥求读取

1
2
3
4
5
6
7
from Crypto.PublicKey import RSA

path = '<key file path here>'
with open(path) as f:
    key = RSA.import_key(f.read())
    print('e = %d' % key.e)
    print('n = %d' % key.n)

私钥读取

1
2
3
4
5
6
7
8
9
10
from Crypto.PublicKey import RSA
with open("private1.pem","rb") as f:
    key = RSA.import_key(f.read())
    print('n = %d' % key.n)
    print('e = %d' % key.e)
    print('d = %d' % key.d)
    print('p = %d' % key.p)
    print('q = %d' % key.q)


rsa模块公私钥读取与生成

公钥生成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import rsa

p= 787228223375328491232514653709
q= 814212346998672554509751911073
n= 640970939378021470187479083920100737340912672709639557619757
d= 590103645243332826117029128695341159496883001869370080307201
e= 65537

pubkey = rsa.PublicKey(n , e )
print(pubkey)
pub=rsa.PublicKey.save_pkcs1(pubkey)
with open("pub.pem","wb") as f:
    f.write(pub)

私钥生成

1
2
3
4
5
6
7
8
9
10
11
12
13
import rsa

p= 787228223375328491232514653709
q= 814212346998672554509751911073
n= 640970939378021470187479083920100737340912672709639557619757
d= 590103645243332826117029128695341159496883001869370080307201
e= 65537
prikey = rsa.PrivateKey(n , e , d , p , q)
print(prikey)
pri=rsa.PrivateKey.save_pkcs1(prikey)
with open("pri.pem","wb") as f:
    f.write(pri)

公钥读取

1
2
3
4
5
6
7
8
import rsa
with open('2.pem','rb') as f:
    keydata= f.read()
pubckey = rsa.PublicKey.load_pkcs1(keydata)
#pubckey = rsa.PublicKey.load_pkcs1_openssl_pem(keydata)
print(pubckey.n)
print(pubckey.e)

私钥读取

1
2
3
4
5
6
7
8
9
10
import rsa
with open('1.pem','rb') as f:
    keydata= f.read()
pubckey = rsa.PrivateKey.load_pkcs1(keydata)
print(pubckey.n)
print(pubckey.e)
print(pubckey.d)
print(pubckey.q)
print(pubckey.p)

题目

随机生成flag

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import random
import hashlib
import string

#字符串列表
a=string.printable
#随机生成flag
for i in range(10):
    flag = ""
    for i in range(10):
        flag += a[random.randint(0, 99)]
    flag = hashlib.md5(flag.encode()).hexdigest()
    print("flag{" + flag + "}")


基于N分解的题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import libnum
import gmpy2
from Crypto.PublicKey import RSA

p=libnum.generate_prime(1024)
#下一个素数
q=int(gmpy2.next_prime(p))
e=65537
m="flag{a272722c1db834353ea3ce1d9c71feca}"
m=libnum.s2n(m)
n=p*q
c=pow(m,e,n)
flag_c=libnum.n2s(c)
rsa_components = (n, e)
keypair = RSA.construct(rsa_components)
with open('pubckey1.pem', 'wb') as f :
    f.write(keypair.exportKey())
with open("flag.txt","wb") as f:
    f.write(flag_c)


解题脚本

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
import libnum
import gmpy2
from Crypto.PublicKey import RSA


def isqrt(n):
  x = n
  y = (x + n // x) // 2
  while y < x:
    x = y
    y = (x + n // x) // 2
  return x

def fermat(n, verbose=True):
    a = isqrt(n) # int(ceil(n**0.5))
    b2 = a*a - n
    b = isqrt(n) # int(b2**0.5)
    count = 0
    while b*b != b2:
        # if verbose:
        #     print('Trying: a=%s b2=%s b=%s' % (a, b2, b))
        a = a + 1
        b2 = a*a - n
        b = isqrt(b2) # int(b2**0.5)
        count += 1
    p=a+b
    q=a-b
    assert n == p * q
    # print('a=',a)
    # print('b=',b)
    # print('p=',p)
    # print('q=',q)
    # print('pq=',p*q)
    return p, q


with open("pubckey1.pem","rb") as f:
    key = RSA.import_key(f.read())
    n=key.n
    e=key.e

with open("flag.txt","rb") as f:
    c=f.read()
    c=libnum.s2n(c)
    
#费马分解,
n1=fermat(n)
p=n1[0]
q=n1[1]
phi_n=(p-1)*(q-1)
#求逆元
d=libnum.invmod(e,phi_n)
m=pow(c,d,n)
print(m)
print(libnum.n2s(int(m)).decode())


已知p q dp dq c求密文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
p=
q=
dp=
dq=

import gmpy2
I = gmpy2.invert(q,p)
mp = pow(c,dp,p)
mq = pow(c,dq,q)               #求幂取模运算

m = (((mp-mq)*I)%p)*q+mq       #求明文公式

print(hex(m))          #转为十六进制


dp泄露

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import gmpy2 as gp

e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657

c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751


for i in range(1,e):                   #在范围(1,e)之间进行遍历
    if(dp*e-1)%i == 0:
        if n%(((dp*e-1)//i)+1) == 0:   #存在p，使得n能被p整除
            p=((dp*e-1)//i)+1
            q=n//(((dp*e-1)//i)+1)
            phi=(q-1)*(p-1)            #欧拉定理
            d=gp.invert(e,phi)         #求模逆
            m=pow(c,d,n)               #快速求幂取模运算
           
print(m)                               #10进制明文
print('------------')
print(hex(m)[2:])                      #16进制明文
print('------------')
print(bytes.fromhex(hex(m)[2:]))       #16进制转文本

共模攻击

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
import libnum 
from gmpy2 import invert
# 欧几里得算法
def egcd(a, b):
  if a == 0:
    return (b, 0, 1)
  else:
    g, y, x = egcd(b % a, a)
    return (g, x - (b // a) * y, y)

def main():
  n = 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
  c1 = 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
  c2 = 18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
  e1 = 11187289
  e2 = 9647291
  s = egcd(e1, e2)
  s1 = s[1]
  s2 = s[2]
  # 求模反元素
  if s1<0:
    s1 = - s1
    c1 = invert(c1, n)
  elif s2<0:
    s2 = - s2
    c2 = invert(c2, n)

  m = pow(c1,s1,n)*pow(c2,s2,n) % n
  print (libnum.n2s(m))

if __name__ == '__main__':
  main()

低加密指数攻击：

所谓低加密指数指的就是e非常小的情况下，通常为3。
这种题目通常有两种类型，一种直接爆破，另外一种是低指数广播攻击。

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


from gmpy2 import iroot
import libnum
n = 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793

c = 0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365

k = 0
while 1:
    res=iroot(c+k*n,3)   //iroot()，该函数的作用是计算一个数的整数平方根
    if(res[1]==True):
        print(libnum.n2s(int(res[0])))
        break
    k=k+1


'''
第二种写法


import gmpy2 
from libnum import*
n = 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793
c = 0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365

i = 0
while 1:
    if(gmpy2.iroot(c+i*n,3)[1]==1):     #开根号
        print(gmpy2.iroot(c+i*n,3))
        break
    i=i+1

'''