Gausst松鼠会

这个屌丝很懒，什么也没留下！

热门标签

CTF-Crypto-学习笔记_在学习了凯撒大帝使用的神奇密码后,密码前辈们有创造出了更为奇异的加密方法。本

作者：Gausst松鼠会 | 2024-02-22 22:22:19

踩

在学习了凯撒大帝使用的神奇密码后,密码前辈们有创造出了更为奇异的加密方法。本

最常见的字符编码规范

ASCII

为了在计算机中表示字符，在设计编码的时候用1个字节也就是8bit位数来编码英文字符集

拉丁字母及标点符号
阿拉伯数字
一些控制字符
这就是 ASCII（American Standard Code for InformationInterchange, 美国信息交换标准代码）

Python中，使用 chr( ) 函数可得 ASCII 对应的字符，使用 ord( ) 函数可得字符的 ASCII码。

Unicode 字符集

Unicode（万国码、统一码、国际码）用于编码世界
它是一本很厚的字典，为每一个字符规定了用来表示、存储的数字。
ASCII转Unicode：flag→flag
中文转Unicode：你好→\u4f60\u597d

进制转换

可见字符:flag{congratulations!_you_got_it}
字符串转字符：

s = "flag{congratulations!_you_got_it}"
s.encode()
# b'flag{congratulations!_you_got_it}'
1
2
3

可见字符的十六进制表示：
需要安装pycryptodome：

pip install pycryptodome
1

from Crypto.Util.number import *
s = "flag{congratulations!_you_got_it}"
hex(bytes_to_long(s.encode()))
1
2
3

可见字符的十进制表示：

from Crypto.Util.number import *
s = "flag{congratulations!_you_got_it}"
bytes_to_long(s.encode())
# 11859814988224947122955311638945820597710118248738191266010403296376873770644605
1
2
3
4

可见字符的二进制表示：

from Crypto.Util.number import *
s = "flag{congratulations!_you_got_it}"
print(bin(bytes_to_long(s.encode())))
# 0b11001100110110001100001011001110111101101100011011011110110111001100111011100100110000101110100011101010110110001100001011101000110100101101111011011100111001100100001010111110111100101101111011101010101111101100111011011110111010001011111011010010111010001111101
1
2
3
4

URL（百分号）编码

统一资源定位符（Uniform Resource Locator, URL）是 Internet上标准的资源地址，可视为网络上的门牌。
如果 URL 中出现了拉丁字母、阿拉伯数字、. -_~ 外的符号，则必须使用百分号编码，所以 URL 编码也称为百分号编码。
如你在浏览器地址栏上看到：https://www.baidu.com/s?wd=春节
实际查询的网址是这样：https://www.baidu.com/s?wd=%E6%98%A5%E8%8A%82

import urllib.parse
s = "春节"
print(urllib.parse.quote(s))
# %E6%98%A5%E8%8A%82
print(urllib.parse.unquote("%E4%BD%A0%E5%A5%BD"))
# 你好
1
2
3
4
5
6

Base系列

Base64 / Base32 / Base16

这边的 Base 可理解为「基数」：
Base64 基数为 64 ，即 6 个比特位
Base32 基数为 32 ，即 5 个比特位
Base16 基数为 16 ，即 4 个比特位
ASCII 基数为 256 ，即 8 个比特位（不过最高位一定是 0）

Base64

base64
我们知道，ASCII 的一个字符对应 8 比特，所以3个字符对应4个Base64 位。
例如:fff→二进制表示为01100110 0110011001100110
Base64也就是分为 011001 100110 011001 100110
对应的数值为 25 38 25 38
找到对应的Base64编码表 Z m Z m
不足 3 的倍数怎么办，直接在末尾填充全 0 。
填充几个字节就再最后加上几个 =
所以base64只可能有一个=号或者两个=号

Base系列表现形式

Ascii字符串:flag{congratulations_you_got_it}
Base64:

import base64
s = b"flag{congratulations_you_got_it}"
print(base64.b64encode(s))
# ZmxhZ3tjb25ncmF0dWxhdGlvbnNfeW91X2dvdF9pdH0=
1
2
3
4

Base32:

import base64
s = b"flag{congratulations_you_got_it}"
print(base64.b32encode(s))
# MZWGCZ33MNXW4Z3SMF2HK3DBORUW63TTL54W65K7M5XXIX3JOR6Q====
1
2
3
4

Base16:

import base64
s = b"flag{congratulations_you_got_it}"
print(base64.b16encode(s))
# 666C61677B636F6E67726174756C6174696F6E735F796F755F676F745F69747D
1
2
3
4

特征：
=号
base16的表现形式就是16进制的ascii字符串表示
建议遇到base系列的多尝试几种base系列的解码

摩斯编码

摩斯编码
由点、划、空格组成。

字符内部的停顿：0
字符之间的停顿：000
单词之间的停顿：0000000
因无线电而生。
在线解密：
http://ctf.ssleye.com/morse.html

JSFuck/BrainFuck/ook/aaencode

JSFuck:只用 6 个字符 !+ 来编写 JavaScript
BrainFuck:只有[->+空格
Ook！:表现形式就是Ook
Ook！:还有一种表现形式为!. ?
aaencode:就是颜文字来编写JavaScript 程序，表现形式就是颜文字。

其他形式的编码表现形式

Quoted-printable:你好→=E4=BD=A0=E5=A5=BD
UUencode:flag{test}→*9FQA9WMT97-T?0
XXencode:flag{test}→8NalVNrhoNLBoTE++
在线解密:http://web.chacuo.net/charsetuuencode

古典密码学

栅栏密码

举例

篱笆墙的影子

felhaagv{ewtehtehfilnakgw}
1

凯撒密码

举例

凯撒？替换？呵呵！

MTHJ{CUBCGXGUGXWREXIPOYAOEYFIGXWRXCHTKHFCOHCFDUCGTXZOHIXOEOWMEHZO}
1

ROT13

rot13

ASCII 移位密码

ascii

举例

'''
# -*- coding:utf-8 -*-
import A,SALT
from itertools import *

def encrypt(m, a, si):
    c=""
    for i in range(len(m)):
        c+=hex(((ord(m[i])) * a + ord(next(si))) % 128)[2:].zfill(2)
    return c
if __name__ == "__main__":
    m = 'flag{********************************}'
    a = A
    salt = SALT
    assert(len(salt)==3)
    assert(salt.isalpha())
    si = cycle(salt.lower())
    print("明文内容为：")
    print(m)
    print("加密后的密文为：")
    c=encrypt(m, a, si)
    print(c)
    #加密后的密文为：
    #177401504b0125272c122743171e2c250a602e3a7c206e014a012703273a3c0160173a73753d
'''
for a in range(128):
    for b in range(128):
        if (ord("f")*a+b)% 128==0x17:
            if (ord("g")*a+b)% 128==0x50:
                print(a,b)

a=57
salt=chr(97)+chr(104)+chr(104)
for b in range(128):
    if (ord("l")*a+b)% 128==0x74:
        print(b)
for b in range(128):
    if (ord("a")*a+b)% 128==0x01:
        print(b)
c=0x177401504b0125272c122743171e2c250a602e3a7c206e014a012703273a3c0160173a73753d
from Crypto.Util.number import *
c_bytes=long_to_bytes(c)
print(c_bytes)
from itertools import *
si=cycle(salt)
import gmpy2
a1=gmpy2.invert(a,128)
for i in c_bytes:
    print(chr(((i-ord(next(si)))*a1)%128),end="")

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

乘法密码

仿射密码

埃特巴什码

单表替换密码的安全性

上面说的几种都是单表代换密码。
在单表替换加密中，所有的加密方式几乎都有一个共性，那就是明密文一一对应。
密钥空间小，直接爆破。
密钥空间大，尝试统计分析找到攻击点！
词频分析:https://quipqiup.com/
https://www.qqxiuzi.cn/daohang.htm

维吉尼亚密码 Vigenère cipher

26 × 26 方阵
密钥循环使用
不可破译的密码

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

举例：其实很简单

在学习了凯撒大帝使用的神奇密码后，密码前辈们有创造出了更为奇异的加密方法。本题出题者喜欢用helloworld当密钥，密文如下：dlpcsegkshrij,请破解后提交。附录是一张似乎有用的表。答案为非常规形式。

希尔（Hill）密码：基于矩阵乘法

在线工具：http://www.practicalcryptography.com/ciphers/hill-cipher/

培根（Bacon）密码

在线工具：http://rumkin.com/tools/cipher/baconian.php

举例

第一关：大帝
iodj{36g9i2777

第二关：滴滴滴
-... ----. ..--- -... .- -.-. ...-- ----. .- .- ..---

第三关：篱笆
a0dd}b6942c07



flag{36d9f2777b92bac39aa2ab206cd90d47}
1
2
3
4
5
6
7
8
9
10
11
12

现代密码

现代密码体制（系统）由五部分组成：

明文空间M
密文空间C
密钥空间K
加密算法E
解密算法D
对称加密体制：加密密钥等于或约等于解密密钥，主要分为流加密和分组加密。
流密码（Stream Cipher）：利用一个较短的种子密钥，通过密钥流产生器，生成伪随机的密钥流，与明文逐比特异或，得到密文。
根据异或运算的性质，解密算法也是异或运算。

公钥加密体制（双钥加密体制）:加密密钥（公开）≠ 解密密钥（保密）加密算法 ≠ 解密算法。
安全性主要是基于数学上的计算困难问题，如大数分解RSA、离散对数、椭圆曲线上离散对数等。

分组密码

XOR

异性相吸

f1=open("key.txt","r")
key=f1.read()
print(key)
f2=open("密文.txt","rb")
c=f2.read()
print(c)
print(len(key))
print(len(c))
for i in range(len(key)):
    print(chr(ord(key[i])^c[i]),end="")

'''
asadsasdasdasdasdasdasdasdasdasdqwesqf
b'\x07\x1f\x00\x03\x08\x04\x12U\x03\x10TXK\\XJVSDR\x03D\x02XF\x06TG\x05VGWD\x12]J\x14\x1b'
38
38
flag{ea1bc0988992276b7f95b54a7435e89e}
'''
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

LFSR（线性反馈移位寄存器）

f=open("key","rb")
st=f.read()
out=""
for i in st:
    out+=bin(i)[2:].zfill(8)
#out="000010111001010111010101111001101101101110011001101010100111101000010100001001110000001011010011"
key=out[18]+out[0:18]
print(key)
mask=0b1010011000100011100
flag=""
for x in range(19):
    tmp=0
    for i in range(19):
        if (mask>>i) &1:
            tmp^=int(key[18-i])
    flag=str(tmp)+flag
    key=key[18]+str(tmp)+key[1:18]
print(flag)

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

forecast

利用了python random的漏洞

flag.enc

499,123,495,149,245,118,133,441,273,140,421,391,268,493,269,413,273,386,115,107,94,459,134,481,271,172,361,287,92,235,501,477,169,416,501,477,470,421
1

import random

flag="**************************************"

def test():
    f=open("test","wb")
    s=""
    for i in range(1000):
        s+=str(random.getrandbits(32))+"\n"
    f.write(s.encode())
    f.close()
test()
f=open("flag.enc","wb")
s=""
for i in flag:
    s+=str(ord(i)^random.getrandbits(9))+","
s=s[:-1]
f.write(s.encode())    
f.close()

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

exp.py

c=[499,123,495,149,245,118,133,441,273,140,421,391,268,493,269,413,273,386,115,107,94,459,134,481,271,172,361,287,92,235,501,477,169,416,501,477,470,421]
from randcrack import RandCrack
rc=RandCrack()
f=open("test","r")
arr=[]
for i in range(1000):
    arr.append(int(f.readline().strip("\n")))
print(arr)
for i in arr[1000-624:]:
    rc.submit(i)

for i in c:
    print(chr((i^rc.predict_getrandbits(9))%128),end="")
1
2
3
4
5
6
7
8
9
10
11
12
13

randcrack.py

class RandCrack:

    def __init__(self):
        self.counter = 0
        self.mt = []
        self.state = False

    def submit(self, num):
        if self.state:
            raise ValueError("Already got enough bits")

        bits = self._to_bitarray(num)

        assert (all([x == 0 or x == 1 for x in bits]))
        self.counter += 1
        self.mt.append(self._harden_inverse(bits))
        if self.counter == 624:
            self._regen()
            self.state = True

    def _predict_32(self):
        if not self.state:
            raise ValueError("Didn't recieve enough bits to predict")

        if self.counter >= 624:
            self._regen()
        self.counter += 1

        return self._harden(self.mt[self.counter - 1])

    def predict_getrandbits(self, k):
        if not self.state:
            raise ValueError("Didn't recieve enough bits to predict")

        if k == 0:
            return 0
        words = (k - 1) // 32 + 1
        res = []
        for i in range(words):
            r = self._predict_32()
            if k < 32:
                r = [0] * (32 - k) + r[:k]
            res = r + res
            k -= 32
        return self._to_int(res)

    def predict_randbelow(self, n):
        k = n.bit_length()
        r = self.predict_getrandbits(k)
        while r >= n:
            r = self.predict_getrandbits(k)
        return r

    def predict_randrange(self, start, stop=None, step=1, _int=int):
        # Adopted messy code from random.py module
        # In fact only changed _randbelow() method calls to predict_randbelow()
        istart = _int(start)
        if istart != start:
            raise ValueError("non-integer arg 1 for randrange()")
        if stop is None:
            if istart > 0:
                return self.predict_randbelow(istart)
            raise ValueError("empty range for randrange()")

        # stop argument supplied.
        istop = _int(stop)
        if istop != stop:
            raise ValueError("non-integer stop for randrange()")
        width = istop - istart
        if step == 1 and width > 0:
            return istart + self.predict_randbelow(width)
        if step == 1:
            raise ValueError("empty range for randrange() (%d,%d, %d)" % (istart, istop, width))

        # Non-unit step argument supplied.
        istep = _int(step)
        if istep != step:
            raise ValueError("non-integer step for randrange()")
        if istep > 0:
            n = (width + istep - 1) // istep
        elif istep < 0:
            n = (width + istep + 1) // istep
        else:
            raise ValueError("zero step for randrange()")

        if n <= 0:
            raise ValueError("empty range for randrange()")

        return istart + istep * self.predict_randbelow(n)

    def predict_randint(self, a, b):
        return self.predict_randrange(a, b + 1)

    def predict_choice(self, seq):
        try:
            i = self.predict_randbelow(len(seq))
        except ValueError:
            raise IndexError('Cannot choose from an empty sequence')
        return seq[i]

    def _to_bitarray(self, num):
        k = [int(x) for x in bin(num)[2:]]
        return [0] * (32 - len(k)) + k

    def _to_int(self, bits):
        return int("".join(str(i) for i in bits), 2)

    def _or_nums(self, a, b):
        if len(a) < 32:
            a = [0] * (32 - len(a)) + a
        if len(b) < 32:
            b = [0] * (32 - len(b)) + b

        return [x[0] | x[1] for x in zip(a, b)]

    def _xor_nums(self, a, b):
        if len(a) < 32:
            a = [0] * (32 - len(a)) + a
        if len(b) < 32:
            b = [0] * (32 - len(b)) + b

        return [x[0] ^ x[1] for x in zip(a, b)]

    def _and_nums(self, a, b):
        if len(a) < 32:
            a = [0] * (32 - len(a)) + a
        if len(b) < 32:
            b = [0] * (32 - len(b)) + b

        return [x[0] & x[1] for x in zip(a, b)]

    def _decode_harden_midop(self, enc, and_arr, shift):

        NEW = 0
        XOR = 1
        OK = 2
        work = []
        for i in range(32):
            work.append((NEW, enc[i]))
        changed = True
        while changed:
            changed = False
            for i in range(32):
                status = work[i][0]
                data = work[i][1]
                if i >= 32 - shift and status == NEW:
                    work[i] = (OK, data)
                    changed = True
                elif i < 32 - shift and status == NEW:
                    if and_arr[i] == 0:
                        work[i] = (OK, data)
                        changed = True
                    else:
                        work[i] = (XOR, data)
                        changed = True
                elif status == XOR:
                    i_other = i + shift
                    if work[i_other][0] == OK:
                        work[i] = (OK, data ^ work[i_other][1])
                        changed = True

        return [x[1] for x in work]

    def _harden(self, bits):
        bits = self._xor_nums(bits, bits[:-11])
        bits = self._xor_nums(bits, self._and_nums(bits[7:] + [0] * 7, self._to_bitarray(0x9d2c5680)))
        bits = self._xor_nums(bits, self._and_nums(bits[15:] + [0] * 15, self._to_bitarray(0xefc60000)))
        bits = self._xor_nums(bits, bits[:-18])
        return bits

    def _harden_inverse(self, bits):
        # inverse for: bits = _xor_nums(bits, bits[:-11])
        bits = self._xor_nums(bits, bits[:-18])
        # inverse for: bits = _xor_nums(bits, _and_nums(bits[15:] + [0] * 15 , _to_bitarray(0xefc60000)))
        bits = self._decode_harden_midop(bits, self._to_bitarray(0xefc60000), 15)
        # inverse for: bits = _xor_nums(bits, _and_nums(bits[7:] + [0] * 7 , _to_bitarray(0x9d2c5680)))
        bits = self._decode_harden_midop(bits, self._to_bitarray(0x9d2c5680), 7)
        # inverse for: bits = _xor_nums(bits, bits[:-11])
        bits = self._xor_nums(bits, [0] * 11 + bits[:11] + [0] * 10)
        bits = self._xor_nums(bits, bits[11:21])

        return bits

    def _regen(self):
        # C code translated from python sources
        N = 624
        M = 397
        MATRIX_A = 0x9908b0df
        LOWER_MASK = 0x7fffffff
        UPPER_MASK = 0x80000000
        mag01 = [self._to_bitarray(0), self._to_bitarray(MATRIX_A)]

        l_bits = self._to_bitarray(LOWER_MASK)
        u_bits = self._to_bitarray(UPPER_MASK)

        for kk in range(0, N - M):
            y = self._or_nums(self._and_nums(self.mt[kk], u_bits), self._and_nums(self.mt[kk + 1], l_bits))
            self.mt[kk] = self._xor_nums(self._xor_nums(self.mt[kk + M], y[:-1]), mag01[y[-1] & 1])

        for kk in range(N - M - 1, N - 1):
            y = self._or_nums(self._and_nums(self.mt[kk], u_bits), self._and_nums(self.mt[kk + 1], l_bits))
            self.mt[kk] = self._xor_nums(self._xor_nums(self.mt[kk + (M - N)], y[:-1]), mag01[y[-1] & 1])

        y = self._or_nums(self._and_nums(self.mt[N - 1], u_bits), self._and_nums(self.mt[0], l_bits))
        self.mt[N - 1] = self._xor_nums(self._xor_nums(self.mt[M - 1], y[:-1]), mag01[y[-1] & 1])

        self.counter = 0


if __name__ == "__main__":
    import random
    import time

    print("Testing random module cracker...")

    cracker = RandCrack()

    random.seed(time.time())

    for i in range(624):
        cracker.submit(random.randint(0, 4294967294))

    print("Guessing next 32000 random bits success rate: {}%"
          .format(sum([random.getrandbits(32) == cracker.predict_getrandbits(32) for x in range(1000)]) / 10))

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225

RSA

密钥的生成

举例：

RSA安全性

理论上基于大数分解的困难性，即分解模数N的困难性
但随着计算机计算能力的发展，为了确保模数N不被分解，N需要取得越来越大。
工具：yafu
在线工具：factordb

RSA攻击套路

首先，我这边就不放冗长的百度百科的东西了，我概括一下我自己对RSA的看法。
RSA是一种算法，并且广泛应用于现代，用于保密通信。
RSA算法涉及三个参数,n,e,d，其中分为私钥和公钥，私钥是n,d，公钥是n,e
n是两个素数的乘积，一般这两个素数在RSA中用字母p,q表示
e是一个素数
d是e模 varphi(n) 的逆元，CTF的角度看就是，d是由e,p,q可以求解出的
一般CTF就是把我们想要获得的flag作为明文，RSA中表示为m。然后通过RSA加密，得到密文，RSA中表示为C。
加密过程c=m^e mod n

c=pow(m,e,n)
1

解密过程m=c^d mod n

m=pow(c,d,n)
1

求解私钥d

d = gmpy2.invert(e, (p-1)*(q-1))
1

一般来说，n，e是公开的，但是由于n一般是两个大素数的乘积，所以我们很难求解出d，所以RSA加密就是利用现代无法快速实现大素数的分解，所存在的一种安全的非对称加密。

基础RSA加密

from Crypto.Util.number import *
import gmpy2

# 明文m
msg = 'flag is :testflag'
# 转成16进制整数
hex_msg=int(msg.encode("hex"),16)
print(hex_msg)
# 素数p
p=getPrime(100)
# 素数q
q=getPrime(100)
# n是两个素数的乘积
n=p*q
# 公钥是n,e，e是一个素数。私钥是n,d
e=0x10001
#
phi=(p-1)*(q-1)
# d是e模 varphi(n) 的逆元，CTF的角度看就是，d是由e,p,q可以求解出的
d=gmpy2.invert(e,phi)
print("d=",hex(d))
# 密文c
c=pow(hex_msg,e,n)
print("e=",hex(e))
print("n=",hex(n))
print("c=",hex(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

34852863793931897547090823807754671251815
('d=', '0xe0cb53bac57348a423f43f2aed1bf0f503688c90a0cff19c1')
('e=', '0x10001')
('n=', '0xde23e693f412952e8e057270d0f14f56a0df99d598586e8edfL')
('c=', '0x644078982d648df7097dd388a29f67a8567de4c6ff196fbc6eL')
1
2
3
4
5

基础RSA解密

#!/usr/bin/env python
# -*- coding:utf-8 -*-
import binascii
import gmpy2
# 两个素数的乘积n
n=0x80b32f2ce68da974f25310a23144977d76732fa78fa29fdcbf
#这边我用yafu分解了n
p=780900790334269659443297956843
q=1034526559407993507734818408829
# 公钥e
e=0x10001
# 密文c
c=0x534280240c65bb1104ce3000bc8181363806e7173418d15762

phi=(p-1)*(q-1)
# 逆元d
d=gmpy2.invert(e,phi)
# 明文m
m=pow(c,d,n)
print(hex(m))
print(binascii.unhexlify(hex(m)[2:].strip("L")))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

0x666c6167206973203a74657374666c6167
flag is :testflag
1
2

RSA因子p&q不当分解

p和q相差过大或过小，如上例。

利用条件

因为n=p*q
其中若p和q的值相差较小，或者较大，都会造成n更容易分解的结果
例如出题如下

p=getPrime(512)
q=gmpy2.next_prime(p)
n=p*q
1
2
3

因为p和q十分接近，所以可以使用yafu直接分解

yafu分解
使用

factor(*)
1

括号中为要分解的数
因式分解
在线网站分解
http://factordb.com/
通过在此类网站上查询n，如果可以分解或者之前分解成功过，那么可以直接得到p和q

举例

from Crypto.Util.number import *
import gmpy2

flag = 'flag{*********************}'
m=bytes_to_long(flag.encode())
p=getPrime(512)
# 临近q
q=gmpy2.next_prime(p)
n=p*q
e=0x10001
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
c=pow(m,e,n)
print("e=",hex(e))
print("n=",hex(n))
print("c=",hex(c))

#e= 0x10001
#n= 0x96d562f7100cff53f608b6ba1552d58727fbf3fd163726fa65c5d6cf777bdabec3b549242897055caaea5c0a0bb6a30bab73a57b528265ae6045cae800c17978993bb6d4d81e4d995a6ffb92ee10ed606871037b0ddace3db81a1537cb6f16c322160fa36f5903eb1aa84f0ee46bfacde03a2cac18504df552648b407852040f
#c= 0x75c64aa529f2c6987653122d1d5e20d37bdb3c86049da0cac13b93279409a8a08c15ed09e3b0f4f2d854e64a167438ff36ef6aa0821542f31c9543db7d85e7aefde04f47e0403d8e8f74e83acb7b3a7b5b92fd9f12237d48ed865317ebd7888cd895f7959233dd3190965e7426a68d49bd98206712c168b144423351742f94f3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

exp.py

e= 0x10001
n= 0x96d562f7100cff53f608b6ba1552d58727fbf3fd163726fa65c5d6cf777bdabec3b549242897055caaea5c0a0bb6a30bab73a57b528265ae6045cae800c17978993bb6d4d81e4d995a6ffb92ee10ed606871037b0ddace3db81a1537cb6f16c322160fa36f5903eb1aa84f0ee46bfacde03a2cac18504df552648b407852040f
c= 0x75c64aa529f2c6987653122d1d5e20d37bdb3c86049da0cac13b93279409a8a08c15ed09e3b0f4f2d854e64a167438ff36ef6aa0821542f31c9543db7d85e7aefde04f47e0403d8e8f74e83acb7b3a7b5b92fd9f12237d48ed865317ebd7888cd895f7959233dd3190965e7426a68d49bd98206712c168b144423351742f94f3

p = 10291691539956320954972581754251612994384170725799086560166488710492236835931157131382616562400233051981075764700669983013064614944432405231738947852601201
q = 10291691539956320954972581754251612994384170725799086560166488710492236835931157131382616562400233051981075764700669983013064614944432405231738947852600191
print(p*q==n)


import gmpy2
import binascii

phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(binascii.unhexlify(hex(m)[2:].strip("L")))

'''
True
flag{a2d10a3211b415832791a6bc6031f9ab}
'''
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

公约数分解n

利用条件

当题目给的多对公钥n是公用了一个素数因子的时候，可以尝试公约数分解
出题一般如下

p1=getPrime(512)
p2=getPrime(512)
q=getPrime(512)
n1=p1*q
n2=p2*q
1
2
3
4
5

所以当题目给了多个n，并且发现n无法分解，可以尝试是否有公约数。

欧几里得辗转相除法
求公约数可以使用欧几里得辗转相除法，实现python脚本如下

def gcd(a, b):   #求最大公约数
    if a < b:
        a, b = b, a
    while b != 0:
        temp = a % b
        a = b
        b = temp
    return a
1
2
3
4
5
6
7
8

举例

from Crypto.Util.number import *
import gmpy2

flag = 'flag{******************}'
m=bytes_to_long(flag.encode())
p=getPrime(512)
q=getPrime(512)
p2=getPrime(512)
# n1和n2有公约数q
n1=p*q
n2=p2*q
e=0x10001
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
c=pow(m,e,n1)
print("e=",e)
print("n1=",n1)
print("n2=",n2)
print("c=",c)
'''
e= 65537
n1= 115205766471059781270815604837009314657798597158913292644119663583719125777824041586752032035243666254025203786188035607022471569797983564319842982498755649057896881618966000477214120345088836045599502515494252992934633359436850135398632587182499247836972087805864758310205067696292979360247491268935445760747
n2= 139151110513318209083176529711756450516319765206948018486876906602717789940417835912041508342627710084011340627446281100656028403764567565659197999643325780583386127242149024266190288969045344868291613275890848074094845235636145367687600666935329150610685125752376402648945766877555960666113629584870151828091
c= 37784362005912178721263973742304143596248403802904670205564588193888169464689052352887133037886697168082757263755584166545598212048396908425843861624178309849720696116722927642936187733426593227579988489557113698133433804364722953380850950658119086544556004805582948121618951251321352586046056523556934859706
'''

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

exp.py

e= 65537
n1= 115205766471059781270815604837009314657798597158913292644119663583719125777824041586752032035243666254025203786188035607022471569797983564319842982498755649057896881618966000477214120345088836045599502515494252992934633359436850135398632587182499247836972087805864758310205067696292979360247491268935445760747
n2= 139151110513318209083176529711756450516319765206948018486876906602717789940417835912041508342627710084011340627446281100656028403764567565659197999643325780583386127242149024266190288969045344868291613275890848074094845235636145367687600666935329150610685125752376402648945766877555960666113629584870151828091
c= 37784362005912178721263973742304143596248403802904670205564588193888169464689052352887133037886697168082757263755584166545598212048396908425843861624178309849720696116722927642936187733426593227579988489557113698133433804364722953380850950658119086544556004805582948121618951251321352586046056523556934859706
import gmpy2
from Crypto.Util.number import *
q=gmpy2.gcd(n1,n2)
print(q)
p=n1//q
print(p*q==n1)

phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n1)
print(long_to_bytes(m))

'''
11043683466206674381259998118558614894944034894097887196897007818771125370029573924739794492474626247268682883829182888241620348309323653096361191238356333
True
flag{a2d10a3211b415832791a6bc6031f9ab}
'''
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

模数分解

利用条件

已知e,d,n求p,q、

dp&dq泄露

利用条件

首先了解一下什么是dp、dq

dp=d%(p-1)
dq=d%(q-1)
1
2

这种参数是为了让解密的时候更快速产生的。

('p=', '0xf85d730bbf09033a75379e58a8465f8048b8516f8105ce2879ce774241305b6eb4ea506b61eb7e376d4fcd425c76e80cb748ebfaf3a852b5cf3119f028cc5971L')
('q=', '0xc1f34b4f826f91c5d68c5751c9af830bc770467a68699991be6e847c29c13170110ccd5e855710950abab2694b6ac730141152758acbeca0c5a51889cbe84d57L')
('dp=', '0xf7b885a246a59fa1b3fe88a2971cb1ee8b19c4a7f9c1a791b9845471320220803854a967a1a03820e297c0fc1aabc2e1c40228d50228766ebebc93c97577f511')
('dq=', '0x865fe807b8595067ff93d053cc269be6a75134a34e800b741cba39744501a31cffd31cdea6078267a0bd652aeaa39a49c73d9121fafdfa7e1131a764a12fdb95')
('c=', '0xae05e0c34e2ba4ca3536987cc2cfc3f1f7f53190164d0ac50b44832f0e7224c6fdeebd2c91e3991e7d179c26b1b997295dc9724925ba431f527fba212703a0d14a34ce133661ae0b6001ee326303d6ccdc27dbd94e0987fae25a84f197c1535bdac9094bfb3846b7ca696b2e5082bea7bff804da275772ca05dd51b185a4fc30L')
1
2
3
4
5

解题代码：

InvQ=gmpy2.invert(q,p)
mp=pow(c,dp,p)
mq=pow(c,dq,q)
m=(((mp-mq)*InvQ)%p)*q+mq
print '{:x}'.format(m).decode('hex')
1
2
3
4
5

举例

from Crypto.Util.number import *
import gmpy2

flag = 'flag{********************************}'
m=bytes_to_long(flag.encode())
p=getPrime(512)
q=getPrime(512)
n=p*q
e=getPrime(20)
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
dp=d%(p-1)
dq=d%(q-1)
c=pow(m,e,n)
print("n=",n)
print("p=",p)
print("q=",q)
print("dp=",dp)
print("dq=",dq)
print("c=",c)
'''
n= 118618954287615269695904875995489548511444940267622767094047739634494646358809304433978173495687678370406458702860536342785803753234702546219494665535864474652301862284591690673176769043630372899075883834606545174586348720993678078895654149136676023206963021215226128014757783383076786413359604861549162636747
p= 12244425890527037559457450758199625345224440148602500121947513405940248134857180032689144921510099766782376592176091852775339372003558472079284757727362571
q= 9687588078701625994967484476321431565856840411439788976614047902260935119170606128529184693304251663287418434325133814992945149670372082642015792984936257
dp= 11661765341055037028213110243140762441891859947132976341835485861002039690412298548398000165827316261292160830963662695604031845480131372329938955617008307
dq= 5330972108962230819517925352753760247189342573369390983643754562382224659226949816794659715545630171557328975020873518879918889149973698886977898856476183
c= 12374013610995935975987144573885493212459411904794697197903023715805777590324318665512805085245267803654557700689811822171219122398629103950576556025535606948328799420133553234348610960343249046259660281472602396406991408998707805300684186709474247145123999521260863968647240075574632249474210031448000004668
'''
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

exp.py

import gmpy2
import binascii
def decrypt(dp,dq,p,q,c):
    InvQ = gmpy2.invert(q,p)
    mp = pow(c,dp,p)
    mq = pow(c,dq,q)
    m=(((mp-mq)*InvQ)%p)*q+mq
    print (binascii.unhexlify(hex(m)[2:]))

n= 118618954287615269695904875995489548511444940267622767094047739634494646358809304433978173495687678370406458702860536342785803753234702546219494665535864474652301862284591690673176769043630372899075883834606545174586348720993678078895654149136676023206963021215226128014757783383076786413359604861549162636747
p= 12244425890527037559457450758199625345224440148602500121947513405940248134857180032689144921510099766782376592176091852775339372003558472079284757727362571
q= 9687588078701625994967484476321431565856840411439788976614047902260935119170606128529184693304251663287418434325133814992945149670372082642015792984936257
dp= 11661765341055037028213110243140762441891859947132976341835485861002039690412298548398000165827316261292160830963662695604031845480131372329938955617008307
dq= 5330972108962230819517925352753760247189342573369390983643754562382224659226949816794659715545630171557328975020873518879918889149973698886977898856476183
c= 12374013610995935975987144573885493212459411904794697197903023715805777590324318665512805085245267803654557700689811822171219122398629103950576556025535606948328799420133553234348610960343249046259660281472602396406991408998707805300684186709474247145123999521260863968647240075574632249474210031448000004668

decrypt(dp,dq,p,q,c)
# flag{a2d10a3211b415832791a6bc6031f9ab}

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

dp泄露

利用条件

假设题目给出公钥n,e以及dp

('dp=', '0x7f1344a0b8d2858492aaf88d692b32c23ef0d2745595bc5fe68de384b61c03e8fd054232f2986f8b279a0105b7bee85f74378c7f5f35c3fd505e214c0738e1d9')
('n=', '0x5eee1b4b4f17912274b7427d8dc0c274dc96baa72e43da36ff39d452ff6f2ef0dc6bf7eb9bdab899a6bb718c070687feff517fcf5377435c56c248ad88caddad6a9cefa0ca9182daffcc6e48451d481f37e6520be384bedb221465ec7c95e2434bf76568ef81e988039829a2db43572e2fe57e5be0dc5d94d45361e96e14bd65L')
('e=', '0x10001')
('c=', '0x510fd8c3f6e21dfc0764a352a2c7ff1e604e1681a3867480a070a480f722e2f4a63ca3d7a92b862955ab4be76cde43b51576a128fba49348af7a6e34b335cfdbda8e882925b20503762edf530d6cd765bfa951886e192b1e9aeed61c0ce50d55d11e343c78bb617d8a0adb7b4cf3b913ee85437191f1136e35b94078e68bee8dL')
1
2
3
4

给出密文要求解明文
我们可以通过n，e，dp求解私钥d。
公式推导参考简书
https://www.jianshu.com/p/74270dc7a14b
首先dp是

dp=d%(p-1)
1

以下推导过程如果有问题欢迎指正
现在我们可以知道的是

c≡m^e mod n
m≡c^d mod n
ϕ(n)=(p−1)∗(q−1)
d∗e≡1 mod ϕ(n)
dp≡d mod (p−1)
1
2
3
4
5

由上式可以得到

dp∗e≡d∗e mod (p−1)
1

因此可以得到

d∗e=k∗(p−1)+dp∗ed∗e≡1 mod ϕ(n)
1

我们将式1带入式2可以得到

k∗(p−1)+dp∗e≡1 mod (p−1)∗(q−1)
1

故此可以得到

k2∗(p−1)∗(q−1)+1=k1∗(p−1)+dp∗e
1

变换一下

(p−1)∗[k2∗(q−1)−k1]+1=dp∗e
1

因为

dp<p−1
1

可以得到

e>k2∗(q−1)−k1
1

我们假设

x=k2∗(q−1)−k1
1

可以得到x的范围为

(0,e)
1

因此有

x∗(p−1)+1=dp∗e
1

那么我们可以遍历

x∈(0,e)
1

求出p-1，求的方法也很简单，遍历65537种可能，其中肯定有一个p可以被n整除那么求出p和q，即可利用

ϕ(n)=(p−1)∗(q−1)d∗e≡1 mod ϕ(n)
1

推出

d≡1∗e−1 mod ϕ(n)
1

注：这里的-1为逆元，不是倒数的那个-1

公式的python实现
求解私钥d脚本如下

def getd(n,e,dp):
    for i in range(1,e):
        if (dp*e-1)%i == 0:
            if n%(((dp*e-1)/i)+1)==0:
                p=((dp*e-1)/i)+1
                q=n/(((dp*e-1)/i)+1)
                phi = (p-1)*(q-1)
                d = gmpy2.invert(e,phi)%phi
                return d
1
2
3
4
5
6
7
8
9

举例

from Crypto.Util.number import *
import gmpy2

flag = 'flag{*****************************}'
m=bytes_to_long(flag.encode())
p=getPrime(512)
q=getPrime(512)
n=p*q
e=0x10001
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
dp=d%(p-1)
c=pow(m,e,n)
print("e=",e)
print("n=",n)
print("dp=",dp)
print("c=",c)
'''
e= 65537
n= 92828237009545230120118069089223514912716896165610308064504460604082624853938431962923949334864864436264408433256288068202484225961256898972743676389188622775737958995025654351705278456167733907608412584542016121478865285024454893448016017969632116442841446786562704173003893111037687107024681444848078613927
dp= 4082218682388454520843878160797744907842495447068248006379787528326114811047197268952039581542773781854559607944658834487467299675549398662256389836821909
c= 14490533356014180733497751921539678090452759083476295303899740842911168177354564459129698267996626531829194777130342559029232479939335746334521688770129350369504991860912181278314347862204291618819118798920468232748953919317971699169539017795380789372322430009718018665278749598988666351269866046298409588225
'''
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

exp.py

import gmpy2
import binascii

def getd(n,e,dp):
    for i in range(1,e):
        if (dp*e-1)%i == 0:
            if n%(((dp*e-1)//i)+1)==0:
                p=((dp*e-1)//i)+1
                q=n//(((dp*e-1)//i)+1)
                phi = (p-1)*(q-1)
                d = gmpy2.invert(e,phi)%phi
                return d



e= 65537
n= 92828237009545230120118069089223514912716896165610308064504460604082624853938431962923949334864864436264408433256288068202484225961256898972743676389188622775737958995025654351705278456167733907608412584542016121478865285024454893448016017969632116442841446786562704173003893111037687107024681444848078613927
dp= 4082218682388454520843878160797744907842495447068248006379787528326114811047197268952039581542773781854559607944658834487467299675549398662256389836821909
c= 14490533356014180733497751921539678090452759083476295303899740842911168177354564459129698267996626531829194777130342559029232479939335746334521688770129350369504991860912181278314347862204291618819118798920468232748953919317971699169539017795380789372322430009718018665278749598988666351269866046298409588225


d=getd(n,e,dp)
m=pow(c,d,n)
print (binascii.unhexlify(hex(m)[2:]))
# flag{a2d10a3211b415832791a6bc6031f9ab}

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

e与φ(n)不互素

利用条件

('n1=', '0xbf510b8e2b169fbce366eb15a4f6c71b370f02f2108c7feb482234a386185bce1a740fa6498e04edbdf2a639e320619d9f39d3e740ebaf578af0426bc3e851001a1d599108a08725347f6680a7f5581a32d91505023701872c3df723e8de9f201d3b17059bebff944b915045870d757eb6d6d009eb4561cc7e4b89968e4433a9L')
('e1=', '0x15d6439c6')
('c1=', '0x43e5cc4c99c3040aef2ccb0d4c45266f6b75cd7f9f1be105766689283f0886061c9cd52ac2b2b6c1b7d250c2079f354ca9b988db5556336201f3b5e489916b3b60b80c34bef8f608d7471fafaf14bee421b60630f42c5cc813356e786ff10e5efa334b8a73b7ea06afa6043f33be6a31010d306ba60516243add65c183da843aL')
('n2=', '0xba85d38d1bfc3fb281927c9246b5b771ac3344ca9fe1c2d9c793a886bffb5c84558f4a578cd5ba9e777a4e08f66d0cabe05b9aa2ae8d075778b5fbfff318a7f9b6f22e2eff6f79d8c1148941b3974f3e83a4a4f1520ad42336eddc572ec7ea04766eb798b2f1b1b52009b3eeea7741b2c55e3c7c11c5cf6a4e204c6b0d312f49L')
('e2=', '0x2c09848c6')
('c2=', '0x79ec6350649377f69b475eca83a7d9d5356a1d62e29933e9c8e2b19b4b23626a581037aba3be6d7f73d5bed049350e41c1ed4cdc3e10ee34ec576ef3449be2f7d930c759612e1c23c4db71d0e5185a80b548031e3857dd93eca4af017fcd25895fcc4e8a2b36c1dd36b8cd9cc9200e2879f025928fe346e2cfae5200e66de6ccL')
1
2
3
4
5
6

首先用公约数分解可以分解得到n1、n2的因子
但是发现e和φ(n)是不互为素数的，所以我们无法求出私钥d。

解题公式推导

gcd(e1,(p-1)*(q1-1))
gcd(e2,(p-1)*(q2-1))
1
2

得到结果为79858
也就是说，e和φ(n)不互素且具有公约数79858
公式推导过程参考博客
https://blog.csdn.net/chenzzhenguo/article/details/94339659

举例

exp.py

#!/usr/bin/env python
# -*- coding:utf-8 -*-
import gmpy2
import binascii


def gcd(a, b):
    if a < b:
        a, b = b, a
    while b != 0:
        temp = a % b
        a = b
        b = temp
    return a

n1=0xbf510b8e2b169fbce366eb15a4f6c71b370f02f2108c7feb482234a386185bce1a740fa6498e04edbdf2a639e320619d9f39d3e740ebaf578af0426bc3e851001a1d599108a08725347f6680a7f5581a32d91505023701872c3df723e8de9f201d3b17059bebff944b915045870d757eb6d6d009eb4561cc7e4b89968e4433a9
n2=0xba85d38d1bfc3fb281927c9246b5b771ac3344ca9fe1c2d9c793a886bffb5c84558f4a578cd5ba9e777a4e08f66d0cabe05b9aa2ae8d075778b5fbfff318a7f9b6f22e2eff6f79d8c1148941b3974f3e83a4a4f1520ad42336eddc572ec7ea04766eb798b2f1b1b52009b3eeea7741b2c55e3c7c11c5cf6a4e204c6b0d312f49

p=gcd(n1,n2)
q1=n1//p
q2=n2//p



c1=0x43e5cc4c99c3040aef2ccb0d4c45266f6b75cd7f9f1be105766689283f0886061c9cd52ac2b2b6c1b7d250c2079f354ca9b988db5556336201f3b5e489916b3b60b80c34bef8f608d7471fafaf14bee421b60630f42c5cc813356e786ff10e5efa334b8a73b7ea06afa6043f33be6a31010d306ba60516243add65c183da843a
c2=0x79ec6350649377f69b475eca83a7d9d5356a1d62e29933e9c8e2b19b4b23626a581037aba3be6d7f73d5bed049350e41c1ed4cdc3e10ee34ec576ef3449be2f7d930c759612e1c23c4db71d0e5185a80b548031e3857dd93eca4af017fcd25895fcc4e8a2b36c1dd36b8cd9cc9200e2879f025928fe346e2cfae5200e66de6cc
e1 =0x15d6439c6
e2 =0x2c09848c6

#print(gcd(e1,(p-1)*(q1-1)))
#print(gcd(e2,(p-1)*(q2-1)))


e1=e1//gcd(e1,(p-1)*(q1-1))
e2=e2//gcd(e2,(p-1)*(q2-1))


phi1=(p-1)*(q1-1);phi2=(p-1)*(q2-1)
d1=gmpy2.invert(e1,phi1)
d2=gmpy2.invert(e2,phi2)
f1=pow(c1,d1,n1)
f2=pow(c2,d2,n2)


def GCRT(mi, ai):
    curm, cura = mi[0], ai[0]
    for (m, a) in zip(mi[1:], ai[1:]):
        d = gmpy2.gcd(curm, m)
        c = a - cura
        K = c // d * gmpy2.invert(curm // d, m // d)
        cura += curm * K
        curm = curm * m // d
        cura %= curm
    return (cura % curm, curm)


f3,lcm = GCRT([n1,n2],[f1,f2])
n3=q1*q2
c3=f3%n3
phi3=(q1-1)*(q2-1)

d3=gmpy2.invert(39929,phi3)#39929是79858//gcd((q1-1)*(q2-1),79858) 因为新的e和φ(n)还是有公因数2
m3=pow(c3,d3,n3)

if gmpy2.iroot(m3,2)[1] == 1:
    flag=gmpy2.iroot(m3,2)[0]
    print(binascii.unhexlify(hex(flag)[2:].strip("L")))
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

公钥n由多个素数因子组成

利用条件

题目如下

('n=', '0xf1b234e8a03408df4868015d654dcb931f038ef4fc0be8658c9b951ee6c60d23689a1bfb151e74df0910fa1cf8a542282a65')
('e=', '0x10001')
('c=', '0x22fda6137013bac19754f78e8d9658498017f05a4b0814f2af97dc2c60fdc433d2949ea27b13337961ef3c4cf27452ad3c95')
1
2
3

因为这题的公钥n是由四个素数相乘得来的，
其中四个素数的值相差较小，或者较大，都会造成n更容易分解的结果
例如出题如下

p=getPrime(100)
q=gmpy2.next_prime(p)
r=gmpy2.next_prime(q)
s=gmpy2.next_prime(r)
n=p*q*r*s
1
2
3
4
5

因为p、q、r、s十分接近，所以可以使用yafu直接分解
yafu

import binascii
import gmpy2
p=1249559655343546956371276497499
q=1249559655343546956371276497489
r=1249559655343546956371276497537
s=1249559655343546956371276497423
e=0x10001
c=0x22fda6137013bac19754f78e8d9658498017f05a4b0814f2af97dc2c60fdc433d2949ea27b13337961ef3c4cf27452ad3c95
n=p*q*r*s

phi=(p-1)*(q-1)*(r-1)*(s-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(binascii.unhexlify(hex(m)[2:].strip("L")))
# flag is:testflag

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

举例

from Crypto.Util.number import *
import gmpy2

flag = 'flag{*****************************}'
m=bytes_to_long(flag.encode())
p=getPrime(128)
q=gmpy2.next_prime(p)
r=getPrime(128)
n=p*q*r
e=0x10001
c=pow(m,e,n)
print("e=",e)
print("n=",n)
print("c=",c)
print("r=",r)
'''
e= 65537
n= 15457914185002396188272793481814354803901078733691131783857141421040343122904471787555943138320876412334439563870423
c= 8036525777130443184393455047034333939594051741708051133260156016939103486238878891876906912026231768495818380158485
r= 291772877613383069932935701252073023153
'''

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

exp.py

e= 65537
n= 15457914185002396188272793481814354803901078733691131783857141421040343122904471787555943138320876412334439563870423
c= 8036525777130443184393455047034333939594051741708051133260156016939103486238878891876906912026231768495818380158485
r= 291772877613383069932935701252073023153
import gmpy2
from Crypto.Util.number import *

pq=n//r
print(pq)
p = 230172262495731574542243822462679932863
q = 230172262495731574542243822462679932857
phi=(p-1)*(q-1)*(r-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

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

小明文攻击

利用条件

明文过小，导致明文的e次方仍然小于n明文的三次方虽然比n大，但是大不了多少
小明文攻击是基于低加密指数的，主要分成两种情况。

明文过小，导致明文的e次方仍然小于n

('n=', '0xad03794ef170d81aad370dccb7b92af7d174c10e0ae9ddc99b7dc5f93af6c65b51cc9c40941b002c7633caf8cd50e1b73aa942c8488d46c0032064306de388151814982b6d35b4e2a62dd647f527b31b4f826c36848dc52999574a8694460e1b59b4e96bda1341d3ba5f991f0000a56004d47681ecfd37a5e64bd198617f8dadL')
('e=', '0x3')
('c=', '0x10652cdf6f422470ea251f77L')
1
2
3

这种情况直接对密文e次开方，即可得到明文

解题脚本

import binascii
import gmpy2
n=0xad03794ef170d81aad370dccb7b92af7d174c10e0ae9ddc99b7dc5f93af6c65b51cc9c40941b002c7633caf8cd50e1b73aa942c8488d46c0032064306de388151814982b6d35b4e2a62dd647f527b31b4f826c36848dc52999574a8694460e1b59b4e96bda1341d3ba5f991f0000a56004d47681ecfd37a5e64bd198617f8dad
e=0x3
c=0x10652cdf6f422470ea251f77

m=gmpy2.iroot(c, 3)[0]
print(binascii.unhexlify(hex(m)[2:].strip("L")))
1
2
3
4
5
6
7
8

明文的三次方虽然比n大，但是大不了多少

('n=', '0x9683f5f8073b6cd9df96ee4dbe6629c7965e1edd2854afa113d80c44f5dfcf030a18c1b2ff40575fe8e222230d7bb5b6dd8c419c9d4bca1a7e84440a2a87f691e2c0c76caaab61492db143a61132f584ba874a98363c23e93218ac83d1dd715db6711009ceda2a31820bbacaf1b6171bbaa68d1be76fe986e4b4c1b66d10af25L')
('e=', '0x3')
('c=', '0x8541ee560f77d8fe536d48eab425b0505e86178e6ffefa1b0c37ccbfc6cb5f9a7727baeb3916356d6fce3205cd4e586a1cc407703b3f709e2011d7b66eaaeea9e381e595b4d515c433682eb3906d9870fadbffd0695c0168aa26447f7a049c260456f51e937ce75b74e5c3c2bd7709b981898016a3a18f15ae99763ff40805aaL')
1
2
3

爆破即可，每次加上一个n

i = 0
while 1:
    res = iroot(c+i*n,3)
    if(res[1] == True):
        print res
        break
    print "i="+str(i)
    i = i+1
1
2
3
4
5
6
7
8

完整脚本：

import binascii
import gmpy2

n=0x9683f5f8073b6cd9df96ee4dbe6629c7965e1edd2854afa113d80c44f5dfcf030a18c1b2ff40575fe8e222230d7bb5b6dd8c419c9d4bca1a7e84440a2a87f691e2c0c76caaab61492db143a61132f584ba874a98363c23e93218ac83d1dd715db6711009ceda2a31820bbacaf1b6171bbaa68d1be76fe986e4b4c1b66d10af25
e=0x3
c=0x8541ee560f77d8fe536d48eab425b0505e86178e6ffefa1b0c37ccbfc6cb5f9a7727baeb3916356d6fce3205cd4e586a1cc407703b3f709e2011d7b66eaaeea9e381e595b4d515c433682eb3906d9870fadbffd0695c0168aa26447f7a049c260456f51e937ce75b74e5c3c2bd7709b981898016a3a18f15ae99763ff40805aa

i = 0
while 1:
    res = gmpy2.iroot(c+i*n,3)
    if(res[1] == True):
        m=res[0]
        print(binascii.unhexlify(hex(m)[2:].strip("L")))
        break
    print "i="+str(i)
    i = i+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

举例

#n:  0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793L
#e:  0x3
#c:0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
so,how to get the message?
1
2
3
4

exp.py

e= 65537
n= 15457914185002396188272793481814354803901078733691131783857141421040343122904471787555943138320876412334439563870423
c= 8036525777130443184393455047034333939594051741708051133260156016939103486238878891876906912026231768495818380158485
r= 291772877613383069932935701252073023153
import gmpy2
from Crypto.Util.number import *

pq=n//r
print(pq)
p = 230172262495731574542243822462679932863
q = 230172262495731574542243822462679932857
phi=(p-1)*(q-1)*(r-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

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

低加密指数广播攻击

利用条件

如果选取的加密指数较低，并且使用了相同的加密指数给一个接受者的群发送相同的信息，那么可以进行广播攻击得到明文。
这个识别起来比较简单，一般来说都是给了三组加密的参数和明密文，其中题目很明确地能告诉你这三组的明文都是一样的，并且e都取了一个较小的数字。

举例

from Crypto.Util.number import *
import gmpy2

flag = 'flag{*********************************}'
m=bytes_to_long(flag.encode())
def getN():
    p=getPrime(256)
    q=getPrime(256)
    n=p*q
    return n
e=0x3
n1=getN()
c1=pow(m,e,n1)
n2=getN()
c2=pow(m,e,n2)
n3=getN()
c3=pow(m,e,n3)
print("n=",[n1,n2,n3])
print("c=",[c1,c2,c3])

'''

n= [5567000486226353254524673454357147076118077122275789480555238584552332526459181641567858429587222587683345901310468140782420858931709570476562698953112801, 6982887363645354856540867035629441781549999700006363403940951376485517460506822033812812263179663875843737953430050436453298336104404304183964162702612863, 5569628780521526092136759047774448808289588145127191213956593902336353172559905282602383716258500935021056393917971164303539941268395159953652768614304911]
c= [4112523544883480830903403452517516825703078902670926405984774762024235980767805538947466914193950835488469608756778569692190967901730207690525300247682815, 4181292472036270897593568708931413787888488621274030741130549434467976405476555130890722346319549396800183827305452019796119873044279138566837264814627098, 3857434270788621361517349247277347831953021241414984430770586220424214110700999615785879462771584952744049357875753754209006439028080870626012342467148773]

'''
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

exp.py

import binascii,gmpy2

n= [5567000486226353254524673454357147076118077122275789480555238584552332526459181641567858429587222587683345901310468140782420858931709570476562698953112801, 6982887363645354856540867035629441781549999700006363403940951376485517460506822033812812263179663875843737953430050436453298336104404304183964162702612863, 5569628780521526092136759047774448808289588145127191213956593902336353172559905282602383716258500935021056393917971164303539941268395159953652768614304911]
c= [4112523544883480830903403452517516825703078902670926405984774762024235980767805538947466914193950835488469608756778569692190967901730207690525300247682815, 4181292472036270897593568708931413787888488621274030741130549434467976405476555130890722346319549396800183827305452019796119873044279138566837264814627098, 3857434270788621361517349247277347831953021241414984430770586220424214110700999615785879462771584952744049357875753754209006439028080870626012342467148773]
from functools import reduce
def CRT(mi, ai):
    assert(reduce(gmpy2.gcd,mi)==1)
    assert (isinstance(mi, list) and isinstance(ai, list))
    M = reduce(lambda x, y: x * y, mi)
    ai_ti_Mi = [a * (M // m) * gmpy2.invert(M // m, m) for (m, a) in zip(mi, ai)]
    return reduce(lambda x, y: x + y, ai_ti_Mi) % M
e=0x3
m=gmpy2.iroot(CRT(n, c), e)[0]
print(binascii.unhexlify(hex(m)[2:].strip("L")))

# flag{a2d10a3211b415832791a6bc6031f9ab}

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

低解密指数攻击

利用条件

主要利用的是私钥d很小，表现形式一般是e很大

举例

github上有开源的攻击代码https://github.com/pablocelayes/rsa-wiener-attack

from secret import flag
from Crypto.Util.number import *

m = bytes_to_long(flag)

p = getPrime(512)
q = getPrime(512)
N = p * q
phi = (p-1) * (q-1)
while True:
    d = getRandomNBitInteger(200)
    if GCD(d, phi) == 1:
        e = inverse(d, phi)
        break

c = pow(m, e, N)

print(c, e, N, sep='\n')

# 37625098109081701774571613785279343908814425141123915351527903477451570893536663171806089364574293449414561630485312247061686191366669404389142347972565020570877175992098033759403318443705791866939363061966538210758611679849037990315161035649389943256526167843576617469134413191950908582922902210791377220066
# 46867417013414476511855705167486515292101865210840925173161828985833867821644239088991107524584028941183216735115986313719966458608881689802377181633111389920813814350964315420422257050287517851213109465823444767895817372377616723406116946259672358254060231210263961445286931270444042869857616609048537240249
# 86966590627372918010571457840724456774194080910694231109811773050866217415975647358784246153710824794652840306389428729923771431340699346354646708396564203957270393882105042714920060055401541794748437242707186192941546185666953574082803056612193004258064074902605834799171191314001030749992715155125694272289

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

exp.py

def rational_to_contfrac (x, y):
    ''' 
    Converts a rational x/y fraction into
    a list of partial quotients [a0, ..., an] 
    '''
    a = x//y
    if a * y == x:
        return [a]
    else:
        pquotients = rational_to_contfrac(y, x - a * y)
        pquotients.insert(0, a)
        return pquotients
def convergents_from_contfrac(frac):    
    '''
    computes the list of convergents
    using the list of partial quotients 
    '''
    convs = [];
    for i in range(len(frac)):
        convs.append(contfrac_to_rational(frac[0:i]))
    return convs

def contfrac_to_rational (frac):
    '''Converts a finite continued fraction [a0, ..., an]
     to an x/y rational.
     '''
    if len(frac) == 0:
        return (0,1)
    elif len(frac) == 1:
        return (frac[0], 1)
    else:
        remainder = frac[1:len(frac)]
        (num, denom) = contfrac_to_rational(remainder)
        # fraction is now frac[0] + 1/(num/denom), which is 
        # frac[0] + denom/num.
        return (frac[0] * num + denom, num)

def egcd(a,b):
    '''
    Extended Euclidean Algorithm
    returns x, y, gcd(a,b) such that ax + by = gcd(a,b)
    '''
    u, u1 = 1, 0
    v, v1 = 0, 1
    while b:
        q = a // b
        u, u1 = u1, u - q * u1
        v, v1 = v1, v - q * v1
        a, b = b, a - q * b
    return u, v, a

def gcd(a,b):
    '''
    2.8 times faster than egcd(a,b)[2]
    '''
    a,b=(b,a) if a<b else (a,b)
    while b:
        a,b=b,a%b
    return a

def modInverse(e,n):
    '''
    d such that de = 1 (mod n)
    e must be coprime to n
    this is assumed to be true
    '''
    return egcd(e,n)[0]%n

def totient(p,q):
    '''
    Calculates the totient of pq
    '''
    return (p-1)*(q-1)

def bitlength(x):
    '''
    Calculates the bitlength of x
    '''
    assert x >= 0
    n = 0
    while x > 0:
        n = n+1
        x = x>>1
    return n


def isqrt(n):
    '''
    Calculates the integer square root
    for arbitrary large nonnegative integers
    '''
    if n < 0:
        raise ValueError('square root not defined for negative numbers')

    if n == 0:
        return 0
    a, b = divmod(bitlength(n), 2)
    x = 2**(a+b)
    while True:
        y = (x + n//x)//2
        if y >= x:
            return x
        x = y


def is_perfect_square(n):
    '''
    If n is a perfect square it returns sqrt(n),

    otherwise returns -1
    '''
    h = n & 0xF; #last hexadecimal "digit"

    if h > 9:
        return -1 # return immediately in 6 cases out of 16.

    # Take advantage of Boolean short-circuit evaluation
    if ( h != 2 and h != 3 and h != 5 and h != 6 and h != 7 and h != 8 ):
        # take square root if you must
        t = isqrt(n)
        if t*t == n:
            return t
        else:
            return -1

    return -1

def hack_RSA(e,n):
    frac = rational_to_contfrac(e, n)
    convergents = convergents_from_contfrac(frac)

    for (k,d) in convergents:
        #check if d is actually the key
        if k!=0 and (e*d-1)%k == 0:
            phi = (e*d-1)//k
            s = n - phi + 1
            # check if the equation x^2 - s*x + n = 0
            # has integer roots
            discr = s*s - 4*n
            if(discr>=0):
                t = is_perfect_square(discr)
                if t!=-1 and (s+t)%2==0:
                    print("\nHacked!")
                    return d
from Crypto.Util.number import *
def main():
    c=37625098109081701774571613785279343908814425141123915351527903477451570893536663171806089364574293449414561630485312247061686191366669404389142347972565020570877175992098033759403318443705791866939363061966538210758611679849037990315161035649389943256526167843576617469134413191950908582922902210791377220066
    e=46867417013414476511855705167486515292101865210840925173161828985833867821644239088991107524584028941183216735115986313719966458608881689802377181633111389920813814350964315420422257050287517851213109465823444767895817372377616723406116946259672358254060231210263961445286931270444042869857616609048537240249
    n=86966590627372918010571457840724456774194080910694231109811773050866217415975647358784246153710824794652840306389428729923771431340699346354646708396564203957270393882105042714920060055401541794748437242707186192941546185666953574082803056612193004258064074902605834799171191314001030749992715155125694272289
    d=hack_RSA(e,n)
    print ("d=")
    print (d)
    m=pow(c,d,n)
    

    print(long_to_bytes(m))

if __name__ == '__main__':
    main()

'''
Hacked!
d=
1485313191830359055093545745451584299495272920840463008756233
flag{d3752538-90d0-c373-cfef-9247d3e16848}
'''
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166

共模攻击

利用条件

识别：若干次加密，e不同，n相同，m相同。就可以在不分解n和求d的前提下，解出明文m。
推导过程:

首先，两个加密指数互质：
gcd(e1,e2)=1

即存在s1、s2使得：
s1+*e1+s2*e2=1

又因为：
c1≡m^e1 mod n
c2≡m mod n

代入化简可得：
c1^s1 * c2^s2 ≡ m mod n

即可求出明文
1
2
3
4
5
6
7
8
9
10
11
12
13
14

举例

{6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249,773}
{6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249,839}

message1=3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349
message2=5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535

1
2
3
4
5
6

exp.py

import sys
import binascii
sys.setrecursionlimit(1000000)
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 modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
      raise Exception('modular inverse does not exist')
    else:
      return x % m

c1=3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349
n=6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249
e1=773
c2=5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535
e2=839

s = egcd(e1, e2)
s1 = s[1]
s2 = s[2]

if s1<0:
   s1 = - s1
   c1 = modinv(c1, n)
elif s2<0:
   s2 = - s2
   c2 = modinv(c2, n)
m=(pow(c1,s1,n)*pow(c2,s2,n)) % n
print(m)
#print (binascii.unhexlify(hex(m)[2:].strip("L")))
flag=[102,108,97,103,123,119,104,101,110,119,101,116,104,105,110,107,105,116,105,115,112,111,115,115,105,98,108,101,125]
r = ""
for i in flag:
    r += chr(i)
print(r)

'''
1021089710312311910410111011910111610410511010710511610511511211111511510598108101125
flag{whenwethinkitispossible}
'''
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

参考：https://xz.aliyun.com/t/6459

国密算法

实操

RSA是一种算法，并且广泛应用于现代，用于保密通信。
RSA算法涉及三个参数,n,e,d，其中分为私钥和公钥，私钥是n,d，公钥是n,e
n是两个素数的乘积，一般这两个素数在RSA中用字母p,q表示
e是一个素数
d是e模 varphi(n) 的逆元，CTF的角度看就是，d是由e,p,q可以求解出的
一般CTF就是把我们想要获得的flag作为明文，RSA中表示为m。然后通过RSA加密，得到密文，RSA中表示为C。

加密过程 c=m^e mod n

c=pow(m,e,n)
1

解密过程 m=c^d mod n

m=pow(c,d,n)
1

求解私钥d

d = gmpy2.invert(e, (p-1)*(q-1))
1

基础RSA加密脚本

from Crypto.Util.number import *
import gmpy2

msg = 'flag is :testflag'
hex_msg=int(msg.encode("hex"),16)
print(hex_msg)
p=getPrime(100)
q=getPrime(100)
n=p*q
e=0x10001
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
print("d=",hex(d))
c=pow(hex_msg,e,n)
print("e=",hex(e))
print("n=",hex(n))
print("c=",hex(c))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

34852863793931897547090823807754671251815
('d=', '0x66e16452adf1d19c8cbad6544d0e519a3072fb25cfcec1e041')
('e=', '0x10001')
('n=', '0xb072fbfb159a37ff21a09106517fe9eddfb70fa7a199d50913L')
('c=', '0x35499823e8e3c9e27909d5c46da61f29b95883ad4c017241d0L')
1
2
3
4
5

基础RSA解密脚本

#!/usr/bin/env python
# -*- coding:utf-8 -*-
import binascii
import gmpy2
n=0x80b32f2ce68da974f25310a23144977d76732fa78fa29fdcbf
#这边我用yafu分解了n
p=780900790334269659443297956843
q=1034526559407993507734818408829
e=0x10001
c=0x534280240c65bb1104ce3000bc8181363806e7173418d15762

phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(hex(m))
print(binascii.unhexlify(hex(m)[2:].strip("L")))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

0x666c6167206973203a74657374666c6167
flag is :testflag
1
2

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/131552?site