汇总CTF常见加密算法的解密脚本

XXtea

具体可以查看这篇博客

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
#include <iostream>
#include <stdio.h>
 
using namespace std;
 
#include <stdint.h>
#define DELTA 0x9e3779b9
#define MX (((z>>5^y<<2) + (y>>3^z<<4)) ^ ((sum^y) + (key[(p&3)^e] ^ z)))
 
  void btea(uint32_t *v, int n, uint32_t const key[4]) {
    uint32_t y, z, sum;
    unsigned p, rounds, e;
    if (n > 1) {          /* Coding Part */
      rounds = 6 + 52/n;
      sum = 0;
      z = v[n-1];
      do {
        sum += DELTA;
        e = (sum >> 2) & 3;
        for (p=0; p<n-1; p++) {
          y = v[p+1];
          z = v[p] += MX;
        }
        y = v[0];
        z = v[n-1] += MX;
      } while (--rounds);
    } else if (n < -1) {  /* Decoding Part */
      n = -n;
      rounds = 6 + 52/n;
      sum = rounds*DELTA;
      y = v[0];
      do {
        e = (sum >> 2) & 3;
        for (p=n-1; p>0; p--) {
          z = v[p-1];
          y = v[p] -= MX;
        }
        z = v[n-1];
        y = v[0] -= MX;
      } while ((sum -= DELTA) != 0);
    }
  }
 
int main()
{
    uint32_t const key[4]={0x01234567,0x89ABCDEF,0xFEDCBA98,0x76543210};
    uint32_t data[3]={0x12345678,0x87654321,0x13579243};
    uint32_t *sent=data;
    btea(sent,3,key);
    printf("coded:%x  %x  %x \n",sent[0],sent[1],sent[2]);
    btea(sent,-3,key);
    printf("decoded:%x  %x  %x \n",sent[0],sent[1],sent[2]);
    return 0;
}

例题1：eztea

解这种题目的时候要注意轮回次数以及递增变量大小

解密脚本：

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
#include <iostream>
#include <stdio.h>
 
using namespace std;
 
#include <stdint.h>
#define DELTA 0x61C88647
#define MX (((z>>5^y<<2) + (y>>3^z<<4)) ^ ((sum^y) + (key[(p&3)^e] ^ z)))
 
  void btea(uint32_t *v, int n, uint32_t const key[4]) {
    uint32_t y, z, sum;
    unsigned int p, rounds, e;
    if (n > 1) {          /* Coding Part */
      rounds = 172;
      sum = 0;
      z = v[n-1];
      do {
        sum = (sum - DELTA) & 0xFFFFFFFF;
        e = (sum >> 2) & 3;
        for (p=0; p<n-1; p++) {
          y = v[p+1];
          z = v[p] += MX;
        }
        y = v[0];
        z = v[n-1] += MX;
      } while (--rounds);
    } else if (n < -1) {  /* Decoding Part */
      n = -n;
      rounds = 172;
      sum = (rounds*-DELTA) & 0xFFFFFFFF;
      y = v[0];
      do {
        e = (sum >> 2) & 3;
        for (p=n-1; p>0; p--) {
          z = v[p-1];
          y = v[p] -= MX;
        }
        z = v[n-1];
        y = v[0] -= MX;
      } while ((sum = (sum+DELTA)&0xFFFFFFFF) != 0);
    }
  }
 
int main()
{
    uint32_t const key[4]={4660,22136,37155,17767};
    uint32_t data[4]={1332370953,2931878637,776785408,4020115239};
    uint32_t *sent=data;
    printf("before:%x  %x  %x  %x\n",sent[0],sent[1],sent[2],sent[3]);
    btea(sent,-4,key);
    printf("decoded:%x  %x  %x  %x\n",sent[0],sent[1],sent[2],sent[3]);
    btea(sent,4,key);
    printf("encoded:%x  %x  %x  %x\n",sent[0],sent[1],sent[2],sent[3]);

    return 0;
}

例题2 2022-DefCampCTF-cup_of_tea

RC4

原理请查看这里

例题1 GUET-CTF2019-encrypt

例题2 2021CISCN-glass

下面给出c实现RC4加密解密代码

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
66
67
68
69
70
71
72
#include <stdio.h>
#include <stdlib.h>

void rc4_init(unsigned char*s,unsigned char*key,unsigned long len)
{
    int i=0;
    int j=0;
    unsigned char k[256]={};
    unsigned char temp = 0;
    for(i=0;i<256;i++)
    {
        s[i]=i;         //0-255赋给s
        k[i]=key[i%len];   //将k重新计算
    }
    for(i=0;i<256;i++)
    {
        j=(j+s[i]+k[i])%256;    //给j赋值
        temp=s[i];
        s[i]=s[j];
        s[j]=temp;    //s[i]和s[j]交换
    }
}

void rc4_crypt(unsigned char*s,unsigned char*data,unsigned long len)
{
    int i=0,j=0,t=0;
    unsigned long k=0;
    unsigned char temp;
    for(k=0;k<len;k++)
    {
        i=(i+1)%256;            //固定方式生成的i
        j=(j+s[i])%256;          //固定方式生成的j
        temp=s[i];
        s[i]=s[j];
        s[j]=temp;             //交换s[i]和s[j]
        t=(s[i]+s[j])%256;      //固定方式生成的t
        data[k]^=s[t];          //来作为s的下标和data进行异或运算
    }
}

int main()
{
    unsigned char s[256]={0};
    int i=0,j=0;
    char key[256] = "12345678";
    unsigned char data[512]={0xA3, 0x1A, 0xE3, 0x69, 0x2F, 0xBB, 0x1A, 0x84, 0x65, 0xC2, 0xAD, 0xAD, 0x9E, 0x96, 0x05, 0x02,0x1F, 0x8E, 0x36, 0x4F, 0xE1, 0xEB, 0xAF, 0xF0, 0xEA, 0xC4, 0xA8, 0x2D, 0x42, 0xC7, 0x6E, 0x3F,0xB0, 0xD3, 0xCC, 0x78, 0xF9, 0x98, 0x3F, 0x00};
    
    unsigned long data_len = 39;
    unsigned long key_len = 8;
    for(i=0;i<39;i+=key_len)
    {
        for (j = 0; (key_len & ~(key_len >> 31)) != j && i + j < 39; ++j)
        {
            data[i+j] = data[i+j] ^ key[j];
        }
    }
    for(i=0;i<data_len;i+=3)
    {
        //向右循环回去
        data[i+1] = data[i] ^ data[i+1];
        data[i+2] = data[i+1] ^ data[i+2];
        data[i] = data[i+2] ^ data[i];
    }
    rc4_init(s,(unsigned char*)key,key_len);//初始化得到s
    rc4_crypt(s,(unsigned char*)data,data_len);//解密
    for(i=0;i<39;i++)
    {
        printf("%c",data[i]);
    }
    return 0;
}

LCG(线性同余生成器)

我们设置增量为b，乘数为a，模数为n，seed随机产生，Si为产生的随机数项数

s0 = (a * seed + b) % n

s1 = (a * s0 + b) % n

……

原理实现可以查看这篇博客

ezLCG

seed是随机产生的，需要输入四个正确的seed值。四个challenge对应四个不同的类型，正好可以用这题来学习一下，解密代码来自Facker007师傅。

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
import os
import hashlib
from string import ascii_letters
from Crypto.Util.number import *
from Crypto.Random.random import randrange, getrandbits, choice

from flag import flag

class LCG(object):
    def __init__(self, seed):
        # 产生一个256位二进制素数
        self.N = getPrime(256)
        # 在N范围内随机产生两个数
        self.a = randrange(self.N)
        self.b = randrange(self.N)
        # seed = seed%N
        self.seed = seed % self.N
        self.state = self.seed

    # self.state = (a * seed + b)% N
    def next(self):
        self.state = (self.a * self.state + self.b) % self.N
        return self.state

def challenge1():
    print("This is the challenge1")
    init_seed = getrandbits(256)
    lcg = LCG(init_seed)
    print("lcg.a="+str(lcg.a))
    print("lcg.b="+str(lcg.b))
    print("lcg.N="+str(lcg.N))
    print("lcg.num1="+str(lcg.next()))
    seed1 = int(input("lcg.seed = "))
    if seed1 != lcg.seed:
        print("worry")
        exit(0)
    print("success!")

def challenge2():
    print("This is the challenge2")
    init_seed = getrandbits(256)
    lcg = LCG(init_seed)
    print("lcg.a="+str(lcg.a))
    print("lcg.N="+str(lcg.N))
    print("lcg.num1="+str(lcg.next()))
    print("lcg.num2="+str(lcg.next()))
    seed1 = int(input("lcg.seed = "))
    if seed1 != lcg.seed:
        print("worry")
        exit(0)
    print("success!")

def challenge3():
    print("This is the challenge3")
    init_seed = getrandbits(256)
    lcg = LCG(init_seed)
    print("lcg.N="+str(lcg.N))
    print("lcg.num1="+str(lcg.next()))
    print("lcg.num2="+str(lcg.next()))
    print("lcg.num3="+str(lcg.next()))
    seed1 = int(input("lcg.seed = "))
    if seed1 != lcg.seed:
        print("worry")
        exit(0)
    print("success!")

def challenge4():
    print("This is the challenge4")
    init_seed = getrandbits(256)
    lcg = LCG(init_seed)
    print("lcg.num1="+str(lcg.next()))
    print("lcg.num2="+str(lcg.next()))
    print("lcg.num2="+str(lcg.next()))
    print("lcg.num2="+str(lcg.next()))
    print("lcg.num2="+str(lcg.next()))
    print("lcg.num2="+str(lcg.next()))
    seed1 = int(input("lcg.seed = "))
    if seed1 != lcg.seed:
        print("worry")
        exit(0)
    print("success!")


challenge1()
challenge2()
challenge3()
challenge4()
print("OHHH,give you flag:"+str(flag))

1、乘数、增量、模数以及第一项已知

当我们知道乘数a，增量b模数n，以及第一项s0的值：

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
import os
import hashlib
from string import ascii_letters
from Crypto.Util.number import *
from Crypto.Random.random import randrange, getrandbits, choice

from flag import flag

class LCG(object):
    def __init__(self, seed):
        # 产生一个256位二进制素数
        self.N = getPrime(256)
        # 在N范围内随机产生两个数
        self.a = randrange(self.N)
        self.b = randrange(self.N)
        # seed = seed%N
        self.seed = seed % self.N
        self.state = self.seed

    # self.state = (a * seed + b)% N
    def next(self):
        self.state = (self.a * self.state + self.b) % self.N
        return self.state

def challenge1():
    print("This is the challenge1")
    init_seed = getrandbits(256)
    lcg = LCG(init_seed)
    print("lcg.a="+str(lcg.a))
    print("lcg.b="+str(lcg.b))
    print("lcg.N="+str(lcg.N))
    print("lcg.num1="+str(lcg.next()))
    seed1 = int(input("lcg.seed = "))
    if seed1 != lcg.seed:
        print("worry")
        exit(0)
    print("success!")
    
challenge1()

解密代码：

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *
a=11117737577616430261700579904669567704125468079996490555771745492505915194718
b=84923302761234043356542012549810957105354826174004592024027163821299864963373
n=92990280170239686940570202979208858357118851384588771765813565538598979636449
c=75995933492081158742111827152893916938467931731213291787903627350954936992901

MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1] #逆元计算
ani=MMI(a,n) 
seed=c
seed = (ani*(seed-b))%n
print(seed)

2、增量未知

增量b未知，但是我们指导乘数a，模数n，以及第一项s0和第二项s1的值

1
2
3
4
5
6
7
8
9
10
11
12
13
def challenge2():
    print("This is the challenge2")
    init_seed = getrandbits(256)
    lcg = LCG(init_seed)
    print("lcg.a="+str(lcg.a))
    print("lcg.N="+str(lcg.N))
    print("lcg.num1="+str(lcg.next()))
    print("lcg.num2="+str(lcg.next()))
    seed1 = int(input("lcg.seed = "))
    if seed1 != lcg.seed:
        print("worry")
        exit(0)
    print("success!")
1
2
s1 = s0 * a + b (mod n)
b = s1 - s0 * a (mod n)

所以先把b求出，在将b带入第一种情况的公式中计算

1
2
3
4
5
6
7
8
9
10
11
12
13
a=60323727461893512389613444053173573556289769830864516385213165273963439419666
n=63772765535116504991324866664138155127506417671814317141463381824201626745971
output1=43256779548950618105205057172060658758096778650647953356786682933134845983013
output2=29587660751402347472955722163351167446529078992073715521709478134706039994408
b=(output2-a*output1)%n
plaintext=b
print(b)

MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1] #逆元计算
ani=MMI(a,n) 
seed=output1
seed = (ani*(seed-b))%n
print(seed)

3、增量和乘数都未知

不知道增量、乘数，但是我们知道模数和生成的三个项

1
2
3
4
5
6
7
8
9
10
11
12
13
def challenge3():
    print("This is the challenge3")
    init_seed = getrandbits(256)
    lcg = LCG(init_seed)
    print("lcg.N="+str(lcg.N))
    print("lcg.num1="+str(lcg.next()))
    print("lcg.num2="+str(lcg.next()))
    print("lcg.num3="+str(lcg.next()))
    seed1 = int(input("lcg.seed = "))
    if seed1 != lcg.seed:
        print("worry")
        exit(0)
    print("success!")

通过推导，我们能够得出m和第一项s0和s1的关系，进而求出乘数a

1
2
3
4
5
6
7
8
9
s_1 = s0 * a + c (mod n)

s_2 = s1 * a + c (mod n) 

s_2 - s_1 = s1 * a - s0 * a (mod n) 

s_2 - s_1 = a * (s1 - s0) (mod n) 

a = (s_2 - s_1) / (s_1 - s_0) (mod n)

解密代码：

1
2
3
4
5
6
7
8
9
n=104461692199190870384162670916383905806504699111028506483787017106937648022643
output=[6550230559976097543274928060228453869006546100488341839360547865795937436891,44752667588957927743657454733563259587297714640962541054244442038265293238724,89196637577760609199681073855370265788123333887828297191613180231566862499303]

MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1] #逆元计算
a=(output[2]-output[1])*MMI((output[1]-output[0]),n)%n
ani=MMI(a,n)
b=(output[1]-a*output[0])%n
seed = (ani*(output[0]-b))%n
print(seed)

4.增量，乘数和模数均未知

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def challenge4():
    print("This is the challenge4")
    init_seed = getrandbits(256)
    lcg = LCG(init_seed)
    print("lcg.num1="+str(lcg.next()))
    print("lcg.num2="+str(lcg.next()))
    print("lcg.num2="+str(lcg.next()))
    print("lcg.num2="+str(lcg.next()))
    print("lcg.num2="+str(lcg.next()))
    print("lcg.num2="+str(lcg.next()))
    seed1 = int(input("lcg.seed = "))
    if seed1 != lcg.seed:
        print("worry")
        exit(0)
    print("success!")

通过以上的条件，我们可以得知

1
2
3
4
5
6
s1 = s0*a + b  (mod n)
s2 = s1*a + b  (mod n)
s3 = s2*a + b  (mod n)
s1 - (s0*a + b) = k_1 * n
s2 - (s1*a + b) = k_2 * n
s3 - (s2*a + b) = k_3 * n
1
2
3
4
5
6
t0 = s1 - s0 
t1 = s2 - s1 = (s1*a + b) - (s0*a + b) = a*(s1 - s0) = a*t0 (mod n) 
t2 = s3 - s2 = (s2*a + b) - (s1*a + b) = a*(s2 - s1) = a*t1 (mod n) 
t3 = s4 - s3 = (s3*a + b) - (s2*a + b) = a*(s3 - s2) = a*t2 (mod n)

t2*t0 - t1*t1 = (a*a*t0 * t0) - (a*t0 * a*t0) = 0 (mod n)

这样我们就能得知模数的值了，然后和上面的步骤一样，首先是求出乘数a，再求出增量b，最后求出seed

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
from Crypto.Util.number import *
def gcd(a,b): 
    if(b==0): 
        return a 
    else: 
        return gcd(b,a%b) 
s=[57910593547760246431462713630032142367244471051605076587740229220042280832920,11600425056943962908662902750683336131127946274679975994830394345407157891082,47119365134041787030301982910979871560470568882978296406276875902026809579279,25490059061411916076337727920693205583062663924577215773084273265684255685447,47700923797846895333737702397666052553146427650812068867781925243881523549580,16494559622316759559052404259689488233512192201762700665909062412108972353608]
t = []
for i in range(5):
    t.append(s[i]-s[i-1]) 
all_n = []
for i in range(3):
    all_n.append(gcd((t[i+1]*t[i-1]-t[i]*t[i]), (t[i+2]*t[i]-t[i+1]*t[i+1]))) 

MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1] #逆元计算
for n in all_n:
    n=abs(n)
    if n==1:
        continue
    a=(s[2]-s[1])*MMI((s[1]-s[0]),n)%n
    ani=MMI(a,n)
    b=(s[1]-a*s[0])%n
    seed = (ani*(s[0]-b))%n
    print("seed=",seed)
    plaintext=seed
    print(long_to_bytes(plaintext))

RSA

当然也有RSA，详细查看我的另一篇博客

ECC

记录一下XCTF中的一道关于ECC的题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
已知椭圆曲线加密Ep(a,b)参数为

p = 15424654874903

a = 16546484

b = 4548674875

G(6478678675,5636379357093)

私钥为

k = 546768

求公钥K(x,y)

这边使用ECCTOOL来解

Rx = 13957031351290

Ry = 5520194834100

Rx + Ry = 19477226185390