发表更新Writeup17 分钟读完 (大约2604个字)

XMUTCTF 2021 Writeup 0x2

Rank2

某校校赛，放到博客上水水，（为什么要水？题目很基础，对CTF感兴趣的可以看看）

文章篇幅过长，分为0x1和0x2

阅读更多
发表更新Writeup13 分钟读完 (大约1957个字)

XMUTCTF 2021 Writeup 0x1

Rank2

某校校赛，放到博客上水水，（为什么要水？题目很基础，对CTF感兴趣的可以看看）

阅读更多
发表更新Writeup5 分钟读完 (大约719个字)

HackTheBox - Forest Writeup

About Forest

Forest in an easy difficulty Windows Domain Controller (DC), for a domain in which Exchange Server has been installed. The DC is found to allow anonymous LDAP binds, which is used to enumerate domain objects. The password for a service account with Kerberos pre-authentication disabled can be cracked to gain a foothold. The service account is found to be a member of the Account Operators group, which can be used to add users to privileged Exchange groups. The Exchange group membership is leveraged to gain DCSync privileges on the domain and dump the NTLM hashes.

阅读更多
发表更新LIFE10 分钟读完 (大约1481个字)

重整一下我家的网络 v1.0 (Dragon)

很早就想重整一下农村家里的网络，毕竟服务器和种种设备（监控、硬碟机、交换机…）都在家里，年初做了一版，简单画了张拓扑，可惜那时候整的不怎么样（资金不足、设备损坏等等原因），现在资金够了，该买的也买了，就随便写写吧。

阅读更多
发表更新Research15 分钟读完 (大约2229个字)

Stack overflow learning

栈的介绍

栈是一种只能从表的一端存取数据且遵循 “先进后出”/“后进先出 (Last in First Out) “ 原则的线性存储结构，主要操作有入栈（push）和出栈（pop），往上叫栈顶，往下叫栈底

img栈

在汇编中栈入栈和出栈的操作形式，先从ESP/RSP/SP寄存器（栈指针）指向的内存中读取数据写入其他内存地址或者基础，再根据不同的系统架构将栈指针的数值增加4（32位）或者增加8（64位）

阅读更多
发表更新LIFE11 分钟读完 (大约1669个字)

雅马哈P-125B电钢琴开箱及使用体验

买之前一直在罗兰FP30X和雅马哈P128之间徘徊，最终选择了雅马哈P125，希望这是一个不会让我后悔的选择。

简单开箱

产品价格：看官网价格，P-125 - 概述 - 可攜式數位鋼琴(P系列) - 鋼琴 - 樂器 - 產品 - Yamaha - 台灣

产品规格：P125B本体+U架+单踏（延音踏板）+礼包（转接头）

重量：提着爬六楼累得半死

在此之前我已经有了一台电子琴，注意是电子琴（带打击音效+编曲功能的那种），陪了我8年多，牌子叫（SHUSIAMAN，杂牌），记得当时到SM买的，花了3k多还送了个家教😅，学了两个月左右打下了基础（指基础指法，但这破电子琴只有61键，很难受），后来因为学业和种种原因就搁在那儿不动了，也就偶尔拿出来练个599，另外这台琴琴键是镂空的，不像传统钢琴一样中间是实心的，有到琴行和学校钢琴间摸过真钢，那手感真的不能比。。。

阅读更多
发表更新HAM25 分钟读完 (大约3753个字)

中国无线电协会业余电台 A 类操作证书笔记

关于

本篇文章仅列出一些易错点及小TIP，还有一些速记技巧（供那些临时抱佛脚的人使用），更深入的内容请自行了解。本人是在福建省考的试，各省份考试方式及费用可能略有不同，请翻阅自己省工信部网站上有关无线电的资料

题目已经熟透不少了，现在上场的话99.9%能拿满分，A类考试题目一共371道题，考试会从题库里边抽出30道题目来，总的来说还算简单，CRAC官网有配套的考试系统，测了几下都能满分，A类和B类题目都差不多，等考完A类后我就开始奋斗B类啦，争取六个月后顺利通过B类。

题目不怎么难，有初中物理基础基本上就能对一半，还有那本小绿皮（现在是小蓝皮？）写得很详细，整本看完基本上稳了。

步入正题，我花了几天刷A类题库，稍微总结了一下，A类40%政策题，60%技术题（大概是这样）

阅读更多
发表更新Research8 分钟读完 (大约1200个字)

计算机网络基础 - 子网掩码划分

先来回顾一下IP地址，这里只列出三种常用的IP地址，ABC类，IP地址由32个二进制组成。点分十进制表达法为：192.168.0.1

img

子网掩码的表示方法：

  • 32位二进制数字，在子网掩码中，网络号部分用”1”表示，主机号部分用”0”表示
  • 网络后缀法表示子网掩码，”/<网络号位数>”
阅读更多
发表更新Research23 分钟读完 (大约3383个字)

Crypto RSA 个人密码学全解

RSA

  1. Find two large prime numbers

    1. e.g N = p * q
    2. N（Large Integers / Modulus）

  2. Calculating the Euler function

    1. f(n) = (p - 1) * (q - 1)

  3. Then Choose an e，And e and f(n) are mutually prime

    1. mutually prime: The number of conventions is only 1 integer

  4. The modulo inverse of e * d ≡ 1 (mod φ) (modulo inverse element: If two positive integers e and n are prime to each other), Then an integer d must be found such that e * d - 1 is divisible by n, or the remainder of e * d divided by n is 1, At this point, d is called the “modulo inverse element” of e, Euler’s theorem can be used to prove that modulo inverse elements must exist. (Two integers a and b), Divided by and integer M, have equal remainders: a ≡ b(mod m), for example, 5 divided by 3 has a remainder of 2, 11 divided by 3 has a remainder of 2, so it can be written 11 ≡ 5(mod 3).

  5. Encryption of plaintext m: c = pow(m, e, N), Ciphertext c

    1. c = pow(m, e, n)

  6. Decryption of ciphertext c: m = pow(c, d, N), Plaintext m

    1. m = pow(c, d, n)
  • p and q: two big prime number, N = p * q
  • N: Big integer, It can be called modulus number
    • e and d: Two indices that are invariant to each other
  • c and m: Ciphertext and Plaintext
  • (N, e): Public Key
  • (N, d): Private Key
  • pow(x, y, z): effect equivalence pow(x, y) 1 % z，先计算x的y次方，如果存在另一个参数z，需要再对结果进行取模。
  • 密钥长度：n以二进制表示的的位数，例如密钥长度为512代表n用二进制表示的长度为512bit。

RSA加密解密原理图

公钥：{e,n}
私钥：{d,n}
image-20220403215156849

RSA Security Analysis

对于RSA加密算法

公钥(N, e)为公钥，可以任意公开，破解RSA最直接（亦或是暴力）的方法就是分解整数N，然后计算欧拉函数 φ(n)=(p-1) * (q-1)

再通过d * e ≡ 1 mod φ(N)，即可计算出 d，然后就可以使用私钥(N, d)通过m = pow(c,d,N)解密明文。

Guarantee RSA Security

  1. 定期更换密钥
  2. 不同的用户不可以使用相同的模数N
  3. p与q的差值要大，最好是差几个比特
  4. p-1与q-1都应该有大的素因子，一般建议选择的两个大素数p、q使得p=2p+1和q=2q+1也是素数
  5. e的选择不要太小
  6. d的选择也是不可以太小，最好满足d>=n的4分之1

Common Attack Methods

Direct decomposition modulo N

直接分解模数N是最直接的攻击方法，也是最困难的方法。具体的解析同上RSA安全性分析。
如果n小于256bit，可以使用本地工具进行暴力分解，例如Windows平台的RSATool，可以在数分钟之内完成256bit的n的分解。
如果n大于768bit，可以尝试利用在线网站 http://factordb.com， 这一类在线网站的原理是储存了部分n分解成功的的值。

例题

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
{920139713,19}
 
704796792
752211152
274704164
18414022
368270835
483295235
263072905
459788476
483295235
459788476
663551792
475206804
459788476
428313374
475206804
459788476
425392137
704796792
458265677
341524652
483295235
534149509
425392137
428313374
425392137
341524652
458265677
263072905
483295235
828509797
341524652
425392137
475206804
428313374
483295235
475206804
459788476
306220148

拆分N：920139713

得到：18443 · 49891

现在已知p、q、e以及c，可以通过前三个参数求出d

搞出 d 后就可以搞出 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
#求明文
import gmpy2
n = 920139713
d = 96849619
c = """
704796792
752211152
274704164
18414022
368270835
483295235
263072905
459788476
483295235
459788476
663551792
475206804
459788476
428313374
475206804
459788476
425392137
704796792
458265677
341524652
483295235
534149509
425392137
428313374
425392137
341524652
458265677
263072905
483295235
828509797
341524652
425392137
475206804
428313374
483295235
475206804
459788476
306220148
"""
result = ""
c_list = c.split()
for i in c_list:
    result += chr(pow(int(i),d,n))
print(result)

对RSA的公共模数攻击

适用于：使用相同的模数 N 、不同的私钥，加密同一明文消息

基本原理

假如采用两个或者两个以上的**公钥(N,e)**来加密同一条信息，可以得到下面的结论：

1
2
c1 = pow(m, e1, N)
c2 = pow(m, e2, N)

分别拿对应的私钥来加密，可以得到相同的明文m

1
2
m = pow(c1, d1, N)
m = pow(c2, d2, N)

假设攻击者已知n,e1,e2,c1,c2，即可可以得到明文m，因为e1和e2互质，所以使用欧几里得算法（用于计算两个整数a,b的最大公约数）可以找到能够满足以下条件的x，y：

1
pow(x,e1)+pow(y,e2)=1

假设x为负数，需再使用欧几里得算法来计算

1
pow(c1,-1)

则可以得到

1
pow(pow(c1,-1),-x) * pow(c2,y) = p mod(n)

如果p<n，则p可以被计算出来。

加密

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
coding:utf-8
import libnum
import gmpy2
#生成素数
p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
e1=2333
e2=23333
m="flag{6ed4c74e022cb18c8039e96de93aa9ce}"
m=libnum.s2n(m)
n=p*q
c1=pow(m,e1,n)
c2=pow(m,e2,n)
print("n1=",n)
print("e1=",e1)
print("c1=",c1)
print("n2=",n)
print("e2=",e2)
print("c2=",c2)

解密

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
#coding:utf-8
import gmpy2
import libnum

n= 25333966058003377512707481338795714713737652659944601834182685873529702913988641983855700459996104700470621411559153944988952210084014634675583566338568882440708528997808798650962116756969822211586531522430245040013570571043385238601846104615050089457836721437790715225367971106085839523500735480715155424498941150468093083816830215632716244390679417218873179734276657411907216486790815037105108306055794473002315541787461904728375164737225486501009857299717749346279371251245318729951905832578739696926931502225899707226264570557623527701806829827566904224572897378639191756878049342203546309520458672464170859577433
e1= 2333
c1= 11355981897781478907853356911752561659125575027336719997290835661089901154031171698660586203170528368228850895159361637188990782030255983633790580700032092629587631108597144196551438410868034739981960656110887650747325311613900008001234835897835613759692146419080113176963747835592656185435741504176116672174539018089139547795447109458469225330809064539216773123671814859510069089532677704482026169178543062578686794346026774853085101278125763460212801929360456888869350105294595904940799522522144740464043605342348269086324747729288399275079874271519208155039364092577755518532799345651172433227745483422620900776136
e2= 23333
c2= 1326499538902841116411674554069945581390130048432351353260154261863309471312810811160302458644816390944833633923435634961251092531893503039914793217247984595331920909367627316087404934402312358642315675486438968585084964845763881078835787872160374025547400141298650794551970291119975344578667689961134814676553190178139842507675899262024572370313939107080072875068218336255452161407859907308656094331557912187788276334833723893856310434523337557011032081467262457427167978528280339494077785813461280853735266463152709443731638714219391773144349752633555310299318290576258086971373777118482642702020599928071855133041

#共模攻击
#共模攻击函数
def rsa_gong_N_def(e1,e2,c1,c2,n):
    e1, e2, c1, c2, n=int(e1),int(e2),int(c1),int(c2),int(n)
    s = gmpy2.gcdext(e1, e2)
    s1 = s[1]
    s2 = s[2]
    if s1 < 0:
        s1 = - s1
        c1 = gmpy2.invert(c1, n)
    elif s2 < 0:
        s2 = - s2
        c2 = gmpy2.invert(c2, n)
    m = (pow(c1,s1,n) * pow(c2 ,s2 ,n)) % n
    return int(m)
m = rsa_gong_N_def(e1,e2,c1,c2,n)
print(m)
print(libnum.n2s(int(m)))

RSA小指数e攻击

如果RSA系统的公钥e选取较小的值，可以使得加密和验证签名的速度有所提高，但是如果e的选取太小，就容易受到攻击。

有三个分别使用不同的模数n1,n2,n3，但是都选取e=3，加密同一个明文可以得到：

1
2
3
c1 = pow(m,3,n1)
c2 = pow(m,3,n2)
c3 = pow(m,3,n3)

一般情况下，n1,n2,n3互素，否则会比较容易求出公因子，从而安全性大幅度的减低。

RSA选择密文攻击

在此种攻击模型中，攻击者需要掌握的内容包括：加密算法、截获的部分密文、自己选择的密文消息以及相应的被解密的明文。

利用公约数

思路
如果两次加密的n1和n2具有相同的素因子，可以利用欧几里德算法直接分解n1和n2.
通过欧几里德算法计算出两个n的最大公约数p：

1
2
3
4
5
6
7
8
9
10
11
12
13
def gcd(a, b):
	if a < b:
    	a, b = b, a
	while b != 0:
    	temp = a % b
     	a = b
     	b = temp
def gcd_digui(a, b):
	if b != 0:
   		return a
	return gcd(b,a%b)

p = gcd(n1,n2)

思路
如果两次加密的n1和n2具有相同的素因子，可以利用欧几里德算法直接分解n1和n2.
通过欧几里德算法计算出两个n的最大公约数p：

例子

n1=9051013965404084482870087864821455535159008696042953021965631089095795348830954383127323853272528967729311045179605407693592665683311660581204886571146327720288455874927281128121117323579691204792399913106627543274457036172455814805715668293705603675386878220947722186914112990452722174363713630297685159669328951520891938403452797650685849523658191947411429068829734053745180460758604283051344339641429819373112365211739216160420494167071996438506850526168389386850499796102003625404245645796271690310748804327
n2=13225948396179603816062046418717214792668512413625091569997524364243995991961018894150059207824093837420451375240550310050209398964506318518991620142575926623780411532257230701985821629425722030608722035570690474171259238153947095310303522831971664666067542649034461621725656234869005501293423975184701929729170077280251436216167293058560030089006140224375425679571181787206982712477261432579537981278055755344573767076951793312062480275004564657590263719816033564139497109942073701755011873153205366238585665743

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def gcd(a, b):
    if a < b:
        a, b = b, a
    while b != 0:
        temp = a % b
        a = b
        b = temp
def gcd_digui(a, b):
    if b != 0:
        return a
    return gcd(b,a%b)
n1 = 9051013965404084482870087864821455535159008696042953021965631089095795348830954383127323853272528967729311045179605407693592665683311660581204886571146327720288455874927281128121117323579691204792399913106627543274457036172455814805715668293705603675386878220947722186914112990452722174363713630297685159669328951520891938403452797650685849523658191947411429068829734053745180460758604283051344339641429819373112365211739216160420494167071996438506850526168389386850499796102003625404245645796271690310748804327

n2 = 13225948396179603816062046418717214792668512413625091569997524364243995991961018894150059207824093837420451375240550310050209398964506318518991620142575926623780411532257230701985821629425722030608722035570690474171259238153947095310303522831971664666067542649034461621725656234869005501293423975184701929729170077280251436216167293058560030089006140224375425679571181787206982712477261432579537981278055755344573767076951793312062480275004564657590263719816033564139497109942073701755011873153205366238585665743
p = gcd_digui(n1, n2)
print(p)

Format方法与Pollard rho方法

针对大整数的分解有很多种算法，性能上各有优异。
在p，q的取值差异过大，或者p，q的取值过于相近的时候，Format方法与Pollard rho方法都可以很快将n分解成功。
此类分解方法有一个开源项目yafu将其自动化实现了，不论n的大小，只要p和q存在相差过大或者过近时，都可以通过yafu很快地分解成功。

识别
不能直接分解n，不能使用公约数分解n，可以尝试yafu。

低加密指数攻击

在RSA中的e被称为加密指数。由于e的选择只需要满足以下条件即可

计算欧拉函数 φ = (p-1) * (q-1)，然后选择一个e(1<e<φ)，并且e和φ互质

选择小的e可以缩短加密时间，但是选择的e不当，可能会造成严重的安全问题。

e=3的小明文攻击
当e=3，并且明文过小时，导致明文的三次方仍然小于n，通过直接对密文三次开方，即可得到明文。
原理如下

对明文m进行加密：c = pow(m, 3, N),可以得到密文c。
因为n > pow(m, 3)，所以c = pow(m, 3, N) = pow(m, 3)，故对密文三次开方，即可得到明文。

有一种特殊的情况是：pow(m, 3) > n，但是不是足够，假设存在这样的k，有下列的公式成立

1
c = pow(m, 3) + k * n

爆破k，当且仅当c - (k * n)可以开三次方，c - (k * n)开三次方结果就是明文m。

识别
当e=3时，优先使用这种方法解密。

1
2
3
4
5
6
i=0
while 1:
	if(gmpy.root(c+i*N, 3)[1]==1):
		 print gmpy.root(c+i*N, 3)
		 break
	i=i+1

低解密指数攻击

与低加密指数类似，低解密指数可以加快解密的过程，但是这两者都带来了安全问题。
识别
e看起来非常的大。

使用：RSA-WIENER-ATTACK

如果运行报错

1
2
import sys
sys.setrecursionlimit(10000000)

低加密指数广播攻击

如果选取的加密指数e比较低，并且使用了相同的加密指数e给若干个接收者发送相同的信息，可以利用低加密指数广播攻击得到明文。
选取相同的加密指数e（例如e=3），对相同的明文m进行了加密并进行了消息的发送。有以下的等式成立。

1
2
3
c1 = pow(m, e, n1)
c2 = pow(m, e, n2)
c3 = pow(m, e, n3)

对上述等式运用中国剩余定理，在e=3时，可以得到

1
c_x = pow(m, 3, n1 * n2 * n3)

通过对 c_x进行三次开方可以得到明文。

识别
一般来说都是给了三组加密的参数和明密文，其中题目很明确地能告诉你这三组的明文都是一样的，并且e都取了一个较小的数字。

Coppersmith定理攻击

Coppersmith定理指出在一个e阶的mod n多项式f(x)中，如果有一个根小于n^frac{1}{e} ，就可以运用一个O(log n)的算法求出这些根。

这个定理可以应用于RSA算法。如果e = 3并且在明文当中只有三分之二的比特是已知的，这种算法可以求出明文中所有的比特

CTF中常见的题型分析

可能使用到的工具

N太大的时候使用费马分解

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
from isqrt import isqrt
def fermat(n):
    a = isqrt(n)
    b2 = a * a - n
    b = isqrt(n)
    count = 0
    while b * b != b2:
        a = a + 1
        b2 = a * a - n
        b = isqrt(b2)
        count += 1
    p = a + b
    q = a - b
    assert n == p * q
    return p, q

if __name__ == '__main__':
    import libnum
    N=27272410937497615429184017335437367466288981498585803398561456300019447702001403165885200936510173980380489828828523983388730026101865884520679872671569532101708469344562155718974222196684544003071765625134489632331414011555536130289106822732544904502428727133498239161324625698270381715640332111381465813621908465311076678337695819124178638737015840941223342176563458181918865641701282965455705790456658431641632470787689389714643528968037519265144919465402561959014798324908010947632834281698638848683632113623788303921939908168450492197671761167009855312820364427648296494571794298105543758141065915257674305081267
    e=65537
    c=14181751948841206148995320731138166924841307246014981115736748934451763670304308496261846056687977917728671991049712129745906089287169170294259856601300717330153987080212591008738712344004443623518040786009771108879196701679833782022875324499201475522241396314392429412747392203809125245393462952461525539673218721341853515099201642769577031724762640317081252046606564108211626446676911167979492329012381654087618979631924439276786566078856385835786995011067720124277812004808431347148593882791476391944410064371926611180496847010107167486521927340045188960373155894717498700488982910217850877130989318706580155251854
    p,q=fermat(N)
    print("p:",p)
    print("q:",q)

    # 根据p,q求phi_n也即N的欧拉函数值
    phi_n=(p-1)*(q-1)
    # 求d
    d= libnum.invmod(e,phi_n)
    
    # 用d解密
    flag=libnum.n2s(pow(c,d,N))
    print(flag)

已知p、q、e求解d

思路
根据欧拉函数，可以通过p、q计算出欧拉函数值

φ(n) = (p-1) * (q-1)

之后再根据以下的公式反推出d

d * e ≡ 1 mod φ(N)

在一次RSA密钥对生成中，假设p=473398607161，q=4511491，e=17
求解出d

将得到的d提交

根据思路可以python进行实现：

1
2
3
4
5
6
7
8
9
# 已知p、q、e求解d
import gmpy2

p = gmpy2.mpz(473398607161)
q = gmpy2.mpz(4511491)
e = gmpy2.mpz(17)
n = (p-1)*(q-1)
d = gmpy2.invert(e,n)
print("d is:\n%s"%d)

已知p、q、e、c求解明文

思路
根据常规的思路，求解出明文m，必须通过通过以下的公式

1
m ≡ pow(c,d) mod n

现在缺少的参数有d、n，其中的n可以通过以下的公式可以求出

1
n = p * q

而d可以通过以下公式求出

1
2
d * e = 1 mod φ(n)
φ(n) = (p-1) * (q-1)

例题

p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e = 65537
c = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034

1
2
3
4
5
6
7
8
9
10
import gmpy2
p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e = 65537
c = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034
n = p * q
phi_n = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi_n)
m = pow(c, d, n)
print("m=%s" % m)

已知c、n、e求解明文

思路
先根据

1
n = p * q

对已知的n进行大数分解得到p、q，一般通过在线或者自己通过脚本实现
根据欧拉函数，可以通过p、q计算出欧拉函数值

1
φ(n) = (p-1) * (q-1)

之后再根据以下的公式反推出d

1
d * e ≡ 1 mod φ(N)

最后对密文c进行解密：m = pow(c, d, N)，可以得到明文m。

例题

N=0xee290c7a603fc23300eb3f0e5868d056b7deb1af33b5112a6da1edc9612c5eeb4ab07d838a3b4397d8e6b6844065d98543a977ed40ccd8f57ac5bc2daee2dec301aac508f9befc27fae4a2665e82f13b1ddd17d3a0c85740bed8d53eeda665a5fc1bed35fbbcedd4279d04aa747ac1f996f724b14f0228366aeae34305152e1f430221f9594497686c9f49021d833144962c2a53dbb47bdbfd19785ad8da6e7b59be24d34ed201384d3b0f34267df4ba8b53f0f4481f9bd2e26c4a3e95cd1a47f806a1f16b86a9fc5e8a0756898f63f5c9144f51b401ba0dd5ad58fb0e97ebac9a41dc3fb4a378707f7210e64c131bca19bd54e39bbfa0d7a0e7c89d955b1c9f
e=0x10001
c=0x3dbf00a02f924a70f44bdd69e73c46241e9f036bfa49a0c92659d8eb0fe47e42068eaf156a9b3ee81651bc0576a91ffed48610c158dc8d2fb1719c7242704f0d965f8798304925a322c121904b91e5fc5eb3dc960b03eb8635be53b995217d4c317126e0ec6e9a9acfd5d915265634a22a612de962cfaa2e0443b78bdf841ff901423ef765e3d98b38bcce114fede1f13e223b9bd8155e913c8670d8b85b1f3bcb99353053cdb4aef1bf16fa74fd81e42325209c0953a694636c0ce0a19949f343dc229b2b7d80c3c43ebe80e89cbe3a3f7c867fd7cee06943886b0718a4a3584c9d9f9a66c9de29fda7cfee30ad3db061981855555eeac01940b1924eb4c301

转一下n为十进制，得到

1
2
3
4
n = int(0xee290c7a603fc23300eb3f0e5868d056b7deb1af33b5112a6da1edc9612c5eeb4ab07d838a3b4397d8e6b6844065d98543a977ed40ccd8f57ac5bc2daee2dec301aac508f9befc27fae4a2665e82f13b1ddd17d3a0c85740bed8d53eeda665a5fc1bed35fbbcedd4279d04aa747ac1f996f724b14f0228366aeae34305152e1f430221f9594497686c9f49021d833144962c2a53dbb47bdbfd19785ad8da6e7b59be24d34ed201384d3b0f34267df4ba8b53f0f4481f9bd2e26c4a3e95cd1a47f806a1f16b86a9fc5e8a0756898f63f5c9144f51b401ba0dd5ad58fb0e97ebac9a41dc3fb4a378707f7210e64c131bca19bd54e39bbfa0d7a0e7c89d955b1c9f)
print("%s" % n)

30064958471180141352963255964320727764941087854957385562672821662319854021395100968823341108075020928542437446993994119863902565874355296188498304761389336438421889636409561936141985786801002923752627293790265351723795968412774268086467114263767947693310444934316205390814185802517514694528501333851255084653925181726978734804806707740444755908398751964899143494522781405457103697373868972836201511424363601490903086488506985489526910314474245106338585623571369549388434865567951986866445306840505397268281889886738015891982162371413136885989746931929787765617838750381226036784122498143172854419447324975505933540511

然后n就等于

30064958471180141352963255964320727764941087854957385562672821662319854021395100968823341108075020928542437446993994119863902565874355296188498304761389336438421889636409561936141985786801002923752627293790265351723795968412774268086467114263767947693310444934316205390814185802517514694528501333851255084653925181726978734804806707740444755908398751964899143494522781405457103697373868972836201511424363601490903086488506985489526910314474245106338585623571369549388434865567951986866445306840505397268281889886738015891982162371413136885989746931929787765617838750381226036784122498143172854419447324975505933540511

接着分解

p=57970027

q=518629368090170828331048663550229634444384299751272939077168648935075604180676006392464524953128293842996441022771890719731811852948684950388211907532651941639114462313594608747413310447500790775078081191686616804987790818396104388332734677935684723647108960882771460341293023764117182393730838418468480006985768382115446225422781116531906323045161803441960506496275763429558238732127362521949515590606221409745127192859630468854653290302491063292735496286233738504010613373838035073995140744724948933839238851600638652315655508861728439180988253324943039367876070687033249730660337593825389358874152757864093

接着搞出d就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import gmpy2
from binascii import a2b_hex
n = 0xee290c7a603fc23300eb3f0e5868d056b7deb1af33b5112a6da1edc9612c5eeb4ab07d838a3b4397d8e6b6844065d98543a977ed40ccd8f57ac5bc2daee2dec301aac508f9befc27fae4a2665e82f13b1ddd17d3a0c85740bed8d53eeda665a5fc1bed35fbbcedd4279d04aa747ac1f996f724b14f0228366aeae34305152e1f430221f9594497686c9f49021d833144962c2a53dbb47bdbfd19785ad8da6e7b59be24d34ed201384d3b0f34267df4ba8b53f0f4481f9bd2e26c4a3e95cd1a47f806a1f16b86a9fc5e8a0756898f63f5c9144f51b401ba0dd5ad58fb0e97ebac9a41dc3fb4a378707f7210e64c131bca19bd54e39bbfa0d7a0e7c89d955b1c9f
e = 0x10001
c = 0x3dbf00a02f924a70f44bdd69e73c46241e9f036bfa49a0c92659d8eb0fe47e42068eaf156a9b3ee81651bc0576a91ffed48610c158dc8d2fb1719c7242704f0d965f8798304925a322c121904b91e5fc5eb3dc960b03eb8635be53b995217d4c317126e0ec6e9a9acfd5d915265634a22a612de962cfaa2e0443b78bdf841ff901423ef765e3d98b38bcce114fede1f13e223b9bd8155e913c8670d8b85b1f3bcb99353053cdb4aef1bf16fa74fd81e42325209c0953a694636c0ce0a19949f343dc229b2b7d80c3c43ebe80e89cbe3a3f7c867fd7cee06943886b0718a4a3584c9d9f9a66c9de29fda7cfee30ad3db061981855555eeac01940b1924eb4c301
p = 57970027
q = 518629368090170828331048663550229634444384299751272939077168648935075604180676006392464524953128293842996441022771890719731811852948684950388211907532651941639114462313594608747413310447500790775078081191686616804987790818396104388332734677935684723647108960882771460341293023764117182393730838418468480006985768382115446225422781116531906323045161803441960506496275763429558238732127362521949515590606221409745127192859630468854653290302491063292735496286233738504010613373838035073995140744724948933839238851600638652315655508861728439180988253324943039367876070687033249730660337593825389358874152757864093

phi_n = (p - 1) * (q - 1)
# d = hex(gmpy2.invert(e, phi_n))
# print(d)
d = 0x9186c78d098af6815622ea9901cf84a89ead578a6dbdded7d7fc63531756239dc586501216fc2e4bd1a8cee7e62284d16d91195f356d733a52dff011ebc3bf1e5d62af54d0455ea2f6ec948f45f34931f5b0b4478b16c66951a95d2f069a6c8867a6bc673c8e40052a54dbc5c1aeacbbfae7cad150a4f41ef4a02b1c97d70636ae187ed3c45f2551696a6a1172ae4089e033fb4853057c0f1e227d71ccf24fb27073ca4fe4ac3744dfed2cd7763c47ac4ae4d42820a19d68961bc103bb9016197463875169d062b45807e2e86aa17fa65e3088cc75ef35f984d0ca92d4c9270c2e694eb1f5df16b7ebe32b5c1d26086d6aac5fe327288f2904cb54164db39151
flag = a2b_hex(hex(pow(c,d,n))[2:])
print(flag)

已知c、e，求解明文

首先通过公钥文件public.pem获取n、e

通过公钥文件获取n、e

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

public = RSA.importKey(open("./RSA/public.pem").read())
n = public.n
e = public.e
print("n=\n%s\ne=\n%s"%(n,e))

n=
74207624142945242263057035287110983967646020057307828709587969646701361764263
e=
65537

通过在线网站
http://www.factordb.com/index.php?query=74207624142945242263057035287110983967646020057307828709587969646701361764263 分解n
可以得到p=258631601377848992211685134376492365269以及q=286924040788547268861394901519826758027

n=
74207624142945242263057035287110983967646020057307828709587969646701361764263
e=
65537

通过在线网站
http://www.factordb.com/index.php?query=74207624142945242263057035287110983967646020057307828709587969646701361764263 分解n
可以得到p=258631601377848992211685134376492365269以及q=286924040788547268861394901519826758027

生成私钥

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

from Crypto.PublicKey import RSA

keypair = RSA.generate(1024)
keypair.p = 258631601377848992211685134376492365269
keypair.q = 286924040788547268861394901519826758027
keypair.e = 65537
keypair.n = keypair.p * keypair.q
phi_n = (keypair.p-1) * (keypair.q-1)

i = 1
while (True):
        x = (phi_n * i ) + 1
        if (x % keypair.e == 0):
            keypair.d = x / keypair.e
            break
        i += 1

private = open('private.pem','w')
private.write(keypair.exportKey())
private.close()

最后使用生成的私钥将加密文件解密

1
openssl rsautl -decrypt -in ./RSA/flag.enc -inkey private.pem -out flag.txt

求解d

求解d一般的除了可以利用gmpy2模块的gmpy2.invert(e,phi_n)函数之外，还可以利用 扩展欧几里德算法计算出d，以下是python的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#coding:utf-8      
                   
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):  
    #d=modinv(e,(p-1)*(q-1))
	
    g, x, y = egcd(a, m)    
    if g != 1:     
       raise Exception('modular inverse does not exist')
    else:          
       return x % m
关注我

链接

归档

分类

最新文章

标签

CTF14
CVEs1
Computer Network2
Crypto1
DN421
HAM5
HackTheBox2
Hacking6
Hardware4
Music1
OS3
Pwn1
Red Team3
Tetris1
WEB31
Web Security2
Writeup14
开箱1
随笔7
×