首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 峰会 看雪商城 证书查询
  1. 社区
  2. CTF对抗
    3. 发新帖
[求助]求解一个简单的RSA的题目
发表于: 2023-9-27 15:38 5391

[求助]求解一个简单的RSA的题目

tfll 活跃值
2023-9-27 15:38
5391
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
from Crypto.Util.number import *
import gmpy2
from jx2023 import flag, N, E
 
p = getPrime(1024)
q = getPrime(1024)
n = p*q
e1 = 65537
m = bytes_to_long(flag)
flagenc = pow(m, e1, n)
print("n is %d"%n)
print("flagenc is %d"%flagenc)
 
e2 = getPrime(122)
d2 = gmpy2.invert(e2,(p-1)*(q-1))
 
c1 = pow(e2, 17, n)
print("c1 is %d"%c1)
c2 = pow(d2, E, N)
print("N is %d"%N)
print("E is %d"%E)
print("c2 is %d"%c2)
 
# n is 8783117353228609820060025773720048836109116296720444291318682193328216575376903671782151675801584925066872219021319381163804239505579013818679255656402117567158378369967703317919205364480806143209934093723468591544792794708122025724968669241594029740047941933910596214170603520800531302474255823072859735679699558933009869241259760910402379740926512037606096020308081609477145816657118917642443176163860564823645522254412566891344745856141731910712040298787696382973824645074768059896153817964229975814742137600918515702471008251376697190058997187350022140633621955761877009643524289144711721902192261617574896449017
 
# flagenc is 1832021020586052459314800741399454951500982061634041208695770794636942946870944684781204845687614819955481692885982545657535952608100558061853098768890990198808258902800083671402999197944855469054517686346352932015639347886120547093778527571008483890754044661117042113616196224634409728684137167049242919543742476300792865668127981523314258326046469003175979484948578219765126696355000799390683333335678236115175267218556919253045561467791607635318317825080003594243366362225620291777807071774013296604063473075790067769213249767073197915283384750139985842145668772180552896467043807903712438253502782564391233381742
 
# c1 is 7501185876834032332235110133210399479682524972321262801050956129090974843598848916000280794969942298848478394986779571489577405391165372124215072990382219817624500948789393550575823082225944683449240150364401487955484843961943987266467050723988657081468393104862383181698999645914573683498375228946881234015678337769955671069215094086232377038727627179660862997067062391991524231807127953937881102711759932207432989764529075450526104070640765094626829603546052250863300827172150912585791552174463067989228539713261075253602907390439036055716154404417991482262846355144755622306307102084492476950657455416297047328320
 
# N is 29956031606905964747690208452463077877156885038545111351508842927295510069375356079358289621922278316223452695576175299757472345749152582617292471487006177231261463793638998998552474423214925625798531662484883149899251884707864709821973208465998076621327151198438158796296778838657562126343551661323471767755161686549607991960624754677443327266743771304424298446433734879681913848286620429175461870451099771965936783237191184798864363652633155779478727580408625494617809961465590055999661472563150275608218351797354628429061984878432442357241449134341597647749840966740944318445550768334070331490455379767889443973947
 
# E is 3527492693
 
# c2 is 11237333233288323887902003767693284822911839921763421974808265907264411495367936669799604082222415065052099486867383635886650443299459413288200494593477575168578514325691333043832168789236017314435940348619410775859032696755081680003338452277759483862961120696587307757666691557048088894021864124052243936836752825473836552342254367444581003605318145868368417247224184184040226260236268012375524575700053732026218766291274077482132408824236096242385408780811520890742688121731805867574680433796282417791570436991022839930635640379142355212121030479526679958801911687722402447690578345774902440346290388183936888977900

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课

最后于 2023-9-27 15:41 被tfll编辑 ，原因：
收藏
免费 ・0
支持
分享
最新回复 (11)
hypersine
雪    币： 267
活跃值： (625)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
2 楼
这个应该还是很好办的

N是一个不安全的大合数，可以用yafu快速分解得到P, Q
因此可以算出E对应的D，从而解密c2得到d2

c1 = pow(e2, 17, n)，但e2是一个122位的质数，因此e2^17应该有122 * 17 = 2074位，太接近于n的2048位。这里可以暴力破解，因为c1 = pow(e2, 17, n)，所以存在k使得e2^17 == k * n + c1，这个k范围不大，不超过2^(2074 - 2048 + 1) = 2^27，自己写个程序穷举k就好，穷举到k * n + c1是一个完全17次方数就行，然后开17次方得到e2

现在知道d2, e2那就能分解n了，自己写个程序分解n得到p、q，最后解密flagenc


2023-9-27 19:32
1
scz
雪    币： 4834
活跃值： (3832)
能力值： ( LV12，RANK：230 )
在线值：
发帖
回帖
粉丝
私信
3 楼
2楼说得太清楚了，我第一次听说yafu，谢谢。照着2楼的做了一遍

b'flag{616fa39c8781aa45031e15651228489a}'
2023-9-29 16:55
0
tDasm
雪    币： 14865
活跃值： (6088)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
4 楼
hypersine 这个应该还是很好办的 N是一个不安全的大合数，可以用yafu快速分解得到P, Q 因此可以算出E对应的D，从而解密c2得到d2 c1 = pow(e2, 17, n)，但e2是一个122 ...
你知道分解1024位及以上N要多久吗？
2023-9-30 06:31
0
hypersine
雪    币： 267
活跃值： (625)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
5 楼
tDasm 你知道分解1024位及以上N要多久吗？
要看情况，题目中的N它的两个因数P、Q靠得太近了，两者之差好像不超过10000，所以很容易分解。但如果是安全的N，分解就别想了，个人不可能有那么多资源在有限时间内分解的。
2023-9-30 10:18
0
tDasm
雪    币： 14865
活跃值： (6088)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
6 楼
hypersine 要看情况，题目中的N它的两个因数P、Q靠得太近了，两者之差好像不超过10000，所以很容易分解。但如果是安全的N，分解就别想了，个人不可能有那么多资源在有限时间内分解的。
你从哪里看出P、Q靠得近？应该都是随机数产生。也许是我见识少，如果P、Q靠得近怎么使分解更容易？因为即便1024位，P、Q靠近的组合也有无数个
2023-9-30 13:40
0
hypersine
雪    币： 267
活跃值： (625)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
7 楼
tDasm 你从哪里看出P、Q靠得近？应该都是随机数产生。也许是我见识少，如果P、Q靠得近怎么使分解更容易？因为即便1024位，P、Q靠近的组合也有无数个
所以这就是ctf题目的特点，很多东西需要试一试。比如见到一个大数N，用yafu分解一段时间看看能不能找到一个因数，或者去factordb查下有没有人已经分解出了该数。试一试才会有惊喜。这个题目的N估计是出题人故意挑了两个比较近的两个质数。

如果P、Q很近，那么你对N开方得到sqrt(N)，接着往sqrt(N)下面穷举，很快就能找到因数

2023-9-30 14:04
0
mb_pygwwatg
雪    币：
能力值： ( LV1，RANK：0 )
在线值：
发帖
回帖
粉丝
私信
8 楼

@tDasm   这位我感觉你需要看看心理医生，这是一个友善的建议。我看了你的大部分回复，发现你和人交流充满了戾气，几乎每个回复都带着反问和不友善的心态。

最后于 2023-9-30 15:07 被mb_pygwwatg编辑 ，原因：
2023-9-30 15:02
0
tDasm
雪    币： 14865
活跃值： (6088)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
9 楼
hypersine 所以这就是ctf题目的特点，很多东西需要试一试。比如见到一个大数N，用yafu分解一段时间看看能不能找到一个因数，或者去factordb查下有没有人已经分解出了该数。试一试才会有惊喜。这个题目的N估计 ...
学习了，以前用RSA都是随机产生P、Q，没有检查二个素数是否靠的太近。
2023-9-30 15:21
0
tfll
雪    币： 419
活跃值： (770)
能力值： ( LV2，RANK：15 )
在线值：
发帖
回帖
粉丝
私信
10 楼
谢谢2楼的解答，学习了。
2023-9-30 21:12
0
mb_lxcelyzd
雪    币：
能力值： ( LV1，RANK：0 )
在线值：
发帖
回帖
粉丝
私信
11 楼
scz 2楼说得太清楚了，我第一次听说yafu，谢谢。照着2楼的做了一遍 b'flag{616fa39c8781aa45031e15651228489a}'
可以发一下代码吗？我没找到k
2023-10-2 19:57
0
scz
雪    币： 4834
活跃值： (3832)
能力值： ( LV12，RANK：230 )
在线值：
发帖
回帖
粉丝
私信
12 楼
mb_lxcelyzd 可以发一下代码吗？我没找到k
https://bbs.kanxue.com/thread-279074.htm
2023-10-3 11:15
0
游客
登录 | 注册 方可回帖
回帖 表情 雪币赚取及消费
高级回复
返回
//