word in the first

记录我遇到的一些题

crypto-exercise

i春秋第二届春秋欢乐赛RSA256

题目是给了四个文件

encrypted.message1

encrypted.message2

encrypted.message3

还有 public.key

这时候可以想到openssl

其中

1
2
3

Exponent = 65537
N = 0xD99E952296A6D960DFC2504ABA545B9442D60A7B9E930AFF451C78EC55D555EB
    (98432079271513130981267919056149161631892822707167177858831841699521774310891)

分解一下factordb.com

1
2
3

p=302825536744096741518546212761194311477

q=325045504186436346209877301320131277983

exp:

import gmpy2
import rsa
p=302825536744096741518546212761194311477
q=325045504186436346209877301320131277983
n=98432079271513130981267919056149161631892822707167177858831841699521774310891
e=65537
d=int(gmpy2.invert(e,(p-1)*(q-1)))

privatekey = rsa.PrivateKey(n,e,d,p,q)
with open("encrypted.message1","rb") as f:
    print(rsa.decrypt(f.read(),privatekey).decode())

with open("encrypted.message2","rb") as f:
    print(rsa.decrypt(f.read(),privatekey).decode())

with open("encrypted.message3","rb") as f:
    print(rsa.decrypt(f.read(),privatekey).decode())

2017第二届广东省强网杯线上赛-SimpleMath

题目源码如下：

from Crypto.Util.number import *
from hashlib import md5

flag = "xxx"
assert len(flag) == 15
pad = bytes_to_long(md5(flag).digest())

hack = 0

for char in flag:
	hack *= ord(char)
	hack += pad
	
print hack
# hack = 280098481791453837177137197730537158171743673148935867304957882116
# flag = "flag{" + flag + "}"

定义flag的长度为15位

1	assert len(flag) == 15

定义pad为md5加密值，所以pad的长度为32位，那么其比特位为120-128位

1	pad = bytes_to_long(md5(flag).digest())

加密过程

1
2
3

for char in flag:
	hack *= ord(char)
	hack += pad

这个加密过程如下：

hack0=0
hack1=hack0*f1+pad=pad
hack2=hack1*f2+pad=pad*(f2+1)
hack3=hack2*f3+pad=pad*(f3*f2+f3+1)
hack4=hack3*f4+pad=pad*(f4*f3*f2+f4*f3+f4+1)
....
....
hack15=..=pad*(f15*..*f3*f2+f15*..*f4*f3+..+f15+1)

hack15即最后的加密结果,hack15可以看做是pad和某个整数的相乘结果：

当我们将hack进行因式分解：

1	2,2,19,31,59,97,127,3727,44948980991,1753609692783577883,556795634058750798159011

所以pad为这12个因子中某些个因子的相乘结果，又由于pad为md5加密的结果。所以其比特位120-128之间。这样子我们可以爆破获得几个符合条件的pad

，有如下等式：

1	hack/pad=f15..f3f2+f15..f4f3+..+f15+1

故而有：

1	(hack/pad)-1=f15..f3f2+f15..f4f3+..+f15

由于f1至f15为可见字符，所以其ascii值的取值为32-127。

这个等式将会满足：

1	[(hack/pad)-1]%f15=0

以及

1
2
3

[[(hack/pad)-1]/f15-1]%f14=0
[[[(hack/pad)-1]/f15-1]/f14-1]%f13=0
....

解密exp如下：

# -*- coding:utf-8 -*-
import itertools
from hashlib import md5
hack=280098481791453837177137197730537158171743673148935867304957882116
dic=[2,2,19,31,59,97,127,3727,44948980991,1753609692783577883,556795634058750798159011]


def result1(arr):#获得每一个组合结果中数字的相乘结果
    source = 1
    for i in arr:
        source *= i
    return source    
        

def f2(a,b,s,n):
    if a//b-1 in range(32, 127):
        s = s+chr(a//b-1)
        if len(s)==14:
            checkMD5(s[::-1],n)        
        
    for c in range(32,127):
        if (a//b-1)%c==0:
            f2(a//b-1,c,s+chr(c),n)

def checkMD5(s,n):
     for c in range(32,127):
         t= chr(c)+s
         if int.from_bytes(md5(t.encode('utf-8')).digest(),byteorder='big')==n:
             print(t)


for i in range(1,12):
    for j in list(itertools.combinations(dic,i)):#将这些数字进行组合
        tmp = result1(j)
        if tmp.bit_length() in range(120,129):
            f2(hack,tmp,'',tmp)

算法的优势在于合理利用了递归算法。